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_ELIMINATION_H_
       6             : #define V8_COMPILER_BRANCH_ELIMINATION_H_
       7             : 
       8             : #include "src/base/compiler-specific.h"
       9             : #include "src/compiler/functional-list.h"
      10             : #include "src/compiler/graph-reducer.h"
      11             : #include "src/compiler/node-aux-data.h"
      12             : #include "src/globals.h"
      13             : 
      14             : namespace v8 {
      15             : namespace internal {
      16             : namespace compiler {
      17             : 
      18             : // Forward declarations.
      19             : class CommonOperatorBuilder;
      20             : class JSGraph;
      21             : 
      22     1991172 : class V8_EXPORT_PRIVATE BranchElimination final
      23             :     : public NON_EXPORTED_BASE(AdvancedReducer) {
      24             :  public:
      25             :   BranchElimination(Editor* editor, JSGraph* js_graph, Zone* zone);
      26             :   ~BranchElimination() final;
      27             : 
      28          71 :   const char* reducer_name() const override { return "BranchElimination"; }
      29             : 
      30             :   Reduction Reduce(Node* node) final;
      31             : 
      32             :  private:
      33             :   struct BranchCondition {
      34             :     Node* condition;
      35             :     Node* branch;
      36             :     bool is_true;
      37             : 
      38             :     bool operator==(BranchCondition other) const {
      39         516 :       return condition == other.condition && branch == other.branch &&
      40         199 :              is_true == other.is_true;
      41             :     }
      42         279 :     bool operator!=(BranchCondition other) const { return !(*this == other); }
      43             :   };
      44             : 
      45             :   // Class for tracking information about branch conditions.
      46             :   // At the moment it is a linked list of conditions and their values
      47             :   // (true or false).
      48             :   class ControlPathConditions : public FunctionalList<BranchCondition> {
      49             :    public:
      50             :     bool LookupCondition(Node* condition, Node** branch, bool* is_true) const;
      51             :     void AddCondition(Zone* zone, Node* condition, Node* branch, bool is_true,
      52             :                       ControlPathConditions hint);
      53             : 
      54             :    private:
      55             :     using FunctionalList<BranchCondition>::PushFront;
      56             :   };
      57             : 
      58             :   Reduction ReduceBranch(Node* node);
      59             :   Reduction ReduceDeoptimizeConditional(Node* node);
      60             :   Reduction ReduceIf(Node* node, bool is_true_branch);
      61             :   Reduction ReduceLoop(Node* node);
      62             :   Reduction ReduceMerge(Node* node);
      63             :   Reduction ReduceStart(Node* node);
      64             :   Reduction ReduceOtherControl(Node* node);
      65             : 
      66             :   Reduction TakeConditionsFromFirstControl(Node* node);
      67             :   Reduction UpdateConditions(Node* node, ControlPathConditions conditions);
      68             :   Reduction UpdateConditions(Node* node, ControlPathConditions prev_conditions,
      69             :                              Node* current_condition, Node* current_branch,
      70             :                              bool is_true_branch);
      71             : 
      72             :   Node* dead() const { return dead_; }
      73             :   Graph* graph() const;
      74             :   JSGraph* jsgraph() const { return jsgraph_; }
      75             :   Isolate* isolate() const;
      76             :   CommonOperatorBuilder* common() const;
      77             : 
      78             :   JSGraph* const jsgraph_;
      79             : 
      80             :   // Maps each control node to the condition information known about the node.
      81             :   // If the information is nullptr, then we have not calculated the information
      82             :   // yet.
      83             :   NodeAuxData<ControlPathConditions> node_conditions_;
      84             :   NodeAuxData<bool> reduced_;
      85             :   Zone* zone_;
      86             :   Node* dead_;
      87             : };
      88             : 
      89             : }  // namespace compiler
      90             : }  // namespace internal
      91             : }  // namespace v8
      92             : 
      93             : #endif  // V8_COMPILER_BRANCH_ELIMINATION_H_