Fix suspend check optimization

Art's Quick compiler currently uses a convervative mechanism
to ensure that a safe point will be reached within a "small" amount
of time.  Explicit suspend checks are placed prior to backwards
branches and on returns.  There are a lot of ways to optimize,
which we'll get to in the future, but for now the only optimization
is to detect a backwards branch that targets a return block.  That's
a common pattern in dex, and simple to detect.  In those cases, we can
suppress the suspend check on the backwards branch knowing that the
return will do it.

However, the notion of what is a backwards branch got a bit muddied
with some mir optimizations that transform the graph by changing the
sense of branches.  What started off as a taken backwards branch may
turn into a fallthrough backwards branch.

This CL avoid the confusion by marking branches backwards based on
their original dex targets rather than using the post-transform test
of backwardness.

Change-Id: I9b30be168c801af51bae7f66ecd442edcb115a18

7 files changed, 131 insertions, 12 deletions

diff --git a/compiler/dex/mir_graph.cc b/compiler/dex/mir_graph.cc
index 86f6ee5..5732dce 100644
--- a/compiler/dex/mir_graph.cc
+++ b/compiler/dex/mir_graph.cc
@@ -306,6 +306,9 @@ BasicBlock* MIRGraph::ProcessCanBranch(BasicBlock* cur_block, MIR* insn, int cur
     default:
       LOG(FATAL) << "Unexpected opcode(" << insn->dalvikInsn.opcode << ") with kBranch set";
   }
+  if (target <= cur_offset) {
+    insn->backwards_branch = true;
+  }
   BasicBlock *taken_block = FindBlock(target, /* split */ true, /* create */ true,
                                       /* immed_pred_block_p */ &cur_block);
   cur_block->taken = taken_block;
