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 Proto;
70 struct DbgInfoHeader;
71 struct LineNumber;
72 struct DbgInfoAnnotation;
73
74 // Code IR visitor interface
75 class Visitor {
76 public:
77 Visitor() = default;
78 virtual ~Visitor() = default;
79
80 Visitor(const Visitor&) = delete;
81 Visitor& operator=(const Visitor&) = delete;
82
83 // instructions
Visit(Bytecode * bytecode)84 virtual bool Visit(Bytecode* bytecode) { return false; }
Visit(PackedSwitchPayload * packed_switch)85 virtual bool Visit(PackedSwitchPayload* packed_switch) { return false; }
Visit(SparseSwitchPayload * sparse_switch)86 virtual bool Visit(SparseSwitchPayload* sparse_switch) { return false; }
Visit(ArrayData * array_data)87 virtual bool Visit(ArrayData* array_data) { return false; }
Visit(Label * label)88 virtual bool Visit(Label* label) { return false; }
Visit(DbgInfoHeader * dbg_header)89 virtual bool Visit(DbgInfoHeader* dbg_header) { return false; }
Visit(DbgInfoAnnotation * dbg_annotation)90 virtual bool Visit(DbgInfoAnnotation* dbg_annotation) { return false; }
Visit(TryBlockBegin * try_begin)91 virtual bool Visit(TryBlockBegin* try_begin) { return false; }
Visit(TryBlockEnd * try_end)92 virtual bool Visit(TryBlockEnd* try_end) { return false; }
93
94 // operands
Visit(CodeLocation * location)95 virtual bool Visit(CodeLocation* location) { return false; }
Visit(Const32 * const32)96 virtual bool Visit(Const32* const32) { return false; }
Visit(Const64 * const64)97 virtual bool Visit(Const64* const64) { return false; }
Visit(VReg * vreg)98 virtual bool Visit(VReg* vreg) { return false; }
Visit(VRegPair * vreg_pair)99 virtual bool Visit(VRegPair* vreg_pair) { return false; }
Visit(VRegList * vreg_list)100 virtual bool Visit(VRegList* vreg_list) { return false; }
Visit(VRegRange * vreg_range)101 virtual bool Visit(VRegRange* vreg_range) { return false; }
Visit(String * string)102 virtual bool Visit(String* string) { return false; }
Visit(Type * type)103 virtual bool Visit(Type* type) { return false; }
Visit(Field * field)104 virtual bool Visit(Field* field) { return false; }
Visit(Method * method)105 virtual bool Visit(Method* method) { return false; }
Visit(Proto * proto)106 virtual bool Visit(Proto* proto) { return false; }
Visit(LineNumber * line)107 virtual bool Visit(LineNumber* line) { return false; }
108 };
109
110 // The root of the polymorphic code IR nodes hierarchy
111 //
112 // NOTE: in general it's possible to "reuse" code IR nodes
113 // (ie. refcount > 1) although extra care is required since
114 // modifications to shared nodes will be visible in multiple places
115 // (notable exception: instruction nodes can't be reused)
116 //
117 struct Node {
118 Node() = default;
119 virtual ~Node() = default;
120
121 Node(const Node&) = delete;
122 Node& operator=(const Node&) = delete;
123
AcceptNode124 virtual bool Accept(Visitor* visitor) { return false; }
125 };
126
127 struct Operand : public Node {};
128
129 struct Const32 : public Operand {
130 union {
131 dex::s4 s4_value;
132 dex::u4 u4_value;
133 float float_value;
134 } u;
135
Const32Const32136 explicit Const32(dex::u4 value) { u.u4_value = value; }
137
AcceptConst32138 virtual bool Accept(Visitor* visitor) override { return visitor->Visit(this); }
139 };
140
141 struct Const64 : public Operand {
142 union {
143 dex::s8 s8_value;
144 dex::u8 u8_value;
145 double double_value;
146 } u;
147
Const64Const64148 explicit Const64(dex::u8 value) { u.u8_value = value; }
149
AcceptConst64150 virtual bool Accept(Visitor* visitor) override { return visitor->Visit(this); }
151 };
152
153 struct VReg : public Operand {
154 dex::u4 reg;
155
VRegVReg156 explicit VReg(dex::u4 reg) : reg(reg) {}
157
AcceptVReg158 virtual bool Accept(Visitor* visitor) override { return visitor->Visit(this); }
159 };
160
161 struct VRegPair : public Operand {
162 dex::u4 base_reg;
163
VRegPairVRegPair164 explicit VRegPair(dex::u4 base_reg) : base_reg(base_reg) {}
165
AcceptVRegPair166 virtual bool Accept(Visitor* visitor) override { return visitor->Visit(this); }
167 };
168
169 struct VRegList : public Operand {
170 std::vector<dex::u4> registers;
171
AcceptVRegList172 virtual bool Accept(Visitor* visitor) override { return visitor->Visit(this); }
173 };
174
175 struct VRegRange : public Operand {
176 dex::u4 base_reg;
177 int count;
178
VRegRangeVRegRange179 VRegRange(dex::u4 base_reg, int count) : base_reg(base_reg), count(count) {}
180
AcceptVRegRange181 virtual bool Accept(Visitor* visitor) override { return visitor->Visit(this); }
182 };
183
184 struct IndexedOperand : public Operand {
185 dex::u4 index;
186
IndexedOperandIndexedOperand187 explicit IndexedOperand(dex::u4 index) : index(index) {}
188 };
189
190 struct String : public IndexedOperand {
191 ir::String* ir_string;
192
StringString193 String(ir::String* ir_string, dex::u4 index) : IndexedOperand(index), ir_string(ir_string) {}
194
AcceptString195 virtual bool Accept(Visitor* visitor) override { return visitor->Visit(this); }
196 };
197
198 struct Type : public IndexedOperand {
199 ir::Type* ir_type;
200
TypeType201 Type(ir::Type* ir_type, dex::u4 index) : IndexedOperand(index), ir_type(ir_type) {}
202
AcceptType203 virtual bool Accept(Visitor* visitor) override { return visitor->Visit(this); }
204 };
205
206 struct Field : public IndexedOperand {
207 ir::FieldDecl* ir_field;
208
FieldField209 Field(ir::FieldDecl* ir_field, dex::u4 index) : IndexedOperand(index), ir_field(ir_field) {}
210
AcceptField211 virtual bool Accept(Visitor* visitor) override { return visitor->Visit(this); }
212 };
213
214 struct Method : public IndexedOperand {
215 ir::MethodDecl* ir_method;
216
MethodMethod217 Method(ir::MethodDecl* ir_method, dex::u4 index) : IndexedOperand(index), ir_method(ir_method) {
218 SLICER_CHECK_NE(ir_method, nullptr);
219 }
220
AcceptMethod221 virtual bool Accept(Visitor* visitor) override { return visitor->Visit(this); }
222 };
223
224 struct Proto : public IndexedOperand {
225 ir::Proto* ir_proto;
226
ProtoProto227 Proto(ir::Proto* ir_proto, dex::u4 index) : IndexedOperand(index), ir_proto(ir_proto) {}
228
AcceptProto229 virtual bool Accept(Visitor* visitor) override { return visitor->Visit(this); }
230 };
231
232 struct CodeLocation : public Operand {
233 Label* label;
234
CodeLocationCodeLocation235 explicit CodeLocation(Label* label) : label(label) {}
236
AcceptCodeLocation237 virtual bool Accept(Visitor* visitor) override { return visitor->Visit(this); }
238 };
239
240 // Code IR is a linked list of Instructions
241 struct Instruction : public Node {
242 // absolute offset from the start of the method
243 dex::u4 offset = 0;
244
245 Instruction* prev = nullptr;
246 Instruction* next = nullptr;
247 };
248
249 using InstructionsList = slicer::IntrusiveList<Instruction>;
250
251 namespace detail {
252
253 template<class T>
CastOperand(Operand * op)254 inline T* CastOperand(Operand* op) {
255 #ifdef RTTI_ENABLED
256 T* operand = dynamic_cast<T*>(op);
257 SLICER_CHECK_NE(operand, nullptr);
258 return operand;
259 #else
260 SLICER_CHECK_NE(op, nullptr);
261 struct CastVisitor : public Visitor {
262 T* converted = nullptr;
263 bool Visit(T* val) override {
264 converted = val;
265 return true;
266 }
267 };
268 CastVisitor cv;
269 op->Accept(&cv);
270 SLICER_CHECK_NE(cv.converted, nullptr);
271 return cv.converted;
272 #endif
273 }
274
275 // Special-case for IndexedOperand.
276 template<>
277 inline IndexedOperand* CastOperand<IndexedOperand>(Operand* op) {
278 #ifdef RTTI_ENABLED
279 IndexedOperand* operand = dynamic_cast<IndexedOperand*>(op);
280 SLICER_CHECK_NE(operand, nullptr);
281 return operand;
282 #else
283 SLICER_CHECK_NE(op, nullptr);
284 struct CastVisitor : public Visitor {
285 IndexedOperand* converted = nullptr;
286 bool Visit(String* val) override {
287 converted = val;
288 return true;
289 }
290 bool Visit(Type* val) override {
291 converted = val;
292 return true;
293 }
294 bool Visit(Field* val) override {
295 converted = val;
296 return true;
297 }
298 bool Visit(Method* val) override {
299 converted = val;
300 return true;
301 }
302 };
303 CastVisitor cv;
304 op->Accept(&cv);
305 SLICER_CHECK_NE(cv.converted, nullptr);
306 return cv.converted;
307 #endif
308 }
309
310 } // namespace detail
311
312 struct Bytecode : public Instruction {
313 dex::Opcode opcode = dex::OP_NOP;
314 std::vector<Operand*> operands;
315
316 template<class T>
CastOperandBytecode317 T* CastOperand(int index) const {
318 return detail::CastOperand<T>(operands[index]);
319 }
320
AcceptBytecode321 virtual bool Accept(Visitor* visitor) override { return visitor->Visit(this); }
322 };
323
324 struct PackedSwitchPayload : public Instruction {
325 dex::s4 first_key = 0;
326 std::vector<Label*> targets;
327
AcceptPackedSwitchPayload328 virtual bool Accept(Visitor* visitor) override { return visitor->Visit(this); }
329 };
330
331 struct SparseSwitchPayload : public Instruction {
332 struct SwitchCase {
333 dex::s4 key = 0;
334 Label* target = nullptr;
335 };
336
337 std::vector<SwitchCase> switch_cases;
338
AcceptSparseSwitchPayload339 virtual bool Accept(Visitor* visitor) override { return visitor->Visit(this); }
340 };
341
342 struct ArrayData : public Instruction {
343 slicer::MemView data;
344
AcceptArrayData345 virtual bool Accept(Visitor* visitor) override { return visitor->Visit(this); }
346 };
347
348 struct Label : public Instruction {
349 int id = 0;
350 int refCount = 0;
351 bool aligned = false;
352
LabelLabel353 explicit Label(dex::u4 offset) { this->offset = offset; }
354
AcceptLabel355 virtual bool Accept(Visitor* visitor) override { return visitor->Visit(this); }
356 };
357
358 struct TryBlockBegin : public Instruction {
359 int id = 0;
360
AcceptTryBlockBegin361 virtual bool Accept(Visitor* visitor) override { return visitor->Visit(this); }
362 };
363
364 struct CatchHandler {
365 ir::Type* ir_type = nullptr;
366 Label* label = nullptr;
367 };
368
369 struct TryBlockEnd : public Instruction {
370 TryBlockBegin* try_begin = nullptr;
371 std::vector<CatchHandler> handlers;
372 Label* catch_all = nullptr;
373
AcceptTryBlockEnd374 virtual bool Accept(Visitor* visitor) override { return visitor->Visit(this); }
375 };
376
377 struct DbgInfoHeader : public Instruction {
378 std::vector<ir::String*> param_names;
379
AcceptDbgInfoHeader380 virtual bool Accept(Visitor* visitor) override { return visitor->Visit(this); }
381 };
382
383 struct LineNumber : public Operand {
384 int line = 0;
385
LineNumberLineNumber386 explicit LineNumber(int line) : line(line) {
387 SLICER_WEAK_CHECK(line > 0);
388 }
389
AcceptLineNumber390 virtual bool Accept(Visitor* visitor) override { return visitor->Visit(this); }
391 };
392
393 struct DbgInfoAnnotation : public Instruction {
394 dex::u1 dbg_opcode = 0;
395 std::vector<Operand*> operands;
396
DbgInfoAnnotationDbgInfoAnnotation397 explicit DbgInfoAnnotation(dex::u1 dbg_opcode) : dbg_opcode(dbg_opcode) {}
398
399 template<class T>
CastOperandDbgInfoAnnotation400 T* CastOperand(int index) const {
401 return detail::CastOperand<T>(operands[index]);
402 }
403
AcceptDbgInfoAnnotation404 virtual bool Accept(Visitor* visitor) override { return visitor->Visit(this); }
405 };
406
407 // Code IR container and manipulation interface
408 struct CodeIr {
409 // linked list of the method's instructions
410 InstructionsList instructions;
411
412 ir::EncodedMethod* ir_method = nullptr;
413 std::shared_ptr<ir::DexFile> dex_ir;
414
415 public:
CodeIrCodeIr416 CodeIr(ir::EncodedMethod* ir_method, std::shared_ptr<ir::DexFile> dex_ir)
417 : ir_method(ir_method), dex_ir(dex_ir) {
418 Disassemble();
419 }
420
421 // No copy/move semantics
422 CodeIr(const CodeIr&) = delete;
423 CodeIr& operator=(const CodeIr&) = delete;
424
425 void Assemble();
426
AcceptCodeIr427 void Accept(Visitor* visitor) {
428 for (auto instr : instructions) {
429 instr->Accept(visitor);
430 }
431 }
432
433 template <class T, class... Args>
AllocCodeIr434 T* Alloc(Args&&... args) {
435 auto p = new T(std::forward<Args>(args)...);
436 nodes_.push_back(own<T>(p));
437 return p;
438 }
439
440 private:
441 void Disassemble();
442 void DisassembleBytecode(const ir::Code* ir_code);
443 void DisassembleTryBlocks(const ir::Code* ir_code);
444 void DisassembleDebugInfo(const ir::DebugInfo* ir_debug_info);
445
446 void FixupSwitches();
447 void FixupPackedSwitch(PackedSwitchPayload* instr, dex::u4 base_offset, const dex::u2* ptr);
448 void FixupSparseSwitch(SparseSwitchPayload* instr, dex::u4 base_offset, const dex::u2* ptr);
449
450 SparseSwitchPayload* DecodeSparseSwitch(const dex::u2* /*ptr*/, dex::u4 offset);
451 PackedSwitchPayload* DecodePackedSwitch(const dex::u2* /*ptr*/, dex::u4 offset);
452 ArrayData* DecodeArrayData(const dex::u2* ptr, dex::u4 offset);
453 Bytecode* DecodeBytecode(const dex::u2* ptr, dex::u4 offset);
454
455 IndexedOperand* GetIndexedOperand(dex::InstructionIndexType index_type, dex::u4 index);
456 IndexedOperand* GetSecondIndexedOperand(dex::InstructionIndexType index_type, dex::u4 index);
457
458 Type* GetType(dex::u4 index);
459 String* GetString(dex::u4 index);
460 Label* GetLabel(dex::u4 offset);
461
462 Operand* GetRegA(const dex::Instruction& dex_instr);
463 Operand* GetRegB(const dex::Instruction& dex_instr);
464 Operand* GetRegC(const dex::Instruction& dex_instr);
465
466 private:
467 // the "master index" of all the LIR owned nodes
468 std::vector<own<Node>> nodes_;
469
470 // data structures for fixing up switch payloads
471 struct PackedSwitchFixup {
472 PackedSwitchPayload* instr = nullptr;
473 dex::u4 base_offset = kInvalidOffset;
474 };
475
476 struct SparseSwitchFixup {
477 SparseSwitchPayload* instr = nullptr;
478 dex::u4 base_offset = kInvalidOffset;
479 };
480
481 // used during bytecode raising
482 std::map<dex::u4, Label*> labels_;
483 std::map<dex::u4, PackedSwitchFixup> packed_switches_;
484 std::map<dex::u4, SparseSwitchFixup> sparse_switches_;
485
486 // extra instructions/annotations created during raising
487 // (intended to be merged in with the main instruction
488 // list at end of the IR raising phase)
489 std::vector<TryBlockBegin*> try_begins_;
490 std::vector<TryBlockEnd*> try_ends_;
491 std::vector<Instruction*> dbg_annotations_;
492 };
493
494 } // namespace lir
495