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_.front();
     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         if (FLAG_trace_turbo_reduction) {
     93           StdoutStream{} << "- In-place update of " << *node << " by reducer "
     94                          << (*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         if (FLAG_trace_turbo_reduction) {
    102           StdoutStream{} << "- Replacement of " << *node << " with "
    103                          << *(reduction.replacement()) << " by reducer "
    104                          << (*i)->reducer_name() << std::endl;
    105         }
    106         return reduction;
    107       }
    108     }
    109     ++i;
    110   }
    111   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 void GraphReducer::ReduceTop() {
    121   NodeState& entry = stack_.top();
    122   Node* node = entry.node;
    123   DCHECK_EQ(State::kOnStack, state_.Get(node));
    124 
    125   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   int start = entry.input_index < node_inputs.count() ? entry.input_index : 0;
    131   for (int i = start; i < node_inputs.count(); ++i) {
    132     Node* input = node_inputs[i];
    133     if (input != node && Recurse(input)) {
    134       entry.input_index = i + 1;
    135       return;
    136     }
    137   }
    138   for (int i = 0; i < start; ++i) {
    139     Node* input = node_inputs[i];
    140     if (input != node && Recurse(input)) {
    141       entry.input_index = i + 1;
    142       return;
    143     }
    144   }
    145 
    146   // Remember the max node id before reduction.
    147   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   Reduction reduction = Reduce(node);
    151 
    152   // If there was no reduction, pop {node} and continue.
    153   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   if (replacement == node) {
    158     // In-place update of {node}, may need to recurse on an input.
    159     Node::Inputs node_inputs = node->inputs();
    160     for (int i = 0; i < node_inputs.count(); ++i) {
    161       Node* input = node_inputs[i];
    162       if (input != node && Recurse(input)) {
    163         entry.input_index = i + 1;
    164         return;
    165       }
    166     }
    167   }
    168 
    169   // After reducing the node, pop it off the stack.
    170   Pop();
    171 
    172   // Check if we have a new replacement.
    173   if (replacement != node) {
    174     Replace(node, replacement, max_id);
    175   } else {
    176     // Revisit all uses of the node.
    177     for (Node* const user : node->uses()) {
    178       // Don't revisit this node if it refers to itself.
    179       if (user != node) Revisit(user);
    180     }
    181   }
    182 }
    183 
    184 
    185 void GraphReducer::Replace(Node* node, Node* replacement) {
    186   Replace(node, replacement, std::numeric_limits<NodeId>::max());
    187 }
    188 
    189 
    190 void GraphReducer::Replace(Node* node, Node* replacement, NodeId max_id) {
    191   if (node == graph()->start()) graph()->SetStart(replacement);
    192   if (node == graph()->end()) graph()->SetEnd(replacement);
    193   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     for (Edge edge : node->use_edges()) {
    197       Node* const user = edge.from();
    198       Verifier::VerifyEdgeInputReplacement(edge, replacement);
    199       edge.UpdateTo(replacement);
    200       // Don't revisit this node if it refers to itself.
    201       if (user != node) Revisit(user);
    202     }
    203     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     for (Edge edge : node->use_edges()) {
    208       Node* const user = edge.from();
    209       if (user->id() <= max_id) {
    210         edge.UpdateTo(replacement);
    211         // Don't revisit this node if it refers to itself.
    212         if (user != node) Revisit(user);
    213       }
    214     }
    215     // Unlink {node} if it's no longer used.
    216     if (node->uses().empty()) node->Kill();
    217 
    218     // If there was a replacement, reduce it after popping {node}.
    219     Recurse(replacement);
    220   }
    221 }
    222 
    223 
    224 void GraphReducer::ReplaceWithValue(Node* node, Node* value, Node* effect,
    225                                     Node* control) {
    226   if (effect == nullptr && node->op()->EffectInputCount() > 0) {
    227     effect = NodeProperties::GetEffectInput(node);
    228   }
    229   if (control == nullptr && node->op()->ControlInputCount() > 0) {
    230     control = NodeProperties::GetControlInput(node);
    231   }
    232 
    233   // Requires distinguishing between value, effect and control edges.
    234   for (Edge edge : node->use_edges()) {
    235     Node* const user = edge.from();
    236     DCHECK(!user->IsDead());
    237     if (NodeProperties::IsControlEdge(edge)) {
    238       if (user->opcode() == IrOpcode::kIfSuccess) {
    239         Replace(user, control);
    240       } else if (user->opcode() == IrOpcode::kIfException) {
    241         DCHECK_NOT_NULL(dead_);
    242         edge.UpdateTo(dead_);
    243         Revisit(user);
    244       } else {
    245         DCHECK_NOT_NULL(control);
    246         edge.UpdateTo(control);
    247         Revisit(user);
    248       }
    249     } else if (NodeProperties::IsEffectEdge(edge)) {
    250       DCHECK_NOT_NULL(effect);
    251       edge.UpdateTo(effect);
    252       Revisit(user);
    253     } else {
    254       DCHECK_NOT_NULL(value);
    255       edge.UpdateTo(value);
    256       Revisit(user);
    257     }
    258   }
    259 }
    260 
    261 
    262 void GraphReducer::Pop() {
    263   Node* node = stack_.top().node;
    264   state_.Set(node, State::kVisited);
    265   stack_.pop();
    266 }
    267 
    268 
    269 void GraphReducer::Push(Node* const node) {
    270   DCHECK_NE(State::kOnStack, state_.Get(node));
    271   state_.Set(node, State::kOnStack);
    272   stack_.push({node, 0});
    273 }
    274 
    275 
    276 bool GraphReducer::Recurse(Node* node) {
    277   if (state_.Get(node) > State::kRevisit) return false;
    278   Push(node);
    279   return true;
    280 }
    281 
    282 
    283 void GraphReducer::Revisit(Node* node) {
    284   if (state_.Get(node) == State::kVisited) {
    285     state_.Set(node, State::kRevisit);
    286     revisit_.push(node);
    287   }
    288 }
    289 
    290 }  // namespace compiler
    291 }  // namespace internal
    292 }  // namespace v8
    293