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