1 //===- bolt/Passes/ReachingDefOrUse.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_REACHINGDEFORUSE_H 10 #define BOLT_PASSES_REACHINGDEFORUSE_H 11 12 #include "bolt/Passes/DataflowAnalysis.h" 13 #include "bolt/Passes/RegAnalysis.h" 14 #include "llvm/Support/CommandLine.h" 15 #include <optional> 16 17 namespace opts { 18 extern llvm::cl::opt<bool> TimeOpts; 19 } 20 21 namespace llvm { 22 namespace bolt { 23 24 /// If \p Def is true, this computes a forward dataflow equation to 25 /// propagate reaching definitions. 26 /// If false, this computes a backward dataflow equation propagating 27 /// uses to their definitions. 28 template <bool Def = false> 29 class ReachingDefOrUse 30 : public InstrsDataflowAnalysis<ReachingDefOrUse<Def>, !Def> { 31 friend class DataflowAnalysis<ReachingDefOrUse<Def>, BitVector, !Def>; 32 33 public: 34 ReachingDefOrUse(const RegAnalysis &RA, BinaryFunction &BF, 35 std::optional<MCPhysReg> TrackingReg = std::nullopt, 36 MCPlusBuilder::AllocatorIdTy AllocId = 0) 37 : InstrsDataflowAnalysis<ReachingDefOrUse<Def>, !Def>(BF, AllocId), 38 RA(RA), TrackingReg(TrackingReg) {} ~ReachingDefOrUse()39 virtual ~ReachingDefOrUse() {} 40 isReachedBy(MCPhysReg Reg,ExprIterator Candidates)41 bool isReachedBy(MCPhysReg Reg, ExprIterator Candidates) { 42 for (auto I = Candidates; I != this->expr_end(); ++I) { 43 BitVector BV = BitVector(this->BC.MRI->getNumRegs(), false); 44 if (Def) 45 RA.getInstClobberList(**I, BV); 46 else 47 this->BC.MIB->getTouchedRegs(**I, BV); 48 if (BV[Reg]) 49 return true; 50 } 51 return false; 52 } 53 doesAReachesB(const MCInst & A,const MCInst & B)54 bool doesAReachesB(const MCInst &A, const MCInst &B) { 55 return (*this->getStateAt(B))[this->ExprToIdx[&A]]; 56 } 57 run()58 void run() { InstrsDataflowAnalysis<ReachingDefOrUse<Def>, !Def>::run(); } 59 60 protected: 61 /// Reference to the result of reg analysis 62 const RegAnalysis &RA; 63 64 /// If set, limit the dataflow to only track instructions affecting this 65 /// register. Otherwise the analysis can be too permissive. 66 std::optional<MCPhysReg> TrackingReg; 67 preflight()68 void preflight() { 69 // Populate our universe of tracked expressions with all instructions 70 // except pseudos 71 for (BinaryBasicBlock &BB : this->Func) { 72 for (MCInst &Inst : BB) { 73 this->Expressions.push_back(&Inst); 74 this->ExprToIdx[&Inst] = this->NumInstrs++; 75 } 76 } 77 } 78 getStartingStateAtBB(const BinaryBasicBlock & BB)79 BitVector getStartingStateAtBB(const BinaryBasicBlock &BB) { 80 return BitVector(this->NumInstrs, false); 81 } 82 getStartingStateAtPoint(const MCInst & Point)83 BitVector getStartingStateAtPoint(const MCInst &Point) { 84 return BitVector(this->NumInstrs, false); 85 } 86 doConfluence(BitVector & StateOut,const BitVector & StateIn)87 void doConfluence(BitVector &StateOut, const BitVector &StateIn) { 88 StateOut |= StateIn; 89 } 90 91 /// Define the function computing the kill set -- whether expression Y, a 92 /// tracked expression, will be considered to be dead after executing X. doesXKillsY(const MCInst * X,const MCInst * Y)93 bool doesXKillsY(const MCInst *X, const MCInst *Y) { 94 // getClobberedRegs for X and Y. If they intersect, return true 95 BitVector XClobbers = BitVector(this->BC.MRI->getNumRegs(), false); 96 BitVector YClobbers = BitVector(this->BC.MRI->getNumRegs(), false); 97 RA.getInstClobberList(*X, XClobbers); 98 // In defs, write after write -> kills first write 99 // In uses, write after access (read or write) -> kills access 100 if (Def) 101 RA.getInstClobberList(*Y, YClobbers); 102 else 103 this->BC.MIB->getTouchedRegs(*Y, YClobbers); 104 // Limit the analysis, if requested 105 if (TrackingReg) { 106 XClobbers &= this->BC.MIB->getAliases(*TrackingReg); 107 YClobbers &= this->BC.MIB->getAliases(*TrackingReg); 108 } 109 // X kills Y if it clobbers Y completely -- this is a conservative approach. 110 // In practice, we may produce use-def links that may not exist. 111 XClobbers &= YClobbers; 112 return XClobbers == YClobbers; 113 } 114 computeNext(const MCInst & Point,const BitVector & Cur)115 BitVector computeNext(const MCInst &Point, const BitVector &Cur) { 116 BitVector Next = Cur; 117 // Kill 118 for (auto I = this->expr_begin(Next), E = this->expr_end(); I != E; ++I) { 119 assert(*I != nullptr && "Lost pointers"); 120 if (doesXKillsY(&Point, *I)) { 121 Next.reset(I.getBitVectorIndex()); 122 } 123 } 124 // Gen 125 if (!this->BC.MIB->isCFI(Point)) { 126 if (TrackingReg == std::nullopt) { 127 // Track all instructions 128 Next.set(this->ExprToIdx[&Point]); 129 } else { 130 // Track only instructions relevant to TrackingReg 131 BitVector Regs = BitVector(this->BC.MRI->getNumRegs(), false); 132 if (Def) 133 RA.getInstClobberList(Point, Regs); 134 else 135 RA.getInstUsedRegsList(Point, Regs, false); 136 Regs &= this->BC.MIB->getAliases(*TrackingReg); 137 if (Regs.any()) 138 Next.set(this->ExprToIdx[&Point]); 139 } 140 } 141 return Next; 142 } 143 getAnnotationName()144 StringRef getAnnotationName() const { 145 if (Def) 146 return StringRef("ReachingDefs"); 147 return StringRef("ReachingUses"); 148 } 149 }; 150 151 } // end namespace bolt 152 } // end namespace llvm 153 154 #endif 155