| // Copyright 2014 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/common-operator.h" |
| #include "src/compiler/control-reducer.h" |
| #include "src/compiler/graph.h" |
| #include "src/compiler/js-graph.h" |
| #include "src/compiler/node-matchers.h" |
| #include "src/compiler/node-properties-inl.h" |
| #include "src/zone-containers.h" |
| |
| namespace v8 { |
| namespace internal { |
| namespace compiler { |
| |
| enum VisitState { kUnvisited = 0, kOnStack = 1, kRevisit = 2, kVisited = 3 }; |
| enum Decision { kFalse, kUnknown, kTrue }; |
| |
| class ReachabilityMarker : public NodeMarker<uint8_t> { |
| public: |
| explicit ReachabilityMarker(Graph* graph) : NodeMarker<uint8_t>(graph, 8) {} |
| bool SetReachableFromEnd(Node* node) { |
| uint8_t before = Get(node); |
| Set(node, before | kFromEnd); |
| return before & kFromEnd; |
| } |
| bool IsReachableFromEnd(Node* node) { return Get(node) & kFromEnd; } |
| bool SetReachableFromStart(Node* node) { |
| uint8_t before = Get(node); |
| Set(node, before | kFromStart); |
| return before & kFromStart; |
| } |
| bool IsReachableFromStart(Node* node) { return Get(node) & kFromStart; } |
| void Push(Node* node) { Set(node, Get(node) | kFwStack); } |
| void Pop(Node* node) { Set(node, Get(node) & ~kFwStack); } |
| bool IsOnStack(Node* node) { return Get(node) & kFwStack; } |
| |
| private: |
| enum Bit { kFromEnd = 1, kFromStart = 2, kFwStack = 4 }; |
| }; |
| |
| |
| #define TRACE(x) \ |
| if (FLAG_trace_turbo_reduction) PrintF x |
| |
| class ControlReducerImpl { |
| public: |
| ControlReducerImpl(Zone* zone, JSGraph* jsgraph, |
| CommonOperatorBuilder* common) |
| : zone_(zone), |
| jsgraph_(jsgraph), |
| common_(common), |
| state_(jsgraph->graph()->NodeCount(), kUnvisited, zone_), |
| stack_(zone_), |
| revisit_(zone_), |
| dead_(NULL) {} |
| |
| Zone* zone_; |
| JSGraph* jsgraph_; |
| CommonOperatorBuilder* common_; |
| ZoneVector<VisitState> state_; |
| ZoneDeque<Node*> stack_; |
| ZoneDeque<Node*> revisit_; |
| Node* dead_; |
| |
| void Reduce() { |
| Push(graph()->end()); |
| do { |
| // Process the node on the top of the stack, potentially pushing more |
| // or popping the node off the stack. |
| ReduceTop(); |
| // If the stack becomes empty, revisit any nodes in the revisit queue. |
| // If no nodes in the revisit queue, try removing dead loops. |
| // If no dead loops, then finish. |
| } while (!stack_.empty() || TryRevisit() || RepairAndRemoveLoops()); |
| } |
| |
| bool TryRevisit() { |
| while (!revisit_.empty()) { |
| Node* n = revisit_.back(); |
| revisit_.pop_back(); |
| if (state_[n->id()] == kRevisit) { // state can change while in queue. |
| Push(n); |
| return true; |
| } |
| } |
| return false; |
| } |
| |
| // Repair the graph after the possible creation of non-terminating or dead |
| // loops. Removing dead loops can produce more opportunities for reduction. |
| bool RepairAndRemoveLoops() { |
| // TODO(turbofan): we can skip this if the graph has no loops, but |
| // we have to be careful about proper loop detection during reduction. |
| |
| // Gather all nodes backwards-reachable from end (through inputs). |
| ReachabilityMarker marked(graph()); |
| NodeVector nodes(zone_); |
| AddNodesReachableFromEnd(marked, nodes); |
| |
| // Walk forward through control nodes, looking for back edges to nodes |
| // that are not connected to end. Those are non-terminating loops (NTLs). |
| Node* start = graph()->start(); |
| marked.Push(start); |
| marked.SetReachableFromStart(start); |
| |
| // We use a stack of (Node, UseIter) pairs to avoid O(n^2) traversal. |
| typedef std::pair<Node*, UseIter> FwIter; |
| ZoneVector<FwIter> fw_stack(zone_); |
| fw_stack.push_back(FwIter(start, start->uses().begin())); |
| |
| while (!fw_stack.empty()) { |
| Node* node = fw_stack.back().first; |
| TRACE(("ControlFw: #%d:%s\n", node->id(), node->op()->mnemonic())); |
| bool pop = true; |
| while (fw_stack.back().second != node->uses().end()) { |
| Node* succ = *(fw_stack.back().second); |
| if (marked.IsOnStack(succ) && !marked.IsReachableFromEnd(succ)) { |
| // {succ} is on stack and not reachable from end. |
| Node* added = ConnectNTL(succ); |
| nodes.push_back(added); |
| marked.SetReachableFromEnd(added); |
| AddBackwardsReachableNodes(marked, nodes, nodes.size() - 1); |
| |
| // Reset the use iterators for the entire stack. |
| for (size_t i = 0; i < fw_stack.size(); i++) { |
| FwIter& iter = fw_stack[i]; |
| fw_stack[i] = FwIter(iter.first, iter.first->uses().begin()); |
| } |
| pop = false; // restart traversing successors of this node. |
| break; |
| } |
| if (IrOpcode::IsControlOpcode(succ->opcode()) && |
| !marked.IsReachableFromStart(succ)) { |
| // {succ} is a control node and not yet reached from start. |
| marked.Push(succ); |
| marked.SetReachableFromStart(succ); |
| fw_stack.push_back(FwIter(succ, succ->uses().begin())); |
| pop = false; // "recurse" into successor control node. |
| break; |
| } |
| ++fw_stack.back().second; |
| } |
| if (pop) { |
| marked.Pop(node); |
| fw_stack.pop_back(); |
| } |
| } |
| |
| // Trim references from dead nodes to live nodes first. |
| jsgraph_->GetCachedNodes(&nodes); |
| TrimNodes(marked, nodes); |
| |
| // Any control nodes not reachable from start are dead, even loops. |
| for (size_t i = 0; i < nodes.size(); i++) { |
| Node* node = nodes[i]; |
| if (IrOpcode::IsControlOpcode(node->opcode()) && |
| !marked.IsReachableFromStart(node)) { |
| ReplaceNode(node, dead()); // uses will be added to revisit queue. |
| } |
| } |
| return TryRevisit(); // try to push a node onto the stack. |
| } |
| |
| // Connect {loop}, the header of a non-terminating loop, to the end node. |
| Node* ConnectNTL(Node* loop) { |
| TRACE(("ConnectNTL: #%d:%s\n", loop->id(), loop->op()->mnemonic())); |
| |
| if (loop->opcode() != IrOpcode::kTerminate) { |
| // Insert a {Terminate} node if the loop has effects. |
| ZoneDeque<Node*> effects(zone_); |
| for (Node* const use : loop->uses()) { |
| if (use->opcode() == IrOpcode::kEffectPhi) effects.push_back(use); |
| } |
| int count = static_cast<int>(effects.size()); |
| if (count > 0) { |
| Node** inputs = zone_->NewArray<Node*>(1 + count); |
| for (int i = 0; i < count; i++) inputs[i] = effects[i]; |
| inputs[count] = loop; |
| loop = graph()->NewNode(common_->Terminate(count), 1 + count, inputs); |
| TRACE(("AddTerminate: #%d:%s[%d]\n", loop->id(), loop->op()->mnemonic(), |
| count)); |
| } |
| } |
| |
| Node* to_add = loop; |
| Node* end = graph()->end(); |
| CHECK_EQ(IrOpcode::kEnd, end->opcode()); |
| Node* merge = end->InputAt(0); |
| if (merge == NULL || merge->opcode() == IrOpcode::kDead) { |
| // The end node died; just connect end to {loop}. |
| end->ReplaceInput(0, loop); |
| } else if (merge->opcode() != IrOpcode::kMerge) { |
| // Introduce a final merge node for {end->InputAt(0)} and {loop}. |
| merge = graph()->NewNode(common_->Merge(2), merge, loop); |
| end->ReplaceInput(0, merge); |
| to_add = merge; |
| // Mark the node as visited so that we can revisit later. |
| EnsureStateSize(merge->id()); |
| state_[merge->id()] = kVisited; |
| } else { |
| // Append a new input to the final merge at the end. |
| merge->AppendInput(graph()->zone(), loop); |
| merge->set_op(common_->Merge(merge->InputCount())); |
| } |
| return to_add; |
| } |
| |
| void AddNodesReachableFromEnd(ReachabilityMarker& marked, NodeVector& nodes) { |
| Node* end = graph()->end(); |
| marked.SetReachableFromEnd(end); |
| if (!end->IsDead()) { |
| nodes.push_back(end); |
| AddBackwardsReachableNodes(marked, nodes, nodes.size() - 1); |
| } |
| } |
| |
| void AddBackwardsReachableNodes(ReachabilityMarker& marked, NodeVector& nodes, |
| size_t cursor) { |
| while (cursor < nodes.size()) { |
| Node* node = nodes[cursor++]; |
| for (Node* const input : node->inputs()) { |
| if (!marked.SetReachableFromEnd(input)) { |
| nodes.push_back(input); |
| } |
| } |
| } |
| } |
| |
| void Trim() { |
| // Gather all nodes backwards-reachable from end through inputs. |
| ReachabilityMarker marked(graph()); |
| NodeVector nodes(zone_); |
| AddNodesReachableFromEnd(marked, nodes); |
| |
| // Process cached nodes in the JSGraph too. |
| jsgraph_->GetCachedNodes(&nodes); |
| TrimNodes(marked, nodes); |
| } |
| |
| void TrimNodes(ReachabilityMarker& marked, NodeVector& nodes) { |
| // Remove dead->live edges. |
| for (size_t j = 0; j < nodes.size(); j++) { |
| Node* node = nodes[j]; |
| for (Edge edge : node->use_edges()) { |
| Node* use = edge.from(); |
| if (!marked.IsReachableFromEnd(use)) { |
| TRACE(("DeadLink: #%d:%s(%d) -> #%d:%s\n", use->id(), |
| use->op()->mnemonic(), edge.index(), node->id(), |
| node->op()->mnemonic())); |
| edge.UpdateTo(NULL); |
| } |
| } |
| } |
| #if DEBUG |
| // Verify that no inputs to live nodes are NULL. |
| for (size_t j = 0; j < nodes.size(); j++) { |
| Node* node = nodes[j]; |
| for (Node* const input : node->inputs()) { |
| CHECK_NE(NULL, input); |
| } |
| for (Node* const use : node->uses()) { |
| CHECK(marked.IsReachableFromEnd(use)); |
| } |
| } |
| #endif |
| } |
| |
| // Reduce the node on the top of the stack. |
| // If an input {i} is not yet visited or needs to be revisited, push {i} onto |
| // the stack and return. Otherwise, all inputs are visited, so apply |
| // reductions for {node} and pop it off the stack. |
| void ReduceTop() { |
| size_t height = stack_.size(); |
| Node* node = stack_.back(); |
| |
| if (node->IsDead()) return Pop(); // Node was killed while on stack. |
| |
| TRACE(("ControlReduce: #%d:%s\n", node->id(), node->op()->mnemonic())); |
| |
| // Recurse on an input if necessary. |
| for (Node* const input : node->inputs()) { |
| if (Recurse(input)) return; |
| } |
| |
| // All inputs should be visited or on stack. Apply reductions to node. |
| Node* replacement = ReduceNode(node); |
| if (replacement != node) ReplaceNode(node, replacement); |
| |
| // After reducing the node, pop it off the stack. |
| CHECK_EQ(static_cast<int>(height), static_cast<int>(stack_.size())); |
| Pop(); |
| |
| // If there was a replacement, reduce it after popping {node}. |
| if (replacement != node) Recurse(replacement); |
| } |
| |
| void EnsureStateSize(size_t id) { |
| if (id >= state_.size()) { |
| state_.resize((3 * id) / 2, kUnvisited); |
| } |
| } |
| |
| // Push a node onto the stack if its state is {kUnvisited} or {kRevisit}. |
| bool Recurse(Node* node) { |
| size_t id = static_cast<size_t>(node->id()); |
| EnsureStateSize(id); |
| if (state_[id] != kRevisit && state_[id] != kUnvisited) return false; |
| Push(node); |
| return true; |
| } |
| |
| void Push(Node* node) { |
| state_[node->id()] = kOnStack; |
| stack_.push_back(node); |
| } |
| |
| void Pop() { |
| int pos = static_cast<int>(stack_.size()) - 1; |
| DCHECK_GE(pos, 0); |
| DCHECK_EQ(kOnStack, state_[stack_[pos]->id()]); |
| state_[stack_[pos]->id()] = kVisited; |
| stack_.pop_back(); |
| } |
| |
| // Queue a node to be revisited if it has been visited once already. |
| void Revisit(Node* node) { |
| size_t id = static_cast<size_t>(node->id()); |
| if (id < state_.size() && state_[id] == kVisited) { |
| TRACE((" Revisit #%d:%s\n", node->id(), node->op()->mnemonic())); |
| state_[id] = kRevisit; |
| revisit_.push_back(node); |
| } |
| } |
| |
| Node* dead() { |
| if (dead_ == NULL) dead_ = graph()->NewNode(common_->Dead()); |
| return dead_; |
| } |
| |
| //=========================================================================== |
| // Reducer implementation: perform reductions on a node. |
| //=========================================================================== |
| Node* ReduceNode(Node* node) { |
| if (node->op()->ControlInputCount() == 1) { |
| // If a node has only one control input and it is dead, replace with dead. |
| Node* control = NodeProperties::GetControlInput(node); |
| if (control->opcode() == IrOpcode::kDead) { |
| TRACE(("ControlDead: #%d:%s\n", node->id(), node->op()->mnemonic())); |
| return control; |
| } |
| } |
| |
| // Reduce branches, phis, and merges. |
| switch (node->opcode()) { |
| case IrOpcode::kBranch: |
| return ReduceBranch(node); |
| case IrOpcode::kLoop: |
| case IrOpcode::kMerge: |
| return ReduceMerge(node); |
| case IrOpcode::kSelect: |
| return ReduceSelect(node); |
| case IrOpcode::kPhi: |
| case IrOpcode::kEffectPhi: |
| return ReducePhi(node); |
| default: |
| return node; |
| } |
| } |
| |
| // Try to statically fold a condition. |
| Decision DecideCondition(Node* cond) { |
| switch (cond->opcode()) { |
| case IrOpcode::kInt32Constant: |
| return Int32Matcher(cond).Is(0) ? kFalse : kTrue; |
| case IrOpcode::kInt64Constant: |
| return Int64Matcher(cond).Is(0) ? kFalse : kTrue; |
| case IrOpcode::kNumberConstant: |
| return NumberMatcher(cond).Is(0) ? kFalse : kTrue; |
| case IrOpcode::kHeapConstant: { |
| Handle<Object> object = |
| HeapObjectMatcher<Object>(cond).Value().handle(); |
| if (object->IsTrue()) return kTrue; |
| if (object->IsFalse()) return kFalse; |
| // TODO(turbofan): decide more conditions for heap constants. |
| break; |
| } |
| default: |
| break; |
| } |
| return kUnknown; |
| } |
| |
| // Reduce redundant selects. |
| Node* ReduceSelect(Node* const node) { |
| Node* const tvalue = node->InputAt(1); |
| Node* const fvalue = node->InputAt(2); |
| if (tvalue == fvalue) return tvalue; |
| Decision result = DecideCondition(node->InputAt(0)); |
| if (result == kTrue) return tvalue; |
| if (result == kFalse) return fvalue; |
| return node; |
| } |
| |
| // Reduce redundant phis. |
| Node* ReducePhi(Node* node) { |
| int n = node->InputCount(); |
| if (n <= 1) return dead(); // No non-control inputs. |
| if (n == 2) return node->InputAt(0); // Only one non-control input. |
| |
| // Never remove an effect phi from a (potentially non-terminating) loop. |
| // Otherwise, we might end up eliminating effect nodes, such as calls, |
| // before the loop. |
| if (node->opcode() == IrOpcode::kEffectPhi && |
| NodeProperties::GetControlInput(node)->opcode() == IrOpcode::kLoop) { |
| return node; |
| } |
| |
| Node* replacement = NULL; |
| Node::Inputs inputs = node->inputs(); |
| for (InputIter it = inputs.begin(); n > 1; --n, ++it) { |
| Node* input = *it; |
| if (input->opcode() == IrOpcode::kDead) continue; // ignore dead inputs. |
| if (input != node && input != replacement) { // non-redundant input. |
| if (replacement != NULL) return node; |
| replacement = input; |
| } |
| } |
| return replacement == NULL ? dead() : replacement; |
| } |
| |
| // Reduce merges by trimming away dead inputs from the merge and phis. |
| Node* ReduceMerge(Node* node) { |
| // Count the number of live inputs. |
| int live = 0; |
| int index = 0; |
| int live_index = 0; |
| for (Node* const input : node->inputs()) { |
| if (input->opcode() != IrOpcode::kDead) { |
| live++; |
| live_index = index; |
| } |
| index++; |
| } |
| |
| if (live > 1 && live == node->InputCount()) return node; // nothing to do. |
| |
| TRACE(("ReduceMerge: #%d:%s (%d live)\n", node->id(), |
| node->op()->mnemonic(), live)); |
| |
| if (live == 0) return dead(); // no remaining inputs. |
| |
| // Gather phis and effect phis to be edited. |
| ZoneVector<Node*> phis(zone_); |
| for (Node* const use : node->uses()) { |
| if (use->opcode() == IrOpcode::kPhi || |
| use->opcode() == IrOpcode::kEffectPhi) { |
| phis.push_back(use); |
| } |
| } |
| |
| if (live == 1) { |
| // All phis are redundant. Replace them with their live input. |
| for (Node* const phi : phis) ReplaceNode(phi, phi->InputAt(live_index)); |
| // The merge itself is redundant. |
| return node->InputAt(live_index); |
| } |
| |
| // Edit phis in place, removing dead inputs and revisiting them. |
| for (Node* const phi : phis) { |
| TRACE((" PhiInMerge: #%d:%s (%d live)\n", phi->id(), |
| phi->op()->mnemonic(), live)); |
| RemoveDeadInputs(node, phi); |
| Revisit(phi); |
| } |
| // Edit the merge in place, removing dead inputs. |
| RemoveDeadInputs(node, node); |
| return node; |
| } |
| |
| // Reduce branches if they have constant inputs. |
| Node* ReduceBranch(Node* node) { |
| Decision result = DecideCondition(node->InputAt(0)); |
| if (result == kUnknown) return node; |
| |
| TRACE(("BranchReduce: #%d:%s = %s\n", node->id(), node->op()->mnemonic(), |
| (result == kTrue) ? "true" : "false")); |
| |
| // Replace IfTrue and IfFalse projections from this branch. |
| Node* control = NodeProperties::GetControlInput(node); |
| for (Edge edge : node->use_edges()) { |
| Node* use = edge.from(); |
| if (use->opcode() == IrOpcode::kIfTrue) { |
| TRACE((" IfTrue: #%d:%s\n", use->id(), use->op()->mnemonic())); |
| edge.UpdateTo(NULL); |
| ReplaceNode(use, (result == kTrue) ? control : dead()); |
| } else if (use->opcode() == IrOpcode::kIfFalse) { |
| TRACE((" IfFalse: #%d:%s\n", use->id(), use->op()->mnemonic())); |
| edge.UpdateTo(NULL); |
| ReplaceNode(use, (result == kTrue) ? dead() : control); |
| } |
| } |
| return control; |
| } |
| |
| // Remove inputs to {node} corresponding to the dead inputs to {merge} |
| // and compact the remaining inputs, updating the operator. |
| void RemoveDeadInputs(Node* merge, Node* node) { |
| int pos = 0; |
| for (int i = 0; i < node->InputCount(); i++) { |
| // skip dead inputs. |
| if (i < merge->InputCount() && |
| merge->InputAt(i)->opcode() == IrOpcode::kDead) |
| continue; |
| // compact live inputs. |
| if (pos != i) node->ReplaceInput(pos, node->InputAt(i)); |
| pos++; |
| } |
| node->TrimInputCount(pos); |
| if (node->opcode() == IrOpcode::kPhi) { |
| node->set_op(common_->Phi(OpParameter<MachineType>(node->op()), pos - 1)); |
| } else if (node->opcode() == IrOpcode::kEffectPhi) { |
| node->set_op(common_->EffectPhi(pos - 1)); |
| } else if (node->opcode() == IrOpcode::kMerge) { |
| node->set_op(common_->Merge(pos)); |
| } else if (node->opcode() == IrOpcode::kLoop) { |
| node->set_op(common_->Loop(pos)); |
| } else { |
| UNREACHABLE(); |
| } |
| } |
| |
| // Replace uses of {node} with {replacement} and revisit the uses. |
| void ReplaceNode(Node* node, Node* replacement) { |
| if (node == replacement) return; |
| TRACE((" Replace: #%d:%s with #%d:%s\n", node->id(), |
| node->op()->mnemonic(), replacement->id(), |
| replacement->op()->mnemonic())); |
| for (Node* const use : node->uses()) { |
| // Don't revisit this node if it refers to itself. |
| if (use != node) Revisit(use); |
| } |
| node->ReplaceUses(replacement); |
| node->Kill(); |
| } |
| |
| Graph* graph() { return jsgraph_->graph(); } |
| }; |
| |
| |
| void ControlReducer::ReduceGraph(Zone* zone, JSGraph* jsgraph, |
| CommonOperatorBuilder* common) { |
| ControlReducerImpl impl(zone, jsgraph, common); |
| impl.Reduce(); |
| } |
| |
| |
| void ControlReducer::TrimGraph(Zone* zone, JSGraph* jsgraph) { |
| ControlReducerImpl impl(zone, jsgraph, NULL); |
| impl.Trim(); |
| } |
| |
| |
| Node* ControlReducer::ReducePhiForTesting(JSGraph* jsgraph, |
| CommonOperatorBuilder* common, |
| Node* node) { |
| Zone zone(jsgraph->graph()->zone()->isolate()); |
| ControlReducerImpl impl(&zone, jsgraph, common); |
| return impl.ReducePhi(node); |
| } |
| |
| |
| Node* ControlReducer::ReduceMergeForTesting(JSGraph* jsgraph, |
| CommonOperatorBuilder* common, |
| Node* node) { |
| Zone zone(jsgraph->graph()->zone()->isolate()); |
| ControlReducerImpl impl(&zone, jsgraph, common); |
| return impl.ReduceMerge(node); |
| } |
| |
| |
| Node* ControlReducer::ReduceBranchForTesting(JSGraph* jsgraph, |
| CommonOperatorBuilder* common, |
| Node* node) { |
| Zone zone(jsgraph->graph()->zone()->isolate()); |
| ControlReducerImpl impl(&zone, jsgraph, common); |
| return impl.ReduceBranch(node); |
| } |
| } |
| } |
| } // namespace v8::internal::compiler |