1 files changed, 163 insertions, 143 deletions

diff --git a/polly/lib/CodeGen/IslExprBuilder.cpp b/polly/lib/CodeGen/IslExprBuilder.cpp
index 069e23df7b5..62c166f7b66 100644
--- a/polly/lib/CodeGen/IslExprBuilder.cpp
+++ b/polly/lib/CodeGen/IslExprBuilder.cpp
@@ -39,12 +39,6 @@ static cl::opt<OverflowTrackingChoice> OTMode(
                clEnumValEnd),
     cl::Hidden, cl::init(OT_REQUEST), cl::ZeroOrMore, cl::cat(PollyCategory));
 
-// @TODO This should actually be derived from the DataLayout.
-static cl::opt<unsigned> PollyMaxAllowedBitWidth(
-    "polly-max-expr-bit-width",
-    cl::desc("The maximal bit with for generated expressions."), cl::Hidden,
-    cl::ZeroOrMore, cl::init(64), cl::cat(PollyCategory));
-
 IslExprBuilder::IslExprBuilder(Scop &S, PollyIRBuilder &Builder,
                                IDToValueTy &IDToValue, ValueMapT &GlobalMap,
                                const DataLayout &DL, ScalarEvolution &SE,
@@ -80,23 +74,8 @@ Value *IslExprBuilder::getOverflowState() const {
 
 Value *IslExprBuilder::createBinOp(BinaryOperator::BinaryOps Opc, Value *LHS,
                                    Value *RHS, const Twine &Name) {
-  // Flag that is true if the computation cannot overflow.
-  bool IsSafeToCompute = false;
-  switch (Opc) {
-  case Instruction::Add:
-  case Instruction::Sub:
-    IsSafeToCompute = adjustTypesForSafeAddition(LHS, RHS);
-    break;
-  case Instruction::Mul:
-    IsSafeToCompute = adjustTypesForSafeMultiplication(LHS, RHS);
-    break;
-  default:
-    llvm_unreachable("Unknown binary operator!");
-  }
-
-  // Handle the plain operation (without overflow tracking or a safe
-  // computation) first.
-  if (!OverflowState || (IsSafeToCompute && (OTMode != OT_ALWAYS))) {
+  // Handle the plain operation (without overflow tracking) first.
+  if (!OverflowState) {
     switch (Opc) {
     case Instruction::Add:
       return Builder.CreateNSWAdd(LHS, RHS, Name);
@@ -158,7 +137,7 @@ Value *IslExprBuilder::createMul(Value *LHS, Value *RHS, const Twine &Name) {
   return createBinOp(Instruction::Mul, LHS, RHS, Name);
 }
 
-static Type *getWidestType(Type *T1, Type *T2) {
+Type *IslExprBuilder::getWidestType(Type *T1, Type *T2) {
   assert(isa<IntegerType>(T1) && isa<IntegerType>(T2));
 
   if (T1->getPrimitiveSizeInBits() < T2->getPrimitiveSizeInBits())
@@ -167,63 +146,23 @@ static Type *getWidestType(Type *T1, Type *T2) {
     return T1;
 }
 
-void IslExprBuilder::unifyTypes(Value *&V0, Value *&V1, Value *&V2) {
-  auto *T0 = V0->getType();
-  auto *T1 = V1->getType();
-  auto *T2 = V2->getType();
-  if (T0 == T1 && T1 == T2)
-    return;
-  auto *MaxT = getWidestType(T0, T1);
-  MaxT = getWidestType(MaxT, T2);
-  V0 = Builder.CreateSExt(V0, MaxT);
-  V1 = Builder.CreateSExt(V1, MaxT);
-  V2 = Builder.CreateSExt(V2, MaxT);
-}
-
-bool IslExprBuilder::adjustTypesForSafeComputation(Value *&LHS, Value *&RHS,
-                                                   unsigned RequiredBitWidth) {
-  unsigned LBitWidth = LHS->getType()->getPrimitiveSizeInBits();
-  unsigned RBitWidth = RHS->getType()->getPrimitiveSizeInBits();
-  unsigned MaxUsedBitWidth = std::max(LBitWidth, RBitWidth);
-
-  // @TODO For now use the maximal bit width if the required one is to large but
-  //       note that this is not sound.
-  unsigned MaxAllowedBitWidth = PollyMaxAllowedBitWidth;
-  unsigned NewBitWidth =
-      std::max(MaxUsedBitWidth, std::min(MaxAllowedBitWidth, RequiredBitWidth));
-
-  Type *Ty = Builder.getIntNTy(NewBitWidth);
-  LHS = Builder.CreateSExt(LHS, Ty);
-  RHS = Builder.CreateSExt(RHS, Ty);
-
-  // If the new bit width is not large enough the computation is not sound.
-  return NewBitWidth == RequiredBitWidth;
-}
-
-bool IslExprBuilder::adjustTypesForSafeAddition(Value *&LHS, Value *&RHS) {
-  unsigned LBitWidth = LHS->getType()->getPrimitiveSizeInBits();
-  unsigned RBitWidth = RHS->getType()->getPrimitiveSizeInBits();
-  return adjustTypesForSafeComputation(LHS, RHS,
-                                       std::max(LBitWidth, RBitWidth) + 1);
-}
-
-bool IslExprBuilder::adjustTypesForSafeMultiplication(Value *&LHS,
-                                                      Value *&RHS) {
-  unsigned LBitWidth = LHS->getType()->getPrimitiveSizeInBits();
-  unsigned RBitWidth = RHS->getType()->getPrimitiveSizeInBits();
-  return adjustTypesForSafeComputation(LHS, RHS, LBitWidth + RBitWidth);
-}
-
 Value *IslExprBuilder::createOpUnary(__isl_take isl_ast_expr *Expr) {
   assert(isl_ast_expr_get_op_type(Expr) == isl_ast_op_minus &&
          "Unsupported unary operation");
 
-  auto *V = create(isl_ast_expr_get_op_arg(Expr, 0));
-  assert(V->getType()->isIntegerTy() &&
+  Value *V;
+  Type *MaxType = getType(Expr);
+  assert(MaxType->isIntegerTy() &&
          "Unary expressions can only be created for integer types");
 
+  V = create(isl_ast_expr_get_op_arg(Expr, 0));
+  MaxType = getWidestType(MaxType, V->getType());
+
+  if (MaxType != V->getType())
+    V = Builder.CreateSExt(V, MaxType);
+
   isl_ast_expr_free(Expr);
-  return createSub(ConstantInt::getNullValue(V->getType()), V);
+  return createSub(ConstantInt::getNullValue(MaxType), V);
 }
 
 Value *IslExprBuilder::createOpNAry(__isl_take isl_ast_expr *Expr) {
@@ -231,20 +170,44 @@ Value *IslExprBuilder::createOpNAry(__isl_take isl_ast_expr *Expr) {
          "isl ast expression not of type isl_ast_op");
   assert(isl_ast_expr_get_op_n_arg(Expr) >= 2 &&
          "We need at least two operands in an n-ary operation");
-  assert((isl_ast_expr_get_op_type(Expr) == isl_ast_op_max ||
-          isl_ast_expr_get_op_type(Expr) == isl_ast_op_min) &&
-         "This is no n-ary isl ast expression");
-
-  bool IsMax = isl_ast_expr_get_op_type(Expr) == isl_ast_op_max;
-  auto Pred = IsMax ? CmpInst::ICMP_SGT : CmpInst::ICMP_SLT;
-  auto *V = create(isl_ast_expr_get_op_arg(Expr, 0));
-
-  for (int i = 1; i < isl_ast_expr_get_op_n_arg(Expr); ++i) {
-    auto *OpV = create(isl_ast_expr_get_op_arg(Expr, i));
-    unifyTypes(V, OpV);
-    V = Builder.CreateSelect(Builder.CreateICmp(Pred, V, OpV), V, OpV);
+
+  Value *V;
+
+  V = create(isl_ast_expr_get_op_arg(Expr, 0));
+
+  for (int i = 0; i < isl_ast_expr_get_op_n_arg(Expr); ++i) {
+    Value *OpV;
+    OpV = create(isl_ast_expr_get_op_arg(Expr, i));
+
+    Type *Ty = getWidestType(V->getType(), OpV->getType());
+
+    if (Ty != OpV->getType())
+      OpV = Builder.CreateSExt(OpV, Ty);
+
+    if (Ty != V->getType())
+      V = Builder.CreateSExt(V, Ty);
+
+    switch (isl_ast_expr_get_op_type(Expr)) {
+    default:
+      llvm_unreachable("This is no n-ary isl ast expression");
+
+    case isl_ast_op_max: {
+      Value *Cmp = Builder.CreateICmpSGT(V, OpV);
+      V = Builder.CreateSelect(Cmp, V, OpV);
+      continue;
+    }
+    case isl_ast_op_min: {
+      Value *Cmp = Builder.CreateICmpSLT(V, OpV);
+      V = Builder.CreateSelect(Cmp, V, OpV);
+      continue;
+    }
+    }
   }
 
+  // TODO: We can truncate the result, if it fits into a smaller type. This can
+  // help in cases where we have larger operands (e.g. i67) but the result is
+  // known to fit into i64. Without the truncation, the larger i67 type may
+  // force all subsequent operations to be performed on a non-native type.
   isl_ast_expr_free(Expr);
   return V;
 }
@@ -287,8 +250,18 @@ Value *IslExprBuilder::createAccessAddress(isl_ast_expr *Expr) {
     assert(NextIndex->getType()->isIntegerTy() &&
            "Access index should be an integer");
 
-    IndexOp = !IndexOp ? NextIndex : createAdd(IndexOp, NextIndex,
-                                               "polly.access.add." + BaseName);
+    if (!IndexOp) {
+      IndexOp = NextIndex;
+    } else {
+      Type *Ty = getWidestType(NextIndex->getType(), IndexOp->getType());
+
+      if (Ty != NextIndex->getType())
+        NextIndex = Builder.CreateIntCast(NextIndex, Ty, true);
+      if (Ty != IndexOp->getType())
+        IndexOp = Builder.CreateIntCast(IndexOp, Ty, true);
+
+      IndexOp = createAdd(IndexOp, NextIndex, "polly.access.add." + BaseName);
+    }
 
     // For every but the last dimension multiply the size, for the last
     // dimension we can exit the loop.
@@ -303,6 +276,14 @@ Value *IslExprBuilder::createAccessAddress(isl_ast_expr *Expr) {
         expandCodeFor(S, SE, DL, "polly", DimSCEV, DimSCEV->getType(),
                       &*Builder.GetInsertPoint());
 
+    Type *Ty = getWidestType(DimSize->getType(), IndexOp->getType());
+
+    if (Ty != IndexOp->getType())
+      IndexOp = Builder.CreateSExtOrTrunc(IndexOp, Ty,
+                                          "polly.access.sext." + BaseName);
+    if (Ty != DimSize->getType())
+      DimSize = Builder.CreateSExtOrTrunc(DimSize, Ty,
+                                          "polly.access.sext." + BaseName);
     IndexOp = createMul(IndexOp, DimSize, "polly.access.mul." + BaseName);
   }
 
@@ -318,50 +299,9 @@ 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;
+  Type *MaxType;
   isl_ast_op_type OpType;
 
   assert(isl_ast_expr_get_type(Expr) == isl_ast_expr_op &&
@@ -374,25 +314,41 @@ Value *IslExprBuilder::createOpBin(__isl_take isl_ast_expr *Expr) {
   LHS = create(isl_ast_expr_get_op_arg(Expr, 0));
   RHS = create(isl_ast_expr_get_op_arg(Expr, 1));
 
-  // For possibly overflowing operations we will later adjust types but
-  // for others we do it now as we will directly create the operations.
+  Type *LHSType = LHS->getType();
+  Type *RHSType = RHS->getType();
+
+  MaxType = getWidestType(LHSType, RHSType);
+
+  // Take the result into account when calculating the widest type.
+  //
+  // For operations such as '+' the result may require a type larger than
+  // the type of the individual operands. For other operations such as '/', the
+  // result type cannot be larger than the type of the individual operand. isl
+  // does not calculate correct types for these operations and we consequently
+  // exclude those operations here.
   switch (OpType) {
   case isl_ast_op_pdiv_q:
   case isl_ast_op_pdiv_r:
   case isl_ast_op_div:
   case isl_ast_op_fdiv_q:
   case isl_ast_op_zdiv_r:
-    unifyTypes(LHS, RHS);
+    // Do nothing
     break;
   case isl_ast_op_add:
   case isl_ast_op_sub:
   case isl_ast_op_mul:
-    // Do nothing
+    MaxType = getWidestType(MaxType, getType(Expr));
     break;
   default:
     llvm_unreachable("This is no binary isl ast expression");
   }
 
+  if (MaxType != RHS->getType())
+    RHS = Builder.CreateSExt(RHS, MaxType);
+
+  if (MaxType != LHS->getType())
+    LHS = Builder.CreateSExt(LHS, MaxType);
+
   switch (OpType) {
   default:
     llvm_unreachable("This is no binary isl ast expression");
@@ -406,22 +362,46 @@ Value *IslExprBuilder::createOpBin(__isl_take isl_ast_expr *Expr) {
     Res = createMul(LHS, RHS);
     break;
   case isl_ast_op_div:
-    Res = createDiv(LHS, RHS, DM_SIGNED);
+    Res = Builder.CreateSDiv(LHS, RHS, "pexp.div", true);
     break;
   case isl_ast_op_pdiv_q: // Dividend is non-negative
-    Res = createDiv(LHS, RHS, DM_UNSIGNED);
+    Res = Builder.CreateUDiv(LHS, RHS, "pexp.p_div_q");
     break;
-  case isl_ast_op_fdiv_q: // Round towards -infty
-    Res = createDiv(LHS, RHS, DM_FLOORED);
+  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 *One = ConstantInt::get(MaxType, 1);
+    Value *Zero = ConstantInt::get(MaxType, 0);
+    Value *Sum1 = createSub(LHS, RHS, "pexp.fdiv_q.0");
+    Value *Sum2 = createAdd(Sum1, One, "pexp.fdiv_q.1");
+    Value *isNegative = Builder.CreateICmpSLT(LHS, Zero, "pexp.fdiv_q.2");
+    Value *Dividend =
+        Builder.CreateSelect(isNegative, Sum2, LHS, "pexp.fdiv_q.3");
+    Res = Builder.CreateSDiv(Dividend, RHS, "pexp.fdiv_q.4");
     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;
   }
 
+  // TODO: We can truncate the result, if it fits into a smaller type. This can
+  // help in cases where we have larger operands (e.g. i67) but the result is
+  // known to fit into i64. Without the truncation, the larger i67 type may
+  // force all subsequent operations to be performed on a non-native type.
   isl_ast_expr_free(Expr);
   return Res;
 }
@@ -430,6 +410,7 @@ Value *IslExprBuilder::createOpSelect(__isl_take isl_ast_expr *Expr) {
   assert(isl_ast_expr_get_op_type(Expr) == isl_ast_op_select &&
          "Unsupported unary isl ast expression");
   Value *LHS, *RHS, *Cond;
+  Type *MaxType = getType(Expr);
 
   Cond = create(isl_ast_expr_get_op_arg(Expr, 0));
   if (!Cond->getType()->isIntegerTy(1))
@@ -437,8 +418,17 @@ Value *IslExprBuilder::createOpSelect(__isl_take isl_ast_expr *Expr) {
 
   LHS = create(isl_ast_expr_get_op_arg(Expr, 1));
   RHS = create(isl_ast_expr_get_op_arg(Expr, 2));
-  unifyTypes(LHS, RHS);
 
+  MaxType = getWidestType(MaxType, LHS->getType());
+  MaxType = getWidestType(MaxType, RHS->getType());
+
+  if (MaxType != RHS->getType())
+    RHS = Builder.CreateSExt(RHS, MaxType);
+
+  if (MaxType != LHS->getType())
+    LHS = Builder.CreateSExt(LHS, MaxType);
+
+  // TODO: Do we want to truncate the result?
   isl_ast_expr_free(Expr);
   return Builder.CreateSelect(Cond, LHS, RHS);
 }
@@ -471,7 +461,16 @@ Value *IslExprBuilder::createOpICmp(__isl_take isl_ast_expr *Expr) {
   if (RHSTy->isPointerTy())
     RHS = Builder.CreatePtrToInt(RHS, PtrAsIntTy);
 
-  unifyTypes(LHS, RHS);
+  if (LHS->getType() != RHS->getType()) {
+    Type *MaxType = LHS->getType();
+    MaxType = getWidestType(MaxType, RHS->getType());
+
+    if (MaxType != RHS->getType())
+      RHS = Builder.CreateSExt(RHS, MaxType);
+
+    if (MaxType != LHS->getType())
+      LHS = Builder.CreateSExt(LHS, MaxType);
+  }
 
   isl_ast_op_type OpType = isl_ast_expr_get_op_type(Expr);
   assert(OpType >= isl_ast_op_eq && OpType <= isl_ast_op_gt &&
@@ -677,7 +676,7 @@ Value *IslExprBuilder::createId(__isl_take isl_ast_expr *Expr) {
 
   V = IDToValue[Id];
   if (!V)
-    V = UndefValue::get(Builder.getInt1Ty());
+    V = UndefValue::get(getType(Expr));
 
   if (V->getType()->isPointerTy())
     V = Builder.CreatePtrToInt(V, Builder.getIntNTy(DL.getPointerSizeInBits()));
@@ -690,12 +689,33 @@ Value *IslExprBuilder::createId(__isl_take isl_ast_expr *Expr) {
   return V;
 }
 
+IntegerType *IslExprBuilder::getType(__isl_keep isl_ast_expr *Expr) {
+  // XXX: We assume i64 is large enough. This is often true, but in general
+  //      incorrect. Also, on 32bit architectures, it would be beneficial to
+  //      use a smaller type. We can and should directly derive this information
+  //      during code generation.
+  return IntegerType::get(Builder.getContext(), 64);
+}
+
 Value *IslExprBuilder::createInt(__isl_take isl_ast_expr *Expr) {
   assert(isl_ast_expr_get_type(Expr) == isl_ast_expr_int &&
          "Expression not of type isl_ast_expr_int");
+  isl_val *Val;
+  Value *V;
+  APInt APValue;
+  IntegerType *T;
+
+  Val = isl_ast_expr_get_val(Expr);
+  APValue = APIntFromVal(Val);
+
+  auto BitWidth = APValue.getBitWidth();
+  if (BitWidth <= 64)
+    T = getType(Expr);
+  else
+    T = Builder.getIntNTy(BitWidth);
 
-  auto *Val = isl_ast_expr_get_val(Expr);
-  auto *V = ConstantInt::get(Builder.getContext(), APIntFromVal(Val));
+  APValue = APValue.sextOrSelf(T->getBitWidth());
+  V = ConstantInt::get(T, APValue);
 
   isl_ast_expr_free(Expr);
   return V;