From 062157f4e07b525728fa58f4ec57ffe1bf15d545 Mon Sep 17 00:00:00 2001 From: Mingyao Yang Date: Wed, 2 Mar 2016 10:15:36 -0800 Subject: [PATCH] Enable allocation elimination as part of LSE After load-store elimination, an allocation may not be used any more and may be eliminated. Change-Id: I7fcaaefa9d6ec2c611e46119c5799293770a917c --- compiler/optimizing/instruction_builder.cc | 8 ++-- compiler/optimizing/load_store_elimination.cc | 23 +++++----- compiler/optimizing/nodes.h | 17 +++---- test/098-ddmc/src/Main.java | 7 ++- test/530-checker-lse/src/Main.java | 65 ++++++++++++++++++++------- 5 files changed, 80 insertions(+), 40 deletions(-) diff --git a/compiler/optimizing/instruction_builder.cc b/compiler/optimizing/instruction_builder.cc index f5e49c223..12cb82639 100644 --- a/compiler/optimizing/instruction_builder.cc +++ b/compiler/optimizing/instruction_builder.cc @@ -897,12 +897,12 @@ bool HInstructionBuilder::BuildNewInstance(uint16_t type_index, uint32_t dex_pc) Handle outer_dex_cache = outer_compilation_unit_->GetDexCache(); bool finalizable; - bool can_throw = NeedsAccessCheck(type_index, dex_cache, &finalizable); + bool needs_access_check = NeedsAccessCheck(type_index, dex_cache, &finalizable); // Only the non-resolved entrypoint handles the finalizable class case. If we // need access checks, then we haven't resolved the method and the class may // again be finalizable. - QuickEntrypointEnum entrypoint = (finalizable || can_throw) + QuickEntrypointEnum entrypoint = (finalizable || needs_access_check) ? kQuickAllocObject : kQuickAllocObjectInitialized; @@ -917,7 +917,7 @@ bool HInstructionBuilder::BuildNewInstance(uint16_t type_index, uint32_t dex_pc) outer_dex_file, IsOutermostCompilingClass(type_index), dex_pc, - /*needs_access_check*/ can_throw, + needs_access_check, compiler_driver_->CanAssumeTypeIsPresentInDexCache(outer_dex_cache, type_index)); AppendInstruction(load_class); @@ -933,7 +933,7 @@ bool HInstructionBuilder::BuildNewInstance(uint16_t type_index, uint32_t dex_pc) dex_pc, type_index, *dex_compilation_unit_->GetDexFile(), - can_throw, + needs_access_check, finalizable, entrypoint)); return true; diff --git a/compiler/optimizing/load_store_elimination.cc b/compiler/optimizing/load_store_elimination.cc index e1977b179..ac7ed86d1 100644 --- a/compiler/optimizing/load_store_elimination.cc +++ b/compiler/optimizing/load_store_elimination.cc @@ -480,7 +480,7 @@ class HeapLocationCollector : public HGraphVisitor { // alias analysis and won't be as effective. bool has_volatile_; // If there are volatile field accesses. bool has_monitor_operations_; // If there are monitor operations. - bool may_deoptimize_; + bool may_deoptimize_; // Only true for HDeoptimize with single-frame deoptimization. DISALLOW_COPY_AND_ASSIGN(HeapLocationCollector); }; @@ -551,19 +551,20 @@ class LSEVisitor : public HGraphVisitor { } // At this point, stores in possibly_removed_stores_ can be safely removed. - size = possibly_removed_stores_.size(); - for (size_t i = 0; i < size; i++) { + for (size_t i = 0, e = possibly_removed_stores_.size(); i < e; i++) { HInstruction* store = possibly_removed_stores_[i]; DCHECK(store->IsInstanceFieldSet() || store->IsStaticFieldSet() || store->IsArraySet()); store->GetBlock()->RemoveInstruction(store); } - // TODO: remove unnecessary allocations. - // Eliminate instructions in singleton_new_instances_ that: - // - don't have uses, - // - don't have finalizers, - // - are instantiable and accessible, - // - have no/separate clinit check. + // Eliminate allocations that are not used. + for (size_t i = 0, e = singleton_new_instances_.size(); i < e; i++) { + HInstruction* new_instance = singleton_new_instances_[i]; + if (!new_instance->HasNonEnvironmentUses()) { + new_instance->RemoveEnvironmentUsers(); + new_instance->GetBlock()->RemoveInstruction(new_instance); + } + } } private: @@ -969,8 +970,8 @@ class LSEVisitor : public HGraphVisitor { if (!heap_location_collector_.MayDeoptimize() && ref_info->IsSingletonAndNotReturned() && !new_instance->IsFinalizable() && - !new_instance->CanThrow()) { - // TODO: add new_instance to singleton_new_instances_ and enable allocation elimination. + !new_instance->NeedsAccessCheck()) { + singleton_new_instances_.push_back(new_instance); } ArenaVector& heap_values = heap_values_for_[new_instance->GetBlock()->GetBlockId()]; diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h index 7fc39cbad..fc9b449f9 100644 --- a/compiler/optimizing/nodes.h +++ b/compiler/optimizing/nodes.h @@ -3652,14 +3652,14 @@ class HNewInstance : public HExpression<2> { uint32_t dex_pc, uint16_t type_index, const DexFile& dex_file, - bool can_throw, + bool needs_access_check, bool finalizable, QuickEntrypointEnum entrypoint) : HExpression(Primitive::kPrimNot, SideEffects::CanTriggerGC(), dex_pc), type_index_(type_index), dex_file_(dex_file), entrypoint_(entrypoint) { - SetPackedFlag(can_throw); + SetPackedFlag(needs_access_check); SetPackedFlag(finalizable); SetRawInputAt(0, cls); SetRawInputAt(1, current_method); @@ -3671,10 +3671,11 @@ class HNewInstance : public HExpression<2> { // Calls runtime so needs an environment. bool NeedsEnvironment() const OVERRIDE { return true; } - // It may throw when called on type that's not instantiable/accessible. - // It can throw OOME. - // TODO: distinguish between the two cases so we can for example allow allocation elimination. - bool CanThrow() const OVERRIDE { return GetPackedFlag() || true; } + // Can throw errors when out-of-memory or if it's not instantiable/accessible. + bool CanThrow() const OVERRIDE { return true; } + + // Needs to call into runtime to make sure it's instantiable/accessible. + bool NeedsAccessCheck() const { return GetPackedFlag(); } bool IsFinalizable() const { return GetPackedFlag(); } @@ -3691,8 +3692,8 @@ class HNewInstance : public HExpression<2> { DECLARE_INSTRUCTION(NewInstance); private: - static constexpr size_t kFlagCanThrow = kNumberOfExpressionPackedBits; - static constexpr size_t kFlagFinalizable = kFlagCanThrow + 1; + static constexpr size_t kFlagNeedsAccessCheck = kNumberOfExpressionPackedBits; + static constexpr size_t kFlagFinalizable = kFlagNeedsAccessCheck + 1; static constexpr size_t kNumberOfNewInstancePackedBits = kFlagFinalizable + 1; static_assert(kNumberOfNewInstancePackedBits <= kMaxNumberOfPackedBits, "Too many packed fields."); diff --git a/test/098-ddmc/src/Main.java b/test/098-ddmc/src/Main.java index f41ff2a94..50bbe5178 100644 --- a/test/098-ddmc/src/Main.java +++ b/test/098-ddmc/src/Main.java @@ -44,7 +44,12 @@ public class Main { System.out.println("Confirm when we overflow, we don't roll over to zero. b/17392248"); final int overflowAllocations = 64 * 1024; // Won't fit in unsigned 16-bit value. for (int i = 0; i < overflowAllocations; i++) { - new Object(); + new Object() { + // Add a finalizer so that the allocation won't be eliminated. + public void finalize() { + System.out.print(""); + } + }; } Allocations after = new Allocations(DdmVmInternal.getRecentAllocations()); System.out.println("before < overflowAllocations=" + (before.numberOfEntries < overflowAllocations)); diff --git a/test/530-checker-lse/src/Main.java b/test/530-checker-lse/src/Main.java index 4d6ea06fe..89875d7fe 100644 --- a/test/530-checker-lse/src/Main.java +++ b/test/530-checker-lse/src/Main.java @@ -70,6 +70,10 @@ class Finalizable { } } +interface Filter { + public boolean isValid(int i); +} + public class Main { /// CHECK-START: double Main.calcCircleArea(double) load_store_elimination (before) @@ -78,7 +82,7 @@ public class Main { /// CHECK: InstanceFieldGet /// CHECK-START: double Main.calcCircleArea(double) load_store_elimination (after) - /// CHECK: NewInstance + /// CHECK-NOT: NewInstance /// CHECK-NOT: InstanceFieldSet /// CHECK-NOT: InstanceFieldGet @@ -124,7 +128,6 @@ public class Main { } /// CHECK-START: int Main.test3(TestClass) load_store_elimination (before) - /// CHECK: NewInstance /// CHECK: StaticFieldGet /// CHECK: NewInstance /// CHECK: InstanceFieldSet @@ -137,7 +140,6 @@ public class Main { /// CHECK: InstanceFieldGet /// CHECK-START: int Main.test3(TestClass) load_store_elimination (after) - /// CHECK: NewInstance /// CHECK: StaticFieldGet /// CHECK: NewInstance /// CHECK: InstanceFieldSet @@ -149,9 +151,6 @@ public class Main { // A new allocation (even non-singleton) shouldn't alias with pre-existing values. static int test3(TestClass obj) { - // Do an allocation here to avoid the HLoadClass and HClinitCheck - // at the second allocation. - new TestClass(); TestClass obj1 = TestClass.sTestClassObj; TestClass obj2 = new TestClass(); // Cannot alias with obj or obj1 which pre-exist. obj.next = obj2; // Make obj2 a non-singleton. @@ -256,7 +255,7 @@ public class Main { /// CHECK: InstanceFieldGet /// CHECK-START: int Main.test8() load_store_elimination (after) - /// CHECK: NewInstance + /// CHECK-NOT: NewInstance /// CHECK-NOT: InstanceFieldSet /// CHECK: InvokeVirtual /// CHECK-NOT: NullCheck @@ -414,7 +413,7 @@ public class Main { /// CHECK: InstanceFieldGet /// CHECK-START: int Main.test16() load_store_elimination (after) - /// CHECK: NewInstance + /// CHECK-NOT: NewInstance /// CHECK-NOT: InstanceFieldSet /// CHECK-NOT: InstanceFieldGet @@ -431,7 +430,7 @@ public class Main { /// CHECK-START: int Main.test17() load_store_elimination (after) /// CHECK: <> IntConstant 0 - /// CHECK: NewInstance + /// CHECK-NOT: NewInstance /// CHECK-NOT: InstanceFieldSet /// CHECK-NOT: InstanceFieldGet /// CHECK: Return [<>] @@ -527,12 +526,12 @@ public class Main { /// CHECK: InstanceFieldGet /// CHECK-START: int Main.test22() load_store_elimination (after) - /// CHECK: NewInstance + /// CHECK-NOT: NewInstance /// CHECK-NOT: InstanceFieldSet - /// CHECK: NewInstance + /// CHECK-NOT: NewInstance /// CHECK-NOT: InstanceFieldSet /// CHECK-NOT: InstanceFieldGet - /// CHECK: NewInstance + /// CHECK-NOT: NewInstance /// CHECK-NOT: InstanceFieldSet /// CHECK-NOT: InstanceFieldGet /// CHECK-NOT: InstanceFieldGet @@ -673,7 +672,7 @@ public class Main { /// CHECK: Select // Test that HSelect creates alias. - public static int $noinline$testHSelect(boolean b) { + static int $noinline$testHSelect(boolean b) { if (sFlag) { throw new Error(); } @@ -686,19 +685,51 @@ public class Main { return obj2.i; } - public static void assertIntEquals(int result, int expected) { + static int sumWithFilter(int[] array, Filter f) { + int sum = 0; + for (int i = 0; i < array.length; i++) { + if (f.isValid(array[i])) { + sum += array[i]; + } + } + return sum; + } + + /// CHECK-START: int Main.sumWithinRange(int[], int, int) load_store_elimination (before) + /// CHECK: NewInstance + /// CHECK: InstanceFieldSet + /// CHECK: InstanceFieldSet + /// CHECK: InstanceFieldGet + /// CHECK: InstanceFieldGet + + /// CHECK-START: int Main.sumWithinRange(int[], int, int) load_store_elimination (after) + /// CHECK-NOT: NewInstance + /// CHECK-NOT: InstanceFieldSet + /// CHECK-NOT: InstanceFieldGet + + // A lambda-style allocation can be eliminated after inlining. + static int sumWithinRange(int[] array, final int low, final int high) { + Filter filter = new Filter() { + public boolean isValid(int i) { + return (i >= low) && (i <= high); + } + }; + return sumWithFilter(array, filter); + } + + static void assertIntEquals(int result, int expected) { if (expected != result) { throw new Error("Expected: " + expected + ", found: " + result); } } - public static void assertFloatEquals(float result, float expected) { + static void assertFloatEquals(float result, float expected) { if (expected != result) { throw new Error("Expected: " + expected + ", found: " + result); } } - public static void assertDoubleEquals(double result, double expected) { + static void assertDoubleEquals(double result, double expected) { if (expected != result) { throw new Error("Expected: " + expected + ", found: " + result); } @@ -746,6 +777,8 @@ public class Main { assertFloatEquals(test24(), 8.0f); testFinalizableByForcingGc(); assertIntEquals($noinline$testHSelect(true), 0xdead); + int[] array = {2, 5, 9, -1, -3, 10, 8, 4}; + assertIntEquals(sumWithinRange(array, 1, 5), 11); } static boolean sFlag; -- 2.11.0