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_;