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 NON_EXPORTED_BASE(AdvancedReducer)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