chromium/v8/src/compiler/scheduler.cc

// 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/compiler/scheduler.h"

#include <iomanip>
#include <optional>

#include "src/base/iterator.h"
#include "src/builtins/profile-data-reader.h"
#include "src/codegen/tick-counter.h"
#include "src/compiler/common-operator.h"
#include "src/compiler/control-equivalence.h"
#include "src/compiler/graph.h"
#include "src/compiler/node-marker.h"
#include "src/compiler/node-properties.h"
#include "src/compiler/node.h"
#include "src/utils/bit-vector.h"
#include "src/zone/zone-containers.h"

namespace v8 {
namespace internal {
namespace compiler {

#define TRACE …

Scheduler::Scheduler(Zone* zone, Graph* graph, Schedule* schedule, Flags flags,
                     size_t node_count_hint, TickCounter* tick_counter,
                     const ProfileDataFromFile* profile_data)
    : … { … }

Schedule* Scheduler::ComputeSchedule(Zone* zone, Graph* graph, Flags flags,
                                     TickCounter* tick_counter,
                                     const ProfileDataFromFile* profile_data) { … }

Scheduler::SchedulerData Scheduler::DefaultSchedulerData() { … }


Scheduler::SchedulerData* Scheduler::GetData(Node* node) { … }

Scheduler::Placement Scheduler::InitializePlacement(Node* node) { … }

Scheduler::Placement Scheduler::GetPlacement(Node* node) { … }

bool Scheduler::IsLive(Node* node) { … }

void Scheduler::UpdatePlacement(Node* node, Placement placement) { … }

std::optional<int> Scheduler::GetCoupledControlEdge(Node* node) { … }

void Scheduler::IncrementUnscheduledUseCount(Node* node, Node* from) { … }

void Scheduler::DecrementUnscheduledUseCount(Node* node, Node* from) { … }

// -----------------------------------------------------------------------------
// Phase 1: Build control-flow graph.


// Internal class to build a control flow graph (i.e the basic blocks and edges
// between them within a Schedule) from the node graph. Visits control edges of
// the graph backwards from an end node in order to find the connected control
// subgraph, needed for scheduling.
class CFGBuilder : public ZoneObject { … };


void Scheduler::BuildCFG() { … }


// -----------------------------------------------------------------------------
// Phase 2: Compute special RPO and dominator tree.


// Compute the special reverse-post-order block ordering, which is essentially
// a RPO of the graph where loop bodies are contiguous. Properties:
// 1. If block A is a predecessor of B, then A appears before B in the order,
//    unless B is a loop header and A is in the loop headed at B
//    (i.e. A -> B is a backedge).
// => If block A dominates block B, then A appears before B in the order.
// => If block A is a loop header, A appears before all blocks in the loop
//    headed at A.
// 2. All loops are contiguous in the order (i.e. no intervening blocks that
//    do not belong to the loop.)
// Note a simple RPO traversal satisfies (1) but not (2).
class SpecialRPONumberer : public ZoneObject { … };


BasicBlockVector* Scheduler::ComputeSpecialRPO(Zone* zone, Schedule* schedule) { … }


void Scheduler::ComputeSpecialRPONumbering() { … }

BasicBlock* Scheduler::GetCommonDominatorIfCached(BasicBlock* b1,
                                                  BasicBlock* b2) { … }

BasicBlock* Scheduler::GetCommonDominator(BasicBlock* b1, BasicBlock* b2) { … }

void Scheduler::PropagateImmediateDominators(BasicBlock* block) { … }

void Scheduler::GenerateDominatorTree(Schedule* schedule) { … }

void Scheduler::GenerateDominatorTree() { … }

// -----------------------------------------------------------------------------
// Phase 3: Prepare use counts for nodes.


class PrepareUsesVisitor { … };


void Scheduler::PrepareUses() { … }


// -----------------------------------------------------------------------------
// Phase 4: Schedule nodes early.


class ScheduleEarlyNodeVisitor { … };


void Scheduler::ScheduleEarly() { … }


// -----------------------------------------------------------------------------
// Phase 5: Schedule nodes late.


class ScheduleLateNodeVisitor { … };


void Scheduler::ScheduleLate() { … }


// -----------------------------------------------------------------------------
// Phase 6: Seal the final schedule.


void Scheduler::SealFinalSchedule() { … }


// -----------------------------------------------------------------------------


void Scheduler::FuseFloatingControl(BasicBlock* block, Node* node) { … }


void Scheduler::MovePlannedNodes(BasicBlock* from, BasicBlock* to) { … }

#undef TRACE

}  // namespace compiler
}  // namespace internal
}  // namespace v8