Implement suspend checks in new compiler.

For simplicity, they are currently placed on all (dex-level)
back edges, and at method entry.

Change-Id: I6e833e244d559dd788c69727e22fe40aff5b3435
diff --git a/build/Android.gtest.mk b/build/Android.gtest.mk
index 700bcf0..db60ff8 100644
--- a/build/Android.gtest.mk
+++ b/build/Android.gtest.mk
@@ -151,6 +151,7 @@
   compiler/optimizing/register_allocator_test.cc \
   compiler/optimizing/ssa_test.cc \
   compiler/optimizing/stack_map_test.cc \
+  compiler/optimizing/suspend_check_test.cc \
   compiler/output_stream_test.cc \
   compiler/utils/arena_allocator_test.cc \
   compiler/utils/dedupe_set_test.cc \
diff --git a/compiler/optimizing/builder.cc b/compiler/optimizing/builder.cc
index ecd6802..71e71f7 100644
--- a/compiler/optimizing/builder.cc
+++ b/compiler/optimizing/builder.cc
@@ -138,13 +138,15 @@
 
 template<typename T>
 void HGraphBuilder::If_22t(const Instruction& instruction, uint32_t dex_offset) {
+  int32_t target_offset = instruction.GetTargetOffset();
+  PotentiallyAddSuspendCheck(target_offset, dex_offset);
   HInstruction* first = LoadLocal(instruction.VRegA(), Primitive::kPrimInt);
   HInstruction* second = LoadLocal(instruction.VRegB(), Primitive::kPrimInt);
   T* comparison = new (arena_) T(first, second);
   current_block_->AddInstruction(comparison);
   HInstruction* ifinst = new (arena_) HIf(comparison);
   current_block_->AddInstruction(ifinst);
-  HBasicBlock* target = FindBlockStartingAt(dex_offset + instruction.GetTargetOffset());
+  HBasicBlock* target = FindBlockStartingAt(dex_offset + target_offset);
   DCHECK(target != nullptr);
   current_block_->AddSuccessor(target);
   target = FindBlockStartingAt(dex_offset + instruction.SizeInCodeUnits());
@@ -155,12 +157,15 @@
 
 template<typename T>
 void HGraphBuilder::If_21t(const Instruction& instruction, uint32_t dex_offset) {
+  int32_t target_offset = instruction.GetTargetOffset();
+  PotentiallyAddSuspendCheck(target_offset, dex_offset);
   HInstruction* value = LoadLocal(instruction.VRegA(), Primitive::kPrimInt);
   T* comparison = new (arena_) T(value, GetIntConstant(0));
   current_block_->AddInstruction(comparison);
   HInstruction* ifinst = new (arena_) HIf(comparison);
   current_block_->AddInstruction(ifinst);
-  HBasicBlock* target = FindBlockStartingAt(dex_offset + instruction.GetTargetOffset());
+  fprintf(stderr, "%d and %d\n", dex_offset, target_offset);
+  HBasicBlock* target = FindBlockStartingAt(dex_offset + target_offset);
   DCHECK(target != nullptr);
   current_block_->AddSuccessor(target);
   target = FindBlockStartingAt(dex_offset + instruction.SizeInCodeUnits());
@@ -196,6 +201,9 @@
     return nullptr;
   }
 
+  // Add the suspend check to the entry block.
+  entry_block_->AddInstruction(new (arena_) HSuspendCheck(0));
+
   size_t dex_offset = 0;
   while (code_ptr < code_end) {
     // Update the current block if dex_offset starts a new block.
@@ -462,7 +470,15 @@
   }
 }
 
