ART: Add PackedSwitch support to the optimizing compiler
Add simple packed-switch support through chained IFs.
Now enables compiled versions of 015-switch and 095-switch-MAX_INT.
Change-Id: I17cc8d659d1dd2d64227851c23998c04367e8cf5
diff --git a/compiler/optimizing/builder.cc b/compiler/optimizing/builder.cc
index eb6181c..4fa9f34 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,53 @@
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_;
+ }
+
+ int32_t GetEntryAt(size_t index) const {
+ DCHECK_LE(index, static_cast<size_t>(sparse_ ? num_entries_ - 1 : num_entries_));
+ return values_[index];
+ }
+
+ uint32_t GetDexPcForIndex(size_t index) const {
+ DCHECK_LE(index, static_cast<size_t>(sparse_ ? num_entries_ - 1 : num_entries_));
+ return dex_pc_ +
+ (reinterpret_cast<const int16_t*>(values_ + index) -
+ reinterpret_cast<const int16_t*>(&instruction_));
+ }
+
+ 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 +334,7 @@
size_t* number_of_dex_instructions,
size_t* number_of_blocks,
size_t* number_of_branches) {
- // TODO: Support switch instructions.
+ // TODO: Support sparse-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 +344,7 @@
// 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 +364,37 @@
branch_targets_.Put(dex_pc, block);
(*number_of_blocks)++;
}
+ } else if (instruction.Opcode() == Instruction::PACKED_SWITCH) {
+ SwitchTable table(instruction, dex_pc, false);
+
+ uint16_t num_entries = table.GetNumEntries();
+
+ // Entry @0: starting key. Use a larger loop counter type to avoid overflow issues.
+ for (size_t i = 1; i <= num_entries; ++i) {
+ // The target of the case.
+ uint32_t target = dex_pc + table.GetEntryAt(i);
+ 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();
@@ -863,6 +942,63 @@
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);
+
+ // Chained cmp-and-branch, starting from starting_key.
+ int32_t starting_key = table.GetEntryAt(0);
+
+ uint16_t num_entries = table.GetNumEntries();
+ // On overflow condition (or zero cases) just punt.
+ if (num_entries == 0 || num_entries == UINT16_MAX) {
+ return false;
+ }
+
+ for (size_t i = 1; i <= num_entries; i++) {
+ int32_t target_offset = table.GetEntryAt(i);
+ PotentiallyAddSuspendCheck(target_offset, dex_pc);
+
+ // The current case's value.
+ HInstruction* this_case_value = GetIntConstant(starting_key + i - 1);
+
+ // 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: Peel the last iteration to avoid conditional.
+ if (i < table.GetNumEntries()) {
+ HBasicBlock* next_case_target = FindBlockStartingAt(table.GetDexPcForIndex(i));
+ 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;
+ }
+ }
+ return true;
+}
+
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
@@ -1760,6 +1896,13 @@
break;
}
+ case Instruction::PACKED_SWITCH: {
+ if (!BuildPackedSwitch(instruction, dex_pc)) {
+ return false;
+ }
+ break;
+ }
+
default:
return false;
}
diff --git a/compiler/optimizing/builder.h b/compiler/optimizing/builder.h
index 8519bcb..0e46899 100644
--- a/compiler/optimizing/builder.h
+++ b/compiler/optimizing/builder.h
@@ -202,6 +202,10 @@
uint16_t type_index,
uint32_t dex_pc);
+ // Builds an instruction sequence for a packed switch statement. This will punt to the interpreter
+ // for a switch with a full 64k set of cases.
+ bool BuildPackedSwitch(const Instruction& instruction, uint32_t dex_pc);
+
ArenaAllocator* const arena_;
// A list of the size of the dex code holding block information for