Lines Matching defs:node
15 #include "src/compiler/node-marker.h"
16 #include "src/compiler/node-properties.h"
17 #include "src/compiler/node.h"
54 // Reserve 10% more space for nodes if node splitting is enabled to try to
83 Scheduler::SchedulerData* Scheduler::GetData(Node* node) {
84 return &node_data_[node->id()];
87 Scheduler::Placement Scheduler::InitializePlacement(Node* node) {
88 SchedulerData* data = GetData(node);
95 switch (node->opcode()) {
104 // otherwise they are coupled to a floating control node.
105 Placement p = GetPlacement(NodeProperties::GetControlInput(node));
117 Scheduler::Placement Scheduler::GetPlacement(Node* node) {
118 return GetData(node)->placement_;
121 bool Scheduler::IsLive(Node* node) { return GetPlacement(node) != kUnknown; }
123 void Scheduler::UpdatePlacement(Node* node, Placement placement) {
124 SchedulerData* data = GetData(node);
127 // should check that {node} is a control node (including exceptional calls),
134 switch (node->opcode()) {
143 Node* control = NodeProperties::GetControlInput(node);
145 schedule_->AddNode(block, node);
153 for (auto use : node->uses()) {
155 DCHECK_EQ(node, NodeProperties::GetControlInput(use));
166 // Reduce the use count of the node's inputs to potentially make them
167 // schedulable. If all the uses of a node have been scheduled, then the node
169 base::Optional<int> coupled_control_edge = GetCoupledControlEdge(node);
170 for (Edge const edge : node->input_edges()) {
171 DCHECK_EQ(node, edge.from());
173 DecrementUnscheduledUseCount(edge.to(), node);
179 base::Optional<int> Scheduler::GetCoupledControlEdge(Node* node) {
180 if (GetPlacement(node) == kCoupled) {
181 return NodeProperties::FirstControlIndex(node);
186 void Scheduler::IncrementUnscheduledUseCount(Node* node, Node* from) {
188 if (GetPlacement(node) == kFixed) return;
191 if (GetPlacement(node) == kCoupled) {
192 node = NodeProperties::GetControlInput(node);
193 DCHECK_NE(GetPlacement(node), Placement::kFixed);
194 DCHECK_NE(GetPlacement(node), Placement::kCoupled);
197 ++(GetData(node)->unscheduled_count_);
199 TRACE(" Use count of #%d:%s (used by #%d:%s)++ = %d\n", node->id(),
200 node->op()->mnemonic(), from->id(), from->op()->mnemonic(),
201 GetData(node)->unscheduled_count_);
205 void Scheduler::DecrementUnscheduledUseCount(Node* node, Node* from) {
207 if (GetPlacement(node) == kFixed) return;
210 if (GetPlacement(node) == kCoupled) {
211 node = NodeProperties::GetControlInput(node);
212 DCHECK_NE(GetPlacement(node), Placement::kFixed);
213 DCHECK_NE(GetPlacement(node), Placement::kCoupled);
216 DCHECK_LT(0, GetData(node)->unscheduled_count_);
217 --(GetData(node)->unscheduled_count_);
219 TRACE(" Use count of #%d:%s (used by #%d:%s)-- = %d\n", node->id(),
220 node->op()->mnemonic(), from->id(), from->op()->mnemonic(),
221 GetData(node)->unscheduled_count_);
223 if (GetData(node)->unscheduled_count_ == 0) {
224 TRACE(" newly eligible #%d:%s\n", node->id(), node->op()->mnemonic());
225 schedule_queue_.push(node);
234 // between them within a Schedule) from the node graph. Visits control edges of
235 // the graph backwards from an end node in order to find the connected control
259 Node* node = queue_.front();
261 int max = NodeProperties::PastControlIndex(node);
262 for (int i = NodeProperties::FirstControlIndex(node); i < max; i++) {
263 Queue(node->InputAt(i));
285 Node* node = queue_.front();
290 if (IsSingleEntrySingleExitRegion(node, exit)) {
291 TRACE("Found SESE at #%d:%s\n", node->id(), node->op()->mnemonic());
293 component_entry_ = node;
297 int max = NodeProperties::PastControlIndex(node);
298 for (int i = NodeProperties::FirstControlIndex(node); i < max; i++) {
299 Queue(node->InputAt(i));
313 void FixNode(BasicBlock* block, Node* node) {
314 schedule_->AddNode(block, node);
315 scheduler_->UpdatePlacement(node, Scheduler::kFixed);
318 void Queue(Node* node) {
320 if (!queued_.Get(node)) {
321 BuildBlocks(node);
322 queue_.push(node);
323 queued_.Set(node, true);
324 control_.push_back(node);
328 void BuildBlocks(Node* node) {
329 switch (node->opcode()) {
331 FixNode(schedule_->end(), node);
334 FixNode(schedule_->start(), node);
338 BuildBlockForNode(node);
342 Node* loop = NodeProperties::GetControlInput(node);
344 FixNode(block, node);
349 BuildBlocksForSuccessors(node);
356 if (NodeProperties::IsExceptionalCall(node)) {
357 BuildBlocksForSuccessors(node);
365 void ConnectBlocks(Node* node) {
366 switch (node->opcode()) {
369 ConnectMerge(node);
372 scheduler_->UpdatePlacement(node, Scheduler::kFixed);
373 ConnectBranch(node);
376 scheduler_->UpdatePlacement(node, Scheduler::kFixed);
377 ConnectSwitch(node);
380 scheduler_->UpdatePlacement(node, Scheduler::kFixed);
381 ConnectDeoptimize(node);
384 scheduler_->UpdatePlacement(node, Scheduler::kFixed);
385 ConnectTailCall(node);
388 scheduler_->UpdatePlacement(node, Scheduler::kFixed);
389 ConnectReturn(node);
392 scheduler_->UpdatePlacement(node, Scheduler::kFixed);
393 ConnectThrow(node);
400 if (NodeProperties::IsExceptionalCall(node)) {
401 scheduler_->UpdatePlacement(node, Scheduler::kFixed);
402 ConnectCall(node);
410 BasicBlock* BuildBlockForNode(Node* node) {
411 BasicBlock* block = schedule_->block(node);
414 TRACE("Create block id:%d for #%d:%s\n", block->id().ToInt(), node->id(),
415 node->op()->mnemonic());
416 FixNode(block, node);
421 void BuildBlocksForSuccessors(Node* node) {
422 size_t const successor_cnt = node->op()->ControlOutputCount();
424 NodeProperties::CollectControlProjections(node, successors, successor_cnt);
430 void CollectSuccessorBlocks(Node* node, BasicBlock** successor_blocks,
433 NodeProperties::CollectControlProjections(node, successors, successor_cnt);
439 BasicBlock* FindPredecessorBlock(Node* node) {
442 predecessor_block = schedule_->block(node);
444 node = NodeProperties::GetControlInput(node);
602 void TraceConnect(Node* node, BasicBlock* block, BasicBlock* succ) {
605 TRACE("Connect #%d:%s, id:%d -> end\n", node->id(),
606 node->op()->mnemonic(), block->id().ToInt());
608 TRACE("Connect #%d:%s, id:%d -> id:%d\n", node->id(),
609 node->op()->mnemonic(), block->id().ToInt(), succ->id().ToInt());
613 bool IsFinalMerge(Node* node) {
614 return (node->opcode() == IrOpcode::kMerge &&
615 node == scheduler_->graph_->end()->InputAt(0));
633 NodeMarker<bool> queued_; // Mark indicating whether node is queued.
636 Node* component_entry_; // Component single-entry node.
932 // Pop a single node off the stack and add it to the order.
1327 Node* node = stack_.top();
1329 VisitInputs(node);
1334 void InitializePlacement(Node* node) {
1335 TRACE("Pre #%d:%s\n", node->id(), node->op()->mnemonic());
1336 DCHECK(!Visited(node));
1337 if (scheduler_->InitializePlacement(node) == Scheduler::kFixed) {
1339 scheduler_->schedule_root_nodes_.push_back(node);
1340 if (!schedule_->IsScheduled(node)) {
1342 TRACE("Scheduling fixed position node #%d:%s\n", node->id(),
1343 node->op()->mnemonic());
1344 IrOpcode::Value opcode = node->opcode();
1348 : schedule_->block(NodeProperties::GetControlInput(node));
1350 schedule_->AddNode(block, node);
1353 stack_.push(node);
1354 visited_[node->id()] = true;
1357 void VisitInputs(Node* node) {
1358 DCHECK_NE(scheduler_->GetPlacement(node), Scheduler::kUnknown);
1359 bool is_scheduled = schedule_->IsScheduled(node);
1361 scheduler_->GetCoupledControlEdge(node);
1362 for (auto edge : node->input_edges()) {
1364 DCHECK_EQ(node, edge.from());
1368 TRACE("PostEdge #%d:%s->#%d:%s\n", node->id(), node->op()->mnemonic(),
1372 scheduler_->IncrementUnscheduledUseCount(to, node);
1377 bool Visited(Node* node) { return visited_[node->id()]; }
1390 // Count the uses of every node, which is used to ensure that all of a
1391 // node's uses are scheduled before the node itself.
1420 // Visits one node from the queue and propagates its current schedule early
1422 void VisitNode(Node* node) {
1423 Scheduler::SchedulerData* data = scheduler_->GetData(node);
1426 if (scheduler_->GetPlacement(node) == Scheduler::kFixed) {
1427 data->minimum_block_ = schedule_->block(node);
1429 node->id(), node->op()->mnemonic(),
1439 for (auto use : node->uses()) {
1446 // Propagates {block} as another minimum position into the given {node}. This
1447 // has the net effect of computing the minimum dominator block of {node} that
1448 // still post-dominates all inputs to {node} when the queue is processed.
1449 void PropagateMinimumPositionToNode(BasicBlock* block, Node* node) {
1450 Scheduler::SchedulerData* data = scheduler_->GetData(node);
1452 // No need to propagate to fixed node, it's guaranteed to be a root.
1453 if (scheduler_->GetPlacement(node) == Scheduler::kFixed) return;
1456 if (scheduler_->GetPlacement(node) == Scheduler::kCoupled) {
1457 Node* control = NodeProperties::GetControlInput(node);
1463 // the dominator chain of {node}'s minimum block position.
1467 queue_.push(node);
1469 node->id(), node->op()->mnemonic(),
1497 for (Node* node : schedule_root_nodes_) {
1498 TRACE("#%d:%s ", node->id(), node->op()->mnemonic());
1503 // Compute the minimum block for each node thereby determining the earliest
1504 // position each node could be placed within a valid schedule.
1533 for (Node* node : root->inputs()) {
1535 if (scheduler_->GetPlacement(node) == Scheduler::kCoupled) {
1536 node = NodeProperties::GetControlInput(node);
1540 if (scheduler_->GetData(node)->unscheduled_count_ != 0) continue;
1542 queue->push(node);
1552 // Visits one node from the queue of schedulable nodes and determines its
1555 void VisitNode(Node* node) {
1556 DCHECK_EQ(0, scheduler_->GetData(node)->unscheduled_count_);
1559 if (schedule_->IsScheduled(node)) return;
1560 DCHECK_EQ(Scheduler::kSchedulable, scheduler_->GetPlacement(node));
1562 // Determine the dominating block for all of the uses of this node. It is
1563 // the latest block that this node can be scheduled in.
1564 TRACE("Scheduling #%d:%s\n", node->id(), node->op()->mnemonic());
1565 BasicBlock* block = GetCommonDominatorOfUses(node);
1569 BasicBlock* min_block = scheduler_->GetData(node)->minimum_block_;
1574 node->id(), node->op()->mnemonic(), block->id().ToInt(),
1585 TRACE(" hoisting #%d:%s to block id:%d\n", node->id(),
1586 node->op()->mnemonic(), hoist_block->id().ToInt());
1593 // Split the {node} if beneficial and return the new {block} for it.
1594 block = SplitNode(block, node);
1597 // Schedule the node or a floating control structure.
1598 if (IrOpcode::IsMergeOpcode(node->opcode())) {
1599 ScheduleFloatingControl(block, node);
1600 } else if (node->opcode() == IrOpcode::kFinishRegion) {
1601 ScheduleRegion(block, node);
1603 ScheduleNode(block, node);
1624 BasicBlock* SplitNode(BasicBlock* block, Node* node) {
1626 if (!node->op()->HasProperty(Operator::kPure)) return block;
1628 if (node->opcode() == IrOpcode::kProjection) return block;
1630 // The {block} is common dominator of all uses of {node}, so we cannot
1632 DCHECK_EQ(block, GetCommonDominatorOfUses(node));
1640 // Check if the {node} has uses in {block}.
1641 for (Edge edge : node->use_edges()) {
1646 TRACE(" not splitting #%d:%s, it is used in id:%d\n", node->id(),
1647 node->op()->mnemonic(), block->id().ToInt());
1671 // {block} to the end contain at least one use of {node}, and hence there's
1672 // no point in splitting the {node} in this case.
1675 node->id(), node->op()->mnemonic(), block->id().ToInt());
1679 // Split {node} for uses according to the previously computed marking
1681 // copy of the {node} with the exception of the first partition, which get's
1682 // the {node} itself.
1684 for (Edge edge : node->use_edges()) {
1694 // Place the {node} at {use_block}.
1696 use_node = node;
1697 TRACE(" pushing #%d:%s down to id:%d\n", node->id(),
1698 node->op()->mnemonic(), block->id().ToInt());
1700 // Place a copy of {node} at {use_block}.
1701 use_node = CloneNode(node);
1732 BasicBlock* GetCommonDominatorOfUses(Node* node) {
1734 for (Edge edge : node->use_edges()) {
1746 BasicBlock* FindPredecessorBlock(Node* node) {
1747 return scheduler_->control_flow_builder_->FindPredecessorBlock(node);
1790 void ScheduleFloatingControl(BasicBlock* block, Node* node) {
1791 scheduler_->FuseFloatingControl(block, node);
1796 // effect chain. The only value allowed to be produced by a node
1797 // in the chain must be the value consumed by the FinishRegion node.
1804 Node* node = NodeProperties::GetEffectInput(region_end);
1805 while (node->opcode() != IrOpcode::kBeginRegion) {
1806 DCHECK_EQ(0, scheduler_->GetData(node)->unscheduled_count_);
1807 DCHECK_EQ(1, node->op()->EffectInputCount());
1808 DCHECK_EQ(1, node->op()->EffectOutputCount());
1809 DCHECK_EQ(0, node->op()->ControlOutputCount());
1811 // by the EndRegion node.
1812 DCHECK(node->op()->ValueOutputCount() == 0 ||
1813 node == region_end->InputAt(0));
1814 ScheduleNode(block, node);
1815 node = NodeProperties::GetEffectInput(node);
1817 // Schedule the BeginRegion node.
1818 DCHECK_EQ(0, scheduler_->GetData(node)->unscheduled_count_);
1819 ScheduleNode(block, node);
1822 void ScheduleNode(BasicBlock* block, Node* node) {
1823 schedule_->PlanNode(block, node);
1828 scheduler_->scheduled_nodes_[block_id]->push_back(node);
1829 scheduler_->UpdatePlacement(node, Scheduler::kScheduled);
1832 Node* CloneNode(Node* node) {
1833 int const input_count = node->InputCount();
1835 scheduler_->GetCoupledControlEdge(node);
1838 Node* const input = node->InputAt(index);
1839 scheduler_->IncrementUnscheduledUseCount(input, node);
1842 Node* const copy = scheduler_->graph_->CloneNode(node);
1843 TRACE(("clone #%d:%s -> #%d\n"), node->id(), node->op()->mnemonic(),
1847 scheduler_->node_data_[copy->id()] = scheduler_->node_data_[node->id()];
1863 for (Node* node : schedule_root_nodes_) {
1864 TRACE("#%d:%s ", node->id(), node->op()->mnemonic());
1892 for (Node* node : base::Reversed(*nodes)) {
1893 schedule_->AddNode(block, node);
1903 void Scheduler::FuseFloatingControl(BasicBlock* block, Node* node) {
1910 control_flow_builder_->Run(block, node);
1913 special_rpo_->UpdateSpecialRPO(block, schedule_->block(node));
1946 MovePlannedNodes(block, schedule_->block(node));
1961 for (Node* const node : *from_nodes) {
1962 schedule_->SetBlockForNode(to, node);