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

7 files changed, 259 insertions, 12 deletions

diff --git a/compiler/optimizing/constant_folding.cc b/compiler/optimizing/constant_folding.cc
index bd9c899770..b737fb396f 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 @@ class HConstantFoldingVisitor : public HGraphDelegateVisitor {
   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::VisitBinaryOperation(HBinaryOperation* inst) {
   }
 }
 
-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::VisitIf(HIf* inst) {
   }
 }
 
+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 1a5e9044b8..73ac3ceb81 100644
--- a/compiler/optimizing/constant_folding.h
+++ b/compiler/optimizing/constant_folding.h
@@ -41,7 +41,9 @@ namespace art HIDDEN {
  */
 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 12ca30fb1b..b772fbbbb6 100644
--- a/compiler/optimizing/instruction_simplifier.cc
+++ b/compiler/optimizing/instruction_simplifier.cc
@@ -1117,6 +1117,10 @@ void InstructionSimplifierVisitor::VisitIf(HIf* instruction) {
   }
 }
 
+// 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 0000000000..e69de29bb2
--- /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 0000000000..e69de29bb2
--- /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 0000000000..61e987f8fb
--- /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 0000000000..0130943cda
--- /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);
+        }
+    }
+}