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