diff options
Diffstat (limited to 'deps/v8/src/compiler/bytecode-analysis.cc')
| -rw-r--r-- | deps/v8/src/compiler/bytecode-analysis.cc | 622 |
1 files changed, 622 insertions, 0 deletions
diff --git a/deps/v8/src/compiler/bytecode-analysis.cc b/deps/v8/src/compiler/bytecode-analysis.cc new file mode 100644 index 0000000000..f0e870739b --- /dev/null +++ b/deps/v8/src/compiler/bytecode-analysis.cc @@ -0,0 +1,622 @@ +// Copyright 2016 the V8 project authors. All rights reserved. +// Use of this source code is governed by a BSD-style license that can be +// found in the LICENSE file. + +#include "src/compiler/bytecode-analysis.h" + +#include "src/interpreter/bytecode-array-iterator.h" +#include "src/interpreter/bytecode-array-random-iterator.h" +#include "src/objects-inl.h" + +namespace v8 { +namespace internal { +namespace compiler { + +using namespace interpreter; + +BytecodeLoopAssignments::BytecodeLoopAssignments(int parameter_count, + int register_count, Zone* zone) + : parameter_count_(parameter_count), + bit_vector_(new (zone) + BitVector(parameter_count + register_count, zone)) {} + +void BytecodeLoopAssignments::Add(interpreter::Register r) { + if (r.is_parameter()) { + bit_vector_->Add(r.ToParameterIndex(parameter_count_)); + } else { + bit_vector_->Add(parameter_count_ + r.index()); + } +} + +void BytecodeLoopAssignments::AddPair(interpreter::Register r) { + if (r.is_parameter()) { + DCHECK(interpreter::Register(r.index() + 1).is_parameter()); + bit_vector_->Add(r.ToParameterIndex(parameter_count_)); + bit_vector_->Add(r.ToParameterIndex(parameter_count_) + 1); + } else { + DCHECK(!interpreter::Register(r.index() + 1).is_parameter()); + bit_vector_->Add(parameter_count_ + r.index()); + bit_vector_->Add(parameter_count_ + r.index() + 1); + } +} + +void BytecodeLoopAssignments::AddTriple(interpreter::Register r) { + if (r.is_parameter()) { + DCHECK(interpreter::Register(r.index() + 1).is_parameter()); + DCHECK(interpreter::Register(r.index() + 2).is_parameter()); + bit_vector_->Add(r.ToParameterIndex(parameter_count_)); + bit_vector_->Add(r.ToParameterIndex(parameter_count_) + 1); + bit_vector_->Add(r.ToParameterIndex(parameter_count_) + 2); + } else { + DCHECK(!interpreter::Register(r.index() + 1).is_parameter()); + DCHECK(!interpreter::Register(r.index() + 2).is_parameter()); + bit_vector_->Add(parameter_count_ + r.index()); + bit_vector_->Add(parameter_count_ + r.index() + 1); + bit_vector_->Add(parameter_count_ + r.index() + 2); + } +} + +void BytecodeLoopAssignments::AddAll() { bit_vector_->AddAll(); } + +void BytecodeLoopAssignments::Union(const BytecodeLoopAssignments& other) { + bit_vector_->Union(*other.bit_vector_); +} + +bool BytecodeLoopAssignments::ContainsParameter(int index) const { + DCHECK_GE(index, 0); + DCHECK_LT(index, parameter_count()); + return bit_vector_->Contains(index); +} + +bool BytecodeLoopAssignments::ContainsLocal(int index) const { + DCHECK_GE(index, 0); + DCHECK_LT(index, local_count()); + return bit_vector_->Contains(parameter_count_ + index); +} + +bool BytecodeLoopAssignments::ContainsAccumulator() const { + // TODO(leszeks): This assumes the accumulator is always assigned. This is + // probably correct, but that assignment is also probably dead, so we should + // check liveness. + return true; +} + +BytecodeAnalysis::BytecodeAnalysis(Handle<BytecodeArray> bytecode_array, + Zone* zone, bool do_liveness_analysis) + : bytecode_array_(bytecode_array), + do_liveness_analysis_(do_liveness_analysis), + zone_(zone), + loop_stack_(zone), + loop_end_index_queue_(zone), + end_to_header_(zone), + header_to_info_(zone), + liveness_map_(bytecode_array->length(), zone) {} + +namespace { + +void UpdateInLiveness(Bytecode bytecode, BytecodeLivenessState& in_liveness, + const BytecodeArrayAccessor& accessor) { + int num_operands = Bytecodes::NumberOfOperands(bytecode); + const OperandType* operand_types = Bytecodes::GetOperandTypes(bytecode); + AccumulatorUse accumulator_use = Bytecodes::GetAccumulatorUse(bytecode); + + if (accumulator_use == AccumulatorUse::kWrite) { + in_liveness.MarkAccumulatorDead(); + } + for (int i = 0; i < num_operands; ++i) { + switch (operand_types[i]) { + case OperandType::kRegOut: { + interpreter::Register r = accessor.GetRegisterOperand(i); + if (!r.is_parameter()) { + in_liveness.MarkRegisterDead(r.index()); + } + break; + } + case OperandType::kRegOutPair: { + interpreter::Register r = accessor.GetRegisterOperand(i); + if (!r.is_parameter()) { + DCHECK(!interpreter::Register(r.index() + 1).is_parameter()); + in_liveness.MarkRegisterDead(r.index()); + in_liveness.MarkRegisterDead(r.index() + 1); + } + break; + } + case OperandType::kRegOutTriple: { + interpreter::Register r = accessor.GetRegisterOperand(i); + if (!r.is_parameter()) { + DCHECK(!interpreter::Register(r.index() + 1).is_parameter()); + DCHECK(!interpreter::Register(r.index() + 2).is_parameter()); + in_liveness.MarkRegisterDead(r.index()); + in_liveness.MarkRegisterDead(r.index() + 1); + in_liveness.MarkRegisterDead(r.index() + 2); + } + break; + } + default: + DCHECK(!Bytecodes::IsRegisterOutputOperandType(operand_types[i])); + break; + } + } + + if (accumulator_use == AccumulatorUse::kRead) { + in_liveness.MarkAccumulatorLive(); + } + for (int i = 0; i < num_operands; ++i) { + switch (operand_types[i]) { + case OperandType::kReg: { + interpreter::Register r = accessor.GetRegisterOperand(i); + if (!r.is_parameter()) { + in_liveness.MarkRegisterLive(r.index()); + } + break; + } + case OperandType::kRegPair: { + interpreter::Register r = accessor.GetRegisterOperand(i); + if (!r.is_parameter()) { + DCHECK(!interpreter::Register(r.index() + 1).is_parameter()); + in_liveness.MarkRegisterLive(r.index()); + in_liveness.MarkRegisterLive(r.index() + 1); + } + break; + } + case OperandType::kRegList: { + interpreter::Register r = accessor.GetRegisterOperand(i++); + uint32_t reg_count = accessor.GetRegisterCountOperand(i); + if (!r.is_parameter()) { + for (uint32_t j = 0; j < reg_count; ++j) { + DCHECK(!interpreter::Register(r.index() + j).is_parameter()); + in_liveness.MarkRegisterLive(r.index() + j); + } + } + } + default: + DCHECK(!Bytecodes::IsRegisterInputOperandType(operand_types[i])); + break; + } + } +} + +void UpdateOutLiveness(Bytecode bytecode, BytecodeLivenessState& out_liveness, + BytecodeLivenessState* next_bytecode_in_liveness, + const BytecodeArrayAccessor& accessor, + const BytecodeLivenessMap& liveness_map) { + int current_offset = accessor.current_offset(); + const Handle<BytecodeArray>& bytecode_array = accessor.bytecode_array(); + + // Update from jump target (if any). Skip loops, we update these manually in + // the liveness iterations. + if (Bytecodes::IsForwardJump(bytecode)) { + int target_offset = accessor.GetJumpTargetOffset(); + out_liveness.Union(*liveness_map.GetInLiveness(target_offset)); + } + + // Update from next bytecode (unless there isn't one or this is an + // unconditional jump). + if (next_bytecode_in_liveness != nullptr && + !Bytecodes::IsUnconditionalJump(bytecode)) { + out_liveness.Union(*next_bytecode_in_liveness); + } + + // Update from exception handler (if any). + if (!interpreter::Bytecodes::IsWithoutExternalSideEffects(bytecode)) { + int handler_context; + // TODO(leszeks): We should look up this range only once per entry. + HandlerTable* table = HandlerTable::cast(bytecode_array->handler_table()); + int handler_offset = + table->LookupRange(current_offset, &handler_context, nullptr); + + if (handler_offset != -1) { + out_liveness.Union(*liveness_map.GetInLiveness(handler_offset)); + out_liveness.MarkRegisterLive(handler_context); + } + } +} + +void UpdateAssignments(Bytecode bytecode, BytecodeLoopAssignments& assignments, + const BytecodeArrayAccessor& accessor) { + int num_operands = Bytecodes::NumberOfOperands(bytecode); + const OperandType* operand_types = Bytecodes::GetOperandTypes(bytecode); + + for (int i = 0; i < num_operands; ++i) { + switch (operand_types[i]) { + case OperandType::kRegOut: { + assignments.Add(accessor.GetRegisterOperand(i)); + break; + } + case OperandType::kRegOutPair: { + assignments.AddPair(accessor.GetRegisterOperand(i)); + break; + } + case OperandType::kRegOutTriple: { + assignments.AddTriple(accessor.GetRegisterOperand(i)); + break; + } + default: + DCHECK(!Bytecodes::IsRegisterOutputOperandType(operand_types[i])); + break; + } + } +} + +} // namespace + +void BytecodeAnalysis::Analyze(BailoutId osr_bailout_id) { + loop_stack_.push({-1, nullptr}); + + BytecodeLivenessState* next_bytecode_in_liveness = nullptr; + + int osr_loop_end_offset = + osr_bailout_id.IsNone() ? -1 : osr_bailout_id.ToInt(); + + BytecodeArrayRandomIterator iterator(bytecode_array(), zone()); + for (iterator.GoToEnd(); iterator.IsValid(); --iterator) { + Bytecode bytecode = iterator.current_bytecode(); + int current_offset = iterator.current_offset(); + + if (bytecode == Bytecode::kJumpLoop) { + // Every byte up to and including the last byte within the backwards jump + // instruction is considered part of the loop, set loop end accordingly. + int loop_end = current_offset + iterator.current_bytecode_size(); + PushLoop(iterator.GetJumpTargetOffset(), loop_end); + + // Normally prefixed bytecodes are treated as if the prefix's offset was + // the actual bytecode's offset. However, the OSR id is the offset of the + // actual JumpLoop bytecode, so we need to find the location of that + // bytecode ignoring the prefix. + int jump_loop_offset = current_offset + iterator.current_prefix_offset(); + bool is_osr_loop = (jump_loop_offset == osr_loop_end_offset); + + // Check that is_osr_loop is set iff the osr_loop_end_offset is within + // this bytecode. + DCHECK(!is_osr_loop || + iterator.OffsetWithinBytecode(osr_loop_end_offset)); + + // OSR "assigns" everything to OSR values on entry into an OSR loop, so we + // need to make sure to considered everything to be assigned. + if (is_osr_loop) { + loop_stack_.top().loop_info->assignments().AddAll(); + } + + // Save the index so that we can do another pass later. + if (do_liveness_analysis_) { + loop_end_index_queue_.push_back(iterator.current_index()); + } + } else if (loop_stack_.size() > 1) { + LoopStackEntry& current_loop = loop_stack_.top(); + LoopInfo* current_loop_info = current_loop.loop_info; + + // TODO(leszeks): Ideally, we'd only set values that were assigned in + // the loop *and* are live when the loop exits. However, this requires + // tracking the out-liveness of *all* loop exits, which is not + // information we currently have. + UpdateAssignments(bytecode, current_loop_info->assignments(), iterator); + + if (current_offset == current_loop.header_offset) { + loop_stack_.pop(); + if (loop_stack_.size() > 1) { + // Propagate inner loop assignments to outer loop. + loop_stack_.top().loop_info->assignments().Union( + current_loop_info->assignments()); + } + } + } + + if (do_liveness_analysis_) { + BytecodeLiveness& liveness = liveness_map_.InitializeLiveness( + current_offset, bytecode_array()->register_count(), zone()); + + UpdateOutLiveness(bytecode, *liveness.out, next_bytecode_in_liveness, + iterator, liveness_map_); + liveness.in->CopyFrom(*liveness.out); + UpdateInLiveness(bytecode, *liveness.in, iterator); + + next_bytecode_in_liveness = liveness.in; + } + } + + DCHECK_EQ(loop_stack_.size(), 1u); + DCHECK_EQ(loop_stack_.top().header_offset, -1); + + if (!do_liveness_analysis_) return; + + // At this point, every bytecode has a valid in and out liveness, except for + // propagating liveness across back edges (i.e. JumpLoop). Subsequent liveness + // analysis iterations can only add additional liveness bits that are pulled + // across these back edges. + // + // Furthermore, a loop header's in-liveness can only change based on any + // bytecodes *after* the loop end -- it cannot change as a result of the + // JumpLoop liveness being updated, as the only liveness bits than can be + // added to the loop body are those of the loop header. + // + // So, if we know that the liveness of bytecodes after a loop header won't + // change (e.g. because there are no loops in them, or we have already ensured + // those loops are valid), we can safely update the loop end and pass over the + // loop body, and then never have to pass over that loop end again, because we + // have shown that its target, the loop header, can't change from the entries + // after the loop, and can't change from any loop body pass. + // + // This means that in a pass, we can iterate backwards over the bytecode + // array, process any loops that we encounter, and on subsequent passes we can + // skip processing those loops (though we still have to process inner loops). + // + // Equivalently, we can queue up loop ends from back to front, and pass over + // the loops in that order, as this preserves both the bottom-to-top and + // outer-to-inner requirements. + + for (int loop_end_index : loop_end_index_queue_) { + iterator.GoToIndex(loop_end_index); + + DCHECK_EQ(iterator.current_bytecode(), Bytecode::kJumpLoop); + + int header_offset = iterator.GetJumpTargetOffset(); + int end_offset = iterator.current_offset(); + + BytecodeLiveness& header_liveness = + liveness_map_.GetLiveness(header_offset); + BytecodeLiveness& end_liveness = liveness_map_.GetLiveness(end_offset); + + if (!end_liveness.out->UnionIsChanged(*header_liveness.in)) { + // Only update the loop body if the loop end liveness changed. + continue; + } + end_liveness.in->CopyFrom(*end_liveness.out); + next_bytecode_in_liveness = end_liveness.in; + + // Advance into the loop body. + --iterator; + for (; iterator.current_offset() > header_offset; --iterator) { + Bytecode bytecode = iterator.current_bytecode(); + + int current_offset = iterator.current_offset(); + BytecodeLiveness& liveness = liveness_map_.GetLiveness(current_offset); + + UpdateOutLiveness(bytecode, *liveness.out, next_bytecode_in_liveness, + iterator, liveness_map_); + liveness.in->CopyFrom(*liveness.out); + UpdateInLiveness(bytecode, *liveness.in, iterator); + + next_bytecode_in_liveness = liveness.in; + } + // Now we are at the loop header. Since the in-liveness of the header + // can't change, we need only to update the out-liveness. + UpdateOutLiveness(iterator.current_bytecode(), *header_liveness.out, + next_bytecode_in_liveness, iterator, liveness_map_); + } + + DCHECK(LivenessIsValid()); +} + +void BytecodeAnalysis::PushLoop(int loop_header, int loop_end) { + DCHECK(loop_header < loop_end); + DCHECK(loop_stack_.top().header_offset < loop_header); + DCHECK(end_to_header_.find(loop_end) == end_to_header_.end()); + DCHECK(header_to_info_.find(loop_header) == header_to_info_.end()); + + int parent_offset = loop_stack_.top().header_offset; + + end_to_header_.insert({loop_end, loop_header}); + auto it = header_to_info_.insert( + {loop_header, LoopInfo(parent_offset, bytecode_array_->parameter_count(), + bytecode_array_->register_count(), zone_)}); + // Get the loop info pointer from the output of insert. + LoopInfo* loop_info = &it.first->second; + + loop_stack_.push({loop_header, loop_info}); +} + +bool BytecodeAnalysis::IsLoopHeader(int offset) const { + return header_to_info_.find(offset) != header_to_info_.end(); +} + +int BytecodeAnalysis::GetLoopOffsetFor(int offset) const { + auto loop_end_to_header = end_to_header_.upper_bound(offset); + // If there is no next end => offset is not in a loop. + if (loop_end_to_header == end_to_header_.end()) { + return -1; + } + // If the header preceeds the offset, this is the loop + // + // .> header <--loop_end_to_header + // | + // | <--offset + // | + // `- end + if (loop_end_to_header->second <= offset) { + return loop_end_to_header->second; + } + // Otherwise there is a (potentially nested) loop after this offset. + // + // <--offset + // + // .> header + // | + // | .> header <--loop_end_to_header + // | | + // | `- end + // | + // `- end + // We just return the parent of the next loop (might be -1). + DCHECK(header_to_info_.upper_bound(offset) != header_to_info_.end()); + + return header_to_info_.upper_bound(offset)->second.parent_offset(); +} + +const LoopInfo& BytecodeAnalysis::GetLoopInfoFor(int header_offset) const { + DCHECK(IsLoopHeader(header_offset)); + + return header_to_info_.find(header_offset)->second; +} + +const BytecodeLivenessState* BytecodeAnalysis::GetInLivenessFor( + int offset) const { + if (!do_liveness_analysis_) return nullptr; + + return liveness_map_.GetInLiveness(offset); +} + +const BytecodeLivenessState* BytecodeAnalysis::GetOutLivenessFor( + int offset) const { + if (!do_liveness_analysis_) return nullptr; + + return liveness_map_.GetOutLiveness(offset); +} + +std::ostream& BytecodeAnalysis::PrintLivenessTo(std::ostream& os) const { + interpreter::BytecodeArrayIterator iterator(bytecode_array()); + + for (; !iterator.done(); iterator.Advance()) { + int current_offset = iterator.current_offset(); + + const BitVector& in_liveness = + GetInLivenessFor(current_offset)->bit_vector(); + const BitVector& out_liveness = + GetOutLivenessFor(current_offset)->bit_vector(); + + for (int i = 0; i < in_liveness.length(); ++i) { + os << (in_liveness.Contains(i) ? "L" : "."); + } + os << " -> "; + + for (int i = 0; i < out_liveness.length(); ++i) { + os << (out_liveness.Contains(i) ? "L" : "."); + } + + os << " | " << current_offset << ": "; + iterator.PrintTo(os) << std::endl; + } + + return os; +} + +#if DEBUG +bool BytecodeAnalysis::LivenessIsValid() { + BytecodeArrayRandomIterator iterator(bytecode_array(), zone()); + + BytecodeLivenessState previous_liveness(bytecode_array()->register_count(), + zone()); + + int invalid_offset = -1; + int which_invalid = -1; + + BytecodeLivenessState* next_bytecode_in_liveness = nullptr; + + // Ensure that there are no liveness changes if we iterate one more time. + for (iterator.GoToEnd(); iterator.IsValid(); --iterator) { + Bytecode bytecode = iterator.current_bytecode(); + + int current_offset = iterator.current_offset(); + + BytecodeLiveness& liveness = liveness_map_.GetLiveness(current_offset); + + previous_liveness.CopyFrom(*liveness.out); + + UpdateOutLiveness(bytecode, *liveness.out, next_bytecode_in_liveness, + iterator, liveness_map_); + // UpdateOutLiveness skips kJumpLoop, so we update it manually. + if (bytecode == Bytecode::kJumpLoop) { + int target_offset = iterator.GetJumpTargetOffset(); + liveness.out->Union(*liveness_map_.GetInLiveness(target_offset)); + } + + if (!liveness.out->Equals(previous_liveness)) { + // Reset the invalid liveness. + liveness.out->CopyFrom(previous_liveness); + invalid_offset = current_offset; + which_invalid = 1; + break; + } + + previous_liveness.CopyFrom(*liveness.in); + + liveness.in->CopyFrom(*liveness.out); + UpdateInLiveness(bytecode, *liveness.in, iterator); + + if (!liveness.in->Equals(previous_liveness)) { + // Reset the invalid liveness. + liveness.in->CopyFrom(previous_liveness); + invalid_offset = current_offset; + which_invalid = 0; + break; + } + + next_bytecode_in_liveness = liveness.in; + } + + if (invalid_offset != -1) { + OFStream of(stderr); + of << "Invalid liveness:" << std::endl; + + // Dump the bytecode, annotated with the liveness and marking loops. + + int loop_indent = 0; + + BytecodeArrayIterator forward_iterator(bytecode_array()); + for (; !forward_iterator.done(); forward_iterator.Advance()) { + int current_offset = forward_iterator.current_offset(); + const BitVector& in_liveness = + GetInLivenessFor(current_offset)->bit_vector(); + const BitVector& out_liveness = + GetOutLivenessFor(current_offset)->bit_vector(); + + for (int i = 0; i < in_liveness.length(); ++i) { + of << (in_liveness.Contains(i) ? 'L' : '.'); + } + + of << " | "; + + for (int i = 0; i < out_liveness.length(); ++i) { + of << (out_liveness.Contains(i) ? 'L' : '.'); + } + + of << " : " << current_offset << " : "; + + // Draw loop back edges by indentin everything between loop headers and + // jump loop instructions. + if (forward_iterator.current_bytecode() == Bytecode::kJumpLoop) { + loop_indent--; + } + for (int i = 0; i < loop_indent; ++i) { + of << " | "; + } + if (forward_iterator.current_bytecode() == Bytecode::kJumpLoop) { + of << " `-" << current_offset; + } else if (IsLoopHeader(current_offset)) { + of << " .>" << current_offset; + loop_indent++; + } + forward_iterator.PrintTo(of) << std::endl; + + if (current_offset == invalid_offset) { + // Underline the invalid liveness. + if (which_invalid == 0) { + for (int i = 0; i < in_liveness.length(); ++i) { + of << '^'; + } + } else { + for (int i = 0; i < in_liveness.length() + 3; ++i) { + of << ' '; + } + for (int i = 0; i < out_liveness.length(); ++i) { + of << '^'; + } + } + + // Make sure to draw the loop indentation marks on this additional line. + of << " : " << current_offset << " : "; + for (int i = 0; i < loop_indent; ++i) { + of << " | "; + } + + of << std::endl; + } + } + } + + return invalid_offset == -1; +} +#endif + +} // namespace compiler +} // namespace internal +} // namespace v8 |