src/v8/src/hydrogen-instructions.cc

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