Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP
Fetching contributors…

Cannot retrieve contributors at this time

9885 lines (8466 sloc) 349.154 kb
// 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 "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) {
ASSERT(!IsStartBlock() || !IsFinished());
ASSERT(!instr->IsLinked());
ASSERT(!IsFinished());
if (first_ == NULL) {
ASSERT(last_environment() != NULL);
ASSERT(!last_environment()->ast_id().IsNone());
HBlockEntry* entry = new(zone()) HBlockEntry();
entry->InitializeAsFirst(this);
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) {
ASSERT(!IsFinished());
AddInstruction(end);
end_ = end;
for (HSuccessorIterator it(end); !it.Done(); it.Advance()) {
it.Current()->RegisterPredecessor(this);
}
}
void HBasicBlock::Goto(HBasicBlock* block,
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));
UpdateEnvironment(last_environment()->DiscardInlined(drop_extra));
}
if (add_simulate) AddNewSimulate(BailoutId::None());
HGoto* instr = new(zone()) HGoto(block);
Finish(instr);
}
void HBasicBlock::AddLeaveInlined(HValue* return_value,
FunctionState* state) {
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));
UpdateEnvironment(last_environment()->DiscardInlined(drop_extra));
last_environment()->Push(return_value);
AddNewSimulate(BailoutId::None());
HGoto* instr = new(zone()) HGoto(target);
Finish(instr);
}
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(GetConstantUndefined());
pointer->set(constant);
}
return pointer->get();
}
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(GetConstantUndefined()); \
constant_##name##_.set(constant); \
} \
return constant_##name##_.get(); \
}
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, int position)
: builder_(builder),
position_(position),
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),
position_(RelocInfo::kNoPosition),
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_,
&position_);
}
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);
}
split_edge->GotoNoSimulate(split_edge_merge_block_);
} else {
compare->SetSuccessorAt(0, first_true_block_);
compare->SetSuccessorAt(1, first_false_block_);
}
builder_->current_block()->Finish(compare);
needs_compare_ = false;
return compare;
}
void HGraphBuilder::IfBuilder::Or() {
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());
first_true_block_->GotoNoSimulate(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(!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());
first_false_block_->GotoNoSimulate(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, position_);
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());
true_block->GotoNoSimulate(continuation->true_branch());
}
if (false_block != NULL && !false_block->IsFinished()) {
ASSERT(continuation->IsFalseReachable());
false_block->GotoNoSimulate(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_->current_block()->Finish(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) {
HBasicBlock* block = builder_->current_block();
HValue* parameter_count = builder_->graph()->GetConstantMinus1();
block->FinishExit(builder_->New<HReturn>(value, parameter_count));
builder_->set_current_block(NULL);
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_) {
last_false_block->GotoNoSimulate(merge_block_);
builder_->PadEnvironmentForContinuation(last_true_block_,
merge_block_);
last_true_block_->GotoNoSimulate(merge_block_);
} else {
last_true_block_->GotoNoSimulate(merge_block_);
if (deopt_else_) {
builder_->PadEnvironmentForContinuation(last_false_block,
merge_block_);
}
last_false_block->GotoNoSimulate(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_->current_block()->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_->current_block()->Finish(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);
exit_block_->GotoNoSimulate(exit_trampoline_block_);
}
builder_->current_block()->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();
last_block->GotoNoSimulate(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);
current_block()->AddInstruction(instr);
if (graph()->IsInsideNoSideEffectsScope()) {
instr->SetFlag(HValue::kHasNoObservableSideEffects);
}
return instr;
}
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()) {
current_block()->GotoNoSimulate(continuation);
} else {
current_block()->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) {
Zone* zone = this->zone();
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* context = environment()->context();
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 = AddInstruction(
HAdd::New(zone, context, 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::BuildLookupNumberStringCache(
HValue* object,
HIfContinuation* continuation) {
// 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 maks 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 = AddFastElementAccess(number_string_cache, key_index,
NULL, NULL, FAST_ELEMENTS, false,
ALLOW_RETURN_HOLE, STANDARD_STORE);
// Check if object == key.
IfBuilder if_objectiskey(this);
if_objectiskey.If<HCompareObjectEqAndBranch>(key, object);
if_objectiskey.Then();
{
// Make the key_index available.
Push(key_index);
}
if_objectiskey.JoinContinuation(&found);
}
if_objectissmi.Else();
{
// Check if 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 = AddFastElementAccess(number_string_cache, key_index,
NULL, NULL, FAST_ELEMENTS, false,
ALLOW_RETURN_HOLE, STANDARD_STORE);
// Check if key is a heap number.
IfBuilder if_keyisnumber(this);
if_keyisnumber.IfNot<HIsSmiAndBranch>(key);
if_keyisnumber.AndIf<HCompareMap>(
key, isolate()->factory()->heap_number_map());
if_keyisnumber.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_keyisnumber.JoinContinuation(&found);
}
if_objectisnumber.JoinContinuation(&found);
}
if_objectissmi.End();
// Check for cache hit.
IfBuilder if_found(this, &found);
if_found.Then();
// Load the value in case of cache hit.
HValue* key_index = Pop();
HValue* value_index = Add<HAdd>(key_index, graph()->GetConstant1());
HValue* value = AddFastElementAccess(number_string_cache, value_index,
NULL, NULL, FAST_ELEMENTS, false,
ALLOW_RETURN_HOLE, STANDARD_STORE);
AddIncrementCounter(isolate()->counters()->number_to_string_native());
if_found.CaptureContinuation(continuation);
// The value is only available in true branch of continuation.
return value;
}
HValue* HGraphBuilder::BuildNumberToString(HValue* number) {
NoObservableSideEffectsScope scope(this);
// Lookup the number in the number string cache.
HIfContinuation continuation;
HValue* value = BuildLookupNumberStringCache(number, &continuation);
IfBuilder if_found(this, &continuation);
if_found.Then();
// Cache hit.
Push(value);
if_found.Else();
// Cache miss, fallback to runtime.
Add<HPushArgument>(number);
Push(Add<HCallRuntime>(
isolate()->factory()->empty_string(),
Runtime::FunctionForId(Runtime::kNumberToStringSkipCache),
1));
if_found.End();
return Pop();
}
HInstruction* HGraphBuilder::BuildUncheckedMonomorphicElementAccess(
HValue* checked_object,
HValue* key,
HValue* val,
bool is_js_array,
ElementsKind elements_kind,
bool is_store,
LoadKeyedHoleMode load_mode,
KeyedAccessStoreMode store_mode) {
ASSERT(!IsExternalArrayElementsKind(elements_kind) || !is_js_array);
// No GVNFlag is necessary for ElementsKind if there is an explicit dependency
// on a HElementsTransition instruction. The flag can also be removed if the
// map to check has FAST_HOLEY_ELEMENTS, since there can be no further
// ElementsKind transitions. Finally, the dependency can be removed for stores
// for FAST_ELEMENTS, since a transition to HOLEY elements won't change the
// generated store code.
if ((elements_kind == FAST_HOLEY_ELEMENTS) ||
(elements_kind == FAST_ELEMENTS && is_store)) {
checked_object->ClearGVNFlag(kDependsOnElementsKind);
}
bool fast_smi_only_elements = IsFastSmiElementsKind(elements_kind);
bool fast_elements = IsFastObjectElementsKind(elements_kind);
HValue* elements = AddLoadElements(checked_object);
if (is_store && (fast_elements || fast_smi_only_elements) &&
store_mode != STORE_NO_TRANSITION_HANDLE_COW) {
HCheckMaps* check_cow_map = Add<HCheckMaps>(
elements, isolate()->factory()->fixed_array_map(), top_info());
check_cow_map->ClearGVNFlag(kDependsOnElementsKind);
}
HInstruction* length = NULL;
if (is_js_array) {
length = Add<HLoadNamedField>(
checked_object, HObjectAccess::ForArrayLength(elements_kind));
} else {
length = AddLoadFixedArrayLength(elements);
}
length->set_type(HType::Smi());
HValue* checked_key = NULL;
if (IsExternalArrayElementsKind(elements_kind)) {
if (store_mode == STORE_NO_TRANSITION_IGNORE_OUT_OF_BOUNDS) {
NoObservableSideEffectsScope no_effects(this);
HLoadExternalArrayPointer* external_elements =
Add<HLoadExternalArrayPointer>(elements);
IfBuilder length_checker(this);
length_checker.If<HCompareNumericAndBranch>(key, length, Token::LT);
length_checker.Then();
IfBuilder negative_checker(this);
HValue* bounds_check = negative_checker.If<HCompareNumericAndBranch>(
key, graph()->GetConstant0(), Token::GTE);
negative_checker.Then();
HInstruction* result = AddExternalArrayElementAccess(
external_elements, key, val, bounds_check, elements_kind, is_store);
negative_checker.ElseDeopt("Negative key encountered");
length_checker.End();
return result;
} else {
ASSERT(store_mode == STANDARD_STORE);
checked_key = Add<HBoundsCheck>(key, length);
HLoadExternalArrayPointer* external_elements =
Add<HLoadExternalArrayPointer>(elements);
return AddExternalArrayElementAccess(
external_elements, checked_key, val,
checked_object, elements_kind, is_store);
}
}
ASSERT(fast_smi_only_elements ||
fast_elements ||
IsFastDoubleElementsKind(elements_kind));
// In case val is stored into a fast smi array, assure that the value is a smi
// before manipulating the backing store. Otherwise the actual store may
// deopt, leaving the backing store in an invalid state.
if (is_store && IsFastSmiElementsKind(elements_kind) &&
!val->type().IsSmi()) {
val = Add<HForceRepresentation>(val, Representation::Smi());
}
if (IsGrowStoreMode(store_mode)) {
NoObservableSideEffectsScope no_effects(this);
elements = BuildCheckForCapacityGrow(checked_object, elements,
elements_kind, length, key,
is_js_array);
checked_key = key;
} else {
checked_key = Add<HBoundsCheck>(key, length);
if (is_store && (fast_elements || fast_smi_only_elements)) {
if (store_mode == STORE_NO_TRANSITION_HANDLE_COW) {
NoObservableSideEffectsScope no_effects(this);
elements = BuildCopyElementsOnWrite(checked_object, elements,
elements_kind, length);
} else {
HCheckMaps* check_cow_map = Add<HCheckMaps>(
elements, isolate()->factory()->fixed_array_map(),
top_info());
check_cow_map->ClearGVNFlag(kDependsOnElementsKind);
}
}
}
return AddFastElementAccess(elements, checked_key, val, checked_object,
elements_kind, is_store, load_mode, store_mode);
}
HValue* HGraphBuilder::BuildAllocateElements(ElementsKind kind,
HValue* capacity) {
int elements_size;
InstanceType instance_type;
if (IsFastDoubleElementsKind(kind)) {
elements_size = kDoubleSize;
instance_type = FIXED_DOUBLE_ARRAY_TYPE;
} else {
elements_size = kPointerSize;
instance_type = FIXED_ARRAY_TYPE;
}
HConstant* elements_size_value = Add<HConstant>(elements_size);
HValue* mul = Add<HMul>(capacity, elements_size_value);
mul->ClearFlag(HValue::kCanOverflow);
HConstant* header_size = Add<HConstant>(FixedArray::kHeaderSize);
HValue* total_size = Add<HAdd>(mul, header_size);
total_size->ClearFlag(HValue::kCanOverflow);
return Add<HAllocate>(total_size, HType::JSArray(),
isolate()->heap()->GetPretenureMode(), instance_type);
}
void HGraphBuilder::BuildInitializeElementsHeader(HValue* elements,
ElementsKind kind,
HValue* capacity) {
Factory* factory = isolate()->factory();
Handle<Map> map = IsFastDoubleElementsKind(kind)
? factory->fixed_double_array_map()
: factory->fixed_array_map();
AddStoreMapConstant(elements, map);
Add<HStoreNamedField>(elements, HObjectAccess::ForFixedArrayLength(),
capacity);
}
HValue* HGraphBuilder::BuildAllocateElementsAndInitializeElementsHeader(
ElementsKind kind,
HValue* capacity) {
// The HForceRepresentation is to prevent possible deopt on int-smi
// conversion after allocation but before the new object fields are set.
capacity = Add<HForceRepresentation>(capacity, Representation::Smi());
HValue* new_elements = BuildAllocateElements(kind, capacity);
BuildInitializeElementsHeader(new_elements, kind, capacity);
return new_elements;
}
HInnerAllocatedObject* HGraphBuilder::BuildJSArrayHeader(HValue* array,
HValue* array_map,
AllocationSiteMode mode,
ElementsKind elements_kind,
HValue* allocation_site_payload,
HValue* length_field) {
Add<HStoreNamedField>(array, HObjectAccess::ForMap(), array_map);
HConstant* empty_fixed_array =
Add<HConstant>(isolate()->factory()->empty_fixed_array());
HObjectAccess access = HObjectAccess::ForPropertiesPointer();
Add<HStoreNamedField>(array, access, empty_fixed_array);
Add<HStoreNamedField>(array, HObjectAccess::ForArrayLength(elements_kind),
length_field);
if (mode == TRACK_ALLOCATION_SITE) {
BuildCreateAllocationMemento(array,
JSArray::kSize,
allocation_site_payload);
}
int elements_location = JSArray::kSize;
if (mode == TRACK_ALLOCATION_SITE) {
elements_location += AllocationMemento::kSize;
}
HValue* elements = Add<HInnerAllocatedObject>(array, elements_location);
Add<HStoreNamedField>(array, HObjectAccess::ForElementsPointer(), elements);
return static_cast<HInnerAllocatedObject*>(elements);
}
HInstruction* HGraphBuilder::AddExternalArrayElementAccess(
HValue* external_elements,
HValue* checked_key,
HValue* val,
HValue* dependency,
ElementsKind elements_kind,
bool is_store) {
if (is_store) {
ASSERT(val != NULL);
switch (elements_kind) {
case EXTERNAL_PIXEL_ELEMENTS: {
val = Add<HClampToUint8>(val);
break;
}
case EXTERNAL_BYTE_ELEMENTS:
case EXTERNAL_UNSIGNED_BYTE_ELEMENTS:
case EXTERNAL_SHORT_ELEMENTS:
case EXTERNAL_UNSIGNED_SHORT_ELEMENTS:
case EXTERNAL_INT_ELEMENTS:
case EXTERNAL_UNSIGNED_INT_ELEMENTS: {
break;
}
case EXTERNAL_FLOAT_ELEMENTS:
case EXTERNAL_DOUBLE_ELEMENTS:
break;
case FAST_SMI_ELEMENTS:
case FAST_ELEMENTS:
case FAST_DOUBLE_ELEMENTS:
case FAST_HOLEY_SMI_ELEMENTS:
case FAST_HOLEY_ELEMENTS:
case FAST_HOLEY_DOUBLE_ELEMENTS:
case DICTIONARY_ELEMENTS:
case NON_STRICT_ARGUMENTS_ELEMENTS:
UNREACHABLE();
break;
}
return Add<HStoreKeyed>(external_elements, checked_key, val, elements_kind);
} else {
ASSERT(val == NULL);
HLoadKeyed* load = Add<HLoadKeyed>(external_elements,
checked_key,
dependency,
elements_kind);
if (FLAG_opt_safe_uint32_operations &&
elements_kind == EXTERNAL_UNSIGNED_INT_ELEMENTS) {
graph()->RecordUint32Instruction(load);
}
return load;
}
}
HInstruction* HGraphBuilder::AddFastElementAccess(
HValue* elements,
HValue* checked_key,
HValue* val,
HValue* load_dependency,
ElementsKind elements_kind,
bool is_store,
LoadKeyedHoleMode load_mode,
KeyedAccessStoreMode store_mode) {
if (is_store) {
ASSERT(val != NULL);
switch (elements_kind) {
case FAST_SMI_ELEMENTS:
case FAST_HOLEY_SMI_ELEMENTS:
case FAST_ELEMENTS:
case FAST_HOLEY_ELEMENTS:
case FAST_DOUBLE_ELEMENTS:
case FAST_HOLEY_DOUBLE_ELEMENTS:
return Add<HStoreKeyed>(elements, checked_key, val, elements_kind);
default:
UNREACHABLE();
return NULL;
}
}
// It's an element load (!is_store).
return Add<HLoadKeyed>(
elements, checked_key, load_dependency, elements_kind, load_mode);
}
HLoadNamedField* HGraphBuilder::AddLoadElements(HValue* object) {
return Add<HLoadNamedField>(object, HObjectAccess::ForElementsPointer());
}
HLoadNamedField* HGraphBuilder::AddLoadFixedArrayLength(HValue* object) {
return Add<HLoadNamedField>(object,
HObjectAccess::ForFixedArrayLength());
}
HValue* HGraphBuilder::BuildNewElementsCapacity(HValue* old_capacity) {
HValue* half_old_capacity = AddUncasted<HShr>(old_capacity,
graph_->GetConstant1());
HValue* new_capacity = AddUncasted<HAdd>(half_old_capacity, old_capacity);
new_capacity->ClearFlag(HValue::kCanOverflow);
HValue* min_growth = Add<HConstant>(16);
new_capacity = AddUncasted<HAdd>(new_capacity, min_growth);
new_capacity->ClearFlag(HValue::kCanOverflow);
return new_capacity;
}
void HGraphBuilder::BuildNewSpaceArrayCheck(HValue* length, ElementsKind kind) {
Heap* heap = isolate()->heap();
int element_size = IsFastDoubleElementsKind(kind) ? kDoubleSize
: kPointerSize;
int max_size = heap->MaxRegularSpaceAllocationSize() / element_size;
max_size -= JSArray::kSize / element_size;
HConstant* max_size_constant = Add<HConstant>(max_size);
Add<HBoundsCheck>(length, max_size_constant);
}
HValue* HGraphBuilder::BuildGrowElementsCapacity(HValue* object,
HValue* elements,
ElementsKind kind,
ElementsKind new_kind,
HValue* length,
HValue* new_capacity) {
BuildNewSpaceArrayCheck(new_capacity, new_kind);
HValue* new_elements = BuildAllocateElementsAndInitializeElementsHeader(
new_kind, new_capacity);
BuildCopyElements(elements, kind,
new_elements, new_kind,
length, new_capacity);
Add<HStoreNamedField>(object, HObjectAccess::ForElementsPointer(),
new_elements);
return new_elements;
}
void HGraphBuilder::BuildFillElementsWithHole(HValue* elements,
ElementsKind elements_kind,
HValue* from,
HValue* to) {
// Fast elements kinds need to be initialized in case statements below cause
// a garbage collection.
Factory* factory = isolate()->factory();
double nan_double = FixedDoubleArray::hole_nan_as_double();
HValue* hole = IsFastSmiOrObjectElementsKind(elements_kind)
? Add<HConstant>(factory->the_hole_value())
: Add<HConstant>(nan_double);
// Special loop unfolding case
static const int kLoopUnfoldLimit = 4;
bool unfold_loop = false;
int initial_capacity = JSArray::kPreallocatedArrayElements;
if (from->IsConstant() && to->IsConstant() &&
initial_capacity <= kLoopUnfoldLimit) {
HConstant* constant_from = HConstant::cast(from);
HConstant* constant_to = HConstant::cast(to);
if (constant_from->HasInteger32Value() &&
constant_from->Integer32Value() == 0 &&
constant_to->HasInteger32Value() &&
constant_to->Integer32Value() == initial_capacity) {
unfold_loop = true;
}
}
// Since we're about to store a hole value, the store instruction below must
// assume an elements kind that supports heap object values.
if (IsFastSmiOrObjectElementsKind(elements_kind)) {
elements_kind = FAST_HOLEY_ELEMENTS;
}
if (unfold_loop) {
for (int i = 0; i < initial_capacity; i++) {
HInstruction* key = Add<HConstant>(i);
Add<HStoreKeyed>(elements, key, hole, elements_kind);
}
} else {
LoopBuilder builder(this, context(), LoopBuilder::kPostIncrement);
HValue* key = builder.BeginBody(from, to, Token::LT);
Add<HStoreKeyed>(elements, key, hole, elements_kind);
builder.EndBody();
}
}
void HGraphBuilder::BuildCopyElements(HValue* from_elements,
ElementsKind from_elements_kind,
HValue* to_elements,
ElementsKind to_elements_kind,
HValue* length,
HValue* capacity) {
bool pre_fill_with_holes =
IsFastDoubleElementsKind(from_elements_kind) &&
IsFastObjectElementsKind(to_elements_kind);
if (pre_fill_with_holes) {
// If the copy might trigger a GC, make sure that the FixedArray is
// pre-initialized with holes to make sure that it's always in a consistent
// state.
BuildFillElementsWithHole(to_elements, to_elements_kind,
graph()->GetConstant0(), capacity);
}
LoopBuilder builder(this, context(), LoopBuilder::kPostIncrement);
HValue* key = builder.BeginBody(graph()->GetConstant0(), length, Token::LT);
HValue* element = Add<HLoadKeyed>(from_elements, key,
static_cast<HValue*>(NULL),
from_elements_kind,
ALLOW_RETURN_HOLE);
ElementsKind kind = (IsHoleyElementsKind(from_elements_kind) &&
IsFastSmiElementsKind(to_elements_kind))
? FAST_HOLEY_ELEMENTS : to_elements_kind;
if (IsHoleyElementsKind(from_elements_kind) &&
from_elements_kind != to_elements_kind) {
IfBuilder if_hole(this);
if_hole.If<HCompareHoleAndBranch>(element);
if_hole.Then();
HConstant* hole_constant = IsFastDoubleElementsKind(to_elements_kind)
? Add<HConstant>(FixedDoubleArray::hole_nan_as_double())
: graph()->GetConstantHole();
Add<HStoreKeyed>(to_elements, key, hole_constant, kind);
if_hole.Else();
HStoreKeyed* store = Add<HStoreKeyed>(to_elements, key, element, kind);
store->SetFlag(HValue::kAllowUndefinedAsNaN);
if_hole.End();
} else {
HStoreKeyed* store = Add<HStoreKeyed>(to_elements, key, element, kind);
store->SetFlag(HValue::kAllowUndefinedAsNaN);
}
builder.EndBody();
if (!pre_fill_with_holes && length != capacity) {
// Fill unused capacity with the hole.
BuildFillElementsWithHole(to_elements, to_elements_kind,
key, capacity);
}
}
HValue* HGraphBuilder::BuildCloneShallowArray(HValue* boilerplate,
HValue* allocation_site,
AllocationSiteMode mode,
ElementsKind kind,
int length) {
NoObservableSideEffectsScope no_effects(this);
// All sizes here are multiples of kPointerSize.
int size = JSArray::kSize;
if (mode == TRACK_ALLOCATION_SITE) {
size += AllocationMemento::kSize;
}
HValue* size_in_bytes = Add<HConstant>(size);
HInstruction* object = Add<HAllocate>(size_in_bytes,
HType::JSObject(),
NOT_TENURED,
JS_OBJECT_TYPE);
// Copy the JS array part.
for (int i = 0; i < JSArray::kSize; i += kPointerSize) {
if ((i != JSArray::kElementsOffset) || (length == 0)) {
HObjectAccess access = HObjectAccess::ForJSArrayOffset(i);
Add<HStoreNamedField>(object, access,
Add<HLoadNamedField>(boilerplate, access));
}
}
// Create an allocation site info if requested.
if (mode == TRACK_ALLOCATION_SITE) {
BuildCreateAllocationMemento(object, JSArray::kSize, allocation_site);
}
if (length > 0) {
HValue* boilerplate_elements = AddLoadElements(boilerplate);
HValue* object_elements;
if (IsFastDoubleElementsKind(kind)) {
HValue* elems_size = Add<HConstant>(FixedDoubleArray::SizeFor(length));
object_elements = Add<HAllocate>(elems_size, HType::JSArray(),
NOT_TENURED, FIXED_DOUBLE_ARRAY_TYPE);
} else {
HValue* elems_size = Add<HConstant>(FixedArray::SizeFor(length));
object_elements = Add<HAllocate>(elems_size, HType::JSArray(),
NOT_TENURED, FIXED_ARRAY_TYPE);
}
Add<HStoreNamedField>(object, HObjectAccess::ForElementsPointer(),
object_elements);
// Copy the elements array header.
for (int i = 0; i < FixedArrayBase::kHeaderSize; i += kPointerSize) {
HObjectAccess access = HObjectAccess::ForFixedArrayHeader(i);
Add<HStoreNamedField>(object_elements, access,
Add<HLoadNamedField>(boilerplate_elements, access));
}
// Copy the elements array contents.
// TODO(mstarzinger): Teach HGraphBuilder::BuildCopyElements to unfold
// copying loops with constant length up to a given boundary and use this
// helper here instead.
for (int i = 0; i < length; i++) {
HValue* key_constant = Add<HConstant>(i);
HInstruction* value = Add<HLoadKeyed>(boilerplate_elements, key_constant,
static_cast<HValue*>(NULL), kind);
Add<HStoreKeyed>(object_elements, key_constant, value, kind);
}
}
return object;
}
void HGraphBuilder::BuildCompareNil(
HValue* value,
Handle<Type> type,
int position,
HIfContinuation* continuation) {
IfBuilder if_nil(this, position);
bool some_case_handled = false;
bool some_case_missing = false;
if (type->Maybe(Type::Null())) {
if (some_case_handled) if_nil.Or();
if_nil.If<HCompareObjectEqAndBranch>(value, graph()->GetConstantNull());
some_case_handled = true;
} else {
some_case_missing = true;
}
if (type->Maybe(Type::Undefined())) {
if (some_case_handled) if_nil.Or();
if_nil.If<HCompareObjectEqAndBranch>(value,
graph()->GetConstantUndefined());
some_case_handled = true;
} else {
some_case_missing = true;
}
if (type->Maybe(Type::Undetectable())) {
if (some_case_handled) if_nil.Or();
if_nil.If<HIsUndetectableAndBranch>(value);
some_case_handled = true;
} else {
some_case_missing = true;
}
if (some_case_missing) {
if_nil.Then();
if_nil.Else();
if (type->NumClasses() == 1) {
BuildCheckHeapObject(value);
// For ICs, the map checked below is a sentinel map that gets replaced by
// the monomorphic map when the code is used as a template to generate a
// new IC. For optimized functions, there is no sentinel map, the map
// emitted below is the actual monomorphic map.
BuildCheckMap(value, type->Classes().Current());
} else {
if_nil.Deopt("Too many undetectable types");
}
}
if_nil.CaptureContinuation(continuation);
}
HValue* HGraphBuilder::BuildCreateAllocationMemento(HValue* previous_object,
int previous_object_size,
HValue* alloc_site) {
ASSERT(alloc_site != NULL);
HInnerAllocatedObject* alloc_memento = Add<HInnerAllocatedObject>(
previous_object, previous_object_size);
Handle<Map> alloc_memento_map =
isolate()->factory()->allocation_memento_map();
AddStoreMapConstant(alloc_memento, alloc_memento_map);
HObjectAccess access = HObjectAccess::ForAllocationMementoSite();
Add<HStoreNamedField>(alloc_memento, access, alloc_site);
return alloc_memento;
}
HInstruction* HGraphBuilder::BuildGetNativeContext() {
// Get the global context, then the native context
HInstruction* global_object = Add<HGlobalObject>();
HObjectAccess access = HObjectAccess::ForJSObjectOffset(
GlobalObject::kNativeContextOffset);
return Add<HLoadNamedField>(global_object, access);
}
HInstruction* HGraphBuilder::BuildGetArrayFunction() {
HInstruction* native_context = BuildGetNativeContext();
HInstruction* index =
Add<HConstant>(static_cast<int32_t>(Context::ARRAY_FUNCTION_INDEX));
return Add<HLoadKeyed>(
native_context, index, static_cast<HValue*>(NULL), FAST_ELEMENTS);
}
HGraphBuilder::JSArrayBuilder::JSArrayBuilder(HGraphBuilder* builder,
ElementsKind kind,
HValue* allocation_site_payload,
HValue* constructor_function,
AllocationSiteOverrideMode override_mode) :
builder_(builder),
kind_(kind),
allocation_site_payload_(allocation_site_payload),
constructor_function_(constructor_function) {
mode_ = override_mode == DISABLE_ALLOCATION_SITES
? DONT_TRACK_ALLOCATION_SITE
: AllocationSite::GetMode(kind);
}
HGraphBuilder::JSArrayBuilder::JSArrayBuilder(HGraphBuilder* builder,
ElementsKind kind,
HValue* constructor_function) :
builder_(builder),
kind_(kind),
mode_(DONT_TRACK_ALLOCATION_SITE),
allocation_site_payload_(NULL),
constructor_function_(constructor_function) {
}
HValue* HGraphBuilder::JSArrayBuilder::EmitMapCode() {
if (kind_ == GetInitialFastElementsKind()) {
// No need for a context lookup if the kind_ matches the initial
// map, because we can just load the map in that case.
HObjectAccess access = HObjectAccess::ForPrototypeOrInitialMap();
return builder()->AddInstruction(
builder()->BuildLoadNamedField(constructor_function_, access));
}
HInstruction* native_context = builder()->BuildGetNativeContext();
HInstruction* index = builder()->Add<HConstant>(
static_cast<int32_t>(Context::JS_ARRAY_MAPS_INDEX));
HInstruction* map_array = builder()->Add<HLoadKeyed>(
native_context, index, static_cast<HValue*>(NULL), FAST_ELEMENTS);
HInstruction* kind_index = builder()->Add<HConstant>(kind_);
return builder()->Add<HLoadKeyed>(
map_array, kind_index, static_cast<HValue*>(NULL), FAST_ELEMENTS);
}
HValue* HGraphBuilder::JSArrayBuilder::EmitInternalMapCode() {
// Find the map near the constructor function
HObjectAccess access = HObjectAccess::ForPrototypeOrInitialMap();
return builder()->AddInstruction(
builder()->BuildLoadNamedField(constructor_function_, access));
}
HValue* HGraphBuilder::JSArrayBuilder::EstablishAllocationSize(
HValue* length_node) {
ASSERT(length_node != NULL);
int base_size = JSArray::kSize;
if (mode_ == TRACK_ALLOCATION_SITE) {
base_size += AllocationMemento::kSize;
}
STATIC_ASSERT(FixedDoubleArray::kHeaderSize == FixedArray::kHeaderSize);
base_size += FixedArray::kHeaderSize;
HInstruction* elements_size_value =
builder()->Add<HConstant>(elements_size());
HInstruction* mul = builder()->Add<HMul>(length_node, elements_size_value);
mul->ClearFlag(HValue::kCanOverflow);
HInstruction* base = builder()->Add<HConstant>(base_size);
HInstruction* total_size = builder()->Add<HAdd>(base, mul);
total_size->ClearFlag(HValue::kCanOverflow);
return total_size;
}
HValue* HGraphBuilder::JSArrayBuilder::EstablishEmptyArrayAllocationSize() {
int base_size = JSArray::kSize;
if (mode_ == TRACK_ALLOCATION_SITE) {
base_size += AllocationMemento::kSize;
}
base_size += IsFastDoubleElementsKind(kind_)
? FixedDoubleArray::SizeFor(initial_capacity())
: FixedArray::SizeFor(initial_capacity());
return builder()->Add<HConstant>(base_size);
}
HValue* HGraphBuilder::JSArrayBuilder::AllocateEmptyArray() {
HValue* size_in_bytes = EstablishEmptyArrayAllocationSize();
HConstant* capacity = builder()->Add<HConstant>(initial_capacity());
return AllocateArray(size_in_bytes,
capacity,
builder()->graph()->GetConstant0(),
true);
}
HValue* HGraphBuilder::JSArrayBuilder::AllocateArray(HValue* capacity,
HValue* length_field,
bool fill_with_hole) {
HValue* size_in_bytes = EstablishAllocationSize(capacity);
return AllocateArray(size_in_bytes, capacity, length_field, fill_with_hole);
}
HValue* HGraphBuilder::JSArrayBuilder::AllocateArray(HValue* size_in_bytes,
HValue* capacity,
HValue* length_field,
bool fill_with_hole) {
// These HForceRepresentations are because we store these as fields in the
// objects we construct, and an int32-to-smi HChange could deopt. Accept
// the deopt possibility now, before allocation occurs.
capacity = builder()->Add<HForceRepresentation>(capacity,
Representation::Smi());
length_field = builder()->Add<HForceRepresentation>(length_field,
Representation::Smi());
// Allocate (dealing with failure appropriately)
HAllocate* new_object = builder()->Add<HAllocate>(size_in_bytes,
HType::JSArray(), NOT_TENURED, JS_ARRAY_TYPE);
// Fill in the fields: map, properties, length
HValue* map;
if (allocation_site_payload_ == NULL) {
map = EmitInternalMapCode();
} else {
map = EmitMapCode();
}
elements_location_ = builder()->BuildJSArrayHeader(new_object,
map,
mode_,
kind_,
allocation_site_payload_,
length_field);
// Initialize the elements
builder()->BuildInitializeElementsHeader(elements_location_, kind_, capacity);
if (fill_with_hole) {
builder()->BuildFillElementsWithHole(elements_location_, kind_,
graph()->GetConstant0(), capacity);
}
return new_object;
}
HStoreNamedField* HGraphBuilder::AddStoreMapConstant(HValue *object,
Handle<Map> map) {
return Add<HStoreNamedField>(object, HObjectAccess::ForMap(),
Add<HConstant>(map));
}
HValue* HGraphBuilder::AddLoadJSBuiltin(Builtins::JavaScript builtin) {
HGlobalObject* global_object = Add<HGlobalObject>();
HObjectAccess access = HObjectAccess::ForJSObjectOffset(
GlobalObject::kBuiltinsOffset);
HValue* builtins = Add<HLoadNamedField>(global_object, access);
HObjectAccess function_access = HObjectAccess::ForJSObjectOffset(
JSBuiltinsObject::OffsetOfFunctionWithId(builtin));
return Add<HLoadNamedField>(builtins, function_access);
}
HOptimizedGraphBuilder::HOptimizedGraphBuilder(CompilationInfo* info)
: HGraphBuilder(info),
function_state_(NULL),
initial_function_state_(this, info, NORMAL_RETURN),
ast_context_(NULL),
break_scope_(NULL),
inlined_count_(0),
globals_(10, info->zone()),
inline_bailout_(false),
osr_(new(info->zone()) HOsrBuilder(this)) {
// This is not initialized in the initializer list because the
// constructor for the initial state relies on function_state_ == NULL
// to know it's the initial state.
function_state_= &initial_function_state_;
InitializeAstVisitor(info->isolate());
}
HBasicBlock* HOptimizedGraphBuilder::CreateJoin(HBasicBlock* first,
HBasicBlock* second,
BailoutId join_id) {
if (first == NULL) {
return second;
} else if (second == NULL) {
return first;
} else {
HBasicBlock* join_block = graph()->CreateBasicBlock();
first->Goto(join_block);
second->Goto(join_block);
join_block->SetJoinId(join_id);
return join_block;
}
}
HBasicBlock* HOptimizedGraphBuilder::JoinContinue(IterationStatement* statement,
HBasicBlock* exit_block,
HBasicBlock* continue_block) {
if (continue_block != NULL) {
if (exit_block != NULL) exit_block->Goto(continue_block);
continue_block->SetJoinId(statement->ContinueId());
return continue_block;
}
return exit_block;
}
HBasicBlock* HOptimizedGraphBuilder::CreateLoop(IterationStatement* statement,
HBasicBlock* loop_entry,
HBasicBlock* body_exit,
HBasicBlock* loop_successor,
HBasicBlock* break_block) {
if (body_exit != NULL) body_exit->Goto(loop_entry);
loop_entry->PostProcessLoopHeader(statement);
if (break_block != NULL) {
if (loop_successor != NULL) loop_successor->Goto(break_block);
break_block->SetJoinId(statement->ExitId());
return break_block;
}
return loop_successor;
}
// Build a new loop header block and set it as the current block.
HBasicBlock* HOptimizedGraphBuilder::BuildLoopEntry() {
HBasicBlock* loop_entry = CreateLoopHeaderBlock();
current_block()->Goto(loop_entry);
set_current_block(loop_entry);
return loop_entry;
}
HBasicBlock* HOptimizedGraphBuilder::BuildLoopEntry(
IterationStatement* statement) {
HBasicBlock* loop_entry = osr()->HasOsrEntryAt(statement)
? osr()->BuildOsrLoopEntry(statement)
: BuildLoopEntry();
return loop_entry;
}
void HBasicBlock::FinishExit(HControlInstruction* instruction) {
Finish(instruction);
ClearEnvironment();
}
HGraph::HGraph(CompilationInfo* info)
: isolate_(info->isolate()),
next_block_id_(0),
entry_block_(NULL),
blocks_(8, info->zone()),
values_(16, info->zone()),
phi_list_(NULL),
uint32_instructions_(NULL),
osr_(NULL),
info_(info),
zone_(info->zone()),
is_recursive_(false),
use_optimistic_licm_(false),
depends_on_empty_array_proto_elements_(false),
type_change_checksum_(0),
maximum_environment_size_(0),
no_side_effects_scope_count_(0) {
if (info->IsStub()) {
HydrogenCodeStub* stub = info->code_stub();
CodeStubInterfaceDescriptor* descriptor =
stub->GetInterfaceDescriptor(isolate_);
start_environment_ =
new(zone_) HEnvironment(zone_, descriptor->environment_length());
} else {
start_environment_ =
new(zone_) HEnvironment(NULL, info->scope(), info->closure(), zone_);
}
start_environment_->set_ast_id(BailoutId::FunctionEntry());
entry_block_ = CreateBasicBlock();
entry_block_->SetInitialEnvironment(start_environment_);
}
HBasicBlock* HGraph::CreateBasicBlock() {
HBasicBlock* result = new(zone()) HBasicBlock(this);
blocks_.Add(result, zone());
return result;
}
void HGraph::FinalizeUniqueness() {
DisallowHeapAllocation no_gc;
ASSERT(!isolate()->optimizing_compiler_thread()->IsOptimizerThread());
for (int i = 0; i < blocks()->length(); ++i) {
for (HInstructionIterator it(blocks()->at(i)); !it.Done(); it.Advance()) {
it.Current()->FinalizeUniqueness();
}
}
}
// Block ordering was implemented with two mutually recursive methods,
// HGraph::Postorder and HGraph::PostorderLoopBlocks.
// The recursion could lead to stack overflow so the algorithm has been
// implemented iteratively.
// At a high level the algorithm looks like this:
//
// Postorder(block, loop_header) : {
// if (block has already been visited or is of another loop) return;
// mark block as visited;
// if (block is a loop header) {
// VisitLoopMembers(block, loop_header);
// VisitSuccessorsOfLoopHeader(block);
// } else {
// VisitSuccessors(block)
// }
// put block in result list;
// }
//
// VisitLoopMembers(block, outer_loop_header) {
// foreach (block b in block loop members) {
// VisitSuccessorsOfLoopMember(b, outer_loop_header);
// if (b is loop header) VisitLoopMembers(b);
// }
// }
//
// VisitSuccessorsOfLoopMember(block, outer_loop_header) {
// foreach (block b in block successors) Postorder(b, outer_loop_header)
// }
//
// VisitSuccessorsOfLoopHeader(block) {
// foreach (block b in block successors) Postorder(b, block)
// }
//
// VisitSuccessors(block, loop_header) {
// foreach (block b in block successors) Postorder(b, loop_header)
// }
//
// The ordering is started calling Postorder(entry, NULL).
//
// Each instance of PostorderProcessor represents the "stack frame" of the
// recursion, and particularly keeps the state of the loop (iteration) of the
// "Visit..." function it represents.
// To recycle memory we keep all the frames in a double linked list but
// this means that we cannot use constructors to initialize the frames.
//
class PostorderProcessor : public ZoneObject {
public:
// Back link (towards the stack bottom).
PostorderProcessor* parent() {return father_; }
// Forward link (towards the stack top).
PostorderProcessor* child() {return child_; }
HBasicBlock* block() { return block_; }
HLoopInformation* loop() { return loop_; }
HBasicBlock* loop_header() { return loop_header_; }
static PostorderProcessor* CreateEntryProcessor(Zone* zone,
HBasicBlock* block,
BitVector* visited) {
PostorderProcessor* result = new(zone) PostorderProcessor(NULL);
return result->SetupSuccessors(zone, block, NULL, visited);
}
PostorderProcessor* PerformStep(Zone* zone,
BitVector* visited,
ZoneList<HBasicBlock*>* order) {
PostorderProcessor* next =
PerformNonBacktrackingStep(zone, visited, order);
if (next != NULL) {
return next;
} else {
return Backtrack(zone, visited, order);
}
}
private:
explicit PostorderProcessor(PostorderProcessor* father)
: father_(father), child_(NULL), successor_iterator(NULL) { }
// Each enum value states the cycle whose state is kept by this instance.
enum LoopKind {
NONE,
SUCCESSORS,
SUCCESSORS_OF_LOOP_HEADER,
LOOP_MEMBERS,
SUCCESSORS_OF_LOOP_MEMBER
};
// Each "Setup..." method is like a constructor for a cycle state.
PostorderProcessor* SetupSuccessors(Zone* zone,
HBasicBlock* block,
HBasicBlock* loop_header,
BitVector* visited) {
if (block == NULL || visited->Contains(block->block_id()) ||
block->parent_loop_header() != loop_header) {
kind_ = NONE;
block_ = NULL;
loop_ = NULL;
loop_header_ = NULL;
return this;
} else {
block_ = block;
loop_ = NULL;
visited->Add(block->block_id());
if (block->IsLoopHeader()) {
kind_ = SUCCESSORS_OF_LOOP_HEADER;
loop_header_ = block;
InitializeSuccessors();
PostorderProcessor* result = Push(zone);
return result->SetupLoopMembers(zone, block, block->loop_information(),
loop_header);
} else {
ASSERT(block->IsFinished());
kind_ = SUCCESSORS;
loop_header_ = loop_header;
InitializeSuccessors();
return this;
}
}
}
PostorderProcessor* SetupLoopMembers(Zone* zone,
HBasicBlock* block,
HLoopInformation* loop,
HBasicBlock* loop_header) {
kind_ = LOOP_MEMBERS;
block_ = block;
loop_ = loop;
loop_header_ = loop_header;
InitializeLoopMembers();
return this;
}
PostorderProcessor* SetupSuccessorsOfLoopMember(
HBasicBlock* block,
HLoopInformation* loop,
HBasicBlock* loop_header) {
kind_ = SUCCESSORS_OF_LOOP_MEMBER;
block_ = block;
loop_ = loop;
loop_header_ = loop_header;
InitializeSuccessors();
return this;
}
// This method "allocates" a new stack frame.
PostorderProcessor* Push(Zone* zone) {
if (child_ == NULL) {
child_ = new(zone) PostorderProcessor(this);
}
return child_;
}
void ClosePostorder(ZoneList<HBasicBlock*>* order, Zone* zone) {
ASSERT(block_->end()->FirstSuccessor() == NULL ||
order->Contains(block_->end()->FirstSuccessor()) ||
block_->end()->FirstSuccessor()->IsLoopHeader());
ASSERT(block_->end()->SecondSuccessor() == NULL ||
order->Contains(block_->end()->SecondSuccessor()) ||
block_->end()->SecondSuccessor()->IsLoopHeader());
order->Add(block_, zone);
}
// This method is the basic block to walk up the stack.
PostorderProcessor* Pop(Zone* zone,
BitVector* visited,
ZoneList<HBasicBlock*>* order) {
switch (kind_) {
case SUCCESSORS:
case SUCCESSORS_OF_LOOP_HEADER:
ClosePostorder(order, zone);
return father_;
case LOOP_MEMBERS:
return father_;
case SUCCESSORS_OF_LOOP_MEMBER:
if (block()->IsLoopHeader() && block() != loop_->loop_header()) {
// In this case we need to perform a LOOP_MEMBERS cycle so we
// initialize it and return this instead of father.
return SetupLoopMembers(zone, block(),
block()->loop_information(), loop_header_);
} else {
return father_;
}
case NONE:
return father_;
}
UNREACHABLE();
return NULL;
}
// Walks up the stack.
PostorderProcessor* Backtrack(Zone* zone,
BitVector* visited,
ZoneList<HBasicBlock*>* order) {
PostorderProcessor* parent = Pop(zone, visited, order);
while (parent != NULL) {
PostorderProcessor* next =
parent->PerformNonBacktrackingStep(zone, visited, order);
if (next != NULL) {
return next;
} else {
parent = parent->Pop(zone, visited, order);
}
}
return NULL;
}
PostorderProcessor* PerformNonBacktrackingStep(
Zone* zone,
BitVector* visited,
ZoneList<HBasicBlock*>* order) {
HBasicBlock* next_block;
switch (kind_) {
case SUCCESSORS:
next_block = AdvanceSuccessors();
if (next_block != NULL) {
PostorderProcessor* result = Push(zone);
return result->SetupSuccessors(zone, next_block,
loop_header_, visited);
}
break;
case SUCCESSORS_OF_LOOP_HEADER:
next_block = AdvanceSuccessors();
if (next_block != NULL) {
PostorderProcessor* result = Push(zone);
return result->SetupSuccessors(zone, next_block,
block(), visited);
}
break;
case LOOP_MEMBERS:
next_block = AdvanceLoopMembers();
if (next_block != NULL) {
PostorderProcessor* result = Push(zone);
return result->SetupSuccessorsOfLoopMember(next_block,
loop_, loop_header_);
}
break;
case SUCCESSORS_OF_LOOP_MEMBER:
next_block = AdvanceSuccessors();
if (next_block != NULL) {
PostorderProcessor* result = Push(zone);
return result->SetupSuccessors(zone, next_block,
loop_header_, visited);
}
break;
case NONE:
return NULL;
}
return NULL;
}
// The following two methods implement a "foreach b in successors" cycle.
void InitializeSuccessors() {
loop_index = 0;
loop_length = 0;
successor_iterator = HSuccessorIterator(block_->end());
}
HBasicBlock* AdvanceSuccessors() {
if (!successor_iterator.Done()) {
HBasicBlock* result = successor_iterator.Current();
successor_iterator.Advance();
return result;
}
return NULL;
}
// The following two methods implement a "foreach b in loop members" cycle.
void InitializeLoopMembers() {
loop_index = 0;
loop_length = loop_->blocks()->length();
}
HBasicBlock* AdvanceLoopMembers() {
if (loop_index < loop_length) {
HBasicBlock* result = loop_->blocks()->at(loop_index);
loop_index++;
return result;
} else {
return NULL;
}
}
LoopKind kind_;
PostorderProcessor* father_;
PostorderProcessor* child_;
HLoopInformation* loop_;
HBasicBlock* block_;
HBasicBlock* loop_header_;
int loop_index;
int loop_length;
HSuccessorIterator successor_iterator;
};
void HGraph::OrderBlocks() {
CompilationPhase phase("H_Block ordering", info());
BitVector visited(blocks_.length(), zone());
ZoneList<HBasicBlock*> reverse_result(8, zone());
HBasicBlock* start = blocks_[0];
PostorderProcessor* postorder =
PostorderProcessor::CreateEntryProcessor(zone(), start, &visited);
while (postorder != NULL) {
postorder = postorder->PerformStep(zone(), &visited, &reverse_result);
}
blocks_.Rewind(0);
int index = 0;
for (int i = reverse_result.length() - 1; i >= 0; --i) {
HBasicBlock* b = reverse_result[i];
blocks_.Add(b, zone());
b->set_block_id(index++);
}
}
void HGraph::AssignDominators() {
HPhase phase("H_Assign dominators", this);
for (int i = 0; i < blocks_.length(); ++i) {
HBasicBlock* block = blocks_[i];
if (block->IsLoopHeader()) {
// Only the first predecessor of a loop header is from outside the loop.
// All others are back edges, and thus cannot dominate the loop header.
block->AssignCommonDominator(block->predecessors()->first());
block->AssignLoopSuccessorDominators();
} else {
for (int j = blocks_[i]->predecessors()->length() - 1; j >= 0; --j) {
blocks_[i]->AssignCommonDominator(blocks_[i]->predecessors()->at(j));
}
}
}
}
bool HGraph::CheckArgumentsPhiUses() {
int block_count = blocks_.length();
for (int i = 0; i < block_count; ++i) {
for (int j = 0; j < blocks_[i]->phis()->length(); ++j) {
HPhi* phi = blocks_[i]->phis()->at(j);
// We don't support phi uses of arguments for now.
if (phi->CheckFlag(HValue::kIsArguments)) return false;
}
}
return true;
}
bool HGraph::CheckConstPhiUses() {
int block_count = blocks_.length();
for (int i = 0; i < block_count; ++i) {
for (int j = 0; j < blocks_[i]->phis()->length(); ++j) {
HPhi* phi = blocks_[i]->phis()->at(j);
// Check for the hole value (from an uninitialized const).
for (int k = 0; k < phi->OperandCount(); k++) {
if (phi->OperandAt(k) == GetConstantHole()) return false;
}
}
}
return true;
}
void HGraph::CollectPhis() {
int block_count = blocks_.length();
phi_list_ = new(zone()) ZoneList<HPhi*>(block_count, zone());
for (int i = 0; i < block_count; ++i) {
for (int j = 0; j < blocks_[i]->phis()->length(); ++j) {
HPhi* phi = blocks_[i]->phis()->at(j);
phi_list_->Add(phi, zone());
}
}
}
// Implementation of utility class to encapsulate the translation state for
// a (possibly inlined) function.
FunctionState::FunctionState(HOptimizedGraphBuilder* owner,
CompilationInfo* info,
InliningKind inlining_kind)
: owner_(owner),
compilation_info_(info),
call_context_(NULL),
inlining_kind_(inlining_kind),
function_return_(NULL),
test_context_(NULL),
entry_(NULL),
arguments_object_(NULL),
arguments_elements_(NULL),
outer_(owner->function_state()) {
if (outer_ != NULL) {
// State for an inline function.
if (owner->ast_context()->IsTest()) {
HBasicBlock* if_true = owner->graph()->CreateBasicBlock();
HBasicBlock* if_false = owner->graph()->CreateBasicBlock();
if_true->MarkAsInlineReturnTarget(owner->current_block());
if_false->MarkAsInlineReturnTarget(owner->current_block());
TestContext* outer_test_context = TestContext::cast(owner->ast_context());
Expression* cond = outer_test_context->condition();
// The AstContext constructor pushed on the context stack. This newed
// instance is the reason that AstContext can't be BASE_EMBEDDED.
test_context_ = new TestContext(owner, cond, if_true, if_false);
} else {
function_return_ = owner->graph()->CreateBasicBlock();
function_return()->MarkAsInlineReturnTarget(owner->current_block());
}
// Set this after possibly allocating a new TestContext above.
call_context_ = owner->ast_context();
}
// Push on the state stack.
owner->set_function_state(this);
}
FunctionState::~FunctionState() {
delete test_context_;
owner_->set_function_state(outer_);
}
// Implementation of utility classes to represent an expression's context in
// the AST.
AstContext::AstContext(HOptimizedGraphBuilder* owner, Expression::Context kind)
: owner_(owner),
kind_(kind),
outer_(owner->ast_context()),
for_typeof_(false) {
owner->set_ast_context(this); // Push.
#ifdef DEBUG
ASSERT(owner->environment()->frame_type() == JS_FUNCTION);
original_length_ = owner->environment()->length();
#endif
}
AstContext::~AstContext() {
owner_->set_ast_context(outer_); // Pop.
}
EffectContext::~EffectContext() {
ASSERT(owner()->HasStackOverflow() ||
owner()->current_block() == NULL ||
(owner()->environment()->length() == original_length_ &&
owner()->environment()->frame_type() == JS_FUNCTION));
}
ValueContext::~ValueContext() {
ASSERT(owner()->HasStackOverflow() ||
owner()->current_block() == NULL ||
(owner()->environment()->length() == original_length_ + 1 &&
owner()->environment()->frame_type() == JS_FUNCTION));
}
void EffectContext::ReturnValue(HValue* value) {
// The value is simply ignored.
}
void ValueContext::ReturnValue(HValue* value) {
// The value is tracked in the bailout environment, and communicated
// through the environment as the result of the expression.
if (!arguments_allowed() && value->CheckFlag(HValue::kIsArguments)) {
owner()->Bailout(kBadValueContextForArgumentsValue);
}
owner()->Push(value);
}
void TestContext::ReturnValue(HValue* value) {
BuildBranch(value);
}
void EffectContext::ReturnInstruction(HInstruction* instr, BailoutId ast_id) {
ASSERT(!instr->IsControlInstruction());
owner()->AddInstruction(instr);
if (instr->HasObservableSideEffects()) {
owner()->Add<HSimulate>(ast_id, REMOVABLE_SIMULATE);
}
}
void EffectContext::ReturnControl(HControlInstruction* instr,
BailoutId ast_id) {
ASSERT(!instr->HasObservableSideEffects());
HBasicBlock* empty_true = owner()->graph()->CreateBasicBlock();
HBasicBlock* empty_false = owner()->graph()->CreateBasicBlock();
instr->SetSuccessorAt(0, empty_true);
instr->SetSuccessorAt(1, empty_false);
owner()->current_block()->Finish(instr);
HBasicBlock* join = owner()->CreateJoin(empty_true, empty_false, ast_id);
owner()->set_current_block(join);
}
void EffectContext::ReturnContinuation(HIfContinuation* continuation,
BailoutId ast_id) {
HBasicBlock* true_branch = NULL;
HBasicBlock* false_branch = NULL;
continuation->Continue(&true_branch, &false_branch, NULL);
if (!continuation->IsTrueReachable()) {
owner()->set_current_block(false_branch);
} else if (!continuation->IsFalseReachable()) {
owner()->set_current_block(true_branch);
} else {
HBasicBlock* join = owner()->CreateJoin(true_branch, false_branch, ast_id);
owner()->set_current_block(join);
}
}
void ValueContext::ReturnInstruction(HInstruction* instr, BailoutId ast_id) {
ASSERT(!instr->IsControlInstruction());
if (!arguments_allowed() && instr->CheckFlag(HValue::kIsArguments)) {
return owner()->Bailout(kBadValueContextForArgumentsObjectValue);
}
owner()->AddInstruction(instr);
owner()->Push(instr);
if (instr->HasObservableSideEffects()) {
owner()->Add<HSimulate>(ast_id, REMOVABLE_SIMULATE);
}
}
void ValueContext::ReturnControl(HControlInstruction* instr, BailoutId ast_id) {
ASSERT(!instr->HasObservableSideEffects());
if (!arguments_allowed() && instr->CheckFlag(HValue::kIsArguments)) {
return owner()->Bailout(kBadValueContextForArgumentsObjectValue);
}
HBasicBlock* materialize_false = owner()->graph()->CreateBasicBlock();
HBasicBlock* materialize_true = owner()->graph()->CreateBasicBlock();
instr->SetSuccessorAt(0, materialize_true);
instr->SetSuccessorAt(1, materialize_false);
owner()->current_block()->Finish(instr);
owner()->set_current_block(materialize_true);
owner()->Push(owner()->graph()->GetConstantTrue());
owner()->set_current_block(materialize_false);
owner()->Push(owner()->graph()->GetConstantFalse());
HBasicBlock* join =
owner()->CreateJoin(materialize_true, materialize_false, ast_id);
owner()->set_current_block(join);
}
void ValueContext::ReturnContinuation(HIfContinuation* continuation,
BailoutId ast_id) {
HBasicBlock* materialize_true = NULL;
HBasicBlock* materialize_false = NULL;
continuation->Continue(&materialize_true, &materialize_false, NULL);
if (continuation->IsTrueReachable()) {
owner()->set_current_block(materialize_true);
owner()->Push(owner()->graph()->GetConstantTrue());
owner()->set_current_block(materialize_true);
}
if (continuation->IsFalseReachable()) {
owner()->set_current_block(materialize_false);
owner()->Push(owner()->graph()->GetConstantFalse());
owner()->set_current_block(materialize_false);
}
if (continuation->TrueAndFalseReachable()) {
HBasicBlock* join =
owner()->CreateJoin(materialize_true, materialize_false, ast_id);
owner()->set_current_block(join);
}
}
void TestContext::ReturnInstruction(HInstruction* instr, BailoutId ast_id) {
ASSERT(!instr->IsControlInstruction());
HOptimizedGraphBuilder* builder = owner();
builder->AddInstruction(instr);
// We expect a simulate after every expression with side effects, though
// this one isn't actually needed (and wouldn't work if it were targeted).
if (instr->HasObservableSideEffects()) {
builder->Push(instr);
builder->Add<HSimulate>(ast_id, REMOVABLE_SIMULATE);
builder->Pop();
}
BuildBranch(instr);
}
void TestContext::ReturnControl(HControlInstruction* instr, BailoutId ast_id) {
ASSERT(!instr->HasObservableSideEffects());
HBasicBlock* empty_true = owner()->graph()->CreateBasicBlock();
HBasicBlock* empty_false = owner()->graph()->CreateBasicBlock();
instr->SetSuccessorAt(0, empty_true);
instr->SetSuccessorAt(1, empty_false);
owner()->current_block()->Finish(instr);
empty_true->Goto(if_true(), owner()->function_state());
empty_false->Goto(if_false(), owner()->function_state());
owner()->set_current_block(NULL);
}
void TestContext::ReturnContinuation(HIfContinuation* continuation,
BailoutId ast_id) {
HBasicBlock* true_branch = NULL;
HBasicBlock* false_branch = NULL;
continuation->Continue(&true_branch, &false_branch, NULL);
if (continuation->IsTrueReachable()) {
true_branch->Goto(if_true(), owner()->function_state());
}
if (continuation->IsFalseReachable()) {
false_branch->Goto(if_false(), owner()->function_state());
}
owner()->set_current_block(NULL);
}
void TestContext::BuildBranch(HValue* value) {
// We expect the graph to be in edge-split form: there is no edge that
// connects a branch node to a join node. We conservatively ensure that
// property by always adding an empty block on the outgoing edges of this
// branch.
HOptimizedGraphBuilder* builder = owner();
if (value != NULL && value->CheckFlag(HValue::kIsArguments)) {
builder->Bailout(kArgumentsObjectValueInATestContext);
}
HBasicBlock* empty_true = builder->graph()->CreateBasicBlock();
HBasicBlock* empty_false = builder->graph()->CreateBasicBlock();
ToBooleanStub::Types expected(condition()->to_boolean_types());
builder->current_block()->Finish(builder->New<HBranch>(
value, expected, empty_true, empty_false));
empty_true->Goto(if_true(), builder->function_state());
empty_false->Goto(if_false(), builder->function_state());
builder->set_current_block(NULL);
}
// HOptimizedGraphBuilder infrastructure for bailing out and checking bailouts.
#define CHECK_BAILOUT(call) \
do { \
call; \
if (HasStackOverflow()) return; \
} while (false)
#define CHECK_ALIVE(call) \
do { \
call; \
if (HasStackOverflow() || current_block() == NULL) return; \
} while (false)
#define CHECK_ALIVE_OR_RETURN(call, value) \
do { \
call; \
if (HasStackOverflow() || current_block() == NULL) return value; \
} while (false)
void HOptimizedGraphBuilder::Bailout(BailoutReason reason) {
current_info()->set_bailout_reason(reason);
SetStackOverflow();
}
void HOptimizedGraphBuilder::VisitForEffect(Expression* expr) {
EffectContext for_effect(this);
Visit(expr);
}
void HOptimizedGraphBuilder::VisitForValue(Expression* expr,
ArgumentsAllowedFlag flag) {
ValueContext for_value(this, flag);
Visit(expr);
}
void HOptimizedGraphBuilder::VisitForTypeOf(Expression* expr) {
ValueContext for_value(this, ARGUMENTS_NOT_ALLOWED);
for_value.set_for_typeof(true);
Visit(expr);
}
void HOptimizedGraphBuilder::VisitForControl(Expression* expr,
HBasicBlock* true_block,
HBasicBlock* false_block) {
TestContext for_test(this, expr, true_block, false_block);
Visit(expr);
}
void HOptimizedGraphBuilder::VisitArgument(Expression* expr) {
CHECK_ALIVE(VisitForValue(expr));
Push(Add<HPushArgument>(Pop()));
}
void HOptimizedGraphBuilder::VisitArgumentList(
ZoneList<Expression*>* arguments) {
for (int i = 0; i < arguments->length(); i++) {
CHECK_ALIVE(VisitArgument(arguments->at(i)));
}
}
void HOptimizedGraphBuilder::VisitExpressions(
ZoneList<Expression*>* exprs) {
for (int i = 0; i < exprs->length(); ++i) {
CHECK_ALIVE(VisitForValue(exprs->at(i)));
}
}
bool HOptimizedGraphBuilder::BuildGraph() {
if (current_info()->function()->is_generator()) {
Bailout(kFunctionIsAGenerator);
return false;
}
Scope* scope = current_info()->scope();
if (scope->HasIllegalRedeclaration()) {
Bailout(kFunctionWithIllegalRedeclaration);
return false;
}
if (scope->calls_eval()) {
Bailout(kFunctionCallsEval);
return false;
}
SetUpScope(scope);
// Add an edge to the body entry. This is warty: the graph's start
// environment will be used by the Lithium translation as the initial
// environment on graph entry, but it has now been mutated by the
// Hydrogen translation of the instructions in the start block. This
// environment uses values which have not been defined yet. These
// Hydrogen instructions will then be replayed by the Lithium
// translation, so they cannot have an environment effect. The edge to
// the body's entry block (along with some special logic for the start
// block in HInstruction::InsertAfter) seals the start block from
// getting unwanted instructions inserted.
//
// TODO(kmillikin): Fix this. Stop mutating the initial environment.
// Make the Hydrogen instructions in the initial block into Hydrogen
// values (but not instructions), present in the initial environment and
// not replayed by the Lithium translation.
HEnvironment* initial_env = environment()->CopyWithoutHistory();
HBasicBlock* body_entry = CreateBasicBlock(initial_env);
current_block()->Goto(body_entry);
body_entry->SetJoinId(BailoutId::FunctionEntry());
set_current_block(body_entry);
// Handle implicit declaration of the function name in named function
// expressions before other declarations.
if (scope->is_function_scope() && scope->function() != NULL) {
VisitVariableDeclaration(scope->function());
}
VisitDeclarations(scope->declarations());
Add<HSimulate>(BailoutId::Declarations());
Add<HStackCheck>(HStackCheck::kFunctionEntry);
VisitStatements(current_info()->function()->body());
if (HasStackOverflow()) return false;
if (current_block() != NULL) {
Add<HReturn>(graph()->GetConstantUndefined());
set_current_block(NULL);
}
// If the checksum of the number of type info changes is the same as the
// last time this function was compiled, then this recompile is likely not
// due to missing/inadequate type feedback, but rather too aggressive
// optimization. Disable optimistic LICM in that case.
Handle<Code> unoptimized_code(current_info()->shared_info()->code());
ASSERT(unoptimized_code->kind() == Code::FUNCTION);
Handle<TypeFeedbackInfo> type_info(
TypeFeedbackInfo::cast(unoptimized_code->type_feedback_info()));
int checksum = type_info->own_type_change_checksum();
int composite_checksum = graph()->update_type_change_checksum(checksum);
graph()->set_use_optimistic_licm(
!type_info->matches_inlined_type_change_checksum(composite_checksum));
type_info->set_inlined_type_change_checksum(composite_checksum);
// Perform any necessary OSR-specific cleanups or changes to the graph.
osr()->FinishGraph();
return true;
}
bool HGraph::Optimize(BailoutReason* bailout_reason) {
OrderBlocks();
AssignDominators();
// We need to create a HConstant "zero" now so that GVN will fold every
// zero-valued constant in the graph together.
// The constant is needed to make idef-based bounds check work: the pass
// evaluates relations with "zero" and that zero cannot be created after GVN.
GetConstant0();
#ifdef DEBUG
// Do a full verify after building the graph and computing dominators.
Verify(true);
#endif
if (FLAG_analyze_environment_liveness && maximum_environment_size() != 0) {
Run<HEnvironmentLivenessAnalysisPhase>();
}
if (!CheckConstPhiUses()) {
*bailout_reason = kUnsupportedPhiUseOfConstVariable;
return false;
}
Run<HRedundantPhiEliminationPhase>();
if (!CheckArgumentsPhiUses()) {
*bailout_reason = kUnsupportedPhiUseOfArguments;
return false;
}
// Find and mark unreachable code to simplify optimizations, especially gvn,
// where unreachable code could unnecessarily defeat LICM.
Run<HMarkUnreachableBlocksPhase>();
if (FLAG_check_elimination) Run<HCheckEliminationPhase>();
if (FLAG_dead_code_elimination) Run<HDeadCodeEliminationPhase>();
if (FLAG_use_escape_analysis) Run<HEscapeAnalysisPhase>();
if (FLAG_load_elimination) Run<HLoadEliminationPhase>();
CollectPhis();
if (has_osr()) osr()->FinishOsrValues();
Run<HInferRepresentationPhase>();
// Remove HSimulate instructions that have turned out not to be needed
// after all by folding them into the following HSimulate.
// This must happen after inferring representations.
Run<HMergeRemovableSimulatesPhase>();
Run<HMarkDeoptimizeOnUndefinedPhase>();
Run<HRepresentationChangesPhase>();
Run<HInferTypesPhase>();
// Must be performed before canonicalization to ensure that Canonicalize
// will not remove semantically meaningful ToInt32 operations e.g. BIT_OR with
// zero.
if (FLAG_opt_safe_uint32_operations) Run<HUint32AnalysisPhase>();
if (FLAG_use_canonicalizing) Run<HCanonicalizePhase>();
if (FLAG_use_gvn) Run<HGlobalValueNumberingPhase>();
if (FLAG_use_range) Run<HRangeAnalysisPhase>();
Run<HComputeChangeUndefinedToNaN>();
Run<HComputeMinusZeroChecksPhase>();
// Eliminate redundant stack checks on backwards branches.
Run<HStackCheckEliminationPhase>();
if (FLAG_array_bounds_checks_elimination) Run<HBoundsCheckEliminationPhase>();
if (FLAG_array_bounds_checks_hoisting) Run<HBoundsCheckHoistingPhase>();
if (FLAG_array_index_dehoisting) Run<HDehoistIndexComputationsPhase>();
if (FLAG_dead_code_elimination) Run<HDeadCodeEliminationPhase>();
RestoreActualValues();
// Find unreachable code a second time, GVN and other optimizations may have
// made blocks unreachable that were previously reachable.
Run<HMarkUnreachableBlocksPhase>();
return true;
}
void HGraph::RestoreActualValues() {
HPhase phase("H_Restore actual values", this);
for (int block_index = 0; block_index < blocks()->length(); block_index++) {
HBasicBlock* block = blocks()->at(block_index);
#ifdef DEBUG
for (int i = 0; i < block->phis()->length(); i++) {
HPhi* phi = block->phis()->at(i);
ASSERT(phi->ActualValue() == phi);
}
#endif
for (HInstructionIterator it(block); !it.Done(); it.Advance()) {
HInstruction* instruction = it.Current();
if (instruction->ActualValue() != instruction) {
ASSERT(instruction->IsInformativeDefinition());
if (instruction->IsPurelyInformativeDefinition()) {
instruction->DeleteAndReplaceWith(instruction->RedefinedOperand());
} else {
instruction->ReplaceAllUsesWith(instruction->ActualValue());
}
}
}
}
}
void HGraphBuilder::PushAndAdd(HInstruction* instr) {
Push(instr);
AddInstruction(instr);
}
template <class Instruction>
HInstruction* HOptimizedGraphBuilder::PreProcessCall(Instruction* call) {
int count = call->argument_count();
ZoneList<HValue*> arguments(count, zone());
for (int i = 0; i < count; ++i) {
arguments.Add(Pop(), zone());
}
while (!arguments.is_empty()) {
Add<HPushArgument>(arguments.RemoveLast());
}
return call;
}
void HOptimizedGraphBuilder::SetUpScope(Scope* scope) {
// First special is HContext.
HInstruction* context = Add<HContext>();
environment()->BindContext(context);
HConstant* undefined_constant = HConstant::cast(Add<HConstant>(
isolate()->factory()->undefined_value()));
graph()->set_undefined_constant(undefined_constant);
// Create an arguments object containing the initial parameters. Set the
// initial values of parameters including "this" having parameter index 0.
ASSERT_EQ(scope->num_parameters() + 1, environment()->parameter_count());
HArgumentsObject* arguments_object =
New<HArgumentsObject>(environment()->parameter_count());
for (int i = 0; i < environment()->parameter_count(); ++i) {
HInstruction* parameter = Add<HParameter>(i);
arguments_object->AddArgument(parameter, zone());
environment()->Bind(i, parameter);
}
AddInstruction(arguments_object);
graph()->SetArgumentsObject(arguments_object);
// Initialize specials and locals to undefined.
for (int i = environment()->parameter_count() + 1;
i < environment()->length();
++i) {
environment()->Bind(i, undefined_constant);
}
// Handle the arguments and arguments shadow variables specially (they do
// not have declarations).
if (scope->arguments() != NULL) {
if (!scope->arguments()->IsStackAllocated()) {
return Bailout(kContextAllocatedArguments);
}
environment()->Bind(scope->arguments(),
graph()->GetArgumentsObject());
}
}
void HOptimizedGraphBuilder::VisitStatements(ZoneList<Statement*>* statements) {
for (int i = 0; i < statements->length(); i++) {
Statement* stmt = statements->at(i);
CHECK_ALIVE(Visit(stmt));
if (stmt->IsJump()) break;
}
}
void HOptimizedGraphBuilder::VisitBlock(Block* stmt) {
ASSERT(!HasStackOverflow());
ASSERT(current_block() != NULL);
ASSERT(current_block()->HasPredecessor());
if (stmt->scope() != NULL) {
return Bailout(kScopedBlock);
}
BreakAndContinueInfo break_info(stmt);
{ BreakAndContinueScope push(&break_info, this);
CHECK_BAILOUT(VisitStatements(stmt->statements()));
}
HBasicBlock* break_block = break_info.break_block();
if (break_block != NULL) {
if (current_block() != NULL) current_block()->Goto(break_block);
break_block->SetJoinId(stmt->ExitId());
set_current_block(break_block);
}
}
void HOptimizedGraphBuilder::VisitExpressionStatement(
ExpressionStatement* stmt) {
ASSERT(!HasStackOverflow());
ASSERT(current_block() != NULL);
ASSERT(current_block()->HasPredecessor());
VisitForEffect(stmt->expression());
}
void HOptimizedGraphBuilder::VisitEmptyStatement(EmptyStatement* stmt) {
ASSERT(!HasStackOverflow());
ASSERT(current_block() != NULL);
ASSERT(current_block()->HasPredecessor());
}
void HOptimizedGraphBuilder::VisitIfStatement(IfStatement* stmt) {
ASSERT(!HasStackOverflow());
ASSERT(current_block() != NULL);
ASSERT(current_block()->HasPredecessor());
if (stmt->condition()->ToBooleanIsTrue()) {
Add<HSimulate>(stmt->ThenId());
Visit(stmt->then_statement());
} else if (stmt->condition()->ToBooleanIsFalse()) {
Add<HSimulate>(stmt->ElseId());
Visit(stmt->else_statement());
} else {
HBasicBlock* cond_true = graph()->CreateBasicBlock();
HBasicBlock* cond_false = graph()->CreateBasicBlock();
CHECK_BAILOUT(VisitForControl(stmt->condition(), cond_true, cond_false));
if (cond_true->HasPredecessor()) {
cond_true->SetJoinId(stmt->ThenId());
set_current_block(cond_true);
CHECK_BAILOUT(Visit(stmt->then_statement()));
cond_true = current_block();
} else {
cond_true = NULL;
}
if (cond_false->HasPredecessor()) {
cond_false->SetJoinId(stmt->ElseId());
set_current_block(cond_false);
CHECK_BAILOUT(Visit(stmt->else_statement()));
cond_false = current_block();
} else {
cond_false = NULL;
}
HBasicBlock* join = CreateJoin(cond_true, cond_false, stmt->IfId());
set_current_block(join);
}
}
HBasicBlock* HOptimizedGraphBuilder::BreakAndContinueScope::Get(
BreakableStatement* stmt,
BreakType type,
int* drop_extra) {
*drop_extra = 0;
BreakAndContinueScope* current = this;
while (current != NULL && current->info()->target() != stmt) {
*drop_extra += current->info()->drop_extra();
current = current->next();
}
ASSERT(current != NULL); // Always found (unless stack is malformed).
if (type == BREAK) {
*drop_extra += current->info()->drop_extra();
}
HBasicBlock* block = NULL;
switch (type) {
case BREAK:
block = current->info()->break_block();
if (block == NULL) {
block = current->owner()->graph()->CreateBasicBlock();
current->info()->set_break_block(block);
}
break;
case CONTINUE:
block = current->info()->continue_block();
if (block == NULL) {
block = current->owner()->graph()->CreateBasicBlock();
current->info()->set_continue_block(block);
}
break;
}
return block;
}
void HOptimizedGraphBuilder::VisitContinueStatement(
ContinueStatement* stmt) {
ASSERT(!HasStackOverflow());
ASSERT(current_block() != NULL);
ASSERT(current_block()->HasPredecessor());
int drop_extra = 0;
HBasicBlock* continue_block = break_scope()->Get(
stmt->target(), BreakAndContinueScope::CONTINUE, &drop_extra);
Drop(drop_extra);
current_block()->Goto(continue_block);
set_current_block(NULL);
}
void HOptimizedGraphBuilder::VisitBreakStatement(BreakStatement* stmt) {
ASSERT(!HasStackOverflow());
ASSERT(current_block() != NULL);
ASSERT(current_block()->HasPredecessor());
int drop_extra = 0;
HBasicBlock* break_block = break_scope()->Get(
stmt->target(), BreakAndContinueScope::BREAK, &drop_extra);
Drop(drop_extra);
current_block()->Goto(break_block);
set_current_block(NULL);
}
void HOptimizedGraphBuilder::VisitReturnStatement(ReturnStatement* stmt) {
ASSERT(!HasStackOverflow());
ASSERT(current_block() != NULL);
ASSERT(current_block()->HasPredecessor());
FunctionState* state = function_state();
AstContext* context = call_context();
if (context == NULL) {
// Not an inlined return, so an actual one.
CHECK_ALIVE(VisitForValue(stmt->expression()));
HValue* result = environment()->Pop();
Add<HReturn>(result);
} else if (state->inlining_kind() == CONSTRUCT_CALL_RETURN) {
// Return from an inlined construct call. In a test context the return value
// will always evaluate to true, in a value context the return value needs
// to be a JSObject.
if (context->IsTest()) {
TestContext* test = TestContext::cast(context);
CHECK_ALIVE(VisitForEffect(stmt->expression()));
current_block()->Goto(test->if_true(), state);
} else if (context->IsEffect()) {
CHECK_ALIVE(VisitForEffect(stmt->expression()));
current_block()->Goto(function_return(), state);
} else {
ASSERT(context->IsValue());
CHECK_ALIVE(VisitForValue(stmt->expression()));
HValue* return_value = Pop();
HValue* receiver = environment()->arguments_environment()->Lookup(0);
HHasInstanceTypeAndBranch* typecheck =
new(zone()) HHasInstanceTypeAndBranch(return_value,
FIRST_SPEC_OBJECT_TYPE,
LAST_SPEC_OBJECT_TYPE);
HBasicBlock* if_spec_object = graph()->CreateBasicBlock();
HBasicBlock* not_spec_object = graph()->CreateBasicBlock();
typecheck->SetSuccessorAt(0, if_spec_object);
typecheck->SetSuccessorAt(1, not_spec_object);
current_block()->Finish(typecheck);
if_spec_object->AddLeaveInlined(return_value, state);
not_spec_object->AddLeaveInlined(receiver, state);
}
} else if (state->inlining_kind() == SETTER_CALL_RETURN) {
// Return from an inlined setter call. The returned value is never used, the
// value of an assignment is always the value of the RHS of the assignment.
CHECK_ALIVE(VisitForEffect(stmt->expression()));
if (context->IsTest()) {
HValue* rhs = environment()->arguments_environment()->Lookup(1);
context->ReturnValue(rhs);
} else if (context->IsEffect()) {
current_block()->Goto(function_return(), state);
} else {
ASSERT(context->IsValue());
HValue* rhs = environment()->arguments_environment()->Lookup(1);
current_block()->AddLeaveInlined(rhs, state);
}
} else {
// Return from a normal inlined function. Visit the subexpression in the
// expression context of the call.
if (context->IsTest()) {
TestContext* test = TestContext::cast(context);
VisitForControl(stmt->expression(), test->if_true(), test->if_false());
} else if (context->IsEffect()) {
CHECK_ALIVE(VisitForEffect(stmt->expression()));
current_block()->Goto(function_return(), state);
} else {
ASSERT(context->IsValue());
CHECK_ALIVE(VisitForValue(stmt->expression()));
current_block()->AddLeaveInlined(Pop(), state);
}
}
set_current_block(NULL);
}
void HOptimizedGraphBuilder::VisitWithStatement(WithStatement* stmt) {
ASSERT(!HasStackOverflow());
ASSERT(current_block() != NULL);
ASSERT(current_block()->HasPredecessor());
return Bailout(kWithStatement);
}
void HOptimizedGraphBuilder::VisitSwitchStatement(SwitchStatement* stmt) {
ASSERT(!HasStackOverflow());
ASSERT(current_block() != NULL);
ASSERT(current_block()->HasPredecessor());
// We only optimize switch statements with smi-literal smi comparisons,
// with a bounded number of clauses.
const int kCaseClauseLimit = 128;
ZoneList<CaseClause*>* clauses = stmt->cases();
int clause_count = clauses->length();
if (clause_count > kCaseClauseLimit) {
return Bailout(kSwitchStatementTooManyClauses);
}
ASSERT(stmt->switch_type() != SwitchStatement::UNKNOWN_SWITCH);
if (stmt->switch_type() == SwitchStatement::GENERIC_SWITCH) {
return Bailout(kSwitchStatementMixedOrNonLiteralSwitchLabels);
}
CHECK_ALIVE(VisitForValue(stmt->tag()));
Add<HSimulate>(stmt->EntryId());
HValue* tag_value = Pop();
HBasicBlock* first_test_block = current_block();
HUnaryControlInstruction* string_check = NULL;
HBasicBlock* not_string_block = NULL;
// Test switch's tag value if all clauses are string literals
if (stmt->switch_type() == SwitchStatement::STRING_SWITCH) {
first_test_block = graph()->CreateBasicBlock();
not_string_block = graph()->CreateBasicBlock();
string_check = New<HIsStringAndBranch>(
tag_value, first_test_block, not_string_block);
current_block()->Finish(string_check);
set_current_block(first_test_block);
}
// 1. Build all the tests, with dangling true branches
BailoutId default_id = BailoutId::None();
for (int i = 0; i < clause_count; ++i) {
CaseClause* clause = clauses->at(i);
if (clause->is_default()) {
default_id = clause->EntryId();
continue;
}
// Generate a compare and branch.
CHECK_ALIVE(VisitForValue(clause->label()));
HValue* label_value = Pop();
HBasicBlock* next_test_block = graph()->CreateBasicBlock();
HBasicBlock* body_block = graph()->CreateBasicBlock();
HControlInstruction* compare;
if (stmt->switch_type() == SwitchStatement::SMI_SWITCH) {
if (!clause->compare_type()->Is(Type::Smi())) {
Add<HDeoptimize>("Non-smi switch type", Deoptimizer::SOFT);
}
HCompareNumericAndBranch* compare_ =
New<HCompareNumericAndBranch>(tag_value,
label_value,
Token::EQ_STRICT);
compare_->set_observed_input_representation(
Representation::Smi(), Representation::Smi());
compare = compare_;
} else {
compare = New<HStringCompareAndBranch>(tag_value,
label_value,
Token::EQ_STRICT);
}
compare->SetSuccessorAt(0, body_block);
compare->SetSuccessorAt(1, next_test_block);
current_block()->Finish(compare);
set_current_block(next_test_block);
}
// Save the current block to use for the default or to join with the
// exit.
HBasicBlock* last_block = current_block();
if (not_string_block != NULL) {
BailoutId join_id = !default_id.IsNone() ? default_id : stmt->ExitId();
last_block = CreateJoin(last_block, not_string_block, join_id);
}
// 2. Loop over the clauses and the linked list of tests in lockstep,
// translating the clause bodies.
HBasicBlock* curr_test_block = first_test_block;
HBasicBlock* fall_through_block = NULL;
BreakAndContinueInfo break_info(stmt);
{ BreakAndContinueScope push(&break_info, this);
for (int i = 0; i < clause_count; ++i) {
CaseClause* clause = clauses->at(i);
// Identify the block where normal (non-fall-through) control flow
// goes to.
HBasicBlock* normal_block = NULL;
if (clause->is_default()) {
if (last_block != NULL) {
normal_block = last_block;
last_block = NULL; // Cleared to indicate we've handled it.
}
} else {
// If the current test block is deoptimizing due to an unhandled clause
// of the switch, the test instruction is in the next block since the
// deopt must end the current block.
if (curr_test_block->IsDeoptimizing()) {
ASSERT(curr_test_block->end()->SecondSuccessor() == NULL);
curr_test_block = curr_test_block->end()->FirstSuccessor();
}
normal_block = curr_test_block->end()->FirstSuccessor();
curr_test_block = curr_test_block->end()->SecondSuccessor();
}
// Identify a block to emit the body into.
if (normal_block == NULL) {
if (fall_through_block == NULL) {
// (a) Unreachable.
if (clause->is_default()) {
continue; // Might still be reachable clause bodies.
} else {
break;
}
} else {
// (b) Reachable only as fall through.
set_current_block(fall_through_block);
}
} else if (fall_through_block == NULL) {
// (c) Reachable only normally.
set_current_block(normal_block);
} else {
// (d) Reachable both ways.
HBasicBlock* join = CreateJoin(fall_through_block,
normal_block,
clause->EntryId());
set_current_block(join);
}
CHECK_BAILOUT(VisitStatements(clause->statements()));
fall_through_block = current_block();
}
}
// Create an up-to-3-way join. Use the break block if it exists since
// it's already a join block.
HBasicBlock* break_block = break_info.break_block();
if (break_block == NULL) {
set_current_block(CreateJoin(fall_through_block,
last_block,
stmt->ExitId()));
} else {
if (fall_through_block != NULL) fall_through_block->Goto(break_block);
if (last_block != NULL) last_block->Goto(break_block);
break_block->SetJoinId(stmt->ExitId());
set_current_block(break_block);
}
}
void HOptimizedGraphBuilder::VisitLoopBody(IterationStatement* stmt,
HBasicBlock* loop_entry,
BreakAndContinueInfo* break_info) {
BreakAndContinueScope push(break_info, this);
Add<HSimulate>(stmt->StackCheckId());
HStackCheck* stack_check =
HStackCheck::cast(Add<HStackCheck>(HStackCheck::kBackwardsBranch));
ASSERT(loop_entry->IsLoopHeader());
loop_entry->loop_information()->set_stack_check(stack_check);
CHECK_BAILOUT(Visit(stmt->body()));
}
void HOptimizedGraphBuilder::VisitDoWhileStatement(DoWhileStatement* stmt) {
ASSERT(!HasStackOverflow());
ASSERT(current_block() != NULL);
ASSERT(current_block()->HasPredecessor());
ASSERT(current_block() != NULL);
HBasicBlock* loop_entry = BuildLoopEntry(stmt);
BreakAndContinueInfo break_info(stmt);
CHECK_BAILOUT(VisitLoopBody(stmt, loop_entry, &break_info));
HBasicBlock* body_exit =
JoinContinue(stmt, current_block(), break_info.continue_block());
HBasicBlock* loop_successor = NULL;
if (body_exit != NULL && !stmt->cond()->ToBooleanIsTrue()) {
set_current_block(body_exit);
// The block for a true condition, the actual predecessor block of the
// back edge.
body_exit = graph()->CreateBasicBlock();
loop_successor = graph()->CreateBasicBlock();
CHECK_BAILOUT(VisitForControl(stmt->cond(), body_exit, loop_successor));
if (body_exit->HasPredecessor()) {
body_exit->SetJoinId(stmt->BackEdgeId());
} else {
body_exit = NULL;
}
if (loop_successor->HasPredecessor()) {
loop_successor->SetJoinId(stmt->ExitId());
} else {
loop_successor = NULL;
}
}
HBasicBlock* loop_exit = CreateLoop(stmt,
loop_entry,
body_exit,
loop_successor,
break_info.break_block());
set_current_block(loop_exit);
}
void HOptimizedGraphBuilder::VisitWhileStatement(WhileStatement* stmt) {
ASSERT(!HasStackOverflow());
ASSERT(current_block() != NULL);
ASSERT(current_block()->HasPredecessor());
ASSERT(current_block() != NULL);
HBasicBlock* loop_entry = BuildLoopEntry(stmt);
// If the condition is constant true, do not generate a branch.
HBasicBlock* loop_successor = NULL;
if (!stmt->cond()->ToBooleanIsTrue()) {
HBasicBlock* body_entry = graph()->CreateBasicBlock();
loop_successor = graph()->CreateBasicBlock();
CHECK_BAILOUT(VisitForControl(stmt->cond(), body_entry, loop_successor));
if (body_entry->HasPredecessor()) {
body_entry->SetJoinId(stmt->BodyId());
set_current_block(body_entry);
}
if (loop_successor->HasPredecessor()) {
loop_successor->SetJoinId(stmt->ExitId());
} else {
loop_successor = NULL;
}
}
BreakAndContinueInfo break_info(stmt);
if (current_block() != NULL) {
CHECK_BAILOUT(VisitLoopBody(stmt, loop_entry, &break_info));
}
HBasicBlock* body_exit =
JoinContinue(stmt, current_block(), break_info.continue_block());
HBasicBlock* loop_exit = CreateLoop(stmt,
loop_entry,
body_exit,
loop_successor,
break_info.break_block());
set_current_block(loop_exit);
}
void HOptimizedGraphBuilder::VisitForStatement(ForStatement* stmt) {
ASSERT(!HasStackOverflow());
ASSERT(current_block() != NULL);
ASSERT(current_block()->HasPredecessor());
if (stmt->init() != NULL) {
CHECK_ALIVE(Visit(stmt->init()));
}
ASSERT(current_block() != NULL);
HBasicBlock* loop_entry = BuildLoopEntry(stmt);
HBasicBlock* loop_successor = NULL;
if (stmt->cond() != NULL) {
HBasicBlock* body_entry = graph()->CreateBasicBlock();
loop_successor = graph()->CreateBasicBlock();
CHECK_BAILOUT(VisitForControl(stmt->cond(), body_entry, loop_successor));
if (body_entry->HasPredecessor()) {
body_entry->SetJoinId(stmt->BodyId());
set_current_block(body_entry);
}
if (loop_successor->HasPredecessor()) {
loop_successor->SetJoinId(stmt->ExitId());
} else {
loop_successor = NULL;
}
}
BreakAndContinueInfo break_info(stmt);
if (current_block() != NULL) {
CHECK_BAILOUT(VisitLoopBody(stmt, loop_entry, &break_info));
}
HBasicBlock* body_exit =
JoinContinue(stmt, current_block(), break_info.continue_block());
if (stmt->next() != NULL && body_exit != NULL) {
set_current_block(body_exit);
CHECK_BAILOUT(Visit(stmt->next()));
body_exit = current_block();
}
HBasicBlock* loop_exit = CreateLoop(stmt,
loop_entry,
body_exit,
loop_successor,
break_info.break_block());
set_current_block(loop_exit);
}
void HOptimizedGraphBuilder::VisitForInStatement(ForInStatement* stmt) {
ASSERT(!HasStackOverflow());
ASSERT(current_block() != NULL);
ASSERT(current_block()->HasPredecessor());
if (!FLAG_optimize_for_in) {
return Bailout(kForInStatementOptimizationIsDisabled);
}
if (stmt->for_in_type() != ForInStatement::FAST_FOR_IN) {
return Bailout(kForInStatementIsNotFastCase);
}
if (!stmt->each()->IsVariableProxy() ||
!stmt->each()->AsVariableProxy()->var()->IsStackLocal()) {
return Bailout(kForInStatementWithNonLocalEachVariable);
}
Variable* each_var = stmt->each()->AsVariableProxy()->var();
CHECK_ALIVE(VisitForValue(stmt->enumerable()));
HValue* enumerable = Top(); // Leave enumerable at the top.
HInstruction* map = Add<HForInPrepareMap>(enumerable);
Add<HSimulate>(stmt->PrepareId());
HInstruction* array = Add<HForInCacheArray>(
enumerable, map, DescriptorArray::kEnumCacheBridgeCacheIndex);
HInstruction* enum_length = Add<HMapEnumLength>(map);
HInstruction* start_index = Add<HConstant>(0);
Push(map);
Push(array);
Push(enum_length);
Push(start_index);
HInstruction* index_cache = Add<HForInCacheA