ART: Add SparseSwitch support to the optimizing compiler
Add simple sparse-switch support through chained IFs. Refactor a
bit to better reuse code between switch types.
Now enables compiled versions of 015-switch and 095-switch-MAX_INT.
Bug: 18410979
Change-Id: Ib617e4b877f0b7fbc3bb289800f612f013480713
diff --git a/compiler/optimizing/builder.cc b/compiler/optimizing/builder.cc
index 76efef0..9561054 100644
--- a/compiler/optimizing/builder.cc
+++ b/compiler/optimizing/builder.cc
@@ -88,18 +88,39 @@
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 {
- DCHECK_LE(index, static_cast<size_t>(sparse_ ? num_entries_ - 1 : num_entries_));
+ CheckIndex(index);
return values_[index];
}
uint32_t GetDexPcForIndex(size_t index) const {
- DCHECK_LE(index, static_cast<size_t>(sparse_ ? num_entries_ - 1 : num_entries_));
+ 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_;
@@ -334,7 +355,6 @@
size_t* number_of_dex_instructions,
size_t* number_of_blocks,
size_t* number_of_branches) {
- // 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.
@@ -364,15 +384,19 @@
branch_targets_.Put(dex_pc, block);
(*number_of_blocks)++;
}
- } else if (instruction.Opcode() == Instruction::PACKED_SWITCH) {
- SwitchTable table(instruction, dex_pc, false);
+ } else if (instruction.IsSwitch()) {
+ SwitchTable table(instruction, dex_pc, instruction.Opcode() == Instruction::SPARSE_SWITCH);
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) {
+ // 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);
+ uint32_t target = dex_pc + table.GetEntryAt(i + offset);
if (FindBlockStartingAt(target) == nullptr) {
block = new (arena_) HBasicBlock(graph_, target);
branch_targets_.Put(target, block);
@@ -949,57 +973,79 @@
// 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);
- 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;
- }
+ 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
@@ -1919,6 +1965,13 @@
break;
}
+ case Instruction::SPARSE_SWITCH: {
+ if (!BuildSparseSwitch(instruction, dex_pc)) {
+ return false;
+ }
+ break;
+ }
+
default:
return false;
}
diff --git a/compiler/optimizing/builder.h b/compiler/optimizing/builder.h
index e4e3705..73c2f50 100644
--- a/compiler/optimizing/builder.h
+++ b/compiler/optimizing/builder.h
@@ -29,6 +29,7 @@
namespace art {
class Instruction;
+class SwitchTable;
class HGraphBuilder : public ValueObject {
public:
@@ -203,10 +204,17 @@
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.
+ // Builds an instruction sequence for a packed switch statement.
bool BuildPackedSwitch(const Instruction& instruction, uint32_t dex_pc);
+ // Builds an instruction sequence for a sparse switch statement.
+ bool BuildSparseSwitch(const Instruction& instruction, uint32_t dex_pc);
+
+ void 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);
+
ArenaAllocator* const arena_;
// A list of the size of the dex code holding block information for