Optimize String's length/isEmpty for constant strings
If at compile time we know the length of the string, we can insert
that constant into the graph.
As part of this CL, I introduced VisitArrayLength in
ConstantFolding. This is done because:
* We are folding the instrucion into a constant so it makes
logical sense, and
* It plays better with isEmpty since that's an ArrayLength+Equal
which can be dealt with in one ConstantFolding pass.
As a note, there's VisitArrayLength in InstructionSimplifier which
would make sense to also move to ConstantFolding. However, in doing
so we get code size regressions. Added a TODO to see if we can deal
with that in the future.
Locally speed-compiling in a Pixel 5:
* SystemServer: -4.38 KB (-0.01%)
* SystemUIGoogle: -23.92KB (-0.09%)
* AGSA: -217.66KB (-0.07%)
Bug: 276416001
Test: art/test/testrunner/testrunner.py --host --64 --optimizing -b
Change-Id: Ic2081d489482157b016762e0ec103319d3b9a46e
diff --git a/compiler/optimizing/constant_folding.cc b/compiler/optimizing/constant_folding.cc
index bd9c899..b737fb3 100644
--- a/compiler/optimizing/constant_folding.cc
+++ b/compiler/optimizing/constant_folding.cc
@@ -18,6 +18,7 @@
#include <algorithm>
+#include "dex/dex_file-inl.h"
#include "optimizing/data_type.h"
#include "optimizing/nodes.h"
@@ -36,9 +37,10 @@
void VisitUnaryOperation(HUnaryOperation* inst) override;
void VisitBinaryOperation(HBinaryOperation* inst) override;
- void VisitTypeConversion(HTypeConversion* inst) override;
+ void VisitArrayLength(HArrayLength* inst) override;
void VisitDivZeroCheck(HDivZeroCheck* inst) override;
void VisitIf(HIf* inst) override;
+ void VisitTypeConversion(HTypeConversion* inst) override;
void PropagateValue(HBasicBlock* starting_block, HInstruction* variable, HConstant* constant);
@@ -124,16 +126,6 @@
}
}
-void HConstantFoldingVisitor::VisitTypeConversion(HTypeConversion* inst) {
- // Constant folding: replace `TypeConversion(a)' with a constant at
- // compile time if `a' is a constant.
- HConstant* constant = inst->TryStaticEvaluation();
- if (constant != nullptr) {
- inst->ReplaceWith(constant);
- inst->GetBlock()->RemoveInstruction(inst);
- }
-}
-
void HConstantFoldingVisitor::VisitDivZeroCheck(HDivZeroCheck* inst) {
// We can safely remove the check if the input is a non-null constant.
HInstruction* check_input = inst->InputAt(0);
@@ -275,6 +267,27 @@
}
}
+void HConstantFoldingVisitor::VisitArrayLength(HArrayLength* inst) {
+ HInstruction* input = inst->InputAt(0);
+ if (input->IsLoadString()) {
+ DCHECK(inst->IsStringLength());
+ HLoadString* load_string = input->AsLoadString();
+ const DexFile& dex_file = load_string->GetDexFile();
+ const dex::StringId& string_id = dex_file.GetStringId(load_string->GetStringIndex());
+ inst->ReplaceWith(GetGraph()->GetIntConstant(dex_file.GetStringLength(string_id)));
+ }
+}
+
+void HConstantFoldingVisitor::VisitTypeConversion(HTypeConversion* inst) {
+ // Constant folding: replace `TypeConversion(a)' with a constant at
+ // compile time if `a' is a constant.
+ HConstant* constant = inst->TryStaticEvaluation();
+ if (constant != nullptr) {
+ inst->ReplaceWith(constant);
+ inst->GetBlock()->RemoveInstruction(inst);
+ }
+}
+
void InstructionWithAbsorbingInputSimplifier::VisitShift(HBinaryOperation* instruction) {
DCHECK(instruction->IsShl() || instruction->IsShr() || instruction->IsUShr());
HInstruction* left = instruction->GetLeft();
diff --git a/compiler/optimizing/constant_folding.h b/compiler/optimizing/constant_folding.h
index 1a5e904..73ac3ce 100644
--- a/compiler/optimizing/constant_folding.h
+++ b/compiler/optimizing/constant_folding.h
@@ -41,7 +41,9 @@
*/
class HConstantFolding : public HOptimization {
public:
- HConstantFolding(HGraph* graph, OptimizingCompilerStats* stats, const char* name)
+ HConstantFolding(HGraph* graph,
+ OptimizingCompilerStats* stats = nullptr,
+ const char* name = kConstantFoldingPassName)
: HOptimization(graph, name, stats) {}
bool Run() override;
diff --git a/compiler/optimizing/instruction_simplifier.cc b/compiler/optimizing/instruction_simplifier.cc
index 12ca30f..b772fbb 100644
--- a/compiler/optimizing/instruction_simplifier.cc
+++ b/compiler/optimizing/instruction_simplifier.cc
@@ -1117,6 +1117,10 @@
}
}
+// TODO(solanes): This optimization should be in ConstantFolding since we are folding to a constant.
+// However, we get code size regressions when we do that since we sometimes have a NullCheck between
+// HArrayLength and IsNewArray, and said NullCheck is eliminated in InstructionSimplifier. If we run
+// ConstantFolding and InstructionSimplifier in lockstep this wouldn't be an issue.
void InstructionSimplifierVisitor::VisitArrayLength(HArrayLength* instruction) {
HInstruction* input = instruction->InputAt(0);
// If the array is a NewArray with constant size, replace the array length
diff --git a/test/2047-checker-const-string-length/expected-stderr.txt b/test/2047-checker-const-string-length/expected-stderr.txt
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/test/2047-checker-const-string-length/expected-stderr.txt
diff --git a/test/2047-checker-const-string-length/expected-stdout.txt b/test/2047-checker-const-string-length/expected-stdout.txt
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/test/2047-checker-const-string-length/expected-stdout.txt
diff --git a/test/2047-checker-const-string-length/info.txt b/test/2047-checker-const-string-length/info.txt
new file mode 100644
index 0000000..61e987f
--- /dev/null
+++ b/test/2047-checker-const-string-length/info.txt
@@ -0,0 +1 @@
+Tests that we optimize String's length()/isEmpty() for constant strings.
diff --git a/test/2047-checker-const-string-length/src/Main.java b/test/2047-checker-const-string-length/src/Main.java
new file mode 100644
index 0000000..0130943
--- /dev/null
+++ b/test/2047-checker-const-string-length/src/Main.java
@@ -0,0 +1,227 @@
+/*
+ * Copyright (C) 2023 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.
+ */
+
+// Note that the empty string is present in the BootImage but the other one is a BSS string. We are
+// testing both AOT LoadString kinds.
+
+public class Main {
+ public static void main(String[] args) {
+ $noinline$testLength();
+ $noinline$testIsEmpty();
+ }
+
+ private static void $noinline$testLength() {
+ assertEquals(0, $noinline$testLengthEmptyString());
+ assertEquals(0, $noinline$testLengthEmptyStringWithInline());
+ assertEquals(32, $noinline$testLengthBssString());
+ assertEquals(32, $noinline$testLengthBssStringWithInline());
+ }
+
+ /// CHECK-START: int Main.$noinline$testLengthEmptyString() constant_folding (before)
+ /// CHECK: LoadString load_kind:BootImageRelRo
+ /// CHECK: <<Length:i\d+>> ArrayLength
+ /// CHECK: Return [<<Length>>]
+
+ /// CHECK-START: int Main.$noinline$testLengthEmptyString() constant_folding (after)
+ /// CHECK: <<Const0:i\d+>> IntConstant 0
+ /// CHECK: Return [<<Const0>>]
+
+ /// CHECK-START: int Main.$noinline$testLengthEmptyString() dead_code_elimination$initial (after)
+ /// CHECK-NOT: LoadString
+
+ /// CHECK-START: int Main.$noinline$testLengthEmptyString() dead_code_elimination$initial (after)
+ /// CHECK-NOT: ArrayLength
+ private static int $noinline$testLengthEmptyString() {
+ String str = "";
+ return str.length();
+ }
+
+ /// CHECK-START: int Main.$noinline$testLengthEmptyStringWithInline() constant_folding$after_inlining (before)
+ /// CHECK: LoadString load_kind:BootImageRelRo
+ /// CHECK: <<Length:i\d+>> ArrayLength
+ /// CHECK: Return [<<Length>>]
+
+ /// CHECK-START: int Main.$noinline$testLengthEmptyStringWithInline() constant_folding$after_inlining (after)
+ /// CHECK: <<Const0:i\d+>> IntConstant 0
+ /// CHECK: Return [<<Const0>>]
+
+ /// CHECK-START: int Main.$noinline$testLengthEmptyStringWithInline() dead_code_elimination$after_inlining (after)
+ /// CHECK-NOT: LoadString
+
+ /// CHECK-START: int Main.$noinline$testLengthEmptyStringWithInline() dead_code_elimination$after_inlining (after)
+ /// CHECK-NOT: ArrayLength
+ private static int $noinline$testLengthEmptyStringWithInline() {
+ String str = "";
+ return $inline$returnLength(str);
+ }
+
+ /// CHECK-START: int Main.$noinline$testLengthBssString() constant_folding (before)
+ /// CHECK: LoadString load_kind:BssEntry
+ /// CHECK: <<Length:i\d+>> ArrayLength
+ /// CHECK: Return [<<Length>>]
+
+ /// CHECK-START: int Main.$noinline$testLengthBssString() constant_folding (after)
+ /// CHECK: <<Const32:i\d+>> IntConstant 32
+ /// CHECK: Return [<<Const32>>]
+
+ // We don't remove LoadString load_kind:BssEntry even if they have no uses, since IsRemovable()
+ // returns false for them.
+ /// CHECK-START: int Main.$noinline$testLengthBssString() dead_code_elimination$initial (after)
+ /// CHECK: LoadString load_kind:BssEntry
+
+ /// CHECK-START: int Main.$noinline$testLengthBssString() dead_code_elimination$initial (after)
+ /// CHECK-NOT: ArrayLength
+ private static int $noinline$testLengthBssString() {
+ String str = "2047-checker-const-string-length";
+ return str.length();
+ }
+
+ /// CHECK-START: int Main.$noinline$testLengthBssStringWithInline() constant_folding$after_inlining (before)
+ /// CHECK: LoadString load_kind:BssEntry
+ /// CHECK: <<Length:i\d+>> ArrayLength
+ /// CHECK: Return [<<Length>>]
+
+ /// CHECK-START: int Main.$noinline$testLengthBssStringWithInline() constant_folding$after_inlining (after)
+ /// CHECK: <<Const32:i\d+>> IntConstant 32
+ /// CHECK: Return [<<Const32>>]
+
+ // We don't remove LoadString load_kind:BssEntry even if they have no uses, since IsRemovable()
+ // returns false for them.
+ /// CHECK-START: int Main.$noinline$testLengthBssStringWithInline() dead_code_elimination$after_inlining (after)
+ /// CHECK: LoadString load_kind:BssEntry
+
+ /// CHECK-START: int Main.$noinline$testLengthBssStringWithInline() dead_code_elimination$after_inlining (after)
+ /// CHECK-NOT: ArrayLength
+ private static int $noinline$testLengthBssStringWithInline() {
+ String str = "2047-checker-const-string-length";
+ return $inline$returnLength(str);
+ }
+
+ private static int $inline$returnLength(String str) {
+ return str.length();
+ }
+
+ private static void $noinline$testIsEmpty() {
+ assertEquals(true, $noinline$testIsEmptyEmptyString());
+ assertEquals(true, $noinline$testIsEmptyEmptyStringWithInline());
+ assertEquals(false, $noinline$testIsEmptyBssString());
+ assertEquals(false, $noinline$testIsEmptyBssStringWithInline());
+ }
+
+ /// CHECK-START: boolean Main.$noinline$testIsEmptyEmptyString() constant_folding (before)
+ /// CHECK: <<Const0:i\d+>> IntConstant 0
+ /// CHECK: LoadString load_kind:BootImageRelRo
+ /// CHECK: <<Length:i\d+>> ArrayLength
+ /// CHECK: <<Eq:z\d+>> Equal [<<Length>>,<<Const0>>]
+ /// CHECK: Return [<<Eq>>]
+
+ /// CHECK-START: boolean Main.$noinline$testIsEmptyEmptyString() constant_folding (after)
+ /// CHECK: <<Const1:i\d+>> IntConstant 1
+ /// CHECK: Return [<<Const1>>]
+
+ /// CHECK-START: boolean Main.$noinline$testIsEmptyEmptyString() dead_code_elimination$initial (after)
+ /// CHECK-NOT: LoadString
+
+ /// CHECK-START: boolean Main.$noinline$testIsEmptyEmptyString() dead_code_elimination$initial (after)
+ /// CHECK-NOT: ArrayLength
+ private static boolean $noinline$testIsEmptyEmptyString() {
+ String str = "";
+ return str.isEmpty();
+ }
+
+ /// CHECK-START: boolean Main.$noinline$testIsEmptyEmptyStringWithInline() constant_folding$after_inlining (before)
+ /// CHECK: <<Const0:i\d+>> IntConstant 0
+ /// CHECK: LoadString load_kind:BootImageRelRo
+ /// CHECK: <<Length:i\d+>> ArrayLength
+ /// CHECK: <<Eq:z\d+>> Equal [<<Length>>,<<Const0>>]
+ /// CHECK: Return [<<Eq>>]
+
+ /// CHECK-START: boolean Main.$noinline$testIsEmptyEmptyStringWithInline() constant_folding$after_inlining (after)
+ /// CHECK: <<Const1:i\d+>> IntConstant 1
+ /// CHECK: Return [<<Const1>>]
+
+ /// CHECK-START: boolean Main.$noinline$testIsEmptyEmptyStringWithInline() dead_code_elimination$after_inlining (after)
+ /// CHECK-NOT: LoadString
+
+ /// CHECK-START: boolean Main.$noinline$testIsEmptyEmptyStringWithInline() dead_code_elimination$after_inlining (after)
+ /// CHECK-NOT: ArrayLength
+ private static boolean $noinline$testIsEmptyEmptyStringWithInline() {
+ String str = "";
+ return $inline$returnIsEmpty(str);
+ }
+
+ /// CHECK-START: boolean Main.$noinline$testIsEmptyBssString() constant_folding (before)
+ /// CHECK: <<Const0:i\d+>> IntConstant 0
+ /// CHECK: LoadString load_kind:BssEntry
+ /// CHECK: <<Length:i\d+>> ArrayLength
+ /// CHECK: <<Eq:z\d+>> Equal [<<Length>>,<<Const0>>]
+ /// CHECK: Return [<<Eq>>]
+
+ /// CHECK-START: boolean Main.$noinline$testIsEmptyBssString() constant_folding (after)
+ /// CHECK: <<Const0:i\d+>> IntConstant 0
+ /// CHECK: Return [<<Const0>>]
+
+ // We don't remove LoadString load_kind:BssEntry even if they have no uses, since IsRemovable()
+ // returns false for them.
+ /// CHECK-START: boolean Main.$noinline$testIsEmptyBssString() dead_code_elimination$initial (after)
+ /// CHECK: LoadString load_kind:BssEntry
+
+ /// CHECK-START: boolean Main.$noinline$testIsEmptyBssString() dead_code_elimination$initial (after)
+ /// CHECK-NOT: ArrayLength
+ private static boolean $noinline$testIsEmptyBssString() {
+ String str = "2047-checker-const-string-length";
+ return str.isEmpty();
+ }
+
+ /// CHECK-START: boolean Main.$noinline$testIsEmptyBssStringWithInline() constant_folding$after_inlining (before)
+ /// CHECK: <<Const0:i\d+>> IntConstant 0
+ /// CHECK: LoadString load_kind:BssEntry
+ /// CHECK: <<Length:i\d+>> ArrayLength
+ /// CHECK: <<Eq:z\d+>> Equal [<<Length>>,<<Const0>>]
+ /// CHECK: Return [<<Eq>>]
+
+ /// CHECK-START: boolean Main.$noinline$testIsEmptyBssStringWithInline() constant_folding$after_inlining (after)
+ /// CHECK: <<Const0:i\d+>> IntConstant 0
+ /// CHECK: Return [<<Const0>>]
+
+ // We don't remove LoadString load_kind:BssEntry even if they have no uses, since IsRemovable()
+ // returns false for them.
+ /// CHECK-START: boolean Main.$noinline$testIsEmptyBssStringWithInline() dead_code_elimination$after_inlining (after)
+ /// CHECK: LoadString load_kind:BssEntry
+
+ /// CHECK-START: boolean Main.$noinline$testIsEmptyBssStringWithInline() dead_code_elimination$after_inlining (after)
+ /// CHECK-NOT: ArrayLength
+ private static boolean $noinline$testIsEmptyBssStringWithInline() {
+ String str = "2047-checker-const-string-length";
+ return $inline$returnIsEmpty(str);
+ }
+
+ private static boolean $inline$returnIsEmpty(String str) {
+ return str.isEmpty();
+ }
+
+ static void assertEquals(int expected, int actual) {
+ if (expected != actual) {
+ throw new AssertionError("Expected " + expected + " got " + actual);
+ }
+ }
+
+ static void assertEquals(boolean expected, boolean actual) {
+ if (expected != actual) {
+ throw new AssertionError("Expected " + expected + " got " + actual);
+ }
+ }
+}