[OpenMP] Avoid remainder operations for loop index values on a collapsed loop nest.
Summary: Change the strategy for computing loop index variables after collapsing a loop nest via the collapse clause by replacing the expensive remainder operation with multiplications and additions.
Reviewers: ABataev, caomhin
Reviewed By: ABataev
Subscribers: guansong, arphaman, cfe-commits
Differential Revision: https://reviews.llvm.org/D56413
llvm-svn: 350759
diff --git a/clang/lib/Sema/SemaOpenMP.cpp b/clang/lib/Sema/SemaOpenMP.cpp
index 89eb2e2..36048a3 100644
--- a/clang/lib/Sema/SemaOpenMP.cpp
+++ b/clang/lib/Sema/SemaOpenMP.cpp
@@ -5579,31 +5579,59 @@
Built.Updates.resize(NestedLoopCount);
Built.Finals.resize(NestedLoopCount);
{
- ExprResult Div;
- // Go from inner nested loop to outer.
- for (int Cnt = NestedLoopCount - 1; Cnt >= 0; --Cnt) {
+ // We implement the following algorithm for obtaining the
+ // original loop iteration variable values based on the
+ // value of the collapsed loop iteration variable IV.
+ //
+ // Let n+1 be the number of collapsed loops in the nest.
+ // Iteration variables (I0, I1, .... In)
+ // Iteration counts (N0, N1, ... Nn)
+ //
+ // Acc = IV;
+ //
+ // To compute Ik for loop k, 0 <= k <= n, generate:
+ // Prod = N(k+1) * N(k+2) * ... * Nn;
+ // Ik = Acc / Prod;
+ // Acc -= Ik * Prod;
+ //
+ ExprResult Acc = IV;
+ for (unsigned int Cnt = 0; Cnt < NestedLoopCount; ++Cnt) {
LoopIterationSpace &IS = IterSpaces[Cnt];
SourceLocation UpdLoc = IS.IncSrcRange.getBegin();
- // Build: Iter = (IV / Div) % IS.NumIters
- // where Div is product of previous iterations' IS.NumIters.
ExprResult Iter;
- if (Div.isUsable()) {
- Iter =
- SemaRef.BuildBinOp(CurScope, UpdLoc, BO_Div, IV.get(), Div.get());
- } else {
- Iter = IV;
- assert((Cnt == (int)NestedLoopCount - 1) &&
- "unusable div expected on first iteration only");
- }
- if (Cnt != 0 && Iter.isUsable())
- Iter = SemaRef.BuildBinOp(CurScope, UpdLoc, BO_Rem, Iter.get(),
- IS.NumIterations);
+ // Compute prod
+ ExprResult Prod =
+ SemaRef.ActOnIntegerConstant(SourceLocation(), 1).get();
+ for (unsigned int K = Cnt+1; K < NestedLoopCount; ++K)
+ Prod = SemaRef.BuildBinOp(CurScope, UpdLoc, BO_Mul, Prod.get(),
+ IterSpaces[K].NumIterations);
+
+ // Iter = Acc / Prod
+ // If there is at least one more inner loop to avoid
+ // multiplication by 1.
+ if (Cnt + 1 < NestedLoopCount)
+ Iter = SemaRef.BuildBinOp(CurScope, UpdLoc, BO_Div,
+ Acc.get(), Prod.get());
+ else
+ Iter = Acc;
if (!Iter.isUsable()) {
HasErrors = true;
break;
}
+ // Update Acc:
+ // Acc -= Iter * Prod
+ // Check if there is at least one more inner loop to avoid
+ // multiplication by 1.
+ if (Cnt + 1 < NestedLoopCount)
+ Prod = SemaRef.BuildBinOp(CurScope, UpdLoc, BO_Mul,
+ Iter.get(), Prod.get());
+ else
+ Prod = Iter;
+ Acc = SemaRef.BuildBinOp(CurScope, UpdLoc, BO_Sub,
+ Acc.get(), Prod.get());
+
// Build update: IS.CounterVar(Private) = IS.Start + Iter * IS.Step
auto *VD = cast<VarDecl>(cast<DeclRefExpr>(IS.CounterVar)->getDecl());
DeclRefExpr *CounterVar = buildDeclRefExpr(
@@ -5632,22 +5660,6 @@
break;
}
- // Build Div for the next iteration: Div <- Div * IS.NumIters
- if (Cnt != 0) {
- if (Div.isUnset())
- Div = IS.NumIterations;
- else
- Div = SemaRef.BuildBinOp(CurScope, UpdLoc, BO_Mul, Div.get(),
- IS.NumIterations);
-
- // Add parentheses (for debugging purposes only).
- if (Div.isUsable())
- Div = tryBuildCapture(SemaRef, Div.get(), Captures);
- if (!Div.isUsable()) {
- HasErrors = true;
- break;
- }
- }
if (!Update.isUsable() || !Final.isUsable()) {
HasErrors = true;
break;