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-exception 6 // 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 26 using namespace llvm; 27 using namespace polly; 28 29 #define DEBUG_TYPE "polly-scop-helper" 30 31 static 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 the 39 // region. 40 // The identity of the region entry node is preserved. 41 static 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 NewEntering 68 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 it 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(); 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. 105 static 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 153 void 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 RegionInfo 168 static BasicBlock *splitBlock(BasicBlock *Old, Instruction *SplitPt, 169 DominatorTree *DT, llvm::LoopInfo *LI, 170 RegionInfo *RI) { 171 assert(Old && SplitPt); 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 197 void polly::splitEntryBlockForAlloca(BasicBlock *EntryBlock, DominatorTree *DT, 198 LoopInfo *LI, RegionInfo *RI) { 199 // Find first non-alloca instruction. Every basic block has a non-alloca 200 // 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 209 void polly::splitEntryBlockForAlloca(BasicBlock *EntryBlock, Pass *P) { 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; 216 217 // splitBlock updates DT, LI and RI. 218 polly::splitEntryBlockForAlloca(EntryBlock, DT, LI, RI); 219 } 220 221 void polly::recordAssumption(polly::RecordedAssumptionsTy *RecordedAssumptions, 222 polly::AssumptionKind Kind, isl::set Set, 223 DebugLoc Loc, polly::AssumptionSign Sign, 224 BasicBlock *BB, bool RTC) { 225 assert((Set.is_params() || BB) && 226 "Assumptions without a basic block must be parameter sets"); 227 if (RecordedAssumptions) 228 RecordedAssumptions->push_back({Kind, Sign, Set, Loc, BB, RTC}); 229 } 230 231 /// ScopExpander generates IR the the value of a SCEV that represents a value 232 /// from a SCoP. 233 /// 234 /// IMPORTANT: There are two ScalarEvolutions at play here. First, the SE that 235 /// was used to analyze the original SCoP (not actually referenced anywhere 236 /// here, but passed as argument to make the distinction clear). Second, GenSE 237 /// which is the SE for the function that the code is emitted into. SE and GenSE 238 /// may be different when the generated code is to be emitted into an outlined 239 /// function, e.g. for a parallel loop. That is, each SCEV is to be used only by 240 /// the SE that "owns" it and ScopExpander handles the translation between them. 241 /// The SCEVVisitor methods are only to be called on SCEVs of the original SE. 242 /// Their job is to create a new SCEV for GenSE. The nested SCEVExpander is to 243 /// be used only with SCEVs belonging to GenSE. Currently SCEVs do not store a 244 /// reference to the ScalarEvolution they belong to, so a mixup does not 245 /// immediately cause a crash but certainly is a violation of its interface. 246 /// 247 /// The SCEVExpander will __not__ generate any code for an existing SDiv/SRem 248 /// instruction but just use it, if it is referenced as a SCEVUnknown. We want 249 /// however to generate new code if the instruction is in the analyzed region 250 /// and we generate code outside/in front of that region. Hence, we generate the 251 /// code for the SDiv/SRem operands in front of the analyzed region and then 252 /// create a new SDiv/SRem operation there too. 253 struct ScopExpander final : SCEVVisitor<ScopExpander, const SCEV *> { 254 friend struct SCEVVisitor<ScopExpander, const SCEV *>; 255 256 explicit ScopExpander(const Region &R, ScalarEvolution &SE, Function *GenFn, 257 ScalarEvolution &GenSE, const DataLayout &DL, 258 const char *Name, ValueMapT *VMap, 259 LoopToScevMapT *LoopMap, BasicBlock *RTCBB) 260 : Expander(GenSE, DL, Name, /*PreserveLCSSA=*/false), Name(Name), R(R), 261 VMap(VMap), LoopMap(LoopMap), RTCBB(RTCBB), GenSE(GenSE), GenFn(GenFn) { 262 } 263 264 Value *expandCodeFor(const SCEV *E, Type *Ty, Instruction *IP) { 265 assert(isInGenRegion(IP) && 266 "ScopExpander assumes to be applied to generated code region"); 267 const SCEV *GenE = visit(E); 268 return Expander.expandCodeFor(GenE, Ty, IP); 269 } 270 271 const SCEV *visit(const SCEV *E) { 272 // Cache the expansion results for intermediate SCEV expressions. A SCEV 273 // expression can refer to an operand multiple times (e.g. "x*x), so 274 // a naive visitor takes exponential time. 275 if (SCEVCache.count(E)) 276 return SCEVCache[E]; 277 const SCEV *Result = SCEVVisitor::visit(E); 278 SCEVCache[E] = Result; 279 return Result; 280 } 281 282 private: 283 SCEVExpander Expander; 284 const char *Name; 285 const Region &R; 286 ValueMapT *VMap; 287 LoopToScevMapT *LoopMap; 288 BasicBlock *RTCBB; 289 DenseMap<const SCEV *, const SCEV *> SCEVCache; 290 291 ScalarEvolution &GenSE; 292 Function *GenFn; 293 294 /// Is the instruction part of the original SCoP (in contrast to be located in 295 /// the code-generated region)? 296 bool isInOrigRegion(Instruction *Inst) { 297 Function *Fn = R.getEntry()->getParent(); 298 bool isInOrigRegion = Inst->getFunction() == Fn && R.contains(Inst); 299 assert((isInOrigRegion || GenFn == Inst->getFunction()) && 300 "Instruction expected to be either in the SCoP or the translated " 301 "region"); 302 return isInOrigRegion; 303 } 304 305 bool isInGenRegion(Instruction *Inst) { return !isInOrigRegion(Inst); } 306 307 const SCEV *visitGenericInst(const SCEVUnknown *E, Instruction *Inst, 308 Instruction *IP) { 309 if (!Inst || isInGenRegion(Inst)) 310 return E; 311 312 assert(!Inst->mayThrow() && !Inst->mayReadOrWriteMemory() && 313 !isa<PHINode>(Inst)); 314 315 auto *InstClone = Inst->clone(); 316 for (auto &Op : Inst->operands()) { 317 assert(GenSE.isSCEVable(Op->getType())); 318 const SCEV *OpSCEV = GenSE.getSCEV(Op); 319 auto *OpClone = expandCodeFor(OpSCEV, Op->getType(), IP); 320 InstClone->replaceUsesOfWith(Op, OpClone); 321 } 322 323 InstClone->setName(Name + Inst->getName()); 324 InstClone->insertBefore(IP->getIterator()); 325 return GenSE.getSCEV(InstClone); 326 } 327 328 const SCEV *visitUnknown(const SCEVUnknown *E) { 329 330 // If a value mapping was given try if the underlying value is remapped. 331 Value *NewVal = VMap ? VMap->lookup(E->getValue()) : nullptr; 332 if (NewVal) { 333 const SCEV *NewE = GenSE.getSCEV(NewVal); 334 335 // While the mapped value might be different the SCEV representation might 336 // not be. To this end we will check before we go into recursion here. 337 // FIXME: SCEVVisitor must only visit SCEVs that belong to the original 338 // SE. This calls it on SCEVs that belong GenSE. 339 if (E != NewE) 340 return visit(NewE); 341 } 342 343 Instruction *Inst = dyn_cast<Instruction>(E->getValue()); 344 Instruction *IP; 345 if (Inst && isInGenRegion(Inst)) 346 IP = Inst; 347 else if (R.getEntry()->getParent() != GenFn) { 348 // RTCBB is in the original function, but we are generating for a 349 // subfunction so we cannot emit to RTCBB. Usually, we land here only 350 // because E->getValue() is not an instruction but a global or constant 351 // which do not need to emit anything. 352 IP = GenFn->getEntryBlock().getTerminator(); 353 } else if (Inst && RTCBB->getParent() == Inst->getFunction()) 354 IP = RTCBB->getTerminator(); 355 else 356 IP = RTCBB->getParent()->getEntryBlock().getTerminator(); 357 358 if (!Inst || (Inst->getOpcode() != Instruction::SRem && 359 Inst->getOpcode() != Instruction::SDiv)) 360 return visitGenericInst(E, Inst, IP); 361 362 const SCEV *LHSScev = GenSE.getSCEV(Inst->getOperand(0)); 363 const SCEV *RHSScev = GenSE.getSCEV(Inst->getOperand(1)); 364 365 if (!GenSE.isKnownNonZero(RHSScev)) 366 RHSScev = GenSE.getUMaxExpr(RHSScev, GenSE.getConstant(E->getType(), 1)); 367 368 Value *LHS = expandCodeFor(LHSScev, E->getType(), IP); 369 Value *RHS = expandCodeFor(RHSScev, E->getType(), IP); 370 371 Inst = 372 BinaryOperator::Create((Instruction::BinaryOps)Inst->getOpcode(), LHS, 373 RHS, Inst->getName() + Name, IP->getIterator()); 374 return GenSE.getSCEV(Inst); 375 } 376 377 /// The following functions will just traverse the SCEV and rebuild it using 378 /// GenSE and the new operands returned by the traversal. 379 /// 380 ///{ 381 const SCEV *visitConstant(const SCEVConstant *E) { return E; } 382 const SCEV *visitVScale(const SCEVVScale *E) { return E; } 383 const SCEV *visitPtrToIntExpr(const SCEVPtrToIntExpr *E) { 384 return GenSE.getPtrToIntExpr(visit(E->getOperand()), E->getType()); 385 } 386 const SCEV *visitTruncateExpr(const SCEVTruncateExpr *E) { 387 return GenSE.getTruncateExpr(visit(E->getOperand()), E->getType()); 388 } 389 const SCEV *visitZeroExtendExpr(const SCEVZeroExtendExpr *E) { 390 return GenSE.getZeroExtendExpr(visit(E->getOperand()), E->getType()); 391 } 392 const SCEV *visitSignExtendExpr(const SCEVSignExtendExpr *E) { 393 return GenSE.getSignExtendExpr(visit(E->getOperand()), E->getType()); 394 } 395 const SCEV *visitUDivExpr(const SCEVUDivExpr *E) { 396 auto *RHSScev = visit(E->getRHS()); 397 if (!GenSE.isKnownNonZero(RHSScev)) 398 RHSScev = GenSE.getUMaxExpr(RHSScev, GenSE.getConstant(E->getType(), 1)); 399 return GenSE.getUDivExpr(visit(E->getLHS()), RHSScev); 400 } 401 const SCEV *visitAddExpr(const SCEVAddExpr *E) { 402 SmallVector<const SCEV *, 4> NewOps; 403 for (const SCEV *Op : E->operands()) 404 NewOps.push_back(visit(Op)); 405 return GenSE.getAddExpr(NewOps); 406 } 407 const SCEV *visitMulExpr(const SCEVMulExpr *E) { 408 SmallVector<const SCEV *, 4> NewOps; 409 for (const SCEV *Op : E->operands()) 410 NewOps.push_back(visit(Op)); 411 return GenSE.getMulExpr(NewOps); 412 } 413 const SCEV *visitUMaxExpr(const SCEVUMaxExpr *E) { 414 SmallVector<const SCEV *, 4> NewOps; 415 for (const SCEV *Op : E->operands()) 416 NewOps.push_back(visit(Op)); 417 return GenSE.getUMaxExpr(NewOps); 418 } 419 const SCEV *visitSMaxExpr(const SCEVSMaxExpr *E) { 420 SmallVector<const SCEV *, 4> NewOps; 421 for (const SCEV *Op : E->operands()) 422 NewOps.push_back(visit(Op)); 423 return GenSE.getSMaxExpr(NewOps); 424 } 425 const SCEV *visitUMinExpr(const SCEVUMinExpr *E) { 426 SmallVector<const SCEV *, 4> NewOps; 427 for (const SCEV *Op : E->operands()) 428 NewOps.push_back(visit(Op)); 429 return GenSE.getUMinExpr(NewOps); 430 } 431 const SCEV *visitSMinExpr(const SCEVSMinExpr *E) { 432 SmallVector<const SCEV *, 4> NewOps; 433 for (const SCEV *Op : E->operands()) 434 NewOps.push_back(visit(Op)); 435 return GenSE.getSMinExpr(NewOps); 436 } 437 const SCEV *visitSequentialUMinExpr(const SCEVSequentialUMinExpr *E) { 438 SmallVector<const SCEV *, 4> NewOps; 439 for (const SCEV *Op : E->operands()) 440 NewOps.push_back(visit(Op)); 441 return GenSE.getUMinExpr(NewOps, /*Sequential=*/true); 442 } 443 const SCEV *visitAddRecExpr(const SCEVAddRecExpr *E) { 444 SmallVector<const SCEV *, 4> NewOps; 445 for (const SCEV *Op : E->operands()) 446 NewOps.push_back(visit(Op)); 447 448 const Loop *L = E->getLoop(); 449 const SCEV *GenLRepl = LoopMap ? LoopMap->lookup(L) : nullptr; 450 if (!GenLRepl) 451 return GenSE.getAddRecExpr(NewOps, L, E->getNoWrapFlags()); 452 453 // evaluateAtIteration replaces the SCEVAddrExpr with a direct calculation. 454 const SCEV *Evaluated = 455 SCEVAddRecExpr::evaluateAtIteration(NewOps, GenLRepl, GenSE); 456 457 // FIXME: This emits a SCEV for GenSE (since GenLRepl will refer to the 458 // induction variable of a generated loop), so we should not use SCEVVisitor 459 // with it. However, it still contains references to the SCoP region. 460 return visit(Evaluated); 461 } 462 ///} 463 }; 464 465 Value *polly::expandCodeFor(Scop &S, llvm::ScalarEvolution &SE, 466 llvm::Function *GenFn, ScalarEvolution &GenSE, 467 const DataLayout &DL, const char *Name, 468 const SCEV *E, Type *Ty, Instruction *IP, 469 ValueMapT *VMap, LoopToScevMapT *LoopMap, 470 BasicBlock *RTCBB) { 471 ScopExpander Expander(S.getRegion(), SE, GenFn, GenSE, DL, Name, VMap, 472 LoopMap, RTCBB); 473 return Expander.expandCodeFor(E, Ty, IP); 474 } 475 476 Value *polly::getConditionFromTerminator(Instruction *TI) { 477 if (BranchInst *BR = dyn_cast<BranchInst>(TI)) { 478 if (BR->isUnconditional()) 479 return ConstantInt::getTrue(Type::getInt1Ty(TI->getContext())); 480 481 return BR->getCondition(); 482 } 483 484 if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) 485 return SI->getCondition(); 486 487 return nullptr; 488 } 489 490 Loop *polly::getLoopSurroundingScop(Scop &S, LoopInfo &LI) { 491 // Start with the smallest loop containing the entry and expand that 492 // loop until it contains all blocks in the region. If there is a loop 493 // containing all blocks in the region check if it is itself contained 494 // and if so take the parent loop as it will be the smallest containing 495 // the region but not contained by it. 496 Loop *L = LI.getLoopFor(S.getEntry()); 497 while (L) { 498 bool AllContained = true; 499 for (auto *BB : S.blocks()) 500 AllContained &= L->contains(BB); 501 if (AllContained) 502 break; 503 L = L->getParentLoop(); 504 } 505 506 return L ? (S.contains(L) ? L->getParentLoop() : L) : nullptr; 507 } 508 509 unsigned polly::getNumBlocksInLoop(Loop *L) { 510 unsigned NumBlocks = L->getNumBlocks(); 511 SmallVector<BasicBlock *, 4> ExitBlocks; 512 L->getExitBlocks(ExitBlocks); 513 514 for (auto ExitBlock : ExitBlocks) { 515 if (isa<UnreachableInst>(ExitBlock->getTerminator())) 516 NumBlocks++; 517 } 518 return NumBlocks; 519 } 520 521 unsigned polly::getNumBlocksInRegionNode(RegionNode *RN) { 522 if (!RN->isSubRegion()) 523 return 1; 524 525 Region *R = RN->getNodeAs<Region>(); 526 return std::distance(R->block_begin(), R->block_end()); 527 } 528 529 Loop *polly::getRegionNodeLoop(RegionNode *RN, LoopInfo &LI) { 530 if (!RN->isSubRegion()) { 531 BasicBlock *BB = RN->getNodeAs<BasicBlock>(); 532 Loop *L = LI.getLoopFor(BB); 533 534 // Unreachable statements are not considered to belong to a LLVM loop, as 535 // they are not part of an actual loop in the control flow graph. 536 // Nevertheless, we handle certain unreachable statements that are common 537 // when modeling run-time bounds checks as being part of the loop to be 538 // able to model them and to later eliminate the run-time bounds checks. 539 // 540 // Specifically, for basic blocks that terminate in an unreachable and 541 // where the immediate predecessor is part of a loop, we assume these 542 // basic blocks belong to the loop the predecessor belongs to. This 543 // allows us to model the following code. 544 // 545 // for (i = 0; i < N; i++) { 546 // if (i > 1024) 547 // abort(); <- this abort might be translated to an 548 // unreachable 549 // 550 // A[i] = ... 551 // } 552 if (!L && isa<UnreachableInst>(BB->getTerminator()) && BB->getPrevNode()) 553 L = LI.getLoopFor(BB->getPrevNode()); 554 return L; 555 } 556 557 Region *NonAffineSubRegion = RN->getNodeAs<Region>(); 558 Loop *L = LI.getLoopFor(NonAffineSubRegion->getEntry()); 559 while (L && NonAffineSubRegion->contains(L)) 560 L = L->getParentLoop(); 561 return L; 562 } 563 564 static bool hasVariantIndex(GetElementPtrInst *Gep, Loop *L, Region &R, 565 ScalarEvolution &SE) { 566 for (const Use &Val : llvm::drop_begin(Gep->operands(), 1)) { 567 const SCEV *PtrSCEV = SE.getSCEVAtScope(Val, L); 568 Loop *OuterLoop = R.outermostLoopInRegion(L); 569 if (!SE.isLoopInvariant(PtrSCEV, OuterLoop)) 570 return true; 571 } 572 return false; 573 } 574 575 bool polly::isHoistableLoad(LoadInst *LInst, Region &R, LoopInfo &LI, 576 ScalarEvolution &SE, const DominatorTree &DT, 577 const InvariantLoadsSetTy &KnownInvariantLoads) { 578 Loop *L = LI.getLoopFor(LInst->getParent()); 579 auto *Ptr = LInst->getPointerOperand(); 580 581 // A LoadInst is hoistable if the address it is loading from is also 582 // invariant; in this case: another invariant load (whether that address 583 // is also not written to has to be checked separately) 584 // TODO: This only checks for a LoadInst->GetElementPtrInst->LoadInst 585 // pattern generated by the Chapel frontend, but generally this applies 586 // for any chain of instruction that does not also depend on any 587 // induction variable 588 if (auto *GepInst = dyn_cast<GetElementPtrInst>(Ptr)) { 589 if (!hasVariantIndex(GepInst, L, R, SE)) { 590 if (auto *DecidingLoad = 591 dyn_cast<LoadInst>(GepInst->getPointerOperand())) { 592 if (KnownInvariantLoads.count(DecidingLoad)) 593 return true; 594 } 595 } 596 } 597 598 const SCEV *PtrSCEV = SE.getSCEVAtScope(Ptr, L); 599 while (L && R.contains(L)) { 600 if (!SE.isLoopInvariant(PtrSCEV, L)) 601 return false; 602 L = L->getParentLoop(); 603 } 604 605 for (auto *User : Ptr->users()) { 606 auto *UserI = dyn_cast<Instruction>(User); 607 if (!UserI || UserI->getFunction() != LInst->getFunction() || 608 !R.contains(UserI)) 609 continue; 610 if (!UserI->mayWriteToMemory()) 611 continue; 612 613 auto &BB = *UserI->getParent(); 614 if (DT.dominates(&BB, LInst->getParent())) 615 return false; 616 617 bool DominatesAllPredecessors = true; 618 if (R.isTopLevelRegion()) { 619 for (BasicBlock &I : *R.getEntry()->getParent()) 620 if (isa<ReturnInst>(I.getTerminator()) && !DT.dominates(&BB, &I)) 621 DominatesAllPredecessors = false; 622 } else { 623 for (auto Pred : predecessors(R.getExit())) 624 if (R.contains(Pred) && !DT.dominates(&BB, Pred)) 625 DominatesAllPredecessors = false; 626 } 627 628 if (!DominatesAllPredecessors) 629 continue; 630 631 return false; 632 } 633 634 return true; 635 } 636 637 bool polly::isIgnoredIntrinsic(const Value *V) { 638 if (auto *IT = dyn_cast<IntrinsicInst>(V)) { 639 switch (IT->getIntrinsicID()) { 640 // Lifetime markers are supported/ignored. 641 case llvm::Intrinsic::lifetime_start: 642 case llvm::Intrinsic::lifetime_end: 643 // Invariant markers are supported/ignored. 644 case llvm::Intrinsic::invariant_start: 645 case llvm::Intrinsic::invariant_end: 646 // Some misc annotations are supported/ignored. 647 case llvm::Intrinsic::var_annotation: 648 case llvm::Intrinsic::ptr_annotation: 649 case llvm::Intrinsic::annotation: 650 case llvm::Intrinsic::donothing: 651 case llvm::Intrinsic::assume: 652 // Some debug info intrinsics are supported/ignored. 653 case llvm::Intrinsic::dbg_value: 654 case llvm::Intrinsic::dbg_declare: 655 return true; 656 default: 657 break; 658 } 659 } 660 return false; 661 } 662 663 bool polly::canSynthesize(const Value *V, const Scop &S, ScalarEvolution *SE, 664 Loop *Scope) { 665 if (!V || !SE->isSCEVable(V->getType())) 666 return false; 667 668 const InvariantLoadsSetTy &ILS = S.getRequiredInvariantLoads(); 669 if (const SCEV *Scev = SE->getSCEVAtScope(const_cast<Value *>(V), Scope)) 670 if (!isa<SCEVCouldNotCompute>(Scev)) 671 if (!hasScalarDepsInsideRegion(Scev, &S.getRegion(), Scope, false, ILS)) 672 return true; 673 674 return false; 675 } 676 677 llvm::BasicBlock *polly::getUseBlock(const llvm::Use &U) { 678 Instruction *UI = dyn_cast<Instruction>(U.getUser()); 679 if (!UI) 680 return nullptr; 681 682 if (PHINode *PHI = dyn_cast<PHINode>(UI)) 683 return PHI->getIncomingBlock(U); 684 685 return UI->getParent(); 686 } 687 688 llvm::Loop *polly::getFirstNonBoxedLoopFor(llvm::Loop *L, llvm::LoopInfo &LI, 689 const BoxedLoopsSetTy &BoxedLoops) { 690 while (BoxedLoops.count(L)) 691 L = L->getParentLoop(); 692 return L; 693 } 694 695 llvm::Loop *polly::getFirstNonBoxedLoopFor(llvm::BasicBlock *BB, 696 llvm::LoopInfo &LI, 697 const BoxedLoopsSetTy &BoxedLoops) { 698 Loop *L = LI.getLoopFor(BB); 699 return getFirstNonBoxedLoopFor(L, LI, BoxedLoops); 700 } 701 702 bool polly::isDebugCall(Instruction *Inst) { 703 auto *CI = dyn_cast<CallInst>(Inst); 704 if (!CI) 705 return false; 706 707 Function *CF = CI->getCalledFunction(); 708 if (!CF) 709 return false; 710 711 return std::find(DebugFunctions.begin(), DebugFunctions.end(), 712 CF->getName()) != DebugFunctions.end(); 713 } 714 715 static bool hasDebugCall(BasicBlock *BB) { 716 for (Instruction &Inst : *BB) { 717 if (isDebugCall(&Inst)) 718 return true; 719 } 720 return false; 721 } 722 723 bool polly::hasDebugCall(ScopStmt *Stmt) { 724 // Quick skip if no debug functions have been defined. 725 if (DebugFunctions.empty()) 726 return false; 727 728 if (!Stmt) 729 return false; 730 731 for (Instruction *Inst : Stmt->getInstructions()) 732 if (isDebugCall(Inst)) 733 return true; 734 735 if (Stmt->isRegionStmt()) { 736 for (BasicBlock *RBB : Stmt->getRegion()->blocks()) 737 if (RBB != Stmt->getEntryBlock() && ::hasDebugCall(RBB)) 738 return true; 739 } 740 741 return false; 742 } 743 744 /// Find a property in a LoopID. 745 static MDNode *findNamedMetadataNode(MDNode *LoopMD, StringRef Name) { 746 if (!LoopMD) 747 return nullptr; 748 for (const MDOperand &X : drop_begin(LoopMD->operands(), 1)) { 749 auto *OpNode = dyn_cast<MDNode>(X.get()); 750 if (!OpNode) 751 continue; 752 753 auto *OpName = dyn_cast<MDString>(OpNode->getOperand(0)); 754 if (!OpName) 755 continue; 756 if (OpName->getString() == Name) 757 return OpNode; 758 } 759 return nullptr; 760 } 761 762 static std::optional<const MDOperand *> findNamedMetadataArg(MDNode *LoopID, 763 StringRef Name) { 764 MDNode *MD = findNamedMetadataNode(LoopID, Name); 765 if (!MD) 766 return std::nullopt; 767 switch (MD->getNumOperands()) { 768 case 1: 769 return nullptr; 770 case 2: 771 return &MD->getOperand(1); 772 default: 773 llvm_unreachable("loop metadata has 0 or 1 operand"); 774 } 775 } 776 777 std::optional<Metadata *> polly::findMetadataOperand(MDNode *LoopMD, 778 StringRef Name) { 779 MDNode *MD = findNamedMetadataNode(LoopMD, Name); 780 if (!MD) 781 return std::nullopt; 782 switch (MD->getNumOperands()) { 783 case 1: 784 return nullptr; 785 case 2: 786 return MD->getOperand(1).get(); 787 default: 788 llvm_unreachable("loop metadata must have 0 or 1 operands"); 789 } 790 } 791 792 static std::optional<bool> getOptionalBoolLoopAttribute(MDNode *LoopID, 793 StringRef Name) { 794 MDNode *MD = findNamedMetadataNode(LoopID, Name); 795 if (!MD) 796 return std::nullopt; 797 switch (MD->getNumOperands()) { 798 case 1: 799 return true; 800 case 2: 801 if (ConstantInt *IntMD = 802 mdconst::extract_or_null<ConstantInt>(MD->getOperand(1).get())) 803 return IntMD->getZExtValue(); 804 return true; 805 } 806 llvm_unreachable("unexpected number of options"); 807 } 808 809 bool polly::getBooleanLoopAttribute(MDNode *LoopID, StringRef Name) { 810 return getOptionalBoolLoopAttribute(LoopID, Name).value_or(false); 811 } 812 813 std::optional<int> polly::getOptionalIntLoopAttribute(MDNode *LoopID, 814 StringRef Name) { 815 const MDOperand *AttrMD = 816 findNamedMetadataArg(LoopID, Name).value_or(nullptr); 817 if (!AttrMD) 818 return std::nullopt; 819 820 ConstantInt *IntMD = mdconst::extract_or_null<ConstantInt>(AttrMD->get()); 821 if (!IntMD) 822 return std::nullopt; 823 824 return IntMD->getSExtValue(); 825 } 826 827 bool polly::hasDisableAllTransformsHint(Loop *L) { 828 return llvm::hasDisableAllTransformsHint(L); 829 } 830 831 bool polly::hasDisableAllTransformsHint(llvm::MDNode *LoopID) { 832 return getBooleanLoopAttribute(LoopID, "llvm.loop.disable_nonforced"); 833 } 834 835 isl::id polly::getIslLoopAttr(isl::ctx Ctx, BandAttr *Attr) { 836 assert(Attr && "Must be a valid BandAttr"); 837 838 // The name "Loop" signals that this id contains a pointer to a BandAttr. 839 // The ScheduleOptimizer also uses the string "Inter iteration alias-free" in 840 // markers, but it's user pointer is an llvm::Value. 841 isl::id Result = isl::id::alloc(Ctx, "Loop with Metadata", Attr); 842 Result = isl::manage(isl_id_set_free_user(Result.release(), [](void *Ptr) { 843 BandAttr *Attr = reinterpret_cast<BandAttr *>(Ptr); 844 delete Attr; 845 })); 846 return Result; 847 } 848 849 isl::id polly::createIslLoopAttr(isl::ctx Ctx, Loop *L) { 850 if (!L) 851 return {}; 852 853 // A loop without metadata does not need to be annotated. 854 MDNode *LoopID = L->getLoopID(); 855 if (!LoopID) 856 return {}; 857 858 BandAttr *Attr = new BandAttr(); 859 Attr->OriginalLoop = L; 860 Attr->Metadata = L->getLoopID(); 861 862 return getIslLoopAttr(Ctx, Attr); 863 } 864 865 bool polly::isLoopAttr(const isl::id &Id) { 866 if (Id.is_null()) 867 return false; 868 869 return Id.get_name() == "Loop with Metadata"; 870 } 871 872 BandAttr *polly::getLoopAttr(const isl::id &Id) { 873 if (!isLoopAttr(Id)) 874 return nullptr; 875 876 return reinterpret_cast<BandAttr *>(Id.get_user()); 877 } 878