String Compression for MIPS32 and MIPS64

Changes on intrinsics and Code Generation on MIPS32 and MIPS64 for
string compression feature.

Testing is done with STRING_COMPRESSION_ENABLED = true (in libcore),
mirror::kUseStringCompression = true and STRING_COMPRESSION_FEATURE set
to 1.

Test: booted MIPS32 and MIPS64 in QEMU
Test: mma test-art-target-run-test on CI20 (MIPS32R2)
Test: mma test-art-target-run-test in QEMU (MIPS64R6)

Change-Id: If50a6b6c0792bfa34d4fdff6bf2c7542211d2689

4 files changed, 197 insertions, 27 deletions

diff --git a/compiler/optimizing/code_generator_mips.cc b/compiler/optimizing/code_generator_mips.cc
index 0677dad078..c9dde7cc55 100644
--- a/compiler/optimizing/code_generator_mips.cc
+++ b/compiler/optimizing/code_generator_mips.cc
@@ -1914,6 +1914,8 @@ void InstructionCodeGeneratorMIPS::VisitArrayGet(HArrayGet* instruction) {
   auto null_checker = GetImplicitNullChecker(instruction);
 
   Primitive::Type type = instruction->GetType();
+  const bool maybe_compressed_char_at = mirror::kUseStringCompression &&
+                                        instruction->IsStringCharAt();
   switch (type) {
     case Primitive::kPrimBoolean: {
       Register out = locations->Out().AsRegister<Register>();
@@ -1957,14 +1959,54 @@ void InstructionCodeGeneratorMIPS::VisitArrayGet(HArrayGet* instruction) {
 
     case Primitive::kPrimChar: {
       Register out = locations->Out().AsRegister<Register>();
+      if (maybe_compressed_char_at) {
+        uint32_t count_offset = mirror::String::CountOffset().Uint32Value();
+        __ LoadFromOffset(kLoadWord, TMP, obj, count_offset, null_checker);
+        __ Sll(TMP, TMP, 31);    // Extract compression flag into the most significant bit of TMP.
+        static_assert(static_cast<uint32_t>(mirror::StringCompressionFlag::kCompressed) == 0u,
+                      "Expecting 0=compressed, 1=uncompressed");
+      }
       if (index.IsConstant()) {
-        size_t offset =
-            (index.GetConstant()->AsIntConstant()->GetValue() << TIMES_2) + data_offset;
-        __ LoadFromOffset(kLoadUnsignedHalfword, out, obj, offset, null_checker);
+        int32_t const_index = index.GetConstant()->AsIntConstant()->GetValue();
+        if (maybe_compressed_char_at) {
+          MipsLabel uncompressed_load, done;
+          __ Bnez(TMP, &uncompressed_load);
+          __ LoadFromOffset(kLoadUnsignedByte,
+                            out,
+                            obj,
+                            data_offset + (const_index << TIMES_1));
+          __ B(&done);
+          __ Bind(&uncompressed_load);
+          __ LoadFromOffset(kLoadUnsignedHalfword,
+                            out,
+                            obj,
+                            data_offset + (const_index << TIMES_2));
+          __ Bind(&done);
+        } else {
+          __ LoadFromOffset(kLoadUnsignedHalfword,
+                            out,
+                            obj,
+                            data_offset + (const_index << TIMES_2),
+                            null_checker);
+        }
       } else {
-        __ Sll(TMP, index.AsRegister<Register>(), TIMES_2);
-        __ Addu(TMP, obj, TMP);
-        __ LoadFromOffset(kLoadUnsignedHalfword, out, TMP, data_offset, null_checker);
+        Register index_reg = index.AsRegister<Register>();
+        if (maybe_compressed_char_at) {
+          MipsLabel uncompressed_load, done;
+          __ Bnez(TMP, &uncompressed_load);
+          __ Addu(TMP, obj, index_reg);
+          __ LoadFromOffset(kLoadUnsignedByte, out, TMP, data_offset);
+          __ B(&done);
+          __ Bind(&uncompressed_load);
+          __ Sll(TMP, index_reg, TIMES_2);
+          __ Addu(TMP, obj, TMP);
+          __ LoadFromOffset(kLoadUnsignedHalfword, out, TMP, data_offset);
+          __ Bind(&done);
+        } else {
+          __ Sll(TMP, index_reg, TIMES_2);
+          __ Addu(TMP, obj, TMP);
+          __ LoadFromOffset(kLoadUnsignedHalfword, out, TMP, data_offset, null_checker);
+        }
       }
       break;
     }
@@ -2046,6 +2088,10 @@ void InstructionCodeGeneratorMIPS::VisitArrayLength(HArrayLength* instruction) {
   Register out = locations->Out().AsRegister<Register>();
   __ LoadFromOffset(kLoadWord, out, obj, offset);
   codegen_->MaybeRecordImplicitNullCheck(instruction);
+  // Mask out compression flag from String's array length.
+  if (mirror::kUseStringCompression && instruction->IsStringLength()) {
+    __ Srl(out, out, 1u);
+  }
 }
 
 Location LocationsBuilderMIPS::RegisterOrZeroConstant(HInstruction* instruction) {
diff --git a/compiler/optimizing/code_generator_mips64.cc b/compiler/optimizing/code_generator_mips64.cc
index 4c8dabfede..5be0da4011 100644
--- a/compiler/optimizing/code_generator_mips64.cc
+++ b/compiler/optimizing/code_generator_mips64.cc
@@ -1490,6 +1490,8 @@ void InstructionCodeGeneratorMIPS64::VisitArrayGet(HArrayGet* instruction) {
   uint32_t data_offset = CodeGenerator::GetArrayDataOffset(instruction);
 
   Primitive::Type type = instruction->GetType();
+  const bool maybe_compressed_char_at = mirror::kUseStringCompression &&
+                                        instruction->IsStringCharAt();
   switch (type) {
     case Primitive::kPrimBoolean: {
       GpuRegister out = locations->Out().AsRegister<GpuRegister>();
@@ -1533,14 +1535,54 @@ void InstructionCodeGeneratorMIPS64::VisitArrayGet(HArrayGet* instruction) {
 
     case Primitive::kPrimChar: {
       GpuRegister out = locations->Out().AsRegister<GpuRegister>();
+      if (maybe_compressed_char_at) {
+        uint32_t count_offset = mirror::String::CountOffset().Uint32Value();
+        __ LoadFromOffset(kLoadWord, TMP, obj, count_offset);
+        codegen_->MaybeRecordImplicitNullCheck(instruction);
+        __ Dext(TMP, TMP, 0, 1);
+        static_assert(static_cast<uint32_t>(mirror::StringCompressionFlag::kCompressed) == 0u,
+                      "Expecting 0=compressed, 1=uncompressed");
+      }
       if (index.IsConstant()) {
-        size_t offset =
-            (index.GetConstant()->AsIntConstant()->GetValue() << TIMES_2) + data_offset;
-        __ LoadFromOffset(kLoadUnsignedHalfword, out, obj, offset);
+        int32_t const_index = index.GetConstant()->AsIntConstant()->GetValue();
+        if (maybe_compressed_char_at) {
+          Mips64Label uncompressed_load, done;
+          __ Bnezc(TMP, &uncompressed_load);
+          __ LoadFromOffset(kLoadUnsignedByte,
+                            out,
+                            obj,
+                            data_offset + (const_index << TIMES_1));
+          __ Bc(&done);
+          __ Bind(&uncompressed_load);
+          __ LoadFromOffset(kLoadUnsignedHalfword,
+                            out,
+                            obj,
+                            data_offset + (const_index << TIMES_2));
+          __ Bind(&done);
+        } else {
+          __ LoadFromOffset(kLoadUnsignedHalfword,
+                            out,
+                            obj,
+                            data_offset + (const_index << TIMES_2));
+        }
       } else {
-        __ Dsll(TMP, index.AsRegister<GpuRegister>(), TIMES_2);
-        __ Daddu(TMP, obj, TMP);
-        __ LoadFromOffset(kLoadUnsignedHalfword, out, TMP, data_offset);
+        GpuRegister index_reg = index.AsRegister<GpuRegister>();
+        if (maybe_compressed_char_at) {
+          Mips64Label uncompressed_load, done;
+          __ Bnezc(TMP, &uncompressed_load);
+          __ Daddu(TMP, obj, index_reg);
+          __ LoadFromOffset(kLoadUnsignedByte, out, TMP, data_offset);
+          __ Bc(&done);
+          __ Bind(&uncompressed_load);
+          __ Dsll(TMP, index_reg, TIMES_2);
+          __ Daddu(TMP, obj, TMP);
+          __ LoadFromOffset(kLoadUnsignedHalfword, out, TMP, data_offset);
+          __ Bind(&done);
+        } else {
+          __ Dsll(TMP, index_reg, TIMES_2);
+          __ Daddu(TMP, obj, TMP);
+          __ LoadFromOffset(kLoadUnsignedHalfword, out, TMP, data_offset);
+        }
       }
       break;
     }
@@ -1608,7 +1650,9 @@ void InstructionCodeGeneratorMIPS64::VisitArrayGet(HArrayGet* instruction) {
       LOG(FATAL) << "Unreachable type " << instruction->GetType();
       UNREACHABLE();
   }
-  codegen_->MaybeRecordImplicitNullCheck(instruction);
+  if (!maybe_compressed_char_at) {
+    codegen_->MaybeRecordImplicitNullCheck(instruction);
+  }
 }
 
 void LocationsBuilderMIPS64::VisitArrayLength(HArrayLength* instruction) {
@@ -1624,6 +1668,10 @@ void InstructionCodeGeneratorMIPS64::VisitArrayLength(HArrayLength* instruction)
   GpuRegister out = locations->Out().AsRegister<GpuRegister>();
   __ LoadFromOffset(kLoadWord, out, obj, offset);
   codegen_->MaybeRecordImplicitNullCheck(instruction);
+  // Mask out compression flag from String's array length.
+  if (mirror::kUseStringCompression && instruction->IsStringLength()) {
+    __ Srl(out, out, 1u);
+  }
 }
 
 void LocationsBuilderMIPS64::VisitArraySet(HArraySet* instruction) {
diff --git a/compiler/optimizing/intrinsics_mips.cc b/compiler/optimizing/intrinsics_mips.cc
index 6cf9b83d44..64a68403e9 100644
--- a/compiler/optimizing/intrinsics_mips.cc
+++ b/compiler/optimizing/intrinsics_mips.cc
@@ -2004,31 +2004,48 @@ void IntrinsicCodeGeneratorMIPS::VisitStringEquals(HInvoke* invoke) {
   __ Lw(temp2, arg, class_offset);
   __ Bne(temp1, temp2, &return_false);
 
-  // Load lengths of this and argument strings.
+  // Load `count` fields of this and argument strings.
   __ Lw(temp1, str, count_offset);
   __ Lw(temp2, arg, count_offset);
-  // Check if lengths are equal, return false if they're not.
+  // Check if `count` fields are equal, return false if they're not.
+  // Also compares the compression style, if differs return false.
   __ Bne(temp1, temp2, &return_false);
-  // Return true if both strings are empty.
+  // Return true if both strings are empty. Even with string compression `count == 0` means empty.
+  static_assert(static_cast<uint32_t>(mirror::StringCompressionFlag::kCompressed) == 0u,
+                "Expecting 0=compressed, 1=uncompressed");
   __ Beqz(temp1, &return_true);
 
   // Don't overwrite input registers
   __ Move(TMP, str);
   __ Move(temp3, arg);
 
-  // Assertions that must hold in order to compare strings 2 characters at a time.
+  // Assertions that must hold in order to compare strings 4 bytes at a time.
   DCHECK_ALIGNED(value_offset, 4);
   static_assert(IsAligned<4>(kObjectAlignment), "String of odd length is not zero padded");
 
-  // Loop to compare strings 2 characters at a time starting at the beginning of the string.
-  // Ok to do this because strings are zero-padded.
+  // For string compression, calculate the number of bytes to compare (not chars).
+  if (mirror::kUseStringCompression) {
+    // Extract compression flag.
+    if (IsR2OrNewer()) {
+      __ Ext(temp2, temp1, 0, 1);
+    } else {
+      __ Sll(temp2, temp1, 31);
+      __ Srl(temp2, temp2, 31);
+    }
+    __ Srl(temp1, temp1, 1);             // Extract length.
+    __ Sllv(temp1, temp1, temp2);        // Double the byte count if uncompressed.
+  }
+
+  // Loop to compare strings 4 bytes at a time starting at the beginning of the string.
+  // Ok to do this because strings are zero-padded to kObjectAlignment.
   __ Bind(&loop);
   __ Lw(out, TMP, value_offset);
   __ Lw(temp2, temp3, value_offset);
   __ Bne(out, temp2, &return_false);
   __ Addiu(TMP, TMP, 4);
   __ Addiu(temp3, temp3, 4);
-  __ Addiu(temp1, temp1, -2);
+  // With string compression, we have compared 4 bytes, otherwise 2 chars.
+  __ Addiu(temp1, temp1, mirror::kUseStringCompression ? -4 : -2);
   __ Bgtz(temp1, &loop);
 
   // Return true and exit the function.
@@ -2578,6 +2595,30 @@ void IntrinsicCodeGeneratorMIPS::VisitStringGetCharsNoCheck(HInvoke* invoke) {
     __ Addu(dstPtr, dstPtr, AT);
   }
 
+  if (mirror::kUseStringCompression) {
+    MipsLabel uncompressed_copy, compressed_loop;
+    const uint32_t count_offset = mirror::String::CountOffset().Uint32Value();
+    // Load count field and extract compression flag.
+    __ LoadFromOffset(kLoadWord, TMP, srcObj, count_offset);
+    __ Sll(TMP, TMP, 31);
+
+    // If string is uncompressed, use memcpy() path.
+    __ Bnez(TMP, &uncompressed_copy);
+
+    // Copy loop for compressed src, copying 1 character (8-bit) to (16-bit) at a time.
+    __ Addu(srcPtr, srcObj, srcBegin);
+    __ Bind(&compressed_loop);
+    __ LoadFromOffset(kLoadUnsignedByte, TMP, srcPtr, value_offset);
+    __ StoreToOffset(kStoreHalfword, TMP, dstPtr, 0);
+    __ Addiu(numChrs, numChrs, -1);
+    __ Addiu(srcPtr, srcPtr, 1);
+    __ Addiu(dstPtr, dstPtr, 2);
+    __ Bnez(numChrs, &compressed_loop);
+
+    __ B(&done);
+    __ Bind(&uncompressed_copy);
+  }
+
   // Calculate source address.
   __ Addiu(srcPtr, srcObj, value_offset);
   if (IsR6()) {
diff --git a/compiler/optimizing/intrinsics_mips64.cc b/compiler/optimizing/intrinsics_mips64.cc
index 00a1fa11bb..3888828722 100644
--- a/compiler/optimizing/intrinsics_mips64.cc
+++ b/compiler/optimizing/intrinsics_mips64.cc
@@ -1607,31 +1607,42 @@ void IntrinsicCodeGeneratorMIPS64::VisitStringEquals(HInvoke* invoke) {
   __ Lw(temp2, arg, class_offset);
   __ Bnec(temp1, temp2, &return_false);
 
-  // Load lengths of this and argument strings.
+  // Load `count` fields of this and argument strings.
   __ Lw(temp1, str, count_offset);
   __ Lw(temp2, arg, count_offset);
-  // Check if lengths are equal, return false if they're not.
+  // Check if `count` fields are equal, return false if they're not.
+  // Also compares the compression style, if differs return false.
   __ Bnec(temp1, temp2, &return_false);
-  // Return true if both strings are empty.
+  // Return true if both strings are empty. Even with string compression `count == 0` means empty.
+  static_assert(static_cast<uint32_t>(mirror::StringCompressionFlag::kCompressed) == 0u,
+                "Expecting 0=compressed, 1=uncompressed");
   __ Beqzc(temp1, &return_true);
 
   // Don't overwrite input registers
   __ Move(TMP, str);
   __ Move(temp3, arg);
 
-  // Assertions that must hold in order to compare strings 4 characters at a time.
+  // Assertions that must hold in order to compare strings 8 bytes at a time.
   DCHECK_ALIGNED(value_offset, 8);
   static_assert(IsAligned<8>(kObjectAlignment), "String of odd length is not zero padded");
 
-  // Loop to compare strings 4 characters at a time starting at the beginning of the string.
-  // Ok to do this because strings are zero-padded to be 8-byte aligned.
+  if (mirror::kUseStringCompression) {
+    // For string compression, calculate the number of bytes to compare (not chars).
+    __ Dext(temp2, temp1, 0, 1);         // Extract compression flag.
+    __ Srl(temp1, temp1, 1);             // Extract length.
+    __ Sllv(temp1, temp1, temp2);        // Double the byte count if uncompressed.
+  }
+
+  // Loop to compare strings 8 bytes at a time starting at the beginning of the string.
+  // Ok to do this because strings are zero-padded to kObjectAlignment.
   __ Bind(&loop);
   __ Ld(out, TMP, value_offset);
   __ Ld(temp2, temp3, value_offset);
   __ Bnec(out, temp2, &return_false);
   __ Daddiu(TMP, TMP, 8);
   __ Daddiu(temp3, temp3, 8);
-  __ Addiu(temp1, temp1, -4);
+  // With string compression, we have compared 8 bytes, otherwise 4 chars.
+  __ Addiu(temp1, temp1, mirror::kUseStringCompression ? -8 : -4);
   __ Bgtzc(temp1, &loop);
 
   // Return true and exit the function.
@@ -1912,6 +1923,30 @@ void IntrinsicCodeGeneratorMIPS64::VisitStringGetCharsNoCheck(HInvoke* invoke) {
   __ Daddiu(dstPtr, dstObj, data_offset);
   __ Dlsa(dstPtr, dstBegin, dstPtr, char_shift);
 
+  if (mirror::kUseStringCompression) {
+    Mips64Label uncompressed_copy, compressed_loop;
+    const uint32_t count_offset = mirror::String::CountOffset().Uint32Value();
+    // Load count field and extract compression flag.
+    __ LoadFromOffset(kLoadWord, TMP, srcObj, count_offset);
+    __ Dext(TMP, TMP, 0, 1);
+
+    // If string is uncompressed, use memcpy() path.
+    __ Bnezc(TMP, &uncompressed_copy);
+
+    // Copy loop for compressed src, copying 1 character (8-bit) to (16-bit) at a time.
+    __ Daddu(srcPtr, srcObj, srcBegin);
+    __ Bind(&compressed_loop);
+    __ LoadFromOffset(kLoadUnsignedByte, TMP, srcPtr, value_offset);
+    __ StoreToOffset(kStoreHalfword, TMP, dstPtr, 0);
+    __ Daddiu(numChrs, numChrs, -1);
+    __ Daddiu(srcPtr, srcPtr, 1);
+    __ Daddiu(dstPtr, dstPtr, 2);
+    __ Bnezc(numChrs, &compressed_loop);
+
+    __ Bc(&done);
+    __ Bind(&uncompressed_copy);
+  }
+
   // Calculate source address.
   __ Daddiu(srcPtr, srcObj, value_offset);
   __ Dlsa(srcPtr, srcBegin, srcPtr, char_shift);