lib/Analysis/MustExecute.cpp

   1 //===- MustExecute.cpp - Printer for isGuaranteedToExecute ----------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9
  10 #include "llvm/Analysis/MustExecute.h"
  11 #include "llvm/Analysis/InstructionSimplify.h"
  12 #include "llvm/Analysis/LoopInfo.h"
  13 #include "llvm/Analysis/Passes.h"
  14 #include "llvm/Analysis/ValueTracking.h"
  15 #include "llvm/IR/AssemblyAnnotationWriter.h"
  16 #include "llvm/IR/DataLayout.h"
  17 #include "llvm/IR/InstIterator.h"
  18 #include "llvm/IR/LLVMContext.h"
  19 #include "llvm/IR/Module.h"
  20 #include "llvm/Support/ErrorHandling.h"
  21 #include "llvm/Support/FormattedStream.h"
  22 #include "llvm/Support/raw_ostream.h"
  23 using namespace llvm;
  24
  25 bool LoopSafetyInfo::headerMayThrow() const {
  26   return HeaderMayThrow;
  27 }
  28
  29 bool LoopSafetyInfo::anyBlockMayThrow() const {
  30   return MayThrow;
  31 }
  32
  33 void LoopSafetyInfo::computeLoopSafetyInfo(Loop *CurLoop) {
  34   assert(CurLoop != nullptr && "CurLoop can't be null");
  35   BasicBlock *Header = CurLoop->getHeader();
  36   // Iterate over header and compute safety info.
  37   HeaderMayThrow = !isGuaranteedToTransferExecutionToSuccessor(Header);
  38   MayThrow = HeaderMayThrow;
  39   // Iterate over loop instructions and compute safety info.
  40   // Skip header as it has been computed and stored in HeaderMayThrow.
  41   // The first block in loopinfo.Blocks is guaranteed to be the header.
  42   assert(Header == *CurLoop->getBlocks().begin() &&
  43          "First block must be header");
  44   for (Loop::block_iterator BB = std::next(CurLoop->block_begin()),
  45                             BBE = CurLoop->block_end();
  46        (BB != BBE) && !MayThrow; ++BB)
  47     MayThrow |= !isGuaranteedToTransferExecutionToSuccessor(*BB);
  48
  49   // Compute funclet colors if we might sink/hoist in a function with a funclet
  50   // personality routine.
  51   Function *Fn = CurLoop->getHeader()->getParent();
  52   if (Fn->hasPersonalityFn())
  53     if (Constant *PersonalityFn = Fn->getPersonalityFn())
  54       if (isScopedEHPersonality(classifyEHPersonality(PersonalityFn)))
  55         BlockColors = colorEHFunclets(*Fn);
  56 }
  57
  58 /// Return true if we can prove that the given ExitBlock is not reached on the
  59 /// first iteration of the given loop.  That is, the backedge of the loop must
  60 /// be executed before the ExitBlock is executed in any dynamic execution trace.
  61 static bool CanProveNotTakenFirstIteration(const BasicBlock *ExitBlock,
  62                                            const DominatorTree *DT,
  63                                            const Loop *CurLoop) {
  64   auto *CondExitBlock = ExitBlock->getSinglePredecessor();
  65   if (!CondExitBlock)
  66     // expect unique exits
  67     return false;
  68   assert(CurLoop->contains(CondExitBlock) && "meaning of exit block");
  69   auto *BI = dyn_cast<BranchInst>(CondExitBlock->getTerminator());
  70   if (!BI || !BI->isConditional())
  71     return false;
  72   // If condition is constant and false leads to ExitBlock then we always
  73   // execute the true branch.
  74   if (auto *Cond = dyn_cast<ConstantInt>(BI->getCondition()))
  75     return BI->getSuccessor(Cond->getZExtValue() ? 1 : 0) == ExitBlock;
  76   auto *Cond = dyn_cast<CmpInst>(BI->getCondition());
  77   if (!Cond)
  78     return false;
  79   // todo: this would be a lot more powerful if we used scev, but all the
  80   // plumbing is currently missing to pass a pointer in from the pass
  81   // Check for cmp (phi [x, preheader] ...), y where (pred x, y is known
  82   auto *LHS = dyn_cast<PHINode>(Cond->getOperand(0));
  83   auto *RHS = Cond->getOperand(1);
  84   if (!LHS || LHS->getParent() != CurLoop->getHeader())
  85     return false;
  86   auto DL = ExitBlock->getModule()->getDataLayout();
  87   auto *IVStart = LHS->getIncomingValueForBlock(CurLoop->getLoopPreheader());
  88   auto *SimpleValOrNull = SimplifyCmpInst(Cond->getPredicate(),
  89                                           IVStart, RHS,
  90                                           {DL, /*TLI*/ nullptr,
  91                                               DT, /*AC*/ nullptr, BI});
  92   auto *SimpleCst = dyn_cast_or_null<Constant>(SimpleValOrNull);
  93   if (!SimpleCst)
  94     return false;
  95   if (ExitBlock == BI->getSuccessor(0))
  96     return SimpleCst->isZeroValue();
  97   assert(ExitBlock == BI->getSuccessor(1) && "implied by above");
  98   return SimpleCst->isAllOnesValue();
  99 }
 100
 101 void LoopSafetyInfo::collectTransitivePredecessors(
 102     const Loop *CurLoop, const BasicBlock *BB,
 103     SmallPtrSetImpl<const BasicBlock *> &Predecessors) const {
 104   assert(Predecessors.empty() && "Garbage in predecessors set?");
 105   assert(CurLoop->contains(BB) && "Should only be called for loop blocks!");
 106   if (BB == CurLoop->getHeader())
 107     return;
 108   SmallVector<const BasicBlock *, 4> WorkList;
 109   for (auto *Pred : predecessors(BB)) {
 110     Predecessors.insert(Pred);
 111     WorkList.push_back(Pred);
 112   }
 113   while (!WorkList.empty()) {
 114     auto *Pred = WorkList.pop_back_val();
 115     assert(CurLoop->contains(Pred) && "Should only reach loop blocks!");
 116     // We are not interested in backedges and we don't want to leave loop.
 117     if (Pred == CurLoop->getHeader())
 118       continue;
 119     // TODO: If BB lies in an inner loop of CurLoop, this will traverse over all
 120     // blocks of this inner loop, even those that are always executed AFTER the
 121     // BB. It may make our analysis more conservative than it could be, see test
 122     // @nested and @nested_no_throw in test/Analysis/MustExecute/loop-header.ll.
 123     // We can ignore backedge of all loops containing BB to get a sligtly more
 124     // optimistic result.
 125     for (auto *PredPred : predecessors(Pred))
 126       if (Predecessors.insert(PredPred).second)
 127         WorkList.push_back(PredPred);
 128   }
 129 }
 130
 131 bool LoopSafetyInfo::allLoopPathsLeadToBlock(const Loop *CurLoop,
 132                                              const BasicBlock *BB,
 133                                              const DominatorTree *DT) const {
 134   assert(CurLoop->contains(BB) && "Should only be called for loop blocks!");
 135
 136   // Fast path: header is always reached once the loop is entered.
 137   if (BB == CurLoop->getHeader())
 138     return true;
 139
 140   // Collect all transitive predecessors of BB in the same loop. This set will
 141   // be a subset of the blocks within the loop.
 142   SmallPtrSet<const BasicBlock *, 4> Predecessors;
 143   collectTransitivePredecessors(CurLoop, BB, Predecessors);
 144
 145   // Make sure that all successors of all predecessors of BB are either:
 146   // 1) BB,
 147   // 2) Also predecessors of BB,
 148   // 3) Exit blocks which are not taken on 1st iteration.
 149   // Memoize blocks we've already checked.
 150   SmallPtrSet<const BasicBlock *, 4> CheckedSuccessors;
 151   for (auto *Pred : Predecessors)
 152     for (auto *Succ : successors(Pred))
 153       if (CheckedSuccessors.insert(Succ).second &&
 154           Succ != BB && !Predecessors.count(Succ))
 155         // By discharging conditions that are not executed on the 1st iteration,
 156         // we guarantee that *at least* on the first iteration all paths from
 157         // header that *may* execute will lead us to the block of interest. So
 158         // that if we had virtually peeled one iteration away, in this peeled
 159         // iteration the set of predecessors would contain only paths from
 160         // header to BB without any exiting edges that may execute.
 161         //
 162         // TODO: We only do it for exiting edges currently. We could use the
 163         // same function to skip some of the edges within the loop if we know
 164         // that they will not be taken on the 1st iteration.
 165         //
 166         // TODO: If we somehow know the number of iterations in loop, the same
 167         // check may be done for any arbitrary N-th iteration as long as N is
 168         // not greater than minimum number of iterations in this loop.
 169         if (CurLoop->contains(Succ) ||
 170             !CanProveNotTakenFirstIteration(Succ, DT, CurLoop))
 171           return false;
 172
 173   // All predecessors can only lead us to BB.
 174   return true;
 175 }
 176
 177 /// Returns true if the instruction in a loop is guaranteed to execute at least
 178 /// once.
 179 bool llvm::isGuaranteedToExecute(const Instruction &Inst,
 180                                  const DominatorTree *DT, const Loop *CurLoop,
 181                                  const LoopSafetyInfo *SafetyInfo) {
 182   // We have to check to make sure that the instruction dominates all
 183   // of the exit blocks.  If it doesn't, then there is a path out of the loop
 184   // which does not execute this instruction, so we can't hoist it.
 185
 186   // If the instruction is in the header block for the loop (which is very
 187   // common), it is always guaranteed to dominate the exit blocks.  Since this
 188   // is a common case, and can save some work, check it now.
 189   if (Inst.getParent() == CurLoop->getHeader())
 190     // If there's a throw in the header block, we can't guarantee we'll reach
 191     // Inst unless we can prove that Inst comes before the potential implicit
 192     // exit.  At the moment, we use a (cheap) hack for the common case where
 193     // the instruction of interest is the first one in the block.
 194     return !SafetyInfo->headerMayThrow() ||
 195       Inst.getParent()->getFirstNonPHIOrDbg() == &Inst;
 196
 197   // Somewhere in this loop there is an instruction which may throw and make us
 198   // exit the loop.
 199   if (SafetyInfo->anyBlockMayThrow())
 200     return false;
 201
 202   // If there is a path from header to exit or latch that doesn't lead to our
 203   // instruction's block, return false.
 204   if (!SafetyInfo->allLoopPathsLeadToBlock(CurLoop, Inst.getParent(), DT))
 205     return false;
 206
 207   return true;
 208 }
 209
 210
 211 namespace {
 212   struct MustExecutePrinter : public FunctionPass {
 213
 214     static char ID; // Pass identification, replacement for typeid
 215     MustExecutePrinter() : FunctionPass(ID) {
 216       initializeMustExecutePrinterPass(*PassRegistry::getPassRegistry());
 217     }
 218     void getAnalysisUsage(AnalysisUsage &AU) const override {
 219       AU.setPreservesAll();
 220       AU.addRequired<DominatorTreeWrapperPass>();
 221       AU.addRequired<LoopInfoWrapperPass>();
 222     }
 223     bool runOnFunction(Function &F) override;
 224   };
 225 }
 226
 227 char MustExecutePrinter::ID = 0;
 228 INITIALIZE_PASS_BEGIN(MustExecutePrinter, "print-mustexecute",
 229                       "Instructions which execute on loop entry", false, true)
 230 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
 231 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
 232 INITIALIZE_PASS_END(MustExecutePrinter, "print-mustexecute",
 233                     "Instructions which execute on loop entry", false, true)
 234
 235 FunctionPass *llvm::createMustExecutePrinter() {
 236   return new MustExecutePrinter();
 237 }
 238
 239 static bool isMustExecuteIn(const Instruction &I, Loop *L, DominatorTree *DT) {
 240   // TODO: merge these two routines.  For the moment, we display the best
 241   // result obtained by *either* implementation.  This is a bit unfair since no
 242   // caller actually gets the full power at the moment.
 243   LoopSafetyInfo LSI;
 244   LSI.computeLoopSafetyInfo(L);
 245   return isGuaranteedToExecute(I, DT, L, &LSI) ||
 246     isGuaranteedToExecuteForEveryIteration(&I, L);
 247 }
 248
 249 namespace {
 250 /// An assembly annotator class to print must execute information in
 251 /// comments.
 252 class MustExecuteAnnotatedWriter : public AssemblyAnnotationWriter {
 253   DenseMap<const Value*, SmallVector<Loop*, 4> > MustExec;
 254
 255 public:
 256   MustExecuteAnnotatedWriter(const Function &F,
 257                              DominatorTree &DT, LoopInfo &LI) {
 258     for (auto &I: instructions(F)) {
 259       Loop *L = LI.getLoopFor(I.getParent());
 260       while (L) {
 261         if (isMustExecuteIn(I, L, &DT)) {
 262           MustExec[&I].push_back(L);
 263         }
 264         L = L->getParentLoop();
 265       };
 266     }
 267   }
 268   MustExecuteAnnotatedWriter(const Module &M,
 269                              DominatorTree &DT, LoopInfo &LI) {
 270     for (auto &F : M)
 271     for (auto &I: instructions(F)) {
 272       Loop *L = LI.getLoopFor(I.getParent());
 273       while (L) {
 274         if (isMustExecuteIn(I, L, &DT)) {
 275           MustExec[&I].push_back(L);
 276         }
 277         L = L->getParentLoop();
 278       };
 279     }
 280   }
 281
 282
 283   void printInfoComment(const Value &V, formatted_raw_ostream &OS) override {
 284     if (!MustExec.count(&V))
 285       return;
 286
 287     const auto &Loops = MustExec.lookup(&V);
 288     const auto NumLoops = Loops.size();
 289     if (NumLoops > 1)
 290       OS << " ; (mustexec in " << NumLoops << " loops: ";
 291     else
 292       OS << " ; (mustexec in: ";
 293
 294     bool first = true;
 295     for (const Loop *L : Loops) {
 296       if (!first)
 297         OS << ", ";
 298       first = false;
 299       OS << L->getHeader()->getName();
 300     }
 301     OS << ")";
 302   }
 303 };
 304 } // namespace
 305
 306 bool MustExecutePrinter::runOnFunction(Function &F) {
 307   auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
 308   auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
 309
 310   MustExecuteAnnotatedWriter Writer(F, DT, LI);
 311   F.print(dbgs(), &Writer);
 312
 313   return false;
 314 }