This reverts recent expression type changes

The recent expression type changes still need more discussion, which will happen
on phabricator or on the mailing list. The precise list of commits reverted are:

- "Refactor division generation code"
- "[NFC] Generate runtime checks after the SCoP"
- "[FIX] Determine insertion point during SCEV expansion"
- "Look through IntToPtr & PtrToInt instructions"
- "Use minimal types for generated expressions"
- "Temporarily promote values to i64 again"
- "[NFC] Avoid unnecessary comparison for min/max expressions"
- "[Polly] Fix -Wunused-variable warnings (NFC)"
- "[NFC] Simplify min/max expression generation"
- "Simplify the type adjustment in the IslExprBuilder"

Some of them are just reverted as we would otherwise get conflicts. I will try
to re-commit them if possible.

llvm-svn: 272483

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;