Home | History | Annotate | Download | only in compiler 
      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
     99