Index: src/compiler/bytecode-graph-builder.cc |
diff --git a/src/compiler/bytecode-graph-builder.cc b/src/compiler/bytecode-graph-builder.cc |
index 5f963770075659cb1939025cf35861bd8235407c..bf9eb1df7addf121ab4204094850f3b6ecfcb1d6 100644 |
--- a/src/compiler/bytecode-graph-builder.cc |
+++ b/src/compiler/bytecode-graph-builder.cc |
@@ -4,6 +4,7 @@ |
#include "src/compiler/bytecode-graph-builder.h" |
+#include "src/compiler/bytecode-basic-block-analysis.h" |
#include "src/compiler/linkage.h" |
#include "src/compiler/operator-properties.h" |
#include "src/interpreter/bytecode-array-iterator.h" |
@@ -55,6 +56,21 @@ BytecodeGraphBuilder::Environment::Environment(BytecodeGraphBuilder* builder, |
} |
+BytecodeGraphBuilder::Environment::Environment( |
+ const BytecodeGraphBuilder::Environment* other) |
+ : builder_(other->builder_), |
+ register_count_(other->register_count_), |
+ parameter_count_(other->parameter_count_), |
+ accumulator_(other->accumulator_), |
+ context_(other->context_), |
+ control_dependency_(other->control_dependency_), |
+ effect_dependency_(other->effect_dependency_), |
+ values_(other->zone()), |
+ register_base_(other->register_base_) { |
+ values_ = other->values_; |
+} |
+ |
+ |
int BytecodeGraphBuilder::Environment::RegisterToValuesIndex( |
interpreter::Register the_register) const { |
if (the_register.is_parameter()) { |
@@ -107,12 +123,74 @@ void BytecodeGraphBuilder::Environment::MarkAsUnreachable() { |
} |
+BytecodeGraphBuilder::Environment* |
+BytecodeGraphBuilder::Environment::CopyForLoop() { |
+ PrepareForLoop(); |
+ return new (zone()) Environment(this); |
+} |
+ |
+ |
+BytecodeGraphBuilder::Environment* |
+BytecodeGraphBuilder::Environment::CopyForConditional() const { |
+ return new (zone()) Environment(this); |
+} |
+ |
+ |
+void BytecodeGraphBuilder::Environment::Merge( |
+ BytecodeGraphBuilder::Environment* other) { |
+ // Nothing to do if the other environment is dead. |
+ if (other->IsMarkedAsUnreachable()) { |
+ return; |
+ } |
+ |
+ // Create a merge of the control dependencies of both environments and update |
+ // the current environment's control dependency accordingly. |
+ Node* control = builder()->MergeControl(GetControlDependency(), |
+ other->GetControlDependency()); |
+ UpdateControlDependency(control); |
+ |
+ // Create a merge of the effect dependencies of both environments and update |
+ // the current environment's effect dependency accordingly. |
+ Node* effect = builder()->MergeEffect(GetEffectDependency(), |
+ other->GetEffectDependency(), control); |
+ UpdateEffectDependency(effect); |
+ |
+ // Introduce Phi nodes for values that have differing input at merge points, |
+ // potentially extending an existing Phi node if possible. |
+ accumulator_ = |
+ builder()->MergeValue(accumulator_, other->accumulator_, control); |
+ context_ = builder()->MergeValue(context_, other->context_, control); |
+ for (int i = 0; i < static_cast<int>(values_.size()); i++) { |
+ values_[i] = builder()->MergeValue(values_[i], other->values_[i], control); |
+ } |
+} |
+ |
+ |
+void BytecodeGraphBuilder::Environment::PrepareForLoop() { |
+ Node* control = builder()->NewLoop(); |
+ accumulator_ = builder()->NewPhi(1, accumulator_, control); |
+ context_ = builder()->NewPhi(1, context_, control); |
+ |
+ int size = static_cast<int>(values()->size()); |
+ for (int i = 0; i < size; i++) { |
+ values()->at(i) = builder()->NewPhi(1, values()->at(i), control); |
+ } |
+ Node* effect = builder_->NewEffectPhi(1, GetEffectDependency(), control); |
+ UpdateEffectDependency(effect); |
+ |
+ Node* terminate = builder()->graph()->NewNode( |
+ builder()->common()->Terminate(), effect, control); |
+ builder()->exit_controls_.push_back(terminate); |
+} |
+ |
+ |
BytecodeGraphBuilder::BytecodeGraphBuilder(Zone* local_zone, |
CompilationInfo* compilation_info, |
JSGraph* jsgraph) |
: local_zone_(local_zone), |
info_(compilation_info), |
jsgraph_(jsgraph), |
+ block_environment_infos_(local_zone), |
input_buffer_size_(0), |
input_buffer_(nullptr), |
exit_controls_(local_zone) { |
@@ -241,13 +319,30 @@ bool BytecodeGraphBuilder::CreateGraph(bool stack_check) { |
void BytecodeGraphBuilder::CreateGraphBody(bool stack_check) { |
// TODO(oth): Review ast-graph-builder equivalent, i.e. arguments |
// object setup, this function variable if used, tracing hooks. |
- VisitBytecodes(); |
+ VisitBasicBlocks(); |
} |
-void BytecodeGraphBuilder::VisitBytecodes() { |
+void BytecodeGraphBuilder::VisitBasicBlocks() { |
+ BytecodeBasicBlockAnalysis analyzer(local_zone(), bytecode_array()); |
+ const ZoneVector<BytecodeBasicBlock*>* blocks = analyzer.Analyze(); |
+ |
+ block_environment_infos_.resize(blocks->size()); |
+ for (auto block_iter = blocks->begin(); block_iter != blocks->end(); |
+ block_iter++) { |
+ VisitBytecodesInBasicBlock(*block_iter); |
+ } |
+} |
+ |
+void BytecodeGraphBuilder::VisitBytecodesInBasicBlock( |
+ BytecodeBasicBlock* block) { |
+ set_basic_block(block); |
+ PrepareForNewBasicBlockVisit(); |
+ |
interpreter::BytecodeArrayIterator iterator(bytecode_array()); |
- while (!iterator.done()) { |
+ iterator.AdvanceToOffset(basic_block()->start()); |
+ while (!iterator.done() && |
+ iterator.current_offset() != basic_block()->end()) { |
switch (iterator.current_bytecode()) { |
#define BYTECODE_CASE(name, ...) \ |
case interpreter::Bytecode::k##name: \ |
@@ -258,6 +353,7 @@ void BytecodeGraphBuilder::VisitBytecodes() { |
} |
iterator.Advance(); |
} |
+ CompleteNewBasicBlockVisit(); |
} |
@@ -1118,85 +1214,141 @@ void BytecodeGraphBuilder::VisitToObject( |
void BytecodeGraphBuilder::VisitJump( |
const interpreter::BytecodeArrayIterator& iterator) { |
- UNIMPLEMENTED(); |
+ BuildJump(); |
} |
void BytecodeGraphBuilder::VisitJumpConstant( |
const interpreter::BytecodeArrayIterator& iterator) { |
- UNIMPLEMENTED(); |
+ BuildJump(); |
} |
void BytecodeGraphBuilder::VisitJumpIfTrue( |
const interpreter::BytecodeArrayIterator& iterator) { |
- UNIMPLEMENTED(); |
+ Node* accumulator = environment()->LookupAccumulator(); |
+ Node* comperand = jsgraph()->TrueConstant(); |
+ Node* comparison = |
+ NewNode(javascript()->StrictEqual(), accumulator, comperand); |
+ BuildConditionalJump(comparison); |
} |
void BytecodeGraphBuilder::VisitJumpIfTrueConstant( |
const interpreter::BytecodeArrayIterator& iterator) { |
- UNIMPLEMENTED(); |
+ Node* accumulator = environment()->LookupAccumulator(); |
+ Node* comperand = jsgraph()->TrueConstant(); |
+ Node* comparison = |
+ NewNode(javascript()->StrictEqual(), accumulator, comperand); |
+ BuildConditionalJump(comparison); |
rmcilroy
2015/12/08 13:25:07
Please factor out the common code here into a Buil
oth
2015/12/09 11:26:45
I'd like to keep the control flow aspects and cond
|
} |
void BytecodeGraphBuilder::VisitJumpIfFalse( |
const interpreter::BytecodeArrayIterator& iterator) { |
- UNIMPLEMENTED(); |
+ Node* accumulator = environment()->LookupAccumulator(); |
+ Node* comperand = jsgraph()->FalseConstant(); |
+ Node* comparison = |
+ NewNode(javascript()->StrictEqual(), accumulator, comperand); |
+ BuildConditionalJump(comparison); |
} |
void BytecodeGraphBuilder::VisitJumpIfFalseConstant( |
const interpreter::BytecodeArrayIterator& iterator) { |
- UNIMPLEMENTED(); |
+ Node* accumulator = environment()->LookupAccumulator(); |
+ Node* comperand = jsgraph()->FalseConstant(); |
+ Node* comparison = |
+ NewNode(javascript()->StrictEqual(), accumulator, comperand); |
+ BuildConditionalJump(comparison); |
} |
void BytecodeGraphBuilder::VisitJumpIfToBooleanTrue( |
const interpreter::BytecodeArrayIterator& iterator) { |
- UNIMPLEMENTED(); |
+ Node* accumulator = environment()->LookupAccumulator(); |
+ Node* to_boolean = |
+ NewNode(javascript()->ToBoolean(ToBooleanHint::kAny), accumulator); |
+ Node* comperand = jsgraph()->TrueConstant(); |
+ Node* comparison = |
+ NewNode(javascript()->StrictEqual(), to_boolean, comperand); |
+ BuildConditionalJump(comparison); |
rmcilroy
2015/12/08 13:25:07
ditto, with a BuildJumpIfToBooleanValueEquals(...)
oth
2015/12/09 11:26:45
Done.
|
} |
void BytecodeGraphBuilder::VisitJumpIfToBooleanTrueConstant( |
const interpreter::BytecodeArrayIterator& iterator) { |
- UNIMPLEMENTED(); |
+ Node* accumulator = environment()->LookupAccumulator(); |
+ Node* to_boolean = |
+ NewNode(javascript()->ToBoolean(ToBooleanHint::kAny), accumulator); |
+ Node* comperand = jsgraph()->TrueConstant(); |
+ Node* comparison = |
+ NewNode(javascript()->StrictEqual(), to_boolean, comperand); |
+ BuildConditionalJump(comparison); |
} |
void BytecodeGraphBuilder::VisitJumpIfToBooleanFalse( |
const interpreter::BytecodeArrayIterator& iterator) { |
- UNIMPLEMENTED(); |
+ Node* accumulator = environment()->LookupAccumulator(); |
+ Node* to_boolean = |
+ NewNode(javascript()->ToBoolean(ToBooleanHint::kAny), accumulator); |
+ Node* comperand = jsgraph()->FalseConstant(); |
+ Node* comparison = |
+ NewNode(javascript()->StrictEqual(), to_boolean, comperand); |
+ BuildConditionalJump(comparison); |
} |
void BytecodeGraphBuilder::VisitJumpIfToBooleanFalseConstant( |
const interpreter::BytecodeArrayIterator& iterator) { |
- UNIMPLEMENTED(); |
+ Node* accumulator = environment()->LookupAccumulator(); |
+ Node* to_boolean = |
+ NewNode(javascript()->ToBoolean(ToBooleanHint::kAny), accumulator); |
+ Node* comperand = jsgraph()->FalseConstant(); |
+ Node* comparison = |
+ NewNode(javascript()->StrictEqual(), to_boolean, comperand); |
+ BuildConditionalJump(comparison); |
} |
void BytecodeGraphBuilder::VisitJumpIfNull( |
const interpreter::BytecodeArrayIterator& iterator) { |
- UNIMPLEMENTED(); |
+ Node* accumulator = environment()->LookupAccumulator(); |
+ Node* comperand = jsgraph()->NullConstant(); |
+ Node* comparison = |
+ NewNode(javascript()->StrictEqual(), accumulator, comperand); |
+ BuildConditionalJump(comparison); |
} |
void BytecodeGraphBuilder::VisitJumpIfNullConstant( |
const interpreter::BytecodeArrayIterator& iterator) { |
- UNIMPLEMENTED(); |
+ Node* accumulator = environment()->LookupAccumulator(); |
+ Node* comperand = jsgraph()->NullConstant(); |
+ Node* comparison = |
+ NewNode(javascript()->StrictEqual(), accumulator, comperand); |
+ BuildConditionalJump(comparison); |
} |
void BytecodeGraphBuilder::VisitJumpIfUndefined( |
const interpreter::BytecodeArrayIterator& iterator) { |
- UNIMPLEMENTED(); |
+ Node* accumulator = environment()->LookupAccumulator(); |
+ Node* comperand = jsgraph()->UndefinedConstant(); |
+ Node* comparison = |
+ NewNode(javascript()->StrictEqual(), accumulator, comperand); |
+ BuildConditionalJump(comparison); |
} |
void BytecodeGraphBuilder::VisitJumpIfUndefinedConstant( |
const interpreter::BytecodeArrayIterator& iterator) { |
- UNIMPLEMENTED(); |
+ Node* accumulator = environment()->LookupAccumulator(); |
+ Node* comperand = jsgraph()->UndefinedConstant(); |
+ Node* comparison = |
+ NewNode(javascript()->StrictEqual(), accumulator, comperand); |
+ BuildConditionalJump(comparison); |
} |
@@ -1205,6 +1357,7 @@ void BytecodeGraphBuilder::VisitReturn( |
Node* control = |
NewNode(common()->Return(), environment()->LookupAccumulator()); |
UpdateControlDependencyToLeaveFunction(control); |
+ BuildReturn(); |
} |
@@ -1226,6 +1379,119 @@ void BytecodeGraphBuilder::VisitForInDone( |
} |
+void BytecodeGraphBuilder::PrepareForNewBasicBlockVisit() { |
rmcilroy
2015/12/08 13:25:07
nit - I would drop the "new" here, but don't reall
oth
2015/12/09 11:26:45
Done.
|
+ int block_id = basic_block()->rpo_id(); |
+ |
+ DCHECK_NULL(block_environment_infos_[block_id]); |
+ block_environment_infos_[block_id] = |
+ new (local_zone()) BlockEnvironmentInfo(); |
+ |
+ // Count number of forward and back links to this block |
+ int back_edges = 0; |
+ |
+ // Merge forward links and check for backwards edges |
+ bool default_done = false; |
+ for (size_t i = 0; i < basic_block()->incoming_count(); i++) { |
+ const BytecodeBasicBlock* incoming = basic_block()->incoming(i); |
+ if (incoming->is_dominated_by(basic_block())) { |
+ back_edges++; |
+ } else { |
+ Environment* preceding_environment; |
+ if (incoming->if_true() == basic_block()) { |
+ preceding_environment = |
+ block_environment_infos_[incoming->rpo_id()]->if_true_environment(); |
+ } else { |
+ DCHECK_EQ(incoming->if_false(), basic_block()); |
+ preceding_environment = block_environment_infos_[incoming->rpo_id()] |
+ ->if_false_environment(); |
+ } |
+ |
+ DCHECK_NOT_NULL(preceding_environment); |
+ if (default_done) { |
rmcilroy
2015/12/08 13:25:07
Could you get rid of the default_done boolean by a
oth
2015/12/09 11:26:45
Done.
|
+ environment()->Merge(preceding_environment); |
+ } else { |
+ set_environment(preceding_environment); |
+ default_done = true; |
+ } |
+ } |
+ } |
+ |
+ if (back_edges) { |
rmcilroy
2015/12/08 13:25:07
nit - back_edges != 0
oth
2015/12/09 11:26:45
Done.
|
+ Environment* loop_env = environment()->CopyForLoop(); |
+ block_environment_infos_[block_id]->set_loop_header_environment(loop_env); |
+ } |
+} |
+ |
+ |
+void BytecodeGraphBuilder::CompleteNewBasicBlockVisit() { |
rmcilroy
2015/12/08 13:25:07
ditto
oth
2015/12/09 11:26:45
Done.
|
+ if (!basic_block()->is_exit()) { |
+ int last_offset = basic_block()->last_bytecode_offset(); |
+ interpreter::Bytecode last_bytecode = |
+ interpreter::Bytecodes::FromByte(bytecode_array()->get(last_offset)); |
+ if (!interpreter::Bytecodes::IsLocalControlFlow(last_bytecode)) { |
rmcilroy
2015/12/08 13:25:08
Could you do the IsLocalControlFlow check in the b
oth
2015/12/09 11:26:45
Done.
|
+ DCHECK_NOT_NULL(basic_block()->if_true()); |
+ DCHECK_NULL(basic_block()->if_false()); |
+ DCHECK(basic_block()->if_true() != nullptr); |
+ DCHECK_NOT_NULL(environment()); |
rmcilroy
2015/12/08 13:25:08
Should environment not always be non-null at this
oth
2015/12/09 11:26:45
Change to make the invariant true.
|
+ int block_id = basic_block()->rpo_id(); |
+ block_environment_infos_[block_id]->set_if_true_environment( |
+ environment()); |
+ BuildBackEdgeIfRequired(basic_block()->if_true()); |
rmcilroy
2015/12/08 13:25:07
Would be good to have a comment here one why what
oth
2015/12/09 11:26:45
Done.
|
+ } |
+ } |
+ set_environment(nullptr); |
+} |
+ |
+ |
+void BytecodeGraphBuilder::BuildReturn() { |
+ DCHECK_NOT_NULL(basic_block()->if_true()); |
+ DCHECK_NULL(basic_block()->if_false()); |
+ int block_id = basic_block()->rpo_id(); |
+ block_environment_infos_[block_id]->set_if_true_environment(environment()); |
+ set_environment(nullptr); |
+} |
+ |
+ |
+void BytecodeGraphBuilder::BuildBackEdgeIfRequired(BytecodeBasicBlock* target) { |
rmcilroy
2015/12/08 13:25:07
nit - move above BuildReturn (group BuildReturn /
oth
2015/12/09 11:26:45
Done.
|
+ if (basic_block()->is_dominated_by(target)) { |
+ BytecodeBasicBlock* loop_header = target; |
+ BlockEnvironmentInfo* info = |
+ block_environment_infos_[loop_header->rpo_id()]; |
+ info->loop_header_environment()->Merge(environment()); |
+ } |
+} |
+ |
+ |
+void BytecodeGraphBuilder::BuildJump() { |
+ DCHECK_NOT_NULL(basic_block()->if_true()); |
+ DCHECK_NULL(basic_block()->if_false()); |
+ int block_id = basic_block()->rpo_id(); |
+ block_environment_infos_[block_id]->set_if_true_environment(environment()); |
+ BuildBackEdgeIfRequired(basic_block()->if_true()); |
+ set_environment(nullptr); |
+} |
+ |
+ |
+void BytecodeGraphBuilder::BuildConditionalJump(Node* condition) { |
+ DCHECK_NOT_NULL(basic_block()->if_true()); |
+ DCHECK_NOT_NULL(basic_block()->if_false()); |
+ int block_id = basic_block()->rpo_id(); |
+ NewBranch(condition); |
+ // Save environment for false branch. |
+ Environment* saved_env = environment()->CopyForConditional(); |
+ // Process true branch. |
+ NewIfTrue(); |
+ block_environment_infos_[block_id]->set_if_true_environment(environment()); |
+ BuildBackEdgeIfRequired(basic_block()->if_true()); |
+ // Restore environment and process false branch. |
+ set_environment(saved_env); |
+ NewIfFalse(); |
+ block_environment_infos_[block_id]->set_if_false_environment(environment()); |
+ BuildBackEdgeIfRequired(basic_block()->if_false()); |
+ set_environment(nullptr); |
+} |
+ |
+ |
Node** BytecodeGraphBuilder::EnsureInputBufferSize(int size) { |
if (size > input_buffer_size_) { |
size = size + kInputBufferSizeIncrement + input_buffer_size_; |
@@ -1298,6 +1564,26 @@ Node* BytecodeGraphBuilder::MakeNode(const Operator* op, int value_input_count, |
} |
+Node* BytecodeGraphBuilder::NewPhi(int count, Node* input, Node* control) { |
+ const Operator* phi_op = common()->Phi(kMachAnyTagged, count); |
+ Node** buffer = EnsureInputBufferSize(count + 1); |
+ MemsetPointer(buffer, input, count); |
+ buffer[count] = control; |
+ return graph()->NewNode(phi_op, count + 1, buffer, true); |
+} |
+ |
+ |
+// TODO(mstarzinger): Revisit this once we have proper effect states. |
+Node* BytecodeGraphBuilder::NewEffectPhi(int count, Node* input, |
+ Node* control) { |
+ const Operator* phi_op = common()->EffectPhi(count); |
+ Node** buffer = EnsureInputBufferSize(count + 1); |
+ MemsetPointer(buffer, input, count); |
+ buffer[count] = control; |
+ return graph()->NewNode(phi_op, count + 1, buffer, true); |
+} |
+ |
+ |
Node* BytecodeGraphBuilder::MergeControl(Node* control, Node* other) { |
int inputs = control->op()->ControlInputCount() + 1; |
if (control->opcode() == IrOpcode::kLoop) { |
@@ -1320,6 +1606,40 @@ Node* BytecodeGraphBuilder::MergeControl(Node* control, Node* other) { |
} |
+Node* BytecodeGraphBuilder::MergeEffect(Node* value, Node* other, |
+ Node* control) { |
+ int inputs = control->op()->ControlInputCount(); |
+ if (value->opcode() == IrOpcode::kEffectPhi && |
+ NodeProperties::GetControlInput(value) == control) { |
+ // Phi already exists, add input. |
+ value->InsertInput(graph_zone(), inputs - 1, other); |
+ NodeProperties::ChangeOp(value, common()->EffectPhi(inputs)); |
+ } else if (value != other) { |
+ // Phi does not exist yet, introduce one. |
+ value = NewEffectPhi(inputs, value, control); |
+ value->ReplaceInput(inputs - 1, other); |
+ } |
+ return value; |
+} |
+ |
+ |
+Node* BytecodeGraphBuilder::MergeValue(Node* value, Node* other, |
+ Node* control) { |
+ int inputs = control->op()->ControlInputCount(); |
+ if (value->opcode() == IrOpcode::kPhi && |
+ NodeProperties::GetControlInput(value) == control) { |
+ // Phi already exists, add input. |
+ value->InsertInput(graph_zone(), inputs - 1, other); |
+ NodeProperties::ChangeOp(value, common()->Phi(kMachAnyTagged, inputs)); |
+ } else if (value != other) { |
+ // Phi does not exist yet, introduce one. |
+ value = NewPhi(inputs, value, control); |
+ value->ReplaceInput(inputs - 1, other); |
+ } |
+ return value; |
+} |
+ |
+ |
void BytecodeGraphBuilder::UpdateControlDependencyToLeaveFunction(Node* exit) { |
if (environment()->IsMarkedAsUnreachable()) return; |
environment()->MarkAsUnreachable(); |