Update V8 to version 4.1.0.21
This is a cherry-pick of all commits up to and including the
4.1.0.21 cherry-pick in Chromium.
Original commit message:
Version 4.1.0.21 (cherry-pick)
Merged 206e9136bde0f2b5ae8cb77afbb1e7833e5bd412
Unlink pages from the space page list after evacuation.
BUG=430201
LOG=N
R=jkummerow@chromium.org
Review URL: https://codereview.chromium.org/953813002
Cr-Commit-Position: refs/branch-heads/4.1@{#22}
Cr-Branched-From: 2e08d2a7aa9d65d269d8c57aba82eb38a8cb0a18-refs/heads/candidates@{#25353}
---
FPIIM-449
Change-Id: I8c23c7bbb70772b4858fe8a47b64fa97ee0d1f8c
diff --git a/src/compiler/scheduler.h b/src/compiler/scheduler.h
index b21662f..9da0b6d 100644
--- a/src/compiler/scheduler.h
+++ b/src/compiler/scheduler.h
@@ -9,89 +9,106 @@
#include "src/compiler/opcodes.h"
#include "src/compiler/schedule.h"
+#include "src/compiler/zone-pool.h"
#include "src/zone-containers.h"
namespace v8 {
namespace internal {
namespace compiler {
+class CFGBuilder;
+class ControlEquivalence;
+class SpecialRPONumberer;
+
// Computes a schedule from a graph, placing nodes into basic blocks and
// ordering the basic blocks in the special RPO order.
class Scheduler {
public:
- // The complete scheduling algorithm.
- // Create a new schedule and place all nodes from the graph into it.
- static Schedule* ComputeSchedule(Graph* graph);
+ // The complete scheduling algorithm. Creates a new schedule and places all
+ // nodes from the graph into it.
+ static Schedule* ComputeSchedule(Zone* zone, Graph* graph);
// Compute the RPO of blocks in an existing schedule.
- static BasicBlockVector* ComputeSpecialRPO(Schedule* schedule);
-
- // (Exposed for testing only)
- // Build and connect the CFG for a node graph, but don't schedule nodes.
- static void ComputeCFG(Graph* graph, Schedule* schedule);
+ static BasicBlockVector* ComputeSpecialRPO(Zone* zone, Schedule* schedule);
private:
- enum Placement { kUnknown, kSchedulable, kFixed };
+ // 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) GetPlacement(): kUnknown -> kCoupled|kSchedulable|kFixed
+ // 2) UpdatePlacement(): kCoupled|kSchedulable -> kFixed|kScheduled
+ 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.
- int minimum_rpo_; // Minimum legal RPO placement.
- bool is_connected_control_; // {true} if control-connected to the end node.
- bool is_floating_control_; // {true} if control, but not control-connected
- // to the end node.
- Placement placement_ : 3; // Whether the node is fixed, schedulable,
- // or not yet known.
+ Placement placement_; // Whether the node is fixed, schedulable,
+ // coupled to another node, or not yet known.
};
Zone* zone_;
Graph* graph_;
Schedule* schedule_;
- NodeVectorVector scheduled_nodes_;
- NodeVector schedule_root_nodes_;
- ZoneVector<SchedulerData> node_data_;
- bool has_floating_control_;
+ NodeVectorVector 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.
Scheduler(Zone* zone, Graph* graph, Schedule* schedule);
- SchedulerData DefaultSchedulerData();
-
- SchedulerData* GetData(Node* node) {
- DCHECK(node->id() < static_cast<int>(node_data_.size()));
- return &node_data_[node->id()];
- }
-
- void BuildCFG();
+ inline SchedulerData DefaultSchedulerData();
+ inline SchedulerData* GetData(Node* node);
Placement GetPlacement(Node* node);
+ void UpdatePlacement(Node* node, Placement placement);
- int GetRPONumber(BasicBlock* block) {
- DCHECK(block->rpo_number_ >= 0 &&
- block->rpo_number_ < static_cast<int>(schedule_->rpo_order_.size()));
- DCHECK(schedule_->rpo_order_[block->rpo_number_] == block);
- return block->rpo_number_;
- }
+ inline bool IsCoupledControlEdge(Node* node, int index);
+ void IncrementUnscheduledUseCount(Node* node, int index, Node* from);
+ void DecrementUnscheduledUseCount(Node* node, int index, Node* from);
- void GenerateImmediateDominatorTree();
BasicBlock* GetCommonDominator(BasicBlock* b1, BasicBlock* b2);
+ void PropagateImmediateDominators(BasicBlock* block);
+ // Phase 1: Build control-flow graph.
friend class CFGBuilder;
+ void BuildCFG();
- friend class ScheduleEarlyNodeVisitor;
- void ScheduleEarly();
+ // Phase 2: Compute special RPO and dominator tree.
+ friend class SpecialRPONumberer;
+ void ComputeSpecialRPONumbering();
+ void GenerateImmediateDominatorTree();
+ // 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();
- bool ConnectFloatingControl();
+ // Phase 6: Seal the final schedule.
+ void SealFinalSchedule();
- void ConnectFloatingControlSubgraph(BasicBlock* block, Node* node);
+ void FuseFloatingControl(BasicBlock* block, Node* node);
+ void MovePlannedNodes(BasicBlock* from, BasicBlock* to);
};
-}
-}
-} // namespace v8::internal::compiler
+
+} // namespace compiler
+} // namespace internal
+} // namespace v8
#endif // V8_COMPILER_SCHEDULER_H_