ART: Refactor SchedulingGraph for consistency and clarity

The CL moves functionality from SchedulingGraph to other classes,
deletes unused code and moves code used for testing to the tests source
file:
1. SchedulingGraph::AddDependency: move checks whether a dependency has
been added to SchedulingNode::Add*Predecessor as it is a SchedulingNode
responsibility to keep a unique set of predecessors.
2. Create SideEffectDependencyAnalysis class. Code doing side effect dependency
analysis is moved from SchedulingGraph into the class.
3. Remove SchedulingGraph::HasImmediate*Dependency methods as there are
SchedulingNode::Has*Dependency methods for such kind of checks.
4. SchedulingGraph::HasImmediate*Dependency(HInstruction,HInstruction) methods
are only used by tests. Their code is moved to a new class TestSchedulingGraph in
the tests source file.

Test: test.py --host --optimizing --jit --gtest
Test: test.py --target --optimizing --jit
Test: run-gtests.sh

Change-Id: Id16eb6e9f8b9706e616dff0ccc1d0353ed968367

3 files changed, 172 insertions, 148 deletions

diff --git a/compiler/optimizing/scheduler.cc b/compiler/optimizing/scheduler.cc
index fdef45ec8b..e5ff8a886a 100644
--- a/compiler/optimizing/scheduler.cc
+++ b/compiler/optimizing/scheduler.cc
@@ -43,34 +43,37 @@ void SchedulingGraph::AddDependency(SchedulingNode* node,
   }
 
   if (is_data_dependency) {
-    if (!HasImmediateDataDependency(node, dependency)) {
-      node->AddDataPredecessor(dependency);
-    }
-  } else if (!HasImmediateOtherDependency(node, dependency)) {
+    node->AddDataPredecessor(dependency);
+  } else {
     node->AddOtherPredecessor(dependency);
   }
 }
 
