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.<init>). 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.<init> 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
diff --git a/compiler/optimizing/ssa_builder.cc b/compiler/optimizing/ssa_builder.cc
index 7494e33..c0011cd 100644
--- a/compiler/optimizing/ssa_builder.cc
+++ b/compiler/optimizing/ssa_builder.cc
@@ -422,6 +422,34 @@
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 @@
// 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 @@
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 28eef6a..ccef8ea 100644
--- a/compiler/optimizing/ssa_builder.h
+++ b/compiler/optimizing/ssa_builder.h
@@ -57,6 +57,7 @@
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<HInstruction*>(graph->GetArena()->Adapter(kArenaAllocSsaBuilder)),
graph->GetArena()->Adapter(kArenaAllocSsaBuilder)) {
@@ -105,6 +106,8 @@
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 @@
ArenaVector<HArrayGet*> ambiguous_agets_;
ArenaVector<HArraySet*> ambiguous_asets_;
+ ArenaVector<HNewInstance*> uninitialized_strings_;
// HEnvironment for each block.
ArenaVector<ArenaVector<HInstruction*>> locals_for_;
diff --git a/runtime/entrypoints/entrypoint_utils-inl.h b/runtime/entrypoints/entrypoint_utils-inl.h
index 9a9f42b..68f2dcb 100644
--- a/runtime/entrypoints/entrypoint_utils-inl.h
+++ b/runtime/entrypoints/entrypoint_utils-inl.h
@@ -410,10 +410,19 @@
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.<init> 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 18fb0d8..ecd4de9 100644
--- a/runtime/interpreter/interpreter_common.cc
+++ b/runtime/interpreter/interpreter_common.cc
@@ -592,6 +592,10 @@
//
// (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 ae8bac9..266ed19 100644
--- a/test/127-checker-secondarydex/src/Test.java
+++ b/test/127-checker-secondarydex/src/Test.java
@@ -23,8 +23,12 @@
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 cd52f3d..4bd804d 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: <<Null:l\d+>> NullConstant
+## CHECK: Deoptimize env:[[<<Null>>,{{.*]]}}
+## CHECK: InvokeStaticOrDirect method_name:java.lang.String.<init>
+
+## CHECK-START-DEBUGGABLE: int TestCase.deoptimizeNewInstance(int[], byte[]) register (after)
## CHECK: <<String:l\d+>> NewInstance
## CHECK: Deoptimize env:[[<<String>>,{{.*]]}}
## CHECK: InvokeStaticOrDirect method_name:java.lang.String.<init>
@@ -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;-><init>([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 750f718..04df0f6 100644
--- a/test/563-checker-fakestring/src/Main.java
+++ b/test/563-checker-fakestring/src/Main.java
@@ -57,5 +57,11 @@
}
}
}
+
+ {
+ Method m = c.getMethod("removeNewInstance", byte[].class);
+ String result = (String) m.invoke(null, new Object[] { testData });
+ assertEqual(testString, result);
+ }
}
}
