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