-bool HGraphBuilder::AnalyzeDexInstruction(const Instruction& instruction, int32_t dex_offset) {
+void HGraphBuilder::PotentiallyAddSuspendCheck(int32_t target_offset, uint32_t dex_offset) {
+  if (target_offset <= 0) {
+    // Unconditionnally add a suspend check to backward branches. We can remove
+    // them after we recognize loops in the graph.
+    current_block_->AddInstruction(new (arena_) HSuspendCheck(dex_offset));
+  }
+}
+
+bool HGraphBuilder::AnalyzeDexInstruction(const Instruction& instruction, uint32_t dex_offset) {
   if (current_block_ == nullptr) {
     return true;  // Dead code
   }
@@ -580,7 +596,9 @@
     case Instruction::GOTO:
     case Instruction::GOTO_16:
     case Instruction::GOTO_32: {
-      HBasicBlock* target = FindBlockStartingAt(instruction.GetTargetOffset() + dex_offset);
+      int32_t offset = instruction.GetTargetOffset();
+      PotentiallyAddSuspendCheck(offset, dex_offset);
+      HBasicBlock* target = FindBlockStartingAt(offset + dex_offset);
       DCHECK(target != nullptr);
       current_block_->AddInstruction(new (arena_) HGoto());
       current_block_->AddSuccessor(target);
diff --git a/compiler/optimizing/builder.h b/compiler/optimizing/builder.h
index 170c427..e143786 100644
--- a/compiler/optimizing/builder.h
+++ b/compiler/optimizing/builder.h
@@ -54,7 +54,7 @@
   // Analyzes the dex instruction and adds HInstruction to the graph
   // to execute that instruction. Returns whether the instruction can
   // be handled.
-  bool AnalyzeDexInstruction(const Instruction& instruction, int32_t dex_offset);
+  bool AnalyzeDexInstruction(const Instruction& instruction, uint32_t dex_offset);
 
   // Finds all instructions that start a new block, and populates branch_targets_ with
   // the newly created blocks.
@@ -70,6 +70,7 @@
   HLocal* GetLocalAt(int register_index) const;
   void UpdateLocal(int register_index, HInstruction* instruction) const;
   HInstruction* LoadLocal(int register_index, Primitive::Type type) const;
+  void PotentiallyAddSuspendCheck(int32_t target_offset, uint32_t dex_offset);
 
   // Temporarily returns whether the compiler supports the parameters
   // of the method.
diff --git a/compiler/optimizing/code_generator_arm.cc b/compiler/optimizing/code_generator_arm.cc
index e72e39b..9903092 100644
--- a/compiler/optimizing/code_generator_arm.cc
+++ b/compiler/optimizing/code_generator_arm.cc
@@ -90,6 +90,29 @@
   DISALLOW_COPY_AND_ASSIGN(StackOverflowCheckSlowPathARM);
 };
 
+class SuspendCheckSlowPathARM : public SlowPathCode {
+ public:
+  explicit SuspendCheckSlowPathARM(HSuspendCheck* instruction)
+      : instruction_(instruction) {}
+
+  virtual void EmitNativeCode(CodeGenerator* codegen) OVERRIDE {
+    __ Bind(GetEntryLabel());
+    int32_t offset = QUICK_ENTRYPOINT_OFFSET(kArmWordSize, pTestSuspend).Int32Value();
+    __ ldr(LR, Address(TR, offset));
+    __ blx(LR);
+    codegen->RecordPcInfo(instruction_, instruction_->GetDexPc());
+    __ b(GetReturnLabel());
+  }
+
+  Label* GetReturnLabel() { return &return_label_; }
+
+ private:
+  HSuspendCheck* const instruction_;
+  Label return_label_;
+
+  DISALLOW_COPY_AND_ASSIGN(SuspendCheckSlowPathARM);
+};
+
 class BoundsCheckSlowPathARM : public SlowPathCode {
  public:
   explicit BoundsCheckSlowPathARM(HBoundsCheck* instruction,
@@ -1494,6 +1517,21 @@
   codegen_->GetMoveResolver()->EmitNativeCode(instruction);
 }
 
+void LocationsBuilderARM::VisitSuspendCheck(HSuspendCheck* instruction) {
+  new (GetGraph()->GetArena()) LocationSummary(instruction, LocationSummary::kCallOnSlowPath);
+}
+
+void InstructionCodeGeneratorARM::VisitSuspendCheck(HSuspendCheck* instruction) {
+  SuspendCheckSlowPathARM* slow_path =
+      new (GetGraph()->GetArena()) SuspendCheckSlowPathARM(instruction);
+  codegen_->AddSlowPath(slow_path);
+
+  __ AddConstant(R4, R4, -1);
+  __ cmp(R4, ShifterOperand(0));
+  __ b(slow_path->GetEntryLabel(), LE);
+  __ Bind(slow_path->GetReturnLabel());
+}
+
 ArmAssembler* ParallelMoveResolverARM::GetAssembler() const {
   return codegen_->GetAssembler();
 }
diff --git a/compiler/optimizing/code_generator_x86.cc b/compiler/optimizing/code_generator_x86.cc
index 6602d3f..2ecc46e 100644
--- a/compiler/optimizing/code_generator_x86.cc
+++ b/compiler/optimizing/code_generator_x86.cc
@@ -114,6 +114,27 @@
   DISALLOW_COPY_AND_ASSIGN(BoundsCheckSlowPathX86);
 };
 
+class SuspendCheckSlowPathX86 : public SlowPathCode {
+ public:
+  explicit SuspendCheckSlowPathX86(HSuspendCheck* instruction)
+      : instruction_(instruction) {}
+
+  virtual void EmitNativeCode(CodeGenerator* codegen) OVERRIDE {
+    __ Bind(GetEntryLabel());
+    __ fs()->call(Address::Absolute(QUICK_ENTRYPOINT_OFFSET(kX86WordSize, pTestSuspend)));
+    codegen->RecordPcInfo(instruction_, instruction_->GetDexPc());
+    __ jmp(GetReturnLabel());
+  }
+
+  Label* GetReturnLabel() { return &return_label_; }
+
+ private:
+  HSuspendCheck* const instruction_;
+  Label return_label_;
+
+  DISALLOW_COPY_AND_ASSIGN(SuspendCheckSlowPathX86);
+};
+
 #undef __
 #define __ reinterpret_cast<X86Assembler*>(GetAssembler())->
 
@@ -1483,6 +1504,20 @@
   codegen_->GetMoveResolver()->EmitNativeCode(instruction);
 }
 
+void LocationsBuilderX86::VisitSuspendCheck(HSuspendCheck* instruction) {
+  new (GetGraph()->GetArena()) LocationSummary(instruction, LocationSummary::kCall);
+}
+
+void InstructionCodeGeneratorX86::VisitSuspendCheck(HSuspendCheck* instruction) {
+  SuspendCheckSlowPathX86* slow_path =
+      new (GetGraph()->GetArena()) SuspendCheckSlowPathX86(instruction);
+  codegen_->AddSlowPath(slow_path);
+  __ fs()->cmpl(Address::Absolute(
+      Thread::ThreadFlagsOffset<kX86WordSize>().Int32Value()), Immediate(0));
+  __ j(kNotEqual, slow_path->GetEntryLabel());
+  __ Bind(slow_path->GetReturnLabel());
+}
+
 X86Assembler* ParallelMoveResolverX86::GetAssembler() const {
   return codegen_->GetAssembler();
 }
diff --git a/compiler/optimizing/code_generator_x86_64.cc b/compiler/optimizing/code_generator_x86_64.cc
index b2d81e3..2f352e0 100644
--- a/compiler/optimizing/code_generator_x86_64.cc
+++ b/compiler/optimizing/code_generator_x86_64.cc
@@ -95,6 +95,27 @@
   DISALLOW_COPY_AND_ASSIGN(StackOverflowCheckSlowPathX86_64);
 };
 
