1 //===-- PostfixExpression.cpp -----------------------------------*- C++ -*-===// 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 19 using namespace lldb_private; 20 using namespace lldb_private::postfix; 21 22 static llvm::Optional<BinaryOpNode::OpType> 23 GetBinaryOpType(llvm::StringRef token) { 24 if (token.size() != 1) 25 return llvm::None; 26 switch (token[0]) { 27 case '@': 28 return BinaryOpNode::Align; 29 case '-': 30 return BinaryOpNode::Minus; 31 case '+': 32 return BinaryOpNode::Plus; 33 } 34 return llvm::None; 35 } 36 37 static llvm::Optional<UnaryOpNode::OpType> 38 GetUnaryOpType(llvm::StringRef token) { 39 if (token == "^") 40 return UnaryOpNode::Deref; 41 return llvm::None; 42 } 43 44 Node *postfix::Parse(llvm::StringRef expr, llvm::BumpPtrAllocator &alloc) { 45 llvm::SmallVector<Node *, 4> stack; 46 47 llvm::StringRef token; 48 while (std::tie(token, expr) = getToken(expr), !token.empty()) { 49 if (auto op_type = GetBinaryOpType(token)) { 50 // token is binary operator 51 if (stack.size() < 2) 52 return nullptr; 53 54 Node *right = stack.pop_back_val(); 55 Node *left = stack.pop_back_val(); 56 stack.push_back(MakeNode<BinaryOpNode>(alloc, *op_type, *left, *right)); 57 continue; 58 } 59 60 if (auto op_type = GetUnaryOpType(token)) { 61 // token is unary operator 62 if (stack.empty()) 63 return nullptr; 64 65 Node *operand = stack.pop_back_val(); 66 stack.push_back(MakeNode<UnaryOpNode>(alloc, *op_type, *operand)); 67 continue; 68 } 69 70 uint32_t value; 71 if (to_integer(token, value, 10)) { 72 // token is integer literal 73 stack.push_back(MakeNode<IntegerNode>(alloc, value)); 74 continue; 75 } 76 77 stack.push_back(MakeNode<SymbolNode>(alloc, token)); 78 } 79 80 if (stack.size() != 1) 81 return nullptr; 82 83 return stack.back(); 84 } 85 86 namespace { 87 class SymbolResolver : public Visitor<bool> { 88 public: 89 SymbolResolver(llvm::function_ref<Node *(SymbolNode &symbol)> replacer) 90 : m_replacer(replacer) {} 91 92 using Visitor<bool>::Dispatch; 93 94 private: 95 bool Visit(BinaryOpNode &binary, Node *&) override { 96 return Dispatch(binary.Left()) && Dispatch(binary.Right()); 97 } 98 99 bool Visit(IntegerNode &integer, Node *&) override { return true; } 100 bool Visit(RegisterNode ®, Node *&) override { return true; } 101 102 bool Visit(SymbolNode &symbol, Node *&ref) override { 103 if (Node *replacement = m_replacer(symbol)) { 104 ref = replacement; 105 if (replacement != &symbol) 106 return Dispatch(ref); 107 return true; 108 } 109 return false; 110 } 111 112 bool Visit(UnaryOpNode &unary, Node *&) override { 113 return Dispatch(unary.Operand()); 114 } 115 116 llvm::function_ref<Node *(SymbolNode &symbol)> m_replacer; 117 }; 118 119 class DWARFCodegen : public Visitor<> { 120 public: 121 DWARFCodegen(Stream &stream) : m_out_stream(stream) {} 122 123 using Visitor<>::Dispatch; 124 125 private: 126 void Visit(BinaryOpNode &binary, Node *&); 127 128 void Visit(IntegerNode &integer, Node *&) { 129 m_out_stream.PutHex8(DW_OP_constu); 130 m_out_stream.PutULEB128(integer.GetValue()); 131 } 132 133 void Visit(RegisterNode ®, Node *&); 134 135 void Visit(SymbolNode &symbol, Node *&) { 136 llvm_unreachable("Symbols should have been resolved by now!"); 137 } 138 139 void Visit(UnaryOpNode &unary, Node *&); 140 141 Stream &m_out_stream; 142 }; 143 } // namespace 144 145 void DWARFCodegen::Visit(BinaryOpNode &binary, Node *&) { 146 Dispatch(binary.Left()); 147 Dispatch(binary.Right()); 148 149 switch (binary.GetOpType()) { 150 case BinaryOpNode::Plus: 151 m_out_stream.PutHex8(DW_OP_plus); 152 // NOTE: can be optimized by using DW_OP_plus_uconst opcpode 153 // if right child node is constant value 154 break; 155 case BinaryOpNode::Minus: 156 m_out_stream.PutHex8(DW_OP_minus); 157 break; 158 case BinaryOpNode::Align: 159 // emit align operator a @ b as 160 // a & ~(b - 1) 161 // NOTE: implicitly assuming that b is power of 2 162 m_out_stream.PutHex8(DW_OP_lit1); 163 m_out_stream.PutHex8(DW_OP_minus); 164 m_out_stream.PutHex8(DW_OP_not); 165 166 m_out_stream.PutHex8(DW_OP_and); 167 break; 168 } 169 } 170 171 void DWARFCodegen::Visit(RegisterNode ®, Node *&) { 172 uint32_t reg_num = reg.GetRegNum(); 173 assert(reg_num != LLDB_INVALID_REGNUM); 174 175 if (reg_num > 31) { 176 m_out_stream.PutHex8(DW_OP_bregx); 177 m_out_stream.PutULEB128(reg_num); 178 } else 179 m_out_stream.PutHex8(DW_OP_breg0 + reg_num); 180 181 m_out_stream.PutSLEB128(0); 182 } 183 184 void DWARFCodegen::Visit(UnaryOpNode &unary, Node *&) { 185 Dispatch(unary.Operand()); 186 187 switch (unary.GetOpType()) { 188 case UnaryOpNode::Deref: 189 m_out_stream.PutHex8(DW_OP_deref); 190 break; 191 } 192 } 193 194 bool postfix::ResolveSymbols( 195 Node *&node, llvm::function_ref<Node *(SymbolNode &)> replacer) { 196 return SymbolResolver(replacer).Dispatch(node); 197 } 198 199 void postfix::ToDWARF(Node &node, Stream &stream) { 200 Node *ptr = &node; 201 DWARFCodegen(stream).Dispatch(ptr); 202 } 203