src/v8/src/compiler/machine-operator-reducer.cc

   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/compiler/generic-node-inl.h"
   9 #include "src/compiler/graph.h"
  10 #include "src/compiler/js-graph.h"
  11 #include "src/compiler/node-matchers.h"
  12
  13 namespace v8 {
  14 namespace internal {
  15 namespace compiler {
  16
  17 MachineOperatorReducer::MachineOperatorReducer(JSGraph* jsgraph)
  18     : jsgraph_(jsgraph) {}
  19
  20
  21 MachineOperatorReducer::~MachineOperatorReducer() {}
  22
  23
  24 Node* MachineOperatorReducer::Float32Constant(volatile float value) {
  25   return graph()->NewNode(common()->Float32Constant(value));
  26 }
  27
  28
  29 Node* MachineOperatorReducer::Float64Constant(volatile double value) {
  30   return jsgraph()->Float64Constant(value);
  31 }
  32
  33
  34 Node* MachineOperatorReducer::Int32Constant(int32_t value) {
  35   return jsgraph()->Int32Constant(value);
  36 }
  37
  38
  39 Node* MachineOperatorReducer::Int64Constant(int64_t value) {
  40   return graph()->NewNode(common()->Int64Constant(value));
  41 }
  42
  43
  44 // Perform constant folding and strength reduction on machine operators.
  45 Reduction MachineOperatorReducer::Reduce(Node* node) {
  46   switch (node->opcode()) {
  47     case IrOpcode::kProjection:
  48       return ReduceProjection(OpParameter<size_t>(node), node->InputAt(0));
  49     case IrOpcode::kWord32And: {
  50       Int32BinopMatcher m(node);
  51       if (m.right().Is(0)) return Replace(m.right().node());  // x & 0  => 0
  52       if (m.right().Is(-1)) return Replace(m.left().node());  // x & -1 => x
  53       if (m.IsFoldable()) {                                   // K & K  => K
  54         return ReplaceInt32(m.left().Value() & m.right().Value());
  55       }
  56       if (m.LeftEqualsRight()) return Replace(m.left().node());  // x & x => x
  57       break;
  58     }
  59     case IrOpcode::kWord32Or: {
  60       Int32BinopMatcher m(node);
  61       if (m.right().Is(0)) return Replace(m.left().node());    // x | 0  => x
  62       if (m.right().Is(-1)) return Replace(m.right().node());  // x | -1 => -1
  63       if (m.IsFoldable()) {                                    // K | K  => K
  64         return ReplaceInt32(m.left().Value() | m.right().Value());
  65       }
  66       if (m.LeftEqualsRight()) return Replace(m.left().node());  // x | x => x
  67       if (m.left().IsWord32Shl() && m.right().IsWord32Shr()) {
  68         Int32BinopMatcher mleft(m.left().node());
  69         Int32BinopMatcher mright(m.right().node());
  70         if (mleft.left().node() == mright.left().node()) {
  71           // (x << y) | (x >> (32 - y)) => x ror y
  72           if (mright.right().IsInt32Sub()) {
  73             Int32BinopMatcher mrightright(mright.right().node());
  74             if (mrightright.left().Is(32) &&
  75                 mrightright.right().node() == mleft.right().node()) {
  76               node->set_op(machine()->Word32Ror());
  77               node->ReplaceInput(0, mleft.left().node());
  78               node->ReplaceInput(1, mleft.right().node());
  79               return Changed(node);
  80             }
  81           }
  82           // (x << K) | (x >> (32 - K)) => x ror K
  83           if (mleft.right().IsInRange(0, 31) &&
  84               mright.right().Is(32 - mleft.right().Value())) {
  85             node->set_op(machine()->Word32Ror());
  86             node->ReplaceInput(0, mleft.left().node());
  87             node->ReplaceInput(1, mleft.right().node());
  88             return Changed(node);
  89           }
  90         }
  91       }
  92       if (m.left().IsWord32Shr() && m.right().IsWord32Shl()) {
  93         // (x >> (32 - y)) | (x << y)  => x ror y
  94         Int32BinopMatcher mleft(m.left().node());
  95         Int32BinopMatcher mright(m.right().node());
  96         if (mleft.left().node() == mright.left().node()) {
  97           if (mleft.right().IsInt32Sub()) {
  98             Int32BinopMatcher mleftright(mleft.right().node());
  99             if (mleftright.left().Is(32) &&
 100                 mleftright.right().node() == mright.right().node()) {
 101               node->set_op(machine()->Word32Ror());
 102               node->ReplaceInput(0, mright.left().node());
 103               node->ReplaceInput(1, mright.right().node());
 104               return Changed(node);
 105             }
 106           }
 107           // (x >> (32 - K)) | (x << K) => x ror K
 108           if (mright.right().IsInRange(0, 31) &&
 109               mleft.right().Is(32 - mright.right().Value())) {
 110             node->set_op(machine()->Word32Ror());
 111             node->ReplaceInput(0, mright.left().node());
 112             node->ReplaceInput(1, mright.right().node());
 113             return Changed(node);
 114           }
 115         }
 116       }
 117       break;
 118     }
 119     case IrOpcode::kWord32Xor: {
 120       Int32BinopMatcher m(node);
 121       if (m.right().Is(0)) return Replace(m.left().node());  // x ^ 0 => x
 122       if (m.IsFoldable()) {                                  // K ^ K => K
 123         return ReplaceInt32(m.left().Value() ^ m.right().Value());
 124       }
 125       if (m.LeftEqualsRight()) return ReplaceInt32(0);  // x ^ x => 0
 126       break;
 127     }
 128     case IrOpcode::kWord32Shl: {
 129       Int32BinopMatcher m(node);
 130       if (m.right().Is(0)) return Replace(m.left().node());  // x << 0 => x
 131       if (m.IsFoldable()) {                                  // K << K => K
 132         return ReplaceInt32(m.left().Value() << m.right().Value());
 133       }
 134       break;
 135     }
 136     case IrOpcode::kWord32Shr: {
 137       Uint32BinopMatcher m(node);
 138       if (m.right().Is(0)) return Replace(m.left().node());  // x >>> 0 => x
 139       if (m.IsFoldable()) {                                  // K >>> K => K
 140         return ReplaceInt32(m.left().Value() >> m.right().Value());
 141       }
 142       break;
 143     }
 144     case IrOpcode::kWord32Sar: {
 145       Int32BinopMatcher m(node);
 146       if (m.right().Is(0)) return Replace(m.left().node());  // x >> 0 => x
 147       if (m.IsFoldable()) {                                  // K >> K => K
 148         return ReplaceInt32(m.left().Value() >> m.right().Value());
 149       }
 150       break;
 151     }
 152     case IrOpcode::kWord32Ror: {
 153       Int32BinopMatcher m(node);
 154       if (m.right().Is(0)) return Replace(m.left().node());  // x ror 0 => x
 155       if (m.IsFoldable()) {                                  // K ror K => K
 156         return ReplaceInt32(
 157             base::bits::RotateRight32(m.left().Value(), m.right().Value()));
 158       }
 159       break;
 160     }
 161     case IrOpcode::kWord32Equal: {
 162       Int32BinopMatcher m(node);
 163       if (m.IsFoldable()) {  // K == K => K
 164         return ReplaceBool(m.left().Value() == m.right().Value());
 165       }
 166       if (m.left().IsInt32Sub() && m.right().Is(0)) {  // x - y == 0 => x == y
 167         Int32BinopMatcher msub(m.left().node());
 168         node->ReplaceInput(0, msub.left().node());
 169         node->ReplaceInput(1, msub.right().node());
 170         return Changed(node);
 171       }
 172       // TODO(turbofan): fold HeapConstant, ExternalReference, pointer compares
 173       if (m.LeftEqualsRight()) return ReplaceBool(true);  // x == x => true
 174       break;
 175     }
 176     case IrOpcode::kInt32Add: {
 177       Int32BinopMatcher m(node);
 178       if (m.right().Is(0)) return Replace(m.left().node());  // x + 0 => x
 179       if (m.IsFoldable()) {                                  // K + K => K
 180         return ReplaceInt32(static_cast<uint32_t>(m.left().Value()) +
 181                             static_cast<uint32_t>(m.right().Value()));
 182       }
 183       break;
 184     }
 185     case IrOpcode::kInt32Sub: {
 186       Int32BinopMatcher m(node);
 187       if (m.right().Is(0)) return Replace(m.left().node());  // x - 0 => x
 188       if (m.IsFoldable()) {                                  // K - K => K
 189         return ReplaceInt32(static_cast<uint32_t>(m.left().Value()) -
 190                             static_cast<uint32_t>(m.right().Value()));
 191       }
 192       if (m.LeftEqualsRight()) return ReplaceInt32(0);  // x - x => 0
 193       break;
 194     }
 195     case IrOpcode::kInt32Mul: {
 196       Int32BinopMatcher m(node);
 197       if (m.right().Is(0)) return Replace(m.right().node());  // x * 0 => 0
 198       if (m.right().Is(1)) return Replace(m.left().node());   // x * 1 => x
 199       if (m.IsFoldable()) {                                   // K * K => K
 200         return ReplaceInt32(m.left().Value() * m.right().Value());
 201       }
 202       if (m.right().Is(-1)) {  // x * -1 => 0 - x
 203         node->set_op(machine()->Int32Sub());
 204         node->ReplaceInput(0, Int32Constant(0));
 205         node->ReplaceInput(1, m.left().node());
 206         return Changed(node);
 207       }
 208       if (m.right().IsPowerOf2()) {  // x * 2^n => x << n
 209         node->set_op(machine()->Word32Shl());
 210         node->ReplaceInput(1, Int32Constant(WhichPowerOf2(m.right().Value())));
 211         return Changed(node);
 212       }
 213       break;
 214     }
 215     case IrOpcode::kInt32Div: {
 216       Int32BinopMatcher m(node);
 217       if (m.right().Is(1)) return Replace(m.left().node());  // x / 1 => x
 218       // TODO(turbofan): if (m.left().Is(0))
 219       // TODO(turbofan): if (m.right().IsPowerOf2())
 220       // TODO(turbofan): if (m.right().Is(0))
 221       // TODO(turbofan): if (m.LeftEqualsRight())
 222       if (m.IsFoldable() && !m.right().Is(0)) {  // K / K => K
 223         if (m.right().Is(-1)) return ReplaceInt32(-m.left().Value());
 224         return ReplaceInt32(m.left().Value() / m.right().Value());
 225       }
 226       if (m.right().Is(-1)) {  // x / -1 => 0 - x
 227         node->set_op(machine()->Int32Sub());
 228         node->ReplaceInput(0, Int32Constant(0));
 229         node->ReplaceInput(1, m.left().node());
 230         return Changed(node);
 231       }
 232       break;
 233     }
 234     case IrOpcode::kInt32UDiv: {
 235       Uint32BinopMatcher m(node);
 236       if (m.right().Is(1)) return Replace(m.left().node());  // x / 1 => x
 237       // TODO(turbofan): if (m.left().Is(0))
 238       // TODO(turbofan): if (m.right().Is(0))
 239       // TODO(turbofan): if (m.LeftEqualsRight())
 240       if (m.IsFoldable() && !m.right().Is(0)) {  // K / K => K
 241         return ReplaceInt32(m.left().Value() / m.right().Value());
 242       }
 243       if (m.right().IsPowerOf2()) {  // x / 2^n => x >> n
 244         node->set_op(machine()->Word32Shr());
 245         node->ReplaceInput(1, Int32Constant(WhichPowerOf2(m.right().Value())));
 246         return Changed(node);
 247       }
 248       break;
 249     }
 250     case IrOpcode::kInt32Mod: {
 251       Int32BinopMatcher m(node);
 252       if (m.right().Is(1)) return ReplaceInt32(0);   // x % 1  => 0
 253       if (m.right().Is(-1)) return ReplaceInt32(0);  // x % -1 => 0
 254       // TODO(turbofan): if (m.left().Is(0))
 255       // TODO(turbofan): if (m.right().IsPowerOf2())
 256       // TODO(turbofan): if (m.right().Is(0))
 257       // TODO(turbofan): if (m.LeftEqualsRight())
 258       if (m.IsFoldable() && !m.right().Is(0)) {  // K % K => K
 259         return ReplaceInt32(m.left().Value() % m.right().Value());
 260       }
 261       break;
 262     }
 263     case IrOpcode::kInt32UMod: {
 264       Uint32BinopMatcher m(node);
 265       if (m.right().Is(1)) return ReplaceInt32(0);  // x % 1 => 0
 266       // TODO(turbofan): if (m.left().Is(0))
 267       // TODO(turbofan): if (m.right().Is(0))
 268       // TODO(turbofan): if (m.LeftEqualsRight())
 269       if (m.IsFoldable() && !m.right().Is(0)) {  // K % K => K
 270         return ReplaceInt32(m.left().Value() % m.right().Value());
 271       }
 272       if (m.right().IsPowerOf2()) {  // x % 2^n => x & 2^n-1
 273         node->set_op(machine()->Word32And());
 274         node->ReplaceInput(1, Int32Constant(m.right().Value() - 1));
 275         return Changed(node);
 276       }
 277       break;
 278     }
 279     case IrOpcode::kInt32LessThan: {
 280       Int32BinopMatcher m(node);
 281       if (m.IsFoldable()) {  // K < K => K
 282         return ReplaceBool(m.left().Value() < m.right().Value());
 283       }
 284       if (m.left().IsInt32Sub() && m.right().Is(0)) {  // x - y < 0 => x < y
 285         Int32BinopMatcher msub(m.left().node());
 286         node->ReplaceInput(0, msub.left().node());
 287         node->ReplaceInput(1, msub.right().node());
 288         return Changed(node);
 289       }
 290       if (m.left().Is(0) && m.right().IsInt32Sub()) {  // 0 < x - y => y < x
 291         Int32BinopMatcher msub(m.right().node());
 292         node->ReplaceInput(0, msub.right().node());
 293         node->ReplaceInput(1, msub.left().node());
 294         return Changed(node);
 295       }
 296       if (m.LeftEqualsRight()) return ReplaceBool(false);  // x < x => false
 297       break;
 298     }
 299     case IrOpcode::kInt32LessThanOrEqual: {
 300       Int32BinopMatcher m(node);
 301       if (m.IsFoldable()) {  // K <= K => K
 302         return ReplaceBool(m.left().Value() <= m.right().Value());
 303       }
 304       if (m.left().IsInt32Sub() && m.right().Is(0)) {  // x - y <= 0 => x <= y
 305         Int32BinopMatcher msub(m.left().node());
 306         node->ReplaceInput(0, msub.left().node());
 307         node->ReplaceInput(1, msub.right().node());
 308         return Changed(node);
 309       }
 310       if (m.left().Is(0) && m.right().IsInt32Sub()) {  // 0 <= x - y => y <= x
 311         Int32BinopMatcher msub(m.right().node());
 312         node->ReplaceInput(0, msub.right().node());
 313         node->ReplaceInput(1, msub.left().node());
 314         return Changed(node);
 315       }
 316       if (m.LeftEqualsRight()) return ReplaceBool(true);  // x <= x => true
 317       break;
 318     }
 319     case IrOpcode::kUint32LessThan: {
 320       Uint32BinopMatcher m(node);
 321       if (m.left().Is(kMaxUInt32)) return ReplaceBool(false);  // M < x => false
 322       if (m.right().Is(0)) return ReplaceBool(false);          // x < 0 => false
 323       if (m.IsFoldable()) {                                    // K < K => K
 324         return ReplaceBool(m.left().Value() < m.right().Value());
 325       }
 326       if (m.LeftEqualsRight()) return ReplaceBool(false);  // x < x => false
 327       break;
 328     }
 329     case IrOpcode::kUint32LessThanOrEqual: {
 330       Uint32BinopMatcher m(node);
 331       if (m.left().Is(0)) return ReplaceBool(true);            // 0 <= x => true
 332       if (m.right().Is(kMaxUInt32)) return ReplaceBool(true);  // x <= M => true
 333       if (m.IsFoldable()) {                                    // K <= K => K
 334         return ReplaceBool(m.left().Value() <= m.right().Value());
 335       }
 336       if (m.LeftEqualsRight()) return ReplaceBool(true);  // x <= x => true
 337       break;
 338     }
 339     case IrOpcode::kFloat64Add: {
 340       Float64BinopMatcher m(node);
 341       if (m.IsFoldable()) {  // K + K => K
 342         return ReplaceFloat64(m.left().Value() + m.right().Value());
 343       }
 344       break;
 345     }
 346     case IrOpcode::kFloat64Sub: {
 347       Float64BinopMatcher m(node);
 348       if (m.IsFoldable()) {  // K - K => K
 349         return ReplaceFloat64(m.left().Value() - m.right().Value());
 350       }
 351       break;
 352     }
 353     case IrOpcode::kFloat64Mul: {
 354       Float64BinopMatcher m(node);
 355       if (m.right().Is(1)) return Replace(m.left().node());  // x * 1.0 => x
 356       if (m.right().IsNaN()) {                               // x * NaN => NaN
 357         return Replace(m.right().node());
 358       }
 359       if (m.IsFoldable()) {  // K * K => K
 360         return ReplaceFloat64(m.left().Value() * m.right().Value());
 361       }
 362       break;
 363     }
 364     case IrOpcode::kFloat64Div: {
 365       Float64BinopMatcher m(node);
 366       if (m.right().Is(1)) return Replace(m.left().node());  // x / 1.0 => x
 367       if (m.right().IsNaN()) {                               // x / NaN => NaN
 368         return Replace(m.right().node());
 369       }
 370       if (m.left().IsNaN()) {  // NaN / x => NaN
 371         return Replace(m.left().node());
 372       }
 373       if (m.IsFoldable()) {  // K / K => K
 374         return ReplaceFloat64(m.left().Value() / m.right().Value());
 375       }
 376       break;
 377     }
 378     case IrOpcode::kFloat64Mod: {
 379       Float64BinopMatcher m(node);
 380       if (m.right().IsNaN()) {  // x % NaN => NaN
 381         return Replace(m.right().node());
 382       }
 383       if (m.left().IsNaN()) {  // NaN % x => NaN
 384         return Replace(m.left().node());
 385       }
 386       if (m.IsFoldable()) {  // K % K => K
 387         return ReplaceFloat64(modulo(m.left().Value(), m.right().Value()));
 388       }
 389       break;
 390     }
 391     case IrOpcode::kChangeFloat32ToFloat64: {
 392       Float32Matcher m(node->InputAt(0));
 393       if (m.HasValue()) return ReplaceFloat64(m.Value());
 394       break;
 395     }
 396     case IrOpcode::kChangeFloat64ToInt32: {
 397       Float64Matcher m(node->InputAt(0));
 398       if (m.HasValue()) return ReplaceInt32(FastD2I(m.Value()));
 399       if (m.IsChangeInt32ToFloat64()) return Replace(m.node()->InputAt(0));
 400       break;
 401     }
 402     case IrOpcode::kChangeFloat64ToUint32: {
 403       Float64Matcher m(node->InputAt(0));
 404       if (m.HasValue()) return ReplaceInt32(FastD2UI(m.Value()));
 405       if (m.IsChangeUint32ToFloat64()) return Replace(m.node()->InputAt(0));
 406       break;
 407     }
 408     case IrOpcode::kChangeInt32ToFloat64: {
 409       Int32Matcher m(node->InputAt(0));
 410       if (m.HasValue()) return ReplaceFloat64(FastI2D(m.Value()));
 411       break;
 412     }
 413     case IrOpcode::kChangeInt32ToInt64: {
 414       Int32Matcher m(node->InputAt(0));
 415       if (m.HasValue()) return ReplaceInt64(m.Value());
 416       break;
 417     }
 418     case IrOpcode::kChangeUint32ToFloat64: {
 419       Uint32Matcher m(node->InputAt(0));
 420       if (m.HasValue()) return ReplaceFloat64(FastUI2D(m.Value()));
 421       break;
 422     }
 423     case IrOpcode::kChangeUint32ToUint64: {
 424       Uint32Matcher m(node->InputAt(0));
 425       if (m.HasValue()) return ReplaceInt64(static_cast<uint64_t>(m.Value()));
 426       break;
 427     }
 428     case IrOpcode::kTruncateFloat64ToInt32: {
 429       Float64Matcher m(node->InputAt(0));
 430       if (m.HasValue()) return ReplaceInt32(DoubleToInt32(m.Value()));
 431       if (m.IsChangeInt32ToFloat64()) return Replace(m.node()->InputAt(0));
 432       break;
 433     }
 434     case IrOpcode::kTruncateInt64ToInt32: {
 435       Int64Matcher m(node->InputAt(0));
 436       if (m.HasValue()) return ReplaceInt32(static_cast<int32_t>(m.Value()));
 437       if (m.IsChangeInt32ToInt64()) return Replace(m.node()->InputAt(0));
 438       break;
 439     }
 440     case IrOpcode::kTruncateFloat64ToFloat32: {
 441       Float64Matcher m(node->InputAt(0));
 442       if (m.HasValue()) return ReplaceFloat32(DoubleToFloat32(m.Value()));
 443       if (m.IsChangeFloat32ToFloat64()) return Replace(m.node()->InputAt(0));
 444       break;
 445     }
 446     default:
 447       break;
 448   }
 449   return NoChange();
 450 }
 451
 452
 453 Reduction MachineOperatorReducer::ReduceProjection(size_t index, Node* node) {
 454   switch (node->opcode()) {
 455     case IrOpcode::kInt32AddWithOverflow: {
 456       DCHECK(index == 0 || index == 1);
 457       Int32BinopMatcher m(node);
 458       if (m.IsFoldable()) {
 459         int32_t val;
 460         bool ovf = base::bits::SignedAddOverflow32(m.left().Value(),
 461                                                    m.right().Value(), &val);
 462         return ReplaceInt32((index == 0) ? val : ovf);
 463       }
 464       if (m.right().Is(0)) {
 465         return (index == 0) ? Replace(m.left().node()) : ReplaceInt32(0);
 466       }
 467       break;
 468     }
 469     case IrOpcode::kInt32SubWithOverflow: {
 470       DCHECK(index == 0 || index == 1);
 471       Int32BinopMatcher m(node);
 472       if (m.IsFoldable()) {
 473         int32_t val;
 474         bool ovf = base::bits::SignedSubOverflow32(m.left().Value(),
 475                                                    m.right().Value(), &val);
 476         return ReplaceInt32((index == 0) ? val : ovf);
 477       }
 478       if (m.right().Is(0)) {
 479         return (index == 0) ? Replace(m.left().node()) : ReplaceInt32(0);
 480       }
 481       break;
 482     }
 483     default:
 484       break;
 485   }
 486   return NoChange();
 487 }
 488
 489
 490 CommonOperatorBuilder* MachineOperatorReducer::common() const {
 491   return jsgraph()->common();
 492 }
 493
 494
 495 MachineOperatorBuilder* MachineOperatorReducer::machine() const {
 496   return jsgraph()->machine();
 497 }
 498
 499
 500 Graph* MachineOperatorReducer::graph() const { return jsgraph()->graph(); }
 501
 502 }  // namespace compiler
 503 }  // namespace internal
 504 }  // namespace v8