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