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.h b/compiler/optimizing/scheduler.h
index d2dbeca..a97eda7 100644
--- a/compiler/optimizing/scheduler.h
+++ b/compiler/optimizing/scheduler.h
@@ -21,6 +21,7 @@
#include "base/scoped_arena_allocator.h"
#include "base/scoped_arena_containers.h"
+#include "base/stl_util.h"
#include "base/time_utils.h"
#include "code_generator.h"
#include "load_store_analysis.h"
@@ -168,6 +169,10 @@
}
void AddDataPredecessor(SchedulingNode* predecessor) {
+ // Check whether the predecessor has been added earlier.
+ if (HasDataDependency(predecessor)) {
+ return;
+ }
data_predecessors_.push_back(predecessor);
predecessor->num_unscheduled_successors_++;
}
@@ -177,6 +182,10 @@
}
void AddOtherPredecessor(SchedulingNode* predecessor) {
+ // Check whether the predecessor has been added earlier.
+ if (HasOtherDependency(predecessor)) {
+ return;
+ }
other_predecessors_.push_back(predecessor);
predecessor->num_unscheduled_successors_++;
}
@@ -205,6 +214,14 @@
uint32_t GetCriticalPath() const { return critical_path_; }
bool IsSchedulingBarrier() const { return is_scheduling_barrier_; }
+ bool HasDataDependency(const SchedulingNode* node) const {
+ return ContainsElement(data_predecessors_, node);
+ }
+
+ bool HasOtherDependency(const SchedulingNode* node) const {
+ return ContainsElement(other_predecessors_, node);
+ }
+
private:
// The latency of this node. It represents the latency between the moment the
// last instruction for this node has executed to the moment the result
@@ -246,18 +263,67 @@
};
/*
+ * Provide analysis of instruction dependencies (side effects) which are not in a form of explicit
+ * def-use data dependencies.
+ */
+class SideEffectDependencyAnalysis {
+ public:
+ explicit SideEffectDependencyAnalysis(const HeapLocationCollector* heap_location_collector)
+ : memory_dependency_analysis_(heap_location_collector) {}
+
+ bool HasSideEffectDependency(HInstruction* instr1, HInstruction* instr2) const {
+ if (memory_dependency_analysis_.HasMemoryDependency(instr1, instr2)) {
+ 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(instr1, instr2)) {
+ return true;
+ }
+
+ return false;
+ }
+
+ private:
+ static bool HasExceptionDependency(const HInstruction* instr1, const HInstruction* instr2);
+ static bool HasReorderingDependency(const HInstruction* instr1, const HInstruction* instr2);
+
+ /*
+ * Memory dependency analysis of instructions based on their memory side effects
+ * and heap location information from the LCA pass if it is provided.
+ */
+ class MemoryDependencyAnalysis {
+ public:
+ explicit MemoryDependencyAnalysis(const HeapLocationCollector* heap_location_collector)
+ : heap_location_collector_(heap_location_collector) {}
+
+ bool HasMemoryDependency(HInstruction* instr1, HInstruction* instr2) const;
+
+ private:
+ bool ArrayAccessMayAlias(HInstruction* instr1, HInstruction* instr2) const;
+ bool FieldAccessMayAlias(const HInstruction* instr1, const HInstruction* instr2) const;
+ size_t ArrayAccessHeapLocation(HInstruction* instruction) const;
+ size_t FieldAccessHeapLocation(const HInstruction* instruction) const;
+
+ const HeapLocationCollector* const heap_location_collector_;
+ };
+
+ MemoryDependencyAnalysis memory_dependency_analysis_;
+};
+
+/*
* Directed acyclic graph for scheduling.
*/
class SchedulingGraph : public ValueObject {
public:
- SchedulingGraph(const HScheduler* scheduler,
- ScopedArenaAllocator* allocator,
+ SchedulingGraph(ScopedArenaAllocator* allocator,
const HeapLocationCollector* heap_location_collector)
- : scheduler_(scheduler),
- allocator_(allocator),
+ : allocator_(allocator),
contains_scheduling_barrier_(false),
nodes_map_(allocator_->Adapter(kArenaAllocScheduler)),
- heap_location_collector_(heap_location_collector) {}
+ side_effect_dependency_analysis_(heap_location_collector) {}
SchedulingNode* AddNode(HInstruction* instr, bool is_scheduling_barrier = false) {
std::unique_ptr<SchedulingNode> node(
@@ -265,7 +331,7 @@
SchedulingNode* result = node.get();
nodes_map_.insert(std::make_pair(instr, std::move(node)));
contains_scheduling_barrier_ |= is_scheduling_barrier;
- AddDependencies(instr, is_scheduling_barrier);
+ AddDependencies(result, is_scheduling_barrier);
return result;
}
@@ -278,13 +344,6 @@
}
}
- bool IsSchedulingBarrier(const HInstruction* instruction) const;
-
- bool HasImmediateDataDependency(const SchedulingNode* node, const SchedulingNode* other) const;
- bool HasImmediateDataDependency(const HInstruction* node, const HInstruction* other) const;
- bool HasImmediateOtherDependency(const SchedulingNode* node, const SchedulingNode* other) const;
- bool HasImmediateOtherDependency(const HInstruction* node, const HInstruction* other) const;
-
size_t Size() const {
return nodes_map_.size();
}
@@ -302,26 +361,14 @@
void AddOtherDependency(SchedulingNode* node, SchedulingNode* dependency) {
AddDependency(node, dependency, /*is_data_dependency*/false);
}
- bool HasMemoryDependency(HInstruction* node, HInstruction* other) const;
- bool HasExceptionDependency(const HInstruction* node, const HInstruction* other) const;
- bool HasSideEffectDependency(HInstruction* node, HInstruction* other) const;
- bool ArrayAccessMayAlias(HInstruction* node, HInstruction* other) const;
- bool FieldAccessMayAlias(const HInstruction* node, const HInstruction* other) const;
- size_t ArrayAccessHeapLocation(HInstruction* instruction) 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);
-
- const HScheduler* const scheduler_;
+ // Add dependencies nodes for the given `SchedulingNode`: inputs, environments, and side-effects.
+ void AddDependencies(SchedulingNode* node, bool is_scheduling_barrier = false);
ScopedArenaAllocator* const allocator_;
-
bool contains_scheduling_barrier_;
-
ScopedArenaHashMap<const HInstruction*, std::unique_ptr<SchedulingNode>> nodes_map_;
-
- const HeapLocationCollector* const heap_location_collector_;
+ SideEffectDependencyAnalysis side_effect_dependency_analysis_;
};
/*
@@ -477,10 +524,6 @@
DISALLOW_COPY_AND_ASSIGN(HScheduler);
};
-inline bool SchedulingGraph::IsSchedulingBarrier(const HInstruction* instruction) const {
- return scheduler_->IsSchedulingBarrier(instruction);
-}
-
class HInstructionScheduling : public HOptimization {
public:
HInstructionScheduling(HGraph* graph,