186ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil/* 286ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil * Copyright (C) 2016 The Android Open Source Project 386ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil * 486ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil * Licensed under the Apache License, Version 2.0 (the "License"); 586ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil * you may not use this file except in compliance with the License. 686ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil * You may obtain a copy of the License at 786ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil * 886ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil * http://www.apache.org/licenses/LICENSE-2.0 986ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil * 1086ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil * Unless required by applicable law or agreed to in writing, software 1186ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil * distributed under the License is distributed on an "AS IS" BASIS, 1286ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 1386ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil * See the License for the specific language governing permissions and 1486ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil * limitations under the License. 1586ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil */ 1686ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil 1786ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil#ifndef ART_COMPILER_OPTIMIZING_BYTECODE_UTILS_H_ 1886ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil#define ART_COMPILER_OPTIMIZING_BYTECODE_UTILS_H_ 1986ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil 2086ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil#include "base/arena_object.h" 2186ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil#include "dex_file.h" 2286ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil#include "dex_file-inl.h" 2386ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil#include "dex_instruction-inl.h" 2486ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil 2586ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdilnamespace art { 2686ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil 2786ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdilclass CodeItemIterator : public ValueObject { 2886ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil public: 2986ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil CodeItemIterator(const DexFile::CodeItem& code_item, uint32_t start_dex_pc = 0u) 3086ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil : code_ptr_(code_item.insns_ + start_dex_pc), 3186ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil code_end_(code_item.insns_ + code_item.insns_size_in_code_units_), 3286ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil dex_pc_(start_dex_pc) {} 3386ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil 3486ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil bool Done() const { return code_ptr_ >= code_end_; } 3586ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil bool IsLast() const { return code_ptr_ + CurrentInstruction().SizeInCodeUnits() >= code_end_; } 3686ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil 3786ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil const Instruction& CurrentInstruction() const { return *Instruction::At(code_ptr_); } 3886ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil uint32_t CurrentDexPc() const { return dex_pc_; } 3986ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil 4086ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil void Advance() { 4186ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil DCHECK(!Done()); 4286ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil size_t instruction_size = CurrentInstruction().SizeInCodeUnits(); 4386ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil code_ptr_ += instruction_size; 4486ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil dex_pc_ += instruction_size; 4586ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil } 4686ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil 4786ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil private: 4886ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil const uint16_t* code_ptr_; 4986ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil const uint16_t* const code_end_; 5086ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil uint32_t dex_pc_; 5186ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil 5286ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil DISALLOW_COPY_AND_ASSIGN(CodeItemIterator); 5386ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil}; 5486ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil 5586ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdilclass DexSwitchTable : public ValueObject { 5686ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil public: 5786ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil DexSwitchTable(const Instruction& instruction, uint32_t dex_pc) 5886ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil : instruction_(instruction), 5986ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil dex_pc_(dex_pc), 6086ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil sparse_(instruction.Opcode() == Instruction::SPARSE_SWITCH) { 6186ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil int32_t table_offset = instruction.VRegB_31t(); 6286ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil const uint16_t* table = reinterpret_cast<const uint16_t*>(&instruction) + table_offset; 6386ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil DCHECK_EQ(table[0], sparse_ ? static_cast<uint16_t>(Instruction::kSparseSwitchSignature) 6486ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil : static_cast<uint16_t>(Instruction::kPackedSwitchSignature)); 6586ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil num_entries_ = table[1]; 6686ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil values_ = reinterpret_cast<const int32_t*>(&table[2]); 6786ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil } 6886ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil 6986ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil uint16_t GetNumEntries() const { 7086ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil return num_entries_; 7186ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil } 7286ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil 7386ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil void CheckIndex(size_t index) const { 7486ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil if (sparse_) { 7586ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil // In a sparse table, we have num_entries_ keys and num_entries_ values, in that order. 7686ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil DCHECK_LT(index, 2 * static_cast<size_t>(num_entries_)); 7786ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil } else { 7886ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil // In a packed table, we have the starting key and num_entries_ values. 7986ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil DCHECK_LT(index, 1 + static_cast<size_t>(num_entries_)); 8086ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil } 8186ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil } 8286ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil 8386ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil int32_t GetEntryAt(size_t index) const { 8486ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil CheckIndex(index); 8586ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil return values_[index]; 8686ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil } 8786ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil 8886ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil uint32_t GetDexPcForIndex(size_t index) const { 8986ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil CheckIndex(index); 9086ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil return dex_pc_ + 9186ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil (reinterpret_cast<const int16_t*>(values_ + index) - 9286ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil reinterpret_cast<const int16_t*>(&instruction_)); 9386ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil } 9486ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil 9586ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil // Index of the first value in the table. 9686ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil size_t GetFirstValueIndex() const { 9786ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil if (sparse_) { 9886ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil // In a sparse table, we have num_entries_ keys and num_entries_ values, in that order. 9986ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil return num_entries_; 10086ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil } else { 10186ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil // In a packed table, we have the starting key and num_entries_ values. 10286ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil return 1; 10386ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil } 10486ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil } 10586ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil 10686ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil bool IsSparse() const { return sparse_; } 10786ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil 10886ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil bool ShouldBuildDecisionTree() { 10986ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil return IsSparse() || GetNumEntries() <= kSmallSwitchThreshold; 11086ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil } 11186ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil 11286ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil private: 11386ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil const Instruction& instruction_; 11486ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil const uint32_t dex_pc_; 11586ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil 11686ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil // Whether this is a sparse-switch table (or a packed-switch one). 11786ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil const bool sparse_; 11886ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil 11986ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil // This can't be const as it needs to be computed off of the given instruction, and complicated 12086ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil // expressions in the initializer list seemed very ugly. 12186ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil uint16_t num_entries_; 12286ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil 12386ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil const int32_t* values_; 12486ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil 12586ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil // The number of entries in a packed switch before we use a jump table or specified 12686ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil // compare/jump series. 12786ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil static constexpr uint16_t kSmallSwitchThreshold = 3; 12886ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil 12986ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil DISALLOW_COPY_AND_ASSIGN(DexSwitchTable); 13086ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil}; 13186ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil 13286ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdilclass DexSwitchTableIterator { 13386ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil public: 13486ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil explicit DexSwitchTableIterator(const DexSwitchTable& table) 13586ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil : table_(table), 13686ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil num_entries_(static_cast<size_t>(table_.GetNumEntries())), 13786ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil first_target_offset_(table_.GetFirstValueIndex()), 13886ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil index_(0u) {} 13986ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil 14086ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil bool Done() const { return index_ >= num_entries_; } 14186ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil bool IsLast() const { return index_ == num_entries_ - 1; } 14286ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil 14386ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil void Advance() { 14486ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil DCHECK(!Done()); 14586ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil index_++; 14686ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil } 14786ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil 14886ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil int32_t CurrentKey() const { 14986ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil return table_.IsSparse() ? table_.GetEntryAt(index_) : table_.GetEntryAt(0) + index_; 15086ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil } 15186ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil 15286ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil int32_t CurrentTargetOffset() const { 15386ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil return table_.GetEntryAt(index_ + first_target_offset_); 15486ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil } 15586ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil 15686ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil uint32_t GetDexPcForCurrentIndex() const { return table_.GetDexPcForIndex(index_); } 15786ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil 15886ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil private: 15986ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil const DexSwitchTable& table_; 16086ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil const size_t num_entries_; 16186ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil const size_t first_target_offset_; 16286ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil 16386ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil size_t index_; 16486ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil}; 16586ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil 16686ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdilinline const Instruction& GetDexInstructionAt(const DexFile::CodeItem& code_item, uint32_t dex_pc) { 16786ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil return CodeItemIterator(code_item, dex_pc).CurrentInstruction(); 16886ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil} 16986ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil 17086ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdilinline bool IsThrowingDexInstruction(const Instruction& instruction) { 17186ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil // Special-case MONITOR_EXIT which is a throwing instruction but the verifier 17286ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil // guarantees that it will never throw. This is necessary to avoid rejecting 17386ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil // 'synchronized' blocks/methods. 17486ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil return instruction.IsThrow() && instruction.Opcode() != Instruction::MONITOR_EXIT; 17586ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil} 17686ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil 17786ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil} // namespace art 17886ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil 17986ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil#endif // ART_COMPILER_OPTIMIZING_BYTECODE_UTILS_H_ 180