| //===- ScopHelper.cpp - Some Helper Functions for Scop. ------------------===// |
| // |
| // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
| // See https://llvm.org/LICENSE.txt for license information. |
| // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
| // |
| //===----------------------------------------------------------------------===// |
| // |
| // Small functions that help with Scop and LLVM-IR. |
| // |
| //===----------------------------------------------------------------------===// |
| |
| #include "polly/Support/ScopHelper.h" |
| #include "polly/Options.h" |
| #include "polly/ScopInfo.h" |
| #include "polly/Support/SCEVValidator.h" |
| #include "llvm/Analysis/LoopInfo.h" |
| #include "llvm/Analysis/RegionInfo.h" |
| #include "llvm/Analysis/ScalarEvolution.h" |
| #include "llvm/Analysis/ScalarEvolutionExpressions.h" |
| #include "llvm/Transforms/Utils/BasicBlockUtils.h" |
| #include "llvm/Transforms/Utils/LoopUtils.h" |
| #include "llvm/Transforms/Utils/ScalarEvolutionExpander.h" |
| #include <optional> |
| |
| using namespace llvm; |
| using namespace polly; |
| |
| #define DEBUG_TYPE "polly-scop-helper" |
| |
| 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)); |
| |
| // Ensures that there is just one predecessor to the entry node from outside the |
| // region. |
| // The identity of the region entry node is preserved. |
| static void simplifyRegionEntry(Region *R, DominatorTree *DT, LoopInfo *LI, |
| RegionInfo *RI) { |
| BasicBlock *EnteringBB = R->getEnteringBlock(); |
| BasicBlock *Entry = R->getEntry(); |
| |
| // Before (one of): |
| // |
| // \ / // |
| // EnteringBB // |
| // | \------> // |
| // \ / | // |
| // Entry <--\ Entry <--\ // |
| // / \ / / \ / // |
| // .... .... // |
| |
| // Create single entry edge if the region has multiple entry edges. |
| if (!EnteringBB) { |
| SmallVector<BasicBlock *, 4> Preds; |
| for (BasicBlock *P : predecessors(Entry)) |
| if (!R->contains(P)) |
| Preds.push_back(P); |
| |
| BasicBlock *NewEntering = |
| SplitBlockPredecessors(Entry, Preds, ".region_entering", DT, LI); |
| |
| if (RI) { |
| // The exit block of predecessing regions must be changed to NewEntering |
| for (BasicBlock *ExitPred : predecessors(NewEntering)) { |
| Region *RegionOfPred = RI->getRegionFor(ExitPred); |
| if (RegionOfPred->getExit() != Entry) |
| continue; |
| |
| while (!RegionOfPred->isTopLevelRegion() && |
| RegionOfPred->getExit() == Entry) { |
| RegionOfPred->replaceExit(NewEntering); |
| RegionOfPred = RegionOfPred->getParent(); |
| } |
| } |
| |
| // Make all ancestors use EnteringBB as entry; there might be edges to it |
| Region *AncestorR = R->getParent(); |
| RI->setRegionFor(NewEntering, AncestorR); |
| while (!AncestorR->isTopLevelRegion() && AncestorR->getEntry() == Entry) { |
| AncestorR->replaceEntry(NewEntering); |
| AncestorR = AncestorR->getParent(); |
| } |
| } |
| |
| EnteringBB = NewEntering; |
| } |
| assert(R->getEnteringBlock() == EnteringBB); |
| |
| // After: |
| // |
| // \ / // |
| // EnteringBB // |
| // | // |
| // | // |
| // Entry <--\ // |
| // / \ / // |
| // .... // |
| } |
| |
| // Ensure that the region has a single block that branches to the exit node. |
| static void simplifyRegionExit(Region *R, DominatorTree *DT, LoopInfo *LI, |
| RegionInfo *RI) { |
| BasicBlock *ExitBB = R->getExit(); |
| BasicBlock *ExitingBB = R->getExitingBlock(); |
| |
| // Before: |
| // |
| // (Region) ______/ // |
| // \ | / // |
| // ExitBB // |
| // / \ // |
| |
| if (!ExitingBB) { |
| SmallVector<BasicBlock *, 4> Preds; |
| for (BasicBlock *P : predecessors(ExitBB)) |
| if (R->contains(P)) |
| Preds.push_back(P); |
| |
| // Preds[0] Preds[1] otherBB // |
| // \ | ________/ // |
| // \ | / // |
| // BB // |
| ExitingBB = |
| SplitBlockPredecessors(ExitBB, Preds, ".region_exiting", DT, LI); |
| // Preds[0] Preds[1] otherBB // |
| // \ / / // |
| // BB.region_exiting / // |
| // \ / // |
| // BB // |
| |
| if (RI) |
| RI->setRegionFor(ExitingBB, R); |
| |
| // Change the exit of nested regions, but not the region itself, |
| R->replaceExitRecursive(ExitingBB); |
| R->replaceExit(ExitBB); |
| } |
| assert(ExitingBB == R->getExitingBlock()); |
| |
| // After: |
| // |
| // \ / // |
| // ExitingBB _____/ // |
| // \ / // |
| // ExitBB // |
| // / \ // |
| } |
| |
| void polly::simplifyRegion(Region *R, DominatorTree *DT, LoopInfo *LI, |
| RegionInfo *RI) { |
| assert(R && !R->isTopLevelRegion()); |
| assert(!RI || RI == R->getRegionInfo()); |
| assert((!RI || DT) && |
| "RegionInfo requires DominatorTree to be updated as well"); |
| |
| simplifyRegionEntry(R, DT, LI, RI); |
| simplifyRegionExit(R, DT, LI, RI); |
| assert(R->isSimple()); |
| } |
| |
| // Split the block into two successive blocks. |
| // |
| // Like llvm::SplitBlock, but also preserves RegionInfo |
| static BasicBlock *splitBlock(BasicBlock *Old, Instruction *SplitPt, |
| DominatorTree *DT, llvm::LoopInfo *LI, |
| RegionInfo *RI) { |
| assert(Old && SplitPt); |
| |
| // Before: |
| // |
| // \ / // |
| // Old // |
| // / \ // |
| |
| BasicBlock *NewBlock = llvm::SplitBlock(Old, SplitPt, DT, LI); |
| |
| if (RI) { |
| Region *R = RI->getRegionFor(Old); |
| RI->setRegionFor(NewBlock, R); |
| } |
| |
| // After: |
| // |
| // \ / // |
| // Old // |
| // | // |
| // NewBlock // |
| // / \ // |
| |
| return NewBlock; |
| } |
| |
| void polly::splitEntryBlockForAlloca(BasicBlock *EntryBlock, DominatorTree *DT, |
| LoopInfo *LI, RegionInfo *RI) { |
| // Find first non-alloca instruction. Every basic block has a non-alloca |
| // instruction, as every well formed basic block has a terminator. |
| BasicBlock::iterator I = EntryBlock->begin(); |
| while (isa<AllocaInst>(I)) |
| ++I; |
| |
| // splitBlock updates DT, LI and RI. |
| splitBlock(EntryBlock, &*I, DT, LI, RI); |
| } |
| |
| void polly::splitEntryBlockForAlloca(BasicBlock *EntryBlock, Pass *P) { |
| auto *DTWP = P->getAnalysisIfAvailable<DominatorTreeWrapperPass>(); |
| auto *DT = DTWP ? &DTWP->getDomTree() : nullptr; |
| auto *LIWP = P->getAnalysisIfAvailable<LoopInfoWrapperPass>(); |
| auto *LI = LIWP ? &LIWP->getLoopInfo() : nullptr; |
| RegionInfoPass *RIP = P->getAnalysisIfAvailable<RegionInfoPass>(); |
| RegionInfo *RI = RIP ? &RIP->getRegionInfo() : nullptr; |
| |
| // splitBlock updates DT, LI and RI. |
| polly::splitEntryBlockForAlloca(EntryBlock, DT, LI, RI); |
| } |
| |
| void polly::recordAssumption(polly::RecordedAssumptionsTy *RecordedAssumptions, |
| polly::AssumptionKind Kind, isl::set Set, |
| DebugLoc Loc, polly::AssumptionSign Sign, |
| BasicBlock *BB, bool RTC) { |
| assert((Set.is_params() || BB) && |
| "Assumptions without a basic block must be parameter sets"); |
| if (RecordedAssumptions) |
| RecordedAssumptions->push_back({Kind, Sign, Set, Loc, BB, RTC}); |
| } |
| |
| /// ScopExpander generates IR the the value of a SCEV that represents a value |
| /// from a SCoP. |
| /// |
| /// IMPORTANT: There are two ScalarEvolutions at play here. First, the SE that |
| /// was used to analyze the original SCoP (not actually referenced anywhere |
| /// here, but passed as argument to make the distinction clear). Second, GenSE |
| /// which is the SE for the function that the code is emitted into. SE and GenSE |
| /// may be different when the generated code is to be emitted into an outlined |
| /// function, e.g. for a parallel loop. That is, each SCEV is to be used only by |
| /// the SE that "owns" it and ScopExpander handles the translation between them. |
| /// The SCEVVisitor methods are only to be called on SCEVs of the original SE. |
| /// Their job is to create a new SCEV for GenSE. The nested SCEVExpander is to |
| /// be used only with SCEVs belonging to GenSE. Currently SCEVs do not store a |
| /// reference to the ScalarEvolution they belong to, so a mixup does not |
| /// immediately cause a crash but certainly is a violation of its interface. |
| /// |
| /// The SCEVExpander will __not__ generate any code for an existing SDiv/SRem |
| /// instruction but just use it, if it is referenced as a SCEVUnknown. We want |
| /// however to generate new code if the instruction is in the analyzed region |
| /// and we generate code outside/in front of that region. Hence, we generate the |
| /// code for the SDiv/SRem operands in front of the analyzed region and then |
| /// create a new SDiv/SRem operation there too. |
| struct ScopExpander final : SCEVVisitor<ScopExpander, const SCEV *> { |
| friend struct SCEVVisitor<ScopExpander, const SCEV *>; |
| |
| explicit ScopExpander(const Region &R, ScalarEvolution &SE, Function *GenFn, |
| ScalarEvolution &GenSE, const DataLayout &DL, |
| const char *Name, ValueMapT *VMap, |
| LoopToScevMapT *LoopMap, BasicBlock *RTCBB) |
| : Expander(GenSE, DL, Name, /*PreserveLCSSA=*/false), Name(Name), R(R), |
| VMap(VMap), LoopMap(LoopMap), RTCBB(RTCBB), GenSE(GenSE), GenFn(GenFn) { |
| } |
| |
| Value *expandCodeFor(const SCEV *E, Type *Ty, Instruction *IP) { |
| assert(isInGenRegion(IP) && |
| "ScopExpander assumes to be applied to generated code region"); |
| const SCEV *GenE = visit(E); |
| return Expander.expandCodeFor(GenE, Ty, IP); |
| } |
| |
| const SCEV *visit(const SCEV *E) { |
| // Cache the expansion results for intermediate SCEV expressions. A SCEV |
| // expression can refer to an operand multiple times (e.g. "x*x), so |
| // a naive visitor takes exponential time. |
| if (SCEVCache.count(E)) |
| return SCEVCache[E]; |
| const SCEV *Result = SCEVVisitor::visit(E); |
| SCEVCache[E] = Result; |
| return Result; |
| } |
| |
| private: |
| SCEVExpander Expander; |
| const char *Name; |
| const Region &R; |
| ValueMapT *VMap; |
| LoopToScevMapT *LoopMap; |
| BasicBlock *RTCBB; |
| DenseMap<const SCEV *, const SCEV *> SCEVCache; |
| |
| ScalarEvolution &GenSE; |
| Function *GenFn; |
| |
| /// Is the instruction part of the original SCoP (in contrast to be located in |
| /// the code-generated region)? |
| bool isInOrigRegion(Instruction *Inst) { |
| Function *Fn = R.getEntry()->getParent(); |
| bool isInOrigRegion = Inst->getFunction() == Fn && R.contains(Inst); |
| assert((isInOrigRegion || GenFn == Inst->getFunction()) && |
| "Instruction expected to be either in the SCoP or the translated " |
| "region"); |
| return isInOrigRegion; |
| } |
| |
| bool isInGenRegion(Instruction *Inst) { return !isInOrigRegion(Inst); } |
| |
| const SCEV *visitGenericInst(const SCEVUnknown *E, Instruction *Inst, |
| Instruction *IP) { |
| if (!Inst || isInGenRegion(Inst)) |
| return E; |
| |
| assert(!Inst->mayThrow() && !Inst->mayReadOrWriteMemory() && |
| !isa<PHINode>(Inst)); |
| |
| auto *InstClone = Inst->clone(); |
| for (auto &Op : Inst->operands()) { |
| assert(GenSE.isSCEVable(Op->getType())); |
| auto *OpSCEV = GenSE.getSCEV(Op); |
| auto *OpClone = expandCodeFor(OpSCEV, Op->getType(), IP); |
| InstClone->replaceUsesOfWith(Op, OpClone); |
| } |
| |
| InstClone->setName(Name + Inst->getName()); |
| InstClone->insertBefore(IP); |
| return GenSE.getSCEV(InstClone); |
| } |
| |
| const SCEV *visitUnknown(const SCEVUnknown *E) { |
| |
| // If a value mapping was given try if the underlying value is remapped. |
| Value *NewVal = VMap ? VMap->lookup(E->getValue()) : nullptr; |
| if (NewVal) { |
| auto *NewE = GenSE.getSCEV(NewVal); |
| |
| // While the mapped value might be different the SCEV representation might |
| // not be. To this end we will check before we go into recursion here. |
| // FIXME: SCEVVisitor must only visit SCEVs that belong to the original |
| // SE. This calls it on SCEVs that belong GenSE. |
| if (E != NewE) |
| return visit(NewE); |
| } |
| |
| Instruction *Inst = dyn_cast<Instruction>(E->getValue()); |
| Instruction *IP; |
| if (Inst && isInGenRegion(Inst)) |
| IP = Inst; |
| else if (R.getEntry()->getParent() != GenFn) { |
| // RTCBB is in the original function, but we are generating for a |
| // subfunction so we cannot emit to RTCBB. Usually, we land here only |
| // because E->getValue() is not an instruction but a global or constant |
| // which do not need to emit anything. |
| IP = GenFn->getEntryBlock().getTerminator(); |
| } else if (Inst && RTCBB->getParent() == Inst->getFunction()) |
| IP = RTCBB->getTerminator(); |
| else |
| IP = RTCBB->getParent()->getEntryBlock().getTerminator(); |
| |
| if (!Inst || (Inst->getOpcode() != Instruction::SRem && |
| Inst->getOpcode() != Instruction::SDiv)) |
| return visitGenericInst(E, Inst, IP); |
| |
| const SCEV *LHSScev = GenSE.getSCEV(Inst->getOperand(0)); |
| const SCEV *RHSScev = GenSE.getSCEV(Inst->getOperand(1)); |
| |
| if (!GenSE.isKnownNonZero(RHSScev)) |
| RHSScev = GenSE.getUMaxExpr(RHSScev, GenSE.getConstant(E->getType(), 1)); |
| |
| Value *LHS = expandCodeFor(LHSScev, E->getType(), IP); |
| Value *RHS = expandCodeFor(RHSScev, E->getType(), IP); |
| |
| Inst = |
| BinaryOperator::Create((Instruction::BinaryOps)Inst->getOpcode(), LHS, |
| RHS, Inst->getName() + Name, IP->getIterator()); |
| return GenSE.getSCEV(Inst); |
| } |
| |
| /// The following functions will just traverse the SCEV and rebuild it using |
| /// GenSE and the new operands returned by the traversal. |
| /// |
| ///{ |
| const SCEV *visitConstant(const SCEVConstant *E) { return E; } |
| const SCEV *visitVScale(const SCEVVScale *E) { return E; } |
| const SCEV *visitPtrToIntExpr(const SCEVPtrToIntExpr *E) { |
| return GenSE.getPtrToIntExpr(visit(E->getOperand()), E->getType()); |
| } |
| const SCEV *visitTruncateExpr(const SCEVTruncateExpr *E) { |
| return GenSE.getTruncateExpr(visit(E->getOperand()), E->getType()); |
| } |
| const SCEV *visitZeroExtendExpr(const SCEVZeroExtendExpr *E) { |
| return GenSE.getZeroExtendExpr(visit(E->getOperand()), E->getType()); |
| } |
| const SCEV *visitSignExtendExpr(const SCEVSignExtendExpr *E) { |
| return GenSE.getSignExtendExpr(visit(E->getOperand()), E->getType()); |
| } |
| const SCEV *visitUDivExpr(const SCEVUDivExpr *E) { |
| auto *RHSScev = visit(E->getRHS()); |
| if (!GenSE.isKnownNonZero(RHSScev)) |
| RHSScev = GenSE.getUMaxExpr(RHSScev, GenSE.getConstant(E->getType(), 1)); |
| return GenSE.getUDivExpr(visit(E->getLHS()), RHSScev); |
| } |
| const SCEV *visitAddExpr(const SCEVAddExpr *E) { |
| SmallVector<const SCEV *, 4> NewOps; |
| for (const SCEV *Op : E->operands()) |
| NewOps.push_back(visit(Op)); |
| return GenSE.getAddExpr(NewOps); |
| } |
| const SCEV *visitMulExpr(const SCEVMulExpr *E) { |
| SmallVector<const SCEV *, 4> NewOps; |
| for (const SCEV *Op : E->operands()) |
| NewOps.push_back(visit(Op)); |
| return GenSE.getMulExpr(NewOps); |
| } |
| const SCEV *visitUMaxExpr(const SCEVUMaxExpr *E) { |
| SmallVector<const SCEV *, 4> NewOps; |
| for (const SCEV *Op : E->operands()) |
| NewOps.push_back(visit(Op)); |
| return GenSE.getUMaxExpr(NewOps); |
| } |
| const SCEV *visitSMaxExpr(const SCEVSMaxExpr *E) { |
| SmallVector<const SCEV *, 4> NewOps; |
| for (const SCEV *Op : E->operands()) |
| NewOps.push_back(visit(Op)); |
| return GenSE.getSMaxExpr(NewOps); |
| } |
| const SCEV *visitUMinExpr(const SCEVUMinExpr *E) { |
| SmallVector<const SCEV *, 4> NewOps; |
| for (const SCEV *Op : E->operands()) |
| NewOps.push_back(visit(Op)); |
| return GenSE.getUMinExpr(NewOps); |
| } |
| const SCEV *visitSMinExpr(const SCEVSMinExpr *E) { |
| SmallVector<const SCEV *, 4> NewOps; |
| for (const SCEV *Op : E->operands()) |
| NewOps.push_back(visit(Op)); |
| return GenSE.getSMinExpr(NewOps); |
| } |
| const SCEV *visitSequentialUMinExpr(const SCEVSequentialUMinExpr *E) { |
| SmallVector<const SCEV *, 4> NewOps; |
| for (const SCEV *Op : E->operands()) |
| NewOps.push_back(visit(Op)); |
| return GenSE.getUMinExpr(NewOps, /*Sequential=*/true); |
| } |
| const SCEV *visitAddRecExpr(const SCEVAddRecExpr *E) { |
| SmallVector<const SCEV *, 4> NewOps; |
| for (const SCEV *Op : E->operands()) |
| NewOps.push_back(visit(Op)); |
| |
| const Loop *L = E->getLoop(); |
| const SCEV *GenLRepl = LoopMap ? LoopMap->lookup(L) : nullptr; |
| if (!GenLRepl) |
| return GenSE.getAddRecExpr(NewOps, L, E->getNoWrapFlags()); |
| |
| // evaluateAtIteration replaces the SCEVAddrExpr with a direct calculation. |
| const SCEV *Evaluated = |
| SCEVAddRecExpr::evaluateAtIteration(NewOps, GenLRepl, GenSE); |
| |
| // FIXME: This emits a SCEV for GenSE (since GenLRepl will refer to the |
| // induction variable of a generated loop), so we should not use SCEVVisitor |
| // with it. Howver, it still contains references to the SCoP region. |
| return visit(Evaluated); |
| } |
| ///} |
| }; |
| |
| Value *polly::expandCodeFor(Scop &S, llvm::ScalarEvolution &SE, |
| llvm::Function *GenFn, ScalarEvolution &GenSE, |
| const DataLayout &DL, const char *Name, |
| const SCEV *E, Type *Ty, Instruction *IP, |
| ValueMapT *VMap, LoopToScevMapT *LoopMap, |
| BasicBlock *RTCBB) { |
| ScopExpander Expander(S.getRegion(), SE, GenFn, GenSE, DL, Name, VMap, |
| LoopMap, RTCBB); |
| return Expander.expandCodeFor(E, Ty, IP); |
| } |
| |
| Value *polly::getConditionFromTerminator(Instruction *TI) { |
| if (BranchInst *BR = dyn_cast<BranchInst>(TI)) { |
| if (BR->isUnconditional()) |
| return ConstantInt::getTrue(Type::getInt1Ty(TI->getContext())); |
| |
| return BR->getCondition(); |
| } |
| |
| if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) |
| return SI->getCondition(); |
| |
| return nullptr; |
| } |
| |
| Loop *polly::getLoopSurroundingScop(Scop &S, LoopInfo &LI) { |
| // Start with the smallest loop containing the entry and expand that |
| // loop until it contains all blocks in the region. If there is a loop |
| // containing all blocks in the region check if it is itself contained |
| // and if so take the parent loop as it will be the smallest containing |
| // the region but not contained by it. |
| Loop *L = LI.getLoopFor(S.getEntry()); |
| while (L) { |
| bool AllContained = true; |
| for (auto *BB : S.blocks()) |
| AllContained &= L->contains(BB); |
| if (AllContained) |
| break; |
| L = L->getParentLoop(); |
| } |
| |
| return L ? (S.contains(L) ? L->getParentLoop() : L) : nullptr; |
| } |
| |
| unsigned polly::getNumBlocksInLoop(Loop *L) { |
| unsigned NumBlocks = L->getNumBlocks(); |
| SmallVector<BasicBlock *, 4> ExitBlocks; |
| L->getExitBlocks(ExitBlocks); |
| |
| for (auto ExitBlock : ExitBlocks) { |
| if (isa<UnreachableInst>(ExitBlock->getTerminator())) |
| NumBlocks++; |
| } |
| return NumBlocks; |
| } |
| |
| unsigned polly::getNumBlocksInRegionNode(RegionNode *RN) { |
| if (!RN->isSubRegion()) |
| return 1; |
| |
| Region *R = RN->getNodeAs<Region>(); |
| return std::distance(R->block_begin(), R->block_end()); |
| } |
| |
| Loop *polly::getRegionNodeLoop(RegionNode *RN, LoopInfo &LI) { |
| if (!RN->isSubRegion()) { |
| BasicBlock *BB = RN->getNodeAs<BasicBlock>(); |
| Loop *L = LI.getLoopFor(BB); |
| |
| // Unreachable statements are not considered to belong to a LLVM loop, as |
| // they are not part of an actual loop in the control flow graph. |
| // Nevertheless, we handle certain unreachable statements that are common |
| // when modeling run-time bounds checks as being part of the loop to be |
| // able to model them and to later eliminate the run-time bounds checks. |
| // |
| // Specifically, for basic blocks that terminate in an unreachable and |
| // where the immediate predecessor is part of a loop, we assume these |
| // basic blocks belong to the loop the predecessor belongs to. This |
| // allows us to model the following code. |
| // |
| // for (i = 0; i < N; i++) { |
| // if (i > 1024) |
| // abort(); <- this abort might be translated to an |
| // unreachable |
| // |
| // A[i] = ... |
| // } |
| if (!L && isa<UnreachableInst>(BB->getTerminator()) && BB->getPrevNode()) |
| L = LI.getLoopFor(BB->getPrevNode()); |
| return L; |
| } |
| |
| Region *NonAffineSubRegion = RN->getNodeAs<Region>(); |
| Loop *L = LI.getLoopFor(NonAffineSubRegion->getEntry()); |
| while (L && NonAffineSubRegion->contains(L)) |
| L = L->getParentLoop(); |
| return L; |
| } |
| |
| static bool hasVariantIndex(GetElementPtrInst *Gep, Loop *L, Region &R, |
| ScalarEvolution &SE) { |
| for (const Use &Val : llvm::drop_begin(Gep->operands(), 1)) { |
| const SCEV *PtrSCEV = SE.getSCEVAtScope(Val, L); |
| Loop *OuterLoop = R.outermostLoopInRegion(L); |
| if (!SE.isLoopInvariant(PtrSCEV, OuterLoop)) |
| return true; |
| } |
| return false; |
| } |
| |
| bool polly::isHoistableLoad(LoadInst *LInst, Region &R, LoopInfo &LI, |
| ScalarEvolution &SE, const DominatorTree &DT, |
| const InvariantLoadsSetTy &KnownInvariantLoads) { |
| Loop *L = LI.getLoopFor(LInst->getParent()); |
| auto *Ptr = LInst->getPointerOperand(); |
| |
| // A LoadInst is hoistable if the address it is loading from is also |
| // invariant; in this case: another invariant load (whether that address |
| // is also not written to has to be checked separately) |
| // TODO: This only checks for a LoadInst->GetElementPtrInst->LoadInst |
| // pattern generated by the Chapel frontend, but generally this applies |
| // for any chain of instruction that does not also depend on any |
| // induction variable |
| if (auto *GepInst = dyn_cast<GetElementPtrInst>(Ptr)) { |
| if (!hasVariantIndex(GepInst, L, R, SE)) { |
| if (auto *DecidingLoad = |
| dyn_cast<LoadInst>(GepInst->getPointerOperand())) { |
| if (KnownInvariantLoads.count(DecidingLoad)) |
| return true; |
| } |
| } |
| } |
| |
| const SCEV *PtrSCEV = SE.getSCEVAtScope(Ptr, L); |
| while (L && R.contains(L)) { |
| if (!SE.isLoopInvariant(PtrSCEV, L)) |
| return false; |
| L = L->getParentLoop(); |
| } |
| |
| for (auto *User : Ptr->users()) { |
| auto *UserI = dyn_cast<Instruction>(User); |
| if (!UserI || !R.contains(UserI)) |
| continue; |
| if (!UserI->mayWriteToMemory()) |
| continue; |
| |
| auto &BB = *UserI->getParent(); |
| if (DT.dominates(&BB, LInst->getParent())) |
| return false; |
| |
| bool DominatesAllPredecessors = true; |
| if (R.isTopLevelRegion()) { |
| for (BasicBlock &I : *R.getEntry()->getParent()) |
| if (isa<ReturnInst>(I.getTerminator()) && !DT.dominates(&BB, &I)) |
| DominatesAllPredecessors = false; |
| } else { |
| for (auto Pred : predecessors(R.getExit())) |
| if (R.contains(Pred) && !DT.dominates(&BB, Pred)) |
| DominatesAllPredecessors = false; |
| } |
| |
| if (!DominatesAllPredecessors) |
| continue; |
| |
| return false; |
| } |
| |
| return true; |
| } |
| |
| bool polly::isIgnoredIntrinsic(const Value *V) { |
| if (auto *IT = dyn_cast<IntrinsicInst>(V)) { |
| switch (IT->getIntrinsicID()) { |
| // Lifetime markers are supported/ignored. |
| case llvm::Intrinsic::lifetime_start: |
| case llvm::Intrinsic::lifetime_end: |
| // Invariant markers are supported/ignored. |
| case llvm::Intrinsic::invariant_start: |
| case llvm::Intrinsic::invariant_end: |
| // Some misc annotations are supported/ignored. |
| case llvm::Intrinsic::var_annotation: |
| case llvm::Intrinsic::ptr_annotation: |
| case llvm::Intrinsic::annotation: |
| case llvm::Intrinsic::donothing: |
| case llvm::Intrinsic::assume: |
| // Some debug info intrinsics are supported/ignored. |
| case llvm::Intrinsic::dbg_value: |
| case llvm::Intrinsic::dbg_declare: |
| return true; |
| default: |
| break; |
| } |
| } |
| return false; |
| } |
| |
| bool polly::canSynthesize(const Value *V, const Scop &S, ScalarEvolution *SE, |
| Loop *Scope) { |
| if (!V || !SE->isSCEVable(V->getType())) |
| return false; |
| |
| const InvariantLoadsSetTy &ILS = S.getRequiredInvariantLoads(); |
| if (const SCEV *Scev = SE->getSCEVAtScope(const_cast<Value *>(V), Scope)) |
| if (!isa<SCEVCouldNotCompute>(Scev)) |
| if (!hasScalarDepsInsideRegion(Scev, &S.getRegion(), Scope, false, ILS)) |
| return true; |
| |
| return false; |
| } |
| |
| llvm::BasicBlock *polly::getUseBlock(const llvm::Use &U) { |
| Instruction *UI = dyn_cast<Instruction>(U.getUser()); |
| if (!UI) |
| return nullptr; |
| |
| if (PHINode *PHI = dyn_cast<PHINode>(UI)) |
| return PHI->getIncomingBlock(U); |
| |
| return UI->getParent(); |
| } |
| |
| llvm::Loop *polly::getFirstNonBoxedLoopFor(llvm::Loop *L, llvm::LoopInfo &LI, |
| const BoxedLoopsSetTy &BoxedLoops) { |
| while (BoxedLoops.count(L)) |
| L = L->getParentLoop(); |
| return L; |
| } |
| |
| llvm::Loop *polly::getFirstNonBoxedLoopFor(llvm::BasicBlock *BB, |
| llvm::LoopInfo &LI, |
| const BoxedLoopsSetTy &BoxedLoops) { |
| Loop *L = LI.getLoopFor(BB); |
| return getFirstNonBoxedLoopFor(L, LI, BoxedLoops); |
| } |
| |
| bool polly::isDebugCall(Instruction *Inst) { |
| auto *CI = dyn_cast<CallInst>(Inst); |
| if (!CI) |
| return false; |
| |
| Function *CF = CI->getCalledFunction(); |
| if (!CF) |
| return false; |
| |
| return std::find(DebugFunctions.begin(), DebugFunctions.end(), |
| CF->getName()) != DebugFunctions.end(); |
| } |
| |
| static bool hasDebugCall(BasicBlock *BB) { |
| for (Instruction &Inst : *BB) { |
| if (isDebugCall(&Inst)) |
| return true; |
| } |
| return false; |
| } |
| |
| bool polly::hasDebugCall(ScopStmt *Stmt) { |
| // Quick skip if no debug functions have been defined. |
| if (DebugFunctions.empty()) |
| return false; |
| |
| if (!Stmt) |
| return false; |
| |
| for (Instruction *Inst : Stmt->getInstructions()) |
| if (isDebugCall(Inst)) |
| return true; |
| |
| if (Stmt->isRegionStmt()) { |
| for (BasicBlock *RBB : Stmt->getRegion()->blocks()) |
| if (RBB != Stmt->getEntryBlock() && ::hasDebugCall(RBB)) |
| return true; |
| } |
| |
| return false; |
| } |
| |
| /// Find a property in a LoopID. |
| static MDNode *findNamedMetadataNode(MDNode *LoopMD, StringRef Name) { |
| if (!LoopMD) |
| return nullptr; |
| for (const MDOperand &X : drop_begin(LoopMD->operands(), 1)) { |
| auto *OpNode = dyn_cast<MDNode>(X.get()); |
| if (!OpNode) |
| continue; |
| |
| auto *OpName = dyn_cast<MDString>(OpNode->getOperand(0)); |
| if (!OpName) |
| continue; |
| if (OpName->getString() == Name) |
| return OpNode; |
| } |
| return nullptr; |
| } |
| |
| static std::optional<const MDOperand *> findNamedMetadataArg(MDNode *LoopID, |
| StringRef Name) { |
| MDNode *MD = findNamedMetadataNode(LoopID, Name); |
| if (!MD) |
| return std::nullopt; |
| switch (MD->getNumOperands()) { |
| case 1: |
| return nullptr; |
| case 2: |
| return &MD->getOperand(1); |
| default: |
| llvm_unreachable("loop metadata has 0 or 1 operand"); |
| } |
| } |
| |
| std::optional<Metadata *> polly::findMetadataOperand(MDNode *LoopMD, |
| StringRef Name) { |
| MDNode *MD = findNamedMetadataNode(LoopMD, Name); |
| if (!MD) |
| return std::nullopt; |
| switch (MD->getNumOperands()) { |
| case 1: |
| return nullptr; |
| case 2: |
| return MD->getOperand(1).get(); |
| default: |
| llvm_unreachable("loop metadata must have 0 or 1 operands"); |
| } |
| } |
| |
| static std::optional<bool> getOptionalBoolLoopAttribute(MDNode *LoopID, |
| StringRef Name) { |
| MDNode *MD = findNamedMetadataNode(LoopID, Name); |
| if (!MD) |
| return std::nullopt; |
| switch (MD->getNumOperands()) { |
| case 1: |
| return true; |
| case 2: |
| if (ConstantInt *IntMD = |
| mdconst::extract_or_null<ConstantInt>(MD->getOperand(1).get())) |
| return IntMD->getZExtValue(); |
| return true; |
| } |
| llvm_unreachable("unexpected number of options"); |
| } |
| |
| bool polly::getBooleanLoopAttribute(MDNode *LoopID, StringRef Name) { |
| return getOptionalBoolLoopAttribute(LoopID, Name).value_or(false); |
| } |
| |
| std::optional<int> polly::getOptionalIntLoopAttribute(MDNode *LoopID, |
| StringRef Name) { |
| const MDOperand *AttrMD = |
| findNamedMetadataArg(LoopID, Name).value_or(nullptr); |
| if (!AttrMD) |
| return std::nullopt; |
| |
| ConstantInt *IntMD = mdconst::extract_or_null<ConstantInt>(AttrMD->get()); |
| if (!IntMD) |
| return std::nullopt; |
| |
| return IntMD->getSExtValue(); |
| } |
| |
| bool polly::hasDisableAllTransformsHint(Loop *L) { |
| return llvm::hasDisableAllTransformsHint(L); |
| } |
| |
| bool polly::hasDisableAllTransformsHint(llvm::MDNode *LoopID) { |
| return getBooleanLoopAttribute(LoopID, "llvm.loop.disable_nonforced"); |
| } |
| |
| isl::id polly::getIslLoopAttr(isl::ctx Ctx, BandAttr *Attr) { |
| assert(Attr && "Must be a valid BandAttr"); |
| |
| // The name "Loop" signals that this id contains a pointer to a BandAttr. |
| // The ScheduleOptimizer also uses the string "Inter iteration alias-free" in |
| // markers, but it's user pointer is an llvm::Value. |
| isl::id Result = isl::id::alloc(Ctx, "Loop with Metadata", Attr); |
| Result = isl::manage(isl_id_set_free_user(Result.release(), [](void *Ptr) { |
| BandAttr *Attr = reinterpret_cast<BandAttr *>(Ptr); |
| delete Attr; |
| })); |
| return Result; |
| } |
| |
| isl::id polly::createIslLoopAttr(isl::ctx Ctx, Loop *L) { |
| if (!L) |
| return {}; |
| |
| // A loop without metadata does not need to be annotated. |
| MDNode *LoopID = L->getLoopID(); |
| if (!LoopID) |
| return {}; |
| |
| BandAttr *Attr = new BandAttr(); |
| Attr->OriginalLoop = L; |
| Attr->Metadata = L->getLoopID(); |
| |
| return getIslLoopAttr(Ctx, Attr); |
| } |
| |
| bool polly::isLoopAttr(const isl::id &Id) { |
| if (Id.is_null()) |
| return false; |
| |
| return Id.get_name() == "Loop with Metadata"; |
| } |
| |
| BandAttr *polly::getLoopAttr(const isl::id &Id) { |
| if (!isLoopAttr(Id)) |
| return nullptr; |
| |
| return reinterpret_cast<BandAttr *>(Id.get_user()); |
| } |