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 "src/base/bits.h"
   8 #include "src/code-factory.h"
   9 #include "src/compiler/common-operator.h"
  10 #include "src/compiler/graph-inl.h"
  11 #include "src/compiler/node-properties-inl.h"
  12 #include "src/compiler/representation-change.h"
  13 #include "src/compiler/simplified-lowering.h"
  14 #include "src/compiler/simplified-operator.h"
  15 #include "src/objects.h"
  16
  17 namespace v8 {
  18 namespace internal {
  19 namespace compiler {
  20
  21 // Macro for outputting trace information from representation inference.
  22 #define TRACE(x) \
  23   if (FLAG_trace_representation) PrintF x
  24
  25 // Representation selection and lowering of {Simplified} operators to machine
  26 // operators are interwined. We use a fixpoint calculation to compute both the
  27 // output representation and the best possible lowering for {Simplified} nodes.
  28 // Representation change insertion ensures that all values are in the correct
  29 // machine representation after this phase, as dictated by the machine
  30 // operators themselves.
  31 enum Phase {
  32   // 1.) PROPAGATE: Traverse the graph from the end, pushing usage information
  33   //     backwards from uses to definitions, around cycles in phis, according
  34   //     to local rules for each operator.
  35   //     During this phase, the usage information for a node determines the best
  36   //     possible lowering for each operator so far, and that in turn determines
  37   //     the output representation.
  38   //     Therefore, to be correct, this phase must iterate to a fixpoint before
  39   //     the next phase can begin.
  40   PROPAGATE,
  41
  42   // 2.) LOWER: perform lowering for all {Simplified} nodes by replacing some
  43   //     operators for some nodes, expanding some nodes to multiple nodes, or
  44   //     removing some (redundant) nodes.
  45   //     During this phase, use the {RepresentationChanger} to insert
  46   //     representation changes between uses that demand a particular
  47   //     representation and nodes that produce a different representation.
  48   LOWER
  49 };
  50
  51
  52 class RepresentationSelector {
  53  public:
  54   // Information for each node tracked during the fixpoint.
  55   struct NodeInfo {
  56     MachineTypeUnion use : 15;     // Union of all usages for the node.
  57     bool queued : 1;           // Bookkeeping for the traversal.
  58     bool visited : 1;          // Bookkeeping for the traversal.
  59     MachineTypeUnion output : 15;  // Output type of the node.
  60   };
  61
  62   RepresentationSelector(JSGraph* jsgraph, Zone* zone,
  63                          RepresentationChanger* changer)
  64       : jsgraph_(jsgraph),
  65         count_(jsgraph->graph()->NodeCount()),
  66         info_(zone->NewArray<NodeInfo>(count_)),
  67         nodes_(zone),
  68         replacements_(zone),
  69         contains_js_nodes_(false),
  70         phase_(PROPAGATE),
  71         changer_(changer),
  72         queue_(zone) {
  73     memset(info_, 0, sizeof(NodeInfo) * count_);
  74   }
  75
  76   void Run(SimplifiedLowering* lowering) {
  77     // Run propagation phase to a fixpoint.
  78     TRACE(("--{Propagation phase}--\n"));
  79     phase_ = PROPAGATE;
  80     Enqueue(jsgraph_->graph()->end());
  81     // Process nodes from the queue until it is empty.
  82     while (!queue_.empty()) {
  83       Node* node = queue_.front();
  84       NodeInfo* info = GetInfo(node);
  85       queue_.pop();
  86       info->queued = false;
  87       TRACE((" visit #%d: %s\n", node->id(), node->op()->mnemonic()));
  88       VisitNode(node, info->use, NULL);
  89       TRACE(("  ==> output "));
  90       PrintInfo(info->output);
  91       TRACE(("\n"));
  92     }
  93
  94     // Run lowering and change insertion phase.
  95     TRACE(("--{Simplified lowering phase}--\n"));
  96     phase_ = LOWER;
  97     // Process nodes from the collected {nodes_} vector.
  98     for (NodeVector::iterator i = nodes_.begin(); i != nodes_.end(); ++i) {
  99       Node* node = *i;
 100       TRACE((" visit #%d: %s\n", node->id(), node->op()->mnemonic()));
 101       // Reuse {VisitNode()} so the representation rules are in one place.
 102       VisitNode(node, GetUseInfo(node), lowering);
 103     }
 104
 105     // Perform the final replacements.
 106     for (NodeVector::iterator i = replacements_.begin();
 107          i != replacements_.end(); ++i) {
 108       Node* node = *i;
 109       Node* replacement = *(++i);
 110       node->ReplaceUses(replacement);
 111     }
 112   }
 113
 114   // Enqueue {node} if the {use} contains new information for that node.
 115   // Add {node} to {nodes_} if this is the first time it's been visited.
 116   void Enqueue(Node* node, MachineTypeUnion use = 0) {
 117     if (phase_ != PROPAGATE) return;
 118     NodeInfo* info = GetInfo(node);
 119     if (!info->visited) {
 120       // First visit of this node.
 121       info->visited = true;
 122       info->queued = true;
 123       nodes_.push_back(node);
 124       queue_.push(node);
 125       TRACE(("  initial: "));
 126       info->use |= use;
 127       PrintUseInfo(node);
 128       return;
 129     }
 130     TRACE(("   queue?: "));
 131     PrintUseInfo(node);
 132     if ((info->use & use) != use) {
 133       // New usage information for the node is available.
 134       if (!info->queued) {
 135         queue_.push(node);
 136         info->queued = true;
 137         TRACE(("   added: "));
 138       } else {
 139         TRACE((" inqueue: "));
 140       }
 141       info->use |= use;
 142       PrintUseInfo(node);
 143     }
 144   }
 145
 146   bool lower() { return phase_ == LOWER; }
 147
 148   void Enqueue(Node* node, MachineType use) {
 149     Enqueue(node, static_cast<MachineTypeUnion>(use));
 150   }
 151
 152   void SetOutput(Node* node, MachineTypeUnion output) {
 153     // Every node should have at most one output representation. Note that
 154     // phis can have 0, if they have not been used in a representation-inducing
 155     // instruction.
 156     DCHECK((output & kRepMask) == 0 ||
 157            base::bits::IsPowerOfTwo32(output & kRepMask));
 158     GetInfo(node)->output = output;
 159   }
 160
 161   bool BothInputsAre(Node* node, Type* type) {
 162     DCHECK_EQ(2, node->InputCount());
 163     return NodeProperties::GetBounds(node->InputAt(0)).upper->Is(type) &&
 164            NodeProperties::GetBounds(node->InputAt(1)).upper->Is(type);
 165   }
 166
 167   void ProcessInput(Node* node, int index, MachineTypeUnion use) {
 168     Node* input = node->InputAt(index);
 169     if (phase_ == PROPAGATE) {
 170       // In the propagate phase, propagate the usage information backward.
 171       Enqueue(input, use);
 172     } else {
 173       // In the change phase, insert a change before the use if necessary.
 174       if ((use & kRepMask) == 0) return;  // No input requirement on the use.
 175       MachineTypeUnion output = GetInfo(input)->output;
 176       if ((output & kRepMask & use) == 0) {
 177         // Output representation doesn't match usage.
 178         TRACE(("  change: #%d:%s(@%d #%d:%s) ", node->id(),
 179                node->op()->mnemonic(), index, input->id(),
 180                input->op()->mnemonic()));
 181         TRACE((" from "));
 182         PrintInfo(output);
 183         TRACE((" to "));
 184         PrintInfo(use);
 185         TRACE(("\n"));
 186         Node* n = changer_->GetRepresentationFor(input, output, use);
 187         node->ReplaceInput(index, n);
 188       }
 189     }
 190   }
 191
 192   void ProcessRemainingInputs(Node* node, int index) {
 193     DCHECK_GE(index, NodeProperties::PastValueIndex(node));
 194     DCHECK_GE(index, NodeProperties::PastContextIndex(node));
 195     for (int i = std::max(index, NodeProperties::FirstEffectIndex(node));
 196          i < NodeProperties::PastEffectIndex(node); ++i) {
 197       Enqueue(node->InputAt(i));  // Effect inputs: just visit
 198     }
 199     for (int i = std::max(index, NodeProperties::FirstControlIndex(node));
 200          i < NodeProperties::PastControlIndex(node); ++i) {
 201       Enqueue(node->InputAt(i));  // Control inputs: just visit
 202     }
 203   }
 204
 205   // The default, most general visitation case. For {node}, process all value,
 206   // context, effect, and control inputs, assuming that value inputs should have
 207   // {kRepTagged} representation and can observe all output values {kTypeAny}.
 208   void VisitInputs(Node* node) {
 209     InputIter i = node->inputs().begin();
 210     for (int j = OperatorProperties::GetValueInputCount(node->op()); j > 0;
 211          ++i, j--) {
 212       ProcessInput(node, i.index(), kMachAnyTagged);  // Value inputs
 213     }
 214     for (int j = OperatorProperties::GetContextInputCount(node->op()); j > 0;
 215          ++i, j--) {
 216       ProcessInput(node, i.index(), kMachAnyTagged);  // Context inputs
 217     }
 218     for (int j = OperatorProperties::GetEffectInputCount(node->op()); j > 0;
 219          ++i, j--) {
 220       Enqueue(*i);  // Effect inputs: just visit
 221     }
 222     for (int j = OperatorProperties::GetControlInputCount(node->op()); j > 0;
 223          ++i, j--) {
 224       Enqueue(*i);  // Control inputs: just visit
 225     }
 226     SetOutput(node, kMachAnyTagged);
 227   }
 228
 229   // Helper for binops of the I x I -> O variety.
 230   void VisitBinop(Node* node, MachineTypeUnion input_use,
 231                   MachineTypeUnion output) {
 232     DCHECK_EQ(2, node->InputCount());
 233     ProcessInput(node, 0, input_use);
 234     ProcessInput(node, 1, input_use);
 235     SetOutput(node, output);
 236   }
 237
 238   // Helper for unops of the I -> O variety.
 239   void VisitUnop(Node* node, MachineTypeUnion input_use,
 240                  MachineTypeUnion output) {
 241     DCHECK_EQ(1, node->InputCount());
 242     ProcessInput(node, 0, input_use);
 243     SetOutput(node, output);
 244   }
 245
 246   // Helper for leaf nodes.
 247   void VisitLeaf(Node* node, MachineTypeUnion output) {
 248     DCHECK_EQ(0, node->InputCount());
 249     SetOutput(node, output);
 250   }
 251
 252   // Helpers for specific types of binops.
 253   void VisitFloat64Binop(Node* node) {
 254     VisitBinop(node, kMachFloat64, kMachFloat64);
 255   }
 256   void VisitInt32Binop(Node* node) { VisitBinop(node, kMachInt32, kMachInt32); }
 257   void VisitUint32Binop(Node* node) {
 258     VisitBinop(node, kMachUint32, kMachUint32);
 259   }
 260   void VisitInt64Binop(Node* node) { VisitBinop(node, kMachInt64, kMachInt64); }
 261   void VisitUint64Binop(Node* node) {
 262     VisitBinop(node, kMachUint64, kMachUint64);
 263   }
 264   void VisitFloat64Cmp(Node* node) { VisitBinop(node, kMachFloat64, kRepBit); }
 265   void VisitInt32Cmp(Node* node) { VisitBinop(node, kMachInt32, kRepBit); }
 266   void VisitUint32Cmp(Node* node) { VisitBinop(node, kMachUint32, kRepBit); }
 267   void VisitInt64Cmp(Node* node) { VisitBinop(node, kMachInt64, kRepBit); }
 268   void VisitUint64Cmp(Node* node) { VisitBinop(node, kMachUint64, kRepBit); }
 269
 270   // Helper for handling phis.
 271   void VisitPhi(Node* node, MachineTypeUnion use,
 272                 SimplifiedLowering* lowering) {
 273     // First, propagate the usage information to inputs of the phi.
 274     if (!lower()) {
 275       int values = OperatorProperties::GetValueInputCount(node->op());
 276       // Propagate {use} of the phi to value inputs, and 0 to control.
 277       Node::Inputs inputs = node->inputs();
 278       for (Node::Inputs::iterator iter(inputs.begin()); iter != inputs.end();
 279            ++iter, --values) {
 280         // TODO(titzer): it'd be nice to have distinguished edge kinds here.
 281         ProcessInput(node, iter.index(), values > 0 ? use : 0);
 282       }
 283     }
 284     // Phis adapt to whatever output representation their uses demand,
 285     // pushing representation changes to their inputs.
 286     MachineTypeUnion use_rep = GetUseInfo(node) & kRepMask;
 287     MachineTypeUnion use_type = GetUseInfo(node) & kTypeMask;
 288     MachineTypeUnion rep = 0;
 289     if (use_rep & kRepTagged) {
 290       rep = kRepTagged;  // Tagged overrides everything.
 291     } else if (use_rep & kRepFloat64) {
 292       rep = kRepFloat64;
 293     } else if (use_rep & kRepWord64) {
 294       rep = kRepWord64;
 295     } else if (use_rep & kRepWord32) {
 296       rep = kRepWord32;
 297     } else if (use_rep & kRepBit) {
 298       rep = kRepBit;
 299     } else {
 300       // There was no representation associated with any of the uses.
 301       // TODO(titzer): Select the best rep using phi's type, not the usage type?
 302       if (use_type & kTypeAny) {
 303         rep = kRepTagged;
 304       } else if (use_type & kTypeNumber) {
 305         rep = kRepFloat64;
 306       } else if (use_type & kTypeInt64 || use_type & kTypeUint64) {
 307         rep = kRepWord64;
 308       } else if (use_type & kTypeInt32 || use_type & kTypeUint32) {
 309         rep = kRepWord32;
 310       } else if (use_type & kTypeBool) {
 311         rep = kRepBit;
 312       } else {
 313         UNREACHABLE();  // should have at least a usage type!
 314       }
 315     }
 316     // Preserve the usage type, but set the representation.
 317     Type* upper = NodeProperties::GetBounds(node).upper;
 318     MachineTypeUnion output_type = rep | changer_->TypeFromUpperBound(upper);
 319     SetOutput(node, output_type);
 320
 321     if (lower()) {
 322       int values = OperatorProperties::GetValueInputCount(node->op());
 323
 324       // Update the phi operator.
 325       MachineType type = static_cast<MachineType>(output_type);
 326       if (type != OpParameter<MachineType>(node)) {
 327         node->set_op(lowering->common()->Phi(type, values));
 328       }
 329
 330       // Convert inputs to the output representation of this phi.
 331       Node::Inputs inputs = node->inputs();
 332       for (Node::Inputs::iterator iter(inputs.begin()); iter != inputs.end();
 333            ++iter, --values) {
 334         // TODO(titzer): it'd be nice to have distinguished edge kinds here.
 335         ProcessInput(node, iter.index(), values > 0 ? output_type : 0);
 336       }
 337     }
 338   }
 339
 340   const Operator* Int32Op(Node* node) {
 341     return changer_->Int32OperatorFor(node->opcode());
 342   }
 343
 344   const Operator* Uint32Op(Node* node) {
 345     return changer_->Uint32OperatorFor(node->opcode());
 346   }
 347
 348   const Operator* Float64Op(Node* node) {
 349     return changer_->Float64OperatorFor(node->opcode());
 350   }
 351
 352   static MachineType AssumeImplicitFloat32Change(MachineType type) {
 353     // TODO(titzer): Assume loads of float32 change representation to float64.
 354     // Fix this with full support for float32 representations.
 355     if (type & kRepFloat32) {
 356       return static_cast<MachineType>((type & ~kRepFloat32) | kRepFloat64);
 357     }
 358     return type;
 359   }
 360
 361   // Dispatching routine for visiting the node {node} with the usage {use}.
 362   // Depending on the operator, propagate new usage info to the inputs.
 363   void VisitNode(Node* node, MachineTypeUnion use,
 364                  SimplifiedLowering* lowering) {
 365     switch (node->opcode()) {
 366       //------------------------------------------------------------------
 367       // Common operators.
 368       //------------------------------------------------------------------
 369       case IrOpcode::kStart:
 370       case IrOpcode::kDead:
 371         return VisitLeaf(node, 0);
 372       case IrOpcode::kParameter: {
 373         // TODO(titzer): use representation from linkage.
 374         Type* upper = NodeProperties::GetBounds(node).upper;
 375         ProcessInput(node, 0, 0);
 376         SetOutput(node, kRepTagged | changer_->TypeFromUpperBound(upper));
 377         return;
 378       }
 379       case IrOpcode::kInt32Constant:
 380         return VisitLeaf(node, kRepWord32);
 381       case IrOpcode::kInt64Constant:
 382         return VisitLeaf(node, kRepWord64);
 383       case IrOpcode::kFloat64Constant:
 384         return VisitLeaf(node, kRepFloat64);
 385       case IrOpcode::kExternalConstant:
 386         return VisitLeaf(node, kMachPtr);
 387       case IrOpcode::kNumberConstant:
 388         return VisitLeaf(node, kRepTagged);
 389       case IrOpcode::kHeapConstant:
 390         return VisitLeaf(node, kRepTagged);
 391
 392       case IrOpcode::kEnd:
 393       case IrOpcode::kIfTrue:
 394       case IrOpcode::kIfFalse:
 395       case IrOpcode::kReturn:
 396       case IrOpcode::kMerge:
 397       case IrOpcode::kThrow:
 398         return VisitInputs(node);  // default visit for all node inputs.
 399
 400       case IrOpcode::kBranch:
 401         ProcessInput(node, 0, kRepBit);
 402         Enqueue(NodeProperties::GetControlInput(node, 0));
 403         break;
 404       case IrOpcode::kPhi:
 405         return VisitPhi(node, use, lowering);
 406
 407 //------------------------------------------------------------------
 408 // JavaScript operators.
 409 //------------------------------------------------------------------
 410 // For now, we assume that all JS operators were too complex to lower
 411 // to Simplified and that they will always require tagged value inputs
 412 // and produce tagged value outputs.
 413 // TODO(turbofan): it might be possible to lower some JSOperators here,
 414 // but that responsibility really lies in the typed lowering phase.
 415 #define DEFINE_JS_CASE(x) case IrOpcode::k##x:
 416         JS_OP_LIST(DEFINE_JS_CASE)
 417 #undef DEFINE_JS_CASE
 418         contains_js_nodes_ = true;
 419         VisitInputs(node);
 420         return SetOutput(node, kRepTagged);
 421
 422       //------------------------------------------------------------------
 423       // Simplified operators.
 424       //------------------------------------------------------------------
 425       case IrOpcode::kBooleanNot: {
 426         if (lower()) {
 427           MachineTypeUnion input = GetInfo(node->InputAt(0))->output;
 428           if (input & kRepBit) {
 429             // BooleanNot(x: kRepBit) => WordEqual(x, #0)
 430             node->set_op(lowering->machine()->WordEqual());
 431             node->AppendInput(jsgraph_->zone(), jsgraph_->Int32Constant(0));
 432           } else {
 433             // BooleanNot(x: kRepTagged) => WordEqual(x, #false)
 434             node->set_op(lowering->machine()->WordEqual());
 435             node->AppendInput(jsgraph_->zone(), jsgraph_->FalseConstant());
 436           }
 437         } else {
 438           // No input representation requirement; adapt during lowering.
 439           ProcessInput(node, 0, kTypeBool);
 440           SetOutput(node, kRepBit);
 441         }
 442         break;
 443       }
 444       case IrOpcode::kBooleanToNumber: {
 445         if (lower()) {
 446           MachineTypeUnion input = GetInfo(node->InputAt(0))->output;
 447           if (input & kRepBit) {
 448             // BooleanToNumber(x: kRepBit) => x
 449             DeferReplacement(node, node->InputAt(0));
 450           } else {
 451             // BooleanToNumber(x: kRepTagged) => WordEqual(x, #true)
 452             node->set_op(lowering->machine()->WordEqual());
 453             node->AppendInput(jsgraph_->zone(), jsgraph_->TrueConstant());
 454           }
 455         } else {
 456           // No input representation requirement; adapt during lowering.
 457           ProcessInput(node, 0, kTypeBool);
 458           SetOutput(node, kMachInt32);
 459         }
 460         break;
 461       }
 462       case IrOpcode::kNumberEqual:
 463       case IrOpcode::kNumberLessThan:
 464       case IrOpcode::kNumberLessThanOrEqual: {
 465         // Number comparisons reduce to integer comparisons for integer inputs.
 466         if (BothInputsAre(node, Type::Signed32())) {
 467           // => signed Int32Cmp
 468           VisitInt32Cmp(node);
 469           if (lower()) node->set_op(Int32Op(node));
 470         } else if (BothInputsAre(node, Type::Unsigned32())) {
 471           // => unsigned Int32Cmp
 472           VisitUint32Cmp(node);
 473           if (lower()) node->set_op(Uint32Op(node));
 474         } else {
 475           // => Float64Cmp
 476           VisitFloat64Cmp(node);
 477           if (lower()) node->set_op(Float64Op(node));
 478         }
 479         break;
 480       }
 481       case IrOpcode::kNumberAdd:
 482       case IrOpcode::kNumberSubtract: {
 483         // Add and subtract reduce to Int32Add/Sub if the inputs
 484         // are already integers and all uses are truncating.
 485         if (BothInputsAre(node, Type::Signed32()) &&
 486             (use & (kTypeUint32 | kTypeNumber | kTypeAny)) == 0) {
 487           // => signed Int32Add/Sub
 488           VisitInt32Binop(node);
 489           if (lower()) node->set_op(Int32Op(node));
 490         } else if (BothInputsAre(node, Type::Unsigned32()) &&
 491                    (use & (kTypeInt32 | kTypeNumber | kTypeAny)) == 0) {
 492           // => unsigned Int32Add/Sub
 493           VisitUint32Binop(node);
 494           if (lower()) node->set_op(Uint32Op(node));
 495         } else {
 496           // => Float64Add/Sub
 497           VisitFloat64Binop(node);
 498           if (lower()) node->set_op(Float64Op(node));
 499         }
 500         break;
 501       }
 502       case IrOpcode::kNumberMultiply:
 503       case IrOpcode::kNumberDivide:
 504       case IrOpcode::kNumberModulus: {
 505         // Float64Mul/Div/Mod
 506         VisitFloat64Binop(node);
 507         if (lower()) node->set_op(Float64Op(node));
 508         break;
 509       }
 510       case IrOpcode::kNumberToInt32: {
 511         MachineTypeUnion use_rep = use & kRepMask;
 512         if (lower()) {
 513           MachineTypeUnion in = GetInfo(node->InputAt(0))->output;
 514           if ((in & kTypeMask) == kTypeInt32 || (in & kRepMask) == kRepWord32) {
 515             // If the input has type int32, or is already a word32, just change
 516             // representation if necessary.
 517             VisitUnop(node, kTypeInt32 | use_rep, kTypeInt32 | use_rep);
 518             DeferReplacement(node, node->InputAt(0));
 519           } else {
 520             // Require the input in float64 format and perform truncation.
 521             // TODO(turbofan): avoid a truncation with a smi check.
 522             VisitUnop(node, kTypeInt32 | kRepFloat64, kTypeInt32 | kRepWord32);
 523             node->set_op(lowering->machine()->TruncateFloat64ToInt32());
 524           }
 525         } else {
 526           // Propagate a type to the input, but pass through representation.
 527           VisitUnop(node, kTypeInt32, kTypeInt32 | use_rep);
 528         }
 529         break;
 530       }
 531       case IrOpcode::kNumberToUint32: {
 532         MachineTypeUnion use_rep = use & kRepMask;
 533         if (lower()) {
 534           MachineTypeUnion in = GetInfo(node->InputAt(0))->output;
 535           if ((in & kTypeMask) == kTypeUint32 ||
 536               (in & kRepMask) == kRepWord32) {
 537             // The input has type int32, just change representation.
 538             VisitUnop(node, kTypeUint32 | use_rep, kTypeUint32 | use_rep);
 539             DeferReplacement(node, node->InputAt(0));
 540           } else {
 541             // Require the input in float64 format to perform truncation.
 542             // TODO(turbofan): avoid the truncation with a smi check.
 543             VisitUnop(node, kTypeUint32 | kRepFloat64,
 544                       kTypeUint32 | kRepWord32);
 545             node->set_op(lowering->machine()->TruncateFloat64ToInt32());
 546           }
 547         } else {
 548           // Propagate a type to the input, but pass through representation.
 549           VisitUnop(node, kTypeUint32, kTypeUint32 | use_rep);
 550         }
 551         break;
 552       }
 553       case IrOpcode::kReferenceEqual: {
 554         VisitBinop(node, kMachAnyTagged, kRepBit);
 555         if (lower()) node->set_op(lowering->machine()->WordEqual());
 556         break;
 557       }
 558       case IrOpcode::kStringEqual: {
 559         VisitBinop(node, kMachAnyTagged, kRepBit);
 560         if (lower()) lowering->DoStringEqual(node);
 561         break;
 562       }
 563       case IrOpcode::kStringLessThan: {
 564         VisitBinop(node, kMachAnyTagged, kRepBit);
 565         if (lower()) lowering->DoStringLessThan(node);
 566         break;
 567       }
 568       case IrOpcode::kStringLessThanOrEqual: {
 569         VisitBinop(node, kMachAnyTagged, kRepBit);
 570         if (lower()) lowering->DoStringLessThanOrEqual(node);
 571         break;
 572       }
 573       case IrOpcode::kStringAdd: {
 574         VisitBinop(node, kMachAnyTagged, kMachAnyTagged);
 575         if (lower()) lowering->DoStringAdd(node);
 576         break;
 577       }
 578       case IrOpcode::kLoadField: {
 579         FieldAccess access = FieldAccessOf(node->op());
 580         ProcessInput(node, 0, changer_->TypeForBasePointer(access));
 581         ProcessRemainingInputs(node, 1);
 582         SetOutput(node, AssumeImplicitFloat32Change(access.machine_type));
 583         if (lower()) lowering->DoLoadField(node);
 584         break;
 585       }
 586       case IrOpcode::kStoreField: {
 587         FieldAccess access = FieldAccessOf(node->op());
 588         ProcessInput(node, 0, changer_->TypeForBasePointer(access));
 589         ProcessInput(node, 1, AssumeImplicitFloat32Change(access.machine_type));
 590         ProcessRemainingInputs(node, 2);
 591         SetOutput(node, 0);
 592         if (lower()) lowering->DoStoreField(node);
 593         break;
 594       }
 595       case IrOpcode::kLoadElement: {
 596         ElementAccess access = ElementAccessOf(node->op());
 597         ProcessInput(node, 0, changer_->TypeForBasePointer(access));
 598         ProcessInput(node, 1, kMachInt32);  // element index
 599         ProcessInput(node, 2, kMachInt32);  // length
 600         ProcessRemainingInputs(node, 3);
 601         SetOutput(node, AssumeImplicitFloat32Change(access.machine_type));
 602         if (lower()) lowering->DoLoadElement(node);
 603         break;
 604       }
 605       case IrOpcode::kStoreElement: {
 606         ElementAccess access = ElementAccessOf(node->op());
 607         ProcessInput(node, 0, changer_->TypeForBasePointer(access));
 608         ProcessInput(node, 1, kMachInt32);  // element index
 609         ProcessInput(node, 2, kMachInt32);  // length
 610         ProcessInput(node, 3, AssumeImplicitFloat32Change(access.machine_type));
 611         ProcessRemainingInputs(node, 4);
 612         SetOutput(node, 0);
 613         if (lower()) lowering->DoStoreElement(node);
 614         break;
 615       }
 616
 617       //------------------------------------------------------------------
 618       // Machine-level operators.
 619       //------------------------------------------------------------------
 620       case IrOpcode::kLoad: {
 621         // TODO(titzer): machine loads/stores need to know BaseTaggedness!?
 622         MachineType tBase = kRepTagged;
 623         LoadRepresentation rep = OpParameter<LoadRepresentation>(node);
 624         ProcessInput(node, 0, tBase);   // pointer or object
 625         ProcessInput(node, 1, kMachInt32);  // index
 626         ProcessRemainingInputs(node, 2);
 627         SetOutput(node, rep);
 628         break;
 629       }
 630       case IrOpcode::kStore: {
 631         // TODO(titzer): machine loads/stores need to know BaseTaggedness!?
 632         MachineType tBase = kRepTagged;
 633         StoreRepresentation rep = OpParameter<StoreRepresentation>(node);
 634         ProcessInput(node, 0, tBase);   // pointer or object
 635         ProcessInput(node, 1, kMachInt32);  // index
 636         ProcessInput(node, 2, rep.machine_type());
 637         ProcessRemainingInputs(node, 3);
 638         SetOutput(node, 0);
 639         break;
 640       }
 641       case IrOpcode::kWord32Shr:
 642         // We output unsigned int32 for shift right because JavaScript.
 643         return VisitBinop(node, kRepWord32, kRepWord32 | kTypeUint32);
 644       case IrOpcode::kWord32And:
 645       case IrOpcode::kWord32Or:
 646       case IrOpcode::kWord32Xor:
 647       case IrOpcode::kWord32Shl:
 648       case IrOpcode::kWord32Sar:
 649         // We use signed int32 as the output type for these word32 operations,
 650         // though the machine bits are the same for either signed or unsigned,
 651         // because JavaScript considers the result from these operations signed.
 652         return VisitBinop(node, kRepWord32, kRepWord32 | kTypeInt32);
 653       case IrOpcode::kWord32Equal:
 654         return VisitBinop(node, kRepWord32, kRepBit);
 655
 656       case IrOpcode::kInt32Add:
 657       case IrOpcode::kInt32Sub:
 658       case IrOpcode::kInt32Mul:
 659       case IrOpcode::kInt32Div:
 660       case IrOpcode::kInt32Mod:
 661         return VisitInt32Binop(node);
 662       case IrOpcode::kInt32UDiv:
 663       case IrOpcode::kInt32UMod:
 664         return VisitUint32Binop(node);
 665       case IrOpcode::kInt32LessThan:
 666       case IrOpcode::kInt32LessThanOrEqual:
 667         return VisitInt32Cmp(node);
 668
 669       case IrOpcode::kUint32LessThan:
 670       case IrOpcode::kUint32LessThanOrEqual:
 671         return VisitUint32Cmp(node);
 672
 673       case IrOpcode::kInt64Add:
 674       case IrOpcode::kInt64Sub:
 675       case IrOpcode::kInt64Mul:
 676       case IrOpcode::kInt64Div:
 677       case IrOpcode::kInt64Mod:
 678         return VisitInt64Binop(node);
 679       case IrOpcode::kInt64LessThan:
 680       case IrOpcode::kInt64LessThanOrEqual:
 681         return VisitInt64Cmp(node);
 682
 683       case IrOpcode::kInt64UDiv:
 684       case IrOpcode::kInt64UMod:
 685         return VisitUint64Binop(node);
 686
 687       case IrOpcode::kWord64And:
 688       case IrOpcode::kWord64Or:
 689       case IrOpcode::kWord64Xor:
 690       case IrOpcode::kWord64Shl:
 691       case IrOpcode::kWord64Shr:
 692       case IrOpcode::kWord64Sar:
 693         return VisitBinop(node, kRepWord64, kRepWord64);
 694       case IrOpcode::kWord64Equal:
 695         return VisitBinop(node, kRepWord64, kRepBit);
 696
 697       case IrOpcode::kChangeInt32ToInt64:
 698         return VisitUnop(node, kTypeInt32 | kRepWord32,
 699                          kTypeInt32 | kRepWord64);
 700       case IrOpcode::kChangeUint32ToUint64:
 701         return VisitUnop(node, kTypeUint32 | kRepWord32,
 702                          kTypeUint32 | kRepWord64);
 703       case IrOpcode::kTruncateInt64ToInt32:
 704         // TODO(titzer): Is kTypeInt32 correct here?
 705         return VisitUnop(node, kTypeInt32 | kRepWord64,
 706                          kTypeInt32 | kRepWord32);
 707
 708       case IrOpcode::kChangeInt32ToFloat64:
 709         return VisitUnop(node, kTypeInt32 | kRepWord32,
 710                          kTypeInt32 | kRepFloat64);
 711       case IrOpcode::kChangeUint32ToFloat64:
 712         return VisitUnop(node, kTypeUint32 | kRepWord32,
 713                          kTypeUint32 | kRepFloat64);
 714       case IrOpcode::kChangeFloat64ToInt32:
 715         return VisitUnop(node, kTypeInt32 | kRepFloat64,
 716                          kTypeInt32 | kRepWord32);
 717       case IrOpcode::kChangeFloat64ToUint32:
 718         return VisitUnop(node, kTypeUint32 | kRepFloat64,
 719                          kTypeUint32 | kRepWord32);
 720
 721       case IrOpcode::kFloat64Add:
 722       case IrOpcode::kFloat64Sub:
 723       case IrOpcode::kFloat64Mul:
 724       case IrOpcode::kFloat64Div:
 725       case IrOpcode::kFloat64Mod:
 726         return VisitFloat64Binop(node);
 727       case IrOpcode::kFloat64Sqrt:
 728         return VisitUnop(node, kMachFloat64, kMachFloat64);
 729       case IrOpcode::kFloat64Equal:
 730       case IrOpcode::kFloat64LessThan:
 731       case IrOpcode::kFloat64LessThanOrEqual:
 732         return VisitFloat64Cmp(node);
 733       default:
 734         VisitInputs(node);
 735         break;
 736     }
 737   }
 738
 739   void DeferReplacement(Node* node, Node* replacement) {
 740     if (replacement->id() < count_) {
 741       // Replace with a previously existing node eagerly.
 742       node->ReplaceUses(replacement);
 743     } else {
 744       // Otherwise, we are replacing a node with a representation change.
 745       // Such a substitution must be done after all lowering is done, because
 746       // new nodes do not have {NodeInfo} entries, and that would confuse
 747       // the representation change insertion for uses of it.
 748       replacements_.push_back(node);
 749       replacements_.push_back(replacement);
 750     }
 751     // TODO(titzer) node->RemoveAllInputs();  // Node is now dead.
 752   }
 753
 754   void PrintUseInfo(Node* node) {
 755     TRACE(("#%d:%-20s ", node->id(), node->op()->mnemonic()));
 756     PrintInfo(GetUseInfo(node));
 757     TRACE(("\n"));
 758   }
 759
 760   void PrintInfo(MachineTypeUnion info) {
 761     if (FLAG_trace_representation) {
 762       OFStream os(stdout);
 763       os << static_cast<MachineType>(info);
 764     }
 765   }
 766
 767  private:
 768   JSGraph* jsgraph_;
 769   int count_;                       // number of nodes in the graph
 770   NodeInfo* info_;                  // node id -> usage information
 771   NodeVector nodes_;                // collected nodes
 772   NodeVector replacements_;         // replacements to be done after lowering
 773   bool contains_js_nodes_;          // {true} if a JS operator was seen
 774   Phase phase_;                     // current phase of algorithm
 775   RepresentationChanger* changer_;  // for inserting representation changes
 776   ZoneQueue<Node*> queue_;          // queue for traversing the graph
 777
 778   NodeInfo* GetInfo(Node* node) {
 779     DCHECK(node->id() >= 0);
 780     DCHECK(node->id() < count_);
 781     return &info_[node->id()];
 782   }
 783
 784   MachineTypeUnion GetUseInfo(Node* node) { return GetInfo(node)->use; }
 785 };
 786
 787
 788 Node* SimplifiedLowering::IsTagged(Node* node) {
 789   // TODO(titzer): factor this out to a TaggingScheme abstraction.
 790   STATIC_ASSERT(kSmiTagMask == 1);  // Only works if tag is the low bit.
 791   return graph()->NewNode(machine()->WordAnd(), node,
 792                           jsgraph()->Int32Constant(kSmiTagMask));
 793 }
 794
 795
 796 void SimplifiedLowering::LowerAllNodes() {
 797   SimplifiedOperatorBuilder simplified(graph()->zone());
 798   RepresentationChanger changer(jsgraph(), &simplified,
 799                                 graph()->zone()->isolate());
 800   RepresentationSelector selector(jsgraph(), zone(), &changer);
 801   selector.Run(this);
 802 }
 803
 804
 805 Node* SimplifiedLowering::Untag(Node* node) {
 806   // TODO(titzer): factor this out to a TaggingScheme abstraction.
 807   Node* shift_amount = jsgraph()->Int32Constant(kSmiTagSize + kSmiShiftSize);
 808   return graph()->NewNode(machine()->WordSar(), node, shift_amount);
 809 }
 810
 811
 812 Node* SimplifiedLowering::SmiTag(Node* node) {
 813   // TODO(titzer): factor this out to a TaggingScheme abstraction.
 814   Node* shift_amount = jsgraph()->Int32Constant(kSmiTagSize + kSmiShiftSize);
 815   return graph()->NewNode(machine()->WordShl(), node, shift_amount);
 816 }
 817
 818
 819 Node* SimplifiedLowering::OffsetMinusTagConstant(int32_t offset) {
 820   return jsgraph()->Int32Constant(offset - kHeapObjectTag);
 821 }
 822
 823
 824 static WriteBarrierKind ComputeWriteBarrierKind(BaseTaggedness base_is_tagged,
 825                                                 MachineType representation,
 826                                                 Type* type) {
 827   // TODO(turbofan): skip write barriers for Smis, etc.
 828   if (base_is_tagged == kTaggedBase &&
 829       RepresentationOf(representation) == kRepTagged) {
 830     // Write barriers are only for writes into heap objects (i.e. tagged base).
 831     return kFullWriteBarrier;
 832   }
 833   return kNoWriteBarrier;
 834 }
 835
 836
 837 void SimplifiedLowering::DoLoadField(Node* node) {
 838   const FieldAccess& access = FieldAccessOf(node->op());
 839   node->set_op(machine()->Load(access.machine_type));
 840   Node* offset = jsgraph()->Int32Constant(access.offset - access.tag());
 841   node->InsertInput(zone(), 1, offset);
 842 }
 843
 844
 845 void SimplifiedLowering::DoStoreField(Node* node) {
 846   const FieldAccess& access = FieldAccessOf(node->op());
 847   WriteBarrierKind kind = ComputeWriteBarrierKind(
 848       access.base_is_tagged, access.machine_type, access.type);
 849   node->set_op(
 850       machine()->Store(StoreRepresentation(access.machine_type, kind)));
 851   Node* offset = jsgraph()->Int32Constant(access.offset - access.tag());
 852   node->InsertInput(zone(), 1, offset);
 853 }
 854
 855
 856 Node* SimplifiedLowering::ComputeIndex(const ElementAccess& access,
 857                                        Node* index) {
 858   int element_size = ElementSizeOf(access.machine_type);
 859   if (element_size != 1) {
 860     index = graph()->NewNode(machine()->Int32Mul(),
 861                              jsgraph()->Int32Constant(element_size), index);
 862   }
 863   int fixed_offset = access.header_size - access.tag();
 864   if (fixed_offset == 0) return index;
 865   return graph()->NewNode(machine()->Int32Add(), index,
 866                           jsgraph()->Int32Constant(fixed_offset));
 867 }
 868
 869
 870 void SimplifiedLowering::DoLoadElement(Node* node) {
 871   const ElementAccess& access = ElementAccessOf(node->op());
 872   node->set_op(machine()->Load(access.machine_type));
 873   node->ReplaceInput(1, ComputeIndex(access, node->InputAt(1)));
 874   node->RemoveInput(2);
 875 }
 876
 877
 878 void SimplifiedLowering::DoStoreElement(Node* node) {
 879   const ElementAccess& access = ElementAccessOf(node->op());
 880   WriteBarrierKind kind = ComputeWriteBarrierKind(
 881       access.base_is_tagged, access.machine_type, access.type);
 882   node->set_op(
 883       machine()->Store(StoreRepresentation(access.machine_type, kind)));
 884   node->ReplaceInput(1, ComputeIndex(access, node->InputAt(1)));
 885   node->RemoveInput(2);
 886 }
 887
 888
 889 void SimplifiedLowering::DoStringAdd(Node* node) {
 890   Callable callable = CodeFactory::StringAdd(
 891       zone()->isolate(), STRING_ADD_CHECK_NONE, NOT_TENURED);
 892   CallDescriptor::Flags flags = CallDescriptor::kNoFlags;
 893   CallDescriptor* desc =
 894       Linkage::GetStubCallDescriptor(callable.descriptor(), 0, flags, zone());
 895   node->set_op(common()->Call(desc));
 896   node->InsertInput(zone(), 0, jsgraph()->HeapConstant(callable.code()));
 897   node->AppendInput(zone(), jsgraph()->UndefinedConstant());
 898   node->AppendInput(zone(), graph()->start());
 899   node->AppendInput(zone(), graph()->start());
 900 }
 901
 902
 903 Node* SimplifiedLowering::StringComparison(Node* node, bool requires_ordering) {
 904   CEntryStub stub(zone()->isolate(), 1);
 905   Runtime::FunctionId f =
 906       requires_ordering ? Runtime::kStringCompare : Runtime::kStringEquals;
 907   ExternalReference ref(f, zone()->isolate());
 908   Operator::Properties props = node->op()->properties();
 909   // TODO(mstarzinger): We should call StringCompareStub here instead, once an
 910   // interface descriptor is available for it.
 911   CallDescriptor* desc = Linkage::GetRuntimeCallDescriptor(f, 2, props, zone());
 912   return graph()->NewNode(common()->Call(desc),
 913                           jsgraph()->HeapConstant(stub.GetCode()),
 914                           NodeProperties::GetValueInput(node, 0),
 915                           NodeProperties::GetValueInput(node, 1),
 916                           jsgraph()->ExternalConstant(ref),
 917                           jsgraph()->Int32Constant(2),
 918                           jsgraph()->UndefinedConstant());
 919 }
 920
 921
 922 void SimplifiedLowering::DoStringEqual(Node* node) {
 923   node->set_op(machine()->WordEqual());
 924   node->ReplaceInput(0, StringComparison(node, false));
 925   node->ReplaceInput(1, jsgraph()->SmiConstant(EQUAL));
 926 }
 927
 928
 929 void SimplifiedLowering::DoStringLessThan(Node* node) {
 930   node->set_op(machine()->IntLessThan());
 931   node->ReplaceInput(0, StringComparison(node, true));
 932   node->ReplaceInput(1, jsgraph()->SmiConstant(EQUAL));
 933 }
 934
 935
 936 void SimplifiedLowering::DoStringLessThanOrEqual(Node* node) {
 937   node->set_op(machine()->IntLessThanOrEqual());
 938   node->ReplaceInput(0, StringComparison(node, true));
 939   node->ReplaceInput(1, jsgraph()->SmiConstant(EQUAL));
 940 }
 941
 942
 943 }  // namespace compiler
 944 }  // namespace internal
 945 }  // namespace v8