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/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         : 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       return !(*this == other);
     53     }
     54 
     55    private:
     56     ControlPathConditions(BranchCondition* head, size_t condition_count)
     57         : 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);
     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_
    107