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