src/v8/src/hydrogen-instructions.cc

   1 // Copyright 2012 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/v8.h"
   6
   7 #include "src/double.h"
   8 #include "src/factory.h"
   9 #include "src/hydrogen-infer-representation.h"
  10 #include "src/property-details-inl.h"
  11
  12 #if V8_TARGET_ARCH_IA32
  13 #include "src/ia32/lithium-ia32.h"  // NOLINT
  14 #elif V8_TARGET_ARCH_X64
  15 #include "src/x64/lithium-x64.h"  // NOLINT
  16 #elif V8_TARGET_ARCH_ARM64
  17 #include "src/arm64/lithium-arm64.h"  // NOLINT
  18 #elif V8_TARGET_ARCH_ARM
  19 #include "src/arm/lithium-arm.h"  // NOLINT
  20 #elif V8_TARGET_ARCH_MIPS
  21 #include "src/mips/lithium-mips.h"  // NOLINT
  22 #elif V8_TARGET_ARCH_MIPS64
  23 #include "src/mips64/lithium-mips64.h"  // NOLINT
  24 #elif V8_TARGET_ARCH_X87
  25 #include "src/x87/lithium-x87.h"  // NOLINT
  26 #else
  27 #error Unsupported target architecture.
  28 #endif
  29
  30 #include "src/base/safe_math.h"
  31
  32 namespace v8 {
  33 namespace internal {
  34
  35 #define DEFINE_COMPILE(type)                                         \
  36   LInstruction* H##type::CompileToLithium(LChunkBuilder* builder) {  \
  37     return builder->Do##type(this);                                  \
  38   }
  39 HYDROGEN_CONCRETE_INSTRUCTION_LIST(DEFINE_COMPILE)
  40 #undef DEFINE_COMPILE
  41
  42
  43 Isolate* HValue::isolate() const {
  44   DCHECK(block() != NULL);
  45   return block()->isolate();
  46 }
  47
  48
  49 void HValue::AssumeRepresentation(Representation r) {
  50   if (CheckFlag(kFlexibleRepresentation)) {
  51     ChangeRepresentation(r);
  52     // The representation of the value is dictated by type feedback and
  53     // will not be changed later.
  54     ClearFlag(kFlexibleRepresentation);
  55   }
  56 }
  57
  58
  59 void HValue::InferRepresentation(HInferRepresentationPhase* h_infer) {
  60   DCHECK(CheckFlag(kFlexibleRepresentation));
  61   Representation new_rep = RepresentationFromInputs();
  62   UpdateRepresentation(new_rep, h_infer, "inputs");
  63   new_rep = RepresentationFromUses();
  64   UpdateRepresentation(new_rep, h_infer, "uses");
  65   if (representation().IsSmi() && HasNonSmiUse()) {
  66     UpdateRepresentation(
  67         Representation::Integer32(), h_infer, "use requirements");
  68   }
  69 }
  70
  71
  72 Representation HValue::RepresentationFromUses() {
  73   if (HasNoUses()) return Representation::None();
  74
  75   // Array of use counts for each representation.
  76   int use_count[Representation::kNumRepresentations] = { 0 };
  77
  78   for (HUseIterator it(uses()); !it.Done(); it.Advance()) {
  79     HValue* use = it.value();
  80     Representation rep = use->observed_input_representation(it.index());
  81     if (rep.IsNone()) continue;
  82     if (FLAG_trace_representation) {
  83       PrintF("#%d %s is used by #%d %s as %s%s\n",
  84              id(), Mnemonic(), use->id(), use->Mnemonic(), rep.Mnemonic(),
  85              (use->CheckFlag(kTruncatingToInt32) ? "-trunc" : ""));
  86     }
  87     use_count[rep.kind()] += 1;
  88   }
  89   if (IsPhi()) HPhi::cast(this)->AddIndirectUsesTo(&use_count[0]);
  90   int tagged_count = use_count[Representation::kTagged];
  91   int double_count = use_count[Representation::kDouble];
  92   int int32_count = use_count[Representation::kInteger32];
  93   int smi_count = use_count[Representation::kSmi];
  94
  95   if (tagged_count > 0) return Representation::Tagged();
  96   if (double_count > 0) return Representation::Double();
  97   if (int32_count > 0) return Representation::Integer32();
  98   if (smi_count > 0) return Representation::Smi();
  99
 100   return Representation::None();
 101 }
 102
 103
 104 void HValue::UpdateRepresentation(Representation new_rep,
 105                                   HInferRepresentationPhase* h_infer,
 106                                   const char* reason) {
 107   Representation r = representation();
 108   if (new_rep.is_more_general_than(r)) {
 109     if (CheckFlag(kCannotBeTagged) && new_rep.IsTagged()) return;
 110     if (FLAG_trace_representation) {
 111       PrintF("Changing #%d %s representation %s -> %s based on %s\n",
 112              id(), Mnemonic(), r.Mnemonic(), new_rep.Mnemonic(), reason);
 113     }
 114     ChangeRepresentation(new_rep);
 115     AddDependantsToWorklist(h_infer);
 116   }
 117 }
 118
 119
 120 void HValue::AddDependantsToWorklist(HInferRepresentationPhase* h_infer) {
 121   for (HUseIterator it(uses()); !it.Done(); it.Advance()) {
 122     h_infer->AddToWorklist(it.value());
 123   }
 124   for (int i = 0; i < OperandCount(); ++i) {
 125     h_infer->AddToWorklist(OperandAt(i));
 126   }
 127 }
 128
 129
 130 static int32_t ConvertAndSetOverflow(Representation r,
 131                                      int64_t result,
 132                                      bool* overflow) {
 133   if (r.IsSmi()) {
 134     if (result > Smi::kMaxValue) {
 135       *overflow = true;
 136       return Smi::kMaxValue;
 137     }
 138     if (result < Smi::kMinValue) {
 139       *overflow = true;
 140       return Smi::kMinValue;
 141     }
 142   } else {
 143     if (result > kMaxInt) {
 144       *overflow = true;
 145       return kMaxInt;
 146     }
 147     if (result < kMinInt) {
 148       *overflow = true;
 149       return kMinInt;
 150     }
 151   }
 152   return static_cast<int32_t>(result);
 153 }
 154
 155
 156 static int32_t AddWithoutOverflow(Representation r,
 157                                   int32_t a,
 158                                   int32_t b,
 159                                   bool* overflow) {
 160   int64_t result = static_cast<int64_t>(a) + static_cast<int64_t>(b);
 161   return ConvertAndSetOverflow(r, result, overflow);
 162 }
 163
 164
 165 static int32_t SubWithoutOverflow(Representation r,
 166                                   int32_t a,
 167                                   int32_t b,
 168                                   bool* overflow) {
 169   int64_t result = static_cast<int64_t>(a) - static_cast<int64_t>(b);
 170   return ConvertAndSetOverflow(r, result, overflow);
 171 }
 172
 173
 174 static int32_t MulWithoutOverflow(const Representation& r,
 175                                   int32_t a,
 176                                   int32_t b,
 177                                   bool* overflow) {
 178   int64_t result = static_cast<int64_t>(a) * static_cast<int64_t>(b);
 179   return ConvertAndSetOverflow(r, result, overflow);
 180 }
 181
 182
 183 int32_t Range::Mask() const {
 184   if (lower_ == upper_) return lower_;
 185   if (lower_ >= 0) {
 186     int32_t res = 1;
 187     while (res < upper_) {
 188       res = (res << 1) | 1;
 189     }
 190     return res;
 191   }
 192   return 0xffffffff;
 193 }
 194
 195
 196 void Range::AddConstant(int32_t value) {
 197   if (value == 0) return;
 198   bool may_overflow = false;  // Overflow is ignored here.
 199   Representation r = Representation::Integer32();
 200   lower_ = AddWithoutOverflow(r, lower_, value, &may_overflow);
 201   upper_ = AddWithoutOverflow(r, upper_, value, &may_overflow);
 202 #ifdef DEBUG
 203   Verify();
 204 #endif
 205 }
 206
 207
 208 void Range::Intersect(Range* other) {
 209   upper_ = Min(upper_, other->upper_);
 210   lower_ = Max(lower_, other->lower_);
 211   bool b = CanBeMinusZero() && other->CanBeMinusZero();
 212   set_can_be_minus_zero(b);
 213 }
 214
 215
 216 void Range::Union(Range* other) {
 217   upper_ = Max(upper_, other->upper_);
 218   lower_ = Min(lower_, other->lower_);
 219   bool b = CanBeMinusZero() || other->CanBeMinusZero();
 220   set_can_be_minus_zero(b);
 221 }
 222
 223
 224 void Range::CombinedMax(Range* other) {
 225   upper_ = Max(upper_, other->upper_);
 226   lower_ = Max(lower_, other->lower_);
 227   set_can_be_minus_zero(CanBeMinusZero() || other->CanBeMinusZero());
 228 }
 229
 230
 231 void Range::CombinedMin(Range* other) {
 232   upper_ = Min(upper_, other->upper_);
 233   lower_ = Min(lower_, other->lower_);
 234   set_can_be_minus_zero(CanBeMinusZero() || other->CanBeMinusZero());
 235 }
 236
 237
 238 void Range::Sar(int32_t value) {
 239   int32_t bits = value & 0x1F;
 240   lower_ = lower_ >> bits;
 241   upper_ = upper_ >> bits;
 242   set_can_be_minus_zero(false);
 243 }
 244
 245
 246 void Range::Shl(int32_t value) {
 247   int32_t bits = value & 0x1F;
 248   int old_lower = lower_;
 249   int old_upper = upper_;
 250   lower_ = lower_ << bits;
 251   upper_ = upper_ << bits;
 252   if (old_lower != lower_ >> bits || old_upper != upper_ >> bits) {
 253     upper_ = kMaxInt;
 254     lower_ = kMinInt;
 255   }
 256   set_can_be_minus_zero(false);
 257 }
 258
 259
 260 bool Range::AddAndCheckOverflow(const Representation& r, Range* other) {
 261   bool may_overflow = false;
 262   lower_ = AddWithoutOverflow(r, lower_, other->lower(), &may_overflow);
 263   upper_ = AddWithoutOverflow(r, upper_, other->upper(), &may_overflow);
 264   KeepOrder();
 265 #ifdef DEBUG
 266   Verify();
 267 #endif
 268   return may_overflow;
 269 }
 270
 271
 272 bool Range::SubAndCheckOverflow(const Representation& r, Range* other) {
 273   bool may_overflow = false;
 274   lower_ = SubWithoutOverflow(r, lower_, other->upper(), &may_overflow);
 275   upper_ = SubWithoutOverflow(r, upper_, other->lower(), &may_overflow);
 276   KeepOrder();
 277 #ifdef DEBUG
 278   Verify();
 279 #endif
 280   return may_overflow;
 281 }
 282
 283
 284 void Range::KeepOrder() {
 285   if (lower_ > upper_) {
 286     int32_t tmp = lower_;
 287     lower_ = upper_;
 288     upper_ = tmp;
 289   }
 290 }
 291
 292
 293 #ifdef DEBUG
 294 void Range::Verify() const {
 295   DCHECK(lower_ <= upper_);
 296 }
 297 #endif
 298
 299
 300 bool Range::MulAndCheckOverflow(const Representation& r, Range* other) {
 301   bool may_overflow = false;
 302   int v1 = MulWithoutOverflow(r, lower_, other->lower(), &may_overflow);
 303   int v2 = MulWithoutOverflow(r, lower_, other->upper(), &may_overflow);
 304   int v3 = MulWithoutOverflow(r, upper_, other->lower(), &may_overflow);
 305   int v4 = MulWithoutOverflow(r, upper_, other->upper(), &may_overflow);
 306   lower_ = Min(Min(v1, v2), Min(v3, v4));
 307   upper_ = Max(Max(v1, v2), Max(v3, v4));
 308 #ifdef DEBUG
 309   Verify();
 310 #endif
 311   return may_overflow;
 312 }
 313
 314
 315 bool HValue::IsDefinedAfter(HBasicBlock* other) const {
 316   return block()->block_id() > other->block_id();
 317 }
 318
 319
 320 HUseListNode* HUseListNode::tail() {
 321   // Skip and remove dead items in the use list.
 322   while (tail_ != NULL && tail_->value()->CheckFlag(HValue::kIsDead)) {
 323     tail_ = tail_->tail_;
 324   }
 325   return tail_;
 326 }
 327
 328
 329 bool HValue::CheckUsesForFlag(Flag f) const {
 330   for (HUseIterator it(uses()); !it.Done(); it.Advance()) {
 331     if (it.value()->IsSimulate()) continue;
 332     if (!it.value()->CheckFlag(f)) return false;
 333   }
 334   return true;
 335 }
 336
 337
 338 bool HValue::CheckUsesForFlag(Flag f, HValue** value) const {
 339   for (HUseIterator it(uses()); !it.Done(); it.Advance()) {
 340     if (it.value()->IsSimulate()) continue;
 341     if (!it.value()->CheckFlag(f)) {
 342       *value = it.value();
 343       return false;
 344     }
 345   }
 346   return true;
 347 }
 348
 349
 350 bool HValue::HasAtLeastOneUseWithFlagAndNoneWithout(Flag f) const {
 351   bool return_value = false;
 352   for (HUseIterator it(uses()); !it.Done(); it.Advance()) {
 353     if (it.value()->IsSimulate()) continue;
 354     if (!it.value()->CheckFlag(f)) return false;
 355     return_value = true;
 356   }
 357   return return_value;
 358 }
 359
 360
 361 HUseIterator::HUseIterator(HUseListNode* head) : next_(head) {
 362   Advance();
 363 }
 364
 365
 366 void HUseIterator::Advance() {
 367   current_ = next_;
 368   if (current_ != NULL) {
 369     next_ = current_->tail();
 370     value_ = current_->value();
 371     index_ = current_->index();
 372   }
 373 }
 374
 375
 376 int HValue::UseCount() const {
 377   int count = 0;
 378   for (HUseIterator it(uses()); !it.Done(); it.Advance()) ++count;
 379   return count;
 380 }
 381
 382
 383 HUseListNode* HValue::RemoveUse(HValue* value, int index) {
 384   HUseListNode* previous = NULL;
 385   HUseListNode* current = use_list_;
 386   while (current != NULL) {
 387     if (current->value() == value && current->index() == index) {
 388       if (previous == NULL) {
 389         use_list_ = current->tail();
 390       } else {
 391         previous->set_tail(current->tail());
 392       }
 393       break;
 394     }
 395
 396     previous = current;
 397     current = current->tail();
 398   }
 399
 400 #ifdef DEBUG
 401   // Do not reuse use list nodes in debug mode, zap them.
 402   if (current != NULL) {
 403     HUseListNode* temp =
 404         new(block()->zone())
 405         HUseListNode(current->value(), current->index(), NULL);
 406     current->Zap();
 407     current = temp;
 408   }
 409 #endif
 410   return current;
 411 }
 412
 413
 414 bool HValue::Equals(HValue* other) {
 415   if (other->opcode() != opcode()) return false;
 416   if (!other->representation().Equals(representation())) return false;
 417   if (!other->type_.Equals(type_)) return false;
 418   if (other->flags() != flags()) return false;
 419   if (OperandCount() != other->OperandCount()) return false;
 420   for (int i = 0; i < OperandCount(); ++i) {
 421     if (OperandAt(i)->id() != other->OperandAt(i)->id()) return false;
 422   }
 423   bool result = DataEquals(other);
 424   DCHECK(!result || Hashcode() == other->Hashcode());
 425   return result;
 426 }
 427
 428
 429 intptr_t HValue::Hashcode() {
 430   intptr_t result = opcode();
 431   int count = OperandCount();
 432   for (int i = 0; i < count; ++i) {
 433     result = result * 19 + OperandAt(i)->id() + (result >> 7);
 434   }
 435   return result;
 436 }
 437
 438
 439 const char* HValue::Mnemonic() const {
 440   switch (opcode()) {
 441 #define MAKE_CASE(type) case k##type: return #type;
 442     HYDROGEN_CONCRETE_INSTRUCTION_LIST(MAKE_CASE)
 443 #undef MAKE_CASE
 444     case kPhi: return "Phi";
 445     default: return "";
 446   }
 447 }
 448
 449
 450 bool HValue::CanReplaceWithDummyUses() {
 451   return FLAG_unreachable_code_elimination &&
 452       !(block()->IsReachable() ||
 453         IsBlockEntry() ||
 454         IsControlInstruction() ||
 455         IsArgumentsObject() ||
 456         IsCapturedObject() ||
 457         IsSimulate() ||
 458         IsEnterInlined() ||
 459         IsLeaveInlined());
 460 }
 461
 462
 463 bool HValue::IsInteger32Constant() {
 464   return IsConstant() && HConstant::cast(this)->HasInteger32Value();
 465 }
 466
 467
 468 int32_t HValue::GetInteger32Constant() {
 469   return HConstant::cast(this)->Integer32Value();
 470 }
 471
 472
 473 bool HValue::EqualsInteger32Constant(int32_t value) {
 474   return IsInteger32Constant() && GetInteger32Constant() == value;
 475 }
 476
 477
 478 void HValue::SetOperandAt(int index, HValue* value) {
 479   RegisterUse(index, value);
 480   InternalSetOperandAt(index, value);
 481 }
 482
 483
 484 void HValue::DeleteAndReplaceWith(HValue* other) {
 485   // We replace all uses first, so Delete can assert that there are none.
 486   if (other != NULL) ReplaceAllUsesWith(other);
 487   Kill();
 488   DeleteFromGraph();
 489 }
 490
 491
 492 void HValue::ReplaceAllUsesWith(HValue* other) {
 493   while (use_list_ != NULL) {
 494     HUseListNode* list_node = use_list_;
 495     HValue* value = list_node->value();
 496     DCHECK(!value->block()->IsStartBlock());
 497     value->InternalSetOperandAt(list_node->index(), other);
 498     use_list_ = list_node->tail();
 499     list_node->set_tail(other->use_list_);
 500     other->use_list_ = list_node;
 501   }
 502 }
 503
 504
 505 void HValue::Kill() {
 506   // Instead of going through the entire use list of each operand, we only
 507   // check the first item in each use list and rely on the tail() method to
 508   // skip dead items, removing them lazily next time we traverse the list.
 509   SetFlag(kIsDead);
 510   for (int i = 0; i < OperandCount(); ++i) {
 511     HValue* operand = OperandAt(i);
 512     if (operand == NULL) continue;
 513     HUseListNode* first = operand->use_list_;
 514     if (first != NULL && first->value()->CheckFlag(kIsDead)) {
 515       operand->use_list_ = first->tail();
 516     }
 517   }
 518 }
 519
 520
 521 void HValue::SetBlock(HBasicBlock* block) {
 522   DCHECK(block_ == NULL || block == NULL);
 523   block_ = block;
 524   if (id_ == kNoNumber && block != NULL) {
 525     id_ = block->graph()->GetNextValueID(this);
 526   }
 527 }
 528
 529
 530 OStream& operator<<(OStream& os, const HValue& v) { return v.PrintTo(os); }
 531
 532
 533 OStream& operator<<(OStream& os, const TypeOf& t) {
 534   if (t.value->representation().IsTagged() &&
 535       !t.value->type().Equals(HType::Tagged()))
 536     return os;
 537   return os << " type:" << t.value->type();
 538 }
 539
 540
 541 OStream& operator<<(OStream& os, const ChangesOf& c) {
 542   GVNFlagSet changes_flags = c.value->ChangesFlags();
 543   if (changes_flags.IsEmpty()) return os;
 544   os << " changes[";
 545   if (changes_flags == c.value->AllSideEffectsFlagSet()) {
 546     os << "*";
 547   } else {
 548     bool add_comma = false;
 549 #define PRINT_DO(Type)                   \
 550   if (changes_flags.Contains(k##Type)) { \
 551     if (add_comma) os << ",";            \
 552     add_comma = true;                    \
 553     os << #Type;                         \
 554   }
 555     GVN_TRACKED_FLAG_LIST(PRINT_DO);
 556     GVN_UNTRACKED_FLAG_LIST(PRINT_DO);
 557 #undef PRINT_DO
 558   }
 559   return os << "]";
 560 }
 561
 562
 563 bool HValue::HasMonomorphicJSObjectType() {
 564   return !GetMonomorphicJSObjectMap().is_null();
 565 }
 566
 567
 568 bool HValue::UpdateInferredType() {
 569   HType type = CalculateInferredType();
 570   bool result = (!type.Equals(type_));
 571   type_ = type;
 572   return result;
 573 }
 574
 575
 576 void HValue::RegisterUse(int index, HValue* new_value) {
 577   HValue* old_value = OperandAt(index);
 578   if (old_value == new_value) return;
 579
 580   HUseListNode* removed = NULL;
 581   if (old_value != NULL) {
 582     removed = old_value->RemoveUse(this, index);
 583   }
 584
 585   if (new_value != NULL) {
 586     if (removed == NULL) {
 587       new_value->use_list_ = new(new_value->block()->zone()) HUseListNode(
 588           this, index, new_value->use_list_);
 589     } else {
 590       removed->set_tail(new_value->use_list_);
 591       new_value->use_list_ = removed;
 592     }
 593   }
 594 }
 595
 596
 597 void HValue::AddNewRange(Range* r, Zone* zone) {
 598   if (!HasRange()) ComputeInitialRange(zone);
 599   if (!HasRange()) range_ = new(zone) Range();
 600   DCHECK(HasRange());
 601   r->StackUpon(range_);
 602   range_ = r;
 603 }
 604
 605
 606 void HValue::RemoveLastAddedRange() {
 607   DCHECK(HasRange());
 608   DCHECK(range_->next() != NULL);
 609   range_ = range_->next();
 610 }
 611
 612
 613 void HValue::ComputeInitialRange(Zone* zone) {
 614   DCHECK(!HasRange());
 615   range_ = InferRange(zone);
 616   DCHECK(HasRange());
 617 }
 618
 619
 620 OStream& operator<<(OStream& os, const HSourcePosition& p) {
 621   if (p.IsUnknown()) {
 622     return os << "<?>";
 623   } else if (FLAG_hydrogen_track_positions) {
 624     return os << "<" << p.inlining_id() << ":" << p.position() << ">";
 625   } else {
 626     return os << "<0:" << p.raw() << ">";
 627   }
 628 }
 629
 630
 631 OStream& HInstruction::PrintTo(OStream& os) const {  // NOLINT
 632   os << Mnemonic() << " ";
 633   PrintDataTo(os) << ChangesOf(this) << TypeOf(this);
 634   if (CheckFlag(HValue::kHasNoObservableSideEffects)) os << " [noOSE]";
 635   if (CheckFlag(HValue::kIsDead)) os << " [dead]";
 636   return os;
 637 }
 638
 639
 640 OStream& HInstruction::PrintDataTo(OStream& os) const {  // NOLINT
 641   for (int i = 0; i < OperandCount(); ++i) {
 642     if (i > 0) os << " ";
 643     os << NameOf(OperandAt(i));
 644   }
 645   return os;
 646 }
 647
 648
 649 void HInstruction::Unlink() {
 650   DCHECK(IsLinked());
 651   DCHECK(!IsControlInstruction());  // Must never move control instructions.
 652   DCHECK(!IsBlockEntry());  // Doesn't make sense to delete these.
 653   DCHECK(previous_ != NULL);
 654   previous_->next_ = next_;
 655   if (next_ == NULL) {
 656     DCHECK(block()->last() == this);
 657     block()->set_last(previous_);
 658   } else {
 659     next_->previous_ = previous_;
 660   }
 661   clear_block();
 662 }
 663
 664
 665 void HInstruction::InsertBefore(HInstruction* next) {
 666   DCHECK(!IsLinked());
 667   DCHECK(!next->IsBlockEntry());
 668   DCHECK(!IsControlInstruction());
 669   DCHECK(!next->block()->IsStartBlock());
 670   DCHECK(next->previous_ != NULL);
 671   HInstruction* prev = next->previous();
 672   prev->next_ = this;
 673   next->previous_ = this;
 674   next_ = next;
 675   previous_ = prev;
 676   SetBlock(next->block());
 677   if (!has_position() && next->has_position()) {
 678     set_position(next->position());
 679   }
 680 }
 681
 682
 683 void HInstruction::InsertAfter(HInstruction* previous) {
 684   DCHECK(!IsLinked());
 685   DCHECK(!previous->IsControlInstruction());
 686   DCHECK(!IsControlInstruction() || previous->next_ == NULL);
 687   HBasicBlock* block = previous->block();
 688   // Never insert anything except constants into the start block after finishing
 689   // it.
 690   if (block->IsStartBlock() && block->IsFinished() && !IsConstant()) {
 691     DCHECK(block->end()->SecondSuccessor() == NULL);
 692     InsertAfter(block->end()->FirstSuccessor()->first());
 693     return;
 694   }
 695
 696   // If we're inserting after an instruction with side-effects that is
 697   // followed by a simulate instruction, we need to insert after the
 698   // simulate instruction instead.
 699   HInstruction* next = previous->next_;
 700   if (previous->HasObservableSideEffects() && next != NULL) {
 701     DCHECK(next->IsSimulate());
 702     previous = next;
 703     next = previous->next_;
 704   }
 705
 706   previous_ = previous;
 707   next_ = next;
 708   SetBlock(block);
 709   previous->next_ = this;
 710   if (next != NULL) next->previous_ = this;
 711   if (block->last() == previous) {
 712     block->set_last(this);
 713   }
 714   if (!has_position() && previous->has_position()) {
 715     set_position(previous->position());
 716   }
 717 }
 718
 719
 720 bool HInstruction::Dominates(HInstruction* other) {
 721   if (block() != other->block()) {
 722     return block()->Dominates(other->block());
 723   }
 724   // Both instructions are in the same basic block. This instruction
 725   // should precede the other one in order to dominate it.
 726   for (HInstruction* instr = next(); instr != NULL; instr = instr->next()) {
 727     if (instr == other) {
 728       return true;
 729     }
 730   }
 731   return false;
 732 }
 733
 734
 735 #ifdef DEBUG
 736 void HInstruction::Verify() {
 737   // Verify that input operands are defined before use.
 738   HBasicBlock* cur_block = block();
 739   for (int i = 0; i < OperandCount(); ++i) {
 740     HValue* other_operand = OperandAt(i);
 741     if (other_operand == NULL) continue;
 742     HBasicBlock* other_block = other_operand->block();
 743     if (cur_block == other_block) {
 744       if (!other_operand->IsPhi()) {
 745         HInstruction* cur = this->previous();
 746         while (cur != NULL) {
 747           if (cur == other_operand) break;
 748           cur = cur->previous();
 749         }
 750         // Must reach other operand in the same block!
 751         DCHECK(cur == other_operand);
 752       }
 753     } else {
 754       // If the following assert fires, you may have forgotten an
 755       // AddInstruction.
 756       DCHECK(other_block->Dominates(cur_block));
 757     }
 758   }
 759
 760   // Verify that instructions that may have side-effects are followed
 761   // by a simulate instruction.
 762   if (HasObservableSideEffects() && !IsOsrEntry()) {
 763     DCHECK(next()->IsSimulate());
 764   }
 765
 766   // Verify that instructions that can be eliminated by GVN have overridden
 767   // HValue::DataEquals.  The default implementation is UNREACHABLE.  We
 768   // don't actually care whether DataEquals returns true or false here.
 769   if (CheckFlag(kUseGVN)) DataEquals(this);
 770
 771   // Verify that all uses are in the graph.
 772   for (HUseIterator use = uses(); !use.Done(); use.Advance()) {
 773     if (use.value()->IsInstruction()) {
 774       DCHECK(HInstruction::cast(use.value())->IsLinked());
 775     }
 776   }
 777 }
 778 #endif
 779
 780
 781 bool HInstruction::CanDeoptimize() {
 782   // TODO(titzer): make this a virtual method?
 783   switch (opcode()) {
 784     case HValue::kAbnormalExit:
 785     case HValue::kAccessArgumentsAt:
 786     case HValue::kAllocate:
 787     case HValue::kArgumentsElements:
 788     case HValue::kArgumentsLength:
 789     case HValue::kArgumentsObject:
 790     case HValue::kBlockEntry:
 791     case HValue::kBoundsCheckBaseIndexInformation:
 792     case HValue::kCallFunction:
 793     case HValue::kCallNew:
 794     case HValue::kCallNewArray:
 795     case HValue::kCallStub:
 796     case HValue::kCallWithDescriptor:
 797     case HValue::kCapturedObject:
 798     case HValue::kClassOfTestAndBranch:
 799     case HValue::kCompareGeneric:
 800     case HValue::kCompareHoleAndBranch:
 801     case HValue::kCompareMap:
 802     case HValue::kCompareMinusZeroAndBranch:
 803     case HValue::kCompareNumericAndBranch:
 804     case HValue::kCompareObjectEqAndBranch:
 805     case HValue::kConstant:
 806     case HValue::kConstructDouble:
 807     case HValue::kContext:
 808     case HValue::kDebugBreak:
 809     case HValue::kDeclareGlobals:
 810     case HValue::kDoubleBits:
 811     case HValue::kDummyUse:
 812     case HValue::kEnterInlined:
 813     case HValue::kEnvironmentMarker:
 814     case HValue::kForceRepresentation:
 815     case HValue::kGetCachedArrayIndex:
 816     case HValue::kGoto:
 817     case HValue::kHasCachedArrayIndexAndBranch:
 818     case HValue::kHasInstanceTypeAndBranch:
 819     case HValue::kInnerAllocatedObject:
 820     case HValue::kInstanceOf:
 821     case HValue::kInstanceOfKnownGlobal:
 822     case HValue::kIsConstructCallAndBranch:
 823     case HValue::kIsObjectAndBranch:
 824     case HValue::kIsSmiAndBranch:
 825     case HValue::kIsStringAndBranch:
 826     case HValue::kIsUndetectableAndBranch:
 827     case HValue::kLeaveInlined:
 828     case HValue::kLoadFieldByIndex:
 829     case HValue::kLoadGlobalGeneric:
 830     case HValue::kLoadNamedField:
 831     case HValue::kLoadNamedGeneric:
 832     case HValue::kLoadRoot:
 833     case HValue::kMapEnumLength:
 834     case HValue::kMathMinMax:
 835     case HValue::kParameter:
 836     case HValue::kPhi:
 837     case HValue::kPushArguments:
 838     case HValue::kRegExpLiteral:
 839     case HValue::kReturn:
 840     case HValue::kSeqStringGetChar:
 841     case HValue::kStoreCodeEntry:
 842     case HValue::kStoreFrameContext:
 843     case HValue::kStoreNamedField:
 844     case HValue::kStoreNamedGeneric:
 845     case HValue::kStringCharCodeAt:
 846     case HValue::kStringCharFromCode:
 847     case HValue::kThisFunction:
 848     case HValue::kTypeofIsAndBranch:
 849     case HValue::kUnknownOSRValue:
 850     case HValue::kUseConst:
 851     case HValue::kNullarySIMDOperation:
 852       return false;
 853
 854     case HValue::kStoreKeyed:
 855       return !CpuFeatures::SupportsSIMD128InCrankshaft() &&
 856              IsSIMD128ElementsKind(HStoreKeyed::cast(this)->elements_kind());
 857
 858     case HValue::kAdd:
 859     case HValue::kAllocateBlockContext:
 860     case HValue::kApplyArguments:
 861     case HValue::kBitwise:
 862     case HValue::kBoundsCheck:
 863     case HValue::kBranch:
 864     case HValue::kCallJSFunction:
 865     case HValue::kCallRuntime:
 866     case HValue::kChange:
 867     case HValue::kCheckHeapObject:
 868     case HValue::kCheckInstanceType:
 869     case HValue::kCheckMapValue:
 870     case HValue::kCheckMaps:
 871     case HValue::kCheckSmi:
 872     case HValue::kCheckValue:
 873     case HValue::kClampToUint8:
 874     case HValue::kDateField:
 875     case HValue::kDeoptimize:
 876     case HValue::kDiv:
 877     case HValue::kForInCacheArray:
 878     case HValue::kForInPrepareMap:
 879     case HValue::kFunctionLiteral:
 880     case HValue::kInvokeFunction:
 881     case HValue::kLoadContextSlot:
 882     case HValue::kLoadFunctionPrototype:
 883     case HValue::kLoadGlobalCell:
 884     case HValue::kLoadKeyed:
 885     case HValue::kLoadKeyedGeneric:
 886     case HValue::kMathFloorOfDiv:
 887     case HValue::kMod:
 888     case HValue::kMul:
 889     case HValue::kOsrEntry:
 890     case HValue::kPower:
 891     case HValue::kRor:
 892     case HValue::kSar:
 893     case HValue::kSeqStringSetChar:
 894     case HValue::kShl:
 895     case HValue::kShr:
 896     case HValue::kSimulate:
 897     case HValue::kStackCheck:
 898     case HValue::kStoreContextSlot:
 899     case HValue::kStoreGlobalCell:
 900     case HValue::kStoreKeyedGeneric:
 901     case HValue::kStringAdd:
 902     case HValue::kStringCompareAndBranch:
 903     case HValue::kSub:
 904     case HValue::kToFastProperties:
 905     case HValue::kTransitionElementsKind:
 906     case HValue::kTrapAllocationMemento:
 907     case HValue::kTypeof:
 908     case HValue::kUnaryMathOperation:
 909     case HValue::kWrapReceiver:
 910     case HValue::kUnarySIMDOperation:
 911     case HValue::kBinarySIMDOperation:
 912     case HValue::kTernarySIMDOperation:
 913     case HValue::kQuarternarySIMDOperation:
 914       return true;
 915   }
 916   UNREACHABLE();
 917   return true;
 918 }
 919
 920
 921 OStream& operator<<(OStream& os, const NameOf& v) {
 922   return os << v.value->representation().Mnemonic() << v.value->id();
 923 }
 924
 925 OStream& HDummyUse::PrintDataTo(OStream& os) const {  // NOLINT
 926   return os << NameOf(value());
 927 }
 928
 929
 930 OStream& HEnvironmentMarker::PrintDataTo(OStream& os) const {  // NOLINT
 931   return os << (kind() == BIND ? "bind" : "lookup") << " var[" << index()
 932             << "]";
 933 }
 934
 935
 936 OStream& HUnaryCall::PrintDataTo(OStream& os) const {  // NOLINT
 937   return os << NameOf(value()) << " #" << argument_count();
 938 }
 939
 940
 941 OStream& HCallJSFunction::PrintDataTo(OStream& os) const {  // NOLINT
 942   return os << NameOf(function()) << " #" << argument_count();
 943 }
 944
 945
 946 HCallJSFunction* HCallJSFunction::New(
 947     Zone* zone,
 948     HValue* context,
 949     HValue* function,
 950     int argument_count,
 951     bool pass_argument_count) {
 952   bool has_stack_check = false;
 953   if (function->IsConstant()) {
 954     HConstant* fun_const = HConstant::cast(function);
 955     Handle<JSFunction> jsfun =
 956         Handle<JSFunction>::cast(fun_const->handle(zone->isolate()));
 957     has_stack_check = !jsfun.is_null() &&
 958         (jsfun->code()->kind() == Code::FUNCTION ||
 959          jsfun->code()->kind() == Code::OPTIMIZED_FUNCTION);
 960   }
 961
 962   return new(zone) HCallJSFunction(
 963       function, argument_count, pass_argument_count,
 964       has_stack_check);
 965 }
 966
 967
 968 OStream& HBinaryCall::PrintDataTo(OStream& os) const {  // NOLINT
 969   return os << NameOf(first()) << " " << NameOf(second()) << " #"
 970             << argument_count();
 971 }
 972
 973
 974 void HBoundsCheck::ApplyIndexChange() {
 975   if (skip_check()) return;
 976
 977   DecompositionResult decomposition;
 978   bool index_is_decomposable = index()->TryDecompose(&decomposition);
 979   if (index_is_decomposable) {
 980     DCHECK(decomposition.base() == base());
 981     if (decomposition.offset() == offset() &&
 982         decomposition.scale() == scale()) return;
 983   } else {
 984     return;
 985   }
 986
 987   ReplaceAllUsesWith(index());
 988
 989   HValue* current_index = decomposition.base();
 990   int actual_offset = decomposition.offset() + offset();
 991   int actual_scale = decomposition.scale() + scale();
 992
 993   Zone* zone = block()->graph()->zone();
 994   HValue* context = block()->graph()->GetInvalidContext();
 995   if (actual_offset != 0) {
 996     HConstant* add_offset = HConstant::New(zone, context, actual_offset);
 997     add_offset->InsertBefore(this);
 998     HInstruction* add = HAdd::New(zone, context,
 999                                   current_index, add_offset);
1000     add->InsertBefore(this);
1001     add->AssumeRepresentation(index()->representation());
1002     add->ClearFlag(kCanOverflow);
1003     current_index = add;
1004   }
1005
1006   if (actual_scale != 0) {
1007     HConstant* sar_scale = HConstant::New(zone, context, actual_scale);
1008     sar_scale->InsertBefore(this);
1009     HInstruction* sar = HSar::New(zone, context,
1010                                   current_index, sar_scale);
1011     sar->InsertBefore(this);
1012     sar->AssumeRepresentation(index()->representation());
1013     current_index = sar;
1014   }
1015
1016   SetOperandAt(0, current_index);
1017
1018   base_ = NULL;
1019   offset_ = 0;
1020   scale_ = 0;
1021 }
1022
1023
1024 OStream& HBoundsCheck::PrintDataTo(OStream& os) const {  // NOLINT
1025   os << NameOf(index()) << " " << NameOf(length());
1026   if (base() != NULL && (offset() != 0 || scale() != 0)) {
1027     os << " base: ((";
1028     if (base() != index()) {
1029       os << NameOf(index());
1030     } else {
1031       os << "index";
1032     }
1033     os << " + " << offset() << ") >> " << scale() << ")";
1034   }
1035   if (skip_check()) os << " [DISABLED]";
1036   return os;
1037 }
1038
1039
1040 void HBoundsCheck::InferRepresentation(HInferRepresentationPhase* h_infer) {
1041   DCHECK(CheckFlag(kFlexibleRepresentation));
1042   HValue* actual_index = index()->ActualValue();
1043   HValue* actual_length = length()->ActualValue();
1044   Representation index_rep = actual_index->representation();
1045   Representation length_rep = actual_length->representation();
1046   if (index_rep.IsTagged() && actual_index->type().IsSmi()) {
1047     index_rep = Representation::Smi();
1048   }
1049   if (length_rep.IsTagged() && actual_length->type().IsSmi()) {
1050     length_rep = Representation::Smi();
1051   }
1052   Representation r = index_rep.generalize(length_rep);
1053   if (r.is_more_general_than(Representation::Integer32())) {
1054     r = Representation::Integer32();
1055   }
1056   UpdateRepresentation(r, h_infer, "boundscheck");
1057 }
1058
1059
1060 Range* HBoundsCheck::InferRange(Zone* zone) {
1061   Representation r = representation();
1062   if (r.IsSmiOrInteger32() && length()->HasRange()) {
1063     int upper = length()->range()->upper() - (allow_equality() ? 0 : 1);
1064     int lower = 0;
1065
1066     Range* result = new(zone) Range(lower, upper);
1067     if (index()->HasRange()) {
1068       result->Intersect(index()->range());
1069     }
1070
1071     // In case of Smi representation, clamp result to Smi::kMaxValue.
1072     if (r.IsSmi()) result->ClampToSmi();
1073     return result;
1074   }
1075   return HValue::InferRange(zone);
1076 }
1077
1078
1079 OStream& HBoundsCheckBaseIndexInformation::PrintDataTo(
1080     OStream& os) const {  // NOLINT
1081   // TODO(svenpanne) This 2nd base_index() looks wrong...
1082   return os << "base: " << NameOf(base_index())
1083             << ", check: " << NameOf(base_index());
1084 }
1085
1086
1087 OStream& HCallWithDescriptor::PrintDataTo(OStream& os) const {  // NOLINT
1088   for (int i = 0; i < OperandCount(); i++) {
1089     os << NameOf(OperandAt(i)) << " ";
1090   }
1091   return os << "#" << argument_count();
1092 }
1093
1094
1095 OStream& HCallNewArray::PrintDataTo(OStream& os) const {  // NOLINT
1096   os << ElementsKindToString(elements_kind()) << " ";
1097   return HBinaryCall::PrintDataTo(os);
1098 }
1099
1100
1101 OStream& HCallRuntime::PrintDataTo(OStream& os) const {  // NOLINT
1102   os << name()->ToCString().get() << " ";
1103   if (save_doubles() == kSaveFPRegs) os << "[save doubles] ";
1104   return os << "#" << argument_count();
1105 }
1106
1107
1108 OStream& HClassOfTestAndBranch::PrintDataTo(OStream& os) const {  // NOLINT
1109   return os << "class_of_test(" << NameOf(value()) << ", \""
1110             << class_name()->ToCString().get() << "\")";
1111 }
1112
1113
1114 OStream& HWrapReceiver::PrintDataTo(OStream& os) const {  // NOLINT
1115   return os << NameOf(receiver()) << " " << NameOf(function());
1116 }
1117
1118
1119 OStream& HAccessArgumentsAt::PrintDataTo(OStream& os) const {  // NOLINT
1120   return os << NameOf(arguments()) << "[" << NameOf(index()) << "], length "
1121             << NameOf(length());
1122 }
1123
1124
1125 OStream& HAllocateBlockContext::PrintDataTo(OStream& os) const {  // NOLINT
1126   return os << NameOf(context()) << " " << NameOf(function());
1127 }
1128
1129
1130 OStream& HControlInstruction::PrintDataTo(OStream& os) const {  // NOLINT
1131   os << " goto (";
1132   bool first_block = true;
1133   for (HSuccessorIterator it(this); !it.Done(); it.Advance()) {
1134     if (!first_block) os << ", ";
1135     os << *it.Current();
1136     first_block = false;
1137   }
1138   return os << ")";
1139 }
1140
1141
1142 OStream& HUnaryControlInstruction::PrintDataTo(OStream& os) const {  // NOLINT
1143   os << NameOf(value());
1144   return HControlInstruction::PrintDataTo(os);
1145 }
1146
1147
1148 OStream& HReturn::PrintDataTo(OStream& os) const {  // NOLINT
1149   return os << NameOf(value()) << " (pop " << NameOf(parameter_count())
1150             << " values)";
1151 }
1152
1153
1154 Representation HBranch::observed_input_representation(int index) {
1155   static const ToBooleanStub::Types tagged_types(
1156       ToBooleanStub::NULL_TYPE |
1157       ToBooleanStub::SPEC_OBJECT |
1158       ToBooleanStub::STRING |
1159       ToBooleanStub::SYMBOL);
1160   if (expected_input_types_.ContainsAnyOf(tagged_types)) {
1161     return Representation::Tagged();
1162   }
1163   if (expected_input_types_.Contains(ToBooleanStub::UNDEFINED)) {
1164     if (expected_input_types_.Contains(ToBooleanStub::HEAP_NUMBER)) {
1165       return Representation::Double();
1166     }
1167     return Representation::Tagged();
1168   }
1169   if (expected_input_types_.Contains(ToBooleanStub::HEAP_NUMBER)) {
1170     return Representation::Double();
1171   }
1172   if (expected_input_types_.Contains(ToBooleanStub::SMI)) {
1173     return Representation::Smi();
1174   }
1175   return Representation::None();
1176 }
1177
1178
1179 bool HBranch::KnownSuccessorBlock(HBasicBlock** block) {
1180   HValue* value = this->value();
1181   if (value->EmitAtUses()) {
1182     DCHECK(value->IsConstant());
1183     DCHECK(!value->representation().IsDouble());
1184     *block = HConstant::cast(value)->BooleanValue()
1185         ? FirstSuccessor()
1186         : SecondSuccessor();
1187     return true;
1188   }
1189   *block = NULL;
1190   return false;
1191 }
1192
1193
1194 OStream& HBranch::PrintDataTo(OStream& os) const {  // NOLINT
1195   return HUnaryControlInstruction::PrintDataTo(os) << " "
1196                                                    << expected_input_types();
1197 }
1198
1199
1200 OStream& HCompareMap::PrintDataTo(OStream& os) const {  // NOLINT
1201   os << NameOf(value()) << " (" << *map().handle() << ")";
1202   HControlInstruction::PrintDataTo(os);
1203   if (known_successor_index() == 0) {
1204     os << " [true]";
1205   } else if (known_successor_index() == 1) {
1206     os << " [false]";
1207   }
1208   return os;
1209 }
1210
1211
1212 const char* HUnaryMathOperation::OpName() const {
1213   switch (op()) {
1214     case kMathFloor:
1215       return "floor";
1216     case kMathFround:
1217       return "fround";
1218     case kMathRound:
1219       return "round";
1220     case kMathAbs:
1221       return "abs";
1222     case kMathLog:
1223       return "log";
1224     case kMathExp:
1225       return "exp";
1226     case kMathSqrt:
1227       return "sqrt";
1228     case kMathPowHalf:
1229       return "pow-half";
1230     case kMathClz32:
1231       return "clz32";
1232     default:
1233       UNREACHABLE();
1234       return NULL;
1235   }
1236 }
1237
1238
1239 Range* HUnaryMathOperation::InferRange(Zone* zone) {
1240   Representation r = representation();
1241   if (op() == kMathClz32) return new(zone) Range(0, 32);
1242   if (r.IsSmiOrInteger32() && value()->HasRange()) {
1243     if (op() == kMathAbs) {
1244       int upper = value()->range()->upper();
1245       int lower = value()->range()->lower();
1246       bool spans_zero = value()->range()->CanBeZero();
1247       // Math.abs(kMinInt) overflows its representation, on which the
1248       // instruction deopts. Hence clamp it to kMaxInt.
1249       int abs_upper = upper == kMinInt ? kMaxInt : abs(upper);
1250       int abs_lower = lower == kMinInt ? kMaxInt : abs(lower);
1251       Range* result =
1252           new(zone) Range(spans_zero ? 0 : Min(abs_lower, abs_upper),
1253                           Max(abs_lower, abs_upper));
1254       // In case of Smi representation, clamp Math.abs(Smi::kMinValue) to
1255       // Smi::kMaxValue.
1256       if (r.IsSmi()) result->ClampToSmi();
1257       return result;
1258     }
1259   }
1260   return HValue::InferRange(zone);
1261 }
1262
1263
1264 OStream& HUnaryMathOperation::PrintDataTo(OStream& os) const {  // NOLINT
1265   return os << OpName() << " " << NameOf(value());
1266 }
1267
1268
1269 OStream& HUnaryOperation::PrintDataTo(OStream& os) const {  // NOLINT
1270   return os << NameOf(value());
1271 }
1272
1273
1274 OStream& HHasInstanceTypeAndBranch::PrintDataTo(OStream& os) const {  // NOLINT
1275   os << NameOf(value());
1276   switch (from_) {
1277     case FIRST_JS_RECEIVER_TYPE:
1278       if (to_ == LAST_TYPE) os << " spec_object";
1279       break;
1280     case JS_REGEXP_TYPE:
1281       if (to_ == JS_REGEXP_TYPE) os << " reg_exp";
1282       break;
1283     case JS_ARRAY_TYPE:
1284       if (to_ == JS_ARRAY_TYPE) os << " array";
1285       break;
1286     case JS_FUNCTION_TYPE:
1287       if (to_ == JS_FUNCTION_TYPE) os << " function";
1288       break;
1289     default:
1290       break;
1291   }
1292   return os;
1293 }
1294
1295
1296 OStream& HTypeofIsAndBranch::PrintDataTo(OStream& os) const {  // NOLINT
1297   os << NameOf(value()) << " == " << type_literal()->ToCString().get();
1298   return HControlInstruction::PrintDataTo(os);
1299 }
1300
1301
1302 static String* TypeOfString(HConstant* constant, Isolate* isolate) {
1303   Heap* heap = isolate->heap();
1304   if (constant->HasNumberValue()) return heap->number_string();
1305   if (constant->IsUndetectable()) return heap->undefined_string();
1306   if (constant->HasStringValue()) return heap->string_string();
1307   switch (constant->GetInstanceType()) {
1308     case ODDBALL_TYPE: {
1309       Unique<Object> unique = constant->GetUnique();
1310       if (unique.IsKnownGlobal(heap->true_value()) ||
1311           unique.IsKnownGlobal(heap->false_value())) {
1312         return heap->boolean_string();
1313       }
1314       if (unique.IsKnownGlobal(heap->null_value())) {
1315         return heap->object_string();
1316       }
1317       DCHECK(unique.IsKnownGlobal(heap->undefined_value()));
1318       return heap->undefined_string();
1319     }
1320     case SYMBOL_TYPE:
1321       return heap->symbol_string();
1322     case JS_FUNCTION_TYPE:
1323     case JS_FUNCTION_PROXY_TYPE:
1324       return heap->function_string();
1325     default:
1326       return heap->object_string();
1327   }
1328 }
1329
1330
1331 bool HTypeofIsAndBranch::KnownSuccessorBlock(HBasicBlock** block) {
1332   if (FLAG_fold_constants && value()->IsConstant()) {
1333     HConstant* constant = HConstant::cast(value());
1334     String* type_string = TypeOfString(constant, isolate());
1335     bool same_type = type_literal_.IsKnownGlobal(type_string);
1336     *block = same_type ? FirstSuccessor() : SecondSuccessor();
1337     return true;
1338   } else if (value()->representation().IsSpecialization()) {
1339     bool number_type =
1340         type_literal_.IsKnownGlobal(isolate()->heap()->number_string());
1341     *block = number_type ? FirstSuccessor() : SecondSuccessor();
1342     return true;
1343   } else if (value()->representation().IsFloat32x4()) {
1344     bool float32x4_type =
1345         type_literal_.IsKnownGlobal(isolate()->heap()->float32x4_string());
1346     *block = float32x4_type ? FirstSuccessor() : SecondSuccessor();
1347     return true;
1348   } else if (value()->representation().IsFloat64x2()) {
1349     bool float64x2_type =
1350         type_literal_.IsKnownGlobal(isolate()->heap()->float64x2_string());
1351     *block = float64x2_type ? FirstSuccessor() : SecondSuccessor();
1352     return true;
1353   } else if (value()->representation().IsInt32x4()) {
1354     bool int32x4_type =
1355         type_literal_.IsKnownGlobal(isolate()->heap()->int32x4_string());
1356     *block = int32x4_type ? FirstSuccessor() : SecondSuccessor();
1357     return true;
1358   }
1359
1360   *block = NULL;
1361   return false;
1362 }
1363
1364
1365 OStream& HCheckMapValue::PrintDataTo(OStream& os) const {  // NOLINT
1366   return os << NameOf(value()) << " " << NameOf(map());
1367 }
1368
1369
1370 HValue* HCheckMapValue::Canonicalize() {
1371   if (map()->IsConstant()) {
1372     HConstant* c_map = HConstant::cast(map());
1373     return HCheckMaps::CreateAndInsertAfter(
1374         block()->graph()->zone(), value(), c_map->MapValue(),
1375         c_map->HasStableMapValue(), this);
1376   }
1377   return this;
1378 }
1379
1380
1381 OStream& HForInPrepareMap::PrintDataTo(OStream& os) const {  // NOLINT
1382   return os << NameOf(enumerable());
1383 }
1384
1385
1386 OStream& HForInCacheArray::PrintDataTo(OStream& os) const {  // NOLINT
1387   return os << NameOf(enumerable()) << " " << NameOf(map()) << "[" << idx_
1388             << "]";
1389 }
1390
1391
1392 OStream& HLoadFieldByIndex::PrintDataTo(OStream& os) const {  // NOLINT
1393   return os << NameOf(object()) << " " << NameOf(index());
1394 }
1395
1396
1397 static bool MatchLeftIsOnes(HValue* l, HValue* r, HValue** negated) {
1398   if (!l->EqualsInteger32Constant(~0)) return false;
1399   *negated = r;
1400   return true;
1401 }
1402
1403
1404 static bool MatchNegationViaXor(HValue* instr, HValue** negated) {
1405   if (!instr->IsBitwise()) return false;
1406   HBitwise* b = HBitwise::cast(instr);
1407   return (b->op() == Token::BIT_XOR) &&
1408       (MatchLeftIsOnes(b->left(), b->right(), negated) ||
1409        MatchLeftIsOnes(b->right(), b->left(), negated));
1410 }
1411
1412
1413 static bool MatchDoubleNegation(HValue* instr, HValue** arg) {
1414   HValue* negated;
1415   return MatchNegationViaXor(instr, &negated) &&
1416       MatchNegationViaXor(negated, arg);
1417 }
1418
1419
1420 HValue* HBitwise::Canonicalize() {
1421   if (!representation().IsSmiOrInteger32()) return this;
1422   // If x is an int32, then x & -1 == x, x | 0 == x and x ^ 0 == x.
1423   int32_t nop_constant = (op() == Token::BIT_AND) ? -1 : 0;
1424   if (left()->EqualsInteger32Constant(nop_constant) &&
1425       !right()->CheckFlag(kUint32)) {
1426     return right();
1427   }
1428   if (right()->EqualsInteger32Constant(nop_constant) &&
1429       !left()->CheckFlag(kUint32)) {
1430     return left();
1431   }
1432   // Optimize double negation, a common pattern used for ToInt32(x).
1433   HValue* arg;
1434   if (MatchDoubleNegation(this, &arg) && !arg->CheckFlag(kUint32)) {
1435     return arg;
1436   }
1437   return this;
1438 }
1439
1440
1441 Representation HAdd::RepresentationFromInputs() {
1442   Representation left_rep = left()->representation();
1443   if (left_rep.IsExternal()) {
1444     return Representation::External();
1445   }
1446   return HArithmeticBinaryOperation::RepresentationFromInputs();
1447 }
1448
1449
1450 Representation HAdd::RequiredInputRepresentation(int index) {
1451   if (index == 2) {
1452     Representation left_rep = left()->representation();
1453     if (left_rep.IsExternal()) {
1454       return Representation::Integer32();
1455     }
1456   }
1457   return HArithmeticBinaryOperation::RequiredInputRepresentation(index);
1458 }
1459
1460
1461 static bool IsIdentityOperation(HValue* arg1, HValue* arg2, int32_t identity) {
1462   return arg1->representation().IsSpecialization() &&
1463     arg2->EqualsInteger32Constant(identity);
1464 }
1465
1466
1467 HValue* HAdd::Canonicalize() {
1468   // Adding 0 is an identity operation except in case of -0: -0 + 0 = +0
1469   if (IsIdentityOperation(left(), right(), 0) &&
1470       !left()->representation().IsDouble()) {  // Left could be -0.
1471     return left();
1472   }
1473   if (IsIdentityOperation(right(), left(), 0) &&
1474       !left()->representation().IsDouble()) {  // Right could be -0.
1475     return right();
1476   }
1477   return this;
1478 }
1479
1480
1481 HValue* HSub::Canonicalize() {
1482   if (IsIdentityOperation(left(), right(), 0)) return left();
1483   return this;
1484 }
1485
1486
1487 HValue* HMul::Canonicalize() {
1488   if (IsIdentityOperation(left(), right(), 1)) return left();
1489   if (IsIdentityOperation(right(), left(), 1)) return right();
1490   return this;
1491 }
1492
1493
1494 bool HMul::MulMinusOne() {
1495   if (left()->EqualsInteger32Constant(-1) ||
1496       right()->EqualsInteger32Constant(-1)) {
1497     return true;
1498   }
1499
1500   return false;
1501 }
1502
1503
1504 HValue* HMod::Canonicalize() {
1505   return this;
1506 }
1507
1508
1509 HValue* HDiv::Canonicalize() {
1510   if (IsIdentityOperation(left(), right(), 1)) return left();
1511   return this;
1512 }
1513
1514
1515 HValue* HChange::Canonicalize() {
1516   return (from().Equals(to())) ? value() : this;
1517 }
1518
1519
1520 HValue* HWrapReceiver::Canonicalize() {
1521   if (HasNoUses()) return NULL;
1522   if (receiver()->type().IsJSObject()) {
1523     return receiver();
1524   }
1525   return this;
1526 }
1527
1528
1529 OStream& HTypeof::PrintDataTo(OStream& os) const {  // NOLINT
1530   return os << NameOf(value());
1531 }
1532
1533
1534 HInstruction* HForceRepresentation::New(Zone* zone, HValue* context,
1535        HValue* value, Representation representation) {
1536   if (FLAG_fold_constants && value->IsConstant()) {
1537     HConstant* c = HConstant::cast(value);
1538     if (c->HasNumberValue()) {
1539       double double_res = c->DoubleValue();
1540       if (representation.IsDouble()) {
1541         return HConstant::New(zone, context, double_res);
1542
1543       } else if (representation.CanContainDouble(double_res)) {
1544         return HConstant::New(zone, context,
1545                               static_cast<int32_t>(double_res),
1546                               representation);
1547       }
1548     }
1549   }
1550   return new(zone) HForceRepresentation(value, representation);
1551 }
1552
1553
1554 OStream& HForceRepresentation::PrintDataTo(OStream& os) const {  // NOLINT
1555   return os << representation().Mnemonic() << " " << NameOf(value());
1556 }
1557
1558
1559 OStream& HChange::PrintDataTo(OStream& os) const {  // NOLINT
1560   HUnaryOperation::PrintDataTo(os);
1561   os << " " << from().Mnemonic() << " to " << to().Mnemonic();
1562
1563   if (CanTruncateToSmi()) os << " truncating-smi";
1564   if (CanTruncateToInt32()) os << " truncating-int32";
1565   if (CheckFlag(kBailoutOnMinusZero)) os << " -0?";
1566   if (CheckFlag(kAllowUndefinedAsNaN)) os << " allow-undefined-as-nan";
1567   return os;
1568 }
1569
1570
1571 HValue* HUnaryMathOperation::Canonicalize() {
1572   if (op() == kMathRound || op() == kMathFloor) {
1573     HValue* val = value();
1574     if (val->IsChange()) val = HChange::cast(val)->value();
1575     if (val->representation().IsSmiOrInteger32()) {
1576       if (val->representation().Equals(representation())) return val;
1577       return Prepend(new(block()->zone()) HChange(
1578           val, representation(), false, false));
1579     }
1580   }
1581   if (op() == kMathFloor && value()->IsDiv() && value()->HasOneUse()) {
1582     HDiv* hdiv = HDiv::cast(value());
1583
1584     HValue* left = hdiv->left();
1585     if (left->representation().IsInteger32()) {
1586       // A value with an integer representation does not need to be transformed.
1587     } else if (left->IsChange() && HChange::cast(left)->from().IsInteger32()) {
1588       // A change from an integer32 can be replaced by the integer32 value.
1589       left = HChange::cast(left)->value();
1590     } else if (hdiv->observed_input_representation(1).IsSmiOrInteger32()) {
1591       left = Prepend(new(block()->zone()) HChange(
1592           left, Representation::Integer32(), false, false));
1593     } else {
1594       return this;
1595     }
1596
1597     HValue* right = hdiv->right();
1598     if (right->IsInteger32Constant()) {
1599       right = Prepend(HConstant::cast(right)->CopyToRepresentation(
1600           Representation::Integer32(), right->block()->zone()));
1601     } else if (right->representation().IsInteger32()) {
1602       // A value with an integer representation does not need to be transformed.
1603     } else if (right->IsChange() &&
1604                HChange::cast(right)->from().IsInteger32()) {
1605       // A change from an integer32 can be replaced by the integer32 value.
1606       right = HChange::cast(right)->value();
1607     } else if (hdiv->observed_input_representation(2).IsSmiOrInteger32()) {
1608       right = Prepend(new(block()->zone()) HChange(
1609           right, Representation::Integer32(), false, false));
1610     } else {
1611       return this;
1612     }
1613
1614     return Prepend(HMathFloorOfDiv::New(
1615         block()->zone(), context(), left, right));
1616   }
1617   return this;
1618 }
1619
1620
1621 HValue* HCheckInstanceType::Canonicalize() {
1622   if ((check_ == IS_SPEC_OBJECT && value()->type().IsJSObject()) ||
1623       (check_ == IS_JS_ARRAY && value()->type().IsJSArray()) ||
1624       (check_ == IS_STRING && value()->type().IsString())) {
1625     return value();
1626   }
1627
1628   if (check_ == IS_INTERNALIZED_STRING && value()->IsConstant()) {
1629     if (HConstant::cast(value())->HasInternalizedStringValue()) {
1630       return value();
1631     }
1632   }
1633   return this;
1634 }
1635
1636
1637 void HCheckInstanceType::GetCheckInterval(InstanceType* first,
1638                                           InstanceType* last) {
1639   DCHECK(is_interval_check());
1640   switch (check_) {
1641     case IS_SPEC_OBJECT:
1642       *first = FIRST_SPEC_OBJECT_TYPE;
1643       *last = LAST_SPEC_OBJECT_TYPE;
1644       return;
1645     case IS_JS_ARRAY:
1646       *first = *last = JS_ARRAY_TYPE;
1647       return;
1648     default:
1649       UNREACHABLE();
1650   }
1651 }
1652
1653
1654 void HCheckInstanceType::GetCheckMaskAndTag(uint8_t* mask, uint8_t* tag) {
1655   DCHECK(!is_interval_check());
1656   switch (check_) {
1657     case IS_STRING:
1658       *mask = kIsNotStringMask;
1659       *tag = kStringTag;
1660       return;
1661     case IS_INTERNALIZED_STRING:
1662       *mask = kIsNotStringMask | kIsNotInternalizedMask;
1663       *tag = kInternalizedTag;
1664       return;
1665     default:
1666       UNREACHABLE();
1667   }
1668 }
1669
1670
1671 OStream& HCheckMaps::PrintDataTo(OStream& os) const {  // NOLINT
1672   os << NameOf(value()) << " [" << *maps()->at(0).handle();
1673   for (int i = 1; i < maps()->size(); ++i) {
1674     os << "," << *maps()->at(i).handle();
1675   }
1676   os << "]";
1677   if (IsStabilityCheck()) os << "(stability-check)";
1678   return os;
1679 }
1680
1681
1682 HValue* HCheckMaps::Canonicalize() {
1683   if (!IsStabilityCheck() && maps_are_stable() && value()->IsConstant()) {
1684     HConstant* c_value = HConstant::cast(value());
1685     if (c_value->HasObjectMap()) {
1686       for (int i = 0; i < maps()->size(); ++i) {
1687         if (c_value->ObjectMap() == maps()->at(i)) {
1688           if (maps()->size() > 1) {
1689             set_maps(new(block()->graph()->zone()) UniqueSet<Map>(
1690                     maps()->at(i), block()->graph()->zone()));
1691           }
1692           MarkAsStabilityCheck();
1693           break;
1694         }
1695       }
1696     }
1697   }
1698   return this;
1699 }
1700
1701
1702 OStream& HCheckValue::PrintDataTo(OStream& os) const {  // NOLINT
1703   return os << NameOf(value()) << " " << Brief(*object().handle());
1704 }
1705
1706
1707 HValue* HCheckValue::Canonicalize() {
1708   return (value()->IsConstant() &&
1709           HConstant::cast(value())->EqualsUnique(object_)) ? NULL : this;
1710 }
1711
1712
1713 const char* HCheckInstanceType::GetCheckName() const {
1714   switch (check_) {
1715     case IS_SPEC_OBJECT: return "object";
1716     case IS_JS_ARRAY: return "array";
1717     case IS_STRING: return "string";
1718     case IS_INTERNALIZED_STRING: return "internalized_string";
1719   }
1720   UNREACHABLE();
1721   return "";
1722 }
1723
1724
1725 OStream& HCheckInstanceType::PrintDataTo(OStream& os) const {  // NOLINT
1726   os << GetCheckName() << " ";
1727   return HUnaryOperation::PrintDataTo(os);
1728 }
1729
1730
1731 OStream& HCallStub::PrintDataTo(OStream& os) const {  // NOLINT
1732   os << CodeStub::MajorName(major_key_, false) << " ";
1733   return HUnaryCall::PrintDataTo(os);
1734 }
1735
1736
1737 OStream& HUnknownOSRValue::PrintDataTo(OStream& os) const {  // NOLINT
1738   const char* type = "expression";
1739   if (environment_->is_local_index(index_)) type = "local";
1740   if (environment_->is_special_index(index_)) type = "special";
1741   if (environment_->is_parameter_index(index_)) type = "parameter";
1742   return os << type << " @ " << index_;
1743 }
1744
1745
1746 OStream& HInstanceOf::PrintDataTo(OStream& os) const {  // NOLINT
1747   return os << NameOf(left()) << " " << NameOf(right()) << " "
1748             << NameOf(context());
1749 }
1750
1751
1752 Range* HValue::InferRange(Zone* zone) {
1753   Range* result;
1754   if (representation().IsSmi() || type().IsSmi()) {
1755     result = new(zone) Range(Smi::kMinValue, Smi::kMaxValue);
1756     result->set_can_be_minus_zero(false);
1757   } else {
1758     result = new(zone) Range();
1759     result->set_can_be_minus_zero(!CheckFlag(kAllUsesTruncatingToInt32));
1760     // TODO(jkummerow): The range cannot be minus zero when the upper type
1761     // bound is Integer32.
1762   }
1763   return result;
1764 }
1765
1766
1767 Range* HChange::InferRange(Zone* zone) {
1768   Range* input_range = value()->range();
1769   if (from().IsInteger32() && !value()->CheckFlag(HInstruction::kUint32) &&
1770       (to().IsSmi() ||
1771        (to().IsTagged() &&
1772         input_range != NULL &&
1773         input_range->IsInSmiRange()))) {
1774     set_type(HType::Smi());
1775     ClearChangesFlag(kNewSpacePromotion);
1776   }
1777   if (to().IsSmiOrTagged() &&
1778       input_range != NULL &&
1779       input_range->IsInSmiRange() &&
1780       (!SmiValuesAre32Bits() ||
1781        !value()->CheckFlag(HValue::kUint32) ||
1782        input_range->upper() != kMaxInt)) {
1783     // The Range class can't express upper bounds in the (kMaxInt, kMaxUint32]
1784     // interval, so we treat kMaxInt as a sentinel for this entire interval.
1785     ClearFlag(kCanOverflow);
1786   }
1787   Range* result = (input_range != NULL)
1788       ? input_range->Copy(zone)
1789       : HValue::InferRange(zone);
1790   result->set_can_be_minus_zero(!to().IsSmiOrInteger32() ||
1791                                 !(CheckFlag(kAllUsesTruncatingToInt32) ||
1792                                   CheckFlag(kAllUsesTruncatingToSmi)));
1793   if (to().IsSmi()) result->ClampToSmi();
1794   return result;
1795 }
1796
1797
1798 Range* HConstant::InferRange(Zone* zone) {
1799   if (has_int32_value_) {
1800     Range* result = new(zone) Range(int32_value_, int32_value_);
1801     result->set_can_be_minus_zero(false);
1802     return result;
1803   }
1804   return HValue::InferRange(zone);
1805 }
1806
1807
1808 HSourcePosition HPhi::position() const {
1809   return block()->first()->position();
1810 }
1811
1812
1813 Range* HPhi::InferRange(Zone* zone) {
1814   Representation r = representation();
1815   if (r.IsSmiOrInteger32()) {
1816     if (block()->IsLoopHeader()) {
1817       Range* range = r.IsSmi()
1818           ? new(zone) Range(Smi::kMinValue, Smi::kMaxValue)
1819           : new(zone) Range(kMinInt, kMaxInt);
1820       return range;
1821     } else {
1822       Range* range = OperandAt(0)->range()->Copy(zone);
1823       for (int i = 1; i < OperandCount(); ++i) {
1824         range->Union(OperandAt(i)->range());
1825       }
1826       return range;
1827     }
1828   } else {
1829     return HValue::InferRange(zone);
1830   }
1831 }
1832
1833
1834 Range* HAdd::InferRange(Zone* zone) {
1835   Representation r = representation();
1836   if (r.IsSmiOrInteger32()) {
1837     Range* a = left()->range();
1838     Range* b = right()->range();
1839     Range* res = a->Copy(zone);
1840     if (!res->AddAndCheckOverflow(r, b) ||
1841         (r.IsInteger32() && CheckFlag(kAllUsesTruncatingToInt32)) ||
1842         (r.IsSmi() && CheckFlag(kAllUsesTruncatingToSmi))) {
1843       ClearFlag(kCanOverflow);
1844     }
1845     res->set_can_be_minus_zero(!CheckFlag(kAllUsesTruncatingToSmi) &&
1846                                !CheckFlag(kAllUsesTruncatingToInt32) &&
1847                                a->CanBeMinusZero() && b->CanBeMinusZero());
1848     return res;
1849   } else {
1850     return HValue::InferRange(zone);
1851   }
1852 }
1853
1854
1855 Range* HSub::InferRange(Zone* zone) {
1856   Representation r = representation();
1857   if (r.IsSmiOrInteger32()) {
1858     Range* a = left()->range();
1859     Range* b = right()->range();
1860     Range* res = a->Copy(zone);
1861     if (!res->SubAndCheckOverflow(r, b) ||
1862         (r.IsInteger32() && CheckFlag(kAllUsesTruncatingToInt32)) ||
1863         (r.IsSmi() && CheckFlag(kAllUsesTruncatingToSmi))) {
1864       ClearFlag(kCanOverflow);
1865     }
1866     res->set_can_be_minus_zero(!CheckFlag(kAllUsesTruncatingToSmi) &&
1867                                !CheckFlag(kAllUsesTruncatingToInt32) &&
1868                                a->CanBeMinusZero() && b->CanBeZero());
1869     return res;
1870   } else {
1871     return HValue::InferRange(zone);
1872   }
1873 }
1874
1875
1876 Range* HMul::InferRange(Zone* zone) {
1877   Representation r = representation();
1878   if (r.IsSmiOrInteger32()) {
1879     Range* a = left()->range();
1880     Range* b = right()->range();
1881     Range* res = a->Copy(zone);
1882     if (!res->MulAndCheckOverflow(r, b) ||
1883         (((r.IsInteger32() && CheckFlag(kAllUsesTruncatingToInt32)) ||
1884          (r.IsSmi() && CheckFlag(kAllUsesTruncatingToSmi))) &&
1885          MulMinusOne())) {
1886       // Truncated int multiplication is too precise and therefore not the
1887       // same as converting to Double and back.
1888       // Handle truncated integer multiplication by -1 special.
1889       ClearFlag(kCanOverflow);
1890     }
1891     res->set_can_be_minus_zero(!CheckFlag(kAllUsesTruncatingToSmi) &&
1892                                !CheckFlag(kAllUsesTruncatingToInt32) &&
1893                                ((a->CanBeZero() && b->CanBeNegative()) ||
1894                                 (a->CanBeNegative() && b->CanBeZero())));
1895     return res;
1896   } else {
1897     return HValue::InferRange(zone);
1898   }
1899 }
1900
1901
1902 Range* HDiv::InferRange(Zone* zone) {
1903   if (representation().IsInteger32()) {
1904     Range* a = left()->range();
1905     Range* b = right()->range();
1906     Range* result = new(zone) Range();
1907     result->set_can_be_minus_zero(!CheckFlag(kAllUsesTruncatingToInt32) &&
1908                                   (a->CanBeMinusZero() ||
1909                                    (a->CanBeZero() && b->CanBeNegative())));
1910     if (!a->Includes(kMinInt) || !b->Includes(-1)) {
1911       ClearFlag(kCanOverflow);
1912     }
1913
1914     if (!b->CanBeZero()) {
1915       ClearFlag(kCanBeDivByZero);
1916     }
1917     return result;
1918   } else {
1919     return HValue::InferRange(zone);
1920   }
1921 }
1922
1923
1924 Range* HMathFloorOfDiv::InferRange(Zone* zone) {
1925   if (representation().IsInteger32()) {
1926     Range* a = left()->range();
1927     Range* b = right()->range();
1928     Range* result = new(zone) Range();
1929     result->set_can_be_minus_zero(!CheckFlag(kAllUsesTruncatingToInt32) &&
1930                                   (a->CanBeMinusZero() ||
1931                                    (a->CanBeZero() && b->CanBeNegative())));
1932     if (!a->Includes(kMinInt)) {
1933       ClearFlag(kLeftCanBeMinInt);
1934     }
1935
1936     if (!a->CanBeNegative()) {
1937       ClearFlag(HValue::kLeftCanBeNegative);
1938     }
1939
1940     if (!a->CanBePositive()) {
1941       ClearFlag(HValue::kLeftCanBePositive);
1942     }
1943
1944     if (!a->Includes(kMinInt) || !b->Includes(-1)) {
1945       ClearFlag(kCanOverflow);
1946     }
1947
1948     if (!b->CanBeZero()) {
1949       ClearFlag(kCanBeDivByZero);
1950     }
1951     return result;
1952   } else {
1953     return HValue::InferRange(zone);
1954   }
1955 }
1956
1957
1958 // Returns the absolute value of its argument minus one, avoiding undefined
1959 // behavior at kMinInt.
1960 static int32_t AbsMinus1(int32_t a) { return a < 0 ? -(a + 1) : (a - 1); }
1961
1962
1963 Range* HMod::InferRange(Zone* zone) {
1964   if (representation().IsInteger32()) {
1965     Range* a = left()->range();
1966     Range* b = right()->range();
1967
1968     // The magnitude of the modulus is bounded by the right operand.
1969     int32_t positive_bound = Max(AbsMinus1(b->lower()), AbsMinus1(b->upper()));
1970
1971     // The result of the modulo operation has the sign of its left operand.
1972     bool left_can_be_negative = a->CanBeMinusZero() || a->CanBeNegative();
1973     Range* result = new(zone) Range(left_can_be_negative ? -positive_bound : 0,
1974                                     a->CanBePositive() ? positive_bound : 0);
1975
1976     result->set_can_be_minus_zero(!CheckFlag(kAllUsesTruncatingToInt32) &&
1977                                   left_can_be_negative);
1978
1979     if (!a->CanBeNegative()) {
1980       ClearFlag(HValue::kLeftCanBeNegative);
1981     }
1982
1983     if (!a->Includes(kMinInt) || !b->Includes(-1)) {
1984       ClearFlag(HValue::kCanOverflow);
1985     }
1986
1987     if (!b->CanBeZero()) {
1988       ClearFlag(HValue::kCanBeDivByZero);
1989     }
1990     return result;
1991   } else {
1992     return HValue::InferRange(zone);
1993   }
1994 }
1995
1996
1997 InductionVariableData* InductionVariableData::ExaminePhi(HPhi* phi) {
1998   if (phi->block()->loop_information() == NULL) return NULL;
1999   if (phi->OperandCount() != 2) return NULL;
2000   int32_t candidate_increment;
2001
2002   candidate_increment = ComputeIncrement(phi, phi->OperandAt(0));
2003   if (candidate_increment != 0) {
2004     return new(phi->block()->graph()->zone())
2005         InductionVariableData(phi, phi->OperandAt(1), candidate_increment);
2006   }
2007
2008   candidate_increment = ComputeIncrement(phi, phi->OperandAt(1));
2009   if (candidate_increment != 0) {
2010     return new(phi->block()->graph()->zone())
2011         InductionVariableData(phi, phi->OperandAt(0), candidate_increment);
2012   }
2013
2014   return NULL;
2015 }
2016
2017
2018 /*
2019  * This function tries to match the following patterns (and all the relevant
2020  * variants related to |, & and + being commutative):
2021  * base | constant_or_mask
2022  * base & constant_and_mask
2023  * (base + constant_offset) & constant_and_mask
2024  * (base - constant_offset) & constant_and_mask
2025  */
2026 void InductionVariableData::DecomposeBitwise(
2027     HValue* value,
2028     BitwiseDecompositionResult* result) {
2029   HValue* base = IgnoreOsrValue(value);
2030   result->base = value;
2031
2032   if (!base->representation().IsInteger32()) return;
2033
2034   if (base->IsBitwise()) {
2035     bool allow_offset = false;
2036     int32_t mask = 0;
2037
2038     HBitwise* bitwise = HBitwise::cast(base);
2039     if (bitwise->right()->IsInteger32Constant()) {
2040       mask = bitwise->right()->GetInteger32Constant();
2041       base = bitwise->left();
2042     } else if (bitwise->left()->IsInteger32Constant()) {
2043       mask = bitwise->left()->GetInteger32Constant();
2044       base = bitwise->right();
2045     } else {
2046       return;
2047     }
2048     if (bitwise->op() == Token::BIT_AND) {
2049       result->and_mask = mask;
2050       allow_offset = true;
2051     } else if (bitwise->op() == Token::BIT_OR) {
2052       result->or_mask = mask;
2053     } else {
2054       return;
2055     }
2056
2057     result->context = bitwise->context();
2058
2059     if (allow_offset) {
2060       if (base->IsAdd()) {
2061         HAdd* add = HAdd::cast(base);
2062         if (add->right()->IsInteger32Constant()) {
2063           base = add->left();
2064         } else if (add->left()->IsInteger32Constant()) {
2065           base = add->right();
2066         }
2067       } else if (base->IsSub()) {
2068         HSub* sub = HSub::cast(base);
2069         if (sub->right()->IsInteger32Constant()) {
2070           base = sub->left();
2071         }
2072       }
2073     }
2074
2075     result->base = base;
2076   }
2077 }
2078
2079
2080 void InductionVariableData::AddCheck(HBoundsCheck* check,
2081                                      int32_t upper_limit) {
2082   DCHECK(limit_validity() != NULL);
2083   if (limit_validity() != check->block() &&
2084       !limit_validity()->Dominates(check->block())) return;
2085   if (!phi()->block()->current_loop()->IsNestedInThisLoop(
2086       check->block()->current_loop())) return;
2087
2088   ChecksRelatedToLength* length_checks = checks();
2089   while (length_checks != NULL) {
2090     if (length_checks->length() == check->length()) break;
2091     length_checks = length_checks->next();
2092   }
2093   if (length_checks == NULL) {
2094     length_checks = new(check->block()->zone())
2095         ChecksRelatedToLength(check->length(), checks());
2096     checks_ = length_checks;
2097   }
2098
2099   length_checks->AddCheck(check, upper_limit);
2100 }
2101
2102
2103 void InductionVariableData::ChecksRelatedToLength::CloseCurrentBlock() {
2104   if (checks() != NULL) {
2105     InductionVariableCheck* c = checks();
2106     HBasicBlock* current_block = c->check()->block();
2107     while (c != NULL && c->check()->block() == current_block) {
2108       c->set_upper_limit(current_upper_limit_);
2109       c = c->next();
2110     }
2111   }
2112 }
2113
2114
2115 void InductionVariableData::ChecksRelatedToLength::UseNewIndexInCurrentBlock(
2116     Token::Value token,
2117     int32_t mask,
2118     HValue* index_base,
2119     HValue* context) {
2120   DCHECK(first_check_in_block() != NULL);
2121   HValue* previous_index = first_check_in_block()->index();
2122   DCHECK(context != NULL);
2123
2124   Zone* zone = index_base->block()->graph()->zone();
2125   set_added_constant(HConstant::New(zone, context, mask));
2126   if (added_index() != NULL) {
2127     added_constant()->InsertBefore(added_index());
2128   } else {
2129     added_constant()->InsertBefore(first_check_in_block());
2130   }
2131
2132   if (added_index() == NULL) {
2133     first_check_in_block()->ReplaceAllUsesWith(first_check_in_block()->index());
2134     HInstruction* new_index =  HBitwise::New(zone, context, token, index_base,
2135                                              added_constant());
2136     DCHECK(new_index->IsBitwise());
2137     new_index->ClearAllSideEffects();
2138     new_index->AssumeRepresentation(Representation::Integer32());
2139     set_added_index(HBitwise::cast(new_index));
2140     added_index()->InsertBefore(first_check_in_block());
2141   }
2142   DCHECK(added_index()->op() == token);
2143
2144   added_index()->SetOperandAt(1, index_base);
2145   added_index()->SetOperandAt(2, added_constant());
2146   first_check_in_block()->SetOperandAt(0, added_index());
2147   if (previous_index->HasNoUses()) {
2148     previous_index->DeleteAndReplaceWith(NULL);
2149   }
2150 }
2151
2152 void InductionVariableData::ChecksRelatedToLength::AddCheck(
2153     HBoundsCheck* check,
2154     int32_t upper_limit) {
2155   BitwiseDecompositionResult decomposition;
2156   InductionVariableData::DecomposeBitwise(check->index(), &decomposition);
2157
2158   if (first_check_in_block() == NULL ||
2159       first_check_in_block()->block() != check->block()) {
2160     CloseCurrentBlock();
2161
2162     first_check_in_block_ = check;
2163     set_added_index(NULL);
2164     set_added_constant(NULL);
2165     current_and_mask_in_block_ = decomposition.and_mask;
2166     current_or_mask_in_block_ = decomposition.or_mask;
2167     current_upper_limit_ = upper_limit;
2168
2169     InductionVariableCheck* new_check = new(check->block()->graph()->zone())
2170         InductionVariableCheck(check, checks_, upper_limit);
2171     checks_ = new_check;
2172     return;
2173   }
2174
2175   if (upper_limit > current_upper_limit()) {
2176     current_upper_limit_ = upper_limit;
2177   }
2178
2179   if (decomposition.and_mask != 0 &&
2180       current_or_mask_in_block() == 0) {
2181     if (current_and_mask_in_block() == 0 ||
2182         decomposition.and_mask > current_and_mask_in_block()) {
2183       UseNewIndexInCurrentBlock(Token::BIT_AND,
2184                                 decomposition.and_mask,
2185                                 decomposition.base,
2186                                 decomposition.context);
2187       current_and_mask_in_block_ = decomposition.and_mask;
2188     }
2189     check->set_skip_check();
2190   }
2191   if (current_and_mask_in_block() == 0) {
2192     if (decomposition.or_mask > current_or_mask_in_block()) {
2193       UseNewIndexInCurrentBlock(Token::BIT_OR,
2194                                 decomposition.or_mask,
2195                                 decomposition.base,
2196                                 decomposition.context);
2197       current_or_mask_in_block_ = decomposition.or_mask;
2198     }
2199     check->set_skip_check();
2200   }
2201
2202   if (!check->skip_check()) {
2203     InductionVariableCheck* new_check = new(check->block()->graph()->zone())
2204         InductionVariableCheck(check, checks_, upper_limit);
2205     checks_ = new_check;
2206   }
2207 }
2208
2209
2210 /*
2211  * This method detects if phi is an induction variable, with phi_operand as
2212  * its "incremented" value (the other operand would be the "base" value).
2213  *
2214  * It cheks is phi_operand has the form "phi + constant".
2215  * If yes, the constant is the increment that the induction variable gets at
2216  * every loop iteration.
2217  * Otherwise it returns 0.
2218  */
2219 int32_t InductionVariableData::ComputeIncrement(HPhi* phi,
2220                                                 HValue* phi_operand) {
2221   if (!phi_operand->representation().IsInteger32()) return 0;
2222
2223   if (phi_operand->IsAdd()) {
2224     HAdd* operation = HAdd::cast(phi_operand);
2225     if (operation->left() == phi &&
2226         operation->right()->IsInteger32Constant()) {
2227       return operation->right()->GetInteger32Constant();
2228     } else if (operation->right() == phi &&
2229                operation->left()->IsInteger32Constant()) {
2230       return operation->left()->GetInteger32Constant();
2231     }
2232   } else if (phi_operand->IsSub()) {
2233     HSub* operation = HSub::cast(phi_operand);
2234     if (operation->left() == phi &&
2235         operation->right()->IsInteger32Constant()) {
2236       return -operation->right()->GetInteger32Constant();
2237     }
2238   }
2239
2240   return 0;
2241 }
2242
2243
2244 /*
2245  * Swaps the information in "update" with the one contained in "this".
2246  * The swapping is important because this method is used while doing a
2247  * dominator tree traversal, and "update" will retain the old data that
2248  * will be restored while backtracking.
2249  */
2250 void InductionVariableData::UpdateAdditionalLimit(
2251     InductionVariableLimitUpdate* update) {
2252   DCHECK(update->updated_variable == this);
2253   if (update->limit_is_upper) {
2254     swap(&additional_upper_limit_, &update->limit);
2255     swap(&additional_upper_limit_is_included_, &update->limit_is_included);
2256   } else {
2257     swap(&additional_lower_limit_, &update->limit);
2258     swap(&additional_lower_limit_is_included_, &update->limit_is_included);
2259   }
2260 }
2261
2262
2263 int32_t InductionVariableData::ComputeUpperLimit(int32_t and_mask,
2264                                                  int32_t or_mask) {
2265   // Should be Smi::kMaxValue but it must fit 32 bits; lower is safe anyway.
2266   const int32_t MAX_LIMIT = 1 << 30;
2267
2268   int32_t result = MAX_LIMIT;
2269
2270   if (limit() != NULL &&
2271       limit()->IsInteger32Constant()) {
2272     int32_t limit_value = limit()->GetInteger32Constant();
2273     if (!limit_included()) {
2274       limit_value--;
2275     }
2276     if (limit_value < result) result = limit_value;
2277   }
2278
2279   if (additional_upper_limit() != NULL &&
2280       additional_upper_limit()->IsInteger32Constant()) {
2281     int32_t limit_value = additional_upper_limit()->GetInteger32Constant();
2282     if (!additional_upper_limit_is_included()) {
2283       limit_value--;
2284     }
2285     if (limit_value < result) result = limit_value;
2286   }
2287
2288   if (and_mask > 0 && and_mask < MAX_LIMIT) {
2289     if (and_mask < result) result = and_mask;
2290     return result;
2291   }
2292
2293   // Add the effect of the or_mask.
2294   result |= or_mask;
2295
2296   return result >= MAX_LIMIT ? kNoLimit : result;
2297 }
2298
2299
2300 HValue* InductionVariableData::IgnoreOsrValue(HValue* v) {
2301   if (!v->IsPhi()) return v;
2302   HPhi* phi = HPhi::cast(v);
2303   if (phi->OperandCount() != 2) return v;
2304   if (phi->OperandAt(0)->block()->is_osr_entry()) {
2305     return phi->OperandAt(1);
2306   } else if (phi->OperandAt(1)->block()->is_osr_entry()) {
2307     return phi->OperandAt(0);
2308   } else {
2309     return v;
2310   }
2311 }
2312
2313
2314 InductionVariableData* InductionVariableData::GetInductionVariableData(
2315     HValue* v) {
2316   v = IgnoreOsrValue(v);
2317   if (v->IsPhi()) {
2318     return HPhi::cast(v)->induction_variable_data();
2319   }
2320   return NULL;
2321 }
2322
2323
2324 /*
2325  * Check if a conditional branch to "current_branch" with token "token" is
2326  * the branch that keeps the induction loop running (and, conversely, will
2327  * terminate it if the "other_branch" is taken).
2328  *
2329  * Three conditions must be met:
2330  * - "current_branch" must be in the induction loop.
2331  * - "other_branch" must be out of the induction loop.
2332  * - "token" and the induction increment must be "compatible": the token should
2333  *   be a condition that keeps the execution inside the loop until the limit is
2334  *   reached.
2335  */
2336 bool InductionVariableData::CheckIfBranchIsLoopGuard(
2337     Token::Value token,
2338     HBasicBlock* current_branch,
2339     HBasicBlock* other_branch) {
2340   if (!phi()->block()->current_loop()->IsNestedInThisLoop(
2341       current_branch->current_loop())) {
2342     return false;
2343   }
2344
2345   if (phi()->block()->current_loop()->IsNestedInThisLoop(
2346       other_branch->current_loop())) {
2347     return false;
2348   }
2349
2350   if (increment() > 0 && (token == Token::LT || token == Token::LTE)) {
2351     return true;
2352   }
2353   if (increment() < 0 && (token == Token::GT || token == Token::GTE)) {
2354     return true;
2355   }
2356   if (Token::IsInequalityOp(token) && (increment() == 1 || increment() == -1)) {
2357     return true;
2358   }
2359
2360   return false;
2361 }
2362
2363
2364 void InductionVariableData::ComputeLimitFromPredecessorBlock(
2365     HBasicBlock* block,
2366     LimitFromPredecessorBlock* result) {
2367   if (block->predecessors()->length() != 1) return;
2368   HBasicBlock* predecessor = block->predecessors()->at(0);
2369   HInstruction* end = predecessor->last();
2370
2371   if (!end->IsCompareNumericAndBranch()) return;
2372   HCompareNumericAndBranch* branch = HCompareNumericAndBranch::cast(end);
2373
2374   Token::Value token = branch->token();
2375   if (!Token::IsArithmeticCompareOp(token)) return;
2376
2377   HBasicBlock* other_target;
2378   if (block == branch->SuccessorAt(0)) {
2379     other_target = branch->SuccessorAt(1);
2380   } else {
2381     other_target = branch->SuccessorAt(0);
2382     token = Token::NegateCompareOp(token);
2383     DCHECK(block == branch->SuccessorAt(1));
2384   }
2385
2386   InductionVariableData* data;
2387
2388   data = GetInductionVariableData(branch->left());
2389   HValue* limit = branch->right();
2390   if (data == NULL) {
2391     data = GetInductionVariableData(branch->right());
2392     token = Token::ReverseCompareOp(token);
2393     limit = branch->left();
2394   }
2395
2396   if (data != NULL) {
2397     result->variable = data;
2398     result->token = token;
2399     result->limit = limit;
2400     result->other_target = other_target;
2401   }
2402 }
2403
2404
2405 /*
2406  * Compute the limit that is imposed on an induction variable when entering
2407  * "block" (if any).
2408  * If the limit is the "proper" induction limit (the one that makes the loop
2409  * terminate when the induction variable reaches it) it is stored directly in
2410  * the induction variable data.
2411  * Otherwise the limit is written in "additional_limit" and the method
2412  * returns true.
2413  */
2414 bool InductionVariableData::ComputeInductionVariableLimit(
2415     HBasicBlock* block,
2416     InductionVariableLimitUpdate* additional_limit) {
2417   LimitFromPredecessorBlock limit;
2418   ComputeLimitFromPredecessorBlock(block, &limit);
2419   if (!limit.LimitIsValid()) return false;
2420
2421   if (limit.variable->CheckIfBranchIsLoopGuard(limit.token,
2422                                                block,
2423                                                limit.other_target)) {
2424     limit.variable->limit_ = limit.limit;
2425     limit.variable->limit_included_ = limit.LimitIsIncluded();
2426     limit.variable->limit_validity_ = block;
2427     limit.variable->induction_exit_block_ = block->predecessors()->at(0);
2428     limit.variable->induction_exit_target_ = limit.other_target;
2429     return false;
2430   } else {
2431     additional_limit->updated_variable = limit.variable;
2432     additional_limit->limit = limit.limit;
2433     additional_limit->limit_is_upper = limit.LimitIsUpper();
2434     additional_limit->limit_is_included = limit.LimitIsIncluded();
2435     return true;
2436   }
2437 }
2438
2439
2440 Range* HMathMinMax::InferRange(Zone* zone) {
2441   if (representation().IsSmiOrInteger32()) {
2442     Range* a = left()->range();
2443     Range* b = right()->range();
2444     Range* res = a->Copy(zone);
2445     if (operation_ == kMathMax) {
2446       res->CombinedMax(b);
2447     } else {
2448       DCHECK(operation_ == kMathMin);
2449       res->CombinedMin(b);
2450     }
2451     return res;
2452   } else {
2453     return HValue::InferRange(zone);
2454   }
2455 }
2456
2457
2458 void HPushArguments::AddInput(HValue* value) {
2459   inputs_.Add(NULL, value->block()->zone());
2460   SetOperandAt(OperandCount() - 1, value);
2461 }
2462
2463
2464 OStream& HPhi::PrintTo(OStream& os) const {  // NOLINT
2465   os << "[";
2466   for (int i = 0; i < OperandCount(); ++i) {
2467     os << " " << NameOf(OperandAt(i)) << " ";
2468   }
2469   return os << " uses:" << UseCount() << "_"
2470             << smi_non_phi_uses() + smi_indirect_uses() << "s_"
2471             << int32_non_phi_uses() + int32_indirect_uses() << "i_"
2472             << double_non_phi_uses() + double_indirect_uses() << "d_"
2473             << tagged_non_phi_uses() + tagged_indirect_uses() << "t"
2474             << TypeOf(this) << "]";
2475 }
2476
2477
2478 void HPhi::AddInput(HValue* value) {
2479   inputs_.Add(NULL, value->block()->zone());
2480   SetOperandAt(OperandCount() - 1, value);
2481   // Mark phis that may have 'arguments' directly or indirectly as an operand.
2482   if (!CheckFlag(kIsArguments) && value->CheckFlag(kIsArguments)) {
2483     SetFlag(kIsArguments);
2484   }
2485 }
2486
2487
2488 bool HPhi::HasRealUses() {
2489   for (HUseIterator it(uses()); !it.Done(); it.Advance()) {
2490     if (!it.value()->IsPhi()) return true;
2491   }
2492   return false;
2493 }
2494
2495
2496 HValue* HPhi::GetRedundantReplacement() {
2497   HValue* candidate = NULL;
2498   int count = OperandCount();
2499   int position = 0;
2500   while (position < count && candidate == NULL) {
2501     HValue* current = OperandAt(position++);
2502     if (current != this) candidate = current;
2503   }
2504   while (position < count) {
2505     HValue* current = OperandAt(position++);
2506     if (current != this && current != candidate) return NULL;
2507   }
2508   DCHECK(candidate != this);
2509   return candidate;
2510 }
2511
2512
2513 void HPhi::DeleteFromGraph() {
2514   DCHECK(block() != NULL);
2515   block()->RemovePhi(this);
2516   DCHECK(block() == NULL);
2517 }
2518
2519
2520 void HPhi::InitRealUses(int phi_id) {
2521   // Initialize real uses.
2522   phi_id_ = phi_id;
2523   // Compute a conservative approximation of truncating uses before inferring
2524   // representations. The proper, exact computation will be done later, when
2525   // inserting representation changes.
2526   SetFlag(kTruncatingToSmi);
2527   SetFlag(kTruncatingToInt32);
2528   for (HUseIterator it(uses()); !it.Done(); it.Advance()) {
2529     HValue* value = it.value();
2530     if (!value->IsPhi()) {
2531       Representation rep = value->observed_input_representation(it.index());
2532       non_phi_uses_[rep.kind()] += 1;
2533       if (FLAG_trace_representation) {
2534         PrintF("#%d Phi is used by real #%d %s as %s\n",
2535                id(), value->id(), value->Mnemonic(), rep.Mnemonic());
2536       }
2537       if (!value->IsSimulate()) {
2538         if (!value->CheckFlag(kTruncatingToSmi)) {
2539           ClearFlag(kTruncatingToSmi);
2540         }
2541         if (!value->CheckFlag(kTruncatingToInt32)) {
2542           ClearFlag(kTruncatingToInt32);
2543         }
2544       }
2545     }
2546   }
2547 }
2548
2549
2550 void HPhi::AddNonPhiUsesFrom(HPhi* other) {
2551   if (FLAG_trace_representation) {
2552     PrintF("adding to #%d Phi uses of #%d Phi: s%d i%d d%d t%d\n",
2553            id(), other->id(),
2554            other->non_phi_uses_[Representation::kSmi],
2555            other->non_phi_uses_[Representation::kInteger32],
2556            other->non_phi_uses_[Representation::kDouble],
2557            other->non_phi_uses_[Representation::kTagged]);
2558   }
2559
2560   for (int i = 0; i < Representation::kNumRepresentations; i++) {
2561     indirect_uses_[i] += other->non_phi_uses_[i];
2562   }
2563 }
2564
2565
2566 void HPhi::AddIndirectUsesTo(int* dest) {
2567   for (int i = 0; i < Representation::kNumRepresentations; i++) {
2568     dest[i] += indirect_uses_[i];
2569   }
2570 }
2571
2572
2573 void HSimulate::MergeWith(ZoneList<HSimulate*>* list) {
2574   while (!list->is_empty()) {
2575     HSimulate* from = list->RemoveLast();
2576     ZoneList<HValue*>* from_values = &from->values_;
2577     for (int i = 0; i < from_values->length(); ++i) {
2578       if (from->HasAssignedIndexAt(i)) {
2579         int index = from->GetAssignedIndexAt(i);
2580         if (HasValueForIndex(index)) continue;
2581         AddAssignedValue(index, from_values->at(i));
2582       } else {
2583         if (pop_count_ > 0) {
2584           pop_count_--;
2585         } else {
2586           AddPushedValue(from_values->at(i));
2587         }
2588       }
2589     }
2590     pop_count_ += from->pop_count_;
2591     from->DeleteAndReplaceWith(NULL);
2592   }
2593 }
2594
2595
2596 OStream& HSimulate::PrintDataTo(OStream& os) const {  // NOLINT
2597   os << "id=" << ast_id().ToInt();
2598   if (pop_count_ > 0) os << " pop " << pop_count_;
2599   if (values_.length() > 0) {
2600     if (pop_count_ > 0) os << " /";
2601     for (int i = values_.length() - 1; i >= 0; --i) {
2602       if (HasAssignedIndexAt(i)) {
2603         os << " var[" << GetAssignedIndexAt(i) << "] = ";
2604       } else {
2605         os << " push ";
2606       }
2607       os << NameOf(values_[i]);
2608       if (i > 0) os << ",";
2609     }
2610   }
2611   return os;
2612 }
2613
2614
2615 void HSimulate::ReplayEnvironment(HEnvironment* env) {
2616   if (done_with_replay_) return;
2617   DCHECK(env != NULL);
2618   env->set_ast_id(ast_id());
2619   env->Drop(pop_count());
2620   for (int i = values()->length() - 1; i >= 0; --i) {
2621     HValue* value = values()->at(i);
2622     if (HasAssignedIndexAt(i)) {
2623       env->Bind(GetAssignedIndexAt(i), value);
2624     } else {
2625       env->Push(value);
2626     }
2627   }
2628   done_with_replay_ = true;
2629 }
2630
2631
2632 static void ReplayEnvironmentNested(const ZoneList<HValue*>* values,
2633                                     HCapturedObject* other) {
2634   for (int i = 0; i < values->length(); ++i) {
2635     HValue* value = values->at(i);
2636     if (value->IsCapturedObject()) {
2637       if (HCapturedObject::cast(value)->capture_id() == other->capture_id()) {
2638         values->at(i) = other;
2639       } else {
2640         ReplayEnvironmentNested(HCapturedObject::cast(value)->values(), other);
2641       }
2642     }
2643   }
2644 }
2645
2646
2647 // Replay captured objects by replacing all captured objects with the
2648 // same capture id in the current and all outer environments.
2649 void HCapturedObject::ReplayEnvironment(HEnvironment* env) {
2650   DCHECK(env != NULL);
2651   while (env != NULL) {
2652     ReplayEnvironmentNested(env->values(), this);
2653     env = env->outer();
2654   }
2655 }
2656
2657
2658 OStream& HCapturedObject::PrintDataTo(OStream& os) const {  // NOLINT
2659   os << "#" << capture_id() << " ";
2660   return HDematerializedObject::PrintDataTo(os);
2661 }
2662
2663
2664 void HEnterInlined::RegisterReturnTarget(HBasicBlock* return_target,
2665                                          Zone* zone) {
2666   DCHECK(return_target->IsInlineReturnTarget());
2667   return_targets_.Add(return_target, zone);
2668 }
2669
2670
2671 OStream& HEnterInlined::PrintDataTo(OStream& os) const {  // NOLINT
2672   return os << function()->debug_name()->ToCString().get()
2673             << ", id=" << function()->id().ToInt();
2674 }
2675
2676
2677 static bool IsInteger32(double value) {
2678   double roundtrip_value = static_cast<double>(static_cast<int32_t>(value));
2679   return BitCast<int64_t>(roundtrip_value) == BitCast<int64_t>(value);
2680 }
2681
2682
2683 HConstant::HConstant(Handle<Object> object, Representation r)
2684   : HTemplateInstruction<0>(HType::FromValue(object)),
2685     object_(Unique<Object>::CreateUninitialized(object)),
2686     object_map_(Handle<Map>::null()),
2687     has_stable_map_value_(false),
2688     has_smi_value_(false),
2689     has_int32_value_(false),
2690     has_double_value_(false),
2691     has_external_reference_value_(false),
2692     is_not_in_new_space_(true),
2693     boolean_value_(object->BooleanValue()),
2694     is_undetectable_(false),
2695     instance_type_(kUnknownInstanceType) {
2696   if (object->IsHeapObject()) {
2697     Handle<HeapObject> heap_object = Handle<HeapObject>::cast(object);
2698     Isolate* isolate = heap_object->GetIsolate();
2699     Handle<Map> map(heap_object->map(), isolate);
2700     is_not_in_new_space_ = !isolate->heap()->InNewSpace(*object);
2701     instance_type_ = map->instance_type();
2702     is_undetectable_ = map->is_undetectable();
2703     if (map->is_stable()) object_map_ = Unique<Map>::CreateImmovable(map);
2704     has_stable_map_value_ = (instance_type_ == MAP_TYPE &&
2705                              Handle<Map>::cast(heap_object)->is_stable());
2706   }
2707   if (object->IsNumber()) {
2708     double n = object->Number();
2709     has_int32_value_ = IsInteger32(n);
2710     int32_value_ = DoubleToInt32(n);
2711     has_smi_value_ = has_int32_value_ && Smi::IsValid(int32_value_);
2712     double_value_ = n;
2713     has_double_value_ = true;
2714     // TODO(titzer): if this heap number is new space, tenure a new one.
2715   }
2716
2717   Initialize(r);
2718 }
2719
2720
2721 HConstant::HConstant(Unique<Object> object,
2722                      Unique<Map> object_map,
2723                      bool has_stable_map_value,
2724                      Representation r,
2725                      HType type,
2726                      bool is_not_in_new_space,
2727                      bool boolean_value,
2728                      bool is_undetectable,
2729                      InstanceType instance_type)
2730   : HTemplateInstruction<0>(type),
2731     object_(object),
2732     object_map_(object_map),
2733     has_stable_map_value_(has_stable_map_value),
2734     has_smi_value_(false),
2735     has_int32_value_(false),
2736     has_double_value_(false),
2737     has_external_reference_value_(false),
2738     is_not_in_new_space_(is_not_in_new_space),
2739     boolean_value_(boolean_value),
2740     is_undetectable_(is_undetectable),
2741     instance_type_(instance_type) {
2742   DCHECK(!object.handle().is_null());
2743   DCHECK(!type.IsTaggedNumber() || type.IsNone());
2744   Initialize(r);
2745 }
2746
2747
2748 HConstant::HConstant(int32_t integer_value,
2749                      Representation r,
2750                      bool is_not_in_new_space,
2751                      Unique<Object> object)
2752   : object_(object),
2753     object_map_(Handle<Map>::null()),
2754     has_stable_map_value_(false),
2755     has_smi_value_(Smi::IsValid(integer_value)),
2756     has_int32_value_(true),
2757     has_double_value_(true),
2758     has_external_reference_value_(false),
2759     is_not_in_new_space_(is_not_in_new_space),
2760     boolean_value_(integer_value != 0),
2761     is_undetectable_(false),
2762     int32_value_(integer_value),
2763     double_value_(FastI2D(integer_value)),
2764     instance_type_(kUnknownInstanceType) {
2765   // It's possible to create a constant with a value in Smi-range but stored
2766   // in a (pre-existing) HeapNumber. See crbug.com/349878.
2767   bool could_be_heapobject = r.IsTagged() && !object.handle().is_null();
2768   bool is_smi = has_smi_value_ && !could_be_heapobject;
2769   set_type(is_smi ? HType::Smi() : HType::TaggedNumber());
2770   Initialize(r);
2771 }
2772
2773
2774 HConstant::HConstant(double double_value,
2775                      Representation r,
2776                      bool is_not_in_new_space,
2777                      Unique<Object> object)
2778   : object_(object),
2779     object_map_(Handle<Map>::null()),
2780     has_stable_map_value_(false),
2781     has_int32_value_(IsInteger32(double_value)),
2782     has_double_value_(true),
2783     has_external_reference_value_(false),
2784     is_not_in_new_space_(is_not_in_new_space),
2785     boolean_value_(double_value != 0 && !std::isnan(double_value)),
2786     is_undetectable_(false),
2787     int32_value_(DoubleToInt32(double_value)),
2788     double_value_(double_value),
2789     instance_type_(kUnknownInstanceType) {
2790   has_smi_value_ = has_int32_value_ && Smi::IsValid(int32_value_);
2791   // It's possible to create a constant with a value in Smi-range but stored
2792   // in a (pre-existing) HeapNumber. See crbug.com/349878.
2793   bool could_be_heapobject = r.IsTagged() && !object.handle().is_null();
2794   bool is_smi = has_smi_value_ && !could_be_heapobject;
2795   set_type(is_smi ? HType::Smi() : HType::TaggedNumber());
2796   Initialize(r);
2797 }
2798
2799
2800 HConstant::HConstant(ExternalReference reference)
2801   : HTemplateInstruction<0>(HType::Any()),
2802     object_(Unique<Object>(Handle<Object>::null())),
2803     object_map_(Handle<Map>::null()),
2804     has_stable_map_value_(false),
2805     has_smi_value_(false),
2806     has_int32_value_(false),
2807     has_double_value_(false),
2808     has_external_reference_value_(true),
2809     is_not_in_new_space_(true),
2810     boolean_value_(true),
2811     is_undetectable_(false),
2812     external_reference_value_(reference),
2813     instance_type_(kUnknownInstanceType) {
2814   Initialize(Representation::External());
2815 }
2816
2817
2818 void HConstant::Initialize(Representation r) {
2819   if (r.IsNone()) {
2820     if (has_smi_value_ && SmiValuesAre31Bits()) {
2821       r = Representation::Smi();
2822     } else if (has_int32_value_) {
2823       r = Representation::Integer32();
2824     } else if (has_double_value_) {
2825       r = Representation::Double();
2826     } else if (has_external_reference_value_) {
2827       r = Representation::External();
2828     } else {
2829       Handle<Object> object = object_.handle();
2830       if (object->IsJSObject()) {
2831         // Try to eagerly migrate JSObjects that have deprecated maps.
2832         Handle<JSObject> js_object = Handle<JSObject>::cast(object);
2833         if (js_object->map()->is_deprecated()) {
2834           JSObject::TryMigrateInstance(js_object);
2835         }
2836       }
2837       r = Representation::Tagged();
2838     }
2839   }
2840   set_representation(r);
2841   SetFlag(kUseGVN);
2842 }
2843
2844
2845 bool HConstant::ImmortalImmovable() const {
2846   if (has_int32_value_) {
2847     return false;
2848   }
2849   if (has_double_value_) {
2850     if (IsSpecialDouble()) {
2851       return true;
2852     }
2853     return false;
2854   }
2855   if (has_external_reference_value_) {
2856     return false;
2857   }
2858
2859   DCHECK(!object_.handle().is_null());
2860   Heap* heap = isolate()->heap();
2861   DCHECK(!object_.IsKnownGlobal(heap->minus_zero_value()));
2862   DCHECK(!object_.IsKnownGlobal(heap->nan_value()));
2863   return
2864 #define IMMORTAL_IMMOVABLE_ROOT(name) \
2865       object_.IsKnownGlobal(heap->name()) ||
2866       IMMORTAL_IMMOVABLE_ROOT_LIST(IMMORTAL_IMMOVABLE_ROOT)
2867 #undef IMMORTAL_IMMOVABLE_ROOT
2868 #define INTERNALIZED_STRING(name, value) \
2869       object_.IsKnownGlobal(heap->name()) ||
2870       INTERNALIZED_STRING_LIST(INTERNALIZED_STRING)
2871 #undef INTERNALIZED_STRING
2872 #define STRING_TYPE(NAME, size, name, Name) \
2873       object_.IsKnownGlobal(heap->name##_map()) ||
2874       STRING_TYPE_LIST(STRING_TYPE)
2875 #undef STRING_TYPE
2876       false;
2877 }
2878
2879
2880 bool HConstant::EmitAtUses() {
2881   DCHECK(IsLinked());
2882   if (block()->graph()->has_osr() &&
2883       block()->graph()->IsStandardConstant(this)) {
2884     // TODO(titzer): this seems like a hack that should be fixed by custom OSR.
2885     return true;
2886   }
2887   if (HasNoUses()) return true;
2888   if (IsCell()) return false;
2889   if (representation().IsDouble()) return false;
2890   if (representation().IsExternal()) return false;
2891   return true;
2892 }
2893
2894
2895 HConstant* HConstant::CopyToRepresentation(Representation r, Zone* zone) const {
2896   if (r.IsSmi() && !has_smi_value_) return NULL;
2897   if (r.IsInteger32() && !has_int32_value_) return NULL;
2898   if (r.IsDouble() && !has_double_value_) return NULL;
2899   if (r.IsExternal() && !has_external_reference_value_) return NULL;
2900   if (has_int32_value_) {
2901     return new(zone) HConstant(int32_value_, r, is_not_in_new_space_, object_);
2902   }
2903   if (has_double_value_) {
2904     return new(zone) HConstant(double_value_, r, is_not_in_new_space_, object_);
2905   }
2906   if (has_external_reference_value_) {
2907     return new(zone) HConstant(external_reference_value_);
2908   }
2909   DCHECK(!object_.handle().is_null());
2910   return new(zone) HConstant(object_,
2911                              object_map_,
2912                              has_stable_map_value_,
2913                              r,
2914                              type_,
2915                              is_not_in_new_space_,
2916                              boolean_value_,
2917                              is_undetectable_,
2918                              instance_type_);
2919 }
2920
2921
2922 Maybe<HConstant*> HConstant::CopyToTruncatedInt32(Zone* zone) {
2923   HConstant* res = NULL;
2924   if (has_int32_value_) {
2925     res = new(zone) HConstant(int32_value_,
2926                               Representation::Integer32(),
2927                               is_not_in_new_space_,
2928                               object_);
2929   } else if (has_double_value_) {
2930     res = new(zone) HConstant(DoubleToInt32(double_value_),
2931                               Representation::Integer32(),
2932                               is_not_in_new_space_,
2933                               object_);
2934   }
2935   return Maybe<HConstant*>(res != NULL, res);
2936 }
2937
2938
2939 Maybe<HConstant*> HConstant::CopyToTruncatedNumber(Zone* zone) {
2940   HConstant* res = NULL;
2941   Handle<Object> handle = this->handle(zone->isolate());
2942   if (handle->IsBoolean()) {
2943     res = handle->BooleanValue() ?
2944       new(zone) HConstant(1) : new(zone) HConstant(0);
2945   } else if (handle->IsUndefined()) {
2946     res = new(zone) HConstant(base::OS::nan_value());
2947   } else if (handle->IsNull()) {
2948     res = new(zone) HConstant(0);
2949   }
2950   return Maybe<HConstant*>(res != NULL, res);
2951 }
2952
2953
2954 OStream& HConstant::PrintDataTo(OStream& os) const {  // NOLINT
2955   if (has_int32_value_) {
2956     os << int32_value_ << " ";
2957   } else if (has_double_value_) {
2958     os << double_value_ << " ";
2959   } else if (has_external_reference_value_) {
2960     os << reinterpret_cast<void*>(external_reference_value_.address()) << " ";
2961   } else {
2962     // The handle() method is silently and lazily mutating the object.
2963     Handle<Object> h = const_cast<HConstant*>(this)->handle(Isolate::Current());
2964     os << Brief(*h) << " ";
2965     if (HasStableMapValue()) os << "[stable-map] ";
2966     if (HasObjectMap()) os << "[map " << *ObjectMap().handle() << "] ";
2967   }
2968   if (!is_not_in_new_space_) os << "[new space] ";
2969   return os;
2970 }
2971
2972
2973 OStream& HBinaryOperation::PrintDataTo(OStream& os) const {  // NOLINT
2974   os << NameOf(left()) << " " << NameOf(right());
2975   if (CheckFlag(kCanOverflow)) os << " !";
2976   if (CheckFlag(kBailoutOnMinusZero)) os << " -0?";
2977   return os;
2978 }
2979
2980
2981 void HBinaryOperation::InferRepresentation(HInferRepresentationPhase* h_infer) {
2982   DCHECK(CheckFlag(kFlexibleRepresentation));
2983   Representation new_rep = RepresentationFromInputs();
2984   UpdateRepresentation(new_rep, h_infer, "inputs");
2985
2986   if (representation().IsSmi() && HasNonSmiUse()) {
2987     UpdateRepresentation(
2988         Representation::Integer32(), h_infer, "use requirements");
2989   }
2990
2991   if (observed_output_representation_.IsNone()) {
2992     new_rep = RepresentationFromUses();
2993     UpdateRepresentation(new_rep, h_infer, "uses");
2994   } else {
2995     new_rep = RepresentationFromOutput();
2996     UpdateRepresentation(new_rep, h_infer, "output");
2997   }
2998 }
2999
3000
3001 Representation HBinaryOperation::RepresentationFromInputs() {
3002   // Determine the worst case of observed input representations and
3003   // the currently assumed output representation.
3004   Representation rep = representation();
3005   for (int i = 1; i <= 2; ++i) {
3006     rep = rep.generalize(observed_input_representation(i));
3007   }
3008   // If any of the actual input representation is more general than what we
3009   // have so far but not Tagged, use that representation instead.
3010   Representation left_rep = left()->representation();
3011   Representation right_rep = right()->representation();
3012   if (!left_rep.IsTagged()) rep = rep.generalize(left_rep);
3013   if (!right_rep.IsTagged()) rep = rep.generalize(right_rep);
3014
3015   return rep;
3016 }
3017
3018
3019 bool HBinaryOperation::IgnoreObservedOutputRepresentation(
3020     Representation current_rep) {
3021   return ((current_rep.IsInteger32() && CheckUsesForFlag(kTruncatingToInt32)) ||
3022           (current_rep.IsSmi() && CheckUsesForFlag(kTruncatingToSmi))) &&
3023          // Mul in Integer32 mode would be too precise.
3024          (!this->IsMul() || HMul::cast(this)->MulMinusOne());
3025 }
3026
3027
3028 Representation HBinaryOperation::RepresentationFromOutput() {
3029   Representation rep = representation();
3030   // Consider observed output representation, but ignore it if it's Double,
3031   // this instruction is not a division, and all its uses are truncating
3032   // to Integer32.
3033   if (observed_output_representation_.is_more_general_than(rep) &&
3034       !IgnoreObservedOutputRepresentation(rep)) {
3035     return observed_output_representation_;
3036   }
3037   return Representation::None();
3038 }
3039
3040
3041 void HBinaryOperation::AssumeRepresentation(Representation r) {
3042   set_observed_input_representation(1, r);
3043   set_observed_input_representation(2, r);
3044   HValue::AssumeRepresentation(r);
3045 }
3046
3047
3048 void HMathMinMax::InferRepresentation(HInferRepresentationPhase* h_infer) {
3049   DCHECK(CheckFlag(kFlexibleRepresentation));
3050   Representation new_rep = RepresentationFromInputs();
3051   UpdateRepresentation(new_rep, h_infer, "inputs");
3052   // Do not care about uses.
3053 }
3054
3055
3056 Range* HBitwise::InferRange(Zone* zone) {
3057   if (op() == Token::BIT_XOR) {
3058     if (left()->HasRange() && right()->HasRange()) {
3059       // The maximum value has the high bit, and all bits below, set:
3060       // (1 << high) - 1.
3061       // If the range can be negative, the minimum int is a negative number with
3062       // the high bit, and all bits below, unset:
3063       // -(1 << high).
3064       // If it cannot be negative, conservatively choose 0 as minimum int.
3065       int64_t left_upper = left()->range()->upper();
3066       int64_t left_lower = left()->range()->lower();
3067       int64_t right_upper = right()->range()->upper();
3068       int64_t right_lower = right()->range()->lower();
3069
3070       if (left_upper < 0) left_upper = ~left_upper;
3071       if (left_lower < 0) left_lower = ~left_lower;
3072       if (right_upper < 0) right_upper = ~right_upper;
3073       if (right_lower < 0) right_lower = ~right_lower;
3074
3075       int high = MostSignificantBit(
3076           static_cast<uint32_t>(
3077               left_upper | left_lower | right_upper | right_lower));
3078
3079       int64_t limit = 1;
3080       limit <<= high;
3081       int32_t min = (left()->range()->CanBeNegative() ||
3082                      right()->range()->CanBeNegative())
3083                     ? static_cast<int32_t>(-limit) : 0;
3084       return new(zone) Range(min, static_cast<int32_t>(limit - 1));
3085     }
3086     Range* result = HValue::InferRange(zone);
3087     result->set_can_be_minus_zero(false);
3088     return result;
3089   }
3090   const int32_t kDefaultMask = static_cast<int32_t>(0xffffffff);
3091   int32_t left_mask = (left()->range() != NULL)
3092       ? left()->range()->Mask()
3093       : kDefaultMask;
3094   int32_t right_mask = (right()->range() != NULL)
3095       ? right()->range()->Mask()
3096       : kDefaultMask;
3097   int32_t result_mask = (op() == Token::BIT_AND)
3098       ? left_mask & right_mask
3099       : left_mask | right_mask;
3100   if (result_mask >= 0) return new(zone) Range(0, result_mask);
3101
3102   Range* result = HValue::InferRange(zone);
3103   result->set_can_be_minus_zero(false);
3104   return result;
3105 }
3106
3107
3108 Range* HSar::InferRange(Zone* zone) {
3109   if (right()->IsConstant()) {
3110     HConstant* c = HConstant::cast(right());
3111     if (c->HasInteger32Value()) {
3112       Range* result = (left()->range() != NULL)
3113           ? left()->range()->Copy(zone)
3114           : new(zone) Range();
3115       result->Sar(c->Integer32Value());
3116       return result;
3117     }
3118   }
3119   return HValue::InferRange(zone);
3120 }
3121
3122
3123 Range* HShr::InferRange(Zone* zone) {
3124   if (right()->IsConstant()) {
3125     HConstant* c = HConstant::cast(right());
3126     if (c->HasInteger32Value()) {
3127       int shift_count = c->Integer32Value() & 0x1f;
3128       if (left()->range()->CanBeNegative()) {
3129         // Only compute bounds if the result always fits into an int32.
3130         return (shift_count >= 1)
3131             ? new(zone) Range(0,
3132                               static_cast<uint32_t>(0xffffffff) >> shift_count)
3133             : new(zone) Range();
3134       } else {
3135         // For positive inputs we can use the >> operator.
3136         Range* result = (left()->range() != NULL)
3137             ? left()->range()->Copy(zone)
3138             : new(zone) Range();
3139         result->Sar(c->Integer32Value());
3140         return result;
3141       }
3142     }
3143   }
3144   return HValue::InferRange(zone);
3145 }
3146
3147
3148 Range* HShl::InferRange(Zone* zone) {
3149   if (right()->IsConstant()) {
3150     HConstant* c = HConstant::cast(right());
3151     if (c->HasInteger32Value()) {
3152       Range* result = (left()->range() != NULL)
3153           ? left()->range()->Copy(zone)
3154           : new(zone) Range();
3155       result->Shl(c->Integer32Value());
3156       return result;
3157     }
3158   }
3159   return HValue::InferRange(zone);
3160 }
3161
3162
3163 Range* HLoadNamedField::InferRange(Zone* zone) {
3164   if (access().representation().IsInteger8()) {
3165     return new(zone) Range(kMinInt8, kMaxInt8);
3166   }
3167   if (access().representation().IsUInteger8()) {
3168     return new(zone) Range(kMinUInt8, kMaxUInt8);
3169   }
3170   if (access().representation().IsInteger16()) {
3171     return new(zone) Range(kMinInt16, kMaxInt16);
3172   }
3173   if (access().representation().IsUInteger16()) {
3174     return new(zone) Range(kMinUInt16, kMaxUInt16);
3175   }
3176   if (access().IsStringLength()) {
3177     return new(zone) Range(0, String::kMaxLength);
3178   }
3179   return HValue::InferRange(zone);
3180 }
3181
3182
3183 Range* HLoadKeyed::InferRange(Zone* zone) {
3184   switch (elements_kind()) {
3185     case EXTERNAL_INT8_ELEMENTS:
3186       return new(zone) Range(kMinInt8, kMaxInt8);
3187     case EXTERNAL_UINT8_ELEMENTS:
3188     case EXTERNAL_UINT8_CLAMPED_ELEMENTS:
3189       return new(zone) Range(kMinUInt8, kMaxUInt8);
3190     case EXTERNAL_INT16_ELEMENTS:
3191       return new(zone) Range(kMinInt16, kMaxInt16);
3192     case EXTERNAL_UINT16_ELEMENTS:
3193       return new(zone) Range(kMinUInt16, kMaxUInt16);
3194     default:
3195       return HValue::InferRange(zone);
3196   }
3197 }
3198
3199
3200 OStream& HCompareGeneric::PrintDataTo(OStream& os) const {  // NOLINT
3201   os << Token::Name(token()) << " ";
3202   return HBinaryOperation::PrintDataTo(os);
3203 }
3204
3205
3206 OStream& HStringCompareAndBranch::PrintDataTo(OStream& os) const {  // NOLINT
3207   os << Token::Name(token()) << " ";
3208   return HControlInstruction::PrintDataTo(os);
3209 }
3210
3211
3212 OStream& HCompareNumericAndBranch::PrintDataTo(OStream& os) const {  // NOLINT
3213   os << Token::Name(token()) << " " << NameOf(left()) << " " << NameOf(right());
3214   return HControlInstruction::PrintDataTo(os);
3215 }
3216
3217
3218 OStream& HCompareObjectEqAndBranch::PrintDataTo(OStream& os) const {  // NOLINT
3219   os << NameOf(left()) << " " << NameOf(right());
3220   return HControlInstruction::PrintDataTo(os);
3221 }
3222
3223
3224 bool HCompareObjectEqAndBranch::KnownSuccessorBlock(HBasicBlock** block) {
3225   if (known_successor_index() != kNoKnownSuccessorIndex) {
3226     *block = SuccessorAt(known_successor_index());
3227     return true;
3228   }
3229   if (FLAG_fold_constants && left()->IsConstant() && right()->IsConstant()) {
3230     *block = HConstant::cast(left())->DataEquals(HConstant::cast(right()))
3231         ? FirstSuccessor() : SecondSuccessor();
3232     return true;
3233   }
3234   *block = NULL;
3235   return false;
3236 }
3237
3238
3239 bool ConstantIsObject(HConstant* constant, Isolate* isolate) {
3240   if (constant->HasNumberValue()) return false;
3241   if (constant->GetUnique().IsKnownGlobal(isolate->heap()->null_value())) {
3242     return true;
3243   }
3244   if (constant->IsUndetectable()) return false;
3245   InstanceType type = constant->GetInstanceType();
3246   return (FIRST_NONCALLABLE_SPEC_OBJECT_TYPE <= type) &&
3247          (type <= LAST_NONCALLABLE_SPEC_OBJECT_TYPE);
3248 }
3249
3250
3251 bool HIsObjectAndBranch::KnownSuccessorBlock(HBasicBlock** block) {
3252   if (FLAG_fold_constants && value()->IsConstant()) {
3253     *block = ConstantIsObject(HConstant::cast(value()), isolate())
3254         ? FirstSuccessor() : SecondSuccessor();
3255     return true;
3256   }
3257   *block = NULL;
3258   return false;
3259 }
3260
3261
3262 bool HIsStringAndBranch::KnownSuccessorBlock(HBasicBlock** block) {
3263   if (known_successor_index() != kNoKnownSuccessorIndex) {
3264     *block = SuccessorAt(known_successor_index());
3265     return true;
3266   }
3267   if (FLAG_fold_constants && value()->IsConstant()) {
3268     *block = HConstant::cast(value())->HasStringValue()
3269         ? FirstSuccessor() : SecondSuccessor();
3270     return true;
3271   }
3272   if (value()->type().IsString()) {
3273     *block = FirstSuccessor();
3274     return true;
3275   }
3276   if (value()->type().IsSmi() ||
3277       value()->type().IsNull() ||
3278       value()->type().IsBoolean() ||
3279       value()->type().IsUndefined() ||
3280       value()->type().IsJSObject()) {
3281     *block = SecondSuccessor();
3282     return true;
3283   }
3284   *block = NULL;
3285   return false;
3286 }
3287
3288
3289 bool HIsUndetectableAndBranch::KnownSuccessorBlock(HBasicBlock** block) {
3290   if (FLAG_fold_constants && value()->IsConstant()) {
3291     *block = HConstant::cast(value())->IsUndetectable()
3292         ? FirstSuccessor() : SecondSuccessor();
3293     return true;
3294   }
3295   *block = NULL;
3296   return false;
3297 }
3298
3299
3300 bool HHasInstanceTypeAndBranch::KnownSuccessorBlock(HBasicBlock** block) {
3301   if (FLAG_fold_constants && value()->IsConstant()) {
3302     InstanceType type = HConstant::cast(value())->GetInstanceType();
3303     *block = (from_ <= type) && (type <= to_)
3304         ? FirstSuccessor() : SecondSuccessor();
3305     return true;
3306   }
3307   *block = NULL;
3308   return false;
3309 }
3310
3311
3312 void HCompareHoleAndBranch::InferRepresentation(
3313     HInferRepresentationPhase* h_infer) {
3314   ChangeRepresentation(value()->representation());
3315 }
3316
3317
3318 bool HCompareNumericAndBranch::KnownSuccessorBlock(HBasicBlock** block) {
3319   if (left() == right() &&
3320       left()->representation().IsSmiOrInteger32()) {
3321     *block = (token() == Token::EQ ||
3322               token() == Token::EQ_STRICT ||
3323               token() == Token::LTE ||
3324               token() == Token::GTE)
3325         ? FirstSuccessor() : SecondSuccessor();
3326     return true;
3327   }
3328   *block = NULL;
3329   return false;
3330 }
3331
3332
3333 bool HCompareMinusZeroAndBranch::KnownSuccessorBlock(HBasicBlock** block) {
3334   if (FLAG_fold_constants && value()->IsConstant()) {
3335     HConstant* constant = HConstant::cast(value());
3336     if (constant->HasDoubleValue()) {
3337       *block = IsMinusZero(constant->DoubleValue())
3338           ? FirstSuccessor() : SecondSuccessor();
3339       return true;
3340     }
3341   }
3342   if (value()->representation().IsSmiOrInteger32()) {
3343     // A Smi or Integer32 cannot contain minus zero.
3344     *block = SecondSuccessor();
3345     return true;
3346   }
3347   *block = NULL;
3348   return false;
3349 }
3350
3351
3352 void HCompareMinusZeroAndBranch::InferRepresentation(
3353     HInferRepresentationPhase* h_infer) {
3354   ChangeRepresentation(value()->representation());
3355 }
3356
3357
3358 OStream& HGoto::PrintDataTo(OStream& os) const {  // NOLINT
3359   return os << *SuccessorAt(0);
3360 }
3361
3362
3363 void HCompareNumericAndBranch::InferRepresentation(
3364     HInferRepresentationPhase* h_infer) {
3365   Representation left_rep = left()->representation();
3366   Representation right_rep = right()->representation();
3367   Representation observed_left = observed_input_representation(0);
3368   Representation observed_right = observed_input_representation(1);
3369
3370   Representation rep = Representation::None();
3371   rep = rep.generalize(observed_left);
3372   rep = rep.generalize(observed_right);
3373   if (rep.IsNone() || rep.IsSmiOrInteger32()) {
3374     if (!left_rep.IsTagged()) rep = rep.generalize(left_rep);
3375     if (!right_rep.IsTagged()) rep = rep.generalize(right_rep);
3376   } else {
3377     rep = Representation::Double();
3378   }
3379
3380   if (rep.IsDouble()) {
3381     // According to the ES5 spec (11.9.3, 11.8.5), Equality comparisons (==, ===
3382     // and !=) have special handling of undefined, e.g. undefined == undefined
3383     // is 'true'. Relational comparisons have a different semantic, first
3384     // calling ToPrimitive() on their arguments.  The standard Crankshaft
3385     // tagged-to-double conversion to ensure the HCompareNumericAndBranch's
3386     // inputs are doubles caused 'undefined' to be converted to NaN. That's
3387     // compatible out-of-the box with ordered relational comparisons (<, >, <=,
3388     // >=). However, for equality comparisons (and for 'in' and 'instanceof'),
3389     // it is not consistent with the spec. For example, it would cause undefined
3390     // == undefined (should be true) to be evaluated as NaN == NaN
3391     // (false). Therefore, any comparisons other than ordered relational
3392     // comparisons must cause a deopt when one of their arguments is undefined.
3393     // See also v8:1434
3394     if (Token::IsOrderedRelationalCompareOp(token_)) {
3395       SetFlag(kAllowUndefinedAsNaN);
3396     }
3397   }
3398   ChangeRepresentation(rep);
3399 }
3400
3401
3402 OStream& HParameter::PrintDataTo(OStream& os) const {  // NOLINT
3403   return os << index();
3404 }
3405
3406
3407 OStream& HLoadNamedField::PrintDataTo(OStream& os) const {  // NOLINT
3408   os << NameOf(object()) << access_;
3409
3410   if (maps() != NULL) {
3411     os << " [" << *maps()->at(0).handle();
3412     for (int i = 1; i < maps()->size(); ++i) {
3413       os << "," << *maps()->at(i).handle();
3414     }
3415     os << "]";
3416   }
3417
3418   if (HasDependency()) os << " " << NameOf(dependency());
3419   return os;
3420 }
3421
3422
3423 OStream& HLoadNamedGeneric::PrintDataTo(OStream& os) const {  // NOLINT
3424   Handle<String> n = Handle<String>::cast(name());
3425   return os << NameOf(object()) << "." << n->ToCString().get();
3426 }
3427
3428
3429 OStream& HLoadKeyed::PrintDataTo(OStream& os) const {  // NOLINT
3430   if (!is_external()) {
3431     os << NameOf(elements());
3432   } else {
3433     DCHECK(elements_kind() >= FIRST_EXTERNAL_ARRAY_ELEMENTS_KIND &&
3434            elements_kind() <= LAST_EXTERNAL_ARRAY_ELEMENTS_KIND);
3435     os << NameOf(elements()) << "." << ElementsKindToString(elements_kind());
3436   }
3437
3438   os << "[" << NameOf(key());
3439   if (IsDehoisted()) os << " + " << base_offset();
3440   os << "]";
3441
3442   if (HasDependency()) os << " " << NameOf(dependency());
3443   if (RequiresHoleCheck()) os << " check_hole";
3444   return os;
3445 }
3446
3447
3448 bool HLoadKeyed::TryIncreaseBaseOffset(uint32_t increase_by_value) {
3449   // The base offset is usually simply the size of the array header, except
3450   // with dehoisting adds an addition offset due to a array index key
3451   // manipulation, in which case it becomes (array header size +
3452   // constant-offset-from-key * kPointerSize)
3453   uint32_t base_offset = BaseOffsetField::decode(bit_field_);
3454   v8::base::internal::CheckedNumeric<uint32_t> addition_result = base_offset;
3455   addition_result += increase_by_value;
3456   if (!addition_result.IsValid()) return false;
3457   base_offset = addition_result.ValueOrDie();
3458   if (!BaseOffsetField::is_valid(base_offset)) return false;
3459   bit_field_ = BaseOffsetField::update(bit_field_, base_offset);
3460   return true;
3461 }
3462
3463
3464 bool HLoadKeyed::UsesMustHandleHole() const {
3465   if (IsFastPackedElementsKind(elements_kind())) {
3466     return false;
3467   }
3468
3469   if (IsExternalArrayElementsKind(elements_kind())) {
3470     return false;
3471   }
3472
3473   if (hole_mode() == ALLOW_RETURN_HOLE) {
3474     if (IsFastDoubleElementsKind(elements_kind())) {
3475       return AllUsesCanTreatHoleAsNaN();
3476     }
3477     return true;
3478   }
3479
3480   if (IsFastDoubleElementsKind(elements_kind())) {
3481     return false;
3482   }
3483
3484   // Holes are only returned as tagged values.
3485   if (!representation().IsTagged()) {
3486     return false;
3487   }
3488
3489   for (HUseIterator it(uses()); !it.Done(); it.Advance()) {
3490     HValue* use = it.value();
3491     if (!use->IsChange()) return false;
3492   }
3493
3494   return true;
3495 }
3496
3497
3498 bool HLoadKeyed::AllUsesCanTreatHoleAsNaN() const {
3499   return IsFastDoubleElementsKind(elements_kind()) &&
3500       CheckUsesForFlag(HValue::kAllowUndefinedAsNaN);
3501 }
3502
3503
3504 bool HLoadKeyed::RequiresHoleCheck() const {
3505   if (IsFastPackedElementsKind(elements_kind())) {
3506     return false;
3507   }
3508
3509   if (IsExternalArrayElementsKind(elements_kind())) {
3510     return false;
3511   }
3512
3513   return !UsesMustHandleHole();
3514 }
3515
3516
3517 OStream& HLoadKeyedGeneric::PrintDataTo(OStream& os) const {  // NOLINT
3518   return os << NameOf(object()) << "[" << NameOf(key()) << "]";
3519 }
3520
3521
3522 HValue* HLoadKeyedGeneric::Canonicalize() {
3523   // Recognize generic keyed loads that use property name generated
3524   // by for-in statement as a key and rewrite them into fast property load
3525   // by index.
3526   if (key()->IsLoadKeyed()) {
3527     HLoadKeyed* key_load = HLoadKeyed::cast(key());
3528     if (key_load->elements()->IsForInCacheArray()) {
3529       HForInCacheArray* names_cache =
3530           HForInCacheArray::cast(key_load->elements());
3531
3532       if (names_cache->enumerable() == object()) {
3533         HForInCacheArray* index_cache =
3534             names_cache->index_cache();
3535         HCheckMapValue* map_check =
3536             HCheckMapValue::New(block()->graph()->zone(),
3537                                 block()->graph()->GetInvalidContext(),
3538                                 object(),
3539                                 names_cache->map());
3540         HInstruction* index = HLoadKeyed::New(
3541             block()->graph()->zone(),
3542             block()->graph()->GetInvalidContext(),
3543             index_cache,
3544             key_load->key(),
3545             key_load->key(),
3546             key_load->elements_kind());
3547         map_check->InsertBefore(this);
3548         index->InsertBefore(this);
3549         return Prepend(new(block()->zone()) HLoadFieldByIndex(
3550             object(), index));
3551       }
3552     }
3553   }
3554
3555   return this;
3556 }
3557
3558
3559 OStream& HStoreNamedGeneric::PrintDataTo(OStream& os) const {  // NOLINT
3560   Handle<String> n = Handle<String>::cast(name());
3561   return os << NameOf(object()) << "." << n->ToCString().get() << " = "
3562             << NameOf(value());
3563 }
3564
3565
3566 OStream& HStoreNamedField::PrintDataTo(OStream& os) const {  // NOLINT
3567   os << NameOf(object()) << access_ << " = " << NameOf(value());
3568   if (NeedsWriteBarrier()) os << " (write-barrier)";
3569   if (has_transition()) os << " (transition map " << *transition_map() << ")";
3570   return os;
3571 }
3572
3573
3574 OStream& HStoreKeyed::PrintDataTo(OStream& os) const {  // NOLINT
3575   if (!is_external()) {
3576     os << NameOf(elements());
3577   } else {
3578     DCHECK(elements_kind() >= FIRST_EXTERNAL_ARRAY_ELEMENTS_KIND &&
3579            elements_kind() <= LAST_EXTERNAL_ARRAY_ELEMENTS_KIND);
3580     os << NameOf(elements()) << "." << ElementsKindToString(elements_kind());
3581   }
3582
3583   os << "[" << NameOf(key());
3584   if (IsDehoisted()) os << " + " << base_offset();
3585   return os << "] = " << NameOf(value());
3586 }
3587
3588
3589 OStream& HStoreKeyedGeneric::PrintDataTo(OStream& os) const {  // NOLINT
3590   return os << NameOf(object()) << "[" << NameOf(key())
3591             << "] = " << NameOf(value());
3592 }
3593
3594
3595 OStream& HTransitionElementsKind::PrintDataTo(OStream& os) const {  // NOLINT
3596   os << NameOf(object());
3597   ElementsKind from_kind = original_map().handle()->elements_kind();
3598   ElementsKind to_kind = transitioned_map().handle()->elements_kind();
3599   os << " " << *original_map().handle() << " ["
3600      << ElementsAccessor::ForKind(from_kind)->name() << "] -> "
3601      << *transitioned_map().handle() << " ["
3602      << ElementsAccessor::ForKind(to_kind)->name() << "]";
3603   if (IsSimpleMapChangeTransition(from_kind, to_kind)) os << " (simple)";
3604   return os;
3605 }
3606
3607
3608 OStream& HLoadGlobalCell::PrintDataTo(OStream& os) const {  // NOLINT
3609   os << "[" << *cell().handle() << "]";
3610   if (!details_.IsDontDelete()) os << " (deleteable)";
3611   if (details_.IsReadOnly()) os << " (read-only)";
3612   return os;
3613 }
3614
3615
3616 bool HLoadGlobalCell::RequiresHoleCheck() const {
3617   if (details_.IsDontDelete() && !details_.IsReadOnly()) return false;
3618   for (HUseIterator it(uses()); !it.Done(); it.Advance()) {
3619     HValue* use = it.value();
3620     if (!use->IsChange()) return true;
3621   }
3622   return false;
3623 }
3624
3625
3626 OStream& HLoadGlobalGeneric::PrintDataTo(OStream& os) const {  // NOLINT
3627   return os << name()->ToCString().get() << " ";
3628 }
3629
3630
3631 OStream& HInnerAllocatedObject::PrintDataTo(OStream& os) const {  // NOLINT
3632   os << NameOf(base_object()) << " offset ";
3633   return offset()->PrintTo(os);
3634 }
3635
3636
3637 OStream& HStoreGlobalCell::PrintDataTo(OStream& os) const {  // NOLINT
3638   os << "[" << *cell().handle() << "] = " << NameOf(value());
3639   if (!details_.IsDontDelete()) os << " (deleteable)";
3640   if (details_.IsReadOnly()) os << " (read-only)";
3641   return os;
3642 }
3643
3644
3645 OStream& HLoadContextSlot::PrintDataTo(OStream& os) const {  // NOLINT
3646   return os << NameOf(value()) << "[" << slot_index() << "]";
3647 }
3648
3649
3650 OStream& HStoreContextSlot::PrintDataTo(OStream& os) const {  // NOLINT
3651   return os << NameOf(context()) << "[" << slot_index()
3652             << "] = " << NameOf(value());
3653 }
3654
3655
3656 // Implementation of type inference and type conversions. Calculates
3657 // the inferred type of this instruction based on the input operands.
3658
3659 HType HValue::CalculateInferredType() {
3660   return type_;
3661 }
3662
3663
3664 HType HPhi::CalculateInferredType() {
3665   if (OperandCount() == 0) return HType::Tagged();
3666   HType result = OperandAt(0)->type();
3667   for (int i = 1; i < OperandCount(); ++i) {
3668     HType current = OperandAt(i)->type();
3669     result = result.Combine(current);
3670   }
3671   return result;
3672 }
3673
3674
3675 HType HChange::CalculateInferredType() {
3676   if (from().IsDouble() && to().IsTagged()) return HType::HeapNumber();
3677   return type();
3678 }
3679
3680
3681 Representation HUnaryMathOperation::RepresentationFromInputs() {
3682   if (SupportsFlexibleFloorAndRound() &&
3683       (op_ == kMathFloor || op_ == kMathRound)) {
3684     // Floor and Round always take a double input. The integral result can be
3685     // used as an integer or a double. Infer the representation from the uses.
3686     return Representation::None();
3687   }
3688   Representation rep = representation();
3689   // If any of the actual input representation is more general than what we
3690   // have so far but not Tagged, use that representation instead.
3691   Representation input_rep = value()->representation();
3692   if (!input_rep.IsTagged()) {
3693     rep = rep.generalize(input_rep);
3694   }
3695   return rep;
3696 }
3697
3698
3699 bool HAllocate::HandleSideEffectDominator(GVNFlag side_effect,
3700                                           HValue* dominator) {
3701   DCHECK(side_effect == kNewSpacePromotion);
3702   Zone* zone = block()->zone();
3703   if (!FLAG_use_allocation_folding) return false;
3704
3705   // Try to fold allocations together with their dominating allocations.
3706   if (!dominator->IsAllocate()) {
3707     if (FLAG_trace_allocation_folding) {
3708       PrintF("#%d (%s) cannot fold into #%d (%s)\n",
3709           id(), Mnemonic(), dominator->id(), dominator->Mnemonic());
3710     }
3711     return false;
3712   }
3713
3714   // Check whether we are folding within the same block for local folding.
3715   if (FLAG_use_local_allocation_folding && dominator->block() != block()) {
3716     if (FLAG_trace_allocation_folding) {
3717       PrintF("#%d (%s) cannot fold into #%d (%s), crosses basic blocks\n",
3718           id(), Mnemonic(), dominator->id(), dominator->Mnemonic());
3719     }
3720     return false;
3721   }
3722
3723   HAllocate* dominator_allocate = HAllocate::cast(dominator);
3724   HValue* dominator_size = dominator_allocate->size();
3725   HValue* current_size = size();
3726
3727   // TODO(hpayer): Add support for non-constant allocation in dominator.
3728   if (!dominator_size->IsInteger32Constant()) {
3729     if (FLAG_trace_allocation_folding) {
3730       PrintF("#%d (%s) cannot fold into #%d (%s), "
3731              "dynamic allocation size in dominator\n",
3732           id(), Mnemonic(), dominator->id(), dominator->Mnemonic());
3733     }
3734     return false;
3735   }
3736
3737   dominator_allocate = GetFoldableDominator(dominator_allocate);
3738   if (dominator_allocate == NULL) {
3739     return false;
3740   }
3741
3742   if (!has_size_upper_bound()) {
3743     if (FLAG_trace_allocation_folding) {
3744       PrintF("#%d (%s) cannot fold into #%d (%s), "
3745              "can't estimate total allocation size\n",
3746           id(), Mnemonic(), dominator->id(), dominator->Mnemonic());
3747     }
3748     return false;
3749   }
3750
3751   if (!current_size->IsInteger32Constant()) {
3752     // If it's not constant then it is a size_in_bytes calculation graph
3753     // like this: (const_header_size + const_element_size * size).
3754     DCHECK(current_size->IsInstruction());
3755
3756     HInstruction* current_instr = HInstruction::cast(current_size);
3757     if (!current_instr->Dominates(dominator_allocate)) {
3758       if (FLAG_trace_allocation_folding) {
3759         PrintF("#%d (%s) cannot fold into #%d (%s), dynamic size "
3760                "value does not dominate target allocation\n",
3761             id(), Mnemonic(), dominator_allocate->id(),
3762             dominator_allocate->Mnemonic());
3763       }
3764       return false;
3765     }
3766   }
3767
3768   DCHECK((IsNewSpaceAllocation() &&
3769          dominator_allocate->IsNewSpaceAllocation()) ||
3770          (IsOldDataSpaceAllocation() &&
3771          dominator_allocate->IsOldDataSpaceAllocation()) ||
3772          (IsOldPointerSpaceAllocation() &&
3773          dominator_allocate->IsOldPointerSpaceAllocation()));
3774
3775   // First update the size of the dominator allocate instruction.
3776   dominator_size = dominator_allocate->size();
3777   int32_t original_object_size =
3778       HConstant::cast(dominator_size)->GetInteger32Constant();
3779   int32_t dominator_size_constant = original_object_size;
3780
3781   if (MustAllocateDoubleAligned()) {
3782     if ((dominator_size_constant & kDoubleAlignmentMask) != 0) {
3783       dominator_size_constant += kDoubleSize / 2;
3784     }
3785   }
3786
3787   int32_t current_size_max_value = size_upper_bound()->GetInteger32Constant();
3788   int32_t new_dominator_size = dominator_size_constant + current_size_max_value;
3789
3790   // Since we clear the first word after folded memory, we cannot use the
3791   // whole Page::kMaxRegularHeapObjectSize memory.
3792   if (new_dominator_size > Page::kMaxRegularHeapObjectSize - kPointerSize) {
3793     if (FLAG_trace_allocation_folding) {
3794       PrintF("#%d (%s) cannot fold into #%d (%s) due to size: %d\n",
3795           id(), Mnemonic(), dominator_allocate->id(),
3796           dominator_allocate->Mnemonic(), new_dominator_size);
3797     }
3798     return false;
3799   }
3800
3801   HInstruction* new_dominator_size_value;
3802
3803   if (current_size->IsInteger32Constant()) {
3804     new_dominator_size_value =
3805         HConstant::CreateAndInsertBefore(zone,
3806                                          context(),
3807                                          new_dominator_size,
3808                                          Representation::None(),
3809                                          dominator_allocate);
3810   } else {
3811     HValue* new_dominator_size_constant =
3812         HConstant::CreateAndInsertBefore(zone,
3813                                          context(),
3814                                          dominator_size_constant,
3815                                          Representation::Integer32(),
3816                                          dominator_allocate);
3817
3818     // Add old and new size together and insert.
3819     current_size->ChangeRepresentation(Representation::Integer32());
3820
3821     new_dominator_size_value = HAdd::New(zone, context(),
3822         new_dominator_size_constant, current_size);
3823     new_dominator_size_value->ClearFlag(HValue::kCanOverflow);
3824     new_dominator_size_value->ChangeRepresentation(Representation::Integer32());
3825
3826     new_dominator_size_value->InsertBefore(dominator_allocate);
3827   }
3828
3829   dominator_allocate->UpdateSize(new_dominator_size_value);
3830
3831   if (MustAllocateDoubleAligned()) {
3832     if (!dominator_allocate->MustAllocateDoubleAligned()) {
3833       dominator_allocate->MakeDoubleAligned();
3834     }
3835   }
3836
3837   bool keep_new_space_iterable = FLAG_log_gc || FLAG_heap_stats;
3838 #ifdef VERIFY_HEAP
3839   keep_new_space_iterable = keep_new_space_iterable || FLAG_verify_heap;
3840 #endif
3841
3842   if (keep_new_space_iterable && dominator_allocate->IsNewSpaceAllocation()) {
3843     dominator_allocate->MakePrefillWithFiller();
3844   } else {
3845     // TODO(hpayer): This is a short-term hack to make allocation mementos
3846     // work again in new space.
3847     dominator_allocate->ClearNextMapWord(original_object_size);
3848   }
3849
3850   dominator_allocate->UpdateClearNextMapWord(MustClearNextMapWord());
3851
3852   // After that replace the dominated allocate instruction.
3853   HInstruction* inner_offset = HConstant::CreateAndInsertBefore(
3854       zone,
3855       context(),
3856       dominator_size_constant,
3857       Representation::None(),
3858       this);
3859
3860   HInstruction* dominated_allocate_instr =
3861       HInnerAllocatedObject::New(zone,
3862                                  context(),
3863                                  dominator_allocate,
3864                                  inner_offset,
3865                                  type());
3866   dominated_allocate_instr->InsertBefore(this);
3867   DeleteAndReplaceWith(dominated_allocate_instr);
3868   if (FLAG_trace_allocation_folding) {
3869     PrintF("#%d (%s) folded into #%d (%s)\n",
3870         id(), Mnemonic(), dominator_allocate->id(),
3871         dominator_allocate->Mnemonic());
3872   }
3873   return true;
3874 }
3875
3876
3877 HAllocate* HAllocate::GetFoldableDominator(HAllocate* dominator) {
3878   if (!IsFoldable(dominator)) {
3879     // We cannot hoist old space allocations over new space allocations.
3880     if (IsNewSpaceAllocation() || dominator->IsNewSpaceAllocation()) {
3881       if (FLAG_trace_allocation_folding) {
3882         PrintF("#%d (%s) cannot fold into #%d (%s), new space hoisting\n",
3883             id(), Mnemonic(), dominator->id(), dominator->Mnemonic());
3884       }
3885       return NULL;
3886     }
3887
3888     HAllocate* dominator_dominator = dominator->dominating_allocate_;
3889
3890     // We can hoist old data space allocations over an old pointer space
3891     // allocation and vice versa. For that we have to check the dominator
3892     // of the dominator allocate instruction.
3893     if (dominator_dominator == NULL) {
3894       dominating_allocate_ = dominator;
3895       if (FLAG_trace_allocation_folding) {
3896         PrintF("#%d (%s) cannot fold into #%d (%s), different spaces\n",
3897             id(), Mnemonic(), dominator->id(), dominator->Mnemonic());
3898       }
3899       return NULL;
3900     }
3901
3902     // We can just fold old space allocations that are in the same basic block,
3903     // since it is not guaranteed that we fill up the whole allocated old
3904     // space memory.
3905     // TODO(hpayer): Remove this limitation and add filler maps for each each
3906     // allocation as soon as we have store elimination.
3907     if (block()->block_id() != dominator_dominator->block()->block_id()) {
3908       if (FLAG_trace_allocation_folding) {
3909         PrintF("#%d (%s) cannot fold into #%d (%s), different basic blocks\n",
3910             id(), Mnemonic(), dominator_dominator->id(),
3911             dominator_dominator->Mnemonic());
3912       }
3913       return NULL;
3914     }
3915
3916     DCHECK((IsOldDataSpaceAllocation() &&
3917            dominator_dominator->IsOldDataSpaceAllocation()) ||
3918            (IsOldPointerSpaceAllocation() &&
3919            dominator_dominator->IsOldPointerSpaceAllocation()));
3920
3921     int32_t current_size = HConstant::cast(size())->GetInteger32Constant();
3922     HStoreNamedField* dominator_free_space_size =
3923         dominator->filler_free_space_size_;
3924     if (dominator_free_space_size != NULL) {
3925       // We already hoisted one old space allocation, i.e., we already installed
3926       // a filler map. Hence, we just have to update the free space size.
3927       dominator->UpdateFreeSpaceFiller(current_size);
3928     } else {
3929       // This is the first old space allocation that gets hoisted. We have to
3930       // install a filler map since the follwing allocation may cause a GC.
3931       dominator->CreateFreeSpaceFiller(current_size);
3932     }
3933
3934     // We can hoist the old space allocation over the actual dominator.
3935     return dominator_dominator;
3936   }
3937   return dominator;
3938 }
3939
3940
3941 void HAllocate::UpdateFreeSpaceFiller(int32_t free_space_size) {
3942   DCHECK(filler_free_space_size_ != NULL);
3943   Zone* zone = block()->zone();
3944   // We must explicitly force Smi representation here because on x64 we
3945   // would otherwise automatically choose int32, but the actual store
3946   // requires a Smi-tagged value.
3947   HConstant* new_free_space_size = HConstant::CreateAndInsertBefore(
3948       zone,
3949       context(),
3950       filler_free_space_size_->value()->GetInteger32Constant() +
3951           free_space_size,
3952       Representation::Smi(),
3953       filler_free_space_size_);
3954   filler_free_space_size_->UpdateValue(new_free_space_size);
3955 }
3956
3957
3958 void HAllocate::CreateFreeSpaceFiller(int32_t free_space_size) {
3959   DCHECK(filler_free_space_size_ == NULL);
3960   Zone* zone = block()->zone();
3961   HInstruction* free_space_instr =
3962       HInnerAllocatedObject::New(zone, context(), dominating_allocate_,
3963       dominating_allocate_->size(), type());
3964   free_space_instr->InsertBefore(this);
3965   HConstant* filler_map = HConstant::CreateAndInsertAfter(
3966       zone, Unique<Map>::CreateImmovable(
3967           isolate()->factory()->free_space_map()), true, free_space_instr);
3968   HInstruction* store_map = HStoreNamedField::New(zone, context(),
3969       free_space_instr, HObjectAccess::ForMap(), filler_map);
3970   store_map->SetFlag(HValue::kHasNoObservableSideEffects);
3971   store_map->InsertAfter(filler_map);
3972
3973   // We must explicitly force Smi representation here because on x64 we
3974   // would otherwise automatically choose int32, but the actual store
3975   // requires a Smi-tagged value.
3976   HConstant* filler_size = HConstant::CreateAndInsertAfter(
3977       zone, context(), free_space_size, Representation::Smi(), store_map);
3978   // Must force Smi representation for x64 (see comment above).
3979   HObjectAccess access =
3980       HObjectAccess::ForMapAndOffset(isolate()->factory()->free_space_map(),
3981                                      FreeSpace::kSizeOffset,
3982                                      Representation::Smi());
3983   HStoreNamedField* store_size = HStoreNamedField::New(zone, context(),
3984       free_space_instr, access, filler_size);
3985   store_size->SetFlag(HValue::kHasNoObservableSideEffects);
3986   store_size->InsertAfter(filler_size);
3987   filler_free_space_size_ = store_size;
3988 }
3989
3990
3991 void HAllocate::ClearNextMapWord(int offset) {
3992   if (MustClearNextMapWord()) {
3993     Zone* zone = block()->zone();
3994     HObjectAccess access =
3995         HObjectAccess::ForObservableJSObjectOffset(offset);
3996     HStoreNamedField* clear_next_map =
3997         HStoreNamedField::New(zone, context(), this, access,
3998             block()->graph()->GetConstant0());
3999     clear_next_map->ClearAllSideEffects();
4000     clear_next_map->InsertAfter(this);
4001   }
4002 }
4003
4004
4005 OStream& HAllocate::PrintDataTo(OStream& os) const {  // NOLINT
4006   os << NameOf(size()) << " (";
4007   if (IsNewSpaceAllocation()) os << "N";
4008   if (IsOldPointerSpaceAllocation()) os << "P";
4009   if (IsOldDataSpaceAllocation()) os << "D";
4010   if (MustAllocateDoubleAligned()) os << "A";
4011   if (MustPrefillWithFiller()) os << "F";
4012   return os << ")";
4013 }
4014
4015
4016 bool HStoreKeyed::TryIncreaseBaseOffset(uint32_t increase_by_value) {
4017   // The base offset is usually simply the size of the array header, except
4018   // with dehoisting adds an addition offset due to a array index key
4019   // manipulation, in which case it becomes (array header size +
4020   // constant-offset-from-key * kPointerSize)
4021   v8::base::internal::CheckedNumeric<uint32_t> addition_result = base_offset_;
4022   addition_result += increase_by_value;
4023   if (!addition_result.IsValid()) return false;
4024   base_offset_ = addition_result.ValueOrDie();
4025   return true;
4026 }
4027
4028
4029 bool HStoreKeyed::NeedsCanonicalization() {
4030   // If value is an integer or smi or comes from the result of a keyed load or
4031   // constant then it is either be a non-hole value or in the case of a constant
4032   // the hole is only being stored explicitly: no need for canonicalization.
4033   //
4034   // The exception to that is keyed loads from external float or double arrays:
4035   // these can load arbitrary representation of NaN.
4036
4037   if (value()->IsConstant()) {
4038     return false;
4039   }
4040
4041   if (value()->IsLoadKeyed()) {
4042     return IsExternalFloatOrDoubleElementsKind(
4043         HLoadKeyed::cast(value())->elements_kind());
4044   }
4045
4046   if (value()->IsChange()) {
4047     if (HChange::cast(value())->from().IsSmiOrInteger32()) {
4048       return false;
4049     }
4050     if (HChange::cast(value())->value()->type().IsSmi()) {
4051       return false;
4052     }
4053   }
4054   return true;
4055 }
4056
4057
4058 #define H_CONSTANT_INT(val)                                                    \
4059 HConstant::New(zone, context, static_cast<int32_t>(val))
4060 #define H_CONSTANT_DOUBLE(val)                                                 \
4061 HConstant::New(zone, context, static_cast<double>(val))
4062
4063 #define DEFINE_NEW_H_SIMPLE_ARITHMETIC_INSTR(HInstr, op)                       \
4064 HInstruction* HInstr::New(                                                     \
4065     Zone* zone, HValue* context, HValue* left, HValue* right) {                \
4066   if (FLAG_fold_constants && left->IsConstant() && right->IsConstant()) {      \
4067     HConstant* c_left = HConstant::cast(left);                                 \
4068     HConstant* c_right = HConstant::cast(right);                               \
4069     if ((c_left->HasNumberValue() && c_right->HasNumberValue())) {             \
4070       double double_res = c_left->DoubleValue() op c_right->DoubleValue();     \
4071       if (IsInt32Double(double_res)) {                                         \
4072         return H_CONSTANT_INT(double_res);                                     \
4073       }                                                                        \
4074       return H_CONSTANT_DOUBLE(double_res);                                    \
4075     }                                                                          \
4076   }                                                                            \
4077   return new(zone) HInstr(context, left, right);                               \
4078 }
4079
4080
4081 DEFINE_NEW_H_SIMPLE_ARITHMETIC_INSTR(HAdd, +)
4082 DEFINE_NEW_H_SIMPLE_ARITHMETIC_INSTR(HMul, *)
4083 DEFINE_NEW_H_SIMPLE_ARITHMETIC_INSTR(HSub, -)
4084
4085 #undef DEFINE_NEW_H_SIMPLE_ARITHMETIC_INSTR
4086
4087
4088 HInstruction* HStringAdd::New(Zone* zone,
4089                               HValue* context,
4090                               HValue* left,
4091                               HValue* right,
4092                               PretenureFlag pretenure_flag,
4093                               StringAddFlags flags,
4094                               Handle<AllocationSite> allocation_site) {
4095   if (FLAG_fold_constants && left->IsConstant() && right->IsConstant()) {
4096     HConstant* c_right = HConstant::cast(right);
4097     HConstant* c_left = HConstant::cast(left);
4098     if (c_left->HasStringValue() && c_right->HasStringValue()) {
4099       Handle<String> left_string = c_left->StringValue();
4100       Handle<String> right_string = c_right->StringValue();
4101       // Prevent possible exception by invalid string length.
4102       if (left_string->length() + right_string->length() < String::kMaxLength) {
4103         MaybeHandle<String> concat = zone->isolate()->factory()->NewConsString(
4104             c_left->StringValue(), c_right->StringValue());
4105         return HConstant::New(zone, context, concat.ToHandleChecked());
4106       }
4107     }
4108   }
4109   return new(zone) HStringAdd(
4110       context, left, right, pretenure_flag, flags, allocation_site);
4111 }
4112
4113
4114 OStream& HStringAdd::PrintDataTo(OStream& os) const {  // NOLINT
4115   if ((flags() & STRING_ADD_CHECK_BOTH) == STRING_ADD_CHECK_BOTH) {
4116     os << "_CheckBoth";
4117   } else if ((flags() & STRING_ADD_CHECK_BOTH) == STRING_ADD_CHECK_LEFT) {
4118     os << "_CheckLeft";
4119   } else if ((flags() & STRING_ADD_CHECK_BOTH) == STRING_ADD_CHECK_RIGHT) {
4120     os << "_CheckRight";
4121   }
4122   HBinaryOperation::PrintDataTo(os);
4123   os << " (";
4124   if (pretenure_flag() == NOT_TENURED)
4125     os << "N";
4126   else if (pretenure_flag() == TENURED)
4127     os << "D";
4128   return os << ")";
4129 }
4130
4131
4132 HInstruction* HStringCharFromCode::New(
4133     Zone* zone, HValue* context, HValue* char_code) {
4134   if (FLAG_fold_constants && char_code->IsConstant()) {
4135     HConstant* c_code = HConstant::cast(char_code);
4136     Isolate* isolate = zone->isolate();
4137     if (c_code->HasNumberValue()) {
4138       if (std::isfinite(c_code->DoubleValue())) {
4139         uint32_t code = c_code->NumberValueAsInteger32() & 0xffff;
4140         return HConstant::New(zone, context,
4141             isolate->factory()->LookupSingleCharacterStringFromCode(code));
4142       }
4143       return HConstant::New(zone, context, isolate->factory()->empty_string());
4144     }
4145   }
4146   return new(zone) HStringCharFromCode(context, char_code);
4147 }
4148
4149
4150 HInstruction* HUnaryMathOperation::New(
4151     Zone* zone, HValue* context, HValue* value, BuiltinFunctionId op) {
4152   do {
4153     if (!FLAG_fold_constants) break;
4154     if (!value->IsConstant()) break;
4155     HConstant* constant = HConstant::cast(value);
4156     if (!constant->HasNumberValue()) break;
4157     double d = constant->DoubleValue();
4158     if (std::isnan(d)) {  // NaN poisons everything.
4159       return H_CONSTANT_DOUBLE(base::OS::nan_value());
4160     }
4161     if (std::isinf(d)) {  // +Infinity and -Infinity.
4162       switch (op) {
4163         case kMathExp:
4164           return H_CONSTANT_DOUBLE((d > 0.0) ? d : 0.0);
4165         case kMathLog:
4166         case kMathSqrt:
4167           return H_CONSTANT_DOUBLE((d > 0.0) ? d : base::OS::nan_value());
4168         case kMathPowHalf:
4169         case kMathAbs:
4170           return H_CONSTANT_DOUBLE((d > 0.0) ? d : -d);
4171         case kMathRound:
4172         case kMathFround:
4173         case kMathFloor:
4174           return H_CONSTANT_DOUBLE(d);
4175         case kMathClz32:
4176           return H_CONSTANT_INT(32);
4177         default:
4178           UNREACHABLE();
4179           break;
4180       }
4181     }
4182     switch (op) {
4183       case kMathExp:
4184         return H_CONSTANT_DOUBLE(fast_exp(d));
4185       case kMathLog:
4186         return H_CONSTANT_DOUBLE(std::log(d));
4187       case kMathSqrt:
4188         return H_CONSTANT_DOUBLE(fast_sqrt(d));
4189       case kMathPowHalf:
4190         return H_CONSTANT_DOUBLE(power_double_double(d, 0.5));
4191       case kMathAbs:
4192         return H_CONSTANT_DOUBLE((d >= 0.0) ? d + 0.0 : -d);
4193       case kMathRound:
4194         // -0.5 .. -0.0 round to -0.0.
4195         if ((d >= -0.5 && Double(d).Sign() < 0)) return H_CONSTANT_DOUBLE(-0.0);
4196         // Doubles are represented as Significant * 2 ^ Exponent. If the
4197         // Exponent is not negative, the double value is already an integer.
4198         if (Double(d).Exponent() >= 0) return H_CONSTANT_DOUBLE(d);
4199         return H_CONSTANT_DOUBLE(Floor(d + 0.5));
4200       case kMathFround:
4201         return H_CONSTANT_DOUBLE(static_cast<double>(static_cast<float>(d)));
4202       case kMathFloor:
4203         return H_CONSTANT_DOUBLE(Floor(d));
4204       case kMathClz32: {
4205         uint32_t i = DoubleToUint32(d);
4206         return H_CONSTANT_INT(
4207             (i == 0) ? 32 : CompilerIntrinsics::CountLeadingZeros(i));
4208       }
4209       default:
4210         UNREACHABLE();
4211         break;
4212     }
4213   } while (false);
4214   return new(zone) HUnaryMathOperation(context, value, op);
4215 }
4216
4217
4218 Representation HUnaryMathOperation::RepresentationFromUses() {
4219   if (op_ != kMathFloor && op_ != kMathRound) {
4220     return HValue::RepresentationFromUses();
4221   }
4222
4223   // The instruction can have an int32 or double output. Prefer a double
4224   // representation if there are double uses.
4225   bool use_double = false;
4226
4227   for (HUseIterator it(uses()); !it.Done(); it.Advance()) {
4228     HValue* use = it.value();
4229     int use_index = it.index();
4230     Representation rep_observed = use->observed_input_representation(use_index);
4231     Representation rep_required = use->RequiredInputRepresentation(use_index);
4232     use_double |= (rep_observed.IsDouble() || rep_required.IsDouble());
4233     if (use_double && !FLAG_trace_representation) {
4234       // Having seen one double is enough.
4235       break;
4236     }
4237     if (FLAG_trace_representation) {
4238       if (!rep_required.IsDouble() || rep_observed.IsDouble()) {
4239         PrintF("#%d %s is used by #%d %s as %s%s\n",
4240                id(), Mnemonic(), use->id(),
4241                use->Mnemonic(), rep_observed.Mnemonic(),
4242                (use->CheckFlag(kTruncatingToInt32) ? "-trunc" : ""));
4243       } else {
4244         PrintF("#%d %s is required by #%d %s as %s%s\n",
4245                id(), Mnemonic(), use->id(),
4246                use->Mnemonic(), rep_required.Mnemonic(),
4247                (use->CheckFlag(kTruncatingToInt32) ? "-trunc" : ""));
4248       }
4249     }
4250   }
4251   return use_double ? Representation::Double() : Representation::Integer32();
4252 }
4253
4254
4255 HInstruction* HPower::New(Zone* zone,
4256                           HValue* context,
4257                           HValue* left,
4258                           HValue* right) {
4259   if (FLAG_fold_constants && left->IsConstant() && right->IsConstant()) {
4260     HConstant* c_left = HConstant::cast(left);
4261     HConstant* c_right = HConstant::cast(right);
4262     if (c_left->HasNumberValue() && c_right->HasNumberValue()) {
4263       double result = power_helper(c_left->DoubleValue(),
4264                                    c_right->DoubleValue());
4265       return H_CONSTANT_DOUBLE(std::isnan(result) ? base::OS::nan_value()
4266                                                   : result);
4267     }
4268   }
4269   return new(zone) HPower(left, right);
4270 }
4271
4272
4273 HInstruction* HMathMinMax::New(
4274     Zone* zone, HValue* context, HValue* left, HValue* right, Operation op) {
4275   if (FLAG_fold_constants && left->IsConstant() && right->IsConstant()) {
4276     HConstant* c_left = HConstant::cast(left);
4277     HConstant* c_right = HConstant::cast(right);
4278     if (c_left->HasNumberValue() && c_right->HasNumberValue()) {
4279       double d_left = c_left->DoubleValue();
4280       double d_right = c_right->DoubleValue();
4281       if (op == kMathMin) {
4282         if (d_left > d_right) return H_CONSTANT_DOUBLE(d_right);
4283         if (d_left < d_right) return H_CONSTANT_DOUBLE(d_left);
4284         if (d_left == d_right) {
4285           // Handle +0 and -0.
4286           return H_CONSTANT_DOUBLE((Double(d_left).Sign() == -1) ? d_left
4287                                                                  : d_right);
4288         }
4289       } else {
4290         if (d_left < d_right) return H_CONSTANT_DOUBLE(d_right);
4291         if (d_left > d_right) return H_CONSTANT_DOUBLE(d_left);
4292         if (d_left == d_right) {
4293           // Handle +0 and -0.
4294           return H_CONSTANT_DOUBLE((Double(d_left).Sign() == -1) ? d_right
4295                                                                  : d_left);
4296         }
4297       }
4298       // All comparisons failed, must be NaN.
4299       return H_CONSTANT_DOUBLE(base::OS::nan_value());
4300     }
4301   }
4302   return new(zone) HMathMinMax(context, left, right, op);
4303 }
4304
4305
4306 HInstruction* HMod::New(Zone* zone,
4307                         HValue* context,
4308                         HValue* left,
4309                         HValue* right) {
4310   if (FLAG_fold_constants && left->IsConstant() && right->IsConstant()) {
4311     HConstant* c_left = HConstant::cast(left);
4312     HConstant* c_right = HConstant::cast(right);
4313     if (c_left->HasInteger32Value() && c_right->HasInteger32Value()) {
4314       int32_t dividend = c_left->Integer32Value();
4315       int32_t divisor = c_right->Integer32Value();
4316       if (dividend == kMinInt && divisor == -1) {
4317         return H_CONSTANT_DOUBLE(-0.0);
4318       }
4319       if (divisor != 0) {
4320         int32_t res = dividend % divisor;
4321         if ((res == 0) && (dividend < 0)) {
4322           return H_CONSTANT_DOUBLE(-0.0);
4323         }
4324         return H_CONSTANT_INT(res);
4325       }
4326     }
4327   }
4328   return new(zone) HMod(context, left, right);
4329 }
4330
4331
4332 HInstruction* HDiv::New(
4333     Zone* zone, HValue* context, HValue* left, HValue* right) {
4334   // If left and right are constant values, try to return a constant value.
4335   if (FLAG_fold_constants && left->IsConstant() && right->IsConstant()) {
4336     HConstant* c_left = HConstant::cast(left);
4337     HConstant* c_right = HConstant::cast(right);
4338     if ((c_left->HasNumberValue() && c_right->HasNumberValue())) {
4339       if (c_right->DoubleValue() != 0) {
4340         double double_res = c_left->DoubleValue() / c_right->DoubleValue();
4341         if (IsInt32Double(double_res)) {
4342           return H_CONSTANT_INT(double_res);
4343         }
4344         return H_CONSTANT_DOUBLE(double_res);
4345       } else {
4346         int sign = Double(c_left->DoubleValue()).Sign() *
4347                    Double(c_right->DoubleValue()).Sign();  // Right could be -0.
4348         return H_CONSTANT_DOUBLE(sign * V8_INFINITY);
4349       }
4350     }
4351   }
4352   return new(zone) HDiv(context, left, right);
4353 }
4354
4355
4356 HInstruction* HBitwise::New(
4357     Zone* zone, HValue* context, Token::Value op, HValue* left, HValue* right) {
4358   if (FLAG_fold_constants && left->IsConstant() && right->IsConstant()) {
4359     HConstant* c_left = HConstant::cast(left);
4360     HConstant* c_right = HConstant::cast(right);
4361     if ((c_left->HasNumberValue() && c_right->HasNumberValue())) {
4362       int32_t result;
4363       int32_t v_left = c_left->NumberValueAsInteger32();
4364       int32_t v_right = c_right->NumberValueAsInteger32();
4365       switch (op) {
4366         case Token::BIT_XOR:
4367           result = v_left ^ v_right;
4368           break;
4369         case Token::BIT_AND:
4370           result = v_left & v_right;
4371           break;
4372         case Token::BIT_OR:
4373           result = v_left | v_right;
4374           break;
4375         default:
4376           result = 0;  // Please the compiler.
4377           UNREACHABLE();
4378       }
4379       return H_CONSTANT_INT(result);
4380     }
4381   }
4382   return new(zone) HBitwise(context, op, left, right);
4383 }
4384
4385
4386 #define DEFINE_NEW_H_BITWISE_INSTR(HInstr, result)                             \
4387 HInstruction* HInstr::New(                                                     \
4388     Zone* zone, HValue* context, HValue* left, HValue* right) {                \
4389   if (FLAG_fold_constants && left->IsConstant() && right->IsConstant()) {      \
4390     HConstant* c_left = HConstant::cast(left);                                 \
4391     HConstant* c_right = HConstant::cast(right);                               \
4392     if ((c_left->HasNumberValue() && c_right->HasNumberValue())) {             \
4393       return H_CONSTANT_INT(result);                                           \
4394     }                                                                          \
4395   }                                                                            \
4396   return new(zone) HInstr(context, left, right);                               \
4397 }
4398
4399
4400 DEFINE_NEW_H_BITWISE_INSTR(HSar,
4401 c_left->NumberValueAsInteger32() >> (c_right->NumberValueAsInteger32() & 0x1f))
4402 DEFINE_NEW_H_BITWISE_INSTR(HShl,
4403 c_left->NumberValueAsInteger32() << (c_right->NumberValueAsInteger32() & 0x1f))
4404
4405 #undef DEFINE_NEW_H_BITWISE_INSTR
4406
4407
4408 HInstruction* HShr::New(
4409     Zone* zone, HValue* context, HValue* left, HValue* right) {
4410   if (FLAG_fold_constants && left->IsConstant() && right->IsConstant()) {
4411     HConstant* c_left = HConstant::cast(left);
4412     HConstant* c_right = HConstant::cast(right);
4413     if ((c_left->HasNumberValue() && c_right->HasNumberValue())) {
4414       int32_t left_val = c_left->NumberValueAsInteger32();
4415       int32_t right_val = c_right->NumberValueAsInteger32() & 0x1f;
4416       if ((right_val == 0) && (left_val < 0)) {
4417         return H_CONSTANT_DOUBLE(static_cast<uint32_t>(left_val));
4418       }
4419       return H_CONSTANT_INT(static_cast<uint32_t>(left_val) >> right_val);
4420     }
4421   }
4422   return new(zone) HShr(context, left, right);
4423 }
4424
4425
4426 HInstruction* HSeqStringGetChar::New(Zone* zone,
4427                                      HValue* context,
4428                                      String::Encoding encoding,
4429                                      HValue* string,
4430                                      HValue* index) {
4431   if (FLAG_fold_constants && string->IsConstant() && index->IsConstant()) {
4432     HConstant* c_string = HConstant::cast(string);
4433     HConstant* c_index = HConstant::cast(index);
4434     if (c_string->HasStringValue() && c_index->HasInteger32Value()) {
4435       Handle<String> s = c_string->StringValue();
4436       int32_t i = c_index->Integer32Value();
4437       DCHECK_LE(0, i);
4438       DCHECK_LT(i, s->length());
4439       return H_CONSTANT_INT(s->Get(i));
4440     }
4441   }
4442   return new(zone) HSeqStringGetChar(encoding, string, index);
4443 }
4444
4445
4446 #undef H_CONSTANT_INT
4447 #undef H_CONSTANT_DOUBLE
4448
4449
4450 OStream& HBitwise::PrintDataTo(OStream& os) const {  // NOLINT
4451   os << Token::Name(op_) << " ";
4452   return HBitwiseBinaryOperation::PrintDataTo(os);
4453 }
4454
4455
4456 void HPhi::SimplifyConstantInputs() {
4457   // Convert constant inputs to integers when all uses are truncating.
4458   // This must happen before representation inference takes place.
4459   if (!CheckUsesForFlag(kTruncatingToInt32)) return;
4460   for (int i = 0; i < OperandCount(); ++i) {
4461     if (!OperandAt(i)->IsConstant()) return;
4462   }
4463   HGraph* graph = block()->graph();
4464   for (int i = 0; i < OperandCount(); ++i) {
4465     HConstant* operand = HConstant::cast(OperandAt(i));
4466     if (operand->HasInteger32Value()) {
4467       continue;
4468     } else if (operand->HasDoubleValue()) {
4469       HConstant* integer_input =
4470           HConstant::New(graph->zone(), graph->GetInvalidContext(),
4471                          DoubleToInt32(operand->DoubleValue()));
4472       integer_input->InsertAfter(operand);
4473       SetOperandAt(i, integer_input);
4474     } else if (operand->HasBooleanValue()) {
4475       SetOperandAt(i, operand->BooleanValue() ? graph->GetConstant1()
4476                                               : graph->GetConstant0());
4477     } else if (operand->ImmortalImmovable()) {
4478       SetOperandAt(i, graph->GetConstant0());
4479     }
4480   }
4481   // Overwrite observed input representations because they are likely Tagged.
4482   for (HUseIterator it(uses()); !it.Done(); it.Advance()) {
4483     HValue* use = it.value();
4484     if (use->IsBinaryOperation()) {
4485       HBinaryOperation::cast(use)->set_observed_input_representation(
4486           it.index(), Representation::Smi());
4487     }
4488   }
4489 }
4490
4491
4492 void HPhi::InferRepresentation(HInferRepresentationPhase* h_infer) {
4493   DCHECK(CheckFlag(kFlexibleRepresentation));
4494   Representation new_rep = RepresentationFromInputs();
4495   UpdateRepresentation(new_rep, h_infer, "inputs");
4496   new_rep = RepresentationFromUses();
4497   UpdateRepresentation(new_rep, h_infer, "uses");
4498   new_rep = RepresentationFromUseRequirements();
4499   UpdateRepresentation(new_rep, h_infer, "use requirements");
4500 }
4501
4502
4503 Representation HPhi::RepresentationFromInputs() {
4504   Representation r = Representation::None();
4505   for (int i = 0; i < OperandCount(); ++i) {
4506     r = r.generalize(OperandAt(i)->KnownOptimalRepresentation());
4507   }
4508   return r;
4509 }
4510
4511
4512 // Returns a representation if all uses agree on the same representation.
4513 // Integer32 is also returned when some uses are Smi but others are Integer32.
4514 Representation HValue::RepresentationFromUseRequirements() {
4515   Representation rep = Representation::None();
4516   for (HUseIterator it(uses()); !it.Done(); it.Advance()) {
4517     // Ignore the use requirement from never run code
4518     if (it.value()->block()->IsUnreachable()) continue;
4519
4520     // We check for observed_input_representation elsewhere.
4521     Representation use_rep =
4522         it.value()->RequiredInputRepresentation(it.index());
4523     if (rep.IsNone()) {
4524       rep = use_rep;
4525       continue;
4526     }
4527     if (use_rep.IsNone() || rep.Equals(use_rep)) continue;
4528     if (rep.generalize(use_rep).IsInteger32()) {
4529       rep = Representation::Integer32();
4530       continue;
4531     }
4532     return Representation::None();
4533   }
4534   return rep;
4535 }
4536
4537
4538 bool HValue::HasNonSmiUse() {
4539   for (HUseIterator it(uses()); !it.Done(); it.Advance()) {
4540     // We check for observed_input_representation elsewhere.
4541     Representation use_rep =
4542         it.value()->RequiredInputRepresentation(it.index());
4543     if (!use_rep.IsNone() &&
4544         !use_rep.IsSmi() &&
4545         !use_rep.IsTagged()) {
4546       return true;
4547     }
4548   }
4549   return false;
4550 }
4551
4552
4553 // Node-specific verification code is only included in debug mode.
4554 #ifdef DEBUG
4555
4556 void HPhi::Verify() {
4557   DCHECK(OperandCount() == block()->predecessors()->length());
4558   for (int i = 0; i < OperandCount(); ++i) {
4559     HValue* value = OperandAt(i);
4560     HBasicBlock* defining_block = value->block();
4561     HBasicBlock* predecessor_block = block()->predecessors()->at(i);
4562     DCHECK(defining_block == predecessor_block ||
4563            defining_block->Dominates(predecessor_block));
4564   }
4565 }
4566
4567
4568 void HSimulate::Verify() {
4569   HInstruction::Verify();
4570   DCHECK(HasAstId() || next()->IsEnterInlined());
4571 }
4572
4573
4574 void HCheckHeapObject::Verify() {
4575   HInstruction::Verify();
4576   DCHECK(HasNoUses());
4577 }
4578
4579
4580 void HCheckValue::Verify() {
4581   HInstruction::Verify();
4582   DCHECK(HasNoUses());
4583 }
4584
4585 #endif
4586
4587
4588 HObjectAccess HObjectAccess::ForFixedArrayHeader(int offset) {
4589   DCHECK(offset >= 0);
4590   DCHECK(offset < FixedArray::kHeaderSize);
4591   if (offset == FixedArray::kLengthOffset) return ForFixedArrayLength();
4592   return HObjectAccess(kInobject, offset);
4593 }
4594
4595
4596 HObjectAccess HObjectAccess::ForMapAndOffset(Handle<Map> map, int offset,
4597     Representation representation) {
4598   DCHECK(offset >= 0);
4599   Portion portion = kInobject;
4600
4601   if (offset == JSObject::kElementsOffset) {
4602     portion = kElementsPointer;
4603   } else if (offset == JSObject::kMapOffset) {
4604     portion = kMaps;
4605   }
4606   bool existing_inobject_property = true;
4607   if (!map.is_null()) {
4608     existing_inobject_property = (offset <
4609         map->instance_size() - map->unused_property_fields() * kPointerSize);
4610   }
4611   return HObjectAccess(portion, offset, representation, Handle<String>::null(),
4612                        false, existing_inobject_property);
4613 }
4614
4615
4616 HObjectAccess HObjectAccess::ForAllocationSiteOffset(int offset) {
4617   switch (offset) {
4618     case AllocationSite::kTransitionInfoOffset:
4619       return HObjectAccess(kInobject, offset, Representation::Tagged());
4620     case AllocationSite::kNestedSiteOffset:
4621       return HObjectAccess(kInobject, offset, Representation::Tagged());
4622     case AllocationSite::kPretenureDataOffset:
4623       return HObjectAccess(kInobject, offset, Representation::Smi());
4624     case AllocationSite::kPretenureCreateCountOffset:
4625       return HObjectAccess(kInobject, offset, Representation::Smi());
4626     case AllocationSite::kDependentCodeOffset:
4627       return HObjectAccess(kInobject, offset, Representation::Tagged());
4628     case AllocationSite::kWeakNextOffset:
4629       return HObjectAccess(kInobject, offset, Representation::Tagged());
4630     default:
4631       UNREACHABLE();
4632   }
4633   return HObjectAccess(kInobject, offset);
4634 }
4635
4636
4637 HObjectAccess HObjectAccess::ForContextSlot(int index) {
4638   DCHECK(index >= 0);
4639   Portion portion = kInobject;
4640   int offset = Context::kHeaderSize + index * kPointerSize;
4641   DCHECK_EQ(offset, Context::SlotOffset(index) + kHeapObjectTag);
4642   return HObjectAccess(portion, offset, Representation::Tagged());
4643 }
4644
4645
4646 HObjectAccess HObjectAccess::ForJSArrayOffset(int offset) {
4647   DCHECK(offset >= 0);
4648   Portion portion = kInobject;
4649
4650   if (offset == JSObject::kElementsOffset) {
4651     portion = kElementsPointer;
4652   } else if (offset == JSArray::kLengthOffset) {
4653     portion = kArrayLengths;
4654   } else if (offset == JSObject::kMapOffset) {
4655     portion = kMaps;
4656   }
4657   return HObjectAccess(portion, offset);
4658 }
4659
4660
4661 HObjectAccess HObjectAccess::ForBackingStoreOffset(int offset,
4662     Representation representation) {
4663   DCHECK(offset >= 0);
4664   return HObjectAccess(kBackingStore, offset, representation,
4665                        Handle<String>::null(), false, false);
4666 }
4667
4668
4669 HObjectAccess HObjectAccess::ForField(Handle<Map> map,
4670                                       LookupResult* lookup,
4671                                       Handle<String> name) {
4672   DCHECK(lookup->IsField() || lookup->IsTransitionToField());
4673   int index;
4674   Representation representation;
4675   if (lookup->IsField()) {
4676     index = lookup->GetLocalFieldIndexFromMap(*map);
4677     representation = lookup->representation();
4678   } else {
4679     Map* transition = lookup->GetTransitionTarget();
4680     int descriptor = transition->LastAdded();
4681     index = transition->instance_descriptors()->GetFieldIndex(descriptor) -
4682         map->inobject_properties();
4683     PropertyDetails details =
4684         transition->instance_descriptors()->GetDetails(descriptor);
4685     representation = details.representation();
4686   }
4687   if (index < 0) {
4688     // Negative property indices are in-object properties, indexed
4689     // from the end of the fixed part of the object.
4690     int offset = (index * kPointerSize) + map->instance_size();
4691     return HObjectAccess(kInobject, offset, representation, name, false, true);
4692   } else {
4693     // Non-negative property indices are in the properties array.
4694     int offset = (index * kPointerSize) + FixedArray::kHeaderSize;
4695     return HObjectAccess(kBackingStore, offset, representation, name,
4696                          false, false);
4697   }
4698 }
4699
4700
4701 HObjectAccess HObjectAccess::ForCellPayload(Isolate* isolate) {
4702   return HObjectAccess(
4703       kInobject, Cell::kValueOffset, Representation::Tagged(),
4704       Handle<String>(isolate->heap()->cell_value_string()));
4705 }
4706
4707
4708 void HObjectAccess::SetGVNFlags(HValue *instr, PropertyAccessType access_type) {
4709   // set the appropriate GVN flags for a given load or store instruction
4710   if (access_type == STORE) {
4711     // track dominating allocations in order to eliminate write barriers
4712     instr->SetDependsOnFlag(::v8::internal::kNewSpacePromotion);
4713     instr->SetFlag(HValue::kTrackSideEffectDominators);
4714   } else {
4715     // try to GVN loads, but don't hoist above map changes
4716     instr->SetFlag(HValue::kUseGVN);
4717     instr->SetDependsOnFlag(::v8::internal::kMaps);
4718   }
4719
4720   switch (portion()) {
4721     case kArrayLengths:
4722       if (access_type == STORE) {
4723         instr->SetChangesFlag(::v8::internal::kArrayLengths);
4724       } else {
4725         instr->SetDependsOnFlag(::v8::internal::kArrayLengths);
4726       }
4727       break;
4728     case kStringLengths:
4729       if (access_type == STORE) {
4730         instr->SetChangesFlag(::v8::internal::kStringLengths);
4731       } else {
4732         instr->SetDependsOnFlag(::v8::internal::kStringLengths);
4733       }
4734       break;
4735     case kInobject:
4736       if (access_type == STORE) {
4737         instr->SetChangesFlag(::v8::internal::kInobjectFields);
4738       } else {
4739         instr->SetDependsOnFlag(::v8::internal::kInobjectFields);
4740       }
4741       break;
4742     case kDouble:
4743       if (access_type == STORE) {
4744         instr->SetChangesFlag(::v8::internal::kDoubleFields);
4745       } else {
4746         instr->SetDependsOnFlag(::v8::internal::kDoubleFields);
4747       }
4748       break;
4749     case kBackingStore:
4750       if (access_type == STORE) {
4751         instr->SetChangesFlag(::v8::internal::kBackingStoreFields);
4752       } else {
4753         instr->SetDependsOnFlag(::v8::internal::kBackingStoreFields);
4754       }
4755       break;
4756     case kElementsPointer:
4757       if (access_type == STORE) {
4758         instr->SetChangesFlag(::v8::internal::kElementsPointer);
4759       } else {
4760         instr->SetDependsOnFlag(::v8::internal::kElementsPointer);
4761       }
4762       break;
4763     case kMaps:
4764       if (access_type == STORE) {
4765         instr->SetChangesFlag(::v8::internal::kMaps);
4766       } else {
4767         instr->SetDependsOnFlag(::v8::internal::kMaps);
4768       }
4769       break;
4770     case kExternalMemory:
4771       if (access_type == STORE) {
4772         instr->SetChangesFlag(::v8::internal::kExternalMemory);
4773       } else {
4774         instr->SetDependsOnFlag(::v8::internal::kExternalMemory);
4775       }
4776       break;
4777   }
4778 }
4779
4780
4781 OStream& operator<<(OStream& os, const HObjectAccess& access) {
4782   os << ".";
4783
4784   switch (access.portion()) {
4785     case HObjectAccess::kArrayLengths:
4786     case HObjectAccess::kStringLengths:
4787       os << "%length";
4788       break;
4789     case HObjectAccess::kElementsPointer:
4790       os << "%elements";
4791       break;
4792     case HObjectAccess::kMaps:
4793       os << "%map";
4794       break;
4795     case HObjectAccess::kDouble:  // fall through
4796     case HObjectAccess::kInobject:
4797       if (!access.name().is_null()) {
4798         os << Handle<String>::cast(access.name())->ToCString().get();
4799       }
4800       os << "[in-object]";
4801       break;
4802     case HObjectAccess::kBackingStore:
4803       if (!access.name().is_null()) {
4804         os << Handle<String>::cast(access.name())->ToCString().get();
4805       }
4806       os << "[backing-store]";
4807       break;
4808     case HObjectAccess::kExternalMemory:
4809       os << "[external-memory]";
4810       break;
4811   }
4812
4813   return os << "@" << access.offset();
4814 }
4815
4816
4817 HInstruction* HNullarySIMDOperation::New(
4818     Zone* zone, HValue* context, BuiltinFunctionId op) {
4819   return new(zone) HNullarySIMDOperation(context, op);
4820 }
4821
4822
4823 HInstruction* HUnarySIMDOperation::New(
4824     Zone* zone, HValue* context, HValue* value, BuiltinFunctionId op,
4825     Representation to) {
4826   return new(zone) HUnarySIMDOperation(context, value, op, to);
4827 }
4828
4829
4830 HInstruction* HBinarySIMDOperation::New(
4831     Zone* zone, HValue* context, HValue* left, HValue* right,
4832     BuiltinFunctionId op) {
4833   return new(zone) HBinarySIMDOperation(context, left, right, op);
4834 }
4835
4836
4837 HInstruction* HTernarySIMDOperation::New(
4838     Zone* zone, HValue* context, HValue* mask, HValue* left, HValue* right,
4839     BuiltinFunctionId op) {
4840   return new(zone) HTernarySIMDOperation(context, mask, left, right, op);
4841 }
4842
4843
4844 HInstruction* HQuarternarySIMDOperation::New(
4845     Zone* zone, HValue* context, HValue* x, HValue* y, HValue* z, HValue* w,
4846     BuiltinFunctionId op) {
4847   return new(zone) HQuarternarySIMDOperation(context, x, y, z, w, op);
4848 }
4849
4850
4851 const char* HNullarySIMDOperation::OpName() const {
4852   switch (op()) {
4853 #define SIMD_NULLARY_OPERATION_CASE_ITEM(module, function, name, p4)           \
4854     case k##name:                                                              \
4855       return #module "." #function;
4856 SIMD_NULLARY_OPERATIONS(SIMD_NULLARY_OPERATION_CASE_ITEM)
4857 #undef SIMD_NULLARY_OPERATION_CASE_ITEM
4858     default:
4859       UNREACHABLE();
4860       return NULL;
4861   }
4862 }
4863
4864
4865 OStream& HNullarySIMDOperation::PrintDataTo(OStream& os) const {
4866   return os << OpName();
4867 }
4868
4869
4870 const char* HUnarySIMDOperation::OpName() const {
4871   switch (op()) {
4872 #define SIMD_UNARY_OPERATION_CASE_ITEM(module, function, name, p4, p5)         \
4873     case k##name:                                                              \
4874       return #module "." #function;
4875 SIMD_UNARY_OPERATIONS(SIMD_UNARY_OPERATION_CASE_ITEM)
4876 SIMD_UNARY_OPERATIONS_FOR_PROPERTY_ACCESS(SIMD_UNARY_OPERATION_CASE_ITEM)
4877 #undef SIMD_UNARY_OPERATION_CASE_ITEM
4878     default:
4879       UNREACHABLE();
4880       return NULL;
4881   }
4882 }
4883
4884
4885 OStream& HUnarySIMDOperation::PrintDataTo(OStream& os) const {
4886   return os << OpName() << " " << NameOf(value());
4887 }
4888
4889
4890 const char* HBinarySIMDOperation::OpName() const {
4891   switch (op()) {
4892 #define SIMD_BINARY_OPERATION_CASE_ITEM(module, function, name, p4, p5, p6)    \
4893     case k##name:                                                              \
4894       return #module "." #function;
4895 SIMD_BINARY_OPERATIONS(SIMD_BINARY_OPERATION_CASE_ITEM)
4896 #undef SIMD_BINARY_OPERATION_CASE_ITEM
4897     default:
4898       UNREACHABLE();
4899       return NULL;
4900   }
4901 }
4902
4903
4904 OStream& HBinarySIMDOperation::PrintDataTo(OStream& os) const {
4905   return os << OpName() << " " << NameOf(left()) << " "
4906             << NameOf(right());
4907 }
4908
4909
4910 const char* HTernarySIMDOperation::OpName() const {
4911   switch (op()) {
4912 #define SIMD_TERNARY_OPERATION_CASE_ITEM(module, function, name, p4, p5, p6,   \
4913                                          p7)                                   \
4914     case k##name:                                                              \
4915       return #module "." #function;
4916 SIMD_TERNARY_OPERATIONS(SIMD_TERNARY_OPERATION_CASE_ITEM)
4917 #undef SIMD_TERNARY_OPERATION_CASE_ITEM
4918     default:
4919       UNREACHABLE();
4920       return NULL;
4921   }
4922 }
4923
4924
4925 OStream& HTernarySIMDOperation::PrintDataTo(OStream& os) const {
4926   return os << OpName() << " " << NameOf(first()) << " "
4927             << NameOf(second()) << " " << NameOf(third());
4928 }
4929
4930
4931 const char* HQuarternarySIMDOperation::OpName() const {
4932   switch (op()) {
4933 #define SIMD_QUARTERNARY_OPERATION_CASE_ITEM(module, function, name, p4, p5,   \
4934                                              p6, p7, p8)                       \
4935     case k##name:                                                              \
4936       return #module "." #function;
4937 SIMD_QUARTERNARY_OPERATIONS(SIMD_QUARTERNARY_OPERATION_CASE_ITEM)
4938 #undef SIMD_QUARTERNARY_OPERATION_CASE_ITEM
4939     default:
4940       UNREACHABLE();
4941       return NULL;
4942   }
4943 }
4944
4945
4946 OStream& HQuarternarySIMDOperation::PrintDataTo(OStream& os) const {
4947   return os << OpName() << " " << NameOf(x()) << " " << NameOf(y()) << " "
4948             << NameOf(z()) << " " << NameOf(w());
4949 }
4950
4951
4952 } }  // namespace v8::internal