Reduce memory usage by other deps in scheduler.

Rely on transitive dependencies instead of adding the full
set of side effect dependencies.

Compiling a certain apk, the most memory hungry method has
the scheduler memory allocations in ArenaStack hidden by
the register allocator:
  - before:
    MEM: used: 155744672, allocated: 168446408, lost: 12036488
    Scheduler     155744672
  - after:
    MEM: used: 5181680, allocated: 7096776, lost: 114752
    SsaLiveness     4683440
    RegAllocator     314312
    RegAllocVldt     183928
The total arena memory used, including the ArenaAllocator
not listed above, goes from 167170024 to 16607032 (-90%).
(Measured with kArenaAllocatorCountAllocations=true,
kArenaAllocatorPreciseTracking=false.)

Test: m test-art-host-gtest
Test: testrunner.py --host --optimizing
Bug: 64312607
Change-Id: I825bcfb490171070c46ad6d1f460785f4e75cfd7

2 files changed, 43 insertions, 6 deletions

diff --git a/compiler/optimizing/scheduler.cc b/compiler/optimizing/scheduler.cc
index 1aa16f45bc..df897a4904 100644
--- a/compiler/optimizing/scheduler.cc
+++ b/compiler/optimizing/scheduler.cc
@@ -280,6 +280,23 @@ bool SchedulingGraph::HasSideEffectDependency(HInstruction* node,
   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,
+                                                        HInstruction* old_candidate) {
+  if (!new_candidate->GetSideEffects().Includes(old_candidate->GetSideEffects())) {
+    // Weaker side effects.
+    return false;
+  }
+  if (old_candidate->GetSideEffects().Includes(new_candidate->GetSideEffects())) {
+    // Same side effects, check if `new_candidate` has stronger `CanThrow()`.
+    return new_candidate->CanThrow() && !old_candidate->CanThrow();
+  } else {
+    // Stronger side effects, check if `new_candidate` has at least as strong `CanThrow()`.
+    return new_candidate->CanThrow() || !old_candidate->CanThrow();
+  }
+}
+
 void SchedulingGraph::AddDependencies(HInstruction* instruction, bool is_scheduling_barrier) {
   SchedulingNode* instruction_node = GetNode(instruction);
 
@@ -331,6 +348,7 @@ void SchedulingGraph::AddDependencies(HInstruction* instruction, bool is_schedul
 
   // Side effect dependencies.
   if (!instruction->GetSideEffects().DoesNothing() || instruction->CanThrow()) {
+    HInstruction* dep_chain_candidate = nullptr;
     for (HInstruction* other = instruction->GetNext(); other != nullptr; other = other->GetNext()) {
       SchedulingNode* other_node = GetNode(other);
       if (other_node->IsSchedulingBarrier()) {
@@ -340,7 +358,18 @@ void SchedulingGraph::AddDependencies(HInstruction* instruction, bool is_schedul
         break;
       }
       if (HasSideEffectDependency(other, instruction)) {
-        AddOtherDependency(other_node, instruction_node);
+        if (dep_chain_candidate != nullptr &&
+            HasSideEffectDependency(other, dep_chain_candidate)) {
+          // Skip an explicit dependency to reduce memory usage, rely on the transitive dependency.
+        } else {
+          AddOtherDependency(other_node, instruction_node);
+        }
+        // Check if `other` is a better candidate which more likely will have other instructions
+        // depending on it.
+        if (dep_chain_candidate == nullptr ||
+            IsBetterCandidateWithMoreLikelyDependencies(other, dep_chain_candidate)) {
+          dep_chain_candidate = other;
+        }
       }
     }
   }
diff --git a/compiler/optimizing/scheduler_test.cc b/compiler/optimizing/scheduler_test.cc
index fe23fb4cff..981fcc42a7 100644
--- a/compiler/optimizing/scheduler_test.cc
+++ b/compiler/optimizing/scheduler_test.cc
@@ -171,7 +171,9 @@ class SchedulerTest : public OptimizingUnitTest {
     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));
+    // Unnecessary dependency is not stored, we rely on transitive dependencies.
+    // The array_set2 -> array_get2 -> array_set1 dependencies are tested above.
+    ASSERT_FALSE(scheduling_graph.HasImmediateOtherDependency(array_set2, array_set1));
 
     // Env dependency.
     ASSERT_TRUE(scheduling_graph.HasImmediateOtherDependency(div_check, mul));
@@ -308,7 +310,9 @@ class SchedulerTest : public OptimizingUnitTest {
     loc1 = heap_location_collector.GetArrayHeapLocation(arr_set_i);
     loc2 = heap_location_collector.GetArrayHeapLocation(arr_set_j);
     ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2));
-    ASSERT_TRUE(scheduling_graph.HasImmediateOtherDependency(arr_set_j, arr_set_i));
+    // Unnecessary dependency is not stored, we rely on transitive dependencies.
+    // The arr_set_j -> arr_set_sub0 -> arr_set_add0 -> arr_set_i dependencies are tested below.
+    ASSERT_FALSE(scheduling_graph.HasImmediateOtherDependency(arr_set_j, arr_set_i));
 
     // Test side effect dependency based on LSA analysis: array[i] and array[i+0]
     loc1 = heap_location_collector.GetArrayHeapLocation(arr_set_i);
@@ -320,7 +324,10 @@ class SchedulerTest : public OptimizingUnitTest {
     loc1 = heap_location_collector.GetArrayHeapLocation(arr_set_i);
     loc2 = heap_location_collector.GetArrayHeapLocation(arr_set_sub0);
     ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2));
