LCOV - code coverage report
Current view: top level - src/compiler - bytecode-analysis.cc (source / functions) Hit Total Coverage
Test: app.info Lines: 174 201 86.6 %
Date: 2019-04-17 Functions: 19 23 82.6 %

          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             : #include "src/ostreams.h"
      11             : 
      12             : namespace v8 {
      13             : namespace internal {
      14             : namespace compiler {
      15             : 
      16             : using interpreter::Bytecode;
      17             : using interpreter::Bytecodes;
      18             : using interpreter::OperandType;
      19             : 
      20       57175 : BytecodeLoopAssignments::BytecodeLoopAssignments(int parameter_count,
      21             :                                                  int register_count, Zone* zone)
      22             :     : parameter_count_(parameter_count),
      23             :       bit_vector_(new (zone)
      24      114350 :                       BitVector(parameter_count + register_count, zone)) {}
      25             : 
      26      515817 : void BytecodeLoopAssignments::Add(interpreter::Register r) {
      27      515817 :   if (r.is_parameter()) {
      28        2188 :     bit_vector_->Add(r.ToParameterIndex(parameter_count_));
      29             :   } else {
      30      513629 :     bit_vector_->Add(parameter_count_ + r.index());
      31             :   }
      32      515817 : }
      33             : 
      34        1006 : void BytecodeLoopAssignments::AddList(interpreter::Register r, uint32_t count) {
      35        1006 :   if (r.is_parameter()) {
      36           0 :     for (uint32_t i = 0; i < count; i++) {
      37             :       DCHECK(interpreter::Register(r.index() + i).is_parameter());
      38           0 :       bit_vector_->Add(r.ToParameterIndex(parameter_count_) + i);
      39             :     }
      40             :   } else {
      41       13794 :     for (uint32_t i = 0; i < count; i++) {
      42             :       DCHECK(!interpreter::Register(r.index() + i).is_parameter());
      43       12788 :       bit_vector_->Add(parameter_count_ + r.index() + i);
      44             :     }
      45             :   }
      46        1006 : }
      47             : 
      48             : 
      49        6393 : void BytecodeLoopAssignments::Union(const BytecodeLoopAssignments& other) {
      50        6393 :   bit_vector_->Union(*other.bit_vector_);
      51        6393 : }
      52             : 
      53      420337 : bool BytecodeLoopAssignments::ContainsParameter(int index) const {
      54             :   DCHECK_GE(index, 0);
      55             :   DCHECK_LT(index, parameter_count());
      56      840674 :   return bit_vector_->Contains(index);
      57             : }
      58             : 
      59     4124839 : bool BytecodeLoopAssignments::ContainsLocal(int index) const {
      60             :   DCHECK_GE(index, 0);
      61             :   DCHECK_LT(index, local_count());
      62     8249678 :   return bit_vector_->Contains(parameter_count_ + index);
      63             : }
      64             : 
      65           0 : ResumeJumpTarget::ResumeJumpTarget(int suspend_id, int target_offset,
      66             :                                    int final_target_offset)
      67             :     : suspend_id_(suspend_id),
      68             :       target_offset_(target_offset),
      69           0 :       final_target_offset_(final_target_offset) {}
      70             : 
      71           0 : ResumeJumpTarget ResumeJumpTarget::Leaf(int suspend_id, int target_offset) {
      72           0 :   return ResumeJumpTarget(suspend_id, target_offset, target_offset);
      73             : }
      74             : 
      75           0 : ResumeJumpTarget ResumeJumpTarget::AtLoopHeader(int loop_header_offset,
      76             :                                                 const ResumeJumpTarget& next) {
      77             :   return ResumeJumpTarget(next.suspend_id(), loop_header_offset,
      78           0 :                           next.target_offset());
      79             : }
      80             : 
      81      530037 : BytecodeAnalysis::BytecodeAnalysis(Handle<BytecodeArray> bytecode_array,
      82             :                                    Zone* zone, bool do_liveness_analysis)
      83             :     : bytecode_array_(bytecode_array),
      84             :       do_liveness_analysis_(do_liveness_analysis),
      85             :       zone_(zone),
      86             :       loop_stack_(zone),
      87             :       loop_end_index_queue_(zone),
      88             :       resume_jump_targets_(zone),
      89             :       end_to_header_(zone),
      90             :       header_to_info_(zone),
      91             :       osr_entry_point_(-1),
      92     1590109 :       liveness_map_(bytecode_array->length(), zone) {}
      93             : 
      94             : namespace {
      95             : 
      96    17068053 : void UpdateInLiveness(Bytecode bytecode, BytecodeLivenessState& in_liveness,
      97             :                       const interpreter::BytecodeArrayAccessor& accessor) {
      98             :   int num_operands = Bytecodes::NumberOfOperands(bytecode);
      99             :   const OperandType* operand_types = Bytecodes::GetOperandTypes(bytecode);
     100             : 
     101             :   // Special case Suspend and Resume to just pass through liveness.
     102    17068053 :   if (bytecode == Bytecode::kSuspendGenerator) {
     103             :     // The generator object has to be live.
     104       13096 :     in_liveness.MarkRegisterLive(accessor.GetRegisterOperand(0).index());
     105             :     // Suspend additionally reads and returns the accumulator
     106             :     DCHECK(Bytecodes::ReadsAccumulator(bytecode));
     107             :     in_liveness.MarkAccumulatorLive();
     108             :     return;
     109             :   }
     110    17061505 :   if (bytecode == Bytecode::kResumeGenerator) {
     111             :     // The generator object has to be live.
     112       13096 :     in_liveness.MarkRegisterLive(accessor.GetRegisterOperand(0).index());
     113        6548 :     return;
     114             :   }
     115             : 
     116    17054957 :   if (Bytecodes::WritesAccumulator(bytecode)) {
     117     8950575 :     in_liveness.MarkAccumulatorDead();
     118             :   }
     119    62268819 :   for (int i = 0; i < num_operands; ++i) {
     120    22606939 :     switch (operand_types[i]) {
     121             :       case OperandType::kRegOut: {
     122     4753234 :         interpreter::Register r = accessor.GetRegisterOperand(i);
     123     4753234 :         if (!r.is_parameter()) {
     124             :           in_liveness.MarkRegisterDead(r.index());
     125             :         }
     126             :         break;
     127             :       }
     128             :       case OperandType::kRegOutList: {
     129           0 :         interpreter::Register r = accessor.GetRegisterOperand(i++);
     130           0 :         uint32_t reg_count = accessor.GetRegisterCountOperand(i);
     131           0 :         if (!r.is_parameter()) {
     132           0 :           for (uint32_t j = 0; j < reg_count; ++j) {
     133             :             DCHECK(!interpreter::Register(r.index() + j).is_parameter());
     134           0 :             in_liveness.MarkRegisterDead(r.index() + j);
     135             :           }
     136             :         }
     137             :         break;
     138             :       }
     139             :       case OperandType::kRegOutPair: {
     140         688 :         interpreter::Register r = accessor.GetRegisterOperand(i);
     141         688 :         if (!r.is_parameter()) {
     142             :           DCHECK(!interpreter::Register(r.index() + 1).is_parameter());
     143             :           in_liveness.MarkRegisterDead(r.index());
     144         688 :           in_liveness.MarkRegisterDead(r.index() + 1);
     145             :         }
     146             :         break;
     147             :       }
     148             :       case OperandType::kRegOutTriple: {
     149        1779 :         interpreter::Register r = accessor.GetRegisterOperand(i);
     150        1779 :         if (!r.is_parameter()) {
     151             :           DCHECK(!interpreter::Register(r.index() + 1).is_parameter());
     152             :           DCHECK(!interpreter::Register(r.index() + 2).is_parameter());
     153             :           in_liveness.MarkRegisterDead(r.index());
     154        1779 :           in_liveness.MarkRegisterDead(r.index() + 1);
     155        1779 :           in_liveness.MarkRegisterDead(r.index() + 2);
     156             :         }
     157             :         break;
     158             :       }
     159             :       default:
     160             :         DCHECK(!Bytecodes::IsRegisterOutputOperandType(operand_types[i]));
     161             :         break;
     162             :     }
     163             :   }
     164             : 
     165    17054941 :   if (Bytecodes::ReadsAccumulator(bytecode)) {
     166             :     in_liveness.MarkAccumulatorLive();
     167             :   }
     168    61267851 :   for (int i = 0; i < num_operands; ++i) {
     169    22106456 :     switch (operand_types[i]) {
     170             :       case OperandType::kReg: {
     171     5499905 :         interpreter::Register r = accessor.GetRegisterOperand(i);
     172     5499904 :         if (!r.is_parameter()) {
     173             :           in_liveness.MarkRegisterLive(r.index());
     174             :         }
     175             :         break;
     176             :       }
     177             :       case OperandType::kRegPair: {
     178        3395 :         interpreter::Register r = accessor.GetRegisterOperand(i);
     179        3395 :         if (!r.is_parameter()) {
     180             :           DCHECK(!interpreter::Register(r.index() + 1).is_parameter());
     181             :           in_liveness.MarkRegisterLive(r.index());
     182        3395 :           in_liveness.MarkRegisterLive(r.index() + 1);
     183             :         }
     184             :         break;
     185             :       }
     186             :       case OperandType::kRegList: {
     187      500494 :         interpreter::Register r = accessor.GetRegisterOperand(i++);
     188      500494 :         uint32_t reg_count = accessor.GetRegisterCountOperand(i);
     189      500494 :         if (!r.is_parameter()) {
     190     3140967 :           for (uint32_t j = 0; j < reg_count; ++j) {
     191             :             DCHECK(!interpreter::Register(r.index() + j).is_parameter());
     192     1321350 :             in_liveness.MarkRegisterLive(r.index() + j);
     193             :           }
     194             :         }
     195             :         break;
     196             :       }
     197             :       default:
     198             :         DCHECK(!Bytecodes::IsRegisterInputOperandType(operand_types[i]));
     199             :         break;
     200             :     }
     201             :   }
     202             : }
     203             : 
     204    17121435 : void UpdateOutLiveness(Bytecode bytecode, BytecodeLivenessState& out_liveness,
     205             :                        BytecodeLivenessState* next_bytecode_in_liveness,
     206             :                        const interpreter::BytecodeArrayAccessor& accessor,
     207             :                        const BytecodeLivenessMap& liveness_map) {
     208             :   int current_offset = accessor.current_offset();
     209             :   const Handle<BytecodeArray>& bytecode_array = accessor.bytecode_array();
     210             : 
     211             :   // Special case Suspend and Resume to just pass through liveness.
     212    17121435 :   if (bytecode == Bytecode::kSuspendGenerator ||
     213             :       bytecode == Bytecode::kResumeGenerator) {
     214             :     out_liveness.Union(*next_bytecode_in_liveness);
     215             :     return;
     216             :   }
     217             : 
     218             :   // Update from jump target (if any). Skip loops, we update these manually in
     219             :   // the liveness iterations.
     220    17108339 :   if (Bytecodes::IsForwardJump(bytecode)) {
     221      936992 :     int target_offset = accessor.GetJumpTargetOffset();
     222             :     out_liveness.Union(*liveness_map.GetInLiveness(target_offset));
     223    16171347 :   } else if (Bytecodes::IsSwitch(bytecode)) {
     224       20621 :     for (const auto& entry : accessor.GetJumpTableTargetOffsets()) {
     225       14271 :       out_liveness.Union(*liveness_map.GetInLiveness(entry.target_offset));
     226             :     }
     227             :   }
     228             : 
     229             :   // Update from next bytecode (unless there isn't one or this is an
     230             :   // unconditional jump).
     231    33687829 :   if (next_bytecode_in_liveness != nullptr &&
     232             :       !Bytecodes::IsUnconditionalJump(bytecode)) {
     233             :     out_liveness.Union(*next_bytecode_in_liveness);
     234             :   }
     235             : 
     236             :   // Update from exception handler (if any).
     237    17108339 :   if (!interpreter::Bytecodes::IsWithoutExternalSideEffects(bytecode)) {
     238             :     int handler_context;
     239             :     // TODO(leszeks): We should look up this range only once per entry.
     240     7491097 :     HandlerTable table(*bytecode_array);
     241             :     int handler_offset =
     242     7491093 :         table.LookupRange(current_offset, &handler_context, nullptr);
     243             : 
     244     7491095 :     if (handler_offset != -1) {
     245             :       bool was_accumulator_live = out_liveness.AccumulatorIsLive();
     246             :       out_liveness.Union(*liveness_map.GetInLiveness(handler_offset));
     247      447803 :       out_liveness.MarkRegisterLive(handler_context);
     248      447803 :       if (!was_accumulator_live) {
     249             :         // The accumulator is reset to the exception on entry into a handler,
     250             :         // and so shouldn't be considered live coming out of this bytecode just
     251             :         // because it's live coming into the handler. So, kill the accumulator
     252             :         // if the handler is the only thing that made it live.
     253      145163 :         out_liveness.MarkAccumulatorDead();
     254             : 
     255             :         // TODO(leszeks): Ideally the accumulator wouldn't be considered live at
     256             :         // the start of the handler, but looking up if the current bytecode is
     257             :         // the start of a handler is not free, so we should only do it if we
     258             :         // decide it's necessary.
     259             :       }
     260             :     }
     261             :   }
     262             : }
     263             : 
     264    17067736 : void UpdateLiveness(Bytecode bytecode, BytecodeLiveness& liveness,
     265             :                     BytecodeLivenessState** next_bytecode_in_liveness,
     266             :                     const interpreter::BytecodeArrayAccessor& accessor,
     267             :                     const BytecodeLivenessMap& liveness_map) {
     268    17067736 :   UpdateOutLiveness(bytecode, *liveness.out, *next_bytecode_in_liveness,
     269    17067736 :                     accessor, liveness_map);
     270    17067751 :   liveness.in->CopyFrom(*liveness.out);
     271    17067751 :   UpdateInLiveness(bytecode, *liveness.in, accessor);
     272             : 
     273    17067735 :   *next_bytecode_in_liveness = liveness.in;
     274    17067735 : }
     275             : 
     276     1827801 : void UpdateAssignments(Bytecode bytecode, BytecodeLoopAssignments& assignments,
     277             :                        const interpreter::BytecodeArrayAccessor& accessor) {
     278             :   int num_operands = Bytecodes::NumberOfOperands(bytecode);
     279             :   const OperandType* operand_types = Bytecodes::GetOperandTypes(bytecode);
     280             : 
     281     6956393 :   for (int i = 0; i < num_operands; ++i) {
     282     2564296 :     switch (operand_types[i]) {
     283             :       case OperandType::kRegOut: {
     284      515817 :         assignments.Add(accessor.GetRegisterOperand(i));
     285      515817 :         break;
     286             :       }
     287             :       case OperandType::kRegOutList: {
     288         578 :         interpreter::Register r = accessor.GetRegisterOperand(i++);
     289         578 :         uint32_t reg_count = accessor.GetRegisterCountOperand(i);
     290         578 :         assignments.AddList(r, reg_count);
     291             :         break;
     292             :       }
     293             :       case OperandType::kRegOutPair: {
     294         279 :         assignments.AddList(accessor.GetRegisterOperand(i), 2);
     295         279 :         break;
     296             :       }
     297             :       case OperandType::kRegOutTriple: {
     298         149 :         assignments.AddList(accessor.GetRegisterOperand(i), 3);
     299         149 :         break;
     300             :       }
     301             :       default:
     302             :         DCHECK(!Bytecodes::IsRegisterOutputOperandType(operand_types[i]));
     303             :         break;
     304             :     }
     305             :   }
     306     1827801 : }
     307             : 
     308             : }  // namespace
     309             : 
     310      530036 : void BytecodeAnalysis::Analyze(BailoutId osr_bailout_id) {
     311     1060073 :   loop_stack_.push({-1, nullptr});
     312             : 
     313      530037 :   BytecodeLivenessState* next_bytecode_in_liveness = nullptr;
     314             : 
     315             :   bool is_osr = !osr_bailout_id.IsNone();
     316      530037 :   int osr_loop_end_offset = is_osr ? osr_bailout_id.ToInt() : -1;
     317             : 
     318             :   int generator_switch_index = -1;
     319             : 
     320      530037 :   interpreter::BytecodeArrayRandomIterator iterator(bytecode_array(), zone());
     321    15763098 :   for (iterator.GoToEnd(); iterator.IsValid(); --iterator) {
     322    15233053 :     Bytecode bytecode = iterator.current_bytecode();
     323             :     int current_offset = iterator.current_offset();
     324             : 
     325    15233056 :     if (bytecode == Bytecode::kSwitchOnGeneratorState) {
     326             :       DCHECK_EQ(generator_switch_index, -1);
     327             :       generator_switch_index = iterator.current_index();
     328             :     }
     329             : 
     330    15233056 :     if (bytecode == Bytecode::kJumpLoop) {
     331             :       // Every byte up to and including the last byte within the backwards jump
     332             :       // instruction is considered part of the loop, set loop end accordingly.
     333       57175 :       int loop_end = current_offset + iterator.current_bytecode_size();
     334       57175 :       int loop_header = iterator.GetJumpTargetOffset();
     335       57175 :       PushLoop(loop_header, loop_end);
     336             : 
     337       57175 :       if (current_offset == osr_loop_end_offset) {
     338        4647 :         osr_entry_point_ = loop_header;
     339             :       } else if (current_offset < osr_loop_end_offset) {
     340             :         // Check we've found the osr_entry_point if we've gone past the
     341             :         // osr_loop_end_offset. Note, we are iterating the bytecode in reverse,
     342             :         // so the less than in the check is correct.
     343             :         DCHECK_NE(-1, osr_entry_point_);
     344             :       }
     345             : 
     346             :       // Save the index so that we can do another pass later.
     347       57175 :       if (do_liveness_analysis_) {
     348      114102 :         loop_end_index_queue_.push_back(iterator.current_index());
     349             :       }
     350    15175881 :     } else if (loop_stack_.size() > 1) {
     351             :       LoopStackEntry& current_loop = loop_stack_.top();
     352     1827801 :       LoopInfo* current_loop_info = current_loop.loop_info;
     353             : 
     354             :       // TODO(leszeks): Ideally, we'd only set values that were assigned in
     355             :       // the loop *and* are live when the loop exits. However, this requires
     356             :       // tracking the out-liveness of *all* loop exits, which is not
     357             :       // information we currently have.
     358     1827801 :       UpdateAssignments(bytecode, current_loop_info->assignments(), iterator);
     359             : 
     360             :       // Update suspend counts for this loop, though only if not OSR.
     361     1827801 :       if (!is_osr && bytecode == Bytecode::kSuspendGenerator) {
     362         550 :         int suspend_id = iterator.GetUnsignedImmediateOperand(3);
     363         550 :         int resume_offset = current_offset + iterator.current_bytecode_size();
     364             :         current_loop_info->AddResumeTarget(
     365        1100 :             ResumeJumpTarget::Leaf(suspend_id, resume_offset));
     366             :       }
     367             : 
     368             :       // If we've reached the header of the loop, pop it off the stack.
     369     1827801 :       if (current_offset == current_loop.header_offset) {
     370             :         loop_stack_.pop();
     371       57175 :         if (loop_stack_.size() > 1) {
     372             :           // If there is still an outer loop, propagate inner loop assignments.
     373        6393 :           LoopInfo* parent_loop_info = loop_stack_.top().loop_info;
     374             : 
     375             :           parent_loop_info->assignments().Union(
     376        6393 :               current_loop_info->assignments());
     377             : 
     378             :           // Also, propagate resume targets. Instead of jumping to the target
     379             :           // itself, the outer loop will jump to this loop header for any
     380             :           // targets that are inside the current loop, so that this loop stays
     381             :           // reducible. Hence, a nested loop of the form:
     382             :           //
     383             :           //                switch (#1 -> suspend1, #2 -> suspend2)
     384             :           //                loop {
     385             :           //     suspend1:    suspend #1
     386             :           //                  loop {
     387             :           //     suspend2:      suspend #2
     388             :           //                  }
     389             :           //                }
     390             :           //
     391             :           // becomes:
     392             :           //
     393             :           //                switch (#1 -> loop1, #2 -> loop1)
     394             :           //     loop1:     loop {
     395             :           //                  switch (#1 -> suspend1, #2 -> loop2)
     396             :           //     suspend1:    suspend #1
     397             :           //     loop2:       loop {
     398             :           //                    switch (#2 -> suspend2)
     399             :           //     suspend2:      suspend #2
     400             :           //                  }
     401             :           //                }
     402        6487 :           for (const auto& target : current_loop_info->resume_jump_targets()) {
     403             :             parent_loop_info->AddResumeTarget(
     404         188 :                 ResumeJumpTarget::AtLoopHeader(current_offset, target));
     405             :           }
     406             : 
     407             :         } else {
     408             :           // Otherwise, just propagate inner loop suspends to top-level.
     409       51332 :           for (const auto& target : current_loop_info->resume_jump_targets()) {
     410         550 :             resume_jump_targets_.push_back(
     411        1100 :                 ResumeJumpTarget::AtLoopHeader(current_offset, target));
     412             :           }
     413             :         }
     414             :       }
     415    13348080 :     } else if (!is_osr && bytecode == Bytecode::kSuspendGenerator) {
     416             :       // If we're not in a loop, we still need to look for suspends.
     417             :       // TODO(leszeks): It would be nice to de-duplicate this with the in-loop
     418             :       // case
     419        5319 :       int suspend_id = iterator.GetUnsignedImmediateOperand(3);
     420        5319 :       int resume_offset = current_offset + iterator.current_bytecode_size();
     421        5319 :       resume_jump_targets_.push_back(
     422       10638 :           ResumeJumpTarget::Leaf(suspend_id, resume_offset));
     423             :     }
     424             : 
     425    15233056 :     if (do_liveness_analysis_) {
     426             :       BytecodeLiveness& liveness = liveness_map_.InitializeLiveness(
     427    15183956 :           current_offset, bytecode_array()->register_count(), zone());
     428             :       UpdateLiveness(bytecode, liveness, &next_bytecode_in_liveness, iterator,
     429    15183955 :                      liveness_map_);
     430             :     }
     431             :   }
     432             : 
     433             :   DCHECK_EQ(loop_stack_.size(), 1u);
     434             :   DCHECK_EQ(loop_stack_.top().header_offset, -1);
     435             : 
     436             :   DCHECK(ResumeJumpTargetsAreValid());
     437             : 
     438      530037 :   if (!do_liveness_analysis_) return;
     439             : 
     440             :   // At this point, every bytecode has a valid in and out liveness, except for
     441             :   // propagating liveness across back edges (i.e. JumpLoop). Subsequent liveness
     442             :   // analysis iterations can only add additional liveness bits that are pulled
     443             :   // across these back edges.
     444             :   //
     445             :   // Furthermore, a loop header's in-liveness can only change based on any
     446             :   // bytecodes *after* the loop end --  it cannot change as a result of the
     447             :   // JumpLoop liveness being updated, as the only liveness bits than can be
     448             :   // added to the loop body are those of the loop header.
     449             :   //
     450             :   // So, if we know that the liveness of bytecodes after a loop header won't
     451             :   // change (e.g. because there are no loops in them, or we have already ensured
     452             :   // those loops are valid), we can safely update the loop end and pass over the
     453             :   // loop body, and then never have to pass over that loop end again, because we
     454             :   // have shown that its target, the loop header, can't change from the entries
     455             :   // after the loop, and can't change from any loop body pass.
     456             :   //
     457             :   // This means that in a pass, we can iterate backwards over the bytecode
     458             :   // array, process any loops that we encounter, and on subsequent passes we can
     459             :   // skip processing those loops (though we still have to process inner loops).
     460             :   //
     461             :   // Equivalently, we can queue up loop ends from back to front, and pass over
     462             :   // the loops in that order, as this preserves both the bottom-to-top and
     463             :   // outer-to-inner requirements.
     464             : 
     465      585902 :   for (int loop_end_index : loop_end_index_queue_) {
     466             :     iterator.GoToIndex(loop_end_index);
     467             : 
     468             :     DCHECK_EQ(iterator.current_bytecode(), Bytecode::kJumpLoop);
     469             : 
     470       57051 :     int header_offset = iterator.GetJumpTargetOffset();
     471             :     int end_offset = iterator.current_offset();
     472             : 
     473             :     BytecodeLiveness& header_liveness =
     474       57051 :         liveness_map_.GetLiveness(header_offset);
     475       57051 :     BytecodeLiveness& end_liveness = liveness_map_.GetLiveness(end_offset);
     476             : 
     477      114102 :     if (!end_liveness.out->UnionIsChanged(*header_liveness.in)) {
     478             :       // Only update the loop body if the loop end liveness changed.
     479             :       continue;
     480             :     }
     481       53694 :     end_liveness.in->CopyFrom(*end_liveness.out);
     482       53694 :     next_bytecode_in_liveness = end_liveness.in;
     483             : 
     484             :     // Advance into the loop body.
     485             :     --iterator;
     486     1937475 :     for (; iterator.current_offset() > header_offset; --iterator) {
     487     1883781 :       Bytecode bytecode = iterator.current_bytecode();
     488             :       int current_offset = iterator.current_offset();
     489     1883781 :       BytecodeLiveness& liveness = liveness_map_.GetLiveness(current_offset);
     490             : 
     491             :       UpdateLiveness(bytecode, liveness, &next_bytecode_in_liveness, iterator,
     492     1883781 :                      liveness_map_);
     493             :     }
     494             :     // Now we are at the loop header. Since the in-liveness of the header
     495             :     // can't change, we need only to update the out-liveness.
     496       53694 :     UpdateOutLiveness(iterator.current_bytecode(), *header_liveness.out,
     497      107388 :                       next_bytecode_in_liveness, iterator, liveness_map_);
     498             :   }
     499             : 
     500             :   // Process the generator switch statement separately, once the loops are done.
     501             :   // This has to be a separate pass because the generator switch can jump into
     502             :   // the middle of loops (and is the only kind of jump that can jump across a
     503             :   // loop header).
     504      528851 :   if (generator_switch_index != -1) {
     505             :     iterator.GoToIndex(generator_switch_index);
     506             :     DCHECK_EQ(iterator.current_bytecode(), Bytecode::kSwitchOnGeneratorState);
     507             : 
     508             :     int current_offset = iterator.current_offset();
     509             :     BytecodeLiveness& switch_liveness =
     510        2248 :         liveness_map_.GetLiveness(current_offset);
     511             : 
     512             :     bool any_changed = false;
     513        8126 :     for (const auto& entry : iterator.GetJumpTableTargetOffsets()) {
     514       11756 :       if (switch_liveness.out->UnionIsChanged(
     515        5878 :               *liveness_map_.GetInLiveness(entry.target_offset))) {
     516             :         any_changed = true;
     517             :       }
     518             :     }
     519             : 
     520             :     // If the switch liveness changed, we have to propagate it up the remaining
     521             :     // bytecodes before it.
     522        2248 :     if (any_changed) {
     523         304 :       switch_liveness.in->CopyFrom(*switch_liveness.out);
     524         304 :       UpdateInLiveness(Bytecode::kSwitchOnGeneratorState, *switch_liveness.in,
     525         304 :                        iterator);
     526         304 :       next_bytecode_in_liveness = switch_liveness.in;
     527         304 :       for (--iterator; iterator.IsValid(); --iterator) {
     528           0 :         Bytecode bytecode = iterator.current_bytecode();
     529             :         int current_offset = iterator.current_offset();
     530           0 :         BytecodeLiveness& liveness = liveness_map_.GetLiveness(current_offset);
     531             : 
     532             :         // There shouldn't be any more loops.
     533             :         DCHECK_NE(bytecode, Bytecode::kJumpLoop);
     534             : 
     535             :         UpdateLiveness(bytecode, liveness, &next_bytecode_in_liveness, iterator,
     536           0 :                        liveness_map_);
     537             :       }
     538             :     }
     539             :   }
     540             : 
     541             :   DCHECK(LivenessIsValid());
     542             : }
     543             : 
     544       57175 : void BytecodeAnalysis::PushLoop(int loop_header, int loop_end) {
     545             :   DCHECK(loop_header < loop_end);
     546             :   DCHECK(loop_stack_.top().header_offset < loop_header);
     547             :   DCHECK(end_to_header_.find(loop_end) == end_to_header_.end());
     548             :   DCHECK(header_to_info_.find(loop_header) == header_to_info_.end());
     549             : 
     550       57175 :   int parent_offset = loop_stack_.top().header_offset;
     551             : 
     552       57175 :   end_to_header_.insert({loop_end, loop_header});
     553             :   auto it = header_to_info_.insert(
     554             :       {loop_header, LoopInfo(parent_offset, bytecode_array_->parameter_count(),
     555      171525 :                              bytecode_array_->register_count(), zone_)});
     556             :   // Get the loop info pointer from the output of insert.
     557       57175 :   LoopInfo* loop_info = &it.first->second;
     558             : 
     559      114350 :   loop_stack_.push({loop_header, loop_info});
     560       57175 : }
     561             : 
     562    13171590 : bool BytecodeAnalysis::IsLoopHeader(int offset) const {
     563    13171590 :   return header_to_info_.find(offset) != header_to_info_.end();
     564             : }
     565             : 
     566     2216449 : int BytecodeAnalysis::GetLoopOffsetFor(int offset) const {
     567             :   auto loop_end_to_header = end_to_header_.upper_bound(offset);
     568             :   // If there is no next end => offset is not in a loop.
     569     2216449 :   if (loop_end_to_header == end_to_header_.end()) {
     570             :     return -1;
     571             :   }
     572             :   // If the header precedes the offset, this is the loop
     573             :   //
     574             :   //   .> header  <--loop_end_to_header
     575             :   //   |
     576             :   //   |  <--offset
     577             :   //   |
     578             :   //   `- end
     579      772175 :   if (loop_end_to_header->second <= offset) {
     580             :     return loop_end_to_header->second;
     581             :   }
     582             :   // Otherwise there is a (potentially nested) loop after this offset.
     583             :   //
     584             :   //    <--offset
     585             :   //
     586             :   //   .> header
     587             :   //   |
     588             :   //   | .> header  <--loop_end_to_header
     589             :   //   | |
     590             :   //   | `- end
     591             :   //   |
     592             :   //   `- end
     593             :   // We just return the parent of the next loop (might be -1).
     594             :   DCHECK(header_to_info_.upper_bound(offset) != header_to_info_.end());
     595             : 
     596             :   return header_to_info_.upper_bound(offset)->second.parent_offset();
     597             : }
     598             : 
     599      235530 : const LoopInfo& BytecodeAnalysis::GetLoopInfoFor(int header_offset) const {
     600             :   DCHECK(IsLoopHeader(header_offset));
     601             : 
     602      235530 :   return header_to_info_.find(header_offset)->second;
     603             : }
     604             : 
     605     5193969 : const BytecodeLivenessState* BytecodeAnalysis::GetInLivenessFor(
     606             :     int offset) const {
     607     5193969 :   if (!do_liveness_analysis_) return nullptr;
     608             : 
     609    10347068 :   return liveness_map_.GetInLiveness(offset);
     610             : }
     611             : 
     612     3545112 : const BytecodeLivenessState* BytecodeAnalysis::GetOutLivenessFor(
     613             :     int offset) const {
     614     3545112 :   if (!do_liveness_analysis_) return nullptr;
     615             : 
     616     7060444 :   return liveness_map_.GetOutLiveness(offset);
     617             : }
     618             : 
     619           0 : std::ostream& BytecodeAnalysis::PrintLivenessTo(std::ostream& os) const {
     620           0 :   interpreter::BytecodeArrayIterator iterator(bytecode_array());
     621             : 
     622           0 :   for (; !iterator.done(); iterator.Advance()) {
     623             :     int current_offset = iterator.current_offset();
     624             : 
     625             :     const BitVector& in_liveness =
     626             :         GetInLivenessFor(current_offset)->bit_vector();
     627             :     const BitVector& out_liveness =
     628             :         GetOutLivenessFor(current_offset)->bit_vector();
     629             : 
     630           0 :     for (int i = 0; i < in_liveness.length(); ++i) {
     631           0 :       os << (in_liveness.Contains(i) ? "L" : ".");
     632             :     }
     633           0 :     os << " -> ";
     634             : 
     635           0 :     for (int i = 0; i < out_liveness.length(); ++i) {
     636           0 :       os << (out_liveness.Contains(i) ? "L" : ".");
     637             :     }
     638             : 
     639           0 :     os << " | " << current_offset << ": ";
     640           0 :     iterator.PrintTo(os) << std::endl;
     641             :   }
     642             : 
     643           0 :   return os;
     644             : }
     645             : 
     646             : #if DEBUG
     647             : bool BytecodeAnalysis::ResumeJumpTargetsAreValid() {
     648             :   bool valid = true;
     649             : 
     650             :   // Find the generator switch.
     651             :   interpreter::BytecodeArrayRandomIterator iterator(bytecode_array(), zone());
     652             :   for (iterator.GoToStart(); iterator.IsValid(); ++iterator) {
     653             :     if (iterator.current_bytecode() == Bytecode::kSwitchOnGeneratorState) {
     654             :       break;
     655             :     }
     656             :   }
     657             : 
     658             :   // If the iterator is invalid, we've reached the end without finding the
     659             :   // generator switch. Similarly, if we are OSR-ing, we're not resuming, so we
     660             :   // need no jump targets. So, ensure there are no jump targets and exit.
     661             :   if (!iterator.IsValid() || HasOsrEntryPoint()) {
     662             :     // Check top-level.
     663             :     if (!resume_jump_targets().empty()) {
     664             :       PrintF(stderr,
     665             :              "Found %zu top-level resume targets but no resume switch\n",
     666             :              resume_jump_targets().size());
     667             :       valid = false;
     668             :     }
     669             :     // Check loops.
     670             :     for (const std::pair<const int, LoopInfo>& loop_info : header_to_info_) {
     671             :       if (!loop_info.second.resume_jump_targets().empty()) {
     672             :         PrintF(stderr,
     673             :                "Found %zu resume targets at loop at offset %d, but no resume "
     674             :                "switch\n",
     675             :                loop_info.second.resume_jump_targets().size(), loop_info.first);
     676             :         valid = false;
     677             :       }
     678             :     }
     679             : 
     680             :     return valid;
     681             :   }
     682             : 
     683             :   // Otherwise, we've found the resume switch. Check that the top level jumps
     684             :   // only to leaves and loop headers, then check that each loop header handles
     685             :   // all the unresolved jumps, also jumping only to leaves and inner loop
     686             :   // headers.
     687             : 
     688             :   // First collect all required suspend ids.
     689             :   std::map<int, int> unresolved_suspend_ids;
     690             :   for (const interpreter::JumpTableTargetOffset& offset :
     691             :        iterator.GetJumpTableTargetOffsets()) {
     692             :     int suspend_id = offset.case_value;
     693             :     int resume_offset = offset.target_offset;
     694             : 
     695             :     unresolved_suspend_ids[suspend_id] = resume_offset;
     696             :   }
     697             : 
     698             :   // Check top-level.
     699             :   if (!ResumeJumpTargetLeavesResolveSuspendIds(-1, resume_jump_targets(),
     700             :                                                &unresolved_suspend_ids)) {
     701             :     valid = false;
     702             :   }
     703             :   // Check loops.
     704             :   for (const std::pair<const int, LoopInfo>& loop_info : header_to_info_) {
     705             :     if (!ResumeJumpTargetLeavesResolveSuspendIds(
     706             :             loop_info.first, loop_info.second.resume_jump_targets(),
     707             :             &unresolved_suspend_ids)) {
     708             :       valid = false;
     709             :     }
     710             :   }
     711             : 
     712             :   // Check that everything is resolved.
     713             :   if (!unresolved_suspend_ids.empty()) {
     714             :     PrintF(stderr,
     715             :            "Found suspend ids that are not resolved by a final leaf resume "
     716             :            "jump:\n");
     717             : 
     718             :     for (const std::pair<const int, int>& target : unresolved_suspend_ids) {
     719             :       PrintF(stderr, "  %d -> %d\n", target.first, target.second);
     720             :     }
     721             :     valid = false;
     722             :   }
     723             : 
     724             :   return valid;
     725             : }
     726             : 
     727             : bool BytecodeAnalysis::ResumeJumpTargetLeavesResolveSuspendIds(
     728             :     int parent_offset, const ZoneVector<ResumeJumpTarget>& resume_jump_targets,
     729             :     std::map<int, int>* unresolved_suspend_ids) {
     730             :   bool valid = true;
     731             :   for (const ResumeJumpTarget& target : resume_jump_targets) {
     732             :     std::map<int, int>::iterator it =
     733             :         unresolved_suspend_ids->find(target.suspend_id());
     734             :     if (it == unresolved_suspend_ids->end()) {
     735             :       PrintF(
     736             :           stderr,
     737             :           "No unresolved suspend found for resume target with suspend id %d\n",
     738             :           target.suspend_id());
     739             :       valid = false;
     740             :       continue;
     741             :     }
     742             :     int expected_target = it->second;
     743             : 
     744             :     if (target.is_leaf()) {
     745             :       // Leaves should have the expected target as their target.
     746             :       if (target.target_offset() != expected_target) {
     747             :         PrintF(
     748             :             stderr,
     749             :             "Expected leaf resume target for id %d to have target offset %d, "
     750             :             "but had %d\n",
     751             :             target.suspend_id(), expected_target, target.target_offset());
     752             :         valid = false;
     753             :       } else {
     754             :         // Make sure we're resuming to a Resume bytecode
     755             :         interpreter::BytecodeArrayAccessor assessor(bytecode_array(),
     756             :                                                     target.target_offset());
     757             :         if (assessor.current_bytecode() != Bytecode::kResumeGenerator) {
     758             :           PrintF(stderr,
     759             :                  "Expected resume target for id %d, offset %d, to be "
     760             :                  "ResumeGenerator, but found %s\n",
     761             :                  target.suspend_id(), target.target_offset(),
     762             :                  Bytecodes::ToString(assessor.current_bytecode()));
     763             : 
     764             :           valid = false;
     765             :         }
     766             :       }
     767             :       // We've resolved this suspend id, so erase it to make sure we don't
     768             :       // resolve it twice.
     769             :       unresolved_suspend_ids->erase(it);
     770             :     } else {
     771             :       // Non-leaves should have a direct inner loop header as their target.
     772             :       if (!IsLoopHeader(target.target_offset())) {
     773             :         PrintF(stderr,
     774             :                "Expected non-leaf resume target for id %d to have a loop "
     775             :                "header at target offset %d\n",
     776             :                target.suspend_id(), target.target_offset());
     777             :         valid = false;
     778             :       } else {
     779             :         LoopInfo loop_info = GetLoopInfoFor(target.target_offset());
     780             :         if (loop_info.parent_offset() != parent_offset) {
     781             :           PrintF(stderr,
     782             :                  "Expected non-leaf resume target for id %d to have a direct "
     783             :                  "inner loop at target offset %d\n",
     784             :                  target.suspend_id(), target.target_offset());
     785             :           valid = false;
     786             :         }
     787             :         // If the target loop is a valid inner loop, we'll check its validity
     788             :         // when we analyze its resume targets.
     789             :       }
     790             :     }
     791             :   }
     792             :   return valid;
     793             : }
     794             : 
     795             : bool BytecodeAnalysis::LivenessIsValid() {
     796             :   interpreter::BytecodeArrayRandomIterator iterator(bytecode_array(), zone());
     797             : 
     798             :   BytecodeLivenessState previous_liveness(bytecode_array()->register_count(),
     799             :                                           zone());
     800             : 
     801             :   int invalid_offset = -1;
     802             :   int which_invalid = -1;
     803             : 
     804             :   BytecodeLivenessState* next_bytecode_in_liveness = nullptr;
     805             : 
     806             :   // Ensure that there are no liveness changes if we iterate one more time.
     807             :   for (iterator.GoToEnd(); iterator.IsValid(); --iterator) {
     808             :     Bytecode bytecode = iterator.current_bytecode();
     809             : 
     810             :     int current_offset = iterator.current_offset();
     811             : 
     812             :     BytecodeLiveness& liveness = liveness_map_.GetLiveness(current_offset);
     813             : 
     814             :     previous_liveness.CopyFrom(*liveness.out);
     815             : 
     816             :     UpdateOutLiveness(bytecode, *liveness.out, next_bytecode_in_liveness,
     817             :                       iterator, liveness_map_);
     818             :     // UpdateOutLiveness skips kJumpLoop, so we update it manually.
     819             :     if (bytecode == Bytecode::kJumpLoop) {
     820             :       int target_offset = iterator.GetJumpTargetOffset();
     821             :       liveness.out->Union(*liveness_map_.GetInLiveness(target_offset));
     822             :     }
     823             : 
     824             :     if (!liveness.out->Equals(previous_liveness)) {
     825             :       // Reset the invalid liveness.
     826             :       liveness.out->CopyFrom(previous_liveness);
     827             :       invalid_offset = current_offset;
     828             :       which_invalid = 1;
     829             :       break;
     830             :     }
     831             : 
     832             :     previous_liveness.CopyFrom(*liveness.in);
     833             : 
     834             :     liveness.in->CopyFrom(*liveness.out);
     835             :     UpdateInLiveness(bytecode, *liveness.in, iterator);
     836             : 
     837             :     if (!liveness.in->Equals(previous_liveness)) {
     838             :       // Reset the invalid liveness.
     839             :       liveness.in->CopyFrom(previous_liveness);
     840             :       invalid_offset = current_offset;
     841             :       which_invalid = 0;
     842             :       break;
     843             :     }
     844             : 
     845             :     next_bytecode_in_liveness = liveness.in;
     846             :   }
     847             : 
     848             :   // Ensure that the accumulator is not live when jumping out of a loop, or on
     849             :   // the back-edge of a loop.
     850             :   for (iterator.GoToStart(); iterator.IsValid() && invalid_offset == -1;
     851             :        ++iterator) {
     852             :     Bytecode bytecode = iterator.current_bytecode();
     853             :     int current_offset = iterator.current_offset();
     854             :     int loop_header = GetLoopOffsetFor(current_offset);
     855             : 
     856             :     // We only care if we're inside a loop.
     857             :     if (loop_header == -1) continue;
     858             : 
     859             :     // We only care about jumps.
     860             :     if (!Bytecodes::IsJump(bytecode)) continue;
     861             : 
     862             :     int jump_target = iterator.GetJumpTargetOffset();
     863             : 
     864             :     // If this is a forward jump to somewhere else in the same loop, ignore it.
     865             :     if (Bytecodes::IsForwardJump(bytecode) &&
     866             :         GetLoopOffsetFor(jump_target) == loop_header) {
     867             :       continue;
     868             :     }
     869             : 
     870             :     // The accumulator must be dead at the start of the target of the jump.
     871             :     if (liveness_map_.GetLiveness(jump_target).in->AccumulatorIsLive()) {
     872             :       invalid_offset = jump_target;
     873             :       which_invalid = 0;
     874             :       break;
     875             :     }
     876             :   }
     877             : 
     878             :   if (invalid_offset != -1) {
     879             :     OFStream of(stderr);
     880             :     of << "Invalid liveness:" << std::endl;
     881             : 
     882             :     // Dump the bytecode, annotated with the liveness and marking loops.
     883             : 
     884             :     int loop_indent = 0;
     885             : 
     886             :     interpreter::BytecodeArrayIterator forward_iterator(bytecode_array());
     887             :     for (; !forward_iterator.done(); forward_iterator.Advance()) {
     888             :       int current_offset = forward_iterator.current_offset();
     889             :       const BitVector& in_liveness =
     890             :           GetInLivenessFor(current_offset)->bit_vector();
     891             :       const BitVector& out_liveness =
     892             :           GetOutLivenessFor(current_offset)->bit_vector();
     893             : 
     894             :       for (int i = 0; i < in_liveness.length(); ++i) {
     895             :         of << (in_liveness.Contains(i) ? 'L' : '.');
     896             :       }
     897             : 
     898             :       of << " | ";
     899             : 
     900             :       for (int i = 0; i < out_liveness.length(); ++i) {
     901             :         of << (out_liveness.Contains(i) ? 'L' : '.');
     902             :       }
     903             : 
     904             :       of << " : " << current_offset << " : ";
     905             : 
     906             :       // Draw loop back edges by indentin everything between loop headers and
     907             :       // jump loop instructions.
     908             :       if (forward_iterator.current_bytecode() == Bytecode::kJumpLoop) {
     909             :         loop_indent--;
     910             :       }
     911             :       for (int i = 0; i < loop_indent; ++i) {
     912             :         of << "| ";
     913             :       }
     914             :       if (forward_iterator.current_bytecode() == Bytecode::kJumpLoop) {
     915             :         of << "`-";
     916             :       } else if (IsLoopHeader(current_offset)) {
     917             :         of << ".>";
     918             :         loop_indent++;
     919             :       }
     920             :       forward_iterator.PrintTo(of);
     921             :       if (Bytecodes::IsJump(forward_iterator.current_bytecode())) {
     922             :         of << " (@" << forward_iterator.GetJumpTargetOffset() << ")";
     923             :       }
     924             :       of << std::endl;
     925             : 
     926             :       if (current_offset == invalid_offset) {
     927             :         // Underline the invalid liveness.
     928             :         if (which_invalid == 0) {
     929             :           for (int i = 0; i < in_liveness.length(); ++i) {
     930             :             of << '^';
     931             :           }
     932             :           for (int i = 0; i < out_liveness.length() + 3; ++i) {
     933             :             of << ' ';
     934             :           }
     935             :         } else {
     936             :           for (int i = 0; i < in_liveness.length() + 3; ++i) {
     937             :             of << ' ';
     938             :           }
     939             :           for (int i = 0; i < out_liveness.length(); ++i) {
     940             :             of << '^';
     941             :           }
     942             :         }
     943             : 
     944             :         // Make sure to draw the loop indentation marks on this additional line.
     945             :         of << " : " << current_offset << " : ";
     946             :         for (int i = 0; i < loop_indent; ++i) {
     947             :           of << "| ";
     948             :         }
     949             : 
     950             :         of << std::endl;
     951             :       }
     952             :     }
     953             :   }
     954             : 
     955             :   return invalid_offset == -1;
     956             : }
     957             : #endif
     958             : 
     959             : }  // namespace compiler
     960             : }  // namespace internal
     961      121996 : }  // namespace v8

Generated by: LCOV version 1.10