Index: src/compiler/bytecode-graph-builder.cc |
diff --git a/src/compiler/bytecode-graph-builder.cc b/src/compiler/bytecode-graph-builder.cc |
index 96c1415c5fbf5168b00d0b76ca61b1ab65a0c80f..267d8e7e777f5585248c5cfff8f85ba464dc8f6e 100644 |
--- a/src/compiler/bytecode-graph-builder.cc |
+++ b/src/compiler/bytecode-graph-builder.cc |
@@ -4,9 +4,9 @@ |
#include "src/compiler/bytecode-graph-builder.h" |
+#include "src/compiler/bytecode-branch-analysis.h" |
#include "src/compiler/linkage.h" |
#include "src/compiler/operator-properties.h" |
-#include "src/interpreter/bytecode-array-iterator.h" |
#include "src/interpreter/bytecodes.h" |
namespace v8 { |
@@ -55,6 +55,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 +122,75 @@ 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), |
+ merge_environments_(local_zone), |
+ loop_header_environments_(local_zone), |
input_buffer_size_(0), |
input_buffer_(nullptr), |
exit_controls_(local_zone) { |
@@ -247,18 +325,28 @@ void BytecodeGraphBuilder::CreateGraphBody(bool stack_check) { |
void BytecodeGraphBuilder::VisitBytecodes() { |
+ BytecodeBranchAnalysis analysis(bytecode_array(), local_zone()); |
+ analysis.Analyze(); |
+ set_branch_analysis(&analysis); |
interpreter::BytecodeArrayIterator iterator(bytecode_array()); |
+ set_bytecode_iterator(&iterator); |
while (!iterator.done()) { |
- switch (iterator.current_bytecode()) { |
+ if (analysis.is_reachable(iterator.current_offset())) { |
+ ApplyBranchAnalysis(&analysis); |
+ |
+ switch (iterator.current_bytecode()) { |
#define BYTECODE_CASE(name, ...) \ |
case interpreter::Bytecode::k##name: \ |
Visit##name(iterator); \ |
break; |
- BYTECODE_LIST(BYTECODE_CASE) |
+ BYTECODE_LIST(BYTECODE_CASE) |
#undef BYTECODE_CODE |
+ } |
} |
iterator.Advance(); |
} |
+ set_branch_analysis(nullptr); |
+ set_bytecode_iterator(nullptr); |
} |
@@ -1174,85 +1262,97 @@ 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* condition = BuildJumpCondition(jsgraph()->TrueConstant()); |
+ BuildConditionalJump(condition); |
} |
void BytecodeGraphBuilder::VisitJumpIfTrueConstant( |
const interpreter::BytecodeArrayIterator& iterator) { |
- UNIMPLEMENTED(); |
+ Node* condition = BuildJumpCondition(jsgraph()->TrueConstant()); |
+ BuildConditionalJump(condition); |
} |
void BytecodeGraphBuilder::VisitJumpIfFalse( |
const interpreter::BytecodeArrayIterator& iterator) { |
- UNIMPLEMENTED(); |
+ Node* condition = BuildJumpCondition(jsgraph()->FalseConstant()); |
+ BuildConditionalJump(condition); |
} |
void BytecodeGraphBuilder::VisitJumpIfFalseConstant( |
const interpreter::BytecodeArrayIterator& iterator) { |
- UNIMPLEMENTED(); |
+ Node* condition = BuildJumpCondition(jsgraph()->FalseConstant()); |
+ BuildConditionalJump(condition); |
} |
void BytecodeGraphBuilder::VisitJumpIfToBooleanTrue( |
const interpreter::BytecodeArrayIterator& iterator) { |
- UNIMPLEMENTED(); |
+ Node* condition = BuildToBooleanJumpCondition(jsgraph()->TrueConstant()); |
+ BuildConditionalJump(condition); |
} |
void BytecodeGraphBuilder::VisitJumpIfToBooleanTrueConstant( |
const interpreter::BytecodeArrayIterator& iterator) { |
- UNIMPLEMENTED(); |
+ Node* condition = BuildToBooleanJumpCondition(jsgraph()->TrueConstant()); |
+ BuildConditionalJump(condition); |
} |
void BytecodeGraphBuilder::VisitJumpIfToBooleanFalse( |
const interpreter::BytecodeArrayIterator& iterator) { |
- UNIMPLEMENTED(); |
+ Node* condition = BuildToBooleanJumpCondition(jsgraph()->FalseConstant()); |
+ BuildConditionalJump(condition); |
} |
void BytecodeGraphBuilder::VisitJumpIfToBooleanFalseConstant( |
const interpreter::BytecodeArrayIterator& iterator) { |
- UNIMPLEMENTED(); |
+ Node* condition = BuildToBooleanJumpCondition(jsgraph()->FalseConstant()); |
+ BuildConditionalJump(condition); |
} |
void BytecodeGraphBuilder::VisitJumpIfNull( |
const interpreter::BytecodeArrayIterator& iterator) { |
- UNIMPLEMENTED(); |
+ Node* condition = BuildJumpCondition(jsgraph()->NullConstant()); |
+ BuildConditionalJump(condition); |
} |
void BytecodeGraphBuilder::VisitJumpIfNullConstant( |
const interpreter::BytecodeArrayIterator& iterator) { |
- UNIMPLEMENTED(); |
+ Node* condition = BuildJumpCondition(jsgraph()->NullConstant()); |
+ BuildConditionalJump(condition); |
} |
void BytecodeGraphBuilder::VisitJumpIfUndefined( |
const interpreter::BytecodeArrayIterator& iterator) { |
- UNIMPLEMENTED(); |
+ Node* condition = BuildJumpCondition(jsgraph()->UndefinedConstant()); |
+ BuildConditionalJump(condition); |
} |
void BytecodeGraphBuilder::VisitJumpIfUndefinedConstant( |
const interpreter::BytecodeArrayIterator& iterator) { |
- UNIMPLEMENTED(); |
+ Node* condition = BuildJumpCondition(jsgraph()->UndefinedConstant()); |
+ BuildConditionalJump(condition); |
} |
@@ -1261,6 +1361,7 @@ void BytecodeGraphBuilder::VisitReturn( |
Node* control = |
NewNode(common()->Return(), environment()->LookupAccumulator()); |
UpdateControlDependencyToLeaveFunction(control); |
+ set_environment(nullptr); |
} |
@@ -1282,6 +1383,87 @@ void BytecodeGraphBuilder::VisitForInDone( |
} |
+void BytecodeGraphBuilder::ApplyBranchAnalysis( |
rmcilroy
2015/12/15 17:35:43
Not keen on the name. How about MergeEnvironmentWi
oth
2015/12/15 22:42:17
Done.
|
+ const BytecodeBranchAnalysis* analysis) { |
+ int current_offset = bytecode_iterator()->current_offset(); |
+ if (analysis->forward_branches_target(current_offset)) { |
+ // Merge environments of branches that reach this bytecode. |
+ auto branch_sites = analysis->ForwardBranchesTargetting(current_offset); |
+ Environment* merged = merge_environments_[branch_sites->at(0)]; |
+ for (size_t i = 1; i < branch_sites->size(); i++) { |
+ DCHECK_LT(branch_sites->at(i), current_offset); |
+ merged->Merge(merge_environments_[branch_sites->at(i)]); |
+ } |
+ if (environment()) { |
+ merged->Merge(environment()); |
+ set_environment(nullptr); |
rmcilroy
2015/12/15 17:35:43
why set nullptr here and set to merged immediately
oth
2015/12/15 22:42:17
Churn, removed.
|
+ } |
+ set_environment(merged); |
+ } |
+ |
+ if (analysis->backward_branches_target(current_offset)) { |
+ // Add loop header and store a copy so we can connect merged back |
+ // edge inputs to the loop header. |
+ loop_header_environments_[current_offset] = environment()->CopyForLoop(); |
+ } |
+} |
+ |
+ |
+void BytecodeGraphBuilder::BuildJump(int source_offset, int target_offset) { |
+ DCHECK_NULL(merge_environments_[source_offset]); |
+ merge_environments_[source_offset] = environment(); |
+ if (source_offset >= target_offset) { |
+ // Back branch check if all branches to target offset are |
+ // satisfied. |
+ const ZoneVector<int>* back_branches = |
+ branch_analysis()->BackwardBranchesTargetting(target_offset); |
+ if (back_branches->back() == source_offset) { |
rmcilroy
2015/12/15 17:35:43
Use IsLastBackwardBranchTo here (or remove that fu
oth
2015/12/15 22:42:17
Removed it, want the branches immediately if true.
|
+ // The set of back branches is complete, merge them. |
+ Environment* environment = merge_environments_[back_branches->at(0)]; |
+ for (size_t i = 1; i < back_branches->size(); i++) { |
+ environment->Merge(merge_environments_[back_branches->at(i)]); |
+ } |
+ // And now merge with loop header environment created when loop |
+ // header was visited. |
+ loop_header_environments_[target_offset]->Merge(environment); |
rmcilroy
2015/12/15 17:35:43
nit - could we pull the back-branch stuff out into
oth
2015/12/15 22:42:17
Done.
|
+ } |
+ } |
+ set_environment(nullptr); |
+} |
+ |
+ |
+void BytecodeGraphBuilder::BuildJump() { |
+ int source_offset = bytecode_iterator()->current_offset(); |
+ int target_offset = bytecode_iterator()->GetJumpTargetOffset(); |
+ BuildJump(source_offset, target_offset); |
+} |
+ |
+ |
+void BytecodeGraphBuilder::BuildConditionalJump(Node* condition) { |
+ int source_offset = bytecode_iterator()->current_offset(); |
+ NewBranch(condition); |
+ Environment* if_false_environment = environment()->CopyForConditional(); |
+ NewIfTrue(); |
+ BuildJump(source_offset, bytecode_iterator()->GetJumpTargetOffset()); |
+ set_environment(if_false_environment); |
+ NewIfFalse(); |
+} |
+ |
+ |
+Node* BytecodeGraphBuilder::BuildJumpCondition(Node* comperand) { |
+ Node* accumulator = environment()->LookupAccumulator(); |
+ return NewNode(javascript()->StrictEqual(), accumulator, comperand); |
+} |
+ |
+ |
+Node* BytecodeGraphBuilder::BuildToBooleanJumpCondition(Node* comperand) { |
+ Node* accumulator = environment()->LookupAccumulator(); |
+ Node* to_boolean = |
+ NewNode(javascript()->ToBoolean(ToBooleanHint::kAny), accumulator); |
+ return NewNode(javascript()->StrictEqual(), to_boolean, comperand); |
+} |
+ |
+ |
Node** BytecodeGraphBuilder::EnsureInputBufferSize(int size) { |
if (size > input_buffer_size_) { |
size = size + kInputBufferSizeIncrement + input_buffer_size_; |
@@ -1354,6 +1536,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(MachineRepresentation::kTagged, 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) { |
@@ -1376,6 +1578,42 @@ 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(MachineRepresentation::kTagged, 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(); |