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