diff options
Diffstat (limited to 'compiler/sea_ir')
-rw-r--r-- | compiler/sea_ir/frontend.cc | 67 | ||||
-rw-r--r-- | compiler/sea_ir/instruction_tools.cc | 797 | ||||
-rw-r--r-- | compiler/sea_ir/instruction_tools.h | 124 | ||||
-rw-r--r-- | compiler/sea_ir/sea.cc | 329 | ||||
-rw-r--r-- | compiler/sea_ir/sea.h | 162 |
5 files changed, 1479 insertions, 0 deletions
diff --git a/compiler/sea_ir/frontend.cc b/compiler/sea_ir/frontend.cc new file mode 100644 index 0000000..9af7eff --- /dev/null +++ b/compiler/sea_ir/frontend.cc @@ -0,0 +1,67 @@ +#ifdef ART_SEA_IR_MODE +#include <llvm/Support/Threading.h> +#include "base/logging.h" +#include "dex/portable/mir_to_gbc.h" +#include "driver/compiler_driver.h" +#include "leb128.h" +#include "llvm/llvm_compilation_unit.h" +#include "mirror/object.h" +#include "runtime.h" +#include "sea_ir/sea.h" + +namespace art { + +static CompiledMethod* CompileMethodWithSeaIr(CompilerDriver& compiler, + const CompilerBackend compiler_backend, + const DexFile::CodeItem* code_item, + uint32_t access_flags, InvokeType invoke_type, + uint32_t class_def_idx, uint32_t method_idx, + jobject class_loader, const DexFile& dex_file +#if defined(ART_USE_PORTABLE_COMPILER) + , llvm::LlvmCompilationUnit* llvm_compilation_unit +#endif +) { + // NOTE: Instead of keeping the convention from the Dalvik frontend.cc + // and silencing the cpplint.py warning, I just corrected the formatting. + VLOG(compiler) << "Compiling " << PrettyMethod(method_idx, dex_file) << "..."; + sea_ir::SeaGraph* sg = sea_ir::SeaGraph::GetCurrentGraph(); + sg->CompileMethod(code_item, class_def_idx, method_idx, dex_file); + sg->DumpSea("/tmp/temp.dot"); + CHECK(0 && "No SEA compiled function exists yet."); + return NULL; +} + + +CompiledMethod* SeaIrCompileOneMethod(CompilerDriver& compiler, + const CompilerBackend backend, + const DexFile::CodeItem* code_item, + uint32_t access_flags, + InvokeType invoke_type, + uint32_t class_def_idx, + uint32_t method_idx, + jobject class_loader, + const DexFile& dex_file, + llvm::LlvmCompilationUnit* llvm_compilation_unit) { + return CompileMethodWithSeaIr(compiler, backend, code_item, access_flags, invoke_type, class_def_idx, + method_idx, class_loader, dex_file +#if defined(ART_USE_PORTABLE_COMPILER) + , llvm_compilation_unit +#endif + ); // NOLINT +} + +extern "C" art::CompiledMethod* + SeaIrCompileMethod(art::CompilerDriver& compiler, + const art::DexFile::CodeItem* code_item, + uint32_t access_flags, art::InvokeType invoke_type, + uint32_t class_def_idx, uint32_t method_idx, jobject class_loader, + const art::DexFile& dex_file) { + // TODO: check method fingerprint here to determine appropriate backend type. Until then, use build default + art::CompilerBackend backend = compiler.GetCompilerBackend(); + return art::SeaIrCompileOneMethod(compiler, backend, code_item, access_flags, invoke_type, + class_def_idx, method_idx, class_loader, dex_file, + NULL /* use thread llvm_info */); +} +#endif + +} // end namespace art diff --git a/compiler/sea_ir/instruction_tools.cc b/compiler/sea_ir/instruction_tools.cc new file mode 100644 index 0000000..5433591 --- /dev/null +++ b/compiler/sea_ir/instruction_tools.cc @@ -0,0 +1,797 @@ +/* + * Copyright (C) 2013 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include "instruction_tools.h" + +namespace sea_ir { + +bool InstructionTools::IsDefinition(const art::Instruction* const instruction) { + if (0 != (InstructionTools::instruction_attributes_[instruction->Opcode()] & (1 << kDA))) { + return true; + } + return false; +} + +const int InstructionTools::instruction_attributes_[] = { + // 00 NOP + DF_NOP, + + // 01 MOVE vA, vB + DF_DA | DF_UB | DF_IS_MOVE, + + // 02 MOVE_FROM16 vAA, vBBBB + DF_DA | DF_UB | DF_IS_MOVE, + + // 03 MOVE_16 vAAAA, vBBBB + DF_DA | DF_UB | DF_IS_MOVE, + + // 04 MOVE_WIDE vA, vB + DF_DA | DF_A_WIDE | DF_UB | DF_B_WIDE | DF_IS_MOVE, + + // 05 MOVE_WIDE_FROM16 vAA, vBBBB + DF_DA | DF_A_WIDE | DF_UB | DF_B_WIDE | DF_IS_MOVE, + + // 06 MOVE_WIDE_16 vAAAA, vBBBB + DF_DA | DF_A_WIDE | DF_UB | DF_B_WIDE | DF_IS_MOVE, + + // 07 MOVE_OBJECT vA, vB + DF_DA | DF_UB | DF_NULL_TRANSFER_0 | DF_IS_MOVE | DF_REF_A | DF_REF_B, + + // 08 MOVE_OBJECT_FROM16 vAA, vBBBB + DF_DA | DF_UB | DF_NULL_TRANSFER_0 | DF_IS_MOVE | DF_REF_A | DF_REF_B, + + // 09 MOVE_OBJECT_16 vAAAA, vBBBB + DF_DA | DF_UB | DF_NULL_TRANSFER_0 | DF_IS_MOVE | DF_REF_A | DF_REF_B, + + // 0A MOVE_RESULT vAA + DF_DA, + + // 0B MOVE_RESULT_WIDE vAA + DF_DA | DF_A_WIDE, + + // 0C MOVE_RESULT_OBJECT vAA + DF_DA | DF_REF_A, + + // 0D MOVE_EXCEPTION vAA + DF_DA | DF_REF_A | DF_NON_NULL_DST, + + // 0E RETURN_VOID + DF_NOP, + + // 0F RETURN vAA + DF_UA, + + // 10 RETURN_WIDE vAA + DF_UA | DF_A_WIDE, + + // 11 RETURN_OBJECT vAA + DF_UA | DF_REF_A, + + // 12 CONST_4 vA, #+B + DF_DA | DF_SETS_CONST, + + // 13 CONST_16 vAA, #+BBBB + DF_DA | DF_SETS_CONST, + + // 14 CONST vAA, #+BBBBBBBB + DF_DA | DF_SETS_CONST, + + // 15 CONST_HIGH16 VAA, #+BBBB0000 + DF_DA | DF_SETS_CONST, + + // 16 CONST_WIDE_16 vAA, #+BBBB + DF_DA | DF_A_WIDE | DF_SETS_CONST, + + // 17 CONST_WIDE_32 vAA, #+BBBBBBBB + DF_DA | DF_A_WIDE | DF_SETS_CONST, + + // 18 CONST_WIDE vAA, #+BBBBBBBBBBBBBBBB + DF_DA | DF_A_WIDE | DF_SETS_CONST, + + // 19 CONST_WIDE_HIGH16 vAA, #+BBBB000000000000 + DF_DA | DF_A_WIDE | DF_SETS_CONST, + + // 1A CONST_STRING vAA, string@BBBB + DF_DA | DF_REF_A | DF_NON_NULL_DST, + + // 1B CONST_STRING_JUMBO vAA, string@BBBBBBBB + DF_DA | DF_REF_A | DF_NON_NULL_DST, + + // 1C CONST_CLASS vAA, type@BBBB + DF_DA | DF_REF_A | DF_NON_NULL_DST, + + // 1D MONITOR_ENTER vAA + DF_UA | DF_NULL_CHK_0 | DF_REF_A, + + // 1E MONITOR_EXIT vAA + DF_UA | DF_NULL_CHK_0 | DF_REF_A, + + // 1F CHK_CAST vAA, type@BBBB + DF_UA | DF_REF_A | DF_UMS, + + // 20 INSTANCE_OF vA, vB, type@CCCC + DF_DA | DF_UB | DF_CORE_A | DF_REF_B | DF_UMS, + + // 21 ARRAY_LENGTH vA, vB + DF_DA | DF_UB | DF_NULL_CHK_0 | DF_CORE_A | DF_REF_B, + + // 22 NEW_INSTANCE vAA, type@BBBB + DF_DA | DF_NON_NULL_DST | DF_REF_A | DF_UMS, + + // 23 NEW_ARRAY vA, vB, type@CCCC + DF_DA | DF_UB | DF_NON_NULL_DST | DF_REF_A | DF_CORE_B | DF_UMS, + + // 24 FILLED_NEW_ARRAY {vD, vE, vF, vG, vA} + DF_FORMAT_35C | DF_NON_NULL_RET | DF_UMS, + + // 25 FILLED_NEW_ARRAY_RANGE {vCCCC .. vNNNN}, type@BBBB + DF_FORMAT_3RC | DF_NON_NULL_RET | DF_UMS, + + // 26 FILL_ARRAY_DATA vAA, +BBBBBBBB + DF_UA | DF_REF_A | DF_UMS, + + // 27 THROW vAA + DF_UA | DF_REF_A | DF_UMS, + + // 28 GOTO + DF_NOP, + + // 29 GOTO_16 + DF_NOP, + + // 2A GOTO_32 + DF_NOP, + + // 2B PACKED_SWITCH vAA, +BBBBBBBB + DF_UA, + + // 2C SPARSE_SWITCH vAA, +BBBBBBBB + DF_UA, + + // 2D CMPL_FLOAT vAA, vBB, vCC + DF_DA | DF_UB | DF_UC | DF_FP_B | DF_FP_C | DF_CORE_A, + + // 2E CMPG_FLOAT vAA, vBB, vCC + DF_DA | DF_UB | DF_UC | DF_FP_B | DF_FP_C | DF_CORE_A, + + // 2F CMPL_DOUBLE vAA, vBB, vCC + DF_DA | DF_UB | DF_B_WIDE | DF_UC | DF_C_WIDE | DF_FP_B | DF_FP_C | DF_CORE_A, + + // 30 CMPG_DOUBLE vAA, vBB, vCC + DF_DA | DF_UB | DF_B_WIDE | DF_UC | DF_C_WIDE | DF_FP_B | DF_FP_C | DF_CORE_A, + + // 31 CMP_LONG vAA, vBB, vCC + DF_DA | DF_UB | DF_B_WIDE | DF_UC | DF_C_WIDE | DF_CORE_A | DF_CORE_B | DF_CORE_C, + + // 32 IF_EQ vA, vB, +CCCC + DF_UA | DF_UB, + + // 33 IF_NE vA, vB, +CCCC + DF_UA | DF_UB, + + // 34 IF_LT vA, vB, +CCCC + DF_UA | DF_UB, + + // 35 IF_GE vA, vB, +CCCC + DF_UA | DF_UB, + + // 36 IF_GT vA, vB, +CCCC + DF_UA | DF_UB, + + // 37 IF_LE vA, vB, +CCCC + DF_UA | DF_UB, + + // 38 IF_EQZ vAA, +BBBB + DF_UA, + + // 39 IF_NEZ vAA, +BBBB + DF_UA, + + // 3A IF_LTZ vAA, +BBBB + DF_UA, + + // 3B IF_GEZ vAA, +BBBB + DF_UA, + + // 3C IF_GTZ vAA, +BBBB + DF_UA, + + // 3D IF_LEZ vAA, +BBBB + DF_UA, + + // 3E UNUSED_3E + DF_NOP, + + // 3F UNUSED_3F + DF_NOP, + + // 40 UNUSED_40 + DF_NOP, + + // 41 UNUSED_41 + DF_NOP, + + // 42 UNUSED_42 + DF_NOP, + + // 43 UNUSED_43 + DF_NOP, + + // 44 AGET vAA, vBB, vCC + DF_DA | DF_UB | DF_UC | DF_NULL_CHK_0 | DF_RANGE_CHK_1 | DF_REF_B | DF_CORE_C, + + // 45 AGET_WIDE vAA, vBB, vCC + DF_DA | DF_A_WIDE | DF_UB | DF_UC | DF_NULL_CHK_0 | DF_RANGE_CHK_1 | DF_REF_B | DF_CORE_C, + + // 46 AGET_OBJECT vAA, vBB, vCC + DF_DA | DF_UB | DF_UC | DF_NULL_CHK_0 | DF_RANGE_CHK_1 | DF_REF_A | DF_REF_B | DF_CORE_C, + + // 47 AGET_BOOLEAN vAA, vBB, vCC + DF_DA | DF_UB | DF_UC | DF_NULL_CHK_0 | DF_RANGE_CHK_1 | DF_REF_B | DF_CORE_C, + + // 48 AGET_BYTE vAA, vBB, vCC + DF_DA | DF_UB | DF_UC | DF_NULL_CHK_0 | DF_RANGE_CHK_1 | DF_REF_B | DF_CORE_C, + + // 49 AGET_CHAR vAA, vBB, vCC + DF_DA | DF_UB | DF_UC | DF_NULL_CHK_0 | DF_RANGE_CHK_1 | DF_REF_B | DF_CORE_C, + + // 4A AGET_SHORT vAA, vBB, vCC + DF_DA | DF_UB | DF_UC | DF_NULL_CHK_0 | DF_RANGE_CHK_1 | DF_REF_B | DF_CORE_C, + + // 4B APUT vAA, vBB, vCC + DF_UA | DF_UB | DF_UC | DF_NULL_CHK_1 | DF_RANGE_CHK_2 | DF_REF_B | DF_CORE_C, + + // 4C APUT_WIDE vAA, vBB, vCC + DF_UA | DF_A_WIDE | DF_UB | DF_UC | DF_NULL_CHK_2 | DF_RANGE_CHK_3 | DF_REF_B | DF_CORE_C, + + // 4D APUT_OBJECT vAA, vBB, vCC + DF_UA | DF_UB | DF_UC | DF_NULL_CHK_1 | DF_RANGE_CHK_2 | DF_REF_A | DF_REF_B | DF_CORE_C, + + // 4E APUT_BOOLEAN vAA, vBB, vCC + DF_UA | DF_UB | DF_UC | DF_NULL_CHK_1 | DF_RANGE_CHK_2 | DF_REF_B | DF_CORE_C, + + // 4F APUT_BYTE vAA, vBB, vCC + DF_UA | DF_UB | DF_UC | DF_NULL_CHK_1 | DF_RANGE_CHK_2 | DF_REF_B | DF_CORE_C, + + // 50 APUT_CHAR vAA, vBB, vCC + DF_UA | DF_UB | DF_UC | DF_NULL_CHK_1 | DF_RANGE_CHK_2 | DF_REF_B | DF_CORE_C, + + // 51 APUT_SHORT vAA, vBB, vCC + DF_UA | DF_UB | DF_UC | DF_NULL_CHK_1 | DF_RANGE_CHK_2 | DF_REF_B | DF_CORE_C, + + // 52 IGET vA, vB, field@CCCC + DF_DA | DF_UB | DF_NULL_CHK_0 | DF_REF_B, + + // 53 IGET_WIDE vA, vB, field@CCCC + DF_DA | DF_A_WIDE | DF_UB | DF_NULL_CHK_0 | DF_REF_B, + + // 54 IGET_OBJECT vA, vB, field@CCCC + DF_DA | DF_UB | DF_NULL_CHK_0 | DF_REF_A | DF_REF_B, + + // 55 IGET_BOOLEAN vA, vB, field@CCCC + DF_DA | DF_UB | DF_NULL_CHK_0 | DF_REF_B, + + // 56 IGET_BYTE vA, vB, field@CCCC + DF_DA | DF_UB | DF_NULL_CHK_0 | DF_REF_B, + + // 57 IGET_CHAR vA, vB, field@CCCC + DF_DA | DF_UB | DF_NULL_CHK_0 | DF_REF_B, + + // 58 IGET_SHORT vA, vB, field@CCCC + DF_DA | DF_UB | DF_NULL_CHK_0 | DF_REF_B, + + // 59 IPUT vA, vB, field@CCCC + DF_UA | DF_UB | DF_NULL_CHK_1 | DF_REF_B, + + // 5A IPUT_WIDE vA, vB, field@CCCC + DF_UA | DF_A_WIDE | DF_UB | DF_NULL_CHK_2 | DF_REF_B, + + // 5B IPUT_OBJECT vA, vB, field@CCCC + DF_UA | DF_UB | DF_NULL_CHK_1 | DF_REF_A | DF_REF_B, + + // 5C IPUT_BOOLEAN vA, vB, field@CCCC + DF_UA | DF_UB | DF_NULL_CHK_1 | DF_REF_B, + + // 5D IPUT_BYTE vA, vB, field@CCCC + DF_UA | DF_UB | DF_NULL_CHK_1 | DF_REF_B, + + // 5E IPUT_CHAR vA, vB, field@CCCC + DF_UA | DF_UB | DF_NULL_CHK_1 | DF_REF_B, + + // 5F IPUT_SHORT vA, vB, field@CCCC + DF_UA | DF_UB | DF_NULL_CHK_1 | DF_REF_B, + + // 60 SGET vAA, field@BBBB + DF_DA | DF_UMS, + + // 61 SGET_WIDE vAA, field@BBBB + DF_DA | DF_A_WIDE | DF_UMS, + + // 62 SGET_OBJECT vAA, field@BBBB + DF_DA | DF_REF_A | DF_UMS, + + // 63 SGET_BOOLEAN vAA, field@BBBB + DF_DA | DF_UMS, + + // 64 SGET_BYTE vAA, field@BBBB + DF_DA | DF_UMS, + + // 65 SGET_CHAR vAA, field@BBBB + DF_DA | DF_UMS, + + // 66 SGET_SHORT vAA, field@BBBB + DF_DA | DF_UMS, + + // 67 SPUT vAA, field@BBBB + DF_UA | DF_UMS, + + // 68 SPUT_WIDE vAA, field@BBBB + DF_UA | DF_A_WIDE | DF_UMS, + + // 69 SPUT_OBJECT vAA, field@BBBB + DF_UA | DF_REF_A | DF_UMS, + + // 6A SPUT_BOOLEAN vAA, field@BBBB + DF_UA | DF_UMS, + + // 6B SPUT_BYTE vAA, field@BBBB + DF_UA | DF_UMS, + + // 6C SPUT_CHAR vAA, field@BBBB + DF_UA | DF_UMS, + + // 6D SPUT_SHORT vAA, field@BBBB + DF_UA | DF_UMS, + + // 6E INVOKE_VIRTUAL {vD, vE, vF, vG, vA} + DF_FORMAT_35C | DF_NULL_CHK_OUT0 | DF_UMS, + + // 6F INVOKE_SUPER {vD, vE, vF, vG, vA} + DF_FORMAT_35C | DF_NULL_CHK_OUT0 | DF_UMS, + + // 70 INVOKE_DIRECT {vD, vE, vF, vG, vA} + DF_FORMAT_35C | DF_NULL_CHK_OUT0 | DF_UMS, + + // 71 INVOKE_STATIC {vD, vE, vF, vG, vA} + DF_FORMAT_35C | DF_UMS, + + // 72 INVOKE_INTERFACE {vD, vE, vF, vG, vA} + DF_FORMAT_35C | DF_NULL_CHK_OUT0 | DF_UMS, + + // 73 UNUSED_73 + DF_NOP, + + // 74 INVOKE_VIRTUAL_RANGE {vCCCC .. vNNNN} + DF_FORMAT_3RC | DF_NULL_CHK_OUT0 | DF_UMS, + + // 75 INVOKE_SUPER_RANGE {vCCCC .. vNNNN} + DF_FORMAT_3RC | DF_NULL_CHK_OUT0 | DF_UMS, + + // 76 INVOKE_DIRECT_RANGE {vCCCC .. vNNNN} + DF_FORMAT_3RC | DF_NULL_CHK_OUT0 | DF_UMS, + + // 77 INVOKE_STATIC_RANGE {vCCCC .. vNNNN} + DF_FORMAT_3RC | DF_UMS, + + // 78 INVOKE_INTERFACE_RANGE {vCCCC .. vNNNN} + DF_FORMAT_3RC | DF_NULL_CHK_OUT0 | DF_UMS, + + // 79 UNUSED_79 + DF_NOP, + + // 7A UNUSED_7A + DF_NOP, + + // 7B NEG_INT vA, vB + DF_DA | DF_UB | DF_CORE_A | DF_CORE_B, + + // 7C NOT_INT vA, vB + DF_DA | DF_UB | DF_CORE_A | DF_CORE_B, + + // 7D NEG_LONG vA, vB + DF_DA | DF_A_WIDE | DF_UB | DF_B_WIDE | DF_CORE_A | DF_CORE_B, + + // 7E NOT_LONG vA, vB + DF_DA | DF_A_WIDE | DF_UB | DF_B_WIDE | DF_CORE_A | DF_CORE_B, + + // 7F NEG_FLOAT vA, vB + DF_DA | DF_UB | DF_FP_A | DF_FP_B, + + // 80 NEG_DOUBLE vA, vB + DF_DA | DF_A_WIDE | DF_UB | DF_B_WIDE | DF_FP_A | DF_FP_B, + + // 81 INT_TO_LONG vA, vB + DF_DA | DF_A_WIDE | DF_UB | DF_CORE_A | DF_CORE_B, + + // 82 INT_TO_FLOAT vA, vB + DF_DA | DF_UB | DF_FP_A | DF_CORE_B, + + // 83 INT_TO_DOUBLE vA, vB + DF_DA | DF_A_WIDE | DF_UB | DF_FP_A | DF_CORE_B, + + // 84 LONG_TO_INT vA, vB + DF_DA | DF_UB | DF_B_WIDE | DF_CORE_A | DF_CORE_B, + + // 85 LONG_TO_FLOAT vA, vB + DF_DA | DF_UB | DF_B_WIDE | DF_FP_A | DF_CORE_B, + + // 86 LONG_TO_DOUBLE vA, vB + DF_DA | DF_A_WIDE | DF_UB | DF_B_WIDE | DF_FP_A | DF_CORE_B, + + // 87 FLOAT_TO_INT vA, vB + DF_DA | DF_UB | DF_FP_B | DF_CORE_A, + + // 88 FLOAT_TO_LONG vA, vB + DF_DA | DF_A_WIDE | DF_UB | DF_FP_B | DF_CORE_A, + + // 89 FLOAT_TO_DOUBLE vA, vB + DF_DA | DF_A_WIDE | DF_UB | DF_FP_A | DF_FP_B, + + // 8A DOUBLE_TO_INT vA, vB + DF_DA | DF_UB | DF_B_WIDE | DF_FP_B | DF_CORE_A, + + // 8B DOUBLE_TO_LONG vA, vB + DF_DA | DF_A_WIDE | DF_UB | DF_B_WIDE | DF_FP_B | DF_CORE_A, + + // 8C DOUBLE_TO_FLOAT vA, vB + DF_DA | DF_UB | DF_B_WIDE | DF_FP_A | DF_FP_B, + + // 8D INT_TO_BYTE vA, vB + DF_DA | DF_UB | DF_CORE_A | DF_CORE_B, + + // 8E INT_TO_CHAR vA, vB + DF_DA | DF_UB | DF_CORE_A | DF_CORE_B, + + // 8F INT_TO_SHORT vA, vB + DF_DA | DF_UB | DF_CORE_A | DF_CORE_B, + + // 90 ADD_INT vAA, vBB, vCC + DF_DA | DF_UB | DF_UC | DF_CORE_A | DF_CORE_B | DF_CORE_C, + + // 91 SUB_INT vAA, vBB, vCC + DF_DA | DF_UB | DF_UC | DF_CORE_A | DF_CORE_B | DF_CORE_C, + + // 92 MUL_INT vAA, vBB, vCC + DF_DA | DF_UB | DF_UC | DF_CORE_A | DF_CORE_B | DF_CORE_C, + + // 93 DIV_INT vAA, vBB, vCC + DF_DA | DF_UB | DF_UC | DF_CORE_A | DF_CORE_B | DF_CORE_C, + + // 94 REM_INT vAA, vBB, vCC + DF_DA | DF_UB | DF_UC | DF_CORE_A | DF_CORE_B | DF_CORE_C, + + // 95 AND_INT vAA, vBB, vCC + DF_DA | DF_UB | DF_UC | DF_CORE_A | DF_CORE_B | DF_CORE_C, + + // 96 OR_INT vAA, vBB, vCC + DF_DA | DF_UB | DF_UC | DF_CORE_A | DF_CORE_B | DF_CORE_C, + + // 97 XOR_INT vAA, vBB, vCC + DF_DA | DF_UB | DF_UC | DF_CORE_A | DF_CORE_B | DF_CORE_C, + + // 98 SHL_INT vAA, vBB, vCC + DF_DA | DF_UB | DF_UC | DF_CORE_A | DF_CORE_B | DF_CORE_C, + + // 99 SHR_INT vAA, vBB, vCC + DF_DA | DF_UB | DF_UC | DF_CORE_A | DF_CORE_B | DF_CORE_C, + + // 9A USHR_INT vAA, vBB, vCC + DF_DA | DF_UB | DF_UC | DF_CORE_A | DF_CORE_B | DF_CORE_C, + + // 9B ADD_LONG vAA, vBB, vCC + DF_DA | DF_A_WIDE | DF_UB | DF_B_WIDE | DF_UC | DF_C_WIDE | DF_CORE_A | DF_CORE_B | DF_CORE_C, + + // 9C SUB_LONG vAA, vBB, vCC + DF_DA | DF_A_WIDE | DF_UB | DF_B_WIDE | DF_UC | DF_C_WIDE | DF_CORE_A | DF_CORE_B | DF_CORE_C, + + // 9D MUL_LONG vAA, vBB, vCC + DF_DA | DF_A_WIDE | DF_UB | DF_B_WIDE | DF_UC | DF_C_WIDE | DF_CORE_A | DF_CORE_B | DF_CORE_C, + + // 9E DIV_LONG vAA, vBB, vCC + DF_DA | DF_A_WIDE | DF_UB | DF_B_WIDE | DF_UC | DF_C_WIDE | DF_CORE_A | DF_CORE_B | DF_CORE_C, + + // 9F REM_LONG vAA, vBB, vCC + DF_DA | DF_A_WIDE | DF_UB | DF_B_WIDE | DF_UC | DF_C_WIDE | DF_CORE_A | DF_CORE_B | DF_CORE_C, + + // A0 AND_LONG vAA, vBB, vCC + DF_DA | DF_A_WIDE | DF_UB | DF_B_WIDE | DF_UC | DF_C_WIDE | DF_CORE_A | DF_CORE_B | DF_CORE_C, + + // A1 OR_LONG vAA, vBB, vCC + DF_DA | DF_A_WIDE | DF_UB | DF_B_WIDE | DF_UC | DF_C_WIDE | DF_CORE_A | DF_CORE_B | DF_CORE_C, + + // A2 XOR_LONG vAA, vBB, vCC + DF_DA | DF_A_WIDE | DF_UB | DF_B_WIDE | DF_UC | DF_C_WIDE | DF_CORE_A | DF_CORE_B | DF_CORE_C, + + // A3 SHL_LONG vAA, vBB, vCC + DF_DA | DF_A_WIDE | DF_UB | DF_B_WIDE | DF_UC | DF_CORE_A | DF_CORE_B | DF_CORE_C, + + // A4 SHR_LONG vAA, vBB, vCC + DF_DA | DF_A_WIDE | DF_UB | DF_B_WIDE | DF_UC | DF_CORE_A | DF_CORE_B | DF_CORE_C, + + // A5 USHR_LONG vAA, vBB, vCC + DF_DA | DF_A_WIDE | DF_UB | DF_B_WIDE | DF_UC | DF_CORE_A | DF_CORE_B | DF_CORE_C, + + // A6 ADD_FLOAT vAA, vBB, vCC + DF_DA | DF_UB | DF_UC | DF_FP_A | DF_FP_B | DF_FP_C, + + // A7 SUB_FLOAT vAA, vBB, vCC + DF_DA | DF_UB | DF_UC | DF_FP_A | DF_FP_B | DF_FP_C, + + // A8 MUL_FLOAT vAA, vBB, vCC + DF_DA | DF_UB | DF_UC | DF_FP_A | DF_FP_B | DF_FP_C, + + // A9 DIV_FLOAT vAA, vBB, vCC + DF_DA | DF_UB | DF_UC | DF_FP_A | DF_FP_B | DF_FP_C, + + // AA REM_FLOAT vAA, vBB, vCC + DF_DA | DF_UB | DF_UC | DF_FP_A | DF_FP_B | DF_FP_C, + + // AB ADD_DOUBLE vAA, vBB, vCC + DF_DA | DF_A_WIDE | DF_UB | DF_B_WIDE | DF_UC | DF_C_WIDE | DF_FP_A | DF_FP_B | DF_FP_C, + + // AC SUB_DOUBLE vAA, vBB, vCC + DF_DA | DF_A_WIDE | DF_UB | DF_B_WIDE | DF_UC | DF_C_WIDE | DF_FP_A | DF_FP_B | DF_FP_C, + + // AD MUL_DOUBLE vAA, vBB, vCC + DF_DA | DF_A_WIDE | DF_UB | DF_B_WIDE | DF_UC | DF_C_WIDE | DF_FP_A | DF_FP_B | DF_FP_C, + + // AE DIV_DOUBLE vAA, vBB, vCC + DF_DA | DF_A_WIDE | DF_UB | DF_B_WIDE | DF_UC | DF_C_WIDE | DF_FP_A | DF_FP_B | DF_FP_C, + + // AF REM_DOUBLE vAA, vBB, vCC + DF_DA | DF_A_WIDE | DF_UB | DF_B_WIDE | DF_UC | DF_C_WIDE | DF_FP_A | DF_FP_B | DF_FP_C, + + // B0 ADD_INT_2ADDR vA, vB + DF_DA | DF_UA | DF_UB | DF_CORE_A | DF_CORE_B, + + // B1 SUB_INT_2ADDR vA, vB + DF_DA | DF_UA | DF_UB | DF_CORE_A | DF_CORE_B, + + // B2 MUL_INT_2ADDR vA, vB + DF_DA | DF_UA | DF_UB | DF_CORE_A | DF_CORE_B, + + // B3 DIV_INT_2ADDR vA, vB + DF_DA | DF_UA | DF_UB | DF_CORE_A | DF_CORE_B, + + // B4 REM_INT_2ADDR vA, vB + DF_DA | DF_UA | DF_UB | DF_CORE_A | DF_CORE_B, + + // B5 AND_INT_2ADDR vA, vB + DF_DA | DF_UA | DF_UB | DF_CORE_A | DF_CORE_B, + + // B6 OR_INT_2ADDR vA, vB + DF_DA | DF_UA | DF_UB | DF_CORE_A | DF_CORE_B, + + // B7 XOR_INT_2ADDR vA, vB + DF_DA | DF_UA | DF_UB | DF_CORE_A | DF_CORE_B, + + // B8 SHL_INT_2ADDR vA, vB + DF_DA | DF_UA | DF_UB | DF_CORE_A | DF_CORE_B, + + // B9 SHR_INT_2ADDR vA, vB + DF_DA | DF_UA | DF_UB | DF_CORE_A | DF_CORE_B, + + // BA USHR_INT_2ADDR vA, vB + DF_DA | DF_UA | DF_UB | DF_CORE_A | DF_CORE_B, + + // BB ADD_LONG_2ADDR vA, vB + DF_DA | DF_A_WIDE | DF_UA | DF_UB | DF_B_WIDE | DF_CORE_A | DF_CORE_B, + + // BC SUB_LONG_2ADDR vA, vB + DF_DA | DF_A_WIDE | DF_UA | DF_UB | DF_B_WIDE | DF_CORE_A | DF_CORE_B, + + // BD MUL_LONG_2ADDR vA, vB + DF_DA | DF_A_WIDE | DF_UA | DF_UB | DF_B_WIDE | DF_CORE_A | DF_CORE_B, + + // BE DIV_LONG_2ADDR vA, vB + DF_DA | DF_A_WIDE | DF_UA | DF_UB | DF_B_WIDE | DF_CORE_A | DF_CORE_B, + + // BF REM_LONG_2ADDR vA, vB + DF_DA | DF_A_WIDE | DF_UA | DF_UB | DF_B_WIDE | DF_CORE_A | DF_CORE_B, + + // C0 AND_LONG_2ADDR vA, vB + DF_DA | DF_A_WIDE | DF_UA | DF_UB | DF_B_WIDE | DF_CORE_A | DF_CORE_B, + + // C1 OR_LONG_2ADDR vA, vB + DF_DA | DF_A_WIDE | DF_UA | DF_UB | DF_B_WIDE | DF_CORE_A | DF_CORE_B, + + // C2 XOR_LONG_2ADDR vA, vB + DF_DA | DF_A_WIDE | DF_UA | DF_UB | DF_B_WIDE | DF_CORE_A | DF_CORE_B, + + // C3 SHL_LONG_2ADDR vA, vB + DF_DA | DF_A_WIDE | DF_UA | DF_UB | DF_CORE_A | DF_CORE_B, + + // C4 SHR_LONG_2ADDR vA, vB + DF_DA | DF_A_WIDE | DF_UA | DF_UB | DF_CORE_A | DF_CORE_B, + + // C5 USHR_LONG_2ADDR vA, vB + DF_DA | DF_A_WIDE | DF_UA | DF_UB | DF_CORE_A | DF_CORE_B, + + // C6 ADD_FLOAT_2ADDR vA, vB + DF_DA | DF_UA | DF_UB | DF_FP_A | DF_FP_B, + + // C7 SUB_FLOAT_2ADDR vA, vB + DF_DA | DF_UA | DF_UB | DF_FP_A | DF_FP_B, + + // C8 MUL_FLOAT_2ADDR vA, vB + DF_DA | DF_UA | DF_UB | DF_FP_A | DF_FP_B, + + // C9 DIV_FLOAT_2ADDR vA, vB + DF_DA | DF_UA | DF_UB | DF_FP_A | DF_FP_B, + + // CA REM_FLOAT_2ADDR vA, vB + DF_DA | DF_UA | DF_UB | DF_FP_A | DF_FP_B, + + // CB ADD_DOUBLE_2ADDR vA, vB + DF_DA | DF_A_WIDE | DF_UA | DF_UB | DF_B_WIDE | DF_FP_A | DF_FP_B, + + // CC SUB_DOUBLE_2ADDR vA, vB + DF_DA | DF_A_WIDE | DF_UA | DF_UB | DF_B_WIDE | DF_FP_A | DF_FP_B, + + // CD MUL_DOUBLE_2ADDR vA, vB + DF_DA | DF_A_WIDE | DF_UA | DF_UB | DF_B_WIDE | DF_FP_A | DF_FP_B, + + // CE DIV_DOUBLE_2ADDR vA, vB + DF_DA | DF_A_WIDE | DF_UA | DF_UB | DF_B_WIDE | DF_FP_A | DF_FP_B, + + // CF REM_DOUBLE_2ADDR vA, vB + DF_DA | DF_A_WIDE | DF_UA | DF_UB | DF_B_WIDE | DF_FP_A | DF_FP_B, + + // D0 ADD_INT_LIT16 vA, vB, #+CCCC + DF_DA | DF_UB | DF_CORE_A | DF_CORE_B, + + // D1 RSUB_INT vA, vB, #+CCCC + DF_DA | DF_UB | DF_CORE_A | DF_CORE_B, + + // D2 MUL_INT_LIT16 vA, vB, #+CCCC + DF_DA | DF_UB | DF_CORE_A | DF_CORE_B, + + // D3 DIV_INT_LIT16 vA, vB, #+CCCC + DF_DA | DF_UB | DF_CORE_A | DF_CORE_B, + + // D4 REM_INT_LIT16 vA, vB, #+CCCC + DF_DA | DF_UB | DF_CORE_A | DF_CORE_B, + + // D5 AND_INT_LIT16 vA, vB, #+CCCC + DF_DA | DF_UB | DF_CORE_A | DF_CORE_B, + + // D6 OR_INT_LIT16 vA, vB, #+CCCC + DF_DA | DF_UB | DF_CORE_A | DF_CORE_B, + + // D7 XOR_INT_LIT16 vA, vB, #+CCCC + DF_DA | DF_UB | DF_CORE_A | DF_CORE_B, + + // D8 ADD_INT_LIT8 vAA, vBB, #+CC + DF_DA | DF_UB | DF_CORE_A | DF_CORE_B, + + // D9 RSUB_INT_LIT8 vAA, vBB, #+CC + DF_DA | DF_UB | DF_CORE_A | DF_CORE_B, + + // DA MUL_INT_LIT8 vAA, vBB, #+CC + DF_DA | DF_UB | DF_CORE_A | DF_CORE_B, + + // DB DIV_INT_LIT8 vAA, vBB, #+CC + DF_DA | DF_UB | DF_CORE_A | DF_CORE_B, + + // DC REM_INT_LIT8 vAA, vBB, #+CC + DF_DA | DF_UB | DF_CORE_A | DF_CORE_B, + + // DD AND_INT_LIT8 vAA, vBB, #+CC + DF_DA | DF_UB | DF_CORE_A | DF_CORE_B, + + // DE OR_INT_LIT8 vAA, vBB, #+CC + DF_DA | DF_UB | DF_CORE_A | DF_CORE_B, + + // DF XOR_INT_LIT8 vAA, vBB, #+CC + DF_DA | DF_UB | DF_CORE_A | DF_CORE_B, + + // E0 SHL_INT_LIT8 vAA, vBB, #+CC + DF_DA | DF_UB | DF_CORE_A | DF_CORE_B, + + // E1 SHR_INT_LIT8 vAA, vBB, #+CC + DF_DA | DF_UB | DF_CORE_A | DF_CORE_B, + + // E2 USHR_INT_LIT8 vAA, vBB, #+CC + DF_DA | DF_UB | DF_CORE_A | DF_CORE_B, + + // E3 IGET_VOLATILE + DF_DA | DF_UB | DF_NULL_CHK_0 | DF_REF_B, + + // E4 IPUT_VOLATILE + DF_UA | DF_UB | DF_NULL_CHK_1 | DF_REF_B, + + // E5 SGET_VOLATILE + DF_DA | DF_UMS, + + // E6 SPUT_VOLATILE + DF_UA | DF_UMS, + + // E7 IGET_OBJECT_VOLATILE + DF_DA | DF_UB | DF_NULL_CHK_0 | DF_REF_A | DF_REF_B, + + // E8 IGET_WIDE_VOLATILE + DF_DA | DF_A_WIDE | DF_UB | DF_NULL_CHK_0 | DF_REF_B, + + // E9 IPUT_WIDE_VOLATILE + DF_UA | DF_A_WIDE | DF_UB | DF_NULL_CHK_2 | DF_REF_B, + + // EA SGET_WIDE_VOLATILE + DF_DA | DF_A_WIDE | DF_UMS, + + // EB SPUT_WIDE_VOLATILE + DF_UA | DF_A_WIDE | DF_UMS, + + // EC BREAKPOINT + DF_NOP, + + // ED THROW_VERIFICATION_ERROR + DF_NOP | DF_UMS, + + // EE EXECUTE_INLINE + DF_FORMAT_35C, + + // EF EXECUTE_INLINE_RANGE + DF_FORMAT_3RC, + + // F0 INVOKE_OBJECT_INIT_RANGE + DF_NOP | DF_NULL_CHK_0, + + // F1 RETURN_VOID_BARRIER + DF_NOP, + + // F2 IGET_QUICK + DF_DA | DF_UB | DF_NULL_CHK_0, + + // F3 IGET_WIDE_QUICK + DF_DA | DF_A_WIDE | DF_UB | DF_NULL_CHK_0, + + // F4 IGET_OBJECT_QUICK + DF_DA | DF_UB | DF_NULL_CHK_0, + + // F5 IPUT_QUICK + DF_UA | DF_UB | DF_NULL_CHK_1, + + // F6 IPUT_WIDE_QUICK + DF_UA | DF_A_WIDE | DF_UB | DF_NULL_CHK_2, + + // F7 IPUT_OBJECT_QUICK + DF_UA | DF_UB | DF_NULL_CHK_1, + + // F8 INVOKE_VIRTUAL_QUICK + DF_FORMAT_35C | DF_NULL_CHK_OUT0 | DF_UMS, + + // F9 INVOKE_VIRTUAL_QUICK_RANGE + DF_FORMAT_3RC | DF_NULL_CHK_OUT0 | DF_UMS, + + // FA INVOKE_SUPER_QUICK + DF_FORMAT_35C | DF_NULL_CHK_OUT0 | DF_UMS, + + // FB INVOKE_SUPER_QUICK_RANGE + DF_FORMAT_3RC | DF_NULL_CHK_OUT0 | DF_UMS, + + // FC IPUT_OBJECT_VOLATILE + DF_UA | DF_UB | DF_NULL_CHK_1 | DF_REF_A | DF_REF_B, + + // FD SGET_OBJECT_VOLATILE + DF_DA | DF_REF_A | DF_UMS, + + // FE SPUT_OBJECT_VOLATILE + DF_UA | DF_REF_A | DF_UMS, + + // FF UNUSED_FF + DF_NOP +}; +} // end namespace sea_ir diff --git a/compiler/sea_ir/instruction_tools.h b/compiler/sea_ir/instruction_tools.h new file mode 100644 index 0000000..f68cdd0 --- /dev/null +++ b/compiler/sea_ir/instruction_tools.h @@ -0,0 +1,124 @@ +/* + * Copyright (C) 2013 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + + +#include "dex_instruction.h" + +#ifndef INSTRUCTION_TOOLS_H_ +#define INSTRUCTION_TOOLS_H_ + +// Note: This file has content cannibalized for SEA_IR from the MIR implementation, +// to avoid having a dependence on MIR. +namespace sea_ir { + +#define DF_NOP 0 +#define DF_UA (1 << kUA) +#define DF_UB (1 << kUB) +#define DF_UC (1 << kUC) +#define DF_A_WIDE (1 << kAWide) +#define DF_B_WIDE (1 << kBWide) +#define DF_C_WIDE (1 << kCWide) +#define DF_DA (1 << kDA) +#define DF_IS_MOVE (1 << kIsMove) +#define DF_SETS_CONST (1 << kSetsConst) +#define DF_FORMAT_35C (1 << kFormat35c) +#define DF_FORMAT_3RC (1 << kFormat3rc) +#define DF_NULL_CHK_0 (1 << kNullCheckSrc0) +#define DF_NULL_CHK_1 (1 << kNullCheckSrc1) +#define DF_NULL_CHK_2 (1 << kNullCheckSrc2) +#define DF_NULL_CHK_OUT0 (1 << kNullCheckOut0) +#define DF_NON_NULL_DST (1 << kDstNonNull) +#define DF_NON_NULL_RET (1 << kRetNonNull) +#define DF_NULL_TRANSFER_0 (1 << kNullTransferSrc0) +#define DF_NULL_TRANSFER_N (1 << kNullTransferSrcN) +#define DF_RANGE_CHK_1 (1 << kRangeCheckSrc1) +#define DF_RANGE_CHK_2 (1 << kRangeCheckSrc2) +#define DF_RANGE_CHK_3 (1 << kRangeCheckSrc3) +#define DF_FP_A (1 << kFPA) +#define DF_FP_B (1 << kFPB) +#define DF_FP_C (1 << kFPC) +#define DF_CORE_A (1 << kCoreA) +#define DF_CORE_B (1 << kCoreB) +#define DF_CORE_C (1 << kCoreC) +#define DF_REF_A (1 << kRefA) +#define DF_REF_B (1 << kRefB) +#define DF_REF_C (1 << kRefC) +#define DF_UMS (1 << kUsesMethodStar) + +#define DF_HAS_USES (DF_UA | DF_UB | DF_UC) + +#define DF_HAS_DEFS (DF_DA) + +#define DF_HAS_NULL_CHKS (DF_NULL_CHK_0 | \ + DF_NULL_CHK_1 | \ + DF_NULL_CHK_2 | \ + DF_NULL_CHK_OUT0) + +#define DF_HAS_RANGE_CHKS (DF_RANGE_CHK_1 | \ + DF_RANGE_CHK_2 | \ + DF_RANGE_CHK_3) + +#define DF_HAS_NR_CHKS (DF_HAS_NULL_CHKS | \ + DF_HAS_RANGE_CHKS) + +#define DF_A_IS_REG (DF_UA | DF_DA) +#define DF_B_IS_REG (DF_UB) +#define DF_C_IS_REG (DF_UC) +#define DF_IS_GETTER_OR_SETTER (DF_IS_GETTER | DF_IS_SETTER) +#define DF_USES_FP (DF_FP_A | DF_FP_B | DF_FP_C) + +enum DataFlowAttributePos { + kUA = 0, + kUB, + kUC, + kAWide, + kBWide, + kCWide, + kDA, + kIsMove, + kSetsConst, + kFormat35c, + kFormat3rc, + kNullCheckSrc0, // Null check of uses[0]. + kNullCheckSrc1, // Null check of uses[1]. + kNullCheckSrc2, // Null check of uses[2]. + kNullCheckOut0, // Null check out outgoing arg0. + kDstNonNull, // May assume dst is non-null. + kRetNonNull, // May assume retval is non-null. + kNullTransferSrc0, // Object copy src[0] -> dst. + kNullTransferSrcN, // Phi null check state transfer. + kRangeCheckSrc1, // Range check of uses[1]. + kRangeCheckSrc2, // Range check of uses[2]. + kRangeCheckSrc3, // Range check of uses[3]. + kFPA, + kFPB, + kFPC, + kCoreA, + kCoreB, + kCoreC, + kRefA, + kRefB, + kRefC, + kUsesMethodStar, // Implicit use of Method*. +}; + +class InstructionTools { + public: + static bool IsDefinition(const art::Instruction* instruction); + static const int instruction_attributes_[]; +}; +} // end namespace sea_ir +#endif // INSTRUCTION_TOOLS_H_ diff --git a/compiler/sea_ir/sea.cc b/compiler/sea_ir/sea.cc new file mode 100644 index 0000000..95c36e5 --- /dev/null +++ b/compiler/sea_ir/sea.cc @@ -0,0 +1,329 @@ +/* + * Copyright (C) 2013 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include "sea.h" + +#include "file_output_stream.h" + +#define MAX_REACHING_DEF_ITERERATIONS (10) + +namespace sea_ir { + +SeaGraph SeaGraph::graph_; +int SeaNode::current_max_node_id_ = 0; + + +SeaGraph* SeaGraph::GetCurrentGraph() { + return &sea_ir::SeaGraph::graph_; +} + +void SeaGraph::DumpSea(std::string filename) const { + std::string result; + result += "digraph seaOfNodes {\n"; + for (std::vector<Region*>::const_iterator cit = regions_.begin(); cit != regions_.end(); cit++) { + (*cit)->ToDot(result); + } + result += "}\n"; + art::File* file = art::OS::OpenFile(filename.c_str(), true, true); + art::FileOutputStream fos(file); + fos.WriteFully(result.c_str(), result.size()); + LOG(INFO) << "Written SEA string to file."; +} + +void SeaGraph::AddEdge(Region* src, Region* dst) const { + src->AddSuccessor(dst); + dst->AddPredecessor(src); +} + +void SeaGraph::ComputeDownExposedDefs() { + for (std::vector<Region*>::iterator region_it = regions_.begin(); + region_it != regions_.end(); region_it++) { + (*region_it)->ComputeDownExposedDefs(); + } +} + +void SeaGraph::ComputeReachingDefs() { + // Iterate until the reaching definitions set doesn't change anymore. + // (See Cooper & Torczon, "Engineering a Compiler", second edition, page 487) + bool changed = true; + int iteration = 0; + while (changed && (iteration < MAX_REACHING_DEF_ITERERATIONS)) { + iteration++; + changed = false; + // TODO: optimize the ordering if this becomes performance bottleneck. + for (std::vector<Region*>::iterator regions_it = regions_.begin(); + regions_it != regions_.end(); + regions_it++) { + changed |= (*regions_it)->UpdateReachingDefs(); + } + } + DCHECK(!changed) << "Reaching definitions computation did not reach a fixed point."; +} + + +void SeaGraph::CompileMethod(const art::DexFile::CodeItem* code_item, + uint32_t class_def_idx, uint32_t method_idx, const art::DexFile& dex_file) { + const uint16_t* code = code_item->insns_; + const size_t size_in_code_units = code_item->insns_size_in_code_units_; + + Region* r = NULL; + // This maps target instruction pointers to their corresponding region objects. + std::map<const uint16_t*, Region*> target_regions; + size_t i = 0; + + // Pass: Find the start instruction of basic blocks + // by locating targets and flow-though instructions of branches. + while (i < size_in_code_units) { + const art::Instruction* inst = art::Instruction::At(&code[i]); + if (inst->IsBranch()||inst->IsUnconditional()) { + int32_t offset = inst->GetTargetOffset(); + if (target_regions.end() == target_regions.find(&code[i+offset])) { + Region* region = GetNewRegion(); + target_regions.insert(std::pair<const uint16_t*, Region*>(&code[i+offset], region)); + } + if (inst->CanFlowThrough() && + (target_regions.end() == target_regions.find(&code[i+inst->SizeInCodeUnits()]))) { + Region* region = GetNewRegion(); + target_regions.insert(std::pair<const uint16_t*, Region*>(&code[i+inst->SizeInCodeUnits()], region)); + } + } + i += inst->SizeInCodeUnits(); + } + + // Pass: Assign instructions to region nodes and + // assign branches their control flow successors. + i = 0; + r = GetNewRegion(); + sea_ir::InstructionNode* last_node = NULL; + sea_ir::InstructionNode* node = NULL; + while (i < size_in_code_units) { + const art::Instruction* inst = art::Instruction::At(&code[i]); //TODO: find workaround for this + last_node = node; + node = new sea_ir::InstructionNode(inst); + + if (inst->IsBranch() || inst->IsUnconditional()) { + int32_t offset = inst->GetTargetOffset(); + std::map<const uint16_t*, Region*>::iterator it = target_regions.find(&code[i+offset]); + DCHECK(it != target_regions.end()); + AddEdge(r, it->second); // Add edge to branch target. + } + + std::map<const uint16_t*, Region*>::iterator it = target_regions.find(&code[i]); + if (target_regions.end() != it) { + // Get the already created region because this is a branch target. + Region* nextRegion = it->second; + if (last_node->GetInstruction()->IsBranch() && last_node->GetInstruction()->CanFlowThrough()) { + AddEdge(r, it->second); // Add flow-through edge. + } + r = nextRegion; + } + bool definesRegister = (0 != + InstructionTools::instruction_attributes_[inst->Opcode()] && (1 << kDA)); + LOG(INFO) << inst->GetDexPc(code) << "*** " << inst->DumpString(&dex_file) + << " region:" <<r->StringId() << "Definition?" << definesRegister << std::endl; + r->AddChild(node); + i += inst->SizeInCodeUnits(); + } + + // Pass: compute downward-exposed definitions. + ComputeDownExposedDefs(); + + // Multiple Passes: Compute reaching definitions (iterative fixed-point algorithm) + ComputeReachingDefs(); +} + +Region* SeaGraph::GetNewRegion() { + Region* new_region = new Region(); + AddRegion(new_region); + return new_region; +} + +void SeaGraph::AddRegion(Region* r) { + DCHECK(r) << "Tried to add NULL region to SEA graph."; + regions_.push_back(r); +} + +void Region::AddChild(sea_ir::InstructionNode* instruction) { + DCHECK(instruction) << "Tried to add NULL instruction to region node."; + instructions_.push_back(instruction); +} + +SeaNode* Region::GetLastChild() const { + if (instructions_.size() > 0) { + return instructions_.back(); + } + return NULL; +} + +void InstructionNode::ToDot(std::string& result) const { + result += "// Instruction: \n" + StringId() + + " [label=\"" + instruction_->DumpString(NULL) + "\""; + if (de_def_) { + result += "style=bold"; + } + result += "];\n"; +} + +int InstructionNode::GetResultRegister() const { + if (!InstructionTools::IsDefinition(instruction_)) { + return NO_REGISTER; + } + return instruction_->VRegA(); +} + +void InstructionNode::MarkAsDEDef() { + de_def_ = true; +} + +void Region::ToDot(std::string& result) const { + result += "\n// Region: \n" + StringId() + " [label=\"region " + StringId() + "\"];"; + // Save instruction nodes that belong to this region. + for (std::vector<InstructionNode*>::const_iterator cit = instructions_.begin(); + cit != instructions_.end(); cit++) { + (*cit)->ToDot(result); + result += StringId() + " -> " + (*cit)->StringId() + ";\n"; + } + + for (std::vector<Region*>::const_iterator cit = successors_.begin(); cit != successors_.end(); + cit++) { + DCHECK(NULL != *cit) << "Null successor found for SeaNode" << GetLastChild()->StringId() << "."; + result += GetLastChild()->StringId() + " -> " + (*cit)->StringId() + ";\n\n"; + } + + // Save reaching definitions. + for (std::map<int, std::set<sea_ir::InstructionNode*>* >::const_iterator cit = + reaching_defs_.begin(); + cit != reaching_defs_.end(); cit++) { + for (std::set<sea_ir::InstructionNode*>::const_iterator + reaching_set_it = (*cit).second->begin(); + reaching_set_it != (*cit).second->end(); + reaching_set_it++) { + result += (*reaching_set_it)->StringId() + + " -> " + StringId() + + " [style=dotted]; // Reaching def.\n"; + } + } + + result += "// End Region.\n"; +} + + +void Region::ComputeDownExposedDefs() { + for (std::vector<InstructionNode*>::const_iterator inst_it = instructions_.begin(); + inst_it != instructions_.end(); inst_it++) { + int reg_no = (*inst_it)->GetResultRegister(); + std::map<int, InstructionNode*>::iterator res = de_defs_.find(reg_no); + if ((reg_no != NO_REGISTER) && (res == de_defs_.end())) { + de_defs_.insert(std::pair<int, InstructionNode*>(reg_no, *inst_it)); + } else { + res->second = *inst_it; + } + } + + for (std::map<int, sea_ir::InstructionNode*>::const_iterator cit = de_defs_.begin(); + cit != de_defs_.end(); cit++) { + (*cit).second->MarkAsDEDef(); + } +} + + +const std::map<int, sea_ir::InstructionNode*>* Region::GetDownExposedDefs() const { + return &de_defs_; +} + +std::map<int, std::set<sea_ir::InstructionNode*>* >* Region::GetReachingDefs() { + return &reaching_defs_; +} + +bool Region::UpdateReachingDefs() { + std::map<int, std::set<sea_ir::InstructionNode*>* > new_reaching; + for (std::vector<Region*>::const_iterator pred_it = predecessors_.begin(); + pred_it != predecessors_.end(); pred_it++) { + // The reaching_defs variable will contain reaching defs __for current predecessor only__ + std::map<int, std::set<sea_ir::InstructionNode*>* > reaching_defs; + std::map<int, std::set<sea_ir::InstructionNode*>* >* pred_reaching = (*pred_it)->GetReachingDefs(); + const std::map<int, InstructionNode*>* de_defs = (*pred_it)->GetDownExposedDefs(); + + // The definitions from the reaching set of the predecessor + // may be shadowed by downward exposed definitions from the predecessor, + // otherwise the defs from the reaching set are still good. + for (std::map<int, InstructionNode*>::const_iterator de_def = de_defs->begin(); + de_def != de_defs->end(); de_def++) { + std::set<InstructionNode*>* solo_def; + solo_def = new std::set<InstructionNode*>(); + solo_def->insert(de_def->second); + reaching_defs.insert( + std::pair<int const, std::set<InstructionNode*>*>(de_def->first, solo_def)); + } + LOG(INFO) << "Adding to " <<StringId() << "reaching set of " << (*pred_it)->StringId(); + reaching_defs.insert(pred_reaching->begin(), pred_reaching->end()); + + // Now we combine the reaching map coming from the current predecessor (reaching_defs) + // with the accumulated set from all predecessors so far (from new_reaching). + std::map<int, std::set<sea_ir::InstructionNode*>*>::iterator reaching_it = reaching_defs.begin(); + for (; reaching_it != reaching_defs.end(); reaching_it++) { + std::map<int, std::set<sea_ir::InstructionNode*>*>::iterator crt_entry = + new_reaching.find(reaching_it->first); + if (new_reaching.end() != crt_entry) { + crt_entry->second->insert(reaching_it->second->begin(), reaching_it->second->end()); + } else { + new_reaching.insert( + std::pair<int, std::set<sea_ir::InstructionNode*>*>( + reaching_it->first, + reaching_it->second) ); + } + } + } + bool changed = false; + // Because the sets are monotonically increasing, + // we can compare sizes instead of using set comparison. + // TODO: Find formal proof. + int old_size = 0; + if (-1 == reaching_defs_size_) { + std::map<int, std::set<sea_ir::InstructionNode*>*>::iterator reaching_it = reaching_defs_.begin(); + for (; reaching_it != reaching_defs_.end(); reaching_it++) { + old_size += (*reaching_it).second->size(); + } + } else { + old_size = reaching_defs_size_; + } + int new_size = 0; + std::map<int, std::set<sea_ir::InstructionNode*>*>::iterator reaching_it = new_reaching.begin(); + for (; reaching_it != new_reaching.end(); reaching_it++) { + new_size += (*reaching_it).second->size(); + } + if (old_size != new_size) { + changed = true; + } + if (changed) { + reaching_defs_ = new_reaching; + reaching_defs_size_ = new_size; + } + return changed; +} + +void SeaNode::AddSuccessor(Region* successor) { + DCHECK(successor) << "Tried to add NULL successor to SEA node."; + successors_.push_back(successor); + return; +} + +void SeaNode::AddPredecessor(Region* predecessor) { + DCHECK(predecessor) << "Tried to add NULL predecessor to SEA node."; + predecessors_.push_back(predecessor); +} + +} // end namespace sea_ir diff --git a/compiler/sea_ir/sea.h b/compiler/sea_ir/sea.h new file mode 100644 index 0000000..f2c7146 --- /dev/null +++ b/compiler/sea_ir/sea.h @@ -0,0 +1,162 @@ +/* + * Copyright (C) 2013 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + + +#ifndef SEA_IR_H_ +#define SEA_IR_H_ + +#include <set> +#include <map> + +#include "dex_file.h" +#include "dex_instruction.h" +#include "sea_ir/instruction_tools.h" + +#define NO_REGISTER (-1) + +namespace sea_ir { +class Region; + +class SeaNode { + public: + explicit SeaNode():id_(GetNewId()), string_id_(), successors_(), predecessors_() { + std::stringstream ss; + ss << id_; + string_id_.append(ss.str()); + } + + // Adds CFG predecessors and successors to each block. + void AddSuccessor(Region* successor); + void AddPredecessor(Region* predecesor); + + // Returns the id of the current block as string + const std::string& StringId() const { + return string_id_; + } + + // Appends to @result a dot language formatted string representing the node and + // (by convention) outgoing edges, so that the composition of theToDot() of all nodes + // builds a complete dot graph, but without prolog ("digraph {") and epilog ("}"). + virtual void ToDot(std::string& result) const = 0; + + virtual ~SeaNode() {} + + protected: + static int GetNewId() { + return current_max_node_id_++; + } + + const int id_; + std::string string_id_; + std::vector<sea_ir::Region*> successors_; // CFG successor nodes (regions) + std::vector<sea_ir::Region*> predecessors_; // CFG predecessor nodes (instructions/regions) + + private: + static int current_max_node_id_; +}; + +class InstructionNode: public SeaNode { + public: + explicit InstructionNode(const art::Instruction* in):SeaNode(), instruction_(in), de_def_(false) {} + + const art::Instruction* GetInstruction() const { + DCHECK(NULL != instruction_) << "Tried to access NULL instruction in an InstructionNode."; + return instruction_; + } + // Returns the register that is defined by the current instruction, or NO_REGISTER otherwise. + int GetResultRegister() const; + void ToDot(std::string& result) const; + void MarkAsDEDef(); + + private: + const art::Instruction* const instruction_; + bool de_def_; +}; + + + +class Region : public SeaNode { + public: + explicit Region():SeaNode(), reaching_defs_size_(-1) {} + + // Adds @inst as an instruction node child in the current region. + void AddChild(sea_ir::InstructionNode* inst); + + // Returns the last instruction node child of the current region. + // This child has the CFG successors pointing to the new regions. + SeaNode* GetLastChild() const; + + // Appends to @result a dot language formatted string representing the node and + // (by convention) outgoing edges, so that the composition of theToDot() of all nodes + // builds a complete dot graph (without prolog and epilog though). + virtual void ToDot(std::string& result) const; + + // Computes Downward Exposed Definitions for the current node. + void ComputeDownExposedDefs(); + const std::map<int, sea_ir::InstructionNode*>* GetDownExposedDefs() const; + + // Performs one iteration of the reaching definitions algorithm + // and returns true if the reaching definitions set changed. + bool UpdateReachingDefs(); + + // Returns the set of reaching definitions for the current region. + std::map<int, std::set<sea_ir::InstructionNode*>* >* GetReachingDefs(); + + private: + std::vector<sea_ir::InstructionNode*> instructions_; + std::map<int, sea_ir::InstructionNode*> de_defs_; + std::map<int, std::set<sea_ir::InstructionNode*>* > reaching_defs_; + int reaching_defs_size_; +}; + + + +class SeaGraph { + public: + static SeaGraph* GetCurrentGraph(); + void CompileMethod(const art::DexFile::CodeItem* code_item, + uint32_t class_def_idx, uint32_t method_idx, const art::DexFile& dex_file); + + // Returns a string representation of the region and its Instruction children + void DumpSea(std::string filename) const; + + // Adds a CFG edge from @src node to @dst node. + void AddEdge(Region* src, Region* dst) const; + + // Computes Downward Exposed Definitions for all regions in the graph. + void ComputeDownExposedDefs(); + + // Computes the reaching definitions set following the equations from + // Cooper & Torczon, "Engineering a Compiler", second edition, page 491 + void ComputeReachingDefs(); + + /*** Static helper functions follow: ***/ + static int ParseInstruction(const uint16_t* code_ptr, + art::DecodedInstruction* decoded_instruction); + static bool IsInstruction(const uint16_t* code_ptr); + + private: + // Registers the parameter as a child region of the SeaGraph instance + void AddRegion(Region* r); + // Returns new region and registers it with the SeaGraph instance + Region* GetNewRegion(); + static SeaGraph graph_; + std::vector<Region*> regions_; +}; + + +} // end namespace sea_ir +#endif |