Detect phi cycles.
Having reference and non-reference phi equivalent, only happened
for the 0/null constant. To avoid such occurences, we must
detect phi cycles.
bug:25493693
Change-Id: Ie1a8460c3abacca96c299da107fa4407e17dd792
diff --git a/compiler/optimizing/graph_checker.cc b/compiler/optimizing/graph_checker.cc
index f3c1dbe..3b93b2b 100644
--- a/compiler/optimizing/graph_checker.cc
+++ b/compiler/optimizing/graph_checker.cc
@@ -763,6 +763,14 @@
phi->GetId(),
phi->GetRegNumber(),
type_str.str().c_str()));
+ } else if (phi->GetType() == Primitive::kPrimNot) {
+ std::stringstream type_str;
+ type_str << other_phi->GetType();
+ AddError(StringPrintf(
+ "Equivalent non-reference phi (%d) found for VReg %d with type: %s.",
+ phi->GetId(),
+ phi->GetRegNumber(),
+ type_str.str().c_str()));
} else {
ArenaBitVector visited(GetGraph()->GetArena(), 0, /* expandable */ true);
if (!IsConstantEquivalent(phi, other_phi, &visited)) {
diff --git a/compiler/optimizing/reference_type_propagation.cc b/compiler/optimizing/reference_type_propagation.cc
index 94a297c..8113e65 100644
--- a/compiler/optimizing/reference_type_propagation.cc
+++ b/compiler/optimizing/reference_type_propagation.cc
@@ -124,91 +124,6 @@
}
}
-static void CheckHasNoTypedInputs(HInstruction* root_instr) {
- ArenaAllocatorAdapter<void> adapter =
- root_instr->GetBlock()->GetGraph()->GetArena()->Adapter(kArenaAllocReferenceTypePropagation);
-
- ArenaVector<HPhi*> visited_phis(adapter);
- ArenaVector<HInstruction*> worklist(adapter);
- worklist.push_back(root_instr);
-
- while (!worklist.empty()) {
- HInstruction* instr = worklist.back();
- worklist.pop_back();
-
- if (instr->IsPhi() || instr->IsBoundType() || instr->IsNullCheck()) {
- // Expect that both `root_instr` and its inputs have invalid RTI.
- ScopedObjectAccess soa(Thread::Current());
- DCHECK(!instr->GetReferenceTypeInfo().IsValid()) << "Instruction should not have valid RTI.";
-
- // Insert all unvisited inputs to the worklist.
- for (HInputIterator it(instr); !it.Done(); it.Advance()) {
- HInstruction* input = it.Current();
- if (input->IsPhi()) {
- if (ContainsElement(visited_phis, input->AsPhi())) {
- continue;
- } else {
- visited_phis.push_back(input->AsPhi());
- }
- }
- worklist.push_back(input);
- }
- } else if (instr->IsNullConstant()) {
- // The only input of `root_instr` allowed to have valid RTI because it is ignored.
- } else {
- LOG(FATAL) << "Unexpected input " << instr->DebugName() << instr->GetId() << " with RTI "
- << instr->GetReferenceTypeInfo();
- UNREACHABLE();
- }
- }
-}
-
-template<typename Functor>
-static void ForEachUntypedInstruction(HGraph* graph, Functor fn) {
- ScopedObjectAccess soa(Thread::Current());
- for (HReversePostOrderIterator block_it(*graph); !block_it.Done(); block_it.Advance()) {
- for (HInstructionIterator it(block_it.Current()->GetPhis()); !it.Done(); it.Advance()) {
- HPhi* phi = it.Current()->AsPhi();
- // Note that the graph may contain dead phis when run from the SsaBuilder.
- // Skip those as they might have a type conflict and will be removed anyway.
- if (phi->IsLive() &&
- phi->GetType() == Primitive::kPrimNot &&
- !phi->GetReferenceTypeInfo().IsValid()) {
- fn(phi);
- }
- }
- for (HInstructionIterator it(block_it.Current()->GetInstructions()); !it.Done(); it.Advance()) {
- HInstruction* instr = it.Current();
- if (instr->GetType() == Primitive::kPrimNot && !instr->GetReferenceTypeInfo().IsValid()) {
- fn(instr);
- }
- }
- }
-}
-
-void ReferenceTypePropagation::SetUntypedInstructionsToObject() {
- // In some cases, the fix-point iteration will leave kPrimNot instructions with
- // invalid RTI because bytecode does not provide enough typing information.
- // Set the RTI of such instructions to Object.
- // Example:
- // MyClass a = null, b = null;
- // while (a == null) {
- // if (cond) { a = b; } else { b = a; }
- // }
-
- if (kIsDebugBuild) {
- // Test that if we are going to set RTI from invalid to Object, that
- // instruction did not have any typed instructions in its def-use chain
- // and therefore its type could not be inferred.
- ForEachUntypedInstruction(graph_, [](HInstruction* instr) { CheckHasNoTypedInputs(instr); });
- }
-
- ReferenceTypeInfo obj_rti = ReferenceTypeInfo::Create(object_class_handle_, /* is_exact */ false);
- ForEachUntypedInstruction(graph_, [obj_rti](HInstruction* instr) {
- instr->SetReferenceTypeInfo(obj_rti);
- });
-}
-
void ReferenceTypePropagation::Run() {
// To properly propagate type info we need to visit in the dominator-based order.
// Reverse post order guarantees a node's dominators are visited first.
@@ -218,7 +133,6 @@
}
ProcessWorklist();
- SetUntypedInstructionsToObject();
ValidateTypes();
}
diff --git a/compiler/optimizing/reference_type_propagation.h b/compiler/optimizing/reference_type_propagation.h
index 21789e1..5c05592 100644
--- a/compiler/optimizing/reference_type_propagation.h
+++ b/compiler/optimizing/reference_type_propagation.h
@@ -57,7 +57,6 @@
SHARED_REQUIRES(Locks::mutator_lock_);
void ValidateTypes();
- void SetUntypedInstructionsToObject();
StackHandleScopeCollection* handles_;
diff --git a/compiler/optimizing/ssa_phi_elimination.cc b/compiler/optimizing/ssa_phi_elimination.cc
index 63aba88..2eef307 100644
--- a/compiler/optimizing/ssa_phi_elimination.cc
+++ b/compiler/optimizing/ssa_phi_elimination.cc
@@ -17,6 +17,7 @@
#include "ssa_phi_elimination.h"
#include "base/arena_containers.h"
+#include "base/bit_vector-inl.h"
namespace art {
@@ -129,6 +130,9 @@
}
}
+ ArenaSet<uint32_t> visited_phis_in_cycle(graph_->GetArena()->Adapter());
+ ArenaVector<HPhi*> cycle_worklist(graph_->GetArena()->Adapter());
+
while (!worklist_.empty()) {
HPhi* phi = worklist_.back();
worklist_.pop_back();
@@ -143,46 +147,92 @@
continue;
}
- // Find if the inputs of the phi are the same instruction.
- HInstruction* candidate = phi->InputAt(0);
- // A loop phi cannot have itself as the first phi. Note that this
- // check relies on our simplification pass ensuring the pre-header
- // block is first in the list of predecessors of the loop header.
- DCHECK(!phi->IsLoopHeaderPhi() || phi->GetBlock()->IsLoopPreHeaderFirstPredecessor());
- DCHECK_NE(phi, candidate);
+ HInstruction* candidate = nullptr;
+ visited_phis_in_cycle.clear();
+ cycle_worklist.clear();
- for (size_t i = 1; i < phi->InputCount(); ++i) {
- HInstruction* input = phi->InputAt(i);
- // For a loop phi, if the input is the phi, the phi is still candidate for
- // elimination.
- if (input != candidate && input != phi) {
+ cycle_worklist.push_back(phi);
+ visited_phis_in_cycle.insert(phi->GetId());
+ bool catch_phi_in_cycle = phi->IsCatchPhi();
+
+ // First do a simple loop over inputs and check if they are all the same.
+ for (size_t j = 0; j < phi->InputCount(); ++j) {
+ HInstruction* input = phi->InputAt(j);
+ if (input == phi) {
+ continue;
+ } else if (candidate == nullptr) {
+ candidate = input;
+ } else if (candidate != input) {
candidate = nullptr;
break;
}
}
- // If the inputs are not the same, continue.
+ // If we haven't found a candidate, check for a phi cycle. Note that we need to detect
+ // such cycles to avoid having reference and non-reference equivalents. We check this
+ // invariant in the graph checker.
+ if (candidate == nullptr) {
+ // We iterate over the array as long as it grows.
+ for (size_t i = 0; i < cycle_worklist.size(); ++i) {
+ HPhi* current = cycle_worklist[i];
+ DCHECK(!current->IsLoopHeaderPhi() ||
+ current->GetBlock()->IsLoopPreHeaderFirstPredecessor());
+
+ for (size_t j = 0; j < current->InputCount(); ++j) {
+ HInstruction* input = current->InputAt(j);
+ if (input == current) {
+ continue;
+ } else if (input->IsPhi()) {
+ if (!ContainsElement(visited_phis_in_cycle, input->GetId())) {
+ cycle_worklist.push_back(input->AsPhi());
+ visited_phis_in_cycle.insert(input->GetId());
+ catch_phi_in_cycle |= input->AsPhi()->IsCatchPhi();
+ } else {
+ // Already visited, nothing to do.
+ }
+ } else if (candidate == nullptr) {
+ candidate = input;
+ } else if (candidate != input) {
+ candidate = nullptr;
+ // Clear the cycle worklist to break out of the outer loop.
+ cycle_worklist.clear();
+ break;
+ }
+ }
+ }
+ }
+
if (candidate == nullptr) {
continue;
}
- // The candidate may not dominate a phi in a catch block.
- if (phi->IsCatchPhi() && !candidate->StrictlyDominates(phi)) {
- continue;
- }
-
- // Because we're updating the users of this phi, we may have new candidates
- // for elimination. Add phis that use this phi to the worklist.
- for (HUseIterator<HInstruction*> it(phi->GetUses()); !it.Done(); it.Advance()) {
- HUseListNode<HInstruction*>* current = it.Current();
- HInstruction* user = current->GetUser();
- if (user->IsPhi()) {
- worklist_.push_back(user->AsPhi());
+ for (HPhi* current : cycle_worklist) {
+ // The candidate may not dominate a phi in a catch block: there may be non-throwing
+ // instructions at the beginning of a try range, that may be the first input of
+ // catch phis.
+ // TODO(dbrazdil): Remove this situation by moving those non-throwing instructions
+ // before the try entry.
+ if (catch_phi_in_cycle) {
+ if (!candidate->StrictlyDominates(current)) {
+ continue;
+ }
+ } else {
+ DCHECK(candidate->StrictlyDominates(current));
}
- }
- phi->ReplaceWith(candidate);
- phi->GetBlock()->RemovePhi(phi);
+ // Because we're updating the users of this phi, we may have new candidates
+ // for elimination. Add phis that use this phi to the worklist.
+ for (HUseIterator<HInstruction*> it(current->GetUses()); !it.Done(); it.Advance()) {
+ HUseListNode<HInstruction*>* use = it.Current();
+ HInstruction* user = use->GetUser();
+ if (user->IsPhi() && !ContainsElement(visited_phis_in_cycle, user->GetId())) {
+ worklist_.push_back(user->AsPhi());
+ }
+ }
+ DCHECK(candidate->StrictlyDominates(current));
+ current->ReplaceWith(candidate);
+ current->GetBlock()->RemovePhi(current);
+ }
}
}
diff --git a/test/450-checker-types/src/Main.java b/test/450-checker-types/src/Main.java
index fd4dd5e..92cf807 100644
--- a/test/450-checker-types/src/Main.java
+++ b/test/450-checker-types/src/Main.java
@@ -722,22 +722,6 @@
}
}
- /// CHECK-START: void Main.testLoopPhisWithNullAndCrossUses(boolean) ssa_builder (after)
- /// CHECK-DAG: <<Null:l\d+>> NullConstant
- /// CHECK-DAG: <<PhiA:l\d+>> Phi [<<Null>>,<<PhiB:l\d+>>,<<PhiA>>] klass:java.lang.Object exact:false
- /// CHECK-DAG: <<PhiB>> Phi [<<Null>>,<<PhiB>>,<<PhiA>>] klass:java.lang.Object exact:false
- private void testLoopPhisWithNullAndCrossUses(boolean cond) {
- Main a = null;
- Main b = null;
- while (a == null) {
- if (cond) {
- a = b;
- } else {
- b = a;
- }
- }
- }
-
/// CHECK-START: java.lang.Object[] Main.testInstructionsWithUntypedParent() ssa_builder (after)
/// CHECK-DAG: <<Null:l\d+>> NullConstant
/// CHECK-DAG: <<LoopPhi:l\d+>> Phi [<<Null>>,<<Phi:l\d+>>] klass:java.lang.Object[] exact:true
diff --git a/test/557-checker-ref-equivalent/expected.txt b/test/557-checker-ref-equivalent/expected.txt
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/test/557-checker-ref-equivalent/expected.txt
diff --git a/test/557-checker-ref-equivalent/info.txt b/test/557-checker-ref-equivalent/info.txt
new file mode 100644
index 0000000..30e763b
--- /dev/null
+++ b/test/557-checker-ref-equivalent/info.txt
@@ -0,0 +1 @@
+Checker tests to ensure we do not get reference and integer phi equivalents.
diff --git a/test/557-checker-ref-equivalent/smali/TestCase.smali b/test/557-checker-ref-equivalent/smali/TestCase.smali
new file mode 100644
index 0000000..2472957
--- /dev/null
+++ b/test/557-checker-ref-equivalent/smali/TestCase.smali
@@ -0,0 +1,51 @@
+# Copyright (C) 2015 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: void TestCase.testIntRefEquivalent() ssa_builder (after)
+## CHECK-NOT: Phi
+.method public static testIntRefEquivalent()V
+ .registers 4
+
+ const v0, 0
+
+ :try_start
+ invoke-static {v0,v0}, LTestCase;->foo(ILjava/lang/Object;)V
+ if-eqz v0, :end_if
+ const v0, 0
+ :end_if
+ invoke-static {v0,v0}, LTestCase;->foo(ILjava/lang/Object;)V
+ goto :no_catch
+ :try_end
+
+ .catch Ljava/lang/Exception; {:try_start .. :try_end} :exception
+ :exception
+ # We used to have a reference and an integer phi equivalents here, which
+ # broke the invariant of not sharing the same spill slot between those two
+ # types.
+ invoke-static {v0,v0}, LTestCase;->foo(ILjava/lang/Object;)V
+
+ :no_catch
+ goto :try_start
+ return-void
+
+.end method
+
+.method public static foo(ILjava/lang/Object;)V
+ .registers 4
+ return-void
+.end method
diff --git a/test/557-checker-ref-equivalent/src/Main.java b/test/557-checker-ref-equivalent/src/Main.java
new file mode 100644
index 0000000..a970af5
--- /dev/null
+++ b/test/557-checker-ref-equivalent/src/Main.java
@@ -0,0 +1,47 @@
+/*
+ * Copyright (C) 2015 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.
+ */
+
+public class Main {
+
+ /// CHECK-START: void Main.testRedundantPhiCycle(boolean) ssa_builder (after)
+ /// CHECK-NOT: Phi
+ private void testRedundantPhiCycle(boolean cond) {
+ Object o = null;
+ while (true) {
+ if (cond) {
+ o = null;
+ }
+ System.out.println(o);
+ }
+ }
+
+ /// CHECK-START: void Main.testLoopPhisWithNullAndCrossUses(boolean) ssa_builder (after)
+ /// CHECK-NOT: Phi
+ private void testLoopPhisWithNullAndCrossUses(boolean cond) {
+ Main a = null;
+ Main b = null;
+ while (a == null) {
+ if (cond) {
+ a = b;
+ } else {
+ b = a;
+ }
+ }
+ }
+
+ public static void main(String[] args) {
+ }
+}