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