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 #include "src/compiler/branch-elimination.h" 6 7 #include "src/compiler/js-graph.h" 8 #include "src/compiler/node-properties.h" 9 #include "src/compiler/simplified-operator.h" 10 11 namespace v8 { 12 namespace internal { 13 namespace compiler { 14 15 BranchElimination::BranchElimination(Editor* editor, JSGraph* js_graph, 16 Zone* zone) 17 : AdvancedReducer(editor), 18 jsgraph_(js_graph), 19 node_conditions_(zone, js_graph->graph()->NodeCount()), 20 zone_(zone), 21 dead_(js_graph->graph()->NewNode(js_graph->common()->Dead())) { 22 NodeProperties::SetType(dead_, Type::None()); 23 } 24 25 BranchElimination::~BranchElimination() {} 26 27 28 Reduction BranchElimination::Reduce(Node* node) { 29 switch (node->opcode()) { 30 case IrOpcode::kDead: 31 return NoChange(); 32 case IrOpcode::kDeoptimizeIf: 33 case IrOpcode::kDeoptimizeUnless: 34 return ReduceDeoptimizeConditional(node); 35 case IrOpcode::kMerge: 36 return ReduceMerge(node); 37 case IrOpcode::kLoop: 38 return ReduceLoop(node); 39 case IrOpcode::kBranch: 40 return ReduceBranch(node); 41 case IrOpcode::kIfFalse: 42 return ReduceIf(node, false); 43 case IrOpcode::kIfTrue: 44 return ReduceIf(node, true); 45 case IrOpcode::kStart: 46 return ReduceStart(node); 47 default: 48 if (node->op()->ControlOutputCount() > 0) { 49 return ReduceOtherControl(node); 50 } 51 break; 52 } 53 return NoChange(); 54 } 55 56 57 Reduction BranchElimination::ReduceBranch(Node* node) { 58 Node* condition = node->InputAt(0); 59 Node* control_input = NodeProperties::GetControlInput(node, 0); 60 const ControlPathConditions* from_input = node_conditions_.Get(control_input); 61 if (from_input != nullptr) { 62 Maybe<bool> condition_value = from_input->LookupCondition(condition); 63 // If we know the condition we can discard the branch. 64 if (condition_value.IsJust()) { 65 bool known_value = condition_value.FromJust(); 66 for (Node* const use : node->uses()) { 67 switch (use->opcode()) { 68 case IrOpcode::kIfTrue: 69 Replace(use, known_value ? control_input : dead()); 70 break; 71 case IrOpcode::kIfFalse: 72 Replace(use, known_value ? dead() : control_input); 73 break; 74 default: 75 UNREACHABLE(); 76 } 77 } 78 return Replace(dead()); 79 } 80 } 81 return TakeConditionsFromFirstControl(node); 82 } 83 84 Reduction BranchElimination::ReduceDeoptimizeConditional(Node* node) { 85 DCHECK(node->opcode() == IrOpcode::kDeoptimizeIf || 86 node->opcode() == IrOpcode::kDeoptimizeUnless); 87 bool condition_is_true = node->opcode() == IrOpcode::kDeoptimizeUnless; 88 DeoptimizeParameters p = DeoptimizeParametersOf(node->op()); 89 Node* condition = NodeProperties::GetValueInput(node, 0); 90 Node* frame_state = NodeProperties::GetValueInput(node, 1); 91 Node* effect = NodeProperties::GetEffectInput(node); 92 Node* control = NodeProperties::GetControlInput(node); 93 ControlPathConditions const* conditions = node_conditions_.Get(control); 94 // If we do not know anything about the predecessor, do not propagate just 95 // yet because we will have to recompute anyway once we compute the 96 // predecessor. 97 if (conditions == nullptr) { 98 return UpdateConditions(node, conditions); 99 } 100 Maybe<bool> condition_value = conditions->LookupCondition(condition); 101 if (condition_value.IsJust()) { 102 // If we know the condition we can discard the branch. 103 if (condition_is_true == condition_value.FromJust()) { 104 // We don't update the conditions here, because we're replacing {node} 105 // with the {control} node that already contains the right information. 106 ReplaceWithValue(node, dead(), effect, control); 107 } else { 108 control = graph()->NewNode(common()->Deoptimize(p.kind(), p.reason()), 109 frame_state, effect, control); 110 // TODO(bmeurer): This should be on the AdvancedReducer somehow. 111 NodeProperties::MergeControlToEnd(graph(), common(), control); 112 Revisit(graph()->end()); 113 } 114 return Replace(dead()); 115 } 116 return UpdateConditions( 117 node, conditions->AddCondition(zone_, condition, condition_is_true)); 118 } 119 120 Reduction BranchElimination::ReduceIf(Node* node, bool is_true_branch) { 121 // Add the condition to the list arriving from the input branch. 122 Node* branch = NodeProperties::GetControlInput(node, 0); 123 const ControlPathConditions* from_branch = node_conditions_.Get(branch); 124 // If we do not know anything about the predecessor, do not propagate just 125 // yet because we will have to recompute anyway once we compute the 126 // predecessor. 127 if (from_branch == nullptr) { 128 return UpdateConditions(node, nullptr); 129 } 130 Node* condition = branch->InputAt(0); 131 return UpdateConditions( 132 node, from_branch->AddCondition(zone_, condition, is_true_branch)); 133 } 134 135 136 Reduction BranchElimination::ReduceLoop(Node* node) { 137 // Here we rely on having only reducible loops: 138 // The loop entry edge always dominates the header, so we can just use 139 // the information from the loop entry edge. 140 return TakeConditionsFromFirstControl(node); 141 } 142 143 144 Reduction BranchElimination::ReduceMerge(Node* node) { 145 // Shortcut for the case when we do not know anything about some 146 // input. 147 Node::Inputs inputs = node->inputs(); 148 for (Node* input : inputs) { 149 if (node_conditions_.Get(input) == nullptr) { 150 return UpdateConditions(node, nullptr); 151 } 152 } 153 154 auto input_it = inputs.begin(); 155 156 DCHECK_GT(inputs.count(), 0); 157 158 const ControlPathConditions* first = node_conditions_.Get(*input_it); 159 ++input_it; 160 // Make a copy of the first input's conditions and merge with the conditions 161 // from other inputs. 162 ControlPathConditions* conditions = 163 new (zone_->New(sizeof(ControlPathConditions))) 164 ControlPathConditions(*first); 165 auto input_end = inputs.end(); 166 for (; input_it != input_end; ++input_it) { 167 conditions->Merge(*(node_conditions_.Get(*input_it))); 168 } 169 170 return UpdateConditions(node, conditions); 171 } 172 173 174 Reduction BranchElimination::ReduceStart(Node* node) { 175 return UpdateConditions(node, ControlPathConditions::Empty(zone_)); 176 } 177 178 179 const BranchElimination::ControlPathConditions* 180 BranchElimination::PathConditionsForControlNodes::Get(Node* node) { 181 if (static_cast<size_t>(node->id()) < info_for_node_.size()) { 182 return info_for_node_[node->id()]; 183 } 184 return nullptr; 185 } 186 187 188 void BranchElimination::PathConditionsForControlNodes::Set( 189 Node* node, const ControlPathConditions* conditions) { 190 size_t index = static_cast<size_t>(node->id()); 191 if (index >= info_for_node_.size()) { 192 info_for_node_.resize(index + 1, nullptr); 193 } 194 info_for_node_[index] = conditions; 195 } 196 197 198 Reduction BranchElimination::ReduceOtherControl(Node* node) { 199 DCHECK_EQ(1, node->op()->ControlInputCount()); 200 return TakeConditionsFromFirstControl(node); 201 } 202 203 204 Reduction BranchElimination::TakeConditionsFromFirstControl(Node* node) { 205 // We just propagate the information from the control input (ideally, 206 // we would only revisit control uses if there is change). 207 const ControlPathConditions* from_input = 208 node_conditions_.Get(NodeProperties::GetControlInput(node, 0)); 209 return UpdateConditions(node, from_input); 210 } 211 212 213 Reduction BranchElimination::UpdateConditions( 214 Node* node, const ControlPathConditions* conditions) { 215 const ControlPathConditions* original = node_conditions_.Get(node); 216 // Only signal that the node has Changed if the condition information has 217 // changed. 218 if (conditions != original) { 219 if (conditions == nullptr || original == nullptr || 220 *conditions != *original) { 221 node_conditions_.Set(node, conditions); 222 return Changed(node); 223 } 224 } 225 return NoChange(); 226 } 227 228 229 // static 230 const BranchElimination::ControlPathConditions* 231 BranchElimination::ControlPathConditions::Empty(Zone* zone) { 232 return new (zone->New(sizeof(ControlPathConditions))) 233 ControlPathConditions(nullptr, 0); 234 } 235 236 237 void BranchElimination::ControlPathConditions::Merge( 238 const ControlPathConditions& other) { 239 // Change the current condition list to a longest common tail 240 // of this condition list and the other list. (The common tail 241 // should correspond to the list from the common dominator.) 242 243 // First, we throw away the prefix of the longer list, so that 244 // we have lists of the same length. 245 size_t other_size = other.condition_count_; 246 BranchCondition* other_condition = other.head_; 247 while (other_size > condition_count_) { 248 other_condition = other_condition->next; 249 other_size--; 250 } 251 while (condition_count_ > other_size) { 252 head_ = head_->next; 253 condition_count_--; 254 } 255 256 // Then we go through both lists in lock-step until we find 257 // the common tail. 258 while (head_ != other_condition) { 259 DCHECK(condition_count_ > 0); 260 condition_count_--; 261 other_condition = other_condition->next; 262 head_ = head_->next; 263 } 264 } 265 266 267 const BranchElimination::ControlPathConditions* 268 BranchElimination::ControlPathConditions::AddCondition(Zone* zone, 269 Node* condition, 270 bool is_true) const { 271 DCHECK(LookupCondition(condition).IsNothing()); 272 273 BranchCondition* new_head = new (zone->New(sizeof(BranchCondition))) 274 BranchCondition(condition, is_true, head_); 275 276 ControlPathConditions* conditions = 277 new (zone->New(sizeof(ControlPathConditions))) 278 ControlPathConditions(new_head, condition_count_ + 1); 279 return conditions; 280 } 281 282 283 Maybe<bool> BranchElimination::ControlPathConditions::LookupCondition( 284 Node* condition) const { 285 for (BranchCondition* current = head_; current != nullptr; 286 current = current->next) { 287 if (current->condition == condition) { 288 return Just<bool>(current->is_true); 289 } 290 } 291 return Nothing<bool>(); 292 } 293 294 295 bool BranchElimination::ControlPathConditions::operator==( 296 const ControlPathConditions& other) const { 297 if (condition_count_ != other.condition_count_) return false; 298 BranchCondition* this_condition = head_; 299 BranchCondition* other_condition = other.head_; 300 while (true) { 301 if (this_condition == other_condition) return true; 302 if (this_condition->condition != other_condition->condition || 303 this_condition->is_true != other_condition->is_true) { 304 return false; 305 } 306 this_condition = this_condition->next; 307 other_condition = other_condition->next; 308 } 309 UNREACHABLE(); 310 return false; 311 } 312 313 Graph* BranchElimination::graph() const { return jsgraph()->graph(); } 314 315 CommonOperatorBuilder* BranchElimination::common() const { 316 return jsgraph()->common(); 317 } 318 319 } // namespace compiler 320 } // namespace internal 321 } // namespace v8 322