1 // Copyright 2014 the V8 project authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
5 #include "src/compiler/common-operator.h"
6 #include "src/compiler/control-reducer.h"
7 #include "src/compiler/graph.h"
8 #include "src/compiler/js-graph.h"
9 #include "src/compiler/node-marker.h"
10 #include "src/compiler/node-matchers.h"
11 #include "src/compiler/node-properties.h"
12 #include "src/zone-containers.h"
20 if (FLAG_trace_turbo_reduction) PrintF(__VA_ARGS__); \
23 enum VisitState { kUnvisited = 0, kOnStack = 1, kRevisit = 2, kVisited = 3 };
24 enum Decision { kFalse, kUnknown, kTrue };
26 class ReachabilityMarker : public NodeMarker<uint8_t> {
28 explicit ReachabilityMarker(Graph* graph) : NodeMarker<uint8_t>(graph, 8) {}
29 bool SetReachableFromEnd(Node* node) {
30 uint8_t before = Get(node);
31 Set(node, before | kFromEnd);
32 return before & kFromEnd;
34 bool IsReachableFromEnd(Node* node) { return Get(node) & kFromEnd; }
35 bool SetReachableFromStart(Node* node) {
36 uint8_t before = Get(node);
37 Set(node, before | kFromStart);
38 return before & kFromStart;
40 bool IsReachableFromStart(Node* node) { return Get(node) & kFromStart; }
41 void Push(Node* node) { Set(node, Get(node) | kFwStack); }
42 void Pop(Node* node) { Set(node, Get(node) & ~kFwStack); }
43 bool IsOnStack(Node* node) { return Get(node) & kFwStack; }
46 enum Bit { kFromEnd = 1, kFromStart = 2, kFwStack = 4 };
50 class ControlReducerImpl {
52 ControlReducerImpl(Zone* zone, JSGraph* jsgraph,
53 CommonOperatorBuilder* common)
57 state_(jsgraph->graph()->NodeCount(), kUnvisited, zone_),
63 CommonOperatorBuilder* common_;
64 ZoneVector<VisitState> state_;
65 ZoneDeque<Node*> stack_;
66 ZoneDeque<Node*> revisit_;
71 // Process the node on the top of the stack, potentially pushing more
72 // or popping the node off the stack.
74 // If the stack becomes empty, revisit any nodes in the revisit queue.
75 // If no nodes in the revisit queue, try removing dead loops.
76 // If no dead loops, then finish.
77 } while (!stack_.empty() || TryRevisit() || RepairAndRemoveLoops());
81 while (!revisit_.empty()) {
82 Node* n = revisit_.back();
84 if (state_[n->id()] == kRevisit) { // state can change while in queue.
92 // Repair the graph after the possible creation of non-terminating or dead
93 // loops. Removing dead loops can produce more opportunities for reduction.
94 bool RepairAndRemoveLoops() {
95 // TODO(turbofan): we can skip this if the graph has no loops, but
96 // we have to be careful about proper loop detection during reduction.
98 // Gather all nodes backwards-reachable from end (through inputs).
99 ReachabilityMarker marked(graph());
100 NodeVector nodes(zone_);
101 AddNodesReachableFromEnd(marked, nodes);
103 // Walk forward through control nodes, looking for back edges to nodes
104 // that are not connected to end. Those are non-terminating loops (NTLs).
105 Node* start = graph()->start();
107 marked.SetReachableFromStart(start);
109 // We use a stack of (Node, Node::UseEdges::iterator) pairs to avoid
111 typedef std::pair<Node*, Node::UseEdges::iterator> FwIter;
112 ZoneVector<FwIter> fw_stack(zone_);
113 fw_stack.push_back(FwIter(start, start->use_edges().begin()));
115 while (!fw_stack.empty()) {
116 Node* node = fw_stack.back().first;
117 TRACE("ControlFw: #%d:%s\n", node->id(), node->op()->mnemonic());
119 while (fw_stack.back().second != node->use_edges().end()) {
120 Edge edge = *(fw_stack.back().second);
121 if (NodeProperties::IsControlEdge(edge) &&
122 edge.from()->op()->ControlOutputCount() > 0) {
123 // Only walk control edges to control nodes.
124 Node* succ = edge.from();
126 if (marked.IsOnStack(succ) && !marked.IsReachableFromEnd(succ)) {
127 // {succ} is on stack and not reachable from end.
128 Node* added = ConnectNTL(succ);
129 nodes.push_back(added);
130 marked.SetReachableFromEnd(added);
131 AddBackwardsReachableNodes(marked, nodes, nodes.size() - 1);
133 // Reset the use iterators for the entire stack.
134 for (size_t i = 0; i < fw_stack.size(); i++) {
135 FwIter& iter = fw_stack[i];
136 fw_stack[i] = FwIter(iter.first, iter.first->use_edges().begin());
138 pop = false; // restart traversing successors of this node.
141 if (!marked.IsReachableFromStart(succ)) {
142 // {succ} is not yet reached from start.
144 marked.SetReachableFromStart(succ);
145 fw_stack.push_back(FwIter(succ, succ->use_edges().begin()));
146 pop = false; // "recurse" into successor control node.
150 ++fw_stack.back().second;
158 // Trim references from dead nodes to live nodes first.
159 jsgraph_->GetCachedNodes(&nodes);
160 TrimNodes(marked, nodes);
162 // Any control nodes not reachable from start are dead, even loops.
163 for (size_t i = 0; i < nodes.size(); i++) {
164 Node* node = nodes[i];
165 if (node->op()->ControlOutputCount() > 0 &&
166 !marked.IsReachableFromStart(node)) {
167 ReplaceNode(node, dead()); // uses will be added to revisit queue.
170 return TryRevisit(); // try to push a node onto the stack.
173 // Connect {loop}, the header of a non-terminating loop, to the end node.
174 Node* ConnectNTL(Node* loop) {
175 TRACE("ConnectNTL: #%d:%s\n", loop->id(), loop->op()->mnemonic());
176 DCHECK_EQ(IrOpcode::kLoop, loop->opcode());
178 Node* always = graph()->NewNode(common_->Always());
179 // Mark the node as visited so that we can revisit later.
180 MarkAsVisited(always);
182 Node* branch = graph()->NewNode(common_->Branch(), always, loop);
183 // Mark the node as visited so that we can revisit later.
184 MarkAsVisited(branch);
186 Node* if_true = graph()->NewNode(common_->IfTrue(), branch);
187 // Mark the node as visited so that we can revisit later.
188 MarkAsVisited(if_true);
190 Node* if_false = graph()->NewNode(common_->IfFalse(), branch);
191 // Mark the node as visited so that we can revisit later.
192 MarkAsVisited(if_false);
194 // Hook up the branch into the loop and collect all loop effects.
195 NodeVector effects(zone_);
196 for (auto edge : loop->use_edges()) {
197 DCHECK_EQ(loop, edge.to());
198 DCHECK(NodeProperties::IsControlEdge(edge));
199 if (edge.from() == branch) continue;
200 switch (edge.from()->opcode()) {
203 case IrOpcode::kEffectPhi:
204 effects.push_back(edge.from());
207 // Update all control edges (except {branch}) pointing to the {loop}.
208 edge.UpdateTo(if_true);
213 // Compute effects for the Return.
214 Node* effect = graph()->start();
215 int const effects_count = static_cast<int>(effects.size());
216 if (effects_count == 1) {
218 } else if (effects_count > 1) {
219 effect = graph()->NewNode(common_->EffectSet(effects_count),
220 effects_count, &effects.front());
221 // Mark the node as visited so that we can revisit later.
222 MarkAsVisited(effect);
225 // Add a return to connect the NTL to the end.
226 Node* ret = graph()->NewNode(
227 common_->Return(), jsgraph_->UndefinedConstant(), effect, if_false);
228 // Mark the node as visited so that we can revisit later.
231 Node* end = graph()->end();
232 CHECK_EQ(IrOpcode::kEnd, end->opcode());
233 Node* merge = end->InputAt(0);
234 if (merge == NULL || merge->opcode() == IrOpcode::kDead) {
235 // The end node died; just connect end to {ret}.
236 end->ReplaceInput(0, ret);
237 } else if (merge->opcode() != IrOpcode::kMerge) {
238 // Introduce a final merge node for {end->InputAt(0)} and {ret}.
239 merge = graph()->NewNode(common_->Merge(2), merge, ret);
240 end->ReplaceInput(0, merge);
242 // Mark the node as visited so that we can revisit later.
243 MarkAsVisited(merge);
245 // Append a new input to the final merge at the end.
246 merge->AppendInput(graph()->zone(), ret);
247 merge->set_op(common_->Merge(merge->InputCount()));
252 void AddNodesReachableFromEnd(ReachabilityMarker& marked, NodeVector& nodes) {
253 Node* end = graph()->end();
254 marked.SetReachableFromEnd(end);
255 if (!end->IsDead()) {
256 nodes.push_back(end);
257 AddBackwardsReachableNodes(marked, nodes, nodes.size() - 1);
261 void AddBackwardsReachableNodes(ReachabilityMarker& marked, NodeVector& nodes,
263 while (cursor < nodes.size()) {
264 Node* node = nodes[cursor++];
265 for (Node* const input : node->inputs()) {
266 if (!marked.SetReachableFromEnd(input)) {
267 nodes.push_back(input);
274 // Gather all nodes backwards-reachable from end through inputs.
275 ReachabilityMarker marked(graph());
276 NodeVector nodes(zone_);
277 AddNodesReachableFromEnd(marked, nodes);
279 // Process cached nodes in the JSGraph too.
280 jsgraph_->GetCachedNodes(&nodes);
281 TrimNodes(marked, nodes);
284 void TrimNodes(ReachabilityMarker& marked, NodeVector& nodes) {
285 // Remove dead->live edges.
286 for (size_t j = 0; j < nodes.size(); j++) {
287 Node* node = nodes[j];
288 for (Edge edge : node->use_edges()) {
289 Node* use = edge.from();
290 if (!marked.IsReachableFromEnd(use)) {
291 TRACE("DeadLink: #%d:%s(%d) -> #%d:%s\n", use->id(),
292 use->op()->mnemonic(), edge.index(), node->id(),
293 node->op()->mnemonic());
299 // Verify that no inputs to live nodes are NULL.
300 for (Node* node : nodes) {
301 for (int index = 0; index < node->InputCount(); index++) {
302 Node* input = node->InputAt(index);
303 if (input == nullptr) {
304 std::ostringstream str;
305 str << "GraphError: node #" << node->id() << ":" << *node->op()
306 << "(input @" << index << ") == null";
307 FATAL(str.str().c_str());
309 if (input->opcode() == IrOpcode::kDead) {
310 std::ostringstream str;
311 str << "GraphError: node #" << node->id() << ":" << *node->op()
312 << "(input @" << index << ") == dead";
313 FATAL(str.str().c_str());
316 for (Node* use : node->uses()) {
317 CHECK(marked.IsReachableFromEnd(use));
323 // Reduce the node on the top of the stack.
324 // If an input {i} is not yet visited or needs to be revisited, push {i} onto
325 // the stack and return. Otherwise, all inputs are visited, so apply
326 // reductions for {node} and pop it off the stack.
328 size_t height = stack_.size();
329 Node* node = stack_.back();
331 if (node->IsDead()) return Pop(); // Node was killed while on stack.
333 TRACE("ControlReduce: #%d:%s\n", node->id(), node->op()->mnemonic());
335 // Recurse on an input if necessary.
336 for (Node* const input : node->inputs()) {
338 if (Recurse(input)) return;
341 // All inputs should be visited or on stack. Apply reductions to node.
342 Node* replacement = ReduceNode(node);
343 if (replacement != node) ReplaceNode(node, replacement);
345 // After reducing the node, pop it off the stack.
346 CHECK_EQ(static_cast<int>(height), static_cast<int>(stack_.size()));
349 // If there was a replacement, reduce it after popping {node}.
350 if (replacement != node) Recurse(replacement);
353 void EnsureStateSize(size_t id) {
354 if (id >= state_.size()) {
355 state_.resize((3 * id) / 2, kUnvisited);
359 // Push a node onto the stack if its state is {kUnvisited} or {kRevisit}.
360 bool Recurse(Node* node) {
361 size_t id = static_cast<size_t>(node->id());
363 if (state_[id] != kRevisit && state_[id] != kUnvisited) return false;
368 void Push(Node* node) {
369 state_[node->id()] = kOnStack;
370 stack_.push_back(node);
374 int pos = static_cast<int>(stack_.size()) - 1;
376 DCHECK_EQ(kOnStack, state_[stack_[pos]->id()]);
377 state_[stack_[pos]->id()] = kVisited;
381 // Queue a node to be revisited if it has been visited once already.
382 void Revisit(Node* node) {
383 size_t id = static_cast<size_t>(node->id());
384 if (id < state_.size() && state_[id] == kVisited) {
385 TRACE(" Revisit #%d:%s\n", node->id(), node->op()->mnemonic());
386 state_[id] = kRevisit;
387 revisit_.push_back(node);
391 // Mark {node} as visited.
392 void MarkAsVisited(Node* node) {
393 size_t id = static_cast<size_t>(node->id());
395 state_[id] = kVisited;
398 Node* dead() { return jsgraph_->DeadControl(); }
400 //===========================================================================
401 // Reducer implementation: perform reductions on a node.
402 //===========================================================================
403 Node* ReduceNode(Node* node) {
404 if (node->op()->ControlInputCount() == 1 ||
405 node->opcode() == IrOpcode::kLoop) {
406 // If a node has only one control input and it is dead, replace with dead.
407 Node* control = NodeProperties::GetControlInput(node);
408 if (control->opcode() == IrOpcode::kDead) {
409 TRACE("ControlDead: #%d:%s\n", node->id(), node->op()->mnemonic());
414 // Reduce branches, phis, and merges.
415 switch (node->opcode()) {
416 case IrOpcode::kBranch:
417 return ReduceBranch(node);
418 case IrOpcode::kIfTrue:
419 return ReduceIfTrue(node);
420 case IrOpcode::kIfFalse:
421 return ReduceIfFalse(node);
422 case IrOpcode::kLoop:
423 case IrOpcode::kMerge:
424 return ReduceMerge(node);
425 case IrOpcode::kSelect:
426 return ReduceSelect(node);
428 case IrOpcode::kEffectPhi:
429 return ReducePhi(node);
435 // Try to statically fold a condition.
436 Decision DecideCondition(Node* cond) {
437 switch (cond->opcode()) {
438 case IrOpcode::kInt32Constant:
439 return Int32Matcher(cond).Is(0) ? kFalse : kTrue;
440 case IrOpcode::kInt64Constant:
441 return Int64Matcher(cond).Is(0) ? kFalse : kTrue;
442 case IrOpcode::kNumberConstant:
443 return NumberMatcher(cond).Is(0) ? kFalse : kTrue;
444 case IrOpcode::kHeapConstant: {
445 Handle<Object> object =
446 HeapObjectMatcher<Object>(cond).Value().handle();
447 if (object->IsTrue()) return kTrue;
448 if (object->IsFalse()) return kFalse;
449 // TODO(turbofan): decide more conditions for heap constants.
458 // Reduce redundant selects.
459 Node* ReduceSelect(Node* const node) {
460 Node* const tvalue = node->InputAt(1);
461 Node* const fvalue = node->InputAt(2);
462 if (tvalue == fvalue) return tvalue;
463 Decision result = DecideCondition(node->InputAt(0));
464 if (result == kTrue) return tvalue;
465 if (result == kFalse) return fvalue;
469 // Reduce redundant phis.
470 Node* ReducePhi(Node* node) {
471 int n = node->InputCount();
472 if (n <= 1) return dead(); // No non-control inputs.
473 if (n == 2) return node->InputAt(0); // Only one non-control input.
475 // Never remove an effect phi from a (potentially non-terminating) loop.
476 // Otherwise, we might end up eliminating effect nodes, such as calls,
478 if (node->opcode() == IrOpcode::kEffectPhi &&
479 NodeProperties::GetControlInput(node)->opcode() == IrOpcode::kLoop) {
483 Node* replacement = NULL;
484 auto const inputs = node->inputs();
485 for (auto it = inputs.begin(); n > 1; --n, ++it) {
487 if (input->opcode() == IrOpcode::kDead) continue; // ignore dead inputs.
488 if (input != node && input != replacement) { // non-redundant input.
489 if (replacement != NULL) return node;
493 return replacement == NULL ? dead() : replacement;
497 Node* ReduceBranch(Node* branch) {
498 if (DecideCondition(branch->InputAt(0)) != kUnknown) {
499 for (Node* use : branch->uses()) Revisit(use);
504 // Reduce merges by trimming away dead inputs from the merge and phis.
505 Node* ReduceMerge(Node* node) {
506 // Count the number of live inputs.
510 for (Node* const input : node->inputs()) {
511 if (input->opcode() != IrOpcode::kDead) {
518 TRACE("ReduceMerge: #%d:%s (%d of %d live)\n", node->id(),
519 node->op()->mnemonic(), live, index);
521 if (live == 0) return dead(); // no remaining inputs.
523 // Gather phis and effect phis to be edited.
524 ZoneVector<Node*> phis(zone_);
525 for (Node* const use : node->uses()) {
526 if (NodeProperties::IsPhi(use)) phis.push_back(use);
530 // All phis are redundant. Replace them with their live input.
531 for (Node* const phi : phis) ReplaceNode(phi, phi->InputAt(live_index));
532 // The merge itself is redundant.
533 return node->InputAt(live_index);
538 if (live < node->InputCount()) {
539 // Edit phis in place, removing dead inputs and revisiting them.
540 for (Node* const phi : phis) {
541 TRACE(" PhiInMerge: #%d:%s (%d live)\n", phi->id(),
542 phi->op()->mnemonic(), live);
543 RemoveDeadInputs(node, phi);
546 // Edit the merge in place, removing dead inputs.
547 RemoveDeadInputs(node, node);
550 DCHECK_EQ(live, node->InputCount());
552 // Check if it's an unused diamond.
553 if (live == 2 && phis.empty()) {
554 Node* node0 = node->InputAt(0);
555 Node* node1 = node->InputAt(1);
556 if (((node0->opcode() == IrOpcode::kIfTrue &&
557 node1->opcode() == IrOpcode::kIfFalse) ||
558 (node1->opcode() == IrOpcode::kIfTrue &&
559 node0->opcode() == IrOpcode::kIfFalse)) &&
560 node0->OwnedBy(node) && node1->OwnedBy(node)) {
561 Node* branch0 = NodeProperties::GetControlInput(node0);
562 Node* branch1 = NodeProperties::GetControlInput(node1);
563 if (branch0 == branch1) {
564 // It's a dead diamond, i.e. neither the IfTrue nor the IfFalse nodes
565 // have users except for the Merge and the Merge has no Phi or
566 // EffectPhi uses, so replace the Merge with the control input of the
568 TRACE(" DeadDiamond: #%d:%s #%d:%s #%d:%s\n", node0->id(),
569 node0->op()->mnemonic(), node1->id(), node1->op()->mnemonic(),
570 branch0->id(), branch0->op()->mnemonic());
571 return NodeProperties::GetControlInput(branch0);
579 // Reduce branches if they have constant inputs.
580 Node* ReduceIfTrue(Node* node) {
581 Node* branch = node->InputAt(0);
582 DCHECK_EQ(IrOpcode::kBranch, branch->opcode());
583 Decision result = DecideCondition(branch->InputAt(0));
584 if (result == kTrue) {
585 // fold a true branch by replacing IfTrue with the branch control.
586 TRACE(" BranchReduce: #%d:%s => #%d:%s\n", branch->id(),
587 branch->op()->mnemonic(), node->id(), node->op()->mnemonic());
588 return branch->InputAt(1);
590 return result == kUnknown ? node : dead();
593 // Reduce branches if they have constant inputs.
594 Node* ReduceIfFalse(Node* node) {
595 Node* branch = node->InputAt(0);
596 DCHECK_EQ(IrOpcode::kBranch, branch->opcode());
597 Decision result = DecideCondition(branch->InputAt(0));
598 if (result == kFalse) {
599 // fold a false branch by replacing IfFalse with the branch control.
600 TRACE(" BranchReduce: #%d:%s => #%d:%s\n", branch->id(),
601 branch->op()->mnemonic(), node->id(), node->op()->mnemonic());
602 return branch->InputAt(1);
604 return result == kUnknown ? node : dead();
607 // Remove inputs to {node} corresponding to the dead inputs to {merge}
608 // and compact the remaining inputs, updating the operator.
609 void RemoveDeadInputs(Node* merge, Node* node) {
611 for (int i = 0; i < merge->InputCount(); i++) {
613 if (merge->InputAt(i)->opcode() == IrOpcode::kDead) continue;
614 // compact live inputs.
615 if (live != i) node->ReplaceInput(live, node->InputAt(i));
618 // compact remaining inputs.
620 for (int i = merge->InputCount(); i < node->InputCount(); i++) {
621 if (total != i) node->ReplaceInput(total, node->InputAt(i));
624 DCHECK_EQ(total, live + node->InputCount() - merge->InputCount());
625 DCHECK_NE(total, node->InputCount());
626 node->TrimInputCount(total);
627 node->set_op(common_->ResizeMergeOrPhi(node->op(), live));
630 // Replace uses of {node} with {replacement} and revisit the uses.
631 void ReplaceNode(Node* node, Node* replacement) {
632 if (node == replacement) return;
633 TRACE(" Replace: #%d:%s with #%d:%s\n", node->id(), node->op()->mnemonic(),
634 replacement->id(), replacement->op()->mnemonic());
635 for (Node* const use : node->uses()) {
636 // Don't revisit this node if it refers to itself.
637 if (use != node) Revisit(use);
639 node->ReplaceUses(replacement);
643 Graph* graph() { return jsgraph_->graph(); }
647 void ControlReducer::ReduceGraph(Zone* zone, JSGraph* jsgraph,
648 CommonOperatorBuilder* common) {
649 ControlReducerImpl impl(zone, jsgraph, common);
654 void ControlReducer::TrimGraph(Zone* zone, JSGraph* jsgraph) {
655 ControlReducerImpl impl(zone, jsgraph, NULL);
660 Node* ControlReducer::ReduceMerge(JSGraph* jsgraph,
661 CommonOperatorBuilder* common, Node* node) {
663 ControlReducerImpl impl(&zone, jsgraph, common);
664 return impl.ReduceMerge(node);
668 Node* ControlReducer::ReducePhiForTesting(JSGraph* jsgraph,
669 CommonOperatorBuilder* common,
672 ControlReducerImpl impl(&zone, jsgraph, common);
673 return impl.ReducePhi(node);
677 Node* ControlReducer::ReduceIfNodeForTesting(JSGraph* jsgraph,
678 CommonOperatorBuilder* common,
681 ControlReducerImpl impl(&zone, jsgraph, common);
682 switch (node->opcode()) {
683 case IrOpcode::kIfTrue:
684 return impl.ReduceIfTrue(node);
685 case IrOpcode::kIfFalse:
686 return impl.ReduceIfFalse(node);
693 } // namespace v8::internal::compiler