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

1 files changed, 41 insertions, 1 deletions

diff --git a/compiler/optimizing/ssa_builder.cc b/compiler/optimizing/ssa_builder.cc
index 7494e336b1..c0011cde8d 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) {