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 #include "src/compiler/persistent-map.h" 14 15 namespace v8 { 16 namespace internal { 17 namespace compiler { 18 19 // Forward declarations. 20 class CommonOperatorBuilder; 21 class JSGraph; 22 class SourcePositionTable; 23 24 class V8_EXPORT_PRIVATE BranchElimination final NON_EXPORTED_BASE(AdvancedReducer)25 : public NON_EXPORTED_BASE(AdvancedReducer) { 26 public: 27 enum Phase { 28 kEARLY, 29 kLATE, 30 }; 31 BranchElimination(Editor* editor, JSGraph* js_graph, Zone* zone, 32 SourcePositionTable* sourse_positions, Phase phase = kLATE); 33 ~BranchElimination() final; 34 35 const char* reducer_name() const override { return "BranchElimination"; } 36 37 Reduction Reduce(Node* node) final; 38 39 private: 40 // Represents a condition along with its value in the current control path. 41 // Also stores the node that branched on this condition. 42 struct BranchCondition { 43 BranchCondition() : condition(nullptr), branch(nullptr), is_true(false) {} 44 BranchCondition(Node* condition, Node* branch, bool is_true) 45 : condition(condition), branch(branch), is_true(is_true) {} 46 Node* condition; 47 Node* branch; 48 bool is_true; 49 50 bool operator==(BranchCondition other) const { 51 return condition == other.condition && branch == other.branch && 52 is_true == other.is_true; 53 } 54 bool operator!=(BranchCondition other) const { return !(*this == other); } 55 56 bool IsSet() const { return branch != nullptr; } 57 }; 58 59 // Class for tracking information about branch conditions. It is represented 60 // as a linked list of condition blocks, each of which corresponds to a block 61 // of code bewteen an IfTrue/IfFalse and a Merge. Each block is in turn 62 // represented as a linked list of {BranchCondition}s. 63 class ControlPathConditions { 64 public: 65 explicit ControlPathConditions(Zone* zone) : conditions_(zone) {} 66 // Checks if {condition} is present in this {ControlPathConditions}. 67 bool LookupCondition(Node* condition) const; 68 // Checks if {condition} is present in this {ControlPathConditions} and 69 // copies its {branch} and {is_true} fields. 70 bool LookupCondition(Node* condition, Node** branch, bool* is_true) const; 71 // Adds a condition in the current code block, or a new block if the block 72 // list is empty. 73 void AddCondition(Zone* zone, Node* condition, Node* branch, bool is_true, 74 ControlPathConditions hint); 75 // Adds a condition in a new block. 76 void AddConditionInNewBlock(Zone* zone, Node* condition, Node* branch, 77 bool is_true); 78 // Reset this {ControlPathConditions} to the longest prefix that is common 79 // with {other}. 80 void ResetToCommonAncestor(ControlPathConditions other); 81 82 bool operator==(const ControlPathConditions& other) const { 83 return blocks_ == other.blocks_; 84 } 85 bool operator!=(const ControlPathConditions& other) const { 86 return blocks_ != other.blocks_; 87 } 88 89 friend class BranchElimination; 90 91 private: 92 FunctionalList<FunctionalList<BranchCondition>> blocks_; 93 // This is an auxilliary data structure that provides fast lookups in the 94 // set of conditions. It should hold at any point that the contents of 95 // {blocks_} and {conditions_} is the same, which is implemented in 96 // {BlocksAndConditionsInvariant}. 97 PersistentMap<Node*, BranchCondition> conditions_; 98 #if DEBUG 99 bool BlocksAndConditionsInvariant(); 100 #endif 101 }; 102 103 Reduction ReduceBranch(Node* node); 104 Reduction ReduceDeoptimizeConditional(Node* node); 105 Reduction ReduceIf(Node* node, bool is_true_branch); 106 Reduction ReduceTrapConditional(Node* node); 107 Reduction ReduceLoop(Node* node); 108 Reduction ReduceMerge(Node* node); 109 Reduction ReduceStart(Node* node); 110 Reduction ReduceOtherControl(Node* node); 111 void SimplifyBranchCondition(Node* branch); 112 bool TryPullTrapIntoMerge(Node* node); 113 114 Reduction TakeConditionsFromFirstControl(Node* node); 115 Reduction UpdateConditions(Node* node, ControlPathConditions conditions); 116 Reduction UpdateConditions(Node* node, ControlPathConditions prev_conditions, 117 Node* current_condition, Node* current_branch, 118 bool is_true_branch, bool in_new_block); 119 120 Node* dead() const { return dead_; } 121 Graph* graph() const; 122 JSGraph* jsgraph() const { return jsgraph_; } 123 Isolate* isolate() const; 124 CommonOperatorBuilder* common() const; 125 126 JSGraph* const jsgraph_; 127 128 // Maps each control node to the condition information known about the node. 129 // If the information is nullptr, then we have not calculated the information 130 // yet. 131 132 NodeAuxData<ControlPathConditions, ZoneConstruct<ControlPathConditions>> 133 node_conditions_; 134 NodeAuxData<bool> reduced_; 135 Zone* zone_; 136 SourcePositionTable* source_positions_; 137 Node* dead_; 138 Phase phase_; 139 }; 140 141 } // namespace compiler 142 } // namespace internal 143 } // namespace v8 144 145 #endif // V8_COMPILER_BRANCH_ELIMINATION_H_ 146