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/machine-operator-reducer.h" 6 7 #include "src/base/bits.h" 8 #include "src/base/division-by-constant.h" 9 #include "src/codegen.h" 10 #include "src/compiler/diamond.h" 11 #include "src/compiler/graph.h" 12 #include "src/compiler/js-graph.h" 13 #include "src/compiler/node-matchers.h" 14 15 namespace v8 { 16 namespace internal { 17 namespace compiler { 18 19 MachineOperatorReducer::MachineOperatorReducer(JSGraph* jsgraph) 20 : jsgraph_(jsgraph) {} 21 22 23 MachineOperatorReducer::~MachineOperatorReducer() {} 24 25 26 Node* MachineOperatorReducer::Float32Constant(volatile float value) { 27 return graph()->NewNode(common()->Float32Constant(value)); 28 } 29 30 31 Node* MachineOperatorReducer::Float64Constant(volatile double value) { 32 return jsgraph()->Float64Constant(value); 33 } 34 35 36 Node* MachineOperatorReducer::Int32Constant(int32_t value) { 37 return jsgraph()->Int32Constant(value); 38 } 39 40 41 Node* MachineOperatorReducer::Int64Constant(int64_t value) { 42 return graph()->NewNode(common()->Int64Constant(value)); 43 } 44 45 46 Node* MachineOperatorReducer::Word32And(Node* lhs, Node* rhs) { 47 Node* const node = graph()->NewNode(machine()->Word32And(), lhs, rhs); 48 Reduction const reduction = ReduceWord32And(node); 49 return reduction.Changed() ? reduction.replacement() : node; 50 } 51 52 53 Node* MachineOperatorReducer::Word32Sar(Node* lhs, uint32_t rhs) { 54 if (rhs == 0) return lhs; 55 return graph()->NewNode(machine()->Word32Sar(), lhs, Uint32Constant(rhs)); 56 } 57 58 59 Node* MachineOperatorReducer::Word32Shr(Node* lhs, uint32_t rhs) { 60 if (rhs == 0) return lhs; 61 return graph()->NewNode(machine()->Word32Shr(), lhs, Uint32Constant(rhs)); 62 } 63 64 65 Node* MachineOperatorReducer::Word32Equal(Node* lhs, Node* rhs) { 66 return graph()->NewNode(machine()->Word32Equal(), lhs, rhs); 67 } 68 69 70 Node* MachineOperatorReducer::Int32Add(Node* lhs, Node* rhs) { 71 Node* const node = graph()->NewNode(machine()->Int32Add(), lhs, rhs); 72 Reduction const reduction = ReduceInt32Add(node); 73 return reduction.Changed() ? reduction.replacement() : node; 74 } 75 76 77 Node* MachineOperatorReducer::Int32Sub(Node* lhs, Node* rhs) { 78 Node* const node = graph()->NewNode(machine()->Int32Sub(), lhs, rhs); 79 Reduction const reduction = ReduceInt32Sub(node); 80 return reduction.Changed() ? reduction.replacement() : node; 81 } 82 83 84 Node* MachineOperatorReducer::Int32Mul(Node* lhs, Node* rhs) { 85 return graph()->NewNode(machine()->Int32Mul(), lhs, rhs); 86 } 87 88 89 Node* MachineOperatorReducer::Int32Div(Node* dividend, int32_t divisor) { 90 DCHECK_NE(0, divisor); 91 DCHECK_NE(std::numeric_limits<int32_t>::min(), divisor); 92 base::MagicNumbersForDivision<uint32_t> const mag = 93 base::SignedDivisionByConstant(bit_cast<uint32_t>(divisor)); 94 Node* quotient = graph()->NewNode(machine()->Int32MulHigh(), dividend, 95 Uint32Constant(mag.multiplier)); 96 if (divisor > 0 && bit_cast<int32_t>(mag.multiplier) < 0) { 97 quotient = Int32Add(quotient, dividend); 98 } else if (divisor < 0 && bit_cast<int32_t>(mag.multiplier) > 0) { 99 quotient = Int32Sub(quotient, dividend); 100 } 101 return Int32Add(Word32Sar(quotient, mag.shift), Word32Shr(dividend, 31)); 102 } 103 104 105 Node* MachineOperatorReducer::Uint32Div(Node* dividend, uint32_t divisor) { 106 DCHECK_LT(0u, divisor); 107 // If the divisor is even, we can avoid using the expensive fixup by shifting 108 // the dividend upfront. 109 unsigned const shift = base::bits::CountTrailingZeros32(divisor); 110 dividend = Word32Shr(dividend, shift); 111 divisor >>= shift; 112 // Compute the magic number for the (shifted) divisor. 113 base::MagicNumbersForDivision<uint32_t> const mag = 114 base::UnsignedDivisionByConstant(divisor, shift); 115 Node* quotient = graph()->NewNode(machine()->Uint32MulHigh(), dividend, 116 Uint32Constant(mag.multiplier)); 117 if (mag.add) { 118 DCHECK_LE(1u, mag.shift); 119 quotient = Word32Shr( 120 Int32Add(Word32Shr(Int32Sub(dividend, quotient), 1), quotient), 121 mag.shift - 1); 122 } else { 123 quotient = Word32Shr(quotient, mag.shift); 124 } 125 return quotient; 126 } 127 128 129 // Perform constant folding and strength reduction on machine operators. 130 Reduction MachineOperatorReducer::Reduce(Node* node) { 131 switch (node->opcode()) { 132 case IrOpcode::kProjection: 133 return ReduceProjection(ProjectionIndexOf(node->op()), node->InputAt(0)); 134 case IrOpcode::kWord32And: 135 return ReduceWord32And(node); 136 case IrOpcode::kWord32Or: 137 return ReduceWord32Or(node); 138 case IrOpcode::kWord32Xor: { 139 Int32BinopMatcher m(node); 140 if (m.right().Is(0)) return Replace(m.left().node()); // x ^ 0 => x 141 if (m.IsFoldable()) { // K ^ K => K 142 return ReplaceInt32(m.left().Value() ^ m.right().Value()); 143 } 144 if (m.LeftEqualsRight()) return ReplaceInt32(0); // x ^ x => 0 145 if (m.left().IsWord32Xor() && m.right().Is(-1)) { 146 Int32BinopMatcher mleft(m.left().node()); 147 if (mleft.right().Is(-1)) { // (x ^ -1) ^ -1 => x 148 return Replace(mleft.left().node()); 149 } 150 } 151 break; 152 } 153 case IrOpcode::kWord32Shl: 154 return ReduceWord32Shl(node); 155 case IrOpcode::kWord32Shr: { 156 Uint32BinopMatcher m(node); 157 if (m.right().Is(0)) return Replace(m.left().node()); // x >>> 0 => x 158 if (m.IsFoldable()) { // K >>> K => K 159 return ReplaceInt32(m.left().Value() >> m.right().Value()); 160 } 161 return ReduceWord32Shifts(node); 162 } 163 case IrOpcode::kWord32Sar: 164 return ReduceWord32Sar(node); 165 case IrOpcode::kWord32Ror: { 166 Int32BinopMatcher m(node); 167 if (m.right().Is(0)) return Replace(m.left().node()); // x ror 0 => x 168 if (m.IsFoldable()) { // K ror K => K 169 return ReplaceInt32( 170 base::bits::RotateRight32(m.left().Value(), m.right().Value())); 171 } 172 break; 173 } 174 case IrOpcode::kWord32Equal: { 175 Int32BinopMatcher m(node); 176 if (m.IsFoldable()) { // K == K => K 177 return ReplaceBool(m.left().Value() == m.right().Value()); 178 } 179 if (m.left().IsInt32Sub() && m.right().Is(0)) { // x - y == 0 => x == y 180 Int32BinopMatcher msub(m.left().node()); 181 node->ReplaceInput(0, msub.left().node()); 182 node->ReplaceInput(1, msub.right().node()); 183 return Changed(node); 184 } 185 // TODO(turbofan): fold HeapConstant, ExternalReference, pointer compares 186 if (m.LeftEqualsRight()) return ReplaceBool(true); // x == x => true 187 break; 188 } 189 case IrOpcode::kWord64Equal: { 190 Int64BinopMatcher m(node); 191 if (m.IsFoldable()) { // K == K => K 192 return ReplaceBool(m.left().Value() == m.right().Value()); 193 } 194 if (m.left().IsInt64Sub() && m.right().Is(0)) { // x - y == 0 => x == y 195 Int64BinopMatcher msub(m.left().node()); 196 node->ReplaceInput(0, msub.left().node()); 197 node->ReplaceInput(1, msub.right().node()); 198 return Changed(node); 199 } 200 // TODO(turbofan): fold HeapConstant, ExternalReference, pointer compares 201 if (m.LeftEqualsRight()) return ReplaceBool(true); // x == x => true 202 break; 203 } 204 case IrOpcode::kInt32Add: 205 return ReduceInt32Add(node); 206 case IrOpcode::kInt32Sub: 207 return ReduceInt32Sub(node); 208 case IrOpcode::kInt32Mul: { 209 Int32BinopMatcher m(node); 210 if (m.right().Is(0)) return Replace(m.right().node()); // x * 0 => 0 211 if (m.right().Is(1)) return Replace(m.left().node()); // x * 1 => x 212 if (m.IsFoldable()) { // K * K => K 213 return ReplaceInt32(m.left().Value() * m.right().Value()); 214 } 215 if (m.right().Is(-1)) { // x * -1 => 0 - x 216 node->ReplaceInput(0, Int32Constant(0)); 217 node->ReplaceInput(1, m.left().node()); 218 NodeProperties::ChangeOp(node, machine()->Int32Sub()); 219 return Changed(node); 220 } 221 if (m.right().IsPowerOf2()) { // x * 2^n => x << n 222 node->ReplaceInput(1, Int32Constant(WhichPowerOf2(m.right().Value()))); 223 NodeProperties::ChangeOp(node, machine()->Word32Shl()); 224 Reduction reduction = ReduceWord32Shl(node); 225 return reduction.Changed() ? reduction : Changed(node); 226 } 227 break; 228 } 229 case IrOpcode::kInt32Div: 230 return ReduceInt32Div(node); 231 case IrOpcode::kUint32Div: 232 return ReduceUint32Div(node); 233 case IrOpcode::kInt32Mod: 234 return ReduceInt32Mod(node); 235 case IrOpcode::kUint32Mod: 236 return ReduceUint32Mod(node); 237 case IrOpcode::kInt32LessThan: { 238 Int32BinopMatcher m(node); 239 if (m.IsFoldable()) { // K < K => K 240 return ReplaceBool(m.left().Value() < m.right().Value()); 241 } 242 if (m.left().IsInt32Sub() && m.right().Is(0)) { // x - y < 0 => x < y 243 Int32BinopMatcher msub(m.left().node()); 244 node->ReplaceInput(0, msub.left().node()); 245 node->ReplaceInput(1, msub.right().node()); 246 return Changed(node); 247 } 248 if (m.left().Is(0) && m.right().IsInt32Sub()) { // 0 < x - y => y < x 249 Int32BinopMatcher msub(m.right().node()); 250 node->ReplaceInput(0, msub.right().node()); 251 node->ReplaceInput(1, msub.left().node()); 252 return Changed(node); 253 } 254 if (m.LeftEqualsRight()) return ReplaceBool(false); // x < x => false 255 break; 256 } 257 case IrOpcode::kInt32LessThanOrEqual: { 258 Int32BinopMatcher m(node); 259 if (m.IsFoldable()) { // K <= K => K 260 return ReplaceBool(m.left().Value() <= m.right().Value()); 261 } 262 if (m.left().IsInt32Sub() && m.right().Is(0)) { // x - y <= 0 => x <= y 263 Int32BinopMatcher msub(m.left().node()); 264 node->ReplaceInput(0, msub.left().node()); 265 node->ReplaceInput(1, msub.right().node()); 266 return Changed(node); 267 } 268 if (m.left().Is(0) && m.right().IsInt32Sub()) { // 0 <= x - y => y <= x 269 Int32BinopMatcher msub(m.right().node()); 270 node->ReplaceInput(0, msub.right().node()); 271 node->ReplaceInput(1, msub.left().node()); 272 return Changed(node); 273 } 274 if (m.LeftEqualsRight()) return ReplaceBool(true); // x <= x => true 275 break; 276 } 277 case IrOpcode::kUint32LessThan: { 278 Uint32BinopMatcher m(node); 279 if (m.left().Is(kMaxUInt32)) return ReplaceBool(false); // M < x => false 280 if (m.right().Is(0)) return ReplaceBool(false); // x < 0 => false 281 if (m.IsFoldable()) { // K < K => K 282 return ReplaceBool(m.left().Value() < m.right().Value()); 283 } 284 if (m.LeftEqualsRight()) return ReplaceBool(false); // x < x => false 285 if (m.left().IsWord32Sar() && m.right().HasValue()) { 286 Int32BinopMatcher mleft(m.left().node()); 287 if (mleft.right().HasValue()) { 288 // (x >> K) < C => x < (C << K) 289 // when C < (M >> K) 290 const uint32_t c = m.right().Value(); 291 const uint32_t k = mleft.right().Value() & 0x1f; 292 if (c < static_cast<uint32_t>(kMaxInt >> k)) { 293 node->ReplaceInput(0, mleft.left().node()); 294 node->ReplaceInput(1, Uint32Constant(c << k)); 295 return Changed(node); 296 } 297 // TODO(turbofan): else the comparison is always true. 298 } 299 } 300 break; 301 } 302 case IrOpcode::kUint32LessThanOrEqual: { 303 Uint32BinopMatcher m(node); 304 if (m.left().Is(0)) return ReplaceBool(true); // 0 <= x => true 305 if (m.right().Is(kMaxUInt32)) return ReplaceBool(true); // x <= M => true 306 if (m.IsFoldable()) { // K <= K => K 307 return ReplaceBool(m.left().Value() <= m.right().Value()); 308 } 309 if (m.LeftEqualsRight()) return ReplaceBool(true); // x <= x => true 310 break; 311 } 312 case IrOpcode::kFloat64Add: { 313 Float64BinopMatcher m(node); 314 if (m.right().IsNaN()) { // x + NaN => NaN 315 return Replace(m.right().node()); 316 } 317 if (m.IsFoldable()) { // K + K => K 318 return ReplaceFloat64(m.left().Value() + m.right().Value()); 319 } 320 break; 321 } 322 case IrOpcode::kFloat64Sub: { 323 Float64BinopMatcher m(node); 324 if (m.right().Is(0) && (Double(m.right().Value()).Sign() > 0)) { 325 return Replace(m.left().node()); // x - 0 => x 326 } 327 if (m.right().IsNaN()) { // x - NaN => NaN 328 return Replace(m.right().node()); 329 } 330 if (m.left().IsNaN()) { // NaN - x => NaN 331 return Replace(m.left().node()); 332 } 333 if (m.IsFoldable()) { // K - K => K 334 return ReplaceFloat64(m.left().Value() - m.right().Value()); 335 } 336 break; 337 } 338 case IrOpcode::kFloat64Mul: { 339 Float64BinopMatcher m(node); 340 if (m.right().Is(-1)) { // x * -1.0 => -0.0 - x 341 node->ReplaceInput(0, Float64Constant(-0.0)); 342 node->ReplaceInput(1, m.left().node()); 343 NodeProperties::ChangeOp(node, machine()->Float64Sub()); 344 return Changed(node); 345 } 346 if (m.right().Is(1)) return Replace(m.left().node()); // x * 1.0 => x 347 if (m.right().IsNaN()) { // x * NaN => NaN 348 return Replace(m.right().node()); 349 } 350 if (m.IsFoldable()) { // K * K => K 351 return ReplaceFloat64(m.left().Value() * m.right().Value()); 352 } 353 break; 354 } 355 case IrOpcode::kFloat64Div: { 356 Float64BinopMatcher m(node); 357 if (m.right().Is(1)) return Replace(m.left().node()); // x / 1.0 => x 358 if (m.right().IsNaN()) { // x / NaN => NaN 359 return Replace(m.right().node()); 360 } 361 if (m.left().IsNaN()) { // NaN / x => NaN 362 return Replace(m.left().node()); 363 } 364 if (m.IsFoldable()) { // K / K => K 365 return ReplaceFloat64(m.left().Value() / m.right().Value()); 366 } 367 break; 368 } 369 case IrOpcode::kFloat64Mod: { 370 Float64BinopMatcher m(node); 371 if (m.right().Is(0)) { // x % 0 => NaN 372 return ReplaceFloat64(std::numeric_limits<double>::quiet_NaN()); 373 } 374 if (m.right().IsNaN()) { // x % NaN => NaN 375 return Replace(m.right().node()); 376 } 377 if (m.left().IsNaN()) { // NaN % x => NaN 378 return Replace(m.left().node()); 379 } 380 if (m.IsFoldable()) { // K % K => K 381 return ReplaceFloat64(modulo(m.left().Value(), m.right().Value())); 382 } 383 break; 384 } 385 case IrOpcode::kChangeFloat32ToFloat64: { 386 Float32Matcher m(node->InputAt(0)); 387 if (m.HasValue()) return ReplaceFloat64(m.Value()); 388 break; 389 } 390 case IrOpcode::kChangeFloat64ToInt32: { 391 Float64Matcher m(node->InputAt(0)); 392 if (m.HasValue()) return ReplaceInt32(FastD2I(m.Value())); 393 if (m.IsChangeInt32ToFloat64()) return Replace(m.node()->InputAt(0)); 394 break; 395 } 396 case IrOpcode::kChangeFloat64ToUint32: { 397 Float64Matcher m(node->InputAt(0)); 398 if (m.HasValue()) return ReplaceInt32(FastD2UI(m.Value())); 399 if (m.IsChangeUint32ToFloat64()) return Replace(m.node()->InputAt(0)); 400 break; 401 } 402 case IrOpcode::kChangeInt32ToFloat64: { 403 Int32Matcher m(node->InputAt(0)); 404 if (m.HasValue()) return ReplaceFloat64(FastI2D(m.Value())); 405 break; 406 } 407 case IrOpcode::kChangeInt32ToInt64: { 408 Int32Matcher m(node->InputAt(0)); 409 if (m.HasValue()) return ReplaceInt64(m.Value()); 410 break; 411 } 412 case IrOpcode::kChangeUint32ToFloat64: { 413 Uint32Matcher m(node->InputAt(0)); 414 if (m.HasValue()) return ReplaceFloat64(FastUI2D(m.Value())); 415 break; 416 } 417 case IrOpcode::kChangeUint32ToUint64: { 418 Uint32Matcher m(node->InputAt(0)); 419 if (m.HasValue()) return ReplaceInt64(static_cast<uint64_t>(m.Value())); 420 break; 421 } 422 case IrOpcode::kTruncateFloat64ToInt32: 423 return ReduceTruncateFloat64ToInt32(node); 424 case IrOpcode::kTruncateInt64ToInt32: { 425 Int64Matcher m(node->InputAt(0)); 426 if (m.HasValue()) return ReplaceInt32(static_cast<int32_t>(m.Value())); 427 if (m.IsChangeInt32ToInt64()) return Replace(m.node()->InputAt(0)); 428 break; 429 } 430 case IrOpcode::kTruncateFloat64ToFloat32: { 431 Float64Matcher m(node->InputAt(0)); 432 if (m.HasValue()) return ReplaceFloat32(DoubleToFloat32(m.Value())); 433 if (m.IsChangeFloat32ToFloat64()) return Replace(m.node()->InputAt(0)); 434 break; 435 } 436 case IrOpcode::kFloat64InsertLowWord32: 437 return ReduceFloat64InsertLowWord32(node); 438 case IrOpcode::kFloat64InsertHighWord32: 439 return ReduceFloat64InsertHighWord32(node); 440 case IrOpcode::kStore: 441 return ReduceStore(node); 442 case IrOpcode::kFloat64Equal: 443 case IrOpcode::kFloat64LessThan: 444 case IrOpcode::kFloat64LessThanOrEqual: 445 return ReduceFloat64Compare(node); 446 default: 447 break; 448 } 449 return NoChange(); 450 } 451 452 453 Reduction MachineOperatorReducer::ReduceInt32Add(Node* node) { 454 DCHECK_EQ(IrOpcode::kInt32Add, node->opcode()); 455 Int32BinopMatcher m(node); 456 if (m.right().Is(0)) return Replace(m.left().node()); // x + 0 => x 457 if (m.IsFoldable()) { // K + K => K 458 return ReplaceUint32(bit_cast<uint32_t>(m.left().Value()) + 459 bit_cast<uint32_t>(m.right().Value())); 460 } 461 if (m.left().IsInt32Sub()) { 462 Int32BinopMatcher mleft(m.left().node()); 463 if (mleft.left().Is(0)) { // (0 - x) + y => y - x 464 node->ReplaceInput(0, m.right().node()); 465 node->ReplaceInput(1, mleft.right().node()); 466 NodeProperties::ChangeOp(node, machine()->Int32Sub()); 467 Reduction const reduction = ReduceInt32Sub(node); 468 return reduction.Changed() ? reduction : Changed(node); 469 } 470 } 471 if (m.right().IsInt32Sub()) { 472 Int32BinopMatcher mright(m.right().node()); 473 if (mright.left().Is(0)) { // y + (0 - x) => y - x 474 node->ReplaceInput(1, mright.right().node()); 475 NodeProperties::ChangeOp(node, machine()->Int32Sub()); 476 Reduction const reduction = ReduceInt32Sub(node); 477 return reduction.Changed() ? reduction : Changed(node); 478 } 479 } 480 return NoChange(); 481 } 482 483 484 Reduction MachineOperatorReducer::ReduceInt32Sub(Node* node) { 485 DCHECK_EQ(IrOpcode::kInt32Sub, node->opcode()); 486 Int32BinopMatcher m(node); 487 if (m.right().Is(0)) return Replace(m.left().node()); // x - 0 => x 488 if (m.IsFoldable()) { // K - K => K 489 return ReplaceInt32(static_cast<uint32_t>(m.left().Value()) - 490 static_cast<uint32_t>(m.right().Value())); 491 } 492 if (m.LeftEqualsRight()) return ReplaceInt32(0); // x - x => 0 493 if (m.right().HasValue()) { // x - K => x + -K 494 node->ReplaceInput(1, Int32Constant(-m.right().Value())); 495 NodeProperties::ChangeOp(node, machine()->Int32Add()); 496 Reduction const reduction = ReduceInt32Add(node); 497 return reduction.Changed() ? reduction : Changed(node); 498 } 499 return NoChange(); 500 } 501 502 503 Reduction MachineOperatorReducer::ReduceInt32Div(Node* node) { 504 Int32BinopMatcher m(node); 505 if (m.left().Is(0)) return Replace(m.left().node()); // 0 / x => 0 506 if (m.right().Is(0)) return Replace(m.right().node()); // x / 0 => 0 507 if (m.right().Is(1)) return Replace(m.left().node()); // x / 1 => x 508 if (m.IsFoldable()) { // K / K => K 509 return ReplaceInt32( 510 base::bits::SignedDiv32(m.left().Value(), m.right().Value())); 511 } 512 if (m.LeftEqualsRight()) { // x / x => x != 0 513 Node* const zero = Int32Constant(0); 514 return Replace(Word32Equal(Word32Equal(m.left().node(), zero), zero)); 515 } 516 if (m.right().Is(-1)) { // x / -1 => 0 - x 517 node->ReplaceInput(0, Int32Constant(0)); 518 node->ReplaceInput(1, m.left().node()); 519 node->TrimInputCount(2); 520 NodeProperties::ChangeOp(node, machine()->Int32Sub()); 521 return Changed(node); 522 } 523 if (m.right().HasValue()) { 524 int32_t const divisor = m.right().Value(); 525 Node* const dividend = m.left().node(); 526 Node* quotient = dividend; 527 if (base::bits::IsPowerOfTwo32(Abs(divisor))) { 528 uint32_t const shift = WhichPowerOf2Abs(divisor); 529 DCHECK_NE(0u, shift); 530 if (shift > 1) { 531 quotient = Word32Sar(quotient, 31); 532 } 533 quotient = Int32Add(Word32Shr(quotient, 32u - shift), dividend); 534 quotient = Word32Sar(quotient, shift); 535 } else { 536 quotient = Int32Div(quotient, Abs(divisor)); 537 } 538 if (divisor < 0) { 539 node->ReplaceInput(0, Int32Constant(0)); 540 node->ReplaceInput(1, quotient); 541 node->TrimInputCount(2); 542 NodeProperties::ChangeOp(node, machine()->Int32Sub()); 543 return Changed(node); 544 } 545 return Replace(quotient); 546 } 547 return NoChange(); 548 } 549 550 551 Reduction MachineOperatorReducer::ReduceUint32Div(Node* node) { 552 Uint32BinopMatcher m(node); 553 if (m.left().Is(0)) return Replace(m.left().node()); // 0 / x => 0 554 if (m.right().Is(0)) return Replace(m.right().node()); // x / 0 => 0 555 if (m.right().Is(1)) return Replace(m.left().node()); // x / 1 => x 556 if (m.IsFoldable()) { // K / K => K 557 return ReplaceUint32( 558 base::bits::UnsignedDiv32(m.left().Value(), m.right().Value())); 559 } 560 if (m.LeftEqualsRight()) { // x / x => x != 0 561 Node* const zero = Int32Constant(0); 562 return Replace(Word32Equal(Word32Equal(m.left().node(), zero), zero)); 563 } 564 if (m.right().HasValue()) { 565 Node* const dividend = m.left().node(); 566 uint32_t const divisor = m.right().Value(); 567 if (base::bits::IsPowerOfTwo32(divisor)) { // x / 2^n => x >> n 568 node->ReplaceInput(1, Uint32Constant(WhichPowerOf2(m.right().Value()))); 569 node->TrimInputCount(2); 570 NodeProperties::ChangeOp(node, machine()->Word32Shr()); 571 return Changed(node); 572 } else { 573 return Replace(Uint32Div(dividend, divisor)); 574 } 575 } 576 return NoChange(); 577 } 578 579 580 Reduction MachineOperatorReducer::ReduceInt32Mod(Node* node) { 581 Int32BinopMatcher m(node); 582 if (m.left().Is(0)) return Replace(m.left().node()); // 0 % x => 0 583 if (m.right().Is(0)) return Replace(m.right().node()); // x % 0 => 0 584 if (m.right().Is(1)) return ReplaceInt32(0); // x % 1 => 0 585 if (m.right().Is(-1)) return ReplaceInt32(0); // x % -1 => 0 586 if (m.LeftEqualsRight()) return ReplaceInt32(0); // x % x => 0 587 if (m.IsFoldable()) { // K % K => K 588 return ReplaceInt32( 589 base::bits::SignedMod32(m.left().Value(), m.right().Value())); 590 } 591 if (m.right().HasValue()) { 592 Node* const dividend = m.left().node(); 593 int32_t const divisor = Abs(m.right().Value()); 594 if (base::bits::IsPowerOfTwo32(divisor)) { 595 uint32_t const mask = divisor - 1; 596 Node* const zero = Int32Constant(0); 597 node->ReplaceInput( 598 0, graph()->NewNode(machine()->Int32LessThan(), dividend, zero)); 599 node->ReplaceInput( 600 1, Int32Sub(zero, Word32And(Int32Sub(zero, dividend), mask))); 601 node->ReplaceInput(2, Word32And(dividend, mask)); 602 NodeProperties::ChangeOp( 603 node, 604 common()->Select(MachineRepresentation::kWord32, BranchHint::kFalse)); 605 } else { 606 Node* quotient = Int32Div(dividend, divisor); 607 DCHECK_EQ(dividend, node->InputAt(0)); 608 node->ReplaceInput(1, Int32Mul(quotient, Int32Constant(divisor))); 609 node->TrimInputCount(2); 610 NodeProperties::ChangeOp(node, machine()->Int32Sub()); 611 } 612 return Changed(node); 613 } 614 return NoChange(); 615 } 616 617 618 Reduction MachineOperatorReducer::ReduceUint32Mod(Node* node) { 619 Uint32BinopMatcher m(node); 620 if (m.left().Is(0)) return Replace(m.left().node()); // 0 % x => 0 621 if (m.right().Is(0)) return Replace(m.right().node()); // x % 0 => 0 622 if (m.right().Is(1)) return ReplaceUint32(0); // x % 1 => 0 623 if (m.LeftEqualsRight()) return ReplaceInt32(0); // x % x => 0 624 if (m.IsFoldable()) { // K % K => K 625 return ReplaceUint32( 626 base::bits::UnsignedMod32(m.left().Value(), m.right().Value())); 627 } 628 if (m.right().HasValue()) { 629 Node* const dividend = m.left().node(); 630 uint32_t const divisor = m.right().Value(); 631 if (base::bits::IsPowerOfTwo32(divisor)) { // x % 2^n => x & 2^n-1 632 node->ReplaceInput(1, Uint32Constant(m.right().Value() - 1)); 633 node->TrimInputCount(2); 634 NodeProperties::ChangeOp(node, machine()->Word32And()); 635 } else { 636 Node* quotient = Uint32Div(dividend, divisor); 637 DCHECK_EQ(dividend, node->InputAt(0)); 638 node->ReplaceInput(1, Int32Mul(quotient, Uint32Constant(divisor))); 639 node->TrimInputCount(2); 640 NodeProperties::ChangeOp(node, machine()->Int32Sub()); 641 } 642 return Changed(node); 643 } 644 return NoChange(); 645 } 646 647 648 Reduction MachineOperatorReducer::ReduceTruncateFloat64ToInt32(Node* node) { 649 Float64Matcher m(node->InputAt(0)); 650 if (m.HasValue()) return ReplaceInt32(DoubleToInt32(m.Value())); 651 if (m.IsChangeInt32ToFloat64()) return Replace(m.node()->InputAt(0)); 652 if (m.IsPhi()) { 653 Node* const phi = m.node(); 654 DCHECK_EQ(MachineRepresentation::kFloat64, PhiRepresentationOf(phi->op())); 655 if (phi->OwnedBy(node)) { 656 // TruncateFloat64ToInt32[mode](Phi[Float64](x1,...,xn)) 657 // => Phi[Int32](TruncateFloat64ToInt32[mode](x1), 658 // ..., 659 // TruncateFloat64ToInt32[mode](xn)) 660 const int value_input_count = phi->InputCount() - 1; 661 for (int i = 0; i < value_input_count; ++i) { 662 Node* input = graph()->NewNode(node->op(), phi->InputAt(i)); 663 // TODO(bmeurer): Reschedule input for reduction once we have Revisit() 664 // instead of recursing into ReduceTruncateFloat64ToInt32() here. 665 Reduction reduction = ReduceTruncateFloat64ToInt32(input); 666 if (reduction.Changed()) input = reduction.replacement(); 667 phi->ReplaceInput(i, input); 668 } 669 NodeProperties::ChangeOp( 670 phi, 671 common()->Phi(MachineRepresentation::kWord32, value_input_count)); 672 return Replace(phi); 673 } 674 } 675 return NoChange(); 676 } 677 678 679 Reduction MachineOperatorReducer::ReduceStore(Node* node) { 680 MachineRepresentation const rep = 681 StoreRepresentationOf(node->op()).representation(); 682 Node* const value = node->InputAt(2); 683 switch (value->opcode()) { 684 case IrOpcode::kWord32And: { 685 Uint32BinopMatcher m(value); 686 if (m.right().HasValue() && ((rep == MachineRepresentation::kWord8 && 687 (m.right().Value() & 0xff) == 0xff) || 688 (rep == MachineRepresentation::kWord16 && 689 (m.right().Value() & 0xffff) == 0xffff))) { 690 node->ReplaceInput(2, m.left().node()); 691 return Changed(node); 692 } 693 break; 694 } 695 case IrOpcode::kWord32Sar: { 696 Int32BinopMatcher m(value); 697 if (m.left().IsWord32Shl() && ((rep == MachineRepresentation::kWord8 && 698 m.right().IsInRange(1, 24)) || 699 (rep == MachineRepresentation::kWord16 && 700 m.right().IsInRange(1, 16)))) { 701 Int32BinopMatcher mleft(m.left().node()); 702 if (mleft.right().Is(m.right().Value())) { 703 node->ReplaceInput(2, mleft.left().node()); 704 return Changed(node); 705 } 706 } 707 break; 708 } 709 default: 710 break; 711 } 712 return NoChange(); 713 } 714 715 716 Reduction MachineOperatorReducer::ReduceProjection(size_t index, Node* node) { 717 switch (node->opcode()) { 718 case IrOpcode::kInt32AddWithOverflow: { 719 DCHECK(index == 0 || index == 1); 720 Int32BinopMatcher m(node); 721 if (m.IsFoldable()) { 722 int32_t val; 723 bool ovf = base::bits::SignedAddOverflow32(m.left().Value(), 724 m.right().Value(), &val); 725 return ReplaceInt32((index == 0) ? val : ovf); 726 } 727 if (m.right().Is(0)) { 728 return (index == 0) ? Replace(m.left().node()) : ReplaceInt32(0); 729 } 730 break; 731 } 732 case IrOpcode::kInt32SubWithOverflow: { 733 DCHECK(index == 0 || index == 1); 734 Int32BinopMatcher m(node); 735 if (m.IsFoldable()) { 736 int32_t val; 737 bool ovf = base::bits::SignedSubOverflow32(m.left().Value(), 738 m.right().Value(), &val); 739 return ReplaceInt32((index == 0) ? val : ovf); 740 } 741 if (m.right().Is(0)) { 742 return (index == 0) ? Replace(m.left().node()) : ReplaceInt32(0); 743 } 744 break; 745 } 746 default: 747 break; 748 } 749 return NoChange(); 750 } 751 752 753 Reduction MachineOperatorReducer::ReduceWord32Shifts(Node* node) { 754 DCHECK((node->opcode() == IrOpcode::kWord32Shl) || 755 (node->opcode() == IrOpcode::kWord32Shr) || 756 (node->opcode() == IrOpcode::kWord32Sar)); 757 if (machine()->Word32ShiftIsSafe()) { 758 // Remove the explicit 'and' with 0x1f if the shift provided by the machine 759 // instruction matches that required by JavaScript. 760 Int32BinopMatcher m(node); 761 if (m.right().IsWord32And()) { 762 Int32BinopMatcher mright(m.right().node()); 763 if (mright.right().Is(0x1f)) { 764 node->ReplaceInput(1, mright.left().node()); 765 return Changed(node); 766 } 767 } 768 } 769 return NoChange(); 770 } 771 772 773 Reduction MachineOperatorReducer::ReduceWord32Shl(Node* node) { 774 DCHECK_EQ(IrOpcode::kWord32Shl, node->opcode()); 775 Int32BinopMatcher m(node); 776 if (m.right().Is(0)) return Replace(m.left().node()); // x << 0 => x 777 if (m.IsFoldable()) { // K << K => K 778 return ReplaceInt32(m.left().Value() << m.right().Value()); 779 } 780 if (m.right().IsInRange(1, 31)) { 781 // (x >>> K) << K => x & ~(2^K - 1) 782 // (x >> K) << K => x & ~(2^K - 1) 783 if (m.left().IsWord32Sar() || m.left().IsWord32Shr()) { 784 Int32BinopMatcher mleft(m.left().node()); 785 if (mleft.right().Is(m.right().Value())) { 786 node->ReplaceInput(0, mleft.left().node()); 787 node->ReplaceInput(1, 788 Uint32Constant(~((1U << m.right().Value()) - 1U))); 789 NodeProperties::ChangeOp(node, machine()->Word32And()); 790 Reduction reduction = ReduceWord32And(node); 791 return reduction.Changed() ? reduction : Changed(node); 792 } 793 } 794 } 795 return ReduceWord32Shifts(node); 796 } 797 798 799 Reduction MachineOperatorReducer::ReduceWord32Sar(Node* node) { 800 Int32BinopMatcher m(node); 801 if (m.right().Is(0)) return Replace(m.left().node()); // x >> 0 => x 802 if (m.IsFoldable()) { // K >> K => K 803 return ReplaceInt32(m.left().Value() >> m.right().Value()); 804 } 805 if (m.left().IsWord32Shl()) { 806 Int32BinopMatcher mleft(m.left().node()); 807 if (mleft.left().IsComparison()) { 808 if (m.right().Is(31) && mleft.right().Is(31)) { 809 // Comparison << 31 >> 31 => 0 - Comparison 810 node->ReplaceInput(0, Int32Constant(0)); 811 node->ReplaceInput(1, mleft.left().node()); 812 NodeProperties::ChangeOp(node, machine()->Int32Sub()); 813 Reduction const reduction = ReduceInt32Sub(node); 814 return reduction.Changed() ? reduction : Changed(node); 815 } 816 } else if (mleft.left().IsLoad()) { 817 LoadRepresentation const rep = 818 LoadRepresentationOf(mleft.left().node()->op()); 819 if (m.right().Is(24) && mleft.right().Is(24) && 820 rep == MachineType::Int8()) { 821 // Load[kMachInt8] << 24 >> 24 => Load[kMachInt8] 822 return Replace(mleft.left().node()); 823 } 824 if (m.right().Is(16) && mleft.right().Is(16) && 825 rep == MachineType::Int16()) { 826 // Load[kMachInt16] << 16 >> 16 => Load[kMachInt8] 827 return Replace(mleft.left().node()); 828 } 829 } 830 } 831 return ReduceWord32Shifts(node); 832 } 833 834 835 Reduction MachineOperatorReducer::ReduceWord32And(Node* node) { 836 DCHECK_EQ(IrOpcode::kWord32And, node->opcode()); 837 Int32BinopMatcher m(node); 838 if (m.right().Is(0)) return Replace(m.right().node()); // x & 0 => 0 839 if (m.right().Is(-1)) return Replace(m.left().node()); // x & -1 => x 840 if (m.left().IsComparison() && m.right().Is(1)) { // CMP & 1 => CMP 841 return Replace(m.left().node()); 842 } 843 if (m.IsFoldable()) { // K & K => K 844 return ReplaceInt32(m.left().Value() & m.right().Value()); 845 } 846 if (m.LeftEqualsRight()) return Replace(m.left().node()); // x & x => x 847 if (m.left().IsWord32And() && m.right().HasValue()) { 848 Int32BinopMatcher mleft(m.left().node()); 849 if (mleft.right().HasValue()) { // (x & K) & K => x & K 850 node->ReplaceInput(0, mleft.left().node()); 851 node->ReplaceInput( 852 1, Int32Constant(m.right().Value() & mleft.right().Value())); 853 Reduction const reduction = ReduceWord32And(node); 854 return reduction.Changed() ? reduction : Changed(node); 855 } 856 } 857 if (m.right().IsNegativePowerOf2()) { 858 int32_t const mask = m.right().Value(); 859 if (m.left().IsWord32Shl()) { 860 Uint32BinopMatcher mleft(m.left().node()); 861 if (mleft.right().HasValue() && 862 mleft.right().Value() >= base::bits::CountTrailingZeros32(mask)) { 863 // (x << L) & (-1 << K) => x << L iff K >= L 864 return Replace(mleft.node()); 865 } 866 } else if (m.left().IsInt32Add()) { 867 Int32BinopMatcher mleft(m.left().node()); 868 if (mleft.right().HasValue() && 869 (mleft.right().Value() & mask) == mleft.right().Value()) { 870 // (x + (K << L)) & (-1 << L) => (x & (-1 << L)) + (K << L) 871 node->ReplaceInput(0, Word32And(mleft.left().node(), m.right().node())); 872 node->ReplaceInput(1, mleft.right().node()); 873 NodeProperties::ChangeOp(node, machine()->Int32Add()); 874 Reduction const reduction = ReduceInt32Add(node); 875 return reduction.Changed() ? reduction : Changed(node); 876 } 877 if (mleft.left().IsInt32Mul()) { 878 Int32BinopMatcher mleftleft(mleft.left().node()); 879 if (mleftleft.right().IsMultipleOf(-mask)) { 880 // (y * (K << L) + x) & (-1 << L) => (x & (-1 << L)) + y * (K << L) 881 node->ReplaceInput(0, 882 Word32And(mleft.right().node(), m.right().node())); 883 node->ReplaceInput(1, mleftleft.node()); 884 NodeProperties::ChangeOp(node, machine()->Int32Add()); 885 Reduction const reduction = ReduceInt32Add(node); 886 return reduction.Changed() ? reduction : Changed(node); 887 } 888 } 889 if (mleft.right().IsInt32Mul()) { 890 Int32BinopMatcher mleftright(mleft.right().node()); 891 if (mleftright.right().IsMultipleOf(-mask)) { 892 // (x + y * (K << L)) & (-1 << L) => (x & (-1 << L)) + y * (K << L) 893 node->ReplaceInput(0, 894 Word32And(mleft.left().node(), m.right().node())); 895 node->ReplaceInput(1, mleftright.node()); 896 NodeProperties::ChangeOp(node, machine()->Int32Add()); 897 Reduction const reduction = ReduceInt32Add(node); 898 return reduction.Changed() ? reduction : Changed(node); 899 } 900 } 901 if (mleft.left().IsWord32Shl()) { 902 Int32BinopMatcher mleftleft(mleft.left().node()); 903 if (mleftleft.right().Is(base::bits::CountTrailingZeros32(mask))) { 904 // (y << L + x) & (-1 << L) => (x & (-1 << L)) + y << L 905 node->ReplaceInput(0, 906 Word32And(mleft.right().node(), m.right().node())); 907 node->ReplaceInput(1, mleftleft.node()); 908 NodeProperties::ChangeOp(node, machine()->Int32Add()); 909 Reduction const reduction = ReduceInt32Add(node); 910 return reduction.Changed() ? reduction : Changed(node); 911 } 912 } 913 if (mleft.right().IsWord32Shl()) { 914 Int32BinopMatcher mleftright(mleft.right().node()); 915 if (mleftright.right().Is(base::bits::CountTrailingZeros32(mask))) { 916 // (x + y << L) & (-1 << L) => (x & (-1 << L)) + y << L 917 node->ReplaceInput(0, 918 Word32And(mleft.left().node(), m.right().node())); 919 node->ReplaceInput(1, mleftright.node()); 920 NodeProperties::ChangeOp(node, machine()->Int32Add()); 921 Reduction const reduction = ReduceInt32Add(node); 922 return reduction.Changed() ? reduction : Changed(node); 923 } 924 } 925 } else if (m.left().IsInt32Mul()) { 926 Int32BinopMatcher mleft(m.left().node()); 927 if (mleft.right().IsMultipleOf(-mask)) { 928 // (x * (K << L)) & (-1 << L) => x * (K << L) 929 return Replace(mleft.node()); 930 } 931 } 932 } 933 return NoChange(); 934 } 935 936 937 Reduction MachineOperatorReducer::ReduceWord32Or(Node* node) { 938 DCHECK_EQ(IrOpcode::kWord32Or, node->opcode()); 939 Int32BinopMatcher m(node); 940 if (m.right().Is(0)) return Replace(m.left().node()); // x | 0 => x 941 if (m.right().Is(-1)) return Replace(m.right().node()); // x | -1 => -1 942 if (m.IsFoldable()) { // K | K => K 943 return ReplaceInt32(m.left().Value() | m.right().Value()); 944 } 945 if (m.LeftEqualsRight()) return Replace(m.left().node()); // x | x => x 946 947 Node* shl = nullptr; 948 Node* shr = nullptr; 949 // Recognize rotation, we are matching either: 950 // * x << y | x >>> (32 - y) => x ror (32 - y), i.e x rol y 951 // * x << (32 - y) | x >>> y => x ror y 952 // as well as their commuted form. 953 if (m.left().IsWord32Shl() && m.right().IsWord32Shr()) { 954 shl = m.left().node(); 955 shr = m.right().node(); 956 } else if (m.left().IsWord32Shr() && m.right().IsWord32Shl()) { 957 shl = m.right().node(); 958 shr = m.left().node(); 959 } else { 960 return NoChange(); 961 } 962 963 Int32BinopMatcher mshl(shl); 964 Int32BinopMatcher mshr(shr); 965 if (mshl.left().node() != mshr.left().node()) return NoChange(); 966 967 if (mshl.right().HasValue() && mshr.right().HasValue()) { 968 // Case where y is a constant. 969 if (mshl.right().Value() + mshr.right().Value() != 32) return NoChange(); 970 } else { 971 Node* sub = nullptr; 972 Node* y = nullptr; 973 if (mshl.right().IsInt32Sub()) { 974 sub = mshl.right().node(); 975 y = mshr.right().node(); 976 } else if (mshr.right().IsInt32Sub()) { 977 sub = mshr.right().node(); 978 y = mshl.right().node(); 979 } else { 980 return NoChange(); 981 } 982 983 Int32BinopMatcher msub(sub); 984 if (!msub.left().Is(32) || msub.right().node() != y) return NoChange(); 985 } 986 987 node->ReplaceInput(0, mshl.left().node()); 988 node->ReplaceInput(1, mshr.right().node()); 989 NodeProperties::ChangeOp(node, machine()->Word32Ror()); 990 return Changed(node); 991 } 992 993 994 Reduction MachineOperatorReducer::ReduceFloat64InsertLowWord32(Node* node) { 995 DCHECK_EQ(IrOpcode::kFloat64InsertLowWord32, node->opcode()); 996 Float64Matcher mlhs(node->InputAt(0)); 997 Uint32Matcher mrhs(node->InputAt(1)); 998 if (mlhs.HasValue() && mrhs.HasValue()) { 999 return ReplaceFloat64(bit_cast<double>( 1000 (bit_cast<uint64_t>(mlhs.Value()) & V8_UINT64_C(0xFFFFFFFF00000000)) | 1001 mrhs.Value())); 1002 } 1003 return NoChange(); 1004 } 1005 1006 1007 Reduction MachineOperatorReducer::ReduceFloat64InsertHighWord32(Node* node) { 1008 DCHECK_EQ(IrOpcode::kFloat64InsertHighWord32, node->opcode()); 1009 Float64Matcher mlhs(node->InputAt(0)); 1010 Uint32Matcher mrhs(node->InputAt(1)); 1011 if (mlhs.HasValue() && mrhs.HasValue()) { 1012 return ReplaceFloat64(bit_cast<double>( 1013 (bit_cast<uint64_t>(mlhs.Value()) & V8_UINT64_C(0xFFFFFFFF)) | 1014 (static_cast<uint64_t>(mrhs.Value()) << 32))); 1015 } 1016 return NoChange(); 1017 } 1018 1019 1020 namespace { 1021 1022 bool IsFloat64RepresentableAsFloat32(const Float64Matcher& m) { 1023 if (m.HasValue()) { 1024 double v = m.Value(); 1025 float fv = static_cast<float>(v); 1026 return static_cast<double>(fv) == v; 1027 } 1028 return false; 1029 } 1030 1031 } // namespace 1032 1033 1034 Reduction MachineOperatorReducer::ReduceFloat64Compare(Node* node) { 1035 DCHECK((IrOpcode::kFloat64Equal == node->opcode()) || 1036 (IrOpcode::kFloat64LessThan == node->opcode()) || 1037 (IrOpcode::kFloat64LessThanOrEqual == node->opcode())); 1038 // As all Float32 values have an exact representation in Float64, comparing 1039 // two Float64 values both converted from Float32 is equivalent to comparing 1040 // the original Float32s, so we can ignore the conversions. We can also reduce 1041 // comparisons of converted Float64 values against constants that can be 1042 // represented exactly as Float32. 1043 Float64BinopMatcher m(node); 1044 if ((m.left().IsChangeFloat32ToFloat64() && 1045 m.right().IsChangeFloat32ToFloat64()) || 1046 (m.left().IsChangeFloat32ToFloat64() && 1047 IsFloat64RepresentableAsFloat32(m.right())) || 1048 (IsFloat64RepresentableAsFloat32(m.left()) && 1049 m.right().IsChangeFloat32ToFloat64())) { 1050 switch (node->opcode()) { 1051 case IrOpcode::kFloat64Equal: 1052 NodeProperties::ChangeOp(node, machine()->Float32Equal()); 1053 break; 1054 case IrOpcode::kFloat64LessThan: 1055 NodeProperties::ChangeOp(node, machine()->Float32LessThan()); 1056 break; 1057 case IrOpcode::kFloat64LessThanOrEqual: 1058 NodeProperties::ChangeOp(node, machine()->Float32LessThanOrEqual()); 1059 break; 1060 default: 1061 return NoChange(); 1062 } 1063 node->ReplaceInput( 1064 0, m.left().HasValue() 1065 ? Float32Constant(static_cast<float>(m.left().Value())) 1066 : m.left().InputAt(0)); 1067 node->ReplaceInput( 1068 1, m.right().HasValue() 1069 ? Float32Constant(static_cast<float>(m.right().Value())) 1070 : m.right().InputAt(0)); 1071 return Changed(node); 1072 } 1073 return NoChange(); 1074 } 1075 1076 1077 CommonOperatorBuilder* MachineOperatorReducer::common() const { 1078 return jsgraph()->common(); 1079 } 1080 1081 1082 MachineOperatorBuilder* MachineOperatorReducer::machine() const { 1083 return jsgraph()->machine(); 1084 } 1085 1086 1087 Graph* MachineOperatorReducer::graph() const { return jsgraph()->graph(); } 1088 1089 } // namespace compiler 1090 } // namespace internal 1091 } // namespace v8 1092
