src/v8/src/compiler/graph-reducer.cc

   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 "src/compiler/graph-reducer.h"
   6
   7 #include <functional>
   8
   9 #include "src/compiler/graph-inl.h"
  10
  11 namespace v8 {
  12 namespace internal {
  13 namespace compiler {
  14
  15 GraphReducer::GraphReducer(Graph* graph)
  16     : graph_(graph), reducers_(graph->zone()) {}
  17
  18
  19 static bool NodeIdIsLessThan(const Node* node, NodeId id) {
  20   return node->id() < id;
  21 }
  22
  23
  24 void GraphReducer::ReduceNode(Node* node) {
  25   ZoneVector<Reducer*>::iterator skip = reducers_.end();
  26   static const unsigned kMaxAttempts = 16;
  27   bool reduce = true;
  28   for (unsigned attempts = 0; attempts <= kMaxAttempts; ++attempts) {
  29     if (!reduce) return;
  30     reduce = false;  // Assume we don't need to rerun any reducers.
  31     int before = graph_->NodeCount();
  32     for (ZoneVector<Reducer*>::iterator i = reducers_.begin();
  33          i != reducers_.end(); ++i) {
  34       if (i == skip) continue;  // Skip this reducer.
  35       Reduction reduction = (*i)->Reduce(node);
  36       Node* replacement = reduction.replacement();
  37       if (replacement == NULL) {
  38         // No change from this reducer.
  39       } else if (replacement == node) {
  40         // {replacement == node} represents an in-place reduction.
  41         // Rerun all the reducers except the current one for this node,
  42         // as now there may be more opportunities for reduction.
  43         reduce = true;
  44         skip = i;
  45         break;
  46       } else {
  47         if (node == graph_->start()) graph_->SetStart(replacement);
  48         if (node == graph_->end()) graph_->SetEnd(replacement);
  49         // If {node} was replaced by an old node, unlink {node} and assume that
  50         // {replacement} was already reduced and finish.
  51         if (replacement->id() < before) {
  52           node->ReplaceUses(replacement);
  53           node->Kill();
  54           return;
  55         }
  56         // Otherwise, {node} was replaced by a new node. Replace all old uses of
  57         // {node} with {replacement}. New nodes created by this reduction can
  58         // use {node}.
  59         node->ReplaceUsesIf(
  60             std::bind2nd(std::ptr_fun(&NodeIdIsLessThan), before), replacement);
  61         // Unlink {node} if it's no longer used.
  62         if (node->uses().empty()) {
  63           node->Kill();
  64         }
  65         // Rerun all the reductions on the {replacement}.
  66         skip = reducers_.end();
  67         node = replacement;
  68         reduce = true;
  69         break;
  70       }
  71     }
  72   }
  73 }
  74
  75
  76 // A helper class to reuse the node traversal algorithm.
  77 struct GraphReducerVisitor FINAL : public NullNodeVisitor {
  78   explicit GraphReducerVisitor(GraphReducer* reducer) : reducer_(reducer) {}
  79   GenericGraphVisit::Control Post(Node* node) {
  80     reducer_->ReduceNode(node);
  81     return GenericGraphVisit::CONTINUE;
  82   }
  83   GraphReducer* reducer_;
  84 };
  85
  86
  87 void GraphReducer::ReduceGraph() {
  88   GraphReducerVisitor visitor(this);
  89   // Perform a post-order reduction of all nodes starting from the end.
  90   graph()->VisitNodeInputsFromEnd(&visitor);
  91 }
  92
  93
  94 // TODO(titzer): partial graph reductions.
  95
  96 }  // namespace compiler
  97 }  // namespace internal
  98 }  // namespace v8