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           0 :   const char* reducer_name() const override { return "BranchElimination"; }
      27             : 
      28             :   Reduction Reduce(Node* node) final;
      29             : 
      30             :  private:
      31             :   struct BranchCondition {
      32             :     Node* condition;
      33             :     bool is_true;
      34             :     BranchCondition* next;
      35             : 
      36             :     BranchCondition(Node* condition, bool is_true, BranchCondition* next)
      37     5118499 :         : condition(condition), is_true(is_true), next(next) {}
      38             :   };
      39             : 
      40             :   // Class for tracking information about branch conditions.
      41             :   // At the moment it is a linked list of conditions and their values
      42             :   // (true or false).
      43             :   class ControlPathConditions {
      44             :    public:
      45             :     Maybe<bool> LookupCondition(Node* condition) const;
      46             : 
      47             :     const ControlPathConditions* AddCondition(Zone* zone, Node* condition,
      48             :                                               bool is_true) const;
      49             :     static const ControlPathConditions* Empty(Zone* zone);
      50             :     void Merge(const ControlPathConditions& other);
      51             : 
      52             :     bool IsSamePath(BranchCondition* first, BranchCondition* second) const;
      53             :     bool EqualsAfterAddingCondition(const ControlPathConditions* other,
      54             :                                     const Node* new_condition,
      55             :                                     bool new_branch_condition) const;
      56             :     bool operator==(const ControlPathConditions& other) const;
      57             :     bool operator!=(const ControlPathConditions& other) const {
      58      939691 :       return !(*this == other);
      59             :     }
      60             : 
      61             :    private:
      62             :     ControlPathConditions(BranchCondition* head, size_t condition_count)
      63     6891749 :         : head_(head), condition_count_(condition_count) {}
      64             : 
      65             :     BranchCondition* head_;
      66             :     // We keep track of the list length so that we can find the longest
      67             :     // common tail easily.
      68             :     size_t condition_count_;
      69             :   };
      70             : 
      71             :   // Maps each control node to the condition information known about the node.
      72             :   // If the information is nullptr, then we have not calculated the information
      73             :   // yet.
      74             :   class PathConditionsForControlNodes {
      75             :    public:
      76             :     PathConditionsForControlNodes(Zone* zone, size_t size_hint)
      77             :         : info_for_node_(size_hint, nullptr, zone) {}
      78             :     const ControlPathConditions* Get(Node* node) const;
      79             :     void Set(Node* node, const ControlPathConditions* conditions);
      80             : 
      81             :    private:
      82             :     ZoneVector<const ControlPathConditions*> info_for_node_;
      83             :   };
      84             : 
      85             :   Reduction ReduceBranch(Node* node);
      86             :   Reduction ReduceDeoptimizeConditional(Node* node);
      87             :   Reduction ReduceIf(Node* node, bool is_true_branch);
      88             :   Reduction ReduceLoop(Node* node);
      89             :   Reduction ReduceMerge(Node* node);
      90             :   Reduction ReduceStart(Node* node);
      91             :   Reduction ReduceOtherControl(Node* node);
      92             : 
      93             :   Reduction TakeConditionsFromFirstControl(Node* node);
      94             :   Reduction UpdateConditions(Node* node,
      95             :                              const ControlPathConditions* conditions);
      96             :   Reduction UpdateConditions(Node* node,
      97             :                              const ControlPathConditions* prev_conditions,
      98             :                              Node* current_condition, bool is_true_branch);
      99             : 
     100             :   Node* dead() const { return dead_; }
     101             :   Graph* graph() const;
     102             :   JSGraph* jsgraph() const { return jsgraph_; }
     103             :   CommonOperatorBuilder* common() const;
     104             : 
     105             :   JSGraph* const jsgraph_;
     106             :   PathConditionsForControlNodes node_conditions_;
     107             :   Zone* zone_;
     108             :   Node* dead_;
     109             : };
     110             : 
     111             : }  // namespace compiler
     112             : }  // namespace internal
     113             : }  // namespace v8
     114             : 
     115             : #endif  // V8_COMPILER_BRANCH_CONDITION_ELIMINATION_H_