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 MethodHandle;
70 struct Proto;
71 struct DbgInfoHeader;
72 struct LineNumber;
73 struct DbgInfoAnnotation;
74
75 // Code IR visitor interface
76 class Visitor {
77 public:
78 Visitor() = default;
79 virtual ~Visitor() = default;
80
81 Visitor(const Visitor&) = delete;
82 Visitor& operator=(const Visitor&) = delete;
83
84 // instructions
Visit(Bytecode * bytecode)85 virtual bool Visit(Bytecode* bytecode) { return false; }
Visit(PackedSwitchPayload * packed_switch)86 virtual bool Visit(PackedSwitchPayload* packed_switch) { return false; }
Visit(SparseSwitchPayload * sparse_switch)87 virtual bool Visit(SparseSwitchPayload* sparse_switch) { return false; }
Visit(ArrayData * array_data)88 virtual bool Visit(ArrayData* array_data) { return false; }
Visit(Label * label)89 virtual bool Visit(Label* label) { return false; }
Visit(DbgInfoHeader * dbg_header)90 virtual bool Visit(DbgInfoHeader* dbg_header) { return false; }
Visit(DbgInfoAnnotation * dbg_annotation)91 virtual bool Visit(DbgInfoAnnotation* dbg_annotation) { return false; }
Visit(TryBlockBegin * try_begin)92 virtual bool Visit(TryBlockBegin* try_begin) { return false; }
Visit(TryBlockEnd * try_end)93 virtual bool Visit(TryBlockEnd* try_end) { return false; }
94
95 // operands
Visit(CodeLocation * location)96 virtual bool Visit(CodeLocation* location) { return false; }
Visit(Const32 * const32)97 virtual bool Visit(Const32* const32) { return false; }
Visit(Const64 * const64)98 virtual bool Visit(Const64* const64) { return false; }
Visit(VReg * vreg)99 virtual bool Visit(VReg* vreg) { return false; }
Visit(VRegPair * vreg_pair)100 virtual bool Visit(VRegPair* vreg_pair) { return false; }
Visit(VRegList * vreg_list)101 virtual bool Visit(VRegList* vreg_list) { return false; }
Visit(VRegRange * vreg_range)102 virtual bool Visit(VRegRange* vreg_range) { return false; }
Visit(String * string)103 virtual bool Visit(String* string) { return false; }
Visit(Type * type)104 virtual bool Visit(Type* type) { return false; }
Visit(Field * field)105 virtual bool Visit(Field* field) { return false; }
Visit(Method * method)106 virtual bool Visit(Method* method) { return false; }
Visit(Proto * proto)107 virtual bool Visit(Proto* proto) { return false; }
Visit(LineNumber * line)108 virtual bool Visit(LineNumber* line) { return false; }
Visit(MethodHandle * mh)109 virtual bool Visit(MethodHandle* mh) { return false; }
110 };
111
112 // The root of the polymorphic code IR nodes hierarchy
113 //
114 // NOTE: in general it's possible to "reuse" code IR nodes
115 // (ie. refcount > 1) although extra care is required since
116 // modifications to shared nodes will be visible in multiple places
117 // (notable exception: instruction nodes can't be reused)
118 //
119 struct Node {
120 Node() = default;
121 virtual ~Node() = default;
122
123 Node(const Node&) = delete;
124 Node& operator=(const Node&) = delete;
125
AcceptNode126 virtual bool Accept(Visitor* visitor) { return false; }
127 };
128
129 struct Operand : public Node {};
130
131 struct Const32 : public Operand {
132 union {
133 dex::s4 s4_value;
134 dex::u4 u4_value;
135 float float_value;
136 } u;
137
Const32Const32138 explicit Const32(dex::u4 value) { u.u4_value = value; }
139
AcceptConst32140 virtual bool Accept(Visitor* visitor) override { return visitor->Visit(this); }
141 };
142
143 struct Const64 : public Operand {
144 union {
145 dex::s8 s8_value;
146 dex::u8 u8_value;
147 double double_value;
148 } u;
149
Const64Const64150 explicit Const64(dex::u8 value) { u.u8_value = value; }
151
AcceptConst64152 virtual bool Accept(Visitor* visitor) override { return visitor->Visit(this); }
153 };
154
155 struct VReg : public Operand {
156 dex::u4 reg;
157
VRegVReg158 explicit VReg(dex::u4 reg) : reg(reg) {}
159
AcceptVReg160 virtual bool Accept(Visitor* visitor) override { return visitor->Visit(this); }
161 };
162
163 struct VRegPair : public Operand {
164 dex::u4 base_reg;
165
VRegPairVRegPair166 explicit VRegPair(dex::u4 base_reg) : base_reg(base_reg) {}
167
AcceptVRegPair168 virtual bool Accept(Visitor* visitor) override { return visitor->Visit(this); }
169 };
170
171 struct VRegList : public Operand {
172 std::vector<dex::u4> registers;
173
AcceptVRegList174 virtual bool Accept(Visitor* visitor) override { return visitor->Visit(this); }
175 };
176
177 struct VRegRange : public Operand {
178 dex::u4 base_reg;
179 int count;
180
VRegRangeVRegRange181 VRegRange(dex::u4 base_reg, int count) : base_reg(base_reg), count(count) {}
182
AcceptVRegRange183 virtual bool Accept(Visitor* visitor) override { return visitor->Visit(this); }
184 };
185
186 struct IndexedOperand : public Operand {
187 dex::u4 index;
188
IndexedOperandIndexedOperand189 explicit IndexedOperand(dex::u4 index) : index(index) {}
190 };
191
192 struct String : public IndexedOperand {
193 ir::String* ir_string;
194
StringString195 String(ir::String* ir_string, dex::u4 index) : IndexedOperand(index), ir_string(ir_string) {}
196
AcceptString197 virtual bool Accept(Visitor* visitor) override { return visitor->Visit(this); }
198 };
199
200 struct Type : public IndexedOperand {
201 ir::Type* ir_type;
202
TypeType203 Type(ir::Type* ir_type, dex::u4 index) : IndexedOperand(index), ir_type(ir_type) {}
204
AcceptType205 virtual bool Accept(Visitor* visitor) override { return visitor->Visit(this); }
206 };
207
208 struct Field : public IndexedOperand {
209 ir::FieldDecl* ir_field;
210
FieldField211 Field(ir::FieldDecl* ir_field, dex::u4 index) : IndexedOperand(index), ir_field(ir_field) {}
212
AcceptField213 virtual bool Accept(Visitor* visitor) override { return visitor->Visit(this); }
214 };
215
216 struct Method : public IndexedOperand {
217 ir::MethodDecl* ir_method;
218
MethodMethod219 Method(ir::MethodDecl* ir_method, dex::u4 index) : IndexedOperand(index), ir_method(ir_method) {
220 SLICER_CHECK_NE(ir_method, nullptr);
221 }
222
AcceptMethod223 virtual bool Accept(Visitor* visitor) override { return visitor->Visit(this); }
224 };
225
226 struct MethodHandle : public IndexedOperand {
227 ir::MethodHandle* ir_method_handle;
228
MethodHandleMethodHandle229 MethodHandle(ir::MethodHandle* ir_method_handle, dex::u4 index) : IndexedOperand(index), ir_method_handle(ir_method_handle) {
230 SLICER_CHECK_NE(ir_method_handle, nullptr);
231 }
232
AcceptMethodHandle233 virtual bool Accept(Visitor* visitor) override { return visitor->Visit(this); }
234 };
235
236 struct Proto : public IndexedOperand {
237 ir::Proto* ir_proto;
238
ProtoProto239 Proto(ir::Proto* ir_proto, dex::u4 index) : IndexedOperand(index), ir_proto(ir_proto) {}
240
AcceptProto241 virtual bool Accept(Visitor* visitor) override { return visitor->Visit(this); }
242 };
243
244 struct CodeLocation : public Operand {
245 Label* label;
246
CodeLocationCodeLocation247 explicit CodeLocation(Label* label) : label(label) {}
248
AcceptCodeLocation249 virtual bool Accept(Visitor* visitor) override { return visitor->Visit(this); }
250 };
251
252 // Code IR is a linked list of Instructions
253 struct Instruction : public Node {
254 // absolute offset from the start of the method
255 dex::u4 offset = 0;
256
257 Instruction* prev = nullptr;
258 Instruction* next = nullptr;
259 };
260
261 using InstructionsList = slicer::IntrusiveList<Instruction>;
262
263 namespace detail {
264
265 template<class T>
CastOperand(Operand * op)266 inline T* CastOperand(Operand* op) {
267 #ifdef RTTI_ENABLED
268 T* operand = dynamic_cast<T*>(op);
269 SLICER_CHECK_NE(operand, nullptr);
270 return operand;
271 #else
272 SLICER_CHECK_NE(op, nullptr);
273 struct CastVisitor : public Visitor {
274 T* converted = nullptr;
275 bool Visit(T* val) override {
276 converted = val;
277 return true;
278 }
279 };
280 CastVisitor cv;
281 op->Accept(&cv);
282 SLICER_CHECK_NE(cv.converted, nullptr);
283 return cv.converted;
284 #endif
285 }
286
287 // Special-case for IndexedOperand.
288 template<>
289 inline IndexedOperand* CastOperand<IndexedOperand>(Operand* op) {
290 #ifdef RTTI_ENABLED
291 IndexedOperand* operand = dynamic_cast<IndexedOperand*>(op);
292 SLICER_CHECK_NE(operand, nullptr);
293 return operand;
294 #else
295 SLICER_CHECK_NE(op, nullptr);
296 struct CastVisitor : public Visitor {
297 IndexedOperand* converted = nullptr;
298 bool Visit(String* val) override {
299 converted = val;
300 return true;
301 }
302 bool Visit(Type* val) override {
303 converted = val;
304 return true;
305 }
306 bool Visit(Field* val) override {
307 converted = val;
308 return true;
309 }
310 bool Visit(Method* val) override {
311 converted = val;
312 return true;
313 }
314 bool Visit(MethodHandle* val) override {
315 converted = val;
316 return true;
317 }
318 bool Visit(Proto* val) override {
319 converted = val;
320 return true;
321 }
322 };
323 CastVisitor cv;
324 op->Accept(&cv);
325 SLICER_CHECK_NE(cv.converted, nullptr);
326 return cv.converted;
327 #endif
328 }
329
330 } // namespace detail
331
332 struct Bytecode : public Instruction {
333 dex::Opcode opcode = dex::OP_NOP;
334 std::vector<Operand*> operands;
335
336 template<class T>
CastOperandBytecode337 T* CastOperand(int index) const {
338 return detail::CastOperand<T>(operands[index]);
339 }
340
AcceptBytecode341 virtual bool Accept(Visitor* visitor) override { return visitor->Visit(this); }
342 };
343
344 struct PackedSwitchPayload : public Instruction {
345 dex::s4 first_key = 0;
346 std::vector<Label*> targets;
347
AcceptPackedSwitchPayload348 virtual bool Accept(Visitor* visitor) override { return visitor->Visit(this); }
349 };
350
351 struct SparseSwitchPayload : public Instruction {
352 struct SwitchCase {
353 dex::s4 key = 0;
354 Label* target = nullptr;
355 };
356
357 std::vector<SwitchCase> switch_cases;
358
AcceptSparseSwitchPayload359 virtual bool Accept(Visitor* visitor) override { return visitor->Visit(this); }
360 };
361
362 struct ArrayData : public Instruction {
363 slicer::MemView data;
364
AcceptArrayData365 virtual bool Accept(Visitor* visitor) override { return visitor->Visit(this); }
366 };
367
368 struct Label : public Instruction {
369 int id = 0;
370 int refCount = 0;
371 bool aligned = false;
372
LabelLabel373 explicit Label(dex::u4 offset) { this->offset = offset; }
374
AcceptLabel375 virtual bool Accept(Visitor* visitor) override { return visitor->Visit(this); }
376 };
377
378 struct TryBlockBegin : public Instruction {
379 int id = 0;
380
AcceptTryBlockBegin381 virtual bool Accept(Visitor* visitor) override { return visitor->Visit(this); }
382 };
383
384 struct CatchHandler {
385 ir::Type* ir_type = nullptr;
386 Label* label = nullptr;
387 };
388
389 struct TryBlockEnd : public Instruction {
390 TryBlockBegin* try_begin = nullptr;
391 std::vector<CatchHandler> handlers;
392 Label* catch_all = nullptr;
393
AcceptTryBlockEnd394 virtual bool Accept(Visitor* visitor) override { return visitor->Visit(this); }
395 };
396
397 struct DbgInfoHeader : public Instruction {
398 std::vector<ir::String*> param_names;
399
AcceptDbgInfoHeader400 virtual bool Accept(Visitor* visitor) override { return visitor->Visit(this); }
401 };
402
403 struct LineNumber : public Operand {
404 int line = 0;
405
LineNumberLineNumber406 explicit LineNumber(int line) : line(line) {
407 SLICER_WEAK_CHECK(line >= 0);
408 }
409
AcceptLineNumber410 virtual bool Accept(Visitor* visitor) override { return visitor->Visit(this); }
411 };
412
413 struct DbgInfoAnnotation : public Instruction {
414 dex::u1 dbg_opcode = 0;
415 std::vector<Operand*> operands;
416
DbgInfoAnnotationDbgInfoAnnotation417 explicit DbgInfoAnnotation(dex::u1 dbg_opcode) : dbg_opcode(dbg_opcode) {}
418
419 template<class T>
CastOperandDbgInfoAnnotation420 T* CastOperand(int index) const {
421 return detail::CastOperand<T>(operands[index]);
422 }
423
AcceptDbgInfoAnnotation424 virtual bool Accept(Visitor* visitor) override { return visitor->Visit(this); }
425 };
426
427 // Code IR container and manipulation interface
428 struct CodeIr {
429 // linked list of the method's instructions
430 InstructionsList instructions;
431
432 ir::EncodedMethod* ir_method = nullptr;
433 std::shared_ptr<ir::DexFile> dex_ir;
434
435 public:
CodeIrCodeIr436 CodeIr(ir::EncodedMethod* ir_method, std::shared_ptr<ir::DexFile> dex_ir)
437 : ir_method(ir_method), dex_ir(dex_ir) {
438 Disassemble();
439 }
440
441 // No copy/move semantics
442 CodeIr(const CodeIr&) = delete;
443 CodeIr& operator=(const CodeIr&) = delete;
444
445 void Assemble();
446
AcceptCodeIr447 void Accept(Visitor* visitor) {
448 for (auto instr : instructions) {
449 instr->Accept(visitor);
450 }
451 }
452
453 template <class T, class... Args>
AllocCodeIr454 T* Alloc(Args&&... args) {
455 auto p = new T(std::forward<Args>(args)...);
456 nodes_.push_back(own<T>(p));
457 return p;
458 }
459
460 private:
461 void Disassemble();
462 void DisassembleBytecode(const ir::Code* ir_code);
463 void DisassembleTryBlocks(const ir::Code* ir_code);
464 void DisassembleDebugInfo(const ir::DebugInfo* ir_debug_info);
465
466 void FixupSwitches();
467 void FixupPackedSwitch(PackedSwitchPayload* instr, dex::u4 base_offset, const dex::u2* ptr);
468 void FixupSparseSwitch(SparseSwitchPayload* instr, dex::u4 base_offset, const dex::u2* ptr);
469
470 SparseSwitchPayload* DecodeSparseSwitch(const dex::u2* /*ptr*/, dex::u4 offset);
471 PackedSwitchPayload* DecodePackedSwitch(const dex::u2* /*ptr*/, dex::u4 offset);
472 ArrayData* DecodeArrayData(const dex::u2* ptr, dex::u4 offset);
473 Bytecode* DecodeBytecode(const dex::u2* ptr, dex::u4 offset);
474
475 IndexedOperand* GetIndexedOperand(dex::InstructionIndexType index_type, dex::u4 index);
476 IndexedOperand* GetSecondIndexedOperand(dex::InstructionIndexType index_type, dex::u4 index);
477
478 Type* GetType(dex::u4 index);
479 String* GetString(dex::u4 index);
480 Label* GetLabel(dex::u4 offset);
481
482 Operand* GetRegA(const dex::Instruction& dex_instr);
483 Operand* GetRegB(const dex::Instruction& dex_instr);
484 Operand* GetRegC(const dex::Instruction& dex_instr);
485
486 private:
487 // the "master index" of all the LIR owned nodes
488 std::vector<own<Node>> nodes_;
489
490 // data structures for fixing up switch payloads
491 struct PackedSwitchFixup {
492 PackedSwitchPayload* instr = nullptr;
493 dex::u4 base_offset = kInvalidOffset;
494 };
495
496 struct SparseSwitchFixup {
497 SparseSwitchPayload* instr = nullptr;
498 dex::u4 base_offset = kInvalidOffset;
499 };
500
501 // used during bytecode raising
502 std::map<dex::u4, Label*> labels_;
503 std::map<dex::u4, PackedSwitchFixup> packed_switches_;
504 std::map<dex::u4, SparseSwitchFixup> sparse_switches_;
505
506 // extra instructions/annotations created during raising
507 // (intended to be merged in with the main instruction
508 // list at end of the IR raising phase)
509 std::vector<TryBlockBegin*> try_begins_;
510 std::vector<TryBlockEnd*> try_ends_;
511 std::vector<Instruction*> dbg_annotations_;
512 };
513
514 } // namespace lir
515