blob: d8934ec1572d4317f6de578339eb40ccf47d7295 [file] [log] [blame]
// Copyright 2013 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
#include "src/base/flags.h"
#include "src/common/globals.h"
#include "src/compiler/node.h"
#include "src/compiler/opcodes.h"
#include "src/compiler/schedule.h"
#include "src/compiler/zone-stats.h"
#include "src/zone/zone-containers.h"
namespace v8 {
namespace internal {
class ProfileDataFromFile;
class TickCounter;
namespace compiler {
// Forward declarations.
class CFGBuilder;
class ControlEquivalence;
class Graph;
class SpecialRPONumberer;
// Computes a schedule from a graph, placing nodes into basic blocks and
// ordering the basic blocks in the special RPO order.
class V8_EXPORT_PRIVATE Scheduler {
// Flags that control the mode of operation.
enum Flag { kNoFlags = 0u, kSplitNodes = 1u << 1, kTempSchedule = 1u << 2 };
using Flags = base::Flags<Flag>;
// The complete scheduling algorithm. Creates a new schedule and places all
// nodes from the graph into it.
static Schedule* ComputeSchedule(Zone* temp_zone, Graph* graph, Flags flags,
TickCounter* tick_counter,
const ProfileDataFromFile* profile_data);
// Compute the RPO of blocks in an existing schedule.
static BasicBlockVector* ComputeSpecialRPO(Zone* zone, Schedule* schedule);
// Computes the dominator tree on an existing schedule that has RPO computed.
static void GenerateDominatorTree(Schedule* schedule);
const ProfileDataFromFile* profile_data() const { return profile_data_; }
// Placement of a node changes during scheduling. The placement state
// transitions over time while the scheduler is choosing a position:
// +---------------------+-----+----> kFixed
// / / /
// kUnknown ----+------> kCoupled ----+ /
// \ /
// +----> kSchedulable ----+--------> kScheduled
// 1) InitializePlacement(): kUnknown -> kCoupled|kSchedulable|kFixed
// 2) UpdatePlacement(): kCoupled|kSchedulable -> kFixed|kScheduled
// We maintain the invariant that all nodes that are not reachable
// from the end have kUnknown placement. After the PrepareUses phase runs,
// also the opposite is true - all nodes with kUnknown placement are not
// reachable from the end.
enum Placement { kUnknown, kSchedulable, kFixed, kCoupled, kScheduled };
// Per-node data tracked during scheduling.
struct SchedulerData {
BasicBlock* minimum_block_; // Minimum legal RPO placement.
int unscheduled_count_; // Number of unscheduled uses of this node.
Placement placement_; // Whether the node is fixed, schedulable,
// coupled to another node, or not yet known.
Zone* zone_;
Graph* graph_;
Schedule* schedule_;
Flags flags_;
scheduled_nodes_; // Per-block list of nodes in reverse.
NodeVector schedule_root_nodes_; // Fixed root nodes seed the worklist.
ZoneQueue<Node*> schedule_queue_; // Worklist of schedulable nodes.
ZoneVector<SchedulerData> node_data_; // Per-node data for all nodes.
CFGBuilder* control_flow_builder_; // Builds basic blocks for controls.
SpecialRPONumberer* special_rpo_; // Special RPO numbering of blocks.
ControlEquivalence* equivalence_; // Control dependence equivalence.
TickCounter* const tick_counter_;
const ProfileDataFromFile* profile_data_;
Scheduler(Zone* zone, Graph* graph, Schedule* schedule, Flags flags,
size_t node_count_hint_, TickCounter* tick_counter,
const ProfileDataFromFile* profile_data);
inline SchedulerData DefaultSchedulerData();
inline SchedulerData* GetData(Node* node);
Placement GetPlacement(Node* node);
Placement InitializePlacement(Node* node);
void UpdatePlacement(Node* node, Placement placement);
bool IsLive(Node* node);
inline bool IsCoupledControlEdge(Node* node, int index);
void IncrementUnscheduledUseCount(Node* node, int index, Node* from);
void DecrementUnscheduledUseCount(Node* node, int index, Node* from);
static void PropagateImmediateDominators(BasicBlock* block);
// Phase 1: Build control-flow graph.
friend class CFGBuilder;
void BuildCFG();
// Phase 2: Compute special RPO and dominator tree.
friend class SpecialRPONumberer;
void ComputeSpecialRPONumbering();
void GenerateDominatorTree();
// Phase 3: Prepare use counts for nodes.
friend class PrepareUsesVisitor;
void PrepareUses();
// Phase 4: Schedule nodes early.
friend class ScheduleEarlyNodeVisitor;
void ScheduleEarly();
// Phase 5: Schedule nodes late.
friend class ScheduleLateNodeVisitor;
void ScheduleLate();
// Phase 6: Seal the final schedule.
void SealFinalSchedule();
void FuseFloatingControl(BasicBlock* block, Node* node);
void MovePlannedNodes(BasicBlock* from, BasicBlock* to);
} // namespace compiler
} // namespace internal
} // namespace v8