Index: include/lldb/Symbol/PostfixExpression.h =================================================================== --- include/lldb/Symbol/PostfixExpression.h +++ include/lldb/Symbol/PostfixExpression.h @@ -19,6 +19,9 @@ #include "llvm/Support/Casting.h" namespace lldb_private { + +class Stream; + namespace postfix { /// The base class for all nodes in the parsed postfix tree. @@ -174,6 +177,17 @@ } }; +/// A utility function for "resolving" SymbolNodes. It traverses a tree and +/// calls the callback function for all SymbolNodes it encountered. The +/// replacement function should return the node it wished to replace the current +/// SymbolNode with (this can also be the original node), or nullptr in case of +/// an error. The nodes returned by the callback are inspected and replaced +/// recursively, *except* for the case when the function returns the exact same +/// node as the input one. It returns true if all SymbolNodes were replaced +/// successfully. +bool ResolveSymbols(Node *&node, + llvm::function_ref replacer); + template inline T *MakeNode(llvm::BumpPtrAllocator &alloc, Args &&... args) { static_assert(std::is_trivially_destructible::value, @@ -185,6 +199,10 @@ /// provided allocator. Node *Parse(llvm::StringRef expr, llvm::BumpPtrAllocator &alloc); +/// Serialize the given expression tree as DWARF. The result is written into the +/// given stream. The AST should not contain any SymbolNodes. +void ToDWARF(Node &node, Stream &stream); + } // namespace postfix } // namespace lldb_private Index: source/Plugins/SymbolFile/NativePDB/PdbFPOProgramToDWARFExpression.cpp =================================================================== --- source/Plugins/SymbolFile/NativePDB/PdbFPOProgramToDWARFExpression.cpp +++ source/Plugins/SymbolFile/NativePDB/PdbFPOProgramToDWARFExpression.cpp @@ -10,7 +10,6 @@ #include "CodeViewRegisterMapping.h" #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" @@ -24,83 +23,6 @@ using namespace lldb_private; using namespace lldb_private::postfix; -namespace { - -class FPOProgramASTVisitorMergeDependent : public Visitor<> { -public: - void Visit(BinaryOpNode &binary, Node *&) override { - Dispatch(binary.Left()); - Dispatch(binary.Right()); - } - - void Visit(UnaryOpNode &unary, Node *&) override { - Dispatch(unary.Operand()); - } - - 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, - Node *&ast) { - FPOProgramASTVisitorMergeDependent(dependent_programs).Dispatch(ast); - } - -private: - FPOProgramASTVisitorMergeDependent( - const llvm::DenseMap &dependent_programs) - : m_dependent_programs(dependent_programs) {} - - const llvm::DenseMap &m_dependent_programs; -}; - -void FPOProgramASTVisitorMergeDependent::Visit(SymbolNode &symbol, Node *&ref) { - auto it = m_dependent_programs.find(symbol.GetName()); - if (it == m_dependent_programs.end()) - return; - - ref = it->second; - Dispatch(ref); -} - -class FPOProgramASTVisitorResolveRegisterRefs : public Visitor { -public: - static bool - Resolve(const llvm::DenseMap &dependent_programs, - llvm::Triple::ArchType arch_type, llvm::BumpPtrAllocator &alloc, - Node *&ast) { - return FPOProgramASTVisitorResolveRegisterRefs(dependent_programs, - arch_type, alloc) - .Dispatch(ast); - } - - bool Visit(BinaryOpNode &binary, Node *&) override { - return Dispatch(binary.Left()) && Dispatch(binary.Right()); - } - - bool Visit(UnaryOpNode &unary, Node *&) override { - return Dispatch(unary.Operand()); - } - - bool Visit(RegisterNode &, Node *&) override { return true; } - - bool Visit(IntegerNode &, Node *&) override { return true; } - - bool Visit(SymbolNode &symbol, Node *&ref) override; - -private: - FPOProgramASTVisitorResolveRegisterRefs( - const llvm::DenseMap &dependent_programs, - llvm::Triple::ArchType arch_type, llvm::BumpPtrAllocator &alloc) - : m_dependent_programs(dependent_programs), m_arch_type(arch_type), - m_alloc(alloc) {} - - const llvm::DenseMap &m_dependent_programs; - llvm::Triple::ArchType m_arch_type; - llvm::BumpPtrAllocator &m_alloc; -}; - static uint32_t ResolveLLDBRegisterNum(llvm::StringRef reg_name, llvm::Triple::ArchType arch_type) { // lookup register name to get lldb register number llvm::ArrayRef> register_names = @@ -118,102 +40,6 @@ return npdb::GetLLDBRegisterNumber(arch_type, reg_id); } -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()) { - // Dependent programs are handled elsewhere. - return true; - } - - uint32_t reg_num = - ResolveLLDBRegisterNum(symbol.GetName().drop_front(1), m_arch_type); - - if (reg_num == LLDB_INVALID_REGNUM) - return false; - - ref = MakeNode(m_alloc, reg_num); - return true; -} - -class FPOProgramASTVisitorDWARFCodegen : public Visitor<> { -public: - static void Emit(Stream &stream, Node *&ast) { - FPOProgramASTVisitorDWARFCodegen(stream).Dispatch(ast); - } - - 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(IntegerNode &integer, Node *&); - -private: - FPOProgramASTVisitorDWARFCodegen(Stream &stream) : m_out_stream(stream) {} - - Stream &m_out_stream; -}; - -void FPOProgramASTVisitorDWARFCodegen::Visit(RegisterNode ®, Node *&) { - uint32_t reg_num = reg.GetRegNum(); - lldbassert(reg_num != LLDB_INVALID_REGNUM); - - if (reg_num > 31) { - m_out_stream.PutHex8(DW_OP_bregx); - m_out_stream.PutULEB128(reg_num); - } else - m_out_stream.PutHex8(DW_OP_breg0 + reg_num); - - m_out_stream.PutSLEB128(0); -} - -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(BinaryOpNode &binary, Node *&) { - Dispatch(binary.Left()); - Dispatch(binary.Right()); - - switch (binary.GetOpType()) { - 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 BinaryOpNode::Minus: - m_out_stream.PutHex8(DW_OP_minus); - break; - case BinaryOpNode::Align: - // emit align operator a @ b as - // a & ~(b - 1) - // NOTE: implicitly assuming that b is power of 2 - m_out_stream.PutHex8(DW_OP_lit1); - m_out_stream.PutHex8(DW_OP_minus); - m_out_stream.PutHex8(DW_OP_not); - - m_out_stream.PutHex8(DW_OP_and); - break; - } -} - -void FPOProgramASTVisitorDWARFCodegen::Visit(UnaryOpNode &unary, Node *&) { - Dispatch(unary.Operand()); - - switch (unary.GetOpType()) { - case UnaryOpNode::Deref: - m_out_stream.PutHex8(DW_OP_deref); - break; - } -} - -} // namespace - static bool ParseFPOSingleAssignmentProgram(llvm::StringRef program, llvm::BumpPtrAllocator &alloc, llvm::StringRef ®ister_name, @@ -256,18 +82,25 @@ lldbassert(rvalue_ast); - // check & resolve assignment program - if (!FPOProgramASTVisitorResolveRegisterRefs::Resolve( - dependent_programs, arch_type, alloc, rvalue_ast)) + // Emplace valid dependent subtrees to make target assignment independent + // from predecessors. Resolve all other SymbolNodes as registers. + bool success = + ResolveSymbols(rvalue_ast, [&](SymbolNode &symbol) -> Node * { + if (Node *node = dependent_programs.lookup(symbol.GetName())) + return node; + uint32_t reg_num = + ResolveLLDBRegisterNum(symbol.GetName().drop_front(1), arch_type); + + if (reg_num == LLDB_INVALID_REGNUM) + return nullptr; + + return MakeNode(alloc, reg_num); + }); + if (!success) return nullptr; if (lvalue_name == register_name) { // found target assignment program - no need to parse further - - // emplace valid dependent subtrees to make target assignment independent - // from predecessors - FPOProgramASTVisitorMergeDependent::Merge(dependent_programs, rvalue_ast); - return rvalue_ast; } @@ -288,6 +121,6 @@ return false; } - FPOProgramASTVisitorDWARFCodegen::Emit(stream, target_program); + ToDWARF(*target_program, stream); return true; } Index: source/Symbol/PostfixExpression.cpp =================================================================== --- source/Symbol/PostfixExpression.cpp +++ source/Symbol/PostfixExpression.cpp @@ -12,6 +12,8 @@ //===----------------------------------------------------------------------===// #include "lldb/Symbol/PostfixExpression.h" +#include "lldb/Core/dwarf.h" +#include "lldb/Utility/Stream.h" #include "llvm/ADT/StringExtras.h" using namespace lldb_private; @@ -80,3 +82,121 @@ return stack.back(); } + +namespace { +class SymbolResolver : public Visitor { +public: + SymbolResolver(llvm::function_ref replacer) + : m_replacer(replacer) {} + + using Visitor::Dispatch; + +private: + bool Visit(BinaryOpNode &binary, Node *&) override { + return Dispatch(binary.Left()) && Dispatch(binary.Right()); + } + + bool Visit(IntegerNode &integer, Node *&) override { return true; } + bool Visit(RegisterNode ®, Node *&) override { return true; } + + bool Visit(SymbolNode &symbol, Node *&ref) override { + if (Node *replacement = m_replacer(symbol)) { + ref = replacement; + if (replacement != &symbol) + return Dispatch(ref); + return true; + } + return false; + } + + bool Visit(UnaryOpNode &unary, Node *&) override { + return Dispatch(unary.Operand()); + } + + llvm::function_ref m_replacer; +}; + +class DWARFCodegen : public Visitor<> { +public: + DWARFCodegen(Stream &stream) : m_out_stream(stream) {} + + using Visitor<>::Dispatch; + +private: + void Visit(BinaryOpNode &binary, Node *&); + + void Visit(IntegerNode &integer, Node *&) { + m_out_stream.PutHex8(DW_OP_constu); + m_out_stream.PutULEB128(integer.GetValue()); + } + + void Visit(RegisterNode ®, Node *&); + + void Visit(SymbolNode &symbol, Node *&) { + llvm_unreachable("Symbols should have been resolved by now!"); + } + + void Visit(UnaryOpNode &unary, Node *&); + + Stream &m_out_stream; +}; +} // namespace + +void DWARFCodegen::Visit(BinaryOpNode &binary, Node *&) { + Dispatch(binary.Left()); + Dispatch(binary.Right()); + + switch (binary.GetOpType()) { + 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 BinaryOpNode::Minus: + m_out_stream.PutHex8(DW_OP_minus); + break; + case BinaryOpNode::Align: + // emit align operator a @ b as + // a & ~(b - 1) + // NOTE: implicitly assuming that b is power of 2 + m_out_stream.PutHex8(DW_OP_lit1); + m_out_stream.PutHex8(DW_OP_minus); + m_out_stream.PutHex8(DW_OP_not); + + m_out_stream.PutHex8(DW_OP_and); + break; + } +} + +void DWARFCodegen::Visit(RegisterNode ®, Node *&) { + uint32_t reg_num = reg.GetRegNum(); + assert(reg_num != LLDB_INVALID_REGNUM); + + if (reg_num > 31) { + m_out_stream.PutHex8(DW_OP_bregx); + m_out_stream.PutULEB128(reg_num); + } else + m_out_stream.PutHex8(DW_OP_breg0 + reg_num); + + m_out_stream.PutSLEB128(0); +} + +void DWARFCodegen::Visit(UnaryOpNode &unary, Node *&) { + Dispatch(unary.Operand()); + + switch (unary.GetOpType()) { + case UnaryOpNode::Deref: + m_out_stream.PutHex8(DW_OP_deref); + break; + } +} + +bool postfix::ResolveSymbols( + Node *&node, llvm::function_ref replacer) { + return SymbolResolver(replacer).Dispatch(node); +} + +void postfix::ToDWARF(Node &node, Stream &stream) { + Node *ptr = &node; + DWARFCodegen(stream).Dispatch(ptr); +} Index: unittests/Symbol/PostfixExpressionTest.cpp =================================================================== --- unittests/Symbol/PostfixExpressionTest.cpp +++ unittests/Symbol/PostfixExpressionTest.cpp @@ -7,6 +7,9 @@ //===----------------------------------------------------------------------===// #include "lldb/Symbol/PostfixExpression.h" +#include "lldb/Expression/DWARFExpression.h" +#include "lldb/Utility/DataExtractor.h" +#include "lldb/Utility/StreamString.h" #include "llvm/Support/FormatVariadic.h" #include "llvm/Support/raw_ostream.h" #include "gtest/gtest.h" @@ -95,3 +98,55 @@ EXPECT_EQ("nullptr", ParseAndStringify("1 2")); EXPECT_EQ("nullptr", ParseAndStringify("")); } + +static std::string ParseAndGenerateDWARF(llvm::StringRef expr) { + llvm::BumpPtrAllocator alloc; + Node *ast = Parse(expr, alloc); + if (!ast) + return "Parse failed."; + if (!ResolveSymbols(ast, [&](SymbolNode &symbol) -> Node * { + uint32_t num; + if (to_integer(symbol.GetName().drop_front(), num)) + return MakeNode(alloc, num); + return nullptr; + })) { + return "Resolution failed."; + } + + const size_t addr_size = 4; + StreamString dwarf(Stream::eBinary, addr_size, lldb::eByteOrderLittle); + ToDWARF(*ast, dwarf); + + // print dwarf expression to comparable textual representation + DataExtractor extractor(dwarf.GetData(), dwarf.GetSize(), + lldb::eByteOrderLittle, addr_size); + + StreamString result; + if (!DWARFExpression::PrintDWARFExpression(result, extractor, addr_size, + /*dwarf_ref_size*/ 4, + /*location_expression*/ false)) { + return "DWARF printing failed."; + } + + return result.GetString(); +} + +TEST(PostfixExpression, ToDWARF) { + EXPECT_EQ("DW_OP_constu 0x0", ParseAndGenerateDWARF("0")); + + EXPECT_EQ("DW_OP_breg1 +0", ParseAndGenerateDWARF("R1")); + + EXPECT_EQ("DW_OP_bregx 65 0", ParseAndGenerateDWARF("R65")); + + EXPECT_EQ("DW_OP_constu 0x4, DW_OP_constu 0x5, DW_OP_plus ", + ParseAndGenerateDWARF("4 5 +")); + + EXPECT_EQ("DW_OP_constu 0x4, DW_OP_constu 0x5, DW_OP_minus ", + ParseAndGenerateDWARF("4 5 -")); + + EXPECT_EQ("DW_OP_constu 0x4, DW_OP_deref ", ParseAndGenerateDWARF("4 ^")); + + EXPECT_EQ("DW_OP_breg6 +0, DW_OP_constu 0x80, DW_OP_lit1 " + ", DW_OP_minus , DW_OP_not , DW_OP_and ", + ParseAndGenerateDWARF("R6 128 @")); +}