LCOV - code coverage report
Current view: top level - src/compiler - bytecode-analysis.cc (source / functions) Hit Total Coverage
Test: app.info Lines: 145 164 88.4 %
Date: 2017-04-26 Functions: 18 21 85.7 %

          Line data    Source code
       1             : // Copyright 2016 the V8 project authors. All rights reserved.
       2             : // Use of this source code is governed by a BSD-style license that can be
       3             : // found in the LICENSE file.
       4             : 
       5             : #include "src/compiler/bytecode-analysis.h"
       6             : 
       7             : #include "src/interpreter/bytecode-array-iterator.h"
       8             : #include "src/interpreter/bytecode-array-random-iterator.h"
       9             : #include "src/objects-inl.h"
      10             : 
      11             : namespace v8 {
      12             : namespace internal {
      13             : namespace compiler {
      14             : 
      15             : using namespace interpreter;
      16             : 
      17       56573 : BytecodeLoopAssignments::BytecodeLoopAssignments(int parameter_count,
      18             :                                                  int register_count, Zone* zone)
      19             :     : parameter_count_(parameter_count),
      20             :       bit_vector_(new (zone)
      21      113146 :                       BitVector(parameter_count + register_count, zone)) {}
      22             : 
      23      677114 : void BytecodeLoopAssignments::Add(interpreter::Register r) {
      24      677114 :   if (r.is_parameter()) {
      25      677114 :     bit_vector_->Add(r.ToParameterIndex(parameter_count_));
      26             :   } else {
      27      674372 :     bit_vector_->Add(parameter_count_ + r.index());
      28             :   }
      29      677114 : }
      30             : 
      31          48 : void BytecodeLoopAssignments::AddPair(interpreter::Register r) {
      32          48 :   if (r.is_parameter()) {
      33             :     DCHECK(interpreter::Register(r.index() + 1).is_parameter());
      34          48 :     bit_vector_->Add(r.ToParameterIndex(parameter_count_));
      35           0 :     bit_vector_->Add(r.ToParameterIndex(parameter_count_) + 1);
      36             :   } else {
      37             :     DCHECK(!interpreter::Register(r.index() + 1).is_parameter());
      38          48 :     bit_vector_->Add(parameter_count_ + r.index());
      39          48 :     bit_vector_->Add(parameter_count_ + r.index() + 1);
      40             :   }
      41          48 : }
      42             : 
      43         183 : void BytecodeLoopAssignments::AddTriple(interpreter::Register r) {
      44         183 :   if (r.is_parameter()) {
      45             :     DCHECK(interpreter::Register(r.index() + 1).is_parameter());
      46             :     DCHECK(interpreter::Register(r.index() + 2).is_parameter());
      47         183 :     bit_vector_->Add(r.ToParameterIndex(parameter_count_));
      48           0 :     bit_vector_->Add(r.ToParameterIndex(parameter_count_) + 1);
      49           0 :     bit_vector_->Add(r.ToParameterIndex(parameter_count_) + 2);
      50             :   } else {
      51             :     DCHECK(!interpreter::Register(r.index() + 1).is_parameter());
      52             :     DCHECK(!interpreter::Register(r.index() + 2).is_parameter());
      53         183 :     bit_vector_->Add(parameter_count_ + r.index());
      54         183 :     bit_vector_->Add(parameter_count_ + r.index() + 1);
      55         183 :     bit_vector_->Add(parameter_count_ + r.index() + 2);
      56             :   }
      57         183 : }
      58             : 
      59        5745 : void BytecodeLoopAssignments::AddAll() { bit_vector_->AddAll(); }
      60             : 
      61           0 : void BytecodeLoopAssignments::Union(const BytecodeLoopAssignments& other) {
      62        9328 :   bit_vector_->Union(*other.bit_vector_);
      63           0 : }
      64             : 
      65      467424 : bool BytecodeLoopAssignments::ContainsParameter(int index) const {
      66             :   DCHECK_GE(index, 0);
      67             :   DCHECK_LT(index, parameter_count());
      68      934848 :   return bit_vector_->Contains(index);
      69             : }
      70             : 
      71     4807956 : bool BytecodeLoopAssignments::ContainsLocal(int index) const {
      72             :   DCHECK_GE(index, 0);
      73             :   DCHECK_LT(index, local_count());
      74     9615912 :   return bit_vector_->Contains(parameter_count_ + index);
      75             : }
      76             : 
      77      226366 : bool BytecodeLoopAssignments::ContainsAccumulator() const {
      78             :   // TODO(leszeks): This assumes the accumulator is always assigned. This is
      79             :   // probably correct, but that assignment is also probably dead, so we should
      80             :   // check liveness.
      81      226366 :   return true;
      82             : }
      83             : 
      84      430875 : BytecodeAnalysis::BytecodeAnalysis(Handle<BytecodeArray> bytecode_array,
      85             :                                    Zone* zone, bool do_liveness_analysis)
      86             :     : bytecode_array_(bytecode_array),
      87             :       do_liveness_analysis_(do_liveness_analysis),
      88             :       zone_(zone),
      89             :       loop_stack_(zone),
      90             :       loop_end_index_queue_(zone),
      91             :       end_to_header_(zone),
      92             :       header_to_info_(zone),
      93             :       osr_entry_point_(-1),
      94     1292625 :       liveness_map_(bytecode_array->length(), zone) {}
      95             : 
      96             : namespace {
      97             : 
      98    16436030 : void UpdateInLiveness(Bytecode bytecode, BytecodeLivenessState& in_liveness,
      99             :                       const BytecodeArrayAccessor& accessor) {
     100             :   int num_operands = Bytecodes::NumberOfOperands(bytecode);
     101             :   const OperandType* operand_types = Bytecodes::GetOperandTypes(bytecode);
     102             : 
     103    16436030 :   if (Bytecodes::WritesAccumulator(bytecode)) {
     104             :     in_liveness.MarkAccumulatorDead();
     105             :   }
     106    21615124 :   for (int i = 0; i < num_operands; ++i) {
     107    21615149 :     switch (operand_types[i]) {
     108             :       case OperandType::kRegOut: {
     109     5211416 :         interpreter::Register r = accessor.GetRegisterOperand(i);
     110     5211391 :         if (!r.is_parameter()) {
     111             :           in_liveness.MarkRegisterDead(r.index());
     112             :         }
     113             :         break;
     114             :       }
     115             :       case OperandType::kRegOutPair: {
     116         699 :         interpreter::Register r = accessor.GetRegisterOperand(i);
     117         699 :         if (!r.is_parameter()) {
     118             :           DCHECK(!interpreter::Register(r.index() + 1).is_parameter());
     119             :           in_liveness.MarkRegisterDead(r.index());
     120         699 :           in_liveness.MarkRegisterDead(r.index() + 1);
     121             :         }
     122             :         break;
     123             :       }
     124             :       case OperandType::kRegOutTriple: {
     125        1678 :         interpreter::Register r = accessor.GetRegisterOperand(i);
     126        1678 :         if (!r.is_parameter()) {
     127             :           DCHECK(!interpreter::Register(r.index() + 1).is_parameter());
     128             :           DCHECK(!interpreter::Register(r.index() + 2).is_parameter());
     129             :           in_liveness.MarkRegisterDead(r.index());
     130        1678 :           in_liveness.MarkRegisterDead(r.index() + 1);
     131        1678 :           in_liveness.MarkRegisterDead(r.index() + 2);
     132             :         }
     133             :         break;
     134             :       }
     135             :       default:
     136             :         DCHECK(!Bytecodes::IsRegisterOutputOperandType(operand_types[i]));
     137             :         break;
     138             :     }
     139             :   }
     140             : 
     141    16436005 :   if (Bytecodes::ReadsAccumulator(bytecode)) {
     142             :     in_liveness.MarkAccumulatorLive();
     143             :   }
     144    21197875 :   for (int i = 0; i < num_operands; ++i) {
     145    21197885 :     switch (operand_types[i]) {
     146             :       case OperandType::kReg: {
     147     5222207 :         interpreter::Register r = accessor.GetRegisterOperand(i);
     148     5222197 :         if (!r.is_parameter()) {
     149             :           in_liveness.MarkRegisterLive(r.index());
     150             :         }
     151             :         break;
     152             :       }
     153             :       case OperandType::kRegPair: {
     154        3169 :         interpreter::Register r = accessor.GetRegisterOperand(i);
     155        3169 :         if (!r.is_parameter()) {
     156             :           DCHECK(!interpreter::Register(r.index() + 1).is_parameter());
     157             :           in_liveness.MarkRegisterLive(r.index());
     158        3169 :           in_liveness.MarkRegisterLive(r.index() + 1);
     159             :         }
     160             :         break;
     161             :       }
     162             :       case OperandType::kRegList: {
     163      417235 :         interpreter::Register r = accessor.GetRegisterOperand(i++);
     164      417235 :         uint32_t reg_count = accessor.GetRegisterCountOperand(i);
     165      417235 :         if (!r.is_parameter()) {
     166     1640982 :           for (uint32_t j = 0; j < reg_count; ++j) {
     167             :             DCHECK(!interpreter::Register(r.index() + j).is_parameter());
     168     1640982 :             in_liveness.MarkRegisterLive(r.index() + j);
     169             :           }
     170             :         }
     171             :       }
     172             :       default:
     173             :         DCHECK(!Bytecodes::IsRegisterInputOperandType(operand_types[i]));
     174             :         break;
     175             :     }
     176             :   }
     177    16435995 : }
     178             : 
     179    16487052 : void UpdateOutLiveness(Bytecode bytecode, BytecodeLivenessState& out_liveness,
     180             :                        BytecodeLivenessState* next_bytecode_in_liveness,
     181    16487052 :                        const BytecodeArrayAccessor& accessor,
     182             :                        const BytecodeLivenessMap& liveness_map) {
     183             :   int current_offset = accessor.current_offset();
     184             :   const Handle<BytecodeArray>& bytecode_array = accessor.bytecode_array();
     185             : 
     186             :   // Update from jump target (if any). Skip loops, we update these manually in
     187             :   // the liveness iterations.
     188    16487052 :   if (Bytecodes::IsForwardJump(bytecode)) {
     189      982666 :     int target_offset = accessor.GetJumpTargetOffset();
     190             :     out_liveness.Union(*liveness_map.GetInLiveness(target_offset));
     191             :   }
     192             : 
     193             :   // Update from next bytecode (unless there isn't one or this is an
     194             :   // unconditional jump).
     195    32546179 :   if (next_bytecode_in_liveness != nullptr &&
     196             :       !Bytecodes::IsUnconditionalJump(bytecode)) {
     197             :     out_liveness.Union(*next_bytecode_in_liveness);
     198             :   }
     199             : 
     200             :   // Update from exception handler (if any).
     201    16487052 :   if (!interpreter::Bytecodes::IsWithoutExternalSideEffects(bytecode)) {
     202             :     int handler_context;
     203             :     // TODO(leszeks): We should look up this range only once per entry.
     204             :     HandlerTable* table = HandlerTable::cast(bytecode_array->handler_table());
     205             :     int handler_offset =
     206     5918844 :         table->LookupRange(current_offset, &handler_context, nullptr);
     207             : 
     208     5918845 :     if (handler_offset != -1) {
     209             :       out_liveness.Union(*liveness_map.GetInLiveness(handler_offset));
     210      609553 :       out_liveness.MarkRegisterLive(handler_context);
     211             :     }
     212             :   }
     213    16487076 : }
     214             : 
     215     2269084 : void UpdateAssignments(Bytecode bytecode, BytecodeLoopAssignments& assignments,
     216             :                        const BytecodeArrayAccessor& accessor) {
     217             :   int num_operands = Bytecodes::NumberOfOperands(bytecode);
     218             :   const OperandType* operand_types = Bytecodes::GetOperandTypes(bytecode);
     219             : 
     220     5386609 :   for (int i = 0; i < num_operands; ++i) {
     221     3117529 :     switch (operand_types[i]) {
     222             :       case OperandType::kRegOut: {
     223      677118 :         assignments.Add(accessor.GetRegisterOperand(i));
     224      677114 :         break;
     225             :       }
     226             :       case OperandType::kRegOutPair: {
     227          48 :         assignments.AddPair(accessor.GetRegisterOperand(i));
     228          48 :         break;
     229             :       }
     230             :       case OperandType::kRegOutTriple: {
     231         183 :         assignments.AddTriple(accessor.GetRegisterOperand(i));
     232         183 :         break;
     233             :       }
     234             :       default:
     235             :         DCHECK(!Bytecodes::IsRegisterOutputOperandType(operand_types[i]));
     236             :         break;
     237             :     }
     238             :   }
     239     2269080 : }
     240             : 
     241             : }  // namespace
     242             : 
     243    15036798 : void BytecodeAnalysis::Analyze(BailoutId osr_bailout_id) {
     244      861750 :   loop_stack_.push({-1, nullptr});
     245             : 
     246             :   BytecodeLivenessState* next_bytecode_in_liveness = nullptr;
     247             : 
     248             :   int osr_loop_end_offset =
     249      430875 :       osr_bailout_id.IsNone() ? -1 : osr_bailout_id.ToInt();
     250             : 
     251      430875 :   BytecodeArrayRandomIterator iterator(bytecode_array(), zone());
     252    14760126 :   for (iterator.GoToEnd(); iterator.IsValid(); --iterator) {
     253    14329250 :     Bytecode bytecode = iterator.current_bytecode();
     254    14329246 :     int current_offset = iterator.current_offset();
     255             : 
     256    14329246 :     if (bytecode == Bytecode::kJumpLoop) {
     257             :       // Every byte up to and including the last byte within the backwards jump
     258             :       // instruction is considered part of the loop, set loop end accordingly.
     259       56573 :       int loop_end = current_offset + iterator.current_bytecode_size();
     260       56573 :       int loop_header = iterator.GetJumpTargetOffset();
     261       56573 :       PushLoop(loop_header, loop_end);
     262             : 
     263             :       // Normally prefixed bytecodes are treated as if the prefix's offset was
     264             :       // the actual bytecode's offset. However, the OSR id is the offset of the
     265             :       // actual JumpLoop bytecode, so we need to find the location of that
     266             :       // bytecode ignoring the prefix.
     267       56573 :       int jump_loop_offset = current_offset + iterator.current_prefix_offset();
     268             :       bool is_osr_loop = (jump_loop_offset == osr_loop_end_offset);
     269             : 
     270             :       // Check that is_osr_loop is set iff the osr_loop_end_offset is within
     271             :       // this bytecode.
     272             :       DCHECK(!is_osr_loop ||
     273             :              iterator.OffsetWithinBytecode(osr_loop_end_offset));
     274             : 
     275       56573 :       if (is_osr_loop) {
     276        5745 :         osr_entry_point_ = loop_header;
     277             :         // OSR "assigns" everything to OSR values on entry into an OSR loop, so
     278             :         // we need to make sure to considered everything to be assigned.
     279        5745 :         loop_stack_.top().loop_info->assignments().AddAll();
     280             :       }
     281             : 
     282             :       // Save the index so that we can do another pass later.
     283       56575 :       if (do_liveness_analysis_) {
     284      112030 :         loop_end_index_queue_.push_back(iterator.current_index());
     285             :       }
     286    14272673 :     } else if (loop_stack_.size() > 1) {
     287             :       LoopStackEntry& current_loop = loop_stack_.top();
     288     2269085 :       LoopInfo* current_loop_info = current_loop.loop_info;
     289             : 
     290             :       // TODO(leszeks): Ideally, we'd only set values that were assigned in
     291             :       // the loop *and* are live when the loop exits. However, this requires
     292             :       // tracking the out-liveness of *all* loop exits, which is not
     293             :       // information we currently have.
     294     2269085 :       UpdateAssignments(bytecode, current_loop_info->assignments(), iterator);
     295             : 
     296     2269081 :       if (current_offset == current_loop.header_offset) {
     297             :         loop_stack_.pop();
     298       56573 :         if (loop_stack_.size() > 1) {
     299             :           // Propagate inner loop assignments to outer loop.
     300        9328 :           loop_stack_.top().loop_info->assignments().Union(
     301             :               current_loop_info->assignments());
     302             :         }
     303             :       }
     304             :     }
     305             : 
     306    14329244 :     if (do_liveness_analysis_) {
     307             :       BytecodeLiveness& liveness = liveness_map_.InitializeLiveness(
     308    14175048 :           current_offset, bytecode_array()->register_count(), zone());
     309             : 
     310             :       UpdateOutLiveness(bytecode, *liveness.out, next_bytecode_in_liveness,
     311    14175071 :                         iterator, liveness_map_);
     312    14175079 :       liveness.in->CopyFrom(*liveness.out);
     313    14175080 :       UpdateInLiveness(bytecode, *liveness.in, iterator);
     314             : 
     315    14175059 :       next_bytecode_in_liveness = liveness.in;
     316             :     }
     317             :   }
     318             : 
     319             :   DCHECK_EQ(loop_stack_.size(), 1u);
     320             :   DCHECK_EQ(loop_stack_.top().header_offset, -1);
     321             : 
     322      861750 :   if (!do_liveness_analysis_) return;
     323             : 
     324             :   // At this point, every bytecode has a valid in and out liveness, except for
     325             :   // propagating liveness across back edges (i.e. JumpLoop). Subsequent liveness
     326             :   // analysis iterations can only add additional liveness bits that are pulled
     327             :   // across these back edges.
     328             :   //
     329             :   // Furthermore, a loop header's in-liveness can only change based on any
     330             :   // bytecodes *after* the loop end --  it cannot change as a result of the
     331             :   // JumpLoop liveness being updated, as the only liveness bits than can be
     332             :   // added to the loop body are those of the loop header.
     333             :   //
     334             :   // So, if we know that the liveness of bytecodes after a loop header won't
     335             :   // change (e.g. because there are no loops in them, or we have already ensured
     336             :   // those loops are valid), we can safely update the loop end and pass over the
     337             :   // loop body, and then never have to pass over that loop end again, because we
     338             :   // have shown that its target, the loop header, can't change from the entries
     339             :   // after the loop, and can't change from any loop body pass.
     340             :   //
     341             :   // This means that in a pass, we can iterate backwards over the bytecode
     342             :   // array, process any loops that we encounter, and on subsequent passes we can
     343             :   // skip processing those loops (though we still have to process inner loops).
     344             :   //
     345             :   // Equivalently, we can queue up loop ends from back to front, and pass over
     346             :   // the loops in that order, as this preserves both the bottom-to-top and
     347             :   // outer-to-inner requirements.
     348             : 
     349      911877 :   for (int loop_end_index : loop_end_index_queue_) {
     350             :     iterator.GoToIndex(loop_end_index);
     351             : 
     352             :     DCHECK_EQ(iterator.current_bytecode(), Bytecode::kJumpLoop);
     353             : 
     354       56015 :     int header_offset = iterator.GetJumpTargetOffset();
     355       56015 :     int end_offset = iterator.current_offset();
     356             : 
     357             :     BytecodeLiveness& header_liveness =
     358       56015 :         liveness_map_.GetLiveness(header_offset);
     359       56015 :     BytecodeLiveness& end_liveness = liveness_map_.GetLiveness(end_offset);
     360             : 
     361      112030 :     if (!end_liveness.out->UnionIsChanged(*header_liveness.in)) {
     362             :       // Only update the loop body if the loop end liveness changed.
     363             :       continue;
     364             :     }
     365       51052 :     end_liveness.in->CopyFrom(*end_liveness.out);
     366       51052 :     next_bytecode_in_liveness = end_liveness.in;
     367             : 
     368             :     // Advance into the loop body.
     369             :     --iterator;
     370     2311993 :     for (; iterator.current_offset() > header_offset; --iterator) {
     371     2260941 :       Bytecode bytecode = iterator.current_bytecode();
     372             : 
     373     2260941 :       int current_offset = iterator.current_offset();
     374     2260941 :       BytecodeLiveness& liveness = liveness_map_.GetLiveness(current_offset);
     375             : 
     376             :       UpdateOutLiveness(bytecode, *liveness.out, next_bytecode_in_liveness,
     377     2260941 :                         iterator, liveness_map_);
     378     2260941 :       liveness.in->CopyFrom(*liveness.out);
     379     2260941 :       UpdateInLiveness(bytecode, *liveness.in, iterator);
     380             : 
     381     2260941 :       next_bytecode_in_liveness = liveness.in;
     382             :     }
     383             :     // Now we are at the loop header. Since the in-liveness of the header
     384             :     // can't change, we need only to update the out-liveness.
     385             :     UpdateOutLiveness(iterator.current_bytecode(), *header_liveness.out,
     386       51052 :                       next_bytecode_in_liveness, iterator, liveness_map_);
     387             :   }
     388             : 
     389             :   DCHECK(LivenessIsValid());
     390             : }
     391             : 
     392       56573 : void BytecodeAnalysis::PushLoop(int loop_header, int loop_end) {
     393             :   DCHECK(loop_header < loop_end);
     394             :   DCHECK(loop_stack_.top().header_offset < loop_header);
     395             :   DCHECK(end_to_header_.find(loop_end) == end_to_header_.end());
     396             :   DCHECK(header_to_info_.find(loop_header) == header_to_info_.end());
     397             : 
     398       56573 :   int parent_offset = loop_stack_.top().header_offset;
     399             : 
     400       56573 :   end_to_header_.insert({loop_end, loop_header});
     401             :   auto it = header_to_info_.insert(
     402             :       {loop_header, LoopInfo(parent_offset, bytecode_array_->parameter_count(),
     403      113146 :                              bytecode_array_->register_count(), zone_)});
     404             :   // Get the loop info pointer from the output of insert.
     405       56573 :   LoopInfo* loop_info = &it.first->second;
     406             : 
     407      113146 :   loop_stack_.push({loop_header, loop_info});
     408       56573 : }
     409             : 
     410    13759713 : bool BytecodeAnalysis::IsLoopHeader(int offset) const {
     411    13759713 :   return header_to_info_.find(offset) != header_to_info_.end();
     412             : }
     413             : 
     414     2714934 : int BytecodeAnalysis::GetLoopOffsetFor(int offset) const {
     415             :   auto loop_end_to_header = end_to_header_.upper_bound(offset);
     416             :   // If there is no next end => offset is not in a loop.
     417     2714934 :   if (loop_end_to_header == end_to_header_.end()) {
     418             :     return -1;
     419             :   }
     420             :   // If the header preceeds the offset, this is the loop
     421             :   //
     422             :   //   .> header  <--loop_end_to_header
     423             :   //   |
     424             :   //   |  <--offset
     425             :   //   |
     426             :   //   `- end
     427      945575 :   if (loop_end_to_header->second <= offset) {
     428             :     return loop_end_to_header->second;
     429             :   }
     430             :   // Otherwise there is a (potentially nested) loop after this offset.
     431             :   //
     432             :   //    <--offset
     433             :   //
     434             :   //   .> header
     435             :   //   |
     436             :   //   | .> header  <--loop_end_to_header
     437             :   //   | |
     438             :   //   | `- end
     439             :   //   |
     440             :   //   `- end
     441             :   // We just return the parent of the next loop (might be -1).
     442             :   DCHECK(header_to_info_.upper_bound(offset) != header_to_info_.end());
     443             : 
     444      537636 :   return header_to_info_.upper_bound(offset)->second.parent_offset();
     445             : }
     446             : 
     447      226366 : const LoopInfo& BytecodeAnalysis::GetLoopInfoFor(int header_offset) const {
     448             :   DCHECK(IsLoopHeader(header_offset));
     449             : 
     450      226366 :   return header_to_info_.find(header_offset)->second;
     451             : }
     452             : 
     453     2865424 : const BytecodeLivenessState* BytecodeAnalysis::GetInLivenessFor(
     454             :     int offset) const {
     455     2865424 :   if (!do_liveness_analysis_) return nullptr;
     456             : 
     457     5660216 :   return liveness_map_.GetInLiveness(offset);
     458             : }
     459             : 
     460     3070710 : const BytecodeLivenessState* BytecodeAnalysis::GetOutLivenessFor(
     461             :     int offset) const {
     462     3070710 :   if (!do_liveness_analysis_) return nullptr;
     463             : 
     464     6067123 :   return liveness_map_.GetOutLiveness(offset);
     465             : }
     466             : 
     467           0 : std::ostream& BytecodeAnalysis::PrintLivenessTo(std::ostream& os) const {
     468           0 :   interpreter::BytecodeArrayIterator iterator(bytecode_array());
     469             : 
     470           0 :   for (; !iterator.done(); iterator.Advance()) {
     471           0 :     int current_offset = iterator.current_offset();
     472             : 
     473           0 :     const BitVector& in_liveness =
     474             :         GetInLivenessFor(current_offset)->bit_vector();
     475           0 :     const BitVector& out_liveness =
     476             :         GetOutLivenessFor(current_offset)->bit_vector();
     477             : 
     478           0 :     for (int i = 0; i < in_liveness.length(); ++i) {
     479           0 :       os << (in_liveness.Contains(i) ? "L" : ".");
     480             :     }
     481           0 :     os << " -> ";
     482             : 
     483           0 :     for (int i = 0; i < out_liveness.length(); ++i) {
     484           0 :       os << (out_liveness.Contains(i) ? "L" : ".");
     485             :     }
     486             : 
     487           0 :     os << " | " << current_offset << ": ";
     488           0 :     iterator.PrintTo(os) << std::endl;
     489             :   }
     490             : 
     491           0 :   return os;
     492             : }
     493             : 
     494             : #if DEBUG
     495             : bool BytecodeAnalysis::LivenessIsValid() {
     496             :   BytecodeArrayRandomIterator iterator(bytecode_array(), zone());
     497             : 
     498             :   BytecodeLivenessState previous_liveness(bytecode_array()->register_count(),
     499             :                                           zone());
     500             : 
     501             :   int invalid_offset = -1;
     502             :   int which_invalid = -1;
     503             : 
     504             :   BytecodeLivenessState* next_bytecode_in_liveness = nullptr;
     505             : 
     506             :   // Ensure that there are no liveness changes if we iterate one more time.
     507             :   for (iterator.GoToEnd(); iterator.IsValid(); --iterator) {
     508             :     Bytecode bytecode = iterator.current_bytecode();
     509             : 
     510             :     int current_offset = iterator.current_offset();
     511             : 
     512             :     BytecodeLiveness& liveness = liveness_map_.GetLiveness(current_offset);
     513             : 
     514             :     previous_liveness.CopyFrom(*liveness.out);
     515             : 
     516             :     UpdateOutLiveness(bytecode, *liveness.out, next_bytecode_in_liveness,
     517             :                       iterator, liveness_map_);
     518             :     // UpdateOutLiveness skips kJumpLoop, so we update it manually.
     519             :     if (bytecode == Bytecode::kJumpLoop) {
     520             :       int target_offset = iterator.GetJumpTargetOffset();
     521             :       liveness.out->Union(*liveness_map_.GetInLiveness(target_offset));
     522             :     }
     523             : 
     524             :     if (!liveness.out->Equals(previous_liveness)) {
     525             :       // Reset the invalid liveness.
     526             :       liveness.out->CopyFrom(previous_liveness);
     527             :       invalid_offset = current_offset;
     528             :       which_invalid = 1;
     529             :       break;
     530             :     }
     531             : 
     532             :     previous_liveness.CopyFrom(*liveness.in);
     533             : 
     534             :     liveness.in->CopyFrom(*liveness.out);
     535             :     UpdateInLiveness(bytecode, *liveness.in, iterator);
     536             : 
     537             :     if (!liveness.in->Equals(previous_liveness)) {
     538             :       // Reset the invalid liveness.
     539             :       liveness.in->CopyFrom(previous_liveness);
     540             :       invalid_offset = current_offset;
     541             :       which_invalid = 0;
     542             :       break;
     543             :     }
     544             : 
     545             :     next_bytecode_in_liveness = liveness.in;
     546             :   }
     547             : 
     548             :   if (invalid_offset != -1) {
     549             :     OFStream of(stderr);
     550             :     of << "Invalid liveness:" << std::endl;
     551             : 
     552             :     // Dump the bytecode, annotated with the liveness and marking loops.
     553             : 
     554             :     int loop_indent = 0;
     555             : 
     556             :     BytecodeArrayIterator forward_iterator(bytecode_array());
     557             :     for (; !forward_iterator.done(); forward_iterator.Advance()) {
     558             :       int current_offset = forward_iterator.current_offset();
     559             :       const BitVector& in_liveness =
     560             :           GetInLivenessFor(current_offset)->bit_vector();
     561             :       const BitVector& out_liveness =
     562             :           GetOutLivenessFor(current_offset)->bit_vector();
     563             : 
     564             :       for (int i = 0; i < in_liveness.length(); ++i) {
     565             :         of << (in_liveness.Contains(i) ? 'L' : '.');
     566             :       }
     567             : 
     568             :       of << " | ";
     569             : 
     570             :       for (int i = 0; i < out_liveness.length(); ++i) {
     571             :         of << (out_liveness.Contains(i) ? 'L' : '.');
     572             :       }
     573             : 
     574             :       of << " : " << current_offset << " : ";
     575             : 
     576             :       // Draw loop back edges by indentin everything between loop headers and
     577             :       // jump loop instructions.
     578             :       if (forward_iterator.current_bytecode() == Bytecode::kJumpLoop) {
     579             :         loop_indent--;
     580             :       }
     581             :       for (int i = 0; i < loop_indent; ++i) {
     582             :         of << " | ";
     583             :       }
     584             :       if (forward_iterator.current_bytecode() == Bytecode::kJumpLoop) {
     585             :         of << " `-" << current_offset;
     586             :       } else if (IsLoopHeader(current_offset)) {
     587             :         of << " .>" << current_offset;
     588             :         loop_indent++;
     589             :       }
     590             :       forward_iterator.PrintTo(of) << std::endl;
     591             : 
     592             :       if (current_offset == invalid_offset) {
     593             :         // Underline the invalid liveness.
     594             :         if (which_invalid == 0) {
     595             :           for (int i = 0; i < in_liveness.length(); ++i) {
     596             :             of << '^';
     597             :           }
     598             :         } else {
     599             :           for (int i = 0; i < in_liveness.length() + 3; ++i) {
     600             :             of << ' ';
     601             :           }
     602             :           for (int i = 0; i < out_liveness.length(); ++i) {
     603             :             of << '^';
     604             :           }
     605             :         }
     606             : 
     607             :         // Make sure to draw the loop indentation marks on this additional line.
     608             :         of << " : " << current_offset << " : ";
     609             :         for (int i = 0; i < loop_indent; ++i) {
     610             :           of << " | ";
     611             :         }
     612             : 
     613             :         of << std::endl;
     614             :       }
     615             :     }
     616             :   }
     617             : 
     618             :   return invalid_offset == -1;
     619             : }
     620             : #endif
     621             : 
     622             : }  // namespace compiler
     623             : }  // namespace internal
     624             : }  // namespace v8

Generated by: LCOV version 1.10