Line data    Source code

       1             : // Copyright 2015 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_BRANCH_CONDITION_ELIMINATION_H_
       6             : #define V8_COMPILER_BRANCH_CONDITION_ELIMINATION_H_
       7             : 
       8             : #include "src/base/compiler-specific.h"
       9             : #include "src/compiler/graph-reducer.h"
      10             : #include "src/globals.h"
      11             : 
      12             : namespace v8 {
      13             : namespace internal {
      14             : namespace compiler {
      15             : 
      16             : // Forward declarations.
      17             : class CommonOperatorBuilder;
      18             : class JSGraph;
      19             : 
      20             : class V8_EXPORT_PRIVATE BranchElimination final
      21             :     : public NON_EXPORTED_BASE(AdvancedReducer) {
      22             :  public:
      23             :   BranchElimination(Editor* editor, JSGraph* js_graph, Zone* zone);
      24             :   ~BranchElimination() final;
      25             : 
      26             :   Reduction Reduce(Node* node) final;
      27             : 
      28             :  private:
      29             :   struct BranchCondition {
      30             :     Node* condition;
      31             :     bool is_true;
      32             :     BranchCondition* next;
      33             : 
      34             :     BranchCondition(Node* condition, bool is_true, BranchCondition* next)
      35     5829630 :         : condition(condition), is_true(is_true), next(next) {}
      36             :   };
      37             : 
      38             :   // Class for tracking information about branch conditions.
      39             :   // At the moment it is a linked list of conditions and their values
      40             :   // (true or false).
      41             :   class ControlPathConditions {
      42             :    public:
      43             :     Maybe<bool> LookupCondition(Node* condition) const;
      44             : 
      45             :     const ControlPathConditions* AddCondition(Zone* zone, Node* condition,
      46             :                                               bool is_true) const;
      47             :     static const ControlPathConditions* Empty(Zone* zone);
      48             :     void Merge(const ControlPathConditions& other);
      49             : 
      50             :     bool operator==(const ControlPathConditions& other) const;
      51             :     bool operator!=(const ControlPathConditions& other) const {
      52      863553 :       return !(*this == other);
      53             :     }
      54             : 
      55             :    private:
      56             :     ControlPathConditions(BranchCondition* head, size_t condition_count)
      57     7404398 :         : head_(head), condition_count_(condition_count) {}
      58             : 
      59             :     BranchCondition* head_;
      60             :     // We keep track of the list length so that we can find the longest
      61             :     // common tail easily.
      62             :     size_t condition_count_;
      63             :   };
      64             : 
      65             :   // Maps each control node to the condition information known about the node.
      66             :   // If the information is nullptr, then we have not calculated the information
      67             :   // yet.
      68             :   class PathConditionsForControlNodes {
      69             :    public:
      70             :     PathConditionsForControlNodes(Zone* zone, size_t size_hint)
      71             :         : info_for_node_(size_hint, nullptr, zone) {}
      72             :     const ControlPathConditions* Get(Node* node) const;
      73             :     void Set(Node* node, const ControlPathConditions* conditions);
      74             : 
      75             :    private:
      76             :     ZoneVector<const ControlPathConditions*> info_for_node_;
      77             :   };
      78             : 
      79             :   Reduction ReduceBranch(Node* node);
      80             :   Reduction ReduceDeoptimizeConditional(Node* node);
      81             :   Reduction ReduceIf(Node* node, bool is_true_branch);
      82             :   Reduction ReduceLoop(Node* node);
      83             :   Reduction ReduceMerge(Node* node);
      84             :   Reduction ReduceStart(Node* node);
      85             :   Reduction ReduceOtherControl(Node* node);
      86             : 
      87             :   Reduction TakeConditionsFromFirstControl(Node* node);
      88             :   Reduction UpdateConditions(Node* node,
      89             :                              const ControlPathConditions* conditions);
      90             : 
      91             :   Node* dead() const { return dead_; }
      92             :   Graph* graph() const;
      93             :   JSGraph* jsgraph() const { return jsgraph_; }
      94             :   CommonOperatorBuilder* common() const;
      95             : 
      96             :   JSGraph* const jsgraph_;
      97             :   PathConditionsForControlNodes node_conditions_;
      98             :   Zone* zone_;
      99             :   Node* dead_;
     100             : };
     101             : 
     102             : }  // namespace compiler
     103             : }  // namespace internal
     104             : }  // namespace v8
     105             : 
     106             : #endif  // V8_COMPILER_BRANCH_CONDITION_ELIMINATION_H_