blob: 31fcd4ca46549f5adc575766f2dce2ec90186da1 [file] [log] [blame]
// Copyright 2013 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
#include "src/hydrogen.h"
#include <sstream>
#include "src/v8.h"
#include "src/allocation-site-scopes.h"
#include "src/ast-numbering.h"
#include "src/full-codegen.h"
#include "src/hydrogen-bce.h"
#include "src/hydrogen-bch.h"
#include "src/hydrogen-canonicalize.h"
#include "src/hydrogen-check-elimination.h"
#include "src/hydrogen-dce.h"
#include "src/hydrogen-dehoist.h"
#include "src/hydrogen-environment-liveness.h"
#include "src/hydrogen-escape-analysis.h"
#include "src/hydrogen-gvn.h"
#include "src/hydrogen-infer-representation.h"
#include "src/hydrogen-infer-types.h"
#include "src/hydrogen-load-elimination.h"
#include "src/hydrogen-mark-deoptimize.h"
#include "src/hydrogen-mark-unreachable.h"
#include "src/hydrogen-osr.h"
#include "src/hydrogen-range-analysis.h"
#include "src/hydrogen-redundant-phi.h"
#include "src/hydrogen-removable-simulates.h"
#include "src/hydrogen-representation-changes.h"
#include "src/hydrogen-sce.h"
#include "src/hydrogen-store-elimination.h"
#include "src/hydrogen-uint32-analysis.h"
#include "src/ic/call-optimization.h"
#include "src/ic/ic.h"
// GetRootConstructor
#include "src/ic/ic-inl.h"
#include "src/lithium-allocator.h"
#include "src/parser.h"
#include "src/runtime/runtime.h"
#include "src/scopeinfo.h"
#include "src/typing.h"
#if V8_TARGET_ARCH_IA32
#include "src/ia32/lithium-codegen-ia32.h" // NOLINT
#elif V8_TARGET_ARCH_X64
#include "src/x64/lithium-codegen-x64.h" // NOLINT
#elif V8_TARGET_ARCH_ARM64
#include "src/arm64/lithium-codegen-arm64.h" // NOLINT
#elif V8_TARGET_ARCH_ARM
#include "src/arm/lithium-codegen-arm.h" // NOLINT
#elif V8_TARGET_ARCH_MIPS
#include "src/mips/lithium-codegen-mips.h" // NOLINT
#elif V8_TARGET_ARCH_MIPS64
#include "src/mips64/lithium-codegen-mips64.h" // NOLINT
#elif V8_TARGET_ARCH_X87
#include "src/x87/lithium-codegen-x87.h" // NOLINT
#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),
is_ordered_(false) { }
Isolate* HBasicBlock::isolate() const {
return graph_->isolate();
}
void HBasicBlock::MarkUnreachable() {
is_reachable_ = false;
}
void HBasicBlock::AttachLoopInformation() {
DCHECK(!IsLoopHeader());
loop_information_ = new(zone()) HLoopInformation(this, zone());
}
void HBasicBlock::DetachLoopInformation() {
DCHECK(IsLoopHeader());
loop_information_ = NULL;
}
void HBasicBlock::AddPhi(HPhi* phi) {
DCHECK(!IsStartBlock());
phis_.Add(phi, zone());
phi->SetBlock(this);
}
void HBasicBlock::RemovePhi(HPhi* phi) {
DCHECK(phi->block() == this);
DCHECK(phis_.Contains(phi));
phi->Kill();
phis_.RemoveElement(phi);
phi->SetBlock(NULL);
}
void HBasicBlock::AddInstruction(HInstruction* instr,
HSourcePosition position) {
DCHECK(!IsStartBlock() || !IsFinished());
DCHECK(!instr->IsLinked());
DCHECK(!IsFinished());
if (!position.IsUnknown()) {
instr->set_position(position);
}
if (first_ == NULL) {
DCHECK(last_environment() != NULL);
DCHECK(!last_environment()->ast_id().IsNone());
HBlockEntry* entry = new(zone()) HBlockEntry();
entry->InitializeAsFirst(this);
if (!position.IsUnknown()) {
entry->set_position(position);
} else {
DCHECK(!FLAG_hydrogen_track_positions ||
!graph()->info()->IsOptimizing() || instr->IsAbnormalExit());
}
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) {
DCHECK(HasEnvironment());
HEnvironment* environment = last_environment();
DCHECK(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, HSourcePosition position) {
DCHECK(!IsFinished());
AddInstruction(end, position);
end_ = end;
for (HSuccessorIterator it(end); !it.Done(); it.Advance()) {
it.Current()->RegisterPredecessor(this);
}
}
void HBasicBlock::Goto(HBasicBlock* block,
HSourcePosition position,
FunctionState* state,
bool add_simulate) {
bool drop_extra = state != NULL &&
state->inlining_kind() == NORMAL_RETURN;
if (block->IsInlineReturnTarget()) {
HEnvironment* env = last_environment();
int argument_count = env->arguments_environment()->parameter_count();
AddInstruction(new(zone())
HLeaveInlined(state->entry(), argument_count),
position);
UpdateEnvironment(last_environment()->DiscardInlined(drop_extra));
}
if (add_simulate) AddNewSimulate(BailoutId::None(), position);
HGoto* instr = new(zone()) HGoto(block);
Finish(instr, position);
}
void HBasicBlock::AddLeaveInlined(HValue* return_value,
FunctionState* state,
HSourcePosition position) {
HBasicBlock* target = state->function_return();
bool drop_extra = state->inlining_kind() == NORMAL_RETURN;
DCHECK(target->IsInlineReturnTarget());
DCHECK(return_value != NULL);
HEnvironment* env = last_environment();
int argument_count = env->arguments_environment()->parameter_count();
AddInstruction(new(zone()) HLeaveInlined(state->entry(), argument_count),
position);
UpdateEnvironment(last_environment()->DiscardInlined(drop_extra));
last_environment()->Push(return_value);
AddNewSimulate(BailoutId::None(), position);
HGoto* instr = new(zone()) HGoto(target);
Finish(instr, position);
}
void HBasicBlock::SetInitialEnvironment(HEnvironment* env) {
DCHECK(!HasEnvironment());
DCHECK(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();
DCHECK(length > 0);
for (int i = 0; i < length; i++) {
HBasicBlock* predecessor = predecessors_[i];
DCHECK(predecessor->end()->IsGoto());
HSimulate* simulate = HSimulate::cast(predecessor->end()->previous());
DCHECK(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;
}
bool HBasicBlock::EqualToOrDominates(HBasicBlock* other) const {
if (this == other) return true;
return Dominates(other);
}
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) {
DCHECK(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::MarkSuccEdgeUnreachable(int succ) {
DCHECK(IsFinished());
HBasicBlock* succ_block = end()->SuccessorAt(succ);
DCHECK(succ_block->predecessors()->length() == 1);
succ_block->MarkUnreachable();
}
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).
DCHECK(IsLoopHeader() || first_ == NULL);
HEnvironment* incoming_env = pred->last_environment();
if (IsLoopHeader()) {
DCHECK(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()) {
DCHECK(!IsLoopHeader());
SetInitialEnvironment(pred->last_environment()->Copy());
}
predecessors_.Add(pred, zone());
}
void HBasicBlock::AddDominatedBlock(HBasicBlock* block) {
DCHECK(!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();
}
DCHECK(first != NULL && second != NULL);
}
if (dominator_ != first) {
DCHECK(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.
DCHECK(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.
DCHECK(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.
DCHECK(IsFinished());
DCHECK(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) {
DCHECK(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();
DCHECK(current != NULL && current->IsBlockEntry());
while (current != NULL) {
DCHECK((current->next() == NULL) == current->IsControlInstruction());
DCHECK(current->block() == block);
current->Verify();
current = current->next();
}
// Check that successors are correctly set.
HBasicBlock* first = block->end()->FirstSuccessor();
HBasicBlock* second = block->end()->SecondSuccessor();
DCHECK(second == NULL || first != NULL);
// Check that the predecessor array is correct.
if (first != NULL) {
DCHECK(first->predecessors()->Contains(block));
if (second != NULL) {
DCHECK(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);
DCHECK(predecessor->end()->IsGoto() ||
predecessor->end()->IsDeoptimize());
DCHECK(predecessor->last_environment()->ast_id() == id);
}
}
}
// Check special property of first block to have no predecessors.
DCHECK(blocks_.at(0)->predecessors()->is_empty());
if (do_full_verify) {
// Check that the graph is fully connected.
ReachabilityAnalyzer analyzer(entry_block_, blocks_.length(), NULL);
DCHECK(analyzer.visited_count() == blocks_.length());
// Check that entry block dominator is NULL.
DCHECK(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.
DCHECK(i == 0);
} else {
// Assert that block is unreachable if dominator must not be visited.
ReachabilityAnalyzer dominator_analyzer(entry_block_,
blocks_.length(),
block->dominator());
DCHECK(!dominator_analyzer.reachable()->Contains(block->block_id()));
}
}
}
}
#endif
HConstant* HGraph::GetConstant(SetOncePointer<HConstant>* pointer,
int32_t value) {
if (!pointer->is_set()) {
// Can't pass GetInvalidContext() to HConstant::New, because that will
// recursively call GetConstant
HConstant* constant = HConstant::New(zone(), NULL, value);
constant->InsertAfter(entry_block()->first());
pointer->set(constant);
return constant;
}
return ReinsertConstantIfNecessary(pointer->get());
}
HConstant* HGraph::ReinsertConstantIfNecessary(HConstant* constant) {
if (!constant->IsLinked()) {
// The constant was removed from the graph. Reinsert.
constant->ClearFlag(HValue::kIsDead);
constant->InsertAfter(entry_block()->first());
}
return constant;
}
HConstant* HGraph::GetConstant0() {
return GetConstant(&constant_0_, 0);
}
HConstant* HGraph::GetConstant1() {
return GetConstant(&constant_1_, 1);
}
HConstant* HGraph::GetConstantMinus1() {
return GetConstant(&constant_minus1_, -1);
}
#define DEFINE_GET_CONSTANT(Name, name, type, htype, boolean_value) \
HConstant* HGraph::GetConstant##Name() { \
if (!constant_##name##_.is_set()) { \
HConstant* constant = new(zone()) HConstant( \
Unique<Object>::CreateImmovable(isolate()->factory()->name##_value()), \
Unique<Map>::CreateImmovable(isolate()->factory()->type##_map()), \
false, \
Representation::Tagged(), \
htype, \
true, \
boolean_value, \
false, \
ODDBALL_TYPE); \
constant->InsertAfter(entry_block()->first()); \
constant_##name##_.set(constant); \
} \
return ReinsertConstantIfNecessary(constant_##name##_.get()); \
}
DEFINE_GET_CONSTANT(Undefined, undefined, undefined, HType::Undefined(), false)
DEFINE_GET_CONSTANT(True, true, boolean, HType::Boolean(), true)
DEFINE_GET_CONSTANT(False, false, boolean, HType::Boolean(), false)
DEFINE_GET_CONSTANT(Hole, the_hole, the_hole, HType::None(), false)
DEFINE_GET_CONSTANT(Null, null, null, HType::Null(), false)
#undef DEFINE_GET_CONSTANT
#define DEFINE_IS_CONSTANT(Name, name) \
bool HGraph::IsConstant##Name(HConstant* constant) { \
return constant_##name##_.is_set() && constant == constant_##name##_.get(); \
}
DEFINE_IS_CONSTANT(Undefined, undefined)
DEFINE_IS_CONSTANT(0, 0)
DEFINE_IS_CONSTANT(1, 1)
DEFINE_IS_CONSTANT(Minus1, minus1)
DEFINE_IS_CONSTANT(True, true)
DEFINE_IS_CONSTANT(False, false)
DEFINE_IS_CONSTANT(Hole, the_hole)
DEFINE_IS_CONSTANT(Null, null)
#undef DEFINE_IS_CONSTANT
HConstant* HGraph::GetInvalidContext() {
return GetConstant(&constant_invalid_context_, 0xFFFFC0C7);
}
bool HGraph::IsStandardConstant(HConstant* constant) {
if (IsConstantUndefined(constant)) return true;
if (IsConstant0(constant)) return true;
if (IsConstant1(constant)) return true;
if (IsConstantMinus1(constant)) return true;
if (IsConstantTrue(constant)) return true;
if (IsConstantFalse(constant)) return true;
if (IsConstantHole(constant)) return true;
if (IsConstantNull(constant)) return true;
return false;
}
HGraphBuilder::IfBuilder::IfBuilder() : builder_(NULL), needs_compare_(true) {}
HGraphBuilder::IfBuilder::IfBuilder(HGraphBuilder* builder)
: needs_compare_(true) {
Initialize(builder);
}
HGraphBuilder::IfBuilder::IfBuilder(HGraphBuilder* builder,
HIfContinuation* continuation)
: needs_compare_(false), first_true_block_(NULL), first_false_block_(NULL) {
InitializeDontCreateBlocks(builder);
continuation->Continue(&first_true_block_, &first_false_block_);
}
void HGraphBuilder::IfBuilder::InitializeDontCreateBlocks(
HGraphBuilder* builder) {
builder_ = builder;
finished_ = false;
did_then_ = false;
did_else_ = false;
did_else_if_ = false;
did_and_ = false;
did_or_ = false;
captured_ = false;
pending_merge_block_ = false;
split_edge_merge_block_ = NULL;
merge_at_join_blocks_ = NULL;
normal_merge_at_join_block_count_ = 0;
deopt_merge_at_join_block_count_ = 0;
}
void HGraphBuilder::IfBuilder::Initialize(HGraphBuilder* builder) {
InitializeDontCreateBlocks(builder);
HEnvironment* env = builder->environment();
first_true_block_ = builder->CreateBasicBlock(env->Copy());
first_false_block_ = builder->CreateBasicBlock(env->Copy());
}
HControlInstruction* HGraphBuilder::IfBuilder::AddCompare(
HControlInstruction* compare) {
DCHECK(did_then_ == did_else_);
if (did_else_) {
// Handle if-then-elseif
did_else_if_ = true;
did_else_ = false;
did_then_ = false;
did_and_ = false;
did_or_ = false;
pending_merge_block_ = false;
split_edge_merge_block_ = NULL;
HEnvironment* env = builder()->environment();
first_true_block_ = builder()->CreateBasicBlock(env->Copy());
first_false_block_ = builder()->CreateBasicBlock(env->Copy());
}
if (split_edge_merge_block_ != NULL) {
HEnvironment* env = first_false_block_->last_environment();
HBasicBlock* split_edge = builder()->CreateBasicBlock(env->Copy());
if (did_or_) {
compare->SetSuccessorAt(0, split_edge);
compare->SetSuccessorAt(1, first_false_block_);
} else {
compare->SetSuccessorAt(0, first_true_block_);
compare->SetSuccessorAt(1, split_edge);
}
builder()->GotoNoSimulate(split_edge, split_edge_merge_block_);
} else {
compare->SetSuccessorAt(0, first_true_block_);
compare->SetSuccessorAt(1, first_false_block_);
}
builder()->FinishCurrentBlock(compare);
needs_compare_ = false;
return compare;
}
void HGraphBuilder::IfBuilder::Or() {
DCHECK(!needs_compare_);
DCHECK(!did_and_);
did_or_ = true;
HEnvironment* env = first_false_block_->last_environment();
if (split_edge_merge_block_ == NULL) {
split_edge_merge_block_ = builder()->CreateBasicBlock(env->Copy());
builder()->GotoNoSimulate(first_true_block_, split_edge_merge_block_);
first_true_block_ = split_edge_merge_block_;
}
builder()->set_current_block(first_false_block_);
first_false_block_ = builder()->CreateBasicBlock(env->Copy());
}
void HGraphBuilder::IfBuilder::And() {
DCHECK(!needs_compare_);
DCHECK(!did_or_);
did_and_ = true;
HEnvironment* env = first_false_block_->last_environment();
if (split_edge_merge_block_ == NULL) {
split_edge_merge_block_ = builder()->CreateBasicBlock(env->Copy());
builder()->GotoNoSimulate(first_false_block_, split_edge_merge_block_);
first_false_block_ = split_edge_merge_block_;
}
builder()->set_current_block(first_true_block_);
first_true_block_ = builder()->CreateBasicBlock(env->Copy());
}
void HGraphBuilder::IfBuilder::CaptureContinuation(
HIfContinuation* continuation) {
DCHECK(!did_else_if_);
DCHECK(!finished_);
DCHECK(!captured_);
HBasicBlock* true_block = NULL;
HBasicBlock* false_block = NULL;
Finish(&true_block, &false_block);
DCHECK(true_block != NULL);
DCHECK(false_block != NULL);
continuation->Capture(true_block, false_block);
captured_ = true;
builder()->set_current_block(NULL);
End();
}
void HGraphBuilder::IfBuilder::JoinContinuation(HIfContinuation* continuation) {
DCHECK(!did_else_if_);
DCHECK(!finished_);
DCHECK(!captured_);
HBasicBlock* true_block = NULL;
HBasicBlock* false_block = NULL;
Finish(&true_block, &false_block);
merge_at_join_blocks_ = NULL;
if (true_block != NULL && !true_block->IsFinished()) {
DCHECK(continuation->IsTrueReachable());
builder()->GotoNoSimulate(true_block, continuation->true_branch());
}
if (false_block != NULL && !false_block->IsFinished()) {
DCHECK(continuation->IsFalseReachable());
builder()->GotoNoSimulate(false_block, continuation->false_branch());
}
captured_ = true;
End();
}
void HGraphBuilder::IfBuilder::Then() {
DCHECK(!captured_);
DCHECK(!finished_);
did_then_ = true;
if (needs_compare_) {
// Handle if's without any expressions, they jump directly to the "else"
// branch. However, we must pretend that the "then" branch is reachable,
// so that the graph builder visits it and sees any live range extending
// constructs within it.
HConstant* constant_false = builder()->graph()->GetConstantFalse();
ToBooleanStub::Types boolean_type = ToBooleanStub::Types();
boolean_type.Add(ToBooleanStub::BOOLEAN);
HBranch* branch = builder()->New<HBranch>(
constant_false, boolean_type, first_true_block_, first_false_block_);
builder()->FinishCurrentBlock(branch);
}
builder()->set_current_block(first_true_block_);
pending_merge_block_ = true;
}
void HGraphBuilder::IfBuilder::Else() {
DCHECK(did_then_);
DCHECK(!captured_);
DCHECK(!finished_);
AddMergeAtJoinBlock(false);
builder()->set_current_block(first_false_block_);
pending_merge_block_ = true;
did_else_ = true;
}
void HGraphBuilder::IfBuilder::Deopt(const char* reason) {
DCHECK(did_then_);
builder()->Add<HDeoptimize>(reason, Deoptimizer::EAGER);
AddMergeAtJoinBlock(true);
}
void HGraphBuilder::IfBuilder::Return(HValue* value) {
HValue* parameter_count = builder()->graph()->GetConstantMinus1();
builder()->FinishExitCurrentBlock(
builder()->New<HReturn>(value, parameter_count));
AddMergeAtJoinBlock(false);
}
void HGraphBuilder::IfBuilder::AddMergeAtJoinBlock(bool deopt) {
if (!pending_merge_block_) return;
HBasicBlock* block = builder()->current_block();
DCHECK(block == NULL || !block->IsFinished());
MergeAtJoinBlock* record = new (builder()->zone())
MergeAtJoinBlock(block, deopt, merge_at_join_blocks_);
merge_at_join_blocks_ = record;
if (block != NULL) {
DCHECK(block->end() == NULL);
if (deopt) {
normal_merge_at_join_block_count_++;
} else {
deopt_merge_at_join_block_count_++;
}
}
builder()->set_current_block(NULL);
pending_merge_block_ = false;
}
void HGraphBuilder::IfBuilder::Finish() {
DCHECK(!finished_);
if (!did_then_) {
Then();
}
AddMergeAtJoinBlock(false);
if (!did_else_) {
Else();
AddMergeAtJoinBlock(false);
}
finished_ = true;
}
void HGraphBuilder::IfBuilder::Finish(HBasicBlock** then_continuation,
HBasicBlock** else_continuation) {
Finish();
MergeAtJoinBlock* else_record = merge_at_join_blocks_;
if (else_continuation != NULL) {
*else_continuation = else_record->block_;
}
MergeAtJoinBlock* then_record = else_record->next_;
if (then_continuation != NULL) {
*then_continuation = then_record->block_;
}
DCHECK(then_record->next_ == NULL);
}
void HGraphBuilder::IfBuilder::End() {
if (captured_) return;
Finish();
int total_merged_blocks = normal_merge_at_join_block_count_ +
deopt_merge_at_join_block_count_;
DCHECK(total_merged_blocks >= 1);
HBasicBlock* merge_block =
total_merged_blocks == 1 ? NULL : builder()->graph()->CreateBasicBlock();
// Merge non-deopt blocks first to ensure environment has right size for
// padding.
MergeAtJoinBlock* current = merge_at_join_blocks_;
while (current != NULL) {
if (!current->deopt_ && current->block_ != NULL) {
// If there is only one block that makes it through to the end of the
// if, then just set it as the current block and continue rather then
// creating an unnecessary merge block.
if (total_merged_blocks == 1) {
builder()->set_current_block(current->block_);
return;
}
builder()->GotoNoSimulate(current->block_, merge_block);
}
current = current->next_;
}
// Merge deopt blocks, padding when necessary.
current = merge_at_join_blocks_;
while (current != NULL) {
if (current->deopt_ && current->block_ != NULL) {
current->block_->FinishExit(HAbnormalExit::New(builder()->zone(), NULL),
HSourcePosition::Unknown());
}
current = current->next_;
}
builder()->set_current_block(merge_block);
}
HGraphBuilder::LoopBuilder::LoopBuilder(HGraphBuilder* builder) {
Initialize(builder, NULL, kWhileTrue, NULL);
}
HGraphBuilder::LoopBuilder::LoopBuilder(HGraphBuilder* builder, HValue* context,
LoopBuilder::Direction direction) {
Initialize(builder, context, direction, builder->graph()->GetConstant1());
}
HGraphBuilder::LoopBuilder::LoopBuilder(HGraphBuilder* builder, HValue* context,
LoopBuilder::Direction direction,
HValue* increment_amount) {
Initialize(builder, context, direction, increment_amount);
increment_amount_ = increment_amount;
}
void HGraphBuilder::LoopBuilder::Initialize(HGraphBuilder* builder,
HValue* context,
Direction direction,
HValue* increment_amount) {
builder_ = builder;
context_ = context;
direction_ = direction;
increment_amount_ = increment_amount;
finished_ = false;
header_block_ = builder->CreateLoopHeaderBlock();
body_block_ = NULL;
exit_block_ = NULL;
exit_trampoline_block_ = NULL;
}
HValue* HGraphBuilder::LoopBuilder::BeginBody(
HValue* initial,
HValue* terminating,
Token::Value token) {
DCHECK(direction_ != kWhileTrue);
HEnvironment* env = builder_->environment();
phi_ = header_block_->AddNewPhi(env->values()->length());
phi_->AddInput(initial);
env->Push(initial);
builder_->GotoNoSimulate(header_block_);
HEnvironment* body_env = env->Copy();
HEnvironment* exit_env = env->Copy();
// Remove the phi from the expression stack
body_env->Pop();
exit_env->Pop();
body_block_ = builder_->CreateBasicBlock(body_env);
exit_block_ = builder_->CreateBasicBlock(exit_env);
builder_->set_current_block(header_block_);
env->Pop();
builder_->FinishCurrentBlock(builder_->New<HCompareNumericAndBranch>(
phi_, terminating, token, body_block_, exit_block_));
builder_->set_current_block(body_block_);
if (direction_ == kPreIncrement || direction_ == kPreDecrement) {
HValue* one = builder_->graph()->GetConstant1();
if (direction_ == kPreIncrement) {
increment_ = HAdd::New(zone(), context_, phi_, one);
} else {
increment_ = HSub::New(zone(), context_, phi_, one);
}
increment_->ClearFlag(HValue::kCanOverflow);
builder_->AddInstruction(increment_);
return increment_;
} else {
return phi_;
}
}
void HGraphBuilder::LoopBuilder::BeginBody(int drop_count) {
DCHECK(direction_ == kWhileTrue);
HEnvironment* env = builder_->environment();
builder_->GotoNoSimulate(header_block_);
builder_->set_current_block(header_block_);
env->Drop(drop_count);
}
void HGraphBuilder::LoopBuilder::Break() {
if (exit_trampoline_block_ == NULL) {
// Its the first time we saw a break.
if (direction_ == kWhileTrue) {
HEnvironment* env = builder_->environment()->Copy();
exit_trampoline_block_ = builder_->CreateBasicBlock(env);
} else {
HEnvironment* env = exit_block_->last_environment()->Copy();
exit_trampoline_block_ = builder_->CreateBasicBlock(env);
builder_->GotoNoSimulate(exit_block_, exit_trampoline_block_);
}
}
builder_->GotoNoSimulate(exit_trampoline_block_);
builder_->set_current_block(NULL);
}
void HGraphBuilder::LoopBuilder::EndBody() {
DCHECK(!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_);
}
if (direction_ != kWhileTrue) {
// Push the new increment value on the expression stack to merge into
// the phi.
builder_->environment()->Push(increment_);
}
HBasicBlock* last_block = builder_->current_block();
builder_->GotoNoSimulate(last_block, header_block_);
header_block_->loop_information()->RegisterBackEdge(last_block);
if (exit_trampoline_block_ != NULL) {
builder_->set_current_block(exit_trampoline_block_);
} else {
builder_->set_current_block(exit_block_);
}
finished_ = true;
}
HGraph* HGraphBuilder::CreateGraph() {
graph_ = new(zone()) HGraph(info_);
if (FLAG_hydrogen_stats) isolate()->GetHStatistics()->Initialize(info_);
CompilationPhase phase("H_Block building", info_);
set_current_block(graph()->entry_block());
if (!BuildGraph()) return NULL;
graph()->FinalizeUniqueness();
return graph_;
}
HInstruction* HGraphBuilder::AddInstruction(HInstruction* instr) {
DCHECK(current_block() != NULL);
DCHECK(!FLAG_hydrogen_track_positions ||
!position_.IsUnknown() ||
!info_->IsOptimizing());
current_block()->AddInstruction(instr, source_position());
if (graph()->IsInsideNoSideEffectsScope()) {
instr->SetFlag(HValue::kHasNoObservableSideEffects);
}
return instr;
}
void HGraphBuilder::FinishCurrentBlock(HControlInstruction* last) {
DCHECK(!FLAG_hydrogen_track_positions ||
!info_->IsOptimizing() ||
!position_.IsUnknown());
current_block()->Finish(last, source_position());
if (last->IsReturn() || last->IsAbnormalExit()) {
set_current_block(NULL);
}
}
void HGraphBuilder::FinishExitCurrentBlock(HControlInstruction* instruction) {
DCHECK(!FLAG_hydrogen_track_positions || !info_->IsOptimizing() ||
!position_.IsUnknown());
current_block()->FinishExit(instruction, source_position());
if (instruction->IsReturn() || instruction->IsAbnormalExit()) {
set_current_block(NULL);
}
}
void HGraphBuilder::AddIncrementCounter(StatsCounter* counter) {
if (FLAG_native_code_counters && counter->Enabled()) {
HValue* reference = Add<HConstant>(ExternalReference(counter));
HValue* old_value = Add<HLoadNamedField>(
reference, static_cast<HValue*>(NULL), HObjectAccess::ForCounter());
HValue* new_value = AddUncasted<HAdd>(old_value, graph()->GetConstant1());
new_value->ClearFlag(HValue::kCanOverflow); // Ignore counter overflow
Add<HStoreNamedField>(reference, HObjectAccess::ForCounter(),
new_value, STORE_TO_INITIALIZED_ENTRY);
}
}
void HGraphBuilder::AddSimulate(BailoutId id,
RemovableSimulate removable) {
DCHECK(current_block() != NULL);
DCHECK(!graph()->IsInsideNoSideEffectsScope());
current_block()->AddNewSimulate(id, source_position(), 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::BuildGetElementsKind(HValue* object) {
HValue* map = Add<HLoadNamedField>(object, static_cast<HValue*>(NULL),
HObjectAccess::ForMap());
HValue* bit_field2 = Add<HLoadNamedField>(map, static_cast<HValue*>(NULL),
HObjectAccess::ForMapBitField2());
return BuildDecodeField<Map::ElementsKindBits>(bit_field2);
}
HValue* HGraphBuilder::BuildCheckHeapObject(HValue* obj) {
if (obj->type().IsHeapObject()) return obj;
return Add<HCheckHeapObject>(obj);
}
void HGraphBuilder::FinishExitWithHardDeoptimization(const char* reason) {
Add<HDeoptimize>(reason, Deoptimizer::EAGER);
FinishExitCurrentBlock(New<HAbnormalExit>());
}
HValue* HGraphBuilder::BuildCheckString(HValue* string) {
if (!string->type().IsString()) {
DCHECK(!string->IsConstant() ||
!HConstant::cast(string)->HasStringValue());
BuildCheckHeapObject(string);
return Add<HCheckInstanceType>(string, HCheckInstanceType::IS_STRING);
}
return string;
}
HValue* HGraphBuilder::BuildWrapReceiver(HValue* object, HValue* function) {
if (object->type().IsJSObject()) return object;
if (function->IsConstant() &&
HConstant::cast(function)->handle(isolate())->IsJSFunction()) {
Handle<JSFunction> f = Handle<JSFunction>::cast(
HConstant::cast(function)->handle(isolate()));
SharedFunctionInfo* shared = f->shared();
if (shared->strict_mode() == STRICT || shared->native()) return object;
}
return Add<HWrapReceiver>(object, function);
}
HValue* HGraphBuilder::BuildCheckForCapacityGrow(
HValue* object,
HValue* elements,
ElementsKind kind,
HValue* length,
HValue* key,
bool is_js_array,
PropertyAccessType access_type) {
IfBuilder length_checker(this);
Token::Value token = IsHoleyElementsKind(kind) ? Token::GTE : Token::EQ;
length_checker.If<HCompareNumericAndBranch>(key, length, token);
length_checker.Then();
HValue* current_capacity = AddLoadFixedArrayLength(elements);
IfBuilder capacity_checker(this);
capacity_checker.If<HCompareNumericAndBranch>(key, current_capacity,
Token::GTE);
capacity_checker.Then();
HValue* max_gap = Add<HConstant>(static_cast<int32_t>(JSObject::kMaxGap));
HValue* max_capacity = AddUncasted<HAdd>(current_capacity, max_gap);
Add<HBoundsCheck>(key, max_capacity);
HValue* new_capacity = BuildNewElementsCapacity(key);
HValue* new_elements = BuildGrowElementsCapacity(object, elements,
kind, kind, length,
new_capacity);
environment()->Push(new_elements);
capacity_checker.Else();
environment()->Push(elements);
capacity_checker.End();
if (is_js_array) {
HValue* new_length = AddUncasted<HAdd>(key, graph_->GetConstant1());
new_length->ClearFlag(HValue::kCanOverflow);
Add<HStoreNamedField>(object, HObjectAccess::ForArrayLength(kind),
new_length);
}
if (access_type == STORE && kind == FAST_SMI_ELEMENTS) {
HValue* checked_elements = environment()->Top();
// Write zero to ensure that the new element is initialized with some smi.
Add<HStoreKeyed>(checked_elements, key, graph()->GetConstant0(), kind);
}
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) {
DCHECK(!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, static_cast<HValue*>(NULL),
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);
}
void HGraphBuilder::BuildJSObjectCheck(HValue* receiver,
int bit_field_mask) {
// Check that the object isn't a smi.
Add<HCheckHeapObject>(receiver);
// Get the map of the receiver.
HValue* map = Add<HLoadNamedField>(receiver, static_cast<HValue*>(NULL),
HObjectAccess::ForMap());
// Check the instance type and if an access check is needed, this can be
// done with a single load, since both bytes are adjacent in the map.
HObjectAccess access(HObjectAccess::ForMapInstanceTypeAndBitField());
HValue* instance_type_and_bit_field =
Add<HLoadNamedField>(map, static_cast<HValue*>(NULL), access);
HValue* mask = Add<HConstant>(0x00FF | (bit_field_mask << 8));
HValue* and_result = AddUncasted<HBitwise>(Token::BIT_AND,
instance_type_and_bit_field,
mask);
HValue* sub_result = AddUncasted<HSub>(and_result,
Add<HConstant>(JS_OBJECT_TYPE));
Add<HBoundsCheck>(sub_result,
Add<HConstant>(LAST_JS_OBJECT_TYPE + 1 - JS_OBJECT_TYPE));
}
void HGraphBuilder::BuildKeyedIndexCheck(HValue* key,
HIfContinuation* join_continuation) {
// The sometimes unintuitively backward ordering of the ifs below is
// convoluted, but necessary. All of the paths must guarantee that the
// if-true of the continuation returns a smi element index and the if-false of
// the continuation returns either a symbol or a unique string key. All other
// object types cause a deopt to fall back to the runtime.
IfBuilder key_smi_if(this);
key_smi_if.If<HIsSmiAndBranch>(key);
key_smi_if.Then();
{
Push(key); // Nothing to do, just continue to true of continuation.
}
key_smi_if.Else();
{
HValue* map = Add<HLoadNamedField>(key, static_cast<HValue*>(NULL),
HObjectAccess::ForMap());
HValue* instance_type =
Add<HLoadNamedField>(map, static_cast<HValue*>(NULL),
HObjectAccess::ForMapInstanceType());
// Non-unique string, check for a string with a hash code that is actually
// an index.
STATIC_ASSERT(LAST_UNIQUE_NAME_TYPE == FIRST_NONSTRING_TYPE);
IfBuilder not_string_or_name_if(this);
not_string_or_name_if.If<HCompareNumericAndBranch>(
instance_type,
Add<HConstant>(LAST_UNIQUE_NAME_TYPE),
Token::GT);
not_string_or_name_if.Then();
{
// Non-smi, non-Name, non-String: Try to convert to smi in case of
// HeapNumber.
// TODO(danno): This could call some variant of ToString
Push(AddUncasted<HForceRepresentation>(key, Representation::Smi()));
}
not_string_or_name_if.Else();
{
// String or Name: check explicitly for Name, they can short-circuit
// directly to unique non-index key path.
IfBuilder not_symbol_if(this);
not_symbol_if.If<HCompareNumericAndBranch>(
instance_type,
Add<HConstant>(SYMBOL_TYPE),
Token::NE);
not_symbol_if.Then();
{
// String: check whether the String is a String of an index. If it is,
// extract the index value from the hash.
HValue* hash =
Add<HLoadNamedField>(key, static_cast<HValue*>(NULL),
HObjectAccess::ForNameHashField());
HValue* not_index_mask = Add<HConstant>(static_cast<int>(
String::kContainsCachedArrayIndexMask));
HValue* not_index_test = AddUncasted<HBitwise>(
Token::BIT_AND, hash, not_index_mask);
IfBuilder string_index_if(this);
string_index_if.If<HCompareNumericAndBranch>(not_index_test,
graph()->GetConstant0(),
Token::EQ);
string_index_if.Then();
{
// String with index in hash: extract string and merge to index path.
Push(BuildDecodeField<String::ArrayIndexValueBits>(hash));
}
string_index_if.Else();
{
// Key is a non-index String, check for uniqueness/internalization.
// If it's not internalized yet, internalize it now.
HValue* not_internalized_bit = AddUncasted<HBitwise>(
Token::BIT_AND,
instance_type,
Add<HConstant>(static_cast<int>(kIsNotInternalizedMask)));
IfBuilder internalized(this);
internalized.If<HCompareNumericAndBranch>(not_internalized_bit,
graph()->GetConstant0(),
Token::EQ);
internalized.Then();
Push(key);
internalized.Else();
Add<HPushArguments>(key);
HValue* intern_key = Add<HCallRuntime>(
isolate()->factory()->empty_string(),
Runtime::FunctionForId(Runtime::kInternalizeString), 1);
Push(intern_key);
internalized.End();
// Key guaranteed to be a unique string
}
string_index_if.JoinContinuation(join_continuation);
}
not_symbol_if.Else();
{
Push(key); // Key is symbol
}
not_symbol_if.JoinContinuation(join_continuation);
}
not_string_or_name_if.JoinContinuation(join_continuation);
}
key_smi_if.JoinContinuation(join_continuation);
}
void HGraphBuilder::BuildNonGlobalObjectCheck(HValue* receiver) {
// Get the the instance type of the receiver, and make sure that it is
// not one of the global object types.
HValue* map = Add<HLoadNamedField>(receiver, static_cast<HValue*>(NULL),
HObjectAccess::ForMap());
HValue* instance_type =
Add<HLoadNamedField>(map, static_cast<HValue*>(NULL),
HObjectAccess::ForMapInstanceType());
STATIC_ASSERT(JS_BUILTINS_OBJECT_TYPE == JS_GLOBAL_OBJECT_TYPE + 1);
HValue* min_global_type = Add<HConstant>(JS_GLOBAL_OBJECT_TYPE);
HValue* max_global_type = Add<HConstant>(JS_BUILTINS_OBJECT_TYPE);
IfBuilder if_global_object(this);
if_global_object.If<HCompareNumericAndBranch>(instance_type,
max_global_type,
Token::LTE);
if_global_object.And();
if_global_object.If<HCompareNumericAndBranch>(instance_type,
min_global_type,
Token::GTE);
if_global_object.ThenDeopt("receiver was a global object");
if_global_object.End();
}
void HGraphBuilder::BuildTestForDictionaryProperties(
HValue* object,
HIfContinuation* continuation) {
HValue* properties = Add<HLoadNamedField>(
object, static_cast<HValue*>(NULL),
HObjectAccess::ForPropertiesPointer());
HValue* properties_map =
Add<HLoadNamedField>(properties, static_cast<HValue*>(NULL),
HObjectAccess::ForMap());
HValue* hash_map = Add<HLoadRoot>(Heap::kHashTableMapRootIndex);
IfBuilder builder(this);
builder.If<HCompareObjectEqAndBranch>(properties_map, hash_map);
builder.CaptureContinuation(continuation);
}
HValue* HGraphBuilder::BuildKeyedLookupCacheHash(HValue* object,
HValue* key) {
// Load the map of the receiver, compute the keyed lookup cache hash
// based on 32 bits of the map pointer and the string hash.
HValue* object_map =
Add<HLoadNamedField>(object, static_cast<HValue*>(NULL),
HObjectAccess::ForMapAsInteger32());
HValue* shifted_map = AddUncasted<HShr>(
object_map, Add<HConstant>(KeyedLookupCache::kMapHashShift));
HValue* string_hash =
Add<HLoadNamedField>(key, static_cast<HValue*>(NULL),
HObjectAccess::ForStringHashField());
HValue* shifted_hash = AddUncasted<HShr>(
string_hash, Add<HConstant>(String::kHashShift));
HValue* xor_result = AddUncasted<HBitwise>(Token::BIT_XOR, shifted_map,
shifted_hash);
int mask = (KeyedLookupCache::kCapacityMask & KeyedLookupCache::kHashMask);
return AddUncasted<HBitwise>(Token::BIT_AND, xor_result,
Add<HConstant>(mask));
}
HValue* HGraphBuilder::BuildElementIndexHash(HValue* index) {
int32_t seed_value = static_cast<uint32_t>(isolate()->heap()->HashSeed());
HValue* seed = Add<HConstant>(seed_value);
HValue* hash = AddUncasted<HBitwise>(Token::BIT_XOR, index, seed);
// hash = ~hash + (hash << 15);
HValue* shifted_hash = AddUncasted<HShl>(hash, Add<HConstant>(15));
HValue* not_hash = AddUncasted<HBitwise>(Token::BIT_XOR, hash,
graph()->GetConstantMinus1());
hash = AddUncasted<HAdd>(shifted_hash, not_hash);
// hash = hash ^ (hash >> 12);
shifted_hash = AddUncasted<HShr>(hash, Add<HConstant>(12));
hash = AddUncasted<HBitwise>(Token::BIT_XOR, hash, shifted_hash);
// hash = hash + (hash << 2);
shifted_hash = AddUncasted<HShl>(hash, Add<HConstant>(2));
hash = AddUncasted<HAdd>(hash, shifted_hash);
// hash = hash ^ (hash >> 4);
shifted_hash = AddUncasted<HShr>(hash, Add<HConstant>(4));
hash = AddUncasted<HBitwise>(Token::BIT_XOR, hash, shifted_hash);
// hash = hash * 2057;
hash = AddUncasted<HMul>(hash, Add<HConstant>(2057));
hash->ClearFlag(HValue::kCanOverflow);
// hash = hash ^ (hash >> 16);
shifted_hash = AddUncasted<HShr>(hash, Add<HConstant>(16));
return AddUncasted<HBitwise>(Token::BIT_XOR, hash, shifted_hash);
}
HValue* HGraphBuilder::BuildUncheckedDictionaryElementLoad(HValue* receiver,
HValue* elements,
HValue* key,
HValue* hash) {
HValue* capacity = Add<HLoadKeyed>(
elements,
Add<HConstant>(NameDictionary::kCapacityIndex),
static_cast<HValue*>(NULL),
FAST_ELEMENTS);
HValue* mask = AddUncasted<HSub>(capacity, graph()->GetConstant1());
mask->ChangeRepresentation(Representation::Integer32());
mask->ClearFlag(HValue::kCanOverflow);
HValue* entry = hash;
HValue* count = graph()->GetConstant1();
Push(entry);
Push(count);
HIfContinuation return_or_loop_continuation(graph()->CreateBasicBlock(),
graph()->CreateBasicBlock());
HIfContinuation found_key_match_continuation(graph()->CreateBasicBlock(),
graph()->CreateBasicBlock());
LoopBuilder probe_loop(this);
probe_loop.BeginBody(2); // Drop entry, count from last environment to
// appease live range building without simulates.
count = Pop();
entry = Pop();
entry = AddUncasted<HBitwise>(Token::BIT_AND, entry, mask);
int entry_size = SeededNumberDictionary::kEntrySize;
HValue* base_index = AddUncasted<HMul>(entry, Add<HConstant>(entry_size));
base_index->ClearFlag(HValue::kCanOverflow);
int start_offset = SeededNumberDictionary::kElementsStartIndex;
HValue* key_index =
AddUncasted<HAdd>(base_index, Add<HConstant>(start_offset));
key_index->ClearFlag(HValue::kCanOverflow);
HValue* candidate_key = Add<HLoadKeyed>(
elements, key_index, static_cast<HValue*>(NULL), FAST_ELEMENTS);
IfBuilder if_undefined(this);
if_undefined.If<HCompareObjectEqAndBranch>(candidate_key,
graph()->GetConstantUndefined());
if_undefined.Then();
{
// element == undefined means "not found". Call the runtime.
// TODO(jkummerow): walk the prototype chain instead.
Add<HPushArguments>(receiver, key);
Push(Add<HCallRuntime>(isolate()->factory()->empty_string(),
Runtime::FunctionForId(Runtime::kKeyedGetProperty),
2));
}
if_undefined.Else();
{
IfBuilder if_match(this);
if_match.If<HCompareObjectEqAndBranch>(candidate_key, key);
if_match.Then();
if_match.Else();
// Update non-internalized string in the dictionary with internalized key?
IfBuilder if_update_with_internalized(this);
HValue* smi_check =
if_update_with_internalized.IfNot<HIsSmiAndBranch>(candidate_key);
if_update_with_internalized.And();
HValue* map = AddLoadMap(candidate_key, smi_check);
HValue* instance_type = Add<HLoadNamedField>(
map, static_cast<HValue*>(NULL), HObjectAccess::ForMapInstanceType());
HValue* not_internalized_bit = AddUncasted<HBitwise>(
Token::BIT_AND, instance_type,
Add<HConstant>(static_cast<int>(kIsNotInternalizedMask)));
if_update_with_internalized.If<HCompareNumericAndBranch>(
not_internalized_bit, graph()->GetConstant0(), Token::NE);
if_update_with_internalized.And();
if_update_with_internalized.IfNot<HCompareObjectEqAndBranch>(
candidate_key, graph()->GetConstantHole());
if_update_with_internalized.AndIf<HStringCompareAndBranch>(candidate_key,
key, Token::EQ);
if_update_with_internalized.Then();
// Replace a key that is a non-internalized string by the equivalent
// internalized string for faster further lookups.
Add<HStoreKeyed>(elements, key_index, key, FAST_ELEMENTS);
if_update_with_internalized.Else();
if_update_with_internalized.JoinContinuation(&found_key_match_continuation);
if_match.JoinContinuation(&found_key_match_continuation);
IfBuilder found_key_match(this, &found_key_match_continuation);
found_key_match.Then();
// Key at current probe matches. Relevant bits in the |details| field must
// be zero, otherwise the dictionary element requires special handling.
HValue* details_index =
AddUncasted<HAdd>(base_index, Add<HConstant>(start_offset + 2));
details_index->ClearFlag(HValue::kCanOverflow);
HValue* details = Add<HLoadKeyed>(
elements, details_index, static_cast<HValue*>(NULL), FAST_ELEMENTS);
int details_mask = PropertyDetails::TypeField::kMask |
PropertyDetails::DeletedField::kMask;
details = AddUncasted<HBitwise>(Token::BIT_AND, details,
Add<HConstant>(details_mask));
IfBuilder details_compare(this);
details_compare.If<HCompareNumericAndBranch>(
details, graph()->GetConstant0(), Token::EQ);
details_compare.Then();
HValue* result_index =
AddUncasted<HAdd>(base_index, Add<HConstant>(start_offset + 1));
result_index->ClearFlag(HValue::kCanOverflow);
Push(Add<HLoadKeyed>(elements, result_index, static_cast<HValue*>(NULL),
FAST_ELEMENTS));
details_compare.Else();
Add<HPushArguments>(receiver, key);
Push(Add<HCallRuntime>(isolate()->factory()->empty_string(),
Runtime::FunctionForId(Runtime::kKeyedGetProperty),
2));
details_compare.End();
found_key_match.Else();
found_key_match.JoinContinuation(&return_or_loop_continuation);
}
if_undefined.JoinContinuation(&return_or_loop_continuation);
IfBuilder return_or_loop(this, &return_or_loop_continuation);
return_or_loop.Then();
probe_loop.Break();
return_or_loop.Else();
entry = AddUncasted<HAdd>(entry, count);
entry->ClearFlag(HValue::kCanOverflow);
count = AddUncasted<HAdd>(count, graph()->GetConstant1());
count->ClearFlag(HValue::kCanOverflow);
Push(entry);
Push(count);
probe_loop.EndBody();
return_or_loop.End();
return Pop();
}
HValue* HGraphBuilder::BuildRegExpConstructResult(HValue* length,
HValue* index,
HValue* input) {
NoObservableSideEffectsScope scope(this);
HConstant* max_length = Add<HConstant>(JSObject::kInitialMaxFastElementArray);
Add<HBoundsCheck>(length, max_length);
// Generate size calculation code here in order to make it dominate
// the JSRegExpResult allocation.
ElementsKind elements_kind = FAST_ELEMENTS;
HValue* size = BuildCalculateElementsSize(elements_kind, length);
// Allocate the JSRegExpResult and the FixedArray in one step.
HValue* result = Add<HAllocate>(
Add<HConstant>(JSRegExpResult::kSize), HType::JSArray(),
NOT_TENURED, JS_ARRAY_TYPE);
// Initialize the JSRegExpResult header.
HValue* global_object = Add<HLoadNamedField>(
context(), static_cast<HValue*>(NULL),
HObjectAccess::ForContextSlot(Context::GLOBAL_OBJECT_INDEX));
HValue* native_context = Add<HLoadNamedField>(
global_object, static_cast<HValue*>(NULL),
HObjectAccess::ForGlobalObjectNativeContext());
Add<HStoreNamedField>(
result, HObjectAccess::ForMap(),
Add<HLoadNamedField>(
native_context, static_cast<HValue*>(NULL),
HObjectAccess::ForContextSlot(Context::REGEXP_RESULT_MAP_INDEX)));
HConstant* empty_fixed_array =
Add<HConstant>(isolate()->factory()->empty_fixed_array());
Add<HStoreNamedField>(
result, HObjectAccess::ForJSArrayOffset(JSArray::kPropertiesOffset),
empty_fixed_array);
Add<HStoreNamedField>(
result, HObjectAccess::ForJSArrayOffset(JSArray::kElementsOffset),
empty_fixed_array);
Add<HStoreNamedField>(
result, HObjectAccess::ForJSArrayOffset(JSArray::kLengthOffset), length);
// Initialize the additional fields.
Add<HStoreNamedField>(
result, HObjectAccess::ForJSArrayOffset(JSRegExpResult::kIndexOffset),
index);
Add<HStoreNamedField>(
result, HObjectAccess::ForJSArrayOffset(JSRegExpResult::kInputOffset),
input);
// Allocate and initialize the elements header.
HAllocate* elements = BuildAllocateElements(elements_kind, size);
BuildInitializeElementsHeader(elements, elements_kind, length);
if (!elements->has_size_upper_bound()) {
HConstant* size_in_bytes_upper_bound = EstablishElementsAllocationSize(
elements_kind, max_length->Integer32Value());
elements->set_size_upper_bound(size_in_bytes_upper_bound);
}
Add<HStoreNamedField>(
result, HObjectAccess::ForJSArrayOffset(JSArray::kElementsOffset),
elements);
// Initialize the elements contents with undefined.
BuildFillElementsWithValue(
elements, elements_kind, graph()->GetConstant0(), length,
graph()->GetConstantUndefined());
return result;
}
HValue* HGraphBuilder::BuildNumberToString(HValue* object, Type* type) {
NoObservableSideEffectsScope scope(this);
// Convert constant numbers at compile time.
if (object->IsConstant() && HConstant::cast(object)->HasNumberValue()) {
Handle<Object> number = HConstant::cast(object)->handle(isolate());
Handle<String> result = isolate()->factory()->NumberToString(number);
return Add<HConstant>(result);
}
// Create a joinable continuation.
HIfContinuation found(graph()->CreateBasicBlock(),
graph()->CreateBasicBlock());
// Load the number string cache.
HValue* number_string_cache =
Add<HLoadRoot>(Heap::kNumberStringCacheRootIndex);
// Make the hash mask from the length of the number string cache. It
// contains two elements (number and string) for each cache entry.
HValue* mask = AddLoadFixedArrayLength(number_string_cache);
mask->set_type(HType::Smi());
mask = AddUncasted<HSar>(mask, graph()->GetConstant1());
mask = AddUncasted<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 = AddUncasted<HBitwise>(Token::BIT_AND, object, mask);
// Load the key.
HValue* key_index = AddUncasted<HShl>(hash, graph()->GetConstant1());
HValue* key = Add<HLoadKeyed>(number_string_cache, key_index,
static_cast<HValue*>(NULL),
FAST_ELEMENTS, ALLOW_RETURN_HOLE);
// Check if object == key.
IfBuilder if_objectiskey(this);
if_objectiskey.If<HCompareObjectEqAndBranch>(object, key);
if_objectiskey.Then();
{
// Make the key_index available.
Push(key_index);
}
if_objectiskey.JoinContinuation(&found);
}
if_objectissmi.Else();
{
if (type->Is(Type::SignedSmall())) {
if_objectissmi.Deopt("Expected smi");
} else {
// Check if the object is a heap number.
IfBuilder if_objectisnumber(this);
HValue* objectisnumber = 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, objectisnumber,
HObjectAccess::ForHeapNumberValueLowestBits());
HValue* high = Add<HLoadNamedField>(
object, objectisnumber,
HObjectAccess::ForHeapNumberValueHighestBits());
HValue* hash = AddUncasted<HBitwise>(Token::BIT_XOR, low, high);
hash = AddUncasted<HBitwise>(Token::BIT_AND, hash, mask);
// Load the key.
HValue* key_index = AddUncasted<HShl>(hash, graph()->GetConstant1());
HValue* key = Add<HLoadKeyed>(number_string_cache, key_index,
static_cast<HValue*>(NULL),
FAST_ELEMENTS, ALLOW_RETURN_HOLE);
// Check if the key is a heap number and compare it with the object.
IfBuilder if_keyisnotsmi(this);
HValue* keyisnotsmi = if_keyisnotsmi.IfNot<HIsSmiAndBranch>(key);
if_keyisnotsmi.Then();
{
IfBuilder if_keyisheapnumber(this);
if_keyisheapnumber.If<HCompareMap>(
key, isolate()->factory()->heap_number_map());
if_keyisheapnumber.Then();
{
// Check if values of key and object match.
IfBuilder if_keyeqobject(this);
if_keyeqobject.If<HCompareNumericAndBranch>(
Add<HLoadNamedField>(key, keyisnotsmi,
HObjectAccess::ForHeapNumberValue()),
Add<HLoadNamedField>(object, objectisnumber,
HObjectAccess::ForHeapNumberValue()),
Token::EQ);
if_keyeqobject.Then();
{
// Make the key_index available.
Push(key_index);
}
if_keyeqobject.JoinContinuation(&found);
}
if_keyisheapnumber.JoinContinuation(&found);
}
if_keyisnotsmi.JoinContinuation(&found);
}
if_objectisnumber.Else();
{
if (type->Is(Type::Number())) {
if_objectisnumber.Deopt("Expected heap number");
}
}
if_objectisnumber.JoinContinuation(&found);
}
}
if_objectissmi.JoinContinuation(&found);
// Check for cache hit.
IfBuilder if_found(this, &found);
if_found.Then();
{
// Count number to string operation in native code.
AddIncrementCounter(isolate()->counters()->number_to_string_native());
// Load the value in case of cache hit.
HValue* key_index = Pop();
HValue* value_index = AddUncasted<HAdd>(key_index, graph()->GetConstant1());
Push(Add<HLoadKeyed>(number_string_cache, value_index,
static_cast<HValue*>(NULL),
FAST_ELEMENTS, ALLOW_RETURN_HOLE));
}
if_found.Else();
{
// Cache miss, fallback to runtime.
Add<HPushArguments>(object);
Push(Add<HCallRuntime>(
isolate()->factory()->empty_string(),
Runtime::FunctionForId(Runtime::kNumberToStringSkipCache),
1));
}
if_found.End();
return Pop();
}
HAllocate* HGraphBuilder::BuildAllocate(
HValue* object_size,
HType type,
InstanceType instance_type,
HAllocationMode allocation_mode) {
// Compute the effective allocation size.
HValue* size = object_size;
if (allocation_mode.CreateAllocationMementos()) {
size = AddUncasted<HAdd>(size, Add<HConstant>(AllocationMemento::kSize));
size->ClearFlag(HValue::kCanOverflow);
}
// Perform the actual allocation.
HAllocate* object = Add<HAllocate>(
size, type, allocation_mode.GetPretenureMode(),
instance_type, allocation_mode.feedback_site());
// Setup the allocation memento.
if (allocation_mode.CreateAllocationMementos()) {
BuildCreateAllocationMemento(
object, object_size, allocation_mode.current_site());
}
return object;
}
HValue* HGraphBuilder::BuildAddStringLengths(HValue* left_length,
HValue* right_length) {
// Compute the combined string length and check against max string length.
HValue* length = AddUncasted<HAdd>(left_length, right_length);
// Check that length <= kMaxLength <=> length < MaxLength + 1.
HValue* max_length = Add<HConstant>(String::kMaxLength + 1);
Add<HBoundsCheck>(length, max_length);
return length;
}
HValue* HGraphBuilder::BuildCreateConsString(
HValue* length,
HValue* left,
HValue* right,
HAllocationMode allocation_mode) {
// Determine the string instance types.
HInstruction* left_instance_type = AddLoadStringInstanceType(left);
HInstruction* right_instance_type = AddLoadStringInstanceType(right);
// Allocate the cons string object. HAllocate does not care whether we
// pass CONS_STRING_TYPE or CONS_ONE_BYTE_STRING_TYPE here, so we just use
// CONS_STRING_TYPE here. Below we decide whether the cons string is
// one-byte or two-byte and set the appropriate map.
DCHECK(HAllocate::CompatibleInstanceTypes(CONS_STRING_TYPE,
CONS_ONE_BYTE_STRING_TYPE));
HAllocate* result = BuildAllocate(Add<HConstant>(ConsString::kSize),
HType::String(), CONS_STRING_TYPE,
allocation_mode);
// Compute intersection and difference of instance types.
HValue* anded_instance_types = AddUncasted<HBitwise>(
Token::BIT_AND, left_instance_type, right_instance_type);
HValue* xored_instance_types = AddUncasted<HBitwise>(
Token::BIT_XOR, left_instance_type, right_instance_type);
// We create a one-byte cons string if
// 1. both strings are one-byte, or
// 2. at least one of the strings is two-byte, but happens to contain only
// one-byte characters.
// To do this, we check
// 1. if both strings are one-byte, or if the one-byte data hint is set in
// both strings, or
// 2. if one of the strings has the one-byte data hint set and the other
// string is one-byte.
IfBuilder if_onebyte(this);
STATIC_ASSERT(kOneByteStringTag != 0);
STATIC_ASSERT(kOneByteDataHintMask != 0);
if_onebyte.If<HCompareNumericAndBranch>(
AddUncasted<HBitwise>(
Token::BIT_AND, anded_instance_types,
Add<HConstant>(static_cast<int32_t>(
kStringEncodingMask | kOneByteDataHintMask))),
graph()->GetConstant0(), Token::NE);
if_onebyte.Or();
STATIC_ASSERT(kOneByteStringTag != 0 &&
kOneByteDataHintTag != 0 &&
kOneByteDataHintTag != kOneByteStringTag);
if_onebyte.If<HCompareNumericAndBranch>(
AddUncasted<HBitwise>(
Token::BIT_AND, xored_instance_types,
Add<HConstant>(static_cast<int32_t>(
kOneByteStringTag | kOneByteDataHintTag))),
Add<HConstant>(static_cast<int32_t>(
kOneByteStringTag | kOneByteDataHintTag)), Token::EQ);
if_onebyte.Then();
{
// We can safely skip the write barrier for storing the map here.
Add<HStoreNamedField>(
result, HObjectAccess::ForMap(),
Add<HConstant>(isolate()->factory()->cons_one_byte_string_map()));
}
if_onebyte.Else();
{
// We can safely skip the write barrier for storing the map here.
Add<HStoreNamedField>(
result, HObjectAccess::ForMap(),
Add<HConstant>(isolate()->factory()->cons_string_map()));
}
if_onebyte.End();
// Initialize the cons string fields.
Add<HStoreNamedField>(result, HObjectAccess::ForStringHashField(),
Add<HConstant>(String::kEmptyHashField));
Add<HStoreNamedField>(result, HObjectAccess::ForStringLength(), length);
Add<HStoreNamedField>(result, HObjectAccess::ForConsStringFirst(), left);
Add<HStoreNamedField>(result, HObjectAccess::ForConsStringSecond(), right);
// Count the native string addition.
AddIncrementCounter(isolate()->counters()->string_add_native());
return result;
}
void HGraphBuilder::BuildCopySeqStringChars(HValue* src,
HValue* src_offset,
String::Encoding src_encoding,
HValue* dst,
HValue* dst_offset,
String::Encoding dst_encoding,
HValue* length) {
DCHECK(dst_encoding != String::ONE_BYTE_ENCODING ||
src_encoding == String::ONE_BYTE_ENCODING);
LoopBuilder loop(this, context(), LoopBuilder::kPostIncrement);
HValue* index = loop.BeginBody(graph()->GetConstant0(), length, Token::LT);
{
HValue* src_index = AddUncasted<HAdd>(src_offset, index);
HValue* value =
AddUncasted<HSeqStringGetChar>(src_encoding, src, src_index);
HValue* dst_index = AddUncasted<HAdd>(dst_offset, index);
Add<HSeqStringSetChar>(dst_encoding, dst, dst_index, value);
}
loop.EndBody();
}
HValue* HGraphBuilder::BuildObjectSizeAlignment(
HValue* unaligned_size, int header_size) {
DCHECK((header_size & kObjectAlignmentMask) == 0);
HValue* size = AddUncasted<HAdd>(
unaligned_size, Add<HConstant>(static_cast<int32_t>(
header_size + kObjectAlignmentMask)));
size->ClearFlag(HValue::kCanOverflow);
return AddUncasted<HBitwise>(
Token::BIT_AND, size, Add<HConstant>(static_cast<int32_t>(
~kObjectAlignmentMask)));
}
HValue* HGraphBuilder::BuildUncheckedStringAdd(
HValue* left,
HValue* right,
HAllocationMode allocation_mode) {
// Determine the string lengths.
HValue* left_length = AddLoadStringLength(left);
HValue* right_length = AddLoadStringLength(right);
// Compute the combined string length.
HValue* length = BuildAddStringLengths(left_length, right_length);
// Do some manual constant folding here.
if (left_length->IsConstant()) {
HConstant* c_left_length = HConstant::cast(left_length);
DCHECK_NE(0, c_left_length->Integer32Value());
if (c_left_length->Integer32Value() + 1 >= ConsString::kMinLength) {
// The right string contains at least one character.
return BuildCreateConsString(length, left, right, allocation_mode);
}
} else if (right_length->IsConstant()) {
HConstant* c_right_length = HConstant::cast(right_length);
DCHECK_NE(0, c_right_length->Integer32Value());
if (c_right_length->Integer32Value() + 1 >= ConsString::kMinLength) {
// The left string contains at least one character.
return BuildCreateConsString(length, left, right, allocation_mode);
}
}
// Check if we should create a cons string.
IfBuilder if_createcons(this);
if_createcons.If<HCompareNumericAndBranch>(
length, Add<HConstant>(ConsString::kMinLength), Token::GTE);
if_createcons.Then();
{
// Create a cons string.
Push(BuildCreateConsString(length, left, right, allocation_mode));
}
if_createcons.Else();
{
// Determine the string instance types.
HValue* left_instance_type = AddLoadStringInstanceType(left);
HValue* right_instance_type = AddLoadStringInstanceType(right);
// Compute union and difference of instance types.
HValue* ored_instance_types = AddUncasted<HBitwise>(
Token::BIT_OR, left_instance_type, right_instance_type);
HValue* xored_instance_types = AddUncasted<HBitwise>(
Token::BIT_XOR, left_instance_type, right_instance_type);
// Check if both strings have the same encoding and both are
// sequential.
IfBuilder if_sameencodingandsequential(this);
if_sameencodingandsequential.If<HCompareNumericAndBranch>(
AddUncasted<HBitwise>(
Token::BIT_AND, xored_instance_types,
Add<HConstant>(static_cast<int32_t>(kStringEncodingMask))),
graph()->GetConstant0(), Token::EQ);
if_sameencodingandsequential.And();
STATIC_ASSERT(kSeqStringTag == 0);
if_sameencodingandsequential.If<HCompareNumericAndBranch>(
AddUncasted<HBitwise>(
Token::BIT_AND, ored_instance_types,
Add<HConstant>(static_cast<int32_t>(kStringRepresentationMask))),
graph()->GetConstant0(), Token::EQ);
if_sameencodingandsequential.Then();
{
HConstant* string_map =
Add<HConstant>(isolate()->factory()->string_map());
HConstant* one_byte_string_map =
Add<HConstant>(isolate()->factory()->one_byte_string_map());
// Determine map and size depending on whether result is one-byte string.
IfBuilder if_onebyte(this);
STATIC_ASSERT(kOneByteStringTag != 0);
if_onebyte.If<HCompareNumericAndBranch>(
AddUncasted<HBitwise>(
Token::BIT_AND, ored_instance_types,
Add<HConstant>(static_cast<int32_t>(kStringEncodingMask))),
graph()->GetConstant0(), Token::NE);
if_onebyte.Then();
{
// Allocate sequential one-byte string object.
Push(length);
Push(one_byte_string_map);
}
if_onebyte.Else();
{
// Allocate sequential two-byte string object.
HValue* size = AddUncasted<HShl>(length, graph()->GetConstant1());
size->ClearFlag(HValue::kCanOverflow);
size->SetFlag(HValue::kUint32);
Push(size);
Push(string_map);
}
if_onebyte.End();
HValue* map = Pop();
// Calculate the number of bytes needed for the characters in the
// string while observing object alignment.
STATIC_ASSERT((SeqString::kHeaderSize & kObjectAlignmentMask) == 0);
HValue* size = BuildObjectSizeAlignment(Pop(), SeqString::kHeaderSize);
// Allocate the string object. HAllocate does not care whether we pass
// STRING_TYPE or ONE_BYTE_STRING_TYPE here, so we just use STRING_TYPE.
HAllocate* result = BuildAllocate(
size, HType::String(), STRING_TYPE, allocation_mode);
Add<HStoreNamedField>(result, HObjectAccess::ForMap(), map);
// Initialize the string fields.
Add<HStoreNamedField>(result, HObjectAccess::ForStringHashField(),
Add<HConstant>(String::kEmptyHashField));
Add<HStoreNamedField>(result, HObjectAccess::ForStringLength(), length);
// Copy characters to the result string.
IfBuilder if_twobyte(this);
if_twobyte.If<HCompareObjectEqAndBranch>(map, string_map);
if_twobyte.Then();
{
// Copy characters from the left string.
BuildCopySeqStringChars(
left, graph()->GetConstant0(), String::TWO_BYTE_ENCODING,
result, graph()->GetConstant0(), String::TWO_BYTE_ENCODING,
left_length);
// Copy characters from the right string.
BuildCopySeqStringChars(
right, graph()->GetConstant0(), String::TWO_BYTE_ENCODING,
result, left_length, String::TWO_BYTE_ENCODING,
right_length);
}
if_twobyte.Else();
{
// Copy characters from the left string.
BuildCopySeqStringChars(
left, graph()->GetConstant0(), String::ONE_BYTE_ENCODING,
result, graph()->GetConstant0(), String::ONE_BYTE_ENCODING,
left_length);
// Copy characters from the right string.
BuildCopySeqStringChars(
right, graph()->GetConstant0(), String::ONE_BYTE_ENCODING,
result, left_length, String::ONE_BYTE_ENCODING,
right_length);
}
if_twobyte.End();
// Count the native string addition.
AddIncrementCounter(isolate()->counters()->string_add_native());
// Return the sequential string.
Push(result);
}
if_sameencodingandsequential.Else();
{
// Fallback to the runtime to add the two strings.
Add<HPushArguments>(left, right);
Push(Add<HCallRuntime>(
isolate()->factory()->empty_string(),
Runtime::FunctionForId(Runtime::kStringAdd),
2));
}
if_sameencodingandsequential.End();
}
if_createcons.End();
return Pop();
}
HValue* HGraphBuilder::BuildStringAdd(
HValue* left,
HValue* right,
HAllocationMode allocation_mode) {
NoObservableSideEffectsScope no_effects(this);
// Determine string lengths.
HValue* left_length = AddLoadStringLength(left);
HValue* right_length = AddLoadStringLength(right);
// Check if left string is empty.
IfBuilder if_leftempty(this);
if_leftempty.If<HCompareNumericAndBranch>(
left_length, graph()->GetConstant0(), Token::EQ);
if_leftempty.Then();
{
// Count the native string addition.
AddIncrementCounter(isolate()->counters()->string_add_native());
// Just return the right string.
Push(right);
}
if_leftempty.Else();
{
// Check if right string is empty.
IfBuilder if_rightempty(this);
if_rightempty.If<HCompareNumericAndBranch>(
right_length, graph()->GetConstant0(), Token::EQ);
if_rightempty.Then();
{
// Count the native string addition.
AddIncrementCounter(isolate()->counters()->string_add_native());
// Just return the left string.
Push(left);
}
if_rightempty.Else();
{
// Add the two non-empty strings.
Push(BuildUncheckedStringAdd(left, right, allocation_mode));
}
if_rightempty.End();
}
if_leftempty.End();
return Pop();
}
HInstruction* HGraphBuilder::BuildUncheckedMonomorphicElementAccess(
HValue* checked_object,
HValue* key,
HValue* val,
bool is_js_array,
ElementsKind elements_kind,
PropertyAccessType access_type,
LoadKeyedHoleMode load_mode,
KeyedAccessStoreMode store_mode) {
DCHECK((!IsExternalArrayElementsKind(elements_kind) &&
!IsFixedTypedArrayElementsKind(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 && access_type == STORE)) {
checked_object->ClearDependsOnFlag(kElementsKind);
}
bool fast_smi_only_elements = IsFastSmiElementsKind(elements_kind);
bool fast_elements = IsFastObjectElementsKind(elements_kind);
HValue* elements = AddLoadElements(checked_object);
if (access_type == 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());
check_cow_map->ClearDependsOnFlag(kElementsKind);
}
HInstruction* length = NULL;
if (is_js_array) {
length = Add<HLoadNamedField>(
checked_object->ActualValue(), checked_object,
HObjectAccess::ForArrayLength(elements_kind));
} else {
length = AddLoadFixedArrayLength(elements);
}
length->set_type(HType::Smi());
HValue* checked_key = NULL;
if (IsExternalArrayElementsKind(elements_kind) ||
IsFixedTypedArrayElementsKind(elements_kind)) {
HValue* backing_store;
if (IsExternalArrayElementsKind(elements_kind)) {
backing_store = Add<HLoadNamedField>(
elements, static_cast<HValue*>(NULL),
HObjectAccess::ForExternalArrayExternalPointer());
} else {
backing_store = elements;
}
if (store_mode == STORE_NO_TRANSITION_IGNORE_OUT_OF_BOUNDS) {
NoObservableSideEffectsScope no_effects(this);
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 = AddElementAccess(
backing_store, key, val, bounds_check, elements_kind, access_type);
negative_checker.ElseDeopt("Negative key encountered");
negative_checker.End();
length_checker.End();
return result;
} else {
DCHECK(store_mode == STANDARD_STORE);
checked_key = Add<HBoundsCheck>(key, length);
return AddElementAccess(
backing_store, checked_key, val,
checked_object, elements_kind, access_type);
}
}
DCHECK(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 (access_type == STORE && IsFastSmiElementsKind(elements_kind) &&
!val->type().IsSmi()) {
val = AddUncasted<HForceRepresentation>(val, Representation::Smi());
}
if (IsGrowStoreMode(store_mode)) {
NoObservableSideEffectsScope no_effects(this);
Representation representation = HStoreKeyed::RequiredValueRepresentation(
elements_kind, STORE_TO_INITIALIZED_ENTRY);
val = AddUncasted<HForceRepresentation>(val, representation);
elements = BuildCheckForCapacityGrow(checked_object, elements,
elements_kind, length, key,
is_js_array, access_type);
checked_key = key;
} else {
checked_key = Add<HBoundsCheck>(key, length);
if (access_type == 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());
check_cow_map->ClearDependsOnFlag(kElementsKind);
}
}
}
return AddElementAccess(elements, checked_key, val, checked_object,
elements_kind, access_type, load_mode);
}
HValue* HGraphBuilder::BuildAllocateArrayFromLength(
JSArrayBuilder* array_builder,
HValue* length_argument) {
if (length_argument->IsConstant() &&
HConstant::cast(length_argument)->HasSmiValue()) {
int array_length = HConstant::cast(length_argument)->Integer32Value();
if (array_length == 0) {
return array_builder->AllocateEmptyArray();
} else {
return array_builder->AllocateArray(length_argument,
array_length,
length_argument);
}
}
HValue* constant_zero = graph()->GetConstant0();
HConstant* max_alloc_length =
Add<HConstant>(JSObject::kInitialMaxFastElementArray);
HInstruction* checked_length = Add<HBoundsCheck>(length_argument,
max_alloc_length);
IfBuilder if_builder(this);
if_builder.If<HCompareNumericAndBranch>(checked_length, constant_zero,
Token::EQ);
if_builder.Then();
const int initial_capacity = JSArray::kPreallocatedArrayElements;
HConstant* initial_capacity_node = Add<HConstant>(initial_capacity);
Push(initial_capacity_node); // capacity
Push(constant_zero); // length
if_builder.Else();
if (!(top_info()->IsStub()) &&
IsFastPackedElementsKind(array_builder->kind())) {
// We'll come back later with better (holey) feedback.
if_builder.Deopt("Holey array despite packed elements_kind feedback");
} else {
Push(checked_length); // capacity
Push(checked_length); // length
}
if_builder.End();
// Figure out total size
HValue* length = Pop();
HValue* capacity = Pop();
return array_builder->AllocateArray(capacity, max_alloc_length, length);
}
HValue* HGraphBuilder::BuildCalculateElementsSize(ElementsKind kind,
HValue* capacity) {
int elements_size = IsFastDoubleElementsKind(kind)
? kDoubleSize
: kPointerSize;
HConstant* elements_size_value = Add<HConstant>(elements_size);
HInstruction* mul = HMul::NewImul(zone(), context(),
capacity->ActualValue(),
elements_size_value);
AddInstruction(mul);
mul->ClearFlag(HValue::kCanOverflow);
STATIC_ASSERT(FixedDoubleArray::kHeaderSize == FixedArray::kHeaderSize);
HConstant* header_size = Add<HConstant>(FixedArray::kHeaderSize);
HValue* total_size = AddUncasted<HAdd>(mul, header_size);
total_size->ClearFlag(HValue::kCanOverflow);
return total_size;
}
HAllocate* HGraphBuilder::AllocateJSArrayObject(AllocationSiteMode mode) {
int base_size = JSArray::kSize;
if (mode == TRACK_ALLOCATION_SITE) {
base_size += AllocationMemento::kSize;
}
HConstant* size_in_bytes = Add<HConstant>(base_size);
return Add<HAllocate>(
size_in_bytes, HType::JSArray(), NOT_TENURED, JS_OBJECT_TYPE);
}
HConstant* HGraphBuilder::EstablishElementsAllocationSize(
ElementsKind kind,
int capacity) {
int base_size = IsFastDoubleElementsKind(kind)
? FixedDoubleArray::SizeFor(capacity)