+class SuspendCheckSlowPathX86_64 : public SlowPathCode {
+ public:
+  explicit SuspendCheckSlowPathX86_64(HSuspendCheck* instruction)
+      : instruction_(instruction) {}
+
+  virtual void EmitNativeCode(CodeGenerator* codegen) OVERRIDE {
+    __ Bind(GetEntryLabel());
+    __ gs()->call(Address::Absolute(QUICK_ENTRYPOINT_OFFSET(kX86_64WordSize, pTestSuspend), true));
+    codegen->RecordPcInfo(instruction_, instruction_->GetDexPc());
+    __ jmp(GetReturnLabel());
+  }
+
+  Label* GetReturnLabel() { return &return_label_; }
+
+ private:
+  HSuspendCheck* const instruction_;
+  Label return_label_;
+
+  DISALLOW_COPY_AND_ASSIGN(SuspendCheckSlowPathX86_64);
+};
+
 class BoundsCheckSlowPathX86_64 : public SlowPathCode {
  public:
   explicit BoundsCheckSlowPathX86_64(HBoundsCheck* instruction,
@@ -1329,6 +1350,20 @@
   codegen_->GetMoveResolver()->EmitNativeCode(instruction);
 }
 
+void LocationsBuilderX86_64::VisitSuspendCheck(HSuspendCheck* instruction) {
+  new (GetGraph()->GetArena()) LocationSummary(instruction, LocationSummary::kCallOnSlowPath);
+}
+
+void InstructionCodeGeneratorX86_64::VisitSuspendCheck(HSuspendCheck* instruction) {
+  SuspendCheckSlowPathX86_64* slow_path =
+      new (GetGraph()->GetArena()) SuspendCheckSlowPathX86_64(instruction);
+  codegen_->AddSlowPath(slow_path);
+  __ gs()->cmpl(Address::Absolute(
+      Thread::ThreadFlagsOffset<kX86_64WordSize>().Int32Value(), true), Immediate(0));
+  __ j(kNotEqual, slow_path->GetEntryLabel());
+  __ Bind(slow_path->GetReturnLabel());
+}
+
 X86_64Assembler* ParallelMoveResolverX86_64::GetAssembler() const {
   return codegen_->GetAssembler();
 }
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index 9018fee..ed6dd93 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -443,6 +443,7 @@
   M(BoundsCheck)                                           \
   M(NullCheck)                                             \
   M(Temporary)                                             \
+  M(SuspendCheck)                                          \
 
 #define FOR_EACH_INSTRUCTION(M)                            \
   FOR_EACH_CONCRETE_INSTRUCTION(M)                         \
@@ -1593,6 +1594,25 @@
   DISALLOW_COPY_AND_ASSIGN(HTemporary);
 };
 
