Fixed
Status Update
Comments
js...@google.com <js...@google.com>
ap...@google.com <ap...@google.com> #2
Project: r8
Branch: master
commit bfb29b2971b383cd7dba25ce55e8259b214df5ce
Author: Jinseong Jeon <jsjeon@google.com>
Date: Mon Nov 12 11:10:06 2018
Compute trivial String operations for const-string.
In addition to String#length, this CL adds suuport:
* String#isEmpty
* String#contains
* String#startsWith
* String#endsWith
Bug: 119364907
Change-Id: I10626fa660dba3dfad3d3586db70184f41ee28b9
M src/main/java/com/android/tools/r8/graph/DexItemFactory.java
M src/main/java/com/android/tools/r8/ir/conversion/IRConverter.java
M src/main/java/com/android/tools/r8/ir/optimize/string/StringOptimizer.java
M src/test/java/com/android/tools/r8/ir/analysis/type/TypeLatticeTest.java
M src/test/java/com/android/tools/r8/ir/optimize/reflection/GetClassTest.java
A src/test/java/com/android/tools/r8/ir/optimize/string/StringContentCheckTest.java
A src/test/java/com/android/tools/r8/ir/optimize/string/StringIsEmptyTest.java
https://r8-review.googlesource.com/30502
Branch: master
commit bfb29b2971b383cd7dba25ce55e8259b214df5ce
Author: Jinseong Jeon <jsjeon@google.com>
Date: Mon Nov 12 11:10:06 2018
Compute trivial String operations for const-string.
In addition to String#length, this CL adds suuport:
* String#isEmpty
* String#contains
* String#startsWith
* String#endsWith
Bug: 119364907
Change-Id: I10626fa660dba3dfad3d3586db70184f41ee28b9
M src/main/java/com/android/tools/r8/graph/DexItemFactory.java
M src/main/java/com/android/tools/r8/ir/conversion/IRConverter.java
M src/main/java/com/android/tools/r8/ir/optimize/string/StringOptimizer.java
M src/test/java/com/android/tools/r8/ir/analysis/type/TypeLatticeTest.java
M src/test/java/com/android/tools/r8/ir/optimize/reflection/GetClassTest.java
A src/test/java/com/android/tools/r8/ir/optimize/string/StringContentCheckTest.java
A src/test/java/com/android/tools/r8/ir/optimize/string/StringIsEmptyTest.java
ap...@google.com <ap...@google.com> #3
Project: r8
Branch: master
commit dfc4ec5f0f84c07a93e1923b728b3094b51f557d
Author: Jake Wharton <jakew@google.com>
Date: Wed Nov 21 22:01:02 2018
Compute more trivial String operations for const-string
This CL adds support for:
* String#equals
* String#equalsIgnoreCase
* String#contentEquals
Bug: 119364907
Change-Id: Ic4eec6d48fe6c4e22d9b92df3fd0975c49687a29
M src/main/java/com/android/tools/r8/graph/DexItemFactory.java
M src/main/java/com/android/tools/r8/ir/optimize/string/StringOptimizer.java
M src/test/java/com/android/tools/r8/ir/optimize/string/StringContentCheckTest.java
https://r8-review.googlesource.com/31160
Branch: master
commit dfc4ec5f0f84c07a93e1923b728b3094b51f557d
Author: Jake Wharton <jakew@google.com>
Date: Wed Nov 21 22:01:02 2018
Compute more trivial String operations for const-string
This CL adds support for:
* String#equals
* String#equalsIgnoreCase
* String#contentEquals
Bug: 119364907
Change-Id: Ic4eec6d48fe6c4e22d9b92df3fd0975c49687a29
M src/main/java/com/android/tools/r8/graph/DexItemFactory.java
M src/main/java/com/android/tools/r8/ir/optimize/string/StringOptimizer.java
M src/test/java/com/android/tools/r8/ir/optimize/string/StringContentCheckTest.java
ap...@google.com <ap...@google.com> #4
Project: r8
Branch: master
commit 959ff85d60b92b13833c50c3c4f7ff3353768482
Author: Jake Wharton <jakew@google.com>
Date: Sat Feb 09 22:07:21 2019
Add indexOf and lastIndexOf to compile-time string computation
Bug: 119364907
Change-Id: I8552d1deebccc634f9e4e41f649a07043266bb30
M src/main/java/com/android/tools/r8/graph/DexItemFactory.java
M src/main/java/com/android/tools/r8/ir/optimize/string/StringOptimizer.java
M src/test/java/com/android/tools/r8/ir/optimize/string/StringContentCheckTest.java
https://r8-review.googlesource.com/34020
Branch: master
commit 959ff85d60b92b13833c50c3c4f7ff3353768482
Author: Jake Wharton <jakew@google.com>
Date: Sat Feb 09 22:07:21 2019
Add indexOf and lastIndexOf to compile-time string computation
Bug: 119364907
Change-Id: I8552d1deebccc634f9e4e41f649a07043266bb30
M src/main/java/com/android/tools/r8/graph/DexItemFactory.java
M src/main/java/com/android/tools/r8/ir/optimize/string/StringOptimizer.java
M src/test/java/com/android/tools/r8/ir/optimize/string/StringContentCheckTest.java
ap...@google.com <ap...@google.com> #5
Project: r8
Branch: master
commit 3163f079581d686adbb3bb99f243b2b9083fb709
Author: Jake Wharton <jakew@google.com>
Date: Tue Feb 12 15:54:36 2019
Add compareTo and compareToIgnoreCase to compile-time string computation
Bug: 119364907
Change-Id: I90817bbd254ff58dcff9c0ab3a1cf07839534ed7
M src/main/java/com/android/tools/r8/graph/DexItemFactory.java
M src/main/java/com/android/tools/r8/ir/optimize/string/StringOptimizer.java
M src/test/java/com/android/tools/r8/ir/optimize/string/StringContentCheckTest.java
https://r8-review.googlesource.com/34220
Branch: master
commit 3163f079581d686adbb3bb99f243b2b9083fb709
Author: Jake Wharton <jakew@google.com>
Date: Tue Feb 12 15:54:36 2019
Add compareTo and compareToIgnoreCase to compile-time string computation
Bug: 119364907
Change-Id: I90817bbd254ff58dcff9c0ab3a1cf07839534ed7
M src/main/java/com/android/tools/r8/graph/DexItemFactory.java
M src/main/java/com/android/tools/r8/ir/optimize/string/StringOptimizer.java
M src/test/java/com/android/tools/r8/ir/optimize/string/StringContentCheckTest.java
js...@google.com <js...@google.com> #6
I'd like to close this now. Almost all utils mentioned at comment #1 are covered, except for a couple risky ones:
* String.regionMatches
https://docs.oracle.com/javase/7/docs/api/java/lang/String.html#regionMatches(boolean,%20int,%20java.lang.String,%20int,%20int)
It seems to have low likelihood that all 4 or 5 inputs are constants
* String.substring
Based on b/120138731 , I'd like to avoid adding another const string (even though it would be smaller) just to replace 4 bytes of invoke-virtual.
* String.charAt
Unlike other utils that clearly return `int`, this one returns `char` but will be represented `int` for a while. Based on issue 124152497 , that newly added constant could be mangled (by other optimizations, e.g., constant canonicalization), and end up register type error on legacy VM.
* String.regionMatches
It seems to have low likelihood that all 4 or 5 inputs are constants
* String.substring
Based on
* String.charAt
Unlike other utils that clearly return `int`, this one returns `char` but will be represented `int` for a while. Based on
js...@google.com <js...@google.com> #7
Ah, one exception: computation of substring could be acceptable if the computed substring is already there in the string pool. I'll work on that, and will close this afterwards.
ja...@gmail.com <ja...@gmail.com> #8
I was hoping to also figure out if the receiver was also the only usage of that constant meaning it would disappear after the operation occurred. Not sure if that question can be answered easily and cheaply or not.
js...@google.com <js...@google.com> #10
Found code patterns that rely on IndexOutOfBoundsException from String.substring, interesting.
ja...@gmail.com <ja...@gmail.com> #11
I don't think that approach will work. I want to detect if performing the operation on the receiver string will cause it to become dead.
Basically,
public static void main (String... args) {
System.out.println("test".substring(2));
}
should apply the operation at compile time since "test" will become dead and "st" will replace it. But,
public static void main(String... args) {
System.out.println("test");
System.out.println("test".substring(2));
}
should NOT apply the operation because "test" has another reference and so the addition of "st" will cause the string pool to grow.
Basically,
public static void main (String... args) {
System.out.println("test".substring(2));
}
should apply the operation at compile time since "test" will become dead and "st" will replace it. But,
public static void main(String... args) {
System.out.println("test");
System.out.println("test".substring(2));
}
should NOT apply the operation because "test" has another reference and so the addition of "st" will cause the string pool to grow.
js...@google.com <js...@google.com> #12
We don't have a global view of string usages. If there are other methods in that class (in CF backend) or any places in an app (in DEX backend), even the first case ends up with adding one more string, which could be bigger than 4 bytes we gain. The initial implementation is done, so let me actually test what happens if we don't restrict it.
ja...@gmail.com <ja...@gmail.com> #13
Hmm I don't see how you could get a string out of substring, concat, or StringBuilder that's longer than its input(s). conat and StringBuilder would always be equal (less the bytecodes) and substring's worst case, substring(0), is equal (less the bytecodes).
js...@google.com <js...@google.com> #14
Of course the string out of those utils should be smaller than or equal to the input. I'm talking about potential gains of code size. The following is one heuristic I came up with:
// invoke + const-string for original string
|| 4 + (input.numberOfAllUsers() == 1 ? 4 : 0)
// + const-number for begin index
+ (beginIndex.numberOfAllUsers() == 1 ? 2 : 0)
// + const-number for end index
+ (endIndex != null && endIndex.numberOfAllUsers() == 1 ? 2 : 0)
// >= new constant string and its loading
>= sub.length() + 2;
which is too specific to DEX backend though.
In benchmarks we have, I don't see any difference when we have a guard to limit such compile-time computation v.s. no limit, so maybe we can just go and replace such call if possible. But I still have a gut feeling that doing so always could lead to bigger code size because of newly added constant strings...
// invoke + const-string for original string
|| 4 + (input.numberOfAllUsers() == 1 ? 4 : 0)
// + const-number for begin index
+ (beginIndex.numberOfAllUsers() == 1 ? 2 : 0)
// + const-number for end index
+ (endIndex != null && endIndex.numberOfAllUsers() == 1 ? 2 : 0)
// >= new constant string and its loading
>= sub.length() + 2;
which is too specific to DEX backend though.
In benchmarks we have, I don't see any difference when we have a guard to limit such compile-time computation v.s. no limit, so maybe we can just go and replace such call if possible. But I still have a gut feeling that doing so always could lead to bigger code size because of newly added constant strings...
ap...@google.com <ap...@google.com> #15
Project: r8
Branch: master
commit b40e493ddd55374e9b0a2f14d98951eace715853
Author: Jinseong Jeon <jsjeon@google.com>
Date: Mon Feb 25 12:46:30 2019
Compute String#substring at compile time.
Bug: 119364907
Change-Id: I705e22149bc1fe413d1c88f57f774e7797d5a86a
M src/main/java/com/android/tools/r8/graph/DexItemFactory.java
M src/main/java/com/android/tools/r8/ir/optimize/string/StringOptimizer.java
M src/test/java/com/android/tools/r8/ir/optimize/string/StringContentCheckTest.java
https://r8-review.googlesource.com/34260
Branch: master
commit b40e493ddd55374e9b0a2f14d98951eace715853
Author: Jinseong Jeon <jsjeon@google.com>
Date: Mon Feb 25 12:46:30 2019
Compute String#substring at compile time.
Bug: 119364907
Change-Id: I705e22149bc1fe413d1c88f57f774e7797d5a86a
M src/main/java/com/android/tools/r8/graph/DexItemFactory.java
M src/main/java/com/android/tools/r8/ir/optimize/string/StringOptimizer.java
M src/test/java/com/android/tools/r8/ir/optimize/string/StringContentCheckTest.java
js...@google.com <js...@google.com>
th...@gmail.com <th...@gmail.com> #16
Related issue about the same feature for Kotlin code:
Description
class Prefix {
private static final String PREFIX = "Name: ";
static String removeName(String header) { // LIBRARY
return header.startsWith(PREFIX)
? header.substring(PREFIX.length())
: header;
}
public static void main(String... args) { // APP
System.out.println(removeName("Name: Jake"));
}
}
with rules:
-keepclasseswithmembers class * {
public static void main(...);
}
The `removeName` method gets inlined into the call-site and the call to `PREFIX.length` gets computed at compile-time to the literal 6 (thanks to
[000160] Prefix.main:([Ljava/lang/String;)V
0000: sget-object v2, Ljava/lang/System;.out:Ljava/io/PrintStream;
0002: const-string v0, "Name: Jake"
0004: const-string v1, "Name: "
0006: invoke-virtual {v0, v1}, Ljava/lang/String;.startsWith:(Ljava/lang/String;)Z
0009: move-result v1
000a: if-eqz v1, 0011
000c: const/4 v1, #int 6
000d: invoke-virtual {v0, v1}, Ljava/lang/String;.substring:(I)Ljava/lang/String;
0010: move-result-object v0
0011: invoke-virtual {v2, v0}, Ljava/io/PrintStream;.println:(Ljava/lang/String;)V
0014: return-void
When all arguments are constants and/or literals, the boolean-returning methods are the best candidates here since they likely participate in control flow (and thus could result in DCE). Examples are:
* String.startsWith
* String.endsWith
* String.contains
* String.isEmpty
* String.equals
* String.equalsIgnoreCase
* String.contentEquals(CharSequence)
* String.regionMatches
in rough order of likely usage.
Other methods are still likely candidates:
* String.substring
* String.compareTo
* String.compareToIgnoringCase
* String.charAt
If `String.startsWith` and `String.substring` were implemented, the above example would turn into:
[000160] Prefix.main:([Ljava/lang/String;)V
0000: sget-object v1, Ljava/lang/System;.out:Ljava/io/PrintStream;
0002: const-string v0, "Jake"
0004: invoke-virtual {v1, v0}, Ljava/io/PrintStream;.println:(Ljava/lang/String;)V
0007: return-void