1 //===- bolt/Passes/FrameAnalysis.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_FRAMEANALYSIS_H 10 #define BOLT_PASSES_FRAMEANALYSIS_H 11 12 #include "bolt/Passes/StackPointerTracking.h" 13 14 namespace llvm { 15 namespace bolt { 16 class BinaryFunctionCallGraph; 17 18 /// Alias analysis information attached to each instruction that accesses a 19 /// frame position. This is called a "frame index" by LLVM Target libs when 20 /// it is building a MachineFunction frame, and we use the same name here 21 /// because we are essentially doing the job of frame reconstruction. 22 struct FrameIndexEntry { 23 /// If both IsLoad and IsStore are set, it means this is an instruction that 24 /// reads and updates this frame location. 25 bool IsLoad; 26 bool IsStore; 27 /// If a store, this controls whether the store uses a register os an imm 28 /// as the source value. 29 bool IsStoreFromReg; 30 /// If load, this holds the destination register. If store, this holds 31 /// either the source register or source immediate. 32 int32_t RegOrImm; 33 34 /// StackOffset and Size are the two aspects that identify this frame access 35 /// for the purposes of alias analysis. 36 int64_t StackOffset; 37 uint8_t Size; 38 39 /// If this is false, we will never atempt to remove or optimize this 40 /// instruction. We just use it to keep track of stores we don't fully 41 /// understand but we know it may write to a frame position. 42 bool IsSimple; 43 44 uint16_t StackPtrReg; 45 }; 46 47 /// Record an access to an argument in stack. This should be attached to 48 /// call instructions, so StackOffset and Size are determined in the context 49 /// of the caller. This information helps the caller understand how the callee 50 /// may access its private stack. 51 struct ArgInStackAccess { 52 int64_t StackOffset; 53 uint8_t Size; 54 55 bool operator<(const ArgInStackAccess &RHS) const { 56 if (StackOffset != RHS.StackOffset) 57 return StackOffset < RHS.StackOffset; 58 return Size < RHS.Size; 59 } 60 }; 61 62 /// The set of all args-in-stack accesses for a given instruction. If 63 /// AssumeEverything is true, then the set should be ignored and the 64 /// corresponding instruction should be treated as accessing the entire 65 /// stack for the purposes of analysis and optimization. 66 struct ArgAccesses { 67 bool AssumeEverything; 68 std::set<ArgInStackAccess> Set; 69 ArgAccessesArgAccesses70 explicit ArgAccesses(bool AssumeEverything) 71 : AssumeEverything(AssumeEverything) {} 72 }; 73 74 raw_ostream &operator<<(raw_ostream &OS, const FrameIndexEntry &FIE); 75 76 /// This pass attaches stack access information to instructions. If a load/store 77 /// instruction accesses a stack position, it will identify the CFA offset and 78 /// size information of this access, where CFA is the Canonical Frame Address 79 /// (using DWARF terminology). 80 /// 81 /// This pass also computes frame usage information obtained by a bottom-up call 82 /// graph traversal: which registers are clobbered by functions (including their 83 /// callees as determined by the call graph), whether a function accesses its 84 /// caller's stack frame and whether a function demands its stack to be aligned 85 /// due to the use of SSE aligned load/store operations present in itself or any 86 /// of its direct or indirect callees. 87 /// 88 /// Initialization: 89 /// 90 /// FrameAnalysis FA(PrintPass); 91 /// FA.runOnFunctions(BC); 92 /// 93 /// Usage (fetching frame access information about a given instruction): 94 /// 95 /// auto FIE = FA.getFIEFor(BC, Instruction); 96 /// if (FIE && FIE->IsSimple) { 97 /// ... = FIE->StackOffset 98 /// ... = FIE->Size 99 /// } 100 /// 101 /// Usage (determining the set of stack positions accessed by the target of a 102 /// call: 103 /// 104 /// auto Args = FA.getArgAccessesFor(BC, CallInst); 105 /// if (Args && Args->AssumeEverything) { 106 /// ... callee may access any position of our current stack frame 107 /// } 108 /// 109 class FrameAnalysis { 110 BinaryContext &BC; 111 112 /// Map functions to the set of <stack offsets, size> tuples representing 113 /// accesses to stack positions that belongs to caller 114 std::map<const BinaryFunction *, std::set<std::pair<int64_t, uint8_t>>> 115 ArgsTouchedMap; 116 117 /// The set of functions we were able to perform the full analysis up to 118 /// restoring frame indexes for all load/store instructions. 119 DenseSet<const BinaryFunction *> AnalyzedFunctions; 120 121 /// Set of functions that require the stack to be 16B aligned 122 DenseSet<const BinaryFunction *> FunctionsRequireAlignment; 123 124 /// Set of functions that performs computations with stack addresses and 125 /// complicates our understanding of aliasing of stack spaces. 126 DenseSet<const BinaryFunction *> FunctionsWithStackArithmetic; 127 128 /// Owns ArgAccesses for all instructions. References to elements are 129 /// attached to instructions as indexes to this vector, in MCAnnotations. 130 std::vector<ArgAccesses> ArgAccessesVector; 131 /// Same for FrameIndexEntries. 132 std::vector<FrameIndexEntry> FIEVector; 133 134 /// Analysis stats counters 135 uint64_t NumFunctionsNotOptimized{0}; 136 uint64_t NumFunctionsFailedRestoreFI{0}; 137 uint64_t CountFunctionsFailedRestoreFI{0}; 138 uint64_t CountDenominator{0}; 139 140 /// Convenience functions for appending MCAnnotations to instructions with 141 /// our specific data 142 void addArgAccessesFor(MCInst &Inst, ArgAccesses &&AA); 143 void addArgInStackAccessFor(MCInst &Inst, const ArgInStackAccess &Arg); 144 void addFIEFor(MCInst &Inst, const FrameIndexEntry &FIE); 145 146 /// Perform the step of building the set of registers clobbered by each 147 /// function execution, populating RegsKilledMap and RegsGenMap. 148 void traverseCG(BinaryFunctionCallGraph &CG); 149 150 /// Analyzes an instruction and if it is a call, checks the called function 151 /// to record which args in stack are accessed, if any. Returns true if 152 /// the args data associated with this instruction were updated. 153 bool updateArgsTouchedFor(const BinaryFunction &BF, MCInst &Inst, 154 int CurOffset); 155 156 /// Performs a pass over \p BF to check for accesses to arguments in stack, 157 /// flagging those as accessing the caller stack frame. All functions called 158 /// by \p BF must have been previously analyzed. Returns true if updated 159 /// args data about this function. 160 bool computeArgsAccessed(BinaryFunction &BF); 161 162 /// Alias analysis to disambiguate which frame position is accessed by each 163 /// instruction in function \p BF. Add MCAnnotation<FrameIndexEntry> to 164 /// instructions that access a frame position. Return false if it failed 165 /// to analyze and this information can't be safely determined for \p BF. 166 bool restoreFrameIndex(BinaryFunction &BF); 167 168 /// A store for SPT info per function 169 std::unordered_map<const BinaryFunction *, 170 std::unique_ptr<StackPointerTracking>> 171 SPTMap; 172 173 public: 174 explicit FrameAnalysis(BinaryContext &BC, BinaryFunctionCallGraph &CG); 175 176 /// Return true if we could fully analyze \p Func hasFrameInfo(const BinaryFunction & Func)177 bool hasFrameInfo(const BinaryFunction &Func) const { 178 return AnalyzedFunctions.count(&Func); 179 } 180 181 /// Return true if \p Func cannot operate with a misaligned CFA requiresAlignment(const BinaryFunction & Func)182 bool requiresAlignment(const BinaryFunction &Func) const { 183 return FunctionsRequireAlignment.count(&Func); 184 } 185 186 /// Return true if \p Func does computation with the address of any stack 187 /// position, meaning we have limited alias analysis on this function. hasStackArithmetic(const BinaryFunction & Func)188 bool hasStackArithmetic(const BinaryFunction &Func) const { 189 return FunctionsWithStackArithmetic.count(&Func); 190 } 191 192 /// Functions for retrieving our specific MCAnnotation data from instructions 193 ErrorOr<ArgAccesses &> getArgAccessesFor(const MCInst &Inst); 194 195 ErrorOr<const ArgAccesses &> getArgAccessesFor(const MCInst &Inst) const; 196 197 ErrorOr<const FrameIndexEntry &> getFIEFor(const MCInst &Inst) const; 198 199 /// Remove all MCAnnotations attached by this pass 200 void cleanAnnotations(); 201 ~FrameAnalysis()202 ~FrameAnalysis() { cleanAnnotations(); } 203 204 /// Print to standard output statistics about the analysis performed by this 205 /// pass 206 void printStats(); 207 208 /// Get or create an SPT object and run the analysis getSPT(BinaryFunction & BF)209 StackPointerTracking &getSPT(BinaryFunction &BF) { 210 if (!SPTMap.count(&BF)) { 211 SPTMap.emplace(&BF, std::make_unique<StackPointerTracking>(BF)); 212 auto Iter = SPTMap.find(&BF); 213 assert(Iter != SPTMap.end() && "item should exist"); 214 Iter->second->run(); 215 return *Iter->second; 216 } 217 218 auto Iter = SPTMap.find(&BF); 219 assert(Iter != SPTMap.end() && "item should exist"); 220 return *Iter->second; 221 } 222 223 /// Clean and de-allocate all SPT objects 224 void clearSPTMap(); 225 226 /// Perform SPT analysis for all functions in parallel 227 void preComputeSPT(); 228 }; 229 230 } // namespace bolt 231 } // namespace llvm 232 233 #endif 234