diff --git a/compiler/dex/mir_graph.h b/compiler/dex/mir_graph.h
index 84ab259..45e425b 100644
--- a/compiler/dex/mir_graph.h
+++ b/compiler/dex/mir_graph.h
@@ -232,7 +232,8 @@ struct SSARepresentation {
  */
 struct MIR {
   DecodedInstruction dalvikInsn;
-  unsigned int width;
+  uint16_t width;
+  bool backwards_branch;          // TODO: may be useful to make this an attribute flag word.
   unsigned int offset;
   int m_unit_index;               // From which method was this MIR included
   MIR* prev;
diff --git a/compiler/dex/mir_optimization.cc b/compiler/dex/mir_optimization.cc
index a6314f4..82ba6e3 100644
--- a/compiler/dex/mir_optimization.cc
+++ b/compiler/dex/mir_optimization.cc
@@ -153,7 +153,14 @@ static BasicBlock* NextDominatedBlock(BasicBlock* bb) {
   }
   DCHECK((bb->block_type == kEntryBlock) || (bb->block_type == kDalvikByteCode)
       || (bb->block_type == kExitBlock));
-  bb = bb->fall_through;
+  if (((bb->taken != NULL) && (bb->fall_through == NULL)) &&
+      ((bb->taken->block_type == kDalvikByteCode) || (bb->taken->block_type == kExitBlock))) {
+    // Follow simple unconditional branches.
+    bb = bb->taken;
+  } else {
+    // Follow simple fallthrough
+    bb = (bb->taken != NULL) ? NULL : bb->fall_through;
+  }
   if (bb == NULL || (Predecessors(bb) != 1)) {
     return NULL;
   }
@@ -303,7 +310,8 @@ bool MIRGraph::BasicBlockOpt(BasicBlock* bb) {
         case Instruction::IF_GEZ:
         case Instruction::IF_GTZ:
         case Instruction::IF_LEZ:
-          if (bb->taken->dominates_return) {
+          // If we've got a backwards branch to return, no need to suspend check.
+          if ((bb->taken->dominates_return) && (mir->backwards_branch)) {
             mir->optimization_flags |= MIR_IGNORE_SUSPEND_CHECK;
             if (cu_->verbose) {
               LOG(INFO) << "Suppressed suspend check on branch to return at 0x" << std::hex << mir->offset;
diff --git a/compiler/dex/quick/mir_to_lir.cc b/compiler/dex/quick/mir_to_lir.cc
index 74eaa66..8f42999 100644
--- a/compiler/dex/quick/mir_to_lir.cc
+++ b/compiler/dex/quick/mir_to_lir.cc
@@ -239,7 +239,7 @@ void Mir2Lir::CompileDalvikInstruction(MIR* mir, BasicBlock* bb, LIR* label_list
     case Instruction::GOTO:
     case Instruction::GOTO_16:
     case Instruction::GOTO_32:
-      if (bb->taken->start_offset <= mir->offset) {
+      if (mir->backwards_branch) {
         GenSuspendTestAndBranch(opt_flags, &label_list[bb->taken->id]);
       } else {
         OpUnconditionalBranch(&label_list[bb->taken->id]);
@@ -273,19 +273,17 @@ void Mir2Lir::CompileDalvikInstruction(MIR* mir, BasicBlock* bb, LIR* label_list
     case Instruction::IF_LE: {
       LIR* taken = &label_list[bb->taken->id];
       LIR* fall_through = &label_list[bb->fall_through->id];
-      bool backward_branch;
-      backward_branch = (bb->taken->start_offset <= mir->offset);
       // Result known at compile time?
       if (rl_src[0].is_const && rl_src[1].is_const) {
         bool is_taken = EvaluateBranch(opcode, mir_graph_->ConstantValue(rl_src[0].orig_sreg),
                                        mir_graph_->ConstantValue(rl_src[1].orig_sreg));
-        if (is_taken && backward_branch) {
+        if (is_taken && mir->backwards_branch) {
           GenSuspendTest(opt_flags);
         }
         int id = is_taken ? bb->taken->id : bb->fall_through->id;
         OpUnconditionalBranch(&label_list[id]);
       } else {
-        if (backward_branch) {
+        if (mir->backwards_branch) {
           GenSuspendTest(opt_flags);
         }
         GenCompareAndBranch(opcode, rl_src[0], rl_src[1], taken,
@@ -302,18 +300,16 @@ void Mir2Lir::CompileDalvikInstruction(MIR* mir, BasicBlock* bb, LIR* label_list
     case Instruction::IF_LEZ: {
       LIR* taken = &label_list[bb->taken->id];
       LIR* fall_through = &label_list[bb->fall_through->id];
-      bool backward_branch;
-      backward_branch = (bb->taken->start_offset <= mir->offset);
       // Result known at compile time?
       if (rl_src[0].is_const) {
         bool is_taken = EvaluateBranch(opcode, mir_graph_->ConstantValue(rl_src[0].orig_sreg), 0);
-        if (is_taken && backward_branch) {
+        if (is_taken && mir->backwards_branch) {
           GenSuspendTest(opt_flags);
         }
         int id = is_taken ? bb->taken->id : bb->fall_through->id;
         OpUnconditionalBranch(&label_list[id]);
       } else {
-        if (backward_branch) {
+        if (mir->backwards_branch) {
           GenSuspendTest(opt_flags);
         }
         GenCompareZeroAndBranch(opcode, rl_src[0], taken, fall_through);
diff --git a/test/109-suspend-check/expected.txt b/test/109-suspend-check/expected.txt
new file mode 100644
index 0000000..07cc825
--- /dev/null
+++ b/test/109-suspend-check/expected.txt
@@ -0,0 +1,7 @@
+Running (5 seconds) ...
+.
+.
+.
+.
+.
+Done.
diff --git a/test/109-suspend-check/info.txt b/test/109-suspend-check/info.txt
new file mode 100644
index 0000000..d89d66a
--- /dev/null
+++ b/test/109-suspend-check/info.txt
@@ -0,0 +1,2 @@
+To support garbage collection, debugging and profiling the VM must be able to send all threads
+to a safepoint.  This tests the ability of the VM to do this for a tight loop.
diff --git a/test/109-suspend-check/src/Main.java b/test/109-suspend-check/src/Main.java
new file mode 100644
index 0000000..d92b9e5
--- /dev/null
+++ b/test/109-suspend-check/src/Main.java
@@ -0,0 +1,102 @@
+/*
+ * Copyright (C) 2013 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 {
+    private static final int TEST_TIME = 5;
+
+    public static void main(String[] args) {
+        System.out.println("Running (" + TEST_TIME + " seconds) ...");
+        InfiniteForLoop forLoop = new InfiniteForLoop();
+        InfiniteWhileLoop whileLoop = new InfiniteWhileLoop();
+        InfiniteDoWhileLoop doWhileLoop = new InfiniteDoWhileLoop();
+        MakeGarbage garbage = new MakeGarbage();
+        forLoop.start();
+        whileLoop.start();
+        doWhileLoop.start();
+        garbage.start();
+        for (int i = 0; i < TEST_TIME; i++) {
+          System.gc();
+          System.out.println(".");
+          sleep(1000);
+        }
+        forLoop.stopNow();
+        whileLoop.stopNow();
+        doWhileLoop.stopNow();
+        garbage.stopNow();
+        System.out.println("Done.");
+    }
+
+    public static void sleep(int ms) {
+        try {
+            Thread.sleep(ms);
+        } catch (InterruptedException ie) {
+            System.err.println("sleep was interrupted");
+        }
+    }
+}
+
+class InfiniteWhileLoop extends Thread {
+  volatile private boolean keepGoing = true;
+  public void run() {
+    int i = 0;
+    while (keepGoing) {
+      i++;
+    }
+  }
+  public void stopNow() {
+    keepGoing = false;
+  }
+}
+
+class InfiniteDoWhileLoop extends Thread {
+  volatile private boolean keepGoing = true;
+  public void run() {
+    int i = 0;
+    do {
+      i++;
+    } while (keepGoing);
+  }
+  public void stopNow() {
+    keepGoing = false;
+  }
+}
+
+class InfiniteForLoop extends Thread {
+  int count = 100000;
+  volatile private boolean keepGoing = true;
+  public void run() {
+    int i = 0;
+    for (int j = 0; keepGoing; j++) {
+      i += j;
+    }
+  }
+  public void stopNow() {
+    keepGoing = false;
+  }
+}
+
+
+class MakeGarbage extends Thread {
+  volatile private boolean keepGoing = true;
+  public void run() {
+    while (keepGoing) {
+      byte[] garbage = new byte[100000];
+    }
+  }
+  public void stopNow() {
+    keepGoing = false;
+  }
+}