17#include "llvm/Analysis/LoopInfo.h"
18#include "llvm/Analysis/RegionInfo.h"
19#include "llvm/Analysis/ScalarEvolution.h"
20#include "llvm/Analysis/ScalarEvolutionExpressions.h"
21#include "llvm/Transforms/Utils/BasicBlockUtils.h"
22#include "llvm/Transforms/Utils/LoopUtils.h"
23#include "llvm/Transforms/Utils/ScalarEvolutionExpander.h"
29#define DEBUG_TYPE "polly-scop-helper"
33 cl::desc(
"Allow calls to the specified functions in SCoPs even if their "
34 "side-effects are unknown. This can be used to do debug output in "
35 "Polly-transformed code."),
43 BasicBlock *EnteringBB = R->getEnteringBlock();
44 BasicBlock *
Entry = R->getEntry();
58 SmallVector<BasicBlock *, 4> Preds;
59 for (BasicBlock *P : predecessors(
Entry))
63 BasicBlock *NewEntering =
64 SplitBlockPredecessors(
Entry, Preds,
".region_entering", DT, LI);
68 for (BasicBlock *ExitPred : predecessors(NewEntering)) {
69 Region *RegionOfPred = RI->getRegionFor(ExitPred);
70 if (RegionOfPred->getExit() !=
Entry)
73 while (!RegionOfPred->isTopLevelRegion() &&
74 RegionOfPred->getExit() ==
Entry) {
75 RegionOfPred->replaceExit(NewEntering);
76 RegionOfPred = RegionOfPred->getParent();
81 Region *AncestorR = R->getParent();
82 RI->setRegionFor(NewEntering, AncestorR);
83 while (!AncestorR->isTopLevelRegion() && AncestorR->getEntry() ==
Entry) {
84 AncestorR->replaceEntry(NewEntering);
85 AncestorR = AncestorR->getParent();
89 EnteringBB = NewEntering;
91 assert(R->getEnteringBlock() == EnteringBB);
107 BasicBlock *ExitBB = R->getExit();
108 BasicBlock *ExitingBB = R->getExitingBlock();
118 SmallVector<BasicBlock *, 4> Preds;
119 for (BasicBlock *P : predecessors(ExitBB))
128 SplitBlockPredecessors(ExitBB, Preds,
".region_exiting", DT, LI);
136 RI->setRegionFor(ExitingBB, R);
139 R->replaceExitRecursive(ExitingBB);
140 R->replaceExit(ExitBB);
142 assert(ExitingBB == R->getExitingBlock());
155 assert(R && !R->isTopLevelRegion());
156 assert(!RI || RI == R->getRegionInfo());
158 "RegionInfo requires DominatorTree to be updated as well");
168static BasicBlock *
splitBlock(BasicBlock *Old, Instruction *SplitPt,
169 DominatorTree *DT, llvm::LoopInfo *LI,
179 BasicBlock *NewBlock = llvm::SplitBlock(Old, SplitPt, DT, LI);
182 Region *R = RI->getRegionFor(Old);
183 RI->setRegionFor(NewBlock, R);
198 LoopInfo *LI, RegionInfo *RI) {
201 BasicBlock::iterator I = EntryBlock->begin();
202 while (isa<AllocaInst>(I))
210 auto *DTWP = P->getAnalysisIfAvailable<DominatorTreeWrapperPass>();
211 auto *DT = DTWP ? &DTWP->getDomTree() :
nullptr;
212 auto *LIWP = P->getAnalysisIfAvailable<LoopInfoWrapperPass>();
213 auto *LI = LIWP ? &LIWP->getLoopInfo() :
nullptr;
214 RegionInfoPass *RIP = P->getAnalysisIfAvailable<RegionInfoPass>();
215 RegionInfo *RI = RIP ? &RIP->getRegionInfo() :
nullptr;
224 BasicBlock *BB,
bool RTC) {
226 "Assumptions without a basic block must be parameter sets");
227 if (RecordedAssumptions)
228 RecordedAssumptions->push_back({
Kind, Sign, Set, Loc, BB, RTC});
252 return Expander.expandCodeFor(E, Ty, I);
261 const SCEV *Result = SCEVVisitor::visit(E);
277 if (!Inst || !
R.contains(Inst))
280 assert(!Inst->mayThrow() && !Inst->mayReadOrWriteMemory() &&
281 !isa<PHINode>(Inst));
283 auto *InstClone = Inst->clone();
284 for (
auto &Op : Inst->operands()) {
285 assert(
SE.isSCEVable(Op->getType()));
286 auto *OpSCEV =
SE.getSCEV(Op);
288 InstClone->replaceUsesOfWith(Op, OpClone);
291 InstClone->setName(
Name + Inst->getName());
292 InstClone->insertBefore(IP);
293 return SE.getSCEV(InstClone);
299 Value *NewVal =
VMap ?
VMap->lookup(E->getValue()) :
nullptr;
301 auto *NewE =
SE.getSCEV(NewVal);
309 Instruction *Inst = dyn_cast<Instruction>(E->getValue());
311 if (Inst && !
R.contains(Inst))
313 else if (Inst &&
RTCBB->getParent() == Inst->getFunction())
314 IP =
RTCBB->getTerminator();
316 IP =
RTCBB->getParent()->getEntryBlock().getTerminator();
318 if (!Inst || (Inst->getOpcode() != Instruction::SRem &&
319 Inst->getOpcode() != Instruction::SDiv))
322 const SCEV *LHSScev =
SE.getSCEV(Inst->getOperand(0));
323 const SCEV *RHSScev =
SE.getSCEV(Inst->getOperand(1));
325 if (!
SE.isKnownNonZero(RHSScev))
326 RHSScev =
SE.getUMaxExpr(RHSScev,
SE.getConstant(E->getType(), 1));
332 BinaryOperator::Create((Instruction::BinaryOps)Inst->getOpcode(), LHS,
333 RHS, Inst->getName() +
Name, IP->getIterator());
334 return SE.getSCEV(Inst);
344 return SE.getPtrToIntExpr(
visit(E->getOperand()), E->getType());
347 return SE.getTruncateExpr(
visit(E->getOperand()), E->getType());
350 return SE.getZeroExtendExpr(
visit(E->getOperand()), E->getType());
353 return SE.getSignExtendExpr(
visit(E->getOperand()), E->getType());
356 auto *RHSScev =
visit(E->getRHS());
357 if (!
SE.isKnownNonZero(RHSScev))
358 RHSScev =
SE.getUMaxExpr(RHSScev,
SE.getConstant(E->getType(), 1));
359 return SE.getUDivExpr(
visit(E->getLHS()), RHSScev);
362 SmallVector<const SCEV *, 4> NewOps;
363 for (
const SCEV *Op : E->operands())
364 NewOps.push_back(
visit(Op));
365 return SE.getAddExpr(NewOps);
368 SmallVector<const SCEV *, 4> NewOps;
369 for (
const SCEV *Op : E->operands())
370 NewOps.push_back(
visit(Op));
371 return SE.getMulExpr(NewOps);
374 SmallVector<const SCEV *, 4> NewOps;
375 for (
const SCEV *Op : E->operands())
376 NewOps.push_back(
visit(Op));
377 return SE.getUMaxExpr(NewOps);
380 SmallVector<const SCEV *, 4> NewOps;
381 for (
const SCEV *Op : E->operands())
382 NewOps.push_back(
visit(Op));
383 return SE.getSMaxExpr(NewOps);
386 SmallVector<const SCEV *, 4> NewOps;
387 for (
const SCEV *Op : E->operands())
388 NewOps.push_back(
visit(Op));
389 return SE.getUMinExpr(NewOps);
392 SmallVector<const SCEV *, 4> NewOps;
393 for (
const SCEV *Op : E->operands())
394 NewOps.push_back(
visit(Op));
395 return SE.getSMinExpr(NewOps);
398 SmallVector<const SCEV *, 4> NewOps;
399 for (
const SCEV *Op : E->operands())
400 NewOps.push_back(
visit(Op));
401 return SE.getUMinExpr(NewOps,
true);
404 SmallVector<const SCEV *, 4> NewOps;
405 for (
const SCEV *Op : E->operands())
406 NewOps.push_back(
visit(Op));
407 return SE.getAddRecExpr(NewOps, E->getLoop(), E->getNoWrapFlags());
413 const char *Name,
const SCEV *E, Type *Ty,
416 ScopExpander Expander(
S.getRegion(), SE, DL, Name, VMap, RTCBB);
417 return Expander.expandCodeFor(E, Ty, IP);
421 if (BranchInst *BR = dyn_cast<BranchInst>(TI)) {
422 if (BR->isUnconditional())
423 return ConstantInt::getTrue(Type::getInt1Ty(TI->getContext()));
425 return BR->getCondition();
428 if (SwitchInst *SI = dyn_cast<SwitchInst>(TI))
429 return SI->getCondition();
440 Loop *L = LI.getLoopFor(
S.getEntry());
442 bool AllContained =
true;
443 for (
auto *BB :
S.blocks())
444 AllContained &= L->contains(BB);
447 L = L->getParentLoop();
450 return L ? (
S.contains(L) ? L->getParentLoop() : L) :
nullptr;
454 unsigned NumBlocks = L->getNumBlocks();
455 SmallVector<BasicBlock *, 4> ExitBlocks;
456 L->getExitBlocks(ExitBlocks);
458 for (
auto ExitBlock : ExitBlocks) {
459 if (isa<UnreachableInst>(ExitBlock->getTerminator()))
466 if (!RN->isSubRegion())
469 Region *R = RN->getNodeAs<Region>();
470 return std::distance(R->block_begin(), R->block_end());
474 if (!RN->isSubRegion()) {
475 BasicBlock *BB = RN->getNodeAs<BasicBlock>();
476 Loop *L = LI.getLoopFor(BB);
496 if (!L && isa<UnreachableInst>(BB->getTerminator()) && BB->getPrevNode())
497 L = LI.getLoopFor(BB->getPrevNode());
501 Region *NonAffineSubRegion = RN->getNodeAs<Region>();
502 Loop *L = LI.getLoopFor(NonAffineSubRegion->getEntry());
503 while (L && NonAffineSubRegion->contains(L))
504 L = L->getParentLoop();
509 ScalarEvolution &SE) {
510 for (
const Use &Val : llvm::drop_begin(Gep->operands(), 1)) {
511 const SCEV *PtrSCEV = SE.getSCEVAtScope(Val, L);
512 Loop *OuterLoop = R.outermostLoopInRegion(L);
513 if (!SE.isLoopInvariant(PtrSCEV, OuterLoop))
520 ScalarEvolution &SE,
const DominatorTree &DT,
522 Loop *L = LI.getLoopFor(LInst->getParent());
523 auto *Ptr = LInst->getPointerOperand();
532 if (
auto *GepInst = dyn_cast<GetElementPtrInst>(Ptr)) {
534 if (
auto *DecidingLoad =
535 dyn_cast<LoadInst>(GepInst->getPointerOperand())) {
536 if (KnownInvariantLoads.count(DecidingLoad))
542 const SCEV *PtrSCEV = SE.getSCEVAtScope(Ptr, L);
543 while (L && R.contains(L)) {
544 if (!SE.isLoopInvariant(PtrSCEV, L))
546 L = L->getParentLoop();
549 for (
auto *User : Ptr->users()) {
550 auto *UserI = dyn_cast<Instruction>(User);
551 if (!UserI || !R.contains(UserI))
553 if (!UserI->mayWriteToMemory())
556 auto &BB = *UserI->getParent();
557 if (DT.dominates(&BB, LInst->getParent()))
560 bool DominatesAllPredecessors =
true;
561 if (R.isTopLevelRegion()) {
562 for (BasicBlock &I : *R.getEntry()->getParent())
563 if (isa<ReturnInst>(I.getTerminator()) && !DT.dominates(&BB, &I))
564 DominatesAllPredecessors =
false;
566 for (
auto Pred : predecessors(R.getExit()))
567 if (R.contains(Pred) && !DT.dominates(&BB, Pred))
568 DominatesAllPredecessors =
false;
571 if (!DominatesAllPredecessors)
581 if (
auto *IT = dyn_cast<IntrinsicInst>(V)) {
582 switch (IT->getIntrinsicID()) {
584 case llvm::Intrinsic::lifetime_start:
585 case llvm::Intrinsic::lifetime_end:
587 case llvm::Intrinsic::invariant_start:
588 case llvm::Intrinsic::invariant_end:
590 case llvm::Intrinsic::var_annotation:
591 case llvm::Intrinsic::ptr_annotation:
592 case llvm::Intrinsic::annotation:
593 case llvm::Intrinsic::donothing:
594 case llvm::Intrinsic::assume:
596 case llvm::Intrinsic::dbg_value:
597 case llvm::Intrinsic::dbg_declare:
608 if (!V || !SE->isSCEVable(V->getType()))
612 if (
const SCEV *Scev = SE->getSCEVAtScope(
const_cast<Value *
>(V), Scope))
613 if (!isa<SCEVCouldNotCompute>(Scev))
621 Instruction *UI = dyn_cast<Instruction>(U.getUser());
625 if (PHINode *
PHI = dyn_cast<PHINode>(UI))
626 return PHI->getIncomingBlock(U);
628 return UI->getParent();
633 while (BoxedLoops.count(L))
634 L = L->getParentLoop();
641 Loop *L = LI.getLoopFor(BB);
646 auto *CI = dyn_cast<CallInst>(Inst);
650 Function *CF = CI->getCalledFunction();
659 for (Instruction &Inst : *BB) {
679 for (BasicBlock *RBB : Stmt->
getRegion()->blocks())
691 for (
const MDOperand &
X : drop_begin(LoopMD->operands(), 1)) {
692 auto *OpNode = dyn_cast<MDNode>(
X.get());
696 auto *OpName = dyn_cast<MDString>(OpNode->getOperand(0));
699 if (OpName->getString() == Name)
710 switch (MD->getNumOperands()) {
714 return &MD->getOperand(1);
716 llvm_unreachable(
"loop metadata has 0 or 1 operand");
725 switch (MD->getNumOperands()) {
729 return MD->getOperand(1).get();
731 llvm_unreachable(
"loop metadata must have 0 or 1 operands");
740 switch (MD->getNumOperands()) {
744 if (ConstantInt *IntMD =
745 mdconst::extract_or_null<ConstantInt>(MD->getOperand(1).get()))
746 return IntMD->getZExtValue();
749 llvm_unreachable(
"unexpected number of options");
758 const MDOperand *AttrMD =
763 ConstantInt *IntMD = mdconst::extract_or_null<ConstantInt>(AttrMD->get());
767 return IntMD->getSExtValue();
771 return llvm::hasDisableAllTransformsHint(L);
779 assert(Attr &&
"Must be a valid BandAttr");
786 BandAttr *Attr = reinterpret_cast<BandAttr *>(Ptr);
797 MDNode *LoopID = L->getLoopID();
812 return Id.
get_name() ==
"Loop with Metadata";
polly dump Polly Dump Function
llvm::cl::OptionCategory PollyCategory
static RegisterPass< ScopViewerWrapperPass > X("view-scops", "Polly - View Scops of function")
static std::optional< bool > getOptionalBoolLoopAttribute(MDNode *LoopID, StringRef Name)
static BasicBlock * splitBlock(BasicBlock *Old, Instruction *SplitPt, DominatorTree *DT, llvm::LoopInfo *LI, RegionInfo *RI)
static bool hasDebugCall(BasicBlock *BB)
static void simplifyRegionEntry(Region *R, DominatorTree *DT, LoopInfo *LI, RegionInfo *RI)
static std::optional< const MDOperand * > findNamedMetadataArg(MDNode *LoopID, StringRef Name)
static cl::list< std::string > DebugFunctions("polly-debug-func", cl::desc("Allow calls to the specified functions in SCoPs even if their " "side-effects are unknown. This can be used to do debug output in " "Polly-transformed code."), cl::Hidden, cl::CommaSeparated, cl::cat(PollyCategory))
static MDNode * findNamedMetadataNode(MDNode *LoopMD, StringRef Name)
Find a property in a LoopID.
static void simplifyRegionExit(Region *R, DominatorTree *DT, LoopInfo *LI, RegionInfo *RI)
static bool hasVariantIndex(GetElementPtrInst *Gep, Loop *L, Region &R, ScalarEvolution &SE)
__isl_give isl_id * release()
std::string get_name() const
static isl::id alloc(isl::ctx ctx, const std::string &name, void *user)
boolean is_params() const
BasicBlock * getEntryBlock() const
Return a BasicBlock from this statement.
const std::vector< Instruction * > & getInstructions() const
Region * getRegion() const
Get the region represented by this ScopStmt (if any).
bool isRegionStmt() const
Return true if this statement represents a whole region.
__isl_give isl_id * isl_id_set_free_user(__isl_take isl_id *id, void(*free_user)(void *user))
boolean manage(isl_bool val)
This file contains the declaration of the PolyhedralInfo class, which will provide an interface to ex...
llvm::Loop * getRegionNodeLoop(llvm::RegionNode *RN, llvm::LoopInfo &LI)
Return the smallest loop surrounding RN.
llvm::Value * getConditionFromTerminator(llvm::Instruction *TI)
Return the condition for the terminator TI.
bool isLoopAttr(const isl::id &Id)
Is Id representing a loop?
std::optional< llvm::Metadata * > findMetadataOperand(llvm::MDNode *LoopMD, llvm::StringRef Name)
Find a property value in a LoopID.
unsigned getNumBlocksInRegionNode(llvm::RegionNode *RN)
Get the number of blocks in RN.
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.
llvm::Loop * getFirstNonBoxedLoopFor(llvm::Loop *L, llvm::LoopInfo &LI, const BoxedLoopsSetTy &BoxedLoops)
AssumptionSign
Enum to distinguish between assumptions and restrictions.
@ Value
MemoryKind::Value: Models an llvm::Value.
@ PHI
MemoryKind::PHI: Models PHI nodes within the SCoP.
bool hasDisableAllTransformsHint(llvm::Loop *L)
Does the loop's LoopID contain a 'llvm.loop.disable_heuristics' property?
std::optional< int > getOptionalIntLoopAttribute(llvm::MDNode *LoopID, llvm::StringRef Name)
Find an integers property value in a LoopID.
llvm::SmallVector< Assumption, 8 > RecordedAssumptionsTy
bool isDebugCall(llvm::Instruction *Inst)
Is the given instruction a call to a debug function?
bool hasDebugCall(ScopStmt *Stmt)
Does the statement contain a call to a debug function?
BandAttr * getLoopAttr(const isl::id &Id)
Return the BandAttr of a loop's isl::id.
llvm::BasicBlock * getUseBlock(const llvm::Use &U)
Return the block in which a value is used.
llvm::Loop * getLoopSurroundingScop(Scop &S, llvm::LoopInfo &LI)
Get the smallest loop that contains S but is not in S.
llvm::SetVector< llvm::AssertingVH< llvm::LoadInst > > InvariantLoadsSetTy
Type for a set of invariant loads.
void recordAssumption(RecordedAssumptionsTy *RecordedAssumptions, AssumptionKind Kind, isl::set Set, llvm::DebugLoc Loc, AssumptionSign Sign, llvm::BasicBlock *BB=nullptr, bool RTC=true)
Record an assumption for later addition to the assumed context.
llvm::SetVector< const llvm::Loop * > BoxedLoopsSetTy
Set of loops (used to remember loops in non-affine subregions).
isl::id getIslLoopAttr(isl::ctx Ctx, BandAttr *Attr)
Get an isl::id representing a loop.
bool isHoistableLoad(llvm::LoadInst *LInst, llvm::Region &R, llvm::LoopInfo &LI, llvm::ScalarEvolution &SE, const llvm::DominatorTree &DT, const InvariantLoadsSetTy &KnownInvariantLoads)
Check if LInst can be hoisted in R.
void splitEntryBlockForAlloca(llvm::BasicBlock *EntryBlock, llvm::Pass *P)
Split the entry block of a function to store the newly inserted allocations outside of all Scops.
isl::id createIslLoopAttr(isl::ctx Ctx, llvm::Loop *L)
Create an isl::id that identifies an original loop.
bool hasScalarDepsInsideRegion(const llvm::SCEV *Expr, const llvm::Region *R, llvm::Loop *Scope, bool AllowLoops, const InvariantLoadsSetTy &ILS)
Returns true when the SCEV contains references to instructions within the region.
llvm::DenseMap< llvm::AssertingVH< llvm::Value >, llvm::AssertingVH< llvm::Value > > ValueMapT
Type to remap values.
AssumptionKind
Enumeration of assumptions Polly can take.
bool isIgnoredIntrinsic(const llvm::Value *V)
Return true iff V is an intrinsic that we ignore during code generation.
void simplifyRegion(llvm::Region *R, llvm::DominatorTree *DT, llvm::LoopInfo *LI, llvm::RegionInfo *RI)
Simplify the region to have a single unconditional entry edge and a single exit edge.
bool canSynthesize(const llvm::Value *V, const Scop &S, llvm::ScalarEvolution *SE, llvm::Loop *Scope)
Check whether a value an be synthesized by the code generator.
bool getBooleanLoopAttribute(llvm::MDNode *LoopID, llvm::StringRef Name)
Find a boolean property value in a LoopID.
unsigned getNumBlocksInLoop(llvm::Loop *L)
Get the number of blocks in L.
The SCEVExpander will not generate any code for an existing SDiv/SRem instruction but just use it,...
const SCEV * visit(const SCEV *E)
const SCEV * visitAddExpr(const SCEVAddExpr *E)
const SCEV * visitUMaxExpr(const SCEVUMaxExpr *E)
ScopExpander(const Region &R, ScalarEvolution &SE, const DataLayout &DL, const char *Name, ValueMapT *VMap, BasicBlock *RTCBB)
const SCEV * visitUMinExpr(const SCEVUMinExpr *E)
const SCEV * visitUnknown(const SCEVUnknown *E)
const SCEV * visitGenericInst(const SCEVUnknown *E, Instruction *Inst, Instruction *IP)
const SCEV * visitAddRecExpr(const SCEVAddRecExpr *E)
const SCEV * visitPtrToIntExpr(const SCEVPtrToIntExpr *E)
const SCEV * visitSMaxExpr(const SCEVSMaxExpr *E)
const SCEV * visitConstant(const SCEVConstant *E)
The following functions will just traverse the SCEV and rebuild it with the new operands returned by ...
Value * expandCodeFor(const SCEV *E, Type *Ty, Instruction *I)
const SCEV * visitSequentialUMinExpr(const SCEVSequentialUMinExpr *E)
const SCEV * visitZeroExtendExpr(const SCEVZeroExtendExpr *E)
const SCEV * visitUDivExpr(const SCEVUDivExpr *E)
DenseMap< const SCEV *, const SCEV * > SCEVCache
const SCEV * visitSignExtendExpr(const SCEVSignExtendExpr *E)
const SCEV * visitSMinExpr(const SCEVSMinExpr *E)
const SCEV * visitMulExpr(const SCEVMulExpr *E)
const SCEV * visitVScale(const SCEVVScale *E)
const SCEV * visitTruncateExpr(const SCEVTruncateExpr *E)
Represent the attributes of a loop.
llvm::MDNode * Metadata
LoopID which stores the properties of the loop, such as transformations to apply and the metadata of ...
llvm::Loop * OriginalLoop
The LoopInfo reference for this loop.