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, 4 insertions, 0 deletions

diff --git a/compiler/optimizing/ssa_builder.h b/compiler/optimizing/ssa_builder.h
index 28eef6a40c..ccef8ea380 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<HInstruction*>(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<HArrayGet*> ambiguous_agets_;
   ArenaVector<HArraySet*> ambiguous_asets_;
+  ArenaVector<HNewInstance*> uninitialized_strings_;
 
   // HEnvironment for each block.
   ArenaVector<ArenaVector<HInstruction*>> locals_for_;