summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--compiler/optimizing/builder.cc46
-rw-r--r--compiler/optimizing/builder.h9
-rw-r--r--compiler/optimizing/code_generator_arm.cc27
-rw-r--r--compiler/optimizing/code_generator_arm64.cc32
-rw-r--r--compiler/optimizing/code_generator_mips64.cc33
-rw-r--r--compiler/optimizing/code_generator_x86.cc32
-rw-r--r--compiler/optimizing/code_generator_x86_64.cc32
-rw-r--r--compiler/optimizing/dead_code_elimination.cc15
-rw-r--r--compiler/optimizing/graph_checker.cc16
-rw-r--r--compiler/optimizing/graph_checker.h1
-rw-r--r--compiler/optimizing/nodes.cc19
-rw-r--r--compiler/optimizing/nodes.h33
-rw-r--r--compiler/optimizing/register_allocator.cc6
13 files changed, 287 insertions, 14 deletions
diff --git a/compiler/optimizing/builder.cc b/compiler/optimizing/builder.cc
index 274a2a699f..9d70124a4c 100644
--- a/compiler/optimizing/builder.cc
+++ b/compiler/optimizing/builder.cc
@@ -1685,6 +1685,34 @@ bool HGraphBuilder::NeedsAccessCheck(uint32_t type_index) const {
dex_compilation_unit_->GetDexMethodIndex(), *dex_file_, type_index);
}
+void HGraphBuilder::BuildSwitchJumpTable(const SwitchTable& table,
+ const Instruction& instruction,
+ HInstruction* value,
+ uint32_t dex_pc) {
+ // Add the successor blocks to the current block.
+ uint16_t num_entries = table.GetNumEntries();
+ for (size_t i = 1; i <= num_entries; i++) {
+ int32_t target_offset = table.GetEntryAt(i);
+ HBasicBlock* case_target = FindBlockStartingAt(dex_pc + target_offset);
+ DCHECK(case_target != nullptr);
+
+ // Add the target block as a successor.
+ current_block_->AddSuccessor(case_target);
+ }
+
+ // Add the default target block as the last successor.
+ HBasicBlock* default_target = FindBlockStartingAt(dex_pc + instruction.SizeInCodeUnits());
+ DCHECK(default_target != nullptr);
+ current_block_->AddSuccessor(default_target);
+
+ // Now add the Switch instruction.
+ int32_t starting_key = table.GetEntryAt(0);
+ current_block_->AddInstruction(
+ new (arena_) HPackedSwitch(starting_key, num_entries, value, dex_pc));
+ // This block ends with control flow.
+ current_block_ = nullptr;
+}
+
void HGraphBuilder::BuildPackedSwitch(const Instruction& instruction, uint32_t dex_pc) {
// Verifier guarantees that the payload for PackedSwitch contains:
// (a) number of entries (may be zero)
@@ -1695,18 +1723,24 @@ void HGraphBuilder::BuildPackedSwitch(const Instruction& instruction, uint32_t d
// Value to test against.
HInstruction* value = LoadLocal(instruction.VRegA(), Primitive::kPrimInt, dex_pc);
+ // Starting key value.
+ int32_t starting_key = table.GetEntryAt(0);
+
// Retrieve number of entries.
uint16_t num_entries = table.GetNumEntries();
if (num_entries == 0) {
return;
}
- // 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);
+ // Don't use a packed switch if there are very few entries.
+ if (num_entries > kSmallSwitchThreshold) {
+ BuildSwitchJumpTable(table, instruction, value, dex_pc);
+ } else {
+ // Chained cmp-and-branch, starting from starting_key.
+ 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);
+ }
}
}
diff --git a/compiler/optimizing/builder.h b/compiler/optimizing/builder.h
index ae452f2589..7f87df6df2 100644
--- a/compiler/optimizing/builder.h
+++ b/compiler/optimizing/builder.h
@@ -90,6 +90,9 @@ class HGraphBuilder : public ValueObject {
static constexpr const char* kBuilderPassName = "builder";
+ // The number of entries in a packed switch before we use a jump table.
+ static constexpr uint16_t kSmallSwitchThreshold = 5;
+
private:
// Analyzes the dex instruction and adds HInstruction to the graph
// to execute that instruction. Returns whether the instruction can
@@ -239,6 +242,12 @@ class HGraphBuilder : public ValueObject {
// Builds an instruction sequence for a packed switch statement.
void BuildPackedSwitch(const Instruction& instruction, uint32_t dex_pc);
+ // Build a switch instruction from a packed switch statement.
+ void BuildSwitchJumpTable(const SwitchTable& table,
+ const Instruction& instruction,
+ HInstruction* value,
+ uint32_t dex_pc);
+
// Builds an instruction sequence for a sparse switch statement.
void BuildSparseSwitch(const Instruction& instruction, uint32_t dex_pc);
diff --git a/compiler/optimizing/code_generator_arm.cc b/compiler/optimizing/code_generator_arm.cc
index d431acfb53..4cf4596791 100644
--- a/compiler/optimizing/code_generator_arm.cc
+++ b/compiler/optimizing/code_generator_arm.cc
@@ -4946,6 +4946,33 @@ void InstructionCodeGeneratorARM::VisitFakeString(HFakeString* instruction ATTRI
// Will be generated at use site.
}
+// Simple implementation of packed switch - generate cascaded compare/jumps.
+void LocationsBuilderARM::VisitPackedSwitch(HPackedSwitch* switch_instr) {
+ LocationSummary* locations =
+ new (GetGraph()->GetArena()) LocationSummary(switch_instr, LocationSummary::kNoCall);
+ locations->SetInAt(0, Location::RequiresRegister());
+}
+
+void InstructionCodeGeneratorARM::VisitPackedSwitch(HPackedSwitch* switch_instr) {
+ int32_t lower_bound = switch_instr->GetStartValue();
+ int32_t num_entries = switch_instr->GetNumEntries();
+ LocationSummary* locations = switch_instr->GetLocations();
+ Register value_reg = locations->InAt(0).AsRegister<Register>();
+ HBasicBlock* default_block = switch_instr->GetDefaultBlock();
+
+ // Create a series of compare/jumps.
+ const ArenaVector<HBasicBlock*>& successors = switch_instr->GetBlock()->GetSuccessors();
+ for (int32_t i = 0; i < num_entries; i++) {
+ GenerateCompareWithImmediate(value_reg, lower_bound + i);
+ __ b(codegen_->GetLabelOf(successors.at(i)), EQ);
+ }
+
+ // And the default for any other value.
+ if (!codegen_->GoesToNextBlock(switch_instr->GetBlock(), default_block)) {
+ __ b(codegen_->GetLabelOf(default_block));
+ }
+}
+
void CodeGeneratorARM::MoveFromReturnRegister(Location trg, Primitive::Type type) {
if (!trg.IsValid()) {
DCHECK(type == Primitive::kPrimVoid);
diff --git a/compiler/optimizing/code_generator_arm64.cc b/compiler/optimizing/code_generator_arm64.cc
index 580e93e9c4..40dfedd3a2 100644
--- a/compiler/optimizing/code_generator_arm64.cc
+++ b/compiler/optimizing/code_generator_arm64.cc
@@ -3533,6 +3533,38 @@ void InstructionCodeGeneratorARM64::VisitFakeString(HFakeString* instruction ATT
// Will be generated at use site.
}
+// Simple implementation of packed switch - generate cascaded compare/jumps.
+void LocationsBuilderARM64::VisitPackedSwitch(HPackedSwitch* switch_instr) {
+ LocationSummary* locations =
+ new (GetGraph()->GetArena()) LocationSummary(switch_instr, LocationSummary::kNoCall);
+ locations->SetInAt(0, Location::RequiresRegister());
+}
+
+void InstructionCodeGeneratorARM64::VisitPackedSwitch(HPackedSwitch* switch_instr) {
+ int32_t lower_bound = switch_instr->GetStartValue();
+ int32_t num_entries = switch_instr->GetNumEntries();
+ Register value_reg = InputRegisterAt(switch_instr, 0);
+ HBasicBlock* default_block = switch_instr->GetDefaultBlock();
+
+ // Create a series of compare/jumps.
+ const ArenaVector<HBasicBlock*>& successors = switch_instr->GetBlock()->GetSuccessors();
+ for (int32_t i = 0; i < num_entries; i++) {
+ int32_t case_value = lower_bound + i;
+ vixl::Label* succ = codegen_->GetLabelOf(successors.at(i));
+ if (case_value == 0) {
+ __ Cbz(value_reg, succ);
+ } else {
+ __ Cmp(value_reg, vixl::Operand(case_value));
+ __ B(eq, succ);
+ }
+ }
+
+ // And the default for any other value.
+ if (!codegen_->GoesToNextBlock(switch_instr->GetBlock(), default_block)) {
+ __ B(codegen_->GetLabelOf(default_block));
+ }
+}
+
#undef __
#undef QUICK_ENTRY_POINT
diff --git a/compiler/optimizing/code_generator_mips64.cc b/compiler/optimizing/code_generator_mips64.cc
index 4722e42694..f93449e6be 100644
--- a/compiler/optimizing/code_generator_mips64.cc
+++ b/compiler/optimizing/code_generator_mips64.cc
@@ -3365,5 +3365,38 @@ void InstructionCodeGeneratorMIPS64::VisitFakeString(HFakeString* instruction AT
// Will be generated at use site.
}
+// Simple implementation of packed switch - generate cascaded compare/jumps.
+void LocationsBuilderMIPS64::VisitPackedSwitch(HPackedSwitch* switch_instr) {
+ LocationSummary* locations =
+ new (GetGraph()->GetArena()) LocationSummary(switch_instr, LocationSummary::kNoCall);
+ locations->SetInAt(0, Location::RequiresRegister());
+}
+
+void InstructionCodeGeneratorMIPS64::VisitPackedSwitch(HPackedSwitch* switch_instr) {
+ int32_t lower_bound = switch_instr->GetStartValue();
+ int32_t num_entries = switch_instr->GetNumEntries();
+ LocationSummary* locations = switch_instr->GetLocations();
+ GpuRegister value_reg = locations->InAt(0).AsRegister<GpuRegister>();
+ HBasicBlock* default_block = switch_instr->GetDefaultBlock();
+
+ // Create a series of compare/jumps.
+ const ArenaVector<HBasicBlock*>& successors = switch_instr->GetBlock()->GetSuccessors();
+ for (int32_t i = 0; i < num_entries; i++) {
+ int32_t case_value = lower_bound + i;
+ Label* succ = codegen_->GetLabelOf(successors.at(i));
+ if (case_value == 0) {
+ __ Beqzc(value_reg, succ);
+ } else {
+ __ LoadConst32(TMP, case_value);
+ __ Beqc(value_reg, TMP, succ);
+ }
+ }
+
+ // And the default for any other value.
+ if (!codegen_->GoesToNextBlock(switch_instr->GetBlock(), default_block)) {
+ __ B(codegen_->GetLabelOf(default_block));
+ }
+}
+
} // namespace mips64
} // namespace art
diff --git a/compiler/optimizing/code_generator_x86.cc b/compiler/optimizing/code_generator_x86.cc
index 3d03dd8146..4b185f03ce 100644
--- a/compiler/optimizing/code_generator_x86.cc
+++ b/compiler/optimizing/code_generator_x86.cc
@@ -5470,6 +5470,38 @@ void InstructionCodeGeneratorX86::VisitFakeString(HFakeString* instruction ATTRI
// Will be generated at use site.
}
+// Simple implementation of packed switch - generate cascaded compare/jumps.
+void LocationsBuilderX86::VisitPackedSwitch(HPackedSwitch* switch_instr) {
+ LocationSummary* locations =
+ new (GetGraph()->GetArena()) LocationSummary(switch_instr, LocationSummary::kNoCall);
+ locations->SetInAt(0, Location::RequiresRegister());
+}
+
+void InstructionCodeGeneratorX86::VisitPackedSwitch(HPackedSwitch* switch_instr) {
+ int32_t lower_bound = switch_instr->GetStartValue();
+ int32_t num_entries = switch_instr->GetNumEntries();
+ LocationSummary* locations = switch_instr->GetLocations();
+ Register value_reg = locations->InAt(0).AsRegister<Register>();
+ HBasicBlock* default_block = switch_instr->GetDefaultBlock();
+
+ // Create a series of compare/jumps.
+ const ArenaVector<HBasicBlock*>& successors = switch_instr->GetBlock()->GetSuccessors();
+ for (int i = 0; i < num_entries; i++) {
+ int32_t case_value = lower_bound + i;
+ if (case_value == 0) {
+ __ testl(value_reg, value_reg);
+ } else {
+ __ cmpl(value_reg, Immediate(case_value));
+ }
+ __ j(kEqual, codegen_->GetLabelOf(successors.at(i)));
+ }
+
+ // And the default for any other value.
+ if (!codegen_->GoesToNextBlock(switch_instr->GetBlock(), default_block)) {
+ __ jmp(codegen_->GetLabelOf(default_block));
+ }
+}
+
void LocationsBuilderX86::VisitX86ComputeBaseMethodAddress(
HX86ComputeBaseMethodAddress* insn) {
LocationSummary* locations =
diff --git a/compiler/optimizing/code_generator_x86_64.cc b/compiler/optimizing/code_generator_x86_64.cc
index 32a1db5475..7ee974fd11 100644
--- a/compiler/optimizing/code_generator_x86_64.cc
+++ b/compiler/optimizing/code_generator_x86_64.cc
@@ -5180,6 +5180,38 @@ void InstructionCodeGeneratorX86_64::VisitFakeString(HFakeString* instruction AT
// Will be generated at use site.
}
+// Simple implementation of packed switch - generate cascaded compare/jumps.
+void LocationsBuilderX86_64::VisitPackedSwitch(HPackedSwitch* switch_instr) {
+ LocationSummary* locations =
+ new (GetGraph()->GetArena()) LocationSummary(switch_instr, LocationSummary::kNoCall);
+ locations->SetInAt(0, Location::RequiresRegister());
+}
+
+void InstructionCodeGeneratorX86_64::VisitPackedSwitch(HPackedSwitch* switch_instr) {
+ int32_t lower_bound = switch_instr->GetStartValue();
+ int32_t num_entries = switch_instr->GetNumEntries();
+ LocationSummary* locations = switch_instr->GetLocations();
+ CpuRegister value_reg = locations->InAt(0).AsRegister<CpuRegister>();
+ HBasicBlock* default_block = switch_instr->GetDefaultBlock();
+
+ // Create a series of compare/jumps.
+ const ArenaVector<HBasicBlock*>& successors = switch_instr->GetBlock()->GetSuccessors();
+ for (int i = 0; i < num_entries; i++) {
+ int32_t case_value = lower_bound + i;
+ if (case_value == 0) {
+ __ testl(value_reg, value_reg);
+ } else {
+ __ cmpl(value_reg, Immediate(case_value));
+ }
+ __ j(kEqual, codegen_->GetLabelOf(successors.at(i)));
+ }
+
+ // And the default for any other value.
+ if (!codegen_->GoesToNextBlock(switch_instr->GetBlock(), default_block)) {
+ __ jmp(codegen_->GetLabelOf(default_block));
+ }
+}
+
void CodeGeneratorX86_64::Load64BitValue(CpuRegister dest, int64_t value) {
if (value == 0) {
__ xorl(dest, dest);
diff --git a/compiler/optimizing/dead_code_elimination.cc b/compiler/optimizing/dead_code_elimination.cc
index 7d509a22a6..345ff72148 100644
--- a/compiler/optimizing/dead_code_elimination.cc
+++ b/compiler/optimizing/dead_code_elimination.cc
@@ -41,6 +41,21 @@ static void MarkReachableBlocks(HBasicBlock* block, ArenaBitVector* visited) {
DCHECK(condition->AsIntConstant()->IsZero());
MarkReachableBlocks(if_instruction->IfFalseSuccessor(), visited);
}
+ } else if (last_instruction->IsPackedSwitch() &&
+ last_instruction->AsPackedSwitch()->InputAt(0)->IsIntConstant()) {
+ HPackedSwitch* switch_instruction = last_instruction->AsPackedSwitch();
+ int32_t switch_value = switch_instruction->InputAt(0)->AsIntConstant()->GetValue();
+ int32_t start_value = switch_instruction->GetStartValue();
+ int32_t last_value = start_value + switch_instruction->GetNumEntries();
+ for (int32_t case_value = start_value; case_value <= last_value; case_value++) {
+ if (case_value == last_value) {
+ MarkReachableBlocks(switch_instruction->GetDefaultBlock(), visited);
+ }
+ if (case_value == switch_value) {
+ MarkReachableBlocks(block->GetSuccessor(case_value - start_value), visited);
+ break;
+ }
+ }
} else {
for (HBasicBlock* successor : block->GetSuccessors()) {
MarkReachableBlocks(successor, visited);
diff --git a/compiler/optimizing/graph_checker.cc b/compiler/optimizing/graph_checker.cc
index 583da30438..4e1cafee66 100644
--- a/compiler/optimizing/graph_checker.cc
+++ b/compiler/optimizing/graph_checker.cc
@@ -743,6 +743,22 @@ void SSAChecker::HandleBooleanInput(HInstruction* instruction, size_t input_inde
}
}
+void SSAChecker::VisitPackedSwitch(HPackedSwitch* instruction) {
+ VisitInstruction(instruction);
+ // Check that the number of block successors matches the switch count plus
+ // one for the default block.
+ HBasicBlock* block = instruction->GetBlock();
+ if (instruction->GetNumEntries() + 1u != block->GetSuccessors().size()) {
+ AddError(StringPrintf(
+ "%s instruction %d in block %d expects %u successors to the block, but found: %zu.",
+ instruction->DebugName(),
+ instruction->GetId(),
+ block->GetBlockId(),
+ instruction->GetNumEntries() + 1u,
+ block->GetSuccessors().size()));
+ }
+}
+
void SSAChecker::VisitIf(HIf* instruction) {
VisitInstruction(instruction);
HandleBooleanInput(instruction, 0);
diff --git a/compiler/optimizing/graph_checker.h b/compiler/optimizing/graph_checker.h
index 0e270dbe18..7ddffc136a 100644
--- a/compiler/optimizing/graph_checker.h
+++ b/compiler/optimizing/graph_checker.h
@@ -125,6 +125,7 @@ class SSAChecker : public GraphChecker {
void VisitBinaryOperation(HBinaryOperation* op) OVERRIDE;
void VisitCondition(HCondition* op) OVERRIDE;
void VisitIf(HIf* instruction) OVERRIDE;
+ void VisitPackedSwitch(HPackedSwitch* instruction) OVERRIDE;
void VisitBooleanNot(HBooleanNot* instruction) OVERRIDE;
void VisitConstant(HConstant* instruction) OVERRIDE;
diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc
index b2407c520c..012858920f 100644
--- a/compiler/optimizing/nodes.cc
+++ b/compiler/optimizing/nodes.cc
@@ -1297,16 +1297,25 @@ void HBasicBlock::DisconnectAndDelete() {
// instructions.
for (HBasicBlock* predecessor : predecessors_) {
HInstruction* last_instruction = predecessor->GetLastInstruction();
- predecessor->RemoveInstruction(last_instruction);
predecessor->RemoveSuccessor(this);
- if (predecessor->GetSuccessors().size() == 1u) {
- DCHECK(last_instruction->IsIf());
+ uint32_t num_pred_successors = predecessor->GetSuccessors().size();
+ if (num_pred_successors == 1u) {
+ // If we have one successor after removing one, then we must have
+ // had an HIf or HPackedSwitch, as they have more than one successor.
+ // Replace those with a HGoto.
+ DCHECK(last_instruction->IsIf() || last_instruction->IsPackedSwitch());
+ predecessor->RemoveInstruction(last_instruction);
predecessor->AddInstruction(new (graph_->GetArena()) HGoto(last_instruction->GetDexPc()));
- } else {
+ } else if (num_pred_successors == 0u) {
// The predecessor has no remaining successors and therefore must be dead.
// We deliberately leave it without a control-flow instruction so that the
// SSAChecker fails unless it is not removed during the pass too.
- DCHECK_EQ(predecessor->GetSuccessors().size(), 0u);
+ predecessor->RemoveInstruction(last_instruction);
+ } else {
+ // There are multiple successors left. This must come from a HPackedSwitch
+ // and we are in the middle of removing the HPackedSwitch. Like above, leave
+ // this alone, and the SSAChecker will fail if it is not removed as well.
+ DCHECK(last_instruction->IsPackedSwitch());
}
}
predecessors_.clear();
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index 8dd31bef86..52f6e232ea 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -1056,6 +1056,7 @@ class HLoopInformationOutwardIterator : public ValueObject {
M(NullConstant, Instruction) \
M(NullCheck, Instruction) \
M(Or, BinaryOperation) \
+ M(PackedSwitch, Instruction) \
M(ParallelMove, Instruction) \
M(ParameterValue, Instruction) \
M(Phi, Instruction) \
@@ -2402,6 +2403,38 @@ class HCurrentMethod : public HExpression<0> {
DISALLOW_COPY_AND_ASSIGN(HCurrentMethod);
};
+// PackedSwitch (jump table). A block ending with a PackedSwitch instruction will
+// have one successor for each entry in the switch table, and the final successor
+// will be the block containing the next Dex opcode.
+class HPackedSwitch : public HTemplateInstruction<1> {
+ public:
+ HPackedSwitch(int32_t start_value, int32_t num_entries, HInstruction* input,
+ uint32_t dex_pc = kNoDexPc)
+ : HTemplateInstruction(SideEffects::None(), dex_pc),
+ start_value_(start_value),
+ num_entries_(num_entries) {
+ SetRawInputAt(0, input);
+ }
+
+ bool IsControlFlow() const OVERRIDE { return true; }
+
+ int32_t GetStartValue() const { return start_value_; }
+
+ int32_t GetNumEntries() const { return num_entries_; }
+
+ HBasicBlock* GetDefaultBlock() const {
+ // Last entry is the default block.
+ return GetBlock()->GetSuccessor(num_entries_);
+ }
+ DECLARE_INSTRUCTION(PackedSwitch);
+
+ private:
+ int32_t start_value_;
+ int32_t num_entries_;
+
+ DISALLOW_COPY_AND_ASSIGN(HPackedSwitch);
+};
+
class HUnaryOperation : public HExpression<1> {
public:
HUnaryOperation(Primitive::Type result_type, HInstruction* input, uint32_t dex_pc = kNoDexPc)
diff --git a/compiler/optimizing/register_allocator.cc b/compiler/optimizing/register_allocator.cc
index a4f1f458fd..9594e3b8e1 100644
--- a/compiler/optimizing/register_allocator.cc
+++ b/compiler/optimizing/register_allocator.cc
@@ -1528,10 +1528,10 @@ void RegisterAllocator::InsertParallelMoveAtExitOf(HBasicBlock* block,
DCHECK_EQ(block->NumberOfNormalSuccessors(), 1u);
HInstruction* last = block->GetLastInstruction();
// We insert moves at exit for phi predecessors and connecting blocks.
- // A block ending with an if cannot branch to a block with phis because
- // we do not allow critical edges. It can also not connect
+ // A block ending with an if or a packed switch cannot branch to a block
+ // with phis because we do not allow critical edges. It can also not connect
// a split interval between two blocks: the move has to happen in the successor.
- DCHECK(!last->IsIf());
+ DCHECK(!last->IsIf() && !last->IsPackedSwitch());
HInstruction* previous = last->GetPrevious();
HParallelMove* move;
// This is a parallel move for connecting blocks. We need to differentiate
generated by cgit v1.2.3-59-g8ed1b (git 2.39.0) at 2025-10-20 23:00:21 +0000