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 
BranchConditionBranchCondition30     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:
ControlPathConditions(BranchCondition * head,size_t condition_count)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:
PathConditionsForControlNodes(Zone * zone,size_t size_hint)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 
dead()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