1 // Copyright 2014 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/common-operator-reducer.h" 6 7 #include <algorithm> 8 9 #include "src/compiler/common-operator.h" 10 #include "src/compiler/graph.h" 11 #include "src/compiler/machine-operator.h" 12 #include "src/compiler/node.h" 13 #include "src/compiler/node-matchers.h" 14 #include "src/compiler/node-properties.h" 15 16 namespace v8 { 17 namespace internal { 18 namespace compiler { 19 20 namespace { 21 22 Decision DecideCondition(Node* const cond) { 23 switch (cond->opcode()) { 24 case IrOpcode::kInt32Constant: { 25 Int32Matcher mcond(cond); 26 return mcond.Value() ? Decision::kTrue : Decision::kFalse; 27 } 28 case IrOpcode::kHeapConstant: { 29 HeapObjectMatcher mcond(cond); 30 return mcond.Value()->BooleanValue() ? Decision::kTrue : Decision::kFalse; 31 } 32 default: 33 return Decision::kUnknown; 34 } 35 } 36 37 } // namespace 38 39 CommonOperatorReducer::CommonOperatorReducer(Editor* editor, Graph* graph, 40 CommonOperatorBuilder* common, 41 MachineOperatorBuilder* machine) 42 : AdvancedReducer(editor), 43 graph_(graph), 44 common_(common), 45 machine_(machine), 46 dead_(graph->NewNode(common->Dead())) { 47 NodeProperties::SetType(dead_, Type::None()); 48 } 49 50 Reduction CommonOperatorReducer::Reduce(Node* node) { 51 switch (node->opcode()) { 52 case IrOpcode::kBranch: 53 return ReduceBranch(node); 54 case IrOpcode::kDeoptimizeIf: 55 case IrOpcode::kDeoptimizeUnless: 56 return ReduceDeoptimizeConditional(node); 57 case IrOpcode::kMerge: 58 return ReduceMerge(node); 59 case IrOpcode::kEffectPhi: 60 return ReduceEffectPhi(node); 61 case IrOpcode::kPhi: 62 return ReducePhi(node); 63 case IrOpcode::kReturn: 64 return ReduceReturn(node); 65 case IrOpcode::kSelect: 66 return ReduceSelect(node); 67 default: 68 break; 69 } 70 return NoChange(); 71 } 72 73 74 Reduction CommonOperatorReducer::ReduceBranch(Node* node) { 75 DCHECK_EQ(IrOpcode::kBranch, node->opcode()); 76 Node* const cond = node->InputAt(0); 77 // Swap IfTrue/IfFalse on {branch} if {cond} is a BooleanNot and use the input 78 // to BooleanNot as new condition for {branch}. Note we assume that {cond} was 79 // already properly optimized before we get here (as guaranteed by the graph 80 // reduction logic). The same applies if {cond} is a Select acting as boolean 81 // not (i.e. true being returned in the false case and vice versa). 82 if (cond->opcode() == IrOpcode::kBooleanNot || 83 (cond->opcode() == IrOpcode::kSelect && 84 DecideCondition(cond->InputAt(1)) == Decision::kFalse && 85 DecideCondition(cond->InputAt(2)) == Decision::kTrue)) { 86 for (Node* const use : node->uses()) { 87 switch (use->opcode()) { 88 case IrOpcode::kIfTrue: 89 NodeProperties::ChangeOp(use, common()->IfFalse()); 90 break; 91 case IrOpcode::kIfFalse: 92 NodeProperties::ChangeOp(use, common()->IfTrue()); 93 break; 94 default: 95 UNREACHABLE(); 96 } 97 } 98 // Update the condition of {branch}. No need to mark the uses for revisit, 99 // since we tell the graph reducer that the {branch} was changed and the 100 // graph reduction logic will ensure that the uses are revisited properly. 101 node->ReplaceInput(0, cond->InputAt(0)); 102 // Negate the hint for {branch}. 103 NodeProperties::ChangeOp( 104 node, common()->Branch(NegateBranchHint(BranchHintOf(node->op())))); 105 return Changed(node); 106 } 107 Decision const decision = DecideCondition(cond); 108 if (decision == Decision::kUnknown) return NoChange(); 109 Node* const control = node->InputAt(1); 110 for (Node* const use : node->uses()) { 111 switch (use->opcode()) { 112 case IrOpcode::kIfTrue: 113 Replace(use, (decision == Decision::kTrue) ? control : dead()); 114 break; 115 case IrOpcode::kIfFalse: 116 Replace(use, (decision == Decision::kFalse) ? control : dead()); 117 break; 118 default: 119 UNREACHABLE(); 120 } 121 } 122 return Replace(dead()); 123 } 124 125 Reduction CommonOperatorReducer::ReduceDeoptimizeConditional(Node* node) { 126 DCHECK(node->opcode() == IrOpcode::kDeoptimizeIf || 127 node->opcode() == IrOpcode::kDeoptimizeUnless); 128 bool condition_is_true = node->opcode() == IrOpcode::kDeoptimizeUnless; 129 DeoptimizeParameters p = DeoptimizeParametersOf(node->op()); 130 Node* condition = NodeProperties::GetValueInput(node, 0); 131 Node* frame_state = NodeProperties::GetValueInput(node, 1); 132 Node* effect = NodeProperties::GetEffectInput(node); 133 Node* control = NodeProperties::GetControlInput(node); 134 // Swap DeoptimizeIf/DeoptimizeUnless on {node} if {cond} is a BooleaNot 135 // and use the input to BooleanNot as new condition for {node}. Note we 136 // assume that {cond} was already properly optimized before we get here 137 // (as guaranteed by the graph reduction logic). 138 if (condition->opcode() == IrOpcode::kBooleanNot) { 139 NodeProperties::ReplaceValueInput(node, condition->InputAt(0), 0); 140 NodeProperties::ChangeOp( 141 node, condition_is_true 142 ? common()->DeoptimizeIf(p.kind(), p.reason()) 143 : common()->DeoptimizeUnless(p.kind(), p.reason())); 144 return Changed(node); 145 } 146 Decision const decision = DecideCondition(condition); 147 if (decision == Decision::kUnknown) return NoChange(); 148 if (condition_is_true == (decision == Decision::kTrue)) { 149 ReplaceWithValue(node, dead(), effect, control); 150 } else { 151 control = graph()->NewNode(common()->Deoptimize(p.kind(), p.reason()), 152 frame_state, effect, control); 153 // TODO(bmeurer): This should be on the AdvancedReducer somehow. 154 NodeProperties::MergeControlToEnd(graph(), common(), control); 155 Revisit(graph()->end()); 156 } 157 return Replace(dead()); 158 } 159 160 Reduction CommonOperatorReducer::ReduceMerge(Node* node) { 161 DCHECK_EQ(IrOpcode::kMerge, node->opcode()); 162 // 163 // Check if this is a merge that belongs to an unused diamond, which means 164 // that: 165 // 166 // a) the {Merge} has no {Phi} or {EffectPhi} uses, and 167 // b) the {Merge} has two inputs, one {IfTrue} and one {IfFalse}, which are 168 // both owned by the Merge, and 169 // c) and the {IfTrue} and {IfFalse} nodes point to the same {Branch}. 170 // 171 if (node->InputCount() == 2) { 172 for (Node* const use : node->uses()) { 173 if (IrOpcode::IsPhiOpcode(use->opcode())) return NoChange(); 174 } 175 Node* if_true = node->InputAt(0); 176 Node* if_false = node->InputAt(1); 177 if (if_true->opcode() != IrOpcode::kIfTrue) std::swap(if_true, if_false); 178 if (if_true->opcode() == IrOpcode::kIfTrue && 179 if_false->opcode() == IrOpcode::kIfFalse && 180 if_true->InputAt(0) == if_false->InputAt(0) && if_true->OwnedBy(node) && 181 if_false->OwnedBy(node)) { 182 Node* const branch = if_true->InputAt(0); 183 DCHECK_EQ(IrOpcode::kBranch, branch->opcode()); 184 DCHECK(branch->OwnedBy(if_true, if_false)); 185 Node* const control = branch->InputAt(1); 186 // Mark the {branch} as {Dead}. 187 branch->TrimInputCount(0); 188 NodeProperties::ChangeOp(branch, common()->Dead()); 189 return Replace(control); 190 } 191 } 192 return NoChange(); 193 } 194 195 196 Reduction CommonOperatorReducer::ReduceEffectPhi(Node* node) { 197 DCHECK_EQ(IrOpcode::kEffectPhi, node->opcode()); 198 Node::Inputs inputs = node->inputs(); 199 int const effect_input_count = inputs.count() - 1; 200 DCHECK_LE(1, effect_input_count); 201 Node* const merge = inputs[effect_input_count]; 202 DCHECK(IrOpcode::IsMergeOpcode(merge->opcode())); 203 DCHECK_EQ(effect_input_count, merge->InputCount()); 204 Node* const effect = inputs[0]; 205 DCHECK_NE(node, effect); 206 for (int i = 1; i < effect_input_count; ++i) { 207 Node* const input = inputs[i]; 208 if (input == node) { 209 // Ignore redundant inputs. 210 DCHECK_EQ(IrOpcode::kLoop, merge->opcode()); 211 continue; 212 } 213 if (input != effect) return NoChange(); 214 } 215 // We might now be able to further reduce the {merge} node. 216 Revisit(merge); 217 return Replace(effect); 218 } 219 220 221 Reduction CommonOperatorReducer::ReducePhi(Node* node) { 222 DCHECK_EQ(IrOpcode::kPhi, node->opcode()); 223 Node::Inputs inputs = node->inputs(); 224 int const value_input_count = inputs.count() - 1; 225 DCHECK_LE(1, value_input_count); 226 Node* const merge = inputs[value_input_count]; 227 DCHECK(IrOpcode::IsMergeOpcode(merge->opcode())); 228 DCHECK_EQ(value_input_count, merge->InputCount()); 229 if (value_input_count == 2) { 230 Node* vtrue = inputs[0]; 231 Node* vfalse = inputs[1]; 232 Node::Inputs merge_inputs = merge->inputs(); 233 Node* if_true = merge_inputs[0]; 234 Node* if_false = merge_inputs[1]; 235 if (if_true->opcode() != IrOpcode::kIfTrue) { 236 std::swap(if_true, if_false); 237 std::swap(vtrue, vfalse); 238 } 239 if (if_true->opcode() == IrOpcode::kIfTrue && 240 if_false->opcode() == IrOpcode::kIfFalse && 241 if_true->InputAt(0) == if_false->InputAt(0)) { 242 Node* const branch = if_true->InputAt(0); 243 // Check that the branch is not dead already. 244 if (branch->opcode() != IrOpcode::kBranch) return NoChange(); 245 Node* const cond = branch->InputAt(0); 246 if (cond->opcode() == IrOpcode::kFloat32LessThan) { 247 Float32BinopMatcher mcond(cond); 248 if (mcond.left().Is(0.0) && mcond.right().Equals(vtrue) && 249 vfalse->opcode() == IrOpcode::kFloat32Sub) { 250 Float32BinopMatcher mvfalse(vfalse); 251 if (mvfalse.left().IsZero() && mvfalse.right().Equals(vtrue)) { 252 // We might now be able to further reduce the {merge} node. 253 Revisit(merge); 254 return Change(node, machine()->Float32Abs(), vtrue); 255 } 256 } 257 } else if (cond->opcode() == IrOpcode::kFloat64LessThan) { 258 Float64BinopMatcher mcond(cond); 259 if (mcond.left().Is(0.0) && mcond.right().Equals(vtrue) && 260 vfalse->opcode() == IrOpcode::kFloat64Sub) { 261 Float64BinopMatcher mvfalse(vfalse); 262 if (mvfalse.left().IsZero() && mvfalse.right().Equals(vtrue)) { 263 // We might now be able to further reduce the {merge} node. 264 Revisit(merge); 265 return Change(node, machine()->Float64Abs(), vtrue); 266 } 267 } 268 } 269 } 270 } 271 Node* const value = inputs[0]; 272 DCHECK_NE(node, value); 273 for (int i = 1; i < value_input_count; ++i) { 274 Node* const input = inputs[i]; 275 if (input == node) { 276 // Ignore redundant inputs. 277 DCHECK_EQ(IrOpcode::kLoop, merge->opcode()); 278 continue; 279 } 280 if (input != value) return NoChange(); 281 } 282 // We might now be able to further reduce the {merge} node. 283 Revisit(merge); 284 return Replace(value); 285 } 286 287 Reduction CommonOperatorReducer::ReduceReturn(Node* node) { 288 DCHECK_EQ(IrOpcode::kReturn, node->opcode()); 289 Node* effect = NodeProperties::GetEffectInput(node); 290 if (effect->opcode() == IrOpcode::kCheckpoint) { 291 // Any {Return} node can never be used to insert a deoptimization point, 292 // hence checkpoints can be cut out of the effect chain flowing into it. 293 effect = NodeProperties::GetEffectInput(effect); 294 NodeProperties::ReplaceEffectInput(node, effect); 295 Reduction const reduction = ReduceReturn(node); 296 return reduction.Changed() ? reduction : Changed(node); 297 } 298 // TODO(ahaas): Extend the reduction below to multiple return values. 299 if (ValueInputCountOfReturn(node->op()) != 1) { 300 return NoChange(); 301 } 302 Node* pop_count = NodeProperties::GetValueInput(node, 0); 303 Node* value = NodeProperties::GetValueInput(node, 1); 304 Node* control = NodeProperties::GetControlInput(node); 305 if (value->opcode() == IrOpcode::kPhi && 306 NodeProperties::GetControlInput(value) == control && 307 control->opcode() == IrOpcode::kMerge) { 308 // This optimization pushes {Return} nodes through merges. It checks that 309 // the return value is actually a {Phi} and the return control dependency 310 // is the {Merge} to which the {Phi} belongs. 311 312 // Value1 ... ValueN Control1 ... ControlN 313 // ^ ^ ^ ^ 314 // | | | | 315 // +----+-----+ +------+-----+ 316 // | | 317 // Phi --------------> Merge 318 // ^ ^ 319 // | | 320 // | +-----------------+ 321 // | | 322 // Return -----> Effect 323 // ^ 324 // | 325 // End 326 327 // Now the effect input to the {Return} node can be either an {EffectPhi} 328 // hanging off the same {Merge}, or the {Merge} node is only connected to 329 // the {Return} and the {Phi}, in which case we know that the effect input 330 // must somehow dominate all merged branches. 331 332 Node::Inputs control_inputs = control->inputs(); 333 Node::Inputs value_inputs = value->inputs(); 334 DCHECK_NE(0, control_inputs.count()); 335 DCHECK_EQ(control_inputs.count(), value_inputs.count() - 1); 336 DCHECK_EQ(IrOpcode::kEnd, graph()->end()->opcode()); 337 DCHECK_NE(0, graph()->end()->InputCount()); 338 if (control->OwnedBy(node, value)) { 339 for (int i = 0; i < control_inputs.count(); ++i) { 340 // Create a new {Return} and connect it to {end}. We don't need to mark 341 // {end} as revisit, because we mark {node} as {Dead} below, which was 342 // previously connected to {end}, so we know for sure that at some point 343 // the reducer logic will visit {end} again. 344 Node* ret = graph()->NewNode(node->op(), pop_count, value_inputs[i], 345 effect, control_inputs[i]); 346 NodeProperties::MergeControlToEnd(graph(), common(), ret); 347 } 348 // Mark the Merge {control} and Return {node} as {dead}. 349 Replace(control, dead()); 350 return Replace(dead()); 351 } else if (effect->opcode() == IrOpcode::kEffectPhi && 352 NodeProperties::GetControlInput(effect) == control) { 353 Node::Inputs effect_inputs = effect->inputs(); 354 DCHECK_EQ(control_inputs.count(), effect_inputs.count() - 1); 355 for (int i = 0; i < control_inputs.count(); ++i) { 356 // Create a new {Return} and connect it to {end}. We don't need to mark 357 // {end} as revisit, because we mark {node} as {Dead} below, which was 358 // previously connected to {end}, so we know for sure that at some point 359 // the reducer logic will visit {end} again. 360 Node* ret = graph()->NewNode(node->op(), pop_count, value_inputs[i], 361 effect_inputs[i], control_inputs[i]); 362 NodeProperties::MergeControlToEnd(graph(), common(), ret); 363 } 364 // Mark the Merge {control} and Return {node} as {dead}. 365 Replace(control, dead()); 366 return Replace(dead()); 367 } 368 } 369 return NoChange(); 370 } 371 372 Reduction CommonOperatorReducer::ReduceSelect(Node* node) { 373 DCHECK_EQ(IrOpcode::kSelect, node->opcode()); 374 Node* const cond = node->InputAt(0); 375 Node* const vtrue = node->InputAt(1); 376 Node* const vfalse = node->InputAt(2); 377 if (vtrue == vfalse) return Replace(vtrue); 378 switch (DecideCondition(cond)) { 379 case Decision::kTrue: 380 return Replace(vtrue); 381 case Decision::kFalse: 382 return Replace(vfalse); 383 case Decision::kUnknown: 384 break; 385 } 386 switch (cond->opcode()) { 387 case IrOpcode::kFloat32LessThan: { 388 Float32BinopMatcher mcond(cond); 389 if (mcond.left().Is(0.0) && mcond.right().Equals(vtrue) && 390 vfalse->opcode() == IrOpcode::kFloat32Sub) { 391 Float32BinopMatcher mvfalse(vfalse); 392 if (mvfalse.left().IsZero() && mvfalse.right().Equals(vtrue)) { 393 return Change(node, machine()->Float32Abs(), vtrue); 394 } 395 } 396 break; 397 } 398 case IrOpcode::kFloat64LessThan: { 399 Float64BinopMatcher mcond(cond); 400 if (mcond.left().Is(0.0) && mcond.right().Equals(vtrue) && 401 vfalse->opcode() == IrOpcode::kFloat64Sub) { 402 Float64BinopMatcher mvfalse(vfalse); 403 if (mvfalse.left().IsZero() && mvfalse.right().Equals(vtrue)) { 404 return Change(node, machine()->Float64Abs(), vtrue); 405 } 406 } 407 break; 408 } 409 default: 410 break; 411 } 412 return NoChange(); 413 } 414 415 416 Reduction CommonOperatorReducer::Change(Node* node, Operator const* op, 417 Node* a) { 418 node->ReplaceInput(0, a); 419 node->TrimInputCount(1); 420 NodeProperties::ChangeOp(node, op); 421 return Changed(node); 422 } 423 424 425 Reduction CommonOperatorReducer::Change(Node* node, Operator const* op, Node* a, 426 Node* b) { 427 node->ReplaceInput(0, a); 428 node->ReplaceInput(1, b); 429 node->TrimInputCount(2); 430 NodeProperties::ChangeOp(node, op); 431 return Changed(node); 432 } 433 434 } // namespace compiler 435 } // namespace internal 436 } // namespace v8 437