Merge "ART: Fix critical edge splitting under try/catch"

9 files changed, 128 insertions, 11 deletions

diff --git a/compiler/optimizing/graph_checker.cc b/compiler/optimizing/graph_checker.cc
index dd380c25cc..0d7c796837 100644
--- a/compiler/optimizing/graph_checker.cc
+++ b/compiler/optimizing/graph_checker.cc
@@ -461,12 +461,18 @@ void SSAChecker::CheckLoop(HBasicBlock* loop_header) {
   int id = loop_header->GetBlockId();
   HLoopInformation* loop_information = loop_header->GetLoopInformation();
 
-  // Ensure the pre-header block is first in the list of
-  // predecessors of a loop header.
+  // Ensure the pre-header block is first in the list of predecessors of a loop
+  // header and that the header block is its only successor.
   if (!loop_header->IsLoopPreHeaderFirstPredecessor()) {
     AddError(StringPrintf(
         "Loop pre-header is not the first predecessor of the loop header %d.",
         id));
+  } else if (loop_information->GetPreHeader()->GetSuccessors().size() != 1) {
+    AddError(StringPrintf(
+        "Loop pre-header %d of loop defined by header %d has %zu successors.",
+        loop_information->GetPreHeader()->GetBlockId(),
+        id,
+        loop_information->GetPreHeader()->GetSuccessors().size()));
   }
 
   // Ensure the loop header has only one incoming branch and the remaining
@@ -509,6 +515,13 @@ void SSAChecker::CheckLoop(HBasicBlock* loop_header) {
             "Loop defined by header %d has an invalid back edge %d.",
             id,
             back_edge_id));
+      } else if (back_edge->GetLoopInformation() != loop_information) {
+        AddError(StringPrintf(
+            "Back edge %d of loop defined by header %d belongs to nested loop "
+            "with header %d.",
+            back_edge_id,
+            id,
+            back_edge->GetLoopInformation()->GetHeader()->GetBlockId()));
       }
     }
   }
