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-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 using namespace lldb_private::dwarf; 22 23 static llvm::Optional<BinaryOpNode::OpType> 24 GetBinaryOpType(llvm::StringRef token) { 25 if (token.size() != 1) 26 return llvm::None; 27 switch (token[0]) { 28 case '@': 29 return BinaryOpNode::Align; 30 case '-': 31 return BinaryOpNode::Minus; 32 case '+': 33 return BinaryOpNode::Plus; 34 } 35 return llvm::None; 36 } 37 38 static llvm::Optional<UnaryOpNode::OpType> 39 GetUnaryOpType(llvm::StringRef token) { 40 if (token == "^") 41 return UnaryOpNode::Deref; 42 return llvm::None; 43 } 44 45 Node *postfix::ParseOneExpression(llvm::StringRef expr, 46 llvm::BumpPtrAllocator &alloc) { 47 llvm::SmallVector<Node *, 4> stack; 48 49 llvm::StringRef token; 50 while (std::tie(token, expr) = getToken(expr), !token.empty()) { 51 if (auto op_type = GetBinaryOpType(token)) { 52 // token is binary operator 53 if (stack.size() < 2) 54 return nullptr; 55 56 Node *right = stack.pop_back_val(); 57 Node *left = stack.pop_back_val(); 58 stack.push_back(MakeNode<BinaryOpNode>(alloc, *op_type, *left, *right)); 59 continue; 60 } 61 62 if (auto op_type = GetUnaryOpType(token)) { 63 // token is unary operator 64 if (stack.empty()) 65 return nullptr; 66 67 Node *operand = stack.pop_back_val(); 68 stack.push_back(MakeNode<UnaryOpNode>(alloc, *op_type, *operand)); 69 continue; 70 } 71 72 int64_t value; 73 if (to_integer(token, value, 10)) { 74 // token is integer literal 75 stack.push_back(MakeNode<IntegerNode>(alloc, value)); 76 continue; 77 } 78 79 stack.push_back(MakeNode<SymbolNode>(alloc, token)); 80 } 81 82 if (stack.size() != 1) 83 return nullptr; 84 85 return stack.back(); 86 } 87 88 std::vector<std::pair<llvm::StringRef, Node *>> 89 postfix::ParseFPOProgram(llvm::StringRef prog, llvm::BumpPtrAllocator &alloc) { 90 llvm::SmallVector<llvm::StringRef, 4> exprs; 91 prog.split(exprs, '='); 92 if (exprs.empty() || !exprs.back().trim().empty()) 93 return {}; 94 exprs.pop_back(); 95 96 std::vector<std::pair<llvm::StringRef, Node *>> result; 97 for (llvm::StringRef expr : exprs) { 98 llvm::StringRef lhs; 99 std::tie(lhs, expr) = getToken(expr); 100 Node *rhs = ParseOneExpression(expr, alloc); 101 if (!rhs) 102 return {}; 103 result.emplace_back(lhs, rhs); 104 } 105 return result; 106 } 107 108 namespace { 109 class SymbolResolver : public Visitor<bool> { 110 public: 111 SymbolResolver(llvm::function_ref<Node *(SymbolNode &symbol)> replacer) 112 : m_replacer(replacer) {} 113 114 using Visitor<bool>::Dispatch; 115 116 private: 117 bool Visit(BinaryOpNode &binary, Node *&) override { 118 return Dispatch(binary.Left()) && Dispatch(binary.Right()); 119 } 120 121 bool Visit(InitialValueNode &, Node *&) override { return true; } 122 bool Visit(IntegerNode &, Node *&) override { return true; } 123 bool Visit(RegisterNode &, Node *&) override { return true; } 124 125 bool Visit(SymbolNode &symbol, Node *&ref) override { 126 if (Node *replacement = m_replacer(symbol)) { 127 ref = replacement; 128 if (replacement != &symbol) 129 return Dispatch(ref); 130 return true; 131 } 132 return false; 133 } 134 135 bool Visit(UnaryOpNode &unary, Node *&) override { 136 return Dispatch(unary.Operand()); 137 } 138 139 llvm::function_ref<Node *(SymbolNode &symbol)> m_replacer; 140 }; 141 142 class DWARFCodegen : public Visitor<> { 143 public: 144 DWARFCodegen(Stream &stream) : m_out_stream(stream) {} 145 146 using Visitor<>::Dispatch; 147 148 private: 149 void Visit(BinaryOpNode &binary, Node *&) override; 150 151 void Visit(InitialValueNode &val, Node *&) override; 152 153 void Visit(IntegerNode &integer, Node *&) override { 154 m_out_stream.PutHex8(DW_OP_consts); 155 m_out_stream.PutSLEB128(integer.GetValue()); 156 ++m_stack_depth; 157 } 158 159 void Visit(RegisterNode ®, Node *&) override; 160 161 void Visit(SymbolNode &symbol, Node *&) override { 162 llvm_unreachable("Symbols should have been resolved by now!"); 163 } 164 165 void Visit(UnaryOpNode &unary, Node *&) override; 166 167 Stream &m_out_stream; 168 169 /// The number keeping track of the evaluation stack depth at any given 170 /// moment. Used for implementing InitialValueNodes. We start with 171 /// m_stack_depth = 1, assuming that the initial value is already on the 172 /// stack. This initial value will be the value of all InitialValueNodes. If 173 /// the expression does not contain InitialValueNodes, then m_stack_depth is 174 /// not used, and the generated expression will run correctly even without an 175 /// initial value. 176 size_t m_stack_depth = 1; 177 }; 178 } // namespace 179 180 void DWARFCodegen::Visit(BinaryOpNode &binary, Node *&) { 181 Dispatch(binary.Left()); 182 Dispatch(binary.Right()); 183 184 switch (binary.GetOpType()) { 185 case BinaryOpNode::Plus: 186 m_out_stream.PutHex8(DW_OP_plus); 187 // NOTE: can be optimized by using DW_OP_plus_uconst opcpode 188 // if right child node is constant value 189 break; 190 case BinaryOpNode::Minus: 191 m_out_stream.PutHex8(DW_OP_minus); 192 break; 193 case BinaryOpNode::Align: 194 // emit align operator a @ b as 195 // a & ~(b - 1) 196 // NOTE: implicitly assuming that b is power of 2 197 m_out_stream.PutHex8(DW_OP_lit1); 198 m_out_stream.PutHex8(DW_OP_minus); 199 m_out_stream.PutHex8(DW_OP_not); 200 201 m_out_stream.PutHex8(DW_OP_and); 202 break; 203 } 204 --m_stack_depth; // Two pops, one push. 205 } 206 207 void DWARFCodegen::Visit(InitialValueNode &, Node *&) { 208 // We never go below the initial stack, so we can pick the initial value from 209 // the bottom of the stack at any moment. 210 assert(m_stack_depth >= 1); 211 m_out_stream.PutHex8(DW_OP_pick); 212 m_out_stream.PutHex8(m_stack_depth - 1); 213 ++m_stack_depth; 214 } 215 216 void DWARFCodegen::Visit(RegisterNode ®, Node *&) { 217 uint32_t reg_num = reg.GetRegNum(); 218 assert(reg_num != LLDB_INVALID_REGNUM); 219 220 if (reg_num > 31) { 221 m_out_stream.PutHex8(DW_OP_bregx); 222 m_out_stream.PutULEB128(reg_num); 223 } else 224 m_out_stream.PutHex8(DW_OP_breg0 + reg_num); 225 226 m_out_stream.PutSLEB128(0); 227 ++m_stack_depth; 228 } 229 230 void DWARFCodegen::Visit(UnaryOpNode &unary, Node *&) { 231 Dispatch(unary.Operand()); 232 233 switch (unary.GetOpType()) { 234 case UnaryOpNode::Deref: 235 m_out_stream.PutHex8(DW_OP_deref); 236 break; 237 } 238 // Stack depth unchanged. 239 } 240 241 bool postfix::ResolveSymbols( 242 Node *&node, llvm::function_ref<Node *(SymbolNode &)> replacer) { 243 return SymbolResolver(replacer).Dispatch(node); 244 } 245 246 void postfix::ToDWARF(Node &node, Stream &stream) { 247 Node *ptr = &node; 248 DWARFCodegen(stream).Dispatch(ptr); 249 } 250