-    ASSERT_TRUE(scheduling_graph.HasImmediateOtherDependency(arr_set_sub0, arr_set_i));
+    // Unnecessary dependency is not stored, we rely on transitive dependencies.
+    ASSERT_FALSE(scheduling_graph.HasImmediateOtherDependency(arr_set_sub0, arr_set_i));
+    // Instead, we rely on arr_set_sub0 -> arr_set_add0 -> arr_set_i, the latter is tested above.
+    ASSERT_TRUE(scheduling_graph.HasImmediateOtherDependency(arr_set_sub0, arr_set_add0));
 
     // Test side effect dependency based on LSA analysis: array[i] and array[i+1]
     loc1 = heap_location_collector.GetArrayHeapLocation(arr_set_i);
@@ -335,11 +342,12 @@ class SchedulerTest : public OptimizingUnitTest {
     ASSERT_FALSE(scheduling_graph.HasImmediateOtherDependency(arr_set_sub1, arr_set_add1));
 
     // Test side effect dependency based on LSA analysis: array[j] and all others array accesses
-    ASSERT_TRUE(scheduling_graph.HasImmediateOtherDependency(arr_set_j, arr_set_i));
-    ASSERT_TRUE(scheduling_graph.HasImmediateOtherDependency(arr_set_j, arr_set_add0));
     ASSERT_TRUE(scheduling_graph.HasImmediateOtherDependency(arr_set_j, arr_set_sub0));
     ASSERT_TRUE(scheduling_graph.HasImmediateOtherDependency(arr_set_j, arr_set_add1));
     ASSERT_TRUE(scheduling_graph.HasImmediateOtherDependency(arr_set_j, arr_set_sub1));
+    // Unnecessary dependencies are not stored, we rely on transitive dependencies.
+    ASSERT_FALSE(scheduling_graph.HasImmediateOtherDependency(arr_set_j, arr_set_i));
+    ASSERT_FALSE(scheduling_graph.HasImmediateOtherDependency(arr_set_j, arr_set_add0));
 
     // Test that ArraySet and FieldSet should not have side effect dependency
     ASSERT_FALSE(scheduling_graph.HasImmediateOtherDependency(arr_set_i, set_field10));