From 8c18c2aaedb171f9b03ec49c94b0e33449dc411b Mon Sep 17 00:00:00 2001 From: Andreas Gampe Date: Wed, 6 Aug 2014 10:09:01 -0700 Subject: [PATCH] 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 --- compiler/dex/quick/arm/call_arm.cc | 6 +-- compiler/dex/quick/arm/codegen_arm.h | 4 +- compiler/dex/quick/arm64/call_arm64.cc | 6 +-- compiler/dex/quick/arm64/codegen_arm64.h | 4 +- compiler/dex/quick/gen_common.cc | 88 ++++++++++++++++++++++++++++++++ compiler/dex/quick/mips/call_mips.cc | 6 +-- compiler/dex/quick/mips/codegen_mips.h | 4 +- compiler/dex/quick/mir_to_lir.h | 18 ++++++- compiler/dex/quick/x86/call_x86.cc | 6 +-- compiler/dex/quick/x86/codegen_x86.h | 4 +- test/015-switch/expected.txt | 6 +++ test/015-switch/src/Main.java | 10 ++++ 12 files changed, 136 insertions(+), 26 deletions(-) diff --git a/compiler/dex/quick/arm/call_arm.cc b/compiler/dex/quick/arm/call_arm.cc index 5059c5fc9..b1339916f 100644 --- a/compiler/dex/quick/arm/call_arm.cc +++ b/compiler/dex/quick/arm/call_arm.cc @@ -43,8 +43,7 @@ namespace art { * 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::GenSparseSwitch(MIR* mir, uint32_t table_offset, } -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 9078298b4..cd6c9cc1e 100644 --- a/compiler/dex/quick/arm/codegen_arm.h +++ b/compiler/dex/quick/arm/codegen_arm.h @@ -131,8 +131,8 @@ class ArmMir2Lir FINAL : public Mir2Lir { 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 f00555a7c..28b747b59 100644 --- a/compiler/dex/quick/arm64/call_arm64.cc +++ b/compiler/dex/quick/arm64/call_arm64.cc @@ -43,8 +43,7 @@ namespace art { * 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::GenSparseSwitch(MIR* mir, uint32_t table_offset, } -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 149bafd45..3e1c18baf 100644 --- a/compiler/dex/quick/arm64/codegen_arm64.h +++ b/compiler/dex/quick/arm64/codegen_arm64.h @@ -197,8 +197,8 @@ class Arm64Mir2Lir FINAL : public Mir2Lir { 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 0054f3432..f6c77fcea 100644 --- a/compiler/dex/quick/gen_common.cc +++ b/compiler/dex/quick/gen_common.cc @@ -2008,4 +2008,92 @@ void Mir2Lir::GenConstWide(RegLocation rl_dest, int64_t value) { 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(&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(&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 9adddf079..4577a4c90 100644 --- a/compiler/dex/quick/mips/call_mips.cc +++ b/compiler/dex/quick/mips/call_mips.cc @@ -61,8 +61,7 @@ bool MipsMir2Lir::GenSpecialCase(BasicBlock* bb, MIR* mir, * 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 @@ void MipsMir2Lir::GenSparseSwitch(MIR* mir, DexOffset table_offset, * 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 bd0c020ce..43cbde778 100644 --- a/compiler/dex/quick/mips/codegen_mips.h +++ b/compiler/dex/quick/mips/codegen_mips.h @@ -128,8 +128,8 @@ class MipsMir2Lir FINAL : public Mir2Lir { 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 4ed992933..0e6f36bde 100644 --- a/compiler/dex/quick/mir_to_lir.h +++ b/compiler/dex/quick/mir_to_lir.h @@ -229,6 +229,9 @@ class Mir2Lir : public Backend { 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 @@ class Mir2Lir : public Backend { 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 15aae9ef1..f5f86717b 100644 --- a/compiler/dex/quick/x86/call_x86.cc +++ b/compiler/dex/quick/x86/call_x86.cc @@ -27,8 +27,7 @@ namespace art { * The sparse table in the literal pool is an array of * 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 @@ void X86Mir2Lir::GenSparseSwitch(MIR* mir, DexOffset table_offset, * 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 266191adc..d74caae0c 100644 --- a/compiler/dex/quick/x86/codegen_x86.h +++ b/compiler/dex/quick/x86/codegen_x86.h @@ -246,8 +246,8 @@ class X86Mir2Lir : public Mir2Lir { 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 ca3b518f0..91b47142d 100644 --- a/test/015-switch/expected.txt +++ b/test/015-switch/expected.txt @@ -8,3 +8,9 @@ CORRECT (not found) 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 7198e2b7b..dd97a8c60 100644 --- a/test/015-switch/src/Main.java +++ b/test/015-switch/src/Main.java @@ -101,5 +101,15 @@ public class Main { 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; + } + } } } -- 2.11.0