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