Fix typing bug in load store elimination

Test: 530-checker-lse3
Bug: 69365271
Change-Id: I2289bed5fc7b84ee913a2015d113098777dabd4c
diff --git a/compiler/optimizing/load_store_elimination.cc b/compiler/optimizing/load_store_elimination.cc
index f03fffa..88326d3 100644
--- a/compiler/optimizing/load_store_elimination.cc
+++ b/compiler/optimizing/load_store_elimination.cc
@@ -74,6 +74,20 @@
     HGraphVisitor::VisitBasicBlock(block);
   }
 
+  HTypeConversion* AddTypeConversionIfNecessary(HInstruction* instruction,
+                                                HInstruction* value,
+                                                DataType::Type expected_type) {
+    HTypeConversion* type_conversion = nullptr;
+    // Should never add type conversion into boolean value.
+    if (expected_type != DataType::Type::kBool &&
+        !DataType::IsTypeConversionImplicit(value->GetType(), expected_type)) {
+      type_conversion = new (GetGraph()->GetAllocator()) HTypeConversion(
+          expected_type, value, instruction->GetDexPc());
+      instruction->GetBlock()->InsertInstructionBefore(type_conversion, instruction);
+    }
+    return type_conversion;
+  }
+
   // Find an instruction's substitute if it should be removed.
   // Return the same instruction if it should not be removed.
   HInstruction* FindSubstitute(HInstruction* instruction) {
@@ -86,13 +100,59 @@
     return instruction;
   }
 
+  void AddRemovedLoad(HInstruction* load, HInstruction* heap_value) {
+    DCHECK_EQ(FindSubstitute(heap_value), heap_value) <<
+        "Unexpected heap_value that has a substitute " << heap_value->DebugName();
+    removed_loads_.push_back(load);
+    substitute_instructions_for_loads_.push_back(heap_value);
+  }
+
+  // Scan the list of removed loads to see if we can reuse `type_conversion`, if
+  // the other removed load has the same substitute and type and is dominated
+  // by `type_conversioni`.
+  void TryToReuseTypeConversion(HInstruction* type_conversion, size_t index) {
+    size_t size = removed_loads_.size();
+    HInstruction* load = removed_loads_[index];
+    HInstruction* substitute = substitute_instructions_for_loads_[index];
+    for (size_t j = index + 1; j < size; j++) {
+      HInstruction* load2 = removed_loads_[j];
+      HInstruction* substitute2 = substitute_instructions_for_loads_[j];
+      if (load2 == nullptr) {
+        DCHECK(substitute2->IsTypeConversion());
+        continue;
+      }
+      DCHECK(load2->IsInstanceFieldGet() ||
+             load2->IsStaticFieldGet() ||
+             load2->IsArrayGet());
+      DCHECK(substitute2 != nullptr);
+      if (substitute2 == substitute &&
+          load2->GetType() == load->GetType() &&
+          type_conversion->GetBlock()->Dominates(load2->GetBlock()) &&
+          // Don't share across irreducible loop headers.
+          // TODO: can be more fine-grained than this by testing each dominator.
+          (load2->GetBlock() == type_conversion->GetBlock() ||
+           !GetGraph()->HasIrreducibleLoops())) {
+        // The removed_loads_ are added in reverse post order.
+        DCHECK(type_conversion->StrictlyDominates(load2));
+        load2->ReplaceWith(type_conversion);
+        load2->GetBlock()->RemoveInstruction(load2);
+        removed_loads_[j] = nullptr;
+        substitute_instructions_for_loads_[j] = type_conversion;
+      }
+    }
+  }
+
   // Remove recorded instructions that should be eliminated.
   void RemoveInstructions() {
     size_t size = removed_loads_.size();
     DCHECK_EQ(size, substitute_instructions_for_loads_.size());
     for (size_t i = 0; i < size; i++) {
       HInstruction* load = removed_loads_[i];
-      DCHECK(load != nullptr);
+      if (load == nullptr) {
+        // The load has been handled in the scan for type conversion below.
+        DCHECK(substitute_instructions_for_loads_[i]->IsTypeConversion());
+        continue;
+      }
       DCHECK(load->IsInstanceFieldGet() ||
              load->IsStaticFieldGet() ||
              load->IsArrayGet());
@@ -102,7 +162,28 @@
       // a load that has a substitute should not be observed as a heap
       // location value.
       DCHECK_EQ(FindSubstitute(substitute), substitute);
-      load->ReplaceWith(substitute);
+
+      // The load expects to load the heap value as type load->GetType().
+      // However the tracked heap value may not be of that type. An explicit
+      // type conversion may be needed.
+      // There are actually three types involved here:
+      // (1) tracked heap value's type (type A)
+      // (2) heap location (field or element)'s type (type B)
+      // (3) load's type (type C)
+      // We guarantee that type A stored as type B and then fetched out as
+      // type C is the same as casting from type A to type C directly, since
+      // type B and type C will have the same size which is guarenteed in
+      // HInstanceFieldGet/HStaticFieldGet/HArrayGet's SetType().
+      // So we only need one type conversion from type A to type C.
+      HTypeConversion* type_conversion = AddTypeConversionIfNecessary(
+          load, substitute, load->GetType());
+      if (type_conversion != nullptr) {
+        TryToReuseTypeConversion(type_conversion, i);
+        load->ReplaceWith(type_conversion);
+        substitute_instructions_for_loads_[i] = type_conversion;
+      } else {
+        load->ReplaceWith(substitute);
+      }
       load->GetBlock()->RemoveInstruction(load);
     }
 
@@ -338,8 +419,7 @@
     HInstruction* heap_value = heap_values[idx];
     if (heap_value == kDefaultHeapValue) {
       HInstruction* constant = GetDefaultValue(instruction->GetType());
-      removed_loads_.push_back(instruction);
-      substitute_instructions_for_loads_.push_back(constant);
+      AddRemovedLoad(instruction, constant);
       heap_values[idx] = constant;
       return;
     }
@@ -374,8 +454,7 @@
         }
         return;
       }
