800 lines · 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-exception6//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 18using namespace llvm;19using namespace polly;20 21/// Different overflow tracking modes.22enum 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 28static 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 39IslExprBuilder::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 50void 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 62void IslExprBuilder::setTrackOverflow(bool Enable) {63 // If potential overflows are tracked always or never we ignore requests64 // 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 77Value *IslExprBuilder::getOverflowState() const {78 // If the overflow tracking was requested but it is disabled we avoid the79 // additional nullptr checks at the call sides but instead provide a80 // meaningful result.81 if (OTMode == OT_NEVER)82 return Builder.getFalse();83 return OverflowState;84}85 86bool 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 112Value *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 could154 // cause dominance problems. Instead we will always keep the last overflow155 // flag as current state.156 if (OTMode == OT_ALWAYS)157 OverflowState = OverflowFlag;158 else159 OverflowState =160 Builder.CreateOr(OverflowState, OverflowFlag, "polly.overflow.state");161 162 return Builder.CreateExtractValue(ResultStruct, 0, Name + ".res");163}164 165Value *IslExprBuilder::createAdd(Value *LHS, Value *RHS, const Twine &Name) {166 return createBinOp(Instruction::Add, LHS, RHS, Name);167}168 169Value *IslExprBuilder::createSub(Value *LHS, Value *RHS, const Twine &Name) {170 return createBinOp(Instruction::Sub, LHS, RHS, Name);171}172 173Value *IslExprBuilder::createMul(Value *LHS, Value *RHS, const Twine &Name) {174 return createBinOp(Instruction::Mul, LHS, RHS, Name);175}176 177Type *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 else183 return T1;184}185 186Value *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 205Value *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 can240 // help in cases where we have larger operands (e.g. i67) but the result is241 // known to fit into i64. Without the truncation, the larger i67 type may242 // force all subsequent operations to be performed on a non-native type.243 isl_ast_expr_free(Expr);244 return V;245}246 247std::pair<Value *, Type *>248IslExprBuilder::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 else275 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 last317 // 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 LoopToScev324 // 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 350Value *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 357Value *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 than380 // the type of the individual operands. For other operations such as '/', the381 // result type cannot be larger than the type of the individual operand. isl382 // does not calculate correct types for these operations and we consequently383 // 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 nothing391 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-negative423 Res = Builder.CreateUDiv(LHS, RHS, "pexp.p_div_q");424 break;425 case isl_ast_op_fdiv_q: { // Round towards -infty426 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 yield434 // incorrect overflow in some edge cases.435 //436 // floord(n,d) ((n < 0) ? (n - d + 1) : n) / d437 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-negative448 Res = Builder.CreateURem(LHS, RHS, "pexp.pdiv_r");449 break;450 451 case isl_ast_op_zdiv_r: // Result only compared against zero452 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 can457 // help in cases where we have larger operands (e.g. i67) but the result is458 // known to fit into i64. Without the truncation, the larger i67 type may459 // force all subsequent operations to be performed on a non-native type.460 isl_ast_expr_free(Expr);461 return Res;462}463 464Value *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 491Value *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 551Value *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 expressions568 // '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 reason570 // to go for bitwise operations is, that we assume the reduced control flow571 // will outweigh the overhead introduced by evaluating unneeded expressions.572 // The isl code generation currently does not take advantage of the fact that573 // 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 the577 // 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 598Value *599IslExprBuilder::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, InsertBB->getTerminator()->getIterator());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 else638 BR->setCondition(LHS);639 640 Builder.SetInsertPoint(CondBB, CondBB->getTerminator()->getIterator());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, NextBB->getTerminator()->getIterator());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 657Value *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 -infty676 case isl_ast_op_pdiv_q: // Dividend is non-negative677 case isl_ast_op_pdiv_r: // Dividend is non-negative678 case isl_ast_op_zdiv_r: // Result only compared against zero679 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 703Value *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 721Value *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 747IntegerType *IslExprBuilder::getType(__isl_keep isl_ast_expr *Expr) {748 // XXX: We assume i64 is large enough. This is often true, but in general749 // incorrect. Also, on 32bit architectures, it would be beneficial to750 // use a smaller type. We can and should directly derive this information751 // during code generation.752 return IntegerType::get(Builder.getContext(), 64);753}754 755Value *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 else770 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 779Value *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}793 794llvm::Value *IslExprBuilder::createBool(__isl_take isl_ast_expr *Expr) {795 Value *Result = create(Expr);796 if (!Result->getType()->isIntegerTy(1))797 Result = Builder.CreateICmpNE(Result, Builder.getInt1(false));798 return Result;799}800