src/compiler/bytecode-analysis.cc - platform/external/v8 - Git at Google

 // 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);

   if (Bytecodes::WritesAccumulator(bytecode)) {
     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 (Bytecodes::ReadsAccumulator(bytecode)) {
     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
	// 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);

	if (Bytecodes::WritesAccumulator(bytecode)) {
	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 (Bytecodes::ReadsAccumulator(bytecode)) {
	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