ART: Refactor SchedulingGraph for consistency and clarity
The CL moves functionality from SchedulingGraph to other classes,
deletes unused code and moves code used for testing to the tests source
file:
1. SchedulingGraph::AddDependency: move checks whether a dependency has
been added to SchedulingNode::Add*Predecessor as it is a SchedulingNode
responsibility to keep a unique set of predecessors.
2. Create SideEffectDependencyAnalysis class. Code doing side effect dependency
analysis is moved from SchedulingGraph into the class.
3. Remove SchedulingGraph::HasImmediate*Dependency methods as there are
SchedulingNode::Has*Dependency methods for such kind of checks.
4. SchedulingGraph::HasImmediate*Dependency(HInstruction,HInstruction) methods
are only used by tests. Their code is moved to a new class TestSchedulingGraph in
the tests source file.
Test: test.py --host --optimizing --jit --gtest
Test: test.py --target --optimizing --jit
Test: run-gtests.sh
Change-Id: Id16eb6e9f8b9706e616dff0ccc1d0353ed968367
diff --git a/compiler/optimizing/scheduler.cc b/compiler/optimizing/scheduler.cc
index fdef45e..e5ff8a8 100644
--- a/compiler/optimizing/scheduler.cc
+++ b/compiler/optimizing/scheduler.cc
@@ -43,34 +43,37 @@
}
if (is_data_dependency) {
- if (!HasImmediateDataDependency(node, dependency)) {
- node->AddDataPredecessor(dependency);
- }
- } else if (!HasImmediateOtherDependency(node, dependency)) {
+ node->AddDataPredecessor(dependency);
+ } else {
node->AddOtherPredecessor(dependency);
}
}
-static bool MayHaveReorderingDependency(SideEffects node, SideEffects other) {
+bool SideEffectDependencyAnalysis::HasReorderingDependency(const HInstruction* instr1,
+ const HInstruction* instr2) {
+ SideEffects instr1_side_effects = instr1->GetSideEffects();
+ SideEffects instr2_side_effects = instr2->GetSideEffects();
+
// Read after write.
- if (node.MayDependOn(other)) {
+ if (instr1_side_effects.MayDependOn(instr2_side_effects)) {
return true;
}
// Write after read.
- if (other.MayDependOn(node)) {
+ if (instr2_side_effects.MayDependOn(instr1_side_effects)) {
return true;
}
// Memory write after write.
- if (node.DoesAnyWrite() && other.DoesAnyWrite()) {
+ if (instr1_side_effects.DoesAnyWrite() && instr2_side_effects.DoesAnyWrite()) {
return true;
}
return false;
}
-size_t SchedulingGraph::ArrayAccessHeapLocation(HInstruction* instruction) const {
+size_t SideEffectDependencyAnalysis::MemoryDependencyAnalysis::ArrayAccessHeapLocation(
+ HInstruction* instruction) const {
DCHECK(heap_location_collector_ != nullptr);
size_t heap_loc = heap_location_collector_->GetArrayHeapLocation(instruction);
// This array access should be analyzed and added to HeapLocationCollector before.
@@ -78,19 +81,19 @@
return heap_loc;
}
-bool SchedulingGraph::ArrayAccessMayAlias(HInstruction* node,
- HInstruction* other) const {
+bool SideEffectDependencyAnalysis::MemoryDependencyAnalysis::ArrayAccessMayAlias(
+ HInstruction* instr1, HInstruction* instr2) const {
DCHECK(heap_location_collector_ != nullptr);
- size_t node_heap_loc = ArrayAccessHeapLocation(node);
- size_t other_heap_loc = ArrayAccessHeapLocation(other);
+ size_t instr1_heap_loc = ArrayAccessHeapLocation(instr1);
+ size_t instr2_heap_loc = ArrayAccessHeapLocation(instr2);
// For example: arr[0] and arr[0]
- if (node_heap_loc == other_heap_loc) {
+ if (instr1_heap_loc == instr2_heap_loc) {
return true;
}
// For example: arr[0] and arr[i]
- if (heap_location_collector_->MayAlias(node_heap_loc, other_heap_loc)) {
+ if (heap_location_collector_->MayAlias(instr1_heap_loc, instr2_heap_loc)) {
return true;
}
@@ -148,55 +151,55 @@
}
}
-size_t SchedulingGraph::FieldAccessHeapLocation(HInstruction* obj, const FieldInfo* field) const {
- DCHECK(obj != nullptr);
- DCHECK(field != nullptr);
+size_t SideEffectDependencyAnalysis::MemoryDependencyAnalysis::FieldAccessHeapLocation(
+ const HInstruction* instr) const {
+ DCHECK(instr != nullptr);
+ DCHECK(GetFieldInfo(instr) != nullptr);
DCHECK(heap_location_collector_ != nullptr);
- size_t heap_loc = heap_location_collector_->GetFieldHeapLocation(obj, field);
+ size_t heap_loc = heap_location_collector_->GetFieldHeapLocation(instr->InputAt(0),
+ GetFieldInfo(instr));
// 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 {
+bool SideEffectDependencyAnalysis::MemoryDependencyAnalysis::FieldAccessMayAlias(
+ const HInstruction* instr1, const HInstruction* instr2) const {
DCHECK(heap_location_collector_ != nullptr);
// Static and instance field accesses should not alias.
- if ((IsInstanceFieldAccess(node) && IsStaticFieldAccess(other)) ||
- (IsStaticFieldAccess(node) && IsInstanceFieldAccess(other))) {
+ if ((IsInstanceFieldAccess(instr1) && IsStaticFieldAccess(instr2)) ||
+ (IsStaticFieldAccess(instr1) && IsInstanceFieldAccess(instr2))) {
return false;
}
// If either of the field accesses is unresolved.
- if (IsUnresolvedFieldAccess(node) || IsUnresolvedFieldAccess(other)) {
+ if (IsUnresolvedFieldAccess(instr1) || IsUnresolvedFieldAccess(instr2)) {
// 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 instr1_field_access_heap_loc = FieldAccessHeapLocation(instr1);
+ size_t instr2_field_access_heap_loc = FieldAccessHeapLocation(instr2);
- 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) {
+ if (instr1_field_access_heap_loc == instr2_field_access_heap_loc) {
return true;
}
- if (!heap_location_collector_->MayAlias(node_loc, other_loc)) {
+ if (!heap_location_collector_->MayAlias(instr1_field_access_heap_loc,
+ instr2_field_access_heap_loc)) {
return false;
}
return true;
}
-bool SchedulingGraph::HasMemoryDependency(HInstruction* node,
- HInstruction* other) const {
- if (!MayHaveReorderingDependency(node->GetSideEffects(), other->GetSideEffects())) {
+bool SideEffectDependencyAnalysis::MemoryDependencyAnalysis::HasMemoryDependency(
+ HInstruction* instr1, HInstruction* instr2) const {
+ if (!HasReorderingDependency(instr1, instr2)) {
return false;
}
@@ -208,35 +211,35 @@
return true;
}
- if (IsArrayAccess(node) && IsArrayAccess(other)) {
- return ArrayAccessMayAlias(node, other);
+ if (IsArrayAccess(instr1) && IsArrayAccess(instr2)) {
+ return ArrayAccessMayAlias(instr1, instr2);
}
- if (IsFieldAccess(node) && IsFieldAccess(other)) {
- return FieldAccessMayAlias(node, other);
+ if (IsFieldAccess(instr1) && IsFieldAccess(instr2)) {
+ return FieldAccessMayAlias(instr1, instr2);
}
// TODO(xueliang): LSA to support alias analysis among HVecLoad, HVecStore and ArrayAccess
- if (node->IsVecMemoryOperation() && other->IsVecMemoryOperation()) {
+ if (instr1->IsVecMemoryOperation() && instr2->IsVecMemoryOperation()) {
return true;
}
- if (node->IsVecMemoryOperation() && IsArrayAccess(other)) {
+ if (instr1->IsVecMemoryOperation() && IsArrayAccess(instr2)) {
return true;
}
- if (IsArrayAccess(node) && other->IsVecMemoryOperation()) {
+ if (IsArrayAccess(instr1) && instr2->IsVecMemoryOperation()) {
return true;
}
// Heap accesses of different kinds should not alias.
- if (IsArrayAccess(node) && IsFieldAccess(other)) {
+ if (IsArrayAccess(instr1) && IsFieldAccess(instr2)) {
return false;
}
- if (IsFieldAccess(node) && IsArrayAccess(other)) {
+ if (IsFieldAccess(instr1) && IsArrayAccess(instr2)) {
return false;
}
- if (node->IsVecMemoryOperation() && IsFieldAccess(other)) {
+ if (instr1->IsVecMemoryOperation() && IsFieldAccess(instr2)) {
return false;
}
- if (IsFieldAccess(node) && other->IsVecMemoryOperation()) {
+ if (IsFieldAccess(instr1) && instr2->IsVecMemoryOperation()) {
return false;
}
@@ -245,15 +248,15 @@
return true;
}
-bool SchedulingGraph::HasExceptionDependency(const HInstruction* node,
- const HInstruction* other) const {
- if (other->CanThrow() && node->GetSideEffects().DoesAnyWrite()) {
+bool SideEffectDependencyAnalysis::HasExceptionDependency(const HInstruction* instr1,
+ const HInstruction* instr2) {
+ if (instr2->CanThrow() && instr1->GetSideEffects().DoesAnyWrite()) {
return true;
}
- if (other->GetSideEffects().DoesAnyWrite() && node->CanThrow()) {
+ if (instr2->GetSideEffects().DoesAnyWrite() && instr1->CanThrow()) {
return true;
}
- if (other->CanThrow() && node->CanThrow()) {
+ if (instr2->CanThrow() && instr1->CanThrow()) {
return true;
}
@@ -262,24 +265,6 @@
return false;
}
-// Check whether `node` depends on `other`, taking into account `SideEffect`
-// information and `CanThrow` information.
-bool SchedulingGraph::HasSideEffectDependency(HInstruction* node,
- 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;
- }
-
- return false;
-}
-
// Check if the specified instruction is a better candidate which more likely will
// have other instructions depending on it.
static bool IsBetterCandidateWithMoreLikelyDependencies(HInstruction* new_candidate,
@@ -297,8 +282,9 @@
}
}
-void SchedulingGraph::AddDependencies(HInstruction* instruction, bool is_scheduling_barrier) {
- SchedulingNode* instruction_node = GetNode(instruction);
+void SchedulingGraph::AddDependencies(SchedulingNode* instruction_node,
+ bool is_scheduling_barrier) {
+ HInstruction* instruction = instruction_node->GetInstruction();
// Define-use dependencies.
for (const HUseListNode<HInstruction*>& use : instruction->GetUses()) {
@@ -354,12 +340,12 @@
if (other_node->IsSchedulingBarrier()) {
// We have reached a scheduling barrier so we can stop further
// processing.
- DCHECK(HasImmediateOtherDependency(other_node, instruction_node));
+ DCHECK(other_node->HasOtherDependency(instruction_node));
break;
}
- if (HasSideEffectDependency(other, instruction)) {
+ if (side_effect_dependency_analysis_.HasSideEffectDependency(other, instruction)) {
if (dep_chain_candidate != nullptr &&
- HasSideEffectDependency(other, dep_chain_candidate)) {
+ side_effect_dependency_analysis_.HasSideEffectDependency(other, dep_chain_candidate)) {
// Skip an explicit dependency to reduce memory usage, rely on the transitive dependency.
} else {
AddOtherDependency(other_node, instruction_node);
@@ -388,44 +374,6 @@
}
}
-bool SchedulingGraph::HasImmediateDataDependency(const SchedulingNode* node,
- const SchedulingNode* other) const {
- return ContainsElement(node->GetDataPredecessors(), other);
-}
-
-bool SchedulingGraph::HasImmediateDataDependency(const HInstruction* instruction,
- const HInstruction* other_instruction) const {
- const SchedulingNode* node = GetNode(instruction);
- const SchedulingNode* other = GetNode(other_instruction);
- if (node == nullptr || other == nullptr) {
- // Both instructions must be in current basic block, i.e. the SchedulingGraph can see their
- // corresponding SchedulingNode in the graph, and tell whether there is a dependency.
- // Otherwise there is no dependency from SchedulingGraph's perspective, for example,
- // instruction and other_instruction are in different basic blocks.
- return false;
- }
- return HasImmediateDataDependency(node, other);
-}
-
-bool SchedulingGraph::HasImmediateOtherDependency(const SchedulingNode* node,
- const SchedulingNode* other) const {
- return ContainsElement(node->GetOtherPredecessors(), other);
-}
-
-bool SchedulingGraph::HasImmediateOtherDependency(const HInstruction* instruction,
- const HInstruction* other_instruction) const {
- const SchedulingNode* node = GetNode(instruction);
- const SchedulingNode* other = GetNode(other_instruction);
- if (node == nullptr || other == nullptr) {
- // Both instructions must be in current basic block, i.e. the SchedulingGraph can see their
- // corresponding SchedulingNode in the graph, and tell whether there is a dependency.
- // Otherwise there is no dependency from SchedulingGraph's perspective, for example,
- // instruction and other_instruction are in different basic blocks.
- return false;
- }
- return HasImmediateOtherDependency(node, other);
-}
-
static const std::string InstructionTypeId(const HInstruction* instruction) {
return DataType::TypeId(instruction->GetType()) + std::to_string(instruction->GetId());
}
@@ -594,7 +542,7 @@
ScopedArenaVector<SchedulingNode*> scheduling_nodes(allocator.Adapter(kArenaAllocScheduler));
// Build the scheduling graph.
- SchedulingGraph scheduling_graph(this, &allocator, heap_location_collector);
+ SchedulingGraph scheduling_graph(&allocator, heap_location_collector);
for (HBackwardInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) {
HInstruction* instruction = it.Current();
CHECK_EQ(instruction->GetBlock(), block)