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