Merge "RFC: Generate select instruction for conditional returns."
diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc
index 508027e..1510eaf 100644
--- a/compiler/optimizing/nodes.cc
+++ b/compiler/optimizing/nodes.cc
@@ -1751,6 +1751,10 @@
return HasOnlyOneInstruction(*this) && GetLastInstruction()->IsGoto();
}
+bool HBasicBlock::IsSingleReturn() const {
+ return HasOnlyOneInstruction(*this) && GetLastInstruction()->IsReturn();
+}
+
bool HBasicBlock::IsSingleTryBoundary() const {
return HasOnlyOneInstruction(*this) && GetLastInstruction()->IsTryBoundary();
}
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index 68d6c2e..f60d532 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -959,6 +959,7 @@
}
bool IsSingleGoto() const;
+ bool IsSingleReturn() const;
bool IsSingleTryBoundary() const;
// Returns true if this block emits nothing but a jump.
diff --git a/compiler/optimizing/optimizing_compiler.cc b/compiler/optimizing/optimizing_compiler.cc
index 426a169..e98c97c 100644
--- a/compiler/optimizing/optimizing_compiler.cc
+++ b/compiler/optimizing/optimizing_compiler.cc
@@ -489,7 +489,7 @@
} else if (opt_name == HSharpening::kSharpeningPassName) {
return new (arena) HSharpening(graph, codegen, dex_compilation_unit, driver, handles);
} else if (opt_name == HSelectGenerator::kSelectGeneratorPassName) {
- return new (arena) HSelectGenerator(graph, stats);
+ return new (arena) HSelectGenerator(graph, handles, stats);
} else if (opt_name == HInductionVarAnalysis::kInductionPassName) {
return new (arena) HInductionVarAnalysis(graph);
} else if (opt_name == InstructionSimplifier::kInstructionSimplifierPassName) {
@@ -758,7 +758,7 @@
HConstantFolding* fold1 = new (arena) HConstantFolding(graph, "constant_folding");
InstructionSimplifier* simplify1 = new (arena) InstructionSimplifier(
graph, codegen, driver, stats);
- HSelectGenerator* select_generator = new (arena) HSelectGenerator(graph, stats);
+ HSelectGenerator* select_generator = new (arena) HSelectGenerator(graph, handles, stats);
HConstantFolding* fold2 = new (arena) HConstantFolding(
graph, "constant_folding$after_inlining");
HConstantFolding* fold3 = new (arena) HConstantFolding(graph, "constant_folding$after_bce");
diff --git a/compiler/optimizing/reference_type_propagation.cc b/compiler/optimizing/reference_type_propagation.cc
index 561c9ea..93613a5 100644
--- a/compiler/optimizing/reference_type_propagation.cc
+++ b/compiler/optimizing/reference_type_propagation.cc
@@ -754,8 +754,23 @@
}
}
+void ReferenceTypePropagation::FixUpInstructionType(HInstruction* instruction,
+ VariableSizedHandleScope* handle_scope) {
+ if (instruction->IsSelect()) {
+ ScopedObjectAccess soa(Thread::Current());
+ HandleCache handle_cache(handle_scope);
+ HSelect* select = instruction->AsSelect();
+ ReferenceTypeInfo false_rti = select->GetFalseValue()->GetReferenceTypeInfo();
+ ReferenceTypeInfo true_rti = select->GetTrueValue()->GetReferenceTypeInfo();
+ select->SetReferenceTypeInfo(MergeTypes(false_rti, true_rti, &handle_cache));
+ } else {
+ LOG(FATAL) << "Invalid instruction in FixUpInstructionType";
+ }
+}
+
ReferenceTypeInfo ReferenceTypePropagation::MergeTypes(const ReferenceTypeInfo& a,
- const ReferenceTypeInfo& b) {
+ const ReferenceTypeInfo& b,
+ HandleCache* handle_cache) {
if (!b.IsValid()) {
return a;
}
@@ -780,7 +795,7 @@
is_exact = false;
} else if (!a_is_interface && !b_is_interface) {
result_type_handle =
- handle_cache_.NewHandle(a_type_handle->GetCommonSuperClass(b_type_handle));
+ handle_cache->NewHandle(a_type_handle->GetCommonSuperClass(b_type_handle));
is_exact = false;
} else {
// This can happen if:
@@ -790,7 +805,7 @@
// void foo(Interface i, boolean cond) {
// Object o = cond ? i : new Object();
// }
- result_type_handle = handle_cache_.GetObjectClassHandle();
+ result_type_handle = handle_cache->GetObjectClassHandle();
is_exact = false;
}
@@ -916,7 +931,7 @@
if (inputs[i]->IsNullConstant()) {
continue;
}
- new_rti = MergeTypes(new_rti, inputs[i]->GetReferenceTypeInfo());
+ new_rti = MergeTypes(new_rti, inputs[i]->GetReferenceTypeInfo(), &handle_cache_);
if (new_rti.IsValid() && new_rti.IsObjectClass()) {
if (!new_rti.IsExact()) {
break;
diff --git a/compiler/optimizing/reference_type_propagation.h b/compiler/optimizing/reference_type_propagation.h
index b19f473..c221282 100644
--- a/compiler/optimizing/reference_type_propagation.h
+++ b/compiler/optimizing/reference_type_propagation.h
@@ -54,6 +54,12 @@
static constexpr const char* kReferenceTypePropagationPassName = "reference_type_propagation";
+ // Fix the reference type for an instruction whose inputs have changed.
+ // For a select instruction, the reference types of the inputs are merged
+ // and the resulting reference type is set on the select instruction.
+ static void FixUpInstructionType(HInstruction* instruction,
+ VariableSizedHandleScope* handle_scope);
+
private:
class HandleCache {
public:
@@ -101,7 +107,9 @@
static void UpdateArrayGet(HArrayGet* instr, HandleCache* handle_cache)
REQUIRES_SHARED(Locks::mutator_lock_);
- ReferenceTypeInfo MergeTypes(const ReferenceTypeInfo& a, const ReferenceTypeInfo& b)
+ static ReferenceTypeInfo MergeTypes(const ReferenceTypeInfo& a,
+ const ReferenceTypeInfo& b,
+ HandleCache* handle_cache)
REQUIRES_SHARED(Locks::mutator_lock_);
void ValidateTypes();
diff --git a/compiler/optimizing/reference_type_propagation_test.cc b/compiler/optimizing/reference_type_propagation_test.cc
index d537459..cb2af91 100644
--- a/compiler/optimizing/reference_type_propagation_test.cc
+++ b/compiler/optimizing/reference_type_propagation_test.cc
@@ -49,7 +49,7 @@
// Relay method to merge type in reference type propagation.
ReferenceTypeInfo MergeTypes(const ReferenceTypeInfo& a,
const ReferenceTypeInfo& b) REQUIRES_SHARED(Locks::mutator_lock_) {
- return propagation_->MergeTypes(a, b);
+ return propagation_->MergeTypes(a, b, &propagation_->handle_cache_);
}
// Helper method to construct an invalid type.
@@ -163,4 +163,3 @@
}
} // namespace art
-
diff --git a/compiler/optimizing/select_generator.cc b/compiler/optimizing/select_generator.cc
index cb7ade9..e220d32 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);
}
diff --git a/compiler/optimizing/select_generator.h b/compiler/optimizing/select_generator.h
index c6dca58..c060146 100644
--- a/compiler/optimizing/select_generator.h
+++ b/compiler/optimizing/select_generator.h
@@ -18,7 +18,7 @@
* This optimization recognizes the common diamond selection pattern and
* replaces it with an instance of the HSelect instruction.
*
- * Recognized pattern:
+ * Recognized patterns:
*
* If [ Condition ]
* / \
@@ -26,14 +26,30 @@
* \ /
* Phi [FalseValue, TrueValue]
*
+ * and
+ *
+ * If [ Condition ]
+ * / \
+ * false branch true branch
+ * return FalseValue return TrueValue
+ *
* The pattern will be simplified if `true_branch` and `false_branch` each
* contain at most one instruction without any side effects.
*
- * Blocks are merged into one and Select replaces the If and the Phi:
+ * Blocks are merged into one and Select replaces the If and the Phi.
+ *
+ * For the first pattern it simplifies to:
+ *
* true branch
* false branch
* Select [FalseValue, TrueValue, Condition]
*
+ * For the second pattern it simplifies to:
+ *
+ * true branch
+ * false branch
+ * return Select [FalseValue, TrueValue, Condition]
+ *
* Note: In order to recognize no side-effect blocks, this optimization must be
* run after the instruction simplifier has removed redundant suspend checks.
*/
@@ -42,19 +58,22 @@
#define ART_COMPILER_OPTIMIZING_SELECT_GENERATOR_H_
#include "optimization.h"
+#include "reference_type_propagation.h"
namespace art {
class HSelectGenerator : public HOptimization {
public:
- HSelectGenerator(HGraph* graph, OptimizingCompilerStats* stats)
- : HOptimization(graph, kSelectGeneratorPassName, stats) {}
+ HSelectGenerator(HGraph* graph,
+ VariableSizedHandleScope* handles,
+ OptimizingCompilerStats* stats);
void Run() OVERRIDE;
static constexpr const char* kSelectGeneratorPassName = "select_generator";
private:
+ VariableSizedHandleScope* handle_scope_;
DISALLOW_COPY_AND_ASSIGN(HSelectGenerator);
};
diff --git a/test/592-checker-regression-bool-input/smali/TestCase.smali b/test/592-checker-regression-bool-input/smali/TestCase.smali
index 56c499d..ad4e902 100644
--- a/test/592-checker-regression-bool-input/smali/TestCase.smali
+++ b/test/592-checker-regression-bool-input/smali/TestCase.smali
@@ -16,8 +16,15 @@
.super Ljava/lang/Object;
+## CHECK-START: boolean TestCase.testCase() select_generator (after)
+## CHECK-DAG: <<Select:i\d+>> Select
+## CHECK-DAG: Return [<<Select>>]
+
## CHECK-START: boolean TestCase.testCase() load_store_elimination (after)
-## CHECK-DAG: If [{{b\d+}}]
+## CHECK-DAG: <<Or:i\d+>> Or
+## CHECK-DAG: <<TypeConversion:b\d+>> TypeConversion
+## CHECK-DAG: StaticFieldSet
+## CHECK-DAG: Return [<<TypeConversion>>]
.method public static testCase()Z
.registers 6
@@ -31,7 +38,8 @@
# LSE will replace this sget with the type conversion above...
sget-boolean v2, LMain;->field2:Z
- # ... and generate an If with a byte-typed condition.
+ # ... and select generation will replace this part with a select
+ # that simplifies into simply returning the stored boolean.
if-eqz v2, :else
const v0, 0x1
return v0
diff --git a/test/663-checker-select-generator/expected.txt b/test/663-checker-select-generator/expected.txt
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/test/663-checker-select-generator/expected.txt
diff --git a/test/663-checker-select-generator/info.txt b/test/663-checker-select-generator/info.txt
new file mode 100644
index 0000000..792779f
--- /dev/null
+++ b/test/663-checker-select-generator/info.txt
@@ -0,0 +1,14 @@
+Test for select generation for conditional returns.
+
+Tests the rewriting from:
+
+ If [ Condition ]
+ / \
+ false branch true branch
+ return FalseValue return TrueValue
+
+to:
+
+ true branch
+ false branch
+ return Select [FalseValue, TrueValue, Condition]
diff --git a/test/663-checker-select-generator/smali/TestCase.smali b/test/663-checker-select-generator/smali/TestCase.smali
new file mode 100644
index 0000000..844a9cf
--- /dev/null
+++ b/test/663-checker-select-generator/smali/TestCase.smali
@@ -0,0 +1,72 @@
+# Copyright (C) 2017 The Android Open Source Project
+#
+# Licensed under the Apache License, Version 2.0 (the "License");
+# you may not use this file except in compliance with the License.
+# You may obtain a copy of the License at
+#
+# http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing, software
+# distributed under the License is distributed on an "AS IS" BASIS,
+# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+# See the License for the specific language governing permissions and
+# limitations under the License.
+
+.class public LTestCase;
+
+.super Ljava/lang/Object;
+
+## CHECK-START: boolean TestCase.testCase(boolean) select_generator (before)
+## CHECK-DAG: <<Param:z\d+>> ParameterValue
+## CHECK-DAG: <<Int0:i\d+>> IntConstant 0
+## CHECK-DAG: <<Int1:i\d+>> IntConstant 1
+## CHECK-DAG: If [<<Param>>]
+## CHECK-DAG: Return [<<Int0>>]
+## CHECK-DAG: Return [<<Int1>>]
+
+## CHECK-START: boolean TestCase.testCase(boolean) select_generator (after)
+## CHECK-DAG: <<Param:z\d+>> ParameterValue
+## CHECK-DAG: <<Int0:i\d+>> IntConstant 0
+## CHECK-DAG: <<Int1:i\d+>> IntConstant 1
+## CHECK-DAG: <<Select:i\d+>> Select [<<Int0>>,<<Int1>>,<<Param>>]
+## CHECK-DAG: Return [<<Select>>]
+
+.method public static testCase(Z)Z
+ .registers 1
+
+ # The select generation will replace this with a select
+ # instruction and a return.
+ if-eqz v0, :else
+ const v0, 0x1
+ return v0
+
+ :else
+ const v0, 0x0
+ return v0
+.end method
+
+
+## CHECK-START: java.lang.Object TestCase.referenceTypeTestCase(Main$Sub1, Main$Sub2, boolean) select_generator (before)
+## CHECK-DAG: <<Param0:l\d+>> ParameterValue
+## CHECK-DAG: <<Param1:l\d+>> ParameterValue
+## CHECK-DAG: <<Param2:z\d+>> ParameterValue
+## CHECK-DAG: If [<<Param2>>]
+## CHECK-DAG: Return [<<Param1>>]
+## CHECK-DAG: Return [<<Param0>>]
+
+## CHECK-START: java.lang.Object TestCase.referenceTypeTestCase(Main$Sub1, Main$Sub2, boolean) select_generator (after)
+## CHECK-DAG: <<Param0:l\d+>> ParameterValue
+## CHECK-DAG: <<Param1:l\d+>> ParameterValue
+## CHECK-DAG: <<Param2:z\d+>> ParameterValue
+## CHECK-DAG: <<Select:l\d+>> Select [<<Param1>>,<<Param0>>,<<Param2>>]
+## CHECK-DAG: Return [<<Select>>]
+
+.method public static referenceTypeTestCase(LMain$Sub1;LMain$Sub2;Z)Ljava/lang/Object;
+ .registers 3
+
+ if-eqz v2, :else
+ return-object v0
+
+ :else
+ return-object v1
+.end method
diff --git a/test/663-checker-select-generator/src/Main.java b/test/663-checker-select-generator/src/Main.java
new file mode 100644
index 0000000..c5c7a43
--- /dev/null
+++ b/test/663-checker-select-generator/src/Main.java
@@ -0,0 +1,62 @@
+/*
+ * Copyright (C) 2017 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+import java.lang.reflect.Method;
+
+public class Main {
+ public static class Super {}
+ public static class Sub1 {}
+ public static class Sub2 {}
+
+ public static void assertTrue(boolean result) {
+ if (!result) {
+ throw new Error("Expected true");
+ }
+ }
+
+ public static void assertFalse(boolean result) {
+ if (result) {
+ throw new Error("Expected false");
+ }
+ }
+
+ public static void assertInstanceOfSub1(Object result) {
+ if (!(result instanceof Sub1)) {
+ throw new Error("Expected instance of Sub1");
+ }
+ }
+
+ public static void assertInstanceOfSub2(Object result) {
+ if (!(result instanceof Sub2)) {
+ throw new Error("Expected instance of Sub2");
+ }
+ }
+
+ public static void main(String[] args) throws Throwable {
+ Class<?> c = Class.forName("TestCase");
+ Method m = c.getMethod("testCase", boolean.class);
+ Method m2 = c.getMethod("referenceTypeTestCase", Sub1.class, Sub2.class, boolean.class);
+
+ try {
+ assertTrue((Boolean) m.invoke(null, true));
+ assertFalse((Boolean) m.invoke(null, false));
+ assertInstanceOfSub1(m2.invoke(null, new Sub1(), new Sub2(), true));
+ assertInstanceOfSub2(m2.invoke(null, new Sub1(), new Sub2(), false));
+ } catch (Exception e) {
+ throw new Error(e);
+ }
+ }
+}
diff --git a/test/knownfailures.json b/test/knownfailures.json
index a8191bb..4bf1ee2 100644
--- a/test/knownfailures.json
+++ b/test/knownfailures.json
@@ -505,6 +505,7 @@
"641-checker-arraycopy",
"643-checker-bogus-ic",
"645-checker-abs-simd",
+ "663-checker-select-generator",
"706-checker-scheduler"],
"description": ["Checker tests are not compatible with jvmti."],
"variant": "jvmti-stress | redefine-stress | trace-stress | field-stress | step-stress"