diff options
Diffstat (limited to 'compiler/optimizing/scheduler.h')
| -rw-r--r-- | compiler/optimizing/scheduler.h | 487 |
1 files changed, 487 insertions, 0 deletions
diff --git a/compiler/optimizing/scheduler.h b/compiler/optimizing/scheduler.h new file mode 100644 index 0000000000..ab0dad4300 --- /dev/null +++ b/compiler/optimizing/scheduler.h @@ -0,0 +1,487 @@ +/* + * Copyright (C) 2016 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#ifndef ART_COMPILER_OPTIMIZING_SCHEDULER_H_ +#define ART_COMPILER_OPTIMIZING_SCHEDULER_H_ + +#include <fstream> + +#include "base/time_utils.h" +#include "driver/compiler_driver.h" +#include "nodes.h" +#include "optimization.h" + +namespace art { + +// General description of instruction scheduling. +// +// This pass tries to improve the quality of the generated code by reordering +// instructions in the graph to avoid execution delays caused by execution +// dependencies. +// Currently, scheduling is performed at the block level, so no `HInstruction` +// ever leaves its block in this pass. +// +// The scheduling process iterates through blocks in the graph. For blocks that +// we can and want to schedule: +// 1) Build a dependency graph for instructions. +// It includes data dependencies (inputs/uses), but also environment +// dependencies and side-effect dependencies. +// 2) Schedule the dependency graph. +// This is a topological sort of the dependency graph, using heuristics to +// decide what node to scheduler first when there are multiple candidates. +// +// A few factors impacting the quality of the scheduling are: +// - The heuristics used to decide what node to schedule in the topological sort +// when there are multiple valid candidates. There is a wide range of +// complexity possible here, going from a simple model only considering +// latencies, to a super detailed CPU pipeline model. +// - Fewer dependencies in the dependency graph give more freedom for the +// scheduling heuristics. For example de-aliasing can allow possibilities for +// reordering of memory accesses. +// - The level of abstraction of the IR. It is easier to evaluate scheduling for +// IRs that translate to a single assembly instruction than for IRs +// that generate multiple assembly instructions or generate different code +// depending on properties of the IR. +// - Scheduling is performed before register allocation, it is not aware of the +// impact of moving instructions on register allocation. +// +// +// The scheduling code uses the terms predecessors, successors, and dependencies. +// This can be confusing at times, so here are clarifications. +// These terms are used from the point of view of the program dependency graph. So +// the inputs of an instruction are part of its dependencies, and hence part its +// predecessors. So the uses of an instruction are (part of) its successors. +// (Side-effect dependencies can yield predecessors or successors that are not +// inputs or uses.) +// +// Here is a trivial example. For the Java code: +// +// int a = 1 + 2; +// +// we would have the instructions +// +// i1 HIntConstant 1 +// i2 HIntConstant 2 +// i3 HAdd [i1,i2] +// +// `i1` and `i2` are predecessors of `i3`. +// `i3` is a successor of `i1` and a successor of `i2`. +// In a scheduling graph for this code we would have three nodes `n1`, `n2`, +// and `n3` (respectively for instructions `i1`, `i1`, and `i3`). +// Conceptually the program dependency graph for this would contain two edges +// +// n1 -> n3 +// n2 -> n3 +// +// Since we schedule backwards (starting from the last instruction in each basic +// block), the implementation of nodes keeps a list of pointers their +// predecessors. So `n3` would keep pointers to its predecessors `n1` and `n2`. +// +// Node dependencies are also referred to from the program dependency graph +// point of view: we say that node `B` immediately depends on `A` if there is an +// edge from `A` to `B` in the program dependency graph. `A` is a predecessor of +// `B`, `B` is a successor of `A`. In the example above `n3` depends on `n1` and +// `n2`. +// Since nodes in the scheduling graph keep a list of their predecessors, node +// `B` will have a pointer to its predecessor `A`. +// As we schedule backwards, `B` will be selected for scheduling before `A` is. +// +// So the scheduling for the example above could happen as follow +// +// |---------------------------+------------------------| +// | candidates for scheduling | instructions scheduled | +// | --------------------------+------------------------| +// +// The only node without successors is `n3`, so it is the only initial +// candidate. +// +// | n3 | (none) | +// +// We schedule `n3` as the last (and only) instruction. All its predecessors +// that do not have any unscheduled successors become candidate. That is, `n1` +// and `n2` become candidates. +// +// | n1, n2 | n3 | +// +// One of the candidates is selected. In practice this is where scheduling +// heuristics kick in, to decide which of the candidates should be selected. +// In this example, let it be `n1`. It is scheduled before previously scheduled +// nodes (in program order). There are no other nodes to add to the list of +// candidates. +// +// | n2 | n1 | +// | | n3 | +// +// The only candidate available for scheduling is `n2`. Schedule it before +// (in program order) the previously scheduled nodes. +// +// | (none) | n2 | +// | | n1 | +// | | n3 | +// |---------------------------+------------------------| +// +// So finally the instructions will be executed in the order `i2`, `i1`, and `i3`. +// In this trivial example, it does not matter which of `i1` and `i2` is +// scheduled first since they are constants. However the same process would +// apply if `i1` and `i2` were actual operations (for example `HMul` and `HDiv`). + +// Set to true to have instruction scheduling dump scheduling graphs to the file +// `scheduling_graphs.dot`. See `SchedulingGraph::DumpAsDotGraph()`. +static constexpr bool kDumpDotSchedulingGraphs = false; + +// Typically used as a default instruction latency. +static constexpr uint32_t kGenericInstructionLatency = 1; + +class HScheduler; + +/** + * A node representing an `HInstruction` in the `SchedulingGraph`. + */ +class SchedulingNode : public ArenaObject<kArenaAllocScheduler> { + public: + SchedulingNode(HInstruction* instr, ArenaAllocator* arena, bool is_scheduling_barrier) + : latency_(0), + internal_latency_(0), + critical_path_(0), + instruction_(instr), + is_scheduling_barrier_(is_scheduling_barrier), + data_predecessors_(arena->Adapter(kArenaAllocScheduler)), + other_predecessors_(arena->Adapter(kArenaAllocScheduler)), + num_unscheduled_successors_(0) { + data_predecessors_.reserve(kPreallocatedPredecessors); + } + + void AddDataPredecessor(SchedulingNode* predecessor) { + data_predecessors_.push_back(predecessor); + predecessor->num_unscheduled_successors_++; + } + + void AddOtherPredecessor(SchedulingNode* predecessor) { + other_predecessors_.push_back(predecessor); + predecessor->num_unscheduled_successors_++; + } + + void DecrementNumberOfUnscheduledSuccessors() { + num_unscheduled_successors_--; + } + + void MaybeUpdateCriticalPath(uint32_t other_critical_path) { + critical_path_ = std::max(critical_path_, other_critical_path); + } + + bool HasUnscheduledSuccessors() const { + return num_unscheduled_successors_ != 0; + } + + HInstruction* GetInstruction() const { return instruction_; } + uint32_t GetLatency() const { return latency_; } + void SetLatency(uint32_t latency) { latency_ = latency; } + uint32_t GetInternalLatency() const { return internal_latency_; } + void SetInternalLatency(uint32_t internal_latency) { internal_latency_ = internal_latency; } + uint32_t GetCriticalPath() const { return critical_path_; } + bool IsSchedulingBarrier() const { return is_scheduling_barrier_; } + const ArenaVector<SchedulingNode*>& GetDataPredecessors() const { return data_predecessors_; } + const ArenaVector<SchedulingNode*>& GetOtherPredecessors() const { return other_predecessors_; } + + 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 + // produced by this node is available to users. + uint32_t latency_; + // This represents the time spent *within* the generated code for this node. + // It should be zero for nodes that only generate a single instruction. + uint32_t internal_latency_; + + // The critical path from this instruction to the end of scheduling. It is + // used by the scheduling heuristics to measure the priority of this instruction. + // It is defined as + // critical_path_ = latency_ + max((use.internal_latency_ + use.critical_path_) for all uses) + // (Note that here 'uses' is equivalent to 'data successors'. Also see comments in + // `HScheduler::Schedule(SchedulingNode* scheduling_node)`). + uint32_t critical_path_; + + // The instruction that this node represents. + HInstruction* const instruction_; + + // If a node is scheduling barrier, other nodes cannot be scheduled before it. + const bool is_scheduling_barrier_; + + // The lists of predecessors. They cannot be scheduled before this node. Once + // this node is scheduled, we check whether any of its predecessors has become a + // valid candidate for scheduling. + // Predecessors in `data_predecessors_` are data dependencies. Those in + // `other_predecessors_` contain side-effect dependencies, environment + // dependencies, and scheduling barrier dependencies. + ArenaVector<SchedulingNode*> data_predecessors_; + ArenaVector<SchedulingNode*> other_predecessors_; + + // The number of unscheduled successors for this node. This number is + // decremented as successors are scheduled. When it reaches zero this node + // becomes a valid candidate to schedule. + uint32_t num_unscheduled_successors_; + + static constexpr size_t kPreallocatedPredecessors = 4; +}; + +/* + * Directed acyclic graph for scheduling. + */ +class SchedulingGraph : public ValueObject { + public: + SchedulingGraph(const HScheduler* scheduler, ArenaAllocator* arena) + : scheduler_(scheduler), + arena_(arena), + contains_scheduling_barrier_(false), + nodes_map_(arena_->Adapter(kArenaAllocScheduler)) {} + + SchedulingNode* AddNode(HInstruction* instr, bool is_scheduling_barrier = false) { + SchedulingNode* node = new (arena_) SchedulingNode(instr, arena_, is_scheduling_barrier); + nodes_map_.Insert(std::make_pair(instr, node)); + contains_scheduling_barrier_ |= is_scheduling_barrier; + AddDependencies(instr, is_scheduling_barrier); + return node; + } + + void Clear() { + nodes_map_.Clear(); + contains_scheduling_barrier_ = false; + } + + SchedulingNode* GetNode(const HInstruction* instr) const { + auto it = nodes_map_.Find(instr); + if (it == nodes_map_.end()) { + return nullptr; + } else { + return it->second; + } + } + + 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(); + } + + // Dump the scheduling graph, in dot file format, appending it to the file + // `scheduling_graphs.dot`. + void DumpAsDotGraph(const std::string& description, + const ArenaVector<SchedulingNode*>& initial_candidates); + + protected: + void AddDependency(SchedulingNode* node, SchedulingNode* dependency, bool is_data_dependency); + void AddDataDependency(SchedulingNode* node, SchedulingNode* dependency) { + AddDependency(node, dependency, /*is_data_dependency*/true); + } + void AddOtherDependency(SchedulingNode* node, SchedulingNode* dependency) { + AddDependency(node, dependency, /*is_data_dependency*/false); + } + + // 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_; + + ArenaAllocator* const arena_; + + bool contains_scheduling_barrier_; + + ArenaHashMap<const HInstruction*, SchedulingNode*> nodes_map_; +}; + +/* + * The visitors derived from this base class are used by schedulers to evaluate + * the latencies of `HInstruction`s. + */ +class SchedulingLatencyVisitor : public HGraphDelegateVisitor { + public: + // This class and its sub-classes will never be used to drive a visit of an + // `HGraph` but only to visit `HInstructions` one at a time, so we do not need + // to pass a valid graph to `HGraphDelegateVisitor()`. + SchedulingLatencyVisitor() : HGraphDelegateVisitor(nullptr) {} + + void VisitInstruction(HInstruction* instruction) OVERRIDE { + LOG(FATAL) << "Error visiting " << instruction->DebugName() << ". " + "Architecture-specific scheduling latency visitors must handle all instructions" + " (potentially by overriding the generic `VisitInstruction()`."; + UNREACHABLE(); + } + + void Visit(HInstruction* instruction) { + instruction->Accept(this); + } + + void CalculateLatency(SchedulingNode* node) { + // By default nodes have no internal latency. + last_visited_internal_latency_ = 0; + Visit(node->GetInstruction()); + } + + uint32_t GetLastVisitedLatency() const { return last_visited_latency_; } + uint32_t GetLastVisitedInternalLatency() const { return last_visited_internal_latency_; } + + protected: + // The latency of the most recent visited SchedulingNode. + // This is for reporting the latency value to the user of this visitor. + uint32_t last_visited_latency_; + // This represents the time spent *within* the generated code for the most recent visited + // SchedulingNode. This is for reporting the internal latency value to the user of this visitor. + uint32_t last_visited_internal_latency_; +}; + +class SchedulingNodeSelector : public ArenaObject<kArenaAllocScheduler> { + public: + virtual SchedulingNode* PopHighestPriorityNode(ArenaVector<SchedulingNode*>* nodes, + const SchedulingGraph& graph) = 0; + virtual ~SchedulingNodeSelector() {} + protected: + static void DeleteNodeAtIndex(ArenaVector<SchedulingNode*>* nodes, size_t index) { + (*nodes)[index] = nodes->back(); + nodes->pop_back(); + } +}; + +/* + * Select a `SchedulingNode` at random within the candidates. + */ +class RandomSchedulingNodeSelector : public SchedulingNodeSelector { + public: + explicit RandomSchedulingNodeSelector() : seed_(0) { + seed_ = static_cast<uint32_t>(NanoTime()); + srand(seed_); + } + + SchedulingNode* PopHighestPriorityNode(ArenaVector<SchedulingNode*>* nodes, + const SchedulingGraph& graph) OVERRIDE { + UNUSED(graph); + DCHECK(!nodes->empty()); + size_t select = rand_r(&seed_) % nodes->size(); + SchedulingNode* select_node = (*nodes)[select]; + DeleteNodeAtIndex(nodes, select); + return select_node; + } + + uint32_t seed_; +}; + +/* + * Select a `SchedulingNode` according to critical path information, + * with heuristics to favor certain instruction patterns like materialized condition. + */ +class CriticalPathSchedulingNodeSelector : public SchedulingNodeSelector { + public: + CriticalPathSchedulingNodeSelector() : prev_select_(nullptr) {} + + SchedulingNode* PopHighestPriorityNode(ArenaVector<SchedulingNode*>* nodes, + const SchedulingGraph& graph) OVERRIDE; + + protected: + SchedulingNode* GetHigherPrioritySchedulingNode(SchedulingNode* candidate, + SchedulingNode* check) const; + + SchedulingNode* SelectMaterializedCondition(ArenaVector<SchedulingNode*>* nodes, + const SchedulingGraph& graph) const; + + private: + const SchedulingNode* prev_select_; +}; + +class HScheduler { + public: + HScheduler(ArenaAllocator* arena, + SchedulingLatencyVisitor* latency_visitor, + SchedulingNodeSelector* selector) + : arena_(arena), + latency_visitor_(latency_visitor), + selector_(selector), + only_optimize_loop_blocks_(true), + scheduling_graph_(this, arena), + candidates_(arena_->Adapter(kArenaAllocScheduler)) {} + virtual ~HScheduler() {} + + void Schedule(HGraph* graph); + + void SetOnlyOptimizeLoopBlocks(bool loop_only) { only_optimize_loop_blocks_ = loop_only; } + + // Instructions can not be rescheduled across a scheduling barrier. + virtual bool IsSchedulingBarrier(const HInstruction* instruction) const; + + protected: + void Schedule(HBasicBlock* block); + void Schedule(SchedulingNode* scheduling_node); + void Schedule(HInstruction* instruction); + + // Any instruction returning `false` via this method will prevent its + // containing basic block from being scheduled. + // This method is used to restrict scheduling to instructions that we know are + // safe to handle. + virtual bool IsSchedulable(const HInstruction* instruction) const; + bool IsSchedulable(const HBasicBlock* block) const; + + void CalculateLatency(SchedulingNode* node) { + latency_visitor_->CalculateLatency(node); + node->SetLatency(latency_visitor_->GetLastVisitedLatency()); + node->SetInternalLatency(latency_visitor_->GetLastVisitedInternalLatency()); + } + + ArenaAllocator* const arena_; + SchedulingLatencyVisitor* const latency_visitor_; + SchedulingNodeSelector* const selector_; + bool only_optimize_loop_blocks_; + + // We instantiate the members below as part of this class to avoid + // instantiating them locally for every chunk scheduled. + SchedulingGraph scheduling_graph_; + // A pointer indicating where the next instruction to be scheduled will be inserted. + HInstruction* cursor_; + // The list of candidates for scheduling. A node becomes a candidate when all + // its predecessors have been scheduled. + ArenaVector<SchedulingNode*> candidates_; + + private: + 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, InstructionSet instruction_set) + : HOptimization(graph, kInstructionScheduling), + instruction_set_(instruction_set) {} + + void Run() { + Run(/*only_optimize_loop_blocks*/ true, /*schedule_randomly*/ false); + } + void Run(bool only_optimize_loop_blocks, bool schedule_randomly); + + static constexpr const char* kInstructionScheduling = "scheduler"; + + const InstructionSet instruction_set_; + + private: + DISALLOW_COPY_AND_ASSIGN(HInstructionScheduling); +}; + +} // namespace art + +#endif // ART_COMPILER_OPTIMIZING_SCHEDULER_H_ |