1 //===- bolt/Passes/DominatorAnalysis.h --------------------------*- C++ -*-===// 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 #ifndef BOLT_PASSES_DOMINATORANALYSIS_H 10 #define BOLT_PASSES_DOMINATORANALYSIS_H 11 12 #include "bolt/Passes/DataflowAnalysis.h" 13 #include "llvm/Support/CommandLine.h" 14 15 namespace opts { 16 extern llvm::cl::opt<bool> TimeOpts; 17 } 18 19 namespace llvm { 20 namespace bolt { 21 22 /// The whole reason for running a dominator analysis at the instruction level 23 /// (that is much more expensive than at the BB level) is because of invoke 24 /// instructions that may cause early exits in the middle of the BB, making half 25 /// of the BB potentially dominate the landing pad but not instructions after 26 /// the invoke. 27 template <bool Backward = false> 28 class DominatorAnalysis 29 : public InstrsDataflowAnalysis<DominatorAnalysis<Backward>, Backward> { 30 friend class DataflowAnalysis<DominatorAnalysis<Backward>, BitVector, 31 Backward>; 32 33 public: DominatorAnalysis(BinaryFunction & BF,MCPlusBuilder::AllocatorIdTy AllocId)34 DominatorAnalysis(BinaryFunction &BF, MCPlusBuilder::AllocatorIdTy AllocId) 35 : InstrsDataflowAnalysis<DominatorAnalysis<Backward>, Backward>(BF, 36 AllocId) { 37 } ~DominatorAnalysis()38 virtual ~DominatorAnalysis() {} 39 getDominanceFrontierFor(const MCInst & Dom)40 SmallSetVector<ProgramPoint, 4> getDominanceFrontierFor(const MCInst &Dom) { 41 SmallSetVector<ProgramPoint, 4> Result; 42 uint64_t DomIdx = this->ExprToIdx[&Dom]; 43 assert(!Backward && "Post-dom frontier not implemented"); 44 for (BinaryBasicBlock &BB : this->Func) { 45 bool HasDominatedPred = false; 46 bool HasNonDominatedPred = false; 47 SmallSetVector<ProgramPoint, 4> Candidates; 48 this->doForAllSuccsOrPreds(BB, [&](ProgramPoint P) { 49 if ((*this->getStateAt(P))[DomIdx]) { 50 Candidates.insert(P); 51 HasDominatedPred = true; 52 return; 53 } 54 HasNonDominatedPred = true; 55 }); 56 if (HasDominatedPred && HasNonDominatedPred) 57 Result.insert(Candidates.begin(), Candidates.end()); 58 if ((*this->getStateAt(ProgramPoint::getLastPointAt(BB)))[DomIdx] && 59 BB.succ_begin() == BB.succ_end()) 60 Result.insert(ProgramPoint::getLastPointAt(BB)); 61 } 62 return Result; 63 } 64 doesADominateB(const MCInst & A,unsigned BIdx)65 bool doesADominateB(const MCInst &A, unsigned BIdx) { 66 return this->count(BIdx, A); 67 } 68 doesADominateB(const MCInst & A,const MCInst & B)69 bool doesADominateB(const MCInst &A, const MCInst &B) { 70 return this->count(B, A); 71 } 72 doesADominateB(const MCInst & A,ProgramPoint B)73 bool doesADominateB(const MCInst &A, ProgramPoint B) { 74 return this->count(B, A); 75 } 76 doesADominateB(ProgramPoint A,const MCInst & B)77 bool doesADominateB(ProgramPoint A, const MCInst &B) { 78 if (A.isInst()) 79 return doesADominateB(*A.getInst(), B); 80 81 // This analysis keep track of which instructions dominates another 82 // instruction, it doesn't keep track of BBs. So we need a non-empty 83 // BB if we want to know whether this BB dominates something. 84 BinaryBasicBlock *BB = A.getBB(); 85 while (BB->size() == 0) { 86 if (BB->succ_size() == 0) 87 return false; 88 assert(BB->succ_size() == 1); 89 BB = *BB->succ_begin(); 90 } 91 const MCInst &InstA = *BB->begin(); 92 return doesADominateB(InstA, B); 93 } 94 doForAllDominators(const MCInst & Inst,std::function<void (const MCInst &)> Task)95 void doForAllDominators(const MCInst &Inst, 96 std::function<void(const MCInst &)> Task) { 97 for (auto I = this->expr_begin(Inst), E = this->expr_end(); I != E; ++I) 98 Task(**I); 99 } 100 run()101 void run() { 102 InstrsDataflowAnalysis<DominatorAnalysis<Backward>, Backward>::run(); 103 } 104 105 private: preflight()106 void preflight() { 107 // Populate our universe of tracked expressions with all instructions 108 // except pseudos 109 for (BinaryBasicBlock &BB : this->Func) { 110 for (MCInst &Inst : BB) { 111 this->Expressions.push_back(&Inst); 112 this->ExprToIdx[&Inst] = this->NumInstrs++; 113 } 114 } 115 } 116 getStartingStateAtBB(const BinaryBasicBlock & BB)117 BitVector getStartingStateAtBB(const BinaryBasicBlock &BB) { 118 // Entry points start with empty set 119 // All others start with the full set. 120 if (!Backward && BB.pred_size() == 0 && BB.throw_size() == 0) 121 return BitVector(this->NumInstrs, false); 122 if (Backward && BB.succ_size() == 0) 123 return BitVector(this->NumInstrs, false); 124 return BitVector(this->NumInstrs, true); 125 } 126 getStartingStateAtPoint(const MCInst & Point)127 BitVector getStartingStateAtPoint(const MCInst &Point) { 128 return BitVector(this->NumInstrs, true); 129 } 130 doConfluence(BitVector & StateOut,const BitVector & StateIn)131 void doConfluence(BitVector &StateOut, const BitVector &StateIn) { 132 StateOut &= StateIn; 133 } 134 computeNext(const MCInst & Point,const BitVector & Cur)135 BitVector computeNext(const MCInst &Point, const BitVector &Cur) { 136 BitVector Next = Cur; 137 // Gen 138 if (!this->BC.MIB->isCFI(Point)) 139 Next.set(this->ExprToIdx[&Point]); 140 return Next; 141 } 142 getAnnotationName()143 StringRef getAnnotationName() const { 144 if (Backward) 145 return StringRef("PostDominatorAnalysis"); 146 return StringRef("DominatorAnalysis"); 147 } 148 }; 149 150 } // end namespace bolt 151 } // end namespace llvm 152 153 #endif 154