Enhance removed loads/substitutes in LSE.
LSE does load removal in the end in order to maintain the validity of
all the heap locations collected in the first pass. We should however
proactively retrieve a removed load's substitute as its value. This
simplifies the handling of substitutes by making sure the substitute
itself has no substitute. It also enables some additional optimizations
by using the true heap value for merging/same-value test, etc.
Test: run-test on host.
Change-Id: I26d97e7794d80a141ab02bf446dd07656f5cde1d
diff --git a/compiler/optimizing/load_store_elimination.cc b/compiler/optimizing/load_store_elimination.cc
index 89ad85e..f03fffa 100644
--- a/compiler/optimizing/load_store_elimination.cc
+++ b/compiler/optimizing/load_store_elimination.cc
@@ -74,6 +74,18 @@
HGraphVisitor::VisitBasicBlock(block);
}
+ // Find an instruction's substitute if it should be removed.
+ // Return the same instruction if it should not be removed.
+ HInstruction* FindSubstitute(HInstruction* instruction) {
+ size_t size = removed_loads_.size();
+ for (size_t i = 0; i < size; i++) {
+ if (removed_loads_[i] == instruction) {
+ return substitute_instructions_for_loads_[i];
+ }
+ }
+ return instruction;
+ }
+
// Remove recorded instructions that should be eliminated.
void RemoveInstructions() {
size_t size = removed_loads_.size();
@@ -86,12 +98,10 @@
load->IsArrayGet());
HInstruction* substitute = substitute_instructions_for_loads_[i];
DCHECK(substitute != nullptr);
- // Keep tracing substitute till one that's not removed.
- HInstruction* sub_sub = FindSubstitute(substitute);
- while (sub_sub != substitute) {
- substitute = sub_sub;
- sub_sub = FindSubstitute(substitute);
- }
+ // We proactively retrieve the substitute for a removed load, so
+ // a load that has a substitute should not be observed as a heap
+ // location value.
+ DCHECK_EQ(FindSubstitute(substitute), substitute);
load->ReplaceWith(substitute);
load->GetBlock()->RemoveInstruction(load);
}
@@ -342,6 +352,8 @@
DCHECK(ref_info->IsSingleton());
// Get the real heap value of the store.
heap_value = heap_value->IsInstanceFieldSet() ? store->InputAt(1) : store->InputAt(2);
+ // heap_value may already have a substitute.
+ heap_value = FindSubstitute(heap_value);
}
}
if (heap_value == kUnknownHeapValue) {
@@ -385,6 +397,8 @@
size_t vector_length,
int16_t declaring_class_def_index,
HInstruction* value) {
+ // value may already have a substitute.
+ value = FindSubstitute(value);
HInstruction* original_ref = heap_location_collector_.HuntForOriginalReference(ref);
ReferenceInfo* ref_info = heap_location_collector_.FindReferenceInfoOf(original_ref);
size_t idx = heap_location_collector_.FindHeapLocationIndex(
@@ -679,18 +693,6 @@
}
}
- // Find an instruction's substitute if it should be removed.
- // Return the same instruction if it should not be removed.
- HInstruction* FindSubstitute(HInstruction* instruction) {
- size_t size = removed_loads_.size();
- for (size_t i = 0; i < size; i++) {
- if (removed_loads_[i] == instruction) {
- return substitute_instructions_for_loads_[i];
- }
- }
- return instruction;
- }
-
const HeapLocationCollector& heap_location_collector_;
const SideEffectsAnalysis& side_effects_;
diff --git a/test/530-checker-lse/src/Main.java b/test/530-checker-lse/src/Main.java
index c4cc3b0..f6332b5 100644
--- a/test/530-checker-lse/src/Main.java
+++ b/test/530-checker-lse/src/Main.java
@@ -999,6 +999,24 @@
return res;
}
+ /// CHECK-START: void Main.testStoreSameValue() load_store_elimination (before)
+ /// CHECK: NewArray
+ /// CHECK: ArrayGet
+ /// CHECK: ArraySet
+
+ /// CHECK-START: void Main.testStoreSameValue() load_store_elimination (after)
+ /// CHECK: NewArray
+ /// CHECK-NOT: ArrayGet
+ /// CHECK-NOT: ArraySet
+ private static void testStoreSameValue() {
+ Object[] array = new Object[2];
+ sArray = array;
+ Object obj = array[0];
+ array[1] = obj; // store the same value as the defaut value.
+ }
+
+ static Object[] sArray;
+
static void assertIntEquals(int result, int expected) {
if (expected != result) {
throw new Error("Expected: " + expected + ", found: " + result);
diff --git a/test/532-checker-nonnull-arrayset/src/Main.java b/test/532-checker-nonnull-arrayset/src/Main.java
index 61c9e88..f6f877c 100644
--- a/test/532-checker-nonnull-arrayset/src/Main.java
+++ b/test/532-checker-nonnull-arrayset/src/Main.java
@@ -29,9 +29,7 @@
/// CHECK-NOT: test
/// CHECK: ReturnVoid
public static void test() {
- Object[] array = new Object[2];
- // Storing to static to avoid some lse optimization.
- sArray = array;
+ Object[] array = sArray;
Object nonNull = array[0];
nonNull.getClass(); // Ensure nonNull has an implicit null check.
array[1] = nonNull;