AArch64: Add HInstruction scheduling support.

This commit adds a new `HInstructionScheduling` pass that performs
basic scheduling on the `HGraph`.

Currently, scheduling is performed at the block level, so no
`HInstruction` ever leaves its block in this pass.

The scheduling process iterates through blocks in the graph. For
blocks that we can and want to schedule:
1) Build a dependency graph for instructions. It includes data
   dependencies (inputs/uses), but also environment dependencies and
   side-effect dependencies.
2) Schedule the dependency graph. This is a topological sort of the
   dependency graph, using heuristics to decide what node to schedule
   first when there are multiple candidates. Currently the heuristics
   only consider instruction latencies and schedule first the
   instructions that are on the critical path.

Test: m test-art-host
Test: m test-art-target

Change-Id: Iec103177d4f059666d7c9626e5770531fbc5ccdc

1 files changed, 238 insertions, 0 deletions

diff --git a/compiler/optimizing/scheduler_test.cc b/compiler/optimizing/scheduler_test.cc
new file mode 100644
index 0000000000..31d13e2a26
--- /dev/null
+++ b/compiler/optimizing/scheduler_test.cc
@@ -0,0 +1,238 @@
+/*
+ * 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.
+ */
+
+#include "base/arena_allocator.h"
+#include "builder.h"
+#include "codegen_test_utils.h"
+#include "common_compiler_test.h"
+#include "nodes.h"
+#include "optimizing_unit_test.h"
+#include "pc_relative_fixups_x86.h"
+#include "register_allocator.h"
+#include "scheduler.h"
+
+#ifdef ART_ENABLE_CODEGEN_arm64
+#include "scheduler_arm64.h"
+#endif
+
+namespace art {
+
+// Return all combinations of ISA and code generator that are executable on
+// hardware, or on simulator, and that we'd like to test.
+static ::std::vector<CodegenTargetConfig> GetTargetConfigs() {
+  ::std::vector<CodegenTargetConfig> v;
+  ::std::vector<CodegenTargetConfig> test_config_candidates = {
+#ifdef ART_ENABLE_CODEGEN_arm
+    CodegenTargetConfig(kArm, create_codegen_arm),
+    CodegenTargetConfig(kThumb2, create_codegen_arm),
+#endif
+#ifdef ART_ENABLE_CODEGEN_arm64
+    CodegenTargetConfig(kArm64, create_codegen_arm64),
+#endif
+#ifdef ART_ENABLE_CODEGEN_x86
+    CodegenTargetConfig(kX86, create_codegen_x86),
+#endif
+#ifdef ART_ENABLE_CODEGEN_x86_64
+    CodegenTargetConfig(kX86_64, create_codegen_x86_64),
+#endif
+#ifdef ART_ENABLE_CODEGEN_mips
+    CodegenTargetConfig(kMips, create_codegen_mips),
+#endif
+#ifdef ART_ENABLE_CODEGEN_mips64
+    CodegenTargetConfig(kMips64, create_codegen_mips64)
+#endif
+  };
+
+  for (auto test_config : test_config_candidates) {
+    if (CanExecute(test_config.GetInstructionSet())) {
+      v.push_back(test_config);
+    }
+  }
+
+  return v;
+}
+
+class SchedulerTest : public CommonCompilerTest {};
+
+#ifdef ART_ENABLE_CODEGEN_arm64
+TEST_F(SchedulerTest, DependencyGraph) {
+  ArenaPool pool;
+  ArenaAllocator allocator(&pool);
+  HGraph* graph = CreateGraph(&allocator);
+  HBasicBlock* entry = new (&allocator) HBasicBlock(graph);
+  HBasicBlock* block1 = new (&allocator) HBasicBlock(graph);
+  graph->AddBlock(entry);
+  graph->AddBlock(block1);
+  graph->SetEntryBlock(entry);
+
+  // entry:
+  // array         ParameterValue
+  // c1            IntConstant
+  // c2            IntConstant
+  // block1:
+  // add1          Add [c1, c2]
+  // add2          Add [add1, c2]
+  // mul           Mul [add1, add2]
+  // div_check     DivZeroCheck [add2] (env: add2, mul)
+  // div           Div [add1, div_check]
+  // array_get1    ArrayGet [array, add1]
+  // array_set1    ArraySet [array, add1, add2]
+  // array_get2    ArrayGet [array, add1]
+  // array_set2    ArraySet [array, add1, add2]
+
+  HInstruction* array = new (&allocator) HParameterValue(graph->GetDexFile(),
+                                                         dex::TypeIndex(0),
+                                                         0,
+                                                         Primitive::kPrimNot);
+  HInstruction* c1 = graph->GetIntConstant(1);
+  HInstruction* c2 = graph->GetIntConstant(10);
+  HInstruction* add1 = new (&allocator) HAdd(Primitive::kPrimInt, c1, c2);
+  HInstruction* add2 = new (&allocator) HAdd(Primitive::kPrimInt, add1, c2);
+  HInstruction* mul = new (&allocator) HMul(Primitive::kPrimInt, add1, add2);
+  HInstruction* div_check = new (&allocator) HDivZeroCheck(add2, 0);
+  HInstruction* div = new (&allocator) HDiv(Primitive::kPrimInt, add1, div_check, 0);
+  HInstruction* array_get1 = new (&allocator) HArrayGet(array, add1, Primitive::kPrimInt, 0);
+  HInstruction* array_set1 = new (&allocator) HArraySet(array, add1, add2, Primitive::kPrimInt, 0);
+  HInstruction* array_get2 = new (&allocator) HArrayGet(array, add1, Primitive::kPrimInt, 0);
+  HInstruction* array_set2 = new (&allocator) HArraySet(array, add1, add2, Primitive::kPrimInt, 0);
+
+  DCHECK(div_check->CanThrow());
+
+  entry->AddInstruction(array);
+
+  HInstruction* block_instructions[] = {add1,
+                                        add2,
+                                        mul,
+                                        div_check,
+                                        div,
+                                        array_get1,
+                                        array_set1,
+                                        array_get2,
+                                        array_set2};
+  for (auto instr : block_instructions) {
+    block1->AddInstruction(instr);
+  }
+
+  HEnvironment* environment = new (&allocator) HEnvironment(&allocator,
+                                                            2,
+                                                            graph->GetArtMethod(),
+                                                            0,
+                                                            div_check);
+  div_check->SetRawEnvironment(environment);
+  environment->SetRawEnvAt(0, add2);
+  add2->AddEnvUseAt(div_check->GetEnvironment(), 0);
+  environment->SetRawEnvAt(1, mul);
+  mul->AddEnvUseAt(div_check->GetEnvironment(), 1);
+
+  ArenaAllocator* arena = graph->GetArena();
+  CriticalPathSchedulingNodeSelector critical_path_selector;
+  arm64::HSchedulerARM64 scheduler(arena, &critical_path_selector);
+  SchedulingGraph scheduling_graph(&scheduler, arena);
+  // Instructions must be inserted in reverse order into the scheduling graph.
+  for (auto instr : ReverseRange(block_instructions)) {
+    scheduling_graph.AddNode(instr);
+  }
+
+  // Should not have dependencies cross basic blocks.
+  ASSERT_FALSE(scheduling_graph.HasImmediateDataDependency(add1, c1));
+  ASSERT_FALSE(scheduling_graph.HasImmediateDataDependency(add2, c2));
+
+  // Define-use dependency.
+  ASSERT_TRUE(scheduling_graph.HasImmediateDataDependency(add2, add1));
+  ASSERT_FALSE(scheduling_graph.HasImmediateDataDependency(add1, add2));
+  ASSERT_TRUE(scheduling_graph.HasImmediateDataDependency(div_check, add2));
+  ASSERT_FALSE(scheduling_graph.HasImmediateDataDependency(div_check, add1));
+  ASSERT_TRUE(scheduling_graph.HasImmediateDataDependency(div, div_check));
+  ASSERT_TRUE(scheduling_graph.HasImmediateDataDependency(array_set1, add1));
+  ASSERT_TRUE(scheduling_graph.HasImmediateDataDependency(array_set1, add2));
+
+  // Read and write dependencies
+  ASSERT_TRUE(scheduling_graph.HasImmediateOtherDependency(array_set1, array_get1));
+  ASSERT_TRUE(scheduling_graph.HasImmediateOtherDependency(array_set2, array_get2));
+  ASSERT_TRUE(scheduling_graph.HasImmediateOtherDependency(array_get2, array_set1));
+  ASSERT_TRUE(scheduling_graph.HasImmediateOtherDependency(array_set2, array_set1));
+
+  // Env dependency.
+  ASSERT_TRUE(scheduling_graph.HasImmediateOtherDependency(div_check, mul));
+  ASSERT_FALSE(scheduling_graph.HasImmediateOtherDependency(mul, div_check));
+
+  // CanThrow.
+  ASSERT_TRUE(scheduling_graph.HasImmediateOtherDependency(array_set1, div_check));
+}
+#endif
+
+static void CompileWithRandomSchedulerAndRun(const uint16_t* data,
+                                             bool has_result,
+                                             int expected) {
+  for (CodegenTargetConfig target_config : GetTargetConfigs()) {
+    ArenaPool pool;
+    ArenaAllocator arena(&pool);
+    HGraph* graph = CreateCFG(&arena, data);
+
+    // Schedule the graph randomly.
+    HInstructionScheduling scheduling(graph, target_config.GetInstructionSet());
+    scheduling.Run(/*only_optimize_loop_blocks*/ false, /*schedule_randomly*/ true);
+
+    RunCode(target_config,
+            graph,
+            [](HGraph* graph_arg) { RemoveSuspendChecks(graph_arg); },
+            has_result, expected);
+  }
+}
+
+TEST_F(SchedulerTest, RandomScheduling) {
+  //
+  // Java source: crafted code to make sure (random) scheduling should get correct result.
+  //
+  //  int result = 0;
+  //  float fr = 10.0f;
+  //  for (int i = 1; i < 10; i++) {
+  //    fr ++;
+  //    int t1 = result >> i;
+  //    int t2 = result * i;
+  //    result = result + t1 - t2;
+  //    fr = fr / i;
+  //    result += (int)fr;
+  //  }
+  //  return result;
+  //
+  const uint16_t data[] = SIX_REGISTERS_CODE_ITEM(
+    Instruction::CONST_4 | 0 << 12 | 2 << 8,          // const/4 v2, #int 0
+    Instruction::CONST_HIGH16 | 0 << 8, 0x4120,       // const/high16 v0, #float 10.0 // #41200000
+    Instruction::CONST_4 | 1 << 12 | 1 << 8,          // const/4 v1, #int 1
+    Instruction::CONST_16 | 5 << 8, 0x000a,           // const/16 v5, #int 10
+    Instruction::IF_GE | 5 << 12 | 1 << 8, 0x0014,    // if-ge v1, v5, 001a // +0014
+    Instruction::CONST_HIGH16 | 5 << 8, 0x3f80,       // const/high16 v5, #float 1.0 // #3f800000
+    Instruction::ADD_FLOAT_2ADDR | 5 << 12 | 0 << 8,  // add-float/2addr v0, v5
+    Instruction::SHR_INT | 3 << 8, 1 << 8 | 2 ,       // shr-int v3, v2, v1
+    Instruction::MUL_INT | 4 << 8, 1 << 8 | 2,        // mul-int v4, v2, v1
+    Instruction::ADD_INT | 5 << 8, 3 << 8 | 2,        // add-int v5, v2, v3
+    Instruction::SUB_INT | 2 << 8, 4 << 8 | 5,        // sub-int v2, v5, v4
+    Instruction::INT_TO_FLOAT | 1 << 12 | 5 << 8,     // int-to-float v5, v1
+    Instruction::DIV_FLOAT_2ADDR | 5 << 12 | 0 << 8,  // div-float/2addr v0, v5
+    Instruction::FLOAT_TO_INT | 0 << 12 | 5 << 8,     // float-to-int v5, v0
+    Instruction::ADD_INT_2ADDR | 5 << 12 | 2 << 8,    // add-int/2addr v2, v5
+    Instruction::ADD_INT_LIT8 | 1 << 8, 1 << 8 | 1,   // add-int/lit8 v1, v1, #int 1 // #01
+    Instruction::GOTO | 0xeb << 8,                    // goto 0004 // -0015
+    Instruction::RETURN | 2 << 8);                    // return v2
+
+  constexpr int kNumberOfRuns = 10;
+  for (int i = 0; i < kNumberOfRuns; ++i) {
+    CompileWithRandomSchedulerAndRun(data, true, 138774);
+  }
+}
+
+}  // namespace art