251 lines · 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-exception6//7//===----------------------------------------------------------------------===//8//9// This file implements support for postfix expressions found in several symbol10// 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 20using namespace lldb_private;21using namespace lldb_private::postfix;22using namespace llvm::dwarf;23 24static std::optional<BinaryOpNode::OpType>25GetBinaryOpType(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 39static std::optional<UnaryOpNode::OpType>40GetUnaryOpType(llvm::StringRef token) {41 if (token == "^")42 return UnaryOpNode::Deref;43 return std::nullopt;44}45 46Node *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 operator54 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 operator65 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 literal76 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 89std::vector<std::pair<llvm::StringRef, Node *>>90postfix::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 109namespace {110class SymbolResolver : public Visitor<bool> {111public:112 SymbolResolver(llvm::function_ref<Node *(SymbolNode &symbol)> replacer)113 : m_replacer(replacer) {}114 115 using Visitor<bool>::Dispatch;116 117private: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 143class DWARFCodegen : public Visitor<> {144public:145 DWARFCodegen(Stream &stream) : m_out_stream(stream) {}146 147 using Visitor<>::Dispatch;148 149private: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 ®, 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 given171 /// moment. Used for implementing InitialValueNodes. We start with172 /// m_stack_depth = 1, assuming that the initial value is already on the173 /// stack. This initial value will be the value of all InitialValueNodes. If174 /// the expression does not contain InitialValueNodes, then m_stack_depth is175 /// not used, and the generated expression will run correctly even without an176 /// initial value.177 size_t m_stack_depth = 1;178};179} // namespace180 181void 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 opcpode189 // if right child node is constant value190 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 as196 // a & ~(b - 1)197 // NOTE: implicitly assuming that b is power of 2198 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 208void DWARFCodegen::Visit(InitialValueNode &, Node *&) {209 // We never go below the initial stack, so we can pick the initial value from210 // 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 217void DWARFCodegen::Visit(RegisterNode ®, 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 } else225 m_out_stream.PutHex8(DW_OP_breg0 + reg_num);226 227 m_out_stream.PutSLEB128(0);228 ++m_stack_depth;229}230 231void 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 242bool postfix::ResolveSymbols(243 Node *&node, llvm::function_ref<Node *(SymbolNode &)> replacer) {244 return SymbolResolver(replacer).Dispatch(node);245}246 247void postfix::ToDWARF(Node &node, Stream &stream) {248 Node *ptr = &node;249 DWARFCodegen(stream).Dispatch(ptr);250}251