1 | //===-- PostfixExpression.h -------------------------------------*- 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 | #ifndef LLDB_SYMBOL_POSTFIXEXPRESSION_H |
15 | #define LLDB_SYMBOL_POSTFIXEXPRESSION_H |
16 | |
17 | #include "llvm/ADT/StringRef.h" |
18 | #include "llvm/Support/Allocator.h" |
19 | #include "llvm/Support/Casting.h" |
20 | #include <vector> |
21 | |
22 | namespace lldb_private { |
23 | |
24 | class Stream; |
25 | |
26 | namespace postfix { |
27 | |
28 | /// The base class for all nodes in the parsed postfix tree. |
29 | class Node { |
30 | public: |
31 | enum Kind { |
32 | BinaryOp, |
33 | InitialValue, |
34 | Integer, |
35 | Register, |
36 | Symbol, |
37 | UnaryOp, |
38 | }; |
39 | |
40 | protected: |
41 | Node(Kind kind) : m_kind(kind) {} |
42 | |
43 | public: |
44 | Kind GetKind() const { return m_kind; } |
45 | |
46 | private: |
47 | Kind m_kind; |
48 | }; |
49 | |
50 | /// A node representing a binary expression. |
51 | class BinaryOpNode : public Node { |
52 | public: |
53 | enum OpType { |
54 | Align, // alignDown(a, b) |
55 | Minus, // a - b |
56 | Plus, // a + b |
57 | }; |
58 | |
59 | BinaryOpNode(OpType op_type, Node &left, Node &right) |
60 | : Node(BinaryOp), m_op_type(op_type), m_left(&left), m_right(&right) {} |
61 | |
62 | OpType GetOpType() const { return m_op_type; } |
63 | |
64 | const Node *Left() const { return m_left; } |
65 | Node *&Left() { return m_left; } |
66 | |
67 | const Node *Right() const { return m_right; } |
68 | Node *&Right() { return m_right; } |
69 | |
70 | static bool classof(const Node *node) { return node->GetKind() == BinaryOp; } |
71 | |
72 | private: |
73 | OpType m_op_type; |
74 | Node *m_left; |
75 | Node *m_right; |
76 | }; |
77 | |
78 | /// A node representing the canonical frame address. |
79 | class InitialValueNode: public Node { |
80 | public: |
81 | InitialValueNode() : Node(InitialValue) {} |
82 | |
83 | static bool classof(const Node *node) { |
84 | return node->GetKind() == InitialValue; |
85 | } |
86 | }; |
87 | |
88 | /// A node representing an integer literal. |
89 | class IntegerNode : public Node { |
90 | public: |
91 | IntegerNode(int64_t value) : Node(Integer), m_value(value) {} |
92 | |
93 | int64_t GetValue() const { return m_value; } |
94 | |
95 | static bool classof(const Node *node) { return node->GetKind() == Integer; } |
96 | |
97 | private: |
98 | int64_t m_value; |
99 | }; |
100 | |
101 | /// A node representing the value of a register with the given register number. |
102 | /// The register kind (RegisterKind enum) used for the specifying the register |
103 | /// number is implicit and assumed to be the same for all Register nodes in a |
104 | /// given tree. |
105 | class RegisterNode : public Node { |
106 | public: |
107 | RegisterNode(uint32_t reg_num) : Node(Register), m_reg_num(reg_num) {} |
108 | |
109 | uint32_t GetRegNum() const { return m_reg_num; } |
110 | |
111 | static bool classof(const Node *node) { return node->GetKind() == Register; } |
112 | |
113 | private: |
114 | uint32_t m_reg_num; |
115 | }; |
116 | |
117 | /// A node representing a symbolic reference to a named entity. This may be a |
118 | /// register, which hasn't yet been resolved to a RegisterNode. |
119 | class SymbolNode : public Node { |
120 | public: |
121 | SymbolNode(llvm::StringRef name) : Node(Symbol), m_name(name) {} |
122 | |
123 | llvm::StringRef GetName() const { return m_name; } |
124 | |
125 | static bool classof(const Node *node) { return node->GetKind() == Symbol; } |
126 | |
127 | private: |
128 | llvm::StringRef m_name; |
129 | }; |
130 | |
131 | /// A node representing a unary operation. |
132 | class UnaryOpNode : public Node { |
133 | public: |
134 | enum OpType { |
135 | Deref, // *a |
136 | }; |
137 | |
138 | UnaryOpNode(OpType op_type, Node &operand) |
139 | : Node(UnaryOp), m_op_type(op_type), m_operand(&operand) {} |
140 | |
141 | OpType GetOpType() const { return m_op_type; } |
142 | |
143 | const Node *Operand() const { return m_operand; } |
144 | Node *&Operand() { return m_operand; } |
145 | |
146 | static bool classof(const Node *node) { return node->GetKind() == UnaryOp; } |
147 | |
148 | private: |
149 | OpType m_op_type; |
150 | Node *m_operand; |
151 | }; |
152 | |
153 | /// A template class implementing a visitor pattern, but with a couple of |
154 | /// twists: |
155 | /// - It uses type switch instead of virtual double dispatch. This allows the |
156 | // node classes to be vtable-free and trivially destructible. |
157 | /// - The Visit functions get an extra Node *& parameter, which refers to the |
158 | /// child pointer of the parent of the node we are currently visiting. This |
159 | /// allows mutating algorithms, which replace the currently visited node with |
160 | /// a different one. |
161 | /// - The class is templatized on the return type of the Visit functions, which |
162 | /// means it's possible to return values from them. |
163 | template <typename ResultT = void> class Visitor { |
164 | protected: |
165 | virtual ~Visitor() = default; |
166 | |
167 | virtual ResultT Visit(BinaryOpNode &binary, Node *&ref) = 0; |
168 | virtual ResultT Visit(InitialValueNode &val, Node *&ref) = 0; |
169 | virtual ResultT Visit(IntegerNode &integer, Node *&) = 0; |
170 | virtual ResultT Visit(RegisterNode ®, Node *&) = 0; |
171 | virtual ResultT Visit(SymbolNode &symbol, Node *&ref) = 0; |
172 | virtual ResultT Visit(UnaryOpNode &unary, Node *&ref) = 0; |
173 | |
174 | /// Invoke the correct Visit function based on the dynamic type of the given |
175 | /// node. |
176 | ResultT Dispatch(Node *&node) { |
177 | switch (node->GetKind()) { |
178 | case Node::BinaryOp: |
179 | return Visit(llvm::cast<BinaryOpNode>(Val&: *node), node); |
180 | case Node::InitialValue: |
181 | return Visit(llvm::cast<InitialValueNode>(Val&: *node), node); |
182 | case Node::Integer: |
183 | return Visit(llvm::cast<IntegerNode>(Val&: *node), node); |
184 | case Node::Register: |
185 | return Visit(llvm::cast<RegisterNode>(Val&: *node), node); |
186 | case Node::Symbol: |
187 | return Visit(llvm::cast<SymbolNode>(Val&: *node), node); |
188 | case Node::UnaryOp: |
189 | return Visit(llvm::cast<UnaryOpNode>(Val&: *node), node); |
190 | } |
191 | llvm_unreachable("Fully covered switch!" ); |
192 | } |
193 | }; |
194 | |
195 | /// A utility function for "resolving" SymbolNodes. It traverses a tree and |
196 | /// calls the callback function for all SymbolNodes it encountered. The |
197 | /// replacement function should return the node it wished to replace the current |
198 | /// SymbolNode with (this can also be the original node), or nullptr in case of |
199 | /// an error. The nodes returned by the callback are inspected and replaced |
200 | /// recursively, *except* for the case when the function returns the exact same |
201 | /// node as the input one. It returns true if all SymbolNodes were replaced |
202 | /// successfully. |
203 | bool ResolveSymbols(Node *&node, |
204 | llvm::function_ref<Node *(SymbolNode &symbol)> replacer); |
205 | |
206 | template <typename T, typename... Args> |
207 | inline T *MakeNode(llvm::BumpPtrAllocator &alloc, Args &&... args) { |
208 | static_assert(std::is_trivially_destructible<T>::value, |
209 | "This object will not be destroyed!" ); |
210 | return new (alloc.Allocate<T>()) T(std::forward<Args>(args)...); |
211 | } |
212 | |
213 | /// Parse the given postfix expression. The parsed nodes are placed into the |
214 | /// provided allocator. |
215 | Node *ParseOneExpression(llvm::StringRef expr, llvm::BumpPtrAllocator &alloc); |
216 | |
217 | std::vector<std::pair<llvm::StringRef, Node *>> |
218 | ParseFPOProgram(llvm::StringRef prog, llvm::BumpPtrAllocator &alloc); |
219 | |
220 | /// Serialize the given expression tree as DWARF. The result is written into the |
221 | /// given stream. The AST should not contain any SymbolNodes. If the expression |
222 | /// contains InitialValueNodes, the generated expression will assume that their |
223 | /// value will be provided as the top value of the initial evaluation stack (as |
224 | /// is the case with the CFA value in register eh_unwind rules). |
225 | void ToDWARF(Node &node, Stream &stream); |
226 | |
227 | } // namespace postfix |
228 | } // namespace lldb_private |
229 | |
230 | #endif // LLDB_SYMBOL_POSTFIXEXPRESSION_H |
231 | |