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