1 //===----------------------------------------------------------------------===// 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 LLVM_DEBUGINFO_DWARF_LOWLEVEL_DWARFUNWINDTABLE_H 10 #define LLVM_DEBUGINFO_DWARF_LOWLEVEL_DWARFUNWINDTABLE_H 11 12 #include "llvm/ADT/SmallVector.h" 13 #include "llvm/DebugInfo/DWARF/LowLevel/DWARFCFIProgram.h" 14 #include "llvm/DebugInfo/DWARF/LowLevel/DWARFExpression.h" 15 #include "llvm/Support/Compiler.h" 16 #include "llvm/Support/Error.h" 17 #include <map> 18 #include <vector> 19 20 namespace llvm { 21 22 namespace dwarf { 23 constexpr uint32_t InvalidRegisterNumber = UINT32_MAX; 24 25 /// A class that represents a location for the Call Frame Address (CFA) or a 26 /// register. This is decoded from the DWARF Call Frame Information 27 /// instructions and put into an UnwindRow. 28 class UnwindLocation { 29 public: 30 enum Location { 31 /// Not specified. 32 Unspecified, 33 /// Register is not available and can't be recovered. 34 Undefined, 35 /// Register value is in the register, nothing needs to be done to unwind 36 /// it: 37 /// reg = reg 38 Same, 39 /// Register is in or at the CFA plus an offset: 40 /// reg = CFA + offset 41 /// reg = defef(CFA + offset) 42 CFAPlusOffset, 43 /// Register or CFA is in or at a register plus offset, optionally in 44 /// an address space: 45 /// reg = reg + offset [in addrspace] 46 /// reg = deref(reg + offset [in addrspace]) 47 RegPlusOffset, 48 /// Register or CFA value is in or at a value found by evaluating a DWARF 49 /// expression: 50 /// reg = eval(dwarf_expr) 51 /// reg = deref(eval(dwarf_expr)) 52 DWARFExpr, 53 /// Value is a constant value contained in "Offset": 54 /// reg = Offset 55 Constant, 56 }; 57 58 private: 59 Location Kind; /// The type of the location that describes how to unwind it. 60 uint32_t RegNum; /// The register number for Kind == RegPlusOffset. 61 int32_t Offset; /// The offset for Kind == CFAPlusOffset or RegPlusOffset. 62 std::optional<uint32_t> AddrSpace; /// The address space for Kind == 63 /// RegPlusOffset for CFA. 64 std::optional<DWARFExpression> Expr; /// The DWARF expression for Kind == 65 /// DWARFExpression. 66 bool Dereference; /// If true, the resulting location must be dereferenced 67 /// after the location value is computed. 68 69 // Constructors are private to force people to use the create static 70 // functions. UnwindLocation(Location K)71 UnwindLocation(Location K) 72 : Kind(K), RegNum(InvalidRegisterNumber), Offset(0), 73 AddrSpace(std::nullopt), Dereference(false) {} 74 UnwindLocation(Location K,uint32_t Reg,int32_t Off,std::optional<uint32_t> AS,bool Deref)75 UnwindLocation(Location K, uint32_t Reg, int32_t Off, 76 std::optional<uint32_t> AS, bool Deref) 77 : Kind(K), RegNum(Reg), Offset(Off), AddrSpace(AS), Dereference(Deref) {} 78 UnwindLocation(DWARFExpression E,bool Deref)79 UnwindLocation(DWARFExpression E, bool Deref) 80 : Kind(DWARFExpr), RegNum(InvalidRegisterNumber), Offset(0), Expr(E), 81 Dereference(Deref) {} 82 83 public: 84 /// Create a location whose rule is set to Unspecified. This means the 85 /// register value might be in the same register but it wasn't specified in 86 /// the unwind opcodes. 87 LLVM_ABI static UnwindLocation createUnspecified(); 88 /// Create a location where the value is undefined and not available. This can 89 /// happen when a register is volatile and can't be recovered. 90 LLVM_ABI static UnwindLocation createUndefined(); 91 /// Create a location where the value is known to be in the register itself. 92 LLVM_ABI static UnwindLocation createSame(); 93 /// Create a location that is in (Deref == false) or at (Deref == true) the 94 /// CFA plus an offset. Most registers that are spilled onto the stack use 95 /// this rule. The rule for the register will use this rule and specify a 96 /// unique offset from the CFA with \a Deref set to true. This value will be 97 /// relative to a CFA value which is typically defined using the register 98 /// plus offset location. \see createRegisterPlusOffset(...) for more 99 /// information. 100 LLVM_ABI static UnwindLocation createIsCFAPlusOffset(int32_t Off); 101 LLVM_ABI static UnwindLocation createAtCFAPlusOffset(int32_t Off); 102 /// Create a location where the saved value is in (Deref == false) or at 103 /// (Deref == true) a regiser plus an offset and, optionally, in the specified 104 /// address space (used mostly for the CFA). 105 /// 106 /// The CFA is usually defined using this rule by using the stack pointer or 107 /// frame pointer as the register, with an offset that accounts for all 108 /// spilled registers and all local variables in a function, and Deref == 109 /// false. 110 LLVM_ABI static UnwindLocation 111 createIsRegisterPlusOffset(uint32_t Reg, int32_t Off, 112 std::optional<uint32_t> AddrSpace = std::nullopt); 113 LLVM_ABI static UnwindLocation 114 createAtRegisterPlusOffset(uint32_t Reg, int32_t Off, 115 std::optional<uint32_t> AddrSpace = std::nullopt); 116 /// Create a location whose value is the result of evaluating a DWARF 117 /// expression. This allows complex expressions to be evaluated in order to 118 /// unwind a register or CFA value. 119 LLVM_ABI static UnwindLocation createIsDWARFExpression(DWARFExpression Expr); 120 LLVM_ABI static UnwindLocation createAtDWARFExpression(DWARFExpression Expr); 121 LLVM_ABI static UnwindLocation createIsConstant(int32_t Value); 122 getLocation()123 Location getLocation() const { return Kind; } getRegister()124 uint32_t getRegister() const { return RegNum; } getOffset()125 int32_t getOffset() const { return Offset; } hasAddressSpace()126 bool hasAddressSpace() const { 127 if (AddrSpace) 128 return true; 129 return false; 130 } getAddressSpace()131 uint32_t getAddressSpace() const { 132 assert(Kind == RegPlusOffset && AddrSpace); 133 return *AddrSpace; 134 } getConstant()135 int32_t getConstant() const { return Offset; } getDereference()136 bool getDereference() const { return Dereference; } 137 138 /// Some opcodes will modify the CFA location's register only, so we need 139 /// to be able to modify the CFA register when evaluating DWARF Call Frame 140 /// Information opcodes. setRegister(uint32_t NewRegNum)141 void setRegister(uint32_t NewRegNum) { RegNum = NewRegNum; } 142 /// Some opcodes will modify the CFA location's offset only, so we need 143 /// to be able to modify the CFA offset when evaluating DWARF Call Frame 144 /// Information opcodes. setOffset(int32_t NewOffset)145 void setOffset(int32_t NewOffset) { Offset = NewOffset; } 146 /// Some opcodes modify a constant value and we need to be able to update 147 /// the constant value (DW_CFA_GNU_window_save which is also known as 148 // DW_CFA_AARCH64_negate_ra_state). setConstant(int32_t Value)149 void setConstant(int32_t Value) { Offset = Value; } 150 getDWARFExpressionBytes()151 std::optional<DWARFExpression> getDWARFExpressionBytes() const { 152 return Expr; 153 } 154 155 LLVM_ABI bool operator==(const UnwindLocation &RHS) const; 156 }; 157 158 /// A class that can track all registers with locations in a UnwindRow object. 159 /// 160 /// Register locations use a map where the key is the register number and the 161 /// the value is a UnwindLocation. 162 /// 163 /// The register maps are put into a class so that all register locations can 164 /// be copied when parsing the unwind opcodes DW_CFA_remember_state and 165 /// DW_CFA_restore_state. 166 class RegisterLocations { 167 std::map<uint32_t, UnwindLocation> Locations; 168 169 public: 170 /// Return the location for the register in \a RegNum if there is a location. 171 /// 172 /// \param RegNum the register number to find a location for. 173 /// 174 /// \returns A location if one is available for \a RegNum, or std::nullopt 175 /// otherwise. getRegisterLocation(uint32_t RegNum)176 std::optional<UnwindLocation> getRegisterLocation(uint32_t RegNum) const { 177 auto Pos = Locations.find(RegNum); 178 if (Pos == Locations.end()) 179 return std::nullopt; 180 return Pos->second; 181 } 182 getRegisters()183 SmallVector<uint32_t, 4> getRegisters() const { 184 SmallVector<uint32_t, 4> Registers; 185 for (auto &&[Register, _] : Locations) 186 Registers.push_back(Register); 187 return Registers; 188 } 189 190 /// Set the location for the register in \a RegNum to \a Location. 191 /// 192 /// \param RegNum the register number to set the location for. 193 /// 194 /// \param Location the UnwindLocation that describes how to unwind the value. setRegisterLocation(uint32_t RegNum,const UnwindLocation & Location)195 void setRegisterLocation(uint32_t RegNum, const UnwindLocation &Location) { 196 Locations.erase(RegNum); 197 Locations.insert(std::make_pair(RegNum, Location)); 198 } 199 200 /// Removes any rule for the register in \a RegNum. 201 /// 202 /// \param RegNum the register number to remove the location for. removeRegisterLocation(uint32_t RegNum)203 void removeRegisterLocation(uint32_t RegNum) { Locations.erase(RegNum); } 204 205 /// Returns true if we have any register locations in this object. hasLocations()206 bool hasLocations() const { return !Locations.empty(); } 207 size()208 size_t size() const { return Locations.size(); } 209 210 bool operator==(const RegisterLocations &RHS) const { 211 return Locations == RHS.Locations; 212 } 213 }; 214 215 /// A class that represents a single row in the unwind table that is decoded by 216 /// parsing the DWARF Call Frame Information opcodes. 217 /// 218 /// The row consists of an optional address, the rule to unwind the CFA and all 219 /// rules to unwind any registers. If the address doesn't have a value, this 220 /// row represents the initial instructions for a CIE. If the address has a 221 /// value the UnwindRow represents a row in the UnwindTable for a FDE. The 222 /// address is the first address for which the CFA location and register rules 223 /// are valid within a function. 224 /// 225 /// UnwindRow objects are created by parsing opcodes in the DWARF Call Frame 226 /// Information and UnwindRow objects are lazily populated and pushed onto a 227 /// stack in the UnwindTable when evaluating this state machine. Accessors are 228 /// needed for the address, CFA value, and register locations as the opcodes 229 /// encode a state machine that produces a sorted array of UnwindRow objects 230 /// \see UnwindTable. 231 class UnwindRow { 232 /// The address will be valid when parsing the instructions in a FDE. If 233 /// invalid, this object represents the initial instructions of a CIE. 234 std::optional<uint64_t> Address; ///< Address for row in FDE, invalid for CIE. 235 UnwindLocation CFAValue; ///< How to unwind the Call Frame Address (CFA). 236 RegisterLocations RegLocs; ///< How to unwind all registers in this list. 237 238 public: UnwindRow()239 UnwindRow() : CFAValue(UnwindLocation::createUnspecified()) {} 240 241 /// Returns true if the address is valid in this object. hasAddress()242 bool hasAddress() const { return Address.has_value(); } 243 244 /// Get the address for this row. 245 /// 246 /// Clients should only call this function after verifying it has a valid 247 /// address with a call to \see hasAddress(). getAddress()248 uint64_t getAddress() const { return *Address; } 249 250 /// Set the address for this UnwindRow. 251 /// 252 /// The address represents the first address for which the CFAValue and 253 /// RegLocs are valid within a function. setAddress(uint64_t Addr)254 void setAddress(uint64_t Addr) { Address = Addr; } 255 256 /// Offset the address for this UnwindRow. 257 /// 258 /// The address represents the first address for which the CFAValue and 259 /// RegLocs are valid within a function. Clients must ensure that this object 260 /// already has an address (\see hasAddress()) prior to calling this 261 /// function. slideAddress(uint64_t Offset)262 void slideAddress(uint64_t Offset) { *Address += Offset; } getCFAValue()263 UnwindLocation &getCFAValue() { return CFAValue; } getCFAValue()264 const UnwindLocation &getCFAValue() const { return CFAValue; } getRegisterLocations()265 RegisterLocations &getRegisterLocations() { return RegLocs; } getRegisterLocations()266 const RegisterLocations &getRegisterLocations() const { return RegLocs; } 267 }; 268 269 /// A class that contains all UnwindRow objects for an FDE or a single unwind 270 /// row for a CIE. To unwind an address the rows, which are sorted by start 271 /// address, can be searched to find the UnwindRow with the lowest starting 272 /// address that is greater than or equal to the address that is being looked 273 /// up. 274 class UnwindTable { 275 public: 276 using RowContainer = std::vector<UnwindRow>; 277 using iterator = RowContainer::iterator; 278 using const_iterator = RowContainer::const_iterator; 279 UnwindTable(RowContainer && Rows)280 UnwindTable(RowContainer &&Rows) : Rows(std::move(Rows)) {} 281 size()282 size_t size() const { return Rows.size(); } begin()283 iterator begin() { return Rows.begin(); } begin()284 const_iterator begin() const { return Rows.begin(); } end()285 iterator end() { return Rows.end(); } end()286 const_iterator end() const { return Rows.end(); } 287 const UnwindRow &operator[](size_t Index) const { 288 assert(Index < size()); 289 return Rows[Index]; 290 } 291 292 private: 293 RowContainer Rows; 294 }; 295 296 /// Parse the information in the CFIProgram and update the CurrRow object 297 /// that the state machine describes. 298 /// 299 /// This function emulates the state machine described in the DWARF Call Frame 300 /// Information opcodes and will push CurrRow onto a RowContainer when needed. 301 /// 302 /// \param CFIP the CFI program that contains the opcodes from a CIE or FDE. 303 /// 304 /// \param CurrRow the current row to modify while parsing the state machine. 305 /// 306 /// \param InitialLocs If non-NULL, we are parsing a FDE and this contains 307 /// the initial register locations from the CIE. If NULL, then a CIE's 308 /// opcodes are being parsed and this is not needed. This is used for the 309 /// DW_CFA_restore and DW_CFA_restore_extended opcodes. 310 /// 311 /// \returns An error if the DWARF Call Frame Information opcodes have state 312 /// machine errors, or the accumulated rows otherwise. 313 LLVM_ABI Expected<UnwindTable::RowContainer> 314 parseRows(const CFIProgram &CFIP, UnwindRow &CurrRow, 315 const RegisterLocations *InitialLocs); 316 317 } // end namespace dwarf 318 319 } // end namespace llvm 320 321 #endif // LLVM_DEBUGINFO_DWARF_LOWLEVEL_DWARFUNWINDTABLE_H 322