deps/v8/src/compiler/simplified-lowering.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/simplified-lowering.h"
   6
   7 #include <limits>
   8
   9 #include "src/base/bits.h"
  10 #include "src/code-factory.h"
  11 #include "src/compiler/common-operator.h"
  12 #include "src/compiler/diamond.h"
  13 #include "src/compiler/linkage.h"
  14 #include "src/compiler/node-matchers.h"
  15 #include "src/compiler/node-properties.h"
  16 #include "src/compiler/operator-properties.h"
  17 #include "src/compiler/representation-change.h"
  18 #include "src/compiler/simplified-lowering.h"
  19 #include "src/compiler/simplified-operator.h"
  20 #include "src/compiler/source-position.h"
  21 #include "src/objects.h"
  22
  23 namespace v8 {
  24 namespace internal {
  25 namespace compiler {
  26
  27 // Macro for outputting trace information from representation inference.
  28 #define TRACE(...)                                      \
  29   do {                                                  \
  30     if (FLAG_trace_representation) PrintF(__VA_ARGS__); \
  31   } while (false)
  32
  33 // Representation selection and lowering of {Simplified} operators to machine
  34 // operators are interwined. We use a fixpoint calculation to compute both the
  35 // output representation and the best possible lowering for {Simplified} nodes.
  36 // Representation change insertion ensures that all values are in the correct
  37 // machine representation after this phase, as dictated by the machine
  38 // operators themselves.
  39 enum Phase {
  40   // 1.) PROPAGATE: Traverse the graph from the end, pushing usage information
  41   //     backwards from uses to definitions, around cycles in phis, according
  42   //     to local rules for each operator.
  43   //     During this phase, the usage information for a node determines the best
  44   //     possible lowering for each operator so far, and that in turn determines
  45   //     the output representation.
  46   //     Therefore, to be correct, this phase must iterate to a fixpoint before
  47   //     the next phase can begin.
  48   PROPAGATE,
  49
  50   // 2.) LOWER: perform lowering for all {Simplified} nodes by replacing some
  51   //     operators for some nodes, expanding some nodes to multiple nodes, or
  52   //     removing some (redundant) nodes.
  53   //     During this phase, use the {RepresentationChanger} to insert
  54   //     representation changes between uses that demand a particular
  55   //     representation and nodes that produce a different representation.
  56   LOWER
  57 };
  58
  59
  60 class RepresentationSelector {
  61  public:
  62   // Information for each node tracked during the fixpoint.
  63   struct NodeInfo {
  64     MachineTypeUnion use : 15;     // Union of all usages for the node.
  65     bool queued : 1;           // Bookkeeping for the traversal.
  66     bool visited : 1;          // Bookkeeping for the traversal.
  67     MachineTypeUnion output : 15;  // Output type of the node.
  68   };
  69
  70   RepresentationSelector(JSGraph* jsgraph, Zone* zone,
  71                          RepresentationChanger* changer,
  72                          SourcePositionTable* source_positions)
  73       : jsgraph_(jsgraph),
  74         count_(jsgraph->graph()->NodeCount()),
  75         info_(zone->NewArray<NodeInfo>(count_)),
  76         nodes_(zone),
  77         replacements_(zone),
  78         phase_(PROPAGATE),
  79         changer_(changer),
  80         queue_(zone),
  81         source_positions_(source_positions) {
  82     memset(info_, 0, sizeof(NodeInfo) * count_);
  83
  84     safe_int_additive_range_ =
  85         Type::Range(-std::pow(2.0, 52.0), std::pow(2.0, 52.0), zone);
  86   }
  87
  88   void Run(SimplifiedLowering* lowering) {
  89     // Run propagation phase to a fixpoint.
  90     TRACE("--{Propagation phase}--\n");
  91     phase_ = PROPAGATE;
  92     Enqueue(jsgraph_->graph()->end());
  93     // Process nodes from the queue until it is empty.
  94     while (!queue_.empty()) {
  95       Node* node = queue_.front();
  96       NodeInfo* info = GetInfo(node);
  97       queue_.pop();
  98       info->queued = false;
  99       TRACE(" visit #%d: %s\n", node->id(), node->op()->mnemonic());
 100       VisitNode(node, info->use, NULL);
 101       TRACE("  ==> output ");
 102       PrintInfo(info->output);
 103       TRACE("\n");
 104     }
 105
 106     // Run lowering and change insertion phase.
 107     TRACE("--{Simplified lowering phase}--\n");
 108     phase_ = LOWER;
 109     // Process nodes from the collected {nodes_} vector.
 110     for (NodeVector::iterator i = nodes_.begin(); i != nodes_.end(); ++i) {
 111       Node* node = *i;
 112       TRACE(" visit #%d: %s\n", node->id(), node->op()->mnemonic());
 113       // Reuse {VisitNode()} so the representation rules are in one place.
 114       if (FLAG_turbo_source_positions) {
 115         SourcePositionTable::Scope scope(
 116             source_positions_, source_positions_->GetSourcePosition(node));
 117         VisitNode(node, GetUseInfo(node), lowering);
 118       } else {
 119         VisitNode(node, GetUseInfo(node), lowering);
 120       }
 121     }
 122
 123     // Perform the final replacements.
 124     for (NodeVector::iterator i = replacements_.begin();
 125          i != replacements_.end(); ++i) {
 126       Node* node = *i;
 127       Node* replacement = *(++i);
 128       node->ReplaceUses(replacement);
 129       // We also need to replace the node in the rest of the vector.
 130       for (NodeVector::iterator j = i + 1; j != replacements_.end(); ++j) {
 131         ++j;
 132         if (*j == node) *j = replacement;
 133       }
 134     }
 135   }
 136
 137   // Enqueue {node} if the {use} contains new information for that node.
 138   // Add {node} to {nodes_} if this is the first time it's been visited.
 139   void Enqueue(Node* node, MachineTypeUnion use = 0) {
 140     if (phase_ != PROPAGATE) return;
 141     NodeInfo* info = GetInfo(node);
 142     if (!info->visited) {
 143       // First visit of this node.
 144       info->visited = true;
 145       info->queued = true;
 146       nodes_.push_back(node);
 147       queue_.push(node);
 148       TRACE("  initial: ");
 149       info->use |= use;
 150       PrintUseInfo(node);
 151       return;
 152     }
 153     TRACE("   queue?: ");
 154     PrintUseInfo(node);
 155     if ((info->use & use) != use) {
 156       // New usage information for the node is available.
 157       if (!info->queued) {
 158         queue_.push(node);
 159         info->queued = true;
 160         TRACE("   added: ");
 161       } else {
 162         TRACE(" inqueue: ");
 163       }
 164       info->use |= use;
 165       PrintUseInfo(node);
 166     }
 167   }
 168
 169   bool lower() { return phase_ == LOWER; }
 170
 171   void Enqueue(Node* node, MachineType use) {
 172     Enqueue(node, static_cast<MachineTypeUnion>(use));
 173   }
 174
 175   void SetOutput(Node* node, MachineTypeUnion output) {
 176     // Every node should have at most one output representation. Note that
 177     // phis can have 0, if they have not been used in a representation-inducing
 178     // instruction.
 179     DCHECK((output & kRepMask) == 0 ||
 180            base::bits::IsPowerOfTwo32(output & kRepMask));
 181     GetInfo(node)->output = output;
 182   }
 183
 184   bool BothInputsAre(Node* node, Type* type) {
 185     DCHECK_EQ(2, node->InputCount());
 186     return NodeProperties::GetBounds(node->InputAt(0)).upper->Is(type) &&
 187            NodeProperties::GetBounds(node->InputAt(1)).upper->Is(type);
 188   }
 189
 190   void ProcessTruncateWord32Input(Node* node, int index, MachineTypeUnion use) {
 191     Node* input = node->InputAt(index);
 192     if (phase_ == PROPAGATE) {
 193       // In the propagate phase, propagate the usage information backward.
 194       Enqueue(input, use);
 195     } else {
 196       // In the change phase, insert a change before the use if necessary.
 197       MachineTypeUnion output = GetInfo(input)->output;
 198       if ((output & (kRepBit | kRepWord8 | kRepWord16 | kRepWord32)) == 0) {
 199         // Output representation doesn't match usage.
 200         TRACE("  truncate-to-int32: #%d:%s(@%d #%d:%s) ", node->id(),
 201               node->op()->mnemonic(), index, input->id(),
 202               input->op()->mnemonic());
 203         TRACE(" from ");
 204         PrintInfo(output);
 205         TRACE(" to ");
 206         PrintInfo(use);
 207         TRACE("\n");
 208         Node* n = changer_->GetTruncatedWord32For(input, output);
 209         node->ReplaceInput(index, n);
 210       }
 211     }
 212   }
 213
 214   void ProcessInput(Node* node, int index, MachineTypeUnion use) {
 215     Node* input = node->InputAt(index);
 216     if (phase_ == PROPAGATE) {
 217       // In the propagate phase, propagate the usage information backward.
 218       Enqueue(input, use);
 219     } else {
 220       // In the change phase, insert a change before the use if necessary.
 221       if ((use & kRepMask) == 0) return;  // No input requirement on the use.
 222       MachineTypeUnion output = GetInfo(input)->output;
 223       if ((output & kRepMask & use) == 0) {
 224         // Output representation doesn't match usage.
 225         TRACE("  change: #%d:%s(@%d #%d:%s) ", node->id(),
 226               node->op()->mnemonic(), index, input->id(),
 227               input->op()->mnemonic());
 228         TRACE(" from ");
 229         PrintInfo(output);
 230         TRACE(" to ");
 231         PrintInfo(use);
 232         TRACE("\n");
 233         Node* n = changer_->GetRepresentationFor(input, output, use);
 234         node->ReplaceInput(index, n);
 235       }
 236     }
 237   }
 238
 239   void ProcessRemainingInputs(Node* node, int index) {
 240     DCHECK_GE(index, NodeProperties::PastValueIndex(node));
 241     DCHECK_GE(index, NodeProperties::PastContextIndex(node));
 242     for (int i = std::max(index, NodeProperties::FirstEffectIndex(node));
 243          i < NodeProperties::PastEffectIndex(node); ++i) {
 244       Enqueue(node->InputAt(i));  // Effect inputs: just visit
 245     }
 246     for (int i = std::max(index, NodeProperties::FirstControlIndex(node));
 247          i < NodeProperties::PastControlIndex(node); ++i) {
 248       Enqueue(node->InputAt(i));  // Control inputs: just visit
 249     }
 250   }
 251
 252   // The default, most general visitation case. For {node}, process all value,
 253   // context, frame state, effect, and control inputs, assuming that value
 254   // inputs should have {kRepTagged} representation and can observe all output
 255   // values {kTypeAny}.
 256   void VisitInputs(Node* node) {
 257     int tagged_count = node->op()->ValueInputCount() +
 258                        OperatorProperties::GetContextInputCount(node->op());
 259     // Visit value and context inputs as tagged.
 260     for (int i = 0; i < tagged_count; i++) {
 261       ProcessInput(node, i, kMachAnyTagged);
 262     }
 263     // Only enqueue other inputs (framestates, effects, control).
 264     for (int i = tagged_count; i < node->InputCount(); i++) {
 265       Enqueue(node->InputAt(i));
 266     }
 267     // Assume the output is tagged.
 268     SetOutput(node, kMachAnyTagged);
 269   }
 270
 271   // Helper for binops of the R x L -> O variety.
 272   void VisitBinop(Node* node, MachineTypeUnion left_use,
 273                   MachineTypeUnion right_use, MachineTypeUnion output) {
 274     DCHECK_EQ(2, node->InputCount());
 275     ProcessInput(node, 0, left_use);
 276     ProcessInput(node, 1, right_use);
 277     SetOutput(node, output);
 278   }
 279
 280   // Helper for binops of the I x I -> O variety.
 281   void VisitBinop(Node* node, MachineTypeUnion input_use,
 282                   MachineTypeUnion output) {
 283     VisitBinop(node, input_use, input_use, output);
 284   }
 285
 286   // Helper for unops of the I -> O variety.
 287   void VisitUnop(Node* node, MachineTypeUnion input_use,
 288                  MachineTypeUnion output) {
 289     DCHECK_EQ(1, node->InputCount());
 290     ProcessInput(node, 0, input_use);
 291     SetOutput(node, output);
 292   }
 293
 294   // Helper for leaf nodes.
 295   void VisitLeaf(Node* node, MachineTypeUnion output) {
 296     DCHECK_EQ(0, node->InputCount());
 297     SetOutput(node, output);
 298   }
 299
 300   // Helpers for specific types of binops.
 301   void VisitFloat64Binop(Node* node) {
 302     VisitBinop(node, kMachFloat64, kMachFloat64);
 303   }
 304   void VisitInt32Binop(Node* node) { VisitBinop(node, kMachInt32, kMachInt32); }
 305   void VisitUint32Binop(Node* node) {
 306     VisitBinop(node, kMachUint32, kMachUint32);
 307   }
 308   void VisitInt64Binop(Node* node) { VisitBinop(node, kMachInt64, kMachInt64); }
 309   void VisitUint64Binop(Node* node) {
 310     VisitBinop(node, kMachUint64, kMachUint64);
 311   }
 312   void VisitFloat64Cmp(Node* node) { VisitBinop(node, kMachFloat64, kRepBit); }
 313   void VisitInt32Cmp(Node* node) { VisitBinop(node, kMachInt32, kRepBit); }
 314   void VisitUint32Cmp(Node* node) { VisitBinop(node, kMachUint32, kRepBit); }
 315   void VisitInt64Cmp(Node* node) { VisitBinop(node, kMachInt64, kRepBit); }
 316   void VisitUint64Cmp(Node* node) { VisitBinop(node, kMachUint64, kRepBit); }
 317
 318   // Infer representation for phi-like nodes.
 319   MachineType GetRepresentationForPhi(Node* node, MachineTypeUnion use) {
 320     // Phis adapt to the output representation their uses demand.
 321     Type* upper = NodeProperties::GetBounds(node).upper;
 322     if ((use & kRepMask) == kRepTagged) {
 323       // only tagged uses.
 324       return kRepTagged;
 325     } else if (upper->Is(Type::Integral32())) {
 326       // Integer within [-2^31, 2^32[ range.
 327       if ((use & kRepMask) == kRepFloat64) {
 328         // only float64 uses.
 329         return kRepFloat64;
 330       } else if (upper->Is(Type::Signed32()) || upper->Is(Type::Unsigned32())) {
 331         // multiple uses, but we are within 32 bits range => pick kRepWord32.
 332         return kRepWord32;
 333       } else if (((use & kRepMask) == kRepWord32 &&
 334                   !CanObserveNonWord32(use)) ||
 335                  (use & kTypeMask) == kTypeInt32 ||
 336                  (use & kTypeMask) == kTypeUint32) {
 337         // We only use 32 bits or we use the result consistently.
 338         return kRepWord32;
 339       } else {
 340         return kRepFloat64;
 341       }
 342     } else if (upper->Is(Type::Boolean())) {
 343       // multiple uses => pick kRepBit.
 344       return kRepBit;
 345     } else if (upper->Is(Type::Number())) {
 346       // multiple uses => pick kRepFloat64.
 347       return kRepFloat64;
 348     }
 349     return kRepTagged;
 350   }
 351
 352   // Helper for handling selects.
 353   void VisitSelect(Node* node, MachineTypeUnion use,
 354                    SimplifiedLowering* lowering) {
 355     ProcessInput(node, 0, kRepBit);
 356     MachineType output = GetRepresentationForPhi(node, use);
 357
 358     Type* upper = NodeProperties::GetBounds(node).upper;
 359     MachineType output_type =
 360         static_cast<MachineType>(changer_->TypeFromUpperBound(upper) | output);
 361     SetOutput(node, output_type);
 362
 363     if (lower()) {
 364       // Update the select operator.
 365       SelectParameters p = SelectParametersOf(node->op());
 366       MachineType type = static_cast<MachineType>(output_type);
 367       if (type != p.type()) {
 368         node->set_op(lowering->common()->Select(type, p.hint()));
 369       }
 370
 371       // Convert inputs to the output representation of this select.
 372       ProcessInput(node, 1, output_type);
 373       ProcessInput(node, 2, output_type);
 374     } else {
 375       // Propagate {use} of the select to value inputs.
 376       MachineType use_type =
 377           static_cast<MachineType>((use & kTypeMask) | output);
 378       ProcessInput(node, 1, use_type);
 379       ProcessInput(node, 2, use_type);
 380     }
 381   }
 382
 383   // Helper for handling phis.
 384   void VisitPhi(Node* node, MachineTypeUnion use,
 385                 SimplifiedLowering* lowering) {
 386     MachineType output = GetRepresentationForPhi(node, use);
 387
 388     Type* upper = NodeProperties::GetBounds(node).upper;
 389     MachineType output_type =
 390         static_cast<MachineType>(changer_->TypeFromUpperBound(upper) | output);
 391     SetOutput(node, output_type);
 392
 393     int values = node->op()->ValueInputCount();
 394
 395     if (lower()) {
 396       // Update the phi operator.
 397       MachineType type = static_cast<MachineType>(output_type);
 398       if (type != OpParameter<MachineType>(node)) {
 399         node->set_op(lowering->common()->Phi(type, values));
 400       }
 401
 402       // Convert inputs to the output representation of this phi.
 403       for (int i = 0; i < node->InputCount(); i++) {
 404         ProcessInput(node, i, i < values ? output_type : 0);
 405       }
 406     } else {
 407       // Propagate {use} of the phi to value inputs, and 0 to control.
 408       MachineType use_type =
 409           static_cast<MachineType>((use & kTypeMask) | output);
 410       for (int i = 0; i < node->InputCount(); i++) {
 411         ProcessInput(node, i, i < values ? use_type : 0);
 412       }
 413     }
 414   }
 415
 416   void VisitStateValues(Node* node) {
 417     if (phase_ == PROPAGATE) {
 418       for (int i = 0; i < node->InputCount(); i++) {
 419         Enqueue(node->InputAt(i), kTypeAny);
 420       }
 421     } else {
 422       Zone* zone = jsgraph_->zone();
 423       ZoneVector<MachineType>* types =
 424           new (zone->New(sizeof(ZoneVector<MachineType>)))
 425               ZoneVector<MachineType>(node->InputCount(), zone);
 426       for (int i = 0; i < node->InputCount(); i++) {
 427         MachineTypeUnion input_type = GetInfo(node->InputAt(i))->output;
 428         (*types)[i] = static_cast<MachineType>(input_type);
 429       }
 430       node->set_op(jsgraph_->common()->TypedStateValues(types));
 431     }
 432     SetOutput(node, kMachAnyTagged);
 433   }
 434
 435   const Operator* Int32Op(Node* node) {
 436     return changer_->Int32OperatorFor(node->opcode());
 437   }
 438
 439   const Operator* Uint32Op(Node* node) {
 440     return changer_->Uint32OperatorFor(node->opcode());
 441   }
 442
 443   const Operator* Float64Op(Node* node) {
 444     return changer_->Float64OperatorFor(node->opcode());
 445   }
 446
 447   bool CanLowerToInt32Binop(Node* node, MachineTypeUnion use) {
 448     return BothInputsAre(node, Type::Signed32()) && !CanObserveNonInt32(use);
 449   }
 450
 451   bool CanLowerToInt32AdditiveBinop(Node* node, MachineTypeUnion use) {
 452     return BothInputsAre(node, safe_int_additive_range_) &&
 453            !CanObserveNonInt32(use);
 454   }
 455
 456   bool CanLowerToUint32Binop(Node* node, MachineTypeUnion use) {
 457     return BothInputsAre(node, Type::Unsigned32()) && !CanObserveNonUint32(use);
 458   }
 459
 460   bool CanLowerToUint32AdditiveBinop(Node* node, MachineTypeUnion use) {
 461     return BothInputsAre(node, safe_int_additive_range_) &&
 462            !CanObserveNonUint32(use);
 463   }
 464
 465   bool CanObserveNonWord32(MachineTypeUnion use) {
 466     return (use & ~(kTypeUint32 | kTypeInt32)) != 0;
 467   }
 468
 469   bool CanObserveNonInt32(MachineTypeUnion use) {
 470     return (use & (kTypeUint32 | kTypeNumber | kTypeAny)) != 0;
 471   }
 472
 473   bool CanObserveMinusZero(MachineTypeUnion use) {
 474     // TODO(turbofan): technically Uint32 cannot observe minus zero either.
 475     return (use & (kTypeUint32 | kTypeNumber | kTypeAny)) != 0;
 476   }
 477
 478   bool CanObserveNaN(MachineTypeUnion use) {
 479     return (use & (kTypeNumber | kTypeAny)) != 0;
 480   }
 481
 482   bool CanObserveNonUint32(MachineTypeUnion use) {
 483     return (use & (kTypeInt32 | kTypeNumber | kTypeAny)) != 0;
 484   }
 485
 486   // Dispatching routine for visiting the node {node} with the usage {use}.
 487   // Depending on the operator, propagate new usage info to the inputs.
 488   void VisitNode(Node* node, MachineTypeUnion use,
 489                  SimplifiedLowering* lowering) {
 490     switch (node->opcode()) {
 491       //------------------------------------------------------------------
 492       // Common operators.
 493       //------------------------------------------------------------------
 494       case IrOpcode::kStart:
 495       case IrOpcode::kDead:
 496         return VisitLeaf(node, 0);
 497       case IrOpcode::kParameter: {
 498         // TODO(titzer): use representation from linkage.
 499         Type* upper = NodeProperties::GetBounds(node).upper;
 500         ProcessInput(node, 0, 0);
 501         SetOutput(node, kRepTagged | changer_->TypeFromUpperBound(upper));
 502         return;
 503       }
 504       case IrOpcode::kAlways:
 505         return VisitLeaf(node, kRepBit);
 506       case IrOpcode::kInt32Constant:
 507         return VisitLeaf(node, kRepWord32);
 508       case IrOpcode::kInt64Constant:
 509         return VisitLeaf(node, kRepWord64);
 510       case IrOpcode::kFloat64Constant:
 511         return VisitLeaf(node, kRepFloat64);
 512       case IrOpcode::kExternalConstant:
 513         return VisitLeaf(node, kMachPtr);
 514       case IrOpcode::kNumberConstant:
 515         return VisitLeaf(node, kRepTagged);
 516       case IrOpcode::kHeapConstant:
 517         return VisitLeaf(node, kRepTagged);
 518
 519       case IrOpcode::kBranch:
 520         ProcessInput(node, 0, kRepBit);
 521         Enqueue(NodeProperties::GetControlInput(node, 0));
 522         break;
 523       case IrOpcode::kSwitch:
 524         ProcessInput(node, 0, kRepWord32);
 525         Enqueue(NodeProperties::GetControlInput(node, 0));
 526         break;
 527       case IrOpcode::kSelect:
 528         return VisitSelect(node, use, lowering);
 529       case IrOpcode::kPhi:
 530         return VisitPhi(node, use, lowering);
 531
 532 //------------------------------------------------------------------
 533 // JavaScript operators.
 534 //------------------------------------------------------------------
 535 // For now, we assume that all JS operators were too complex to lower
 536 // to Simplified and that they will always require tagged value inputs
 537 // and produce tagged value outputs.
 538 // TODO(turbofan): it might be possible to lower some JSOperators here,
 539 // but that responsibility really lies in the typed lowering phase.
 540 #define DEFINE_JS_CASE(x) case IrOpcode::k##x:
 541         JS_OP_LIST(DEFINE_JS_CASE)
 542 #undef DEFINE_JS_CASE
 543         VisitInputs(node);
 544         return SetOutput(node, kRepTagged);
 545
 546       //------------------------------------------------------------------
 547       // Simplified operators.
 548       //------------------------------------------------------------------
 549       case IrOpcode::kBooleanNot: {
 550         if (lower()) {
 551           MachineTypeUnion input = GetInfo(node->InputAt(0))->output;
 552           if (input & kRepBit) {
 553             // BooleanNot(x: kRepBit) => Word32Equal(x, #0)
 554             node->set_op(lowering->machine()->Word32Equal());
 555             node->AppendInput(jsgraph_->zone(), jsgraph_->Int32Constant(0));
 556           } else {
 557             // BooleanNot(x: kRepTagged) => WordEqual(x, #false)
 558             node->set_op(lowering->machine()->WordEqual());
 559             node->AppendInput(jsgraph_->zone(), jsgraph_->FalseConstant());
 560           }
 561         } else {
 562           // No input representation requirement; adapt during lowering.
 563           ProcessInput(node, 0, kTypeBool);
 564           SetOutput(node, kRepBit);
 565         }
 566         break;
 567       }
 568       case IrOpcode::kBooleanToNumber: {
 569         if (lower()) {
 570           MachineTypeUnion input = GetInfo(node->InputAt(0))->output;
 571           if (input & kRepBit) {
 572             // BooleanToNumber(x: kRepBit) => x
 573             DeferReplacement(node, node->InputAt(0));
 574           } else {
 575             // BooleanToNumber(x: kRepTagged) => WordEqual(x, #true)
 576             node->set_op(lowering->machine()->WordEqual());
 577             node->AppendInput(jsgraph_->zone(), jsgraph_->TrueConstant());
 578           }
 579         } else {
 580           // No input representation requirement; adapt during lowering.
 581           ProcessInput(node, 0, kTypeBool);
 582           SetOutput(node, kMachInt32);
 583         }
 584         break;
 585       }
 586       case IrOpcode::kNumberEqual:
 587       case IrOpcode::kNumberLessThan:
 588       case IrOpcode::kNumberLessThanOrEqual: {
 589         // Number comparisons reduce to integer comparisons for integer inputs.
 590         if (BothInputsAre(node, Type::Signed32())) {
 591           // => signed Int32Cmp
 592           VisitInt32Cmp(node);
 593           if (lower()) node->set_op(Int32Op(node));
 594         } else if (BothInputsAre(node, Type::Unsigned32())) {
 595           // => unsigned Int32Cmp
 596           VisitUint32Cmp(node);
 597           if (lower()) node->set_op(Uint32Op(node));
 598         } else {
 599           // => Float64Cmp
 600           VisitFloat64Cmp(node);
 601           if (lower()) node->set_op(Float64Op(node));
 602         }
 603         break;
 604       }
 605       case IrOpcode::kNumberAdd:
 606       case IrOpcode::kNumberSubtract: {
 607         // Add and subtract reduce to Int32Add/Sub if the inputs
 608         // are already integers and all uses are truncating.
 609         if (CanLowerToInt32Binop(node, use)) {
 610           // => signed Int32Add/Sub
 611           VisitInt32Binop(node);
 612           if (lower()) node->set_op(Int32Op(node));
 613         } else if (CanLowerToInt32AdditiveBinop(node, use)) {
 614           // => signed Int32Add/Sub, truncating inputs
 615           ProcessTruncateWord32Input(node, 0, kTypeInt32);
 616           ProcessTruncateWord32Input(node, 1, kTypeInt32);
 617           SetOutput(node, kMachInt32);
 618           if (lower()) node->set_op(Int32Op(node));
 619         } else if (CanLowerToUint32Binop(node, use)) {
 620           // => unsigned Int32Add/Sub
 621           VisitUint32Binop(node);
 622           if (lower()) node->set_op(Uint32Op(node));
 623         } else if (CanLowerToUint32AdditiveBinop(node, use)) {
 624           // => signed Int32Add/Sub, truncating inputs
 625           ProcessTruncateWord32Input(node, 0, kTypeUint32);
 626           ProcessTruncateWord32Input(node, 1, kTypeUint32);
 627           SetOutput(node, kMachUint32);
 628           if (lower()) node->set_op(Uint32Op(node));
 629         } else {
 630           // => Float64Add/Sub
 631           VisitFloat64Binop(node);
 632           if (lower()) node->set_op(Float64Op(node));
 633         }
 634         break;
 635       }
 636       case IrOpcode::kNumberMultiply: {
 637         NumberMatcher right(node->InputAt(1));
 638         if (right.IsInRange(-1048576, 1048576)) {  // must fit double mantissa.
 639           if (CanLowerToInt32Binop(node, use)) {
 640             // => signed Int32Mul
 641             VisitInt32Binop(node);
 642             if (lower()) node->set_op(Int32Op(node));
 643             break;
 644           }
 645         }
 646         // => Float64Mul
 647         VisitFloat64Binop(node);
 648         if (lower()) node->set_op(Float64Op(node));
 649         break;
 650       }
 651       case IrOpcode::kNumberDivide: {
 652         if (CanLowerToInt32Binop(node, use)) {
 653           // => signed Int32Div
 654           VisitInt32Binop(node);
 655           if (lower()) DeferReplacement(node, lowering->Int32Div(node));
 656           break;
 657         }
 658         if (BothInputsAre(node, Type::Unsigned32()) && !CanObserveNaN(use)) {
 659           // => unsigned Uint32Div
 660           VisitUint32Binop(node);
 661           if (lower()) DeferReplacement(node, lowering->Uint32Div(node));
 662           break;
 663         }
 664         // => Float64Div
 665         VisitFloat64Binop(node);
 666         if (lower()) node->set_op(Float64Op(node));
 667         break;
 668       }
 669       case IrOpcode::kNumberModulus: {
 670         if (CanLowerToInt32Binop(node, use)) {
 671           // => signed Int32Mod
 672           VisitInt32Binop(node);
 673           if (lower()) DeferReplacement(node, lowering->Int32Mod(node));
 674           break;
 675         }
 676         if (BothInputsAre(node, Type::Unsigned32()) && !CanObserveNaN(use)) {
 677           // => unsigned Uint32Mod
 678           VisitUint32Binop(node);
 679           if (lower()) DeferReplacement(node, lowering->Uint32Mod(node));
 680           break;
 681         }
 682         // => Float64Mod
 683         VisitFloat64Binop(node);
 684         if (lower()) node->set_op(Float64Op(node));
 685         break;
 686       }
 687       case IrOpcode::kNumberToInt32: {
 688         MachineTypeUnion use_rep = use & kRepMask;
 689         Node* input = node->InputAt(0);
 690         Type* in_upper = NodeProperties::GetBounds(input).upper;
 691         MachineTypeUnion in = GetInfo(input)->output;
 692         if (in_upper->Is(Type::Signed32())) {
 693           // If the input has type int32, pass through representation.
 694           VisitUnop(node, kTypeInt32 | use_rep, kTypeInt32 | use_rep);
 695           if (lower()) DeferReplacement(node, node->InputAt(0));
 696         } else if ((in & kTypeMask) == kTypeUint32 ||
 697                    in_upper->Is(Type::Unsigned32())) {
 698           // Just change representation if necessary.
 699           VisitUnop(node, kTypeUint32 | kRepWord32, kTypeInt32 | kRepWord32);
 700           if (lower()) DeferReplacement(node, node->InputAt(0));
 701         } else if ((in & kTypeMask) == kTypeInt32 ||
 702                    (in & kRepMask) == kRepWord32) {
 703           // Just change representation if necessary.
 704           VisitUnop(node, kTypeInt32 | kRepWord32, kTypeInt32 | kRepWord32);
 705           if (lower()) DeferReplacement(node, node->InputAt(0));
 706         } else {
 707           // Require the input in float64 format and perform truncation.
 708           // TODO(turbofan): avoid a truncation with a smi check.
 709           VisitUnop(node, kTypeInt32 | kRepFloat64, kTypeInt32 | kRepWord32);
 710           if (lower())
 711             node->set_op(lowering->machine()->TruncateFloat64ToInt32());
 712         }
 713         break;
 714       }
 715       case IrOpcode::kNumberToUint32: {
 716         MachineTypeUnion use_rep = use & kRepMask;
 717         Node* input = node->InputAt(0);
 718         Type* in_upper = NodeProperties::GetBounds(input).upper;
 719         MachineTypeUnion in = GetInfo(input)->output;
 720         if (in_upper->Is(Type::Unsigned32())) {
 721           // If the input has type uint32, pass through representation.
 722           VisitUnop(node, kTypeUint32 | use_rep, kTypeUint32 | use_rep);
 723           if (lower()) DeferReplacement(node, node->InputAt(0));
 724         } else if ((in & kTypeMask) == kTypeInt32 ||
 725                    in_upper->Is(Type::Signed32())) {
 726           // Just change representation if necessary.
 727           VisitUnop(node, kTypeInt32 | kRepWord32, kTypeUint32 | kRepWord32);
 728           if (lower()) DeferReplacement(node, node->InputAt(0));
 729         } else if ((in & kTypeMask) == kTypeUint32 ||
 730                    (in & kRepMask) == kRepWord32) {
 731           // Just change representation if necessary.
 732           VisitUnop(node, kTypeUint32 | kRepWord32, kTypeUint32 | kRepWord32);
 733           if (lower()) DeferReplacement(node, node->InputAt(0));
 734         } else {
 735           // Require the input in float64 format and perform truncation.
 736           // TODO(turbofan): avoid a truncation with a smi check.
 737           VisitUnop(node, kTypeUint32 | kRepFloat64, kTypeUint32 | kRepWord32);
 738           if (lower())
 739             node->set_op(lowering->machine()->TruncateFloat64ToInt32());
 740         }
 741         break;
 742       }
 743       case IrOpcode::kPlainPrimitiveToNumber: {
 744         VisitUnop(node, kMachAnyTagged, kTypeNumber | kRepTagged);
 745         if (lower()) {
 746           // PlainPrimitiveToNumber(x) => Call(ToNumberStub, x, no-context)
 747           Operator::Properties properties = node->op()->properties();
 748           Callable callable = CodeFactory::ToNumber(jsgraph_->isolate());
 749           CallDescriptor::Flags flags = CallDescriptor::kNoFlags;
 750           CallDescriptor* desc = Linkage::GetStubCallDescriptor(
 751               jsgraph_->isolate(), jsgraph_->zone(), callable.descriptor(), 0,
 752               flags, properties);
 753           node->set_op(jsgraph_->common()->Call(desc));
 754           node->InsertInput(jsgraph_->zone(), 0,
 755                             jsgraph_->HeapConstant(callable.code()));
 756           node->AppendInput(jsgraph_->zone(), jsgraph_->NoContextConstant());
 757         }
 758         break;
 759       }
 760       case IrOpcode::kReferenceEqual: {
 761         VisitBinop(node, kMachAnyTagged, kRepBit);
 762         if (lower()) node->set_op(lowering->machine()->WordEqual());
 763         break;
 764       }
 765       case IrOpcode::kStringEqual: {
 766         VisitBinop(node, kMachAnyTagged, kRepBit);
 767         if (lower()) lowering->DoStringEqual(node);
 768         break;
 769       }
 770       case IrOpcode::kStringLessThan: {
 771         VisitBinop(node, kMachAnyTagged, kRepBit);
 772         if (lower()) lowering->DoStringLessThan(node);
 773         break;
 774       }
 775       case IrOpcode::kStringLessThanOrEqual: {
 776         VisitBinop(node, kMachAnyTagged, kRepBit);
 777         if (lower()) lowering->DoStringLessThanOrEqual(node);
 778         break;
 779       }
 780       case IrOpcode::kStringAdd: {
 781         VisitBinop(node, kMachAnyTagged, kMachAnyTagged);
 782         if (lower()) lowering->DoStringAdd(node);
 783         break;
 784       }
 785       case IrOpcode::kLoadField: {
 786         FieldAccess access = FieldAccessOf(node->op());
 787         ProcessInput(node, 0, changer_->TypeForBasePointer(access));
 788         ProcessRemainingInputs(node, 1);
 789         SetOutput(node, access.machine_type);
 790         if (lower()) lowering->DoLoadField(node);
 791         break;
 792       }
 793       case IrOpcode::kStoreField: {
 794         FieldAccess access = FieldAccessOf(node->op());
 795         ProcessInput(node, 0, changer_->TypeForBasePointer(access));
 796         ProcessInput(node, 1, access.machine_type);
 797         ProcessRemainingInputs(node, 2);
 798         SetOutput(node, 0);
 799         if (lower()) lowering->DoStoreField(node);
 800         break;
 801       }
 802       case IrOpcode::kLoadBuffer: {
 803         BufferAccess access = BufferAccessOf(node->op());
 804         ProcessInput(node, 0, kMachPtr);    // buffer
 805         ProcessInput(node, 1, kMachInt32);  // offset
 806         ProcessInput(node, 2, kMachInt32);  // length
 807         ProcessRemainingInputs(node, 3);
 808         // Tagged overrides everything if we have to do a typed array bounds
 809         // check, because we may need to return undefined then.
 810         MachineType output_type;
 811         if (use & kRepTagged) {
 812           output_type = kMachAnyTagged;
 813         } else if (use & kRepFloat64) {
 814           if (access.machine_type() & kRepFloat32) {
 815             output_type = access.machine_type();
 816           } else {
 817             output_type = kMachFloat64;
 818           }
 819         } else if (use & kRepFloat32) {
 820           output_type = kMachFloat32;
 821         } else {
 822           output_type = access.machine_type();
 823         }
 824         SetOutput(node, output_type);
 825         if (lower()) lowering->DoLoadBuffer(node, output_type, changer_);
 826         break;
 827       }
 828       case IrOpcode::kStoreBuffer: {
 829         BufferAccess access = BufferAccessOf(node->op());
 830         ProcessInput(node, 0, kMachPtr);               // buffer
 831         ProcessInput(node, 1, kMachInt32);             // offset
 832         ProcessInput(node, 2, kMachInt32);             // length
 833         ProcessInput(node, 3, access.machine_type());  // value
 834         ProcessRemainingInputs(node, 4);
 835         SetOutput(node, 0);
 836         if (lower()) lowering->DoStoreBuffer(node);
 837         break;
 838       }
 839       case IrOpcode::kLoadElement: {
 840         ElementAccess access = ElementAccessOf(node->op());
 841         ProcessInput(node, 0, changer_->TypeForBasePointer(access));  // base
 842         ProcessInput(node, 1, kMachInt32);                            // index
 843         ProcessRemainingInputs(node, 2);
 844         SetOutput(node, access.machine_type);
 845         if (lower()) lowering->DoLoadElement(node);
 846         break;
 847       }
 848       case IrOpcode::kStoreElement: {
 849         ElementAccess access = ElementAccessOf(node->op());
 850         ProcessInput(node, 0, changer_->TypeForBasePointer(access));  // base
 851         ProcessInput(node, 1, kMachInt32);                            // index
 852         ProcessInput(node, 2, access.machine_type);                   // value
 853         ProcessRemainingInputs(node, 3);
 854         SetOutput(node, 0);
 855         if (lower()) lowering->DoStoreElement(node);
 856         break;
 857       }
 858       case IrOpcode::kObjectIsSmi: {
 859         ProcessInput(node, 0, kMachAnyTagged);
 860         SetOutput(node, kRepBit | kTypeBool);
 861         if (lower()) {
 862           Node* is_tagged = jsgraph_->graph()->NewNode(
 863               jsgraph_->machine()->WordAnd(), node->InputAt(0),
 864               jsgraph_->IntPtrConstant(kSmiTagMask));
 865           Node* is_smi = jsgraph_->graph()->NewNode(
 866               jsgraph_->machine()->WordEqual(), is_tagged,
 867               jsgraph_->IntPtrConstant(kSmiTag));
 868           DeferReplacement(node, is_smi);
 869         }
 870         break;
 871       }
 872       case IrOpcode::kObjectIsNonNegativeSmi: {
 873         ProcessInput(node, 0, kMachAnyTagged);
 874         SetOutput(node, kRepBit | kTypeBool);
 875         if (lower()) {
 876           Node* is_tagged = jsgraph_->graph()->NewNode(
 877               jsgraph_->machine()->WordAnd(), node->InputAt(0),
 878               jsgraph_->IntPtrConstant(kSmiTagMask));
 879           Node* is_smi = jsgraph_->graph()->NewNode(
 880               jsgraph_->machine()->WordEqual(), is_tagged,
 881               jsgraph_->IntPtrConstant(kSmiTag));
 882           Node* is_non_neg = jsgraph_->graph()->NewNode(
 883               jsgraph_->machine()->IntLessThanOrEqual(),
 884               jsgraph_->IntPtrConstant(0), node->InputAt(0));
 885           Node* is_non_neg_smi = jsgraph_->graph()->NewNode(
 886               jsgraph_->machine()->Word32And(), is_smi, is_non_neg);
 887           DeferReplacement(node, is_non_neg_smi);
 888         }
 889         break;
 890       }
 891
 892       //------------------------------------------------------------------
 893       // Machine-level operators.
 894       //------------------------------------------------------------------
 895       case IrOpcode::kLoad: {
 896         // TODO(titzer): machine loads/stores need to know BaseTaggedness!?
 897         MachineTypeUnion tBase = kRepTagged | kMachPtr;
 898         LoadRepresentation rep = OpParameter<LoadRepresentation>(node);
 899         ProcessInput(node, 0, tBase);   // pointer or object
 900         ProcessInput(node, 1, kMachIntPtr);  // index
 901         ProcessRemainingInputs(node, 2);
 902         SetOutput(node, rep);
 903         break;
 904       }
 905       case IrOpcode::kStore: {
 906         // TODO(titzer): machine loads/stores need to know BaseTaggedness!?
 907         MachineTypeUnion tBase = kRepTagged | kMachPtr;
 908         StoreRepresentation rep = OpParameter<StoreRepresentation>(node);
 909         ProcessInput(node, 0, tBase);   // pointer or object
 910         ProcessInput(node, 1, kMachIntPtr);  // index
 911         ProcessInput(node, 2, rep.machine_type());
 912         ProcessRemainingInputs(node, 3);
 913         SetOutput(node, 0);
 914         break;
 915       }
 916       case IrOpcode::kWord32Shr:
 917         // We output unsigned int32 for shift right because JavaScript.
 918         return VisitBinop(node, kMachUint32, kMachUint32);
 919       case IrOpcode::kWord32And:
 920       case IrOpcode::kWord32Or:
 921       case IrOpcode::kWord32Xor:
 922       case IrOpcode::kWord32Shl:
 923       case IrOpcode::kWord32Sar:
 924         // We use signed int32 as the output type for these word32 operations,
 925         // though the machine bits are the same for either signed or unsigned,
 926         // because JavaScript considers the result from these operations signed.
 927         return VisitBinop(node, kRepWord32, kRepWord32 | kTypeInt32);
 928       case IrOpcode::kWord32Equal:
 929         return VisitBinop(node, kRepWord32, kRepBit);
 930
 931       case IrOpcode::kWord32Clz:
 932         return VisitUnop(node, kMachUint32, kMachUint32);
 933
 934       case IrOpcode::kInt32Add:
 935       case IrOpcode::kInt32Sub:
 936       case IrOpcode::kInt32Mul:
 937       case IrOpcode::kInt32MulHigh:
 938       case IrOpcode::kInt32Div:
 939       case IrOpcode::kInt32Mod:
 940         return VisitInt32Binop(node);
 941       case IrOpcode::kUint32Div:
 942       case IrOpcode::kUint32Mod:
 943       case IrOpcode::kUint32MulHigh:
 944         return VisitUint32Binop(node);
 945       case IrOpcode::kInt32LessThan:
 946       case IrOpcode::kInt32LessThanOrEqual:
 947         return VisitInt32Cmp(node);
 948
 949       case IrOpcode::kUint32LessThan:
 950       case IrOpcode::kUint32LessThanOrEqual:
 951         return VisitUint32Cmp(node);
 952
 953       case IrOpcode::kInt64Add:
 954       case IrOpcode::kInt64Sub:
 955       case IrOpcode::kInt64Mul:
 956       case IrOpcode::kInt64Div:
 957       case IrOpcode::kInt64Mod:
 958         return VisitInt64Binop(node);
 959       case IrOpcode::kInt64LessThan:
 960       case IrOpcode::kInt64LessThanOrEqual:
 961         return VisitInt64Cmp(node);
 962
 963       case IrOpcode::kUint64LessThan:
 964         return VisitUint64Cmp(node);
 965
 966       case IrOpcode::kUint64Div:
 967       case IrOpcode::kUint64Mod:
 968         return VisitUint64Binop(node);
 969
 970       case IrOpcode::kWord64And:
 971       case IrOpcode::kWord64Or:
 972       case IrOpcode::kWord64Xor:
 973       case IrOpcode::kWord64Shl:
 974       case IrOpcode::kWord64Shr:
 975       case IrOpcode::kWord64Sar:
 976         return VisitBinop(node, kRepWord64, kRepWord64);
 977       case IrOpcode::kWord64Equal:
 978         return VisitBinop(node, kRepWord64, kRepBit);
 979
 980       case IrOpcode::kChangeInt32ToInt64:
 981         return VisitUnop(node, kTypeInt32 | kRepWord32,
 982                          kTypeInt32 | kRepWord64);
 983       case IrOpcode::kChangeUint32ToUint64:
 984         return VisitUnop(node, kTypeUint32 | kRepWord32,
 985                          kTypeUint32 | kRepWord64);
 986       case IrOpcode::kTruncateFloat64ToFloat32:
 987         return VisitUnop(node, kTypeNumber | kRepFloat64,
 988                          kTypeNumber | kRepFloat32);
 989       case IrOpcode::kTruncateInt64ToInt32:
 990         // TODO(titzer): Is kTypeInt32 correct here?
 991         return VisitUnop(node, kTypeInt32 | kRepWord64,
 992                          kTypeInt32 | kRepWord32);
 993
 994       case IrOpcode::kChangeFloat32ToFloat64:
 995         return VisitUnop(node, kTypeNumber | kRepFloat32,
 996                          kTypeNumber | kRepFloat64);
 997       case IrOpcode::kChangeInt32ToFloat64:
 998         return VisitUnop(node, kTypeInt32 | kRepWord32,
 999                          kTypeInt32 | kRepFloat64);
1000       case IrOpcode::kChangeUint32ToFloat64:
1001         return VisitUnop(node, kTypeUint32 | kRepWord32,
1002                          kTypeUint32 | kRepFloat64);
1003       case IrOpcode::kChangeFloat64ToInt32:
1004         return VisitUnop(node, kTypeInt32 | kRepFloat64,
1005                          kTypeInt32 | kRepWord32);
1006       case IrOpcode::kChangeFloat64ToUint32:
1007         return VisitUnop(node, kTypeUint32 | kRepFloat64,
1008                          kTypeUint32 | kRepWord32);
1009
1010       case IrOpcode::kFloat64Add:
1011       case IrOpcode::kFloat64Sub:
1012       case IrOpcode::kFloat64Mul:
1013       case IrOpcode::kFloat64Div:
1014       case IrOpcode::kFloat64Mod:
1015       case IrOpcode::kFloat64Min:
1016         return VisitFloat64Binop(node);
1017       case IrOpcode::kFloat64Sqrt:
1018       case IrOpcode::kFloat64RoundDown:
1019       case IrOpcode::kFloat64RoundTruncate:
1020       case IrOpcode::kFloat64RoundTiesAway:
1021         return VisitUnop(node, kMachFloat64, kMachFloat64);
1022       case IrOpcode::kFloat64Equal:
1023       case IrOpcode::kFloat64LessThan:
1024       case IrOpcode::kFloat64LessThanOrEqual:
1025         return VisitFloat64Cmp(node);
1026       case IrOpcode::kFloat64ExtractLowWord32:
1027       case IrOpcode::kFloat64ExtractHighWord32:
1028         return VisitUnop(node, kMachFloat64, kMachInt32);
1029       case IrOpcode::kFloat64InsertLowWord32:
1030       case IrOpcode::kFloat64InsertHighWord32:
1031         return VisitBinop(node, kMachFloat64, kMachInt32, kMachFloat64);
1032       case IrOpcode::kLoadStackPointer:
1033         return VisitLeaf(node, kMachPtr);
1034       case IrOpcode::kStateValues:
1035         VisitStateValues(node);
1036         break;
1037       default:
1038         VisitInputs(node);
1039         break;
1040     }
1041   }
1042
1043   void DeferReplacement(Node* node, Node* replacement) {
1044     TRACE("defer replacement #%d:%s with #%d:%s\n", node->id(),
1045           node->op()->mnemonic(), replacement->id(),
1046           replacement->op()->mnemonic());
1047
1048     if (replacement->id() < count_ &&
1049         GetInfo(replacement)->output == GetInfo(node)->output) {
1050       // Replace with a previously existing node eagerly only if the type is the
1051       // same.
1052       node->ReplaceUses(replacement);
1053     } else {
1054       // Otherwise, we are replacing a node with a representation change.
1055       // Such a substitution must be done after all lowering is done, because
1056       // changing the type could confuse the representation change
1057       // insertion for uses of the node.
1058       replacements_.push_back(node);
1059       replacements_.push_back(replacement);
1060     }
1061     node->NullAllInputs();  // Node is now dead.
1062   }
1063
1064   void PrintUseInfo(Node* node) {
1065     TRACE("#%d:%-20s ", node->id(), node->op()->mnemonic());
1066     PrintInfo(GetUseInfo(node));
1067     TRACE("\n");
1068   }
1069
1070   void PrintInfo(MachineTypeUnion info) {
1071     if (FLAG_trace_representation) {
1072       OFStream os(stdout);
1073       os << static_cast<MachineType>(info);
1074     }
1075   }
1076
1077  private:
1078   JSGraph* jsgraph_;
1079   int count_;                       // number of nodes in the graph
1080   NodeInfo* info_;                  // node id -> usage information
1081   NodeVector nodes_;                // collected nodes
1082   NodeVector replacements_;         // replacements to be done after lowering
1083   Phase phase_;                     // current phase of algorithm
1084   RepresentationChanger* changer_;  // for inserting representation changes
1085   ZoneQueue<Node*> queue_;          // queue for traversing the graph
1086   // TODO(danno): RepresentationSelector shouldn't know anything about the
1087   // source positions table, but must for now since there currently is no other
1088   // way to pass down source position information to nodes created during
1089   // lowering. Once this phase becomes a vanilla reducer, it should get source
1090   // position information via the SourcePositionWrapper like all other reducers.
1091   SourcePositionTable* source_positions_;
1092   Type* safe_int_additive_range_;
1093
1094   NodeInfo* GetInfo(Node* node) {
1095     DCHECK(node->id() >= 0);
1096     DCHECK(node->id() < count_);
1097     return &info_[node->id()];
1098   }
1099
1100   MachineTypeUnion GetUseInfo(Node* node) { return GetInfo(node)->use; }
1101 };
1102
1103
1104 Node* SimplifiedLowering::IsTagged(Node* node) {
1105   // TODO(titzer): factor this out to a TaggingScheme abstraction.
1106   STATIC_ASSERT(kSmiTagMask == 1);  // Only works if tag is the low bit.
1107   return graph()->NewNode(machine()->WordAnd(), node,
1108                           jsgraph()->Int32Constant(kSmiTagMask));
1109 }
1110
1111
1112 void SimplifiedLowering::LowerAllNodes() {
1113   SimplifiedOperatorBuilder simplified(graph()->zone());
1114   RepresentationChanger changer(jsgraph(), &simplified, jsgraph()->isolate());
1115   RepresentationSelector selector(jsgraph(), zone_, &changer,
1116                                   source_positions_);
1117   selector.Run(this);
1118 }
1119
1120
1121 Node* SimplifiedLowering::Untag(Node* node) {
1122   // TODO(titzer): factor this out to a TaggingScheme abstraction.
1123   Node* shift_amount = jsgraph()->Int32Constant(kSmiTagSize + kSmiShiftSize);
1124   return graph()->NewNode(machine()->WordSar(), node, shift_amount);
1125 }
1126
1127
1128 Node* SimplifiedLowering::SmiTag(Node* node) {
1129   // TODO(titzer): factor this out to a TaggingScheme abstraction.
1130   Node* shift_amount = jsgraph()->Int32Constant(kSmiTagSize + kSmiShiftSize);
1131   return graph()->NewNode(machine()->WordShl(), node, shift_amount);
1132 }
1133
1134
1135 Node* SimplifiedLowering::OffsetMinusTagConstant(int32_t offset) {
1136   return jsgraph()->Int32Constant(offset - kHeapObjectTag);
1137 }
1138
1139
1140 namespace {
1141
1142 WriteBarrierKind ComputeWriteBarrierKind(BaseTaggedness base_is_tagged,
1143                                          MachineType representation,
1144                                          Type* type) {
1145   if (type->Is(Type::TaggedSigned())) {
1146     // Write barriers are only for writes of heap objects.
1147     return kNoWriteBarrier;
1148   }
1149   if (base_is_tagged == kTaggedBase &&
1150       RepresentationOf(representation) == kRepTagged) {
1151     // Write barriers are only for writes into heap objects (i.e. tagged base).
1152     return kFullWriteBarrier;
1153   }
1154   return kNoWriteBarrier;
1155 }
1156
1157 }  // namespace
1158
1159
1160 void SimplifiedLowering::DoLoadField(Node* node) {
1161   const FieldAccess& access = FieldAccessOf(node->op());
1162   node->set_op(machine()->Load(access.machine_type));
1163   Node* offset = jsgraph()->IntPtrConstant(access.offset - access.tag());
1164   node->InsertInput(graph()->zone(), 1, offset);
1165 }
1166
1167
1168 void SimplifiedLowering::DoStoreField(Node* node) {
1169   const FieldAccess& access = FieldAccessOf(node->op());
1170   Type* type = NodeProperties::GetBounds(node->InputAt(1)).upper;
1171   WriteBarrierKind kind =
1172       ComputeWriteBarrierKind(access.base_is_tagged, access.machine_type, type);
1173   node->set_op(
1174       machine()->Store(StoreRepresentation(access.machine_type, kind)));
1175   Node* offset = jsgraph()->IntPtrConstant(access.offset - access.tag());
1176   node->InsertInput(graph()->zone(), 1, offset);
1177 }
1178
1179
1180 Node* SimplifiedLowering::ComputeIndex(const ElementAccess& access,
1181                                        Node* const key) {
1182   Node* index = key;
1183   const int element_size_shift = ElementSizeLog2Of(access.machine_type);
1184   if (element_size_shift) {
1185     index = graph()->NewNode(machine()->Word32Shl(), index,
1186                              jsgraph()->Int32Constant(element_size_shift));
1187   }
1188   const int fixed_offset = access.header_size - access.tag();
1189   if (fixed_offset) {
1190     index = graph()->NewNode(machine()->Int32Add(), index,
1191                              jsgraph()->Int32Constant(fixed_offset));
1192   }
1193   if (machine()->Is64()) {
1194     // TODO(turbofan): This is probably only correct for typed arrays, and only
1195     // if the typed arrays are at most 2GiB in size, which happens to match
1196     // exactly our current situation.
1197     index = graph()->NewNode(machine()->ChangeUint32ToUint64(), index);
1198   }
1199   return index;
1200 }
1201
1202
1203 void SimplifiedLowering::DoLoadBuffer(Node* node, MachineType output_type,
1204                                       RepresentationChanger* changer) {
1205   DCHECK_EQ(IrOpcode::kLoadBuffer, node->opcode());
1206   DCHECK_NE(kMachNone, RepresentationOf(output_type));
1207   MachineType const type = BufferAccessOf(node->op()).machine_type();
1208   if (output_type != type) {
1209     Node* const buffer = node->InputAt(0);
1210     Node* const offset = node->InputAt(1);
1211     Node* const length = node->InputAt(2);
1212     Node* const effect = node->InputAt(3);
1213     Node* const control = node->InputAt(4);
1214     Node* const index =
1215         machine()->Is64()
1216             ? graph()->NewNode(machine()->ChangeUint32ToUint64(), offset)
1217             : offset;
1218
1219     Node* check = graph()->NewNode(machine()->Uint32LessThan(), offset, length);
1220     Node* branch =
1221         graph()->NewNode(common()->Branch(BranchHint::kTrue), check, control);
1222
1223     Node* if_true = graph()->NewNode(common()->IfTrue(), branch);
1224     Node* etrue =
1225         graph()->NewNode(machine()->Load(type), buffer, index, effect, if_true);
1226     Node* vtrue = changer->GetRepresentationFor(etrue, type, output_type);
1227
1228     Node* if_false = graph()->NewNode(common()->IfFalse(), branch);
1229     Node* efalse = effect;
1230     Node* vfalse;
1231     if (output_type & kRepTagged) {
1232       vfalse = jsgraph()->UndefinedConstant();
1233     } else if (output_type & kRepFloat64) {
1234       vfalse =
1235           jsgraph()->Float64Constant(std::numeric_limits<double>::quiet_NaN());
1236     } else if (output_type & kRepFloat32) {
1237       vfalse =
1238           jsgraph()->Float32Constant(std::numeric_limits<float>::quiet_NaN());
1239     } else {
1240       vfalse = jsgraph()->Int32Constant(0);
1241     }
1242
1243     Node* merge = graph()->NewNode(common()->Merge(2), if_true, if_false);
1244     Node* ephi = graph()->NewNode(common()->EffectPhi(2), etrue, efalse, merge);
1245
1246     // Replace effect uses of {node} with the {ephi}.
1247     NodeProperties::ReplaceWithValue(node, node, ephi);
1248
1249     // Turn the {node} into a Phi.
1250     node->set_op(common()->Phi(output_type, 2));
1251     node->ReplaceInput(0, vtrue);
1252     node->ReplaceInput(1, vfalse);
1253     node->ReplaceInput(2, merge);
1254     node->TrimInputCount(3);
1255   } else {
1256     node->set_op(machine()->CheckedLoad(type));
1257   }
1258 }
1259
1260
1261 void SimplifiedLowering::DoStoreBuffer(Node* node) {
1262   DCHECK_EQ(IrOpcode::kStoreBuffer, node->opcode());
1263   MachineType const type = BufferAccessOf(node->op()).machine_type();
1264   node->set_op(machine()->CheckedStore(type));
1265 }
1266
1267
1268 void SimplifiedLowering::DoLoadElement(Node* node) {
1269   const ElementAccess& access = ElementAccessOf(node->op());
1270   node->set_op(machine()->Load(access.machine_type));
1271   node->ReplaceInput(1, ComputeIndex(access, node->InputAt(1)));
1272 }
1273
1274
1275 void SimplifiedLowering::DoStoreElement(Node* node) {
1276   const ElementAccess& access = ElementAccessOf(node->op());
1277   Type* type = NodeProperties::GetBounds(node->InputAt(2)).upper;
1278   node->set_op(machine()->Store(
1279       StoreRepresentation(access.machine_type,
1280                           ComputeWriteBarrierKind(access.base_is_tagged,
1281                                                   access.machine_type, type))));
1282   node->ReplaceInput(1, ComputeIndex(access, node->InputAt(1)));
1283 }
1284
1285
1286 void SimplifiedLowering::DoStringAdd(Node* node) {
1287   Operator::Properties properties = node->op()->properties();
1288   Callable callable = CodeFactory::StringAdd(
1289       jsgraph()->isolate(), STRING_ADD_CHECK_NONE, NOT_TENURED);
1290   CallDescriptor::Flags flags = CallDescriptor::kNoFlags;
1291   CallDescriptor* desc = Linkage::GetStubCallDescriptor(
1292       jsgraph()->isolate(), zone(), callable.descriptor(), 0, flags,
1293       properties);
1294   node->set_op(common()->Call(desc));
1295   node->InsertInput(graph()->zone(), 0,
1296                     jsgraph()->HeapConstant(callable.code()));
1297   node->AppendInput(graph()->zone(), jsgraph()->UndefinedConstant());
1298   node->AppendInput(graph()->zone(), graph()->start());
1299   node->AppendInput(graph()->zone(), graph()->start());
1300 }
1301
1302
1303 Node* SimplifiedLowering::StringComparison(Node* node, bool requires_ordering) {
1304   CEntryStub stub(jsgraph()->isolate(), 1);
1305   Runtime::FunctionId f =
1306       requires_ordering ? Runtime::kStringCompareRT : Runtime::kStringEquals;
1307   ExternalReference ref(f, jsgraph()->isolate());
1308   Operator::Properties props = node->op()->properties();
1309   // TODO(mstarzinger): We should call StringCompareStub here instead, once an
1310   // interface descriptor is available for it.
1311   CallDescriptor* desc = Linkage::GetRuntimeCallDescriptor(zone(), f, 2, props);
1312   return graph()->NewNode(common()->Call(desc),
1313                           jsgraph()->HeapConstant(stub.GetCode()),
1314                           NodeProperties::GetValueInput(node, 0),
1315                           NodeProperties::GetValueInput(node, 1),
1316                           jsgraph()->ExternalConstant(ref),
1317                           jsgraph()->Int32Constant(2),
1318                           jsgraph()->UndefinedConstant());
1319 }
1320
1321
1322 Node* SimplifiedLowering::Int32Div(Node* const node) {
1323   Int32BinopMatcher m(node);
1324   Node* const zero = jsgraph()->Int32Constant(0);
1325   Node* const minus_one = jsgraph()->Int32Constant(-1);
1326   Node* const lhs = m.left().node();
1327   Node* const rhs = m.right().node();
1328
1329   if (m.right().Is(-1)) {
1330     return graph()->NewNode(machine()->Int32Sub(), zero, lhs);
1331   } else if (m.right().Is(0)) {
1332     return rhs;
1333   } else if (machine()->Int32DivIsSafe() || m.right().HasValue()) {
1334     return graph()->NewNode(machine()->Int32Div(), lhs, rhs, graph()->start());
1335   }
1336
1337   // General case for signed integer division.
1338   //
1339   //    if 0 < rhs then
1340   //      lhs / rhs
1341   //    else
1342   //      if rhs < -1 then
1343   //        lhs / rhs
1344   //      else if rhs == 0 then
1345   //        0
1346   //      else
1347   //        0 - lhs
1348   //
1349   // Note: We do not use the Diamond helper class here, because it really hurts
1350   // readability with nested diamonds.
1351   const Operator* const merge_op = common()->Merge(2);
1352   const Operator* const phi_op = common()->Phi(kMachInt32, 2);
1353
1354   Node* check0 = graph()->NewNode(machine()->Int32LessThan(), zero, rhs);
1355   Node* branch0 = graph()->NewNode(common()->Branch(BranchHint::kTrue), check0,
1356                                    graph()->start());
1357
1358   Node* if_true0 = graph()->NewNode(common()->IfTrue(), branch0);
1359   Node* true0 = graph()->NewNode(machine()->Int32Div(), lhs, rhs, if_true0);
1360
1361   Node* if_false0 = graph()->NewNode(common()->IfFalse(), branch0);
1362   Node* false0;
1363   {
1364     Node* check1 = graph()->NewNode(machine()->Int32LessThan(), rhs, minus_one);
1365     Node* branch1 = graph()->NewNode(common()->Branch(), check1, if_false0);
1366
1367     Node* if_true1 = graph()->NewNode(common()->IfTrue(), branch1);
1368     Node* true1 = graph()->NewNode(machine()->Int32Div(), lhs, rhs, if_true1);
1369
1370     Node* if_false1 = graph()->NewNode(common()->IfFalse(), branch1);
1371     Node* false1;
1372     {
1373       Node* check2 = graph()->NewNode(machine()->Word32Equal(), rhs, zero);
1374       Node* branch2 = graph()->NewNode(common()->Branch(), check2, if_false1);
1375
1376       Node* if_true2 = graph()->NewNode(common()->IfTrue(), branch2);
1377       Node* true2 = zero;
1378
1379       Node* if_false2 = graph()->NewNode(common()->IfFalse(), branch2);
1380       Node* false2 = graph()->NewNode(machine()->Int32Sub(), zero, lhs);
1381
1382       if_false1 = graph()->NewNode(merge_op, if_true2, if_false2);
1383       false1 = graph()->NewNode(phi_op, true2, false2, if_false1);
1384     }
1385
1386     if_false0 = graph()->NewNode(merge_op, if_true1, if_false1);
1387     false0 = graph()->NewNode(phi_op, true1, false1, if_false0);
1388   }
1389
1390   Node* merge0 = graph()->NewNode(merge_op, if_true0, if_false0);
1391   return graph()->NewNode(phi_op, true0, false0, merge0);
1392 }
1393
1394
1395 Node* SimplifiedLowering::Int32Mod(Node* const node) {
1396   Int32BinopMatcher m(node);
1397   Node* const zero = jsgraph()->Int32Constant(0);
1398   Node* const minus_one = jsgraph()->Int32Constant(-1);
1399   Node* const lhs = m.left().node();
1400   Node* const rhs = m.right().node();
1401
1402   if (m.right().Is(-1) || m.right().Is(0)) {
1403     return zero;
1404   } else if (m.right().HasValue()) {
1405     return graph()->NewNode(machine()->Int32Mod(), lhs, rhs, graph()->start());
1406   }
1407
1408   // General case for signed integer modulus, with optimization for (unknown)
1409   // power of 2 right hand side.
1410   //
1411   //   if 0 < rhs then
1412   //     msk = rhs - 1
1413   //     if rhs & msk != 0 then
1414   //       lhs % rhs
1415   //     else
1416   //       if lhs < 0 then
1417   //         -(-lhs & msk)
1418   //       else
1419   //         lhs & msk
1420   //   else
1421   //     if rhs < -1 then
1422   //       lhs % rhs
1423   //     else
1424   //       zero
1425   //
1426   // Note: We do not use the Diamond helper class here, because it really hurts
1427   // readability with nested diamonds.
1428   const Operator* const merge_op = common()->Merge(2);
1429   const Operator* const phi_op = common()->Phi(kMachInt32, 2);
1430
1431   Node* check0 = graph()->NewNode(machine()->Int32LessThan(), zero, rhs);
1432   Node* branch0 = graph()->NewNode(common()->Branch(BranchHint::kTrue), check0,
1433                                    graph()->start());
1434
1435   Node* if_true0 = graph()->NewNode(common()->IfTrue(), branch0);
1436   Node* true0;
1437   {
1438     Node* msk = graph()->NewNode(machine()->Int32Add(), rhs, minus_one);
1439
1440     Node* check1 = graph()->NewNode(machine()->Word32And(), rhs, msk);
1441     Node* branch1 = graph()->NewNode(common()->Branch(), check1, if_true0);
1442
1443     Node* if_true1 = graph()->NewNode(common()->IfTrue(), branch1);
1444     Node* true1 = graph()->NewNode(machine()->Int32Mod(), lhs, rhs, if_true1);
1445
1446     Node* if_false1 = graph()->NewNode(common()->IfFalse(), branch1);
1447     Node* false1;
1448     {
1449       Node* check2 = graph()->NewNode(machine()->Int32LessThan(), lhs, zero);
1450       Node* branch2 = graph()->NewNode(common()->Branch(BranchHint::kFalse),
1451                                        check2, if_false1);
1452
1453       Node* if_true2 = graph()->NewNode(common()->IfTrue(), branch2);
1454       Node* true2 = graph()->NewNode(
1455           machine()->Int32Sub(), zero,
1456           graph()->NewNode(machine()->Word32And(),
1457                            graph()->NewNode(machine()->Int32Sub(), zero, lhs),
1458                            msk));
1459
1460       Node* if_false2 = graph()->NewNode(common()->IfFalse(), branch2);
1461       Node* false2 = graph()->NewNode(machine()->Word32And(), lhs, msk);
1462
1463       if_false1 = graph()->NewNode(merge_op, if_true2, if_false2);
1464       false1 = graph()->NewNode(phi_op, true2, false2, if_false1);
1465     }
1466
1467     if_true0 = graph()->NewNode(merge_op, if_true1, if_false1);
1468     true0 = graph()->NewNode(phi_op, true1, false1, if_true0);
1469   }
1470
1471   Node* if_false0 = graph()->NewNode(common()->IfFalse(), branch0);
1472   Node* false0;
1473   {
1474     Node* check1 = graph()->NewNode(machine()->Int32LessThan(), rhs, minus_one);
1475     Node* branch1 = graph()->NewNode(common()->Branch(BranchHint::kTrue),
1476                                      check1, if_false0);
1477
1478     Node* if_true1 = graph()->NewNode(common()->IfTrue(), branch1);
1479     Node* true1 = graph()->NewNode(machine()->Int32Mod(), lhs, rhs, if_true1);
1480
1481     Node* if_false1 = graph()->NewNode(common()->IfFalse(), branch1);
1482     Node* false1 = zero;
1483
1484     if_false0 = graph()->NewNode(merge_op, if_true1, if_false1);
1485     false0 = graph()->NewNode(phi_op, true1, false1, if_false0);
1486   }
1487
1488   Node* merge0 = graph()->NewNode(merge_op, if_true0, if_false0);
1489   return graph()->NewNode(phi_op, true0, false0, merge0);
1490 }
1491
1492
1493 Node* SimplifiedLowering::Uint32Div(Node* const node) {
1494   Uint32BinopMatcher m(node);
1495   Node* const zero = jsgraph()->Uint32Constant(0);
1496   Node* const lhs = m.left().node();
1497   Node* const rhs = m.right().node();
1498
1499   if (m.right().Is(0)) {
1500     return zero;
1501   } else if (machine()->Uint32DivIsSafe() || m.right().HasValue()) {
1502     return graph()->NewNode(machine()->Uint32Div(), lhs, rhs, graph()->start());
1503   }
1504
1505   Node* check = graph()->NewNode(machine()->Word32Equal(), rhs, zero);
1506   Diamond d(graph(), common(), check, BranchHint::kFalse);
1507   Node* div = graph()->NewNode(machine()->Uint32Div(), lhs, rhs, d.if_false);
1508   return d.Phi(kMachUint32, zero, div);
1509 }
1510
1511
1512 Node* SimplifiedLowering::Uint32Mod(Node* const node) {
1513   Uint32BinopMatcher m(node);
1514   Node* const minus_one = jsgraph()->Int32Constant(-1);
1515   Node* const zero = jsgraph()->Uint32Constant(0);
1516   Node* const lhs = m.left().node();
1517   Node* const rhs = m.right().node();
1518
1519   if (m.right().Is(0)) {
1520     return zero;
1521   } else if (m.right().HasValue()) {
1522     return graph()->NewNode(machine()->Uint32Mod(), lhs, rhs, graph()->start());
1523   }
1524
1525   // General case for unsigned integer modulus, with optimization for (unknown)
1526   // power of 2 right hand side.
1527   //
1528   //   if rhs then
1529   //     msk = rhs - 1
1530   //     if rhs & msk != 0 then
1531   //       lhs % rhs
1532   //     else
1533   //       lhs & msk
1534   //   else
1535   //     zero
1536   //
1537   // Note: We do not use the Diamond helper class here, because it really hurts
1538   // readability with nested diamonds.
1539   const Operator* const merge_op = common()->Merge(2);
1540   const Operator* const phi_op = common()->Phi(kMachInt32, 2);
1541
1542   Node* branch0 = graph()->NewNode(common()->Branch(BranchHint::kTrue), rhs,
1543                                    graph()->start());
1544
1545   Node* if_true0 = graph()->NewNode(common()->IfTrue(), branch0);
1546   Node* true0;
1547   {
1548     Node* msk = graph()->NewNode(machine()->Int32Add(), rhs, minus_one);
1549
1550     Node* check1 = graph()->NewNode(machine()->Word32And(), rhs, msk);
1551     Node* branch1 = graph()->NewNode(common()->Branch(), check1, if_true0);
1552
1553     Node* if_true1 = graph()->NewNode(common()->IfTrue(), branch1);
1554     Node* true1 = graph()->NewNode(machine()->Uint32Mod(), lhs, rhs, if_true1);
1555
1556     Node* if_false1 = graph()->NewNode(common()->IfFalse(), branch1);
1557     Node* false1 = graph()->NewNode(machine()->Word32And(), lhs, msk);
1558
1559     if_true0 = graph()->NewNode(merge_op, if_true1, if_false1);
1560     true0 = graph()->NewNode(phi_op, true1, false1, if_true0);
1561   }
1562
1563   Node* if_false0 = graph()->NewNode(common()->IfFalse(), branch0);
1564   Node* false0 = zero;
1565
1566   Node* merge0 = graph()->NewNode(merge_op, if_true0, if_false0);
1567   return graph()->NewNode(phi_op, true0, false0, merge0);
1568 }
1569
1570
1571 void SimplifiedLowering::DoStringEqual(Node* node) {
1572   node->set_op(machine()->WordEqual());
1573   node->ReplaceInput(0, StringComparison(node, false));
1574   node->ReplaceInput(1, jsgraph()->SmiConstant(EQUAL));
1575 }
1576
1577
1578 void SimplifiedLowering::DoStringLessThan(Node* node) {
1579   node->set_op(machine()->IntLessThan());
1580   node->ReplaceInput(0, StringComparison(node, true));
1581   node->ReplaceInput(1, jsgraph()->SmiConstant(EQUAL));
1582 }
1583
1584
1585 void SimplifiedLowering::DoStringLessThanOrEqual(Node* node) {
1586   node->set_op(machine()->IntLessThanOrEqual());
1587   node->ReplaceInput(0, StringComparison(node, true));
1588   node->ReplaceInput(1, jsgraph()->SmiConstant(EQUAL));
1589 }
1590
1591 }  // namespace compiler
1592 }  // namespace internal
1593 }  // namespace v8