868 lines · cpp
1//===- ScopHelper.cpp - Some Helper Functions for Scop. ------------------===//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// Small functions that help with Scop and LLVM-IR.10//11//===----------------------------------------------------------------------===//12 13#include "polly/Support/ScopHelper.h"14#include "polly/Options.h"15#include "polly/ScopInfo.h"16#include "polly/Support/SCEVValidator.h"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"24#include <optional>25 26using namespace llvm;27using namespace polly;28 29#define DEBUG_TYPE "polly-scop-helper"30 31static cl::list<std::string> DebugFunctions(32 "polly-debug-func",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."),36 cl::Hidden, cl::CommaSeparated, cl::cat(PollyCategory));37 38// Ensures that there is just one predecessor to the entry node from outside the39// region.40// The identity of the region entry node is preserved.41static void simplifyRegionEntry(Region *R, DominatorTree *DT, LoopInfo *LI,42 RegionInfo *RI) {43 BasicBlock *EnteringBB = R->getEnteringBlock();44 BasicBlock *Entry = R->getEntry();45 46 // Before (one of):47 //48 // \ / //49 // EnteringBB //50 // | \------> //51 // \ / | //52 // Entry <--\ Entry <--\ //53 // / \ / / \ / //54 // .... .... //55 56 // Create single entry edge if the region has multiple entry edges.57 if (!EnteringBB) {58 SmallVector<BasicBlock *, 4> Preds;59 for (BasicBlock *P : predecessors(Entry))60 if (!R->contains(P))61 Preds.push_back(P);62 63 BasicBlock *NewEntering =64 SplitBlockPredecessors(Entry, Preds, ".region_entering", DT, LI);65 66 if (RI) {67 // The exit block of predecessing regions must be changed to NewEntering68 for (BasicBlock *ExitPred : predecessors(NewEntering)) {69 Region *RegionOfPred = RI->getRegionFor(ExitPred);70 if (RegionOfPred->getExit() != Entry)71 continue;72 73 while (!RegionOfPred->isTopLevelRegion() &&74 RegionOfPred->getExit() == Entry) {75 RegionOfPred->replaceExit(NewEntering);76 RegionOfPred = RegionOfPred->getParent();77 }78 }79 80 // Make all ancestors use EnteringBB as entry; there might be edges to it81 Region *AncestorR = R->getParent();82 RI->setRegionFor(NewEntering, AncestorR);83 while (!AncestorR->isTopLevelRegion() && AncestorR->getEntry() == Entry) {84 AncestorR->replaceEntry(NewEntering);85 AncestorR = AncestorR->getParent();86 }87 }88 89 EnteringBB = NewEntering;90 }91 assert(R->getEnteringBlock() == EnteringBB);92 93 // After:94 //95 // \ / //96 // EnteringBB //97 // | //98 // | //99 // Entry <--\ //100 // / \ / //101 // .... //102}103 104// Ensure that the region has a single block that branches to the exit node.105static void simplifyRegionExit(Region *R, DominatorTree *DT, LoopInfo *LI,106 RegionInfo *RI) {107 BasicBlock *ExitBB = R->getExit();108 BasicBlock *ExitingBB = R->getExitingBlock();109 110 // Before:111 //112 // (Region) ______/ //113 // \ | / //114 // ExitBB //115 // / \ //116 117 if (!ExitingBB) {118 SmallVector<BasicBlock *, 4> Preds;119 for (BasicBlock *P : predecessors(ExitBB))120 if (R->contains(P))121 Preds.push_back(P);122 123 // Preds[0] Preds[1] otherBB //124 // \ | ________/ //125 // \ | / //126 // BB //127 ExitingBB =128 SplitBlockPredecessors(ExitBB, Preds, ".region_exiting", DT, LI);129 // Preds[0] Preds[1] otherBB //130 // \ / / //131 // BB.region_exiting / //132 // \ / //133 // BB //134 135 if (RI)136 RI->setRegionFor(ExitingBB, R);137 138 // Change the exit of nested regions, but not the region itself,139 R->replaceExitRecursive(ExitingBB);140 R->replaceExit(ExitBB);141 }142 assert(ExitingBB == R->getExitingBlock());143 144 // After:145 //146 // \ / //147 // ExitingBB _____/ //148 // \ / //149 // ExitBB //150 // / \ //151}152 153void polly::simplifyRegion(Region *R, DominatorTree *DT, LoopInfo *LI,154 RegionInfo *RI) {155 assert(R && !R->isTopLevelRegion());156 assert(!RI || RI == R->getRegionInfo());157 assert((!RI || DT) &&158 "RegionInfo requires DominatorTree to be updated as well");159 160 simplifyRegionEntry(R, DT, LI, RI);161 simplifyRegionExit(R, DT, LI, RI);162 assert(R->isSimple());163}164 165// Split the block into two successive blocks.166//167// Like llvm::SplitBlock, but also preserves RegionInfo168static BasicBlock *splitBlock(BasicBlock *Old, BasicBlock::iterator SplitPt,169 DominatorTree *DT, llvm::LoopInfo *LI,170 RegionInfo *RI) {171 assert(Old);172 173 // Before:174 //175 // \ / //176 // Old //177 // / \ //178 179 BasicBlock *NewBlock = llvm::SplitBlock(Old, SplitPt, DT, LI);180 181 if (RI) {182 Region *R = RI->getRegionFor(Old);183 RI->setRegionFor(NewBlock, R);184 }185 186 // After:187 //188 // \ / //189 // Old //190 // | //191 // NewBlock //192 // / \ //193 194 return NewBlock;195}196 197void polly::splitEntryBlockForAlloca(BasicBlock *EntryBlock, DominatorTree *DT,198 LoopInfo *LI, RegionInfo *RI) {199 // Find first non-alloca instruction. Every basic block has a non-alloca200 // instruction, as every well formed basic block has a terminator.201 BasicBlock::iterator I = EntryBlock->begin();202 while (isa<AllocaInst>(I))203 ++I;204 205 // splitBlock updates DT, LI and RI.206 splitBlock(EntryBlock, I, DT, LI, RI);207}208 209void polly::recordAssumption(polly::RecordedAssumptionsTy *RecordedAssumptions,210 polly::AssumptionKind Kind, isl::set Set,211 DebugLoc Loc, polly::AssumptionSign Sign,212 BasicBlock *BB, bool RTC) {213 assert((Set.is_params() || BB) &&214 "Assumptions without a basic block must be parameter sets");215 if (RecordedAssumptions)216 RecordedAssumptions->push_back({Kind, Sign, Set, Loc, BB, RTC});217}218 219/// ScopExpander generates IR the the value of a SCEV that represents a value220/// from a SCoP.221///222/// IMPORTANT: There are two ScalarEvolutions at play here. First, the SE that223/// was used to analyze the original SCoP (not actually referenced anywhere224/// here, but passed as argument to make the distinction clear). Second, GenSE225/// which is the SE for the function that the code is emitted into. SE and GenSE226/// may be different when the generated code is to be emitted into an outlined227/// function, e.g. for a parallel loop. That is, each SCEV is to be used only by228/// the SE that "owns" it and ScopExpander handles the translation between them.229/// The SCEVVisitor methods are only to be called on SCEVs of the original SE.230/// Their job is to create a new SCEV for GenSE. The nested SCEVExpander is to231/// be used only with SCEVs belonging to GenSE. Currently SCEVs do not store a232/// reference to the ScalarEvolution they belong to, so a mixup does not233/// immediately cause a crash but certainly is a violation of its interface.234///235/// The SCEVExpander will __not__ generate any code for an existing SDiv/SRem236/// instruction but just use it, if it is referenced as a SCEVUnknown. We want237/// however to generate new code if the instruction is in the analyzed region238/// and we generate code outside/in front of that region. Hence, we generate the239/// code for the SDiv/SRem operands in front of the analyzed region and then240/// create a new SDiv/SRem operation there too.241struct ScopExpander final : SCEVVisitor<ScopExpander, const SCEV *> {242 friend struct SCEVVisitor<ScopExpander, const SCEV *>;243 244 explicit ScopExpander(const Region &R, ScalarEvolution &SE, Function *GenFn,245 ScalarEvolution &GenSE, const DataLayout &DL,246 const char *Name, ValueMapT *VMap,247 LoopToScevMapT *LoopMap, BasicBlock *RTCBB)248 : Expander(GenSE, DL, Name, /*PreserveLCSSA=*/false), Name(Name), R(R),249 VMap(VMap), LoopMap(LoopMap), RTCBB(RTCBB), GenSE(GenSE), GenFn(GenFn) {250 }251 252 Value *expandCodeFor(const SCEV *E, Type *Ty, BasicBlock::iterator IP) {253 assert(isInGenRegion(&*IP) &&254 "ScopExpander assumes to be applied to generated code region");255 const SCEV *GenE = visit(E);256 return Expander.expandCodeFor(GenE, Ty, IP);257 }258 259 const SCEV *visit(const SCEV *E) {260 // Cache the expansion results for intermediate SCEV expressions. A SCEV261 // expression can refer to an operand multiple times (e.g. "x*x), so262 // a naive visitor takes exponential time.263 if (SCEVCache.count(E))264 return SCEVCache[E];265 const SCEV *Result = SCEVVisitor::visit(E);266 SCEVCache[E] = Result;267 return Result;268 }269 270private:271 SCEVExpander Expander;272 const char *Name;273 const Region &R;274 ValueMapT *VMap;275 LoopToScevMapT *LoopMap;276 BasicBlock *RTCBB;277 DenseMap<const SCEV *, const SCEV *> SCEVCache;278 279 ScalarEvolution &GenSE;280 Function *GenFn;281 282 /// Is the instruction part of the original SCoP (in contrast to be located in283 /// the code-generated region)?284 bool isInOrigRegion(Instruction *Inst) {285 Function *Fn = R.getEntry()->getParent();286 bool isInOrigRegion = Inst->getFunction() == Fn && R.contains(Inst);287 assert((isInOrigRegion || GenFn == Inst->getFunction()) &&288 "Instruction expected to be either in the SCoP or the translated "289 "region");290 return isInOrigRegion;291 }292 293 bool isInGenRegion(Instruction *Inst) { return !isInOrigRegion(Inst); }294 295 const SCEV *visitGenericInst(const SCEVUnknown *E, Instruction *Inst,296 BasicBlock::iterator IP) {297 if (!Inst || isInGenRegion(Inst))298 return E;299 300 assert(!Inst->mayThrow() && !Inst->mayReadOrWriteMemory() &&301 !isa<PHINode>(Inst));302 303 auto *InstClone = Inst->clone();304 for (auto &Op : Inst->operands()) {305 assert(GenSE.isSCEVable(Op->getType()));306 const SCEV *OpSCEV = GenSE.getSCEV(Op);307 auto *OpClone = expandCodeFor(OpSCEV, Op->getType(), IP);308 InstClone->replaceUsesOfWith(Op, OpClone);309 }310 311 InstClone->setName(Name + Inst->getName());312 InstClone->insertBefore(IP);313 return GenSE.getSCEV(InstClone);314 }315 316 const SCEV *visitUnknown(const SCEVUnknown *E) {317 318 // If a value mapping was given try if the underlying value is remapped.319 Value *NewVal = VMap ? VMap->lookup(E->getValue()) : nullptr;320 if (NewVal) {321 const SCEV *NewE = GenSE.getSCEV(NewVal);322 323 // While the mapped value might be different the SCEV representation might324 // not be. To this end we will check before we go into recursion here.325 // FIXME: SCEVVisitor must only visit SCEVs that belong to the original326 // SE. This calls it on SCEVs that belong GenSE.327 if (E != NewE)328 return visit(NewE);329 }330 331 Instruction *Inst = dyn_cast<Instruction>(E->getValue());332 BasicBlock::iterator IP;333 if (Inst && isInGenRegion(Inst))334 IP = Inst->getIterator();335 else if (R.getEntry()->getParent() != GenFn) {336 // RTCBB is in the original function, but we are generating for a337 // subfunction so we cannot emit to RTCBB. Usually, we land here only338 // because E->getValue() is not an instruction but a global or constant339 // which do not need to emit anything.340 IP = GenFn->getEntryBlock().getTerminator()->getIterator();341 } else if (Inst && RTCBB->getParent() == Inst->getFunction())342 IP = RTCBB->getTerminator()->getIterator();343 else344 IP = RTCBB->getParent()->getEntryBlock().getTerminator()->getIterator();345 346 if (!Inst || (Inst->getOpcode() != Instruction::SRem &&347 Inst->getOpcode() != Instruction::SDiv))348 return visitGenericInst(E, Inst, IP);349 350 const SCEV *LHSScev = GenSE.getSCEV(Inst->getOperand(0));351 const SCEV *RHSScev = GenSE.getSCEV(Inst->getOperand(1));352 353 if (!GenSE.isKnownNonZero(RHSScev))354 RHSScev = GenSE.getUMaxExpr(RHSScev, GenSE.getConstant(E->getType(), 1));355 356 Value *LHS = expandCodeFor(LHSScev, E->getType(), IP);357 Value *RHS = expandCodeFor(RHSScev, E->getType(), IP);358 359 Inst = BinaryOperator::Create((Instruction::BinaryOps)Inst->getOpcode(),360 LHS, RHS, Inst->getName() + Name, IP);361 return GenSE.getSCEV(Inst);362 }363 364 /// The following functions will just traverse the SCEV and rebuild it using365 /// GenSE and the new operands returned by the traversal.366 ///367 ///{368 const SCEV *visitConstant(const SCEVConstant *E) { return E; }369 const SCEV *visitVScale(const SCEVVScale *E) { return E; }370 const SCEV *visitPtrToIntExpr(const SCEVPtrToIntExpr *E) {371 return GenSE.getPtrToIntExpr(visit(E->getOperand()), E->getType());372 }373 const SCEV *visitTruncateExpr(const SCEVTruncateExpr *E) {374 return GenSE.getTruncateExpr(visit(E->getOperand()), E->getType());375 }376 const SCEV *visitZeroExtendExpr(const SCEVZeroExtendExpr *E) {377 return GenSE.getZeroExtendExpr(visit(E->getOperand()), E->getType());378 }379 const SCEV *visitSignExtendExpr(const SCEVSignExtendExpr *E) {380 return GenSE.getSignExtendExpr(visit(E->getOperand()), E->getType());381 }382 const SCEV *visitUDivExpr(const SCEVUDivExpr *E) {383 auto *RHSScev = visit(E->getRHS());384 if (!GenSE.isKnownNonZero(RHSScev))385 RHSScev = GenSE.getUMaxExpr(RHSScev, GenSE.getConstant(E->getType(), 1));386 return GenSE.getUDivExpr(visit(E->getLHS()), RHSScev);387 }388 const SCEV *visitAddExpr(const SCEVAddExpr *E) {389 SmallVector<const SCEV *, 4> NewOps;390 for (const SCEV *Op : E->operands())391 NewOps.push_back(visit(Op));392 return GenSE.getAddExpr(NewOps);393 }394 const SCEV *visitMulExpr(const SCEVMulExpr *E) {395 SmallVector<const SCEV *, 4> NewOps;396 for (const SCEV *Op : E->operands())397 NewOps.push_back(visit(Op));398 return GenSE.getMulExpr(NewOps);399 }400 const SCEV *visitUMaxExpr(const SCEVUMaxExpr *E) {401 SmallVector<const SCEV *, 4> NewOps;402 for (const SCEV *Op : E->operands())403 NewOps.push_back(visit(Op));404 return GenSE.getUMaxExpr(NewOps);405 }406 const SCEV *visitSMaxExpr(const SCEVSMaxExpr *E) {407 SmallVector<const SCEV *, 4> NewOps;408 for (const SCEV *Op : E->operands())409 NewOps.push_back(visit(Op));410 return GenSE.getSMaxExpr(NewOps);411 }412 const SCEV *visitUMinExpr(const SCEVUMinExpr *E) {413 SmallVector<const SCEV *, 4> NewOps;414 for (const SCEV *Op : E->operands())415 NewOps.push_back(visit(Op));416 return GenSE.getUMinExpr(NewOps);417 }418 const SCEV *visitSMinExpr(const SCEVSMinExpr *E) {419 SmallVector<const SCEV *, 4> NewOps;420 for (const SCEV *Op : E->operands())421 NewOps.push_back(visit(Op));422 return GenSE.getSMinExpr(NewOps);423 }424 const SCEV *visitSequentialUMinExpr(const SCEVSequentialUMinExpr *E) {425 SmallVector<const SCEV *, 4> NewOps;426 for (const SCEV *Op : E->operands())427 NewOps.push_back(visit(Op));428 return GenSE.getUMinExpr(NewOps, /*Sequential=*/true);429 }430 const SCEV *visitAddRecExpr(const SCEVAddRecExpr *E) {431 SmallVector<const SCEV *, 4> NewOps;432 for (const SCEV *Op : E->operands())433 NewOps.push_back(visit(Op));434 435 const Loop *L = E->getLoop();436 const SCEV *GenLRepl = LoopMap ? LoopMap->lookup(L) : nullptr;437 if (!GenLRepl)438 return GenSE.getAddRecExpr(NewOps, L, E->getNoWrapFlags());439 440 // evaluateAtIteration replaces the SCEVAddrExpr with a direct calculation.441 const SCEV *Evaluated =442 SCEVAddRecExpr::evaluateAtIteration(NewOps, GenLRepl, GenSE);443 444 // FIXME: This emits a SCEV for GenSE (since GenLRepl will refer to the445 // induction variable of a generated loop), so we should not use SCEVVisitor446 // with it. However, it still contains references to the SCoP region.447 return visit(Evaluated);448 }449 ///}450};451 452Value *polly::expandCodeFor(Scop &S, llvm::ScalarEvolution &SE,453 llvm::Function *GenFn, ScalarEvolution &GenSE,454 const DataLayout &DL, const char *Name,455 const SCEV *E, Type *Ty, BasicBlock::iterator IP,456 ValueMapT *VMap, LoopToScevMapT *LoopMap,457 BasicBlock *RTCBB) {458 ScopExpander Expander(S.getRegion(), SE, GenFn, GenSE, DL, Name, VMap,459 LoopMap, RTCBB);460 return Expander.expandCodeFor(E, Ty, IP);461}462 463Value *polly::getConditionFromTerminator(Instruction *TI) {464 if (BranchInst *BR = dyn_cast<BranchInst>(TI)) {465 if (BR->isUnconditional())466 return ConstantInt::getTrue(Type::getInt1Ty(TI->getContext()));467 468 return BR->getCondition();469 }470 471 if (SwitchInst *SI = dyn_cast<SwitchInst>(TI))472 return SI->getCondition();473 474 return nullptr;475}476 477Loop *polly::getLoopSurroundingScop(Scop &S, LoopInfo &LI) {478 // Start with the smallest loop containing the entry and expand that479 // loop until it contains all blocks in the region. If there is a loop480 // containing all blocks in the region check if it is itself contained481 // and if so take the parent loop as it will be the smallest containing482 // the region but not contained by it.483 Loop *L = LI.getLoopFor(S.getEntry());484 while (L) {485 bool AllContained = true;486 for (auto *BB : S.blocks())487 AllContained &= L->contains(BB);488 if (AllContained)489 break;490 L = L->getParentLoop();491 }492 493 return L ? (S.contains(L) ? L->getParentLoop() : L) : nullptr;494}495 496unsigned polly::getNumBlocksInLoop(Loop *L) {497 unsigned NumBlocks = L->getNumBlocks();498 SmallVector<BasicBlock *, 4> ExitBlocks;499 L->getExitBlocks(ExitBlocks);500 501 for (auto ExitBlock : ExitBlocks) {502 if (isa<UnreachableInst>(ExitBlock->getTerminator()))503 NumBlocks++;504 }505 return NumBlocks;506}507 508unsigned polly::getNumBlocksInRegionNode(RegionNode *RN) {509 if (!RN->isSubRegion())510 return 1;511 512 Region *R = RN->getNodeAs<Region>();513 return std::distance(R->block_begin(), R->block_end());514}515 516Loop *polly::getRegionNodeLoop(RegionNode *RN, LoopInfo &LI) {517 if (!RN->isSubRegion()) {518 BasicBlock *BB = RN->getNodeAs<BasicBlock>();519 Loop *L = LI.getLoopFor(BB);520 521 // Unreachable statements are not considered to belong to a LLVM loop, as522 // they are not part of an actual loop in the control flow graph.523 // Nevertheless, we handle certain unreachable statements that are common524 // when modeling run-time bounds checks as being part of the loop to be525 // able to model them and to later eliminate the run-time bounds checks.526 //527 // Specifically, for basic blocks that terminate in an unreachable and528 // where the immediate predecessor is part of a loop, we assume these529 // basic blocks belong to the loop the predecessor belongs to. This530 // allows us to model the following code.531 //532 // for (i = 0; i < N; i++) {533 // if (i > 1024)534 // abort(); <- this abort might be translated to an535 // unreachable536 //537 // A[i] = ...538 // }539 if (!L && isa<UnreachableInst>(BB->getTerminator()) && BB->getPrevNode())540 L = LI.getLoopFor(BB->getPrevNode());541 return L;542 }543 544 Region *NonAffineSubRegion = RN->getNodeAs<Region>();545 Loop *L = LI.getLoopFor(NonAffineSubRegion->getEntry());546 while (L && NonAffineSubRegion->contains(L))547 L = L->getParentLoop();548 return L;549}550 551static bool hasVariantIndex(GetElementPtrInst *Gep, Loop *L, Region &R,552 ScalarEvolution &SE) {553 for (const Use &Val : llvm::drop_begin(Gep->operands(), 1)) {554 const SCEV *PtrSCEV = SE.getSCEVAtScope(Val, L);555 Loop *OuterLoop = R.outermostLoopInRegion(L);556 if (!SE.isLoopInvariant(PtrSCEV, OuterLoop))557 return true;558 }559 return false;560}561 562bool polly::isHoistableLoad(LoadInst *LInst, Region &R, LoopInfo &LI,563 ScalarEvolution &SE, const DominatorTree &DT,564 const InvariantLoadsSetTy &KnownInvariantLoads) {565 Loop *L = LI.getLoopFor(LInst->getParent());566 auto *Ptr = LInst->getPointerOperand();567 568 // A LoadInst is hoistable if the address it is loading from is also569 // invariant; in this case: another invariant load (whether that address570 // is also not written to has to be checked separately)571 // TODO: This only checks for a LoadInst->GetElementPtrInst->LoadInst572 // pattern generated by the Chapel frontend, but generally this applies573 // for any chain of instruction that does not also depend on any574 // induction variable575 if (auto *GepInst = dyn_cast<GetElementPtrInst>(Ptr)) {576 if (!hasVariantIndex(GepInst, L, R, SE)) {577 if (auto *DecidingLoad =578 dyn_cast<LoadInst>(GepInst->getPointerOperand())) {579 if (KnownInvariantLoads.count(DecidingLoad))580 return true;581 }582 }583 }584 585 const SCEV *PtrSCEV = SE.getSCEVAtScope(Ptr, L);586 while (L && R.contains(L)) {587 if (!SE.isLoopInvariant(PtrSCEV, L))588 return false;589 L = L->getParentLoop();590 }591 592 if (!Ptr->hasUseList())593 return true;594 595 for (auto *User : Ptr->users()) {596 auto *UserI = dyn_cast<Instruction>(User);597 if (!UserI || UserI->getFunction() != LInst->getFunction() ||598 !R.contains(UserI))599 continue;600 if (!UserI->mayWriteToMemory())601 continue;602 603 auto &BB = *UserI->getParent();604 if (DT.dominates(&BB, LInst->getParent()))605 return false;606 607 bool DominatesAllPredecessors = true;608 if (R.isTopLevelRegion()) {609 for (BasicBlock &I : *R.getEntry()->getParent())610 if (isa<ReturnInst>(I.getTerminator()) && !DT.dominates(&BB, &I))611 DominatesAllPredecessors = false;612 } else {613 for (auto Pred : predecessors(R.getExit()))614 if (R.contains(Pred) && !DT.dominates(&BB, Pred))615 DominatesAllPredecessors = false;616 }617 618 if (!DominatesAllPredecessors)619 continue;620 621 return false;622 }623 624 return true;625}626 627bool polly::isIgnoredIntrinsic(const Value *V) {628 if (auto *IT = dyn_cast<IntrinsicInst>(V)) {629 switch (IT->getIntrinsicID()) {630 // Lifetime markers are supported/ignored.631 case llvm::Intrinsic::lifetime_start:632 case llvm::Intrinsic::lifetime_end:633 // Invariant markers are supported/ignored.634 case llvm::Intrinsic::invariant_start:635 case llvm::Intrinsic::invariant_end:636 // Some misc annotations are supported/ignored.637 case llvm::Intrinsic::var_annotation:638 case llvm::Intrinsic::ptr_annotation:639 case llvm::Intrinsic::annotation:640 case llvm::Intrinsic::donothing:641 case llvm::Intrinsic::assume:642 // Some debug info intrinsics are supported/ignored.643 case llvm::Intrinsic::dbg_value:644 case llvm::Intrinsic::dbg_declare:645 return true;646 default:647 break;648 }649 }650 return false;651}652 653bool polly::canSynthesize(const Value *V, const Scop &S, ScalarEvolution *SE,654 Loop *Scope) {655 if (!V || !SE->isSCEVable(V->getType()))656 return false;657 658 const InvariantLoadsSetTy &ILS = S.getRequiredInvariantLoads();659 if (const SCEV *Scev = SE->getSCEVAtScope(const_cast<Value *>(V), Scope))660 if (!isa<SCEVCouldNotCompute>(Scev))661 if (!hasScalarDepsInsideRegion(Scev, &S.getRegion(), Scope, false, ILS))662 return true;663 664 return false;665}666 667llvm::BasicBlock *polly::getUseBlock(const llvm::Use &U) {668 Instruction *UI = dyn_cast<Instruction>(U.getUser());669 if (!UI)670 return nullptr;671 672 if (PHINode *PHI = dyn_cast<PHINode>(UI))673 return PHI->getIncomingBlock(U);674 675 return UI->getParent();676}677 678llvm::Loop *polly::getFirstNonBoxedLoopFor(llvm::Loop *L, llvm::LoopInfo &LI,679 const BoxedLoopsSetTy &BoxedLoops) {680 while (BoxedLoops.count(L))681 L = L->getParentLoop();682 return L;683}684 685llvm::Loop *polly::getFirstNonBoxedLoopFor(llvm::BasicBlock *BB,686 llvm::LoopInfo &LI,687 const BoxedLoopsSetTy &BoxedLoops) {688 Loop *L = LI.getLoopFor(BB);689 return getFirstNonBoxedLoopFor(L, LI, BoxedLoops);690}691 692bool polly::isDebugCall(Instruction *Inst) {693 auto *CI = dyn_cast<CallInst>(Inst);694 if (!CI)695 return false;696 697 Function *CF = CI->getCalledFunction();698 if (!CF)699 return false;700 701 return std::find(DebugFunctions.begin(), DebugFunctions.end(),702 CF->getName()) != DebugFunctions.end();703}704 705static bool hasDebugCall(BasicBlock *BB) {706 for (Instruction &Inst : *BB) {707 if (isDebugCall(&Inst))708 return true;709 }710 return false;711}712 713bool polly::hasDebugCall(ScopStmt *Stmt) {714 // Quick skip if no debug functions have been defined.715 if (DebugFunctions.empty())716 return false;717 718 if (!Stmt)719 return false;720 721 for (Instruction *Inst : Stmt->getInstructions())722 if (isDebugCall(Inst))723 return true;724 725 if (Stmt->isRegionStmt()) {726 for (BasicBlock *RBB : Stmt->getRegion()->blocks())727 if (RBB != Stmt->getEntryBlock() && ::hasDebugCall(RBB))728 return true;729 }730 731 return false;732}733 734/// Find a property in a LoopID.735static MDNode *findNamedMetadataNode(MDNode *LoopMD, StringRef Name) {736 if (!LoopMD)737 return nullptr;738 for (const MDOperand &X : drop_begin(LoopMD->operands(), 1)) {739 auto *OpNode = dyn_cast<MDNode>(X.get());740 if (!OpNode)741 continue;742 743 auto *OpName = dyn_cast<MDString>(OpNode->getOperand(0));744 if (!OpName)745 continue;746 if (OpName->getString() == Name)747 return OpNode;748 }749 return nullptr;750}751 752static std::optional<const MDOperand *> findNamedMetadataArg(MDNode *LoopID,753 StringRef Name) {754 MDNode *MD = findNamedMetadataNode(LoopID, Name);755 if (!MD)756 return std::nullopt;757 switch (MD->getNumOperands()) {758 case 1:759 return nullptr;760 case 2:761 return &MD->getOperand(1);762 default:763 llvm_unreachable("loop metadata has 0 or 1 operand");764 }765}766 767std::optional<Metadata *> polly::findMetadataOperand(MDNode *LoopMD,768 StringRef Name) {769 MDNode *MD = findNamedMetadataNode(LoopMD, Name);770 if (!MD)771 return std::nullopt;772 switch (MD->getNumOperands()) {773 case 1:774 return nullptr;775 case 2:776 return MD->getOperand(1).get();777 default:778 llvm_unreachable("loop metadata must have 0 or 1 operands");779 }780}781 782static std::optional<bool> getOptionalBoolLoopAttribute(MDNode *LoopID,783 StringRef Name) {784 MDNode *MD = findNamedMetadataNode(LoopID, Name);785 if (!MD)786 return std::nullopt;787 switch (MD->getNumOperands()) {788 case 1:789 return true;790 case 2:791 if (ConstantInt *IntMD =792 mdconst::extract_or_null<ConstantInt>(MD->getOperand(1).get()))793 return IntMD->getZExtValue();794 return true;795 }796 llvm_unreachable("unexpected number of options");797}798 799bool polly::getBooleanLoopAttribute(MDNode *LoopID, StringRef Name) {800 return getOptionalBoolLoopAttribute(LoopID, Name).value_or(false);801}802 803std::optional<int> polly::getOptionalIntLoopAttribute(MDNode *LoopID,804 StringRef Name) {805 const MDOperand *AttrMD =806 findNamedMetadataArg(LoopID, Name).value_or(nullptr);807 if (!AttrMD)808 return std::nullopt;809 810 ConstantInt *IntMD = mdconst::extract_or_null<ConstantInt>(AttrMD->get());811 if (!IntMD)812 return std::nullopt;813 814 return IntMD->getSExtValue();815}816 817bool polly::hasDisableAllTransformsHint(Loop *L) {818 return llvm::hasDisableAllTransformsHint(L);819}820 821bool polly::hasDisableAllTransformsHint(llvm::MDNode *LoopID) {822 return getBooleanLoopAttribute(LoopID, "llvm.loop.disable_nonforced");823}824 825isl::id polly::getIslLoopAttr(isl::ctx Ctx, BandAttr *Attr) {826 assert(Attr && "Must be a valid BandAttr");827 828 // The name "Loop" signals that this id contains a pointer to a BandAttr.829 // The ScheduleOptimizer also uses the string "Inter iteration alias-free" in830 // markers, but it's user pointer is an llvm::Value.831 isl::id Result = isl::id::alloc(Ctx, "Loop with Metadata", Attr);832 Result = isl::manage(isl_id_set_free_user(Result.release(), [](void *Ptr) {833 BandAttr *Attr = reinterpret_cast<BandAttr *>(Ptr);834 delete Attr;835 }));836 return Result;837}838 839isl::id polly::createIslLoopAttr(isl::ctx Ctx, Loop *L) {840 if (!L)841 return {};842 843 // A loop without metadata does not need to be annotated.844 MDNode *LoopID = L->getLoopID();845 if (!LoopID)846 return {};847 848 BandAttr *Attr = new BandAttr();849 Attr->OriginalLoop = L;850 Attr->Metadata = L->getLoopID();851 852 return getIslLoopAttr(Ctx, Attr);853}854 855bool polly::isLoopAttr(const isl::id &Id) {856 if (Id.is_null())857 return false;858 859 return Id.get_name() == "Loop with Metadata";860}861 862BandAttr *polly::getLoopAttr(const isl::id &Id) {863 if (!isLoopAttr(Id))864 return nullptr;865 866 return reinterpret_cast<BandAttr *>(Id.get_user());867}868