polly/lib/CodeGen/IslExprBuilder.cpp

   1 //===------ IslExprBuilder.cpp ----- Code generate isl AST expressions ----===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 //===----------------------------------------------------------------------===//
  10
  11 #include "polly/CodeGen/IslExprBuilder.h"
  12 #include "polly/CodeGen/RuntimeDebugBuilder.h"
  13 #include "polly/Options.h"
  14 #include "polly/ScopInfo.h"
  15 #include "polly/Support/GICHelper.h"
  16 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
  17
  18 using namespace llvm;
  19 using namespace polly;
  20
  21 /// Different overflow tracking modes.
  22 enum OverflowTrackingChoice {
  23   OT_NEVER,   ///< Never tack potential overflows.
  24   OT_REQUEST, ///< Track potential overflows if requested.
  25   OT_ALWAYS   ///< Always track potential overflows.
  26 };
  27
  28 static cl::opt<OverflowTrackingChoice> OTMode(
  29     "polly-overflow-tracking",
  30     cl::desc("Define where potential integer overflows in generated "
  31              "expressions should be tracked."),
  32     cl::values(clEnumValN(OT_NEVER, "never", "Never track the overflow bit."),
  33                clEnumValN(OT_REQUEST, "request",
  34                           "Track the overflow bit if requested."),
  35                clEnumValN(OT_ALWAYS, "always",
  36                           "Always track the overflow bit.")),
  37     cl::Hidden, cl::init(OT_REQUEST), cl::cat(PollyCategory));
  38
  39 IslExprBuilder::IslExprBuilder(Scop &S, PollyIRBuilder &Builder,
  40                                IDToValueTy &IDToValue, ValueMapT &GlobalMap,
  41                                const DataLayout &DL, ScalarEvolution &SE,
  42                                DominatorTree &DT, LoopInfo &LI,
  43                                BasicBlock *StartBlock)
  44     : S(S), Builder(Builder), IDToValue(IDToValue), GlobalMap(GlobalMap),
  45       DL(DL), SE(SE), StartBlock(StartBlock), GenDT(&DT), GenLI(&LI),
  46       GenSE(&SE) {
  47   OverflowState = (OTMode == OT_ALWAYS) ? Builder.getFalse() : nullptr;
  48 }
  49
  50 void IslExprBuilder::switchGeneratedFunc(llvm::Function *GenFn,
  51                                          llvm::DominatorTree *GenDT,
  52                                          llvm::LoopInfo *GenLI,
  53                                          llvm::ScalarEvolution *GenSE) {
  54   assert(GenFn == GenDT->getRoot()->getParent());
  55   assert(GenLI->getTopLevelLoops().empty() ||
  56          GenFn == GenLI->getTopLevelLoops().front()->getHeader()->getParent());
  57   this->GenDT = GenDT;
  58   this->GenLI = GenLI;
  59   this->GenSE = GenSE;
  60 }
  61
  62 void IslExprBuilder::setTrackOverflow(bool Enable) {
  63   // If potential overflows are tracked always or never we ignore requests
  64   // to change the behavior.
  65   if (OTMode != OT_REQUEST)
  66     return;
  67
  68   if (Enable) {
  69     // If tracking should be enabled initialize the OverflowState.
  70     OverflowState = Builder.getFalse();
  71   } else {
  72     // If tracking should be disabled just unset the OverflowState.
  73     OverflowState = nullptr;
  74   }
  75 }
  76
  77 Value *IslExprBuilder::getOverflowState() const {
  78   // If the overflow tracking was requested but it is disabled we avoid the
  79   // additional nullptr checks at the call sides but instead provide a
  80   // meaningful result.
  81   if (OTMode == OT_NEVER)
  82     return Builder.getFalse();
  83   return OverflowState;
  84 }
  85
  86 bool IslExprBuilder::hasLargeInts(isl::ast_expr Expr) {
  87   enum isl_ast_expr_type Type = isl_ast_expr_get_type(Expr.get());
  88
  89   if (Type == isl_ast_expr_id)
  90     return false;
  91
  92   if (Type == isl_ast_expr_int) {
  93     isl::val Val = Expr.get_val();
  94     APInt APValue = APIntFromVal(Val);
  95     auto BitWidth = APValue.getBitWidth();
  96     return BitWidth >= 64;
  97   }
  98
  99   assert(Type == isl_ast_expr_op && "Expected isl_ast_expr of type operation");
 100
 101   int NumArgs = isl_ast_expr_get_op_n_arg(Expr.get());
 102
 103   for (int i = 0; i < NumArgs; i++) {
 104     isl::ast_expr Operand = Expr.get_op_arg(i);
 105     if (hasLargeInts(Operand))
 106       return true;
 107   }
 108
 109   return false;
 110 }
 111
 112 Value *IslExprBuilder::createBinOp(BinaryOperator::BinaryOps Opc, Value *LHS,
 113                                    Value *RHS, const Twine &Name) {
 114   // Handle the plain operation (without overflow tracking) first.
 115   if (!OverflowState) {
 116     switch (Opc) {
 117     case Instruction::Add:
 118       return Builder.CreateNSWAdd(LHS, RHS, Name);
 119     case Instruction::Sub:
 120       return Builder.CreateNSWSub(LHS, RHS, Name);
 121     case Instruction::Mul:
 122       return Builder.CreateNSWMul(LHS, RHS, Name);
 123     default:
 124       llvm_unreachable("Unknown binary operator!");
 125     }
 126   }
 127
 128   Function *F = nullptr;
 129   Module *M = Builder.GetInsertBlock()->getModule();
 130   switch (Opc) {
 131   case Instruction::Add:
 132     F = Intrinsic::getOrInsertDeclaration(M, Intrinsic::sadd_with_overflow,
 133                                           {LHS->getType()});
 134     break;
 135   case Instruction::Sub:
 136     F = Intrinsic::getOrInsertDeclaration(M, Intrinsic::ssub_with_overflow,
 137                                           {LHS->getType()});
 138     break;
 139   case Instruction::Mul:
 140     F = Intrinsic::getOrInsertDeclaration(M, Intrinsic::smul_with_overflow,
 141                                           {LHS->getType()});
 142     break;
 143   default:
 144     llvm_unreachable("No overflow intrinsic for binary operator found!");
 145   }
 146
 147   auto *ResultStruct = Builder.CreateCall(F, {LHS, RHS}, Name);
 148   assert(ResultStruct->getType()->isStructTy());
 149
 150   auto *OverflowFlag =
 151       Builder.CreateExtractValue(ResultStruct, 1, Name + ".obit");
 152
 153   // If all overflows are tracked we do not combine the results as this could
 154   // cause dominance problems. Instead we will always keep the last overflow
 155   // flag as current state.
 156   if (OTMode == OT_ALWAYS)
 157     OverflowState = OverflowFlag;
 158   else
 159     OverflowState =
 160         Builder.CreateOr(OverflowState, OverflowFlag, "polly.overflow.state");
 161
 162   return Builder.CreateExtractValue(ResultStruct, 0, Name + ".res");
 163 }
 164
 165 Value *IslExprBuilder::createAdd(Value *LHS, Value *RHS, const Twine &Name) {
 166   return createBinOp(Instruction::Add, LHS, RHS, Name);
 167 }
 168
 169 Value *IslExprBuilder::createSub(Value *LHS, Value *RHS, const Twine &Name) {
 170   return createBinOp(Instruction::Sub, LHS, RHS, Name);
 171 }
 172
 173 Value *IslExprBuilder::createMul(Value *LHS, Value *RHS, const Twine &Name) {
 174   return createBinOp(Instruction::Mul, LHS, RHS, Name);
 175 }
 176
 177 Type *IslExprBuilder::getWidestType(Type *T1, Type *T2) {
 178   assert(isa<IntegerType>(T1) && isa<IntegerType>(T2));
 179
 180   if (T1->getPrimitiveSizeInBits() < T2->getPrimitiveSizeInBits())
 181     return T2;
 182   else
 183     return T1;
 184 }
 185
 186 Value *IslExprBuilder::createOpUnary(__isl_take isl_ast_expr *Expr) {
 187   assert(isl_ast_expr_get_op_type(Expr) == isl_ast_op_minus &&
 188          "Unsupported unary operation");
 189
 190   Value *V;
 191   Type *MaxType = getType(Expr);
 192   assert(MaxType->isIntegerTy() &&
 193          "Unary expressions can only be created for integer types");
 194
 195   V = create(isl_ast_expr_get_op_arg(Expr, 0));
 196   MaxType = getWidestType(MaxType, V->getType());
 197
 198   if (MaxType != V->getType())
 199     V = Builder.CreateSExt(V, MaxType);
 200
 201   isl_ast_expr_free(Expr);
 202   return createSub(ConstantInt::getNullValue(MaxType), V);
 203 }
 204
 205 Value *IslExprBuilder::createOpNAry(__isl_take isl_ast_expr *Expr) {
 206   assert(isl_ast_expr_get_type(Expr) == isl_ast_expr_op &&
 207          "isl ast expression not of type isl_ast_op");
 208   assert(isl_ast_expr_get_op_n_arg(Expr) >= 2 &&
 209          "We need at least two operands in an n-ary operation");
 210
 211   CmpInst::Predicate Pred;
 212   switch (isl_ast_expr_get_op_type(Expr)) {
 213   default:
 214     llvm_unreachable("This is not a an n-ary isl ast expression");
 215   case isl_ast_op_max:
 216     Pred = CmpInst::ICMP_SGT;
 217     break;
 218   case isl_ast_op_min:
 219     Pred = CmpInst::ICMP_SLT;
 220     break;
 221   }
 222
 223   Value *V = create(isl_ast_expr_get_op_arg(Expr, 0));
 224
 225   for (int i = 1; i < isl_ast_expr_get_op_n_arg(Expr); ++i) {
 226     Value *OpV = create(isl_ast_expr_get_op_arg(Expr, i));
 227     Type *Ty = getWidestType(V->getType(), OpV->getType());
 228
 229     if (Ty != OpV->getType())
 230       OpV = Builder.CreateSExt(OpV, Ty);
 231
 232     if (Ty != V->getType())
 233       V = Builder.CreateSExt(V, Ty);
 234
 235     Value *Cmp = Builder.CreateICmp(Pred, V, OpV);
 236     V = Builder.CreateSelect(Cmp, V, OpV);
 237   }
 238
 239   // TODO: We can truncate the result, if it fits into a smaller type. This can
 240   // help in cases where we have larger operands (e.g. i67) but the result is
 241   // known to fit into i64. Without the truncation, the larger i67 type may
 242   // force all subsequent operations to be performed on a non-native type.
 243   isl_ast_expr_free(Expr);
 244   return V;
 245 }
 246
 247 std::pair<Value *, Type *>
 248 IslExprBuilder::createAccessAddress(__isl_take isl_ast_expr *Expr) {
 249   assert(isl_ast_expr_get_type(Expr) == isl_ast_expr_op &&
 250          "isl ast expression not of type isl_ast_op");
 251   assert(isl_ast_expr_get_op_type(Expr) == isl_ast_op_access &&
 252          "not an access isl ast expression");
 253   assert(isl_ast_expr_get_op_n_arg(Expr) >= 1 &&
 254          "We need at least two operands to create a member access.");
 255
 256   Value *Base, *IndexOp, *Access;
 257   isl_ast_expr *BaseExpr;
 258   isl_id *BaseId;
 259
 260   BaseExpr = isl_ast_expr_get_op_arg(Expr, 0);
 261   BaseId = isl_ast_expr_get_id(BaseExpr);
 262   isl_ast_expr_free(BaseExpr);
 263
 264   const ScopArrayInfo *SAI = nullptr;
 265
 266   if (PollyDebugPrinting)
 267     RuntimeDebugBuilder::createCPUPrinter(Builder, isl_id_get_name(BaseId));
 268
 269   if (IDToSAI)
 270     SAI = (*IDToSAI)[BaseId];
 271
 272   if (!SAI)
 273     SAI = ScopArrayInfo::getFromId(isl::manage(BaseId));
 274   else
 275     isl_id_free(BaseId);
 276
 277   assert(SAI && "No ScopArrayInfo found for this isl_id.");
 278
 279   Base = SAI->getBasePtr();
 280
 281   if (auto NewBase = GlobalMap.lookup(Base))
 282     Base = NewBase;
 283
 284   assert(Base->getType()->isPointerTy() && "Access base should be a pointer");
 285   StringRef BaseName = Base->getName();
 286
 287   if (isl_ast_expr_get_op_n_arg(Expr) == 1) {
 288     isl_ast_expr_free(Expr);
 289     if (PollyDebugPrinting)
 290       RuntimeDebugBuilder::createCPUPrinter(Builder, "\n");
 291     return {Base, SAI->getElementType()};
 292   }
 293
 294   IndexOp = nullptr;
 295   for (unsigned u = 1, e = isl_ast_expr_get_op_n_arg(Expr); u < e; u++) {
 296     Value *NextIndex = create(isl_ast_expr_get_op_arg(Expr, u));
 297     assert(NextIndex->getType()->isIntegerTy() &&
 298            "Access index should be an integer");
 299
 300     if (PollyDebugPrinting)
 301       RuntimeDebugBuilder::createCPUPrinter(Builder, "[", NextIndex, "]");
 302
 303     if (!IndexOp) {
 304       IndexOp = NextIndex;
 305     } else {
 306       Type *Ty = getWidestType(NextIndex->getType(), IndexOp->getType());
 307
 308       if (Ty != NextIndex->getType())
 309         NextIndex = Builder.CreateIntCast(NextIndex, Ty, true);
 310       if (Ty != IndexOp->getType())
 311         IndexOp = Builder.CreateIntCast(IndexOp, Ty, true);
 312
 313       IndexOp = createAdd(IndexOp, NextIndex, "polly.access.add." + BaseName);
 314     }
 315
 316     // For every but the last dimension multiply the size, for the last
 317     // dimension we can exit the loop.
 318     if (u + 1 >= e)
 319       break;
 320
 321     const SCEV *DimSCEV = SAI->getDimensionSize(u);
 322
 323     // DimSize should be invariant to the SCoP, so no BBMap nor LoopToScev
 324     // needed. But GlobalMap may contain SCoP-invariant vars.
 325     Value *DimSize = expandCodeFor(
 326         S, SE, Builder.GetInsertBlock()->getParent(), *GenSE, DL, "polly",
 327         DimSCEV, DimSCEV->getType(), &*Builder.GetInsertPoint(), &GlobalMap,
 328         /*LoopMap*/ nullptr, StartBlock->getSinglePredecessor());
 329
 330     Type *Ty = getWidestType(DimSize->getType(), IndexOp->getType());
 331
 332     if (Ty != IndexOp->getType())
 333       IndexOp = Builder.CreateSExtOrTrunc(IndexOp, Ty,
 334                                           "polly.access.sext." + BaseName);
 335     if (Ty != DimSize->getType())
 336       DimSize = Builder.CreateSExtOrTrunc(DimSize, Ty,
 337                                           "polly.access.sext." + BaseName);
 338     IndexOp = createMul(IndexOp, DimSize, "polly.access.mul." + BaseName);
 339   }
 340
 341   Access = Builder.CreateGEP(SAI->getElementType(), Base, IndexOp,
 342                              "polly.access." + BaseName);
 343
 344   if (PollyDebugPrinting)
 345     RuntimeDebugBuilder::createCPUPrinter(Builder, "\n");
 346   isl_ast_expr_free(Expr);
 347   return {Access, SAI->getElementType()};
 348 }
 349
 350 Value *IslExprBuilder::createOpAccess(__isl_take isl_ast_expr *Expr) {
 351   auto Info = createAccessAddress(Expr);
 352   assert(Info.first && "Could not create op access address");
 353   return Builder.CreateLoad(Info.second, Info.first,
 354                             Info.first->getName() + ".load");
 355 }
 356
 357 Value *IslExprBuilder::createOpBin(__isl_take isl_ast_expr *Expr) {
 358   Value *LHS, *RHS, *Res;
 359   Type *MaxType;
 360   isl_ast_op_type OpType;
 361
 362   assert(isl_ast_expr_get_type(Expr) == isl_ast_expr_op &&
 363          "isl ast expression not of type isl_ast_op");
 364   assert(isl_ast_expr_get_op_n_arg(Expr) == 2 &&
 365          "not a binary isl ast expression");
 366
 367   OpType = isl_ast_expr_get_op_type(Expr);
 368
 369   LHS = create(isl_ast_expr_get_op_arg(Expr, 0));
 370   RHS = create(isl_ast_expr_get_op_arg(Expr, 1));
 371
 372   Type *LHSType = LHS->getType();
 373   Type *RHSType = RHS->getType();
 374
 375   MaxType = getWidestType(LHSType, RHSType);
 376
 377   // Take the result into account when calculating the widest type.
 378   //
 379   // For operations such as '+' the result may require a type larger than
 380   // the type of the individual operands. For other operations such as '/', the
 381   // result type cannot be larger than the type of the individual operand. isl
 382   // does not calculate correct types for these operations and we consequently
 383   // exclude those operations here.
 384   switch (OpType) {
 385   case isl_ast_op_pdiv_q:
 386   case isl_ast_op_pdiv_r:
 387   case isl_ast_op_div:
 388   case isl_ast_op_fdiv_q:
 389   case isl_ast_op_zdiv_r:
 390     // Do nothing
 391     break;
 392   case isl_ast_op_add:
 393   case isl_ast_op_sub:
 394   case isl_ast_op_mul:
 395     MaxType = getWidestType(MaxType, getType(Expr));
 396     break;
 397   default:
 398     llvm_unreachable("This is no binary isl ast expression");
 399   }
 400
 401   if (MaxType != RHS->getType())
 402     RHS = Builder.CreateSExt(RHS, MaxType);
 403
 404   if (MaxType != LHS->getType())
 405     LHS = Builder.CreateSExt(LHS, MaxType);
 406
 407   switch (OpType) {
 408   default:
 409     llvm_unreachable("This is no binary isl ast expression");
 410   case isl_ast_op_add:
 411     Res = createAdd(LHS, RHS);
 412     break;
 413   case isl_ast_op_sub:
 414     Res = createSub(LHS, RHS);
 415     break;
 416   case isl_ast_op_mul:
 417     Res = createMul(LHS, RHS);
 418     break;
 419   case isl_ast_op_div:
 420     Res = Builder.CreateSDiv(LHS, RHS, "pexp.div", true);
 421     break;
 422   case isl_ast_op_pdiv_q: // Dividend is non-negative
 423     Res = Builder.CreateUDiv(LHS, RHS, "pexp.p_div_q");
 424     break;
 425   case isl_ast_op_fdiv_q: { // Round towards -infty
 426     if (auto *Const = dyn_cast<ConstantInt>(RHS)) {
 427       auto &Val = Const->getValue();
 428       if (Val.isPowerOf2() && Val.isNonNegative()) {
 429         Res = Builder.CreateAShr(LHS, Val.ceilLogBase2(), "polly.fdiv_q.shr");
 430         break;
 431       }
 432     }
 433     // TODO: Review code and check that this calculation does not yield
 434     //       incorrect overflow in some edge cases.
 435     //
 436     // floord(n,d) ((n < 0) ? (n - d + 1) : n) / d
 437     Value *One = ConstantInt::get(MaxType, 1);
 438     Value *Zero = ConstantInt::get(MaxType, 0);
 439     Value *Sum1 = createSub(LHS, RHS, "pexp.fdiv_q.0");
 440     Value *Sum2 = createAdd(Sum1, One, "pexp.fdiv_q.1");
 441     Value *isNegative = Builder.CreateICmpSLT(LHS, Zero, "pexp.fdiv_q.2");
 442     Value *Dividend =
 443         Builder.CreateSelect(isNegative, Sum2, LHS, "pexp.fdiv_q.3");
 444     Res = Builder.CreateSDiv(Dividend, RHS, "pexp.fdiv_q.4");
 445     break;
 446   }
 447   case isl_ast_op_pdiv_r: // Dividend is non-negative
 448     Res = Builder.CreateURem(LHS, RHS, "pexp.pdiv_r");
 449     break;
 450
 451   case isl_ast_op_zdiv_r: // Result only compared against zero
 452     Res = Builder.CreateSRem(LHS, RHS, "pexp.zdiv_r");
 453     break;
 454   }
 455
 456   // TODO: We can truncate the result, if it fits into a smaller type. This can
 457   // help in cases where we have larger operands (e.g. i67) but the result is
 458   // known to fit into i64. Without the truncation, the larger i67 type may
 459   // force all subsequent operations to be performed on a non-native type.
 460   isl_ast_expr_free(Expr);
 461   return Res;
 462 }
 463
 464 Value *IslExprBuilder::createOpSelect(__isl_take isl_ast_expr *Expr) {
 465   assert(isl_ast_expr_get_op_type(Expr) == isl_ast_op_select &&
 466          "Unsupported unary isl ast expression");
 467   Value *LHS, *RHS, *Cond;
 468   Type *MaxType = getType(Expr);
 469
 470   Cond = create(isl_ast_expr_get_op_arg(Expr, 0));
 471   if (!Cond->getType()->isIntegerTy(1))
 472     Cond = Builder.CreateIsNotNull(Cond);
 473
 474   LHS = create(isl_ast_expr_get_op_arg(Expr, 1));
 475   RHS = create(isl_ast_expr_get_op_arg(Expr, 2));
 476
 477   MaxType = getWidestType(MaxType, LHS->getType());
 478   MaxType = getWidestType(MaxType, RHS->getType());
 479
 480   if (MaxType != RHS->getType())
 481     RHS = Builder.CreateSExt(RHS, MaxType);
 482
 483   if (MaxType != LHS->getType())
 484     LHS = Builder.CreateSExt(LHS, MaxType);
 485
 486   // TODO: Do we want to truncate the result?
 487   isl_ast_expr_free(Expr);
 488   return Builder.CreateSelect(Cond, LHS, RHS);
 489 }
 490
 491 Value *IslExprBuilder::createOpICmp(__isl_take isl_ast_expr *Expr) {
 492   assert(isl_ast_expr_get_type(Expr) == isl_ast_expr_op &&
 493          "Expected an isl_ast_expr_op expression");
 494
 495   Value *LHS, *RHS, *Res;
 496
 497   auto *Op0 = isl_ast_expr_get_op_arg(Expr, 0);
 498   auto *Op1 = isl_ast_expr_get_op_arg(Expr, 1);
 499   bool HasNonAddressOfOperand =
 500       isl_ast_expr_get_type(Op0) != isl_ast_expr_op ||
 501       isl_ast_expr_get_type(Op1) != isl_ast_expr_op ||
 502       isl_ast_expr_get_op_type(Op0) != isl_ast_op_address_of ||
 503       isl_ast_expr_get_op_type(Op1) != isl_ast_op_address_of;
 504
 505   LHS = create(Op0);
 506   RHS = create(Op1);
 507
 508   auto *LHSTy = LHS->getType();
 509   auto *RHSTy = RHS->getType();
 510   bool IsPtrType = LHSTy->isPointerTy() || RHSTy->isPointerTy();
 511   bool UseUnsignedCmp = IsPtrType && !HasNonAddressOfOperand;
 512
 513   auto *PtrAsIntTy = Builder.getIntNTy(DL.getPointerSizeInBits());
 514   if (LHSTy->isPointerTy())
 515     LHS = Builder.CreatePtrToInt(LHS, PtrAsIntTy);
 516   if (RHSTy->isPointerTy())
 517     RHS = Builder.CreatePtrToInt(RHS, PtrAsIntTy);
 518
 519   if (LHS->getType() != RHS->getType()) {
 520     Type *MaxType = LHS->getType();
 521     MaxType = getWidestType(MaxType, RHS->getType());
 522
 523     if (MaxType != RHS->getType())
 524       RHS = Builder.CreateSExt(RHS, MaxType);
 525
 526     if (MaxType != LHS->getType())
 527       LHS = Builder.CreateSExt(LHS, MaxType);
 528   }
 529
 530   isl_ast_op_type OpType = isl_ast_expr_get_op_type(Expr);
 531   assert(OpType >= isl_ast_op_eq && OpType <= isl_ast_op_gt &&
 532          "Unsupported ICmp isl ast expression");
 533   static_assert(isl_ast_op_eq + 4 == isl_ast_op_gt,
 534                 "Isl ast op type interface changed");
 535
 536   CmpInst::Predicate Predicates[5][2] = {
 537       {CmpInst::ICMP_EQ, CmpInst::ICMP_EQ},
 538       {CmpInst::ICMP_SLE, CmpInst::ICMP_ULE},
 539       {CmpInst::ICMP_SLT, CmpInst::ICMP_ULT},
 540       {CmpInst::ICMP_SGE, CmpInst::ICMP_UGE},
 541       {CmpInst::ICMP_SGT, CmpInst::ICMP_UGT},
 542   };
 543
 544   Res = Builder.CreateICmp(Predicates[OpType - isl_ast_op_eq][UseUnsignedCmp],
 545                            LHS, RHS);
 546
 547   isl_ast_expr_free(Expr);
 548   return Res;
 549 }
 550
 551 Value *IslExprBuilder::createOpBoolean(__isl_take isl_ast_expr *Expr) {
 552   assert(isl_ast_expr_get_type(Expr) == isl_ast_expr_op &&
 553          "Expected an isl_ast_expr_op expression");
 554
 555   Value *LHS, *RHS, *Res;
 556   isl_ast_op_type OpType;
 557
 558   OpType = isl_ast_expr_get_op_type(Expr);
 559
 560   assert((OpType == isl_ast_op_and || OpType == isl_ast_op_or) &&
 561          "Unsupported isl_ast_op_type");
 562
 563   LHS = create(isl_ast_expr_get_op_arg(Expr, 0));
 564   RHS = create(isl_ast_expr_get_op_arg(Expr, 1));
 565
 566   // Even though the isl pretty printer prints the expressions as 'exp && exp'
 567   // or 'exp || exp', we actually code generate the bitwise expressions
 568   // 'exp & exp' or 'exp | exp'. This forces the evaluation of both branches,
 569   // but it is, due to the use of i1 types, otherwise equivalent. The reason
 570   // to go for bitwise operations is, that we assume the reduced control flow
 571   // will outweigh the overhead introduced by evaluating unneeded expressions.
 572   // The isl code generation currently does not take advantage of the fact that
 573   // the expression after an '||' or '&&' is in some cases not evaluated.
 574   // Evaluating it anyways does not cause any undefined behaviour.
 575   //
 576   // TODO: Document in isl itself, that the unconditionally evaluating the
 577   // second part of '||' or '&&' expressions is safe.
 578   if (!LHS->getType()->isIntegerTy(1))
 579     LHS = Builder.CreateIsNotNull(LHS);
 580   if (!RHS->getType()->isIntegerTy(1))
 581     RHS = Builder.CreateIsNotNull(RHS);
 582
 583   switch (OpType) {
 584   default:
 585     llvm_unreachable("Unsupported boolean expression");
 586   case isl_ast_op_and:
 587     Res = Builder.CreateAnd(LHS, RHS);
 588     break;
 589   case isl_ast_op_or:
 590     Res = Builder.CreateOr(LHS, RHS);
 591     break;
 592   }
 593
 594   isl_ast_expr_free(Expr);
 595   return Res;
 596 }
 597
 598 Value *
 599 IslExprBuilder::createOpBooleanConditional(__isl_take isl_ast_expr *Expr) {
 600   assert(isl_ast_expr_get_type(Expr) == isl_ast_expr_op &&
 601          "Expected an isl_ast_expr_op expression");
 602
 603   Value *LHS, *RHS;
 604   isl_ast_op_type OpType;
 605
 606   Function *F = Builder.GetInsertBlock()->getParent();
 607   LLVMContext &Context = F->getContext();
 608
 609   OpType = isl_ast_expr_get_op_type(Expr);
 610
 611   assert((OpType == isl_ast_op_and_then || OpType == isl_ast_op_or_else) &&
 612          "Unsupported isl_ast_op_type");
 613
 614   auto InsertBB = Builder.GetInsertBlock();
 615   auto InsertPoint = Builder.GetInsertPoint();
 616   auto NextBB = SplitBlock(InsertBB, &*InsertPoint, GenDT, GenLI);
 617   BasicBlock *CondBB = BasicBlock::Create(Context, "polly.cond", F);
 618   GenLI->changeLoopFor(CondBB, GenLI->getLoopFor(InsertBB));
 619   GenDT->addNewBlock(CondBB, InsertBB);
 620
 621   InsertBB->getTerminator()->eraseFromParent();
 622   Builder.SetInsertPoint(InsertBB);
 623   auto BR = Builder.CreateCondBr(Builder.getTrue(), NextBB, CondBB);
 624
 625   Builder.SetInsertPoint(CondBB);
 626   Builder.CreateBr(NextBB);
 627
 628   Builder.SetInsertPoint(InsertBB->getTerminator());
 629
 630   LHS = create(isl_ast_expr_get_op_arg(Expr, 0));
 631   if (!LHS->getType()->isIntegerTy(1))
 632     LHS = Builder.CreateIsNotNull(LHS);
 633   auto LeftBB = Builder.GetInsertBlock();
 634
 635   if (OpType == isl_ast_op_and || OpType == isl_ast_op_and_then)
 636     BR->setCondition(Builder.CreateNeg(LHS));
 637   else
 638     BR->setCondition(LHS);
 639
 640   Builder.SetInsertPoint(CondBB->getTerminator());
 641   RHS = create(isl_ast_expr_get_op_arg(Expr, 1));
 642   if (!RHS->getType()->isIntegerTy(1))
 643     RHS = Builder.CreateIsNotNull(RHS);
 644   auto RightBB = Builder.GetInsertBlock();
 645
 646   Builder.SetInsertPoint(NextBB->getTerminator());
 647   auto PHI = Builder.CreatePHI(Builder.getInt1Ty(), 2);
 648   PHI->addIncoming(OpType == isl_ast_op_and_then ? Builder.getFalse()
 649                                                  : Builder.getTrue(),
 650                    LeftBB);
 651   PHI->addIncoming(RHS, RightBB);
 652
 653   isl_ast_expr_free(Expr);
 654   return PHI;
 655 }
 656
 657 Value *IslExprBuilder::createOp(__isl_take isl_ast_expr *Expr) {
 658   assert(isl_ast_expr_get_type(Expr) == isl_ast_expr_op &&
 659          "Expression not of type isl_ast_expr_op");
 660   switch (isl_ast_expr_get_op_type(Expr)) {
 661   case isl_ast_op_error:
 662   case isl_ast_op_cond:
 663   case isl_ast_op_call:
 664   case isl_ast_op_member:
 665     llvm_unreachable("Unsupported isl ast expression");
 666   case isl_ast_op_access:
 667     return createOpAccess(Expr);
 668   case isl_ast_op_max:
 669   case isl_ast_op_min:
 670     return createOpNAry(Expr);
 671   case isl_ast_op_add:
 672   case isl_ast_op_sub:
 673   case isl_ast_op_mul:
 674   case isl_ast_op_div:
 675   case isl_ast_op_fdiv_q: // Round towards -infty
 676   case isl_ast_op_pdiv_q: // Dividend is non-negative
 677   case isl_ast_op_pdiv_r: // Dividend is non-negative
 678   case isl_ast_op_zdiv_r: // Result only compared against zero
 679     return createOpBin(Expr);
 680   case isl_ast_op_minus:
 681     return createOpUnary(Expr);
 682   case isl_ast_op_select:
 683     return createOpSelect(Expr);
 684   case isl_ast_op_and:
 685   case isl_ast_op_or:
 686     return createOpBoolean(Expr);
 687   case isl_ast_op_and_then:
 688   case isl_ast_op_or_else:
 689     return createOpBooleanConditional(Expr);
 690   case isl_ast_op_eq:
 691   case isl_ast_op_le:
 692   case isl_ast_op_lt:
 693   case isl_ast_op_ge:
 694   case isl_ast_op_gt:
 695     return createOpICmp(Expr);
 696   case isl_ast_op_address_of:
 697     return createOpAddressOf(Expr);
 698   }
 699
 700   llvm_unreachable("Unsupported isl_ast_expr_op kind.");
 701 }
 702
 703 Value *IslExprBuilder::createOpAddressOf(__isl_take isl_ast_expr *Expr) {
 704   assert(isl_ast_expr_get_type(Expr) == isl_ast_expr_op &&
 705          "Expected an isl_ast_expr_op expression.");
 706   assert(isl_ast_expr_get_op_n_arg(Expr) == 1 && "Address of should be unary.");
 707
 708   isl_ast_expr *Op = isl_ast_expr_get_op_arg(Expr, 0);
 709   assert(isl_ast_expr_get_type(Op) == isl_ast_expr_op &&
 710          "Expected address of operator to be an isl_ast_expr_op expression.");
 711   assert(isl_ast_expr_get_op_type(Op) == isl_ast_op_access &&
 712          "Expected address of operator to be an access expression.");
 713
 714   Value *V = createAccessAddress(Op).first;
 715
 716   isl_ast_expr_free(Expr);
 717
 718   return V;
 719 }
 720
 721 Value *IslExprBuilder::createId(__isl_take isl_ast_expr *Expr) {
 722   assert(isl_ast_expr_get_type(Expr) == isl_ast_expr_id &&
 723          "Expression not of type isl_ast_expr_ident");
 724
 725   isl_id *Id;
 726   Value *V;
 727
 728   Id = isl_ast_expr_get_id(Expr);
 729
 730   assert(IDToValue.count(Id) && "Identifier not found");
 731
 732   V = IDToValue[Id];
 733   if (!V)
 734     V = UndefValue::get(getType(Expr));
 735
 736   if (V->getType()->isPointerTy())
 737     V = Builder.CreatePtrToInt(V, Builder.getIntNTy(DL.getPointerSizeInBits()));
 738
 739   assert(V && "Unknown parameter id found");
 740
 741   isl_id_free(Id);
 742   isl_ast_expr_free(Expr);
 743
 744   return V;
 745 }
 746
 747 IntegerType *IslExprBuilder::getType(__isl_keep isl_ast_expr *Expr) {
 748   // XXX: We assume i64 is large enough. This is often true, but in general
 749   //      incorrect. Also, on 32bit architectures, it would be beneficial to
 750   //      use a smaller type. We can and should directly derive this information
 751   //      during code generation.
 752   return IntegerType::get(Builder.getContext(), 64);
 753 }
 754
 755 Value *IslExprBuilder::createInt(__isl_take isl_ast_expr *Expr) {
 756   assert(isl_ast_expr_get_type(Expr) == isl_ast_expr_int &&
 757          "Expression not of type isl_ast_expr_int");
 758   isl_val *Val;
 759   Value *V;
 760   APInt APValue;
 761   IntegerType *T;
 762
 763   Val = isl_ast_expr_get_val(Expr);
 764   APValue = APIntFromVal(Val);
 765
 766   auto BitWidth = APValue.getBitWidth();
 767   if (BitWidth <= 64)
 768     T = getType(Expr);
 769   else
 770     T = Builder.getIntNTy(BitWidth);
 771
 772   APValue = APValue.sext(T->getBitWidth());
 773   V = ConstantInt::get(T, APValue);
 774
 775   isl_ast_expr_free(Expr);
 776   return V;
 777 }
 778
 779 Value *IslExprBuilder::create(__isl_take isl_ast_expr *Expr) {
 780   switch (isl_ast_expr_get_type(Expr)) {
 781   case isl_ast_expr_error:
 782     llvm_unreachable("Code generation error");
 783   case isl_ast_expr_op:
 784     return createOp(Expr);
 785   case isl_ast_expr_id:
 786     return createId(Expr);
 787   case isl_ast_expr_int:
 788     return createInt(Expr);
 789   }
 790
 791   llvm_unreachable("Unexpected enum value");
 792 }