1 //===- bolt/Passes/LivenessAnalysis.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_LIVENESSANALYSIS_H 10 #define BOLT_PASSES_LIVENESSANALYSIS_H 11 12 #include "bolt/Passes/DataflowAnalysis.h" 13 #include "bolt/Passes/RegAnalysis.h" 14 #include "llvm/MC/MCRegisterInfo.h" 15 #include "llvm/Support/CommandLine.h" 16 17 namespace opts { 18 extern llvm::cl::opt<bool> AssumeABI; 19 extern llvm::cl::opt<bool> TimeOpts; 20 } // namespace opts 21 22 namespace llvm { 23 namespace bolt { 24 25 class LivenessAnalysis : public DataflowAnalysis<LivenessAnalysis, BitVector, 26 true, RegStatePrinter> { 27 using Parent = 28 DataflowAnalysis<LivenessAnalysis, BitVector, true, RegStatePrinter>; 29 friend class DataflowAnalysis<LivenessAnalysis, BitVector, true, 30 RegStatePrinter>; 31 32 public: LivenessAnalysis(const RegAnalysis & RA,BinaryFunction & BF,MCPlusBuilder::AllocatorIdTy AllocId)33 LivenessAnalysis(const RegAnalysis &RA, BinaryFunction &BF, 34 MCPlusBuilder::AllocatorIdTy AllocId) 35 : Parent(BF, AllocId), RA(RA), 36 NumRegs(BF.getBinaryContext().MRI->getNumRegs()) {} 37 virtual ~LivenessAnalysis(); 38 isAlive(ProgramPoint PP,MCPhysReg Reg)39 bool isAlive(ProgramPoint PP, MCPhysReg Reg) const { 40 BitVector BV = (*this->getStateAt(PP)); 41 const BitVector &RegAliases = BC.MIB->getAliases(Reg); 42 BV &= RegAliases; 43 return BV.any(); 44 } 45 run()46 void run() { Parent::run(); } 47 48 // Return a usable general-purpose reg after point P. Return 0 if no reg is 49 // available. scavengeRegAfter(ProgramPoint P)50 MCPhysReg scavengeRegAfter(ProgramPoint P) { 51 BitVector BV = *this->getStateAt(P); 52 BV.flip(); 53 BitVector GPRegs(NumRegs, false); 54 this->BC.MIB->getGPRegs(GPRegs, /*IncludeAlias=*/false); 55 // Ignore the register used for frame pointer even if it is not alive (it 56 // may be used by CFI which is not represented in our dataflow). 57 BitVector FP = BC.MIB->getAliases(BC.MIB->getFramePointer()); 58 FP.flip(); 59 BV &= GPRegs; 60 BV &= FP; 61 int Reg = BV.find_first(); 62 return Reg != -1 ? Reg : 0; 63 } 64 65 protected: 66 /// Reference to the result of reg analysis 67 const RegAnalysis &RA; 68 const uint16_t NumRegs; 69 preflight()70 void preflight() {} 71 getStartingStateAtBB(const BinaryBasicBlock & BB)72 BitVector getStartingStateAtBB(const BinaryBasicBlock &BB) { 73 // Entry points start with default live out (registers used as return 74 // values). 75 if (BB.succ_size() == 0) { 76 BitVector State(NumRegs, false); 77 if (opts::AssumeABI) { 78 BC.MIB->getDefaultLiveOut(State); 79 BC.MIB->getCalleeSavedRegs(State); 80 } else { 81 State.set(); 82 State.reset(BC.MIB->getFlagsReg()); 83 } 84 return State; 85 } 86 return BitVector(NumRegs, false); 87 } 88 getStartingStateAtPoint(const MCInst & Point)89 BitVector getStartingStateAtPoint(const MCInst &Point) { 90 return BitVector(NumRegs, false); 91 } 92 doConfluence(BitVector & StateOut,const BitVector & StateIn)93 void doConfluence(BitVector &StateOut, const BitVector &StateIn) { 94 StateOut |= StateIn; 95 } 96 computeNext(const MCInst & Point,const BitVector & Cur)97 BitVector computeNext(const MCInst &Point, const BitVector &Cur) { 98 BitVector Next = Cur; 99 bool IsCall = this->BC.MIB->isCall(Point); 100 // Kill 101 BitVector Written = BitVector(NumRegs, false); 102 if (!IsCall) { 103 this->BC.MIB->getWrittenRegs(Point, Written); 104 } else { 105 RA.getInstClobberList(Point, Written); 106 // When clobber list is conservative, it is clobbering all/most registers, 107 // a conservative estimate because it knows nothing about this call. 108 // For our purposes, assume it kills no registers/callee-saved regs 109 // because we don't really know what's going on. 110 if (RA.isConservative(Written)) { 111 Written.reset(); 112 BC.MIB->getDefaultLiveOut(Written); 113 // If ABI is respected, everything except CSRs should be dead after a 114 // call 115 if (opts::AssumeABI) { 116 BitVector CSR = BitVector(NumRegs, false); 117 BC.MIB->getCalleeSavedRegs(CSR); 118 CSR.flip(); 119 Written |= CSR; 120 } 121 } 122 } 123 Written.flip(); 124 Next &= Written; 125 // Gen 126 if (!this->BC.MIB->isCFI(Point)) { 127 if (BC.MIB->isCleanRegXOR(Point)) 128 return Next; 129 130 BitVector Used = BitVector(NumRegs, false); 131 if (IsCall) { 132 RA.getInstUsedRegsList(Point, Used, /*GetClobbers*/ true); 133 if (RA.isConservative(Used)) { 134 Used = BC.MIB->getRegsUsedAsParams(); 135 BC.MIB->getDefaultLiveOut(Used); 136 } 137 } 138 const MCInstrDesc &InstInfo = BC.MII->get(Point.getOpcode()); 139 for (const MCOperand &Op : BC.MIB->useOperands(Point)) 140 if (Op.isReg()) 141 Used |= BC.MIB->getAliases(Op.getReg(), /*OnlySmaller=*/false); 142 for (MCPhysReg ImplicitUse : InstInfo.implicit_uses()) 143 Used |= BC.MIB->getAliases(ImplicitUse, false); 144 if (IsCall && 145 (!BC.MIB->isTailCall(Point) || !BC.MIB->isConditionalBranch(Point))) { 146 // Never gen FLAGS from a non-conditional call... this is overly 147 // conservative 148 Used.reset(BC.MIB->getFlagsReg()); 149 } 150 Next |= Used; 151 } 152 return Next; 153 } 154 getAnnotationName()155 StringRef getAnnotationName() const { return StringRef("LivenessAnalysis"); } 156 }; 157 158 } // end namespace bolt 159 } // end namespace llvm 160 161 #endif 162