Refactor division generation code

  This patch refactors the code generation for divisions. This allows to
  always generate a shift for a power-of-two division and to utilize
  information about constant divisors in order to truncate the result
  type.

llvm-svn: 271898

4 files changed, 78 insertions, 37 deletions

diff --git a/polly/include/polly/CodeGen/IslExprBuilder.h b/polly/include/polly/CodeGen/IslExprBuilder.h
index f357569e998..bd9806d08cc 100644
--- a/polly/include/polly/CodeGen/IslExprBuilder.h
+++ b/polly/include/polly/CodeGen/IslExprBuilder.h
@@ -204,6 +204,9 @@ private:
   llvm::Value *createOpAddressOf(__isl_take isl_ast_expr *Expr);
   llvm::Value *createAccessAddress(__isl_take isl_ast_expr *Expr);
 
+  /// @brief Supported kinds of division.
+  enum DivisionMode { DM_SIGNED, DM_UNSIGNED, DM_FLOORED };
+
   /// @brief Create a binary operation @p Opc and track overflows if requested.
   ///
   /// @param OpC  The binary operation that should be performed [Add/Sub/Mul].
@@ -216,6 +219,15 @@ private:
                            llvm::Value *LHS, llvm::Value *RHS,
                            const llvm::Twine &Name);
 
+  /// @brief Create a division and adjust the result type if possible.
+  ///
+  /// @param LHS The left operand.
+  /// @param RHS The right operand.
+  /// @param DM  The requested division mode.
+  ///
+  /// @return A value that represents the result of the division.
+  llvm::Value *createDiv(llvm::Value *LHS, llvm::Value *RHS, DivisionMode DM);
+
   /// @brief Create an addition and track overflows if requested.
   ///
   /// @param LHS  The left operand.
diff --git a/polly/lib/CodeGen/IslExprBuilder.cpp b/polly/lib/CodeGen/IslExprBuilder.cpp
index b2bfbf9b363..069e23df7b5 100644
--- a/polly/lib/CodeGen/IslExprBuilder.cpp
+++ b/polly/lib/CodeGen/IslExprBuilder.cpp
@@ -318,6 +318,48 @@ Value *IslExprBuilder::createOpAccess(isl_ast_expr *Expr) {
   return Builder.CreateLoad(Addr, Addr->getName() + ".load");
 }
 
