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