bytecode-analysis.cc 35.4 KB
Newer Older
1 2 3 4 5 6
// Copyright 2016 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#include "src/compiler/bytecode-analysis.h"

7
#include "src/interpreter/bytecode-array-iterator.h"
8
#include "src/interpreter/bytecode-array-random-iterator.h"
9
#include "src/objects/objects-inl.h"
10
#include "src/utils/ostreams.h"
11 12 13 14 15

namespace v8 {
namespace internal {
namespace compiler {

16 17 18
using interpreter::Bytecode;
using interpreter::Bytecodes;
using interpreter::OperandType;
19

20 21 22
BytecodeLoopAssignments::BytecodeLoopAssignments(int parameter_count,
                                                 int register_count, Zone* zone)
    : parameter_count_(parameter_count),
23 24
      bit_vector_(
          zone->New<BitVector>(parameter_count + register_count, zone)) {}
25 26 27 28 29 30 31 32 33

void BytecodeLoopAssignments::Add(interpreter::Register r) {
  if (r.is_parameter()) {
    bit_vector_->Add(r.ToParameterIndex(parameter_count_));
  } else {
    bit_vector_->Add(parameter_count_ + r.index());
  }
}

34
void BytecodeLoopAssignments::AddList(interpreter::Register r, uint32_t count) {
35
  if (r.is_parameter()) {
36 37 38 39
    for (uint32_t i = 0; i < count; i++) {
      DCHECK(interpreter::Register(r.index() + i).is_parameter());
      bit_vector_->Add(r.ToParameterIndex(parameter_count_) + i);
    }
40
  } else {
41 42 43 44
    for (uint32_t i = 0; i < count; i++) {
      DCHECK(!interpreter::Register(r.index() + i).is_parameter());
      bit_vector_->Add(parameter_count_ + r.index() + i);
    }
45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64
  }
}


void BytecodeLoopAssignments::Union(const BytecodeLoopAssignments& other) {
  bit_vector_->Union(*other.bit_vector_);
}

bool BytecodeLoopAssignments::ContainsParameter(int index) const {
  DCHECK_GE(index, 0);
  DCHECK_LT(index, parameter_count());
  return bit_vector_->Contains(index);
}

bool BytecodeLoopAssignments::ContainsLocal(int index) const {
  DCHECK_GE(index, 0);
  DCHECK_LT(index, local_count());
  return bit_vector_->Contains(parameter_count_ + index);
}

65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80
ResumeJumpTarget::ResumeJumpTarget(int suspend_id, int target_offset,
                                   int final_target_offset)
    : suspend_id_(suspend_id),
      target_offset_(target_offset),
      final_target_offset_(final_target_offset) {}

ResumeJumpTarget ResumeJumpTarget::Leaf(int suspend_id, int target_offset) {
  return ResumeJumpTarget(suspend_id, target_offset, target_offset);
}

ResumeJumpTarget ResumeJumpTarget::AtLoopHeader(int loop_header_offset,
                                                const ResumeJumpTarget& next) {
  return ResumeJumpTarget(next.suspend_id(), loop_header_offset,
                          next.target_offset());
}

81
BytecodeAnalysis::BytecodeAnalysis(Handle<BytecodeArray> bytecode_array,
82
                                   Zone* zone, BytecodeOffset osr_bailout_id,
83
                                   bool analyze_liveness)
84 85
    : bytecode_array_(bytecode_array),
      zone_(zone),
86 87
      osr_bailout_id_(osr_bailout_id),
      analyze_liveness_(analyze_liveness),
88
      loop_stack_(zone),
89
      loop_end_index_queue_(zone),
90
      resume_jump_targets_(zone),
91
      end_to_header_(zone),
92
      header_to_info_(zone),
93 94
      osr_entry_point_(-1) {
  if (analyze_liveness) liveness_map_.emplace(bytecode_array->length(), zone);
95 96
  Analyze();
}
97 98 99

namespace {

100
void UpdateInLiveness(Bytecode bytecode, BytecodeLivenessState* in_liveness,
101
                      const interpreter::BytecodeArrayIterator& iterator) {
102 103 104
  int num_operands = Bytecodes::NumberOfOperands(bytecode);
  const OperandType* operand_types = Bytecodes::GetOperandTypes(bytecode);

105 106 107
  // Special case Suspend and Resume to just pass through liveness.
  if (bytecode == Bytecode::kSuspendGenerator) {
    // The generator object has to be live.
108
    in_liveness->MarkRegisterLive(iterator.GetRegisterOperand(0).index());
109 110
    // Suspend additionally reads and returns the accumulator
    DCHECK(Bytecodes::ReadsAccumulator(bytecode));
111
    in_liveness->MarkAccumulatorLive();
112 113 114 115
    return;
  }
  if (bytecode == Bytecode::kResumeGenerator) {
    // The generator object has to be live.
116
    in_liveness->MarkRegisterLive(iterator.GetRegisterOperand(0).index());
117 118 119
    return;
  }

120
  if (Bytecodes::WritesAccumulator(bytecode)) {
121
    in_liveness->MarkAccumulatorDead();
122 123 124 125
  }
  for (int i = 0; i < num_operands; ++i) {
    switch (operand_types[i]) {
      case OperandType::kRegOut: {
126
        interpreter::Register r = iterator.GetRegisterOperand(i);
127
        if (!r.is_parameter()) {
128
          in_liveness->MarkRegisterDead(r.index());
129 130 131
        }
        break;
      }
132
      case OperandType::kRegOutList: {
133 134
        interpreter::Register r = iterator.GetRegisterOperand(i++);
        uint32_t reg_count = iterator.GetRegisterCountOperand(i);
135 136 137
        if (!r.is_parameter()) {
          for (uint32_t j = 0; j < reg_count; ++j) {
            DCHECK(!interpreter::Register(r.index() + j).is_parameter());
138
            in_liveness->MarkRegisterDead(r.index() + j);
139 140 141 142
          }
        }
        break;
      }
143
      case OperandType::kRegOutPair: {
144
        interpreter::Register r = iterator.GetRegisterOperand(i);
145 146
        if (!r.is_parameter()) {
          DCHECK(!interpreter::Register(r.index() + 1).is_parameter());
147 148
          in_liveness->MarkRegisterDead(r.index());
          in_liveness->MarkRegisterDead(r.index() + 1);
149 150 151 152
        }
        break;
      }
      case OperandType::kRegOutTriple: {
153
        interpreter::Register r = iterator.GetRegisterOperand(i);
154 155 156
        if (!r.is_parameter()) {
          DCHECK(!interpreter::Register(r.index() + 1).is_parameter());
          DCHECK(!interpreter::Register(r.index() + 2).is_parameter());
157 158 159
          in_liveness->MarkRegisterDead(r.index());
          in_liveness->MarkRegisterDead(r.index() + 1);
          in_liveness->MarkRegisterDead(r.index() + 2);
160 161 162 163 164 165 166 167 168
        }
        break;
      }
      default:
        DCHECK(!Bytecodes::IsRegisterOutputOperandType(operand_types[i]));
        break;
    }
  }

169 170 171 172 173
  if (Bytecodes::WritesImplicitRegister(bytecode)) {
    in_liveness->MarkRegisterDead(
        interpreter::Register::FromShortStar(bytecode).index());
  }

174
  if (Bytecodes::ReadsAccumulator(bytecode)) {
175
    in_liveness->MarkAccumulatorLive();
176 177 178 179
  }
  for (int i = 0; i < num_operands; ++i) {
    switch (operand_types[i]) {
      case OperandType::kReg: {
180
        interpreter::Register r = iterator.GetRegisterOperand(i);
181
        if (!r.is_parameter()) {
182
          in_liveness->MarkRegisterLive(r.index());
183 184 185 186
        }
        break;
      }
      case OperandType::kRegPair: {
187
        interpreter::Register r = iterator.GetRegisterOperand(i);
188 189
        if (!r.is_parameter()) {
          DCHECK(!interpreter::Register(r.index() + 1).is_parameter());
190 191
          in_liveness->MarkRegisterLive(r.index());
          in_liveness->MarkRegisterLive(r.index() + 1);
192 193 194 195
        }
        break;
      }
      case OperandType::kRegList: {
196 197
        interpreter::Register r = iterator.GetRegisterOperand(i++);
        uint32_t reg_count = iterator.GetRegisterCountOperand(i);
198 199 200
        if (!r.is_parameter()) {
          for (uint32_t j = 0; j < reg_count; ++j) {
            DCHECK(!interpreter::Register(r.index() + j).is_parameter());
201
            in_liveness->MarkRegisterLive(r.index() + j);
202 203
          }
        }
204
        break;
205 206 207 208 209 210 211 212
      }
      default:
        DCHECK(!Bytecodes::IsRegisterInputOperandType(operand_types[i]));
        break;
    }
  }
}

213 214
void UpdateOutLiveness(Bytecode bytecode, BytecodeLivenessState* out_liveness,
                       BytecodeLivenessState* next_bytecode_in_liveness,
215
                       const interpreter::BytecodeArrayIterator& iterator,
216 217
                       Handle<BytecodeArray> bytecode_array,
                       const BytecodeLivenessMap& liveness_map) {
218
  int current_offset = iterator.current_offset();
219

220 221 222
  // Special case Suspend and Resume to just pass through liveness.
  if (bytecode == Bytecode::kSuspendGenerator ||
      bytecode == Bytecode::kResumeGenerator) {
223
    out_liveness->Union(*next_bytecode_in_liveness);
224 225 226
    return;
  }

227 228 229
  // Update from jump target (if any). Skip loops, we update these manually in
  // the liveness iterations.
  if (Bytecodes::IsForwardJump(bytecode)) {
230
    int target_offset = iterator.GetJumpTargetOffset();
231
    out_liveness->Union(*liveness_map.GetInLiveness(target_offset));
232
  } else if (Bytecodes::IsSwitch(bytecode)) {
233
    for (const auto& entry : iterator.GetJumpTableTargetOffsets()) {
234
      out_liveness->Union(*liveness_map.GetInLiveness(entry.target_offset));
235
    }
236 237
  }

238 239 240 241
  // Update from next bytecode (unless there isn't one or this is an
  // unconditional jump).
  if (next_bytecode_in_liveness != nullptr &&
      !Bytecodes::IsUnconditionalJump(bytecode)) {
242
    out_liveness->Union(*next_bytecode_in_liveness);
243 244 245 246 247 248
  }

  // Update from exception handler (if any).
  if (!interpreter::Bytecodes::IsWithoutExternalSideEffects(bytecode)) {
    int handler_context;
    // TODO(leszeks): We should look up this range only once per entry.
249
    HandlerTable table(*bytecode_array);
250
    int handler_offset =
251
        table.LookupRange(current_offset, &handler_context, nullptr);
252 253

    if (handler_offset != -1) {
254 255 256
      bool was_accumulator_live = out_liveness->AccumulatorIsLive();
      out_liveness->Union(*liveness_map.GetInLiveness(handler_offset));
      out_liveness->MarkRegisterLive(handler_context);
257 258 259 260 261
      if (!was_accumulator_live) {
        // The accumulator is reset to the exception on entry into a handler,
        // and so shouldn't be considered live coming out of this bytecode just
        // because it's live coming into the handler. So, kill the accumulator
        // if the handler is the only thing that made it live.
262
        out_liveness->MarkAccumulatorDead();
263 264 265 266 267 268

        // TODO(leszeks): Ideally the accumulator wouldn't be considered live at
        // the start of the handler, but looking up if the current bytecode is
        // the start of a handler is not free, so we should only do it if we
        // decide it's necessary.
      }
269 270 271 272
    }
  }
}

273
void UpdateLiveness(Bytecode bytecode, BytecodeLiveness const& liveness,
274
                    BytecodeLivenessState** next_bytecode_in_liveness,
275
                    const interpreter::BytecodeArrayIterator& iterator,
276
                    Handle<BytecodeArray> bytecode_array,
277
                    const BytecodeLivenessMap& liveness_map) {
278
  UpdateOutLiveness(bytecode, liveness.out, *next_bytecode_in_liveness,
279
                    iterator, bytecode_array, liveness_map);
280
  liveness.in->CopyFrom(*liveness.out);
281
  UpdateInLiveness(bytecode, liveness.in, iterator);
282

283
  *next_bytecode_in_liveness = liveness.in;
284 285
}

286
void UpdateAssignments(Bytecode bytecode, BytecodeLoopAssignments* assignments,
287
                       const interpreter::BytecodeArrayIterator& iterator) {
288 289 290 291 292 293
  int num_operands = Bytecodes::NumberOfOperands(bytecode);
  const OperandType* operand_types = Bytecodes::GetOperandTypes(bytecode);

  for (int i = 0; i < num_operands; ++i) {
    switch (operand_types[i]) {
      case OperandType::kRegOut: {
294
        assignments->Add(iterator.GetRegisterOperand(i));
295 296
        break;
      }
297
      case OperandType::kRegOutList: {
298 299
        interpreter::Register r = iterator.GetRegisterOperand(i++);
        uint32_t reg_count = iterator.GetRegisterCountOperand(i);
300
        assignments->AddList(r, reg_count);
301 302
        break;
      }
303
      case OperandType::kRegOutPair: {
304
        assignments->AddList(iterator.GetRegisterOperand(i), 2);
305 306 307
        break;
      }
      case OperandType::kRegOutTriple: {
308
        assignments->AddList(iterator.GetRegisterOperand(i), 3);
309 310 311 312 313 314 315
        break;
      }
      default:
        DCHECK(!Bytecodes::IsRegisterOutputOperandType(operand_types[i]));
        break;
    }
  }
316 317 318 319

  if (Bytecodes::WritesImplicitRegister(bytecode)) {
    assignments->Add(interpreter::Register::FromShortStar(bytecode));
  }
320 321
}

322
}  // namespace
323

324
void BytecodeAnalysis::Analyze() {
325
  loop_stack_.push({-1, nullptr});
326

327
  BytecodeLivenessState* next_bytecode_in_liveness = nullptr;
328
  int generator_switch_index = -1;
329 330
  int osr_loop_end_offset = osr_bailout_id_.ToInt();
  DCHECK_EQ(osr_loop_end_offset < 0, osr_bailout_id_.IsNone());
331

332
  interpreter::BytecodeArrayRandomIterator iterator(bytecode_array(), zone());
333
  for (iterator.GoToEnd(); iterator.IsValid(); --iterator) {
334 335 336
    Bytecode bytecode = iterator.current_bytecode();
    int current_offset = iterator.current_offset();

337 338 339
    if (bytecode == Bytecode::kSwitchOnGeneratorState) {
      DCHECK_EQ(generator_switch_index, -1);
      generator_switch_index = iterator.current_index();
340
    } else if (bytecode == Bytecode::kJumpLoop) {
341 342 343
      // Every byte up to and including the last byte within the backwards jump
      // instruction is considered part of the loop, set loop end accordingly.
      int loop_end = current_offset + iterator.current_bytecode_size();
344 345
      int loop_header = iterator.GetJumpTargetOffset();
      PushLoop(loop_header, loop_end);
346

347
      if (current_offset == osr_loop_end_offset) {
348
        osr_entry_point_ = loop_header;
349
      } else if (current_offset < osr_loop_end_offset) {
350
        // Assert that we've found the osr_entry_point if we've gone past the
351
        // osr_loop_end_offset. Note, we are iterating the bytecode in reverse,
352 353
        // so the less-than in the above condition is correct.
        DCHECK_LE(0, osr_entry_point_);
354 355
      }

356
      // Save the index so that we can do another pass later.
357
      if (analyze_liveness_) {
358
        loop_end_index_queue_.push_back(iterator.current_index());
359
      }
360 361 362 363 364 365 366 367 368 369
    }

    // We have to pop from loop_stack_ if:
    // 1) We entered the body of the loop
    // 2) If we have a JumpLoop that jumps to itself (i.e an empty loop)
    bool pop_current_loop = loop_stack_.size() > 1 &&
                            (bytecode != Bytecode::kJumpLoop ||
                             iterator.GetJumpTargetOffset() == current_offset);

    if (pop_current_loop) {
370 371 372 373 374 375 376
      LoopStackEntry& current_loop = loop_stack_.top();
      LoopInfo* current_loop_info = current_loop.loop_info;

      // TODO(leszeks): Ideally, we'd only set values that were assigned in
      // the loop *and* are live when the loop exits. However, this requires
      // tracking the out-liveness of *all* loop exits, which is not
      // information we currently have.
377
      UpdateAssignments(bytecode, &current_loop_info->assignments(), iterator);
378

379 380
      // Update suspend counts for this loop.
      if (bytecode == Bytecode::kSuspendGenerator) {
381 382 383 384 385 386 387
        int suspend_id = iterator.GetUnsignedImmediateOperand(3);
        int resume_offset = current_offset + iterator.current_bytecode_size();
        current_loop_info->AddResumeTarget(
            ResumeJumpTarget::Leaf(suspend_id, resume_offset));
      }

      // If we've reached the header of the loop, pop it off the stack.
388 389 390
      if (current_offset == current_loop.header_offset) {
        loop_stack_.pop();
        if (loop_stack_.size() > 1) {
391 392 393 394
          // If there is still an outer loop, propagate inner loop assignments.
          LoopInfo* parent_loop_info = loop_stack_.top().loop_info;

          parent_loop_info->assignments().Union(
395
              current_loop_info->assignments());
396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431

          // Also, propagate resume targets. Instead of jumping to the target
          // itself, the outer loop will jump to this loop header for any
          // targets that are inside the current loop, so that this loop stays
          // reducible. Hence, a nested loop of the form:
          //
          //                switch (#1 -> suspend1, #2 -> suspend2)
          //                loop {
          //     suspend1:    suspend #1
          //                  loop {
          //     suspend2:      suspend #2
          //                  }
          //                }
          //
          // becomes:
          //
          //                switch (#1 -> loop1, #2 -> loop1)
          //     loop1:     loop {
          //                  switch (#1 -> suspend1, #2 -> loop2)
          //     suspend1:    suspend #1
          //     loop2:       loop {
          //                    switch (#2 -> suspend2)
          //     suspend2:      suspend #2
          //                  }
          //                }
          for (const auto& target : current_loop_info->resume_jump_targets()) {
            parent_loop_info->AddResumeTarget(
                ResumeJumpTarget::AtLoopHeader(current_offset, target));
          }

        } else {
          // Otherwise, just propagate inner loop suspends to top-level.
          for (const auto& target : current_loop_info->resume_jump_targets()) {
            resume_jump_targets_.push_back(
                ResumeJumpTarget::AtLoopHeader(current_offset, target));
          }
432 433
        }
      }
434
    } else if (bytecode == Bytecode::kSuspendGenerator) {
435 436 437 438 439 440 441
      // If we're not in a loop, we still need to look for suspends.
      // TODO(leszeks): It would be nice to de-duplicate this with the in-loop
      // case
      int suspend_id = iterator.GetUnsignedImmediateOperand(3);
      int resume_offset = current_offset + iterator.current_bytecode_size();
      resume_jump_targets_.push_back(
          ResumeJumpTarget::Leaf(suspend_id, resume_offset));
442
    }
443

444
    if (analyze_liveness_) {
445
      BytecodeLiveness const& liveness = liveness_map().InitializeLiveness(
446
          current_offset, bytecode_array()->register_count(), zone());
447
      UpdateLiveness(bytecode, liveness, &next_bytecode_in_liveness, iterator,
448
                     bytecode_array(), liveness_map());
449
    }
450 451 452
  }

  DCHECK_EQ(loop_stack_.size(), 1u);
453
  DCHECK_EQ(loop_stack_.top().header_offset, -1);
454

455 456
  DCHECK(ResumeJumpTargetsAreValid());

457
  if (!analyze_liveness_) return;
458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478

  // At this point, every bytecode has a valid in and out liveness, except for
  // propagating liveness across back edges (i.e. JumpLoop). Subsequent liveness
  // analysis iterations can only add additional liveness bits that are pulled
  // across these back edges.
  //
  // Furthermore, a loop header's in-liveness can only change based on any
  // bytecodes *after* the loop end --  it cannot change as a result of the
  // JumpLoop liveness being updated, as the only liveness bits than can be
  // added to the loop body are those of the loop header.
  //
  // So, if we know that the liveness of bytecodes after a loop header won't
  // change (e.g. because there are no loops in them, or we have already ensured
  // those loops are valid), we can safely update the loop end and pass over the
  // loop body, and then never have to pass over that loop end again, because we
  // have shown that its target, the loop header, can't change from the entries
  // after the loop, and can't change from any loop body pass.
  //
  // This means that in a pass, we can iterate backwards over the bytecode
  // array, process any loops that we encounter, and on subsequent passes we can
  // skip processing those loops (though we still have to process inner loops).
479 480 481 482
  //
  // Equivalently, we can queue up loop ends from back to front, and pass over
  // the loops in that order, as this preserves both the bottom-to-top and
  // outer-to-inner requirements.
483

484 485
  for (int loop_end_index : loop_end_index_queue_) {
    iterator.GoToIndex(loop_end_index);
486 487 488

    DCHECK_EQ(iterator.current_bytecode(), Bytecode::kJumpLoop);

489 490
    int header_offset = iterator.GetJumpTargetOffset();
    int end_offset = iterator.current_offset();
491

492
    BytecodeLiveness& header_liveness =
493 494
        liveness_map().GetLiveness(header_offset);
    BytecodeLiveness& end_liveness = liveness_map().GetLiveness(end_offset);
495

496 497 498 499 500 501
    if (!end_liveness.out->UnionIsChanged(*header_liveness.in)) {
      // Only update the loop body if the loop end liveness changed.
      continue;
    }
    end_liveness.in->CopyFrom(*end_liveness.out);
    next_bytecode_in_liveness = end_liveness.in;
502

503 504 505 506 507
    // Advance into the loop body.
    --iterator;
    for (; iterator.current_offset() > header_offset; --iterator) {
      Bytecode bytecode = iterator.current_bytecode();
      int current_offset = iterator.current_offset();
508
      BytecodeLiveness const& liveness =
509
          liveness_map().GetLiveness(current_offset);
510
      UpdateLiveness(bytecode, liveness, &next_bytecode_in_liveness, iterator,
511
                     bytecode_array(), liveness_map());
512
    }
513 514
    // Now we are at the loop header. Since the in-liveness of the header
    // can't change, we need only to update the out-liveness.
515
    UpdateOutLiveness(iterator.current_bytecode(), header_liveness.out,
516
                      next_bytecode_in_liveness, iterator, bytecode_array(),
517
                      liveness_map());
518 519
  }

520 521 522 523 524 525 526 527 528 529
  // Process the generator switch statement separately, once the loops are done.
  // This has to be a separate pass because the generator switch can jump into
  // the middle of loops (and is the only kind of jump that can jump across a
  // loop header).
  if (generator_switch_index != -1) {
    iterator.GoToIndex(generator_switch_index);
    DCHECK_EQ(iterator.current_bytecode(), Bytecode::kSwitchOnGeneratorState);

    int current_offset = iterator.current_offset();
    BytecodeLiveness& switch_liveness =
530
        liveness_map().GetLiveness(current_offset);
531 532 533 534

    bool any_changed = false;
    for (const auto& entry : iterator.GetJumpTableTargetOffsets()) {
      if (switch_liveness.out->UnionIsChanged(
535
              *liveness_map().GetInLiveness(entry.target_offset))) {
536 537 538 539 540 541 542 543
        any_changed = true;
      }
    }

    // If the switch liveness changed, we have to propagate it up the remaining
    // bytecodes before it.
    if (any_changed) {
      switch_liveness.in->CopyFrom(*switch_liveness.out);
544
      UpdateInLiveness(Bytecode::kSwitchOnGeneratorState, switch_liveness.in,
545 546 547 548 549
                       iterator);
      next_bytecode_in_liveness = switch_liveness.in;
      for (--iterator; iterator.IsValid(); --iterator) {
        Bytecode bytecode = iterator.current_bytecode();
        int current_offset = iterator.current_offset();
550
        BytecodeLiveness const& liveness =
551
            liveness_map().GetLiveness(current_offset);
552 553 554 555

        // There shouldn't be any more loops.
        DCHECK_NE(bytecode, Bytecode::kJumpLoop);

556
        UpdateLiveness(bytecode, liveness, &next_bytecode_in_liveness, iterator,
557
                       bytecode_array(), liveness_map());
558 559 560 561
      }
    }
  }

562
  DCHECK(analyze_liveness_);
563 564 565 566 567
  if (FLAG_trace_environment_liveness) {
    StdoutStream of;
    PrintLivenessTo(of);
  }

568
  DCHECK(LivenessIsValid());
569 570 571
}

void BytecodeAnalysis::PushLoop(int loop_header, int loop_end) {
572 573 574 575
  DCHECK_LT(loop_header, loop_end);
  DCHECK_LT(loop_stack_.top().header_offset, loop_header);
  DCHECK_EQ(end_to_header_.find(loop_end), end_to_header_.end());
  DCHECK_EQ(header_to_info_.find(loop_header), header_to_info_.end());
576 577 578 579 580 581 582 583 584

  int parent_offset = loop_stack_.top().header_offset;

  end_to_header_.insert({loop_end, loop_header});
  auto it = header_to_info_.insert(
      {loop_header, LoopInfo(parent_offset, bytecode_array_->parameter_count(),
                             bytecode_array_->register_count(), zone_)});
  // Get the loop info pointer from the output of insert.
  LoopInfo* loop_info = &it.first->second;
585

586
  loop_stack_.push({loop_header, loop_info});
587 588 589
}

bool BytecodeAnalysis::IsLoopHeader(int offset) const {
590
  return header_to_info_.find(offset) != header_to_info_.end();
591 592 593
}

int BytecodeAnalysis::GetLoopOffsetFor(int offset) const {
594
  auto loop_end_to_header = end_to_header_.upper_bound(offset);
595 596 597 598
  // If there is no next end => offset is not in a loop.
  if (loop_end_to_header == end_to_header_.end()) {
    return -1;
  }
599
  // If the header precedes the offset, this is the loop
600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619
  //
  //   .> header  <--loop_end_to_header
  //   |
  //   |  <--offset
  //   |
  //   `- end
  if (loop_end_to_header->second <= offset) {
    return loop_end_to_header->second;
  }
  // Otherwise there is a (potentially nested) loop after this offset.
  //
  //    <--offset
  //
  //   .> header
  //   |
  //   | .> header  <--loop_end_to_header
  //   | |
  //   | `- end
  //   |
  //   `- end
620 621
  // We just return the parent of the next loop (might be -1).
  DCHECK(header_to_info_.upper_bound(offset) != header_to_info_.end());
622

623
  return header_to_info_.upper_bound(offset)->second.parent_offset();
624 625
}

626
const LoopInfo& BytecodeAnalysis::GetLoopInfoFor(int header_offset) const {
627 628
  DCHECK(IsLoopHeader(header_offset));

629
  return header_to_info_.find(header_offset)->second;
630 631
}

632 633
const BytecodeLivenessState* BytecodeAnalysis::GetInLivenessFor(
    int offset) const {
634
  if (!analyze_liveness_) return nullptr;
635

636
  return liveness_map().GetInLiveness(offset);
637 638
}

639 640
const BytecodeLivenessState* BytecodeAnalysis::GetOutLivenessFor(
    int offset) const {
641
  if (!analyze_liveness_) return nullptr;
642

643
  return liveness_map().GetOutLiveness(offset);
644 645 646 647 648 649 650 651
}

std::ostream& BytecodeAnalysis::PrintLivenessTo(std::ostream& os) const {
  interpreter::BytecodeArrayIterator iterator(bytecode_array());

  for (; !iterator.done(); iterator.Advance()) {
    int current_offset = iterator.current_offset();

652 653 654 655
    const BitVector& in_liveness =
        GetInLivenessFor(current_offset)->bit_vector();
    const BitVector& out_liveness =
        GetOutLivenessFor(current_offset)->bit_vector();
656

657 658
    for (int i = 0; i < in_liveness.length(); ++i) {
      os << (in_liveness.Contains(i) ? "L" : ".");
659 660 661
    }
    os << " -> ";

662 663
    for (int i = 0; i < out_liveness.length(); ++i) {
      os << (out_liveness.Contains(i) ? "L" : ".");
664 665 666 667 668 669 670 671 672 673
    }

    os << " | " << current_offset << ": ";
    iterator.PrintTo(os) << std::endl;
  }

  return os;
}

#if DEBUG
674 675 676 677 678 679 680 681 682 683 684 685
bool BytecodeAnalysis::ResumeJumpTargetsAreValid() {
  bool valid = true;

  // Find the generator switch.
  interpreter::BytecodeArrayRandomIterator iterator(bytecode_array(), zone());
  for (iterator.GoToStart(); iterator.IsValid(); ++iterator) {
    if (iterator.current_bytecode() == Bytecode::kSwitchOnGeneratorState) {
      break;
    }
  }

  // If the iterator is invalid, we've reached the end without finding the
686 687
  // generator switch. So, ensure there are no jump targets and exit.
  if (!iterator.IsValid()) {
688 689 690 691 692 693 694 695
    // Check top-level.
    if (!resume_jump_targets().empty()) {
      PrintF(stderr,
             "Found %zu top-level resume targets but no resume switch\n",
             resume_jump_targets().size());
      valid = false;
    }
    // Check loops.
696
    for (const std::pair<const int, LoopInfo>& loop_info : header_to_info_) {
697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714 715 716 717 718 719 720 721 722 723 724 725 726 727 728 729
      if (!loop_info.second.resume_jump_targets().empty()) {
        PrintF(stderr,
               "Found %zu resume targets at loop at offset %d, but no resume "
               "switch\n",
               loop_info.second.resume_jump_targets().size(), loop_info.first);
        valid = false;
      }
    }

    return valid;
  }

  // Otherwise, we've found the resume switch. Check that the top level jumps
  // only to leaves and loop headers, then check that each loop header handles
  // all the unresolved jumps, also jumping only to leaves and inner loop
  // headers.

  // First collect all required suspend ids.
  std::map<int, int> unresolved_suspend_ids;
  for (const interpreter::JumpTableTargetOffset& offset :
       iterator.GetJumpTableTargetOffsets()) {
    int suspend_id = offset.case_value;
    int resume_offset = offset.target_offset;

    unresolved_suspend_ids[suspend_id] = resume_offset;
  }

  // Check top-level.
  if (!ResumeJumpTargetLeavesResolveSuspendIds(-1, resume_jump_targets(),
                                               &unresolved_suspend_ids)) {
    valid = false;
  }
  // Check loops.
730
  for (const std::pair<const int, LoopInfo>& loop_info : header_to_info_) {
731 732 733 734 735 736 737 738 739 740 741 742 743
    if (!ResumeJumpTargetLeavesResolveSuspendIds(
            loop_info.first, loop_info.second.resume_jump_targets(),
            &unresolved_suspend_ids)) {
      valid = false;
    }
  }

  // Check that everything is resolved.
  if (!unresolved_suspend_ids.empty()) {
    PrintF(stderr,
           "Found suspend ids that are not resolved by a final leaf resume "
           "jump:\n");

744
    for (const std::pair<const int, int>& target : unresolved_suspend_ids) {
745 746 747 748 749 750 751 752 753 754 755 756 757 758 759 760 761 762 763 764 765 766 767 768 769 770 771 772 773 774 775 776 777 778 779 780
      PrintF(stderr, "  %d -> %d\n", target.first, target.second);
    }
    valid = false;
  }

  return valid;
}

bool BytecodeAnalysis::ResumeJumpTargetLeavesResolveSuspendIds(
    int parent_offset, const ZoneVector<ResumeJumpTarget>& resume_jump_targets,
    std::map<int, int>* unresolved_suspend_ids) {
  bool valid = true;
  for (const ResumeJumpTarget& target : resume_jump_targets) {
    std::map<int, int>::iterator it =
        unresolved_suspend_ids->find(target.suspend_id());
    if (it == unresolved_suspend_ids->end()) {
      PrintF(
          stderr,
          "No unresolved suspend found for resume target with suspend id %d\n",
          target.suspend_id());
      valid = false;
      continue;
    }
    int expected_target = it->second;

    if (target.is_leaf()) {
      // Leaves should have the expected target as their target.
      if (target.target_offset() != expected_target) {
        PrintF(
            stderr,
            "Expected leaf resume target for id %d to have target offset %d, "
            "but had %d\n",
            target.suspend_id(), expected_target, target.target_offset());
        valid = false;
      } else {
        // Make sure we're resuming to a Resume bytecode
781
        interpreter::BytecodeArrayIterator iterator(bytecode_array(),
782
                                                    target.target_offset());
783
        if (iterator.current_bytecode() != Bytecode::kResumeGenerator) {
784 785 786 787
          PrintF(stderr,
                 "Expected resume target for id %d, offset %d, to be "
                 "ResumeGenerator, but found %s\n",
                 target.suspend_id(), target.target_offset(),
788
                 Bytecodes::ToString(iterator.current_bytecode()));
789 790 791 792 793 794 795 796 797 798 799 800 801 802 803 804 805 806 807 808 809 810 811 812 813 814 815 816 817 818 819 820

          valid = false;
        }
      }
      // We've resolved this suspend id, so erase it to make sure we don't
      // resolve it twice.
      unresolved_suspend_ids->erase(it);
    } else {
      // Non-leaves should have a direct inner loop header as their target.
      if (!IsLoopHeader(target.target_offset())) {
        PrintF(stderr,
               "Expected non-leaf resume target for id %d to have a loop "
               "header at target offset %d\n",
               target.suspend_id(), target.target_offset());
        valid = false;
      } else {
        LoopInfo loop_info = GetLoopInfoFor(target.target_offset());
        if (loop_info.parent_offset() != parent_offset) {
          PrintF(stderr,
                 "Expected non-leaf resume target for id %d to have a direct "
                 "inner loop at target offset %d\n",
                 target.suspend_id(), target.target_offset());
          valid = false;
        }
        // If the target loop is a valid inner loop, we'll check its validity
        // when we analyze its resume targets.
      }
    }
  }
  return valid;
}

821
bool BytecodeAnalysis::LivenessIsValid() {
822
  interpreter::BytecodeArrayRandomIterator iterator(bytecode_array(), zone());
823

824 825
  BytecodeLivenessState previous_liveness(bytecode_array()->register_count(),
                                          zone());
826 827 828 829

  int invalid_offset = -1;
  int which_invalid = -1;

830
  BytecodeLivenessState* next_bytecode_in_liveness = nullptr;
831

832
  // Ensure that there are no liveness changes if we iterate one more time.
833
  for (iterator.GoToEnd(); iterator.IsValid(); --iterator) {
834 835 836 837
    Bytecode bytecode = iterator.current_bytecode();

    int current_offset = iterator.current_offset();

838
    BytecodeLiveness& liveness = liveness_map().GetLiveness(current_offset);
839 840 841

    previous_liveness.CopyFrom(*liveness.out);

842
    UpdateOutLiveness(bytecode, liveness.out, next_bytecode_in_liveness,
843
                      iterator, bytecode_array(), liveness_map());
844 845 846
    // UpdateOutLiveness skips kJumpLoop, so we update it manually.
    if (bytecode == Bytecode::kJumpLoop) {
      int target_offset = iterator.GetJumpTargetOffset();
847
      liveness.out->Union(*liveness_map().GetInLiveness(target_offset));
848 849 850 851 852 853 854 855 856 857 858 859 860
    }

    if (!liveness.out->Equals(previous_liveness)) {
      // Reset the invalid liveness.
      liveness.out->CopyFrom(previous_liveness);
      invalid_offset = current_offset;
      which_invalid = 1;
      break;
    }

    previous_liveness.CopyFrom(*liveness.in);

    liveness.in->CopyFrom(*liveness.out);
861
    UpdateInLiveness(bytecode, liveness.in, iterator);
862 863 864 865 866 867 868 869

    if (!liveness.in->Equals(previous_liveness)) {
      // Reset the invalid liveness.
      liveness.in->CopyFrom(previous_liveness);
      invalid_offset = current_offset;
      which_invalid = 0;
      break;
    }
870 871

    next_bytecode_in_liveness = liveness.in;
872 873
  }

874 875 876 877 878 879 880 881 882 883 884 885 886 887 888 889 890 891 892 893 894 895 896
  // Ensure that the accumulator is not live when jumping out of a loop, or on
  // the back-edge of a loop.
  for (iterator.GoToStart(); iterator.IsValid() && invalid_offset == -1;
       ++iterator) {
    Bytecode bytecode = iterator.current_bytecode();
    int current_offset = iterator.current_offset();
    int loop_header = GetLoopOffsetFor(current_offset);

    // We only care if we're inside a loop.
    if (loop_header == -1) continue;

    // We only care about jumps.
    if (!Bytecodes::IsJump(bytecode)) continue;

    int jump_target = iterator.GetJumpTargetOffset();

    // If this is a forward jump to somewhere else in the same loop, ignore it.
    if (Bytecodes::IsForwardJump(bytecode) &&
        GetLoopOffsetFor(jump_target) == loop_header) {
      continue;
    }

    // The accumulator must be dead at the start of the target of the jump.
897
    if (liveness_map().GetLiveness(jump_target).in->AccumulatorIsLive()) {
898 899 900 901 902 903
      invalid_offset = jump_target;
      which_invalid = 0;
      break;
    }
  }

904 905 906 907 908 909 910 911
  if (invalid_offset != -1) {
    OFStream of(stderr);
    of << "Invalid liveness:" << std::endl;

    // Dump the bytecode, annotated with the liveness and marking loops.

    int loop_indent = 0;

912
    interpreter::BytecodeArrayIterator forward_iterator(bytecode_array());
913 914
    for (; !forward_iterator.done(); forward_iterator.Advance()) {
      int current_offset = forward_iterator.current_offset();
915 916 917 918
      const BitVector& in_liveness =
          GetInLivenessFor(current_offset)->bit_vector();
      const BitVector& out_liveness =
          GetOutLivenessFor(current_offset)->bit_vector();
919

920 921
      for (int i = 0; i < in_liveness.length(); ++i) {
        of << (in_liveness.Contains(i) ? 'L' : '.');
922 923 924 925
      }

      of << " | ";

926 927
      for (int i = 0; i < out_liveness.length(); ++i) {
        of << (out_liveness.Contains(i) ? 'L' : '.');
928 929 930 931 932 933 934 935 936 937
      }

      of << " : " << current_offset << " : ";

      // Draw loop back edges by indentin everything between loop headers and
      // jump loop instructions.
      if (forward_iterator.current_bytecode() == Bytecode::kJumpLoop) {
        loop_indent--;
      }
      for (int i = 0; i < loop_indent; ++i) {
938
        of << "| ";
939 940
      }
      if (forward_iterator.current_bytecode() == Bytecode::kJumpLoop) {
941
        of << "`-";
942
      } else if (IsLoopHeader(current_offset)) {
943
        of << ".>";
944 945
        loop_indent++;
      }
946 947 948 949 950
      forward_iterator.PrintTo(of);
      if (Bytecodes::IsJump(forward_iterator.current_bytecode())) {
        of << " (@" << forward_iterator.GetJumpTargetOffset() << ")";
      }
      of << std::endl;
951 952 953 954

      if (current_offset == invalid_offset) {
        // Underline the invalid liveness.
        if (which_invalid == 0) {
955
          for (int i = 0; i < in_liveness.length(); ++i) {
956 957
            of << '^';
          }
958 959 960
          for (int i = 0; i < out_liveness.length() + 3; ++i) {
            of << ' ';
          }
961
        } else {
962
          for (int i = 0; i < in_liveness.length() + 3; ++i) {
963 964
            of << ' ';
          }
965
          for (int i = 0; i < out_liveness.length(); ++i) {
966 967 968 969 970 971 972
            of << '^';
          }
        }

        // Make sure to draw the loop indentation marks on this additional line.
        of << " : " << current_offset << " : ";
        for (int i = 0; i < loop_indent; ++i) {
973
          of << "| ";
974 975 976 977 978 979 980 981 982 983 984
        }

        of << std::endl;
      }
    }
  }

  return invalid_offset == -1;
}
#endif

985 986 987
}  // namespace compiler
}  // namespace internal
}  // namespace v8