diff --git a/compiler/optimizing/induction_var_analysis_test.cc b/compiler/optimizing/induction_var_analysis_test.cc
index b7262f6b29..5de94f43c9 100644
--- a/compiler/optimizing/induction_var_analysis_test.cc
+++ b/compiler/optimizing/induction_var_analysis_test.cc
@@ -69,10 +69,13 @@ class InductionVarAnalysisTest : public testing::Test {
     entry_ = new (&allocator_) HBasicBlock(graph_);
     graph_->AddBlock(entry_);
     BuildForLoop(0, n);
+    return_ = new (&allocator_) HBasicBlock(graph_);
+    graph_->AddBlock(return_);
     exit_ = new (&allocator_) HBasicBlock(graph_);
     graph_->AddBlock(exit_);
     entry_->AddSuccessor(loop_preheader_[0]);
-    loop_header_[0]->AddSuccessor(exit_);
+    loop_header_[0]->AddSuccessor(return_);
+    return_->AddSuccessor(exit_);
     graph_->SetEntryBlock(entry_);
     graph_->SetExitBlock(exit_);
 
@@ -91,6 +94,7 @@ class InductionVarAnalysisTest : public testing::Test {
     entry_->AddInstruction(new (&allocator_) HStoreLocal(tmp_, constant100_));
     dum_ = new (&allocator_) HLocal(n + 2);
     entry_->AddInstruction(dum_);
+    return_->AddInstruction(new (&allocator_) HReturnVoid());
     exit_->AddInstruction(new (&allocator_) HExit());
 
     // Provide loop instructions.
@@ -177,6 +181,7 @@ class InductionVarAnalysisTest : public testing::Test {
 
   // Fixed basic blocks and instructions.
   HBasicBlock* entry_;
+  HBasicBlock* return_;
   HBasicBlock* exit_;
   HInstruction* parameter_;  // "this"
   HInstruction* constant0_;
diff --git a/compiler/optimizing/induction_var_range_test.cc b/compiler/optimizing/induction_var_range_test.cc
index fda5153d43..c2ba157ed8 100644
--- a/compiler/optimizing/induction_var_range_test.cc
+++ b/compiler/optimizing/induction_var_range_test.cc
@@ -70,11 +70,14 @@ class InductionVarRangeTest : public testing::Test {
     graph_->AddBlock(loop_header);
     HBasicBlock* loop_body = new (&allocator_) HBasicBlock(graph_);
     graph_->AddBlock(loop_body);
+    HBasicBlock* return_block = new (&allocator_) HBasicBlock(graph_);
+    graph_->AddBlock(return_block);
     entry_block_->AddSuccessor(loop_preheader_);
     loop_preheader_->AddSuccessor(loop_header);
     loop_header->AddSuccessor(loop_body);
-    loop_header->AddSuccessor(exit_block_);
+    loop_header->AddSuccessor(return_block);
     loop_body->AddSuccessor(loop_header);
+    return_block->AddSuccessor(exit_block_);
     // Instructions.
     HLocal* induc = new (&allocator_) HLocal(0);
     entry_block_->AddInstruction(induc);
@@ -96,7 +99,8 @@ class InductionVarRangeTest : public testing::Test {
     loop_body->AddInstruction(increment_);
     loop_body->AddInstruction(new (&allocator_) HStoreLocal(induc, increment_));  // i += s
     loop_body->AddInstruction(new (&allocator_) HGoto());
-    exit_block_->AddInstruction(new (&allocator_) HReturnVoid());
+    return_block->AddInstruction(new (&allocator_) HReturnVoid());
+    exit_block_->AddInstruction(new (&allocator_) HExit());
   }
 
   /** Performs induction variable analysis. */
diff --git a/compiler/optimizing/licm_test.cc b/compiler/optimizing/licm_test.cc
index 47457dec7d..2bb769a430 100644
--- a/compiler/optimizing/licm_test.cc
+++ b/compiler/optimizing/licm_test.cc
@@ -42,12 +42,14 @@ class LICMTest : public testing::Test {
     loop_preheader_ = new (&allocator_) HBasicBlock(graph_);
     loop_header_ = new (&allocator_) HBasicBlock(graph_);
     loop_body_ = new (&allocator_) HBasicBlock(graph_);
+    return_ = new (&allocator_) HBasicBlock(graph_);
     exit_ = new (&allocator_) HBasicBlock(graph_);
 
     graph_->AddBlock(entry_);
     graph_->AddBlock(loop_preheader_);
     graph_->AddBlock(loop_header_);
     graph_->AddBlock(loop_body_);
+    graph_->AddBlock(return_);
     graph_->AddBlock(exit_);
 
     graph_->SetEntryBlock(entry_);
@@ -57,8 +59,9 @@ class LICMTest : public testing::Test {
     entry_->AddSuccessor(loop_preheader_);
     loop_preheader_->AddSuccessor(loop_header_);
     loop_header_->AddSuccessor(loop_body_);
-    loop_header_->AddSuccessor(exit_);
+    loop_header_->AddSuccessor(return_);
     loop_body_->AddSuccessor(loop_header_);
+    return_->AddSuccessor(exit_);
 
     // Provide boiler-plate instructions.
     parameter_ = new (&allocator_) HParameterValue(graph_->GetDexFile(), 0, 0, Primitive::kPrimNot);
@@ -89,6 +92,7 @@ class LICMTest : public testing::Test {
   HBasicBlock* loop_preheader_;
   HBasicBlock* loop_header_;
   HBasicBlock* loop_body_;
+  HBasicBlock* return_;
   HBasicBlock* exit_;
 
   HInstruction* parameter_;  // "this"
diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc
index 2d3dcf746b..7a8b463d13 100644
--- a/compiler/optimizing/nodes.cc
+++ b/compiler/optimizing/nodes.cc
@@ -383,19 +383,27 @@ void HGraph::ComputeTryBlockInformation() {
 }
 
 void HGraph::SimplifyCFG() {
-  // Simplify the CFG for future analysis, and code generation:
+// Simplify the CFG for future analysis, and code generation:
   // (1): Split critical edges.
-  // (2): Simplify loops by having only one back edge, and one preheader.
+  // (2): Simplify loops by having only one preheader.
   // NOTE: We're appending new blocks inside the loop, so we need to use index because iterators
   // can be invalidated. We remember the initial size to avoid iterating over the new blocks.
   for (size_t block_id = 0u, end = blocks_.size(); block_id != end; ++block_id) {
     HBasicBlock* block = blocks_[block_id];
     if (block == nullptr) continue;
-    if (block->NumberOfNormalSuccessors() > 1) {
-      for (size_t j = 0; j < block->GetSuccessors().size(); ++j) {
+    if (block->GetSuccessors().size() > 1) {
+      // Only split normal-flow edges. We cannot split exceptional edges as they
+      // are synthesized (approximate real control flow), and we do not need to
+      // anyway. Moves that would be inserted there are performed by the runtime.
+      for (size_t j = 0, e = block->NumberOfNormalSuccessors(); j < e; ++j) {
         HBasicBlock* successor = block->GetSuccessors()[j];
         DCHECK(!successor->IsCatchBlock());
-        if (successor->GetPredecessors().size() > 1) {
+        if (successor == exit_block_) {
+          // Throw->TryBoundary->Exit. Special case which we do not want to split
+          // because Goto->Exit is not allowed.
+          DCHECK(block->IsSingleTryBoundary());
+          DCHECK(block->GetSinglePredecessor()->GetLastInstruction()->IsThrow());
+        } else if (successor->GetPredecessors().size() > 1) {
           SplitCriticalEdge(block, successor);
           --j;
         }
diff --git a/test/547-regression-trycatch-critical-edge/expected.txt b/test/547-regression-trycatch-critical-edge/expected.txt
new file mode 100644
index 0000000000..e69de29bb2
--- /dev/null
+++ b/test/547-regression-trycatch-critical-edge/expected.txt
diff --git a/test/547-regression-trycatch-critical-edge/info.txt b/test/547-regression-trycatch-critical-edge/info.txt
new file mode 100644
index 0000000000..dc798c0016
--- /dev/null
+++ b/test/547-regression-trycatch-critical-edge/info.txt
@@ -0,0 +1,2 @@
+Test a specific SSA building regression a back edge would not be split due to
+being on try/catch boundary.
\ No newline at end of file
diff --git a/test/547-regression-trycatch-critical-edge/smali/TestCase.smali b/test/547-regression-trycatch-critical-edge/smali/TestCase.smali
new file mode 100644
index 0000000000..53a3cc5b62
--- /dev/null
+++ b/test/547-regression-trycatch-critical-edge/smali/TestCase.smali
@@ -0,0 +1,57 @@
+# 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;
+
+# The following test case would crash liveness analysis because the back edge of
+# the outer loop would have a smaller liveness position than the two back edges
+# of the inner loop. This was caused by a bug which did not split the critical
+# edge between TryBoundary and outer loop header (b/25493695).
+
+.method public static testCase(II)I
+  .registers 10
+
+  const v0, 0x0                                       # v0 = result
+  const v1, 0x1                                       # v1 = const 1
+
+  move v2, p0                                         # v2 = outer loop counter
+  :outer_loop
+  if-eqz v2, :return
+  sub-int/2addr v2, v1
+
+  :try_start
+
+  move v3, p1                                         # v3 = inner loop counter
+  :inner_loop
+  invoke-static {}, Ljava/lang/System;->nanoTime()J   # throwing instruction
+  if-eqz v3, :outer_loop                              # back edge of outer loop
+  sub-int/2addr v3, v1
+
+  invoke-static {}, Ljava/lang/System;->nanoTime()J   # throwing instruction
+  add-int/2addr v0, v1
+  goto :inner_loop                                    # back edge of inner loop
+
+  :try_end
+  .catchall {:try_start .. :try_end} :catch
+
+  :catch
+  const v4, 0x2
+  add-int/2addr v0, v4
+  goto :inner_loop                                    # back edge of inner loop
+
+  :return
+  return v0
+
+.end method
diff --git a/test/547-regression-trycatch-critical-edge/src/Main.java b/test/547-regression-trycatch-critical-edge/src/Main.java
new file mode 100644
index 0000000000..8eddac3fea
--- /dev/null
+++ b/test/547-regression-trycatch-critical-edge/src/Main.java
@@ -0,0 +1,24 @@
+/*
+ * 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 {
+
+  // Workaround for b/18051191.
+  class InnerClass {}
+
+  public static void main(String[] args) {}
+
+}