15ffd83dbSDimitry Andric //===-- PostfixExpression.cpp ---------------------------------------------===//
20b57cec5SDimitry Andric //
30b57cec5SDimitry Andric // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
40b57cec5SDimitry Andric // See https://llvm.org/LICENSE.txt for license information.
50b57cec5SDimitry Andric // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
60b57cec5SDimitry Andric //
70b57cec5SDimitry Andric //===----------------------------------------------------------------------===//
80b57cec5SDimitry Andric //
90b57cec5SDimitry Andric // This file implements support for postfix expressions found in several symbol
100b57cec5SDimitry Andric // file formats, and their conversion to DWARF.
110b57cec5SDimitry Andric //
120b57cec5SDimitry Andric //===----------------------------------------------------------------------===//
130b57cec5SDimitry Andric
140b57cec5SDimitry Andric #include "lldb/Symbol/PostfixExpression.h"
150b57cec5SDimitry Andric #include "lldb/Core/dwarf.h"
160b57cec5SDimitry Andric #include "lldb/Utility/Stream.h"
170b57cec5SDimitry Andric #include "llvm/ADT/StringExtras.h"
18bdd1243dSDimitry Andric #include <optional>
190b57cec5SDimitry Andric
200b57cec5SDimitry Andric using namespace lldb_private;
210b57cec5SDimitry Andric using namespace lldb_private::postfix;
2281ad6265SDimitry Andric using namespace lldb_private::dwarf;
230b57cec5SDimitry Andric
24bdd1243dSDimitry Andric static std::optional<BinaryOpNode::OpType>
GetBinaryOpType(llvm::StringRef token)250b57cec5SDimitry Andric GetBinaryOpType(llvm::StringRef token) {
260b57cec5SDimitry Andric if (token.size() != 1)
27bdd1243dSDimitry Andric return std::nullopt;
280b57cec5SDimitry Andric switch (token[0]) {
290b57cec5SDimitry Andric case '@':
300b57cec5SDimitry Andric return BinaryOpNode::Align;
310b57cec5SDimitry Andric case '-':
320b57cec5SDimitry Andric return BinaryOpNode::Minus;
330b57cec5SDimitry Andric case '+':
340b57cec5SDimitry Andric return BinaryOpNode::Plus;
350b57cec5SDimitry Andric }
36bdd1243dSDimitry Andric return std::nullopt;
370b57cec5SDimitry Andric }
380b57cec5SDimitry Andric
39bdd1243dSDimitry Andric static std::optional<UnaryOpNode::OpType>
GetUnaryOpType(llvm::StringRef token)400b57cec5SDimitry Andric GetUnaryOpType(llvm::StringRef token) {
410b57cec5SDimitry Andric if (token == "^")
420b57cec5SDimitry Andric return UnaryOpNode::Deref;
43bdd1243dSDimitry Andric return std::nullopt;
440b57cec5SDimitry Andric }
450b57cec5SDimitry Andric
ParseOneExpression(llvm::StringRef expr,llvm::BumpPtrAllocator & alloc)469dba64beSDimitry Andric Node *postfix::ParseOneExpression(llvm::StringRef expr,
479dba64beSDimitry Andric llvm::BumpPtrAllocator &alloc) {
480b57cec5SDimitry Andric llvm::SmallVector<Node *, 4> stack;
490b57cec5SDimitry Andric
500b57cec5SDimitry Andric llvm::StringRef token;
510b57cec5SDimitry Andric while (std::tie(token, expr) = getToken(expr), !token.empty()) {
520b57cec5SDimitry Andric if (auto op_type = GetBinaryOpType(token)) {
530b57cec5SDimitry Andric // token is binary operator
540b57cec5SDimitry Andric if (stack.size() < 2)
550b57cec5SDimitry Andric return nullptr;
560b57cec5SDimitry Andric
570b57cec5SDimitry Andric Node *right = stack.pop_back_val();
580b57cec5SDimitry Andric Node *left = stack.pop_back_val();
590b57cec5SDimitry Andric stack.push_back(MakeNode<BinaryOpNode>(alloc, *op_type, *left, *right));
600b57cec5SDimitry Andric continue;
610b57cec5SDimitry Andric }
620b57cec5SDimitry Andric
630b57cec5SDimitry Andric if (auto op_type = GetUnaryOpType(token)) {
640b57cec5SDimitry Andric // token is unary operator
650b57cec5SDimitry Andric if (stack.empty())
660b57cec5SDimitry Andric return nullptr;
670b57cec5SDimitry Andric
680b57cec5SDimitry Andric Node *operand = stack.pop_back_val();
690b57cec5SDimitry Andric stack.push_back(MakeNode<UnaryOpNode>(alloc, *op_type, *operand));
700b57cec5SDimitry Andric continue;
710b57cec5SDimitry Andric }
720b57cec5SDimitry Andric
730b57cec5SDimitry Andric int64_t value;
740b57cec5SDimitry Andric if (to_integer(token, value, 10)) {
750b57cec5SDimitry Andric // token is integer literal
760b57cec5SDimitry Andric stack.push_back(MakeNode<IntegerNode>(alloc, value));
770b57cec5SDimitry Andric continue;
780b57cec5SDimitry Andric }
790b57cec5SDimitry Andric
800b57cec5SDimitry Andric stack.push_back(MakeNode<SymbolNode>(alloc, token));
810b57cec5SDimitry Andric }
820b57cec5SDimitry Andric
830b57cec5SDimitry Andric if (stack.size() != 1)
840b57cec5SDimitry Andric return nullptr;
850b57cec5SDimitry Andric
860b57cec5SDimitry Andric return stack.back();
870b57cec5SDimitry Andric }
880b57cec5SDimitry Andric
899dba64beSDimitry Andric std::vector<std::pair<llvm::StringRef, Node *>>
ParseFPOProgram(llvm::StringRef prog,llvm::BumpPtrAllocator & alloc)909dba64beSDimitry Andric postfix::ParseFPOProgram(llvm::StringRef prog, llvm::BumpPtrAllocator &alloc) {
919dba64beSDimitry Andric llvm::SmallVector<llvm::StringRef, 4> exprs;
929dba64beSDimitry Andric prog.split(exprs, '=');
939dba64beSDimitry Andric if (exprs.empty() || !exprs.back().trim().empty())
949dba64beSDimitry Andric return {};
959dba64beSDimitry Andric exprs.pop_back();
969dba64beSDimitry Andric
979dba64beSDimitry Andric std::vector<std::pair<llvm::StringRef, Node *>> result;
989dba64beSDimitry Andric for (llvm::StringRef expr : exprs) {
999dba64beSDimitry Andric llvm::StringRef lhs;
1009dba64beSDimitry Andric std::tie(lhs, expr) = getToken(expr);
1019dba64beSDimitry Andric Node *rhs = ParseOneExpression(expr, alloc);
1029dba64beSDimitry Andric if (!rhs)
1039dba64beSDimitry Andric return {};
1049dba64beSDimitry Andric result.emplace_back(lhs, rhs);
1059dba64beSDimitry Andric }
1069dba64beSDimitry Andric return result;
1079dba64beSDimitry Andric }
1089dba64beSDimitry Andric
1090b57cec5SDimitry Andric namespace {
1100b57cec5SDimitry Andric class SymbolResolver : public Visitor<bool> {
1110b57cec5SDimitry Andric public:
SymbolResolver(llvm::function_ref<Node * (SymbolNode & symbol)> replacer)1120b57cec5SDimitry Andric SymbolResolver(llvm::function_ref<Node *(SymbolNode &symbol)> replacer)
1130b57cec5SDimitry Andric : m_replacer(replacer) {}
1140b57cec5SDimitry Andric
1150b57cec5SDimitry Andric using Visitor<bool>::Dispatch;
1160b57cec5SDimitry Andric
1170b57cec5SDimitry Andric private:
Visit(BinaryOpNode & binary,Node * &)1180b57cec5SDimitry Andric bool Visit(BinaryOpNode &binary, Node *&) override {
1190b57cec5SDimitry Andric return Dispatch(binary.Left()) && Dispatch(binary.Right());
1200b57cec5SDimitry Andric }
1210b57cec5SDimitry Andric
Visit(InitialValueNode &,Node * &)1220b57cec5SDimitry Andric bool Visit(InitialValueNode &, Node *&) override { return true; }
Visit(IntegerNode &,Node * &)1230b57cec5SDimitry Andric bool Visit(IntegerNode &, Node *&) override { return true; }
Visit(RegisterNode &,Node * &)1240b57cec5SDimitry Andric bool Visit(RegisterNode &, Node *&) override { return true; }
1250b57cec5SDimitry Andric
Visit(SymbolNode & symbol,Node * & ref)1260b57cec5SDimitry Andric bool Visit(SymbolNode &symbol, Node *&ref) override {
1270b57cec5SDimitry Andric if (Node *replacement = m_replacer(symbol)) {
1280b57cec5SDimitry Andric ref = replacement;
1290b57cec5SDimitry Andric if (replacement != &symbol)
1300b57cec5SDimitry Andric return Dispatch(ref);
1310b57cec5SDimitry Andric return true;
1320b57cec5SDimitry Andric }
1330b57cec5SDimitry Andric return false;
1340b57cec5SDimitry Andric }
1350b57cec5SDimitry Andric
Visit(UnaryOpNode & unary,Node * &)1360b57cec5SDimitry Andric bool Visit(UnaryOpNode &unary, Node *&) override {
1370b57cec5SDimitry Andric return Dispatch(unary.Operand());
1380b57cec5SDimitry Andric }
1390b57cec5SDimitry Andric
1400b57cec5SDimitry Andric llvm::function_ref<Node *(SymbolNode &symbol)> m_replacer;
1410b57cec5SDimitry Andric };
1420b57cec5SDimitry Andric
1430b57cec5SDimitry Andric class DWARFCodegen : public Visitor<> {
1440b57cec5SDimitry Andric public:
DWARFCodegen(Stream & stream)1450b57cec5SDimitry Andric DWARFCodegen(Stream &stream) : m_out_stream(stream) {}
1460b57cec5SDimitry Andric
1470b57cec5SDimitry Andric using Visitor<>::Dispatch;
1480b57cec5SDimitry Andric
1490b57cec5SDimitry Andric private:
1500b57cec5SDimitry Andric void Visit(BinaryOpNode &binary, Node *&) override;
1510b57cec5SDimitry Andric
1520b57cec5SDimitry Andric void Visit(InitialValueNode &val, Node *&) override;
1530b57cec5SDimitry Andric
Visit(IntegerNode & integer,Node * &)1540b57cec5SDimitry Andric void Visit(IntegerNode &integer, Node *&) override {
1550b57cec5SDimitry Andric m_out_stream.PutHex8(DW_OP_consts);
1560b57cec5SDimitry Andric m_out_stream.PutSLEB128(integer.GetValue());
1570b57cec5SDimitry Andric ++m_stack_depth;
1580b57cec5SDimitry Andric }
1590b57cec5SDimitry Andric
1600b57cec5SDimitry Andric void Visit(RegisterNode ®, Node *&) override;
1610b57cec5SDimitry Andric
Visit(SymbolNode & symbol,Node * &)1620b57cec5SDimitry Andric void Visit(SymbolNode &symbol, Node *&) override {
1630b57cec5SDimitry Andric llvm_unreachable("Symbols should have been resolved by now!");
1640b57cec5SDimitry Andric }
1650b57cec5SDimitry Andric
1660b57cec5SDimitry Andric void Visit(UnaryOpNode &unary, Node *&) override;
1670b57cec5SDimitry Andric
1680b57cec5SDimitry Andric Stream &m_out_stream;
1690b57cec5SDimitry Andric
1700b57cec5SDimitry Andric /// The number keeping track of the evaluation stack depth at any given
1710b57cec5SDimitry Andric /// moment. Used for implementing InitialValueNodes. We start with
1720b57cec5SDimitry Andric /// m_stack_depth = 1, assuming that the initial value is already on the
1730b57cec5SDimitry Andric /// stack. This initial value will be the value of all InitialValueNodes. If
1740b57cec5SDimitry Andric /// the expression does not contain InitialValueNodes, then m_stack_depth is
1750b57cec5SDimitry Andric /// not used, and the generated expression will run correctly even without an
1760b57cec5SDimitry Andric /// initial value.
1770b57cec5SDimitry Andric size_t m_stack_depth = 1;
1780b57cec5SDimitry Andric };
1790b57cec5SDimitry Andric } // namespace
1800b57cec5SDimitry Andric
Visit(BinaryOpNode & binary,Node * &)1810b57cec5SDimitry Andric void DWARFCodegen::Visit(BinaryOpNode &binary, Node *&) {
1820b57cec5SDimitry Andric Dispatch(binary.Left());
1830b57cec5SDimitry Andric Dispatch(binary.Right());
1840b57cec5SDimitry Andric
1850b57cec5SDimitry Andric switch (binary.GetOpType()) {
1860b57cec5SDimitry Andric case BinaryOpNode::Plus:
1870b57cec5SDimitry Andric m_out_stream.PutHex8(DW_OP_plus);
1880b57cec5SDimitry Andric // NOTE: can be optimized by using DW_OP_plus_uconst opcpode
1890b57cec5SDimitry Andric // if right child node is constant value
1900b57cec5SDimitry Andric break;
1910b57cec5SDimitry Andric case BinaryOpNode::Minus:
1920b57cec5SDimitry Andric m_out_stream.PutHex8(DW_OP_minus);
1930b57cec5SDimitry Andric break;
1940b57cec5SDimitry Andric case BinaryOpNode::Align:
1950b57cec5SDimitry Andric // emit align operator a @ b as
1960b57cec5SDimitry Andric // a & ~(b - 1)
1970b57cec5SDimitry Andric // NOTE: implicitly assuming that b is power of 2
1980b57cec5SDimitry Andric m_out_stream.PutHex8(DW_OP_lit1);
1990b57cec5SDimitry Andric m_out_stream.PutHex8(DW_OP_minus);
2000b57cec5SDimitry Andric m_out_stream.PutHex8(DW_OP_not);
2010b57cec5SDimitry Andric
2020b57cec5SDimitry Andric m_out_stream.PutHex8(DW_OP_and);
2030b57cec5SDimitry Andric break;
2040b57cec5SDimitry Andric }
2050b57cec5SDimitry Andric --m_stack_depth; // Two pops, one push.
2060b57cec5SDimitry Andric }
2070b57cec5SDimitry Andric
Visit(InitialValueNode &,Node * &)2080b57cec5SDimitry Andric void DWARFCodegen::Visit(InitialValueNode &, Node *&) {
2090b57cec5SDimitry Andric // We never go below the initial stack, so we can pick the initial value from
2100b57cec5SDimitry Andric // the bottom of the stack at any moment.
2110b57cec5SDimitry Andric assert(m_stack_depth >= 1);
2120b57cec5SDimitry Andric m_out_stream.PutHex8(DW_OP_pick);
2130b57cec5SDimitry Andric m_out_stream.PutHex8(m_stack_depth - 1);
2140b57cec5SDimitry Andric ++m_stack_depth;
2150b57cec5SDimitry Andric }
2160b57cec5SDimitry Andric
Visit(RegisterNode & reg,Node * &)2170b57cec5SDimitry Andric void DWARFCodegen::Visit(RegisterNode ®, Node *&) {
2180b57cec5SDimitry Andric uint32_t reg_num = reg.GetRegNum();
2190b57cec5SDimitry Andric assert(reg_num != LLDB_INVALID_REGNUM);
2200b57cec5SDimitry Andric
2210b57cec5SDimitry Andric if (reg_num > 31) {
2220b57cec5SDimitry Andric m_out_stream.PutHex8(DW_OP_bregx);
2230b57cec5SDimitry Andric m_out_stream.PutULEB128(reg_num);
2240b57cec5SDimitry Andric } else
2250b57cec5SDimitry Andric m_out_stream.PutHex8(DW_OP_breg0 + reg_num);
2260b57cec5SDimitry Andric
2270b57cec5SDimitry Andric m_out_stream.PutSLEB128(0);
2280b57cec5SDimitry Andric ++m_stack_depth;
2290b57cec5SDimitry Andric }
2300b57cec5SDimitry Andric
Visit(UnaryOpNode & unary,Node * &)2310b57cec5SDimitry Andric void DWARFCodegen::Visit(UnaryOpNode &unary, Node *&) {
2320b57cec5SDimitry Andric Dispatch(unary.Operand());
2330b57cec5SDimitry Andric
2340b57cec5SDimitry Andric switch (unary.GetOpType()) {
2350b57cec5SDimitry Andric case UnaryOpNode::Deref:
2360b57cec5SDimitry Andric m_out_stream.PutHex8(DW_OP_deref);
2370b57cec5SDimitry Andric break;
2380b57cec5SDimitry Andric }
2390b57cec5SDimitry Andric // Stack depth unchanged.
2400b57cec5SDimitry Andric }
2410b57cec5SDimitry Andric
ResolveSymbols(Node * & node,llvm::function_ref<Node * (SymbolNode &)> replacer)2420b57cec5SDimitry Andric bool postfix::ResolveSymbols(
2430b57cec5SDimitry Andric Node *&node, llvm::function_ref<Node *(SymbolNode &)> replacer) {
2440b57cec5SDimitry Andric return SymbolResolver(replacer).Dispatch(node);
2450b57cec5SDimitry Andric }
2460b57cec5SDimitry Andric
ToDWARF(Node & node,Stream & stream)2470b57cec5SDimitry Andric void postfix::ToDWARF(Node &node, Stream &stream) {
2480b57cec5SDimitry Andric Node *ptr = &node;
2490b57cec5SDimitry Andric DWARFCodegen(stream).Dispatch(ptr);
2500b57cec5SDimitry Andric }
251