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