From 09d041b214f54e0866516b18b44e44f28d7be70b Mon Sep 17 00:00:00 2001 From: Vladimir Marko Date: Mon, 30 Jul 2018 12:51:59 +0100 Subject: 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 --- compiler/optimizing/scheduler.cc | 31 ++++++++++++++++++++++++++++++- compiler/optimizing/scheduler_test.cc | 18 +++++++++++++----- 2 files changed, 43 insertions(+), 6 deletions(-) (limited to 'compiler') 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)); -- cgit v1.2.3-59-g8ed1b