ART: Fix wide stores in Optimizing
SsaBuilder::VisitStoreLocal did not take into account the following:
(a) when storing a wide value, the high vreg must be invalidated,
(b) when storing into the high vreg of a wide value, the low vreg
must be invalidated.
Both situations cause overestimation of liveness but only (b) has
implications on correctness. CodeGenerator::EmitEnvironment will skip
the high vreg, causing deoptimizing and try/catch to load a wrong
value for that vreg.
In order to fix this bug, several changes had to be made to the
SsaBuilder:
(1) phis need to be initialized with a type which matches its
inputs' size,
(2) eagerly created loop header phis may end up being undefined
because of their corresponding vregs being invalidated inside
the loop; these are marked dead during input setting,
(3) the entire SSA-building algorithm should never revive an
undefined loop header phi.
Bug: 25677992
Bug: https://code.google.com/p/android/issues/detail?id=194022
Change-Id: Id8a852e38c3f5ff1c2e608b1aafd6d5ac8311e32
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index a5ea154..9f979ed 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -4313,9 +4313,13 @@
: HInstruction(SideEffects::None(), dex_pc),
inputs_(number_of_inputs, arena->Adapter(kArenaAllocPhiInputs)),
reg_number_(reg_number),
- type_(type),
- is_live_(false),
+ type_(ToPhiType(type)),
+ // Phis are constructed live and marked dead if conflicting or unused.
+ // Individual steps of SsaBuilder should assume that if a phi has been
+ // marked dead, it can be ignored and will be removed by SsaPhiElimination.
+ is_live_(true),
can_be_null_(true) {
+ DCHECK_NE(type_, Primitive::kPrimVoid);
}
// Returns a type equivalent to the given `type`, but that a `HPhi` can hold.
diff --git a/compiler/optimizing/primitive_type_propagation.cc b/compiler/optimizing/primitive_type_propagation.cc
index c98f43e..bde54ee 100644
--- a/compiler/optimizing/primitive_type_propagation.cc
+++ b/compiler/optimizing/primitive_type_propagation.cc
@@ -63,7 +63,6 @@
: SsaBuilder::GetFloatOrDoubleEquivalent(phi, input, new_type);
phi->ReplaceInput(equivalent, i);
if (equivalent->IsPhi()) {
- equivalent->AsPhi()->SetLive();
AddToWorklist(equivalent->AsPhi());
} else if (equivalent == input) {
// The input has changed its type. It can be an input of other phis,
diff --git a/compiler/optimizing/ssa_builder.cc b/compiler/optimizing/ssa_builder.cc
index 5190eb3b..9e6cfbe 100644
--- a/compiler/optimizing/ssa_builder.cc
+++ b/compiler/optimizing/ssa_builder.cc
@@ -22,6 +22,13 @@
namespace art {
+// Returns whether this is a loop header phi which was eagerly created but later
+// found inconsistent due to the vreg being undefined in one of its predecessors.
+// Such phi is marked dead and should be ignored until its removal in SsaPhiElimination.
+static bool IsUndefinedLoopHeaderPhi(HPhi* phi) {
+ return phi->IsLoopHeaderPhi() && phi->InputCount() != phi->GetBlock()->GetPredecessors().size();
+}
+
/**
* A debuggable application may require to reviving phis, to ensure their
* associated DEX register is available to a debugger. This class implements
@@ -165,17 +172,15 @@
void DeadPhiHandling::VisitBasicBlock(HBasicBlock* block) {
for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) {
HPhi* phi = it.Current()->AsPhi();
+ if (IsUndefinedLoopHeaderPhi(phi)) {
+ DCHECK(phi->IsDead());
+ continue;
+ }
if (phi->IsDead() && phi->HasEnvironmentUses()) {
phi->SetLive();
if (block->IsLoopHeader()) {
- // Give a type to the loop phi to guarantee convergence of the algorithm.
- // Note that the dead phi may already have a type if it is an equivalent
- // generated for a typed LoadLocal. In that case we do not change the
- // type because it could lead to an unsupported PrimNot/Float/Double ->
- // PrimInt/Long transition and create same type equivalents.
- if (phi->GetType() == Primitive::kPrimVoid) {
- phi->SetType(phi->InputAt(0)->GetType());
- }
+ // Loop phis must have a type to guarantee convergence of the algorithm.
+ DCHECK_NE(phi->GetType(), Primitive::kPrimVoid);
AddToWorklist(phi);
} else {
// Because we are doing a reverse post order visit, all inputs of
@@ -220,6 +225,27 @@
ProcessWorklist();
}
+void SsaBuilder::SetLoopHeaderPhiInputs() {
+ for (size_t i = loop_headers_.size(); i > 0; --i) {
+ HBasicBlock* block = loop_headers_[i - 1];
+ for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) {
+ HPhi* phi = it.Current()->AsPhi();
+ size_t vreg = phi->GetRegNumber();
+ for (HBasicBlock* predecessor : block->GetPredecessors()) {
+ HInstruction* value = ValueOfLocal(predecessor, vreg);
+ if (value == nullptr) {
+ // Vreg is undefined at this predecessor. Mark it dead and leave with
+ // fewer inputs than predecessors. SsaChecker will fail if not removed.
+ phi->SetDead();
+ break;
+ } else {
+ phi->AddInput(value);
+ }
+ }
+ }
+ }
+}
+
void SsaBuilder::FixNullConstantType() {
// The order doesn't matter here.
for (HReversePostOrderIterator itb(*GetGraph()); !itb.Done(); itb.Advance()) {
@@ -283,15 +309,7 @@
}
// 2) Set inputs of loop phis.
- for (HBasicBlock* block : loop_headers_) {
- for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) {
- HPhi* phi = it.Current()->AsPhi();
- for (HBasicBlock* predecessor : block->GetPredecessors()) {
- HInstruction* input = ValueOfLocal(predecessor, phi->GetRegNumber());
- phi->AddInput(input);
- }
- }
- }
+ SetLoopHeaderPhiInputs();
// 3) Mark dead phis. This will mark phis that are only used by environments:
// at the DEX level, the type of these phis does not need to be consistent, but
@@ -403,8 +421,13 @@
for (size_t i = 0; i < vregs; ++i) {
// No point in creating the catch phi if it is already undefined at
// the first throwing instruction.
- if ((*current_locals_)[i] != nullptr) {
- HPhi* phi = new (arena) HPhi(arena, i, 0, Primitive::kPrimVoid);
+ HInstruction* current_local_value = (*current_locals_)[i];
+ if (current_local_value != nullptr) {
+ HPhi* phi = new (arena) HPhi(
+ arena,
+ i,
+ 0,
+ current_local_value->GetType());
block->AddPhi(phi);
(*locals)[i] = phi;
}
@@ -451,7 +474,10 @@
HInstruction* incoming = ValueOfLocal(block->GetLoopInformation()->GetPreHeader(), local);
if (incoming != nullptr) {
HPhi* phi = new (GetGraph()->GetArena()) HPhi(
- GetGraph()->GetArena(), local, 0, Primitive::kPrimVoid);
+ GetGraph()->GetArena(),
+ local,
+ 0,
+ incoming->GetType());
block->AddPhi(phi);
(*current_locals_)[local] = phi;
}
@@ -484,8 +510,12 @@
}
if (is_different) {
+ HInstruction* first_input = ValueOfLocal(block->GetPredecessors()[0], local);
HPhi* phi = new (GetGraph()->GetArena()) HPhi(
- GetGraph()->GetArena(), local, block->GetPredecessors().size(), Primitive::kPrimVoid);
+ GetGraph()->GetArena(),
+ local,
+ block->GetPredecessors().size(),
+ first_input->GetType());
for (size_t i = 0; i < block->GetPredecessors().size(); i++) {
HInstruction* pred_value = ValueOfLocal(block->GetPredecessors()[i], local);
phi->SetRawInputAt(i, pred_value);
@@ -583,8 +613,16 @@
phi->GetBlock()->InsertPhiAfter(new_phi, phi);
return new_phi;
} else {
- DCHECK_EQ(next->GetType(), type);
- return next->AsPhi();
+ HPhi* next_phi = next->AsPhi();
+ DCHECK_EQ(next_phi->GetType(), type);
+ if (next_phi->IsDead()) {
+ // TODO(dbrazdil): Remove this SetLive (we should not need to revive phis)
+ // once we stop running MarkDeadPhis before PrimitiveTypePropagation. This
+ // cannot revive undefined loop header phis because they cannot have uses.
+ DCHECK(!IsUndefinedLoopHeaderPhi(next_phi));
+ next_phi->SetLive();
+ }
+ return next_phi;
}
}
@@ -638,7 +676,36 @@
}
void SsaBuilder::VisitStoreLocal(HStoreLocal* store) {
- (*current_locals_)[store->GetLocal()->GetRegNumber()] = store->InputAt(1);
+ uint32_t reg_number = store->GetLocal()->GetRegNumber();
+ HInstruction* stored_value = store->InputAt(1);
+ Primitive::Type stored_type = stored_value->GetType();
+ DCHECK_NE(stored_type, Primitive::kPrimVoid);
+
+ // Storing into vreg `reg_number` may implicitly invalidate the surrounding
+ // registers. Consider the following cases:
+ // (1) Storing a wide value must overwrite previous values in both `reg_number`
+ // and `reg_number+1`. We store `nullptr` in `reg_number+1`.
+ // (2) If vreg `reg_number-1` holds a wide value, writing into `reg_number`
+ // must invalidate it. We store `nullptr` in `reg_number-1`.
+ // Consequently, storing a wide value into the high vreg of another wide value
+ // will invalidate both `reg_number-1` and `reg_number+1`.
+
+ if (reg_number != 0) {
+ HInstruction* local_low = (*current_locals_)[reg_number - 1];
+ if (local_low != nullptr && Primitive::Is64BitType(local_low->GetType())) {
+ // The vreg we are storing into was previously the high vreg of a pair.
+ // We need to invalidate its low vreg.
+ DCHECK((*current_locals_)[reg_number] == nullptr);
+ (*current_locals_)[reg_number - 1] = nullptr;
+ }
+ }
+
+ (*current_locals_)[reg_number] = stored_value;
+ if (Primitive::Is64BitType(stored_type)) {
+ // We are storing a pair. Invalidate the instruction in the high vreg.
+ (*current_locals_)[reg_number + 1] = nullptr;
+ }
+
store->GetBlock()->RemoveInstruction(store);
}
diff --git a/compiler/optimizing/ssa_builder.h b/compiler/optimizing/ssa_builder.h
index 79f1a28..dcce5e4 100644
--- a/compiler/optimizing/ssa_builder.h
+++ b/compiler/optimizing/ssa_builder.h
@@ -81,6 +81,7 @@
static constexpr const char* kSsaBuilderPassName = "ssa_builder";
private:
+ void SetLoopHeaderPhiInputs();
void FixNullConstantType();
void EquivalentPhisCleanup();
diff --git a/compiler/optimizing/ssa_phi_elimination.cc b/compiler/optimizing/ssa_phi_elimination.cc
index 72f9ddd..a3219dc 100644
--- a/compiler/optimizing/ssa_phi_elimination.cc
+++ b/compiler/optimizing/ssa_phi_elimination.cc
@@ -16,6 +16,8 @@
#include "ssa_phi_elimination.h"
+#include "base/arena_containers.h"
+
namespace art {
void SsaDeadPhiElimination::Run() {
@@ -24,22 +26,36 @@
}
void SsaDeadPhiElimination::MarkDeadPhis() {
+ // Phis are constructed live and should not be revived if previously marked
+ // dead. This algorithm temporarily breaks that invariant but we DCHECK that
+ // only phis which were initially live are revived.
+ ArenaSet<HPhi*> initially_live(graph_->GetArena()->Adapter());
+
// Add to the worklist phis referenced by non-phi instructions.
for (HReversePostOrderIterator it(*graph_); !it.Done(); it.Advance()) {
HBasicBlock* block = it.Current();
for (HInstructionIterator inst_it(block->GetPhis()); !inst_it.Done(); inst_it.Advance()) {
HPhi* phi = inst_it.Current()->AsPhi();
- // Set dead ahead of running through uses. The phi may have no use.
- phi->SetDead();
+ if (phi->IsDead()) {
+ continue;
+ }
+
+ bool has_non_phi_use = false;
for (HUseIterator<HInstruction*> use_it(phi->GetUses()); !use_it.Done(); use_it.Advance()) {
- HUseListNode<HInstruction*>* current = use_it.Current();
- HInstruction* user = current->GetUser();
- if (!user->IsPhi()) {
- worklist_.push_back(phi);
- phi->SetLive();
+ if (!use_it.Current()->GetUser()->IsPhi()) {
+ has_non_phi_use = true;
break;
}
}
+
+ if (has_non_phi_use) {
+ worklist_.push_back(phi);
+ } else {
+ phi->SetDead();
+ if (kIsDebugBuild) {
+ initially_live.insert(phi);
+ }
+ }
}
}
@@ -48,10 +64,13 @@
HPhi* phi = worklist_.back();
worklist_.pop_back();
for (HInputIterator it(phi); !it.Done(); it.Advance()) {
- HInstruction* input = it.Current();
- if (input->IsPhi() && input->AsPhi()->IsDead()) {
- worklist_.push_back(input->AsPhi());
- input->AsPhi()->SetLive();
+ HPhi* input = it.Current()->AsPhi();
+ if (input != nullptr && input->IsDead()) {
+ // Input is a dead phi. Revive it and add to the worklist. We make sure
+ // that the phi was not dead initially (see definition of `initially_live`).
+ DCHECK(ContainsElement(initially_live, input));
+ input->SetLive();
+ worklist_.push_back(input);
}
}
}
@@ -118,7 +137,6 @@
}
if (phi->InputCount() == 0) {
- DCHECK(phi->IsCatchPhi());
DCHECK(phi->IsDead());
continue;
}
diff --git a/test/550-checker-regression-wide-store/expected.txt b/test/550-checker-regression-wide-store/expected.txt
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/test/550-checker-regression-wide-store/expected.txt
diff --git a/test/550-checker-regression-wide-store/info.txt b/test/550-checker-regression-wide-store/info.txt
new file mode 100644
index 0000000..6cf04bc
--- /dev/null
+++ b/test/550-checker-regression-wide-store/info.txt
@@ -0,0 +1,3 @@
+Test an SsaBuilder regression where storing into the high vreg of a pair
+would not invalidate the low vreg. The resulting environment would generate
+an incorrect stack map, causing deopt and try/catch to use a wrong location.
\ No newline at end of file
diff --git a/test/550-checker-regression-wide-store/smali/TestCase.smali b/test/550-checker-regression-wide-store/smali/TestCase.smali
new file mode 100644
index 0000000..7974d56
--- /dev/null
+++ b/test/550-checker-regression-wide-store/smali/TestCase.smali
@@ -0,0 +1,82 @@
+# 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;
+
+.method public static $noinline$throw()V
+ .registers 1
+ new-instance v0, Ljava/lang/Exception;
+ invoke-direct {v0}, Ljava/lang/Exception;-><init>()V
+ throw v0
+.end method
+
+# Test storing into the high vreg of a wide pair. This scenario has runtime
+# behaviour implications so we run it from Main.main.
+
+## CHECK-START: int TestCase.invalidateLow(long) ssa_builder (after)
+## CHECK-DAG: <<Cst0:i\d+>> IntConstant 0
+## CHECK-DAG: <<Arg:j\d+>> ParameterValue
+## CHECK-DAG: <<Cast:i\d+>> TypeConversion [<<Arg>>]
+## CHECK-DAG: InvokeStaticOrDirect method_name:java.lang.System.nanoTime env:[[_,<<Cst0>>,<<Arg>>,_]]
+## CHECK-DAG: InvokeStaticOrDirect method_name:TestCase.$noinline$throw env:[[_,<<Cast>>,<<Arg>>,_]]
+
+.method public static invalidateLow(J)I
+ .registers 4
+
+ const/4 v1, 0x0
+
+ :try_start
+ invoke-static {}, Ljava/lang/System;->nanoTime()J
+ move-wide v0, p0
+ long-to-int v1, v0
+ invoke-static {}, LTestCase;->$noinline$throw()V
+ :try_end
+ .catchall {:try_start .. :try_end} :catchall
+
+ :catchall
+ return v1
+
+.end method
+
+# Test that storing a wide invalidates the value in the high vreg. This
+# cannot be detected from runtime so we only test the environment with Checker.
+
+## CHECK-START: void TestCase.invalidateHigh1(long) ssa_builder (after)
+## CHECK-DAG: <<Arg:j\d+>> ParameterValue
+## CHECK-DAG: InvokeStaticOrDirect method_name:java.lang.System.nanoTime env:[[<<Arg>>,_,<<Arg>>,_]]
+
+.method public static invalidateHigh1(J)V
+ .registers 4
+
+ const/4 v1, 0x0
+ move-wide v0, p0
+ invoke-static {}, Ljava/lang/System;->nanoTime()J
+ return-void
+
+.end method
+
+## CHECK-START: void TestCase.invalidateHigh2(long) ssa_builder (after)
+## CHECK-DAG: <<Arg:j\d+>> ParameterValue
+## CHECK-DAG: InvokeStaticOrDirect method_name:java.lang.System.nanoTime env:[[<<Arg>>,_,_,<<Arg>>,_]]
+
+.method public static invalidateHigh2(J)V
+ .registers 5
+
+ move-wide v1, p0
+ move-wide v0, p0
+ invoke-static {}, Ljava/lang/System;->nanoTime()J
+ return-void
+
+.end method
diff --git a/test/550-checker-regression-wide-store/src/Main.java b/test/550-checker-regression-wide-store/src/Main.java
new file mode 100644
index 0000000..9b502df
--- /dev/null
+++ b/test/550-checker-regression-wide-store/src/Main.java
@@ -0,0 +1,40 @@
+/*
+ * 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.
+ */
+
+import java.lang.reflect.Method;
+
+public class Main {
+
+ // Workaround for b/18051191.
+ class InnerClass {}
+
+ private static int runTestCase(String name, long arg) throws Exception {
+ Class<?> c = Class.forName("TestCase");
+ Method m = c.getMethod(name, long.class);
+ int result = (Integer) m.invoke(null, arg);
+ return result;
+ }
+
+ private static void assertEquals(int expected, int actual) {
+ if (expected != actual) {
+ throw new Error("Wrong result: " + expected + " != " + actual);
+ }
+ }
+
+ public static void main(String[] args) throws Exception {
+ assertEquals(42, runTestCase("invalidateLow", 42L));
+ }
+}
