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