From 65902e86b91f984061657bd8cacf239edb53c39d Mon Sep 17 00:00:00 2001 From: David Brazdil Date: Fri, 15 Jan 2016 09:35:13 +0000 Subject: [PATCH] ART: Optimize out redundant NewInstances of String NewInstance of String creates an empty String object before it is replaced by the result of a StringFactory call (String.). If the empty object is never used prior to the call, it can be safely removed (replaced with null in this case). We do not remove the instruction if: - it has a real use (comparison, instanceof, check-cast), or - we are compiling with --debuggable and there is an environment use. If removed and execution deoptimizes before the StringFactory call, the interpreter will see String. being called on a null object. Since the verifier guarantees that the call was made on new-instance in the input bytecode (b/26579108), the interpreter can safely assume that it was optimized out rather than throw NullPointerException. Results (all without --debuggable): - boot.oat: 563/563 removed - Google Maps: 480/480 removed - Google Docs: 819/819 removed Change-Id: I9fdfc50e9dea6299a7327f94327cdfd2b2538079 --- compiler/optimizing/ssa_builder.cc | 42 +++++++++++++++++++++++- compiler/optimizing/ssa_builder.h | 4 +++ runtime/entrypoints/entrypoint_utils-inl.h | 17 +++++++--- runtime/interpreter/interpreter_common.cc | 4 +++ test/127-checker-secondarydex/src/Test.java | 8 +++-- test/563-checker-fakestring/smali/TestCase.smali | 28 +++++++++++++++- test/563-checker-fakestring/src/Main.java | 6 ++++ 7 files changed, 101 insertions(+), 8 deletions(-) diff --git a/compiler/optimizing/ssa_builder.cc b/compiler/optimizing/ssa_builder.cc index 7494e336b..c0011cde8 100644 --- a/compiler/optimizing/ssa_builder.cc +++ b/compiler/optimizing/ssa_builder.cc @@ -422,6 +422,34 @@ bool SsaBuilder::FixAmbiguousArrayOps() { return true; } +void SsaBuilder::RemoveRedundantUninitializedStrings() { + if (GetGraph()->IsDebuggable()) { + // Do not perform the optimization for consistency with the interpreter + // which always allocates an object for new-instance of String. + return; + } + + for (HNewInstance* new_instance : uninitialized_strings_) { + DCHECK(new_instance->IsStringAlloc()); + + // Replace NewInstance of String with NullConstant if not used prior to + // calling StringFactory. In case of deoptimization, the interpreter is + // expected to skip null check on the `this` argument of the StringFactory call. + if (!new_instance->HasNonEnvironmentUses()) { + new_instance->ReplaceWith(GetGraph()->GetNullConstant()); + new_instance->GetBlock()->RemoveInstruction(new_instance); + + // Remove LoadClass if not needed any more. + HLoadClass* load_class = new_instance->InputAt(0)->AsLoadClass(); + DCHECK(load_class != nullptr); + DCHECK(!load_class->NeedsAccessCheck()) << "String class is always accessible"; + if (!load_class->HasUses()) { + load_class->GetBlock()->RemoveInstruction(load_class); + } + } + } +} + GraphAnalysisResult SsaBuilder::BuildSsa() { // 1) Visit in reverse post order. We need to have all predecessors of a block // visited (with the exception of loops) in order to create the right environment @@ -487,7 +515,15 @@ GraphAnalysisResult SsaBuilder::BuildSsa() { // input types. dead_phi_elimimation.EliminateDeadPhis(); - // 11) Clear locals. + // 11) Step 1) replaced uses of NewInstances of String with the results of + // their corresponding StringFactory calls. Unless the String objects are used + // before they are initialized, they can be replaced with NullConstant. + // Note that this optimization is valid only if unsimplified code does not use + // the uninitialized value because we assume execution can be deoptimized at + // any safepoint. We must therefore perform it before any other optimizations. + RemoveRedundantUninitializedStrings(); + + // 12) Clear locals. for (HInstructionIterator it(GetGraph()->GetEntryBlock()->GetInstructions()); !it.Done(); it.Advance()) { @@ -894,6 +930,10 @@ void SsaBuilder::VisitInvokeStaticOrDirect(HInvokeStaticOrDirect* invoke) { HNewInstance* new_instance = invoke->GetThisArgumentOfStringInit(); invoke->RemoveThisArgumentOfStringInit(); + // Replacing the NewInstance might render it redundant. Keep a list of these + // to be visited once it is clear whether it is has remaining uses. + uninitialized_strings_.push_back(new_instance); + // Walk over all vregs and replace any occurrence of `new_instance` with `invoke`. for (size_t vreg = 0, e = current_locals_->size(); vreg < e; ++vreg) { if ((*current_locals_)[vreg] == new_instance) { diff --git a/compiler/optimizing/ssa_builder.h b/compiler/optimizing/ssa_builder.h index 28eef6a40..ccef8ea38 100644 --- a/compiler/optimizing/ssa_builder.h +++ b/compiler/optimizing/ssa_builder.h @@ -57,6 +57,7 @@ class SsaBuilder : public HGraphVisitor { loop_headers_(graph->GetArena()->Adapter(kArenaAllocSsaBuilder)), ambiguous_agets_(graph->GetArena()->Adapter(kArenaAllocSsaBuilder)), ambiguous_asets_(graph->GetArena()->Adapter(kArenaAllocSsaBuilder)), + uninitialized_strings_(graph->GetArena()->Adapter(kArenaAllocSsaBuilder)), locals_for_(graph->GetBlocks().size(), ArenaVector(graph->GetArena()->Adapter(kArenaAllocSsaBuilder)), graph->GetArena()->Adapter(kArenaAllocSsaBuilder)) { @@ -105,6 +106,8 @@ class SsaBuilder : public HGraphVisitor { HPhi* GetFloatDoubleOrReferenceEquivalentOfPhi(HPhi* phi, Primitive::Type type); HArrayGet* GetFloatOrDoubleEquivalentOfArrayGet(HArrayGet* aget); + void RemoveRedundantUninitializedStrings(); + StackHandleScopeCollection* const handles_; // True if types of ambiguous ArrayGets have been resolved. @@ -119,6 +122,7 @@ class SsaBuilder : public HGraphVisitor { ArenaVector ambiguous_agets_; ArenaVector ambiguous_asets_; + ArenaVector uninitialized_strings_; // HEnvironment for each block. ArenaVector> locals_for_; diff --git a/runtime/entrypoints/entrypoint_utils-inl.h b/runtime/entrypoints/entrypoint_utils-inl.h index 9a9f42b97..68f2dcbf3 100644 --- a/runtime/entrypoints/entrypoint_utils-inl.h +++ b/runtime/entrypoints/entrypoint_utils-inl.h @@ -410,10 +410,19 @@ inline ArtMethod* FindMethodFromCode(uint32_t method_idx, mirror::Object** this_ DCHECK(self->IsExceptionPending()); // Throw exception and unwind. return nullptr; // Failure. } else if (UNLIKELY(*this_object == nullptr && type != kStatic)) { - // Maintain interpreter-like semantics where NullPointerException is thrown - // after potential NoSuchMethodError from class linker. - ThrowNullPointerExceptionForMethodAccess(method_idx, type); - return nullptr; // Failure. + if (UNLIKELY(resolved_method->GetDeclaringClass()->IsStringClass() && + resolved_method->IsConstructor())) { + // Hack for String init: + // + // We assume that the input of String. in verified code is always + // an unitialized reference. If it is a null constant, it must have been + // optimized out by the compiler. Do not throw NullPointerException. + } else { + // Maintain interpreter-like semantics where NullPointerException is thrown + // after potential NoSuchMethodError from class linker. + ThrowNullPointerExceptionForMethodAccess(method_idx, type); + return nullptr; // Failure. + } } else if (access_check) { mirror::Class* methods_class = resolved_method->GetDeclaringClass(); bool can_access_resolved_method = diff --git a/runtime/interpreter/interpreter_common.cc b/runtime/interpreter/interpreter_common.cc index 18fb0d851..ecd4de9bd 100644 --- a/runtime/interpreter/interpreter_common.cc +++ b/runtime/interpreter/interpreter_common.cc @@ -592,6 +592,10 @@ static inline bool DoCallCommon(ArtMethod* called_method, // // (at this point the ArtMethod has already been replaced, // so we just need to fix-up the arguments) + // + // Note that FindMethodFromCode in entrypoint_utils-inl.h was also special-cased + // to handle the compiler optimization of replacing `this` with null without + // throwing NullPointerException. uint32_t string_init_vreg_this = is_range ? vregC : arg[0]; if (UNLIKELY(string_init)) { DCHECK_GT(num_regs, 0u); // As the method is an instance method, there should be at least 1. diff --git a/test/127-checker-secondarydex/src/Test.java b/test/127-checker-secondarydex/src/Test.java index ae8bac937..266ed191b 100644 --- a/test/127-checker-secondarydex/src/Test.java +++ b/test/127-checker-secondarydex/src/Test.java @@ -23,8 +23,12 @@ public class Test extends Super { System.out.println("Test"); } - /// CHECK-START: java.lang.String Test.toString() ssa_builder (after) - /// CHECK: LoadClass needs_access_check:false klass:java.lang.String + /// CHECK-START: java.lang.Integer Test.toInteger() ssa_builder (after) + /// CHECK: LoadClass needs_access_check:false klass:java.lang.Integer + + public Integer toInteger() { + return new Integer(42); + } public String toString() { return new String("Test"); diff --git a/test/563-checker-fakestring/smali/TestCase.smali b/test/563-checker-fakestring/smali/TestCase.smali index cd52f3d55..4bd804da2 100644 --- a/test/563-checker-fakestring/smali/TestCase.smali +++ b/test/563-checker-fakestring/smali/TestCase.smali @@ -64,9 +64,15 @@ .end method -# Test deoptimization between String's allocation and initialization. +# Test deoptimization between String's allocation and initialization. When not +# compiling --debuggable, the NewInstance will be optimized out. ## CHECK-START: int TestCase.deoptimizeNewInstance(int[], byte[]) register (after) +## CHECK: <> NullConstant +## CHECK: Deoptimize env:[[<>,{{.*]]}} +## CHECK: InvokeStaticOrDirect method_name:java.lang.String. + +## CHECK-START-DEBUGGABLE: int TestCase.deoptimizeNewInstance(int[], byte[]) register (after) ## CHECK: <> NewInstance ## CHECK: Deoptimize env:[[<>,{{.*]]}} ## CHECK: InvokeStaticOrDirect method_name:java.lang.String. @@ -98,3 +104,23 @@ return v2 .end method + +# Test that a redundant NewInstance is removed if not used and not compiling +# --debuggable. + +## CHECK-START: java.lang.String TestCase.removeNewInstance(byte[]) register (after) +## CHECK-NOT: NewInstance +## CHECK-NOT: LoadClass + +## CHECK-START-DEBUGGABLE: java.lang.String TestCase.removeNewInstance(byte[]) register (after) +## CHECK: NewInstance + +.method public static removeNewInstance([B)Ljava/lang/String; + .registers 5 + + new-instance v0, Ljava/lang/String; + const-string v1, "UTF8" + invoke-direct {v0, p0, v1}, Ljava/lang/String;->([BLjava/lang/String;)V + return-object v0 + +.end method diff --git a/test/563-checker-fakestring/src/Main.java b/test/563-checker-fakestring/src/Main.java index 750f7184e..04df0f637 100644 --- a/test/563-checker-fakestring/src/Main.java +++ b/test/563-checker-fakestring/src/Main.java @@ -57,5 +57,11 @@ public class Main { } } } + + { + Method m = c.getMethod("removeNewInstance", byte[].class); + String result = (String) m.invoke(null, new Object[] { testData }); + assertEqual(testString, result); + } } } -- 2.11.0