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