Fix LSA hunt for original reference bug.
Fix a bug in LSA where it doesn't take IntermediateAddress
into account during hunting for original reference.
In following example, original reference i0 can be transformed
by NullCheck, BoundType, IntermediateAddress, etc.
i0 NewArray
i1 HInstruction(i0)
i2 ArrayGet(i1, index)
Test: test-art-host
Test: test-art-target
Test: load_store_analysis_test
Test: 706-checker-scheduler
Change-Id: I162dd8a86fcd31daee3517357c6af638c950b31b
diff --git a/compiler/optimizing/code_generator_mips.cc b/compiler/optimizing/code_generator_mips.cc
index 2f65e8c..77e50f3 100644
--- a/compiler/optimizing/code_generator_mips.cc
+++ b/compiler/optimizing/code_generator_mips.cc
@@ -9243,6 +9243,16 @@
}
}
+void LocationsBuilderMIPS::VisitIntermediateAddress(HIntermediateAddress* instruction
+ ATTRIBUTE_UNUSED) {
+ LOG(FATAL) << "Unreachable";
+}
+
+void InstructionCodeGeneratorMIPS::VisitIntermediateAddress(HIntermediateAddress* instruction
+ ATTRIBUTE_UNUSED) {
+ LOG(FATAL) << "Unreachable";
+}
+
#undef __
#undef QUICK_ENTRY_POINT
diff --git a/compiler/optimizing/code_generator_mips64.cc b/compiler/optimizing/code_generator_mips64.cc
index 6cbfa14..ac80326 100644
--- a/compiler/optimizing/code_generator_mips64.cc
+++ b/compiler/optimizing/code_generator_mips64.cc
@@ -7144,5 +7144,15 @@
}
}
+void LocationsBuilderMIPS64::VisitIntermediateAddress(HIntermediateAddress* instruction
+ ATTRIBUTE_UNUSED) {
+ LOG(FATAL) << "Unreachable";
+}
+
+void InstructionCodeGeneratorMIPS64::VisitIntermediateAddress(HIntermediateAddress* instruction
+ ATTRIBUTE_UNUSED) {
+ LOG(FATAL) << "Unreachable";
+}
+
} // namespace mips64
} // namespace art
diff --git a/compiler/optimizing/code_generator_x86.cc b/compiler/optimizing/code_generator_x86.cc
index 44614e1..2ab4359 100644
--- a/compiler/optimizing/code_generator_x86.cc
+++ b/compiler/optimizing/code_generator_x86.cc
@@ -7824,6 +7824,16 @@
}
}
+void LocationsBuilderX86::VisitIntermediateAddress(HIntermediateAddress* instruction
+ ATTRIBUTE_UNUSED) {
+ LOG(FATAL) << "Unreachable";
+}
+
+void InstructionCodeGeneratorX86::VisitIntermediateAddress(HIntermediateAddress* instruction
+ ATTRIBUTE_UNUSED) {
+ LOG(FATAL) << "Unreachable";
+}
+
#undef __
} // namespace x86
diff --git a/compiler/optimizing/code_generator_x86_64.cc b/compiler/optimizing/code_generator_x86_64.cc
index 259bb4a..4c73c65 100644
--- a/compiler/optimizing/code_generator_x86_64.cc
+++ b/compiler/optimizing/code_generator_x86_64.cc
@@ -6833,6 +6833,16 @@
__ jmp(temp_reg);
}
+void LocationsBuilderX86_64::VisitIntermediateAddress(HIntermediateAddress* instruction
+ ATTRIBUTE_UNUSED) {
+ LOG(FATAL) << "Unreachable";
+}
+
+void InstructionCodeGeneratorX86_64::VisitIntermediateAddress(HIntermediateAddress* instruction
+ ATTRIBUTE_UNUSED) {
+ LOG(FATAL) << "Unreachable";
+}
+
void CodeGeneratorX86_64::Load32BitValue(CpuRegister dest, int32_t value) {
if (value == 0) {
__ xorl(dest, dest);
diff --git a/compiler/optimizing/load_store_analysis.h b/compiler/optimizing/load_store_analysis.h
index 5940ee7..5a1df45 100644
--- a/compiler/optimizing/load_store_analysis.h
+++ b/compiler/optimizing/load_store_analysis.h
@@ -196,8 +196,12 @@
}
HInstruction* HuntForOriginalReference(HInstruction* ref) const {
+ // An original reference can be transformed by instructions like:
+ // i0 NewArray
+ // i1 HInstruction(i0) <-- NullCheck, BoundType, IntermediateAddress.
+ // i2 ArrayGet(i1, index)
DCHECK(ref != nullptr);
- while (ref->IsNullCheck() || ref->IsBoundType()) {
+ while (ref->IsNullCheck() || ref->IsBoundType() || ref->IsIntermediateAddress()) {
ref = ref->InputAt(0);
}
return ref;
diff --git a/compiler/optimizing/load_store_analysis_test.cc b/compiler/optimizing/load_store_analysis_test.cc
index 86696d0..b41e1e4 100644
--- a/compiler/optimizing/load_store_analysis_test.cc
+++ b/compiler/optimizing/load_store_analysis_test.cc
@@ -389,4 +389,68 @@
ASSERT_FALSE(heap_location_collector.MayAlias(loc1, loc2));
}
+TEST_F(LoadStoreAnalysisTest, TestHuntOriginalRef) {
+ HBasicBlock* entry = new (GetAllocator()) HBasicBlock(graph_);
+ graph_->AddBlock(entry);
+ graph_->SetEntryBlock(entry);
+
+ // Different ways where orignal array reference are transformed & passed to ArrayGet.
+ // ParameterValue --> ArrayGet
+ // ParameterValue --> BoundType --> ArrayGet
+ // ParameterValue --> BoundType --> NullCheck --> ArrayGet
+ // ParameterValue --> BoundType --> NullCheck --> IntermediateAddress --> ArrayGet
+ HInstruction* c1 = graph_->GetIntConstant(1);
+ HInstruction* array = new (GetAllocator()) HParameterValue(graph_->GetDexFile(),
+ dex::TypeIndex(0),
+ 0,
+ DataType::Type::kReference);
+ HInstruction* array_get1 = new (GetAllocator()) HArrayGet(array,
+ c1,
+ DataType::Type::kInt32,
+ 0);
+
+ HInstruction* bound_type = new (GetAllocator()) HBoundType(array);
+ HInstruction* array_get2 = new (GetAllocator()) HArrayGet(bound_type,
+ c1,
+ DataType::Type::kInt32,
+ 0);
+
+ HInstruction* null_check = new (GetAllocator()) HNullCheck(bound_type, 0);
+ HInstruction* array_get3 = new (GetAllocator()) HArrayGet(null_check,
+ c1,
+ DataType::Type::kInt32,
+ 0);
+
+ HInstruction* inter_addr = new (GetAllocator()) HIntermediateAddress(null_check, c1, 0);
+ HInstruction* array_get4 = new (GetAllocator()) HArrayGet(inter_addr,
+ c1,
+ DataType::Type::kInt32,
+ 0);
+ entry->AddInstruction(array);
+ entry->AddInstruction(array_get1);
+ entry->AddInstruction(bound_type);
+ entry->AddInstruction(array_get2);
+ entry->AddInstruction(null_check);
+ entry->AddInstruction(array_get3);
+ entry->AddInstruction(inter_addr);
+ entry->AddInstruction(array_get4);
+
+ HeapLocationCollector heap_location_collector(graph_);
+ heap_location_collector.VisitBasicBlock(entry);
+
+ // Test that the HeapLocationCollector should be able to tell
+ // that there is only ONE array location, no matter how many
+ // times the original reference has been transformed by BoundType,
+ // NullCheck, IntermediateAddress, etc.
+ ASSERT_EQ(heap_location_collector.GetNumberOfHeapLocations(), 1U);
+ size_t loc1 = heap_location_collector.GetArrayAccessHeapLocation(array, c1);
+ size_t loc2 = heap_location_collector.GetArrayAccessHeapLocation(bound_type, c1);
+ size_t loc3 = heap_location_collector.GetArrayAccessHeapLocation(null_check, c1);
+ size_t loc4 = heap_location_collector.GetArrayAccessHeapLocation(inter_addr, c1);
+ ASSERT_TRUE(loc1 != HeapLocationCollector::kHeapLocationNotFound);
+ ASSERT_EQ(loc1, loc2);
+ ASSERT_EQ(loc1, loc3);
+ ASSERT_EQ(loc1, loc4);
+}
+
} // namespace art
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index 88609ea..29c78a1 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -1334,6 +1334,7 @@
M(InstanceFieldSet, Instruction) \
M(InstanceOf, Instruction) \
M(IntConstant, Constant) \
+ M(IntermediateAddress, Instruction) \
M(InvokeUnresolved, Invoke) \
M(InvokeInterface, Invoke) \
M(InvokeStaticOrDirect, Invoke) \
@@ -1418,7 +1419,6 @@
M(BitwiseNegatedRight, Instruction) \
M(DataProcWithShifterOp, Instruction) \
M(MultiplyAccumulate, Instruction) \
- M(IntermediateAddress, Instruction) \
M(IntermediateAddressIndex, Instruction)
#endif
@@ -6966,6 +6966,38 @@
DISALLOW_COPY_AND_ASSIGN(HParallelMove);
};
+// This instruction computes an intermediate address pointing in the 'middle' of an object. The
+// result pointer cannot be handled by GC, so extra care is taken to make sure that this value is
+// never used across anything that can trigger GC.
+// The result of this instruction is not a pointer in the sense of `DataType::Type::kreference`.
+// So we represent it by the type `DataType::Type::kInt`.
+class HIntermediateAddress FINAL : public HExpression<2> {
+ public:
+ HIntermediateAddress(HInstruction* base_address, HInstruction* offset, uint32_t dex_pc)
+ : HExpression(DataType::Type::kInt32, SideEffects::DependsOnGC(), dex_pc) {
+ DCHECK_EQ(DataType::Size(DataType::Type::kInt32),
+ DataType::Size(DataType::Type::kReference))
+ << "kPrimInt and kPrimNot have different sizes.";
+ SetRawInputAt(0, base_address);
+ SetRawInputAt(1, offset);
+ }
+
+ bool CanBeMoved() const OVERRIDE { return true; }
+ bool InstructionDataEquals(const HInstruction* other ATTRIBUTE_UNUSED) const OVERRIDE {
+ return true;
+ }
+ bool IsActualObject() const OVERRIDE { return false; }
+
+ HInstruction* GetBaseAddress() const { return InputAt(0); }
+ HInstruction* GetOffset() const { return InputAt(1); }
+
+ DECLARE_INSTRUCTION(IntermediateAddress);
+
+ private:
+ DISALLOW_COPY_AND_ASSIGN(HIntermediateAddress);
+};
+
+
} // namespace art
#include "nodes_vector.h"
diff --git a/compiler/optimizing/nodes_shared.h b/compiler/optimizing/nodes_shared.h
index 14cbf85..7b4f5f7 100644
--- a/compiler/optimizing/nodes_shared.h
+++ b/compiler/optimizing/nodes_shared.h
@@ -118,38 +118,6 @@
DISALLOW_COPY_AND_ASSIGN(HBitwiseNegatedRight);
};
-
-// This instruction computes an intermediate address pointing in the 'middle' of an object. The
-// result pointer cannot be handled by GC, so extra care is taken to make sure that this value is
-// never used across anything that can trigger GC.
-// The result of this instruction is not a pointer in the sense of `DataType::Type::kreference`.
-// So we represent it by the type `DataType::Type::kInt`.
-class HIntermediateAddress FINAL : public HExpression<2> {
- public:
- HIntermediateAddress(HInstruction* base_address, HInstruction* offset, uint32_t dex_pc)
- : HExpression(DataType::Type::kInt32, SideEffects::DependsOnGC(), dex_pc) {
- DCHECK_EQ(DataType::Size(DataType::Type::kInt32),
- DataType::Size(DataType::Type::kReference))
- << "kPrimInt and kPrimNot have different sizes.";
- SetRawInputAt(0, base_address);
- SetRawInputAt(1, offset);
- }
-
- bool CanBeMoved() const OVERRIDE { return true; }
- bool InstructionDataEquals(const HInstruction* other ATTRIBUTE_UNUSED) const OVERRIDE {
- return true;
- }
- bool IsActualObject() const OVERRIDE { return false; }
-
- HInstruction* GetBaseAddress() const { return InputAt(0); }
- HInstruction* GetOffset() const { return InputAt(1); }
-
- DECLARE_INSTRUCTION(IntermediateAddress);
-
- private:
- DISALLOW_COPY_AND_ASSIGN(HIntermediateAddress);
-};
-
// This instruction computes part of the array access offset (data and index offset).
//
// For array accesses the element address has the following structure:
diff --git a/test/706-checker-scheduler/src/Main.java b/test/706-checker-scheduler/src/Main.java
index 08a23a7..d21596d 100644
--- a/test/706-checker-scheduler/src/Main.java
+++ b/test/706-checker-scheduler/src/Main.java
@@ -276,6 +276,83 @@
}
}
+ // This case tests a bug found in LSA where LSA doesn't understand IntermediateAddress,
+ // and incorrectly reported no alias between ArraySet1 and ArrayGet2,
+ // thus ArrayGet2 is scheduled above ArraySet1 incorrectly.
+
+ /// CHECK-START-ARM64: void Main.CrossOverLoop(int[], int[]) scheduler (before)
+ /// CHECK: <<ParamA:l\d+>> ParameterValue loop:none
+ /// CHECK: <<ParamB:l\d+>> ParameterValue loop:none
+ /// CHECK: <<NullB:l\d+>> NullCheck [<<ParamB>>] loop:none
+ /// CHECK: <<NullA:l\d+>> NullCheck [<<ParamA>>] loop:none
+ /// CHECK: Phi loop:<<Loop:B\d+>> outer_loop:none
+ /// CHECK: <<ArrayGet1:i\d+>> ArrayGet [<<NullB>>,{{i\d+}}] loop:<<Loop>> outer_loop:none
+ /// CHECK: Add loop:<<Loop>> outer_loop:none
+ /// CHECK: <<Addr1:i\d+>> IntermediateAddress [<<NullA>>,{{i\d+}}] loop:<<Loop>> outer_loop:none
+ /// CHECK: <<ArraySet1:v\d+>> ArraySet [<<Addr1>>,{{i\d+}},{{i\d+}}] loop:<<Loop>> outer_loop:none
+ /// CHECK: <<ArrayGet2:i\d+>> ArrayGet [<<NullB>>,{{i\d+}}] loop:<<Loop>> outer_loop:none
+ /// CHECK: Add loop:<<Loop>> outer_loop:none
+ /// CHECK: <<Addr2:i\d+>> IntermediateAddress [<<NullA>>,{{i\d+}}] loop:<<Loop>> outer_loop:none
+ /// CHECK: <<ArraySet2:v\d+>> ArraySet [<<Addr2>>,{{i\d+}},{{i\d+}}] loop:<<Loop>> outer_loop:none
+ /// CHECK: Add loop:<<Loop>> outer_loop:none
+
+ /// CHECK-START-ARM64: void Main.CrossOverLoop(int[], int[]) scheduler (after)
+ /// CHECK: <<ParamA:l\d+>> ParameterValue loop:none
+ /// CHECK: <<ParamB:l\d+>> ParameterValue loop:none
+ /// CHECK: <<NullB:l\d+>> NullCheck [<<ParamB>>] loop:none
+ /// CHECK: <<NullA:l\d+>> NullCheck [<<ParamA>>] loop:none
+ /// CHECK: Phi loop:<<Loop:B\d+>> outer_loop:none
+ /// CHECK: <<ArrayGet1:i\d+>> ArrayGet [<<NullB>>,{{i\d+}}] loop:<<Loop>> outer_loop:none
+ /// CHECK: Add loop:<<Loop>> outer_loop:none
+ /// CHECK: <<Addr1:i\d+>> IntermediateAddress [<<NullA>>,{{i\d+}}] loop:<<Loop>> outer_loop:none
+ /// CHECK: <<ArraySet1:v\d+>> ArraySet [<<Addr1>>,{{i\d+}},{{i\d+}}] loop:<<Loop>> outer_loop:none
+ /// CHECK: <<ArrayGet2:i\d+>> ArrayGet [<<NullB>>,{{i\d+}}] loop:<<Loop>> outer_loop:none
+ /// CHECK: Add loop:<<Loop>> outer_loop:none
+ /// CHECK: <<Addr2:i\d+>> IntermediateAddress [<<NullA>>,{{i\d+}}] loop:<<Loop>> outer_loop:none
+ /// CHECK: <<ArraySet2:v\d+>> ArraySet [<<Addr2>>,{{i\d+}},{{i\d+}}] loop:<<Loop>> outer_loop:none
+ /// CHECK: Add loop:<<Loop>> outer_loop:none
+ private static void CrossOverLoop(int a[], int b[]) {
+ b[20] = 99;
+ for (int i = 0; i < a.length; i++) {
+ a[i] = b[20] - 7;
+ i++;
+ a[i] = b[20] - 7;
+ }
+ }
+
+ // This test case is similar to above cross over loop,
+ // but has more complex chains of transforming the original references:
+ // ParameterValue --> BoundType --> NullCheck --> ArrayGet.
+ // ParameterValue --> BoundType --> NullCheck --> IntermediateAddress --> ArraySet.
+ // After using LSA to analyze the orginal references, the scheduler should be able
+ // to find out that 'a' and 'b' may alias, hence unable to schedule these ArraGet/Set.
+
+ /// CHECK-START-ARM64: void Main.CrossOverLoop2(java.lang.Object, java.lang.Object) scheduler (before)
+ /// CHECK: Phi loop:<<Loop:B\d+>> outer_loop:none
+ /// CHECK: ArrayGet loop:<<Loop>> outer_loop:none
+ /// CHECK: Add loop:<<Loop>> outer_loop:none
+ /// CHECK: ArraySet loop:<<Loop>> outer_loop:none
+ /// CHECK: ArrayGet loop:<<Loop>> outer_loop:none
+ /// CHECK: Add loop:<<Loop>> outer_loop:none
+ /// CHECK: ArraySet loop:<<Loop>> outer_loop:none
+
+ /// CHECK-START-ARM64: void Main.CrossOverLoop2(java.lang.Object, java.lang.Object) scheduler (after)
+ /// CHECK: Phi loop:<<Loop:B\d+>> outer_loop:none
+ /// CHECK: ArrayGet loop:<<Loop>> outer_loop:none
+ /// CHECK: Add loop:<<Loop>> outer_loop:none
+ /// CHECK: ArraySet loop:<<Loop>> outer_loop:none
+ /// CHECK: ArrayGet loop:<<Loop>> outer_loop:none
+ /// CHECK: Add loop:<<Loop>> outer_loop:none
+ /// CHECK: ArraySet loop:<<Loop>> outer_loop:none
+ private static void CrossOverLoop2(Object a, Object b) {
+ ((int[])b)[20] = 99;
+ for (int i = 0; i < ((int[])a).length; i++) {
+ ((int[])a)[i] = ((int[])b)[20] - 7;
+ i++;
+ ((int[])a)[i] = ((int[])b)[20] - 7;
+ }
+ }
+
/// CHECK-START-ARM: void Main.accessFields() scheduler (before)
/// CHECK: InstanceFieldGet
/// CHECK: Add