CSE2410 Fall 2014 Bounce

// Copyright 2013 the V8 project authors. All rights reserved.

// Redistribution and use in source and binary forms, with or without

// modification, are permitted provided that the following conditions are

// met:

//

//     * Redistributions of source code must retain the above copyright

//       notice, this list of conditions and the following disclaimer.

//     * Redistributions in binary form must reproduce the above

//       copyright notice, this list of conditions and the following

//       disclaimer in the documentation and/or other materials provided

//       with the distribution.

//     * Neither the name of Google Inc. nor the names of its

//       contributors may be used to endorse or promote products derived

//       from this software without specific prior written permission.

//

// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS

// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT

// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR

// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT

// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,

// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT

// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,

// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY

// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT

// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE

// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

#include "hydrogen.h"

#include <algorithm>

#include "v8.h"

#include "allocation-site-scopes.h"

#include "codegen.h"

#include "full-codegen.h"

#include "hashmap.h"

#include "hydrogen-bce.h"

#include "hydrogen-bch.h"

#include "hydrogen-canonicalize.h"

#include "hydrogen-check-elimination.h"

#include "hydrogen-dce.h"

#include "hydrogen-dehoist.h"

#include "hydrogen-environment-liveness.h"

#include "hydrogen-escape-analysis.h"

#include "hydrogen-infer-representation.h"

#include "hydrogen-infer-types.h"

#include "hydrogen-load-elimination.h"

#include "hydrogen-gvn.h"

#include "hydrogen-mark-deoptimize.h"

#include "hydrogen-mark-unreachable.h"

#include "hydrogen-minus-zero.h"

#include "hydrogen-osr.h"

#include "hydrogen-range-analysis.h"

#include "hydrogen-redundant-phi.h"

#include "hydrogen-removable-simulates.h"

#include "hydrogen-representation-changes.h"

#include "hydrogen-sce.h"

#include "hydrogen-uint32-analysis.h"

#include "lithium-allocator.h"

#include "parser.h"

#include "scopeinfo.h"

#include "scopes.h"

#include "stub-cache.h"

#include "typing.h"

#if V8_TARGET_ARCH_IA32

#include "ia32/lithium-codegen-ia32.h"

#elif V8_TARGET_ARCH_X64

#include "x64/lithium-codegen-x64.h"

#elif V8_TARGET_ARCH_ARM

#include "arm/lithium-codegen-arm.h"

#elif V8_TARGET_ARCH_MIPS

#include "mips/lithium-codegen-mips.h"

#else

#error Unsupported target architecture.

#endif

namespace v8 {

namespace internal {

HBasicBlock::HBasicBlock(HGraph* graph)

    : block_id_(graph->GetNextBlockID()),

      graph_(graph),

      phis_(4, graph->zone()),

      first_(NULL),

      last_(NULL),

      end_(NULL),

      loop_information_(NULL),

      predecessors_(2, graph->zone()),

      dominator_(NULL),

      dominated_blocks_(4, graph->zone()),

      last_environment_(NULL),

      argument_count_(-1),

      first_instruction_index_(-1),

      last_instruction_index_(-1),

      deleted_phis_(4, graph->zone()),

      parent_loop_header_(NULL),

      inlined_entry_block_(NULL),

      is_inline_return_target_(false),

      is_reachable_(true),

      dominates_loop_successors_(false),

