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 61601 : BytecodeLoopAssignments::BytecodeLoopAssignments(int parameter_count,
20 : int register_count, Zone* zone)
21 : : parameter_count_(parameter_count),
22 : bit_vector_(new (zone)
23 123202 : BitVector(parameter_count + register_count, zone)) {}
24 :
25 586812 : void BytecodeLoopAssignments::Add(interpreter::Register r) {
26 586812 : if (r.is_parameter()) {
27 3854 : bit_vector_->Add(r.ToParameterIndex(parameter_count_));
28 : } else {
29 582958 : bit_vector_->Add(parameter_count_ + r.index());
30 : }
31 586812 : }
32 :
33 685 : void BytecodeLoopAssignments::AddList(interpreter::Register r, uint32_t count) {
34 685 : 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 5950 : for (uint32_t i = 0; i < count; i++) {
41 : DCHECK(!interpreter::Register(r.index() + i).is_parameter());
42 11900 : bit_vector_->Add(parameter_count_ + r.index() + i);
43 : }
44 : }
45 685 : }
46 :
47 :
48 0 : void BytecodeLoopAssignments::Union(const BytecodeLoopAssignments& other) {
49 8505 : bit_vector_->Union(*other.bit_vector_);
50 0 : }
51 :
52 348775 : bool BytecodeLoopAssignments::ContainsParameter(int index) const {
53 : DCHECK_GE(index, 0);
54 : DCHECK_LT(index, parameter_count());
55 697550 : return bit_vector_->Contains(index);
56 : }
57 :
58 2966503 : bool BytecodeLoopAssignments::ContainsLocal(int index) const {
59 : DCHECK_GE(index, 0);
60 : DCHECK_LT(index, local_count());
61 5933006 : return bit_vector_->Contains(parameter_count_ + index);
62 : }
63 :
64 504916 : BytecodeAnalysis::BytecodeAnalysis(Handle<BytecodeArray> bytecode_array,
65 : Zone* zone, bool do_liveness_analysis)
66 : : bytecode_array_(bytecode_array),
67 : do_liveness_analysis_(do_liveness_analysis),
68 : zone_(zone),
69 : loop_stack_(zone),
70 : loop_end_index_queue_(zone),
71 : end_to_header_(zone),
72 : header_to_info_(zone),
73 : osr_entry_point_(-1),
74 1514754 : liveness_map_(bytecode_array->length(), zone) {}
75 :
76 : namespace {
77 :
78 18021399 : void UpdateInLiveness(Bytecode bytecode, BytecodeLivenessState& in_liveness,
79 : const interpreter::BytecodeArrayAccessor& accessor) {
80 : int num_operands = Bytecodes::NumberOfOperands(bytecode);
81 : const OperandType* operand_types = Bytecodes::GetOperandTypes(bytecode);
82 :
83 18021399 : if (Bytecodes::WritesAccumulator(bytecode)) {
84 : in_liveness.MarkAccumulatorDead();
85 : }
86 24895410 : for (int i = 0; i < num_operands; ++i) {
87 24895426 : switch (operand_types[i]) {
88 : case OperandType::kRegOut: {
89 5217192 : interpreter::Register r = accessor.GetRegisterOperand(i);
90 5217193 : if (!r.is_parameter()) {
91 : in_liveness.MarkRegisterDead(r.index());
92 : }
93 : break;
94 : }
95 : case OperandType::kRegOutList: {
96 5705 : interpreter::Register r = accessor.GetRegisterOperand(i++);
97 5705 : uint32_t reg_count = accessor.GetRegisterCountOperand(i);
98 5705 : if (!r.is_parameter()) {
99 42566 : for (uint32_t j = 0; j < reg_count; ++j) {
100 : DCHECK(!interpreter::Register(r.index() + j).is_parameter());
101 42566 : in_liveness.MarkRegisterDead(r.index() + j);
102 : }
103 : }
104 : break;
105 : }
106 : case OperandType::kRegOutPair: {
107 397 : interpreter::Register r = accessor.GetRegisterOperand(i);
108 397 : if (!r.is_parameter()) {
109 : DCHECK(!interpreter::Register(r.index() + 1).is_parameter());
110 : in_liveness.MarkRegisterDead(r.index());
111 397 : in_liveness.MarkRegisterDead(r.index() + 1);
112 : }
113 : break;
114 : }
115 : case OperandType::kRegOutTriple: {
116 1964 : interpreter::Register r = accessor.GetRegisterOperand(i);
117 1964 : if (!r.is_parameter()) {
118 : DCHECK(!interpreter::Register(r.index() + 1).is_parameter());
119 : DCHECK(!interpreter::Register(r.index() + 2).is_parameter());
120 : in_liveness.MarkRegisterDead(r.index());
121 1964 : in_liveness.MarkRegisterDead(r.index() + 1);
122 1964 : in_liveness.MarkRegisterDead(r.index() + 2);
123 : }
124 : break;
125 : }
126 : default:
127 : DCHECK(!Bytecodes::IsRegisterOutputOperandType(operand_types[i]));
128 : break;
129 : }
130 : }
131 :
132 18021386 : if (Bytecodes::ReadsAccumulator(bytecode)) {
133 9176042 : in_liveness.MarkAccumulatorLive();
134 : }
135 24563883 : for (int i = 0; i < num_operands; ++i) {
136 24563878 : switch (operand_types[i]) {
137 : case OperandType::kReg: {
138 6078345 : interpreter::Register r = accessor.GetRegisterOperand(i);
139 6078350 : if (!r.is_parameter()) {
140 : in_liveness.MarkRegisterLive(r.index());
141 : }
142 : break;
143 : }
144 : case OperandType::kRegPair: {
145 3716 : interpreter::Register r = accessor.GetRegisterOperand(i);
146 3716 : if (!r.is_parameter()) {
147 : DCHECK(!interpreter::Register(r.index() + 1).is_parameter());
148 : in_liveness.MarkRegisterLive(r.index());
149 3716 : in_liveness.MarkRegisterLive(r.index() + 1);
150 : }
151 : break;
152 : }
153 : case OperandType::kRegList: {
154 337231 : interpreter::Register r = accessor.GetRegisterOperand(i++);
155 337231 : uint32_t reg_count = accessor.GetRegisterCountOperand(i);
156 337231 : if (!r.is_parameter()) {
157 1230562 : for (uint32_t j = 0; j < reg_count; ++j) {
158 : DCHECK(!interpreter::Register(r.index() + j).is_parameter());
159 1230562 : in_liveness.MarkRegisterLive(r.index() + j);
160 : }
161 : }
162 : break;
163 : }
164 : default:
165 : DCHECK(!Bytecodes::IsRegisterInputOperandType(operand_types[i]));
166 : break;
167 : }
168 : }
169 18021396 : }
170 :
171 18077542 : void UpdateOutLiveness(Bytecode bytecode, BytecodeLivenessState& out_liveness,
172 : BytecodeLivenessState* next_bytecode_in_liveness,
173 18077542 : const interpreter::BytecodeArrayAccessor& accessor,
174 : const BytecodeLivenessMap& liveness_map) {
175 : int current_offset = accessor.current_offset();
176 : const Handle<BytecodeArray>& bytecode_array = accessor.bytecode_array();
177 :
178 : // Update from jump target (if any). Skip loops, we update these manually in
179 : // the liveness iterations.
180 18077542 : if (Bytecodes::IsForwardJump(bytecode)) {
181 964585 : int target_offset = accessor.GetJumpTargetOffset();
182 : out_liveness.Union(*liveness_map.GetInLiveness(target_offset));
183 17112957 : } else if (Bytecodes::IsSwitch(bytecode)) {
184 25903 : for (const auto& entry : accessor.GetJumpTableTargetOffsets()) {
185 17835 : out_liveness.Union(*liveness_map.GetInLiveness(entry.target_offset));
186 : }
187 : }
188 :
189 : // Update from next bytecode (unless there isn't one or this is an
190 : // unconditional jump).
191 35652108 : if (next_bytecode_in_liveness != nullptr &&
192 : !Bytecodes::IsUnconditionalJump(bytecode)) {
193 : out_liveness.Union(*next_bytecode_in_liveness);
194 : }
195 :
196 : // Update from exception handler (if any).
197 18077540 : if (!interpreter::Bytecodes::IsWithoutExternalSideEffects(bytecode)) {
198 : int handler_context;
199 : // TODO(leszeks): We should look up this range only once per entry.
200 : HandlerTable* table = HandlerTable::cast(bytecode_array->handler_table());
201 : int handler_offset =
202 7581194 : table->LookupRange(current_offset, &handler_context, nullptr);
203 :
204 7581193 : if (handler_offset != -1) {
205 : bool was_accumulator_live = out_liveness.AccumulatorIsLive();
206 : out_liveness.Union(*liveness_map.GetInLiveness(handler_offset));
207 349590 : out_liveness.MarkRegisterLive(handler_context);
208 349590 : if (!was_accumulator_live) {
209 : // The accumulator is reset to the exception on entry into a handler,
210 : // and so shouldn't be considered live coming out of this bytecode just
211 : // because it's live coming into the handler. So, kill the accumulator
212 : // if the handler is the only thing that made it live.
213 : out_liveness.MarkAccumulatorDead();
214 :
215 : // TODO(leszeks): Ideally the accumulator wouldn't be considered live at
216 : // the start of the handler, but looking up if the current bytecode is
217 : // the start of a handler is not free, so we should only do it if we
218 : // decide it's necessary.
219 : }
220 : }
221 : }
222 18077533 : }
223 :
224 2030219 : void UpdateAssignments(Bytecode bytecode, BytecodeLoopAssignments& assignments,
225 : const interpreter::BytecodeArrayAccessor& accessor) {
226 : int num_operands = Bytecodes::NumberOfOperands(bytecode);
227 : const OperandType* operand_types = Bytecodes::GetOperandTypes(bytecode);
228 :
229 4829224 : for (int i = 0; i < num_operands; ++i) {
230 2799005 : switch (operand_types[i]) {
231 : case OperandType::kRegOut: {
232 586812 : assignments.Add(accessor.GetRegisterOperand(i));
233 586812 : break;
234 : }
235 : case OperandType::kRegOutList: {
236 453 : interpreter::Register r = accessor.GetRegisterOperand(i++);
237 453 : uint32_t reg_count = accessor.GetRegisterCountOperand(i);
238 453 : assignments.AddList(r, reg_count);
239 : break;
240 : }
241 : case OperandType::kRegOutPair: {
242 25 : assignments.AddList(accessor.GetRegisterOperand(i), 2);
243 25 : break;
244 : }
245 : case OperandType::kRegOutTriple: {
246 207 : assignments.AddList(accessor.GetRegisterOperand(i), 3);
247 207 : break;
248 : }
249 : default:
250 : DCHECK(!Bytecodes::IsRegisterOutputOperandType(operand_types[i]));
251 : break;
252 : }
253 : }
254 2030219 : }
255 :
256 : } // namespace
257 :
258 17018050 : void BytecodeAnalysis::Analyze(BailoutId osr_bailout_id) {
259 1009836 : loop_stack_.push({-1, nullptr});
260 :
261 : BytecodeLivenessState* next_bytecode_in_liveness = nullptr;
262 :
263 : int osr_loop_end_offset =
264 504919 : osr_bailout_id.IsNone() ? -1 : osr_bailout_id.ToInt();
265 :
266 504919 : interpreter::BytecodeArrayRandomIterator iterator(bytecode_array(), zone());
267 16648644 : for (iterator.GoToEnd(); iterator.IsValid(); --iterator) {
268 16143720 : Bytecode bytecode = iterator.current_bytecode();
269 16143720 : int current_offset = iterator.current_offset();
270 :
271 16143720 : if (bytecode == Bytecode::kJumpLoop) {
272 : // Every byte up to and including the last byte within the backwards jump
273 : // instruction is considered part of the loop, set loop end accordingly.
274 61601 : int loop_end = current_offset + iterator.current_bytecode_size();
275 61601 : int loop_header = iterator.GetJumpTargetOffset();
276 61601 : PushLoop(loop_header, loop_end);
277 :
278 61601 : if (current_offset == osr_loop_end_offset) {
279 5809 : osr_entry_point_ = loop_header;
280 : } else if (current_offset < osr_loop_end_offset) {
281 : // Check we've found the osr_entry_point if we've gone past the
282 : // osr_loop_end_offset. Note, we are iterating the bytecode in reverse,
283 : // so the less than in the check is correct.
284 : DCHECK_NE(-1, osr_entry_point_);
285 : }
286 :
287 : // Save the index so that we can do another pass later.
288 61601 : if (do_liveness_analysis_) {
289 122432 : loop_end_index_queue_.push_back(iterator.current_index());
290 : }
291 16082119 : } else if (loop_stack_.size() > 1) {
292 : LoopStackEntry& current_loop = loop_stack_.top();
293 2030219 : LoopInfo* current_loop_info = current_loop.loop_info;
294 :
295 : // TODO(leszeks): Ideally, we'd only set values that were assigned in
296 : // the loop *and* are live when the loop exits. However, this requires
297 : // tracking the out-liveness of *all* loop exits, which is not
298 : // information we currently have.
299 2030219 : UpdateAssignments(bytecode, current_loop_info->assignments(), iterator);
300 :
301 2030219 : if (current_offset == current_loop.header_offset) {
302 : loop_stack_.pop();
303 61592 : if (loop_stack_.size() > 1) {
304 : // Propagate inner loop assignments to outer loop.
305 8505 : loop_stack_.top().loop_info->assignments().Union(
306 : current_loop_info->assignments());
307 : }
308 : }
309 : }
310 :
311 16143711 : if (do_liveness_analysis_) {
312 : BytecodeLiveness& liveness = liveness_map_.InitializeLiveness(
313 16008214 : current_offset, bytecode_array()->register_count(), zone());
314 :
315 : UpdateOutLiveness(bytecode, *liveness.out, next_bytecode_in_liveness,
316 16008227 : iterator, liveness_map_);
317 16008225 : liveness.in->CopyFrom(*liveness.out);
318 16008222 : UpdateInLiveness(bytecode, *liveness.in, iterator);
319 :
320 16008221 : next_bytecode_in_liveness = liveness.in;
321 : }
322 : }
323 :
324 : DCHECK_EQ(loop_stack_.size(), 1u);
325 : DCHECK_EQ(loop_stack_.top().header_offset, -1);
326 :
327 1009834 : if (!do_liveness_analysis_) return;
328 :
329 : // At this point, every bytecode has a valid in and out liveness, except for
330 : // propagating liveness across back edges (i.e. JumpLoop). Subsequent liveness
331 : // analysis iterations can only add additional liveness bits that are pulled
332 : // across these back edges.
333 : //
334 : // Furthermore, a loop header's in-liveness can only change based on any
335 : // bytecodes *after* the loop end -- it cannot change as a result of the
336 : // JumpLoop liveness being updated, as the only liveness bits than can be
337 : // added to the loop body are those of the loop header.
338 : //
339 : // So, if we know that the liveness of bytecodes after a loop header won't
340 : // change (e.g. because there are no loops in them, or we have already ensured
341 : // those loops are valid), we can safely update the loop end and pass over the
342 : // loop body, and then never have to pass over that loop end again, because we
343 : // have shown that its target, the loop header, can't change from the entries
344 : // after the loop, and can't change from any loop body pass.
345 : //
346 : // This means that in a pass, we can iterate backwards over the bytecode
347 : // array, process any loops that we encounter, and on subsequent passes we can
348 : // skip processing those loops (though we still have to process inner loops).
349 : //
350 : // Equivalently, we can queue up loop ends from back to front, and pass over
351 : // the loops in that order, as this preserves both the bottom-to-top and
352 : // outer-to-inner requirements.
353 :
354 1067160 : for (int loop_end_index : loop_end_index_queue_) {
355 : iterator.GoToIndex(loop_end_index);
356 :
357 : DCHECK_EQ(iterator.current_bytecode(), Bytecode::kJumpLoop);
358 :
359 61216 : int header_offset = iterator.GetJumpTargetOffset();
360 61216 : int end_offset = iterator.current_offset();
361 :
362 : BytecodeLiveness& header_liveness =
363 61216 : liveness_map_.GetLiveness(header_offset);
364 61216 : BytecodeLiveness& end_liveness = liveness_map_.GetLiveness(end_offset);
365 :
366 122432 : if (!end_liveness.out->UnionIsChanged(*header_liveness.in)) {
367 : // Only update the loop body if the loop end liveness changed.
368 : continue;
369 : }
370 56133 : end_liveness.in->CopyFrom(*end_liveness.out);
371 56133 : next_bytecode_in_liveness = end_liveness.in;
372 :
373 : // Advance into the loop body.
374 : --iterator;
375 2069311 : for (; iterator.current_offset() > header_offset; --iterator) {
376 2013178 : Bytecode bytecode = iterator.current_bytecode();
377 :
378 2013178 : int current_offset = iterator.current_offset();
379 2013178 : BytecodeLiveness& liveness = liveness_map_.GetLiveness(current_offset);
380 :
381 : UpdateOutLiveness(bytecode, *liveness.out, next_bytecode_in_liveness,
382 2013178 : iterator, liveness_map_);
383 2013178 : liveness.in->CopyFrom(*liveness.out);
384 2013178 : UpdateInLiveness(bytecode, *liveness.in, iterator);
385 :
386 2013178 : next_bytecode_in_liveness = liveness.in;
387 : }
388 : // Now we are at the loop header. Since the in-liveness of the header
389 : // can't change, we need only to update the out-liveness.
390 : UpdateOutLiveness(iterator.current_bytecode(), *header_liveness.out,
391 56133 : next_bytecode_in_liveness, iterator, liveness_map_);
392 : }
393 :
394 : DCHECK(LivenessIsValid());
395 : }
396 :
397 61601 : void BytecodeAnalysis::PushLoop(int loop_header, int loop_end) {
398 : DCHECK(loop_header < loop_end);
399 : DCHECK(loop_stack_.top().header_offset < loop_header);
400 : DCHECK(end_to_header_.find(loop_end) == end_to_header_.end());
401 : DCHECK(header_to_info_.find(loop_header) == header_to_info_.end());
402 :
403 61601 : int parent_offset = loop_stack_.top().header_offset;
404 :
405 61601 : end_to_header_.insert({loop_end, loop_header});
406 : auto it = header_to_info_.insert(
407 : {loop_header, LoopInfo(parent_offset, bytecode_array_->parameter_count(),
408 123202 : bytecode_array_->register_count(), zone_)});
409 : // Get the loop info pointer from the output of insert.
410 61601 : LoopInfo* loop_info = &it.first->second;
411 :
412 123202 : loop_stack_.push({loop_header, loop_info});
413 61601 : }
414 :
415 13997804 : bool BytecodeAnalysis::IsLoopHeader(int offset) const {
416 13997805 : return header_to_info_.find(offset) != header_to_info_.end();
417 : }
418 :
419 2061538 : int BytecodeAnalysis::GetLoopOffsetFor(int offset) const {
420 : auto loop_end_to_header = end_to_header_.upper_bound(offset);
421 : // If there is no next end => offset is not in a loop.
422 2061538 : if (loop_end_to_header == end_to_header_.end()) {
423 : return -1;
424 : }
425 : // If the header precedes the offset, this is the loop
426 : //
427 : // .> header <--loop_end_to_header
428 : // |
429 : // | <--offset
430 : // |
431 : // `- end
432 653880 : if (loop_end_to_header->second <= offset) {
433 : return loop_end_to_header->second;
434 : }
435 : // Otherwise there is a (potentially nested) loop after this offset.
436 : //
437 : // <--offset
438 : //
439 : // .> header
440 : // |
441 : // | .> header <--loop_end_to_header
442 : // | |
443 : // | `- end
444 : // |
445 : // `- end
446 : // We just return the parent of the next loop (might be -1).
447 : DCHECK(header_to_info_.upper_bound(offset) != header_to_info_.end());
448 :
449 351647 : return header_to_info_.upper_bound(offset)->second.parent_offset();
450 : }
451 :
452 189439 : const LoopInfo& BytecodeAnalysis::GetLoopInfoFor(int header_offset) const {
453 : DCHECK(IsLoopHeader(header_offset));
454 :
455 189439 : return header_to_info_.find(header_offset)->second;
456 : }
457 :
458 5087174 : const BytecodeLivenessState* BytecodeAnalysis::GetInLivenessFor(
459 : int offset) const {
460 5087174 : if (!do_liveness_analysis_) return nullptr;
461 :
462 10074129 : return liveness_map_.GetInLiveness(offset);
463 : }
464 :
465 3649569 : const BytecodeLivenessState* BytecodeAnalysis::GetOutLivenessFor(
466 : int offset) const {
467 3649569 : if (!do_liveness_analysis_) return nullptr;
468 :
469 7230692 : return liveness_map_.GetOutLiveness(offset);
470 : }
471 :
472 0 : std::ostream& BytecodeAnalysis::PrintLivenessTo(std::ostream& os) const {
473 0 : interpreter::BytecodeArrayIterator iterator(bytecode_array());
474 :
475 0 : for (; !iterator.done(); iterator.Advance()) {
476 0 : int current_offset = iterator.current_offset();
477 :
478 0 : const BitVector& in_liveness =
479 : GetInLivenessFor(current_offset)->bit_vector();
480 0 : const BitVector& out_liveness =
481 : GetOutLivenessFor(current_offset)->bit_vector();
482 :
483 0 : for (int i = 0; i < in_liveness.length(); ++i) {
484 0 : os << (in_liveness.Contains(i) ? "L" : ".");
485 : }
486 0 : os << " -> ";
487 :
488 0 : for (int i = 0; i < out_liveness.length(); ++i) {
489 0 : os << (out_liveness.Contains(i) ? "L" : ".");
490 : }
491 :
492 0 : os << " | " << current_offset << ": ";
493 0 : iterator.PrintTo(os) << std::endl;
494 : }
495 :
496 0 : return os;
497 : }
498 :
499 : #if DEBUG
500 : bool BytecodeAnalysis::LivenessIsValid() {
501 : interpreter::BytecodeArrayRandomIterator iterator(bytecode_array(), zone());
502 :
503 : BytecodeLivenessState previous_liveness(bytecode_array()->register_count(),
504 : zone());
505 :
506 : int invalid_offset = -1;
507 : int which_invalid = -1;
508 :
509 : BytecodeLivenessState* next_bytecode_in_liveness = nullptr;
510 :
511 : // Ensure that there are no liveness changes if we iterate one more time.
512 : for (iterator.GoToEnd(); iterator.IsValid(); --iterator) {
513 : Bytecode bytecode = iterator.current_bytecode();
514 :
515 : int current_offset = iterator.current_offset();
516 :
517 : BytecodeLiveness& liveness = liveness_map_.GetLiveness(current_offset);
518 :
519 : previous_liveness.CopyFrom(*liveness.out);
520 :
521 : UpdateOutLiveness(bytecode, *liveness.out, next_bytecode_in_liveness,
522 : iterator, liveness_map_);
523 : // UpdateOutLiveness skips kJumpLoop, so we update it manually.
524 : if (bytecode == Bytecode::kJumpLoop) {
525 : int target_offset = iterator.GetJumpTargetOffset();
526 : liveness.out->Union(*liveness_map_.GetInLiveness(target_offset));
527 : }
528 :
529 : if (!liveness.out->Equals(previous_liveness)) {
530 : // Reset the invalid liveness.
531 : liveness.out->CopyFrom(previous_liveness);
532 : invalid_offset = current_offset;
533 : which_invalid = 1;
534 : break;
535 : }
536 :
537 : previous_liveness.CopyFrom(*liveness.in);
538 :
539 : liveness.in->CopyFrom(*liveness.out);
540 : UpdateInLiveness(bytecode, *liveness.in, iterator);
541 :
542 : if (!liveness.in->Equals(previous_liveness)) {
543 : // Reset the invalid liveness.
544 : liveness.in->CopyFrom(previous_liveness);
545 : invalid_offset = current_offset;
546 : which_invalid = 0;
547 : break;
548 : }
549 :
550 : next_bytecode_in_liveness = liveness.in;
551 : }
552 :
553 : // Ensure that the accumulator is not live when jumping out of a loop, or on
554 : // the back-edge of a loop.
555 : for (iterator.GoToStart(); iterator.IsValid() && invalid_offset == -1;
556 : ++iterator) {
557 : Bytecode bytecode = iterator.current_bytecode();
558 : int current_offset = iterator.current_offset();
559 : int loop_header = GetLoopOffsetFor(current_offset);
560 :
561 : // We only care if we're inside a loop.
562 : if (loop_header == -1) continue;
563 :
564 : // We only care about jumps.
565 : if (!Bytecodes::IsJump(bytecode)) continue;
566 :
567 : int jump_target = iterator.GetJumpTargetOffset();
568 :
569 : // If this is a forward jump to somewhere else in the same loop, ignore it.
570 : if (Bytecodes::IsForwardJump(bytecode) &&
571 : GetLoopOffsetFor(jump_target) == loop_header) {
572 : continue;
573 : }
574 :
575 : // The accumulator must be dead at the start of the target of the jump.
576 : if (liveness_map_.GetLiveness(jump_target).in->AccumulatorIsLive()) {
577 : invalid_offset = jump_target;
578 : which_invalid = 0;
579 : break;
580 : }
581 : }
582 :
583 : if (invalid_offset != -1) {
584 : OFStream of(stderr);
585 : of << "Invalid liveness:" << std::endl;
586 :
587 : // Dump the bytecode, annotated with the liveness and marking loops.
588 :
589 : int loop_indent = 0;
590 :
591 : interpreter::BytecodeArrayIterator forward_iterator(bytecode_array());
592 : for (; !forward_iterator.done(); forward_iterator.Advance()) {
593 : int current_offset = forward_iterator.current_offset();
594 : const BitVector& in_liveness =
595 : GetInLivenessFor(current_offset)->bit_vector();
596 : const BitVector& out_liveness =
597 : GetOutLivenessFor(current_offset)->bit_vector();
598 :
599 : for (int i = 0; i < in_liveness.length(); ++i) {
600 : of << (in_liveness.Contains(i) ? 'L' : '.');
601 : }
602 :
603 : of << " | ";
604 :
605 : for (int i = 0; i < out_liveness.length(); ++i) {
606 : of << (out_liveness.Contains(i) ? 'L' : '.');
607 : }
608 :
609 : of << " : " << current_offset << " : ";
610 :
611 : // Draw loop back edges by indentin everything between loop headers and
612 : // jump loop instructions.
613 : if (forward_iterator.current_bytecode() == Bytecode::kJumpLoop) {
614 : loop_indent--;
615 : }
616 : for (int i = 0; i < loop_indent; ++i) {
617 : of << "| ";
618 : }
619 : if (forward_iterator.current_bytecode() == Bytecode::kJumpLoop) {
620 : of << "`-";
621 : } else if (IsLoopHeader(current_offset)) {
622 : of << ".>";
623 : loop_indent++;
624 : }
625 : forward_iterator.PrintTo(of);
626 : if (Bytecodes::IsJump(forward_iterator.current_bytecode())) {
627 : of << " (@" << forward_iterator.GetJumpTargetOffset() << ")";
628 : }
629 : of << std::endl;
630 :
631 : if (current_offset == invalid_offset) {
632 : // Underline the invalid liveness.
633 : if (which_invalid == 0) {
634 : for (int i = 0; i < in_liveness.length(); ++i) {
635 : of << '^';
636 : }
637 : for (int i = 0; i < out_liveness.length() + 3; ++i) {
638 : of << ' ';
639 : }
640 : } else {
641 : for (int i = 0; i < in_liveness.length() + 3; ++i) {
642 : of << ' ';
643 : }
644 : for (int i = 0; i < out_liveness.length(); ++i) {
645 : of << '^';
646 : }
647 : }
648 :
649 : // Make sure to draw the loop indentation marks on this additional line.
650 : of << " : " << current_offset << " : ";
651 : for (int i = 0; i < loop_indent; ++i) {
652 : of << "| ";
653 : }
654 :
655 : of << std::endl;
656 : }
657 : }
658 : }
659 :
660 : return invalid_offset == -1;
661 : }
662 : #endif
663 :
664 : } // namespace compiler
665 : } // namespace internal
666 : } // namespace v8
|
