1 /*
2 * Copyright (C) 2017 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 #pragma once
18
19 #if defined(__clang__)
20 #if __has_feature(cxx_rtti)
21 #define RTTI_ENABLED 1
22 #endif
23 #endif
24
25 #include "common.h"
26 #include "memview.h"
27 #include "dex_bytecode.h"
28 #include "dex_format.h"
29 #include "dex_ir.h"
30 #include "intrusive_list.h"
31
32 #include <assert.h>
33 #include <stdio.h>
34 #include <stdlib.h>
35
36 #include <algorithm>
37 #include <cstdint>
38 #include <list>
39 #include <map>
40 #include <memory>
41 #include <utility>
42 #include <vector>
43
44 namespace lir {
45
46 template <class T>
47 using own = std::unique_ptr<T>;
48
49 constexpr dex::u4 kInvalidOffset = dex::u4(-1);
50
51 struct Bytecode;
52 struct PackedSwitchPayload;
53 struct SparseSwitchPayload;
54 struct ArrayData;
55 struct Label;
56 struct TryBlockBegin;
57 struct TryBlockEnd;
58 struct Const32;
59 struct Const64;
60 struct VReg;
61 struct VRegPair;
62 struct VRegList;
63 struct VRegRange;
64 struct CodeLocation;
65 struct String;
66 struct Type;
67 struct Field;
68 struct Method;
69 struct DbgInfoHeader;
70 struct LineNumber;
71 struct DbgInfoAnnotation;
72
73 // Code IR visitor interface
74 class Visitor {
75 public:
76 Visitor() = default;
77 virtual ~Visitor() = default;
78
79 Visitor(const Visitor&) = delete;
80 Visitor& operator=(const Visitor&) = delete;
81
82 // instructions
Visit(Bytecode * bytecode)83 virtual bool Visit(Bytecode* bytecode) { return false; }
Visit(PackedSwitchPayload * packed_switch)84 virtual bool Visit(PackedSwitchPayload* packed_switch) { return false; }
Visit(SparseSwitchPayload * sparse_switch)85 virtual bool Visit(SparseSwitchPayload* sparse_switch) { return false; }
Visit(ArrayData * array_data)86 virtual bool Visit(ArrayData* array_data) { return false; }
Visit(Label * label)87 virtual bool Visit(Label* label) { return false; }
Visit(DbgInfoHeader * dbg_header)88 virtual bool Visit(DbgInfoHeader* dbg_header) { return false; }
Visit(DbgInfoAnnotation * dbg_annotation)89 virtual bool Visit(DbgInfoAnnotation* dbg_annotation) { return false; }
Visit(TryBlockBegin * try_begin)90 virtual bool Visit(TryBlockBegin* try_begin) { return false; }
Visit(TryBlockEnd * try_end)91 virtual bool Visit(TryBlockEnd* try_end) { return false; }
92
93 // operands
Visit(CodeLocation * location)94 virtual bool Visit(CodeLocation* location) { return false; }
Visit(Const32 * const32)95 virtual bool Visit(Const32* const32) { return false; }
Visit(Const64 * const64)96 virtual bool Visit(Const64* const64) { return false; }
Visit(VReg * vreg)97 virtual bool Visit(VReg* vreg) { return false; }
Visit(VRegPair * vreg_pair)98 virtual bool Visit(VRegPair* vreg_pair) { return false; }
Visit(VRegList * vreg_list)99 virtual bool Visit(VRegList* vreg_list) { return false; }
Visit(VRegRange * vreg_range)100 virtual bool Visit(VRegRange* vreg_range) { return false; }
Visit(String * string)101 virtual bool Visit(String* string) { return false; }
Visit(Type * type)102 virtual bool Visit(Type* type) { return false; }
Visit(Field * field)103 virtual bool Visit(Field* field) { return false; }
Visit(Method * method)104 virtual bool Visit(Method* method) { return false; }
Visit(LineNumber * line)105 virtual bool Visit(LineNumber* line) { return false; }
106 };
107
108 // The root of the polymorphic code IR nodes hierarchy
109 //
110 // NOTE: in general it's possible to "reuse" code IR nodes
111 // (ie. refcount > 1) although extra care is required since
112 // modifications to shared nodes will be visible in multiple places
113 // (notable exception: instruction nodes can't be reused)
114 //
115 struct Node {
116 Node() = default;
117 virtual ~Node() = default;
118
119 Node(const Node&) = delete;
120 Node& operator=(const Node&) = delete;
121
AcceptNode122 virtual bool Accept(Visitor* visitor) { return false; }
123 };
124
125 struct Operand : public Node {};
126
127 struct Const32 : public Operand {
128 union {
129 dex::s4 s4_value;
130 dex::u4 u4_value;
131 float float_value;
132 } u;
133
Const32Const32134 explicit Const32(dex::u4 value) { u.u4_value = value; }
135
AcceptConst32136 virtual bool Accept(Visitor* visitor) override { return visitor->Visit(this); }
137 };
138
139 struct Const64 : public Operand {
140 union {
141 dex::s8 s8_value;
142 dex::u8 u8_value;
143 double double_value;
144 } u;
145
Const64Const64146 explicit Const64(dex::u8 value) { u.u8_value = value; }
147
AcceptConst64148 virtual bool Accept(Visitor* visitor) override { return visitor->Visit(this); }
149 };
150
151 struct VReg : public Operand {
152 dex::u4 reg;
153
VRegVReg154 explicit VReg(dex::u4 reg) : reg(reg) {}
155
AcceptVReg156 virtual bool Accept(Visitor* visitor) override { return visitor->Visit(this); }
157 };
158
159 struct VRegPair : public Operand {
160 dex::u4 base_reg;
161
VRegPairVRegPair162 explicit VRegPair(dex::u4 base_reg) : base_reg(base_reg) {}
163
AcceptVRegPair164 virtual bool Accept(Visitor* visitor) override { return visitor->Visit(this); }
165 };
166
167 struct VRegList : public Operand {
168 std::vector<dex::u4> registers;
169
AcceptVRegList170 virtual bool Accept(Visitor* visitor) override { return visitor->Visit(this); }
171 };
172
173 struct VRegRange : public Operand {
174 dex::u4 base_reg;
175 int count;
176
VRegRangeVRegRange177 VRegRange(dex::u4 base_reg, int count) : base_reg(base_reg), count(count) {}
178
AcceptVRegRange179 virtual bool Accept(Visitor* visitor) override { return visitor->Visit(this); }
180 };
181
182 struct IndexedOperand : public Operand {
183 dex::u4 index;
184
IndexedOperandIndexedOperand185 explicit IndexedOperand(dex::u4 index) : index(index) {}
186 };
187
188 struct String : public IndexedOperand {
189 ir::String* ir_string;
190
StringString191 String(ir::String* ir_string, dex::u4 index) : IndexedOperand(index), ir_string(ir_string) {}
192
AcceptString193 virtual bool Accept(Visitor* visitor) override { return visitor->Visit(this); }
194 };
195
196 struct Type : public IndexedOperand {
197 ir::Type* ir_type;
198
TypeType199 Type(ir::Type* ir_type, dex::u4 index) : IndexedOperand(index), ir_type(ir_type) {}
200
AcceptType201 virtual bool Accept(Visitor* visitor) override { return visitor->Visit(this); }
202 };
203
204 struct Field : public IndexedOperand {
205 ir::FieldDecl* ir_field;
206
FieldField207 Field(ir::FieldDecl* ir_field, dex::u4 index) : IndexedOperand(index), ir_field(ir_field) {}
208
AcceptField209 virtual bool Accept(Visitor* visitor) override { return visitor->Visit(this); }
210 };
211
212 struct Method : public IndexedOperand {
213 ir::MethodDecl* ir_method;
214
MethodMethod215 Method(ir::MethodDecl* ir_method, dex::u4 index) : IndexedOperand(index), ir_method(ir_method) {}
216
AcceptMethod217 virtual bool Accept(Visitor* visitor) override { return visitor->Visit(this); }
218 };
219
220 struct CodeLocation : public Operand {
221 Label* label;
222
CodeLocationCodeLocation223 explicit CodeLocation(Label* label) : label(label) {}
224
AcceptCodeLocation225 virtual bool Accept(Visitor* visitor) override { return visitor->Visit(this); }
226 };
227
228 // Code IR is a linked list of Instructions
229 struct Instruction : public Node {
230 // absolute offset from the start of the method
231 dex::u4 offset = 0;
232
233 Instruction* prev = nullptr;
234 Instruction* next = nullptr;
235 };
236
237 using InstructionsList = slicer::IntrusiveList<Instruction>;
238
239 namespace detail {
240
241 template<class T>
CastOperand(Operand * op)242 inline T* CastOperand(Operand* op) {
243 #ifdef RTTI_ENABLED
244 T* operand = dynamic_cast<T*>(op);
245 SLICER_CHECK(operand != nullptr);
246 return operand;
247 #else
248 SLICER_CHECK(op != nullptr);
249 struct CastVisitor : public Visitor {
250 T* converted = nullptr;
251 bool Visit(T* val) override {
252 converted = val;
253 return true;
254 }
255 };
256 CastVisitor cv;
257 op->Accept(&cv);
258 SLICER_CHECK(cv.converted != nullptr);
259 return cv.converted;
260 #endif
261 }
262
263 // Special-case for IndexedOperand.
264 template<>
265 inline IndexedOperand* CastOperand<IndexedOperand>(Operand* op) {
266 #ifdef RTTI_ENABLED
267 IndexedOperand* operand = dynamic_cast<IndexedOperand*>(op);
268 SLICER_CHECK(operand != nullptr);
269 return operand;
270 #else
271 SLICER_CHECK(op != nullptr);
272 struct CastVisitor : public Visitor {
273 IndexedOperand* converted = nullptr;
274 bool Visit(String* val) override {
275 converted = val;
276 return true;
277 }
278 bool Visit(Type* val) override {
279 converted = val;
280 return true;
281 }
282 bool Visit(Field* val) override {
283 converted = val;
284 return true;
285 }
286 bool Visit(Method* val) override {
287 converted = val;
288 return true;
289 }
290 };
291 CastVisitor cv;
292 op->Accept(&cv);
293 SLICER_CHECK(cv.converted != nullptr);
294 return cv.converted;
295 #endif
296 }
297
298 } // namespace detail
299
300 struct Bytecode : public Instruction {
301 dex::Opcode opcode = dex::OP_NOP;
302 std::vector<Operand*> operands;
303
304 template<class T>
CastOperandBytecode305 T* CastOperand(int index) const {
306 return detail::CastOperand<T>(operands[index]);
307 }
308
AcceptBytecode309 virtual bool Accept(Visitor* visitor) override { return visitor->Visit(this); }
310 };
311
312 struct PackedSwitchPayload : public Instruction {
313 dex::s4 first_key = 0;
314 std::vector<Label*> targets;
315
AcceptPackedSwitchPayload316 virtual bool Accept(Visitor* visitor) override { return visitor->Visit(this); }
317 };
318
319 struct SparseSwitchPayload : public Instruction {
320 struct SwitchCase {
321 dex::s4 key = 0;
322 Label* target = nullptr;
323 };
324
325 std::vector<SwitchCase> switch_cases;
326
AcceptSparseSwitchPayload327 virtual bool Accept(Visitor* visitor) override { return visitor->Visit(this); }
328 };
329
330 struct ArrayData : public Instruction {
331 slicer::MemView data;
332
AcceptArrayData333 virtual bool Accept(Visitor* visitor) override { return visitor->Visit(this); }
334 };
335
336 struct Label : public Instruction {
337 int id = 0;
338 int refCount = 0;
339 bool aligned = false;
340
LabelLabel341 explicit Label(dex::u4 offset) { this->offset = offset; }
342
AcceptLabel343 virtual bool Accept(Visitor* visitor) override { return visitor->Visit(this); }
344 };
345
346 struct TryBlockBegin : public Instruction {
347 int id = 0;
348
AcceptTryBlockBegin349 virtual bool Accept(Visitor* visitor) override { return visitor->Visit(this); }
350 };
351
352 struct CatchHandler {
353 ir::Type* ir_type = nullptr;
354 Label* label = nullptr;
355 };
356
357 struct TryBlockEnd : public Instruction {
358 TryBlockBegin* try_begin = nullptr;
359 std::vector<CatchHandler> handlers;
360 Label* catch_all = nullptr;
361
AcceptTryBlockEnd362 virtual bool Accept(Visitor* visitor) override { return visitor->Visit(this); }
363 };
364
365 struct DbgInfoHeader : public Instruction {
366 std::vector<ir::String*> param_names;
367
AcceptDbgInfoHeader368 virtual bool Accept(Visitor* visitor) override { return visitor->Visit(this); }
369 };
370
371 struct LineNumber : public Operand {
372 int line = 0;
373
LineNumberLineNumber374 explicit LineNumber(int line) : line(line) {
375 SLICER_WEAK_CHECK(line > 0);
376 }
377
AcceptLineNumber378 virtual bool Accept(Visitor* visitor) override { return visitor->Visit(this); }
379 };
380
381 struct DbgInfoAnnotation : public Instruction {
382 dex::u1 dbg_opcode = 0;
383 std::vector<Operand*> operands;
384
DbgInfoAnnotationDbgInfoAnnotation385 explicit DbgInfoAnnotation(dex::u1 dbg_opcode) : dbg_opcode(dbg_opcode) {}
386
387 template<class T>
CastOperandDbgInfoAnnotation388 T* CastOperand(int index) const {
389 return detail::CastOperand<T>(operands[index]);
390 }
391
AcceptDbgInfoAnnotation392 virtual bool Accept(Visitor* visitor) override { return visitor->Visit(this); }
393 };
394
395 // Code IR container and manipulation interface
396 struct CodeIr {
397 // linked list of the method's instructions
398 InstructionsList instructions;
399
400 ir::EncodedMethod* ir_method = nullptr;
401 std::shared_ptr<ir::DexFile> dex_ir;
402
403 public:
CodeIrCodeIr404 CodeIr(ir::EncodedMethod* ir_method, std::shared_ptr<ir::DexFile> dex_ir)
405 : ir_method(ir_method), dex_ir(dex_ir) {
406 Dissasemble();
407 }
408
409 // No copy/move semantics
410 CodeIr(const CodeIr&) = delete;
411 CodeIr& operator=(const CodeIr&) = delete;
412
413 void Assemble();
414
AcceptCodeIr415 void Accept(Visitor* visitor) {
416 for (auto instr : instructions) {
417 instr->Accept(visitor);
418 }
419 }
420
421 template <class T, class... Args>
AllocCodeIr422 T* Alloc(Args&&... args) {
423 auto p = new T(std::forward<Args>(args)...);
424 nodes_.push_back(own<T>(p));
425 return p;
426 }
427
428 private:
429 void Dissasemble();
430 void DissasembleBytecode(const ir::Code* ir_code);
431 void DissasembleTryBlocks(const ir::Code* ir_code);
432 void DissasembleDebugInfo(const ir::DebugInfo* ir_debug_info);
433
434 void FixupSwitches();
435 void FixupPackedSwitch(PackedSwitchPayload* instr, dex::u4 base_offset, const dex::u2* ptr);
436 void FixupSparseSwitch(SparseSwitchPayload* instr, dex::u4 base_offset, const dex::u2* ptr);
437
438 SparseSwitchPayload* DecodeSparseSwitch(const dex::u2* /*ptr*/, dex::u4 offset);
439 PackedSwitchPayload* DecodePackedSwitch(const dex::u2* /*ptr*/, dex::u4 offset);
440 ArrayData* DecodeArrayData(const dex::u2* ptr, dex::u4 offset);
441 Bytecode* DecodeBytecode(const dex::u2* ptr, dex::u4 offset);
442
443 IndexedOperand* GetIndexedOperand(dex::InstructionIndexType index_type, dex::u4 index);
444
445 Type* GetType(dex::u4 index);
446 String* GetString(dex::u4 index);
447 Label* GetLabel(dex::u4 offset);
448
449 Operand* GetRegA(const dex::Instruction& dex_instr);
450 Operand* GetRegB(const dex::Instruction& dex_instr);
451 Operand* GetRegC(const dex::Instruction& dex_instr);
452
453 private:
454 // the "master index" of all the LIR owned nodes
455 std::vector<own<Node>> nodes_;
456
457 // data structures for fixing up switch payloads
458 struct PackedSwitchFixup {
459 PackedSwitchPayload* instr = nullptr;
460 dex::u4 base_offset = kInvalidOffset;
461 };
462
463 struct SparseSwitchFixup {
464 SparseSwitchPayload* instr = nullptr;
465 dex::u4 base_offset = kInvalidOffset;
466 };
467
468 // used during bytecode raising
469 std::map<dex::u4, Label*> labels_;
470 std::map<dex::u4, PackedSwitchFixup> packed_switches_;
471 std::map<dex::u4, SparseSwitchFixup> sparse_switches_;
472
473 // extra instructions/annotations created during raising
474 // (intended to be merged in with the main instruction
475 // list at end of the IR raising phase)
476 std::vector<TryBlockBegin*> try_begins_;
477 std::vector<TryBlockEnd*> try_ends_;
478 std::vector<Instruction*> dbg_annotations_;
479 };
480
481 } // namespace lir
482