      is_osr_entry_(false) { }

Isolate* HBasicBlock::isolate() const {

  return graph_->isolate();

}

void HBasicBlock::MarkUnreachable() {

  is_reachable_ = false;

}

void HBasicBlock::AttachLoopInformation() {

  ASSERT(!IsLoopHeader());

  loop_information_ = new(zone()) HLoopInformation(this, zone());

}

void HBasicBlock::DetachLoopInformation() {

  ASSERT(IsLoopHeader());

  loop_information_ = NULL;

}

void HBasicBlock::AddPhi(HPhi* phi) {

  ASSERT(!IsStartBlock());

  phis_.Add(phi, zone());

  phi->SetBlock(this);

}

void HBasicBlock::RemovePhi(HPhi* phi) {

  ASSERT(phi->block() == this);

  ASSERT(phis_.Contains(phi));

  phi->Kill();

  phis_.RemoveElement(phi);

  phi->SetBlock(NULL);

}

void HBasicBlock::AddInstruction(HInstruction* instr, int position) {

  ASSERT(!IsStartBlock() || !IsFinished());

  ASSERT(!instr->IsLinked());

  ASSERT(!IsFinished());

  if (position != RelocInfo::kNoPosition) {

    instr->set_position(position);

  }

  if (first_ == NULL) {

    ASSERT(last_environment() != NULL);

    ASSERT(!last_environment()->ast_id().IsNone());

    HBlockEntry* entry = new(zone()) HBlockEntry();

    entry->InitializeAsFirst(this);

    if (position != RelocInfo::kNoPosition) {

      entry->set_position(position);

    } else {

      ASSERT(!FLAG_emit_opt_code_positions ||

             !graph()->info()->IsOptimizing());

    }

    first_ = last_ = entry;

  }

  instr->InsertAfter(last_);

}

HPhi* HBasicBlock::AddNewPhi(int merged_index) {

  if (graph()->IsInsideNoSideEffectsScope()) {

    merged_index = HPhi::kInvalidMergedIndex;

  }

  HPhi* phi = new(zone()) HPhi(merged_index, zone());

  AddPhi(phi);

  return phi;

}

HSimulate* HBasicBlock::CreateSimulate(BailoutId ast_id,

                                       RemovableSimulate removable) {

  ASSERT(HasEnvironment());

  HEnvironment* environment = last_environment();

  ASSERT(ast_id.IsNone() ||

         ast_id == BailoutId::StubEntry() ||

         environment->closure()->shared()->VerifyBailoutId(ast_id));

  int push_count = environment->push_count();

  int pop_count = environment->pop_count();

  HSimulate* instr =

      new(zone()) HSimulate(ast_id, pop_count, zone(), removable);

#ifdef DEBUG

  instr->set_closure(environment->closure());

#endif

  // Order of pushed values: newest (top of stack) first. This allows

  // HSimulate::MergeWith() to easily append additional pushed values

  // that are older (from further down the stack).

  for (int i = 0; i < push_count; ++i) {

    instr->AddPushedValue(environment->ExpressionStackAt(i));

  }

  for (GrowableBitVector::Iterator it(environment->assigned_variables(),

                                      zone());

       !it.Done();

       it.Advance()) {

    int index = it.Current();

    instr->AddAssignedValue(index, environment->Lookup(index));

  }

  environment->ClearHistory();

  return instr;

}

void HBasicBlock::Finish(HControlInstruction* end, int position) {

  ASSERT(!IsFinished());

  AddInstruction(end, position);

  end_ = end;

  for (HSuccessorIterator it(end); !it.Done(); it.Advance()) {

    it.Current()->RegisterPredecessor(this);

  }

}

void HBasicBlock::Goto(HBasicBlock* block,

                       int position,

                       FunctionState* state,

                       bool add_simulate) {

  bool drop_extra = state != NULL &&

      state->inlining_kind() == DROP_EXTRA_ON_RETURN;

  if (block->IsInlineReturnTarget()) {

    HEnvironment* env = last_environment();

    int argument_count = env->arguments_environment()->parameter_count();

    AddInstruction(new(zone())

                   HLeaveInlined(state->entry(), argument_count),

                   position);

    UpdateEnvironment(last_environment()->DiscardInlined(drop_extra));

  }

  if (add_simulate) AddNewSimulate(BailoutId::None(), position);

  HGoto* instr = new(zone()) HGoto(block);

  Finish(instr, position);

}

void HBasicBlock::AddLeaveInlined(HValue* return_value,

                                  FunctionState* state,

                                  int position) {

  HBasicBlock* target = state->function_return();

  bool drop_extra = state->inlining_kind() == DROP_EXTRA_ON_RETURN;

  ASSERT(target->IsInlineReturnTarget());

  ASSERT(return_value != NULL);

  HEnvironment* env = last_environment();

  int argument_count = env->arguments_environment()->parameter_count();

  AddInstruction(new(zone()) HLeaveInlined(state->entry(), argument_count),

                 position);

  UpdateEnvironment(last_environment()->DiscardInlined(drop_extra));

  last_environment()->Push(return_value);

  AddNewSimulate(BailoutId::None(), position);

  HGoto* instr = new(zone()) HGoto(target);

  Finish(instr, position);

}

void HBasicBlock::SetInitialEnvironment(HEnvironment* env) {

  ASSERT(!HasEnvironment());

  ASSERT(first() == NULL);

  UpdateEnvironment(env);

}

void HBasicBlock::UpdateEnvironment(HEnvironment* env) {

  last_environment_ = env;

  graph()->update_maximum_environment_size(env->first_expression_index());

}

void HBasicBlock::SetJoinId(BailoutId ast_id) {

  int length = predecessors_.length();

  ASSERT(length > 0);

  for (int i = 0; i < length; i++) {

    HBasicBlock* predecessor = predecessors_[i];

    ASSERT(predecessor->end()->IsGoto());

    HSimulate* simulate = HSimulate::cast(predecessor->end()->previous());

    ASSERT(i != 0 ||

           (predecessor->last_environment()->closure().is_null() ||

            predecessor->last_environment()->closure()->shared()

              ->VerifyBailoutId(ast_id)));

    simulate->set_ast_id(ast_id);

    predecessor->last_environment()->set_ast_id(ast_id);

  }

}

bool HBasicBlock::Dominates(HBasicBlock* other) const {

  HBasicBlock* current = other->dominator();

  while (current != NULL) {

    if (current == this) return true;

    current = current->dominator();

  }

  return false;

}

int HBasicBlock::LoopNestingDepth() const {

  const HBasicBlock* current = this;

  int result  = (current->IsLoopHeader()) ? 1 : 0;

  while (current->parent_loop_header() != NULL) {

    current = current->parent_loop_header();

    result++;

  }

  return result;

}

void HBasicBlock::PostProcessLoopHeader(IterationStatement* stmt) {

  ASSERT(IsLoopHeader());

  SetJoinId(stmt->EntryId());

  if (predecessors()->length() == 1) {

    // This is a degenerated loop.

    DetachLoopInformation();

    return;

  }

  // Only the first entry into the loop is from outside the loop. All other

  // entries must be back edges.

  for (int i = 1; i < predecessors()->length(); ++i) {

    loop_information()->RegisterBackEdge(predecessors()->at(i));

  }

}

void HBasicBlock::RegisterPredecessor(HBasicBlock* pred) {

  if (HasPredecessor()) {

    // Only loop header blocks can have a predecessor added after

    // instructions have been added to the block (they have phis for all

    // values in the environment, these phis may be eliminated later).

    ASSERT(IsLoopHeader() || first_ == NULL);

    HEnvironment* incoming_env = pred->last_environment();

    if (IsLoopHeader()) {

      ASSERT(phis()->length() == incoming_env->length());

      for (int i = 0; i < phis_.length(); ++i) {

        phis_[i]->AddInput(incoming_env->values()->at(i));

      }

    } else {

      last_environment()->AddIncomingEdge(this, pred->last_environment());

    }

  } else if (!HasEnvironment() && !IsFinished()) {

    ASSERT(!IsLoopHeader());

    SetInitialEnvironment(pred->last_environment()->Copy());

  }

  predecessors_.Add(pred, zone());

}

void HBasicBlock::AddDominatedBlock(HBasicBlock* block) {

  ASSERT(!dominated_blocks_.Contains(block));

  // Keep the list of dominated blocks sorted such that if there is two

  // succeeding block in this list, the predecessor is before the successor.

  int index = 0;

  while (index < dominated_blocks_.length() &&

         dominated_blocks_[index]->block_id() < block->block_id()) {

    ++index;

  }

  dominated_blocks_.InsertAt(index, block, zone());

}

void HBasicBlock::AssignCommonDominator(HBasicBlock* other) {

  if (dominator_ == NULL) {

    dominator_ = other;

    other->AddDominatedBlock(this);

  } else if (other->dominator() != NULL) {

    HBasicBlock* first = dominator_;

    HBasicBlock* second = other;

    while (first != second) {

      if (first->block_id() > second->block_id()) {

        first = first->dominator();

      } else {

        second = second->dominator();

      }

      ASSERT(first != NULL && second != NULL);

    }

    if (dominator_ != first) {

      ASSERT(dominator_->dominated_blocks_.Contains(this));

      dominator_->dominated_blocks_.RemoveElement(this);

      dominator_ = first;

      first->AddDominatedBlock(this);

    }

  }

}

void HBasicBlock::AssignLoopSuccessorDominators() {

  // Mark blocks that dominate all subsequent reachable blocks inside their

  // loop. Exploit the fact that blocks are sorted in reverse post order. When

  // the loop is visited in increasing block id order, if the number of

  // non-loop-exiting successor edges at the dominator_candidate block doesn't

  // exceed the number of previously encountered predecessor edges, there is no

  // path from the loop header to any block with higher id that doesn't go

  // through the dominator_candidate block. In this case, the

  // dominator_candidate block is guaranteed to dominate all blocks reachable

  // from it with higher ids.

  HBasicBlock* last = loop_information()->GetLastBackEdge();

  int outstanding_successors = 1;  // one edge from the pre-header

  // Header always dominates everything.

  MarkAsLoopSuccessorDominator();

  for (int j = block_id(); j <= last->block_id(); ++j) {

    HBasicBlock* dominator_candidate = graph_->blocks()->at(j);

    for (HPredecessorIterator it(dominator_candidate); !it.Done();

         it.Advance()) {

      HBasicBlock* predecessor = it.Current();

      // Don't count back edges.

      if (predecessor->block_id() < dominator_candidate->block_id()) {

        outstanding_successors--;

      }

    }

    // If more successors than predecessors have been seen in the loop up to

    // now, it's not possible to guarantee that the current block dominates

    // all of the blocks with higher IDs. In this case, assume conservatively

    // that those paths through loop that don't go through the current block

    // contain all of the loop's dependencies. Also be careful to record

    // dominator information about the current loop that's being processed,

    // and not nested loops, which will be processed when

    // AssignLoopSuccessorDominators gets called on their header.

    ASSERT(outstanding_successors >= 0);

    HBasicBlock* parent_loop_header = dominator_candidate->parent_loop_header();

    if (outstanding_successors == 0 &&

        (parent_loop_header == this && !dominator_candidate->IsLoopHeader())) {

      dominator_candidate->MarkAsLoopSuccessorDominator();

    }

    HControlInstruction* end = dominator_candidate->end();

    for (HSuccessorIterator it(end); !it.Done(); it.Advance()) {

      HBasicBlock* successor = it.Current();

      // Only count successors that remain inside the loop and don't loop back

      // to a loop header.

      if (successor->block_id() > dominator_candidate->block_id() &&

          successor->block_id() <= last->block_id()) {

        // Backwards edges must land on loop headers.

        ASSERT(successor->block_id() > dominator_candidate->block_id() ||

               successor->IsLoopHeader());

        outstanding_successors++;

      }

    }

  }

}

int HBasicBlock::PredecessorIndexOf(HBasicBlock* predecessor) const {

  for (int i = 0; i < predecessors_.length(); ++i) {

    if (predecessors_[i] == predecessor) return i;

  }

  UNREACHABLE();

  return -1;

}

#ifdef DEBUG

void HBasicBlock::Verify() {

  // Check that every block is finished.

  ASSERT(IsFinished());

  ASSERT(block_id() >= 0);

  // Check that the incoming edges are in edge split form.

  if (predecessors_.length() > 1) {

    for (int i = 0; i < predecessors_.length(); ++i) {

      ASSERT(predecessors_[i]->end()->SecondSuccessor() == NULL);

    }

  }

}

#endif

void HLoopInformation::RegisterBackEdge(HBasicBlock* block) {

  this->back_edges_.Add(block, block->zone());

  AddBlock(block);

}

HBasicBlock* HLoopInformation::GetLastBackEdge() const {

  int max_id = -1;

  HBasicBlock* result = NULL;

  for (int i = 0; i < back_edges_.length(); ++i) {

    HBasicBlock* cur = back_edges_[i];

    if (cur->block_id() > max_id) {

      max_id = cur->block_id();

      result = cur;

    }

  }

  return result;

}

void HLoopInformation::AddBlock(HBasicBlock* block) {

  if (block == loop_header()) return;

  if (block->parent_loop_header() == loop_header()) return;

  if (block->parent_loop_header() != NULL) {

    AddBlock(block->parent_loop_header());

  } else {

    block->set_parent_loop_header(loop_header());

    blocks_.Add(block, block->zone());

    for (int i = 0; i < block->predecessors()->length(); ++i) {

      AddBlock(block->predecessors()->at(i));

    }

  }

}

#ifdef DEBUG

// Checks reachability of the blocks in this graph and stores a bit in

// the BitVector "reachable()" for every block that can be reached

// from the start block of the graph. If "dont_visit" is non-null, the given

// block is treated as if it would not be part of the graph. "visited_count()"

// returns the number of reachable blocks.

class ReachabilityAnalyzer BASE_EMBEDDED {

