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