+Value *IslExprBuilder::createDiv(Value *LHS, Value *RHS, DivisionMode DM) {
+  auto *ConstRHS = dyn_cast<ConstantInt>(RHS);
+  unsigned UnusedBits = 0;
+  Value *Res = nullptr;
+
+  if (ConstRHS)
+    UnusedBits = ConstRHS->getValue().logBase2();
+
+  if (ConstRHS && ConstRHS->getValue().isPowerOf2() &&
+      ConstRHS->getValue().isNonNegative())
+    Res = Builder.CreateAShr(LHS, UnusedBits, "polly.div.shr");
+  else if (DM == DM_SIGNED)
+    Res = Builder.CreateSDiv(LHS, RHS, "pexp.div", true);
+  else if (DM == DM_UNSIGNED)
+    Res = Builder.CreateUDiv(LHS, RHS, "pexp.p_div_q");
+  else {
+    assert(DM == DM_FLOORED);
+    // TODO: Review code and check that this calculation does not yield
+    //       incorrect overflow in some bordercases.
+    //
+    // floord(n,d) ((n < 0) ? (n - d + 1) : n) / d
+    Value *Sum1 = createSub(LHS, RHS, "pexp.fdiv_q.0");
+    Value *One = ConstantInt::get(Sum1->getType(), 1);
+    Value *Sum2 = createAdd(Sum1, One, "pexp.fdiv_q.1");
+    Value *Zero = ConstantInt::get(LHS->getType(), 0);
+    Value *isNegative = Builder.CreateICmpSLT(LHS, Zero, "pexp.fdiv_q.2");
+    unifyTypes(LHS, Sum2);
+    Value *Dividend =
+        Builder.CreateSelect(isNegative, Sum2, LHS, "pexp.fdiv_q.3");
+    unifyTypes(Dividend, RHS);
+    Res = Builder.CreateSDiv(Dividend, RHS, "pexp.fdiv_q.4");
+  }
+
+  if (UnusedBits) {
+    auto RequiredBits = Res->getType()->getPrimitiveSizeInBits() - UnusedBits;
+    Res = Builder.CreateTrunc(Res, Builder.getIntNTy(RequiredBits),
+                              "polly.div.trunc");
+  }
+
+  return Res;
+}
+
 Value *IslExprBuilder::createOpBin(__isl_take isl_ast_expr *Expr) {
   Value *LHS, *RHS, *Res;
   isl_ast_op_type OpType;
@@ -364,39 +406,17 @@ Value *IslExprBuilder::createOpBin(__isl_take isl_ast_expr *Expr) {
     Res = createMul(LHS, RHS);
     break;
   case isl_ast_op_div:
-    Res = Builder.CreateSDiv(LHS, RHS, "pexp.div", true);
+    Res = createDiv(LHS, RHS, DM_SIGNED);
     break;
   case isl_ast_op_pdiv_q: // Dividend is non-negative
-    Res = Builder.CreateUDiv(LHS, RHS, "pexp.p_div_q");
+    Res = createDiv(LHS, RHS, DM_UNSIGNED);
     break;
-  case isl_ast_op_fdiv_q: { // Round towards -infty
-    if (auto *Const = dyn_cast<ConstantInt>(RHS)) {
-      auto &Val = Const->getValue();
-      if (Val.isPowerOf2() && Val.isNonNegative()) {
-        Res = Builder.CreateAShr(LHS, Val.ceilLogBase2(), "polly.fdiv_q.shr");
-        break;
-      }
-    }
-    // TODO: Review code and check that this calculation does not yield
-    //       incorrect overflow in some bordercases.
-    //
-    // floord(n,d) ((n < 0) ? (n - d + 1) : n) / d
-    Value *Sum1 = createSub(LHS, RHS, "pexp.fdiv_q.0");
-    Value *One = ConstantInt::get(Sum1->getType(), 1);
-    Value *Sum2 = createAdd(Sum1, One, "pexp.fdiv_q.1");
-    Value *Zero = ConstantInt::get(LHS->getType(), 0);
-    Value *isNegative = Builder.CreateICmpSLT(LHS, Zero, "pexp.fdiv_q.2");
-    unifyTypes(LHS, Sum2);
-    Value *Dividend =
-        Builder.CreateSelect(isNegative, Sum2, LHS, "pexp.fdiv_q.3");
-    unifyTypes(Dividend, RHS);
-    Res = Builder.CreateSDiv(Dividend, RHS, "pexp.fdiv_q.4");
+  case isl_ast_op_fdiv_q: // Round towards -infty
+    Res = createDiv(LHS, RHS, DM_FLOORED);
     break;
-  }
   case isl_ast_op_pdiv_r: // Dividend is non-negative
     Res = Builder.CreateURem(LHS, RHS, "pexp.pdiv_r");
     break;
-
   case isl_ast_op_zdiv_r: // Result only compared against zero
     Res = Builder.CreateSRem(LHS, RHS, "pexp.zdiv_r");
     break;
diff --git a/polly/test/Isl/CodeGen/exprModDiv.ll b/polly/test/Isl/CodeGen/exprModDiv.ll
index 56e1e7b93d6..7453a93cff0 100644
--- a/polly/test/Isl/CodeGen/exprModDiv.ll
+++ b/polly/test/Isl/CodeGen/exprModDiv.ll
@@ -28,7 +28,8 @@
 ;       each value of i to indeed be mapped to a value.
 ;
 ; CHECK:  %pexp.p_div_q = udiv i64 %polly.indvar, 127
-; CHECK:  %polly.access.B{{[0-9]*}} = getelementptr float, float* %B, i64 %pexp.p_div_q
+; CHECK:  %polly.div.trunc = trunc i64 %pexp.p_div_q to i58
+; CHECK:  %polly.access.B{{[0-9]*}} = getelementptr float, float* %B, i58 %polly.div.trunc
 
 ; #define floord(n,d) ((n < 0) ? (n - d + 1) : n) / d
 ; A[p + 127 * floord(-p - 1, 127) + 127]
@@ -37,32 +38,39 @@
 ; CHECK:  %pexp.fdiv_q.2 = icmp slt i64 %p, 0
 ; CHECK:  %pexp.fdiv_q.3 = select i1 %pexp.fdiv_q.2, i64 %pexp.fdiv_q.1, i64 %p
 ; CHECK:  %pexp.fdiv_q.4 = sdiv i64 %pexp.fdiv_q.3, 127
-; CHECK:  %[[r1:[0-9]*]] = mul nsw i64 127, %pexp.fdiv_q.4
+; CHECK:  %polly.div.trunc1 = trunc i64 %pexp.fdiv_q.4 to i58
+; CHECK:  %[[r0:[0-9]*]] = sext i58 %polly.div.trunc1 to i64
+; CHECK:  %[[r1:[0-9]*]] = mul nsw i64 127, %[[r0]]
 ; CHECK:  %[[r2:[0-9]*]] = sub nsw i64 %p, %[[r1]]
 ; CHECK:  %polly.access.A{{[0-9]*}} = getelementptr float, float* %A, i64 %[[r2]]
 
 ; A[p / 127]
 ; CHECK:  %pexp.div = sdiv exact i64 %p, 127
-; CHECK:  %polly.access.B{{[0-9]*}} = getelementptr float, float* %B, i64 %pexp.div
+; CHECK:  %polly.div.trunc3 = trunc i64 %pexp.div to i58
+; CHECK:  %polly.access.B{{[0-9]*}} = getelementptr float, float* %B, i58 %polly.div.trunc3
 
 ; A[i % 128]
 ; POW2:  %pexp.pdiv_r = urem i64 %polly.indvar, 128
 ; POW2:  %polly.access.A{{[0-9]*}} = getelementptr float, float* %A, i64 %pexp.pdiv_r
 
 ; A[floor(i / 128)]
-; POW2:  %pexp.p_div_q = udiv i64 %polly.indvar, 128
-; POW2:  %polly.access.B{{[0-9]*}} = getelementptr float, float* %B, i64 %pexp.p_div_q
+; POW2:  %polly.div.shr = ashr i64 %polly.indvar, 7
+; POW2:  %polly.div.trunc = trunc i64 %polly.div.shr to i57
+; POW2:  %polly.access.B{{[0-9]*}} = getelementptr float, float* %B, i57 %polly.div.trunc
 
 ; #define floord(n,d) ((n < 0) ? (n - d + 1) : n) / d
 ; A[p + 128 * floord(-p - 1, 128) + 128]
-; POW2:  %polly.fdiv_q.shr = ashr i64 %p, 7
-; POW2:  %[[r1:[0-9]*]] = mul nsw i64 128, %polly.fdiv_q.shr
+; POW2:  %polly.div.shr1 = ashr i64 %p, 7
+; POW2:  %polly.div.trunc2 = trunc i64 %polly.div.shr1 to i57
+; POW2:  %[[r0:[0-9]*]] = sext i57 %polly.div.trunc2 to i64
+; POW2:  %[[r1:[0-9]*]] = mul nsw i64 128, %[[r0]]
 ; POW2:  %[[r2:[0-9]*]] = sub nsw i64 %p, %[[r1]]
 ; POW2:  %polly.access.A{{[0-9]*}} = getelementptr float, float* %A, i64 %[[r2]]
 
 ; A[p / 128]
-; POW2:  %pexp.div = sdiv exact i64 %p, 128
-; POW2:  %polly.access.B{{[0-9]*}} = getelementptr float, float* %B, i64 %pexp.div
+; POW2:  %polly.div.shr4 = ashr i64 %p, 7
+; POW2:  %polly.div.trunc5 = trunc i64 %polly.div.shr4 to i57
+; POW2:  %polly.access.B{{[0-9]*}} = getelementptr float, float* %B, i57 %polly.div.trunc5
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 
diff --git a/polly/test/Isl/CodeGen/invariant_load_escaping_second_scop.ll b/polly/test/Isl/CodeGen/invariant_load_escaping_second_scop.ll
index 042aaf2ee04..d4cef143732 100644
--- a/polly/test/Isl/CodeGen/invariant_load_escaping_second_scop.ll
+++ b/polly/test/Isl/CodeGen/invariant_load_escaping_second_scop.ll
@@ -19,8 +19,9 @@
 ;    }
 ;
 ; CHECK: polly.stmt.stmt.P:
-; CHECK:   %polly.fdiv_q.shr = ashr i32 %tmp.merge, 1
-; CHECL:   sext i32 %polly.fdiv_q.shr to i33
+; CHECK:   %polly.div.shr = ashr i32 %tmp.merge, 1
+; CHECK:   %polly.div.trunc = trunc i32 %polly.div.shr to i31
+; CHECK:   sext i31 %polly.div.trunc to i32
 ;
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"