+class HSuspendCheck : public HTemplateInstruction<0> {
+ public:
+  explicit HSuspendCheck(uint32_t dex_pc)
+      : HTemplateInstruction(SideEffects::ChangesSomething()), dex_pc_(dex_pc) {}
+
+  virtual bool NeedsEnvironment() const {
+    return true;
+  }
+
+  uint32_t GetDexPc() const { return dex_pc_; }
+
+  DECLARE_INSTRUCTION(SuspendCheck);
+
+ private:
+  const uint32_t dex_pc_;
+
+  DISALLOW_COPY_AND_ASSIGN(HSuspendCheck);
+};
+
 class MoveOperands : public ArenaObject {
  public:
   MoveOperands(Location source, Location destination)
diff --git a/compiler/optimizing/suspend_check_test.cc b/compiler/optimizing/suspend_check_test.cc
new file mode 100644
index 0000000..65fc2d8
--- /dev/null
+++ b/compiler/optimizing/suspend_check_test.cc
@@ -0,0 +1,77 @@
+/*
+ * Copyright (C) 2014 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.
+ */
+
+#include "builder.h"
+#include "dex_instruction.h"
+#include "nodes.h"
+#include "optimizing_unit_test.h"
+
+#include "gtest/gtest.h"
+
+namespace art {
+
+/**
+ * Check that the HGraphBuilder adds suspend checks to backward branches.
+ */
+
+static void TestCode(const uint16_t* data) {
+  ArenaPool pool;
+  ArenaAllocator allocator(&pool);
+  HGraphBuilder builder(&allocator);
+  const DexFile::CodeItem* item = reinterpret_cast<const DexFile::CodeItem*>(data);
+  HGraph* graph = builder.BuildGraph(*item);
+  ASSERT_NE(graph, nullptr);
+
+  HBasicBlock* first_block = graph->GetEntryBlock()->GetSuccessors().Get(0);
+  HInstruction* first_instruction = first_block->GetFirstInstruction();
+  // Account for some tests having a store local as first instruction.
+  ASSERT_TRUE(first_instruction->IsSuspendCheck()
+              || first_instruction->GetNext()->IsSuspendCheck());
+}
+
+TEST(CodegenTest, CFG1) {
+  const uint16_t data[] = ZERO_REGISTER_CODE_ITEM(
+    Instruction::NOP,
+    Instruction::GOTO | 0xFF00);
+
+  TestCode(data);
+}
+
+TEST(CodegenTest, CFG2) {
+  const uint16_t data[] = ZERO_REGISTER_CODE_ITEM(
+    Instruction::GOTO_32, 0, 0);
+
+  TestCode(data);
+}
+
+TEST(CodegenTest, CFG3) {
+  const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
+    Instruction::CONST_4 | 0 | 0,
+    Instruction::IF_EQ, 0xFFFF,
+    Instruction::RETURN_VOID);
+
+  TestCode(data);
+}
+
+TEST(CodegenTest, CFG4) {
+  const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
+    Instruction::CONST_4 | 0 | 0,
+    Instruction::IF_NE, 0xFFFF,
+    Instruction::RETURN_VOID);
+
+  TestCode(data);
+}
+}  // namespace art
diff --git a/test/121-simple-suspend-check/expected.txt b/test/121-simple-suspend-check/expected.txt
new file mode 100644
index 0000000..7ef22e9
--- /dev/null
+++ b/test/121-simple-suspend-check/expected.txt
@@ -0,0 +1 @@
+PASS
diff --git a/test/121-simple-suspend-check/info.txt b/test/121-simple-suspend-check/info.txt
new file mode 100644
index 0000000..61611f9
--- /dev/null
+++ b/test/121-simple-suspend-check/info.txt
@@ -0,0 +1 @@
+Simple test to ensure the compiler emits suspend checks on loops.
diff --git a/test/121-simple-suspend-check/src/Main.java b/test/121-simple-suspend-check/src/Main.java
new file mode 100644
index 0000000..80daf37
--- /dev/null
+++ b/test/121-simple-suspend-check/src/Main.java
@@ -0,0 +1,35 @@
+/*
+ * Copyright (C) 2014 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 {
+  public static void main(String args[]) {
+    SpinThread thread = new SpinThread();
+    thread.setDaemon(true);
+    thread.start();
+    Runtime.getRuntime().gc();
+    try {
+      Thread.sleep(3000);
+    } catch (InterruptedException ie) {/*ignore */}
+    Runtime.getRuntime().gc();
+    System.out.println("PASS");
+  }
+}
+
+class SpinThread extends Thread {
+  public void run() {
+    while (true) {}
+  }
+}