1//===-- DWARFExpression.cpp -----------------------------------------------===//
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#include "llvm/DebugInfo/DWARF/DWARFExpression.h"
10#include "llvm/DebugInfo/DWARF/DWARFUnit.h"
11#include "llvm/MC/MCRegisterInfo.h"
12#include "llvm/Support/Format.h"
13#include <cassert>
14#include <cstdint>
15#include <vector>
16
17using namespace llvm;
18using namespace dwarf;
19
20namespace llvm {
21
22typedef std::vector<DWARFExpression::Operation::Description> DescVector;
23
24static DescVector getDescriptions() {
25  DescVector Descriptions;
26  typedef DWARFExpression::Operation Op;
27  typedef Op::Description Desc;
28
29  Descriptions.resize(0xff);
30  Descriptions[DW_OP_addr] = Desc(Op::Dwarf2, Op::SizeAddr);
31  Descriptions[DW_OP_deref] = Desc(Op::Dwarf2);
32  Descriptions[DW_OP_const1u] = Desc(Op::Dwarf2, Op::Size1);
33  Descriptions[DW_OP_const1s] = Desc(Op::Dwarf2, Op::SignedSize1);
34  Descriptions[DW_OP_const2u] = Desc(Op::Dwarf2, Op::Size2);
35  Descriptions[DW_OP_const2s] = Desc(Op::Dwarf2, Op::SignedSize2);
36  Descriptions[DW_OP_const4u] = Desc(Op::Dwarf2, Op::Size4);
37  Descriptions[DW_OP_const4s] = Desc(Op::Dwarf2, Op::SignedSize4);
38  Descriptions[DW_OP_const8u] = Desc(Op::Dwarf2, Op::Size8);
39  Descriptions[DW_OP_const8s] = Desc(Op::Dwarf2, Op::SignedSize8);
40  Descriptions[DW_OP_constu] = Desc(Op::Dwarf2, Op::SizeLEB);
41  Descriptions[DW_OP_consts] = Desc(Op::Dwarf2, Op::SignedSizeLEB);
42  Descriptions[DW_OP_dup] = Desc(Op::Dwarf2);
43  Descriptions[DW_OP_drop] = Desc(Op::Dwarf2);
44  Descriptions[DW_OP_over] = Desc(Op::Dwarf2);
45  Descriptions[DW_OP_pick] = Desc(Op::Dwarf2, Op::Size1);
46  Descriptions[DW_OP_swap] = Desc(Op::Dwarf2);
47  Descriptions[DW_OP_rot] = Desc(Op::Dwarf2);
48  Descriptions[DW_OP_xderef] = Desc(Op::Dwarf2);
49  Descriptions[DW_OP_abs] = Desc(Op::Dwarf2);
50  Descriptions[DW_OP_and] = Desc(Op::Dwarf2);
51  Descriptions[DW_OP_div] = Desc(Op::Dwarf2);
52  Descriptions[DW_OP_minus] = Desc(Op::Dwarf2);
53  Descriptions[DW_OP_mod] = Desc(Op::Dwarf2);
54  Descriptions[DW_OP_mul] = Desc(Op::Dwarf2);
55  Descriptions[DW_OP_neg] = Desc(Op::Dwarf2);
56  Descriptions[DW_OP_not] = Desc(Op::Dwarf2);
57  Descriptions[DW_OP_or] = Desc(Op::Dwarf2);
58  Descriptions[DW_OP_plus] = Desc(Op::Dwarf2);
59  Descriptions[DW_OP_plus_uconst] = Desc(Op::Dwarf2, Op::SizeLEB);
60  Descriptions[DW_OP_shl] = Desc(Op::Dwarf2);
61  Descriptions[DW_OP_shr] = Desc(Op::Dwarf2);
62  Descriptions[DW_OP_shra] = Desc(Op::Dwarf2);
63  Descriptions[DW_OP_xor] = Desc(Op::Dwarf2);
64  Descriptions[DW_OP_skip] = Desc(Op::Dwarf2, Op::SignedSize2);
65  Descriptions[DW_OP_bra] = Desc(Op::Dwarf2, Op::SignedSize2);
66  Descriptions[DW_OP_eq] = Desc(Op::Dwarf2);
67  Descriptions[DW_OP_ge] = Desc(Op::Dwarf2);
68  Descriptions[DW_OP_gt] = Desc(Op::Dwarf2);
69  Descriptions[DW_OP_le] = Desc(Op::Dwarf2);
70  Descriptions[DW_OP_lt] = Desc(Op::Dwarf2);
71  Descriptions[DW_OP_ne] = Desc(Op::Dwarf2);
72  for (uint16_t LA = DW_OP_lit0; LA <= DW_OP_lit31; ++LA)
73    Descriptions[LA] = Desc(Op::Dwarf2);
74  for (uint16_t LA = DW_OP_reg0; LA <= DW_OP_reg31; ++LA)
75    Descriptions[LA] = Desc(Op::Dwarf2);
76  for (uint16_t LA = DW_OP_breg0; LA <= DW_OP_breg31; ++LA)
77    Descriptions[LA] = Desc(Op::Dwarf2, Op::SignedSizeLEB);
78  Descriptions[DW_OP_regx] = Desc(Op::Dwarf2, Op::SizeLEB);
79  Descriptions[DW_OP_fbreg] = Desc(Op::Dwarf2, Op::SignedSizeLEB);
80  Descriptions[DW_OP_bregx] = Desc(Op::Dwarf2, Op::SizeLEB, Op::SignedSizeLEB);
81  Descriptions[DW_OP_piece] = Desc(Op::Dwarf2, Op::SizeLEB);
82  Descriptions[DW_OP_deref_size] = Desc(Op::Dwarf2, Op::Size1);
83  Descriptions[DW_OP_xderef_size] = Desc(Op::Dwarf2, Op::Size1);
84  Descriptions[DW_OP_nop] = Desc(Op::Dwarf2);
85  Descriptions[DW_OP_push_object_address] = Desc(Op::Dwarf3);
86  Descriptions[DW_OP_call2] = Desc(Op::Dwarf3, Op::Size2);
87  Descriptions[DW_OP_call4] = Desc(Op::Dwarf3, Op::Size4);
88  Descriptions[DW_OP_call_ref] = Desc(Op::Dwarf3, Op::SizeRefAddr);
89  Descriptions[DW_OP_form_tls_address] = Desc(Op::Dwarf3);
90  Descriptions[DW_OP_call_frame_cfa] = Desc(Op::Dwarf3);
91  Descriptions[DW_OP_bit_piece] = Desc(Op::Dwarf3, Op::SizeLEB, Op::SizeLEB);
92  Descriptions[DW_OP_implicit_value] =
93      Desc(Op::Dwarf3, Op::SizeLEB, Op::SizeBlock);
94  Descriptions[DW_OP_stack_value] = Desc(Op::Dwarf3);
95  Descriptions[DW_OP_WASM_location] =
96      Desc(Op::Dwarf4, Op::SizeLEB, Op::WasmLocationArg);
97  Descriptions[DW_OP_GNU_push_tls_address] = Desc(Op::Dwarf3);
98  Descriptions[DW_OP_addrx] = Desc(Op::Dwarf4, Op::SizeLEB);
99  Descriptions[DW_OP_GNU_addr_index] = Desc(Op::Dwarf4, Op::SizeLEB);
100  Descriptions[DW_OP_GNU_const_index] = Desc(Op::Dwarf4, Op::SizeLEB);
101  Descriptions[DW_OP_GNU_entry_value] = Desc(Op::Dwarf4, Op::SizeLEB);
102
103  Descriptions[DW_OP_convert] = Desc(Op::Dwarf5, Op::BaseTypeRef);
104  Descriptions[DW_OP_entry_value] = Desc(Op::Dwarf5, Op::SizeLEB);
105  Descriptions[DW_OP_regval_type] =
106      Desc(Op::Dwarf5, Op::SizeLEB, Op::BaseTypeRef);
107
108  return Descriptions;
109}
110
111static DWARFExpression::Operation::Description getOpDesc(unsigned OpCode) {
112  // FIXME: Make this constexpr once all compilers are smart enough to do it.
113  static DescVector Descriptions = getDescriptions();
114  // Handle possible corrupted or unsupported operation.
115  if (OpCode >= Descriptions.size())
116    return {};
117  return Descriptions[OpCode];
118}
119
120bool DWARFExpression::Operation::extract(DataExtractor Data,
121                                         uint8_t AddressSize, uint64_t Offset,
122                                         Optional<DwarfFormat> Format) {
123  EndOffset = Offset;
124  Opcode = Data.getU8(&Offset);
125
126  Desc = getOpDesc(Opcode);
127  if (Desc.Version == Operation::DwarfNA)
128    return false;
129
130  for (unsigned Operand = 0; Operand < 2; ++Operand) {
131    unsigned Size = Desc.Op[Operand];
132    unsigned Signed = Size & Operation::SignBit;
133
134    if (Size == Operation::SizeNA)
135      break;
136
137    switch (Size & ~Operation::SignBit) {
138    case Operation::Size1:
139      Operands[Operand] = Data.getU8(&Offset);
140      if (Signed)
141        Operands[Operand] = (int8_t)Operands[Operand];
142      break;
143    case Operation::Size2:
144      Operands[Operand] = Data.getU16(&Offset);
145      if (Signed)
146        Operands[Operand] = (int16_t)Operands[Operand];
147      break;
148    case Operation::Size4:
149      Operands[Operand] = Data.getU32(&Offset);
150      if (Signed)
151        Operands[Operand] = (int32_t)Operands[Operand];
152      break;
153    case Operation::Size8:
154      Operands[Operand] = Data.getU64(&Offset);
155      break;
156    case Operation::SizeAddr:
157      Operands[Operand] = Data.getUnsigned(&Offset, AddressSize);
158      break;
159    case Operation::SizeRefAddr:
160      if (!Format)
161        return false;
162      Operands[Operand] =
163          Data.getUnsigned(&Offset, dwarf::getDwarfOffsetByteSize(*Format));
164      break;
165    case Operation::SizeLEB:
166      if (Signed)
167        Operands[Operand] = Data.getSLEB128(&Offset);
168      else
169        Operands[Operand] = Data.getULEB128(&Offset);
170      break;
171    case Operation::BaseTypeRef:
172      Operands[Operand] = Data.getULEB128(&Offset);
173      break;
174    case Operation::WasmLocationArg:
175      assert(Operand == 1);
176      switch (Operands[0]) {
177      case 0:
178      case 1:
179      case 2:
180      case 4:
181        Operands[Operand] = Data.getULEB128(&Offset);
182        break;
183      case 3: // global as uint32
184         Operands[Operand] = Data.getU32(&Offset);
185         break;
186      default:
187        return false; // Unknown Wasm location
188      }
189      break;
190    case Operation::SizeBlock:
191      // We need a size, so this cannot be the first operand
192      if (Operand == 0)
193        return false;
194      // Store the offset of the block as the value.
195      Operands[Operand] = Offset;
196      Offset += Operands[Operand - 1];
197      break;
198    default:
199      llvm_unreachable("Unknown DWARFExpression Op size");
200    }
201
202    OperandEndOffsets[Operand] = Offset;
203  }
204
205  EndOffset = Offset;
206  return true;
207}
208
209static void prettyPrintBaseTypeRef(DWARFUnit *U, raw_ostream &OS,
210                                   DIDumpOptions DumpOpts, uint64_t Operands[2],
211                                   unsigned Operand) {
212  assert(Operand < 2 && "operand out of bounds");
213  auto Die = U->getDIEForOffset(U->getOffset() + Operands[Operand]);
214  if (Die && Die.getTag() == dwarf::DW_TAG_base_type) {
215    OS << " (";
216    if (DumpOpts.Verbose)
217      OS << format("0x%08" PRIx64 " -> ", Operands[Operand]);
218    OS << format("0x%08" PRIx64 ")", U->getOffset() + Operands[Operand]);
219    if (auto Name = Die.find(dwarf::DW_AT_name))
220      OS << " \"" << Name->getAsCString() << "\"";
221  } else {
222    OS << format(" <invalid base_type ref: 0x%" PRIx64 ">",
223                 Operands[Operand]);
224  }
225}
226
227static bool prettyPrintRegisterOp(DWARFUnit *U, raw_ostream &OS,
228                                  DIDumpOptions DumpOpts, uint8_t Opcode,
229                                  uint64_t Operands[2],
230                                  const MCRegisterInfo *MRI, bool isEH) {
231  if (!MRI)
232    return false;
233
234  uint64_t DwarfRegNum;
235  unsigned OpNum = 0;
236
237  if (Opcode == DW_OP_bregx || Opcode == DW_OP_regx ||
238      Opcode == DW_OP_regval_type)
239    DwarfRegNum = Operands[OpNum++];
240  else if (Opcode >= DW_OP_breg0 && Opcode < DW_OP_bregx)
241    DwarfRegNum = Opcode - DW_OP_breg0;
242  else
243    DwarfRegNum = Opcode - DW_OP_reg0;
244
245  if (Optional<unsigned> LLVMRegNum = MRI->getLLVMRegNum(DwarfRegNum, isEH)) {
246    if (const char *RegName = MRI->getName(*LLVMRegNum)) {
247      if ((Opcode >= DW_OP_breg0 && Opcode <= DW_OP_breg31) ||
248          Opcode == DW_OP_bregx)
249        OS << format(" %s%+" PRId64, RegName, Operands[OpNum]);
250      else
251        OS << ' ' << RegName;
252
253      if (Opcode == DW_OP_regval_type)
254        prettyPrintBaseTypeRef(U, OS, DumpOpts, Operands, 1);
255      return true;
256    }
257  }
258
259  return false;
260}
261
262bool DWARFExpression::Operation::print(raw_ostream &OS, DIDumpOptions DumpOpts,
263                                       const DWARFExpression *Expr,
264                                       const MCRegisterInfo *RegInfo,
265                                       DWARFUnit *U, bool isEH) {
266  if (Error) {
267    OS << "<decoding error>";
268    return false;
269  }
270
271  StringRef Name = OperationEncodingString(Opcode);
272  assert(!Name.empty() && "DW_OP has no name!");
273  OS << Name;
274
275  if ((Opcode >= DW_OP_breg0 && Opcode <= DW_OP_breg31) ||
276      (Opcode >= DW_OP_reg0 && Opcode <= DW_OP_reg31) ||
277      Opcode == DW_OP_bregx || Opcode == DW_OP_regx ||
278      Opcode == DW_OP_regval_type)
279    if (prettyPrintRegisterOp(U, OS, DumpOpts, Opcode, Operands, RegInfo, isEH))
280      return true;
281
282  for (unsigned Operand = 0; Operand < 2; ++Operand) {
283    unsigned Size = Desc.Op[Operand];
284    unsigned Signed = Size & Operation::SignBit;
285
286    if (Size == Operation::SizeNA)
287      break;
288
289    if (Size == Operation::BaseTypeRef && U) {
290      // For DW_OP_convert the operand may be 0 to indicate that conversion to
291      // the generic type should be done. The same holds for DW_OP_reinterpret,
292      // which is currently not supported.
293      if (Opcode == DW_OP_convert && Operands[Operand] == 0)
294        OS << " 0x0";
295      else
296        prettyPrintBaseTypeRef(U, OS, DumpOpts, Operands, Operand);
297    } else if (Size == Operation::WasmLocationArg) {
298      assert(Operand == 1);
299      switch (Operands[0]) {
300      case 0:
301      case 1:
302      case 2:
303      case 3: // global as uint32
304      case 4:
305        OS << format(" 0x%" PRIx64, Operands[Operand]);
306        break;
307      default: assert(false);
308      }
309    } else if (Size == Operation::SizeBlock) {
310      uint64_t Offset = Operands[Operand];
311      for (unsigned i = 0; i < Operands[Operand - 1]; ++i)
312        OS << format(" 0x%02x", Expr->Data.getU8(&Offset));
313    } else {
314      if (Signed)
315        OS << format(" %+" PRId64, (int64_t)Operands[Operand]);
316      else if (Opcode != DW_OP_entry_value &&
317               Opcode != DW_OP_GNU_entry_value)
318        OS << format(" 0x%" PRIx64, Operands[Operand]);
319    }
320  }
321  return true;
322}
323
324void DWARFExpression::print(raw_ostream &OS, DIDumpOptions DumpOpts,
325                            const MCRegisterInfo *RegInfo, DWARFUnit *U,
326                            bool IsEH) const {
327  uint32_t EntryValExprSize = 0;
328  uint64_t EntryValStartOffset = 0;
329  for (auto &Op : *this) {
330    if (!Op.print(OS, DumpOpts, this, RegInfo, U, IsEH)) {
331      uint64_t FailOffset = Op.getEndOffset();
332      while (FailOffset < Data.getData().size())
333        OS << format(" %02x", Data.getU8(&FailOffset));
334      return;
335    }
336
337    if (Op.getCode() == DW_OP_entry_value ||
338        Op.getCode() == DW_OP_GNU_entry_value) {
339      OS << "(";
340      EntryValExprSize = Op.getRawOperand(0);
341      EntryValStartOffset = Op.getEndOffset();
342      continue;
343    }
344
345    if (EntryValExprSize) {
346      EntryValExprSize -= Op.getEndOffset() - EntryValStartOffset;
347      if (EntryValExprSize == 0)
348        OS << ")";
349    }
350
351    if (Op.getEndOffset() < Data.getData().size())
352      OS << ", ";
353  }
354}
355
356bool DWARFExpression::Operation::verify(DWARFUnit *U) {
357
358  for (unsigned Operand = 0; Operand < 2; ++Operand) {
359    unsigned Size = Desc.Op[Operand];
360
361    if (Size == Operation::SizeNA)
362      break;
363
364    if (Size == Operation::BaseTypeRef) {
365      // For DW_OP_convert the operand may be 0 to indicate that conversion to
366      // the generic type should be done, so don't look up a base type in that
367      // case. The same holds for DW_OP_reinterpret, which is currently not
368      // supported.
369      if (Opcode == DW_OP_convert && Operands[Operand] == 0)
370        continue;
371      auto Die = U->getDIEForOffset(U->getOffset() + Operands[Operand]);
372      if (!Die || Die.getTag() != dwarf::DW_TAG_base_type) {
373        Error = true;
374        return false;
375      }
376    }
377  }
378
379  return true;
380}
381
382bool DWARFExpression::verify(DWARFUnit *U) {
383  for (auto &Op : *this)
384    if (!Op.verify(U))
385      return false;
386
387  return true;
388}
389
390/// A user-facing string representation of a DWARF expression. This might be an
391/// Address expression, in which case it will be implicitly dereferenced, or a
392/// Value expression.
393struct PrintedExpr {
394  enum ExprKind {
395    Address,
396    Value,
397  };
398  ExprKind Kind;
399  SmallString<16> String;
400
401  PrintedExpr(ExprKind K = Address) : Kind(K) {}
402};
403
404static bool printCompactDWARFExpr(raw_ostream &OS, DWARFExpression::iterator I,
405                                  const DWARFExpression::iterator E,
406                                  const MCRegisterInfo &MRI) {
407  SmallVector<PrintedExpr, 4> Stack;
408
409  while (I != E) {
410    DWARFExpression::Operation &Op = *I;
411    uint8_t Opcode = Op.getCode();
412    switch (Opcode) {
413    case dwarf::DW_OP_regx: {
414      // DW_OP_regx: A register, with the register num given as an operand.
415      // Printed as the plain register name.
416      uint64_t DwarfRegNum = Op.getRawOperand(0);
417      Optional<unsigned> LLVMRegNum = MRI.getLLVMRegNum(DwarfRegNum, false);
418      if (!LLVMRegNum) {
419        OS << "<unknown register " << DwarfRegNum << ">";
420        return false;
421      }
422      raw_svector_ostream S(Stack.emplace_back(PrintedExpr::Value).String);
423      S << MRI.getName(*LLVMRegNum);
424      break;
425    }
426    case dwarf::DW_OP_bregx: {
427      int DwarfRegNum = Op.getRawOperand(0);
428      int64_t Offset = Op.getRawOperand(1);
429      Optional<unsigned> LLVMRegNum = MRI.getLLVMRegNum(DwarfRegNum, false);
430      if (!LLVMRegNum) {
431        OS << "<unknown register " << DwarfRegNum << ">";
432        return false;
433      }
434      raw_svector_ostream S(Stack.emplace_back().String);
435      S << MRI.getName(*LLVMRegNum);
436      if (Offset)
437        S << format("%+" PRId64, Offset);
438      break;
439    }
440    case dwarf::DW_OP_entry_value:
441    case dwarf::DW_OP_GNU_entry_value: {
442      // DW_OP_entry_value contains a sub-expression which must be rendered
443      // separately.
444      uint64_t SubExprLength = Op.getRawOperand(0);
445      DWARFExpression::iterator SubExprEnd = I.skipBytes(SubExprLength);
446      ++I;
447      raw_svector_ostream S(Stack.emplace_back().String);
448      S << "entry(";
449      printCompactDWARFExpr(S, I, SubExprEnd, MRI);
450      S << ")";
451      I = SubExprEnd;
452      continue;
453    }
454    case dwarf::DW_OP_stack_value: {
455      // The top stack entry should be treated as the actual value of tne
456      // variable, rather than the address of the variable in memory.
457      assert(!Stack.empty());
458      Stack.back().Kind = PrintedExpr::Value;
459      break;
460    }
461    default:
462      if (Opcode >= dwarf::DW_OP_reg0 && Opcode <= dwarf::DW_OP_reg31) {
463        // DW_OP_reg<N>: A register, with the register num implied by the
464        // opcode. Printed as the plain register name.
465        uint64_t DwarfRegNum = Opcode - dwarf::DW_OP_reg0;
466        Optional<unsigned> LLVMRegNum = MRI.getLLVMRegNum(DwarfRegNum, false);
467        if (!LLVMRegNum) {
468          OS << "<unknown register " << DwarfRegNum << ">";
469          return false;
470        }
471        raw_svector_ostream S(Stack.emplace_back(PrintedExpr::Value).String);
472        S << MRI.getName(*LLVMRegNum);
473      } else if (Opcode >= dwarf::DW_OP_breg0 &&
474                 Opcode <= dwarf::DW_OP_breg31) {
475        int DwarfRegNum = Opcode - dwarf::DW_OP_breg0;
476        int64_t Offset = Op.getRawOperand(0);
477        Optional<unsigned> LLVMRegNum = MRI.getLLVMRegNum(DwarfRegNum, false);
478        if (!LLVMRegNum) {
479          OS << "<unknown register " << DwarfRegNum << ">";
480          return false;
481        }
482        raw_svector_ostream S(Stack.emplace_back().String);
483        S << MRI.getName(*LLVMRegNum);
484        if (Offset)
485          S << format("%+" PRId64, Offset);
486      } else {
487        // If we hit an unknown operand, we don't know its effect on the stack,
488        // so bail out on the whole expression.
489        OS << "<unknown op " << dwarf::OperationEncodingString(Opcode) << " ("
490           << (int)Opcode << ")>";
491        return false;
492      }
493      break;
494    }
495    ++I;
496  }
497
498  assert(Stack.size() == 1 && "expected one value on stack");
499
500  if (Stack.front().Kind == PrintedExpr::Address)
501    OS << "[" << Stack.front().String << "]";
502  else
503    OS << Stack.front().String;
504
505  return true;
506}
507
508bool DWARFExpression::printCompact(raw_ostream &OS, const MCRegisterInfo &MRI) {
509  return printCompactDWARFExpr(OS, begin(), end(), MRI);
510}
511
512bool DWARFExpression::operator==(const DWARFExpression &RHS) const {
513  if (AddressSize != RHS.AddressSize || Format != RHS.Format)
514    return false;
515  return Data.getData() == RHS.Data.getData();
516}
517
518} // namespace llvm
519