RFC: Generate select instruction for conditional returns.
The select generator currently only inserts select instructions
if there is a diamond shape with a phi.
This change extends the select generator to also deal with the
pattern:
if (condition) {
movable instruction 0
return value0
} else {
movable instruction 1
return value1
}
which it turns into:
moveable instruction 0
moveable instruction 1
return select (value0, value1, condition)
Test: 592-checker-regression-bool-input
Change-Id: Iac50fb181dc2c9b7619f28977298662bc09fc0e1
diff --git a/compiler/optimizing/select_generator.cc b/compiler/optimizing/select_generator.cc
index 46d0d0e..d911d73 100644
--- a/compiler/optimizing/select_generator.cc
+++ b/compiler/optimizing/select_generator.cc
@@ -20,9 +20,16 @@
static constexpr size_t kMaxInstructionsInBranch = 1u;
-// Returns true if `block` has only one predecessor, ends with a Goto and
-// contains at most `kMaxInstructionsInBranch` other movable instruction with
-// no side-effects.
+HSelectGenerator::HSelectGenerator(HGraph* graph,
+ VariableSizedHandleScope* handles,
+ OptimizingCompilerStats* stats)
+ : HOptimization(graph, kSelectGeneratorPassName, stats),
+ handle_scope_(handles) {
+}
+
+// Returns true if `block` has only one predecessor, ends with a Goto
+// or a Return and contains at most `kMaxInstructionsInBranch` other
+// movable instruction with no side-effects.
static bool IsSimpleBlock(HBasicBlock* block) {
if (block->GetPredecessors().size() != 1u) {
return false;
@@ -33,7 +40,10 @@
for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) {
HInstruction* instruction = it.Current();
if (instruction->IsControlFlow()) {
- return instruction->IsGoto() && num_instructions <= kMaxInstructionsInBranch;
+ if (num_instructions > kMaxInstructionsInBranch) {
+ return false;
+ }
+ return instruction->IsGoto() || instruction->IsReturn();
} else if (instruction->CanBeMoved() && !instruction->HasSideEffects()) {
num_instructions++;
} else {
@@ -45,8 +55,8 @@
UNREACHABLE();
}
-// Returns true if 'block1' and 'block2' are empty, merge into the same single
-// successor and the successor can only be reached from them.
+// Returns true if 'block1' and 'block2' are empty and merge into the
+// same single successor.
static bool BlocksMergeTogether(HBasicBlock* block1, HBasicBlock* block2) {
return block1->GetSingleSuccessor() == block2->GetSingleSuccessor();
}
@@ -94,48 +104,68 @@
// If the branches are not empty, move instructions in front of the If.
// TODO(dbrazdil): This puts an instruction between If and its condition.
// Implement moving of conditions to first users if possible.
- if (!true_block->IsSingleGoto()) {
+ if (!true_block->IsSingleGoto() && !true_block->IsSingleReturn()) {
true_block->GetFirstInstruction()->MoveBefore(if_instruction);
}
- if (!false_block->IsSingleGoto()) {
+ if (!false_block->IsSingleGoto() && !false_block->IsSingleReturn()) {
false_block->GetFirstInstruction()->MoveBefore(if_instruction);
}
- DCHECK(true_block->IsSingleGoto());
- DCHECK(false_block->IsSingleGoto());
+ DCHECK(true_block->IsSingleGoto() || true_block->IsSingleReturn());
+ DCHECK(false_block->IsSingleGoto() || false_block->IsSingleReturn());
// Find the resulting true/false values.
size_t predecessor_index_true = merge_block->GetPredecessorIndexOf(true_block);
size_t predecessor_index_false = merge_block->GetPredecessorIndexOf(false_block);
DCHECK_NE(predecessor_index_true, predecessor_index_false);
+ bool both_successors_return = true_block->IsSingleReturn() && false_block->IsSingleReturn();
HPhi* phi = GetSingleChangedPhi(merge_block, predecessor_index_true, predecessor_index_false);
- if (phi == nullptr) {
+
+ HInstruction* true_value = nullptr;
+ HInstruction* false_value = nullptr;
+ if (both_successors_return) {
+ true_value = true_block->GetFirstInstruction()->InputAt(0);
+ false_value = false_block->GetFirstInstruction()->InputAt(0);
+ } else if (phi != nullptr) {
+ true_value = phi->InputAt(predecessor_index_true);
+ false_value = phi->InputAt(predecessor_index_false);
+ } else {
continue;
}
- HInstruction* true_value = phi->InputAt(predecessor_index_true);
- HInstruction* false_value = phi->InputAt(predecessor_index_false);
+ DCHECK(both_successors_return || phi != nullptr);
// Create the Select instruction and insert it in front of the If.
HSelect* select = new (graph_->GetArena()) HSelect(if_instruction->InputAt(0),
true_value,
false_value,
if_instruction->GetDexPc());
- if (phi->GetType() == Primitive::kPrimNot) {
+ if (both_successors_return) {
+ if (true_value->GetType() == Primitive::kPrimNot) {
+ DCHECK(false_value->GetType() == Primitive::kPrimNot);
+ ReferenceTypePropagation::FixUpInstructionType(select, handle_scope_);
+ }
+ } else if (phi->GetType() == Primitive::kPrimNot) {
select->SetReferenceTypeInfo(phi->GetReferenceTypeInfo());
}
block->InsertInstructionBefore(select, if_instruction);
- // Remove the true branch which removes the corresponding Phi input.
- // If left only with the false branch, the Phi is automatically removed.
- phi->ReplaceInput(select, predecessor_index_false);
+ // Remove the true branch which removes the corresponding Phi
+ // input if needed. If left only with the false branch, the Phi is
+ // automatically removed.
+ if (both_successors_return) {
+ false_block->GetFirstInstruction()->ReplaceInput(select, 0);
+ } else {
+ phi->ReplaceInput(select, predecessor_index_false);
+ }
+
bool only_two_predecessors = (merge_block->GetPredecessors().size() == 2u);
true_block->DisconnectAndDelete();
- DCHECK_EQ(only_two_predecessors, phi->GetBlock() == nullptr);
// Merge remaining blocks which are now connected with Goto.
DCHECK_EQ(block->GetSingleSuccessor(), false_block);
block->MergeWith(false_block);
- if (only_two_predecessors) {
+ if (!both_successors_return && only_two_predecessors) {
+ DCHECK_EQ(only_two_predecessors, phi->GetBlock() == nullptr);
DCHECK_EQ(block->GetSingleSuccessor(), merge_block);
block->MergeWith(merge_block);
}