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"
18 enum VisitState { kUnvisited = 0, kOnStack = 1, kRevisit = 2, kVisited = 3 };
19 enum Decision { kFalse, kUnknown, kTrue };
21 class ReachabilityMarker : public NodeMarker<uint8_t> {
23 explicit ReachabilityMarker(Graph* graph) : NodeMarker<uint8_t>(graph, 8) {}
24 bool SetReachableFromEnd(Node* node) {
25 uint8_t before = Get(node);
26 Set(node, before | kFromEnd);
27 return before & kFromEnd;
29 bool IsReachableFromEnd(Node* node) { return Get(node) & kFromEnd; }
30 bool SetReachableFromStart(Node* node) {
31 uint8_t before = Get(node);
32 Set(node, before | kFromStart);
33 return before & kFromStart;
35 bool IsReachableFromStart(Node* node) { return Get(node) & kFromStart; }
36 void Push(Node* node) { Set(node, Get(node) | kFwStack); }
37 void Pop(Node* node) { Set(node, Get(node) & ~kFwStack); }
38 bool IsOnStack(Node* node) { return Get(node) & kFwStack; }
41 enum Bit { kFromEnd = 1, kFromStart = 2, kFwStack = 4 };
46 if (FLAG_trace_turbo_reduction) PrintF x
48 class ControlReducerImpl {
50 ControlReducerImpl(Zone* zone, JSGraph* jsgraph,
51 CommonOperatorBuilder* common)
55 state_(jsgraph->graph()->NodeCount(), kUnvisited, zone_),
61 CommonOperatorBuilder* common_;
62 ZoneVector<VisitState> state_;
63 ZoneDeque<Node*> stack_;
64 ZoneDeque<Node*> revisit_;
69 // Process the node on the top of the stack, potentially pushing more
70 // or popping the node off the stack.
72 // If the stack becomes empty, revisit any nodes in the revisit queue.
73 // If no nodes in the revisit queue, try removing dead loops.
74 // If no dead loops, then finish.
75 } while (!stack_.empty() || TryRevisit() || RepairAndRemoveLoops());
79 while (!revisit_.empty()) {
80 Node* n = revisit_.back();
82 if (state_[n->id()] == kRevisit) { // state can change while in queue.
90 // Repair the graph after the possible creation of non-terminating or dead
91 // loops. Removing dead loops can produce more opportunities for reduction.
92 bool RepairAndRemoveLoops() {
93 // TODO(turbofan): we can skip this if the graph has no loops, but
94 // we have to be careful about proper loop detection during reduction.
96 // Gather all nodes backwards-reachable from end (through inputs).
97 ReachabilityMarker marked(graph());
98 NodeVector nodes(zone_);
99 AddNodesReachableFromEnd(marked, nodes);
101 // Walk forward through control nodes, looking for back edges to nodes
102 // that are not connected to end. Those are non-terminating loops (NTLs).
103 Node* start = graph()->start();
105 marked.SetReachableFromStart(start);
107 // We use a stack of (Node, Node::Uses::const_iterator) pairs to avoid
109 typedef std::pair<Node*, Node::Uses::const_iterator> FwIter;
110 ZoneVector<FwIter> fw_stack(zone_);
111 fw_stack.push_back(FwIter(start, start->uses().begin()));
113 while (!fw_stack.empty()) {
114 Node* node = fw_stack.back().first;
115 TRACE(("ControlFw: #%d:%s\n", node->id(), node->op()->mnemonic()));
117 while (fw_stack.back().second != node->uses().end()) {
118 Node* succ = *(fw_stack.back().second);
119 if (marked.IsOnStack(succ) && !marked.IsReachableFromEnd(succ)) {
120 // {succ} is on stack and not reachable from end.
121 Node* added = ConnectNTL(succ);
122 nodes.push_back(added);
123 marked.SetReachableFromEnd(added);
124 AddBackwardsReachableNodes(marked, nodes, nodes.size() - 1);
126 // Reset the use iterators for the entire stack.
127 for (size_t i = 0; i < fw_stack.size(); i++) {
128 FwIter& iter = fw_stack[i];
129 fw_stack[i] = FwIter(iter.first, iter.first->uses().begin());
131 pop = false; // restart traversing successors of this node.
134 if (NodeProperties::IsControl(succ) &&
135 !marked.IsReachableFromStart(succ)) {
136 // {succ} is a control node and not yet reached from start.
138 marked.SetReachableFromStart(succ);
139 fw_stack.push_back(FwIter(succ, succ->uses().begin()));
140 pop = false; // "recurse" into successor control node.
143 ++fw_stack.back().second;
151 // Trim references from dead nodes to live nodes first.
152 jsgraph_->GetCachedNodes(&nodes);
153 TrimNodes(marked, nodes);
155 // Any control nodes not reachable from start are dead, even loops.
156 for (size_t i = 0; i < nodes.size(); i++) {
157 Node* node = nodes[i];
158 if (NodeProperties::IsControl(node) &&
159 !marked.IsReachableFromStart(node)) {
160 ReplaceNode(node, dead()); // uses will be added to revisit queue.
163 return TryRevisit(); // try to push a node onto the stack.
166 // Connect {loop}, the header of a non-terminating loop, to the end node.
167 Node* ConnectNTL(Node* loop) {
168 TRACE(("ConnectNTL: #%d:%s\n", loop->id(), loop->op()->mnemonic()));
170 Node* always = graph()->NewNode(common_->Always());
171 // Mark the node as visited so that we can revisit later.
172 MarkAsVisited(always);
174 Node* branch = graph()->NewNode(common_->Branch(), always, loop);
175 // Mark the node as visited so that we can revisit later.
176 MarkAsVisited(branch);
178 Node* if_true = graph()->NewNode(common_->IfTrue(), branch);
179 // Mark the node as visited so that we can revisit later.
180 MarkAsVisited(if_true);
182 Node* if_false = graph()->NewNode(common_->IfFalse(), branch);
183 // Mark the node as visited so that we can revisit later.
184 MarkAsVisited(if_false);
186 // Hook up the branch into the loop and collect all loop effects.
187 NodeVector effects(zone_);
188 for (auto edge : loop->use_edges()) {
189 DCHECK_EQ(loop, edge.to());
190 DCHECK(NodeProperties::IsControlEdge(edge));
191 if (edge.from() == branch) continue;
192 switch (edge.from()->opcode()) {
193 #define CASE(Opcode) case IrOpcode::k##Opcode:
194 CONTROL_OP_LIST(CASE)
196 // Update all control nodes (except {branch}) pointing to the {loop}.
197 edge.UpdateTo(if_true);
199 case IrOpcode::kEffectPhi:
200 effects.push_back(edge.from());
207 // Compute effects for the Return.
208 Node* effect = graph()->start();
209 int const effects_count = static_cast<int>(effects.size());
210 if (effects_count == 1) {
212 } else if (effects_count > 1) {
213 effect = graph()->NewNode(common_->EffectSet(effects_count),
214 effects_count, &effects.front());
215 // Mark the node as visited so that we can revisit later.
216 MarkAsVisited(effect);
219 // Add a return to connect the NTL to the end.
220 Node* ret = graph()->NewNode(
221 common_->Return(), jsgraph_->UndefinedConstant(), effect, if_false);
222 // Mark the node as visited so that we can revisit later.
225 Node* end = graph()->end();
226 CHECK_EQ(IrOpcode::kEnd, end->opcode());
227 Node* merge = end->InputAt(0);
228 if (merge == NULL || merge->opcode() == IrOpcode::kDead) {
229 // The end node died; just connect end to {ret}.
230 end->ReplaceInput(0, ret);
231 } else if (merge->opcode() != IrOpcode::kMerge) {
232 // Introduce a final merge node for {end->InputAt(0)} and {ret}.
233 merge = graph()->NewNode(common_->Merge(2), merge, ret);
234 end->ReplaceInput(0, merge);
236 // Mark the node as visited so that we can revisit later.
237 MarkAsVisited(merge);
239 // Append a new input to the final merge at the end.
240 merge->AppendInput(graph()->zone(), ret);
241 merge->set_op(common_->Merge(merge->InputCount()));
246 void AddNodesReachableFromEnd(ReachabilityMarker& marked, NodeVector& nodes) {
247 Node* end = graph()->end();
248 marked.SetReachableFromEnd(end);
249 if (!end->IsDead()) {
250 nodes.push_back(end);
251 AddBackwardsReachableNodes(marked, nodes, nodes.size() - 1);
255 void AddBackwardsReachableNodes(ReachabilityMarker& marked, NodeVector& nodes,
257 while (cursor < nodes.size()) {
258 Node* node = nodes[cursor++];
259 for (Node* const input : node->inputs()) {
260 if (!marked.SetReachableFromEnd(input)) {
261 nodes.push_back(input);
268 // Gather all nodes backwards-reachable from end through inputs.
269 ReachabilityMarker marked(graph());
270 NodeVector nodes(zone_);
271 AddNodesReachableFromEnd(marked, nodes);
273 // Process cached nodes in the JSGraph too.
274 jsgraph_->GetCachedNodes(&nodes);
275 TrimNodes(marked, nodes);
278 void TrimNodes(ReachabilityMarker& marked, NodeVector& nodes) {
279 // Remove dead->live edges.
280 for (size_t j = 0; j < nodes.size(); j++) {
281 Node* node = nodes[j];
282 for (Edge edge : node->use_edges()) {
283 Node* use = edge.from();
284 if (!marked.IsReachableFromEnd(use)) {
285 TRACE(("DeadLink: #%d:%s(%d) -> #%d:%s\n", use->id(),
286 use->op()->mnemonic(), edge.index(), node->id(),
287 node->op()->mnemonic()));
293 // Verify that no inputs to live nodes are NULL.
294 for (Node* node : nodes) {
295 for (int index = 0; index < node->InputCount(); index++) {
296 Node* input = node->InputAt(index);
297 if (input == nullptr) {
298 std::ostringstream str;
299 str << "GraphError: node #" << node->id() << ":" << *node->op()
300 << "(input @" << index << ") == null";
301 FATAL(str.str().c_str());
303 if (input->opcode() == IrOpcode::kDead) {
304 std::ostringstream str;
305 str << "GraphError: node #" << node->id() << ":" << *node->op()
306 << "(input @" << index << ") == dead";
307 FATAL(str.str().c_str());
310 for (Node* use : node->uses()) {
311 CHECK(marked.IsReachableFromEnd(use));
317 // Reduce the node on the top of the stack.
318 // If an input {i} is not yet visited or needs to be revisited, push {i} onto
319 // the stack and return. Otherwise, all inputs are visited, so apply
320 // reductions for {node} and pop it off the stack.
322 size_t height = stack_.size();
323 Node* node = stack_.back();
325 if (node->IsDead()) return Pop(); // Node was killed while on stack.
327 TRACE(("ControlReduce: #%d:%s\n", node->id(), node->op()->mnemonic()));
329 // Recurse on an input if necessary.
330 for (Node* const input : node->inputs()) {
332 if (Recurse(input)) return;
335 // All inputs should be visited or on stack. Apply reductions to node.
336 Node* replacement = ReduceNode(node);
337 if (replacement != node) ReplaceNode(node, replacement);
339 // After reducing the node, pop it off the stack.
340 CHECK_EQ(static_cast<int>(height), static_cast<int>(stack_.size()));
343 // If there was a replacement, reduce it after popping {node}.
344 if (replacement != node) Recurse(replacement);
347 void EnsureStateSize(size_t id) {
348 if (id >= state_.size()) {
349 state_.resize((3 * id) / 2, kUnvisited);
353 // Push a node onto the stack if its state is {kUnvisited} or {kRevisit}.
354 bool Recurse(Node* node) {
355 size_t id = static_cast<size_t>(node->id());
357 if (state_[id] != kRevisit && state_[id] != kUnvisited) return false;
362 void Push(Node* node) {
363 state_[node->id()] = kOnStack;
364 stack_.push_back(node);
368 int pos = static_cast<int>(stack_.size()) - 1;
370 DCHECK_EQ(kOnStack, state_[stack_[pos]->id()]);
371 state_[stack_[pos]->id()] = kVisited;
375 // Queue a node to be revisited if it has been visited once already.
376 void Revisit(Node* node) {
377 size_t id = static_cast<size_t>(node->id());
378 if (id < state_.size() && state_[id] == kVisited) {
379 TRACE((" Revisit #%d:%s\n", node->id(), node->op()->mnemonic()));
380 state_[id] = kRevisit;
381 revisit_.push_back(node);
385 // Mark {node} as visited.
386 void MarkAsVisited(Node* node) {
387 size_t id = static_cast<size_t>(node->id());
389 state_[id] = kVisited;
392 Node* dead() { return jsgraph_->DeadControl(); }
394 //===========================================================================
395 // Reducer implementation: perform reductions on a node.
396 //===========================================================================
397 Node* ReduceNode(Node* node) {
398 if (node->op()->ControlInputCount() == 1 ||
399 node->opcode() == IrOpcode::kLoop) {
400 // If a node has only one control input and it is dead, replace with dead.
401 Node* control = NodeProperties::GetControlInput(node);
402 if (control->opcode() == IrOpcode::kDead) {
403 TRACE(("ControlDead: #%d:%s\n", node->id(), node->op()->mnemonic()));
408 // Reduce branches, phis, and merges.
409 switch (node->opcode()) {
410 case IrOpcode::kBranch:
411 return ReduceBranch(node);
412 case IrOpcode::kIfTrue:
413 return ReduceIfTrue(node);
414 case IrOpcode::kIfFalse:
415 return ReduceIfFalse(node);
416 case IrOpcode::kLoop:
417 case IrOpcode::kMerge:
418 return ReduceMerge(node);
419 case IrOpcode::kSelect:
420 return ReduceSelect(node);
422 case IrOpcode::kEffectPhi:
423 return ReducePhi(node);
429 // Try to statically fold a condition.
430 Decision DecideCondition(Node* cond) {
431 switch (cond->opcode()) {
432 case IrOpcode::kInt32Constant:
433 return Int32Matcher(cond).Is(0) ? kFalse : kTrue;
434 case IrOpcode::kInt64Constant:
435 return Int64Matcher(cond).Is(0) ? kFalse : kTrue;
436 case IrOpcode::kNumberConstant:
437 return NumberMatcher(cond).Is(0) ? kFalse : kTrue;
438 case IrOpcode::kHeapConstant: {
439 Handle<Object> object =
440 HeapObjectMatcher<Object>(cond).Value().handle();
441 if (object->IsTrue()) return kTrue;
442 if (object->IsFalse()) return kFalse;
443 // TODO(turbofan): decide more conditions for heap constants.
452 // Reduce redundant selects.
453 Node* ReduceSelect(Node* const node) {
454 Node* const tvalue = node->InputAt(1);
455 Node* const fvalue = node->InputAt(2);
456 if (tvalue == fvalue) return tvalue;
457 Decision result = DecideCondition(node->InputAt(0));
458 if (result == kTrue) return tvalue;
459 if (result == kFalse) return fvalue;
463 // Reduce redundant phis.
464 Node* ReducePhi(Node* node) {
465 int n = node->InputCount();
466 if (n <= 1) return dead(); // No non-control inputs.
467 if (n == 2) return node->InputAt(0); // Only one non-control input.
469 // Never remove an effect phi from a (potentially non-terminating) loop.
470 // Otherwise, we might end up eliminating effect nodes, such as calls,
472 if (node->opcode() == IrOpcode::kEffectPhi &&
473 NodeProperties::GetControlInput(node)->opcode() == IrOpcode::kLoop) {
477 Node* replacement = NULL;
478 auto const inputs = node->inputs();
479 for (auto it = inputs.begin(); n > 1; --n, ++it) {
481 if (input->opcode() == IrOpcode::kDead) continue; // ignore dead inputs.
482 if (input != node && input != replacement) { // non-redundant input.
483 if (replacement != NULL) return node;
487 return replacement == NULL ? dead() : replacement;
491 Node* ReduceBranch(Node* branch) {
492 if (DecideCondition(branch->InputAt(0)) != kUnknown) {
493 for (Node* use : branch->uses()) Revisit(use);
498 // Reduce merges by trimming away dead inputs from the merge and phis.
499 Node* ReduceMerge(Node* node) {
500 // Count the number of live inputs.
504 for (Node* const input : node->inputs()) {
505 if (input->opcode() != IrOpcode::kDead) {
512 if (live > 1 && live == node->InputCount()) return node; // nothing to do.
514 TRACE(("ReduceMerge: #%d:%s (%d live)\n", node->id(),
515 node->op()->mnemonic(), live));
517 if (live == 0) return dead(); // no remaining inputs.
519 // Gather phis and effect phis to be edited.
520 ZoneVector<Node*> phis(zone_);
521 for (Node* const use : node->uses()) {
522 if (NodeProperties::IsPhi(use)) phis.push_back(use);
526 // All phis are redundant. Replace them with their live input.
527 for (Node* const phi : phis) ReplaceNode(phi, phi->InputAt(live_index));
528 // The merge itself is redundant.
529 return node->InputAt(live_index);
532 // Edit phis in place, removing dead inputs and revisiting them.
533 for (Node* const phi : phis) {
534 TRACE((" PhiInMerge: #%d:%s (%d live)\n", phi->id(),
535 phi->op()->mnemonic(), live));
536 RemoveDeadInputs(node, phi);
539 // Edit the merge in place, removing dead inputs.
540 RemoveDeadInputs(node, node);
544 // Reduce branches if they have constant inputs.
545 Node* ReduceIfTrue(Node* node) {
546 Node* branch = node->InputAt(0);
547 DCHECK_EQ(IrOpcode::kBranch, branch->opcode());
548 Decision result = DecideCondition(branch->InputAt(0));
549 if (result == kTrue) {
550 // fold a true branch by replacing IfTrue with the branch control.
551 TRACE(("BranchReduce: #%d:%s => #%d:%s\n", branch->id(),
552 branch->op()->mnemonic(), node->id(), node->op()->mnemonic()));
553 return branch->InputAt(1);
555 return result == kUnknown ? node : dead();
558 // Reduce branches if they have constant inputs.
559 Node* ReduceIfFalse(Node* node) {
560 Node* branch = node->InputAt(0);
561 DCHECK_EQ(IrOpcode::kBranch, branch->opcode());
562 Decision result = DecideCondition(branch->InputAt(0));
563 if (result == kFalse) {
564 // fold a false branch by replacing IfFalse with the branch control.
565 TRACE(("BranchReduce: #%d:%s => #%d:%s\n", branch->id(),
566 branch->op()->mnemonic(), node->id(), node->op()->mnemonic()));
567 return branch->InputAt(1);
569 return result == kUnknown ? node : dead();
572 // Remove inputs to {node} corresponding to the dead inputs to {merge}
573 // and compact the remaining inputs, updating the operator.
574 void RemoveDeadInputs(Node* merge, Node* node) {
576 for (int i = 0; i < merge->InputCount(); i++) {
578 if (merge->InputAt(i)->opcode() == IrOpcode::kDead) continue;
579 // compact live inputs.
580 if (live != i) node->ReplaceInput(live, node->InputAt(i));
583 // compact remaining inputs.
585 for (int i = merge->InputCount(); i < node->InputCount(); i++) {
586 if (total != i) node->ReplaceInput(total, node->InputAt(i));
589 DCHECK_EQ(total, live + node->InputCount() - merge->InputCount());
590 DCHECK_NE(total, node->InputCount());
591 node->TrimInputCount(total);
592 node->set_op(common_->ResizeMergeOrPhi(node->op(), live));
595 // Replace uses of {node} with {replacement} and revisit the uses.
596 void ReplaceNode(Node* node, Node* replacement) {
597 if (node == replacement) return;
598 TRACE((" Replace: #%d:%s with #%d:%s\n", node->id(),
599 node->op()->mnemonic(), replacement->id(),
600 replacement->op()->mnemonic()));
601 for (Node* const use : node->uses()) {
602 // Don't revisit this node if it refers to itself.
603 if (use != node) Revisit(use);
605 node->ReplaceUses(replacement);
609 Graph* graph() { return jsgraph_->graph(); }
613 void ControlReducer::ReduceGraph(Zone* zone, JSGraph* jsgraph,
614 CommonOperatorBuilder* common) {
615 ControlReducerImpl impl(zone, jsgraph, common);
620 void ControlReducer::TrimGraph(Zone* zone, JSGraph* jsgraph) {
621 ControlReducerImpl impl(zone, jsgraph, NULL);
626 Node* ControlReducer::ReduceMerge(JSGraph* jsgraph,
627 CommonOperatorBuilder* common, Node* node) {
629 ControlReducerImpl impl(&zone, jsgraph, common);
630 return impl.ReduceMerge(node);
634 Node* ControlReducer::ReducePhiForTesting(JSGraph* jsgraph,
635 CommonOperatorBuilder* common,
638 ControlReducerImpl impl(&zone, jsgraph, common);
639 return impl.ReducePhi(node);
643 Node* ControlReducer::ReduceIfNodeForTesting(JSGraph* jsgraph,
644 CommonOperatorBuilder* common,
647 ControlReducerImpl impl(&zone, jsgraph, common);
648 switch (node->opcode()) {
649 case IrOpcode::kIfTrue:
650 return impl.ReduceIfTrue(node);
651 case IrOpcode::kIfFalse:
652 return impl.ReduceIfFalse(node);
659 } // namespace v8::internal::compiler