ART: Generate chained compare-and-branch for short switches
Refactor Mir2Lir to generate chained compare-and-branch sequences
for short switches on all architectures.
Bug: 16241558
(cherry picked from commit 48971b3242e5126bcd800cc9c68df64596b43d13)
Change-Id: I0bb3071b8676523e90e0258e9b0e3fd69c1237f4
diff --git a/compiler/dex/quick/arm/call_arm.cc b/compiler/dex/quick/arm/call_arm.cc
index 5059c5f..b133991 100644
--- a/compiler/dex/quick/arm/call_arm.cc
+++ b/compiler/dex/quick/arm/call_arm.cc
@@ -43,8 +43,7 @@
* add rARM_PC, r_disp ; This is the branch from which we compute displacement
* cbnz r_idx, lp
*/
-void ArmMir2Lir::GenSparseSwitch(MIR* mir, uint32_t table_offset,
- RegLocation rl_src) {
+void ArmMir2Lir::GenLargeSparseSwitch(MIR* mir, uint32_t table_offset, RegLocation rl_src) {
const uint16_t* table = cu_->insns + current_dalvik_offset_ + table_offset;
if (cu_->verbose) {
DumpSparseSwitchTable(table);
@@ -92,8 +91,7 @@
}
-void ArmMir2Lir::GenPackedSwitch(MIR* mir, uint32_t table_offset,
- RegLocation rl_src) {
+void ArmMir2Lir::GenLargePackedSwitch(MIR* mir, uint32_t table_offset, RegLocation rl_src) {
const uint16_t* table = cu_->insns + current_dalvik_offset_ + table_offset;
if (cu_->verbose) {
DumpPackedSwitchTable(table);
diff --git a/compiler/dex/quick/arm/codegen_arm.h b/compiler/dex/quick/arm/codegen_arm.h
index 9078298..cd6c9cc 100644
--- a/compiler/dex/quick/arm/codegen_arm.h
+++ b/compiler/dex/quick/arm/codegen_arm.h
@@ -131,8 +131,8 @@
int first_bit, int second_bit);
void GenNegDouble(RegLocation rl_dest, RegLocation rl_src);
void GenNegFloat(RegLocation rl_dest, RegLocation rl_src);
- void GenPackedSwitch(MIR* mir, DexOffset table_offset, RegLocation rl_src);
- void GenSparseSwitch(MIR* mir, DexOffset table_offset, RegLocation rl_src);
+ void GenLargePackedSwitch(MIR* mir, DexOffset table_offset, RegLocation rl_src);
+ void GenLargeSparseSwitch(MIR* mir, DexOffset table_offset, RegLocation rl_src);
// Required for target - single operation generators.
LIR* OpUnconditionalBranch(LIR* target);
diff --git a/compiler/dex/quick/arm64/call_arm64.cc b/compiler/dex/quick/arm64/call_arm64.cc
index f00555a..28b747b 100644
--- a/compiler/dex/quick/arm64/call_arm64.cc
+++ b/compiler/dex/quick/arm64/call_arm64.cc
@@ -43,8 +43,7 @@
* br r_base
* quit:
*/
-void Arm64Mir2Lir::GenSparseSwitch(MIR* mir, uint32_t table_offset,
- RegLocation rl_src) {
+void Arm64Mir2Lir::GenLargeSparseSwitch(MIR* mir, uint32_t table_offset, RegLocation rl_src) {
const uint16_t* table = cu_->insns + current_dalvik_offset_ + table_offset;
if (cu_->verbose) {
DumpSparseSwitchTable(table);
@@ -96,8 +95,7 @@
}
-void Arm64Mir2Lir::GenPackedSwitch(MIR* mir, uint32_t table_offset,
- RegLocation rl_src) {
+void Arm64Mir2Lir::GenLargePackedSwitch(MIR* mir, uint32_t table_offset, RegLocation rl_src) {
const uint16_t* table = cu_->insns + current_dalvik_offset_ + table_offset;
if (cu_->verbose) {
DumpPackedSwitchTable(table);
diff --git a/compiler/dex/quick/arm64/codegen_arm64.h b/compiler/dex/quick/arm64/codegen_arm64.h
index 149bafd..3e1c18b 100644
--- a/compiler/dex/quick/arm64/codegen_arm64.h
+++ b/compiler/dex/quick/arm64/codegen_arm64.h
@@ -197,8 +197,8 @@
int first_bit, int second_bit) OVERRIDE;
void GenNegDouble(RegLocation rl_dest, RegLocation rl_src) OVERRIDE;
void GenNegFloat(RegLocation rl_dest, RegLocation rl_src) OVERRIDE;
- void GenPackedSwitch(MIR* mir, DexOffset table_offset, RegLocation rl_src) OVERRIDE;
- void GenSparseSwitch(MIR* mir, DexOffset table_offset, RegLocation rl_src) OVERRIDE;
+ void GenLargePackedSwitch(MIR* mir, DexOffset table_offset, RegLocation rl_src) OVERRIDE;
+ void GenLargeSparseSwitch(MIR* mir, DexOffset table_offset, RegLocation rl_src) OVERRIDE;
// Required for target - single operation generators.
LIR* OpUnconditionalBranch(LIR* target) OVERRIDE;
diff --git a/compiler/dex/quick/gen_common.cc b/compiler/dex/quick/gen_common.cc
index 0054f34..f6c77fc 100644
--- a/compiler/dex/quick/gen_common.cc
+++ b/compiler/dex/quick/gen_common.cc
@@ -2008,4 +2008,92 @@
StoreValueWide(rl_dest, rl_result);
}
+void Mir2Lir::GenSmallPackedSwitch(MIR* mir, DexOffset table_offset, RegLocation rl_src) {
+ const uint16_t* table = cu_->insns + current_dalvik_offset_ + table_offset;
+ const uint16_t entries = table[1];
+ // Chained cmp-and-branch.
+ const int32_t* as_int32 = reinterpret_cast<const int32_t*>(&table[2]);
+ int32_t current_key = as_int32[0];
+ const int32_t* targets = &as_int32[1];
+ rl_src = LoadValue(rl_src, kCoreReg);
+ int i = 0;
+ for (; i < entries; i++, current_key++) {
+ if (!InexpensiveConstantInt(current_key, Instruction::Code::IF_EQ)) {
+ // Switch to using a temp and add.
+ break;
+ }
+ BasicBlock* case_block =
+ mir_graph_->FindBlock(current_dalvik_offset_ + targets[i]);
+ OpCmpImmBranch(kCondEq, rl_src.reg, current_key, &block_label_list_[case_block->id]);
+ }
+ if (i < entries) {
+ // The rest do not seem to be inexpensive. Try to allocate a temp and use add.
+ RegStorage key_temp = AllocTypedTemp(false, kCoreReg, false);
+ if (key_temp.Valid()) {
+ LoadConstantNoClobber(key_temp, current_key);
+ for (; i < entries - 1; i++, current_key++) {
+ BasicBlock* case_block =
+ mir_graph_->FindBlock(current_dalvik_offset_ + targets[i]);
+ OpCmpBranch(kCondEq, rl_src.reg, key_temp, &block_label_list_[case_block->id]);
+ OpRegImm(kOpAdd, key_temp, 1); // Increment key.
+ }
+ BasicBlock* case_block =
+ mir_graph_->FindBlock(current_dalvik_offset_ + targets[i]);
+ OpCmpBranch(kCondEq, rl_src.reg, key_temp, &block_label_list_[case_block->id]);
+ } else {
+ // No free temp, just finish the old loop.
+ for (; i < entries; i++, current_key++) {
+ BasicBlock* case_block =
+ mir_graph_->FindBlock(current_dalvik_offset_ + targets[i]);
+ OpCmpImmBranch(kCondEq, rl_src.reg, current_key, &block_label_list_[case_block->id]);
+ }
+ }
+ }
+}
+
+void Mir2Lir::GenPackedSwitch(MIR* mir, DexOffset table_offset, RegLocation rl_src) {
+ const uint16_t* table = cu_->insns + current_dalvik_offset_ + table_offset;
+ if (cu_->verbose) {
+ DumpSparseSwitchTable(table);
+ }
+
+ const uint16_t entries = table[1];
+ if (entries <= kSmallSwitchThreshold) {
+ GenSmallPackedSwitch(mir, table_offset, rl_src);
+ } else {
+ // Use the backend-specific implementation.
+ GenLargePackedSwitch(mir, table_offset, rl_src);
+ }
+}
+
+void Mir2Lir::GenSmallSparseSwitch(MIR* mir, DexOffset table_offset, RegLocation rl_src) {
+ const uint16_t* table = cu_->insns + current_dalvik_offset_ + table_offset;
+ const uint16_t entries = table[1];
+ // Chained cmp-and-branch.
+ const int32_t* keys = reinterpret_cast<const int32_t*>(&table[2]);
+ const int32_t* targets = &keys[entries];
+ rl_src = LoadValue(rl_src, kCoreReg);
+ for (int i = 0; i < entries; i++) {
+ int key = keys[i];
+ BasicBlock* case_block =
+ mir_graph_->FindBlock(current_dalvik_offset_ + targets[i]);
+ OpCmpImmBranch(kCondEq, rl_src.reg, key, &block_label_list_[case_block->id]);
+ }
+}
+
+void Mir2Lir::GenSparseSwitch(MIR* mir, DexOffset table_offset, RegLocation rl_src) {
+ const uint16_t* table = cu_->insns + current_dalvik_offset_ + table_offset;
+ if (cu_->verbose) {
+ DumpSparseSwitchTable(table);
+ }
+
+ const uint16_t entries = table[1];
+ if (entries <= kSmallSwitchThreshold) {
+ GenSmallSparseSwitch(mir, table_offset, rl_src);
+ } else {
+ // Use the backend-specific implementation.
+ GenLargeSparseSwitch(mir, table_offset, rl_src);
+ }
+}
+
} // namespace art
diff --git a/compiler/dex/quick/mips/call_mips.cc b/compiler/dex/quick/mips/call_mips.cc
index 9adddf0..4577a4c 100644
--- a/compiler/dex/quick/mips/call_mips.cc
+++ b/compiler/dex/quick/mips/call_mips.cc
@@ -61,8 +61,7 @@
* done:
*
*/
-void MipsMir2Lir::GenSparseSwitch(MIR* mir, DexOffset table_offset,
- RegLocation rl_src) {
+void MipsMir2Lir::GenLargeSparseSwitch(MIR* mir, DexOffset table_offset, RegLocation rl_src) {
const uint16_t* table = cu_->insns + current_dalvik_offset_ + table_offset;
if (cu_->verbose) {
DumpSparseSwitchTable(table);
@@ -139,8 +138,7 @@
* jr rRA
* done:
*/
-void MipsMir2Lir::GenPackedSwitch(MIR* mir, DexOffset table_offset,
- RegLocation rl_src) {
+void MipsMir2Lir::GenLargePackedSwitch(MIR* mir, DexOffset table_offset, RegLocation rl_src) {
const uint16_t* table = cu_->insns + current_dalvik_offset_ + table_offset;
if (cu_->verbose) {
DumpPackedSwitchTable(table);
diff --git a/compiler/dex/quick/mips/codegen_mips.h b/compiler/dex/quick/mips/codegen_mips.h
index bd0c020..43cbde7 100644
--- a/compiler/dex/quick/mips/codegen_mips.h
+++ b/compiler/dex/quick/mips/codegen_mips.h
@@ -128,8 +128,8 @@
int first_bit, int second_bit);
void GenNegDouble(RegLocation rl_dest, RegLocation rl_src);
void GenNegFloat(RegLocation rl_dest, RegLocation rl_src);
- void GenPackedSwitch(MIR* mir, uint32_t table_offset, RegLocation rl_src);
- void GenSparseSwitch(MIR* mir, uint32_t table_offset, RegLocation rl_src);
+ void GenLargePackedSwitch(MIR* mir, uint32_t table_offset, RegLocation rl_src);
+ void GenLargeSparseSwitch(MIR* mir, uint32_t table_offset, RegLocation rl_src);
bool GenSpecialCase(BasicBlock* bb, MIR* mir, const InlineMethod& special);
// Required for target - single operation generators.
diff --git a/compiler/dex/quick/mir_to_lir.h b/compiler/dex/quick/mir_to_lir.h
index 4ed9929..0e6f36b 100644
--- a/compiler/dex/quick/mir_to_lir.h
+++ b/compiler/dex/quick/mir_to_lir.h
@@ -229,6 +229,9 @@
static constexpr bool kFailOnSizeError = true && kIsDebugBuild;
static constexpr bool kReportSizeError = true && kIsDebugBuild;
+ // TODO: If necessary, this could be made target-dependent.
+ static constexpr uint16_t kSmallSwitchThreshold = 5;
+
/*
* Auxiliary information describing the location of data embedded in the Dalvik
* byte code stream.
@@ -1355,8 +1358,19 @@
int first_bit, int second_bit) = 0;
virtual void GenNegDouble(RegLocation rl_dest, RegLocation rl_src) = 0;
virtual void GenNegFloat(RegLocation rl_dest, RegLocation rl_src) = 0;
- virtual void GenPackedSwitch(MIR* mir, DexOffset table_offset, RegLocation rl_src) = 0;
- virtual void GenSparseSwitch(MIR* mir, DexOffset table_offset, RegLocation rl_src) = 0;
+
+ // Create code for switch statements. Will decide between short and long versions below.
+ void GenPackedSwitch(MIR* mir, DexOffset table_offset, RegLocation rl_src);
+ void GenSparseSwitch(MIR* mir, DexOffset table_offset, RegLocation rl_src);
+
+ // Potentially backend-specific versions of switch instructions for shorter switch statements.
+ // The default implementation will create a chained compare-and-branch.
+ virtual void GenSmallPackedSwitch(MIR* mir, DexOffset table_offset, RegLocation rl_src);
+ virtual void GenSmallSparseSwitch(MIR* mir, DexOffset table_offset, RegLocation rl_src);
+ // Backend-specific versions of switch instructions for longer switch statements.
+ virtual void GenLargePackedSwitch(MIR* mir, DexOffset table_offset, RegLocation rl_src) = 0;
+ virtual void GenLargeSparseSwitch(MIR* mir, DexOffset table_offset, RegLocation rl_src) = 0;
+
virtual void GenArrayGet(int opt_flags, OpSize size, RegLocation rl_array,
RegLocation rl_index, RegLocation rl_dest, int scale) = 0;
virtual void GenArrayPut(int opt_flags, OpSize size, RegLocation rl_array,
diff --git a/compiler/dex/quick/x86/call_x86.cc b/compiler/dex/quick/x86/call_x86.cc
index 15aae9e..f5f8671 100644
--- a/compiler/dex/quick/x86/call_x86.cc
+++ b/compiler/dex/quick/x86/call_x86.cc
@@ -27,8 +27,7 @@
* The sparse table in the literal pool is an array of <key,displacement>
* pairs.
*/
-void X86Mir2Lir::GenSparseSwitch(MIR* mir, DexOffset table_offset,
- RegLocation rl_src) {
+void X86Mir2Lir::GenLargeSparseSwitch(MIR* mir, DexOffset table_offset, RegLocation rl_src) {
const uint16_t* table = cu_->insns + current_dalvik_offset_ + table_offset;
if (cu_->verbose) {
DumpSparseSwitchTable(table);
@@ -61,8 +60,7 @@
* jmp r_start_of_method
* done:
*/
-void X86Mir2Lir::GenPackedSwitch(MIR* mir, DexOffset table_offset,
- RegLocation rl_src) {
+void X86Mir2Lir::GenLargePackedSwitch(MIR* mir, DexOffset table_offset, RegLocation rl_src) {
const uint16_t* table = cu_->insns + current_dalvik_offset_ + table_offset;
if (cu_->verbose) {
DumpPackedSwitchTable(table);
diff --git a/compiler/dex/quick/x86/codegen_x86.h b/compiler/dex/quick/x86/codegen_x86.h
index 266191a..d74caae 100644
--- a/compiler/dex/quick/x86/codegen_x86.h
+++ b/compiler/dex/quick/x86/codegen_x86.h
@@ -246,8 +246,8 @@
int first_bit, int second_bit) OVERRIDE;
void GenNegDouble(RegLocation rl_dest, RegLocation rl_src) OVERRIDE;
void GenNegFloat(RegLocation rl_dest, RegLocation rl_src) OVERRIDE;
- void GenPackedSwitch(MIR* mir, DexOffset table_offset, RegLocation rl_src) OVERRIDE;
- void GenSparseSwitch(MIR* mir, DexOffset table_offset, RegLocation rl_src) OVERRIDE;
+ void GenLargePackedSwitch(MIR* mir, DexOffset table_offset, RegLocation rl_src) OVERRIDE;
+ void GenLargeSparseSwitch(MIR* mir, DexOffset table_offset, RegLocation rl_src) OVERRIDE;
/**
* @brief Implement instanceof a final class with x86 specific code.
diff --git a/test/015-switch/expected.txt b/test/015-switch/expected.txt
index ca3b518..91b4714 100644
--- a/test/015-switch/expected.txt
+++ b/test/015-switch/expected.txt
@@ -8,3 +8,9 @@
CORRECT (default only)
CORRECT big sparse / first
CORRECT big sparse / last
+default
+254
+255
+256
+257
+default
diff --git a/test/015-switch/src/Main.java b/test/015-switch/src/Main.java
index 7198e2b..dd97a8c 100644
--- a/test/015-switch/src/Main.java
+++ b/test/015-switch/src/Main.java
@@ -101,5 +101,15 @@
case 100: System.out.print("CORRECT big sparse / last\n"); break;
default: System.out.print("blah!\n"); break;
}
+
+ for (a = 253; a <= 258; a++) {
+ switch (a) {
+ case 254: System.out.println("254"); break;
+ case 255: System.out.println("255"); break;
+ case 256: System.out.println("256"); break;
+ case 257: System.out.println("257"); break;
+ default: System.out.println("default"); break;
+ }
+ }
}
}