Allow read side effects for removing dead instructions.
Rationale:
Instructions that only have the harmless read side effect may
be removed when dead as well, we were too strict previously.
As proof of concept, this cl also provides more accurate information
on a few string related intrinsics. This removes the dead indexOf
from CaffeineString (17% performance improvement, big bottleneck
of the StringBuffer's toString() still remains in loop).
Test: test-art-host
Change-Id: Id835a8e287e13e1f09be6b46278a039b8865802e
diff --git a/compiler/intrinsics_list.h b/compiler/intrinsics_list.h
index b617387..555baf6 100644
--- a/compiler/intrinsics_list.h
+++ b/compiler/intrinsics_list.h
@@ -108,8 +108,10 @@
V(StringCompareTo, kVirtual, kNeedsEnvironmentOrCache, kReadSideEffects, kCanThrow, "Ljava/lang/String;", "compareTo", "(Ljava/lang/String;)I") \
V(StringEquals, kVirtual, kNeedsEnvironmentOrCache, kReadSideEffects, kCanThrow, "Ljava/lang/String;", "equals", "(Ljava/lang/Object;)Z") \
V(StringGetCharsNoCheck, kVirtual, kNeedsEnvironmentOrCache, kReadSideEffects, kCanThrow, "Ljava/lang/String;", "getCharsNoCheck", "(II[CI)V") \
- V(StringIndexOf, kVirtual, kNeedsEnvironmentOrCache, kReadSideEffects, kCanThrow, "Ljava/lang/String;", "indexOf", "(I)I") \
- V(StringIndexOfAfter, kVirtual, kNeedsEnvironmentOrCache, kReadSideEffects, kCanThrow, "Ljava/lang/String;", "indexOf", "(II)I") \
+ V(StringIndexOf, kVirtual, kNeedsEnvironmentOrCache, kReadSideEffects, kNoThrow, "Ljava/lang/String;", "indexOf", "(I)I") \
+ V(StringIndexOfAfter, kVirtual, kNeedsEnvironmentOrCache, kReadSideEffects, kNoThrow, "Ljava/lang/String;", "indexOf", "(II)I") \
+ V(StringStringIndexOf, kVirtual, kNeedsEnvironmentOrCache, kReadSideEffects, kCanThrow, "Ljava/lang/String;", "indexOf", "(Ljava/lang/String;)I") \
+ V(StringStringIndexOfAfter, kVirtual, kNeedsEnvironmentOrCache, kReadSideEffects, kCanThrow, "Ljava/lang/String;", "indexOf", "(Ljava/lang/String;I)I") \
V(StringIsEmpty, kVirtual, kNeedsEnvironmentOrCache, kReadSideEffects, kNoThrow, "Ljava/lang/String;", "isEmpty", "()Z") \
V(StringLength, kVirtual, kNeedsEnvironmentOrCache, kReadSideEffects, kNoThrow, "Ljava/lang/String;", "length", "()I") \
V(StringNewStringFromBytes, kStatic, kNeedsEnvironmentOrCache, kAllSideEffects, kCanThrow, "Ljava/lang/StringFactory;", "newStringFromBytes", "([BIII)Ljava/lang/String;") \
diff --git a/compiler/optimizing/instruction_simplifier.cc b/compiler/optimizing/instruction_simplifier.cc
index e06fdee..85b461d 100644
--- a/compiler/optimizing/instruction_simplifier.cc
+++ b/compiler/optimizing/instruction_simplifier.cc
@@ -106,6 +106,7 @@
void SimplifyFP2Int(HInvoke* invoke);
void SimplifyStringCharAt(HInvoke* invoke);
void SimplifyStringIsEmptyOrLength(HInvoke* invoke);
+ void SimplifyNPEOnArgN(HInvoke* invoke, size_t);
void SimplifyMemBarrier(HInvoke* invoke, MemBarrierKind barrier_kind);
OptimizingCompilerStats* stats_;
@@ -1858,6 +1859,16 @@
invoke->GetBlock()->ReplaceAndRemoveInstructionWith(invoke, replacement);
}
+// This method should only be used on intrinsics whose sole way of throwing an
+// exception is raising a NPE when the nth argument is null. If that argument
+// is provably non-null, we can clear the flag.
+void InstructionSimplifierVisitor::SimplifyNPEOnArgN(HInvoke* invoke, size_t n) {
+ HInstruction* arg = invoke->InputAt(n);
+ if (!arg->CanBeNull()) {
+ invoke->SetCanThrow(false);
+ }
+}
+
void InstructionSimplifierVisitor::SimplifyMemBarrier(HInvoke* invoke, MemBarrierKind barrier_kind) {
uint32_t dex_pc = invoke->GetDexPc();
HMemoryBarrier* mem_barrier = new (GetGraph()->GetArena()) HMemoryBarrier(barrier_kind, dex_pc);
@@ -1911,6 +1922,10 @@
case Intrinsics::kStringLength:
SimplifyStringIsEmptyOrLength(instruction);
break;
+ case Intrinsics::kStringStringIndexOf:
+ case Intrinsics::kStringStringIndexOfAfter:
+ SimplifyNPEOnArgN(instruction, 1); // 0th has own NullCheck
+ break;
case Intrinsics::kUnsafeLoadFence:
SimplifyMemBarrier(instruction, MemBarrierKind::kLoadAny);
break;
diff --git a/compiler/optimizing/intrinsics_arm.cc b/compiler/optimizing/intrinsics_arm.cc
index 93a2340..0c39223 100644
--- a/compiler/optimizing/intrinsics_arm.cc
+++ b/compiler/optimizing/intrinsics_arm.cc
@@ -2600,6 +2600,9 @@
UNIMPLEMENTED_INTRINSIC(ARM, IntegerLowestOneBit)
UNIMPLEMENTED_INTRINSIC(ARM, LongLowestOneBit)
+UNIMPLEMENTED_INTRINSIC(ARM, StringStringIndexOf);
+UNIMPLEMENTED_INTRINSIC(ARM, StringStringIndexOfAfter);
+
// 1.8.
UNIMPLEMENTED_INTRINSIC(ARM, UnsafeGetAndAddInt)
UNIMPLEMENTED_INTRINSIC(ARM, UnsafeGetAndAddLong)
diff --git a/compiler/optimizing/intrinsics_arm64.cc b/compiler/optimizing/intrinsics_arm64.cc
index 47e6d96..b9424a3 100644
--- a/compiler/optimizing/intrinsics_arm64.cc
+++ b/compiler/optimizing/intrinsics_arm64.cc
@@ -2788,6 +2788,9 @@
UNIMPLEMENTED_INTRINSIC(ARM64, IntegerLowestOneBit)
UNIMPLEMENTED_INTRINSIC(ARM64, LongLowestOneBit)
+UNIMPLEMENTED_INTRINSIC(ARM64, StringStringIndexOf);
+UNIMPLEMENTED_INTRINSIC(ARM64, StringStringIndexOfAfter);
+
// 1.8.
UNIMPLEMENTED_INTRINSIC(ARM64, UnsafeGetAndAddInt)
UNIMPLEMENTED_INTRINSIC(ARM64, UnsafeGetAndAddLong)
diff --git a/compiler/optimizing/intrinsics_arm_vixl.cc b/compiler/optimizing/intrinsics_arm_vixl.cc
index 6ff0ca4..e5240a2 100644
--- a/compiler/optimizing/intrinsics_arm_vixl.cc
+++ b/compiler/optimizing/intrinsics_arm_vixl.cc
@@ -2679,6 +2679,9 @@
UNIMPLEMENTED_INTRINSIC(ARMVIXL, IntegerLowestOneBit)
UNIMPLEMENTED_INTRINSIC(ARMVIXL, LongLowestOneBit)
+UNIMPLEMENTED_INTRINSIC(ARMVIXL, StringStringIndexOf);
+UNIMPLEMENTED_INTRINSIC(ARMVIXL, StringStringIndexOfAfter);
+
// 1.8.
UNIMPLEMENTED_INTRINSIC(ARMVIXL, UnsafeGetAndAddInt)
UNIMPLEMENTED_INTRINSIC(ARMVIXL, UnsafeGetAndAddLong)
diff --git a/compiler/optimizing/intrinsics_mips.cc b/compiler/optimizing/intrinsics_mips.cc
index 5239f8f..7c81588 100644
--- a/compiler/optimizing/intrinsics_mips.cc
+++ b/compiler/optimizing/intrinsics_mips.cc
@@ -2495,6 +2495,9 @@
UNIMPLEMENTED_INTRINSIC(MIPS, MathTan)
UNIMPLEMENTED_INTRINSIC(MIPS, MathTanh)
+UNIMPLEMENTED_INTRINSIC(MIPS, StringStringIndexOf);
+UNIMPLEMENTED_INTRINSIC(MIPS, StringStringIndexOfAfter);
+
// 1.8.
UNIMPLEMENTED_INTRINSIC(MIPS, UnsafeGetAndAddInt)
UNIMPLEMENTED_INTRINSIC(MIPS, UnsafeGetAndAddLong)
diff --git a/compiler/optimizing/intrinsics_mips64.cc b/compiler/optimizing/intrinsics_mips64.cc
index 1d153e2..2d4f417 100644
--- a/compiler/optimizing/intrinsics_mips64.cc
+++ b/compiler/optimizing/intrinsics_mips64.cc
@@ -1947,6 +1947,9 @@
UNIMPLEMENTED_INTRINSIC(MIPS64, MathTan)
UNIMPLEMENTED_INTRINSIC(MIPS64, MathTanh)
+UNIMPLEMENTED_INTRINSIC(MIPS64, StringStringIndexOf);
+UNIMPLEMENTED_INTRINSIC(MIPS64, StringStringIndexOfAfter);
+
// 1.8.
UNIMPLEMENTED_INTRINSIC(MIPS64, UnsafeGetAndAddInt)
UNIMPLEMENTED_INTRINSIC(MIPS64, UnsafeGetAndAddLong)
diff --git a/compiler/optimizing/intrinsics_x86.cc b/compiler/optimizing/intrinsics_x86.cc
index 43682c5..bac98d5 100644
--- a/compiler/optimizing/intrinsics_x86.cc
+++ b/compiler/optimizing/intrinsics_x86.cc
@@ -3323,6 +3323,9 @@
UNIMPLEMENTED_INTRINSIC(X86, IntegerLowestOneBit)
UNIMPLEMENTED_INTRINSIC(X86, LongLowestOneBit)
+UNIMPLEMENTED_INTRINSIC(X86, StringStringIndexOf);
+UNIMPLEMENTED_INTRINSIC(X86, StringStringIndexOfAfter);
+
// 1.8.
UNIMPLEMENTED_INTRINSIC(X86, UnsafeGetAndAddInt)
UNIMPLEMENTED_INTRINSIC(X86, UnsafeGetAndAddLong)
diff --git a/compiler/optimizing/intrinsics_x86_64.cc b/compiler/optimizing/intrinsics_x86_64.cc
index de2606c..01577f7 100644
--- a/compiler/optimizing/intrinsics_x86_64.cc
+++ b/compiler/optimizing/intrinsics_x86_64.cc
@@ -2992,6 +2992,9 @@
UNIMPLEMENTED_INTRINSIC(X86_64, FloatIsInfinite)
UNIMPLEMENTED_INTRINSIC(X86_64, DoubleIsInfinite)
+UNIMPLEMENTED_INTRINSIC(X86_64, StringStringIndexOf);
+UNIMPLEMENTED_INTRINSIC(X86_64, StringStringIndexOfAfter);
+
// 1.8.
UNIMPLEMENTED_INTRINSIC(X86_64, UnsafeGetAndAddInt)
UNIMPLEMENTED_INTRINSIC(X86_64, UnsafeGetAndAddLong)
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index ce2edde..7890183 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -1956,7 +1956,7 @@
bool IsRemovable() const {
return
- !HasSideEffects() &&
+ !DoesAnyWrite() &&
!CanThrow() &&
!IsSuspendCheck() &&
!IsControlFlow() &&
@@ -3782,6 +3782,8 @@
return GetEnvironment()->IsFromInlinedInvoke();
}
+ void SetCanThrow(bool can_throw) { SetPackedFlag<kFlagCanThrow>(can_throw); }
+
bool CanThrow() const OVERRIDE { return GetPackedFlag<kFlagCanThrow>(); }
bool CanBeMoved() const OVERRIDE { return IsIntrinsic(); }
@@ -3840,8 +3842,6 @@
SetPackedFlag<kFlagCanThrow>(true);
}
- void SetCanThrow(bool can_throw) { SetPackedFlag<kFlagCanThrow>(can_throw); }
-
uint32_t number_of_arguments_;
ArtMethod* const resolved_method_;
ArenaVector<HUserRecord<HInstruction*>> inputs_;
diff --git a/runtime/image.cc b/runtime/image.cc
index 299d5fd..bd5ba93 100644
--- a/runtime/image.cc
+++ b/runtime/image.cc
@@ -25,7 +25,7 @@
namespace art {
const uint8_t ImageHeader::kImageMagic[] = { 'a', 'r', 't', '\n' };
-const uint8_t ImageHeader::kImageVersion[] = { '0', '3', '1', '\0' };
+const uint8_t ImageHeader::kImageVersion[] = { '0', '3', '2', '\0' };
ImageHeader::ImageHeader(uint32_t image_begin,
uint32_t image_size,
diff --git a/test/559-checker-irreducible-loop/smali/IrreducibleLoop.smali b/test/559-checker-irreducible-loop/smali/IrreducibleLoop.smali
index 5d4aa56..af43973 100644
--- a/test/559-checker-irreducible-loop/smali/IrreducibleLoop.smali
+++ b/test/559-checker-irreducible-loop/smali/IrreducibleLoop.smali
@@ -196,7 +196,7 @@
const-class v0, LMain;
if-ne v0, v2, :exit
:other_loop_entry
- const-class v1, LIrreducibleLoop;
+ const-class v1, Ljava/lang/Class; # LoadClass that can throw
goto :loop_entry
:exit
return-object v0
@@ -250,7 +250,7 @@
const/4 v0, 0
if-ne p0, v0, :other_loop_entry
:loop_entry
- const-class v1, LIrreducibleLoop;
+ const-class v1, Ljava/lang/Class; # LoadClass that can throw
if-ne v0, p0, :exit
:other_loop_entry
sub-int v1, p0, p0
@@ -286,7 +286,7 @@
.method public static licm3(III)I
.registers 4
:loop_entry
- const-class v0, LIrreducibleLoop;
+ const-class v0, Ljava/lang/Class; # LoadClass that can throw
if-ne p1, p2, :exit
goto :loop_body
diff --git a/test/624-checker-stringops/expected.txt b/test/624-checker-stringops/expected.txt
new file mode 100644
index 0000000..b0aad4d
--- /dev/null
+++ b/test/624-checker-stringops/expected.txt
@@ -0,0 +1 @@
+passed
diff --git a/test/624-checker-stringops/info.txt b/test/624-checker-stringops/info.txt
new file mode 100644
index 0000000..64344ac
--- /dev/null
+++ b/test/624-checker-stringops/info.txt
@@ -0,0 +1 @@
+Verify some properties of string operations represented by intrinsics.
diff --git a/test/624-checker-stringops/src/Main.java b/test/624-checker-stringops/src/Main.java
new file mode 100644
index 0000000..34e8283
--- /dev/null
+++ b/test/624-checker-stringops/src/Main.java
@@ -0,0 +1,124 @@
+/*
+ * Copyright (C) 2016 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+/**
+ * Tests properties of some string operations represented by intrinsics.
+ */
+public class Main {
+
+ static final String ABC = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
+ static final String XYZ = "XYZ";
+
+ //
+ // Variant intrinsics remain in the loop, but invariant references are hoisted out of the loop.
+ //
+ /// CHECK-START: int Main.liveIndexOf() licm (before)
+ /// CHECK-DAG: InvokeVirtual intrinsic:StringIndexOf loop:{{B\d+}} outer_loop:none
+ /// CHECK-DAG: InvokeVirtual intrinsic:StringIndexOfAfter loop:{{B\d+}} outer_loop:none
+ /// CHECK-DAG: InvokeVirtual intrinsic:StringStringIndexOf loop:{{B\d+}} outer_loop:none
+ /// CHECK-DAG: InvokeVirtual intrinsic:StringStringIndexOfAfter loop:{{B\d+}} outer_loop:none
+ //
+ /// CHECK-START: int Main.liveIndexOf() licm (after)
+ /// CHECK-DAG: InvokeVirtual intrinsic:StringIndexOf loop:{{B\d+}} outer_loop:none
+ /// CHECK-DAG: InvokeVirtual intrinsic:StringIndexOfAfter loop:{{B\d+}} outer_loop:none
+ /// CHECK-DAG: InvokeVirtual intrinsic:StringStringIndexOf loop:none
+ /// CHECK-DAG: InvokeVirtual intrinsic:StringStringIndexOfAfter loop:none
+ static int liveIndexOf() {
+ int k = ABC.length() + XYZ.length(); // does LoadString before loops
+ for (char c = 'A'; c <= 'Z'; c++) {
+ k += ABC.indexOf(c);
+ }
+ for (char c = 'A'; c <= 'Z'; c++) {
+ k += ABC.indexOf(c, 4);
+ }
+ for (char c = 'A'; c <= 'Z'; c++) {
+ k += ABC.indexOf(XYZ);
+ }
+ for (char c = 'A'; c <= 'Z'; c++) {
+ k += ABC.indexOf(XYZ, 2);
+ }
+ return k;
+ }
+
+ //
+ // All dead intrinsics can be removed completely.
+ //
+ /// CHECK-START: int Main.deadIndexOf() dead_code_elimination$initial (before)
+ /// CHECK-DAG: InvokeVirtual intrinsic:StringIndexOf loop:{{B\d+}} outer_loop:none
+ /// CHECK-DAG: InvokeVirtual intrinsic:StringIndexOfAfter loop:{{B\d+}} outer_loop:none
+ /// CHECK-DAG: InvokeVirtual intrinsic:StringStringIndexOf loop:{{B\d+}} outer_loop:none
+ /// CHECK-DAG: InvokeVirtual intrinsic:StringStringIndexOfAfter loop:{{B\d+}} outer_loop:none
+ //
+ /// CHECK-START: int Main.deadIndexOf() dead_code_elimination$initial (after)
+ /// CHECK-NOT: InvokeVirtual intrinsic:StringIndexOf
+ /// CHECK-NOT: InvokeVirtual intrinsic:StringIndexOfAfter
+ /// CHECK-NOT: InvokeVirtual intrinsic:StringStringIndexOf
+ /// CHECK-NOT: InvokeVirtual intrinsic:StringStringIndexOfAfter
+ static int deadIndexOf() {
+ int k = ABC.length() + XYZ.length(); // does LoadString before loops
+ for (char c = 'A'; c <= 'Z'; c++) {
+ int d = ABC.indexOf(c);
+ }
+ for (char c = 'A'; c <= 'Z'; c++) {
+ int d = ABC.indexOf(c, 4);
+ }
+ for (char c = 'A'; c <= 'Z'; c++) {
+ int d = ABC.indexOf(XYZ);
+ }
+ for (char c = 'A'; c <= 'Z'; c++) {
+ int d = ABC.indexOf(XYZ, 2);
+ }
+ return k;
+ }
+
+ //
+ // Explicit null check on receiver, implicit null check on argument prevents hoisting.
+ //
+ /// CHECK-START: int Main.indexOfExceptions(java.lang.String, java.lang.String) licm (after)
+ /// CHECK-DAG: <<String:l\d+>> NullCheck loop:<<Loop:B\d+>> outer_loop:none
+ /// CHECK-DAG: InvokeVirtual [<<String>>,{{l\d+}}] intrinsic:StringStringIndexOf loop:<<Loop>> outer_loop:none
+ static int indexOfExceptions(String s, String t) {
+ int k = 0;
+ for (char c = 'A'; c <= 'Z'; c++) {
+ k += s.indexOf(t);
+ }
+ return k;
+ }
+
+ public static void main(String[] args) {
+ expectEquals(1865, liveIndexOf());
+ expectEquals(29, deadIndexOf());
+ try {
+ indexOfExceptions(null, XYZ);
+ throw new Error("Expected: NPE");
+ } catch (NullPointerException e) {
+ }
+ try {
+ indexOfExceptions(ABC, null);
+ throw new Error("Expected: NPE");
+ } catch (NullPointerException e) {
+ }
+ expectEquals(598, indexOfExceptions(ABC, XYZ));
+
+ System.out.println("passed");
+ }
+
+ private static void expectEquals(int expected, int result) {
+ if (expected != result) {
+ throw new Error("Expected: " + expected + ", found: " + result);
+ }
+ }
+}