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/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);
+    }
   }
 }