16#include "llvm/Transforms/Utils/BasicBlockUtils.h"
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."),
34 "Track the overflow bit if requested."),
36 "Always track the overflow bit.")),
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) {
82 auto BitWidth = APValue.getBitWidth();
83 return BitWidth >= 64;
90 for (
int i = 0; i < NumArgs; i++) {
100 Value *RHS,
const Twine &Name) {
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);
111 llvm_unreachable(
"Unknown binary operator!");
118 case Instruction::Add:
119 F = Intrinsic::getDeclaration(
M, Intrinsic::sadd_with_overflow,
122 case Instruction::Sub:
123 F = Intrinsic::getDeclaration(
M, Intrinsic::ssub_with_overflow,
126 case Instruction::Mul:
127 F = Intrinsic::getDeclaration(
M, Intrinsic::smul_with_overflow,
131 llvm_unreachable(
"No overflow intrinsic for binary operator found!");
134 auto *ResultStruct =
Builder.CreateCall(F, {LHS, RHS}, Name);
135 assert(ResultStruct->getType()->isStructTy());
138 Builder.CreateExtractValue(ResultStruct, 1, Name +
".obit");
149 return Builder.CreateExtractValue(ResultStruct, 0, Name +
".res");
153 return createBinOp(Instruction::Add, LHS, RHS, Name);
157 return createBinOp(Instruction::Sub, LHS, RHS, Name);
161 return createBinOp(Instruction::Mul, LHS, RHS, Name);
165 assert(isa<IntegerType>(T1) && isa<IntegerType>(T2));
167 if (T1->getPrimitiveSizeInBits() < T2->getPrimitiveSizeInBits())
175 "Unsupported unary operation");
179 assert(MaxType->isIntegerTy() &&
180 "Unary expressions can only be created for integer types");
185 if (MaxType != V->getType())
186 V =
Builder.CreateSExt(V, MaxType);
189 return createSub(ConstantInt::getNullValue(MaxType), V);
194 "isl ast expression not of type isl_ast_op");
196 "We need at least two operands in an n-ary operation");
198 CmpInst::Predicate Pred;
201 llvm_unreachable(
"This is not a an n-ary isl ast expression");
203 Pred = CmpInst::ICMP_SGT;
206 Pred = CmpInst::ICMP_SLT;
216 if (Ty != OpV->getType())
217 OpV =
Builder.CreateSExt(OpV, Ty);
219 if (Ty != V->getType())
223 V =
Builder.CreateSelect(Cmp, V, OpV);
234std::pair<Value *, Type *>
237 "isl ast expression not of type isl_ast_op");
239 "not an access isl ast expression");
241 "We need at least two operands to create a member access.");
243 Value *Base, *IndexOp, *Access;
257 SAI = (*IDToSAI)[BaseId];
264 assert(SAI &&
"No ScopArrayInfo found for this isl_id.");
268 if (
auto NewBase =
GlobalMap.lookup(Base))
271 assert(Base->getType()->isPointerTy() &&
"Access base should be a pointer");
272 StringRef BaseName = Base->getName();
284 assert(NextIndex->getType()->isIntegerTy() &&
285 "Access index should be an integer");
293 Type *Ty =
getWidestType(NextIndex->getType(), IndexOp->getType());
295 if (Ty != NextIndex->getType())
296 NextIndex =
Builder.CreateIntCast(NextIndex, Ty,
true);
297 if (Ty != IndexOp->getType())
298 IndexOp =
Builder.CreateIntCast(IndexOp, Ty,
true);
300 IndexOp =
createAdd(IndexOp, NextIndex,
"polly.access.add." + BaseName);
310 llvm::ValueToSCEVMapTy Map;
312 Map[KV.first] =
SE.getSCEV(KV.second);
313 DimSCEV = SCEVParameterRewriter::rewrite(DimSCEV,
SE, Map);
316 &*
Builder.GetInsertPoint(),
nullptr,
319 Type *Ty =
getWidestType(DimSize->getType(), IndexOp->getType());
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);
331 "polly.access." + BaseName);
341 assert(Info.first &&
"Could not create op access address");
342 return Builder.CreateLoad(Info.second, Info.first,
343 Info.first->getName() +
".load");
352 "isl ast expression not of type isl_ast_op");
354 "not a binary isl ast expression");
361 Type *LHSType = LHS->getType();
362 Type *RHSType = RHS->getType();
387 llvm_unreachable(
"This is no binary isl ast expression");
390 if (MaxType != RHS->getType())
391 RHS =
Builder.CreateSExt(RHS, MaxType);
393 if (MaxType != LHS->getType())
394 LHS =
Builder.CreateSExt(LHS, MaxType);
398 llvm_unreachable(
"This is no binary isl ast expression");
409 Res =
Builder.CreateSDiv(LHS, RHS,
"pexp.div",
true);
412 Res =
Builder.CreateUDiv(LHS, RHS,
"pexp.p_div_q");
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");
426 Value *One = ConstantInt::get(MaxType, 1);
427 Value *Zero = ConstantInt::get(MaxType, 0);
430 Value *isNegative =
Builder.CreateICmpSLT(LHS, Zero,
"pexp.fdiv_q.2");
432 Builder.CreateSelect(isNegative, Sum2, LHS,
"pexp.fdiv_q.3");
433 Res =
Builder.CreateSDiv(Dividend, RHS,
"pexp.fdiv_q.4");
437 Res =
Builder.CreateURem(LHS, RHS,
"pexp.pdiv_r");
441 Res =
Builder.CreateSRem(LHS, RHS,
"pexp.zdiv_r");
455 "Unsupported unary isl ast expression");
456 Value *LHS, *RHS, *Cond;
460 if (!Cond->getType()->isIntegerTy(1))
461 Cond =
Builder.CreateIsNotNull(Cond);
469 if (MaxType != RHS->getType())
470 RHS =
Builder.CreateSExt(RHS, MaxType);
472 if (MaxType != LHS->getType())
473 LHS =
Builder.CreateSExt(LHS, MaxType);
477 return Builder.CreateSelect(Cond, LHS, RHS);
482 "Expected an isl_ast_expr_op expression");
488 bool HasNonAddressOfOperand =
497 auto *LHSTy = LHS->getType();
498 auto *RHSTy = RHS->getType();
499 bool IsPtrType = LHSTy->isPointerTy() || RHSTy->isPointerTy();
500 bool UseUnsignedCmp = IsPtrType && !HasNonAddressOfOperand;
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);
508 if (LHS->getType() != RHS->getType()) {
509 Type *MaxType = LHS->getType();
512 if (MaxType != RHS->getType())
513 RHS =
Builder.CreateSExt(RHS, MaxType);
515 if (MaxType != LHS->getType())
516 LHS =
Builder.CreateSExt(LHS, MaxType);
521 "Unsupported ICmp isl ast expression");
523 "Isl ast op type interface changed");
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},
542 "Expected an isl_ast_expr_op expression");
550 "Unsupported isl_ast_op_type");
567 if (!LHS->getType()->isIntegerTy(1))
568 LHS =
Builder.CreateIsNotNull(LHS);
569 if (!RHS->getType()->isIntegerTy(1))
570 RHS =
Builder.CreateIsNotNull(RHS);
574 llvm_unreachable(
"Unsupported boolean expression");
590 "Expected an isl_ast_expr_op expression");
596 LLVMContext &Context = F->getContext();
601 "Unsupported isl_ast_op_type");
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);
610 InsertBB->getTerminator()->eraseFromParent();
611 Builder.SetInsertPoint(InsertBB);
612 auto BR =
Builder.CreateCondBr(
Builder.getTrue(), NextBB, CondBB);
614 Builder.SetInsertPoint(CondBB);
617 Builder.SetInsertPoint(InsertBB->getTerminator());
620 if (!LHS->getType()->isIntegerTy(1))
621 LHS =
Builder.CreateIsNotNull(LHS);
622 auto LeftBB =
Builder.GetInsertBlock();
625 BR->setCondition(
Builder.CreateNeg(LHS));
627 BR->setCondition(LHS);
629 Builder.SetInsertPoint(CondBB->getTerminator());
631 if (!RHS->getType()->isIntegerTy(1))
632 RHS =
Builder.CreateIsNotNull(RHS);
633 auto RightBB =
Builder.GetInsertBlock();
635 Builder.SetInsertPoint(NextBB->getTerminator());
640 PHI->addIncoming(RHS, RightBB);
648 "Expression not of type isl_ast_expr_op");
654 llvm_unreachable(
"Unsupported isl ast expression");
689 llvm_unreachable(
"Unsupported isl_ast_expr_op kind.");
694 "Expected an isl_ast_expr_op expression.");
699 "Expected address of operator to be an isl_ast_expr_op expression.");
701 "Expected address of operator to be an access expression.");
712 "Expression not of type isl_ast_expr_ident");
723 V = UndefValue::get(
getType(Expr));
725 if (V->getType()->isPointerTy())
726 V =
Builder.CreatePtrToInt(V,
Builder.getIntNTy(
DL.getPointerSizeInBits()));
728 assert(V &&
"Unknown parameter id found");
741 return IntegerType::get(
Builder.getContext(), 64);
746 "Expression not of type isl_ast_expr_int");
755 auto BitWidth = APValue.getBitWidth();
759 T =
Builder.getIntNTy(BitWidth);
761 APValue = APValue.sext(T->getBitWidth());
762 V = ConstantInt::get(T, APValue);
771 llvm_unreachable(
"Code generation error");
780 llvm_unreachable(
"Unexpected enum value");
polly dump Polly Dump Function
polly dump Polly Dump Module
OverflowTrackingChoice
Different overflow tracking modes.
@ OT_ALWAYS
Always track potential overflows.
@ OT_NEVER
Never tack potential overflows.
@ OT_REQUEST
Track potential overflows if requested.
static cl::opt< OverflowTrackingChoice > OTMode("polly-overflow-tracking", cl::desc("Define where potential integer overflows in generated " "expressions should be tracked."), cl::values(clEnumValN(OT_NEVER, "never", "Never track the overflow bit."), clEnumValN(OT_REQUEST, "request", "Track the overflow bit if requested."), clEnumValN(OT_ALWAYS, "always", "Always track the overflow bit.")), cl::Hidden, cl::init(OT_REQUEST), cl::cat(PollyCategory))
llvm::cl::OptionCategory PollyCategory
static RegisterPass< ScopPrinterWrapperPass > M("dot-scops", "Polly - Print Scops of function")
__isl_null isl_ast_expr * isl_ast_expr_free(__isl_take isl_ast_expr *expr)
isl_size isl_ast_expr_get_op_n_arg(__isl_keep isl_ast_expr *expr)
enum isl_ast_expr_op_type isl_ast_expr_get_op_type(__isl_keep isl_ast_expr *expr)
__isl_give isl_ast_expr * isl_ast_expr_get_op_arg(__isl_keep isl_ast_expr *expr, int pos)
__isl_give isl_id * isl_ast_expr_get_id(__isl_keep isl_ast_expr *expr)
__isl_give isl_val * isl_ast_expr_get_val(__isl_keep isl_ast_expr *expr)
#define isl_ast_op_fdiv_q
#define isl_ast_op_member
#define isl_ast_op_pdiv_r
#define isl_ast_op_zdiv_r
#define isl_ast_op_or_else
#define isl_ast_op_access
#define isl_ast_op_select
#define isl_ast_op_pdiv_q
#define isl_ast_op_and_then
#define isl_ast_op_address_of
isl::ast_expr get_op_arg(int pos) const
__isl_keep isl_ast_expr * get() const
llvm::BasicBlock * StartBlock
bool hasLargeInts(isl::ast_expr Expr)
Check if an Expr contains integer constants larger than 64 bit.
llvm::Value * createAdd(llvm::Value *LHS, llvm::Value *RHS, const llvm::Twine &Name="")
Create an addition and track overflows if requested.
llvm::Value * createOpBoolean(__isl_take isl_ast_expr *Expr)
llvm::Value * createOpICmp(__isl_take isl_ast_expr *Expr)
llvm::Value * createBinOp(llvm::BinaryOperator::BinaryOps Opc, llvm::Value *LHS, llvm::Value *RHS, const llvm::Twine &Name)
Create a binary operation Opc and track overflows if requested.
IDToScopArrayInfoTy * IDToSAI
A map from isl_ids to ScopArrayInfo objects.
llvm::Value * createOpAccess(__isl_take isl_ast_expr *Expr)
void setTrackOverflow(bool Enable)
Change if runtime overflows are tracked or not.
IslExprBuilder(Scop &S, PollyIRBuilder &Builder, IDToValueTy &IDToValue, ValueMapT &GlobalMap, const llvm::DataLayout &DL, llvm::ScalarEvolution &SE, llvm::DominatorTree &DT, llvm::LoopInfo &LI, llvm::BasicBlock *StartBlock)
Construct an IslExprBuilder.
llvm::Value * getOverflowState() const
Return the current overflow status or nullptr if it is not tracked.
const llvm::DataLayout & DL
llvm::MapVector< isl_id *, llvm::AssertingVH< llvm::Value > > IDToValueTy
A map from isl_ids to llvm::Values.
llvm::Value * create(__isl_take isl_ast_expr *Expr)
Create LLVM-IR for an isl_ast_expr[ession].
llvm::Type * getWidestType(llvm::Type *T1, llvm::Type *T2)
Return the largest of two types.
std::pair< llvm::Value *, llvm::Type * > createAccessAddress(__isl_take isl_ast_expr *Expr)
Create LLVM-IR that computes the memory location of an access expression.
llvm::Value * createOpAddressOf(__isl_take isl_ast_expr *Expr)
llvm::Value * createMul(llvm::Value *LHS, llvm::Value *RHS, const llvm::Twine &Name="")
Create a multiplication and track overflows if requested.
llvm::Value * OverflowState
Flag that will be set if an overflow occurred at runtime.
llvm::Value * createOpNAry(__isl_take isl_ast_expr *Expr)
llvm::IntegerType * getType(__isl_keep isl_ast_expr *Expr)
Return the type with which this expression should be computed.
llvm::Value * createOpBooleanConditional(__isl_take isl_ast_expr *Expr)
llvm::ScalarEvolution & SE
llvm::Value * createOpSelect(__isl_take isl_ast_expr *Expr)
llvm::Value * createOp(__isl_take isl_ast_expr *Expr)
llvm::Value * createOpUnary(__isl_take isl_ast_expr *Expr)
llvm::Value * createInt(__isl_take isl_ast_expr *Expr)
llvm::Value * createId(__isl_take isl_ast_expr *Expr)
llvm::Value * createSub(llvm::Value *LHS, llvm::Value *RHS, const llvm::Twine &Name="")
Create a subtraction and track overflows if requested.
llvm::Value * createOpBin(__isl_take isl_ast_expr *Expr)
A class to store information about arrays in the SCoP.
const SCEV * getDimensionSize(unsigned Dim) const
Return the size of dimension dim as SCEV*.
static const ScopArrayInfo * getFromId(isl::id Id)
Access the ScopArrayInfo associated with an isl Id.
Value * getBasePtr() const
Return the base pointer.
Type * getElementType() const
Get the canonical element type of this array.
__isl_export __isl_keep const char * isl_id_get_name(__isl_keep isl_id *id)
__isl_null isl_id * isl_id_free(__isl_take isl_id *id)
enum isl_ast_expr_type isl_ast_expr_get_type(__isl_keep isl_ast_expr *expr)
boolean manage(isl_bool val)
This file contains the declaration of the PolyhedralInfo class, which will provide an interface to ex...
llvm::Value * expandCodeFor(Scop &S, llvm::ScalarEvolution &SE, const llvm::DataLayout &DL, const char *Name, const llvm::SCEV *E, llvm::Type *Ty, llvm::Instruction *IP, ValueMapT *VMap, llvm::BasicBlock *RTCBB)
Wrapper for SCEVExpander extended to all Polly features.
@ Value
MemoryKind::Value: Models an llvm::Value.
@ PHI
MemoryKind::PHI: Models PHI nodes within the SCoP.
llvm::IRBuilder< llvm::ConstantFolder, IRInserter > PollyIRBuilder
llvm::DenseMap< llvm::AssertingVH< llvm::Value >, llvm::AssertingVH< llvm::Value > > ValueMapT
Type to remap values.
llvm::APInt APIntFromVal(__isl_take isl_val *Val)
Translate isl_val to llvm::APInt.
static void createCPUPrinter(PollyIRBuilder &Builder, Args... args)
Print a set of LLVM-IR Values or StringRefs via printf.