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