-static bool MayHaveReorderingDependency(SideEffects node, SideEffects other) {
+bool SideEffectDependencyAnalysis::HasReorderingDependency(const HInstruction* instr1,
+                                                           const HInstruction* instr2) {
+  SideEffects instr1_side_effects = instr1->GetSideEffects();
+  SideEffects instr2_side_effects = instr2->GetSideEffects();
+
   // Read after write.
-  if (node.MayDependOn(other)) {
+  if (instr1_side_effects.MayDependOn(instr2_side_effects)) {
     return true;
   }
 
   // Write after read.
-  if (other.MayDependOn(node)) {
+  if (instr2_side_effects.MayDependOn(instr1_side_effects)) {
     return true;
   }
 
   // Memory write after write.
-  if (node.DoesAnyWrite() && other.DoesAnyWrite()) {
+  if (instr1_side_effects.DoesAnyWrite() && instr2_side_effects.DoesAnyWrite()) {
     return true;
   }
 
   return false;
 }
 
-size_t SchedulingGraph::ArrayAccessHeapLocation(HInstruction* instruction) const {
+size_t SideEffectDependencyAnalysis::MemoryDependencyAnalysis::ArrayAccessHeapLocation(
+    HInstruction* instruction) const {
   DCHECK(heap_location_collector_ != nullptr);
   size_t heap_loc = heap_location_collector_->GetArrayHeapLocation(instruction);
   // This array access should be analyzed and added to HeapLocationCollector before.
@@ -78,19 +81,19 @@ size_t SchedulingGraph::ArrayAccessHeapLocation(HInstruction* instruction) const
   return heap_loc;
 }
 
-bool SchedulingGraph::ArrayAccessMayAlias(HInstruction* node,
-                                          HInstruction* other) const {
+bool SideEffectDependencyAnalysis::MemoryDependencyAnalysis::ArrayAccessMayAlias(
+    HInstruction* instr1, HInstruction* instr2) const {
   DCHECK(heap_location_collector_ != nullptr);
-  size_t node_heap_loc = ArrayAccessHeapLocation(node);
-  size_t other_heap_loc = ArrayAccessHeapLocation(other);
+  size_t instr1_heap_loc = ArrayAccessHeapLocation(instr1);
+  size_t instr2_heap_loc = ArrayAccessHeapLocation(instr2);
 
   // For example: arr[0] and arr[0]
-  if (node_heap_loc == other_heap_loc) {
+  if (instr1_heap_loc == instr2_heap_loc) {
     return true;
   }
 
   // For example: arr[0] and arr[i]
-  if (heap_location_collector_->MayAlias(node_heap_loc, other_heap_loc)) {
+  if (heap_location_collector_->MayAlias(instr1_heap_loc, instr2_heap_loc)) {
     return true;
   }
 
@@ -148,55 +151,55 @@ static const FieldInfo* GetFieldInfo(const HInstruction* instruction) {
   }
 }
 
-size_t SchedulingGraph::FieldAccessHeapLocation(HInstruction* obj, const FieldInfo* field) const {
-  DCHECK(obj != nullptr);
-  DCHECK(field != nullptr);
+size_t SideEffectDependencyAnalysis::MemoryDependencyAnalysis::FieldAccessHeapLocation(
+    const HInstruction* instr) const {
+  DCHECK(instr != nullptr);
+  DCHECK(GetFieldInfo(instr) != nullptr);
   DCHECK(heap_location_collector_ != nullptr);
 
-  size_t heap_loc = heap_location_collector_->GetFieldHeapLocation(obj, field);
+  size_t heap_loc = heap_location_collector_->GetFieldHeapLocation(instr->InputAt(0),
+                                                                   GetFieldInfo(instr));
   // This field access should be analyzed and added to HeapLocationCollector before.
   DCHECK(heap_loc != HeapLocationCollector::kHeapLocationNotFound);
 
   return heap_loc;
 }
 
-bool SchedulingGraph::FieldAccessMayAlias(const HInstruction* node,
-                                          const HInstruction* other) const {
+bool SideEffectDependencyAnalysis::MemoryDependencyAnalysis::FieldAccessMayAlias(
+    const HInstruction* instr1, const HInstruction* instr2) const {
   DCHECK(heap_location_collector_ != nullptr);
 
   // Static and instance field accesses should not alias.
-  if ((IsInstanceFieldAccess(node) && IsStaticFieldAccess(other)) ||
-      (IsStaticFieldAccess(node) && IsInstanceFieldAccess(other))) {
+  if ((IsInstanceFieldAccess(instr1) && IsStaticFieldAccess(instr2)) ||
+      (IsStaticFieldAccess(instr1) && IsInstanceFieldAccess(instr2))) {
     return false;
   }
 
   // If either of the field accesses is unresolved.
-  if (IsUnresolvedFieldAccess(node) || IsUnresolvedFieldAccess(other)) {
+  if (IsUnresolvedFieldAccess(instr1) || IsUnresolvedFieldAccess(instr2)) {
     // Conservatively treat these two accesses may alias.
     return true;
   }
 
   // If both fields accesses are resolved.
-  const FieldInfo* node_field = GetFieldInfo(node);
-  const FieldInfo* other_field = GetFieldInfo(other);
-
-  size_t node_loc = FieldAccessHeapLocation(node->InputAt(0), node_field);
-  size_t other_loc = FieldAccessHeapLocation(other->InputAt(0), other_field);
+  size_t instr1_field_access_heap_loc = FieldAccessHeapLocation(instr1);
+  size_t instr2_field_access_heap_loc = FieldAccessHeapLocation(instr2);
 
-  if (node_loc == other_loc) {
+  if (instr1_field_access_heap_loc == instr2_field_access_heap_loc) {
     return true;
   }
 
-  if (!heap_location_collector_->MayAlias(node_loc, other_loc)) {
+  if (!heap_location_collector_->MayAlias(instr1_field_access_heap_loc,
+                                          instr2_field_access_heap_loc)) {
     return false;
   }
 
   return true;
 }
 
-bool SchedulingGraph::HasMemoryDependency(HInstruction* node,
-                                          HInstruction* other) const {
-  if (!MayHaveReorderingDependency(node->GetSideEffects(), other->GetSideEffects())) {
+bool SideEffectDependencyAnalysis::MemoryDependencyAnalysis::HasMemoryDependency(
+    HInstruction* instr1, HInstruction* instr2) const {
+  if (!HasReorderingDependency(instr1, instr2)) {
     return false;
   }
 
@@ -208,35 +211,35 @@ bool SchedulingGraph::HasMemoryDependency(HInstruction* node,
     return true;
   }
 
-  if (IsArrayAccess(node) && IsArrayAccess(other)) {
-    return ArrayAccessMayAlias(node, other);
+  if (IsArrayAccess(instr1) && IsArrayAccess(instr2)) {
+    return ArrayAccessMayAlias(instr1, instr2);
   }
-  if (IsFieldAccess(node) && IsFieldAccess(other)) {
-    return FieldAccessMayAlias(node, other);
+  if (IsFieldAccess(instr1) && IsFieldAccess(instr2)) {
+    return FieldAccessMayAlias(instr1, instr2);
   }
 
   // TODO(xueliang): LSA to support alias analysis among HVecLoad, HVecStore and ArrayAccess
-  if (node->IsVecMemoryOperation() && other->IsVecMemoryOperation()) {
+  if (instr1->IsVecMemoryOperation() && instr2->IsVecMemoryOperation()) {
     return true;
   }
-  if (node->IsVecMemoryOperation() && IsArrayAccess(other)) {
+  if (instr1->IsVecMemoryOperation() && IsArrayAccess(instr2)) {
     return true;
   }
-  if (IsArrayAccess(node) && other->IsVecMemoryOperation()) {
+  if (IsArrayAccess(instr1) && instr2->IsVecMemoryOperation()) {
     return true;
   }
 
   // Heap accesses of different kinds should not alias.
-  if (IsArrayAccess(node) && IsFieldAccess(other)) {
+  if (IsArrayAccess(instr1) && IsFieldAccess(instr2)) {
     return false;
   }
-  if (IsFieldAccess(node) && IsArrayAccess(other)) {
+  if (IsFieldAccess(instr1) && IsArrayAccess(instr2)) {
     return false;
   }
-  if (node->IsVecMemoryOperation() && IsFieldAccess(other)) {
+  if (instr1->IsVecMemoryOperation() && IsFieldAccess(instr2)) {
     return false;
   }
-  if (IsFieldAccess(node) && other->IsVecMemoryOperation()) {
+  if (IsFieldAccess(instr1) && instr2->IsVecMemoryOperation()) {
     return false;
   }
 
@@ -245,15 +248,15 @@ bool SchedulingGraph::HasMemoryDependency(HInstruction* node,
   return true;
 }
 
-bool SchedulingGraph::HasExceptionDependency(const HInstruction* node,
-                                             const HInstruction* other) const {
-  if (other->CanThrow() && node->GetSideEffects().DoesAnyWrite()) {
+bool SideEffectDependencyAnalysis::HasExceptionDependency(const HInstruction* instr1,
+                                                          const HInstruction* instr2) {
+  if (instr2->CanThrow() && instr1->GetSideEffects().DoesAnyWrite()) {
     return true;
   }
-  if (other->GetSideEffects().DoesAnyWrite() && node->CanThrow()) {
+  if (instr2->GetSideEffects().DoesAnyWrite() && instr1->CanThrow()) {
     return true;
   }
-  if (other->CanThrow() && node->CanThrow()) {
+  if (instr2->CanThrow() && instr1->CanThrow()) {
     return true;
   }
 
@@ -262,24 +265,6 @@ bool SchedulingGraph::HasExceptionDependency(const HInstruction* node,
   return false;
 }
 
-// Check whether `node` depends on `other`, taking into account `SideEffect`
-// information and `CanThrow` information.
-bool SchedulingGraph::HasSideEffectDependency(HInstruction* node,
-                                              HInstruction* other) const {
-  if (HasMemoryDependency(node, other)) {
-    return true;
-  }
-
-  // Even if above memory dependency check has passed, it is still necessary to
-  // check dependencies between instructions that can throw and instructions
-  // that write to memory.
-  if (HasExceptionDependency(node, other)) {
-    return true;
-  }
-
-  return false;
-}
-
 // Check if the specified instruction is a better candidate which more likely will
 // have other instructions depending on it.
 static bool IsBetterCandidateWithMoreLikelyDependencies(HInstruction* new_candidate,
@@ -297,8 +282,9 @@ static bool IsBetterCandidateWithMoreLikelyDependencies(HInstruction* new_candid
   }
 }
 
-void SchedulingGraph::AddDependencies(HInstruction* instruction, bool is_scheduling_barrier) {
-  SchedulingNode* instruction_node = GetNode(instruction);
+void SchedulingGraph::AddDependencies(SchedulingNode* instruction_node,
+                                      bool is_scheduling_barrier) {
+  HInstruction* instruction = instruction_node->GetInstruction();
 
   // Define-use dependencies.
   for (const HUseListNode<HInstruction*>& use : instruction->GetUses()) {
@@ -354,12 +340,12 @@ void SchedulingGraph::AddDependencies(HInstruction* instruction, bool is_schedul
       if (other_node->IsSchedulingBarrier()) {
         // We have reached a scheduling barrier so we can stop further
         // processing.
-        DCHECK(HasImmediateOtherDependency(other_node, instruction_node));
+        DCHECK(other_node->HasOtherDependency(instruction_node));
         break;
       }
-      if (HasSideEffectDependency(other, instruction)) {
+      if (side_effect_dependency_analysis_.HasSideEffectDependency(other, instruction)) {
         if (dep_chain_candidate != nullptr &&
-            HasSideEffectDependency(other, dep_chain_candidate)) {
+            side_effect_dependency_analysis_.HasSideEffectDependency(other, dep_chain_candidate)) {
           // Skip an explicit dependency to reduce memory usage, rely on the transitive dependency.
         } else {
           AddOtherDependency(other_node, instruction_node);
@@ -388,44 +374,6 @@ void SchedulingGraph::AddDependencies(HInstruction* instruction, bool is_schedul
   }
 }
 
-bool SchedulingGraph::HasImmediateDataDependency(const SchedulingNode* node,
-                                                 const SchedulingNode* other) const {
-  return ContainsElement(node->GetDataPredecessors(), other);
-}
-
-bool SchedulingGraph::HasImmediateDataDependency(const HInstruction* instruction,
-                                                 const HInstruction* other_instruction) const {
-  const SchedulingNode* node = GetNode(instruction);
-  const SchedulingNode* other = GetNode(other_instruction);
-  if (node == nullptr || other == nullptr) {
-    // Both instructions must be in current basic block, i.e. the SchedulingGraph can see their
-    // corresponding SchedulingNode in the graph, and tell whether there is a dependency.
-    // Otherwise there is no dependency from SchedulingGraph's perspective, for example,
-    // instruction and other_instruction are in different basic blocks.
-    return false;
-  }
-  return HasImmediateDataDependency(node, other);
-}
-
-bool SchedulingGraph::HasImmediateOtherDependency(const SchedulingNode* node,
-                                                  const SchedulingNode* other) const {
-  return ContainsElement(node->GetOtherPredecessors(), other);
-}
-
-bool SchedulingGraph::HasImmediateOtherDependency(const HInstruction* instruction,
-                                                  const HInstruction* other_instruction) const {
-  const SchedulingNode* node = GetNode(instruction);
-  const SchedulingNode* other = GetNode(other_instruction);
-  if (node == nullptr || other == nullptr) {
-    // Both instructions must be in current basic block, i.e. the SchedulingGraph can see their
-    // corresponding SchedulingNode in the graph, and tell whether there is a dependency.
-    // Otherwise there is no dependency from SchedulingGraph's perspective, for example,
-    // instruction and other_instruction are in different basic blocks.
-    return false;
-  }
-  return HasImmediateOtherDependency(node, other);
-}
-
 static const std::string InstructionTypeId(const HInstruction* instruction) {
   return DataType::TypeId(instruction->GetType()) + std::to_string(instruction->GetId());
 }
@@ -594,7 +542,7 @@ void HScheduler::Schedule(HBasicBlock* block,
   ScopedArenaVector<SchedulingNode*> scheduling_nodes(allocator.Adapter(kArenaAllocScheduler));
 
   // Build the scheduling graph.
-  SchedulingGraph scheduling_graph(this, &allocator, heap_location_collector);
+  SchedulingGraph scheduling_graph(&allocator, heap_location_collector);
   for (HBackwardInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) {
     HInstruction* instruction = it.Current();
     CHECK_EQ(instruction->GetBlock(), block)
diff --git a/compiler/optimizing/scheduler.h b/compiler/optimizing/scheduler.h
index d2dbeca924..a97eda7e85 100644
--- a/compiler/optimizing/scheduler.h
+++ b/compiler/optimizing/scheduler.h
@@ -21,6 +21,7 @@
 
 #include "base/scoped_arena_allocator.h"
 #include "base/scoped_arena_containers.h"
+#include "base/stl_util.h"
 #include "base/time_utils.h"
 #include "code_generator.h"
 #include "load_store_analysis.h"
@@ -168,6 +169,10 @@ class SchedulingNode : public DeletableArenaObject<kArenaAllocScheduler> {
   }
 
   void AddDataPredecessor(SchedulingNode* predecessor) {
+    // Check whether the predecessor has been added earlier.
+    if (HasDataDependency(predecessor)) {
+      return;
+    }
     data_predecessors_.push_back(predecessor);
     predecessor->num_unscheduled_successors_++;
   }
@@ -177,6 +182,10 @@ class SchedulingNode : public DeletableArenaObject<kArenaAllocScheduler> {
   }
 
   void AddOtherPredecessor(SchedulingNode* predecessor) {
+    // Check whether the predecessor has been added earlier.
+    if (HasOtherDependency(predecessor)) {
+      return;
+    }
     other_predecessors_.push_back(predecessor);
     predecessor->num_unscheduled_successors_++;
   }
@@ -205,6 +214,14 @@ class SchedulingNode : public DeletableArenaObject<kArenaAllocScheduler> {
   uint32_t GetCriticalPath() const { return critical_path_; }
   bool IsSchedulingBarrier() const { return is_scheduling_barrier_; }
 
+  bool HasDataDependency(const SchedulingNode* node) const {
+    return ContainsElement(data_predecessors_, node);
+  }
+
+  bool HasOtherDependency(const SchedulingNode* node) const {
+    return ContainsElement(other_predecessors_, node);
+  }
+
  private:
   // The latency of this node. It represents the latency between the moment the
   // last instruction for this node has executed to the moment the result
@@ -246,18 +263,67 @@ class SchedulingNode : public DeletableArenaObject<kArenaAllocScheduler> {
 };
 
 /*
+ * Provide analysis of instruction dependencies (side effects) which are not in a form of explicit
+ * def-use data dependencies.
+ */
+class SideEffectDependencyAnalysis {
+ public:
+  explicit SideEffectDependencyAnalysis(const HeapLocationCollector* heap_location_collector)
+      : memory_dependency_analysis_(heap_location_collector) {}
+
+  bool HasSideEffectDependency(HInstruction* instr1, HInstruction* instr2) const {
+    if (memory_dependency_analysis_.HasMemoryDependency(instr1, instr2)) {
+      return true;
+    }
+
+    // Even if above memory dependency check has passed, it is still necessary to
+    // check dependencies between instructions that can throw and instructions
+    // that write to memory.
+    if (HasExceptionDependency(instr1, instr2)) {
+      return true;
+    }
+
+    return false;
+  }
+
+ private:
+  static bool HasExceptionDependency(const HInstruction* instr1, const HInstruction* instr2);
+  static bool HasReorderingDependency(const HInstruction* instr1, const HInstruction* instr2);
+
+  /*
+   * Memory dependency analysis of instructions based on their memory side effects
+   * and heap location information from the LCA pass if it is provided.
+   */
+  class MemoryDependencyAnalysis {
+   public:
+    explicit MemoryDependencyAnalysis(const HeapLocationCollector* heap_location_collector)
+        : heap_location_collector_(heap_location_collector) {}
+
+    bool HasMemoryDependency(HInstruction* instr1, HInstruction* instr2) const;
+
+   private:
+    bool ArrayAccessMayAlias(HInstruction* instr1, HInstruction* instr2) const;
+    bool FieldAccessMayAlias(const HInstruction* instr1, const HInstruction* instr2) const;
+    size_t ArrayAccessHeapLocation(HInstruction* instruction) const;
+    size_t FieldAccessHeapLocation(const HInstruction* instruction) const;
+
+    const HeapLocationCollector* const heap_location_collector_;
+  };
+
+  MemoryDependencyAnalysis memory_dependency_analysis_;
+};
+
+/*
  * Directed acyclic graph for scheduling.
  */
 class SchedulingGraph : public ValueObject {
  public:
-  SchedulingGraph(const HScheduler* scheduler,
-                  ScopedArenaAllocator* allocator,
+  SchedulingGraph(ScopedArenaAllocator* allocator,
                   const HeapLocationCollector* heap_location_collector)
-      : scheduler_(scheduler),
-        allocator_(allocator),
+      : allocator_(allocator),
         contains_scheduling_barrier_(false),
         nodes_map_(allocator_->Adapter(kArenaAllocScheduler)),
-        heap_location_collector_(heap_location_collector) {}
+        side_effect_dependency_analysis_(heap_location_collector) {}
 
   SchedulingNode* AddNode(HInstruction* instr, bool is_scheduling_barrier = false) {
     std::unique_ptr<SchedulingNode> node(
@@ -265,7 +331,7 @@ class SchedulingGraph : public ValueObject {
     SchedulingNode* result = node.get();
     nodes_map_.insert(std::make_pair(instr, std::move(node)));
     contains_scheduling_barrier_ |= is_scheduling_barrier;
-    AddDependencies(instr, is_scheduling_barrier);
+    AddDependencies(result, is_scheduling_barrier);
     return result;
   }
 
@@ -278,13 +344,6 @@ class SchedulingGraph : public ValueObject {
     }
   }
 
-  bool IsSchedulingBarrier(const HInstruction* instruction) const;
-
-  bool HasImmediateDataDependency(const SchedulingNode* node, const SchedulingNode* other) const;
-  bool HasImmediateDataDependency(const HInstruction* node, const HInstruction* other) const;
-  bool HasImmediateOtherDependency(const SchedulingNode* node, const SchedulingNode* other) const;
-  bool HasImmediateOtherDependency(const HInstruction* node, const HInstruction* other) const;
-
   size_t Size() const {
     return nodes_map_.size();
   }
@@ -302,26 +361,14 @@ class SchedulingGraph : public ValueObject {
   void AddOtherDependency(SchedulingNode* node, SchedulingNode* dependency) {
     AddDependency(node, dependency, /*is_data_dependency*/false);
   }
-  bool HasMemoryDependency(HInstruction* node, HInstruction* other) const;
-  bool HasExceptionDependency(const HInstruction* node, const HInstruction* other) const;
-  bool HasSideEffectDependency(HInstruction* node, HInstruction* other) const;
-  bool ArrayAccessMayAlias(HInstruction* node, HInstruction* other) const;
-  bool FieldAccessMayAlias(const HInstruction* node, const HInstruction* other) const;
-  size_t ArrayAccessHeapLocation(HInstruction* instruction) const;
-  size_t FieldAccessHeapLocation(HInstruction* obj, const FieldInfo* field) const;
-
-  // Add dependencies nodes for the given `HInstruction`: inputs, environments, and side-effects.
-  void AddDependencies(HInstruction* instruction, bool is_scheduling_barrier = false);
 
-  const HScheduler* const scheduler_;
+  // Add dependencies nodes for the given `SchedulingNode`: inputs, environments, and side-effects.
+  void AddDependencies(SchedulingNode* node, bool is_scheduling_barrier = false);
 
   ScopedArenaAllocator* const allocator_;
-
   bool contains_scheduling_barrier_;
-
   ScopedArenaHashMap<const HInstruction*, std::unique_ptr<SchedulingNode>> nodes_map_;
-
-  const HeapLocationCollector* const heap_location_collector_;
+  SideEffectDependencyAnalysis side_effect_dependency_analysis_;
 };
 
 /*
@@ -477,10 +524,6 @@ class HScheduler {
   DISALLOW_COPY_AND_ASSIGN(HScheduler);
 };
 
-inline bool SchedulingGraph::IsSchedulingBarrier(const HInstruction* instruction) const {
-  return scheduler_->IsSchedulingBarrier(instruction);
-}
-
 class HInstructionScheduling : public HOptimization {
  public:
   HInstructionScheduling(HGraph* graph,
diff --git a/compiler/optimizing/scheduler_test.cc b/compiler/optimizing/scheduler_test.cc
index e0e265a04c..4c47f2ee57 100644
--- a/compiler/optimizing/scheduler_test.cc
+++ b/compiler/optimizing/scheduler_test.cc
@@ -146,9 +146,7 @@ class SchedulerTest : public OptimizingUnitTest {
     environment->SetRawEnvAt(1, mul);
     mul->AddEnvUseAt(div_check->GetEnvironment(), 1);
 
-    SchedulingGraph scheduling_graph(scheduler,
-                                     GetScopedAllocator(),
-                                     /* heap_location_collector= */ nullptr);
+    TestSchedulingGraph scheduling_graph(GetScopedAllocator());
     // Instructions must be inserted in reverse order into the scheduling graph.
     for (HInstruction* instr : ReverseRange(block_instructions)) {
       scheduling_graph.AddNode(instr);
@@ -283,7 +281,7 @@ class SchedulerTest : public OptimizingUnitTest {
     HeapLocationCollector heap_location_collector(graph_);
     heap_location_collector.VisitBasicBlock(entry);
     heap_location_collector.BuildAliasingMatrix();
-    SchedulingGraph scheduling_graph(scheduler, GetScopedAllocator(), &heap_location_collector);
+    TestSchedulingGraph scheduling_graph(GetScopedAllocator(), &heap_location_collector);
 
     for (HInstruction* instr : ReverseRange(block_instructions)) {
       // Build scheduling graph with memory access aliasing information
@@ -357,6 +355,41 @@ class SchedulerTest : public OptimizingUnitTest {
     scheduler->Schedule(graph_);
   }
 
+  class TestSchedulingGraph : public SchedulingGraph {
+   public:
+    explicit TestSchedulingGraph(ScopedArenaAllocator* allocator,
+                                 const HeapLocationCollector *heap_location_collector = nullptr)
+        : SchedulingGraph(allocator, heap_location_collector) {}
+
+    bool HasImmediateDataDependency(const HInstruction* instruction,
+                                    const HInstruction* other_instruction) const {
+      const SchedulingNode* node = GetNode(instruction);
+      const SchedulingNode* other = GetNode(other_instruction);
+      if (node == nullptr || other == nullptr) {
+        // Both instructions must be in current basic block, i.e. the SchedulingGraph can see their
+        // corresponding SchedulingNode in the graph, and tell whether there is a dependency.
+        // Otherwise there is no dependency from SchedulingGraph's perspective, for example,
+        // instruction and other_instruction are in different basic blocks.
+        return false;
+      }
+      return node->HasDataDependency(other);
+    }
+
+    bool HasImmediateOtherDependency(const HInstruction* instruction,
+                                     const HInstruction* other_instruction) const {
+      const SchedulingNode* node = GetNode(instruction);
+      const SchedulingNode* other = GetNode(other_instruction);
+      if (node == nullptr || other == nullptr) {
+        // Both instructions must be in current basic block, i.e. the SchedulingGraph can see their
+        // corresponding SchedulingNode in the graph, and tell whether there is a dependency.
+        // Otherwise there is no dependency from SchedulingGraph's perspective, for example,
+        // instruction and other_instruction are in different basic blocks.
+        return false;
+      }
+      return node->HasOtherDependency(other);
+    }
+  };
+
   HGraph* graph_;
 };