Disambiguate memory accesses in instruction scheduling
Based on aliasing information from heap location collector,
instruction scheduling can further eliminate side-effect
dependencies between memory accesses to different locations,
and perform better scheduling on memory loads and stores.
Performance improvements of this CL, measured on Cortex-A53:
| benchmarks | ARM64 backend | ARM backend |
|----------------+---------------|-------------|
| algorithm | 0.1 % | 0.1 % |
| benchmarksgame | 0.5 % | 1.3 % |
| caffeinemark | 0.0 % | 0.0 % |
| math | 5.1 % | 5.0 % |
| stanford | 1.1 % | 0.6 % |
| testsimd | 0.4 % | 0.1 % |
Compilation time impact is negligible, because this
heap location load store analysis is only performed
on loop basic blocks that get instruction scheduled.
Test: m test-art-host
Test: m test-art-target
Test: 706-checker-scheduler
Change-Id: I43d7003c09bfab9d3a1814715df666aea9a7360b
diff --git a/compiler/optimizing/scheduler.cc b/compiler/optimizing/scheduler.cc
index 147fa1c..5ad011d 100644
--- a/compiler/optimizing/scheduler.cc
+++ b/compiler/optimizing/scheduler.cc
@@ -66,28 +66,215 @@
return false;
}
+size_t SchedulingGraph::ArrayAccessHeapLocation(HInstruction* array, HInstruction* index) const {
+ DCHECK(heap_location_collector_ != nullptr);
+ size_t heap_loc = heap_location_collector_->GetArrayAccessHeapLocation(array, index);
+ // This array access should be analyzed and added to HeapLocationCollector before.
+ DCHECK(heap_loc != HeapLocationCollector::kHeapLocationNotFound);
+ return heap_loc;
+}
-// Check whether `node` depends on `other`, taking into account `SideEffect`
-// information and `CanThrow` information.
-static bool HasSideEffectDependency(const HInstruction* node, const HInstruction* other) {
- if (MayHaveReorderingDependency(node->GetSideEffects(), other->GetSideEffects())) {
+bool SchedulingGraph::ArrayAccessMayAlias(const HInstruction* node,
+ const HInstruction* other) const {
+ DCHECK(heap_location_collector_ != nullptr);
+ size_t node_heap_loc = ArrayAccessHeapLocation(node->InputAt(0), node->InputAt(1));
+ size_t other_heap_loc = ArrayAccessHeapLocation(other->InputAt(0), other->InputAt(1));
+
+ // For example: arr[0] and arr[0]
+ if (node_heap_loc == other_heap_loc) {
return true;
}
+ // For example: arr[0] and arr[i]
+ if (heap_location_collector_->MayAlias(node_heap_loc, other_heap_loc)) {
+ return true;
+ }
+
+ return false;
+}
+
+static bool IsArrayAccess(const HInstruction* instruction) {
+ return instruction->IsArrayGet() || instruction->IsArraySet();
+}
+
+static bool IsInstanceFieldAccess(const HInstruction* instruction) {
+ return instruction->IsInstanceFieldGet() ||
+ instruction->IsInstanceFieldSet() ||
+ instruction->IsUnresolvedInstanceFieldGet() ||
+ instruction->IsUnresolvedInstanceFieldSet();
+}
+
+static bool IsStaticFieldAccess(const HInstruction* instruction) {
+ return instruction->IsStaticFieldGet() ||
+ instruction->IsStaticFieldSet() ||
+ instruction->IsUnresolvedStaticFieldGet() ||
+ instruction->IsUnresolvedStaticFieldSet();
+}
+
+static bool IsResolvedFieldAccess(const HInstruction* instruction) {
+ return instruction->IsInstanceFieldGet() ||
+ instruction->IsInstanceFieldSet() ||
+ instruction->IsStaticFieldGet() ||
+ instruction->IsStaticFieldSet();
+}
+
+static bool IsUnresolvedFieldAccess(const HInstruction* instruction) {
+ return instruction->IsUnresolvedInstanceFieldGet() ||
+ instruction->IsUnresolvedInstanceFieldSet() ||
+ instruction->IsUnresolvedStaticFieldGet() ||
+ instruction->IsUnresolvedStaticFieldSet();
+}
+
+static bool IsFieldAccess(const HInstruction* instruction) {
+ return IsResolvedFieldAccess(instruction) || IsUnresolvedFieldAccess(instruction);
+}
+
+static const FieldInfo* GetFieldInfo(const HInstruction* instruction) {
+ if (instruction->IsInstanceFieldGet()) {
+ return &instruction->AsInstanceFieldGet()->GetFieldInfo();
+ } else if (instruction->IsInstanceFieldSet()) {
+ return &instruction->AsInstanceFieldSet()->GetFieldInfo();
+ } else if (instruction->IsStaticFieldGet()) {
+ return &instruction->AsStaticFieldGet()->GetFieldInfo();
+ } else if (instruction->IsStaticFieldSet()) {
+ return &instruction->AsStaticFieldSet()->GetFieldInfo();
+ } else {
+ LOG(FATAL) << "Unexpected field access type";
+ UNREACHABLE();
+ }
+}
+
+size_t SchedulingGraph::FieldAccessHeapLocation(HInstruction* obj, const FieldInfo* field) const {
+ DCHECK(obj != nullptr);
+ DCHECK(field != nullptr);
+ DCHECK(heap_location_collector_ != nullptr);
+
+ size_t heap_loc = heap_location_collector_->FindHeapLocationIndex(
+ heap_location_collector_->FindReferenceInfoOf(
+ heap_location_collector_->HuntForOriginalReference(obj)),
+ field->GetFieldOffset().SizeValue(),
+ nullptr,
+ field->GetDeclaringClassDefIndex());
+ // This field access should be analyzed and added to HeapLocationCollector before.
+ DCHECK(heap_loc != HeapLocationCollector::kHeapLocationNotFound);
+
+ return heap_loc;
+}
+
+bool SchedulingGraph::FieldAccessMayAlias(const HInstruction* node,
+ const HInstruction* other) const {
+ DCHECK(heap_location_collector_ != nullptr);
+
+ // Static and instance field accesses should not alias.
+ if ((IsInstanceFieldAccess(node) && IsStaticFieldAccess(other)) ||
+ (IsStaticFieldAccess(node) && IsInstanceFieldAccess(other))) {
+ return false;
+ }
+
+ // If either of the field accesses is unresolved.
+ if (IsUnresolvedFieldAccess(node) || IsUnresolvedFieldAccess(other)) {
+ // Conservatively treat these two accesses may alias.
+ return true;
+ }
+
+ // If both fields accesses are resolved.
+ const FieldInfo* node_field = GetFieldInfo(node);
+ const FieldInfo* other_field = GetFieldInfo(other);
+
+ size_t node_loc = FieldAccessHeapLocation(node->InputAt(0), node_field);
+ size_t other_loc = FieldAccessHeapLocation(other->InputAt(0), other_field);
+
+ if (node_loc == other_loc) {
+ return true;
+ }
+
+ if (!heap_location_collector_->MayAlias(node_loc, other_loc)) {
+ return false;
+ }
+
+ return true;
+}
+
+bool SchedulingGraph::HasMemoryDependency(const HInstruction* node,
+ const HInstruction* other) const {
+ if (!MayHaveReorderingDependency(node->GetSideEffects(), other->GetSideEffects())) {
+ return false;
+ }
+
+ if (heap_location_collector_ == nullptr ||
+ heap_location_collector_->GetNumberOfHeapLocations() == 0) {
+ // Without HeapLocation information from load store analysis,
+ // we cannot do further disambiguation analysis on these two instructions.
+ // Just simply say that those two instructions have memory dependency.
+ return true;
+ }
+
+ if (IsArrayAccess(node) && IsArrayAccess(other)) {
+ return ArrayAccessMayAlias(node, other);
+ }
+ if (IsFieldAccess(node) && IsFieldAccess(other)) {
+ return FieldAccessMayAlias(node, other);
+ }
+
+ // TODO(xueliang): LSA to support alias analysis among HVecLoad, HVecStore and ArrayAccess
+ if (node->IsVecMemoryOperation() && other->IsVecMemoryOperation()) {
+ return true;
+ }
+ if (node->IsVecMemoryOperation() && IsArrayAccess(other)) {
+ return true;
+ }
+ if (IsArrayAccess(node) && other->IsVecMemoryOperation()) {
+ return true;
+ }
+
+ // Heap accesses of different kinds should not alias.
+ if (IsArrayAccess(node) && IsFieldAccess(other)) {
+ return false;
+ }
+ if (IsFieldAccess(node) && IsArrayAccess(other)) {
+ return false;
+ }
+ if (node->IsVecMemoryOperation() && IsFieldAccess(other)) {
+ return false;
+ }
+ if (IsFieldAccess(node) && other->IsVecMemoryOperation()) {
+ return false;
+ }
+
+ // We conservatively treat all other cases having dependency,
+ // for example, Invoke and ArrayGet.
+ return true;
+}
+
+bool SchedulingGraph::HasExceptionDependency(const HInstruction* node,
+ const HInstruction* other) const {
if (other->CanThrow() && node->GetSideEffects().DoesAnyWrite()) {
return true;
}
-
if (other->GetSideEffects().DoesAnyWrite() && node->CanThrow()) {
return true;
}
-
if (other->CanThrow() && node->CanThrow()) {
return true;
}
- // Check side-effect dependency between ArrayGet and BoundsCheck.
- if (node->IsArrayGet() && other->IsBoundsCheck() && node->InputAt(1) == other) {
+ // Above checks should cover all cases where we cannot reorder two
+ // instructions which may throw exception.
+ return false;
+}
+
+// Check whether `node` depends on `other`, taking into account `SideEffect`
+// information and `CanThrow` information.
+bool SchedulingGraph::HasSideEffectDependency(const HInstruction* node,
+ const HInstruction* other) const {
+ if (HasMemoryDependency(node, other)) {
+ return true;
+ }
+
+ // Even if above memory dependency check has passed, it is still necessary to
+ // check dependencies between instructions that can throw and instructions
+ // that write to memory.
+ if (HasExceptionDependency(node, other)) {
return true;
}
@@ -379,6 +566,14 @@
// Build the scheduling graph.
scheduling_graph_.Clear();
+
+ // Only perform LSA/HeapLocation analysis on the basic block that
+ // is going to get instruction scheduled.
+ HeapLocationCollector heap_location_collector(block->GetGraph());
+ heap_location_collector.VisitBasicBlock(block);
+ heap_location_collector.BuildAliasingMatrix();
+ scheduling_graph_.SetHeapLocationCollector(heap_location_collector);
+
for (HBackwardInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) {
HInstruction* instruction = it.Current();
CHECK_EQ(instruction->GetBlock(), block)
@@ -606,7 +801,9 @@
// Avoid compilation error when compiling for unsupported instruction set.
UNUSED(only_optimize_loop_blocks);
UNUSED(schedule_randomly);
+ UNUSED(codegen_);
#endif
+
switch (instruction_set_) {
#ifdef ART_ENABLE_CODEGEN_arm64
case kArm64: {
diff --git a/compiler/optimizing/scheduler.h b/compiler/optimizing/scheduler.h
index 73e8087..930a2c8 100644
--- a/compiler/optimizing/scheduler.h
+++ b/compiler/optimizing/scheduler.h
@@ -21,6 +21,7 @@
#include "base/time_utils.h"
#include "driver/compiler_driver.h"
+#include "load_store_analysis.h"
#include "nodes.h"
#include "optimization.h"
#include "code_generator.h"
@@ -246,7 +247,8 @@
: scheduler_(scheduler),
arena_(arena),
contains_scheduling_barrier_(false),
- nodes_map_(arena_->Adapter(kArenaAllocScheduler)) {}
+ nodes_map_(arena_->Adapter(kArenaAllocScheduler)),
+ heap_location_collector_(nullptr) {}
SchedulingNode* AddNode(HInstruction* instr, bool is_scheduling_barrier = false) {
SchedulingNode* node = new (arena_) SchedulingNode(instr, arena_, is_scheduling_barrier);
@@ -261,6 +263,10 @@
contains_scheduling_barrier_ = false;
}
+ void SetHeapLocationCollector(const HeapLocationCollector& heap_location_collector) {
+ heap_location_collector_ = &heap_location_collector;
+ }
+
SchedulingNode* GetNode(const HInstruction* instr) const {
auto it = nodes_map_.Find(instr);
if (it == nodes_map_.end()) {
@@ -294,6 +300,13 @@
void AddOtherDependency(SchedulingNode* node, SchedulingNode* dependency) {
AddDependency(node, dependency, /*is_data_dependency*/false);
}
+ bool HasMemoryDependency(const HInstruction* node, const HInstruction* other) const;
+ bool HasExceptionDependency(const HInstruction* node, const HInstruction* other) const;
+ bool HasSideEffectDependency(const HInstruction* node, const HInstruction* other) const;
+ bool ArrayAccessMayAlias(const HInstruction* node, const HInstruction* other) const;
+ bool FieldAccessMayAlias(const HInstruction* node, const HInstruction* other) const;
+ size_t ArrayAccessHeapLocation(HInstruction* array, HInstruction* index) const;
+ size_t FieldAccessHeapLocation(HInstruction* obj, const FieldInfo* field) const;
// Add dependencies nodes for the given `HInstruction`: inputs, environments, and side-effects.
void AddDependencies(HInstruction* instruction, bool is_scheduling_barrier = false);
@@ -305,6 +318,8 @@
bool contains_scheduling_barrier_;
ArenaHashMap<const HInstruction*, SchedulingNode*> nodes_map_;
+
+ const HeapLocationCollector* heap_location_collector_;
};
/*
@@ -482,10 +497,9 @@
static constexpr const char* kInstructionScheduling = "scheduler";
+ private:
CodeGenerator* const codegen_;
const InstructionSet instruction_set_;
-
- private:
DISALLOW_COPY_AND_ASSIGN(HInstructionScheduling);
};
diff --git a/compiler/optimizing/scheduler_test.cc b/compiler/optimizing/scheduler_test.cc
index d87600a..cc7222d 100644
--- a/compiler/optimizing/scheduler_test.cc
+++ b/compiler/optimizing/scheduler_test.cc
@@ -18,6 +18,7 @@
#include "builder.h"
#include "codegen_test_utils.h"
#include "common_compiler_test.h"
+#include "load_store_analysis.h"
#include "nodes.h"
#include "optimizing_unit_test.h"
#include "pc_relative_fixups_x86.h"
@@ -193,6 +194,147 @@
}
}
+ void TestDependencyGraphOnAliasingArrayAccesses(HScheduler* scheduler) {
+ HBasicBlock* entry = new (&allocator_) HBasicBlock(graph_);
+ graph_->AddBlock(entry);
+ graph_->SetEntryBlock(entry);
+ graph_->BuildDominatorTree();
+
+ HInstruction* arr = new (&allocator_) HParameterValue(graph_->GetDexFile(),
+ dex::TypeIndex(0),
+ 0,
+ Primitive::kPrimNot);
+ HInstruction* i = new (&allocator_) HParameterValue(graph_->GetDexFile(),
+ dex::TypeIndex(1),
+ 1,
+ Primitive::kPrimInt);
+ HInstruction* j = new (&allocator_) HParameterValue(graph_->GetDexFile(),
+ dex::TypeIndex(1),
+ 1,
+ Primitive::kPrimInt);
+ HInstruction* object = new (&allocator_) HParameterValue(graph_->GetDexFile(),
+ dex::TypeIndex(0),
+ 0,
+ Primitive::kPrimNot);
+ HInstruction* c0 = graph_->GetIntConstant(0);
+ HInstruction* c1 = graph_->GetIntConstant(1);
+ HInstruction* add0 = new (&allocator_) HAdd(Primitive::kPrimInt, i, c0);
+ HInstruction* add1 = new (&allocator_) HAdd(Primitive::kPrimInt, i, c1);
+ HInstruction* sub0 = new (&allocator_) HSub(Primitive::kPrimInt, i, c0);
+ HInstruction* sub1 = new (&allocator_) HSub(Primitive::kPrimInt, i, c1);
+ HInstruction* arr_set_0 = new (&allocator_) HArraySet(arr, c0, c0, Primitive::kPrimInt, 0);
+ HInstruction* arr_set_1 = new (&allocator_) HArraySet(arr, c1, c0, Primitive::kPrimInt, 0);
+ HInstruction* arr_set_i = new (&allocator_) HArraySet(arr, i, c0, Primitive::kPrimInt, 0);
+ HInstruction* arr_set_add0 = new (&allocator_) HArraySet(arr, add0, c0, Primitive::kPrimInt, 0);
+ HInstruction* arr_set_add1 = new (&allocator_) HArraySet(arr, add1, c0, Primitive::kPrimInt, 0);
+ HInstruction* arr_set_sub0 = new (&allocator_) HArraySet(arr, sub0, c0, Primitive::kPrimInt, 0);
+ HInstruction* arr_set_sub1 = new (&allocator_) HArraySet(arr, sub1, c0, Primitive::kPrimInt, 0);
+ HInstruction* arr_set_j = new (&allocator_) HArraySet(arr, j, c0, Primitive::kPrimInt, 0);
+ HInstanceFieldSet* set_field10 = new (&allocator_) HInstanceFieldSet(object,
+ c1,
+ nullptr,
+ Primitive::kPrimInt,
+ MemberOffset(10),
+ false,
+ kUnknownFieldIndex,
+ kUnknownClassDefIndex,
+ graph_->GetDexFile(),
+ 0);
+
+ HInstruction* block_instructions[] = {arr,
+ i,
+ j,
+ object,
+ add0,
+ add1,
+ sub0,
+ sub1,
+ arr_set_0,
+ arr_set_1,
+ arr_set_i,
+ arr_set_add0,
+ arr_set_add1,
+ arr_set_sub0,
+ arr_set_sub1,
+ arr_set_j,
+ set_field10};
+
+ for (HInstruction* instr : block_instructions) {
+ entry->AddInstruction(instr);
+ }
+
+ SchedulingGraph scheduling_graph(scheduler, graph_->GetArena());
+ HeapLocationCollector heap_location_collector(graph_);
+ heap_location_collector.VisitBasicBlock(entry);
+ heap_location_collector.BuildAliasingMatrix();
+ scheduling_graph.SetHeapLocationCollector(heap_location_collector);
+
+ for (HInstruction* instr : ReverseRange(block_instructions)) {
+ // Build scheduling graph with memory access aliasing information
+ // from LSA/heap_location_collector.
+ scheduling_graph.AddNode(instr);
+ }
+
+ // LSA/HeapLocationCollector should see those ArraySet instructions.
+ ASSERT_EQ(heap_location_collector.GetNumberOfHeapLocations(), 9U);
+ ASSERT_TRUE(heap_location_collector.HasHeapStores());
+
+ // Test queries on HeapLocationCollector's aliasing matrix after load store analysis.
+ // HeapLocationCollector and SchedulingGraph should report consistent relationships.
+ size_t loc1 = HeapLocationCollector::kHeapLocationNotFound;
+ size_t loc2 = HeapLocationCollector::kHeapLocationNotFound;
+
+ // Test side effect dependency: array[0] and array[1]
+ loc1 = heap_location_collector.GetArrayAccessHeapLocation(arr, c0);
+ loc2 = heap_location_collector.GetArrayAccessHeapLocation(arr, c1);
+ ASSERT_FALSE(heap_location_collector.MayAlias(loc1, loc2));
+ ASSERT_FALSE(scheduling_graph.HasImmediateOtherDependency(arr_set_1, arr_set_0));
+
+ // Test side effect dependency based on LSA analysis: array[i] and array[j]
+ loc1 = heap_location_collector.GetArrayAccessHeapLocation(arr, i);
+ loc2 = heap_location_collector.GetArrayAccessHeapLocation(arr, j);
+ ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2));
+ ASSERT_TRUE(scheduling_graph.HasImmediateOtherDependency(arr_set_j, arr_set_i));
+
+ // Test side effect dependency based on LSA analysis: array[i] and array[i+0]
+ loc1 = heap_location_collector.GetArrayAccessHeapLocation(arr, i);
+ loc2 = heap_location_collector.GetArrayAccessHeapLocation(arr, add0);
+ ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2));
+ ASSERT_TRUE(scheduling_graph.HasImmediateOtherDependency(arr_set_add0, arr_set_i));
+
+ // Test side effect dependency based on LSA analysis: array[i] and array[i-0]
+ loc1 = heap_location_collector.GetArrayAccessHeapLocation(arr, i);
+ loc2 = heap_location_collector.GetArrayAccessHeapLocation(arr, sub0);
+ ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2));
+ ASSERT_TRUE(scheduling_graph.HasImmediateOtherDependency(arr_set_sub0, arr_set_i));
+
+ // Test side effect dependency based on LSA analysis: array[i] and array[i+1]
+ loc1 = heap_location_collector.GetArrayAccessHeapLocation(arr, i);
+ loc2 = heap_location_collector.GetArrayAccessHeapLocation(arr, add1);
+ ASSERT_FALSE(heap_location_collector.MayAlias(loc1, loc2));
+ ASSERT_FALSE(scheduling_graph.HasImmediateOtherDependency(arr_set_add1, arr_set_i));
+
+ // Test side effect dependency based on LSA analysis: array[i+1] and array[i-1]
+ loc1 = heap_location_collector.GetArrayAccessHeapLocation(arr, add1);
+ loc2 = heap_location_collector.GetArrayAccessHeapLocation(arr, sub1);
+ ASSERT_FALSE(heap_location_collector.MayAlias(loc1, loc2));
+ ASSERT_FALSE(scheduling_graph.HasImmediateOtherDependency(arr_set_sub1, arr_set_add1));
+
+ // Test side effect dependency based on LSA analysis: array[j] and all others array accesses
+ ASSERT_TRUE(scheduling_graph.HasImmediateOtherDependency(arr_set_j, arr_set_i));
+ ASSERT_TRUE(scheduling_graph.HasImmediateOtherDependency(arr_set_j, arr_set_add0));
+ ASSERT_TRUE(scheduling_graph.HasImmediateOtherDependency(arr_set_j, arr_set_sub0));
+ ASSERT_TRUE(scheduling_graph.HasImmediateOtherDependency(arr_set_j, arr_set_add1));
+ ASSERT_TRUE(scheduling_graph.HasImmediateOtherDependency(arr_set_j, arr_set_sub1));
+
+ // Test that ArraySet and FieldSet should not have side effect dependency
+ ASSERT_FALSE(scheduling_graph.HasImmediateOtherDependency(arr_set_i, set_field10));
+ ASSERT_FALSE(scheduling_graph.HasImmediateOtherDependency(arr_set_j, set_field10));
+
+ // Exercise target specific scheduler and SchedulingLatencyVisitor.
+ scheduler->Schedule(graph_);
+ }
+
ArenaPool pool_;
ArenaAllocator allocator_;
HGraph* graph_;
@@ -204,15 +346,28 @@
arm64::HSchedulerARM64 scheduler(&allocator_, &critical_path_selector);
TestBuildDependencyGraphAndSchedule(&scheduler);
}
+
+TEST_F(SchedulerTest, ArrayAccessAliasingARM64) {
+ CriticalPathSchedulingNodeSelector critical_path_selector;
+ arm64::HSchedulerARM64 scheduler(&allocator_, &critical_path_selector);
+ TestDependencyGraphOnAliasingArrayAccesses(&scheduler);
+}
#endif
#if defined(ART_ENABLE_CODEGEN_arm)
-TEST_F(SchedulerTest, DependencyGrapAndSchedulerARM) {
+TEST_F(SchedulerTest, DependencyGraphAndSchedulerARM) {
CriticalPathSchedulingNodeSelector critical_path_selector;
arm::SchedulingLatencyVisitorARM arm_latency_visitor(/*CodeGenerator*/ nullptr);
arm::HSchedulerARM scheduler(&allocator_, &critical_path_selector, &arm_latency_visitor);
TestBuildDependencyGraphAndSchedule(&scheduler);
}
+
+TEST_F(SchedulerTest, ArrayAccessAliasingARM) {
+ CriticalPathSchedulingNodeSelector critical_path_selector;
+ arm::SchedulingLatencyVisitorARM arm_latency_visitor(/*CodeGenerator*/ nullptr);
+ arm::HSchedulerARM scheduler(&allocator_, &critical_path_selector, &arm_latency_visitor);
+ TestDependencyGraphOnAliasingArrayAccesses(&scheduler);
+}
#endif
TEST_F(SchedulerTest, RandomScheduling) {
diff --git a/test/706-checker-scheduler/src/Main.java b/test/706-checker-scheduler/src/Main.java
index 1721e42..a68565b 100644
--- a/test/706-checker-scheduler/src/Main.java
+++ b/test/706-checker-scheduler/src/Main.java
@@ -16,8 +16,22 @@
public class Main {
+ public class ExampleObj {
+ int n1;
+ int n2;
+
+ public ExampleObj(int n1, int n2) {
+ this.n1 = n1;
+ this.n2 = n2;
+ }
+ }
+
static int static_variable = 0;
+ public ExampleObj my_obj;
+ public static int number1;
+ public static int number2;
+
/// CHECK-START-ARM64: int Main.arrayAccess() scheduler (before)
/// CHECK: <<Const1:i\d+>> IntConstant 1
/// CHECK: <<i0:i\d+>> Phi
@@ -50,6 +64,282 @@
return res;
}
+ /// CHECK-START-ARM: void Main.arrayAccessVariable(int) scheduler (before)
+ /// CHECK: <<Param:i\d+>> ParameterValue
+ /// CHECK-DAG: <<Const1:i\d+>> IntConstant 1
+ /// CHECK-DAG: <<Const2:i\d+>> IntConstant 2
+ /// CHECK-DAG: <<Const3:i\d+>> IntConstant -1
+ /// CHECK: <<Add1:i\d+>> Add [<<Param>>,<<Const1>>]
+ /// CHECK: <<Add2:i\d+>> Add [<<Param>>,<<Const2>>]
+ /// CHECK: <<Add3:i\d+>> Add [<<Param>>,<<Const3>>]
+ /// CHECK: <<Array:i\d+>> IntermediateAddress
+ /// CHECK: <<ArrayGet1:i\d+>> ArrayGet [<<Array>>,<<Add1>>]
+ /// CHECK: <<AddArray1:i\d+>> Add [<<ArrayGet1>>,<<Const1>>]
+ /// CHECK: <<ArraySet1:v\d+>> ArraySet [<<Array>>,<<Add1>>,<<AddArray1>>]
+ /// CHECK: <<ArrayGet2:i\d+>> ArrayGet [<<Array>>,<<Add2>>]
+ /// CHECK: <<AddArray2:i\d+>> Add [<<ArrayGet2>>,<<Const1>>]
+ /// CHECK: <<ArraySet2:v\d+>> ArraySet [<<Array>>,<<Add2>>,<<AddArray2>>]
+ /// CHECK: <<ArrayGet3:i\d+>> ArrayGet [<<Array>>,<<Add3>>]
+ /// CHECK: <<AddArray3:i\d+>> Add [<<ArrayGet3>>,<<Const1>>]
+ /// CHECK: <<ArraySet3:v\d+>> ArraySet [<<Array>>,<<Add3>>,<<AddArray3>>]
+
+ /// CHECK-START-ARM: void Main.arrayAccessVariable(int) scheduler (after)
+ /// CHECK: <<Param:i\d+>> ParameterValue
+ /// CHECK-DAG: <<Const1:i\d+>> IntConstant 1
+ /// CHECK-DAG: <<Const2:i\d+>> IntConstant 2
+ /// CHECK-DAG: <<Const3:i\d+>> IntConstant -1
+ /// CHECK: <<Add1:i\d+>> Add [<<Param>>,<<Const1>>]
+ /// CHECK: <<Add2:i\d+>> Add [<<Param>>,<<Const2>>]
+ /// CHECK: <<Add3:i\d+>> Add [<<Param>>,<<Const3>>]
+ /// CHECK: <<Array:i\d+>> IntermediateAddress
+ /// CHECK: ArrayGet [<<Array>>,{{i\d+}}]
+ /// CHECK: ArrayGet [<<Array>>,{{i\d+}}]
+ /// CHECK: ArrayGet [<<Array>>,{{i\d+}}]
+ /// CHECK: Add
+ /// CHECK: Add
+ /// CHECK: Add
+ /// CHECK: ArraySet
+ /// CHECK: ArraySet
+ /// CHECK: ArraySet
+
+ /// CHECK-START-ARM64: void Main.arrayAccessVariable(int) scheduler (before)
+ /// CHECK: <<Param:i\d+>> ParameterValue
+ /// CHECK-DAG: <<Const1:i\d+>> IntConstant 1
+ /// CHECK-DAG: <<Const2:i\d+>> IntConstant 2
+ /// CHECK-DAG: <<Const3:i\d+>> IntConstant -1
+ /// CHECK: <<Add1:i\d+>> Add [<<Param>>,<<Const1>>]
+ /// CHECK: <<Add2:i\d+>> Add [<<Param>>,<<Const2>>]
+ /// CHECK: <<Add3:i\d+>> Add [<<Param>>,<<Const3>>]
+ /// CHECK: <<Array:i\d+>> IntermediateAddress
+ /// CHECK: <<ArrayGet1:i\d+>> ArrayGet [<<Array>>,<<Add1>>]
+ /// CHECK: <<AddArray1:i\d+>> Add [<<ArrayGet1>>,<<Const1>>]
+ /// CHECK: <<ArraySet1:v\d+>> ArraySet [<<Array>>,<<Add1>>,<<AddArray1>>]
+ /// CHECK: <<ArrayGet2:i\d+>> ArrayGet [<<Array>>,<<Add2>>]
+ /// CHECK: <<AddArray2:i\d+>> Add [<<ArrayGet2>>,<<Const1>>]
+ /// CHECK: <<ArraySet2:v\d+>> ArraySet [<<Array>>,<<Add2>>,<<AddArray2>>]
+ /// CHECK: <<ArrayGet3:i\d+>> ArrayGet [<<Array>>,<<Add3>>]
+ /// CHECK: <<AddArray3:i\d+>> Add [<<ArrayGet3>>,<<Const1>>]
+ /// CHECK: <<ArraySet3:v\d+>> ArraySet [<<Array>>,<<Add3>>,<<AddArray3>>]
+
+ /// CHECK-START-ARM64: void Main.arrayAccessVariable(int) scheduler (after)
+ /// CHECK: <<Param:i\d+>> ParameterValue
+ /// CHECK-DAG: <<Const1:i\d+>> IntConstant 1
+ /// CHECK-DAG: <<Const2:i\d+>> IntConstant 2
+ /// CHECK-DAG: <<Const3:i\d+>> IntConstant -1
+ /// CHECK: <<Add1:i\d+>> Add [<<Param>>,<<Const1>>]
+ /// CHECK: <<Add2:i\d+>> Add [<<Param>>,<<Const2>>]
+ /// CHECK: <<Add3:i\d+>> Add [<<Param>>,<<Const3>>]
+ /// CHECK: <<Array:i\d+>> IntermediateAddress
+ /// CHECK: ArrayGet [<<Array>>,{{i\d+}}]
+ /// CHECK: ArrayGet [<<Array>>,{{i\d+}}]
+ /// CHECK: ArrayGet [<<Array>>,{{i\d+}}]
+ /// CHECK: Add
+ /// CHECK: Add
+ /// CHECK: Add
+ /// CHECK: ArraySet
+ /// CHECK: ArraySet
+ /// CHECK: ArraySet
+ public static void arrayAccessVariable(int i) {
+ int [] array = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
+ for (int j = 0; j < 100; j++) {
+ array[i + 1]++;
+ array[i + 2]++;
+ array[i - 1]++;
+ }
+ }
+
+ /// CHECK-START-ARM: void Main.arrayAccessSub(int) scheduler (before)
+ /// CHECK: <<Param:i\d+>> ParameterValue
+ /// CHECK-DAG: <<Const1:i\d+>> IntConstant -1
+ /// CHECK-DAG: <<Const2:i\d+>> IntConstant 9
+ /// CHECK-DAG: <<Const3:i\d+>> IntConstant 1
+ /// CHECK: <<Add1:i\d+>> Add [<<Param>>,<<Const1>>]
+ /// CHECK: <<Sub2:i\d+>> Sub [<<Const2>>,<<Param>>]
+ /// CHECK: <<Array:i\d+>> IntermediateAddress
+ /// CHECK: <<ArrayGet1:i\d+>> ArrayGet [<<Array>>,<<Add1>>]
+ /// CHECK: <<AddArray1:i\d+>> Add [<<ArrayGet1>>,<<Const3>>]
+ /// CHECK: <<ArraySet1:v\d+>> ArraySet [<<Array>>,<<Add1>>,<<AddArray1>>]
+ /// CHECK: <<ArrayGet2:i\d+>> ArrayGet [<<Array>>,<<Sub2>>]
+ /// CHECK: <<AddArray2:i\d+>> Add [<<ArrayGet2>>,<<Const3>>]
+ /// CHECK: <<ArraySet2:v\d+>> ArraySet [<<Array>>,<<Sub2>>,<<AddArray2>>]
+
+ /// CHECK-START-ARM: void Main.arrayAccessSub(int) scheduler (after)
+ /// CHECK: <<Param:i\d+>> ParameterValue
+ /// CHECK-DAG: <<Const1:i\d+>> IntConstant -1
+ /// CHECK-DAG: <<Const2:i\d+>> IntConstant 9
+ /// CHECK-DAG: <<Const3:i\d+>> IntConstant 1
+ /// CHECK: <<Add1:i\d+>> Add [<<Param>>,<<Const1>>]
+ /// CHECK: <<Sub2:i\d+>> Sub [<<Const2>>,<<Param>>]
+ /// CHECK: <<Array:i\d+>> IntermediateAddress
+ /// CHECK: <<ArrayGet1:i\d+>> ArrayGet [<<Array>>,<<Add1>>]
+ /// CHECK: <<AddArray1:i\d+>> Add [<<ArrayGet1>>,<<Const3>>]
+ /// CHECK: <<ArraySet1:v\d+>> ArraySet [<<Array>>,<<Add1>>,<<AddArray1>>]
+ /// CHECK: <<ArrayGet2:i\d+>> ArrayGet [<<Array>>,<<Sub2>>]
+ /// CHECK: <<AddArray2:i\d+>> Add [<<ArrayGet2>>,<<Const3>>]
+ /// CHECK: <<ArraySet2:v\d+>> ArraySet [<<Array>>,<<Sub2>>,<<AddArray2>>]
+
+ /// CHECK-START-ARM64: void Main.arrayAccessSub(int) scheduler (before)
+ /// CHECK: <<Param:i\d+>> ParameterValue
+ /// CHECK-DAG: <<Const1:i\d+>> IntConstant -1
+ /// CHECK-DAG: <<Const2:i\d+>> IntConstant 9
+ /// CHECK-DAG: <<Const3:i\d+>> IntConstant 1
+ /// CHECK: <<Add1:i\d+>> Add [<<Param>>,<<Const1>>]
+ /// CHECK: <<Sub2:i\d+>> Sub [<<Const2>>,<<Param>>]
+ /// CHECK: <<Array:i\d+>> IntermediateAddress
+ /// CHECK: <<ArrayGet1:i\d+>> ArrayGet [<<Array>>,<<Add1>>]
+ /// CHECK: <<AddArray1:i\d+>> Add [<<ArrayGet1>>,<<Const3>>]
+ /// CHECK: <<ArraySet1:v\d+>> ArraySet [<<Array>>,<<Add1>>,<<AddArray1>>]
+ /// CHECK: <<ArrayGet2:i\d+>> ArrayGet [<<Array>>,<<Sub2>>]
+ /// CHECK: <<AddArray2:i\d+>> Add [<<ArrayGet2>>,<<Const3>>]
+ /// CHECK: <<ArraySet2:v\d+>> ArraySet [<<Array>>,<<Sub2>>,<<AddArray2>>]
+
+ /// CHECK-START-ARM64: void Main.arrayAccessSub(int) scheduler (after)
+ /// CHECK: <<Param:i\d+>> ParameterValue
+ /// CHECK-DAG: <<Const1:i\d+>> IntConstant -1
+ /// CHECK-DAG: <<Const2:i\d+>> IntConstant 9
+ /// CHECK-DAG: <<Const3:i\d+>> IntConstant 1
+ /// CHECK: <<Add1:i\d+>> Add [<<Param>>,<<Const1>>]
+ /// CHECK: <<Sub2:i\d+>> Sub [<<Const2>>,<<Param>>]
+ /// CHECK: <<Array:i\d+>> IntermediateAddress
+ /// CHECK: <<ArrayGet1:i\d+>> ArrayGet [<<Array>>,<<Add1>>]
+ /// CHECK: <<AddArray1:i\d+>> Add [<<ArrayGet1>>,<<Const3>>]
+ /// CHECK: <<ArraySet1:v\d+>> ArraySet [<<Array>>,<<Add1>>,<<AddArray1>>]
+ /// CHECK: <<ArrayGet2:i\d+>> ArrayGet [<<Array>>,<<Sub2>>]
+ /// CHECK: <<AddArray2:i\d+>> Add [<<ArrayGet2>>,<<Const3>>]
+ /// CHECK: <<ArraySet2:v\d+>> ArraySet [<<Array>>,<<Sub2>>,<<AddArray2>>]
+ public static void arrayAccessSub(int i) {
+ int [] array = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
+ for (int j = 0; j < 100; j++) {
+ // These two accesses MAY ALIAS
+ array[i - 1]++;
+ array[9 - i]++;
+ }
+ }
+
+ /// CHECK-START-ARM: void Main.arrayAccessLoopVariable() scheduler (before)
+ /// CHECK-DAG: <<Const0:i\d+>> IntConstant 0
+ /// CHECK-DAG: <<Const1:i\d+>> IntConstant 1
+ /// CHECK: <<Phi:i\d+>> Phi
+ /// CHECK: <<Array:i\d+>> IntermediateAddress
+ /// CHECK: <<ArrayGet1:i\d+>> ArrayGet
+ /// CHECK: <<AddArray1:i\d+>> Add
+ /// CHECK: <<ArraySet1:v\d+>> ArraySet
+ /// CHECK: <<AddVar:i\d+>> Add
+ /// CHECK: <<ArrayGet2:i\d+>> ArrayGet
+ /// CHECK: <<AddArray2:i\d+>> Add
+ /// CHECK: <<ArraySet2:v\d+>> ArraySet
+
+ /// CHECK-START-ARM: void Main.arrayAccessLoopVariable() scheduler (after)
+ /// CHECK-DAG: <<Const0:i\d+>> IntConstant 0
+ /// CHECK-DAG: <<Const1:i\d+>> IntConstant 1
+ /// CHECK: <<Phi:i\d+>> Phi
+ /// CHECK: <<Array:i\d+>> IntermediateAddress
+ /// CHECK: <<AddVar:i\d+>> Add
+ /// CHECK: <<ArrayGet1:i\d+>> ArrayGet
+ /// CHECK: <<ArrayGet2:i\d+>> ArrayGet
+ /// CHECK: <<AddArray1:i\d+>> Add
+ /// CHECK: <<AddArray2:i\d+>> Add
+ /// CHECK: <<ArraySet1:v\d+>> ArraySet
+ /// CHECK: <<ArraySet2:v\d+>> ArraySet
+
+ /// CHECK-START-ARM64: void Main.arrayAccessLoopVariable() scheduler (before)
+ /// CHECK-DAG: <<Const0:i\d+>> IntConstant 0
+ /// CHECK-DAG: <<Const1:i\d+>> IntConstant 1
+ /// CHECK: <<Phi:i\d+>> Phi
+ /// CHECK: <<Array:i\d+>> IntermediateAddress
+ /// CHECK: <<ArrayGet1:i\d+>> ArrayGet
+ /// CHECK: <<AddArray1:i\d+>> Add
+ /// CHECK: <<ArraySet1:v\d+>> ArraySet
+ /// CHECK: <<AddVar:i\d+>> Add
+ /// CHECK: <<ArrayGet2:i\d+>> ArrayGet
+ /// CHECK: <<AddArray2:i\d+>> Add
+ /// CHECK: <<ArraySet2:v\d+>> ArraySet
+
+ /// CHECK-START-ARM64: void Main.arrayAccessLoopVariable() scheduler (after)
+ /// CHECK-DAG: <<Const0:i\d+>> IntConstant 0
+ /// CHECK-DAG: <<Const1:i\d+>> IntConstant 1
+ /// CHECK: <<Phi:i\d+>> Phi
+ /// CHECK: <<Array:i\d+>> IntermediateAddress
+ /// CHECK: <<AddVar:i\d+>> Add
+ /// CHECK: <<ArrayGet1:i\d+>> ArrayGet
+ /// CHECK: <<ArrayGet2:i\d+>> ArrayGet
+ /// CHECK: <<AddArray1:i\d+>> Add
+ /// CHECK: <<AddArray2:i\d+>> Add
+ /// CHECK: <<ArraySet1:v\d+>> ArraySet
+ /// CHECK: <<ArraySet2:v\d+>> ArraySet
+ public static void arrayAccessLoopVariable() {
+ int [] array = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
+ for (int j = 0; j < 9; j++) {
+ array[j]++;
+ array[j + 1]++;
+ }
+ }
+
+ /// CHECK-START-ARM: void Main.accessFields() scheduler (before)
+ /// CHECK: InstanceFieldGet
+ /// CHECK: Add
+ /// CHECK: InstanceFieldSet
+ /// CHECK: InstanceFieldGet
+ /// CHECK: Add
+ /// CHECK: InstanceFieldSet
+ /// CHECK: StaticFieldGet
+ /// CHECK: Add
+ /// CHECK: StaticFieldSet
+ /// CHECK: StaticFieldGet
+ /// CHECK: Add
+ /// CHECK: StaticFieldSet
+
+ /// CHECK-START-ARM: void Main.accessFields() scheduler (after)
+ /// CHECK-DAG: InstanceFieldGet
+ /// CHECK-DAG: InstanceFieldGet
+ /// CHECK-DAG: StaticFieldGet
+ /// CHECK-DAG: StaticFieldGet
+ /// CHECK: Add
+ /// CHECK: Add
+ /// CHECK: Add
+ /// CHECK: Add
+ /// CHECK-DAG: InstanceFieldSet
+ /// CHECK-DAG: InstanceFieldSet
+ /// CHECK-DAG: StaticFieldSet
+ /// CHECK-DAG: StaticFieldSet
+
+ /// CHECK-START-ARM64: void Main.accessFields() scheduler (before)
+ /// CHECK: InstanceFieldGet
+ /// CHECK: Add
+ /// CHECK: InstanceFieldSet
+ /// CHECK: InstanceFieldGet
+ /// CHECK: Add
+ /// CHECK: InstanceFieldSet
+ /// CHECK: StaticFieldGet
+ /// CHECK: Add
+ /// CHECK: StaticFieldSet
+ /// CHECK: StaticFieldGet
+ /// CHECK: Add
+ /// CHECK: StaticFieldSet
+
+ /// CHECK-START-ARM64: void Main.accessFields() scheduler (after)
+ /// CHECK-DAG: InstanceFieldGet
+ /// CHECK-DAG: InstanceFieldGet
+ /// CHECK-DAG: StaticFieldGet
+ /// CHECK-DAG: StaticFieldGet
+ /// CHECK: Add
+ /// CHECK: Add
+ /// CHECK: Add
+ /// CHECK: Add
+ /// CHECK-DAG: InstanceFieldSet
+ /// CHECK-DAG: InstanceFieldSet
+ /// CHECK-DAG: StaticFieldSet
+ /// CHECK-DAG: StaticFieldSet
+ public void accessFields() {
+ my_obj = new ExampleObj(1, 2);
+ for (int i = 0; i < 10; i++) {
+ my_obj.n1++;
+ my_obj.n2++;
+ number1++;
+ number2++;
+ }
+ }
+
/// CHECK-START-ARM64: int Main.intDiv(int) scheduler (before)
/// CHECK: Sub
/// CHECK: DivZeroCheck