lib/CodeGen/IslExprBuilder.cpp

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