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 <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 void Reducer::Finalize() {}
     27 
     28 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       stack_(zone) {
     35   if (dead != nullptr) {
     36     NodeProperties::SetType(dead_, Type::None());
     37   }
     38 }
     39 
     40 GraphReducer::~GraphReducer() {}
     41 
     42 
     43 void GraphReducer::AddReducer(Reducer* reducer) {
     44   reducers_.push_back(reducer);
     45 }
     46 
     47 
     48 void GraphReducer::ReduceNode(Node* node) {
     49   DCHECK(stack_.empty());
     50   DCHECK(revisit_.empty());
     51   Push(node);
     52   for (;;) {
     53     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       ReduceTop();
     57     } else if (!revisit_.empty()) {
     58       // If the stack becomes empty, revisit any nodes in the revisit queue.
     59       Node* const node = revisit_.top();
     60       revisit_.pop();
     61       if (state_.Get(node) == State::kRevisit) {
     62         // state can change while in queue.
     63         Push(node);
     64       }
     65     } else {
     66       // Run all finalizers.
     67       for (Reducer* const reducer : reducers_) reducer->Finalize();
     68 
     69       // Check if we have new nodes to revisit.
     70       if (revisit_.empty()) break;
     71     }
     72   }
     73   DCHECK(revisit_.empty());
     74   DCHECK(stack_.empty());
     75 }
     76 
     77 
     78 void GraphReducer::ReduceGraph() { ReduceNode(graph()->end()); }
     79 
     80 
     81 Reduction GraphReducer::Reduce(Node* const node) {
     82   auto skip = reducers_.end();
     83   for (auto i = reducers_.begin(); i != reducers_.end();) {
     84     if (i != skip) {
     85       Reduction reduction = (*i)->Reduce(node);
     86       if (!reduction.Changed()) {
     87         // No change from this reducer.
     88       } 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         return reduction;
     98       }
     99     }
    100     ++i;
    101   }
    102   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 void GraphReducer::ReduceTop() {
    112   NodeState& entry = stack_.top();
    113   Node* node = entry.node;
    114   DCHECK(state_.Get(node) == State::kOnStack);
    115 
    116   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   int start = entry.input_index < node_inputs.count() ? entry.input_index : 0;
    122   for (int i = start; i < node_inputs.count(); ++i) {
    123     Node* input = node_inputs[i];
    124     if (input != node && Recurse(input)) {
    125       entry.input_index = i + 1;
    126       return;
    127     }
    128   }
    129   for (int i = 0; i < start; ++i) {
    130     Node* input = node_inputs[i];
    131     if (input != node && Recurse(input)) {
    132       entry.input_index = i + 1;
    133       return;
    134     }
    135   }
    136 
    137   // Remember the max node id before reduction.
    138   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   Reduction reduction = Reduce(node);
    142 
    143   // If there was no reduction, pop {node} and continue.
    144   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   if (replacement == node) {
    149     // In-place update of {node}, may need to recurse on an input.
    150     Node::Inputs node_inputs = node->inputs();
    151     for (int i = 0; i < node_inputs.count(); ++i) {
    152       Node* input = node_inputs[i];
    153       if (input != node && Recurse(input)) {
    154         entry.input_index = i + 1;
    155         return;
    156       }
    157     }
    158   }
    159 
    160   // After reducing the node, pop it off the stack.
    161   Pop();
    162 
    163   // Check if we have a new replacement.
    164   if (replacement != node) {
    165     Replace(node, replacement, max_id);
    166   } else {
    167     // Revisit all uses of the node.
    168     for (Node* const user : node->uses()) {
    169       // Don't revisit this node if it refers to itself.
    170       if (user != node) Revisit(user);
    171     }
    172   }
    173 }
    174 
    175 
    176 void GraphReducer::Replace(Node* node, Node* replacement) {
    177   Replace(node, replacement, std::numeric_limits<NodeId>::max());
    178 }
    179 
    180 
    181 void GraphReducer::Replace(Node* node, Node* replacement, NodeId max_id) {
    182   if (FLAG_trace_turbo_reduction) {
    183     OFStream os(stdout);
    184     os << "- Replacing " << *node << " with " << *replacement << std::endl;
    185   }
    186   if (node == graph()->start()) graph()->SetStart(replacement);
    187   if (node == graph()->end()) graph()->SetEnd(replacement);
    188   if (replacement->id() <= max_id) {
    189     // {replacement} is an old node, so unlink {node} and assume that
    190     // {replacement} was already reduced and finish.
    191     for (Edge edge : node->use_edges()) {
    192       Node* const user = edge.from();
    193       Verifier::VerifyEdgeInputReplacement(edge, replacement);
    194       edge.UpdateTo(replacement);
    195       // Don't revisit this node if it refers to itself.
    196       if (user != node) Revisit(user);
    197     }
    198     node->Kill();
    199   } else {
    200     // Replace all old uses of {node} with {replacement}, but allow new nodes
    201     // created by this reduction to use {node}.
    202     for (Edge edge : node->use_edges()) {
    203       Node* const user = edge.from();
    204       if (user->id() <= max_id) {
    205         edge.UpdateTo(replacement);
    206         // Don't revisit this node if it refers to itself.
    207         if (user != node) Revisit(user);
    208       }
    209     }
    210     // Unlink {node} if it's no longer used.
    211     if (node->uses().empty()) node->Kill();
    212 
    213     // If there was a replacement, reduce it after popping {node}.
    214     Recurse(replacement);
    215   }
    216 }
    217 
    218 
    219 void GraphReducer::ReplaceWithValue(Node* node, Node* value, Node* effect,
    220                                     Node* control) {
    221   if (effect == nullptr && node->op()->EffectInputCount() > 0) {
    222     effect = NodeProperties::GetEffectInput(node);
    223   }
    224   if (control == nullptr && node->op()->ControlInputCount() > 0) {
    225     control = NodeProperties::GetControlInput(node);
    226   }
    227 
    228   // Requires distinguishing between value, effect and control edges.
    229   for (Edge edge : node->use_edges()) {
    230     Node* const user = edge.from();
    231     DCHECK(!user->IsDead());
    232     if (NodeProperties::IsControlEdge(edge)) {
    233       if (user->opcode() == IrOpcode::kIfSuccess) {
    234         Replace(user, control);
    235       } else if (user->opcode() == IrOpcode::kIfException) {
    236         DCHECK_NOT_NULL(dead_);
    237         edge.UpdateTo(dead_);
    238         Revisit(user);
    239       } else {
    240         DCHECK_NOT_NULL(control);
    241         edge.UpdateTo(control);
    242         Revisit(user);
    243         // TODO(jarin) Check that the node cannot throw (otherwise, it
    244         // would have to be connected via IfSuccess/IfException).
    245       }
    246     } else if (NodeProperties::IsEffectEdge(edge)) {
    247       DCHECK_NOT_NULL(effect);
    248       edge.UpdateTo(effect);
    249       Revisit(user);
    250     } else {
    251       DCHECK_NOT_NULL(value);
    252       edge.UpdateTo(value);
    253       Revisit(user);
    254     }
    255   }
    256 }
    257 
    258 
    259 void GraphReducer::Pop() {
    260   Node* node = stack_.top().node;
    261   state_.Set(node, State::kVisited);
    262   stack_.pop();
    263 }
    264 
    265 
    266 void GraphReducer::Push(Node* const node) {
    267   DCHECK(state_.Get(node) != State::kOnStack);
    268   state_.Set(node, State::kOnStack);
    269   stack_.push({node, 0});
    270 }
    271 
    272 
    273 bool GraphReducer::Recurse(Node* node) {
    274   if (state_.Get(node) > State::kRevisit) return false;
    275   Push(node);
    276   return true;
    277 }
    278 
    279 
    280 void GraphReducer::Revisit(Node* node) {
    281   if (state_.Get(node) == State::kVisited) {
    282     state_.Set(node, State::kRevisit);
    283     revisit_.push(node);
    284   }
    285 }
    286 
    287 }  // namespace compiler
    288 }  // namespace internal
    289 }  // namespace v8
    290