 public:

  ReachabilityAnalyzer(HBasicBlock* entry_block,

                       int block_count,

                       HBasicBlock* dont_visit)

      : visited_count_(0),

        stack_(16, entry_block->zone()),

        reachable_(block_count, entry_block->zone()),

        dont_visit_(dont_visit) {

    PushBlock(entry_block);

    Analyze();

  }

  int visited_count() const { return visited_count_; }

  const BitVector* reachable() const { return &reachable_; }

 private:

  void PushBlock(HBasicBlock* block) {

    if (block != NULL && block != dont_visit_ &&

        !reachable_.Contains(block->block_id())) {

      reachable_.Add(block->block_id());

      stack_.Add(block, block->zone());

      visited_count_++;

    }

  }

  void Analyze() {

    while (!stack_.is_empty()) {

      HControlInstruction* end = stack_.RemoveLast()->end();

      for (HSuccessorIterator it(end); !it.Done(); it.Advance()) {

        PushBlock(it.Current());

      }

    }

  }

  int visited_count_;

  ZoneList<HBasicBlock*> stack_;

  BitVector reachable_;

  HBasicBlock* dont_visit_;

};

void HGraph::Verify(bool do_full_verify) const {

  Heap::RelocationLock relocation_lock(isolate()->heap());

  AllowHandleDereference allow_deref;

  AllowDeferredHandleDereference allow_deferred_deref;

  for (int i = 0; i < blocks_.length(); i++) {

    HBasicBlock* block = blocks_.at(i);

    block->Verify();

    // Check that every block contains at least one node and that only the last

    // node is a control instruction.

    HInstruction* current = block->first();

    ASSERT(current != NULL && current->IsBlockEntry());

    while (current != NULL) {

      ASSERT((current->next() == NULL) == current->IsControlInstruction());

      ASSERT(current->block() == block);

      current->Verify();

      current = current->next();

    }

    // Check that successors are correctly set.

    HBasicBlock* first = block->end()->FirstSuccessor();

    HBasicBlock* second = block->end()->SecondSuccessor();

    ASSERT(second == NULL || first != NULL);

    // Check that the predecessor array is correct.

    if (first != NULL) {

      ASSERT(first->predecessors()->Contains(block));

      if (second != NULL) {

        ASSERT(second->predecessors()->Contains(block));

      }

    }

    // Check that phis have correct arguments.

    for (int j = 0; j < block->phis()->length(); j++) {

      HPhi* phi = block->phis()->at(j);

      phi->Verify();

    }

    // Check that all join blocks have predecessors that end with an

    // unconditional goto and agree on their environment node id.

    if (block->predecessors()->length() >= 2) {

      BailoutId id =

          block->predecessors()->first()->last_environment()->ast_id();

      for (int k = 0; k < block->predecessors()->length(); k++) {

        HBasicBlock* predecessor = block->predecessors()->at(k);

        ASSERT(predecessor->end()->IsGoto());

        ASSERT(predecessor->last_environment()->ast_id() == id);

      }

    }

  }

  // Check special property of first block to have no predecessors.

  ASSERT(blocks_.at(0)->predecessors()->is_empty());

  if (do_full_verify) {

    // Check that the graph is fully connected.

    ReachabilityAnalyzer analyzer(entry_block_, blocks_.length(), NULL);

    ASSERT(analyzer.visited_count() == blocks_.length());

    // Check that entry block dominator is NULL.

    ASSERT(entry_block_->dominator() == NULL);

    // Check dominators.

    for (int i = 0; i < blocks_.length(); ++i) {

      HBasicBlock* block = blocks_.at(i);

      if (block->dominator() == NULL) {

        // Only start block may have no dominator assigned to.

        ASSERT(i == 0);

      } else {

        // Assert that block is unreachable if dominator must not be visited.

        ReachabilityAnalyzer dominator_analyzer(entry_block_,

                                                blocks_.length(),

                                                block->dominator());

        ASSERT(!dominator_analyzer.reachable()->Contains(block->block_id()));

      }

    }

  }

}

#endif

HConstant* HGraph::GetConstant(SetOncePointer<HConstant>* pointer,

                               int32_t value) {

  if (!pointer->is_set()) {

    // Can't pass GetInvalidContext() to HConstant::New, because that will

    // recursively call GetConstant

    HConstant* constant = HConstant::New(zone(), NULL, value);

    constant->InsertAfter(entry_block()->first());

    pointer->set(constant);

    return constant;

  }

  return ReinsertConstantIfNecessary(pointer->get());

}

HConstant* HGraph::ReinsertConstantIfNecessary(HConstant* constant) {

  if (!constant->IsLinked()) {

    // The constant was removed from the graph. Reinsert.

    constant->ClearFlag(HValue::kIsDead);

    constant->InsertAfter(entry_block()->first());

  }

  return constant;

}

HConstant* HGraph::GetConstant0() {

  return GetConstant(&constant_0_, 0);

}

HConstant* HGraph::GetConstant1() {

  return GetConstant(&constant_1_, 1);

}

HConstant* HGraph::GetConstantMinus1() {

  return GetConstant(&constant_minus1_, -1);

}

#define DEFINE_GET_CONSTANT(Name, name, htype, boolean_value)                  \

HConstant* HGraph::GetConstant##Name() {                                       \

