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 #include "common.h" 20 #include "memview.h" 21 #include "dex_bytecode.h" 22 #include "dex_format.h" 23 #include "dex_ir.h" 24 #include "intrusive_list.h" 25 26 #include <assert.h> 27 #include <stdio.h> 28 #include <stdlib.h> 29 30 #include <algorithm> 31 #include <cstdint> 32 #include <list> 33 #include <map> 34 #include <memory> 35 #include <utility> 36 #include <vector> 37 38 namespace lir { 39 40 template <class T> 41 using own = std::unique_ptr<T>; 42 43 constexpr dex::u4 kInvalidOffset = dex::u4(-1); 44 45 struct Bytecode; 46 struct PackedSwitchPayload; 47 struct SparseSwitchPayload; 48 struct ArrayData; 49 struct Label; 50 struct TryBlockBegin; 51 struct TryBlockEnd; 52 struct Const32; 53 struct Const64; 54 struct VReg; 55 struct VRegPair; 56 struct VRegList; 57 struct VRegRange; 58 struct CodeLocation; 59 struct String; 60 struct Type; 61 struct Field; 62 struct Method; 63 struct DbgInfoHeader; 64 struct LineNumber; 65 struct DbgInfoAnnotation; 66 67 // Code IR visitor interface 68 class Visitor { 69 public: 70 Visitor() = default; 71 virtual ~Visitor() = default; 72 73 Visitor(const Visitor&) = delete; 74 Visitor& operator=(const Visitor&) = delete; 75 76 // instructions 77 virtual bool Visit(Bytecode* bytecode) { return false; } 78 virtual bool Visit(PackedSwitchPayload* packed_switch) { return false; } 79 virtual bool Visit(SparseSwitchPayload* sparse_switch) { return false; } 80 virtual bool Visit(ArrayData* array_data) { return false; } 81 virtual bool Visit(Label* label) { return false; } 82 virtual bool Visit(DbgInfoHeader* dbg_header) { return false; } 83 virtual bool Visit(DbgInfoAnnotation* dbg_annotation) { return false; } 84 virtual bool Visit(TryBlockBegin* try_begin) { return false; } 85 virtual bool Visit(TryBlockEnd* try_end) { return false; } 86 87 // operands 88 virtual bool Visit(CodeLocation* location) { return false; } 89 virtual bool Visit(Const32* const32) { return false; } 90 virtual bool Visit(Const64* const64) { return false; } 91 virtual bool Visit(VReg* vreg) { return false; } 92 virtual bool Visit(VRegPair* vreg_pair) { return false; } 93 virtual bool Visit(VRegList* vreg_list) { return false; } 94 virtual bool Visit(VRegRange* vreg_range) { return false; } 95 virtual bool Visit(String* string) { return false; } 96 virtual bool Visit(Type* type) { return false; } 97 virtual bool Visit(Field* field) { return false; } 98 virtual bool Visit(Method* method) { return false; } 99 virtual bool Visit(LineNumber* line) { return false; } 100 }; 101 102 // The root of the polymorphic code IR nodes hierarchy 103 // 104 // NOTE: in general it's possible to "reuse" code IR nodes 105 // (ie. refcount > 1) although extra care is required since 106 // modifications to shared nodes will be visible in multiple places 107 // (notable exception: instruction nodes can't be reused) 108 // 109 struct Node { 110 Node() = default; 111 virtual ~Node() = default; 112 113 Node(const Node&) = delete; 114 Node& operator=(const Node&) = delete; 115 116 virtual bool Accept(Visitor* visitor) { return false; } 117 118 template<class T> 119 bool IsA() const { 120 return dynamic_cast<const T*>(this) != nullptr; 121 } 122 }; 123 124 struct Operand : public Node {}; 125 126 struct Const32 : public Operand { 127 union { 128 dex::s4 s4_value; 129 dex::u4 u4_value; 130 float float_value; 131 } u; 132 133 Const32(dex::u4 value) { u.u4_value = value; } 134 135 virtual bool Accept(Visitor* visitor) override { return visitor->Visit(this); } 136 }; 137 138 struct Const64 : public Operand { 139 union { 140 dex::s8 s8_value; 141 dex::u8 u8_value; 142 double double_value; 143 } u; 144 145 Const64(dex::u8 value) { u.u8_value = value; } 146 147 virtual bool Accept(Visitor* visitor) override { return visitor->Visit(this); } 148 }; 149 150 struct VReg : public Operand { 151 dex::u4 reg; 152 153 VReg(dex::u4 reg) : reg(reg) {} 154 155 virtual bool Accept(Visitor* visitor) override { return visitor->Visit(this); } 156 }; 157 158 struct VRegPair : public Operand { 159 dex::u4 base_reg; 160 161 VRegPair(dex::u4 base_reg) : base_reg(base_reg) {} 162 163 virtual bool Accept(Visitor* visitor) override { return visitor->Visit(this); } 164 }; 165 166 struct VRegList : public Operand { 167 std::vector<dex::u4> registers; 168 169 virtual bool Accept(Visitor* visitor) override { return visitor->Visit(this); } 170 }; 171 172 struct VRegRange : public Operand { 173 dex::u4 base_reg; 174 int count; 175 176 VRegRange(dex::u4 base_reg, int count) : base_reg(base_reg), count(count) {} 177 178 virtual bool Accept(Visitor* visitor) override { return visitor->Visit(this); } 179 }; 180 181 struct IndexedOperand : public Operand { 182 dex::u4 index; 183 184 IndexedOperand(dex::u4 index) : index(index) {} 185 }; 186 187 struct String : public IndexedOperand { 188 ir::String* ir_string; 189 190 String(ir::String* ir_string, dex::u4 index) : IndexedOperand(index), ir_string(ir_string) {} 191 192 virtual bool Accept(Visitor* visitor) override { return visitor->Visit(this); } 193 }; 194 195 struct Type : public IndexedOperand { 196 ir::Type* ir_type; 197 198 Type(ir::Type* ir_type, dex::u4 index) : IndexedOperand(index), ir_type(ir_type) {} 199 200 virtual bool Accept(Visitor* visitor) override { return visitor->Visit(this); } 201 }; 202 203 struct Field : public IndexedOperand { 204 ir::FieldDecl* ir_field; 205 206 Field(ir::FieldDecl* ir_field, dex::u4 index) : IndexedOperand(index), ir_field(ir_field) {} 207 208 virtual bool Accept(Visitor* visitor) override { return visitor->Visit(this); } 209 }; 210 211 struct Method : public IndexedOperand { 212 ir::MethodDecl* ir_method; 213 214 Method(ir::MethodDecl* ir_method, dex::u4 index) : IndexedOperand(index), ir_method(ir_method) {} 215 216 virtual bool Accept(Visitor* visitor) override { return visitor->Visit(this); } 217 }; 218 219 struct CodeLocation : public Operand { 220 Label* label; 221 222 CodeLocation(Label* label) : label(label) {} 223 224 virtual bool Accept(Visitor* visitor) override { return visitor->Visit(this); } 225 }; 226 227 // Code IR is a linked list of Instructions 228 struct Instruction : public Node { 229 // absolute offset from the start of the method 230 dex::u4 offset = 0; 231 232 Instruction* prev = nullptr; 233 Instruction* next = nullptr; 234 }; 235 236 using InstructionsList = slicer::IntrusiveList<Instruction>; 237 238 struct Bytecode : public Instruction { 239 dex::Opcode opcode = dex::OP_NOP; 240 std::vector<Operand*> operands; 241 242 template<class T> 243 T* CastOperand(int index) const { 244 T* operand = dynamic_cast<T*>(operands[index]); 245 SLICER_CHECK(operand != nullptr); 246 return operand; 247 } 248 249 virtual bool Accept(Visitor* visitor) override { return visitor->Visit(this); } 250 }; 251 252 struct PackedSwitchPayload : public Instruction { 253 dex::s4 first_key = 0; 254 std::vector<Label*> targets; 255 256 virtual bool Accept(Visitor* visitor) override { return visitor->Visit(this); } 257 }; 258 259 struct SparseSwitchPayload : public Instruction { 260 struct SwitchCase { 261 dex::s4 key = 0; 262 Label* target = nullptr; 263 }; 264 265 std::vector<SwitchCase> switch_cases; 266 267 virtual bool Accept(Visitor* visitor) override { return visitor->Visit(this); } 268 }; 269 270 struct ArrayData : public Instruction { 271 slicer::MemView data; 272 273 virtual bool Accept(Visitor* visitor) override { return visitor->Visit(this); } 274 }; 275 276 struct Label : public Instruction { 277 int id = 0; 278 int refCount = 0; 279 bool aligned = false; 280 281 Label(dex::u4 offset) { this->offset = offset; } 282 283 virtual bool Accept(Visitor* visitor) override { return visitor->Visit(this); } 284 }; 285 286 struct TryBlockBegin : public Instruction { 287 int id = 0; 288 289 virtual bool Accept(Visitor* visitor) override { return visitor->Visit(this); } 290 }; 291 292 struct CatchHandler { 293 ir::Type* ir_type = nullptr; 294 Label* label = nullptr; 295 }; 296 297 struct TryBlockEnd : public Instruction { 298 TryBlockBegin* try_begin = nullptr; 299 std::vector<CatchHandler> handlers; 300 Label* catch_all = nullptr; 301 302 virtual bool Accept(Visitor* visitor) override { return visitor->Visit(this); } 303 }; 304 305 struct DbgInfoHeader : public Instruction { 306 std::vector<ir::String*> param_names; 307 308 virtual bool Accept(Visitor* visitor) override { return visitor->Visit(this); } 309 }; 310 311 struct LineNumber : public Operand { 312 int line = 0; 313 314 LineNumber(int line) : line(line) { 315 SLICER_WEAK_CHECK(line > 0); 316 } 317 318 virtual bool Accept(Visitor* visitor) override { return visitor->Visit(this); } 319 }; 320 321 struct DbgInfoAnnotation : public Instruction { 322 dex::u1 dbg_opcode = 0; 323 std::vector<Operand*> operands; 324 325 DbgInfoAnnotation(dex::u1 dbg_opcode) : dbg_opcode(dbg_opcode) {} 326 327 template<class T> 328 T* CastOperand(int index) const { 329 T* operand = dynamic_cast<T*>(operands[index]); 330 SLICER_CHECK(operand != nullptr); 331 return operand; 332 } 333 334 virtual bool Accept(Visitor* visitor) override { return visitor->Visit(this); } 335 }; 336 337 // Code IR container and manipulation interface 338 struct CodeIr { 339 // linked list of the method's instructions 340 InstructionsList instructions; 341 342 ir::EncodedMethod* ir_method = nullptr; 343 std::shared_ptr<ir::DexFile> dex_ir; 344 345 public: 346 CodeIr(ir::EncodedMethod* ir_method, std::shared_ptr<ir::DexFile> dex_ir) 347 : ir_method(ir_method), dex_ir(dex_ir) { 348 Dissasemble(); 349 } 350 351 // No copy/move semantics 352 CodeIr(const CodeIr&) = delete; 353 CodeIr& operator=(const CodeIr&) = delete; 354 355 void Assemble(); 356 357 void Accept(Visitor* visitor) { 358 for (auto instr : instructions) { 359 instr->Accept(visitor); 360 } 361 } 362 363 template <class T, class... Args> 364 T* Alloc(Args&&... args) { 365 auto p = new T(std::forward<Args>(args)...); 366 nodes_.push_back(own<T>(p)); 367 return p; 368 } 369 370 private: 371 void Dissasemble(); 372 void DissasembleBytecode(const ir::Code* ir_code); 373 void DissasembleTryBlocks(const ir::Code* ir_code); 374 void DissasembleDebugInfo(const ir::DebugInfo* ir_debug_info); 375 376 void FixupSwitches(); 377 void FixupPackedSwitch(PackedSwitchPayload* instr, dex::u4 base_offset, const dex::u2* ptr); 378 void FixupSparseSwitch(SparseSwitchPayload* instr, dex::u4 base_offset, const dex::u2* ptr); 379 380 SparseSwitchPayload* DecodeSparseSwitch(const dex::u2* /*ptr*/, dex::u4 offset); 381 PackedSwitchPayload* DecodePackedSwitch(const dex::u2* /*ptr*/, dex::u4 offset); 382 ArrayData* DecodeArrayData(const dex::u2* ptr, dex::u4 offset); 383 Bytecode* DecodeBytecode(const dex::u2* ptr, dex::u4 offset); 384 385 IndexedOperand* GetIndexedOperand(dex::InstructionIndexType index_type, dex::u4 index); 386 387 Type* GetType(dex::u4 index); 388 String* GetString(dex::u4 index); 389 Label* GetLabel(dex::u4 offset); 390 391 Operand* GetRegA(const dex::Instruction& dex_instr); 392 Operand* GetRegB(const dex::Instruction& dex_instr); 393 Operand* GetRegC(const dex::Instruction& dex_instr); 394 395 private: 396 // the "master index" of all the LIR owned nodes 397 std::vector<own<Node>> nodes_; 398 399 // data structures for fixing up switch payloads 400 struct PackedSwitchFixup { 401 PackedSwitchPayload* instr = nullptr; 402 dex::u4 base_offset = kInvalidOffset; 403 }; 404 405 struct SparseSwitchFixup { 406 SparseSwitchPayload* instr = nullptr; 407 dex::u4 base_offset = kInvalidOffset; 408 }; 409 410 // used during bytecode raising 411 std::map<dex::u4, Label*> labels_; 412 std::map<dex::u4, PackedSwitchFixup> packed_switches_; 413 std::map<dex::u4, SparseSwitchFixup> sparse_switches_; 414 415 // extra instructions/annotations created during raising 416 // (intended to be merged in with the main instruction 417 // list at end of the IR raising phase) 418 std::vector<TryBlockBegin*> try_begins_; 419 std::vector<TryBlockEnd*> try_ends_; 420 std::vector<Instruction*> dbg_annotations_; 421 }; 422 423 } // namespace lir 424
