LCOV - code coverage report
Current view: top level - src/compiler - graph-reducer.cc (source / functions) Hit Total Coverage
Test: app.info Lines: 108 112 96.4 %
Date: 2017-04-26 Functions: 15 16 93.8 %

          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    20951465 : void Reducer::Finalize() {}
      27             : 
      28     3301866 : 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     6603728 :       stack_(zone) {
      35     3301893 :   if (dead != nullptr) {
      36     2875405 :     NodeProperties::SetType(dead_, Type::None());
      37             :   }
      38     3301893 : }
      39             : 
      40     6603565 : GraphReducer::~GraphReducer() {}
      41             : 
      42             : 
      43    16125661 : void GraphReducer::AddReducer(Reducer* reducer) {
      44    16125661 :   reducers_.push_back(reducer);
      45    16125566 : }
      46             : 
      47             : 
      48     8301754 : void GraphReducer::ReduceNode(Node* node) {
      49             :   DCHECK(stack_.empty());
      50             :   DCHECK(revisit_.empty());
      51     8301754 :   Push(node);
      52             :   for (;;) {
      53   617500137 :     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   593583035 :       ReduceTop();
      57    23917102 :     } else if (!revisit_.empty()) {
      58             :       // If the stack becomes empty, revisit any nodes in the revisit queue.
      59    15580978 :       Node* const node = revisit_.top();
      60             :       revisit_.pop();
      61    15580837 :       if (state_.Get(node) == State::kRevisit) {
      62             :         // state can change while in queue.
      63    12360046 :         Push(node);
      64             :       }
      65             :     } else {
      66             :       // Run all finalizers.
      67    38093187 :       for (Reducer* const reducer : reducers_) reducer->Finalize();
      68             : 
      69             :       // Check if we have new nodes to revisit.
      70     8336147 :       if (revisit_.empty()) break;
      71             :     }
      72             :   }
      73             :   DCHECK(revisit_.empty());
      74             :   DCHECK(stack_.empty());
      75     8301813 : }
      76             : 
      77             : 
      78     3277103 : void GraphReducer::ReduceGraph() { ReduceNode(graph()->end()); }
      79             : 
      80             : 
      81   310042541 : Reduction GraphReducer::Reduce(Node* const node) {
      82             :   auto skip = reducers_.end();
      83  2237149819 :   for (auto i = reducers_.begin(); i != reducers_.end();) {
      84  1624652279 :     if (i != skip) {
      85  1551952319 :       Reduction reduction = (*i)->Reduce(node);
      86  1552087776 :       if (!reduction.Changed()) {
      87             :         // No change from this reducer.
      88    80310627 :       } 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             :         skip = i;
      93             :         i = reducers_.begin();
      94             :         continue;
      95             :       } else {
      96             :         // {node} was replaced by another node.
      97     7722999 :         return reduction;
      98             :       }
      99             :     }
     100             :     ++i;
     101             :   }
     102   302454999 :   if (skip == reducers_.end()) {
     103             :     // No change from any reducer.
     104             :     return Reducer::NoChange();
     105             :   }
     106             :   // At least one reducer did some in-place reduction.
     107             :   return Reducer::Changed(node);
     108             : }
     109             : 
     110             : 
     111   903880609 : void GraphReducer::ReduceTop() {
     112             :   NodeState& entry = stack_.top();
     113   593791259 :   Node* node = entry.node;
     114             :   DCHECK(state_.Get(node) == State::kOnStack);
     115             : 
     116   593791259 :   if (node->IsDead()) return Pop();  // Node was killed while on stack.
     117             : 
     118             :   Node::Inputs node_inputs = node->inputs();
     119             : 
     120             :   // Recurse on an input if necessary.
     121   593158933 :   int start = entry.input_index < node_inputs.count() ? entry.input_index : 0;
     122  1318557832 :   for (int i = start; i < node_inputs.count(); ++i) {
     123             :     Node* input = node_inputs[i];
     124  1008309038 :     if (input != node && Recurse(input)) {
     125   282933235 :       entry.input_index = i + 1;
     126   282933235 :       return;
     127             :     }
     128             :   }
     129   292467411 :   for (int i = 0; i < start; ++i) {
     130             :     Node* input = node_inputs[i];
     131   292626855 :     if (input != node && Recurse(input)) {
     132      146278 :       entry.input_index = i + 1;
     133      146278 :       return;
     134             :     }
     135             :   }
     136             : 
     137             :   // Remember the max node id before reduction.
     138   310089350 :   NodeId const max_id = static_cast<NodeId>(graph()->NodeCount() - 1);
     139             : 
     140             :   // All inputs should be visited or on stack. Apply reductions to node.
     141   310089350 :   Reduction reduction = Reduce(node);
     142             : 
     143             :   // If there was no reduction, pop {node} and continue.
     144   310162729 :   if (!reduction.Changed()) return Pop();
     145             : 
     146             :   // Check if the reduction is an in-place update of the {node}.
     147             :   Node* const replacement = reduction.replacement();
     148    68376108 :   if (replacement == node) {
     149    60657329 :     if (FLAG_trace_turbo_reduction) {
     150           0 :       OFStream os(stdout);
     151           0 :       os << "- In-place update of " << *replacement << std::endl;
     152             :     }
     153             :     // In-place update of {node}, may need to recurse on an input.
     154             :     Node::Inputs node_inputs = node->inputs();
     155   267292359 :     for (int i = 0; i < node_inputs.count(); ++i) {
     156             :       Node* input = node_inputs[i];
     157   209323071 :       if (input != node && Recurse(input)) {
     158     2685961 :         entry.input_index = i + 1;
     159             :         return;
     160             :       }
     161             :     }
     162             :   }
     163             : 
     164             :   // After reducing the node, pop it off the stack.
     165    65688067 :   Pop();
     166             : 
     167             :   // Check if we have a new replacement.
     168    65692340 :   if (replacement != node) {
     169     7722977 :     Replace(node, replacement, max_id);
     170             :   } else {
     171             :     // Revisit all uses of the node.
     172   245457157 :     for (Node* const user : node->uses()) {
     173             :       // Don't revisit this node if it refers to itself.
     174   187489635 :       if (user != node) Revisit(user);
     175             :     }
     176             :   }
     177             : }
     178             : 
     179             : 
     180     1955328 : void GraphReducer::Replace(Node* node, Node* replacement) {
     181     2051531 :   Replace(node, replacement, std::numeric_limits<NodeId>::max());
     182     1955331 : }
     183             : 
     184             : 
     185    39097852 : void GraphReducer::Replace(Node* node, Node* replacement, NodeId max_id) {
     186     9774463 :   if (FLAG_trace_turbo_reduction) {
     187           0 :     OFStream os(stdout);
     188           0 :     os << "- Replacing " << *node << " with " << *replacement << std::endl;
     189             :   }
     190     9774463 :   if (node == graph()->start()) graph()->SetStart(replacement);
     191     9774463 :   if (node == graph()->end()) graph()->SetEnd(replacement);
     192     9774463 :   if (replacement->id() <= max_id) {
     193             :     // {replacement} is an old node, so unlink {node} and assume that
     194             :     // {replacement} was already reduced and finish.
     195    36282379 :     for (Edge edge : node->use_edges()) {
     196             :       Node* const user = edge.from();
     197             :       Verifier::VerifyEdgeInputReplacement(edge, replacement);
     198    14129241 :       edge.UpdateTo(replacement);
     199             :       // Don't revisit this node if it refers to itself.
     200    14129240 :       if (user != node) Revisit(user);
     201             :     }
     202     8023897 :     node->Kill();
     203             :   } else {
     204             :     // Replace all old uses of {node} with {replacement}, but allow new nodes
     205             :     // created by this reduction to use {node}.
     206    13577049 :     for (Edge edge : node->use_edges()) {
     207     5913244 :       Node* const user = edge.from();
     208     5913244 :       if (user->id() <= max_id) {
     209     5913244 :         edge.UpdateTo(replacement);
     210             :         // Don't revisit this node if it refers to itself.
     211     5913245 :         if (user != node) Revisit(user);
     212             :       }
     213             :     }
     214             :     // Unlink {node} if it's no longer used.
     215     1750561 :     if (node->uses().empty()) node->Kill();
     216             : 
     217             :     // If there was a replacement, reduce it after popping {node}.
     218     1750562 :     Recurse(replacement);
     219             :   }
     220     9774515 : }
     221             : 
     222             : 
     223     4781156 : void GraphReducer::ReplaceWithValue(Node* node, Node* value, Node* effect,
     224             :                                     Node* control) {
     225     4513366 :   if (effect == nullptr && node->op()->EffectInputCount() > 0) {
     226     1010634 :     effect = NodeProperties::GetEffectInput(node);
     227             :   }
     228     5048889 :   if (control == nullptr && node->op()->ControlInputCount() > 0) {
     229     1177088 :     control = NodeProperties::GetControlInput(node);
     230             :   }
     231             : 
     232             :   // Requires distinguishing between value, effect and control edges.
     233    23589940 :   for (Edge edge : node->use_edges()) {
     234     2296011 :     Node* const user = edge.from();
     235             :     DCHECK(!user->IsDead());
     236    10686818 :     if (NodeProperties::IsControlEdge(edge)) {
     237     2296011 :       if (user->opcode() == IrOpcode::kIfSuccess) {
     238             :         Replace(user, control);
     239     2199808 :       } else if (user->opcode() == IrOpcode::kIfException) {
     240             :         DCHECK_NOT_NULL(dead_);
     241       95919 :         edge.UpdateTo(dead_);
     242       95919 :         Revisit(user);
     243             :       } else {
     244             :         DCHECK_NOT_NULL(control);
     245     2103889 :         edge.UpdateTo(control);
     246     2103889 :         Revisit(user);
     247             :         // TODO(jarin) Check that the node cannot throw (otherwise, it
     248             :         // would have to be connected via IfSuccess/IfException).
     249             :       }
     250     8390751 :     } else if (NodeProperties::IsEffectEdge(edge)) {
     251             :       DCHECK_NOT_NULL(effect);
     252     2542986 :       edge.UpdateTo(effect);
     253     2543049 :       Revisit(user);
     254             :     } else {
     255             :       DCHECK_NOT_NULL(value);
     256     5848032 :       edge.UpdateTo(value);
     257     5848066 :       Revisit(user);
     258             :     }
     259             :   }
     260     2216304 : }
     261             : 
     262             : 
     263   308011487 : void GraphReducer::Pop() {
     264   308011487 :   Node* node = stack_.top().node;
     265             :   state_.Set(node, State::kVisited);
     266             :   stack_.pop();
     267   308026872 : }
     268             : 
     269             : 
     270   308069804 : void GraphReducer::Push(Node* const node) {
     271             :   DCHECK(state_.Get(node) != State::kOnStack);
     272             :   state_.Set(node, State::kOnStack);
     273   616234460 :   stack_.push({node, 0});
     274   308167291 : }
     275             : 
     276             : 
     277  1510594321 : bool GraphReducer::Recurse(Node* node) {
     278  1510650801 :   if (state_.Get(node) > State::kRevisit) return false;
     279   287460794 :   Push(node);
     280   287518343 :   return true;
     281             : }
     282             : 
     283             : 
     284   218628965 : void GraphReducer::Revisit(Node* node) {
     285   437257930 :   if (state_.Get(node) == State::kVisited) {
     286             :     state_.Set(node, State::kRevisit);
     287             :     revisit_.push(node);
     288             :   }
     289   218628753 : }
     290             : 
     291             : }  // namespace compiler
     292             : }  // namespace internal
     293             : }  // namespace v8

Generated by: LCOV version 1.10