blob: bbe148f285ce09bfcfa00d00bf244ca0c8945cea [file] [log] [blame]
// Copyright 2012 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 "v8.h"
#include "hydrogen.h"
#include "codegen.h"
#include "full-codegen.h"
#include "hashmap.h"
#include "lithium-allocator.h"
#include "parser.h"
#include "scopeinfo.h"
#include "scopes.h"
#include "stub-cache.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),
is_inline_return_target_(false),
is_deoptimizing_(false),
dominates_loop_successors_(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));
ASSERT(phi->HasNoUses() || !phi->is_live());
phi->Kill();
phis_.RemoveElement(phi);
phi->SetBlock(NULL);
}
void HBasicBlock::AddInstruction(HInstruction* instr) {
ASSERT(!IsStartBlock() || !IsFinished());
ASSERT(!instr->IsLinked());
ASSERT(!IsFinished());
if (first_ == NULL) {
HBlockEntry* entry = new(zone()) HBlockEntry();
entry->InitializeAsFirst(this);
first_ = last_ = entry;
}
instr->InsertAfter(last_);
}
HDeoptimize* HBasicBlock::CreateDeoptimize(
HDeoptimize::UseEnvironment has_uses) {
ASSERT(HasEnvironment());
if (has_uses == HDeoptimize::kNoUses)
return new(zone()) HDeoptimize(0, zone());
HEnvironment* environment = last_environment();
HDeoptimize* instr = new(zone()) HDeoptimize(environment->length(), zone());
for (int i = 0; i < environment->length(); i++) {
HValue* val = environment->values()->at(i);
instr->AddEnvironmentValue(val, zone());
}
return instr;
}
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);
// Order of pushed values: newest (top of stack) first. This allows
// HSimulate::MergeInto() 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 drop_extra = state != NULL &&
state->inlining_kind() == DROP_EXTRA_ON_RETURN;
if (block->IsInlineReturnTarget()) {
AddInstruction(new(zone()) HLeaveInlined());
last_environment_ = last_environment()->DiscardInlined(drop_extra);
}
AddSimulate(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);
AddInstruction(new(zone()) HLeaveInlined());
last_environment_ = last_environment()->DiscardInlined(drop_extra);
last_environment()->Push(return_value);
AddSimulate(BailoutId::None());
HGoto* instr = new(zone()) HGoto(target);
Finish(instr);
}
void HBasicBlock::SetInitialEnvironment(HEnvironment* env) {
ASSERT(!HasEnvironment());
ASSERT(first() == NULL);
UpdateEnvironment(env);
}
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());
// We only need to verify the ID once.
ASSERT(i != 0 ||
(predecessor->last_environment()->closure().is_null() ||
predecessor->last_environment()->closure()->shared()
->VerifyBailoutId(ast_id)));
simulate->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 {
// Allow dereferencing for debug mode verification.
AllowHandleDereference allow_handle_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,
Handle<Object> value) {
if (!pointer->is_set()) {
HConstant* constant = new(zone()) HConstant(value,
Representation::Tagged());
constant->InsertAfter(GetConstantUndefined());
pointer->set(constant);
}
return pointer->get();
}
HConstant* HGraph::GetConstantInt32(SetOncePointer<HConstant>* pointer,
int32_t value) {
if (!pointer->is_set()) {
HConstant* constant =
new(zone()) HConstant(value, Representation::Integer32());
constant->InsertAfter(GetConstantUndefined());
pointer->set(constant);
}
return pointer->get();
}
HConstant* HGraph::GetConstant0() {
return GetConstantInt32(&constant_0_, 0);
}
HConstant* HGraph::GetConstant1() {
return GetConstantInt32(&constant_1_, 1);
}
HConstant* HGraph::GetConstantMinus1() {
return GetConstantInt32(&constant_minus1_, -1);
}
HConstant* HGraph::GetConstantTrue() {
return GetConstant(&constant_true_, isolate()->factory()->true_value());
}
HConstant* HGraph::GetConstantFalse() {
return GetConstant(&constant_false_, isolate()->factory()->false_value());
}
HConstant* HGraph::GetConstantHole() {
return GetConstant(&constant_hole_, isolate()->factory()->the_hole_value());
}
HGraphBuilder::IfBuilder::IfBuilder(HGraphBuilder* builder, BailoutId id)
: builder_(builder),
finished_(false),
id_(id) {
HEnvironment* env = builder->environment();
HEnvironment* true_env = env->Copy();
HEnvironment* false_env = env->Copy();
HEnvironment* merge_env = env->Copy();
true_block_ = builder->CreateBasicBlock(true_env);
false_block_ = builder->CreateBasicBlock(false_env);
merge_block_ = builder->CreateBasicBlock(merge_env);
}
void HGraphBuilder::IfBuilder::BeginTrue(HValue* left,
HValue* right,
Token::Value token) {
HCompareIDAndBranch* compare =
new(zone()) HCompareIDAndBranch(left, right, token);
compare->ChangeRepresentation(Representation::Integer32());
compare->SetSuccessorAt(0, true_block_);
compare->SetSuccessorAt(1, false_block_);
builder_->current_block()->Finish(compare);
builder_->set_current_block(true_block_);
}
void HGraphBuilder::IfBuilder::BeginFalse() {
builder_->current_block()->Goto(merge_block_);
builder_->set_current_block(false_block_);
}
void HGraphBuilder::IfBuilder::End() {
ASSERT(!finished_);
builder_->current_block()->Goto(merge_block_);
builder_->set_current_block(merge_block_);
merge_block_->SetJoinId(id_);
finished_ = true;
}
HGraphBuilder::LoopBuilder::LoopBuilder(HGraphBuilder* builder,
HValue* context,
LoopBuilder::Direction direction,
BailoutId id)
: builder_(builder),
context_(context),
direction_(direction),
id_(id),
finished_(false) {
HEnvironment* env = builder_->environment();
HEnvironment* body_env = env->Copy();
HEnvironment* exit_env = env->Copy();
header_block_ = builder->CreateLoopHeaderBlock();
body_block_ = builder->CreateBasicBlock(body_env);
exit_block_ = builder->CreateBasicBlock(exit_env);
}
HValue* HGraphBuilder::LoopBuilder::BeginBody(HValue* initial,
HValue* terminating,
Token::Value token) {
phi_ = new(zone()) HPhi(0, zone());
header_block_->AddPhi(phi_);
phi_->AddInput(initial);
phi_->ChangeRepresentation(Representation::Integer32());
HEnvironment* env = builder_->environment();
env->Push(initial);
builder_->current_block()->Goto(header_block_);
builder_->set_current_block(header_block_);
builder_->set_current_block(header_block_);
HCompareIDAndBranch* compare =
new(zone()) HCompareIDAndBranch(phi_, terminating, token);
compare->ChangeRepresentation(Representation::Integer32());
compare->SetSuccessorAt(0, body_block_);
compare->SetSuccessorAt(1, exit_block_);
builder_->current_block()->Finish(compare);
builder_->set_current_block(body_block_);
if (direction_ == kPreIncrement || direction_ == kPreDecrement) {
HValue* one = builder_->graph()->GetConstant1();
if (direction_ == kPreIncrement) {
increment_ = new(zone()) HAdd(context_, phi_, one);
} else {
increment_ = new(zone()) HSub(context_, phi_, one);
}
increment_->ClearFlag(HValue::kCanOverflow);
increment_->ChangeRepresentation(Representation::Integer32());
builder_->AddInstruction(increment_);
return increment_;
} else {
return phi_;
}
}
void HGraphBuilder::LoopBuilder::EndBody() {
ASSERT(!finished_);
if (direction_ == kPostIncrement || direction_ == kPostDecrement) {
HValue* one = builder_->graph()->GetConstant1();
if (direction_ == kPostIncrement) {
increment_ = new(zone()) HAdd(context_, phi_, one);
} else {
increment_ = new(zone()) HSub(context_, phi_, one);
}
increment_->ClearFlag(HValue::kCanOverflow);
increment_->ChangeRepresentation(Representation::Integer32());
builder_->AddInstruction(increment_);
}
builder_->environment()->Push(increment_);
builder_->current_block()->Goto(header_block_);
header_block_->loop_information()->RegisterBackEdge(body_block_);
header_block_->SetJoinId(BailoutId::StubEntry());
builder_->set_current_block(exit_block_);
finished_ = true;
}
HGraph* HGraphBuilder::CreateGraph() {
graph_ = new(zone()) HGraph(info_);
if (FLAG_hydrogen_stats) HStatistics::Instance()->Initialize(info_);
HPhase phase("H_Block building");
set_current_block(graph()->entry_block());
if (!BuildGraph()) return NULL;
return graph_;
}
HInstruction* HGraphBuilder::AddInstruction(HInstruction* instr) {
ASSERT(current_block() != NULL);
current_block()->AddInstruction(instr);
return instr;
}
void HGraphBuilder::AddSimulate(BailoutId id,
RemovableSimulate removable) {
ASSERT(current_block() != NULL);
current_block()->AddSimulate(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;
}
HInstruction* HGraphBuilder::BuildExternalArrayElementAccess(
HValue* external_elements,
HValue* checked_key,
HValue* val,
HValue* dependency,
ElementsKind elements_kind,
bool is_store) {
Zone* zone = this->zone();
if (is_store) {
ASSERT(val != NULL);
switch (elements_kind) {
case EXTERNAL_PIXEL_ELEMENTS: {
val = AddInstruction(new(zone) 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 new(zone) HStoreKeyed(external_elements, checked_key,
val, elements_kind);
} else {
ASSERT(val == NULL);
HLoadKeyed* load =
new(zone) 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::BuildFastElementAccess(
HValue* elements,
HValue* checked_key,
HValue* val,
HValue* load_dependency,
ElementsKind elements_kind,
bool is_store) {
Zone* zone = this->zone();
if (is_store) {
ASSERT(val != NULL);
switch (elements_kind) {
case FAST_SMI_ELEMENTS:
case FAST_HOLEY_SMI_ELEMENTS:
// Smi-only arrays need a smi check.
AddInstruction(new(zone) HCheckSmi(val));
// Fall through.
case FAST_ELEMENTS:
case FAST_HOLEY_ELEMENTS:
case FAST_DOUBLE_ELEMENTS:
case FAST_HOLEY_DOUBLE_ELEMENTS:
return new(zone) HStoreKeyed(elements, checked_key, val, elements_kind);
default:
UNREACHABLE();
return NULL;
}
}
// It's an element load (!is_store).
return new(zone) HLoadKeyed(elements,
checked_key,
load_dependency,
elements_kind);
}
HInstruction* HGraphBuilder::BuildUncheckedMonomorphicElementAccess(
HValue* object,
HValue* key,
HValue* val,
HCheckMaps* mapcheck,
bool is_js_array,
ElementsKind elements_kind,
bool is_store,
Representation checked_index_representation) {
Zone* zone = this->zone();
// 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)) {
if (mapcheck != NULL) {
mapcheck->ClearGVNFlag(kDependsOnElementsKind);
}
}
bool fast_smi_only_elements = IsFastSmiElementsKind(elements_kind);
bool fast_elements = IsFastObjectElementsKind(elements_kind);
HInstruction* elements =
AddInstruction(new(zone) HLoadElements(object, mapcheck));
if (is_store && (fast_elements || fast_smi_only_elements)) {
HCheckMaps* check_cow_map = new(zone) HCheckMaps(
elements, Isolate::Current()->factory()->fixed_array_map(), zone);
check_cow_map->ClearGVNFlag(kDependsOnElementsKind);
AddInstruction(check_cow_map);
}
HInstruction* length = NULL;
HInstruction* checked_key = NULL;
if (IsExternalArrayElementsKind(elements_kind)) {
length = AddInstruction(new(zone) HFixedArrayBaseLength(elements));
checked_key = AddInstruction(new(zone) HBoundsCheck(
key, length, ALLOW_SMI_KEY, checked_index_representation));
HLoadExternalArrayPointer* external_elements =
new(zone) HLoadExternalArrayPointer(elements);
AddInstruction(external_elements);
return BuildExternalArrayElementAccess(
external_elements, checked_key, val, mapcheck,
elements_kind, is_store);
}
ASSERT(fast_smi_only_elements ||
fast_elements ||
IsFastDoubleElementsKind(elements_kind));
if (is_js_array) {
length = AddInstruction(new(zone) HJSArrayLength(object, mapcheck,
HType::Smi()));
} else {
length = AddInstruction(new(zone) HFixedArrayBaseLength(elements));
}
checked_key = AddInstruction(new(zone) HBoundsCheck(
key, length, ALLOW_SMI_KEY, checked_index_representation));
return BuildFastElementAccess(elements, checked_key, val, mapcheck,
elements_kind, is_store);
}
HValue* HGraphBuilder::BuildAllocateElements(HContext* context,
ElementsKind kind,
HValue* capacity) {
Zone* zone = this->zone();
int elements_size = IsFastDoubleElementsKind(kind)
? kDoubleSize : kPointerSize;
HConstant* elements_size_value =
new(zone) HConstant(elements_size, Representation::Integer32());
AddInstruction(elements_size_value);
HValue* mul = AddInstruction(
new(zone) HMul(context, capacity, elements_size_value));
mul->ChangeRepresentation(Representation::Integer32());
mul->ClearFlag(HValue::kCanOverflow);
HConstant* header_size =
new(zone) HConstant(FixedArray::kHeaderSize, Representation::Integer32());
AddInstruction(header_size);
HValue* total_size = AddInstruction(
new(zone) HAdd(context, mul, header_size));
total_size->ChangeRepresentation(Representation::Integer32());
total_size->ClearFlag(HValue::kCanOverflow);
HAllocate::Flags flags = HAllocate::CAN_ALLOCATE_IN_NEW_SPACE;
if (IsFastDoubleElementsKind(kind)) {
flags = static_cast<HAllocate::Flags>(
flags | HAllocate::ALLOCATE_DOUBLE_ALIGNED);
}
HValue* elements =
AddInstruction(new(zone) HAllocate(context, total_size,
HType::JSArray(), flags));
Isolate* isolate = graph()->isolate();
Factory* factory = isolate->factory();
Handle<Map> map = IsFastDoubleElementsKind(kind)
? factory->fixed_double_array_map()
: factory->fixed_array_map();
BuildStoreMap(elements, map, BailoutId::StubEntry());
Handle<String> fixed_array_length_field_name =
isolate->factory()->length_field_symbol();
HInstruction* store_length =
new(zone) HStoreNamedField(elements, fixed_array_length_field_name,
capacity, true, FixedArray::kLengthOffset);
AddInstruction(store_length);
AddSimulate(BailoutId::StubEntry(), FIXED_SIMULATE);
return elements;
}
HInstruction* HGraphBuilder::BuildStoreMap(HValue* object,
HValue* map,
BailoutId id) {
Zone* zone = this->zone();
Isolate* isolate = graph()->isolate();
Factory* factory = isolate->factory();
Handle<String> map_field_name = factory->map_field_symbol();
HInstruction* store_map =
new(zone) HStoreNamedField(object, map_field_name, map,
true, JSObject::kMapOffset);
store_map->SetGVNFlag(kChangesMaps);
AddInstruction(store_map);
AddSimulate(id, FIXED_SIMULATE);
return store_map;
}
HInstruction* HGraphBuilder::BuildStoreMap(HValue* object,
Handle<Map> map,
BailoutId id) {
Zone* zone = this->zone();
HValue* map_constant =
AddInstruction(new(zone) HConstant(map, Representation::Tagged()));
return BuildStoreMap(object, map_constant, id);
}
void HGraphBuilder::BuildCopyElements(HContext* context,
HValue* from_elements,
ElementsKind from_elements_kind,
HValue* to_elements,
ElementsKind to_elements_kind,
HValue* length) {
LoopBuilder builder(this, context, LoopBuilder::kPostIncrement);
HValue* key = builder.BeginBody(graph()->GetConstant0(),
length, Token::LT);
HValue* element =
AddInstruction(new(zone()) HLoadKeyed(from_elements, key, NULL,
from_elements_kind,
ALLOW_RETURN_HOLE));
AddInstruction(new(zone()) HStoreKeyed(to_elements, key, element,
to_elements_kind));
AddSimulate(BailoutId::StubEntry(), REMOVABLE_SIMULATE);
builder.EndBody();
}
HOptimizedGraphBuilder::HOptimizedGraphBuilder(CompilationInfo* info,
TypeFeedbackOracle* oracle)
: HGraphBuilder(info),
function_state_(NULL),
initial_function_state_(this, info, oracle, NORMAL_RETURN),
ast_context_(NULL),
break_scope_(NULL),
inlined_count_(0),
globals_(10, info->zone()),
inline_bailout_(false) {
// 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();
}
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;
}
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),
info_(info),
zone_(info->zone()),
is_recursive_(false),
use_optimistic_licm_(false),
has_soft_deoptimize_(false),
type_change_checksum_(0) {
if (info->IsStub()) {
start_environment_ =
new(zone_) HEnvironment(zone_);
} 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::Canonicalize() {
if (!FLAG_use_canonicalizing) return;
HPhase phase("H_Canonicalize", this);
for (int i = 0; i < blocks()->length(); ++i) {
HInstruction* instr = blocks()->at(i)->first();
while (instr != NULL) {
HValue* value = instr->Canonicalize();
if (value != instr) instr->DeleteAndReplaceWith(value);
instr = instr->next();
}
}
}
// 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() {
HPhase phase("H_Block ordering");
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));
}
}
}
}
// Mark all blocks that are dominated by an unconditional soft deoptimize to
// prevent code motion across those blocks.
void HGraph::PropagateDeoptimizingMark() {
HPhase phase("H_Propagate deoptimizing mark", this);
// Skip this phase if there is nothing to be done anyway.
if (!has_soft_deoptimize()) return;
MarkAsDeoptimizingRecursively(entry_block());
NullifyUnreachableInstructions();
}
void HGraph::MarkAsDeoptimizingRecursively(HBasicBlock* block) {
for (int i = 0; i < block->dominated_blocks()->length(); ++i) {
HBasicBlock* dominated = block->dominated_blocks()->at(i);
if (block->IsDeoptimizing()) dominated->MarkAsDeoptimizing();
MarkAsDeoptimizingRecursively(dominated);
}
}
void HGraph::NullifyUnreachableInstructions() {
if (!FLAG_unreachable_code_elimination) return;
int block_count = blocks_.length();
for (int i = 0; i < block_count; ++i) {
HBasicBlock* block = blocks_.at(i);
bool nullify = false;
const ZoneList<HBasicBlock*>* predecessors = block->predecessors();
int predecessors_length = predecessors->length();
bool all_predecessors_deoptimizing = (predecessors_length > 0);
for (int j = 0; j < predecessors_length; ++j) {
if (!predecessors->at(j)->IsDeoptimizing()) {
all_predecessors_deoptimizing = false;
break;
}
}
if (all_predecessors_deoptimizing) nullify = true;
for (HInstruction* instr = block->first(); instr != NULL;
instr = instr->next()) {
// Leave the basic structure of the graph intact.
if (instr->IsBlockEntry()) continue;
if (instr->IsControlInstruction()) continue;
if (instr->IsSimulate()) continue;
if (instr->IsEnterInlined()) continue;
if (instr->IsLeaveInlined()) continue;
if (nullify) {
HInstruction* last_dummy = NULL;
for (int j = 0; j < instr->OperandCount(); ++j) {
HValue* operand = instr->OperandAt(j);
// Insert an HDummyUse for each operand, unless the operand
// is an HDummyUse itself. If it's even from the same block,
// remember it as a potential replacement for the instruction.
if (operand->IsDummyUse()) {
if (operand->block() == instr->block() &&
last_dummy == NULL) {
last_dummy = HInstruction::cast(operand);
}
continue;
}
if (operand->IsControlInstruction()) {
// Inserting a dummy use for a value that's not defined anywhere
// will fail. Some instructions define fake inputs on such
// values as control flow dependencies.
continue;
}
HDummyUse* dummy = new(zone()) HDummyUse(operand);
dummy->InsertBefore(instr);
last_dummy = dummy;
}
if (last_dummy == NULL) last_dummy = GetConstant1();
instr->DeleteAndReplaceWith(last_dummy);
continue;
}
if (instr->IsSoftDeoptimize()) {
ASSERT(block->IsDeoptimizing());
nullify = true;
}
}
}
}
// Replace all phis consisting of a single non-loop operand plus any number of
// loop operands by that single non-loop operand.
void HGraph::EliminateRedundantPhis() {
HPhase phase("H_Redundant phi elimination", this);
// We do a simple fixed point iteration without any work list, because
// machine-generated JavaScript can lead to a very dense Hydrogen graph with
// an enormous work list and will consequently result in OOM. Experiments
// showed that this simple algorithm is good enough, and even e.g. tracking
// the set or range of blocks to consider is not a real improvement.
bool need_another_iteration;
ZoneList<HPhi*> redundant_phis(blocks_.length(), zone());
do {
need_another_iteration = false;
for (int i = 0; i < blocks_.length(); ++i) {
HBasicBlock* block = blocks_[i];
for (int j = 0; j < block->phis()->length(); j++) {
HPhi* phi = block->phis()->at(j);
HValue* replacement = phi->GetRedundantReplacement();
if (replacement != NULL) {
// Remember phi to avoid concurrent modification of the block's phis.
redundant_phis.Add(phi, zone());
for (HUseIterator it(phi->uses()); !it.Done(); it.Advance()) {
HValue* value = it.value();
value->SetOperandAt(it.index(), replacement);
need_another_iteration |= value->IsPhi();
}
}
}
for (int i = 0; i < redundant_phis.length(); i++) {
block->RemovePhi(redundant_phis[i]);
}
redundant_phis.Clear();
}
} while (need_another_iteration);
#if DEBUG
// Make sure that we *really* removed all redundant phis.
for (int i = 0; i < blocks_.length(); ++i) {
for (int j = 0; j < blocks_[i]->phis()->length(); j++) {
ASSERT(blocks_[i]->phis()->at(j)->GetRedundantReplacement() == NULL);
}
}
#endif
}
void HGraph::EliminateUnreachablePhis() {
HPhase phase("H_Unreachable phi elimination", this);
// Initialize worklist.
ZoneList<HPhi*> phi_list(blocks_.length(), zone());
ZoneList<HPhi*> worklist(blocks_.length(), zone());
for (int i = 0; i < blocks_.length(); ++i) {
for (int j = 0; j < blocks_[i]->phis()->length(); j++) {
HPhi* phi = blocks_[i]->phis()->at(j);
phi_list.Add(phi, zone());
// We can't eliminate phis in the receiver position in the environment
// because in case of throwing an error we need this value to
// construct a stack trace.
if (phi->HasRealUses() || phi->IsReceiver()) {
phi->set_is_live(true);
worklist.Add(phi, zone());
}
}
}
// Iteratively mark live phis.
while (!worklist.is_empty()) {
HPhi* phi = worklist.RemoveLast();
for (int i = 0; i < phi->OperandCount(); i++) {
HValue* operand = phi->OperandAt(i);
if (operand->IsPhi() && !HPhi::cast(operand)->is_live()) {
HPhi::cast(operand)->set_is_live(true);
worklist.Add(HPhi::cast(operand), zone());
}
}
}
// Remove unreachable phis.
for (int i = 0; i < phi_list.length(); i++) {
HPhi* phi = phi_list[i];
if (!phi->is_live()) {
HBasicBlock* block = phi->block();
block->RemovePhi(phi);
block->RecordDeletedPhi(phi->merged_index());
}
}
}
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());
}
}
}
void HGraph::InferTypes(ZoneList<HValue*>* worklist) {
BitVector in_worklist(GetMaximumValueID(), zone());
for (int i = 0; i < worklist->length(); ++i) {
ASSERT(!in_worklist.Contains(worklist->at(i)->id()));
in_worklist.Add(worklist->at(i)->id());
}
while (!worklist->is_empty()) {
HValue* current = worklist->RemoveLast();
in_worklist.Remove(current->id());
if (current->UpdateInferredType()) {
for (HUseIterator it(current->uses()); !it.Done(); it.Advance()) {
HValue* use = it.value();
if (!in_worklist.Contains(use->id())) {
in_worklist.Add(use->id());
worklist->Add(use, zone());
}
}
}
}
}
class HRangeAnalysis BASE_EMBEDDED {
public:
explicit HRangeAnalysis(HGraph* graph) :
graph_(graph), zone_(graph->zone()), changed_ranges_(16, zone_) { }
void Analyze();
private:
void TraceRange(const char* msg, ...);
void Analyze(HBasicBlock* block);
void InferControlFlowRange(HCompareIDAndBranch* test, HBasicBlock* dest);
void UpdateControlFlowRange(Token::Value op, HValue* value, HValue* other);
void InferRange(HValue* value);
void RollBackTo(int index);
void AddRange(HValue* value, Range* range);
HGraph* graph_;
Zone* zone_;
ZoneList<HValue*> changed_ranges_;
};
void HRangeAnalysis::TraceRange(const char* msg, ...) {
if (FLAG_trace_range) {
va_list arguments;
va_start(arguments, msg);
OS::VPrint(msg, arguments);
va_end(arguments);
}
}
void HRangeAnalysis::Analyze() {
HPhase phase("H_Range analysis", graph_);
Analyze(graph_->entry_block());
}
void HRangeAnalysis::Analyze(HBasicBlock* block) {
TraceRange("Analyzing block B%d\n", block->block_id());
int last_changed_range = changed_ranges_.length() - 1;
// Infer range based on control flow.
if (block->predecessors()->length() == 1) {
HBasicBlock* pred = block->predecessors()->first();
if (pred->end()->IsCompareIDAndBranch()) {
InferControlFlowRange(HCompareIDAndBranch::cast(pred->end()), block);
}
}
// Process phi instructions.
for (int i = 0; i < block->phis()->length(); ++i) {
HPhi* phi = block->phis()->at(i);
InferRange(phi);
}
// Go through all instructions of the current block.
HInstruction* instr = block->first();
while (instr != block->end()) {
InferRange(instr);
instr = instr->next();
}
// Continue analysis in all dominated blocks.
for (int i = 0; i < block->dominated_blocks()->length(); ++i) {
Analyze(block->dominated_blocks()->at(i));
}
RollBackTo(last_changed_range);
}
void HRangeAnalysis::InferControlFlowRange(HCompareIDAndBranch* test,
HBasicBlock* dest) {
ASSERT((test->FirstSuccessor() == dest) == (test->SecondSuccessor() != dest));
if (test->representation().IsInteger32()) {
Token::Value op = test->token();
if (test->SecondSuccessor() == dest) {
op = Token::NegateCompareOp(op);
}
Token::Value inverted_op = Token::ReverseCompareOp(op);
UpdateControlFlowRange(op, test->left(), test->right());
UpdateControlFlowRange(inverted_op, test->right(), test->left());
}
}
// We know that value [op] other. Use this information to update the range on
// value.
void HRangeAnalysis::UpdateControlFlowRange(Token::Value op,
HValue* value,
HValue* other) {
Range temp_range;
Range* range = other->range() != NULL ? other->range() : &temp_range;
Range* new_range = NULL;
TraceRange("Control flow range infer %d %s %d\n",
value->id(),
Token::Name(op),
other->id());
if (op == Token::EQ || op == Token::EQ_STRICT) {
// The same range has to apply for value.
new_range = range->Copy(zone_);
} else if (op == Token::LT || op == Token::LTE) {
new_range = range->CopyClearLower(zone_);
if (op == Token::LT) {
new_range->AddConstant(-1);
}
} else if (op == Token::GT || op == Token::GTE) {
new_range = range->CopyClearUpper(zone_);
if (op == Token::GT) {
new_range->AddConstant(1);
}
}
if (new_range != NULL && !new_range->IsMostGeneric()) {
AddRange(value, new_range);
}
}
void HRangeAnalysis::InferRange(HValue* value) {
ASSERT(!value->HasRange());
if (!value->representation().IsNone()) {
value->ComputeInitialRange(zone_);
Range* range = value->range();
TraceRange("Initial inferred range of %d (%s) set to [%d,%d]\n",
value->id(),
value->Mnemonic(),
range->lower(),
range->upper());
}
}
void HRangeAnalysis::RollBackTo(int index) {
for (int i = index + 1; i < changed_ranges_.length(); ++i) {
changed_ranges_[i]->RemoveLastAddedRange();
}
changed_ranges_.Rewind(index + 1);
}
void HRangeAnalysis::AddRange(HValue* value, Range* range) {
Range* original_range = value->range();
value->AddNewRange(range, zone_);
changed_ranges_.Add(value, zone_);
Range* new_range = value->range();
TraceRange("Updated range of %d set to [%d,%d]\n",
value->id(),
new_range->lower(),
new_range->upper());
if (original_range != NULL) {
TraceRange("Original range was [%d,%d]\n",
original_range->lower(),
original_range->upper());
}
TraceRange("New information was [%d,%d]\n",
range->lower(),
range->upper());
}
void TraceGVN(const char* msg, ...) {
va_list arguments;
va_start(arguments, msg);
OS::VPrint(msg, arguments);
va_end(arguments);
}
// Wrap TraceGVN in macros to avoid the expense of evaluating its arguments when
// --trace-gvn is off.
#define TRACE_GVN_1(msg, a1) \
if (FLAG_trace_gvn) { \
TraceGVN(msg, a1); \
}
#define TRACE_GVN_2(msg, a1, a2) \
if (FLAG_trace_gvn) { \
TraceGVN(msg, a1, a2); \
}
#define TRACE_GVN_3(msg, a1, a2, a3) \
if (FLAG_trace_gvn) { \
TraceGVN(msg, a1, a2, a3); \
}
#define TRACE_GVN_4(msg, a1, a2, a3, a4) \
if (FLAG_trace_gvn) { \
TraceGVN(msg, a1, a2, a3, a4); \
}
#define TRACE_GVN_5(msg, a1, a2, a3, a4, a5) \
if (FLAG_trace_gvn) { \
TraceGVN(msg, a1, a2, a3, a4, a5); \
}
HValueMap::HValueMap(Zone* zone, const HValueMap* other)
: array_size_(other->array_size_),
lists_size_(other->lists_size_),
count_(other->count_),
present_flags_(other->present_flags_),
array_(zone->NewArray<HValueMapListElement>(other->array_size_)),
lists_(zone->NewArray<HValueMapListElement>(other->lists_size_)),
free_list_head_(other->free_list_head_) {
memcpy(array_, other->array_, array_size_ * sizeof(HValueMapListElement));
memcpy(lists_, other->lists_, lists_size_ * sizeof(HValueMapListElement));
}
void HValueMap::Kill(GVNFlagSet flags) {
GVNFlagSet depends_flags = HValue::ConvertChangesToDependsFlags(flags);
if (!present_flags_.ContainsAnyOf(depends_flags)) return;
present_flags_.RemoveAll();
for (int i = 0; i < array_size_; ++i) {
HValue* value = array_[i].value;
if (value != NULL) {
// Clear list of collisions first, so we know if it becomes empty.
int kept = kNil; // List of kept elements.
int next;
for (int current = array_[i].next; current != kNil; current = next) {
next = lists_[current].next;
HValue* value = lists_[current].value;
if (value->gvn_flags().ContainsAnyOf(depends_flags)) {
// Drop it.
count_--;
lists_[current].next = free_list_head_;
free_list_head_ = current;
} else {
// Keep it.
lists_[current].next = kept;
kept = current;
present_flags_.Add(value->gvn_flags());
}
}
array_[i].next = kept;
// Now possibly drop directly indexed element.
value = array_[i].value;
if (value->gvn_flags().ContainsAnyOf(depends_flags)) { // Drop it.
count_--;
int head = array_[i].next;
if (head == kNil) {
array_[i].value = NULL;
} else {
array_[i].value = lists_[head].value;
array_[i].next = lists_[head].next;
lists_[head].next = free_list_head_;
free_list_head_ = head;
}
} else {
present_flags_.Add(value->gvn_flags()); // Keep it.
}
}
}
}
HValue* HValueMap::Lookup(HValue* value) const {
uint32_t hash = static_cast<uint32_t>(value->Hashcode());
uint32_t pos = Bound(hash);
if (array_[pos].value != NULL) {
if (array_[pos].value->Equals(value)) return array_[pos].value;
int next = array_[pos].next;
while (next != kNil) {
if (lists_[next].value->Equals(value)) return lists_[next].value;
next = lists_[next].next;
}
}
return NULL;
}
void HValueMap::Resize(int new_size, Zone* zone) {
ASSERT(new_size > count_);
// Hashing the values into the new array has no more collisions than in the
// old hash map, so we can use the existing lists_ array, if we are careful.
// Make sure we have at least one free element.
if (free_list_head_ == kNil) {
ResizeLists(lists_size_ << 1, zone);
}
HValueMapListElement* new_array =
zone->NewArray<HValueMapListElement>(new_size);
memset(new_array, 0, sizeof(HValueMapListElement) * new_size);
HValueMapListElement* old_array = array_;
int old_size = array_size_;
int old_count = count_;
count_ = 0;
// Do not modify present_flags_. It is currently correct.
array_size_ = new_size;
array_ = new_array;
if (old_array != NULL) {
// Iterate over all the elements in lists, rehashing them.
for (int i = 0; i < old_size; ++i) {
if (old_array[i].value != NULL) {
int current = old_array[i].next;
while (current != kNil) {
Insert(lists_[current].value, zone);
int next = lists_[current].next;
lists_[current].next = free_list_head_;
free_list_head_ = current;
current = next;
}
// Rehash the directly stored value.
Insert(old_array[i].value, zone);
}
}
}
USE(old_count);
ASSERT(count_ == old_count);
}
void HValueMap::ResizeLists(int new_size, Zone* zone) {
ASSERT(new_size > lists_size_);
HValueMapListElement* new_lists =
zone->NewArray<HValueMapListElement>(new_size);
memset(new_lists, 0, sizeof(HValueMapListElement) * new_size);
HValueMapListElement* old_lists = lists_;
int old_size = lists_size_;
lists_size_ = new_size;
lists_ = new_lists;
if (old_lists != NULL) {
memcpy(lists_, old_lists, old_size * sizeof(HValueMapListElement));
}
for (int i = old_size; i < lists_size_; ++i) {
lists_[i].next = free_list_head_;
free_list_head_ = i;
}
}
void HValueMap::Insert(HValue* value, Zone* zone) {
ASSERT(value != NULL);
// Resizing when half of the hashtable is filled up.
if (count_ >= array_size_ >> 1) Resize(array_size_ << 1, zone);
ASSERT(count_ < array_size_);
count_++;
uint32_t pos = Bound(static_cast<uint32_t>(value->Hashcode()));
if (array_[pos].value == NULL) {
array_[pos].value = value;
array_[pos].next = kNil;
} else {
if (free_list_head_ == kNil) {
ResizeLists(lists_size_ << 1, zone);
}
int new_element_pos = free_list_head_;
ASSERT(new_element_pos != kNil);
free_list_head_ = lists_[free_list_head_].next;
lists_[new_element_pos].value = value;
lists_[new_element_pos].next = array_[pos].next;
ASSERT(array_[pos].next == kNil || lists_[array_[pos].next].value != NULL);
array_[pos].next = new_element_pos;
}
}
HSideEffectMap::HSideEffectMap() : count_(0) {
memset(data_, 0, kNumberOfTrackedSideEffects * kPointerSize);
}
HSideEffectMap::HSideEffectMap(HSideEffectMap* other) : count_(other->count_) {
*this = *other; // Calls operator=.
}
HSideEffectMap& HSideEffectMap::operator= (const HSideEffectMap& other) {
if (this != &other) {
memcpy(data_, other.data_, kNumberOfTrackedSideEffects * kPointerSize);
}
return *this;
}
void HSideEffectMap::Kill(GVNFlagSet flags) {
for (int i = 0; i < kNumberOfTrackedSideEffects; i++) {
GVNFlag changes_flag = HValue::ChangesFlagFromInt(i);
if (flags.Contains(changes_flag)) {
if (data_[i] != NULL) count_--;
data_[i] = NULL;
}
}
}
void HSideEffectMap::Store(GVNFlagSet flags, HInstruction* instr) {
for (int i = 0; i < kNumberOfTrackedSideEffects; i++) {
GVNFlag changes_flag = HValue::ChangesFlagFromInt(i);
if (flags.Contains(changes_flag)) {
if (data_[i] == NULL) count_++;
data_[i] = instr;
}
}
}
class HStackCheckEliminator BASE_EMBEDDED {
public:
explicit HStackCheckEliminator(HGraph* graph) : graph_(graph) { }
void Process();
private:
HGraph* graph_;
};
void HStackCheckEliminator::Process() {
// For each loop block walk the dominator tree from the backwards branch to
// the loop header. If a call instruction is encountered the backwards branch
// is dominated by a call and the stack check in the backwards branch can be
// removed.
for (int i = 0; i < graph_->blocks()->length(); i++) {
HBasicBlock* block = graph_->blocks()->at(i);
if (block->IsLoopHeader()) {
HBasicBlock* back_edge = block->loop_information()->GetLastBackEdge();
HBasicBlock* dominator = back_edge;
while (true) {
HInstruction* instr = dominator->first();
while (instr != NULL) {
if (instr->IsCall()) {
block->loop_information()->stack_check()->Eliminate();
break;
}
instr = instr->next();
}
// Done when the loop header is processed.
if (dominator == block) break;
// Move up the dominator tree.
dominator = dominator->dominator();
}
}
}
}
// Simple sparse set with O(1) add, contains, and clear.
class SparseSet {
public:
SparseSet(Zone* zone, int capacity)
: capacity_(capacity),
length_(0),
dense_(zone->NewArray<int>(capacity)),
sparse_(zone->NewArray<int>(capacity)) {
#ifndef NVALGRIND
// Initialize the sparse array to make valgrind happy.
memset(sparse_, 0, sizeof(sparse_[0]) * capacity);
#endif
}
bool Contains(int n) const {
ASSERT(0 <= n && n < capacity_);
int d = sparse_[n];
return 0 <= d && d < length_ && dense_[d] == n;
}
bool Add(int n) {
if (Contains(n)) return false;
dense_[length_] = n;
sparse_[n] = length_;
++length_;
return true;
}
void Clear() { length_ = 0; }
private:
int capacity_;
int length_;
int* dense_;
int* sparse_;
DISALLOW_COPY_AND_ASSIGN(SparseSet);
};
class HGlobalValueNumberer BASE_EMBEDDED {
public:
explicit HGlobalValueNumberer(HGraph* graph, CompilationInfo* info)
: graph_(graph),
info_(info),
removed_side_effects_(false),
block_side_effects_(graph->blocks()->length(), graph->zone()),
loop_side_effects_(graph->blocks()->length(), graph->zone()),
visited_on_paths_(graph->zone(), graph->blocks()->length()) {
#ifdef DEBUG
ASSERT(info->isolate()->optimizing_compiler_thread()->IsOptimizerThread() ||
!info->isolate()->heap()->IsAllocationAllowed());
#endif
block_side_effects_.AddBlock(GVNFlagSet(), graph_->blocks()->length(),
graph_->zone());
loop_side_effects_.AddBlock(GVNFlagSet(), graph_->blocks()->length(),
graph_->zone());
}
// Returns true if values with side effects are removed.
bool Analyze();
private:
GVNFlagSet CollectSideEffectsOnPathsToDominatedBlock(
HBasicBlock* dominator,
HBasicBlock* dominated);
void AnalyzeGraph();
void ComputeBlockSideEffects();
void LoopInvariantCodeMotion();
void ProcessLoopBlock(HBasicBlock* block,
HBasicBlock* before_loop,
GVNFlagSet loop_kills,
GVNFlagSet* accumulated_first_time_depends,
GVNFlagSet* accumulated_first_time_changes);
bool AllowCodeMotion();
bool ShouldMove(HInstruction* instr, HBasicBlock* loop_header);
HGraph* graph() { return graph_; }
CompilationInfo* info() { return info_; }
Zone* zone() const { return graph_->zone(); }
HGraph* graph_;
CompilationInfo* info_;
bool removed_side_effects_;
// A map of block IDs to their side effects.
ZoneList<GVNFlagSet> block_side_effects_;
// A map of loop header block IDs to their loop's side effects.
ZoneList<GVNFlagSet> loop_side_effects_;
// Used when collecting side effects on paths from dominator to
// dominated.
SparseSet visited_on_paths_;
};
bool HGlobalValueNumberer::Analyze() {
removed_side_effects_ = false;
ComputeBlockSideEffects();
if (FLAG_loop_invariant_code_motion) {
LoopInvariantCodeMotion();
}
AnalyzeGraph();
return removed_side_effects_;
}
void HGlobalValueNumberer::ComputeBlockSideEffects() {
// The Analyze phase of GVN can be called multiple times. Clear loop side
// effects before computing them to erase the contents from previous Analyze
// passes.
for (int i = 0; i < loop_side_effects_.length(); ++i) {
loop_side_effects_[i].RemoveAll();
}
for (int i = graph_->blocks()->length() - 1; i >= 0; --i) {
// Compute side effects for the block.
HBasicBlock* block = graph_->blocks()->at(i);
HInstruction* instr = block->first();
int id = block->block_id();
GVNFlagSet side_effects;
while (instr != NULL) {
side_effects.Add(instr->ChangesFlags());
if (instr->IsSoftDeoptimize()) {
block_side_effects_[id].RemoveAll();
side_effects.RemoveAll();
break;
}
instr = instr->next();
}
block_side_effects_[id].Add(side_effects);
// Loop headers are part of their loop.
if (block->IsLoopHeader()) {
loop_side_effects_[id].Add(side_effects);
}
// Propagate loop side effects upwards.
if (block->HasParentLoopHeader()) {
int header_id = block->parent_loop_header()->block_id();
loop_side_effects_[header_id].Add(block->IsLoopHeader()
? loop_side_effects_[id]
: side_effects);
}
}
}
SmartArrayPointer<char> GetGVNFlagsString(GVNFlagSet flags) {
char underlying_buffer[kLastFlag * 128];
Vector<char> buffer(underlying_buffer, sizeof(underlying_buffer));
#if DEBUG
int offset = 0;
const char* separator = "";
const char* comma = ", ";
buffer[0] = 0;
uint32_t set_depends_on = 0;
uint32_t set_changes = 0;
for (int bit = 0; bit < kLastFlag; ++bit) {
if ((flags.ToIntegral() & (1 << bit)) != 0) {
if (bit % 2 == 0) {
set_changes++;
} else {
set_depends_on++;
}
}
}
bool positive_changes = set_changes < (kLastFlag / 2);
bool positive_depends_on = set_depends_on < (kLastFlag / 2);
if (set_changes > 0) {
if (positive_changes) {
offset += OS::SNPrintF(buffer + offset, "changes [");
} else {
offset += OS::SNPrintF(buffer + offset, "changes all except [");
}
for (int bit = 0; bit < kLastFlag; ++bit) {
if (((flags.ToIntegral() & (1 << bit)) != 0) == positive_changes) {
switch (static_cast<GVNFlag>(bit)) {
#define DECLARE_FLAG(type) \
case kChanges##type: \
offset += OS::SNPrintF(buffer + offset, separator); \
offset += OS::SNPrintF(buffer + offset, #type); \
separator = comma; \
break;
GVN_TRACKED_FLAG_LIST(DECLARE_FLAG)
GVN_UNTRACKED_FLAG_LIST(DECLARE_FLAG)
#undef DECLARE_FLAG
default:
break;
}
}
}
offset += OS::SNPrintF(buffer + offset, "]");
}
if (set_depends_on > 0) {
separator = "";
if (set_changes > 0) {
offset += OS::SNPrintF(buffer + offset, ", ");
}
if (positive_depends_on) {
offset += OS::SNPrintF(buffer + offset, "depends on [");
} else {
offset += OS::SNPrintF(buffer + offset, "depends on all except [");
}
for (int bit = 0; bit < kLastFlag; ++bit) {
if (((flags.ToIntegral() & (1 << bit)) != 0) == positive_depends_on) {
switch (static_cast<GVNFlag>(bit)) {
#define DECLARE_FLAG(type) \
case kDependsOn##type: \
offset += OS::SNPrintF(buffer + offset, separator); \
offset += OS::SNPrintF(buffer + offset, #type); \
separator = comma; \
break;
GVN_TRACKED_FLAG_LIST(DECLARE_FLAG)
GVN_UNTRACKED_FLAG_LIST(DECLARE_FLAG)
#undef DECLARE_FLAG
default:
break;
}
}
}
offset += OS::SNPrintF(buffer + offset, "]");
}
#else
OS::SNPrintF(buffer, "0x%08X", flags.ToIntegral());
#endif
size_t string_len = strlen(underlying_buffer) + 1;
ASSERT(string_len <= sizeof(underlying_buffer));
char* result = new char[strlen(underlying_buffer) + 1];
memcpy(result, underlying_buffer, string_len);
return SmartArrayPointer<char>(result);
}
void HGlobalValueNumberer::LoopInvariantCodeMotion() {
TRACE_GVN_1("Using optimistic loop invariant code motion: %s\n",
graph_->use_optimistic_licm() ? "yes" : "no");
for (int i = graph_->blocks()->length() - 1; i >= 0; --i) {
HBasicBlock* block = graph_->blocks()->at(i);
if (block->IsLoopHeader()) {
GVNFlagSet side_effects = loop_side_effects_[block->block_id()];
TRACE_GVN_2("Try loop invariant motion for block B%d %s\n",
block->block_id(),
*GetGVNFlagsString(side_effects));
GVNFlagSet accumulated_first_time_depends;
GVNFlagSet accumulated_first_time_changes;
HBasicBlock* last = block->loop_information()->GetLastBackEdge();
for (int j = block->block_id(); j <= last->block_id(); ++j) {
ProcessLoopBlock(graph_->blocks()->at(j), block, side_effects,
&accumulated_first_time_depends,
&accumulated_first_time_changes);
}
}
}
}
void HGlobalValueNumberer::ProcessLoopBlock(
HBasicBlock* block,
HBasicBlock* loop_header,
GVNFlagSet loop_kills,
GVNFlagSet* first_time_depends,
GVNFlagSet* first_time_changes) {
HBasicBlock* pre_header = loop_header->predecessors()->at(0);
GVNFlagSet depends_flags = HValue::ConvertChangesToDependsFlags(loop_kills);
TRACE_GVN_2("Loop invariant motion for B%d %s\n",
block->block_id(),
*GetGVNFlagsString(depends_flags));
HInstruction* instr = block->first();
while (instr != NULL) {
HInstruction* next = instr->next();
bool hoisted = false;
if (instr->CheckFlag(HValue::kUseGVN)) {
TRACE_GVN_4("Checking instruction %d (%s) %s. Loop %s\n",
instr->id(),
instr->Mnemonic(),
*GetGVNFlagsString(instr->gvn_flags()),
*GetGVNFlagsString(loop_kills));
bool can_hoist = !instr->gvn_flags().ContainsAnyOf(depends_flags);
if (can_hoist && !graph()->use_optimistic_licm()) {
can_hoist = block->IsLoopSuccessorDominator();
}
if (can_hoist) {
bool inputs_loop_invariant = true;
for (int i = 0; i < instr->OperandCount(); ++i) {
if (instr->OperandAt(i)->IsDefinedAfter(pre_header)) {
inputs_loop_invariant = false;
}
}
if (inputs_loop_invariant && ShouldMove(instr, loop_header)) {
TRACE_GVN_1("Hoisting loop invariant instruction %d\n", instr->id());
// Move the instruction out of the loop.
instr->Unlink();
instr->InsertBefore(pre_header->end());
if (instr->HasSideEffects()) removed_side_effects_ = true;
hoisted = true;
}
}
}
if (!hoisted) {
// If an instruction is not hoisted, we have to account for its side
// effects when hoisting later HTransitionElementsKind instructions.
GVNFlagSet previous_depends = *first_time_depends;
GVNFlagSet previous_changes = *first_time_changes;
first_time_depends->Add(instr->DependsOnFlags());
first_time_changes->Add(instr->ChangesFlags());
if (!(previous_depends == *first_time_depends)) {
TRACE_GVN_1("Updated first-time accumulated %s\n",
*GetGVNFlagsString(*first_time_depends));
}
if (!(previous_changes == *first_time_changes)) {
TRACE_GVN_1("Updated first-time accumulated %s\n",
*GetGVNFlagsString(*first_time_changes));
}
}
instr = next;
}
}
bool HGlobalValueNumberer::AllowCodeMotion() {
return info()->IsStub() || info()->opt_count() + 1 < FLAG_max_opt_count;
}
bool HGlobalValueNumberer::ShouldMove(HInstruction* instr,
HBasicBlock* loop_header) {
// If we've disabled code motion or we're in a block that unconditionally
// deoptimizes, don't move any instructions.
return AllowCodeMotion() && !instr->block()->IsDeoptimizing();
}
GVNFlagSet HGlobalValueNumberer::CollectSideEffectsOnPathsToDominatedBlock(
HBasicBlock* dominator, HBasicBlock* dominated) {
GVNFlagSet side_effects;
for (int i = 0; i < dominated->predecessors()->length(); ++i) {
HBasicBlock* block = dominated->predecessors()->at(i);
if (dominator->block_id() < block->block_id() &&
block->block_id() < dominated->block_id() &&
visited_on_paths_.Add(block->block_id())) {
side_effects.Add(block_side_effects_[block->block_id()]);
if (block->IsLoopHeader()) {
side_effects.Add(loop_side_effects_[block->block_id()]);
}
side_effects.Add(CollectSideEffectsOnPathsToDominatedBlock(
dominator, block));
}
}
return side_effects;
}
// Each instance of this class is like a "stack frame" for the recursive
// traversal of the dominator tree done during GVN (the stack is handled
// as a double linked list).
// We reuse frames when possible so the list length is limited by the depth
// of the dominator tree but this forces us to initialize each frame calling
// an explicit "Initialize" method instead of a using constructor.
class GvnBasicBlockState: public ZoneObject {
public:
static GvnBasicBlockState* CreateEntry(Zone* zone,
HBasicBlock* entry_block,
HValueMap* entry_map) {
return new(zone)
GvnBasicBlockState(NULL, entry_block, entry_map, NULL, zone);
}
HBasicBlock* block() { return block_; }
HValueMap* map() { return map_; }
HSideEffectMap* dominators() { return &dominators_; }
GvnBasicBlockState* next_in_dominator_tree_traversal(
Zone* zone,
HBasicBlock** dominator) {
// This assignment needs to happen before calling next_dominated() because
// that call can reuse "this" if we are at the last dominated block.
*dominator = block();
GvnBasicBlockState* result = next_dominated(zone);
if (result == NULL) {
GvnBasicBlockState* dominator_state = pop();
if (dominator_state != NULL) {
// This branch is guaranteed not to return NULL because pop() never
// returns a state where "is_done() == true".
*dominator = dominator_state->block();
result = dominator_state->next_dominated(zone);
} else {
// Unnecessary (we are returning NULL) but done for cleanness.
*dominator = NULL;
}
}
return result;
}
private:
void Initialize(HBasicBlock* block,
HValueMap* map,
HSideEffectMap* dominators,
bool copy_map,
Zone* zone) {
block_ = block;
map_ = copy_map ? map->Copy(zone) : map;
dominated_index_ = -1;
length_ = block->dominated_blocks()->length();
if (dominators != NULL) {
dominators_ = *dominators;
}
}
bool is_done() { return dominated_index_ >= length_; }
GvnBasicBlockState(GvnBasicBlockState* previous,
HBasicBlock* block,
HValueMap* map,
HSideEffectMap* dominators,
Zone* zone)
: previous_(previous), next_(NULL) {
Initialize(block, map, dominators, true, zone);
}
GvnBasicBlockState* next_dominated(Zone* zone) {
dominated_index_++;
if (dominated_index_ == length_ - 1) {
// No need to copy the map for the last child in the dominator tree.
Initialize(block_->dominated_blocks()->at(dominated_index_),
map(),
dominators(),
false,
zone);
return this;
} else if (dominated_index_ < length_) {
return push(zone,
block_->dominated_blocks()->at(dominated_index_),
dominators());
} else {
return NULL;
}
}
GvnBasicBlockState* push(Zone* zone,
HBasicBlock* block,
HSideEffectMap* dominators) {
if (next_ == NULL) {
next_ =
new(zone) GvnBasicBlockState(this, block, map(), dominators, zone);
} else {
next_->Initialize(block, map(), dominators, true, zone);
}
return next_;
}
GvnBasicBlockState* pop() {
GvnBasicBlockState* result = previous_;
while (result != NULL && result->is_done()) {
TRACE_GVN_2("Backtracking from block B%d to block b%d\n",
block()->block_id(),
previous_->block()->block_id())
result = result->previous_;
}
return result;
}
GvnBasicBlockState* previous_;
GvnBasicBlockState* next_;
HBasicBlock* block_;
HValueMap* map_;
HSideEffectMap dominators_;
int dominated_index_;
int length_;
};
// This is a recursive traversal of the dominator tree but it has been turned
// into a loop to avoid stack overflows.
// The logical "stack frames" of the recursion are kept in a list of
// GvnBasicBlockState instances.
void HGlobalValueNumberer::AnalyzeGraph() {
HBasicBlock* entry_block = graph_->entry_block();
HValueMap* entry_map = new(zone()) HValueMap(zone());
GvnBasicBlockState* current =
GvnBasicBlockState::CreateEntry(zone(), entry_block, entry_map);
while (current != NULL) {
HBasicBlock* block = current->block();
HValueMap* map = current->map();
HSideEffectMap* dominators = current->dominators();
TRACE_GVN_2("Analyzing block B%d%s\n",
block->block_id(),
block->IsLoopHeader() ? " (loop header)" : "");
// If this is a loop header kill everything killed by the loop.
if (block->IsLoopHeader()) {
map->Kill(loop_side_effects_[block->block_id()]);
}
// Go through all instructions of the current block.
HInstruction* instr = block->first();
while (instr != NULL) {
HInstruction* next = instr->next();
GVNFlagSet flags = instr->ChangesFlags();
if (!flags.IsEmpty()) {
// Clear all instructions in the map that are affected by side effects.
// Store instruction as the dominating one for tracked side effects.
map->Kill(flags);
dominators->Store(flags, instr);
TRACE_GVN_2("Instruction %d %s\n", instr->id(),
*GetGVNFlagsString(flags));
}
if (instr->CheckFlag(HValue::kUseGVN)) {
ASSERT(!instr->HasObservableSideEffects());
HValue* other = map->Lookup(instr);
if (other != NULL) {
ASSERT(instr->Equals(other) && other->Equals(instr));
TRACE_GVN_4("Replacing value %d (%s) with value %d (%s)\n",
instr->id(),
instr->Mnemonic(),
other->id(),
other->Mnemonic());
if (instr->HasSideEffects()) removed_side_effects_ = true;
instr->DeleteAndReplaceWith(other);
} else {
map->Add(instr, zone());
}
}
if (instr->IsLinked() &&
instr->CheckFlag(HValue::kTrackSideEffectDominators)) {
for (int i = 0; i < kNumberOfTrackedSideEffects; i++) {
HValue* other = dominators->at(i);
GVNFlag changes_flag = HValue::ChangesFlagFromInt(i);
GVNFlag depends_on_flag = HValue::DependsOnFlagFromInt(i);
if (instr->DependsOnFlags().Contains(depends_on_flag) &&
(other != NULL)) {
TRACE_GVN_5("Side-effect #%d in %d (%s) is dominated by %d (%s)\n",
i,
instr->id(),
instr->Mnemonic(),
other->id(),
other->Mnemonic());
instr->SetSideEffectDominator(changes_flag, other);
}
}
}
instr = next;
}
HBasicBlock* dominator_block;
GvnBasicBlockState* next =
current->next_in_dominator_tree_traversal(zone(), &dominator_block);
if (next != NULL) {
HBasicBlock* dominated = next->block();
HValueMap* successor_map = next->map();
HSideEffectMap* successor_dominators = next->dominators();
// Kill everything killed on any path between this block and the
// dominated block. We don't have to traverse these paths if the
// value map and the dominators list is already empty. If the range
// of block ids (block_id, dominated_id) is empty there are no such
// paths.
if ((!successor_map->IsEmpty() || !successor_dominators->IsEmpty()) &&
dominator_block->block_id() + 1 < dominated->block_id()) {
visited_on_paths_.Clear();
GVNFlagSet side_effects_on_all_paths =
CollectSideEffectsOnPathsToDominatedBlock(dominator_block,
dominated);
successor_map->Kill(side_effects_on_all_paths);
successor_dominators->Kill(side_effects_on_all_paths);
}
}
current = next;
}
}
void HInferRepresentation::AddToWorklist(HValue* current) {
if (current->representation().IsTagged()) return;
if (!current->CheckFlag(HValue::kFlexibleRepresentation)) return;
if (in_worklist_.Contains(current->id())) return;
worklist_.Add(current, zone());
in_worklist_.Add(current->id());
}
void HInferRepresentation::Analyze() {
HPhase phase("H_Infer representations", graph_);
// (1) Initialize bit vectors and count real uses. Each phi gets a
// bit-vector of length <number of phis>.
const ZoneList<HPhi*>* phi_list = graph_->phi_list();
int phi_count = phi_list->length();
ZoneList<BitVector*> connected_phis(phi_count, graph_->zone());
for (int i = 0; i < phi_count; ++i) {
phi_list->at(i)->InitRealUses(i);
BitVector* connected_set = new(zone()) BitVector(phi_count, graph_->zone());
connected_set->Add(i);
connected_phis.Add(connected_set, zone());
}
// (2) Do a fixed point iteration to find the set of connected phis. A
// phi is connected to another phi if its value is used either directly or
// indirectly through a transitive closure of the def-use relation.
bool change = true;
while (change) {
change = false;
// We normally have far more "forward edges" than "backward edges",
// so we terminate faster when we walk backwards.
for (int i = phi_count - 1; i >= 0; --i) {
HPhi* phi = phi_list->at(i);
for (HUseIterator it(phi->uses()); !it.Done(); it.Advance()) {
HValue* use = it.value();
if (use->IsPhi()) {
int id = HPhi::cast(use)->phi_id();
if (connected_phis[i]->UnionIsChanged(*connected_phis[id]))
change = true;
}
}
}
}
// (3a) Use the phi reachability information from step 2 to
// push information about values which can't be converted to integer
// without deoptimization through the phi use-def chains, avoiding
// unnecessary deoptimizations later.
for (int i = 0; i < phi_count; ++i) {
HPhi* phi = phi_list->at(i);
bool cti = phi->AllOperandsConvertibleToInteger();
if (cti) continue;
for (BitVector::Iterator it(connected_phis.at(i));
!it.Done();
it.Advance()) {
HPhi* phi = phi_list->at(it.Current());
phi->set_is_convertible_to_integer(false);
}
}
// (3b) Use the phi reachability information from step 2 to
// sum up the non-phi use counts of all connected phis.
for (int i = 0; i < phi_count; ++i) {
HPhi* phi = phi_list->at(i);
for (BitVector::Iterator