1 //===-- PDBFPOProgramToDWARFExpression.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 #include "PdbFPOProgramToDWARFExpression.h"
10 #include "CodeViewRegisterMapping.h"
11 
12 #include "lldb/Core/StreamBuffer.h"
13 #include "lldb/Core/dwarf.h"
14 #include "lldb/Symbol/PostfixExpression.h"
15 #include "lldb/Utility/LLDBAssert.h"
16 #include "lldb/Utility/Stream.h"
17 #include "llvm/ADT/DenseMap.h"
18 
19 #include "llvm/ADT/StringExtras.h"
20 #include "llvm/DebugInfo/CodeView/CodeView.h"
21 #include "llvm/DebugInfo/CodeView/EnumTables.h"
22 
23 using namespace lldb;
24 using namespace lldb_private;
25 using namespace lldb_private::postfix;
26 
27 namespace {
28 
29 class FPOProgramASTVisitorMergeDependent : public Visitor<> {
30 public:
31   void Visit(BinaryOpNode &binary, Node *&) override {
32     Dispatch(binary.Left());
33     Dispatch(binary.Right());
34   }
35 
36   void Visit(UnaryOpNode &unary, Node *&) override {
37     Dispatch(unary.Operand());
38   }
39 
40   void Visit(RegisterNode &, Node *&) override {}
41   void Visit(IntegerNode &, Node *&) override {}
42   void Visit(SymbolNode &symbol, Node *&ref) override;
43 
44   static void
45   Merge(const llvm::DenseMap<llvm::StringRef, Node *> &dependent_programs,
46         Node *&ast) {
47     FPOProgramASTVisitorMergeDependent(dependent_programs).Dispatch(ast);
48   }
49 
50 private:
51   FPOProgramASTVisitorMergeDependent(
52       const llvm::DenseMap<llvm::StringRef, Node *> &dependent_programs)
53       : m_dependent_programs(dependent_programs) {}
54 
55   const llvm::DenseMap<llvm::StringRef, Node *> &m_dependent_programs;
56 };
57 
58 void FPOProgramASTVisitorMergeDependent::Visit(SymbolNode &symbol, Node *&ref) {
59   auto it = m_dependent_programs.find(symbol.GetName());
60   if (it == m_dependent_programs.end())
61     return;
62 
63   ref = it->second;
64   Dispatch(ref);
65 }
66 
67 class FPOProgramASTVisitorResolveRegisterRefs : public Visitor<bool> {
68 public:
69   static bool
70   Resolve(const llvm::DenseMap<llvm::StringRef, Node *> &dependent_programs,
71           llvm::Triple::ArchType arch_type, llvm::BumpPtrAllocator &alloc,
72           Node *&ast) {
73     return FPOProgramASTVisitorResolveRegisterRefs(dependent_programs,
74                                                    arch_type, alloc)
75         .Dispatch(ast);
76   }
77 
78   bool Visit(BinaryOpNode &binary, Node *&) override {
79     return Dispatch(binary.Left()) && Dispatch(binary.Right());
80   }
81 
82   bool Visit(UnaryOpNode &unary, Node *&) override {
83     return Dispatch(unary.Operand());
84   }
85 
86   bool Visit(RegisterNode &, Node *&) override { return true; }
87 
88   bool Visit(IntegerNode &, Node *&) override { return true; }
89 
90   bool Visit(SymbolNode &symbol, Node *&ref) override;
91 
92 private:
93   FPOProgramASTVisitorResolveRegisterRefs(
94       const llvm::DenseMap<llvm::StringRef, Node *> &dependent_programs,
95       llvm::Triple::ArchType arch_type, llvm::BumpPtrAllocator &alloc)
96       : m_dependent_programs(dependent_programs), m_arch_type(arch_type),
97         m_alloc(alloc) {}
98 
99   const llvm::DenseMap<llvm::StringRef, Node *> &m_dependent_programs;
100   llvm::Triple::ArchType m_arch_type;
101   llvm::BumpPtrAllocator &m_alloc;
102 };
103 
104 static uint32_t ResolveLLDBRegisterNum(llvm::StringRef reg_name, llvm::Triple::ArchType arch_type) {
105   // lookup register name to get lldb register number
106   llvm::ArrayRef<llvm::EnumEntry<uint16_t>> register_names =
107       llvm::codeview::getRegisterNames();
108   auto it = llvm::find_if(
109       register_names,
110       [&reg_name](const llvm::EnumEntry<uint16_t> &register_entry) {
111         return reg_name.compare_lower(register_entry.Name) == 0;
112       });
113 
114   if (it == register_names.end())
115     return LLDB_INVALID_REGNUM;
116 
117   auto reg_id = static_cast<llvm::codeview::RegisterId>(it->Value);
118   return npdb::GetLLDBRegisterNumber(arch_type, reg_id);
119 }
120 
121 bool FPOProgramASTVisitorResolveRegisterRefs::Visit(SymbolNode &symbol,
122                                                     Node *&ref) {
123   // Look up register reference as lvalue in preceding assignments.
124   auto it = m_dependent_programs.find(symbol.GetName());
125   if (it != m_dependent_programs.end()) {
126     // Dependent programs are handled elsewhere.
127     return true;
128   }
129 
130   uint32_t reg_num =
131       ResolveLLDBRegisterNum(symbol.GetName().drop_front(1), m_arch_type);
132 
133   if (reg_num == LLDB_INVALID_REGNUM)
134     return false;
135 
136   ref = MakeNode<RegisterNode>(m_alloc, reg_num);
137   return true;
138 }
139 
140 class FPOProgramASTVisitorDWARFCodegen : public Visitor<> {
141 public:
142   static void Emit(Stream &stream, Node *&ast) {
143     FPOProgramASTVisitorDWARFCodegen(stream).Dispatch(ast);
144   }
145 
146   void Visit(RegisterNode &reg, Node *&);
147   void Visit(BinaryOpNode &binary, Node *&);
148   void Visit(UnaryOpNode &unary, Node *&);
149   void Visit(SymbolNode &symbol, Node *&) {
150     llvm_unreachable("Symbols should have been resolved by now!");
151   }
152   void Visit(IntegerNode &integer, Node *&);
153 
154 private:
155   FPOProgramASTVisitorDWARFCodegen(Stream &stream) : m_out_stream(stream) {}
156 
157   Stream &m_out_stream;
158 };
159 
160 void FPOProgramASTVisitorDWARFCodegen::Visit(RegisterNode &reg, Node *&) {
161   uint32_t reg_num = reg.GetRegNum();
162   lldbassert(reg_num != LLDB_INVALID_REGNUM);
163 
164   if (reg_num > 31) {
165     m_out_stream.PutHex8(DW_OP_bregx);
166     m_out_stream.PutULEB128(reg_num);
167   } else
168     m_out_stream.PutHex8(DW_OP_breg0 + reg_num);
169 
170   m_out_stream.PutSLEB128(0);
171 }
172 
173 void FPOProgramASTVisitorDWARFCodegen::Visit(IntegerNode &integer, Node *&) {
174   uint32_t value = integer.GetValue();
175   m_out_stream.PutHex8(DW_OP_constu);
176   m_out_stream.PutULEB128(value);
177 }
178 
179 void FPOProgramASTVisitorDWARFCodegen::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 }
204 
205 void FPOProgramASTVisitorDWARFCodegen::Visit(UnaryOpNode &unary, Node *&) {
206   Dispatch(unary.Operand());
207 
208   switch (unary.GetOpType()) {
209   case UnaryOpNode::Deref:
210     m_out_stream.PutHex8(DW_OP_deref);
211     break;
212   }
213 }
214 
215 } // namespace
216 
217 static bool ParseFPOSingleAssignmentProgram(llvm::StringRef program,
218                                             llvm::BumpPtrAllocator &alloc,
219                                             llvm::StringRef &register_name,
220                                             Node *&ast) {
221   // lvalue of assignment is always first token
222   // rvalue program goes next
223   std::tie(register_name, program) = getToken(program);
224   if (register_name.empty())
225     return false;
226 
227   ast = Parse(program, alloc);
228   return ast != nullptr;
229 }
230 
231 static Node *ParseFPOProgram(llvm::StringRef program,
232                              llvm::StringRef register_name,
233                              llvm::Triple::ArchType arch_type,
234                              llvm::BumpPtrAllocator &alloc) {
235   llvm::DenseMap<llvm::StringRef, Node *> dependent_programs;
236 
237   size_t cur = 0;
238   while (true) {
239     size_t assign_index = program.find('=', cur);
240     if (assign_index == llvm::StringRef::npos) {
241       llvm::StringRef tail = program.slice(cur, llvm::StringRef::npos);
242       if (!tail.trim().empty()) {
243         // missing assign operator
244         return nullptr;
245       }
246       break;
247     }
248     llvm::StringRef assignment_program = program.slice(cur, assign_index);
249 
250     llvm::StringRef lvalue_name;
251     Node *rvalue_ast = nullptr;
252     if (!ParseFPOSingleAssignmentProgram(assignment_program, alloc, lvalue_name,
253                                          rvalue_ast)) {
254       return nullptr;
255     }
256 
257     lldbassert(rvalue_ast);
258 
259     // check & resolve assignment program
260     if (!FPOProgramASTVisitorResolveRegisterRefs::Resolve(
261             dependent_programs, arch_type, alloc, rvalue_ast))
262       return nullptr;
263 
264     if (lvalue_name == register_name) {
265       // found target assignment program - no need to parse further
266 
267       // emplace valid dependent subtrees to make target assignment independent
268       // from predecessors
269       FPOProgramASTVisitorMergeDependent::Merge(dependent_programs, rvalue_ast);
270 
271       return rvalue_ast;
272     }
273 
274     dependent_programs[lvalue_name] = rvalue_ast;
275     cur = assign_index + 1;
276   }
277 
278   return nullptr;
279 }
280 
281 bool lldb_private::npdb::TranslateFPOProgramToDWARFExpression(
282     llvm::StringRef program, llvm::StringRef register_name,
283     llvm::Triple::ArchType arch_type, Stream &stream) {
284   llvm::BumpPtrAllocator node_alloc;
285   Node *target_program =
286       ParseFPOProgram(program, register_name, arch_type, node_alloc);
287   if (target_program == nullptr) {
288     return false;
289   }
290 
291   FPOProgramASTVisitorDWARFCodegen::Emit(stream, target_program);
292   return true;
293 }
294