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/LoopInfo.h" 11 #include "llvm/Analysis/Passes.h" 12 #include "llvm/Analysis/ValueTracking.h" 13 #include "llvm/IR/DataLayout.h" 14 #include "llvm/IR/InstIterator.h" 15 #include "llvm/IR/LLVMContext.h" 16 #include "llvm/IR/Module.h" 17 #include "llvm/Support/ErrorHandling.h" 18 #include "llvm/Support/raw_ostream.h" 19 #include "llvm/Transforms/Utils/LoopUtils.h" 20 using namespace llvm; 21 22 namespace { 23 struct MustExecutePrinter : public FunctionPass { 24 DenseMap<Value*, SmallVector<Loop*, 4> > MustExec; 25 SmallVector<Value *, 4> Ordering; 26 27 static char ID; // Pass identification, replacement for typeid 28 MustExecutePrinter() : FunctionPass(ID) { 29 initializeMustExecutePrinterPass(*PassRegistry::getPassRegistry()); 30 } 31 void getAnalysisUsage(AnalysisUsage &AU) const override { 32 AU.setPreservesAll(); 33 AU.addRequired<DominatorTreeWrapperPass>(); 34 AU.addRequired<LoopInfoWrapperPass>(); 35 } 36 bool runOnFunction(Function &F) override; 37 void print(raw_ostream &OS, const Module * = nullptr) const override; 38 void releaseMemory() override { 39 MustExec.clear(); 40 Ordering.clear(); 41 } 42 }; 43 } 44 45 char MustExecutePrinter::ID = 0; 46 INITIALIZE_PASS_BEGIN(MustExecutePrinter, "print-mustexecute", 47 "Instructions which execute on loop entry", false, true) 48 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) 49 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass) 50 INITIALIZE_PASS_END(MustExecutePrinter, "print-mustexecute", 51 "Instructions which execute on loop entry", false, true) 52 53 FunctionPass *llvm::createMustExecutePrinter() { 54 return new MustExecutePrinter(); 55 } 56 57 bool isMustExecuteIn(Instruction &I, Loop *L, DominatorTree *DT) { 58 // TODO: move loop specific code to analysis 59 //LoopSafetyInfo LSI; 60 //computeLoopSafetyInfo(&LSI, L); 61 //return isGuaranteedToExecute(I, DT, L, &LSI); 62 return isGuaranteedToExecuteForEveryIteration(&I, L); 63 } 64 65 bool MustExecutePrinter::runOnFunction(Function &F) { 66 auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo(); 67 auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree(); 68 for (auto &I: instructions(F)) { 69 Loop *L = LI.getLoopFor(I.getParent()); 70 while (L) { 71 if (isMustExecuteIn(I, L, &DT)) { 72 if (!MustExec.count(&I)) 73 Ordering.push_back(&I); 74 MustExec[&I].push_back(L); 75 } 76 L = L->getParentLoop(); 77 }; 78 } 79 return false; 80 } 81 82 void MustExecutePrinter::print(raw_ostream &OS, const Module *M) const { 83 OS << "The following are guaranteed to execute (for the respective loops):\n"; 84 for (Value *V: Ordering) { 85 V->printAsOperand(OS); 86 auto NumLoops = MustExec.lookup(V).size(); 87 if (NumLoops > 1) 88 OS << "\t(mustexec in " << NumLoops << " loops: "; 89 else 90 OS << "\t(mustexec in: "; 91 92 bool first = true; 93 for (const Loop *L : MustExec.lookup(V)) { 94 if (!first) 95 OS << ", "; 96 first = false; 97 OS << L->getHeader()->getName(); 98 } 99 OS << ")\n"; 100 } 101 OS << "\n"; 102 } 103