Index: include/lldb/Symbol/PostfixExpression.h =================================================================== --- /dev/null +++ include/lldb/Symbol/PostfixExpression.h @@ -0,0 +1,177 @@ +//===-- PostfixExpression.h -------------------------------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// This file implements support for postfix expressions found in several symbol +// file formats, and their conversion to DWARF. +// +//===----------------------------------------------------------------------===// + +#ifndef LLDB_SYMBOL_POSTFIXEXPRESSION_H +#define LLDB_SYMBOL_POSTFIXEXPRESSION_H + +#include "llvm/ADT/StringRef.h" +#include "llvm/Support/Casting.h" + +namespace lldb_private { +namespace postfix { + +/// The base class for all nodes in the parsed postfix tree. +class Node { +public: + enum Kind { + BinaryOp, + Integer, + Register, + Symbol, + UnaryOp, + }; + +protected: + Node(Kind kind) : m_kind(kind) {} + +public: + Kind GetKind() const { return m_kind; } + +private: + Kind m_kind; +}; + +/// A node representing a binary expression. +class BinaryOpNode : public Node { +public: + enum OpType { + Align, // alignDown(a, b) + Minus, // a - b + Plus, // a + b + }; + + BinaryOpNode(OpType op_type, Node &left, Node &right) + : Node(BinaryOp), m_op_type(op_type), m_left(&left), m_right(&right) {} + + OpType GetOpType() const { return m_op_type; } + + const Node *Left() const { return m_left; } + Node *&Left() { return m_left; } + + const Node *Right() const { return m_right; } + Node *&Right() { return m_right; } + + static bool classof(const Node *node) { return node->GetKind() == BinaryOp; } + +private: + OpType m_op_type; + Node *m_left; + Node *m_right; +}; + +/// A node representing an integer literal. +class IntegerNode : public Node { +public: + IntegerNode(uint32_t value) : Node(Integer), m_value(value) {} + + uint32_t GetValue() const { return m_value; } + + static bool classof(const Node *node) { return node->GetKind() == Integer; } + +private: + uint32_t m_value; +}; + +/// A node representing the value of a register with the given register number. +/// The register kind (RegisterKind enum) used for the specifying the register +/// number is implicit and assumed to be the same for all Register nodes in a +/// given tree. +class RegisterNode : public Node { +public: + RegisterNode(uint32_t reg_num) : Node(Register), m_reg_num(reg_num) {} + + uint32_t GetRegNum() const { return m_reg_num; } + + static bool classof(const Node *node) { return node->GetKind() == Register; } + +private: + uint32_t m_reg_num; +}; + +/// A node representing a symbolic reference to a named entity. This may be a +/// register, which hasn't yet been resolved to a RegisterNode. +class SymbolNode : public Node { +public: + SymbolNode(llvm::StringRef name) : Node(Symbol), m_name(name) {} + + llvm::StringRef GetName() const { return m_name; } + + static bool classof(const Node *node) { return node->GetKind() == Symbol; } + +private: + llvm::StringRef m_name; +}; + +/// A node representing a unary operation. +class UnaryOpNode : public Node { +public: + enum OpType { + Deref, // *a + }; + + UnaryOpNode(OpType op_type, Node &operand) + : Node(UnaryOp), m_op_type(op_type), m_operand(&operand) {} + + OpType GetOpType() const { return m_op_type; } + + const Node *Operand() const { return m_operand; } + Node *&Operand() { return m_operand; } + + static bool classof(const Node *node) { return node->GetKind() == UnaryOp; } + +private: + OpType m_op_type; + Node *m_operand; +}; + +/// A template class implementing a visitor pattern, but with a couple of +/// twists: +/// - It uses type switch instead of virtual double dispatch. This allows the +// node classes to be vtable-free and trivially destructible. +/// - The Visit functions get an extra Node *& parameter, which refers to the +/// child pointer of the parent of the node we are currently visiting. This +/// allows mutating algorithms, which replace the currently visited node with +/// a different one. +/// - The class is templatized on the return type of the Visit functions, which +/// means it's possible to return values from them. +template class Visitor { +protected: + virtual ResultT Visit(BinaryOpNode &binary, Node *&ref) = 0; + virtual ResultT Visit(IntegerNode &integer, Node *&) = 0; + virtual ResultT Visit(RegisterNode ®, Node *&) = 0; + virtual ResultT Visit(SymbolNode &symbol, Node *&ref) = 0; + virtual ResultT Visit(UnaryOpNode &unary, Node *&ref) = 0; + + /// Invoke the correct Visit function based on the dynamic type of the given + /// node. + ResultT Dispatch(Node *&node) { + switch (node->GetKind()) { + case Node::BinaryOp: + return Visit(llvm::cast(*node), node); + case Node::Integer: + return Visit(llvm::cast(*node), node); + case Node::Register: + return Visit(llvm::cast(*node), node); + case Node::Symbol: + return Visit(llvm::cast(*node), node); + case Node::UnaryOp: + return Visit(llvm::cast(*node), node); + } + llvm_unreachable("Fully covered switch!"); + } +}; + +} // namespace postfix +} // namespace lldb_private + +#endif // LLDB_SYMBOL_POSTFIXEXPRESSION_H Index: source/Plugins/SymbolFile/NativePDB/PdbFPOProgramToDWARFExpression.cpp =================================================================== --- source/Plugins/SymbolFile/NativePDB/PdbFPOProgramToDWARFExpression.cpp +++ source/Plugins/SymbolFile/NativePDB/PdbFPOProgramToDWARFExpression.cpp @@ -11,6 +11,7 @@ #include "lldb/Core/StreamBuffer.h" #include "lldb/Core/dwarf.h" +#include "lldb/Symbol/PostfixExpression.h" #include "lldb/Utility/LLDBAssert.h" #include "lldb/Utility/Stream.h" #include "llvm/ADT/DenseMap.h" @@ -18,10 +19,10 @@ #include "llvm/ADT/StringExtras.h" #include "llvm/DebugInfo/CodeView/CodeView.h" #include "llvm/DebugInfo/CodeView/EnumTables.h" -#include "llvm/Support/Casting.h" using namespace lldb; using namespace lldb_private; +using namespace lldb_private::postfix; namespace { @@ -38,188 +39,36 @@ llvm::BumpPtrAllocator m_alloc; }; -class FPOProgramNode { +class FPOProgramASTVisitorMergeDependent : public Visitor<> { public: - enum Kind { - Symbol, - Register, - IntegerLiteral, - BinaryOp, - UnaryOp, - }; - -protected: - FPOProgramNode(Kind kind) : m_token_kind(kind) {} - -public: - Kind GetKind() const { return m_token_kind; } - -private: - Kind m_token_kind; -}; - -class FPOProgramNodeSymbol: public FPOProgramNode { -public: - FPOProgramNodeSymbol(llvm::StringRef name) - : FPOProgramNode(Symbol), m_name(name) {} - - llvm::StringRef GetName() const { return m_name; } - - static bool classof(const FPOProgramNode *node) { - return node->GetKind() == Symbol; - } - -private: - llvm::StringRef m_name; -}; - -class FPOProgramNodeRegisterRef : public FPOProgramNode { -public: - FPOProgramNodeRegisterRef(uint32_t lldb_reg_num) - : FPOProgramNode(Register), m_lldb_reg_num(lldb_reg_num) {} - - uint32_t GetLLDBRegNum() const { return m_lldb_reg_num; } - - static bool classof(const FPOProgramNode *node) { - return node->GetKind() == Register; - } - -private: - uint32_t m_lldb_reg_num; -}; - -class FPOProgramNodeIntegerLiteral : public FPOProgramNode { -public: - FPOProgramNodeIntegerLiteral(uint32_t value) - : FPOProgramNode(IntegerLiteral), m_value(value) {} - - uint32_t GetValue() const { return m_value; } - - static bool classof(const FPOProgramNode *node) { - return node->GetKind() == IntegerLiteral; - } - -private: - uint32_t m_value; -}; - -class FPOProgramNodeBinaryOp : public FPOProgramNode { -public: - enum OpType { - Plus, - Minus, - Align, - }; - - FPOProgramNodeBinaryOp(OpType op_type, FPOProgramNode &left, - FPOProgramNode &right) - : FPOProgramNode(BinaryOp), m_op_type(op_type), m_left(&left), - m_right(&right) {} - - OpType GetOpType() const { return m_op_type; } - - const FPOProgramNode *Left() const { return m_left; } - FPOProgramNode *&Left() { return m_left; } - - const FPOProgramNode *Right() const { return m_right; } - FPOProgramNode *&Right() { return m_right; } - - static bool classof(const FPOProgramNode *node) { - return node->GetKind() == BinaryOp; - } - -private: - OpType m_op_type; - FPOProgramNode *m_left; - FPOProgramNode *m_right; -}; - -class FPOProgramNodeUnaryOp : public FPOProgramNode { -public: - enum OpType { - Deref, - }; - - FPOProgramNodeUnaryOp(OpType op_type, FPOProgramNode &operand) - : FPOProgramNode(UnaryOp), m_op_type(op_type), m_operand(&operand) {} - - OpType GetOpType() const { return m_op_type; } - - const FPOProgramNode *Operand() const { return m_operand; } - FPOProgramNode *&Operand() { return m_operand; } - - static bool classof(const FPOProgramNode *node) { - return node->GetKind() == UnaryOp; - } - -private: - OpType m_op_type; - FPOProgramNode *m_operand; -}; - -template -class FPOProgramASTVisitor { -protected: - virtual ResultT Visit(FPOProgramNodeBinaryOp &binary, - FPOProgramNode *&ref) = 0; - virtual ResultT Visit(FPOProgramNodeUnaryOp &unary, FPOProgramNode *&ref) = 0; - virtual ResultT Visit(FPOProgramNodeRegisterRef ®, FPOProgramNode *&) = 0; - virtual ResultT Visit(FPOProgramNodeIntegerLiteral &integer, - FPOProgramNode *&) = 0; - virtual ResultT Visit(FPOProgramNodeSymbol &symbol, FPOProgramNode *&ref) = 0; - - ResultT Dispatch(FPOProgramNode *&node) { - switch (node->GetKind()) { - case FPOProgramNode::Register: - return Visit(llvm::cast(*node), node); - case FPOProgramNode::Symbol: - return Visit(llvm::cast(*node), node); - - case FPOProgramNode::IntegerLiteral: - return Visit(llvm::cast(*node), node); - case FPOProgramNode::UnaryOp: - return Visit(llvm::cast(*node), node); - case FPOProgramNode::BinaryOp: - return Visit(llvm::cast(*node), node); - } - llvm_unreachable("Fully covered switch!"); - } - -}; - -class FPOProgramASTVisitorMergeDependent : public FPOProgramASTVisitor<> { -public: - void Visit(FPOProgramNodeBinaryOp &binary, FPOProgramNode *&) override { + void Visit(BinaryOpNode &binary, Node *&) override { Dispatch(binary.Left()); Dispatch(binary.Right()); } - void Visit(FPOProgramNodeUnaryOp &unary, FPOProgramNode *&) override { + void Visit(UnaryOpNode &unary, Node *&) override { Dispatch(unary.Operand()); } - void Visit(FPOProgramNodeRegisterRef &, FPOProgramNode *&) override {} - void Visit(FPOProgramNodeIntegerLiteral &, FPOProgramNode *&) override {} - void Visit(FPOProgramNodeSymbol &symbol, FPOProgramNode *&ref) override; + void Visit(RegisterNode &, Node *&) override {} + void Visit(IntegerNode &, Node *&) override {} + void Visit(SymbolNode &symbol, Node *&ref) override; - static void Merge(const llvm::DenseMap - &dependent_programs, - FPOProgramNode *&ast) { + static void + Merge(const llvm::DenseMap &dependent_programs, + Node *&ast) { FPOProgramASTVisitorMergeDependent(dependent_programs).Dispatch(ast); } private: FPOProgramASTVisitorMergeDependent( - const llvm::DenseMap - &dependent_programs) + const llvm::DenseMap &dependent_programs) : m_dependent_programs(dependent_programs) {} - const llvm::DenseMap &m_dependent_programs; + const llvm::DenseMap &m_dependent_programs; }; -void FPOProgramASTVisitorMergeDependent::Visit(FPOProgramNodeSymbol &symbol, - FPOProgramNode *&ref) { - +void FPOProgramASTVisitorMergeDependent::Visit(SymbolNode &symbol, Node *&ref) { auto it = m_dependent_programs.find(symbol.GetName()); if (it == m_dependent_programs.end()) return; @@ -228,45 +77,38 @@ Dispatch(ref); } -class FPOProgramASTVisitorResolveRegisterRefs - : public FPOProgramASTVisitor { +class FPOProgramASTVisitorResolveRegisterRefs : public Visitor { public: - static bool Resolve(const llvm::DenseMap - &dependent_programs, - llvm::Triple::ArchType arch_type, NodeAllocator &alloc, - FPOProgramNode *&ast) { + static bool + Resolve(const llvm::DenseMap &dependent_programs, + llvm::Triple::ArchType arch_type, NodeAllocator &alloc, Node *&ast) { return FPOProgramASTVisitorResolveRegisterRefs(dependent_programs, arch_type, alloc) .Dispatch(ast); } - bool Visit(FPOProgramNodeBinaryOp &binary, FPOProgramNode *&) override { + bool Visit(BinaryOpNode &binary, Node *&) override { return Dispatch(binary.Left()) && Dispatch(binary.Right()); } - bool Visit(FPOProgramNodeUnaryOp &unary, FPOProgramNode *&) override { + bool Visit(UnaryOpNode &unary, Node *&) override { return Dispatch(unary.Operand()); } - bool Visit(FPOProgramNodeRegisterRef &, FPOProgramNode *&) override { - return true; - } + bool Visit(RegisterNode &, Node *&) override { return true; } - bool Visit(FPOProgramNodeIntegerLiteral &, FPOProgramNode *&) override { - return true; - } + bool Visit(IntegerNode &, Node *&) override { return true; } - bool Visit(FPOProgramNodeSymbol &symbol, FPOProgramNode *&ref) override; + bool Visit(SymbolNode &symbol, Node *&ref) override; private: FPOProgramASTVisitorResolveRegisterRefs( - const llvm::DenseMap - &dependent_programs, + const llvm::DenseMap &dependent_programs, llvm::Triple::ArchType arch_type, NodeAllocator &alloc) : m_dependent_programs(dependent_programs), m_arch_type(arch_type), m_alloc(alloc) {} - const llvm::DenseMap &m_dependent_programs; + const llvm::DenseMap &m_dependent_programs; llvm::Triple::ArchType m_arch_type; NodeAllocator &m_alloc; }; @@ -288,8 +130,8 @@ return npdb::GetLLDBRegisterNumber(arch_type, reg_id); } -bool FPOProgramASTVisitorResolveRegisterRefs::Visit( - FPOProgramNodeSymbol &symbol, FPOProgramNode *&ref) { +bool FPOProgramASTVisitorResolveRegisterRefs::Visit(SymbolNode &symbol, + Node *&ref) { // Look up register reference as lvalue in preceding assignments. auto it = m_dependent_programs.find(symbol.GetName()); if (it != m_dependent_programs.end()) { @@ -303,23 +145,23 @@ if (reg_num == LLDB_INVALID_REGNUM) return false; - ref = m_alloc.makeNode(reg_num); + ref = m_alloc.makeNode(reg_num); return true; } -class FPOProgramASTVisitorDWARFCodegen : public FPOProgramASTVisitor<> { +class FPOProgramASTVisitorDWARFCodegen : public Visitor<> { public: - static void Emit(Stream &stream, FPOProgramNode *&ast) { + static void Emit(Stream &stream, Node *&ast) { FPOProgramASTVisitorDWARFCodegen(stream).Dispatch(ast); } - void Visit(FPOProgramNodeRegisterRef ®, FPOProgramNode *&); - void Visit(FPOProgramNodeBinaryOp &binary, FPOProgramNode *&); - void Visit(FPOProgramNodeUnaryOp &unary, FPOProgramNode *&); - void Visit(FPOProgramNodeSymbol &symbol, FPOProgramNode *&) { + void Visit(RegisterNode ®, Node *&); + void Visit(BinaryOpNode &binary, Node *&); + void Visit(UnaryOpNode &unary, Node *&); + void Visit(SymbolNode &symbol, Node *&) { llvm_unreachable("Symbols should have been resolved by now!"); } - void Visit(FPOProgramNodeIntegerLiteral &integer, FPOProgramNode *&); + void Visit(IntegerNode &integer, Node *&); private: FPOProgramASTVisitorDWARFCodegen(Stream &stream) : m_out_stream(stream) {} @@ -327,10 +169,8 @@ Stream &m_out_stream; }; -void FPOProgramASTVisitorDWARFCodegen::Visit(FPOProgramNodeRegisterRef ®, - FPOProgramNode *&) { - - uint32_t reg_num = reg.GetLLDBRegNum(); +void FPOProgramASTVisitorDWARFCodegen::Visit(RegisterNode ®, Node *&) { + uint32_t reg_num = reg.GetRegNum(); lldbassert(reg_num != LLDB_INVALID_REGNUM); if (reg_num > 31) { @@ -342,28 +182,26 @@ m_out_stream.PutSLEB128(0); } -void FPOProgramASTVisitorDWARFCodegen::Visit( - FPOProgramNodeIntegerLiteral &integer, FPOProgramNode *&) { +void FPOProgramASTVisitorDWARFCodegen::Visit(IntegerNode &integer, Node *&) { uint32_t value = integer.GetValue(); m_out_stream.PutHex8(DW_OP_constu); m_out_stream.PutULEB128(value); } -void FPOProgramASTVisitorDWARFCodegen::Visit(FPOProgramNodeBinaryOp &binary, - FPOProgramNode *&) { +void FPOProgramASTVisitorDWARFCodegen::Visit(BinaryOpNode &binary, Node *&) { Dispatch(binary.Left()); Dispatch(binary.Right()); switch (binary.GetOpType()) { - case FPOProgramNodeBinaryOp::Plus: + case BinaryOpNode::Plus: m_out_stream.PutHex8(DW_OP_plus); // NOTE: can be optimized by using DW_OP_plus_uconst opcpode // if right child node is constant value break; - case FPOProgramNodeBinaryOp::Minus: + case BinaryOpNode::Minus: m_out_stream.PutHex8(DW_OP_minus); break; - case FPOProgramNodeBinaryOp::Align: + case BinaryOpNode::Align: // emit align operator a @ b as // a & ~(b - 1) // NOTE: implicitly assuming that b is power of 2 @@ -376,12 +214,11 @@ } } -void FPOProgramASTVisitorDWARFCodegen::Visit(FPOProgramNodeUnaryOp &unary, - FPOProgramNode *&) { +void FPOProgramASTVisitorDWARFCodegen::Visit(UnaryOpNode &unary, Node *&) { Dispatch(unary.Operand()); switch (unary.GetOpType()) { - case FPOProgramNodeUnaryOp::Deref: + case UnaryOpNode::Deref: m_out_stream.PutHex8(DW_OP_deref); break; } @@ -392,23 +229,23 @@ static bool ParseFPOSingleAssignmentProgram(llvm::StringRef program, NodeAllocator &alloc, llvm::StringRef ®ister_name, - FPOProgramNode *&ast) { + Node *&ast) { llvm::SmallVector tokens; llvm::SplitString(program, tokens, " "); if (tokens.empty()) return false; - llvm::SmallVector eval_stack; + llvm::SmallVector eval_stack; - llvm::DenseMap ops_binary = { - {"+", FPOProgramNodeBinaryOp::Plus}, - {"-", FPOProgramNodeBinaryOp::Minus}, - {"@", FPOProgramNodeBinaryOp::Align}, + llvm::DenseMap ops_binary = { + {"+", BinaryOpNode::Plus}, + {"-", BinaryOpNode::Minus}, + {"@", BinaryOpNode::Align}, }; - llvm::DenseMap ops_unary = { - {"^", FPOProgramNodeUnaryOp::Deref}, + llvm::DenseMap ops_unary = { + {"^", UnaryOpNode::Deref}, }; constexpr llvm::StringLiteral ra_search_keyword = ".raSearch"; @@ -424,10 +261,10 @@ if (eval_stack.size() < 2) { return false; } - FPOProgramNode *right = eval_stack.pop_back_val(); - FPOProgramNode *left = eval_stack.pop_back_val(); - FPOProgramNode *node = alloc.makeNode( - ops_binary_it->second, *left, *right); + Node *right = eval_stack.pop_back_val(); + Node *left = eval_stack.pop_back_val(); + Node *node = + alloc.makeNode(ops_binary_it->second, *left, *right); eval_stack.push_back(node); continue; } @@ -438,15 +275,14 @@ if (eval_stack.empty()) { return false; } - FPOProgramNode *operand = eval_stack.pop_back_val(); - FPOProgramNode *node = - alloc.makeNode(ops_unary_it->second, *operand); + Node *operand = eval_stack.pop_back_val(); + Node *node = alloc.makeNode(ops_unary_it->second, *operand); eval_stack.push_back(node); continue; } if (cur.startswith("$")) { - eval_stack.push_back(alloc.makeNode(cur)); + eval_stack.push_back(alloc.makeNode(cur)); continue; } @@ -458,7 +294,7 @@ uint32_t value; if (!cur.getAsInteger(10, value)) { // token is integer literal - eval_stack.push_back(alloc.makeNode(value)); + eval_stack.push_back(alloc.makeNode(value)); continue; } @@ -476,11 +312,11 @@ return true; } -static FPOProgramNode *ParseFPOProgram(llvm::StringRef program, - llvm::StringRef register_name, - llvm::Triple::ArchType arch_type, - NodeAllocator &alloc) { - llvm::DenseMap dependent_programs; +static Node *ParseFPOProgram(llvm::StringRef program, + llvm::StringRef register_name, + llvm::Triple::ArchType arch_type, + NodeAllocator &alloc) { + llvm::DenseMap dependent_programs; size_t cur = 0; while (true) { @@ -496,7 +332,7 @@ llvm::StringRef assignment_program = program.slice(cur, assign_index); llvm::StringRef lvalue_name; - FPOProgramNode *rvalue_ast = nullptr; + Node *rvalue_ast = nullptr; if (!ParseFPOSingleAssignmentProgram(assignment_program, alloc, lvalue_name, rvalue_ast)) { return nullptr; @@ -530,7 +366,7 @@ llvm::StringRef program, llvm::StringRef register_name, llvm::Triple::ArchType arch_type, Stream &stream) { NodeAllocator node_alloc; - FPOProgramNode *target_program = + Node *target_program = ParseFPOProgram(program, register_name, arch_type, node_alloc); if (target_program == nullptr) { return false;