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