LCOV - code coverage report
Current view: top level - src/compiler - graph-reducer.h (source / functions) Hit Total Coverage
Test: app.info Lines: 12 12 100.0 %
Date: 2017-04-26 Functions: 0 6 0.0 %

          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             : #ifndef V8_COMPILER_GRAPH_REDUCER_H_
       6             : #define V8_COMPILER_GRAPH_REDUCER_H_
       7             : 
       8             : #include "src/base/compiler-specific.h"
       9             : #include "src/compiler/node-marker.h"
      10             : #include "src/globals.h"
      11             : #include "src/zone/zone-containers.h"
      12             : 
      13             : namespace v8 {
      14             : namespace internal {
      15             : namespace compiler {
      16             : 
      17             : // Forward declarations.
      18             : class Graph;
      19             : class Node;
      20             : 
      21             : 
      22             : // NodeIds are identifying numbers for nodes that can be used to index auxiliary
      23             : // out-of-line data associated with each node.
      24             : typedef uint32_t NodeId;
      25             : 
      26             : 
      27             : // Represents the result of trying to reduce a node in the graph.
      28             : class Reduction final {
      29             :  public:
      30             :   explicit Reduction(Node* replacement = nullptr) : replacement_(replacement) {}
      31             : 
      32      775359 :   Node* replacement() const { return replacement_; }
      33             :   bool Changed() const { return replacement() != nullptr; }
      34             : 
      35             :  private:
      36             :   Node* replacement_;
      37             : };
      38             : 
      39             : 
      40             : // A reducer can reduce or simplify a given node based on its operator and
      41             : // inputs. This class functions as an extension point for the graph reducer for
      42             : // language-specific reductions (e.g. reduction based on types or constant
      43             : // folding of low-level operators) can be integrated into the graph reduction
      44             : // phase.
      45    21924755 : class V8_EXPORT_PRIVATE Reducer {
      46             :  public:
      47    17316351 :   virtual ~Reducer() {}
      48             : 
      49             :   // Try to reduce a node if possible.
      50             :   virtual Reduction Reduce(Node* node) = 0;
      51             : 
      52             :   // Invoked by the {GraphReducer} when all nodes are done.  Can be used to
      53             :   // do additional reductions at the end, which in turn can cause a new round
      54             :   // of reductions.
      55             :   virtual void Finalize();
      56             : 
      57             :   // Helper functions for subclasses to produce reductions for a node.
      58             :   static Reduction NoChange() { return Reduction(); }
      59             :   static Reduction Replace(Node* node) { return Reduction(node); }
      60             :   static Reduction Changed(Node* node) { return Reduction(node); }
      61             : };
      62             : 
      63             : 
      64             : // An advanced reducer can also edit the graphs by changing and replacing nodes
      65             : // other than the one currently being reduced.
      66    13226289 : class AdvancedReducer : public Reducer {
      67             :  public:
      68             :   // Observe the actions of this reducer.
      69     3301866 :   class Editor {
      70             :    public:
      71     3301800 :     virtual ~Editor() {}
      72             : 
      73             :     // Replace {node} with {replacement}.
      74             :     virtual void Replace(Node* node, Node* replacement) = 0;
      75             :     // Revisit the {node} again later.
      76             :     virtual void Revisit(Node* node) = 0;
      77             :     // Replace value uses of {node} with {value} and effect uses of {node} with
      78             :     // {effect}. If {effect == nullptr}, then use the effect input to {node}.
      79             :     // All control uses will be relaxed assuming {node} cannot throw.
      80             :     virtual void ReplaceWithValue(Node* node, Node* value, Node* effect,
      81             :                                   Node* control) = 0;
      82             :   };
      83             : 
      84    13250916 :   explicit AdvancedReducer(Editor* editor) : editor_(editor) {}
      85             : 
      86             :  protected:
      87             :   // Helper functions for subclasses to produce reductions for a node.
      88             :   static Reduction Replace(Node* node) { return Reducer::Replace(node); }
      89             : 
      90             :   // Helper functions for subclasses to edit the graph.
      91             :   void Replace(Node* node, Node* replacement) {
      92             :     DCHECK_NOT_NULL(editor_);
      93     1955361 :     editor_->Replace(node, replacement);
      94             :   }
      95             :   void Revisit(Node* node) {
      96             :     DCHECK_NOT_NULL(editor_);
      97      607232 :     editor_->Revisit(node);
      98             :   }
      99             :   void ReplaceWithValue(Node* node, Node* value, Node* effect = nullptr,
     100             :                         Node* control = nullptr) {
     101             :     DCHECK_NOT_NULL(editor_);
     102     2216390 :     editor_->ReplaceWithValue(node, value, effect, control);
     103             :   }
     104             : 
     105             :   // Relax the effects of {node} by immediately replacing effect and control
     106             :   // uses of {node} with the effect and control input to {node}.
     107             :   // TODO(turbofan): replace the effect input to {node} with {graph->start()}.
     108      555811 :   void RelaxEffectsAndControls(Node* node) {
     109             :     ReplaceWithValue(node, node, nullptr, nullptr);
     110             :   }
     111             : 
     112             :   // Relax the control uses of {node} by immediately replacing them with the
     113             :   // control input to {node}.
     114      116550 :   void RelaxControls(Node* node) {
     115             :     ReplaceWithValue(node, node, node, nullptr);
     116             :   }
     117             : 
     118             :  private:
     119             :   Editor* const editor_;
     120             : };
     121             : 
     122             : 
     123             : // Performs an iterative reduction of a node graph.
     124             : class V8_EXPORT_PRIVATE GraphReducer
     125             :     : public NON_EXPORTED_BASE(AdvancedReducer::Editor) {
     126             :  public:
     127             :   GraphReducer(Zone* zone, Graph* graph, Node* dead = nullptr);
     128             :   ~GraphReducer();
     129             : 
     130             :   Graph* graph() const { return graph_; }
     131             : 
     132             :   void AddReducer(Reducer* reducer);
     133             : 
     134             :   // Reduce a single node.
     135             :   void ReduceNode(Node* const);
     136             :   // Reduce the whole graph.
     137             :   void ReduceGraph();
     138             : 
     139             :  private:
     140             :   enum class State : uint8_t;
     141             :   struct NodeState {
     142             :     Node* node;
     143             :     int input_index;
     144             :   };
     145             : 
     146             :   // Reduce a single node.
     147             :   Reduction Reduce(Node* const);
     148             :   // Reduce the node on top of the stack.
     149             :   void ReduceTop();
     150             : 
     151             :   // Replace {node} with {replacement}.
     152             :   void Replace(Node* node, Node* replacement) final;
     153             : 
     154             :   // Replace value uses of {node} with {value} and effect uses of {node} with
     155             :   // {effect}. If {effect == nullptr}, then use the effect input to {node}. All
     156             :   // control uses will be relaxed assuming {node} cannot throw.
     157             :   void ReplaceWithValue(Node* node, Node* value, Node* effect,
     158             :                         Node* control) final;
     159             : 
     160             :   // Replace all uses of {node} with {replacement} if the id of {replacement} is
     161             :   // less than or equal to {max_id}. Otherwise, replace all uses of {node} whose
     162             :   // id is less than or equal to {max_id} with the {replacement}.
     163             :   void Replace(Node* node, Node* replacement, NodeId max_id);
     164             : 
     165             :   // Node stack operations.
     166             :   void Pop();
     167             :   void Push(Node* node);
     168             : 
     169             :   // Revisit queue operations.
     170             :   bool Recurse(Node* node);
     171             :   void Revisit(Node* node) final;
     172             : 
     173             :   Graph* const graph_;
     174             :   Node* const dead_;
     175             :   NodeMarker<State> state_;
     176             :   ZoneVector<Reducer*> reducers_;
     177             :   ZoneStack<Node*> revisit_;
     178             :   ZoneStack<NodeState> stack_;
     179             : 
     180             :   DISALLOW_COPY_AND_ASSIGN(GraphReducer);
     181             : };
     182             : 
     183             : }  // namespace compiler
     184             : }  // namespace internal
     185             : }  // namespace v8
     186             : 
     187             : #endif  // V8_COMPILER_GRAPH_REDUCER_H_

Generated by: LCOV version 1.10