PostfixExpression.cpp revision 360784
1139749Simp//===-- PostfixExpression.cpp -----------------------------------*- C++ -*-===// 2135048Swpaul// 3135048Swpaul// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4135048Swpaul// See https://llvm.org/LICENSE.txt for license information. 5135048Swpaul// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6135048Swpaul// 7135048Swpaul//===----------------------------------------------------------------------===// 8135048Swpaul// 9135048Swpaul// This file implements support for postfix expressions found in several symbol 10135048Swpaul// file formats, and their conversion to DWARF. 11135048Swpaul// 12135048Swpaul//===----------------------------------------------------------------------===// 13135048Swpaul 14135048Swpaul#include "lldb/Symbol/PostfixExpression.h" 15135048Swpaul#include "lldb/Core/dwarf.h" 16135048Swpaul#include "lldb/Utility/Stream.h" 17135048Swpaul#include "llvm/ADT/StringExtras.h" 18135048Swpaul 19135048Swpaulusing namespace lldb_private; 20135048Swpaulusing namespace lldb_private::postfix; 21135048Swpaul 22135048Swpaulstatic llvm::Optional<BinaryOpNode::OpType> 23135048SwpaulGetBinaryOpType(llvm::StringRef token) { 24135048Swpaul if (token.size() != 1) 25135048Swpaul return llvm::None; 26135048Swpaul switch (token[0]) { 27135048Swpaul case '@': 28135048Swpaul return BinaryOpNode::Align; 29135048Swpaul case '-': 30135048Swpaul return BinaryOpNode::Minus; 31135048Swpaul case '+': 32135048Swpaul return BinaryOpNode::Plus; 33135048Swpaul } 34135048Swpaul return llvm::None; 35135048Swpaul} 36135048Swpaul 37135048Swpaulstatic llvm::Optional<UnaryOpNode::OpType> 38135048SwpaulGetUnaryOpType(llvm::StringRef token) { 39135048Swpaul if (token == "^") 40135048Swpaul return UnaryOpNode::Deref; 41135048Swpaul return llvm::None; 42135048Swpaul} 43135048Swpaul 44135048SwpaulNode *postfix::ParseOneExpression(llvm::StringRef expr, 45135048Swpaul llvm::BumpPtrAllocator &alloc) { 46135048Swpaul llvm::SmallVector<Node *, 4> stack; 47135048Swpaul 48135048Swpaul llvm::StringRef token; 49135048Swpaul while (std::tie(token, expr) = getToken(expr), !token.empty()) { 50135048Swpaul if (auto op_type = GetBinaryOpType(token)) { 51135048Swpaul // token is binary operator 52135048Swpaul if (stack.size() < 2) 53135048Swpaul return nullptr; 54135048Swpaul 55135048Swpaul Node *right = stack.pop_back_val(); 56135048Swpaul Node *left = stack.pop_back_val(); 57135048Swpaul stack.push_back(MakeNode<BinaryOpNode>(alloc, *op_type, *left, *right)); 58135048Swpaul continue; 59135048Swpaul } 60135048Swpaul 61135048Swpaul if (auto op_type = GetUnaryOpType(token)) { 62135048Swpaul // token is unary operator 63135048Swpaul if (stack.empty()) 64135048Swpaul return nullptr; 65135048Swpaul 66135048Swpaul Node *operand = stack.pop_back_val(); 67135048Swpaul stack.push_back(MakeNode<UnaryOpNode>(alloc, *op_type, *operand)); 68135048Swpaul continue; 69135048Swpaul } 70135048Swpaul 71135048Swpaul int64_t value; 72135048Swpaul if (to_integer(token, value, 10)) { 73135048Swpaul // token is integer literal 74135048Swpaul stack.push_back(MakeNode<IntegerNode>(alloc, value)); 75135048Swpaul continue; 76135048Swpaul } 77135048Swpaul 78135048Swpaul stack.push_back(MakeNode<SymbolNode>(alloc, token)); 79135048Swpaul } 80135048Swpaul 81135048Swpaul if (stack.size() != 1) 82135048Swpaul return nullptr; 83150968Sglebius 84150968Sglebius return stack.back(); 85150968Sglebius} 86150968Sglebius 87135048Swpaulstd::vector<std::pair<llvm::StringRef, Node *>> 88135048Swpaulpostfix::ParseFPOProgram(llvm::StringRef prog, llvm::BumpPtrAllocator &alloc) { 89135048Swpaul llvm::SmallVector<llvm::StringRef, 4> exprs; 90135048Swpaul prog.split(exprs, '='); 91135048Swpaul if (exprs.empty() || !exprs.back().trim().empty()) 92135048Swpaul return {}; 93135048Swpaul exprs.pop_back(); 94135048Swpaul 95135048Swpaul std::vector<std::pair<llvm::StringRef, Node *>> result; 96135048Swpaul for (llvm::StringRef expr : exprs) { 97135048Swpaul llvm::StringRef lhs; 98135048Swpaul std::tie(lhs, expr) = getToken(expr); 99135048Swpaul Node *rhs = ParseOneExpression(expr, alloc); 100135048Swpaul if (!rhs) 101135048Swpaul return {}; 102147256Sbrooks result.emplace_back(lhs, rhs); 103135048Swpaul } 104135048Swpaul return result; 105135048Swpaul} 106135048Swpaul 107135048Swpaulnamespace { 108135048Swpaulclass SymbolResolver : public Visitor<bool> { 109135048Swpaulpublic: 110135048Swpaul SymbolResolver(llvm::function_ref<Node *(SymbolNode &symbol)> replacer) 111135048Swpaul : m_replacer(replacer) {} 112135048Swpaul 113135048Swpaul using Visitor<bool>::Dispatch; 114135048Swpaul 115135048Swpaulprivate: 116135048Swpaul bool Visit(BinaryOpNode &binary, Node *&) override { 117135048Swpaul return Dispatch(binary.Left()) && Dispatch(binary.Right()); 118135048Swpaul } 119135048Swpaul 120135048Swpaul bool Visit(InitialValueNode &, Node *&) override { return true; } 121135048Swpaul bool Visit(IntegerNode &, Node *&) override { return true; } 122151545Simp bool Visit(RegisterNode &, Node *&) override { return true; } 123135048Swpaul 124135048Swpaul bool Visit(SymbolNode &symbol, Node *&ref) override { 125135048Swpaul if (Node *replacement = m_replacer(symbol)) { 126135048Swpaul ref = replacement; 127135048Swpaul if (replacement != &symbol) 128135048Swpaul return Dispatch(ref); 129135048Swpaul return true; 130200541Syongari } 131200541Syongari return false; 132200541Syongari } 133200541Syongari 134135048Swpaul bool Visit(UnaryOpNode &unary, Node *&) override { 135135048Swpaul return Dispatch(unary.Operand()); 136135048Swpaul } 137135048Swpaul 138135048Swpaul llvm::function_ref<Node *(SymbolNode &symbol)> m_replacer; 139135048Swpaul}; 140135048Swpaul 141135048Swpaulclass DWARFCodegen : public Visitor<> { 142135048Swpaulpublic: 143135048Swpaul DWARFCodegen(Stream &stream) : m_out_stream(stream) {} 144135048Swpaul 145135048Swpaul using Visitor<>::Dispatch; 146135048Swpaul 147200525Syongariprivate: 148135048Swpaul void Visit(BinaryOpNode &binary, Node *&) override; 149200525Syongari 150200525Syongari void Visit(InitialValueNode &val, Node *&) override; 151200525Syongari 152200525Syongari void Visit(IntegerNode &integer, Node *&) override { 153200525Syongari m_out_stream.PutHex8(DW_OP_consts); 154135048Swpaul m_out_stream.PutSLEB128(integer.GetValue()); 155135048Swpaul ++m_stack_depth; 156200525Syongari } 157200525Syongari 158135048Swpaul void Visit(RegisterNode ®, Node *&) override; 159135048Swpaul 160135048Swpaul void Visit(SymbolNode &symbol, Node *&) override { 161200525Syongari llvm_unreachable("Symbols should have been resolved by now!"); 162135048Swpaul } 163135048Swpaul 164135048Swpaul void Visit(UnaryOpNode &unary, Node *&) override; 165135048Swpaul 166199543Sjhb Stream &m_out_stream; 167135048Swpaul 168135048Swpaul /// The number keeping track of the evaluation stack depth at any given 169199543Sjhb /// moment. Used for implementing InitialValueNodes. We start with 170135048Swpaul /// m_stack_depth = 1, assuming that the initial value is already on the 171199543Sjhb /// stack. This initial value will be the value of all InitialValueNodes. If 172135048Swpaul /// the expression does not contain InitialValueNodes, then m_stack_depth is 173135048Swpaul /// not used, and the generated expression will run correctly even without an 174173839Syongari /// initial value. 175135048Swpaul size_t m_stack_depth = 1; 176135048Swpaul}; 177135048Swpaul} // namespace 178145520Swpaul 179200533Syongarivoid DWARFCodegen::Visit(BinaryOpNode &binary, Node *&) { 180145520Swpaul Dispatch(binary.Left()); 181135048Swpaul Dispatch(binary.Right()); 182135048Swpaul 183135048Swpaul switch (binary.GetOpType()) { 184135048Swpaul case BinaryOpNode::Plus: 185135048Swpaul m_out_stream.PutHex8(DW_OP_plus); 186135048Swpaul // NOTE: can be optimized by using DW_OP_plus_uconst opcpode 187135048Swpaul // if right child node is constant value 188135048Swpaul break; 189135048Swpaul case BinaryOpNode::Minus: 190135048Swpaul m_out_stream.PutHex8(DW_OP_minus); 191135048Swpaul break; 192135048Swpaul case BinaryOpNode::Align: 193135048Swpaul // emit align operator a @ b as 194135048Swpaul // a & ~(b - 1) 195135048Swpaul // NOTE: implicitly assuming that b is power of 2 196135048Swpaul m_out_stream.PutHex8(DW_OP_lit1); 197135048Swpaul m_out_stream.PutHex8(DW_OP_minus); 198135048Swpaul m_out_stream.PutHex8(DW_OP_not); 199135048Swpaul 200135048Swpaul m_out_stream.PutHex8(DW_OP_and); 201135048Swpaul break; 202135048Swpaul } 203135048Swpaul --m_stack_depth; // Two pops, one push. 204135048Swpaul} 205135048Swpaul 206135048Swpaulvoid DWARFCodegen::Visit(InitialValueNode &, Node *&) { 207135048Swpaul // We never go below the initial stack, so we can pick the initial value from 208135048Swpaul // the bottom of the stack at any moment. 209135048Swpaul assert(m_stack_depth >= 1); 210135048Swpaul m_out_stream.PutHex8(DW_OP_pick); 211135048Swpaul m_out_stream.PutHex8(m_stack_depth - 1); 212135048Swpaul ++m_stack_depth; 213135048Swpaul} 214135048Swpaul 215135048Swpaulvoid DWARFCodegen::Visit(RegisterNode ®, Node *&) { 216135048Swpaul uint32_t reg_num = reg.GetRegNum(); 217135048Swpaul assert(reg_num != LLDB_INVALID_REGNUM); 218135048Swpaul 219135048Swpaul if (reg_num > 31) { 220135048Swpaul m_out_stream.PutHex8(DW_OP_bregx); 221135048Swpaul m_out_stream.PutULEB128(reg_num); 222135048Swpaul } else 223135048Swpaul m_out_stream.PutHex8(DW_OP_breg0 + reg_num); 224135048Swpaul 225135048Swpaul m_out_stream.PutSLEB128(0); 226145520Swpaul ++m_stack_depth; 227135048Swpaul} 228135048Swpaul 229135048Swpaulvoid DWARFCodegen::Visit(UnaryOpNode &unary, Node *&) { 230135048Swpaul Dispatch(unary.Operand()); 231200533Syongari 232135048Swpaul switch (unary.GetOpType()) { 233200536Syongari case UnaryOpNode::Deref: 234200536Syongari m_out_stream.PutHex8(DW_OP_deref); 235135048Swpaul break; 236135048Swpaul } 237135048Swpaul // Stack depth unchanged. 238135048Swpaul} 239135048Swpaul 240135048Swpaulbool postfix::ResolveSymbols( 241135048Swpaul Node *&node, llvm::function_ref<Node *(SymbolNode &)> replacer) { 242135048Swpaul return SymbolResolver(replacer).Dispatch(node); 243135048Swpaul} 244135048Swpaul 245135048Swpaulvoid postfix::ToDWARF(Node &node, Stream &stream) { 246135048Swpaul Node *ptr = &node; 247135048Swpaul DWARFCodegen(stream).Dispatch(ptr); 248135048Swpaul} 249135048Swpaul