Disambiguate memory accesses in instruction scheduling

Based on aliasing information from heap location collector,
instruction scheduling can further eliminate side-effect
dependencies between memory accesses to different locations,
and perform better scheduling on memory loads and stores.

Performance improvements of this CL, measured on Cortex-A53:
| benchmarks     | ARM64 backend | ARM backend |
|----------------+---------------|-------------|
| algorithm      |         0.1 % |       0.1 % |
| benchmarksgame |         0.5 % |       1.3 % |
| caffeinemark   |         0.0 % |       0.0 % |
| math           |         5.1 % |       5.0 % |
| stanford       |         1.1 % |       0.6 % |
| testsimd       |         0.4 % |       0.1 % |

Compilation time impact is negligible, because this
heap location load store analysis is only performed
on loop basic blocks that get instruction scheduled.

Test: m test-art-host
Test: m test-art-target
Test: 706-checker-scheduler

Change-Id: I43d7003c09bfab9d3a1814715df666aea9a7360b

1 files changed, 17 insertions, 3 deletions

diff --git a/compiler/optimizing/scheduler.h b/compiler/optimizing/scheduler.h
index 73e8087cd0..930a2c82cf 100644
--- a/compiler/optimizing/scheduler.h
+++ b/compiler/optimizing/scheduler.h
@@ -21,6 +21,7 @@
 
 #include "base/time_utils.h"
 #include "driver/compiler_driver.h"
+#include "load_store_analysis.h"
 #include "nodes.h"
 #include "optimization.h"
 #include "code_generator.h"
@@ -246,7 +247,8 @@ class SchedulingGraph : public ValueObject {
       : scheduler_(scheduler),
         arena_(arena),
         contains_scheduling_barrier_(false),
-        nodes_map_(arena_->Adapter(kArenaAllocScheduler)) {}
+        nodes_map_(arena_->Adapter(kArenaAllocScheduler)),
+        heap_location_collector_(nullptr) {}
 
   SchedulingNode* AddNode(HInstruction* instr, bool is_scheduling_barrier = false) {
     SchedulingNode* node = new (arena_) SchedulingNode(instr, arena_, is_scheduling_barrier);
@@ -261,6 +263,10 @@ class SchedulingGraph : public ValueObject {
     contains_scheduling_barrier_ = false;
   }
 
+  void SetHeapLocationCollector(const HeapLocationCollector& heap_location_collector) {
+    heap_location_collector_ = &heap_location_collector;
+  }
+
   SchedulingNode* GetNode(const HInstruction* instr) const {
     auto it = nodes_map_.Find(instr);
     if (it == nodes_map_.end()) {
@@ -294,6 +300,13 @@ class SchedulingGraph : public ValueObject {
   void AddOtherDependency(SchedulingNode* node, SchedulingNode* dependency) {
     AddDependency(node, dependency, /*is_data_dependency*/false);
   }
+  bool HasMemoryDependency(const HInstruction* node, const HInstruction* other) const;
+  bool HasExceptionDependency(const HInstruction* node, const HInstruction* other) const;
+  bool HasSideEffectDependency(const HInstruction* node, const HInstruction* other) const;
+  bool ArrayAccessMayAlias(const HInstruction* node, const HInstruction* other) const;
+  bool FieldAccessMayAlias(const HInstruction* node, const HInstruction* other) const;
+  size_t ArrayAccessHeapLocation(HInstruction* array, HInstruction* index) 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);
@@ -305,6 +318,8 @@ class SchedulingGraph : public ValueObject {
   bool contains_scheduling_barrier_;
 
   ArenaHashMap<const HInstruction*, SchedulingNode*> nodes_map_;
+
+  const HeapLocationCollector* heap_location_collector_;
 };
 
 /*
@@ -482,10 +497,9 @@ class HInstructionScheduling : public HOptimization {
 
   static constexpr const char* kInstructionScheduling = "scheduler";
 
+ private:
   CodeGenerator* const codegen_;
   const InstructionSet instruction_set_;
-
- private:
   DISALLOW_COPY_AND_ASSIGN(HInstructionScheduling);
 };