lib/Analysis/MustExecute.cpp

   1 //===- MustExecute.cpp - Printer for isGuaranteedToExecute ----------------===//
   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 #include "llvm/Analysis/MustExecute.h"
  10 #include "llvm/ADT/PostOrderIterator.h"
  11 #include "llvm/Analysis/CFG.h"
  12 #include "llvm/Analysis/InstructionSimplify.h"
  13 #include "llvm/Analysis/LoopInfo.h"
  14 #include "llvm/Analysis/Passes.h"
  15 #include "llvm/Analysis/ValueTracking.h"
  16 #include "llvm/IR/AssemblyAnnotationWriter.h"
  17 #include "llvm/IR/DataLayout.h"
  18 #include "llvm/IR/InstIterator.h"
  19 #include "llvm/IR/LLVMContext.h"
  20 #include "llvm/IR/Module.h"
  21 #include "llvm/Support/ErrorHandling.h"
  22 #include "llvm/Support/FormattedStream.h"
  23 #include "llvm/Support/raw_ostream.h"
  24
  25 using namespace llvm;
  26
  27 #define DEBUG_TYPE "must-execute"
  28
  29 const DenseMap<BasicBlock *, ColorVector> &
  30 LoopSafetyInfo::getBlockColors() const {
  31   return BlockColors;
  32 }
  33
  34 void LoopSafetyInfo::copyColors(BasicBlock *New, BasicBlock *Old) {
  35   ColorVector &ColorsForNewBlock = BlockColors[New];
  36   ColorVector &ColorsForOldBlock = BlockColors[Old];
  37   ColorsForNewBlock = ColorsForOldBlock;
  38 }
  39
  40 bool SimpleLoopSafetyInfo::blockMayThrow(const BasicBlock *BB) const {
  41   (void)BB;
  42   return anyBlockMayThrow();
  43 }
  44
  45 bool SimpleLoopSafetyInfo::anyBlockMayThrow() const {
  46   return MayThrow;
  47 }
  48
  49 void SimpleLoopSafetyInfo::computeLoopSafetyInfo(const Loop *CurLoop) {
  50   assert(CurLoop != nullptr && "CurLoop can't be null");
  51   BasicBlock *Header = CurLoop->getHeader();
  52   // Iterate over header and compute safety info.
  53   HeaderMayThrow = !isGuaranteedToTransferExecutionToSuccessor(Header);
  54   MayThrow = HeaderMayThrow;
  55   // Iterate over loop instructions and compute safety info.
  56   // Skip header as it has been computed and stored in HeaderMayThrow.
  57   // The first block in loopinfo.Blocks is guaranteed to be the header.
  58   assert(Header == *CurLoop->getBlocks().begin() &&
  59          "First block must be header");
  60   for (Loop::block_iterator BB = std::next(CurLoop->block_begin()),
  61                             BBE = CurLoop->block_end();
  62        (BB != BBE) && !MayThrow; ++BB)
  63     MayThrow |= !isGuaranteedToTransferExecutionToSuccessor(*BB);
  64
  65   computeBlockColors(CurLoop);
  66 }
  67
  68 bool ICFLoopSafetyInfo::blockMayThrow(const BasicBlock *BB) const {
  69   return ICF.hasICF(BB);
  70 }
  71
  72 bool ICFLoopSafetyInfo::anyBlockMayThrow() const {
  73   return MayThrow;
  74 }
  75
  76 void ICFLoopSafetyInfo::computeLoopSafetyInfo(const Loop *CurLoop) {
  77   assert(CurLoop != nullptr && "CurLoop can't be null");
  78   ICF.clear();
  79   MW.clear();
  80   MayThrow = false;
  81   // Figure out the fact that at least one block may throw.
  82   for (auto &BB : CurLoop->blocks())
  83     if (ICF.hasICF(&*BB)) {
  84       MayThrow = true;
  85       break;
  86     }
  87   computeBlockColors(CurLoop);
  88 }
  89
  90 void ICFLoopSafetyInfo::insertInstructionTo(const Instruction *Inst,
  91                                             const BasicBlock *BB) {
  92   ICF.insertInstructionTo(Inst, BB);
  93   MW.insertInstructionTo(Inst, BB);
  94 }
  95
  96 void ICFLoopSafetyInfo::removeInstruction(const Instruction *Inst) {
  97   ICF.removeInstruction(Inst);
  98   MW.removeInstruction(Inst);
  99 }
 100
 101 void LoopSafetyInfo::computeBlockColors(const Loop *CurLoop) {
 102   // Compute funclet colors if we might sink/hoist in a function with a funclet
 103   // personality routine.
 104   Function *Fn = CurLoop->getHeader()->getParent();
 105   if (Fn->hasPersonalityFn())
 106     if (Constant *PersonalityFn = Fn->getPersonalityFn())
 107       if (isScopedEHPersonality(classifyEHPersonality(PersonalityFn)))
 108         BlockColors = colorEHFunclets(*Fn);
 109 }
 110
 111 /// Return true if we can prove that the given ExitBlock is not reached on the
 112 /// first iteration of the given loop.  That is, the backedge of the loop must
 113 /// be executed before the ExitBlock is executed in any dynamic execution trace.
 114 static bool CanProveNotTakenFirstIteration(const BasicBlock *ExitBlock,
 115                                            const DominatorTree *DT,
 116                                            const Loop *CurLoop) {
 117   auto *CondExitBlock = ExitBlock->getSinglePredecessor();
 118   if (!CondExitBlock)
 119     // expect unique exits
 120     return false;
 121   assert(CurLoop->contains(CondExitBlock) && "meaning of exit block");
 122   auto *BI = dyn_cast<BranchInst>(CondExitBlock->getTerminator());
 123   if (!BI || !BI->isConditional())
 124     return false;
 125   // If condition is constant and false leads to ExitBlock then we always
 126   // execute the true branch.
 127   if (auto *Cond = dyn_cast<ConstantInt>(BI->getCondition()))
 128     return BI->getSuccessor(Cond->getZExtValue() ? 1 : 0) == ExitBlock;
 129   auto *Cond = dyn_cast<CmpInst>(BI->getCondition());
 130   if (!Cond)
 131     return false;
 132   // todo: this would be a lot more powerful if we used scev, but all the
 133   // plumbing is currently missing to pass a pointer in from the pass
 134   // Check for cmp (phi [x, preheader] ...), y where (pred x, y is known
 135   auto *LHS = dyn_cast<PHINode>(Cond->getOperand(0));
 136   auto *RHS = Cond->getOperand(1);
 137   if (!LHS || LHS->getParent() != CurLoop->getHeader())
 138     return false;
 139   auto DL = ExitBlock->getModule()->getDataLayout();
 140   auto *IVStart = LHS->getIncomingValueForBlock(CurLoop->getLoopPreheader());
 141   auto *SimpleValOrNull = SimplifyCmpInst(Cond->getPredicate(),
 142                                           IVStart, RHS,
 143                                           {DL, /*TLI*/ nullptr,
 144                                               DT, /*AC*/ nullptr, BI});
 145   auto *SimpleCst = dyn_cast_or_null<Constant>(SimpleValOrNull);
 146   if (!SimpleCst)
 147     return false;
 148   if (ExitBlock == BI->getSuccessor(0))
 149     return SimpleCst->isZeroValue();
 150   assert(ExitBlock == BI->getSuccessor(1) && "implied by above");
 151   return SimpleCst->isAllOnesValue();
 152 }
 153
 154 /// Collect all blocks from \p CurLoop which lie on all possible paths from
 155 /// the header of \p CurLoop (inclusive) to BB (exclusive) into the set
 156 /// \p Predecessors. If \p BB is the header, \p Predecessors will be empty.
 157 static void collectTransitivePredecessors(
 158     const Loop *CurLoop, const BasicBlock *BB,
 159     SmallPtrSetImpl<const BasicBlock *> &Predecessors) {
 160   assert(Predecessors.empty() && "Garbage in predecessors set?");
 161   assert(CurLoop->contains(BB) && "Should only be called for loop blocks!");
 162   if (BB == CurLoop->getHeader())
 163     return;
 164   SmallVector<const BasicBlock *, 4> WorkList;
 165   for (auto *Pred : predecessors(BB)) {
 166     Predecessors.insert(Pred);
 167     WorkList.push_back(Pred);
 168   }
 169   while (!WorkList.empty()) {
 170     auto *Pred = WorkList.pop_back_val();
 171     assert(CurLoop->contains(Pred) && "Should only reach loop blocks!");
 172     // We are not interested in backedges and we don't want to leave loop.
 173     if (Pred == CurLoop->getHeader())
 174       continue;
 175     // TODO: If BB lies in an inner loop of CurLoop, this will traverse over all
 176     // blocks of this inner loop, even those that are always executed AFTER the
 177     // BB. It may make our analysis more conservative than it could be, see test
 178     // @nested and @nested_no_throw in test/Analysis/MustExecute/loop-header.ll.
 179     // We can ignore backedge of all loops containing BB to get a sligtly more
 180     // optimistic result.
 181     for (auto *PredPred : predecessors(Pred))
 182       if (Predecessors.insert(PredPred).second)
 183         WorkList.push_back(PredPred);
 184   }
 185 }
 186
 187 bool LoopSafetyInfo::allLoopPathsLeadToBlock(const Loop *CurLoop,
 188                                              const BasicBlock *BB,
 189                                              const DominatorTree *DT) const {
 190   assert(CurLoop->contains(BB) && "Should only be called for loop blocks!");
 191
 192   // Fast path: header is always reached once the loop is entered.
 193   if (BB == CurLoop->getHeader())
 194     return true;
 195
 196   // Collect all transitive predecessors of BB in the same loop. This set will
 197   // be a subset of the blocks within the loop.
 198   SmallPtrSet<const BasicBlock *, 4> Predecessors;
 199   collectTransitivePredecessors(CurLoop, BB, Predecessors);
 200
 201   // Make sure that all successors of, all predecessors of BB which are not
 202   // dominated by BB, are either:
 203   // 1) BB,
 204   // 2) Also predecessors of BB,
 205   // 3) Exit blocks which are not taken on 1st iteration.
 206   // Memoize blocks we've already checked.
 207   SmallPtrSet<const BasicBlock *, 4> CheckedSuccessors;
 208   for (auto *Pred : Predecessors) {
 209     // Predecessor block may throw, so it has a side exit.
 210     if (blockMayThrow(Pred))
 211       return false;
 212
 213     // BB dominates Pred, so if Pred runs, BB must run.
 214     // This is true when Pred is a loop latch.
 215     if (DT->dominates(BB, Pred))
 216       continue;
 217
 218     for (auto *Succ : successors(Pred))
 219       if (CheckedSuccessors.insert(Succ).second &&
 220           Succ != BB && !Predecessors.count(Succ))
 221         // By discharging conditions that are not executed on the 1st iteration,
 222         // we guarantee that *at least* on the first iteration all paths from
 223         // header that *may* execute will lead us to the block of interest. So
 224         // that if we had virtually peeled one iteration away, in this peeled
 225         // iteration the set of predecessors would contain only paths from
 226         // header to BB without any exiting edges that may execute.
 227         //
 228         // TODO: We only do it for exiting edges currently. We could use the
 229         // same function to skip some of the edges within the loop if we know
 230         // that they will not be taken on the 1st iteration.
 231         //
 232         // TODO: If we somehow know the number of iterations in loop, the same
 233         // check may be done for any arbitrary N-th iteration as long as N is
 234         // not greater than minimum number of iterations in this loop.
 235         if (CurLoop->contains(Succ) ||
 236             !CanProveNotTakenFirstIteration(Succ, DT, CurLoop))
 237           return false;
 238   }
 239
 240   // All predecessors can only lead us to BB.
 241   return true;
 242 }
 243
 244 /// Returns true if the instruction in a loop is guaranteed to execute at least
 245 /// once.
 246 bool SimpleLoopSafetyInfo::isGuaranteedToExecute(const Instruction &Inst,
 247                                                  const DominatorTree *DT,
 248                                                  const Loop *CurLoop) const {
 249   // If the instruction is in the header block for the loop (which is very
 250   // common), it is always guaranteed to dominate the exit blocks.  Since this
 251   // is a common case, and can save some work, check it now.
 252   if (Inst.getParent() == CurLoop->getHeader())
 253     // If there's a throw in the header block, we can't guarantee we'll reach
 254     // Inst unless we can prove that Inst comes before the potential implicit
 255     // exit.  At the moment, we use a (cheap) hack for the common case where
 256     // the instruction of interest is the first one in the block.
 257     return !HeaderMayThrow ||
 258            Inst.getParent()->getFirstNonPHIOrDbg() == &Inst;
 259
 260   // If there is a path from header to exit or latch that doesn't lead to our
 261   // instruction's block, return false.
 262   return allLoopPathsLeadToBlock(CurLoop, Inst.getParent(), DT);
 263 }
 264
 265 bool ICFLoopSafetyInfo::isGuaranteedToExecute(const Instruction &Inst,
 266                                               const DominatorTree *DT,
 267                                               const Loop *CurLoop) const {
 268   return !ICF.isDominatedByICFIFromSameBlock(&Inst) &&
 269          allLoopPathsLeadToBlock(CurLoop, Inst.getParent(), DT);
 270 }
 271
 272 bool ICFLoopSafetyInfo::doesNotWriteMemoryBefore(const BasicBlock *BB,
 273                                                  const Loop *CurLoop) const {
 274   assert(CurLoop->contains(BB) && "Should only be called for loop blocks!");
 275
 276   // Fast path: there are no instructions before header.
 277   if (BB == CurLoop->getHeader())
 278     return true;
 279
 280   // Collect all transitive predecessors of BB in the same loop. This set will
 281   // be a subset of the blocks within the loop.
 282   SmallPtrSet<const BasicBlock *, 4> Predecessors;
 283   collectTransitivePredecessors(CurLoop, BB, Predecessors);
 284   // Find if there any instruction in either predecessor that could write
 285   // to memory.
 286   for (auto *Pred : Predecessors)
 287     if (MW.mayWriteToMemory(Pred))
 288       return false;
 289   return true;
 290 }
 291
 292 bool ICFLoopSafetyInfo::doesNotWriteMemoryBefore(const Instruction &I,
 293                                                  const Loop *CurLoop) const {
 294   auto *BB = I.getParent();
 295   assert(CurLoop->contains(BB) && "Should only be called for loop blocks!");
 296   return !MW.isDominatedByMemoryWriteFromSameBlock(&I) &&
 297          doesNotWriteMemoryBefore(BB, CurLoop);
 298 }
 299
 300 namespace {
 301   struct MustExecutePrinter : public FunctionPass {
 302
 303     static char ID; // Pass identification, replacement for typeid
 304     MustExecutePrinter() : FunctionPass(ID) {
 305       initializeMustExecutePrinterPass(*PassRegistry::getPassRegistry());
 306     }
 307     void getAnalysisUsage(AnalysisUsage &AU) const override {
 308       AU.setPreservesAll();
 309       AU.addRequired<DominatorTreeWrapperPass>();
 310       AU.addRequired<LoopInfoWrapperPass>();
 311     }
 312     bool runOnFunction(Function &F) override;
 313   };
 314   struct MustBeExecutedContextPrinter : public ModulePass {
 315     static char ID;
 316
 317     MustBeExecutedContextPrinter() : ModulePass(ID) {
 318       initializeMustBeExecutedContextPrinterPass(*PassRegistry::getPassRegistry());
 319     }
 320     void getAnalysisUsage(AnalysisUsage &AU) const override {
 321       AU.setPreservesAll();
 322     }
 323     bool runOnModule(Module &M) override;
 324   };
 325 }
 326
 327 char MustExecutePrinter::ID = 0;
 328 INITIALIZE_PASS_BEGIN(MustExecutePrinter, "print-mustexecute",
 329                       "Instructions which execute on loop entry", false, true)
 330 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
 331 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
 332 INITIALIZE_PASS_END(MustExecutePrinter, "print-mustexecute",
 333                     "Instructions which execute on loop entry", false, true)
 334
 335 FunctionPass *llvm::createMustExecutePrinter() {
 336   return new MustExecutePrinter();
 337 }
 338
 339 char MustBeExecutedContextPrinter::ID = 0;
 340 INITIALIZE_PASS_BEGIN(
 341     MustBeExecutedContextPrinter, "print-must-be-executed-contexts",
 342     "print the must-be-executed-contexed for all instructions", false, true)
 343 INITIALIZE_PASS_DEPENDENCY(PostDominatorTreeWrapperPass)
 344 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
 345 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
 346 INITIALIZE_PASS_END(MustBeExecutedContextPrinter,
 347                     "print-must-be-executed-contexts",
 348                     "print the must-be-executed-contexed for all instructions",
 349                     false, true)
 350
 351 ModulePass *llvm::createMustBeExecutedContextPrinter() {
 352   return new MustBeExecutedContextPrinter();
 353 }
 354
 355 bool MustBeExecutedContextPrinter::runOnModule(Module &M) {
 356   MustBeExecutedContextExplorer Explorer(true);
 357   for (Function &F : M) {
 358     for (Instruction &I : instructions(F)) {
 359       dbgs() << "-- Explore context of: " << I << "\n";
 360       for (const Instruction *CI : Explorer.range(&I))
 361         dbgs() << "  [F: " << CI->getFunction()->getName() << "] " << *CI
 362                << "\n";
 363     }
 364   }
 365
 366   return false;
 367 }
 368
 369 static bool isMustExecuteIn(const Instruction &I, Loop *L, DominatorTree *DT) {
 370   // TODO: merge these two routines.  For the moment, we display the best
 371   // result obtained by *either* implementation.  This is a bit unfair since no
 372   // caller actually gets the full power at the moment.
 373   SimpleLoopSafetyInfo LSI;
 374   LSI.computeLoopSafetyInfo(L);
 375   return LSI.isGuaranteedToExecute(I, DT, L) ||
 376     isGuaranteedToExecuteForEveryIteration(&I, L);
 377 }
 378
 379 namespace {
 380 /// An assembly annotator class to print must execute information in
 381 /// comments.
 382 class MustExecuteAnnotatedWriter : public AssemblyAnnotationWriter {
 383   DenseMap<const Value*, SmallVector<Loop*, 4> > MustExec;
 384
 385 public:
 386   MustExecuteAnnotatedWriter(const Function &F,
 387                              DominatorTree &DT, LoopInfo &LI) {
 388     for (auto &I: instructions(F)) {
 389       Loop *L = LI.getLoopFor(I.getParent());
 390       while (L) {
 391         if (isMustExecuteIn(I, L, &DT)) {
 392           MustExec[&I].push_back(L);
 393         }
 394         L = L->getParentLoop();
 395       };
 396     }
 397   }
 398   MustExecuteAnnotatedWriter(const Module &M,
 399                              DominatorTree &DT, LoopInfo &LI) {
 400     for (auto &F : M)
 401     for (auto &I: instructions(F)) {
 402       Loop *L = LI.getLoopFor(I.getParent());
 403       while (L) {
 404         if (isMustExecuteIn(I, L, &DT)) {
 405           MustExec[&I].push_back(L);
 406         }
 407         L = L->getParentLoop();
 408       };
 409     }
 410   }
 411
 412
 413   void printInfoComment(const Value &V, formatted_raw_ostream &OS) override {
 414     if (!MustExec.count(&V))
 415       return;
 416
 417     const auto &Loops = MustExec.lookup(&V);
 418     const auto NumLoops = Loops.size();
 419     if (NumLoops > 1)
 420       OS << " ; (mustexec in " << NumLoops << " loops: ";
 421     else
 422       OS << " ; (mustexec in: ";
 423
 424     bool first = true;
 425     for (const Loop *L : Loops) {
 426       if (!first)
 427         OS << ", ";
 428       first = false;
 429       OS << L->getHeader()->getName();
 430     }
 431     OS << ")";
 432   }
 433 };
 434 } // namespace
 435
 436 bool MustExecutePrinter::runOnFunction(Function &F) {
 437   auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
 438   auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
 439
 440   MustExecuteAnnotatedWriter Writer(F, DT, LI);
 441   F.print(dbgs(), &Writer);
 442
 443   return false;
 444 }
 445
 446 const Instruction *
 447 MustBeExecutedContextExplorer::getMustBeExecutedNextInstruction(
 448     MustBeExecutedIterator &It, const Instruction *PP) {
 449   if (!PP)
 450     return PP;
 451   LLVM_DEBUG(dbgs() << "Find next instruction for " << *PP << "\n");
 452
 453   // If we explore only inside a given basic block we stop at terminators.
 454   if (!ExploreInterBlock && PP->isTerminator()) {
 455     LLVM_DEBUG(dbgs() << "\tReached terminator in intra-block mode, done\n");
 456     return nullptr;
 457   }
 458
 459   // If we do not traverse the call graph we check if we can make progress in
 460   // the current function. First, check if the instruction is guaranteed to
 461   // transfer execution to the successor.
 462   bool TransfersExecution = isGuaranteedToTransferExecutionToSuccessor(PP);
 463   if (!TransfersExecution)
 464     return nullptr;
 465
 466   // If this is not a terminator we know that there is a single instruction
 467   // after this one that is executed next if control is transfered. If not,
 468   // we can try to go back to a call site we entered earlier. If none exists, we
 469   // do not know any instruction that has to be executd next.
 470   if (!PP->isTerminator()) {
 471     const Instruction *NextPP = PP->getNextNode();
 472     LLVM_DEBUG(dbgs() << "\tIntermediate instruction does transfer control\n");
 473     return NextPP;
 474   }
 475
 476   // Finally, we have to handle terminators, trivial ones first.
 477   assert(PP->isTerminator() && "Expected a terminator!");
 478
 479   // A terminator without a successor is not handled yet.
 480   if (PP->getNumSuccessors() == 0) {
 481     LLVM_DEBUG(dbgs() << "\tUnhandled terminator\n");
 482     return nullptr;
 483   }
 484
 485   // A terminator with a single successor, we will continue at the beginning of
 486   // that one.
 487   if (PP->getNumSuccessors() == 1) {
 488     LLVM_DEBUG(
 489         dbgs() << "\tUnconditional terminator, continue with successor\n");
 490     return &PP->getSuccessor(0)->front();
 491   }
 492
 493   LLVM_DEBUG(dbgs() << "\tNo join point found\n");
 494   return nullptr;
 495 }
 496
 497 MustBeExecutedIterator::MustBeExecutedIterator(
 498     MustBeExecutedContextExplorer &Explorer, const Instruction *I)
 499     : Explorer(Explorer), CurInst(I) {
 500   reset(I);
 501 }
 502
 503 void MustBeExecutedIterator::reset(const Instruction *I) {
 504   CurInst = I;
 505   Visited.clear();
 506   Visited.insert(I);
 507 }
 508
 509 const Instruction *MustBeExecutedIterator::advance() {
 510   assert(CurInst && "Cannot advance an end iterator!");
 511   const Instruction *Next =
 512       Explorer.getMustBeExecutedNextInstruction(*this, CurInst);
 513   if (Next && !Visited.insert(Next).second)
 514     Next = nullptr;
 515   return Next;
 516 }