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), 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 std::pair<Value *, Type *>
 235 IslExprBuilder::createAccessAddress(__isl_take isl_ast_expr *Expr) {
 236   assert(isl_ast_expr_get_type(Expr) == isl_ast_expr_op &&
 237          "isl ast expression not of type isl_ast_op");
 238   assert(isl_ast_expr_get_op_type(Expr) == isl_ast_op_access &&
 239          "not an access isl ast expression");
 240   assert(isl_ast_expr_get_op_n_arg(Expr) >= 1 &&
 241          "We need at least two operands to create a member access.");
 242
 243   Value *Base, *IndexOp, *Access;
 244   isl_ast_expr *BaseExpr;
 245   isl_id *BaseId;
 246
 247   BaseExpr = isl_ast_expr_get_op_arg(Expr, 0);
 248   BaseId = isl_ast_expr_get_id(BaseExpr);
 249   isl_ast_expr_free(BaseExpr);
 250
 251   const ScopArrayInfo *SAI = nullptr;
 252
 253   if (PollyDebugPrinting)
 254     RuntimeDebugBuilder::createCPUPrinter(Builder, isl_id_get_name(BaseId));
 255
 256   if (IDToSAI)
 257     SAI = (*IDToSAI)[BaseId];
 258
 259   if (!SAI)
 260     SAI = ScopArrayInfo::getFromId(isl::manage(BaseId));
 261   else
 262     isl_id_free(BaseId);
 263
 264   assert(SAI && "No ScopArrayInfo found for this isl_id.");
 265
 266   Base = SAI->getBasePtr();
 267
 268   if (auto NewBase = GlobalMap.lookup(Base))
 269     Base = NewBase;
 270
 271   assert(Base->getType()->isPointerTy() && "Access base should be a pointer");
 272   StringRef BaseName = Base->getName();
 273
 274   if (isl_ast_expr_get_op_n_arg(Expr) == 1) {
 275     isl_ast_expr_free(Expr);
 276     if (PollyDebugPrinting)
 277       RuntimeDebugBuilder::createCPUPrinter(Builder, "\n");
 278     return {Base, SAI->getElementType()};
 279   }
 280
 281   IndexOp = nullptr;
 282   for (unsigned u = 1, e = isl_ast_expr_get_op_n_arg(Expr); u < e; u++) {
 283     Value *NextIndex = create(isl_ast_expr_get_op_arg(Expr, u));
 284     assert(NextIndex->getType()->isIntegerTy() &&
 285            "Access index should be an integer");
 286
 287     if (PollyDebugPrinting)
 288       RuntimeDebugBuilder::createCPUPrinter(Builder, "[", NextIndex, "]");
 289
 290     if (!IndexOp) {
 291       IndexOp = NextIndex;
 292     } else {
 293       Type *Ty = getWidestType(NextIndex->getType(), IndexOp->getType());
 294
 295       if (Ty != NextIndex->getType())
 296         NextIndex = Builder.CreateIntCast(NextIndex, Ty, true);
 297       if (Ty != IndexOp->getType())
 298         IndexOp = Builder.CreateIntCast(IndexOp, Ty, true);
 299
 300       IndexOp = createAdd(IndexOp, NextIndex, "polly.access.add." + BaseName);
 301     }
 302
 303     // For every but the last dimension multiply the size, for the last
 304     // dimension we can exit the loop.
 305     if (u + 1 >= e)
 306       break;
 307
 308     const SCEV *DimSCEV = SAI->getDimensionSize(u);
 309
 310     llvm::ValueToSCEVMapTy Map;
 311     for (auto &KV : GlobalMap)
 312       Map[KV.first] = SE.getSCEV(KV.second);
 313     DimSCEV = SCEVParameterRewriter::rewrite(DimSCEV, SE, Map);
 314     Value *DimSize =
 315         expandCodeFor(S, SE, DL, "polly", DimSCEV, DimSCEV->getType(),
 316                       &*Builder.GetInsertPoint(), nullptr,
 317                       StartBlock->getSinglePredecessor());
 318
 319     Type *Ty = getWidestType(DimSize->getType(), IndexOp->getType());
 320
 321     if (Ty != IndexOp->getType())
 322       IndexOp = Builder.CreateSExtOrTrunc(IndexOp, Ty,
 323                                           "polly.access.sext." + BaseName);
 324     if (Ty != DimSize->getType())
 325       DimSize = Builder.CreateSExtOrTrunc(DimSize, Ty,
 326                                           "polly.access.sext." + BaseName);
 327     IndexOp = createMul(IndexOp, DimSize, "polly.access.mul." + BaseName);
 328   }
 329
 330   Access = Builder.CreateGEP(SAI->getElementType(), Base, IndexOp,
 331                              "polly.access." + BaseName);
 332
 333   if (PollyDebugPrinting)
 334     RuntimeDebugBuilder::createCPUPrinter(Builder, "\n");
 335   isl_ast_expr_free(Expr);
 336   return {Access, SAI->getElementType()};
 337 }
 338
 339 Value *IslExprBuilder::createOpAccess(__isl_take isl_ast_expr *Expr) {
 340   auto Info = createAccessAddress(Expr);
 341   assert(Info.first && "Could not create op access address");
 342   return Builder.CreateLoad(Info.second, Info.first,
 343                             Info.first->getName() + ".load");
 344 }
 345
 346 Value *IslExprBuilder::createOpBin(__isl_take isl_ast_expr *Expr) {
 347   Value *LHS, *RHS, *Res;
 348   Type *MaxType;
 349   isl_ast_op_type OpType;
 350
 351   assert(isl_ast_expr_get_type(Expr) == isl_ast_expr_op &&
 352          "isl ast expression not of type isl_ast_op");
 353   assert(isl_ast_expr_get_op_n_arg(Expr) == 2 &&
 354          "not a binary isl ast expression");
 355
 356   OpType = isl_ast_expr_get_op_type(Expr);
 357
 358   LHS = create(isl_ast_expr_get_op_arg(Expr, 0));
 359   RHS = create(isl_ast_expr_get_op_arg(Expr, 1));
 360
 361   Type *LHSType = LHS->getType();
 362   Type *RHSType = RHS->getType();
 363
 364   MaxType = getWidestType(LHSType, RHSType);
 365
 366   // Take the result into account when calculating the widest type.
 367   //
 368   // For operations such as '+' the result may require a type larger than
 369   // the type of the individual operands. For other operations such as '/', the
 370   // result type cannot be larger than the type of the individual operand. isl
 371   // does not calculate correct types for these operations and we consequently
 372   // exclude those operations here.
 373   switch (OpType) {
 374   case isl_ast_op_pdiv_q:
 375   case isl_ast_op_pdiv_r:
 376   case isl_ast_op_div:
 377   case isl_ast_op_fdiv_q:
 378   case isl_ast_op_zdiv_r:
 379     // Do nothing
 380     break;
 381   case isl_ast_op_add:
 382   case isl_ast_op_sub:
 383   case isl_ast_op_mul:
 384     MaxType = getWidestType(MaxType, getType(Expr));
 385     break;
 386   default:
 387     llvm_unreachable("This is no binary isl ast expression");
 388   }
 389
 390   if (MaxType != RHS->getType())
 391     RHS = Builder.CreateSExt(RHS, MaxType);
 392
 393   if (MaxType != LHS->getType())
 394     LHS = Builder.CreateSExt(LHS, MaxType);
 395
 396   switch (OpType) {
 397   default:
 398     llvm_unreachable("This is no binary isl ast expression");
 399   case isl_ast_op_add:
 400     Res = createAdd(LHS, RHS);
 401     break;
 402   case isl_ast_op_sub:
 403     Res = createSub(LHS, RHS);
 404     break;
 405   case isl_ast_op_mul:
 406     Res = createMul(LHS, RHS);
 407     break;
 408   case isl_ast_op_div:
 409     Res = Builder.CreateSDiv(LHS, RHS, "pexp.div", true);
 410     break;
 411   case isl_ast_op_pdiv_q: // Dividend is non-negative
 412     Res = Builder.CreateUDiv(LHS, RHS, "pexp.p_div_q");
 413     break;
 414   case isl_ast_op_fdiv_q: { // Round towards -infty
 415     if (auto *Const = dyn_cast<ConstantInt>(RHS)) {
 416       auto &Val = Const->getValue();
 417       if (Val.isPowerOf2() && Val.isNonNegative()) {
 418         Res = Builder.CreateAShr(LHS, Val.ceilLogBase2(), "polly.fdiv_q.shr");
 419         break;
 420       }
 421     }
 422     // TODO: Review code and check that this calculation does not yield
 423     //       incorrect overflow in some edge cases.
 424     //
 425     // floord(n,d) ((n < 0) ? (n - d + 1) : n) / d
 426     Value *One = ConstantInt::get(MaxType, 1);
 427     Value *Zero = ConstantInt::get(MaxType, 0);
 428     Value *Sum1 = createSub(LHS, RHS, "pexp.fdiv_q.0");
 429     Value *Sum2 = createAdd(Sum1, One, "pexp.fdiv_q.1");
 430     Value *isNegative = Builder.CreateICmpSLT(LHS, Zero, "pexp.fdiv_q.2");
 431     Value *Dividend =
 432         Builder.CreateSelect(isNegative, Sum2, LHS, "pexp.fdiv_q.3");
 433     Res = Builder.CreateSDiv(Dividend, RHS, "pexp.fdiv_q.4");
 434     break;
 435   }
 436   case isl_ast_op_pdiv_r: // Dividend is non-negative
 437     Res = Builder.CreateURem(LHS, RHS, "pexp.pdiv_r");
 438     break;
 439
 440   case isl_ast_op_zdiv_r: // Result only compared against zero
 441     Res = Builder.CreateSRem(LHS, RHS, "pexp.zdiv_r");
 442     break;
 443   }
 444
 445   // TODO: We can truncate the result, if it fits into a smaller type. This can
 446   // help in cases where we have larger operands (e.g. i67) but the result is
 447   // known to fit into i64. Without the truncation, the larger i67 type may
 448   // force all subsequent operations to be performed on a non-native type.
 449   isl_ast_expr_free(Expr);
 450   return Res;
 451 }
 452
 453 Value *IslExprBuilder::createOpSelect(__isl_take isl_ast_expr *Expr) {
 454   assert(isl_ast_expr_get_op_type(Expr) == isl_ast_op_select &&
 455          "Unsupported unary isl ast expression");
 456   Value *LHS, *RHS, *Cond;
 457   Type *MaxType = getType(Expr);
 458
 459   Cond = create(isl_ast_expr_get_op_arg(Expr, 0));
 460   if (!Cond->getType()->isIntegerTy(1))
 461     Cond = Builder.CreateIsNotNull(Cond);
 462
 463   LHS = create(isl_ast_expr_get_op_arg(Expr, 1));
 464   RHS = create(isl_ast_expr_get_op_arg(Expr, 2));
 465
 466   MaxType = getWidestType(MaxType, LHS->getType());
 467   MaxType = getWidestType(MaxType, RHS->getType());
 468
 469   if (MaxType != RHS->getType())
 470     RHS = Builder.CreateSExt(RHS, MaxType);
 471
 472   if (MaxType != LHS->getType())
 473     LHS = Builder.CreateSExt(LHS, MaxType);
 474
 475   // TODO: Do we want to truncate the result?
 476   isl_ast_expr_free(Expr);
 477   return Builder.CreateSelect(Cond, LHS, RHS);
 478 }
 479
 480 Value *IslExprBuilder::createOpICmp(__isl_take isl_ast_expr *Expr) {
 481   assert(isl_ast_expr_get_type(Expr) == isl_ast_expr_op &&
 482          "Expected an isl_ast_expr_op expression");
 483
 484   Value *LHS, *RHS, *Res;
 485
 486   auto *Op0 = isl_ast_expr_get_op_arg(Expr, 0);
 487   auto *Op1 = isl_ast_expr_get_op_arg(Expr, 1);
 488   bool HasNonAddressOfOperand =
 489       isl_ast_expr_get_type(Op0) != isl_ast_expr_op ||
 490       isl_ast_expr_get_type(Op1) != isl_ast_expr_op ||
 491       isl_ast_expr_get_op_type(Op0) != isl_ast_op_address_of ||
 492       isl_ast_expr_get_op_type(Op1) != isl_ast_op_address_of;
 493
 494   LHS = create(Op0);
 495   RHS = create(Op1);
 496
 497   auto *LHSTy = LHS->getType();
 498   auto *RHSTy = RHS->getType();
 499   bool IsPtrType = LHSTy->isPointerTy() || RHSTy->isPointerTy();
 500   bool UseUnsignedCmp = IsPtrType && !HasNonAddressOfOperand;
 501
 502   auto *PtrAsIntTy = Builder.getIntNTy(DL.getPointerSizeInBits());
 503   if (LHSTy->isPointerTy())
 504     LHS = Builder.CreatePtrToInt(LHS, PtrAsIntTy);
 505   if (RHSTy->isPointerTy())
 506     RHS = Builder.CreatePtrToInt(RHS, PtrAsIntTy);
 507
 508   if (LHS->getType() != RHS->getType()) {
 509     Type *MaxType = LHS->getType();
 510     MaxType = getWidestType(MaxType, RHS->getType());
 511
 512     if (MaxType != RHS->getType())
 513       RHS = Builder.CreateSExt(RHS, MaxType);
 514
 515     if (MaxType != LHS->getType())
 516       LHS = Builder.CreateSExt(LHS, MaxType);
 517   }
 518
 519   isl_ast_op_type OpType = isl_ast_expr_get_op_type(Expr);
 520   assert(OpType >= isl_ast_op_eq && OpType <= isl_ast_op_gt &&
 521          "Unsupported ICmp isl ast expression");
 522   static_assert(isl_ast_op_eq + 4 == isl_ast_op_gt,
 523                 "Isl ast op type interface changed");
 524
 525   CmpInst::Predicate Predicates[5][2] = {
 526       {CmpInst::ICMP_EQ, CmpInst::ICMP_EQ},
 527       {CmpInst::ICMP_SLE, CmpInst::ICMP_ULE},
 528       {CmpInst::ICMP_SLT, CmpInst::ICMP_ULT},
 529       {CmpInst::ICMP_SGE, CmpInst::ICMP_UGE},
 530       {CmpInst::ICMP_SGT, CmpInst::ICMP_UGT},
 531   };
 532
 533   Res = Builder.CreateICmp(Predicates[OpType - isl_ast_op_eq][UseUnsignedCmp],
 534                            LHS, RHS);
 535
 536   isl_ast_expr_free(Expr);
 537   return Res;
 538 }
 539
 540 Value *IslExprBuilder::createOpBoolean(__isl_take isl_ast_expr *Expr) {
 541   assert(isl_ast_expr_get_type(Expr) == isl_ast_expr_op &&
 542          "Expected an isl_ast_expr_op expression");
 543
 544   Value *LHS, *RHS, *Res;
 545   isl_ast_op_type OpType;
 546
 547   OpType = isl_ast_expr_get_op_type(Expr);
 548
 549   assert((OpType == isl_ast_op_and || OpType == isl_ast_op_or) &&
 550          "Unsupported isl_ast_op_type");
 551
 552   LHS = create(isl_ast_expr_get_op_arg(Expr, 0));
 553   RHS = create(isl_ast_expr_get_op_arg(Expr, 1));
 554
 555   // Even though the isl pretty printer prints the expressions as 'exp && exp'
 556   // or 'exp || exp', we actually code generate the bitwise expressions
 557   // 'exp & exp' or 'exp | exp'. This forces the evaluation of both branches,
 558   // but it is, due to the use of i1 types, otherwise equivalent. The reason
 559   // to go for bitwise operations is, that we assume the reduced control flow
 560   // will outweigh the overhead introduced by evaluating unneeded expressions.
 561   // The isl code generation currently does not take advantage of the fact that
 562   // the expression after an '||' or '&&' is in some cases not evaluated.
 563   // Evaluating it anyways does not cause any undefined behaviour.
 564   //
 565   // TODO: Document in isl itself, that the unconditionally evaluating the
 566   // second part of '||' or '&&' expressions is safe.
 567   if (!LHS->getType()->isIntegerTy(1))
 568     LHS = Builder.CreateIsNotNull(LHS);
 569   if (!RHS->getType()->isIntegerTy(1))
 570     RHS = Builder.CreateIsNotNull(RHS);
 571
 572   switch (OpType) {
 573   default:
 574     llvm_unreachable("Unsupported boolean expression");
 575   case isl_ast_op_and:
 576     Res = Builder.CreateAnd(LHS, RHS);
 577     break;
 578   case isl_ast_op_or:
 579     Res = Builder.CreateOr(LHS, RHS);
 580     break;
 581   }
 582
 583   isl_ast_expr_free(Expr);
 584   return Res;
 585 }
 586
 587 Value *
 588 IslExprBuilder::createOpBooleanConditional(__isl_take isl_ast_expr *Expr) {
 589   assert(isl_ast_expr_get_type(Expr) == isl_ast_expr_op &&
 590          "Expected an isl_ast_expr_op expression");
 591
 592   Value *LHS, *RHS;
 593   isl_ast_op_type OpType;
 594
 595   Function *F = Builder.GetInsertBlock()->getParent();
 596   LLVMContext &Context = F->getContext();
 597
 598   OpType = isl_ast_expr_get_op_type(Expr);
 599
 600   assert((OpType == isl_ast_op_and_then || OpType == isl_ast_op_or_else) &&
 601          "Unsupported isl_ast_op_type");
 602
 603   auto InsertBB = Builder.GetInsertBlock();
 604   auto InsertPoint = Builder.GetInsertPoint();
 605   auto NextBB = SplitBlock(InsertBB, &*InsertPoint, &DT, &LI);
 606   BasicBlock *CondBB = BasicBlock::Create(Context, "polly.cond", F);
 607   LI.changeLoopFor(CondBB, LI.getLoopFor(InsertBB));
 608   DT.addNewBlock(CondBB, InsertBB);
 609
 610   InsertBB->getTerminator()->eraseFromParent();
 611   Builder.SetInsertPoint(InsertBB);
 612   auto BR = Builder.CreateCondBr(Builder.getTrue(), NextBB, CondBB);
 613
 614   Builder.SetInsertPoint(CondBB);
 615   Builder.CreateBr(NextBB);
 616
 617   Builder.SetInsertPoint(InsertBB->getTerminator());
 618
 619   LHS = create(isl_ast_expr_get_op_arg(Expr, 0));
 620   if (!LHS->getType()->isIntegerTy(1))
 621     LHS = Builder.CreateIsNotNull(LHS);
 622   auto LeftBB = Builder.GetInsertBlock();
 623
 624   if (OpType == isl_ast_op_and || OpType == isl_ast_op_and_then)
 625     BR->setCondition(Builder.CreateNeg(LHS));
 626   else
 627     BR->setCondition(LHS);
 628
 629   Builder.SetInsertPoint(CondBB->getTerminator());
 630   RHS = create(isl_ast_expr_get_op_arg(Expr, 1));
 631   if (!RHS->getType()->isIntegerTy(1))
 632     RHS = Builder.CreateIsNotNull(RHS);
 633   auto RightBB = Builder.GetInsertBlock();
 634
 635   Builder.SetInsertPoint(NextBB->getTerminator());
 636   auto PHI = Builder.CreatePHI(Builder.getInt1Ty(), 2);
 637   PHI->addIncoming(OpType == isl_ast_op_and_then ? Builder.getFalse()
 638                                                  : Builder.getTrue(),
 639                    LeftBB);
 640   PHI->addIncoming(RHS, RightBB);
 641
 642   isl_ast_expr_free(Expr);
 643   return PHI;
 644 }
 645
 646 Value *IslExprBuilder::createOp(__isl_take isl_ast_expr *Expr) {
 647   assert(isl_ast_expr_get_type(Expr) == isl_ast_expr_op &&
 648          "Expression not of type isl_ast_expr_op");
 649   switch (isl_ast_expr_get_op_type(Expr)) {
 650   case isl_ast_op_error:
 651   case isl_ast_op_cond:
 652   case isl_ast_op_call:
 653   case isl_ast_op_member:
 654     llvm_unreachable("Unsupported isl ast expression");
 655   case isl_ast_op_access:
 656     return createOpAccess(Expr);
 657   case isl_ast_op_max:
 658   case isl_ast_op_min:
 659     return createOpNAry(Expr);
 660   case isl_ast_op_add:
 661   case isl_ast_op_sub:
 662   case isl_ast_op_mul:
 663   case isl_ast_op_div:
 664   case isl_ast_op_fdiv_q: // Round towards -infty
 665   case isl_ast_op_pdiv_q: // Dividend is non-negative
 666   case isl_ast_op_pdiv_r: // Dividend is non-negative
 667   case isl_ast_op_zdiv_r: // Result only compared against zero
 668     return createOpBin(Expr);
 669   case isl_ast_op_minus:
 670     return createOpUnary(Expr);
 671   case isl_ast_op_select:
 672     return createOpSelect(Expr);
 673   case isl_ast_op_and:
 674   case isl_ast_op_or:
 675     return createOpBoolean(Expr);
 676   case isl_ast_op_and_then:
 677   case isl_ast_op_or_else:
 678     return createOpBooleanConditional(Expr);
 679   case isl_ast_op_eq:
 680   case isl_ast_op_le:
 681   case isl_ast_op_lt:
 682   case isl_ast_op_ge:
 683   case isl_ast_op_gt:
 684     return createOpICmp(Expr);
 685   case isl_ast_op_address_of:
 686     return createOpAddressOf(Expr);
 687   }
 688
 689   llvm_unreachable("Unsupported isl_ast_expr_op kind.");
 690 }
 691
 692 Value *IslExprBuilder::createOpAddressOf(__isl_take isl_ast_expr *Expr) {
 693   assert(isl_ast_expr_get_type(Expr) == isl_ast_expr_op &&
 694          "Expected an isl_ast_expr_op expression.");
 695   assert(isl_ast_expr_get_op_n_arg(Expr) == 1 && "Address of should be unary.");
 696
 697   isl_ast_expr *Op = isl_ast_expr_get_op_arg(Expr, 0);
 698   assert(isl_ast_expr_get_type(Op) == isl_ast_expr_op &&
 699          "Expected address of operator to be an isl_ast_expr_op expression.");
 700   assert(isl_ast_expr_get_op_type(Op) == isl_ast_op_access &&
 701          "Expected address of operator to be an access expression.");
 702
 703   Value *V = createAccessAddress(Op).first;
 704
 705   isl_ast_expr_free(Expr);
 706
 707   return V;
 708 }
 709
 710 Value *IslExprBuilder::createId(__isl_take isl_ast_expr *Expr) {
 711   assert(isl_ast_expr_get_type(Expr) == isl_ast_expr_id &&
 712          "Expression not of type isl_ast_expr_ident");
 713
 714   isl_id *Id;
 715   Value *V;
 716
 717   Id = isl_ast_expr_get_id(Expr);
 718
 719   assert(IDToValue.count(Id) && "Identifier not found");
 720
 721   V = IDToValue[Id];
 722   if (!V)
 723     V = UndefValue::get(getType(Expr));
 724
 725   if (V->getType()->isPointerTy())
 726     V = Builder.CreatePtrToInt(V, Builder.getIntNTy(DL.getPointerSizeInBits()));
 727
 728   assert(V && "Unknown parameter id found");
 729
 730   isl_id_free(Id);
 731   isl_ast_expr_free(Expr);
 732
 733   return V;
 734 }
 735
 736 IntegerType *IslExprBuilder::getType(__isl_keep isl_ast_expr *Expr) {
 737   // XXX: We assume i64 is large enough. This is often true, but in general
 738   //      incorrect. Also, on 32bit architectures, it would be beneficial to
 739   //      use a smaller type. We can and should directly derive this information
 740   //      during code generation.
 741   return IntegerType::get(Builder.getContext(), 64);
 742 }
 743
 744 Value *IslExprBuilder::createInt(__isl_take isl_ast_expr *Expr) {
 745   assert(isl_ast_expr_get_type(Expr) == isl_ast_expr_int &&
 746          "Expression not of type isl_ast_expr_int");
 747   isl_val *Val;
 748   Value *V;
 749   APInt APValue;
 750   IntegerType *T;
 751
 752   Val = isl_ast_expr_get_val(Expr);
 753   APValue = APIntFromVal(Val);
 754
 755   auto BitWidth = APValue.getBitWidth();
 756   if (BitWidth <= 64)
 757     T = getType(Expr);
 758   else
 759     T = Builder.getIntNTy(BitWidth);
 760
 761   APValue = APValue.sext(T->getBitWidth());
 762   V = ConstantInt::get(T, APValue);
 763
 764   isl_ast_expr_free(Expr);
 765   return V;
 766 }
 767
 768 Value *IslExprBuilder::create(__isl_take isl_ast_expr *Expr) {
 769   switch (isl_ast_expr_get_type(Expr)) {
 770   case isl_ast_expr_error:
 771     llvm_unreachable("Code generation error");
 772   case isl_ast_expr_op:
 773     return createOp(Expr);
 774   case isl_ast_expr_id:
 775     return createId(Expr);
 776   case isl_ast_expr_int:
 777     return createInt(Expr);
 778   }
 779
 780   llvm_unreachable("Unexpected enum value");
 781 }