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_ELIMINATION_H_ 6 #define V8_COMPILER_BRANCH_ELIMINATION_H_ 7 8 #include "src/base/compiler-specific.h" 9 #include "src/common/globals.h" 10 #include "src/compiler/functional-list.h" 11 #include "src/compiler/graph-reducer.h" 12 #include "src/compiler/node-aux-data.h" 13 14 namespace v8 { 15 namespace internal { 16 namespace compiler { 17 18 // Forward declarations. 19 class CommonOperatorBuilder; 20 class JSGraph; 21 22 class V8_EXPORT_PRIVATE BranchElimination final NON_EXPORTED_BASE(AdvancedReducer)23 : public NON_EXPORTED_BASE(AdvancedReducer) { 24 public: 25 enum Phase { 26 kEARLY, 27 kLATE, 28 }; 29 BranchElimination(Editor* editor, JSGraph* js_graph, Zone* zone, 30 Phase phase = kLATE); 31 ~BranchElimination() final; 32 33 const char* reducer_name() const override { return "BranchElimination"; } 34 35 Reduction Reduce(Node* node) final; 36 37 private: 38 struct BranchCondition { 39 Node* condition; 40 Node* branch; 41 bool is_true; 42 43 bool operator==(BranchCondition other) const { 44 return condition == other.condition && branch == other.branch && 45 is_true == other.is_true; 46 } 47 bool operator!=(BranchCondition other) const { return !(*this == other); } 48 }; 49 50 // Class for tracking information about branch conditions. 51 // At the moment it is a linked list of conditions and their values 52 // (true or false). 53 class ControlPathConditions : public FunctionalList<BranchCondition> { 54 public: 55 bool LookupCondition(Node* condition, Node** branch, bool* is_true) const; 56 void AddCondition(Zone* zone, Node* condition, Node* branch, bool is_true, 57 ControlPathConditions hint); 58 59 private: 60 using FunctionalList<BranchCondition>::PushFront; 61 }; 62 63 Reduction ReduceBranch(Node* node); 64 Reduction ReduceDeoptimizeConditional(Node* node); 65 Reduction ReduceIf(Node* node, bool is_true_branch); 66 Reduction ReduceLoop(Node* node); 67 Reduction ReduceMerge(Node* node); 68 Reduction ReduceStart(Node* node); 69 Reduction ReduceOtherControl(Node* node); 70 void SimplifyBranchCondition(Node* branch); 71 72 Reduction TakeConditionsFromFirstControl(Node* node); 73 Reduction UpdateConditions(Node* node, ControlPathConditions conditions); 74 Reduction UpdateConditions(Node* node, ControlPathConditions prev_conditions, 75 Node* current_condition, Node* current_branch, 76 bool is_true_branch); 77 void MarkAsSafetyCheckIfNeeded(Node* branch, Node* node); 78 79 Node* dead() const { return dead_; } 80 Graph* graph() const; 81 JSGraph* jsgraph() const { return jsgraph_; } 82 Isolate* isolate() const; 83 CommonOperatorBuilder* common() const; 84 85 JSGraph* const jsgraph_; 86 87 // Maps each control node to the condition information known about the node. 88 // If the information is nullptr, then we have not calculated the information 89 // yet. 90 NodeAuxData<ControlPathConditions> node_conditions_; 91 NodeAuxData<bool> reduced_; 92 Zone* zone_; 93 Node* dead_; 94 Phase phase_; 95 }; 96 97 } // namespace compiler 98 } // namespace internal 99 } // namespace v8 100 101 #endif // V8_COMPILER_BRANCH_ELIMINATION_H_ 102