lldb/source/Symbol/PostfixExpression.cpp

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