  if (!constant_##name##_.is_set()) {                                          \

    HConstant* constant = new(zone()) HConstant(                               \

        Unique<Object>::CreateImmovable(isolate()->factory()->name##_value()), \

        Representation::Tagged(),                                              \

        htype,                                                                 \

        false,                                                                 \

        true,                                                                  \

        false,                                                                 \

        boolean_value);                                                        \

    constant->InsertAfter(entry_block()->first());                             \

    constant_##name##_.set(constant);                                          \

  }                                                                            \

  return ReinsertConstantIfNecessary(constant_##name##_.get());                \

}

DEFINE_GET_CONSTANT(Undefined, undefined, HType::Tagged(), false)

DEFINE_GET_CONSTANT(True, true, HType::Boolean(), true)

DEFINE_GET_CONSTANT(False, false, HType::Boolean(), false)

DEFINE_GET_CONSTANT(Hole, the_hole, HType::Tagged(), false)

DEFINE_GET_CONSTANT(Null, null, HType::Tagged(), false)

#undef DEFINE_GET_CONSTANT

HConstant* HGraph::GetInvalidContext() {

  return GetConstant(&constant_invalid_context_, 0xFFFFC0C7);

}

bool HGraph::IsStandardConstant(HConstant* constant) {

  if (constant == GetConstantUndefined()) return true;

  if (constant == GetConstant0()) return true;

  if (constant == GetConstant1()) return true;

  if (constant == GetConstantMinus1()) return true;

  if (constant == GetConstantTrue()) return true;

  if (constant == GetConstantFalse()) return true;

  if (constant == GetConstantHole()) return true;

  if (constant == GetConstantNull()) return true;

  return false;

}

HGraphBuilder::IfBuilder::IfBuilder(HGraphBuilder* builder)

    : builder_(builder),

      finished_(false),

      deopt_then_(false),

      deopt_else_(false),

      did_then_(false),

      did_else_(false),

      did_and_(false),

      did_or_(false),

      captured_(false),

      needs_compare_(true),

      split_edge_merge_block_(NULL),

      merge_block_(NULL) {

  HEnvironment* env = builder->environment();

  first_true_block_ = builder->CreateBasicBlock(env->Copy());

  last_true_block_ = NULL;

  first_false_block_ = builder->CreateBasicBlock(env->Copy());

}

HGraphBuilder::IfBuilder::IfBuilder(

    HGraphBuilder* builder,

    HIfContinuation* continuation)

    : builder_(builder),

      finished_(false),

      deopt_then_(false),

      deopt_else_(false),

      did_then_(false),

      did_else_(false),

      did_and_(false),

      did_or_(false),

      captured_(false),

      needs_compare_(false),

      first_true_block_(NULL),

      last_true_block_(NULL),

      first_false_block_(NULL),

      split_edge_merge_block_(NULL),

      merge_block_(NULL) {

  continuation->Continue(&first_true_block_,

                         &first_false_block_);

}

HControlInstruction* HGraphBuilder::IfBuilder::AddCompare(

    HControlInstruction* compare) {

  if (split_edge_merge_block_ != NULL) {

    HEnvironment* env = first_false_block_->last_environment();

    HBasicBlock* split_edge =

        builder_->CreateBasicBlock(env->Copy());

    if (did_or_) {

      compare->SetSuccessorAt(0, split_edge);

      compare->SetSuccessorAt(1, first_false_block_);

    } else {

      compare->SetSuccessorAt(0, first_true_block_);

      compare->SetSuccessorAt(1, split_edge);

    }

    builder_->GotoNoSimulate(split_edge, split_edge_merge_block_);

  } else {

    compare->SetSuccessorAt(0, first_true_block_);

    compare->SetSuccessorAt(1, first_false_block_);

  }

  builder_->FinishCurrentBlock(compare);

  needs_compare_ = false;

  return compare;

}

void HGraphBuilder::IfBuilder::Or() {

  ASSERT(!needs_compare_);

  ASSERT(!did_and_);

  did_or_ = true;

  HEnvironment* env = first_false_block_->last_environment();

  if (split_edge_merge_block_ == NULL) {

    split_edge_merge_block_ =

        builder_->CreateBasicBlock(env->Copy());

    builder_->GotoNoSimulate(first_true_block_, split_edge_merge_block_);

    first_true_block_ = split_edge_merge_block_;

  }

  builder_->set_current_block(first_false_block_);

  first_false_block_ = builder_->CreateBasicBlock(env->Copy());

}

void HGraphBuilder::IfBuilder::And() {

  ASSERT(!needs_compare_);

  ASSERT(!did_or_);

  did_and_ = true;

  HEnvironment* env = first_false_block_->last_environment();

  if (split_edge_merge_block_ == NULL) {

    split_edge_merge_block_ = builder_->CreateBasicBlock(env->Copy());

    builder_->GotoNoSimulate(first_false_block_, split_edge_merge_block_);

    first_false_block_ = split_edge_merge_block_;

  }

  builder_->set_current_block(first_true_block_);

  first_true_block_ = builder_->CreateBasicBlock(env->Copy());

}

void HGraphBuilder::IfBuilder::CaptureContinuation(

    HIfContinuation* continuation) {

  ASSERT(!finished_);

  ASSERT(!captured_);

  HBasicBlock* true_block = last_true_block_ == NULL

      ? first_true_block_

      : last_true_block_;

  HBasicBlock* false_block = did_else_ && (first_false_block_ != NULL)

      ? builder_->current_block()

      : first_false_block_;

  continuation->Capture(true_block, false_block);

  captured_ = true;

  End();

}

void HGraphBuilder::IfBuilder::JoinContinuation(HIfContinuation* continuation) {

  ASSERT(!finished_);

  ASSERT(!captured_);

  HBasicBlock* true_block = last_true_block_ == NULL

      ? first_true_block_

      : last_true_block_;

  HBasicBlock* false_block = did_else_ && (first_false_block_ != NULL)

      ? builder_->current_block()

      : first_false_block_;

  if (true_block != NULL && !true_block->IsFinished()) {

    ASSERT(continuation->IsTrueReachable());

    builder_->GotoNoSimulate(true_block, continuation->true_branch());

  }

  if (false_block != NULL && !false_block->IsFinished()) {

    ASSERT(continuation->IsFalseReachable());

    builder_->GotoNoSimulate(false_block, continuation->false_branch());

  }

  captured_ = true;

  End();

}

void HGraphBuilder::IfBuilder::Then() {

  ASSERT(!captured_);

  ASSERT(!finished_);

  did_then_ = true;

  if (needs_compare_) {

    // Handle if's without any expressions, they jump directly to the "else"

    // branch. However, we must pretend that the "then" branch is reachable,

    // so that the graph builder visits it and sees any live range extending

    // constructs within it.

    HConstant* constant_false = builder_->graph()->GetConstantFalse();

    ToBooleanStub::Types boolean_type = ToBooleanStub::Types();

    boolean_type.Add(ToBooleanStub::BOOLEAN);

    HBranch* branch = builder()->New<HBranch>(

        constant_false, boolean_type, first_true_block_, first_false_block_);

    builder_->FinishCurrentBlock(branch);

  }

  builder_->set_current_block(first_true_block_);

}

void HGraphBuilder::IfBuilder::Else() {

  ASSERT(did_then_);

  ASSERT(!captured_);

  ASSERT(!finished_);

  last_true_block_ = builder_->current_block();

  builder_->set_current_block(first_false_block_);

  did_else_ = true;

}

void HGraphBuilder::IfBuilder::Deopt(const char* reason) {

  ASSERT(did_then_);

  if (did_else_) {

    deopt_else_ = true;

  } else {

    deopt_then_ = true;

  }

  builder_->Add<HDeoptimize>(reason, Deoptimizer::EAGER);

}

void HGraphBuilder::IfBuilder::Return(HValue* value) {

  HValue* parameter_count = builder_->graph()->GetConstantMinus1();

  builder_->FinishExitCurrentBlock(

      builder_->New<HReturn>(value, parameter_count));

  if (did_else_) {

    first_false_block_ = NULL;

  } else {

    first_true_block_ = NULL;

  }

}

void HGraphBuilder::IfBuilder::End() {

  if (!captured_) {

    ASSERT(did_then_);

    if (!did_else_) {

      last_true_block_ = builder_->current_block();

    }

    if (last_true_block_ == NULL || last_true_block_->IsFinished()) {

      ASSERT(did_else_);

      // Return on true. Nothing to do, just continue the false block.

    } else if (first_false_block_ == NULL ||

               (did_else_ && builder_->current_block()->IsFinished())) {

      // Deopt on false. Nothing to do except switching to the true block.

      builder_->set_current_block(last_true_block_);

    } else {

      merge_block_ = builder_->graph()->CreateBasicBlock();

      ASSERT(!finished_);

      if (!did_else_) Else();

      ASSERT(!last_true_block_->IsFinished());

      HBasicBlock* last_false_block = builder_->current_block();

      ASSERT(!last_false_block->IsFinished());

      if (deopt_then_) {

        builder_->GotoNoSimulate(last_false_block, merge_block_);

        builder_->PadEnvironmentForContinuation(last_true_block_,

                                                merge_block_);

        builder_->GotoNoSimulate(last_true_block_, merge_block_);

      } else {

        builder_->GotoNoSimulate(last_true_block_, merge_block_);

        if (deopt_else_) {

          builder_->PadEnvironmentForContinuation(last_false_block,

                                                  merge_block_);

        }

        builder_->GotoNoSimulate(last_false_block, merge_block_);

      }

      builder_->set_current_block(merge_block_);

    }

  }

  finished_ = true;

}

HGraphBuilder::LoopBuilder::LoopBuilder(HGraphBuilder* builder,

                                        HValue* context,

                                        LoopBuilder::Direction direction)

    : builder_(builder),

      context_(context),

      direction_(direction),

      finished_(false) {

  header_block_ = builder->CreateLoopHeaderBlock();

  body_block_ = NULL;

  exit_block_ = NULL;

  exit_trampoline_block_ = NULL;

  increment_amount_ = builder_->graph()->GetConstant1();

}

HGraphBuilder::LoopBuilder::LoopBuilder(HGraphBuilder* builder,

                                        HValue* context,

                                        LoopBuilder::Direction direction,

                                        HValue* increment_amount)

    : builder_(builder),

      context_(context),

      direction_(direction),

      finished_(false) {

  header_block_ = builder->CreateLoopHeaderBlock();

  body_block_ = NULL;

  exit_block_ = NULL;

  exit_trampoline_block_ = NULL;

  increment_amount_ = increment_amount;

}

HValue* HGraphBuilder::LoopBuilder::BeginBody(

    HValue* initial,

    HValue* terminating,

    Token::Value token) {

  HEnvironment* env = builder_->environment();

  phi_ = header_block_->AddNewPhi(env->values()->length());

  phi_->AddInput(initial);

  env->Push(initial);

  builder_->GotoNoSimulate(header_block_);

  HEnvironment* body_env = env->Copy();

  HEnvironment* exit_env = env->Copy();

  // Remove the phi from the expression stack

  body_env->Pop();

  exit_env->Pop();

  body_block_ = builder_->CreateBasicBlock(body_env);

  exit_block_ = builder_->CreateBasicBlock(exit_env);

  builder_->set_current_block(header_block_);

  env->Pop();

  builder_->FinishCurrentBlock(builder_->New<HCompareNumericAndBranch>(

          phi_, terminating, token, body_block_, exit_block_));

  builder_->set_current_block(body_block_);

  if (direction_ == kPreIncrement || direction_ == kPreDecrement) {

    HValue* one = builder_->graph()->GetConstant1();

    if (direction_ == kPreIncrement) {

      increment_ = HAdd::New(zone(), context_, phi_, one);

    } else {

      increment_ = HSub::New(zone(), context_, phi_, one);

    }

    increment_->ClearFlag(HValue::kCanOverflow);

    builder_->AddInstruction(increment_);

    return increment_;

  } else {

    return phi_;

  }

}

void HGraphBuilder::LoopBuilder::Break() {

  if (exit_trampoline_block_ == NULL) {

    // Its the first time we saw a break.

    HEnvironment* env = exit_block_->last_environment()->Copy();

    exit_trampoline_block_ = builder_->CreateBasicBlock(env);

    builder_->GotoNoSimulate(exit_block_, exit_trampoline_block_);

  }

  builder_->GotoNoSimulate(exit_trampoline_block_);

}

void HGraphBuilder::LoopBuilder::EndBody() {

  ASSERT(!finished_);

  if (direction_ == kPostIncrement || direction_ == kPostDecrement) {

    if (direction_ == kPostIncrement) {

      increment_ = HAdd::New(zone(), context_, phi_, increment_amount_);

    } else {

      increment_ = HSub::New(zone(), context_, phi_, increment_amount_);

    }

    increment_->ClearFlag(HValue::kCanOverflow);

    builder_->AddInstruction(increment_);

  }

  // Push the new increment value on the expression stack to merge into the phi.

  builder_->environment()->Push(increment_);

  HBasicBlock* last_block = builder_->current_block();

  builder_->GotoNoSimulate(last_block, header_block_);

  header_block_->loop_information()->RegisterBackEdge(last_block);

  if (exit_trampoline_block_ != NULL) {

    builder_->set_current_block(exit_trampoline_block_);

  } else {

    builder_->set_current_block(exit_block_);

  }

  finished_ = true;

}

HGraph* HGraphBuilder::CreateGraph() {

  graph_ = new(zone()) HGraph(info_);

  if (FLAG_hydrogen_stats) isolate()->GetHStatistics()->Initialize(info_);

  CompilationPhase phase("H_Block building", info_);

  set_current_block(graph()->entry_block());

  if (!BuildGraph()) return NULL;

  graph()->FinalizeUniqueness();

  return graph_;

}

HInstruction* HGraphBuilder::AddInstruction(HInstruction* instr) {

  ASSERT(current_block() != NULL);

  ASSERT(!FLAG_emit_opt_code_positions ||

         position_ != RelocInfo::kNoPosition || !info_->IsOptimizing());

  current_block()->AddInstruction(instr, position_);

  if (graph()->IsInsideNoSideEffectsScope()) {

    instr->SetFlag(HValue::kHasNoObservableSideEffects);

  }

  return instr;

}

void HGraphBuilder::FinishCurrentBlock(HControlInstruction* last) {

  ASSERT(!FLAG_emit_opt_code_positions || !info_->IsOptimizing() ||

         position_ != RelocInfo::kNoPosition);

  current_block()->Finish(last, position_);

  if (last->IsReturn() || last->IsAbnormalExit()) {

    set_current_block(NULL);

  }

}

void HGraphBuilder::FinishExitCurrentBlock(HControlInstruction* instruction) {

  ASSERT(!FLAG_emit_opt_code_positions || !info_->IsOptimizing() ||

         position_ != RelocInfo::kNoPosition);

  current_block()->FinishExit(instruction, position_);

  if (instruction->IsReturn() || instruction->IsAbnormalExit()) {

    set_current_block(NULL);

  }

}

void HGraphBuilder::AddIncrementCounter(StatsCounter* counter) {

  if (FLAG_native_code_counters && counter->Enabled()) {

    HValue* reference = Add<HConstant>(ExternalReference(counter));

    HValue* old_value = Add<HLoadNamedField>(reference,

                                             HObjectAccess::ForCounter());

    HValue* new_value = Add<HAdd>(old_value, graph()->GetConstant1());

    new_value->ClearFlag(HValue::kCanOverflow);  // Ignore counter overflow

    Add<HStoreNamedField>(reference, HObjectAccess::ForCounter(),

                          new_value);

  }

}

void HGraphBuilder::AddSimulate(BailoutId id,

                                RemovableSimulate removable) {

  ASSERT(current_block() != NULL);

  ASSERT(!graph()->IsInsideNoSideEffectsScope());

  current_block()->AddNewSimulate(id, removable);

}

HBasicBlock* HGraphBuilder::CreateBasicBlock(HEnvironment* env) {

  HBasicBlock* b = graph()->CreateBasicBlock();

  b->SetInitialEnvironment(env);

  return b;

}

HBasicBlock* HGraphBuilder::CreateLoopHeaderBlock() {

  HBasicBlock* header = graph()->CreateBasicBlock();

  HEnvironment* entry_env = environment()->CopyAsLoopHeader(header);

  header->SetInitialEnvironment(entry_env);

  header->AttachLoopInformation();

  return header;

}

HValue* HGraphBuilder::BuildCheckHeapObject(HValue* obj) {

  if (obj->type().IsHeapObject()) return obj;

  return Add<HCheckHeapObject>(obj);

}

void HGraphBuilder::FinishExitWithHardDeoptimization(

    const char* reason, HBasicBlock* continuation) {

  PadEnvironmentForContinuation(current_block(), continuation);

  Add<HDeoptimize>(reason, Deoptimizer::EAGER);

  if (graph()->IsInsideNoSideEffectsScope()) {

    GotoNoSimulate(continuation);

  } else {

    Goto(continuation);

  }

}

void HGraphBuilder::PadEnvironmentForContinuation(

    HBasicBlock* from,

    HBasicBlock* continuation) {

  if (continuation->last_environment() != NULL) {

    // When merging from a deopt block to a continuation, resolve differences in

    // environment by pushing constant 0 and popping extra values so that the

    // environments match during the join. Push 0 since it has the most specific

    // representation, and will not influence representation inference of the

    // phi.

    int continuation_env_length = continuation->last_environment()->length();

    while (continuation_env_length != from->last_environment()->length()) {

      if (continuation_env_length > from->last_environment()->length()) {

        from->last_environment()->Push(graph()->GetConstant0());

      } else {

        from->last_environment()->Pop();

      }

    }

  } else {

    ASSERT(continuation->predecessors()->length() == 0);

  }

}

HValue* HGraphBuilder::BuildCheckMap(HValue* obj, Handle<Map> map) {

  return Add<HCheckMaps>(obj, map, top_info());

}

HValue* HGraphBuilder::BuildWrapReceiver(HValue* object, HValue* function) {

  if (object->type().IsJSObject()) return object;

  return Add<HWrapReceiver>(object, function);

}

HValue* HGraphBuilder::BuildCheckForCapacityGrow(HValue* object,

                                                 HValue* elements,

                                                 ElementsKind kind,

                                                 HValue* length,

                                                 HValue* key,

                                                 bool is_js_array) {

  IfBuilder length_checker(this);

  Token::Value token = IsHoleyElementsKind(kind) ? Token::GTE : Token::EQ;

  length_checker.If<HCompareNumericAndBranch>(key, length, token);

  length_checker.Then();

  HValue* current_capacity = AddLoadFixedArrayLength(elements);

  IfBuilder capacity_checker(this);

  capacity_checker.If<HCompareNumericAndBranch>(key, current_capacity,

                                                Token::GTE);

  capacity_checker.Then();

  HValue* max_gap = Add<HConstant>(static_cast<int32_t>(JSObject::kMaxGap));

  HValue* max_capacity = Add<HAdd>(current_capacity, max_gap);

  IfBuilder key_checker(this);

  key_checker.If<HCompareNumericAndBranch>(key, max_capacity, Token::LT);

  key_checker.Then();

  key_checker.ElseDeopt("Key out of capacity range");

  key_checker.End();

  HValue* new_capacity = BuildNewElementsCapacity(key);

  HValue* new_elements = BuildGrowElementsCapacity(object, elements,

                                                   kind, kind, length,

                                                   new_capacity);

  environment()->Push(new_elements);

  capacity_checker.Else();

  environment()->Push(elements);

  capacity_checker.End();

  if (is_js_array) {

    HValue* new_length = AddUncasted<HAdd>(key, graph_->GetConstant1());

    new_length->ClearFlag(HValue::kCanOverflow);

    Add<HStoreNamedField>(object, HObjectAccess::ForArrayLength(kind),

                          new_length);

  }

  length_checker.Else();

  Add<HBoundsCheck>(key, length);

  environment()->Push(elements);

  length_checker.End();

  return environment()->Pop();

}

HValue* HGraphBuilder::BuildCopyElementsOnWrite(HValue* object,

                                                HValue* elements,

                                                ElementsKind kind,

                                                HValue* length) {

  Factory* factory = isolate()->factory();

  IfBuilder cow_checker(this);

  cow_checker.If<HCompareMap>(elements, factory->fixed_cow_array_map());

  cow_checker.Then();

  HValue* capacity = AddLoadFixedArrayLength(elements);

  HValue* new_elements = BuildGrowElementsCapacity(object, elements, kind,

                                                   kind, length, capacity);

  environment()->Push(new_elements);

  cow_checker.Else();

  environment()->Push(elements);

  cow_checker.End();

  return environment()->Pop();

}

void HGraphBuilder::BuildTransitionElementsKind(HValue* object,

                                                HValue* map,

                                                ElementsKind from_kind,

                                                ElementsKind to_kind,

                                                bool is_jsarray) {

  ASSERT(!IsFastHoleyElementsKind(from_kind) ||

         IsFastHoleyElementsKind(to_kind));

  if (AllocationSite::GetMode(from_kind, to_kind) == TRACK_ALLOCATION_SITE) {

    Add<HTrapAllocationMemento>(object);

  }

  if (!IsSimpleMapChangeTransition(from_kind, to_kind)) {

    HInstruction* elements = AddLoadElements(object);

    HInstruction* empty_fixed_array = Add<HConstant>(

        isolate()->factory()->empty_fixed_array());

    IfBuilder if_builder(this);

    if_builder.IfNot<HCompareObjectEqAndBranch>(elements, empty_fixed_array);

    if_builder.Then();

    HInstruction* elements_length = AddLoadFixedArrayLength(elements);

    HInstruction* array_length = is_jsarray

        ? Add<HLoadNamedField>(object, HObjectAccess::ForArrayLength(from_kind))

        : elements_length;

    BuildGrowElementsCapacity(object, elements, from_kind, to_kind,

                              array_length, elements_length);

    if_builder.End();

  }

  Add<HStoreNamedField>(object, HObjectAccess::ForMap(), map);

}

HValue* HGraphBuilder::BuildNumberToString(HValue* object,

                                           Handle<Type> type) {

  NoObservableSideEffectsScope scope(this);

  // Create a joinable continuation.

  HIfContinuation found(graph()->CreateBasicBlock(),

                        graph()->CreateBasicBlock());

  // Load the number string cache.

  HValue* number_string_cache =

      Add<HLoadRoot>(Heap::kNumberStringCacheRootIndex);

  // Make the hash mask from the length of the number string cache. It

  // contains two elements (number and string) for each cache entry.

  HValue* mask = AddLoadFixedArrayLength(number_string_cache);

  mask->set_type(HType::Smi());

  mask = Add<HSar>(mask, graph()->GetConstant1());

  mask = Add<HSub>(mask, graph()->GetConstant1());

  // Check whether object is a smi.

  IfBuilder if_objectissmi(this);

  if_objectissmi.If<HIsSmiAndBranch>(object);

  if_objectissmi.Then();

  {

    // Compute hash for smi similar to smi_get_hash().

    HValue* hash = Add<HBitwise>(Token::BIT_AND, object, mask);

    // Load the key.

    HValue* key_index = Add<HShl>(hash, graph()->GetConstant1());

    HValue* key = Add<HLoadKeyed>(number_string_cache, key_index,

                                  static_cast<HValue*>(NULL),

                                  FAST_ELEMENTS, ALLOW_RETURN_HOLE);

    // Check if object == key.

    IfBuilder if_objectiskey(this);

    if_objectiskey.If<HCompareObjectEqAndBranch>(object, key);

    if_objectiskey.Then();

    {

      // Make the key_index available.

      Push(key_index);

    }

    if_objectiskey.JoinContinuation(&found);

  }

  if_objectissmi.Else();

  {

    if (type->Is(Type::Smi())) {

      if_objectissmi.Deopt("Excepted smi");

    } else {

      // Check if the object is a heap number.

      IfBuilder if_objectisnumber(this);

      if_objectisnumber.If<HCompareMap>(

          object, isolate()->factory()->heap_number_map());

      if_objectisnumber.Then();

      {

        // Compute hash for heap number similar to double_get_hash().

        HValue* low = Add<HLoadNamedField>(

            object, HObjectAccess::ForHeapNumberValueLowestBits());

        HValue* high = Add<HLoadNamedField>(

            object, HObjectAccess::ForHeapNumberValueHighestBits());

        HValue* hash = Add<HBitwise>(Token::BIT_XOR, low, high);

        hash = Add<HBitwise>(Token::BIT_AND, hash, mask);

        // Load the key.

        HValue* key_index = Add<HShl>(hash, graph()->GetConstant1());

        HValue* key = Add<HLoadKeyed>(number_string_cache, key_index,

                                      static_cast<HValue*>(NULL),

                                      FAST_ELEMENTS, ALLOW_RETURN_HOLE);

        // Check if key is a heap number (the number string cache contains only

        // SMIs and heap number, so it is sufficient to do a SMI check here).

        IfBuilder if_keyisnotsmi(this);

        if_keyisnotsmi.IfNot<HIsSmiAndBranch>(key);

        if_keyisnotsmi.Then();

        {

          // Check if values of key and object match.

          IfBuilder if_keyeqobject(this);

          if_keyeqobject.If<HCompareNumericAndBranch>(

              Add<HLoadNamedField>(key, HObjectAccess::ForHeapNumberValue()),

              Add<HLoadNamedField>(object, HObjectAccess::ForHeapNumberValue()),

              Token::EQ);

          if_keyeqobject.Then();

          {

            // Make the key_index available.

            Push(key_index);

          }

          if_keyeqobject.JoinContinuation(&found);

        }

        if_keyisnotsmi.JoinContinuation(&found);

      }

      if_objectisnumber.Else();

      {

        if (type->Is(Type::Number())) {

          if_objectisnumber.Deopt("Expected heap number");

        }

      }

      if_objectisnumber.JoinContinuation(&found);

    }

  }

  if_objectissmi.JoinContinuation(&found);

  // Check for cache hit.

  IfBuilder if_found(this, &found);

  if_found.Then();

  {

    // Count number to string operation in native code.

    AddIncrementCounter(isolate()->counters()->number_to_string_native());

    // Load the value in case of cache hit.

    HValue* key_index = Pop();

    HValue* value_index = Add<HAdd>(key_index, graph()->GetConstant1());