contrib/llvm-project/lldb/source/Symbol/PostfixExpression.cpp

   1 //===-- PostfixExpression.cpp -----------------------------------*- 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 //  This file implements support for postfix expressions found in several symbol
  10 //  file formats, and their conversion to DWARF.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "lldb/Symbol/PostfixExpression.h"
  15 #include "lldb/Core/dwarf.h"
  16 #include "lldb/Utility/Stream.h"
  17 #include "llvm/ADT/StringExtras.h"
  18
  19 using namespace lldb_private;
  20 using namespace lldb_private::postfix;
  21
  22 static llvm::Optional<BinaryOpNode::OpType>
  23 GetBinaryOpType(llvm::StringRef token) {
  24   if (token.size() != 1)
  25     return llvm::None;
  26   switch (token[0]) {
  27   case '@':
  28     return BinaryOpNode::Align;
  29   case '-':
  30     return BinaryOpNode::Minus;
  31   case '+':
  32     return BinaryOpNode::Plus;
  33   }
  34   return llvm::None;
  35 }
  36
  37 static llvm::Optional<UnaryOpNode::OpType>
  38 GetUnaryOpType(llvm::StringRef token) {
  39   if (token == "^")
  40     return UnaryOpNode::Deref;
  41   return llvm::None;
  42 }
  43
  44 Node *postfix::Parse(llvm::StringRef expr, llvm::BumpPtrAllocator &alloc) {
  45   llvm::SmallVector<Node *, 4> stack;
  46
  47   llvm::StringRef token;
  48   while (std::tie(token, expr) = getToken(expr), !token.empty()) {
  49     if (auto op_type = GetBinaryOpType(token)) {
  50       // token is binary operator
  51       if (stack.size() < 2)
  52         return nullptr;
  53
  54       Node *right = stack.pop_back_val();
  55       Node *left = stack.pop_back_val();
  56       stack.push_back(MakeNode<BinaryOpNode>(alloc, *op_type, *left, *right));
  57       continue;
  58     }
  59
  60     if (auto op_type = GetUnaryOpType(token)) {
  61       // token is unary operator
  62       if (stack.empty())
  63         return nullptr;
  64
  65       Node *operand = stack.pop_back_val();
  66       stack.push_back(MakeNode<UnaryOpNode>(alloc, *op_type, *operand));
  67       continue;
  68     }
  69
  70     int64_t value;
  71     if (to_integer(token, value, 10)) {
  72       // token is integer literal
  73       stack.push_back(MakeNode<IntegerNode>(alloc, value));
  74       continue;
  75     }
  76
  77     stack.push_back(MakeNode<SymbolNode>(alloc, token));
  78   }
  79
  80   if (stack.size() != 1)
  81     return nullptr;
  82
  83   return stack.back();
  84 }
  85
  86 namespace {
  87 class SymbolResolver : public Visitor<bool> {
  88 public:
  89   SymbolResolver(llvm::function_ref<Node *(SymbolNode &symbol)> replacer)
  90       : m_replacer(replacer) {}
  91
  92   using Visitor<bool>::Dispatch;
  93
  94 private:
  95   bool Visit(BinaryOpNode &binary, Node *&) override {
  96     return Dispatch(binary.Left()) && Dispatch(binary.Right());
  97   }
  98
  99   bool Visit(InitialValueNode &, Node *&) override { return true; }
 100   bool Visit(IntegerNode &, Node *&) override { return true; }
 101   bool Visit(RegisterNode &, Node *&) override { return true; }
 102
 103   bool Visit(SymbolNode &symbol, Node *&ref) override {
 104     if (Node *replacement = m_replacer(symbol)) {
 105       ref = replacement;
 106       if (replacement != &symbol)
 107         return Dispatch(ref);
 108       return true;
 109     }
 110     return false;
 111   }
 112
 113   bool Visit(UnaryOpNode &unary, Node *&) override {
 114     return Dispatch(unary.Operand());
 115   }
 116
 117   llvm::function_ref<Node *(SymbolNode &symbol)> m_replacer;
 118 };
 119
 120 class DWARFCodegen : public Visitor<> {
 121 public:
 122   DWARFCodegen(Stream &stream) : m_out_stream(stream) {}
 123
 124   using Visitor<>::Dispatch;
 125
 126 private:
 127   void Visit(BinaryOpNode &binary, Node *&) override;
 128
 129   void Visit(InitialValueNode &val, Node *&) override;
 130
 131   void Visit(IntegerNode &integer, Node *&) override {
 132     m_out_stream.PutHex8(DW_OP_consts);
 133     m_out_stream.PutSLEB128(integer.GetValue());
 134     ++m_stack_depth;
 135   }
 136
 137   void Visit(RegisterNode &reg, Node *&) override;
 138
 139   void Visit(SymbolNode &symbol, Node *&) override {
 140     llvm_unreachable("Symbols should have been resolved by now!");
 141   }
 142
 143   void Visit(UnaryOpNode &unary, Node *&) override;
 144
 145   Stream &m_out_stream;
 146
 147   /// The number keeping track of the evaluation stack depth at any given
 148   /// moment. Used for implementing InitialValueNodes. We start with
 149   /// m_stack_depth = 1, assuming that the initial value is already on the
 150   /// stack. This initial value will be the value of all InitialValueNodes. If
 151   /// the expression does not contain InitialValueNodes, then m_stack_depth is
 152   /// not used, and the generated expression will run correctly even without an
 153   /// initial value.
 154   size_t m_stack_depth = 1;
 155 };
 156 } // namespace
 157
 158 void DWARFCodegen::Visit(BinaryOpNode &binary, Node *&) {
 159   Dispatch(binary.Left());
 160   Dispatch(binary.Right());
 161
 162   switch (binary.GetOpType()) {
 163   case BinaryOpNode::Plus:
 164     m_out_stream.PutHex8(DW_OP_plus);
 165     // NOTE: can be optimized by using DW_OP_plus_uconst opcpode
 166     //       if right child node is constant value
 167     break;
 168   case BinaryOpNode::Minus:
 169     m_out_stream.PutHex8(DW_OP_minus);
 170     break;
 171   case BinaryOpNode::Align:
 172     // emit align operator a @ b as
 173     // a & ~(b - 1)
 174     // NOTE: implicitly assuming that b is power of 2
 175     m_out_stream.PutHex8(DW_OP_lit1);
 176     m_out_stream.PutHex8(DW_OP_minus);
 177     m_out_stream.PutHex8(DW_OP_not);
 178
 179     m_out_stream.PutHex8(DW_OP_and);
 180     break;
 181   }
 182   --m_stack_depth; // Two pops, one push.
 183 }
 184
 185 void DWARFCodegen::Visit(InitialValueNode &, Node *&) {
 186   // We never go below the initial stack, so we can pick the initial value from
 187   // the bottom of the stack at any moment.
 188   assert(m_stack_depth >= 1);
 189   m_out_stream.PutHex8(DW_OP_pick);
 190   m_out_stream.PutHex8(m_stack_depth - 1);
 191   ++m_stack_depth;
 192 }
 193
 194 void DWARFCodegen::Visit(RegisterNode &reg, Node *&) {
 195   uint32_t reg_num = reg.GetRegNum();
 196   assert(reg_num != LLDB_INVALID_REGNUM);
 197
 198   if (reg_num > 31) {
 199     m_out_stream.PutHex8(DW_OP_bregx);
 200     m_out_stream.PutULEB128(reg_num);
 201   } else
 202     m_out_stream.PutHex8(DW_OP_breg0 + reg_num);
 203
 204   m_out_stream.PutSLEB128(0);
 205   ++m_stack_depth;
 206 }
 207
 208 void DWARFCodegen::Visit(UnaryOpNode &unary, Node *&) {
 209   Dispatch(unary.Operand());
 210
 211   switch (unary.GetOpType()) {
 212   case UnaryOpNode::Deref:
 213     m_out_stream.PutHex8(DW_OP_deref);
 214     break;
 215   }
 216   // Stack depth unchanged.
 217 }
 218
 219 bool postfix::ResolveSymbols(
 220     Node *&node, llvm::function_ref<Node *(SymbolNode &)> replacer) {
 221   return SymbolResolver(replacer).Dispatch(node);
 222 }
 223
 224 void postfix::ToDWARF(Node &node, Stream &stream) {
 225   Node *ptr = &node;
 226   DWARFCodegen(stream).Dispatch(ptr);
 227 }