Fix another case of live_in at irreducible loop entry.
GVN was implicitly extending the liveness of an instruction across
an irreducible loop.
Fix this problem by clearing the value set at loop entries that contain
an irreducible loop.
bug:28252896
(cherry picked from commit 77ce6430af2709432b22344ed656edd8ec80581b)
Change-Id: Ie0121e83b2dfe47bcd184b90a69c0194d13fce54
diff --git a/compiler/optimizing/graph_visualizer.cc b/compiler/optimizing/graph_visualizer.cc
index 568b8a8..2038c88 100644
--- a/compiler/optimizing/graph_visualizer.cc
+++ b/compiler/optimizing/graph_visualizer.cc
@@ -549,26 +549,19 @@
}
}
- if (IsPass(LICM::kLoopInvariantCodeMotionPassName)
- || IsPass(HDeadCodeElimination::kFinalDeadCodeEliminationPassName)
- || IsPass(HDeadCodeElimination::kInitialDeadCodeEliminationPassName)
- || IsPass(BoundsCheckElimination::kBoundsCheckEliminationPassName)
- || IsPass(RegisterAllocator::kRegisterAllocatorPassName)
- || IsPass(HGraphBuilder::kBuilderPassName)) {
- HLoopInformation* info = instruction->GetBlock()->GetLoopInformation();
- if (info == nullptr) {
- StartAttributeStream("loop") << "none";
+ HLoopInformation* loop_info = instruction->GetBlock()->GetLoopInformation();
+ if (loop_info == nullptr) {
+ StartAttributeStream("loop") << "none";
+ } else {
+ StartAttributeStream("loop") << "B" << loop_info->GetHeader()->GetBlockId();
+ HLoopInformation* outer = loop_info->GetPreHeader()->GetLoopInformation();
+ if (outer != nullptr) {
+ StartAttributeStream("outer_loop") << "B" << outer->GetHeader()->GetBlockId();
} else {
- StartAttributeStream("loop") << "B" << info->GetHeader()->GetBlockId();
- HLoopInformation* outer = info->GetPreHeader()->GetLoopInformation();
- if (outer != nullptr) {
- StartAttributeStream("outer_loop") << "B" << outer->GetHeader()->GetBlockId();
- } else {
- StartAttributeStream("outer_loop") << "none";
- }
- StartAttributeStream("irreducible")
- << std::boolalpha << info->IsIrreducible() << std::noboolalpha;
+ StartAttributeStream("outer_loop") << "none";
}
+ StartAttributeStream("irreducible")
+ << std::boolalpha << loop_info->IsIrreducible() << std::noboolalpha;
}
if ((IsPass(HGraphBuilder::kBuilderPassName)
diff --git a/compiler/optimizing/gvn.cc b/compiler/optimizing/gvn.cc
index d0d52bf..1e86b75 100644
--- a/compiler/optimizing/gvn.cc
+++ b/compiler/optimizing/gvn.cc
@@ -454,11 +454,16 @@
if (!set->IsEmpty()) {
if (block->IsLoopHeader()) {
- if (block->GetLoopInformation()->IsIrreducible()) {
+ if (block->GetLoopInformation()->ContainsIrreducibleLoop()) {
// To satisfy our linear scan algorithm, no instruction should flow in an irreducible
- // loop header.
+ // loop header. We clear the set at entry of irreducible loops and any loop containing
+ // an irreducible loop, as in both cases, GVN can extend the liveness of an instruction
+ // across the irreducible loop.
+ // Note that, if we're not compiling OSR, we could still do GVN and introduce
+ // phis at irreducible loop headers. We decided it was not worth the complexity.
set->Clear();
} else {
+ DCHECK(!block->GetLoopInformation()->IsIrreducible());
DCHECK_EQ(block->GetDominator(), block->GetLoopInformation()->GetPreHeader());
set->Kill(side_effects_.GetLoopEffects(block));
}
diff --git a/compiler/optimizing/licm.cc b/compiler/optimizing/licm.cc
index 5a0b89c..7543cd6 100644
--- a/compiler/optimizing/licm.cc
+++ b/compiler/optimizing/licm.cc
@@ -101,16 +101,6 @@
SideEffects loop_effects = side_effects_.GetLoopEffects(block);
HBasicBlock* pre_header = loop_info->GetPreHeader();
- bool contains_irreducible_loop = false;
- if (graph_->HasIrreducibleLoops()) {
- for (HBlocksInLoopIterator it_loop(*loop_info); !it_loop.Done(); it_loop.Advance()) {
- if (it_loop.Current()->GetLoopInformation()->IsIrreducible()) {
- contains_irreducible_loop = true;
- break;
- }
- }
- }
-
for (HBlocksInLoopIterator it_loop(*loop_info); !it_loop.Done(); it_loop.Advance()) {
HBasicBlock* inner = it_loop.Current();
DCHECK(inner->IsInLoop());
@@ -123,11 +113,12 @@
visited->SetBit(inner->GetBlockId());
}
- if (contains_irreducible_loop) {
+ if (loop_info->ContainsIrreducibleLoop()) {
// We cannot licm in an irreducible loop, or in a natural loop containing an
// irreducible loop.
continue;
}
+ DCHECK(!loop_info->IsIrreducible());
// We can move an instruction that can throw only if it is the first
// throwing instruction in the loop. Note that the first potentially
diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc
index 1e6bf07..60329cc 100644
--- a/compiler/optimizing/nodes.cc
+++ b/compiler/optimizing/nodes.cc
@@ -446,8 +446,10 @@
}
GraphAnalysisResult HGraph::AnalyzeLoops() const {
- // Order does not matter.
- for (HReversePostOrderIterator it(*this); !it.Done(); it.Advance()) {
+ // We iterate post order to ensure we visit inner loops before outer loops.
+ // `PopulateRecursive` needs this guarantee to know whether a natural loop
+ // contains an irreducible loop.
+ for (HPostOrderIterator it(*this); !it.Done(); it.Advance()) {
HBasicBlock* block = it.Current();
if (block->IsLoopHeader()) {
if (block->IsCatchBlock()) {
@@ -580,6 +582,14 @@
blocks_.SetBit(block->GetBlockId());
block->SetInLoop(this);
+ if (block->IsLoopHeader()) {
+ // We're visiting loops in post-order, so inner loops must have been
+ // populated already.
+ DCHECK(block->GetLoopInformation()->IsPopulated());
+ if (block->GetLoopInformation()->IsIrreducible()) {
+ contains_irreducible_loop_ = true;
+ }
+ }
for (HBasicBlock* predecessor : block->GetPredecessors()) {
PopulateRecursive(predecessor);
}
@@ -683,6 +693,7 @@
}
if (is_irreducible_loop) {
irreducible_ = true;
+ contains_irreducible_loop_ = true;
graph->SetHasIrreducibleLoops(true);
}
}
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index 934d355..12ea059 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -650,6 +650,7 @@
: header_(header),
suspend_check_(nullptr),
irreducible_(false),
+ contains_irreducible_loop_(false),
back_edges_(graph->GetArena()->Adapter(kArenaAllocLoopInfoBackEdges)),
// Make bit vector growable, as the number of blocks may change.
blocks_(graph->GetArena(), graph->GetBlocks().size(), true, kArenaAllocLoopInfoBackEdges) {
@@ -657,6 +658,7 @@
}
bool IsIrreducible() const { return irreducible_; }
+ bool ContainsIrreducibleLoop() const { return contains_irreducible_loop_; }
void Dump(std::ostream& os);
@@ -727,6 +729,10 @@
bool HasBackEdgeNotDominatedByHeader() const;
+ bool IsPopulated() const {
+ return blocks_.GetHighestBitSet() != -1;
+ }
+
private:
// Internal recursive implementation of `Populate`.
void PopulateRecursive(HBasicBlock* block);
@@ -735,6 +741,7 @@
HBasicBlock* header_;
HSuspendCheck* suspend_check_;
bool irreducible_;
+ bool contains_irreducible_loop_;
ArenaVector<HBasicBlock*> back_edges_;
ArenaBitVector blocks_;
diff --git a/compiler/optimizing/register_allocator.cc b/compiler/optimizing/register_allocator.cc
index b1f9cbc..4405b80 100644
--- a/compiler/optimizing/register_allocator.cc
+++ b/compiler/optimizing/register_allocator.cc
@@ -1773,7 +1773,9 @@
// therefore will not have a location for that instruction for `to`.
// Because the instruction is a constant or the ArtMethod, we don't need to
// do anything: it will be materialized in the irreducible loop.
- DCHECK(IsMaterializableEntryBlockInstructionOfGraphWithIrreducibleLoop(defined_by));
+ DCHECK(IsMaterializableEntryBlockInstructionOfGraphWithIrreducibleLoop(defined_by))
+ << defined_by->DebugName() << ":" << defined_by->GetId()
+ << " " << from->GetBlockId() << " -> " << to->GetBlockId();
return;
}
diff --git a/compiler/optimizing/ssa_liveness_analysis.cc b/compiler/optimizing/ssa_liveness_analysis.cc
index 5534aea..36e0d99 100644
--- a/compiler/optimizing/ssa_liveness_analysis.cc
+++ b/compiler/optimizing/ssa_liveness_analysis.cc
@@ -309,17 +309,8 @@
}
if (block->IsLoopHeader()) {
- if (kIsDebugBuild && block->GetLoopInformation()->IsIrreducible()) {
- // To satisfy our liveness algorithm, we need to ensure loop headers of
- // irreducible loops do not have any live-in instructions, except constants
- // and the current method, which can be trivially re-materialized.
- for (uint32_t idx : live_in->Indexes()) {
- HInstruction* instruction = GetInstructionFromSsaIndex(idx);
- DCHECK(instruction->GetBlock()->IsEntryBlock()) << instruction->DebugName();
- DCHECK(!instruction->IsParameterValue());
- DCHECK(instruction->IsCurrentMethod() || instruction->IsConstant())
- << instruction->DebugName();
- }
+ if (kIsDebugBuild) {
+ CheckNoLiveInIrreducibleLoop(*block);
}
size_t last_position = block->GetLoopInformation()->GetLifetimeEnd();
// For all live_in instructions at the loop header, we need to create a range
@@ -344,6 +335,9 @@
// change in this loop), and the live_out set. If the live_out
// set does not change, there is no need to update the live_in set.
if (UpdateLiveOut(block) && UpdateLiveIn(block)) {
+ if (kIsDebugBuild) {
+ CheckNoLiveInIrreducibleLoop(block);
+ }
changed = true;
}
}
diff --git a/compiler/optimizing/ssa_liveness_analysis.h b/compiler/optimizing/ssa_liveness_analysis.h
index 1141fd1..1fcba8b 100644
--- a/compiler/optimizing/ssa_liveness_analysis.h
+++ b/compiler/optimizing/ssa_liveness_analysis.h
@@ -1260,6 +1260,23 @@
return instruction->GetType() == Primitive::kPrimNot;
}
+ void CheckNoLiveInIrreducibleLoop(const HBasicBlock& block) const {
+ if (!block.IsLoopHeader() || !block.GetLoopInformation()->IsIrreducible()) {
+ return;
+ }
+ BitVector* live_in = GetLiveInSet(block);
+ // To satisfy our liveness algorithm, we need to ensure loop headers of
+ // irreducible loops do not have any live-in instructions, except constants
+ // and the current method, which can be trivially re-materialized.
+ for (uint32_t idx : live_in->Indexes()) {
+ HInstruction* instruction = GetInstructionFromSsaIndex(idx);
+ DCHECK(instruction->GetBlock()->IsEntryBlock()) << instruction->DebugName();
+ DCHECK(!instruction->IsParameterValue());
+ DCHECK(instruction->IsCurrentMethod() || instruction->IsConstant())
+ << instruction->DebugName();
+ }
+ }
+
HGraph* const graph_;
CodeGenerator* const codegen_;
ArenaVector<BlockInfo*> block_infos_;
diff --git a/test/599-checker-irreducible-loop/expected.txt b/test/599-checker-irreducible-loop/expected.txt
new file mode 100644
index 0000000..573541a
--- /dev/null
+++ b/test/599-checker-irreducible-loop/expected.txt
@@ -0,0 +1 @@
+0
diff --git a/test/599-checker-irreducible-loop/info.txt b/test/599-checker-irreducible-loop/info.txt
new file mode 100644
index 0000000..1e0dd02
--- /dev/null
+++ b/test/599-checker-irreducible-loop/info.txt
@@ -0,0 +1,2 @@
+Regression test for optimizing in the presence of
+an irreducible loop.
diff --git a/test/599-checker-irreducible-loop/smali/IrreducibleLoop.smali b/test/599-checker-irreducible-loop/smali/IrreducibleLoop.smali
new file mode 100644
index 0000000..5331fd6
--- /dev/null
+++ b/test/599-checker-irreducible-loop/smali/IrreducibleLoop.smali
@@ -0,0 +1,56 @@
+# Copyright (C) 2016 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 LIrreducibleLoop;
+
+.super Ljava/lang/Object;
+
+## CHECK-START: int IrreducibleLoop.test(int) GVN (before)
+## CHECK-DAG: LoadClass loop:none
+## CHECK-DAG: LoadClass loop:{{B\d+}} outer_loop:none
+
+## CHECK-START: int IrreducibleLoop.test(int) GVN (after)
+## CHECK-DAG: LoadClass loop:none
+## CHECK-DAG: LoadClass loop:{{B\d+}} outer_loop:none
+.method public static test(I)I
+ .registers 2
+
+ sget v0, LIrreducibleLoop;->field1:I
+ sput v0, LIrreducibleLoop;->field2:I
+
+ if-eqz p0, :loop_entry
+ goto :exit
+
+ :loop_entry
+ if-eqz p0, :irreducible_loop_entry
+ sget v0, LIrreducibleLoop;->field2:I
+ sput v0, LIrreducibleLoop;->field1:I
+ if-eqz v0, :exit
+ goto :irreducible_other_loop_entry
+
+ :irreducible_loop_entry
+ if-eqz p0, :loop_back_edge
+ :irreducible_other_loop_entry
+ if-eqz v0, :loop_back_edge
+ goto :irreducible_loop_entry
+
+ :loop_back_edge
+ goto :loop_entry
+
+ :exit
+ return v0
+.end method
+
+.field public static field1:I
+.field public static field2:I
diff --git a/test/599-checker-irreducible-loop/src/Main.java b/test/599-checker-irreducible-loop/src/Main.java
new file mode 100644
index 0000000..b47721f
--- /dev/null
+++ b/test/599-checker-irreducible-loop/src/Main.java
@@ -0,0 +1,30 @@
+/*
+ * Copyright (C) 2016 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 {}
+
+ public static void main(String[] args) throws Exception {
+ Class<?> c = Class.forName("IrreducibleLoop");
+ Method m = c.getMethod("test", int.class);
+ Object[] arguments = { 42 };
+ // Invoke the code just for sanity checking.
+ System.out.println(m.invoke(null, arguments));
+ }
+}