LCOV - code coverage report
Current view: top level - src/compiler - graph-reducer.cc (source / functions) Hit Total Coverage
Test: app.info Lines: 101 108 93.5 %
Date: 2019-04-17 Functions: 14 15 93.3 %

          Line data    Source code
       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.
       4             : 
       5             : #include <functional>
       6             : #include <limits>
       7             : 
       8             : #include "src/compiler/graph.h"
       9             : #include "src/compiler/graph-reducer.h"
      10             : #include "src/compiler/node.h"
      11             : #include "src/compiler/node-properties.h"
      12             : #include "src/compiler/verifier.h"
      13             : 
      14             : namespace v8 {
      15             : namespace internal {
      16             : namespace compiler {
      17             : 
      18             : enum class GraphReducer::State : uint8_t {
      19             :   kUnvisited,
      20             :   kRevisit,
      21             :   kOnStack,
      22             :   kVisited
      23             : };
      24             : 
      25             : 
      26    32890570 : void Reducer::Finalize() {}
      27             : 
      28     5809448 : GraphReducer::GraphReducer(Zone* zone, Graph* graph, Node* dead)
      29             :     : graph_(graph),
      30             :       dead_(dead),
      31             :       state_(graph, 4),
      32             :       reducers_(zone),
      33             :       revisit_(zone),
      34    11618229 :       stack_(zone) {
      35     5809166 :   if (dead != nullptr) {
      36     5327249 :     NodeProperties::SetType(dead_, Type::None());
      37             :   }
      38     5809166 : }
      39             : 
      40             : GraphReducer::~GraphReducer() = default;
      41             : 
      42             : 
      43    22263228 : void GraphReducer::AddReducer(Reducer* reducer) {
      44    22263228 :   reducers_.push_back(reducer);
      45    22263322 : }
      46             : 
      47             : 
      48    17500824 : void GraphReducer::ReduceNode(Node* node) {
      49             :   DCHECK(stack_.empty());
      50             :   DCHECK(revisit_.empty());
      51             :   Push(node);
      52             :   for (;;) {
      53   944323092 :     if (!stack_.empty()) {
      54             :       // Process the node on the top of the stack, potentially pushing more or
      55             :       // popping the node off the stack.
      56   906154043 :       ReduceTop();
      57    38169049 :     } else if (!revisit_.empty()) {
      58             :       // If the stack becomes empty, revisit any nodes in the revisit queue.
      59    20612777 :       Node* const node = revisit_.front();
      60             :       revisit_.pop();
      61    20612684 :       if (state_.Get(node) == State::kRevisit) {
      62             :         // state can change while in queue.
      63             :         Push(node);
      64             :       }
      65             :     } else {
      66             :       // Run all finalizers.
      67    51942972 :       for (Reducer* const reducer : reducers_) reducer->Finalize();
      68             : 
      69             :       // Check if we have new nodes to revisit.
      70    17556257 :       if (revisit_.empty()) break;
      71             :     }
      72             :   }
      73             :   DCHECK(revisit_.empty());
      74             :   DCHECK(stack_.empty());
      75    17503784 : }
      76             : 
      77             : 
      78     5790681 : void GraphReducer::ReduceGraph() { ReduceNode(graph()->end()); }
      79             : 
      80             : 
      81   472093411 : Reduction GraphReducer::Reduce(Node* const node) {
      82             :   auto skip = reducers_.end();
      83  2524236230 :   for (auto i = reducers_.begin(); i != reducers_.end();) {
      84  2059852072 :     if (i != skip) {
      85  1969919169 :       Reduction reduction = (*i)->Reduce(node);
      86  1970138092 :       if (!reduction.Changed()) {
      87             :         // No change from this reducer.
      88    97850023 :       } else if (reduction.replacement() == node) {
      89             :         // {replacement} == {node} represents an in-place reduction. Rerun
      90             :         // all the other reducers for this node, as now there may be more
      91             :         // opportunities for reduction.
      92    89921847 :         if (FLAG_trace_turbo_reduction) {
      93           0 :           StdoutStream{} << "- In-place update of " << *node << " by reducer "
      94           0 :                          << (*i)->reducer_name() << std::endl;
      95             :         }
      96             :         skip = i;
      97             :         i = reducers_.begin();
      98             :         continue;
      99             :       } else {
     100             :         // {node} was replaced by another node.
     101     7928176 :         if (FLAG_trace_turbo_reduction) {
     102           0 :           StdoutStream{} << "- Replacement of " << *node << " with "
     103           0 :                          << *(reduction.replacement()) << " by reducer "
     104           0 :                          << (*i)->reducer_name() << std::endl;
     105             :         }
     106     7928176 :         return reduction;
     107             :       }
     108             :     }
     109             :     ++i;
     110             :   }
     111   464384158 :   if (skip == reducers_.end()) {
     112             :     // No change from any reducer.
     113             :     return Reducer::NoChange();
     114             :   }
     115             :   // At least one reducer did some in-place reduction.
     116             :   return Reducer::Changed(node);
     117             : }
     118             : 
     119             : 
     120   906777189 : void GraphReducer::ReduceTop() {
     121             :   NodeState& entry = stack_.top();
     122   906777189 :   Node* node = entry.node;
     123             :   DCHECK_EQ(State::kOnStack, state_.Get(node));
     124             : 
     125   906777189 :   if (node->IsDead()) return Pop();  // Node was killed while on stack.
     126             : 
     127             :   Node::Inputs node_inputs = node->inputs();
     128             : 
     129             :   // Recurse on an input if necessary.
     130   906197702 :   int start = entry.input_index < node_inputs.count() ? entry.input_index : 0;
     131  3101891244 :   for (int i = start; i < node_inputs.count(); ++i) {
     132             :     Node* input = node_inputs[i];
     133  1531538186 :     if (input != node && Recurse(input)) {
     134   433884118 :       entry.input_index = i + 1;
     135   433884118 :       return;
     136             :     }
     137             :   }
     138  1341846783 :   for (int i = 0; i < start; ++i) {
     139             :     Node* input = node_inputs[i];
     140   434870095 :     if (input != node && Recurse(input)) {
     141      150866 :       entry.input_index = i + 1;
     142      150866 :       return;
     143             :     }
     144             :   }
     145             : 
     146             :   // Remember the max node id before reduction.
     147   472306440 :   NodeId const max_id = static_cast<NodeId>(graph()->NodeCount() - 1);
     148             : 
     149             :   // All inputs should be visited or on stack. Apply reductions to node.
     150   472306440 :   Reduction reduction = Reduce(node);
     151             : 
     152             :   // If there was no reduction, pop {node} and continue.
     153   472299281 :   if (!reduction.Changed()) return Pop();
     154             : 
     155             :   // Check if the reduction is an in-place update of the {node}.
     156             :   Node* const replacement = reduction.replacement();
     157    82126522 :   if (replacement == node) {
     158             :     // In-place update of {node}, may need to recurse on an input.
     159             :     Node::Inputs node_inputs = node->inputs();
     160   574938113 :     for (int i = 0; i < node_inputs.count(); ++i) {
     161             :       Node* input = node_inputs[i];
     162   253432052 :       if (input != node && Recurse(input)) {
     163     3066655 :         entry.input_index = i + 1;
     164             :         return;
     165             :       }
     166             :     }
     167             :   }
     168             : 
     169             :   // After reducing the node, pop it off the stack.
     170    79060992 :   Pop();
     171             : 
     172             :   // Check if we have a new replacement.
     173    79067252 :   if (replacement != node) {
     174     7928044 :     Replace(node, replacement, max_id);
     175             :   } else {
     176             :     // Revisit all uses of the node.
     177   321147547 :     for (Node* const user : node->uses()) {
     178             :       // Don't revisit this node if it refers to itself.
     179   250006452 :       if (user != node) Revisit(user);
     180             :     }
     181             :   }
     182             : }
     183             : 
     184             : 
     185     1611370 : void GraphReducer::Replace(Node* node, Node* replacement) {
     186     1646118 :   Replace(node, replacement, std::numeric_limits<NodeId>::max());
     187     1611374 : }
     188             : 
     189             : 
     190     9574251 : void GraphReducer::Replace(Node* node, Node* replacement, NodeId max_id) {
     191     9574251 :   if (node == graph()->start()) graph()->SetStart(replacement);
     192     9574251 :   if (node == graph()->end()) graph()->SetEnd(replacement);
     193     9574251 :   if (replacement->id() <= max_id) {
     194             :     // {replacement} is an old node, so unlink {node} and assume that
     195             :     // {replacement} was already reduced and finish.
     196    36720670 :     for (Edge edge : node->use_edges()) {
     197             :       Node* const user = edge.from();
     198             :       Verifier::VerifyEdgeInputReplacement(edge, replacement);
     199    14181419 :       edge.UpdateTo(replacement);
     200             :       // Don't revisit this node if it refers to itself.
     201    14181315 :       if (user != node) Revisit(user);
     202             :     }
     203     8357832 :     node->Kill();
     204             :   } else {
     205             :     // Replace all old uses of {node} with {replacement}, but allow new nodes
     206             :     // created by this reduction to use {node}.
     207    14143354 :     for (Edge edge : node->use_edges()) {
     208             :       Node* const user = edge.from();
     209     6463482 :       if (user->id() <= max_id) {
     210     6463416 :         edge.UpdateTo(replacement);
     211             :         // Don't revisit this node if it refers to itself.
     212     6463420 :         if (user != node) Revisit(user);
     213             :       }
     214             :     }
     215             :     // Unlink {node} if it's no longer used.
     216     1216390 :     if (node->uses().empty()) node->Kill();
     217             : 
     218             :     // If there was a replacement, reduce it after popping {node}.
     219     1216396 :     Recurse(replacement);
     220             :   }
     221     9574421 : }
     222             : 
     223             : 
     224     2212026 : void GraphReducer::ReplaceWithValue(Node* node, Node* value, Node* effect,
     225             :                                     Node* control) {
     226     3547453 :   if (effect == nullptr && node->op()->EffectInputCount() > 0) {
     227     1110959 :     effect = NodeProperties::GetEffectInput(node);
     228             :   }
     229     3914014 :   if (control == nullptr && node->op()->ControlInputCount() > 0) {
     230     1506881 :     control = NodeProperties::GetControlInput(node);
     231             :   }
     232             : 
     233             :   // Requires distinguishing between value, effect and control edges.
     234    21296443 :   for (Edge edge : node->use_edges()) {
     235             :     Node* const user = edge.from();
     236             :     DCHECK(!user->IsDead());
     237     9542307 :     if (NodeProperties::IsControlEdge(edge)) {
     238     2823420 :       if (user->opcode() == IrOpcode::kIfSuccess) {
     239             :         Replace(user, control);
     240     2788672 :       } else if (user->opcode() == IrOpcode::kIfException) {
     241             :         DCHECK_NOT_NULL(dead_);
     242       34314 :         edge.UpdateTo(dead_);
     243       34314 :         Revisit(user);
     244             :       } else {
     245             :         DCHECK_NOT_NULL(control);
     246     2754358 :         edge.UpdateTo(control);
     247     2754358 :         Revisit(user);
     248             :       }
     249     6718763 :     } else if (NodeProperties::IsEffectEdge(edge)) {
     250             :       DCHECK_NOT_NULL(effect);
     251     2291236 :       edge.UpdateTo(effect);
     252     2291265 :       Revisit(user);
     253             :     } else {
     254             :       DCHECK_NOT_NULL(value);
     255     4428112 :       edge.UpdateTo(value);
     256     4428125 :       Revisit(user);
     257             :     }
     258             :   }
     259     2211829 : }
     260             : 
     261             : 
     262   469641985 : void GraphReducer::Pop() {
     263   469641985 :   Node* node = stack_.top().node;
     264             :   state_.Set(node, State::kVisited);
     265             :   stack_.pop();
     266   469621076 : }
     267             : 
     268             : 
     269           0 : void GraphReducer::Push(Node* const node) {
     270             :   DCHECK_NE(State::kOnStack, state_.Get(node));
     271             :   state_.Set(node, State::kOnStack);
     272   940037534 :   stack_.push({node, 0});
     273           0 : }
     274             : 
     275             : 
     276  2218388578 : bool GraphReducer::Recurse(Node* node) {
     277  2218388578 :   if (state_.Get(node) > State::kRevisit) return false;
     278             :   Push(node);
     279   438334355 :   return true;
     280             : }
     281             : 
     282             : 
     283   280632342 : void GraphReducer::Revisit(Node* node) {
     284   561264684 :   if (state_.Get(node) == State::kVisited) {
     285             :     state_.Set(node, State::kRevisit);
     286             :     revisit_.push(node);
     287             :   }
     288   280632212 : }
     289             : 
     290             : }  // namespace compiler
     291             : }  // namespace internal
     292      122004 : }  // namespace v8

Generated by: LCOV version 1.10