diff options
Diffstat (limited to 'compiler/optimizing/builder.cc')
| -rw-r--r-- | compiler/optimizing/builder.cc | 240 |
1 files changed, 226 insertions, 14 deletions
diff --git a/compiler/optimizing/builder.cc b/compiler/optimizing/builder.cc index eb6181c711..9561054b69 100644 --- a/compiler/optimizing/builder.cc +++ b/compiler/optimizing/builder.cc @@ -16,6 +16,7 @@ #include "builder.h" +#include "base/logging.h" #include "class_linker.h" #include "dex_file.h" #include "dex_file-inl.h" @@ -68,6 +69,74 @@ class Temporaries : public ValueObject { size_t index_; }; +class SwitchTable : public ValueObject { + public: + SwitchTable(const Instruction& instruction, uint32_t dex_pc, bool sparse) + : instruction_(instruction), dex_pc_(dex_pc), sparse_(sparse) { + int32_t table_offset = instruction.VRegB_31t(); + const uint16_t* table = reinterpret_cast<const uint16_t*>(&instruction) + table_offset; + if (sparse) { + CHECK_EQ(table[0], static_cast<uint16_t>(Instruction::kSparseSwitchSignature)); + } else { + CHECK_EQ(table[0], static_cast<uint16_t>(Instruction::kPackedSwitchSignature)); + } + num_entries_ = table[1]; + values_ = reinterpret_cast<const int32_t*>(&table[2]); + } + + uint16_t GetNumEntries() const { + return num_entries_; + } + + void CheckIndex(size_t index) const { + if (sparse_) { + // In a sparse table, we have num_entries_ keys and num_entries_ values, in that order. + DCHECK_LT(index, 2 * static_cast<size_t>(num_entries_)); + } else { + // In a packed table, we have the starting key and num_entries_ values. + DCHECK_LT(index, 1 + static_cast<size_t>(num_entries_)); + } + } + + int32_t GetEntryAt(size_t index) const { + CheckIndex(index); + return values_[index]; + } + + uint32_t GetDexPcForIndex(size_t index) const { + CheckIndex(index); + return dex_pc_ + + (reinterpret_cast<const int16_t*>(values_ + index) - + reinterpret_cast<const int16_t*>(&instruction_)); + } + + // Index of the first value in the table. + size_t GetFirstValueIndex() const { + if (sparse_) { + // In a sparse table, we have num_entries_ keys and num_entries_ values, in that order. + return num_entries_; + } else { + // In a packed table, we have the starting key and num_entries_ values. + return 1; + } + } + + private: + const Instruction& instruction_; + const uint32_t dex_pc_; + + // Whether this is a sparse-switch table (or a packed-switch one). + const bool sparse_; + + // This can't be const as it needs to be computed off of the given instruction, and complicated + // expressions in the initializer list seemed very ugly. + uint16_t num_entries_; + + const int32_t* values_; + + DISALLOW_COPY_AND_ASSIGN(SwitchTable); +}; + void HGraphBuilder::InitializeLocals(uint16_t count) { graph_->SetNumberOfVRegs(count); locals_.SetSize(count); @@ -286,7 +355,6 @@ void HGraphBuilder::ComputeBranchTargets(const uint16_t* code_ptr, size_t* number_of_dex_instructions, size_t* number_of_blocks, size_t* number_of_branches) { - // TODO: Support switch instructions. branch_targets_.SetSize(code_end - code_ptr); // Create the first block for the dex instructions, single successor of the entry block. @@ -296,7 +364,7 @@ void HGraphBuilder::ComputeBranchTargets(const uint16_t* code_ptr, // Iterate over all instructions and find branching instructions. Create blocks for // the locations these instructions branch to. - size_t dex_pc = 0; + uint32_t dex_pc = 0; while (code_ptr < code_end) { (*number_of_dex_instructions)++; const Instruction& instruction = *Instruction::At(code_ptr); @@ -316,6 +384,41 @@ void HGraphBuilder::ComputeBranchTargets(const uint16_t* code_ptr, branch_targets_.Put(dex_pc, block); (*number_of_blocks)++; } + } else if (instruction.IsSwitch()) { + SwitchTable table(instruction, dex_pc, instruction.Opcode() == Instruction::SPARSE_SWITCH); + + uint16_t num_entries = table.GetNumEntries(); + + // In a packed-switch, the entry at index 0 is the starting key. In a sparse-switch, the + // entry at index 0 is the first key, and values are after *all* keys. + size_t offset = table.GetFirstValueIndex(); + + // Use a larger loop counter type to avoid overflow issues. + for (size_t i = 0; i < num_entries; ++i) { + // The target of the case. + uint32_t target = dex_pc + table.GetEntryAt(i + offset); + if (FindBlockStartingAt(target) == nullptr) { + block = new (arena_) HBasicBlock(graph_, target); + branch_targets_.Put(target, block); + (*number_of_blocks)++; + } + + // The next case gets its own block. + if (i < num_entries) { + block = new (arena_) HBasicBlock(graph_, target); + branch_targets_.Put(table.GetDexPcForIndex(i), block); + (*number_of_blocks)++; + } + } + + // Fall-through. Add a block if there is more code afterwards. + dex_pc += instruction.SizeInCodeUnits(); + code_ptr += instruction.SizeInCodeUnits(); + if ((code_ptr < code_end) && (FindBlockStartingAt(dex_pc) == nullptr)) { + block = new (arena_) HBasicBlock(graph_, dex_pc); + branch_targets_.Put(dex_pc, block); + (*number_of_blocks)++; + } } else { code_ptr += instruction.SizeInCodeUnits(); dex_pc += instruction.SizeInCodeUnits(); @@ -337,9 +440,10 @@ void HGraphBuilder::Unop_12x(const Instruction& instruction, Primitive::Type typ void HGraphBuilder::Conversion_12x(const Instruction& instruction, Primitive::Type input_type, - Primitive::Type result_type) { + Primitive::Type result_type, + uint32_t dex_pc) { HInstruction* first = LoadLocal(instruction.VRegB(), input_type); - current_block_->AddInstruction(new (arena_) HTypeConversion(result_type, first)); + current_block_->AddInstruction(new (arena_) HTypeConversion(result_type, first, dex_pc)); UpdateLocal(instruction.VRegA(), current_block_->GetLastInstruction()); } @@ -863,6 +967,85 @@ bool HGraphBuilder::BuildTypeCheck(const Instruction& instruction, return true; } +bool HGraphBuilder::BuildPackedSwitch(const Instruction& instruction, uint32_t dex_pc) { + SwitchTable table(instruction, dex_pc, false); + + // Value to test against. + HInstruction* value = LoadLocal(instruction.VRegA(), Primitive::kPrimInt); + + uint16_t num_entries = table.GetNumEntries(); + // There should be at least one entry here. + DCHECK_GT(num_entries, 0U); + + // Chained cmp-and-branch, starting from starting_key. + int32_t starting_key = table.GetEntryAt(0); + + for (size_t i = 1; i <= num_entries; i++) { + BuildSwitchCaseHelper(instruction, i, i == num_entries, table, value, starting_key + i - 1, + table.GetEntryAt(i), dex_pc); + } + return true; +} + +bool HGraphBuilder::BuildSparseSwitch(const Instruction& instruction, uint32_t dex_pc) { + SwitchTable table(instruction, dex_pc, true); + + // Value to test against. + HInstruction* value = LoadLocal(instruction.VRegA(), Primitive::kPrimInt); + + uint16_t num_entries = table.GetNumEntries(); + // There should be at least one entry here. + DCHECK_GT(num_entries, 0U); + + for (size_t i = 0; i < num_entries; i++) { + BuildSwitchCaseHelper(instruction, i, i == static_cast<size_t>(num_entries) - 1, table, value, + table.GetEntryAt(i), table.GetEntryAt(i + num_entries), dex_pc); + } + return true; +} + +void HGraphBuilder::BuildSwitchCaseHelper(const Instruction& instruction, size_t index, + bool is_last_case, const SwitchTable& table, + HInstruction* value, int32_t case_value_int, + int32_t target_offset, uint32_t dex_pc) { + PotentiallyAddSuspendCheck(target_offset, dex_pc); + + // The current case's value. + HInstruction* this_case_value = GetIntConstant(case_value_int); + + // Compare value and this_case_value. + HEqual* comparison = new (arena_) HEqual(value, this_case_value); + current_block_->AddInstruction(comparison); + HInstruction* ifinst = new (arena_) HIf(comparison); + current_block_->AddInstruction(ifinst); + + // Case hit: use the target offset to determine where to go. + HBasicBlock* case_target = FindBlockStartingAt(dex_pc + target_offset); + DCHECK(case_target != nullptr); + current_block_->AddSuccessor(case_target); + + // Case miss: go to the next case (or default fall-through). + // When there is a next case, we use the block stored with the table offset representing this + // case (that is where we registered them in ComputeBranchTargets). + // When there is no next case, we use the following instruction. + // TODO: Find a good way to peel the last iteration to avoid conditional, but still have re-use. + if (!is_last_case) { + HBasicBlock* next_case_target = FindBlockStartingAt(table.GetDexPcForIndex(index)); + DCHECK(next_case_target != nullptr); + current_block_->AddSuccessor(next_case_target); + + // Need to manually add the block, as there is no dex-pc transition for the cases. + graph_->AddBlock(next_case_target); + + current_block_ = next_case_target; + } else { + HBasicBlock* default_target = FindBlockStartingAt(dex_pc + instruction.SizeInCodeUnits()); + DCHECK(default_target != nullptr); + current_block_->AddSuccessor(default_target); + current_block_ = nullptr; + } +} + void HGraphBuilder::PotentiallyAddSuspendCheck(int32_t target_offset, uint32_t dex_pc) { if (target_offset <= 0) { // Unconditionnally add a suspend check to backward branches. We can remove @@ -1079,52 +1262,67 @@ bool HGraphBuilder::AnalyzeDexInstruction(const Instruction& instruction, uint32 } case Instruction::INT_TO_LONG: { - Conversion_12x(instruction, Primitive::kPrimInt, Primitive::kPrimLong); + Conversion_12x(instruction, Primitive::kPrimInt, Primitive::kPrimLong, dex_pc); break; } case Instruction::INT_TO_FLOAT: { - Conversion_12x(instruction, Primitive::kPrimInt, Primitive::kPrimFloat); + Conversion_12x(instruction, Primitive::kPrimInt, Primitive::kPrimFloat, dex_pc); break; } case Instruction::INT_TO_DOUBLE: { - Conversion_12x(instruction, Primitive::kPrimInt, Primitive::kPrimDouble); + Conversion_12x(instruction, Primitive::kPrimInt, Primitive::kPrimDouble, dex_pc); break; } case Instruction::LONG_TO_INT: { - Conversion_12x(instruction, Primitive::kPrimLong, Primitive::kPrimInt); + Conversion_12x(instruction, Primitive::kPrimLong, Primitive::kPrimInt, dex_pc); break; } case Instruction::LONG_TO_FLOAT: { - Conversion_12x(instruction, Primitive::kPrimLong, Primitive::kPrimFloat); + Conversion_12x(instruction, Primitive::kPrimLong, Primitive::kPrimFloat, dex_pc); break; } case Instruction::LONG_TO_DOUBLE: { - Conversion_12x(instruction, Primitive::kPrimLong, Primitive::kPrimDouble); + Conversion_12x(instruction, Primitive::kPrimLong, Primitive::kPrimDouble, dex_pc); break; } case Instruction::FLOAT_TO_INT: { - Conversion_12x(instruction, Primitive::kPrimFloat, Primitive::kPrimInt); + Conversion_12x(instruction, Primitive::kPrimFloat, Primitive::kPrimInt, dex_pc); + break; + } + + case Instruction::FLOAT_TO_LONG: { + Conversion_12x(instruction, Primitive::kPrimFloat, Primitive::kPrimLong, dex_pc); + break; + } + + case Instruction::FLOAT_TO_DOUBLE: { + Conversion_12x(instruction, Primitive::kPrimFloat, Primitive::kPrimDouble, dex_pc); + break; + } + + case Instruction::DOUBLE_TO_FLOAT: { + Conversion_12x(instruction, Primitive::kPrimDouble, Primitive::kPrimFloat, dex_pc); break; } case Instruction::INT_TO_BYTE: { - Conversion_12x(instruction, Primitive::kPrimInt, Primitive::kPrimByte); + Conversion_12x(instruction, Primitive::kPrimInt, Primitive::kPrimByte, dex_pc); break; } case Instruction::INT_TO_SHORT: { - Conversion_12x(instruction, Primitive::kPrimInt, Primitive::kPrimShort); + Conversion_12x(instruction, Primitive::kPrimInt, Primitive::kPrimShort, dex_pc); break; } case Instruction::INT_TO_CHAR: { - Conversion_12x(instruction, Primitive::kPrimInt, Primitive::kPrimChar); + Conversion_12x(instruction, Primitive::kPrimInt, Primitive::kPrimChar, dex_pc); break; } @@ -1760,6 +1958,20 @@ bool HGraphBuilder::AnalyzeDexInstruction(const Instruction& instruction, uint32 break; } + case Instruction::PACKED_SWITCH: { + if (!BuildPackedSwitch(instruction, dex_pc)) { + return false; + } + break; + } + + case Instruction::SPARSE_SWITCH: { + if (!BuildSparseSwitch(instruction, dex_pc)) { + return false; + } + break; + } + default: return false; } |