-      removed_loads_.push_back(instruction);
-      substitute_instructions_for_loads_.push_back(heap_value);
+      AddRemovedLoad(instruction, heap_value);
       TryRemovingNullCheck(instruction);
     }
   }
diff --git a/test/530-checker-lse3/expected.txt b/test/530-checker-lse3/expected.txt
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/test/530-checker-lse3/expected.txt
diff --git a/test/530-checker-lse3/info.txt b/test/530-checker-lse3/info.txt
new file mode 100644
index 0000000..29b4cb8
--- /dev/null
+++ b/test/530-checker-lse3/info.txt
@@ -0,0 +1,4 @@
+Regression test for load store elimination not respecting the loaded type. When
+a wider value is stored in a narrower field and then loaded from that field,
+LSE needs to replace the value to be stored with a type conversion to the
+narrower type.
diff --git a/test/530-checker-lse3/smali/StoreLoad.smali b/test/530-checker-lse3/smali/StoreLoad.smali
new file mode 100644
index 0000000..7fb582c
--- /dev/null
+++ b/test/530-checker-lse3/smali/StoreLoad.smali
@@ -0,0 +1,62 @@
+# Copyright (C) 2017 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.
+
+.class public LStoreLoad;
+
+.super Ljava/lang/Object;
+
+## CHECK-START: int StoreLoad.test(int) load_store_elimination (before)
+## CHECK-DAG:     <<Arg:i\d+>>    ParameterValue
+## CHECK-DAG:                     StaticFieldSet [{{l\d+}},<<Arg>>] field_name:StoreLoad.byteField
+## CHECK-DAG:                     StaticFieldSet [{{l\d+}},<<Arg>>] field_name:StoreLoad.byteField2
+## CHECK-DAG:     <<Val:b\d+>>    StaticFieldGet [{{l\d+}}] field_name:StoreLoad.byteField
+## CHECK-DAG:     <<Val2:b\d+>>   StaticFieldGet [{{l\d+}}] field_name:StoreLoad.byteField2
+## CHECK-DAG:     <<Val3:i\d+>>   Add [<<Val>>,<<Val2>>]
+## CHECK-DAG:                     Return [<<Val3>>]
+
+## CHECK-START: int StoreLoad.test(int) load_store_elimination (after)
+## CHECK-NOT:                     StaticFieldGet
+
+## CHECK-START: int StoreLoad.test(int) load_store_elimination (after)
+## CHECK-DAG:     <<Arg:i\d+>>    ParameterValue
+## CHECK-DAG:                     StaticFieldSet [{{l\d+}},<<Arg>>] field_name:StoreLoad.byteField
+## CHECK-DAG:                     StaticFieldSet [{{l\d+}},<<Arg>>] field_name:StoreLoad.byteField2
+## CHECK-DAG:     <<Conv:b\d+>>   TypeConversion [<<Arg>>]
+## CHECK-DAG:     <<Val3:i\d+>>   Add [<<Conv>>,<<Conv>>]
+## CHECK-DAG:                     Return [<<Val3>>]
+.method public static test(I)I
+    .registers 2
+    sput-byte v1, LStoreLoad;->byteField:B
+    sput-byte v1, LStoreLoad;->byteField2:B
+    sget-byte v0, LStoreLoad;->byteField:B
+    sget-byte v1, LStoreLoad;->byteField2:B
+    add-int/2addr v0, v1
+    return v0
+.end method
+
+## CHECK-START: int StoreLoad.test2(int) load_store_elimination (before)
+## CHECK-DAG:     <<Arg:i\d+>>    ParameterValue
+## CHECK-DAG:                     StaticFieldSet [{{l\d+}},<<Arg>>] field_name:StoreLoad.byteField
+## CHECK-DAG:                     Return [<<Arg>>]
+
+## CHECK-START: int StoreLoad.test2(int) load_store_elimination (after)
+## CHECK-NOT:                     TypeConversion
+.method public static test2(I)I
+    .registers 1
+    sput-byte v0, LStoreLoad;->byteField:B
+    return v0
+.end method
+
+.field public static byteField:B
+.field public static byteField2:B
diff --git a/test/530-checker-lse3/src/Main.java b/test/530-checker-lse3/src/Main.java
new file mode 100644
index 0000000..caef0b3
--- /dev/null
+++ b/test/530-checker-lse3/src/Main.java
@@ -0,0 +1,48 @@
+/*
+ * Copyright (C) 2017 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.
+ */
+
+import java.lang.reflect.Method;
+import java.lang.reflect.Field;
+
+public class Main {
+
+  // Workaround for b/18051191.
+  class InnerClass {}
+
+  public static void main(String[] args) throws Exception {
+    Class<?> c = Class.forName("StoreLoad");
+    Method m = c.getMethod("test", int.class);
+    int result = (Integer)m.invoke(null, 0x12345678);
+    if (result != (0x78 + 0x78)) {
+      throw new Error("Expected 240, got " + result);
+    }
+    m = c.getMethod("test2", int.class);
+    result = (Integer)m.invoke(null, 0xdeadbeef);
+    if (result != 0xdeadbeef) {
+      throw new Error("Expected 0xdeadbeef, got " + result);
+    }
+    Field f = c.getDeclaredField("byteField");
+    byte b = f.getByte(null);
+    if (b != (byte)0xef) {
+      throw new Error("Expected 0xef, got " + b);
+    }
+    f = c.getDeclaredField("byteField2");
+    b = f.getByte(null);
+    if (b != (byte)0x78) {
+      throw new Error("Expected 0xef, got " + b);
+    }
+  }
+}