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 BranchConditionBranchCondition32 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: ControlPathConditions(BranchCondition * head,size_t condition_count)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: PathConditionsForControlNodes(Zone * zone,size_t size_hint)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 dead()89 Node* dead() const { return dead_; } 90 Graph* graph() const; jsgraph()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