OLD | NEW |
1 // Copyright 2016 the V8 project authors. All rights reserved. | 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 | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 #include "src/compiler/bytecode-analysis.h" | 5 #include "src/compiler/bytecode-analysis.h" |
6 | 6 |
| 7 #include "src/interpreter/bytecode-array-iterator.h" |
7 #include "src/interpreter/bytecode-array-reverse-iterator.h" | 8 #include "src/interpreter/bytecode-array-reverse-iterator.h" |
8 #include "src/objects-inl.h" | 9 #include "src/objects-inl.h" |
9 | 10 |
10 namespace v8 { | 11 namespace v8 { |
11 namespace internal { | 12 namespace internal { |
12 namespace compiler { | 13 namespace compiler { |
13 | 14 |
| 15 using namespace interpreter; |
| 16 |
14 BytecodeAnalysis::BytecodeAnalysis(Handle<BytecodeArray> bytecode_array, | 17 BytecodeAnalysis::BytecodeAnalysis(Handle<BytecodeArray> bytecode_array, |
15 Zone* zone) | 18 Zone* zone, bool do_liveness_analysis) |
16 : bytecode_array_(bytecode_array), | 19 : bytecode_array_(bytecode_array), |
| 20 do_liveness_analysis_(do_liveness_analysis), |
17 zone_(zone), | 21 zone_(zone), |
18 loop_stack_(zone), | 22 loop_stack_(zone), |
19 end_to_header_(zone), | 23 end_to_header_(zone), |
20 header_to_parent_(zone) {} | 24 header_to_parent_(zone), |
| 25 liveness_map_(bytecode_array->length(), zone) {} |
| 26 |
| 27 namespace { |
| 28 |
| 29 void UpdateInLiveness(Bytecode bytecode, BitVector& in_liveness, |
| 30 const BytecodeArrayAccessor& accessor) { |
| 31 int num_operands = Bytecodes::NumberOfOperands(bytecode); |
| 32 const OperandType* operand_types = Bytecodes::GetOperandTypes(bytecode); |
| 33 AccumulatorUse accumulator_use = Bytecodes::GetAccumulatorUse(bytecode); |
| 34 |
| 35 if (accumulator_use == AccumulatorUse::kWrite) { |
| 36 in_liveness.Remove(in_liveness.length() - 1); |
| 37 } |
| 38 for (int i = 0; i < num_operands; ++i) { |
| 39 switch (operand_types[i]) { |
| 40 case OperandType::kRegOut: { |
| 41 interpreter::Register r = accessor.GetRegisterOperand(i); |
| 42 if (!r.is_parameter()) { |
| 43 in_liveness.Remove(r.index()); |
| 44 } |
| 45 break; |
| 46 } |
| 47 case OperandType::kRegOutPair: { |
| 48 interpreter::Register r = accessor.GetRegisterOperand(i); |
| 49 if (!r.is_parameter()) { |
| 50 DCHECK(!interpreter::Register(r.index() + 1).is_parameter()); |
| 51 in_liveness.Remove(r.index()); |
| 52 in_liveness.Remove(r.index() + 1); |
| 53 } |
| 54 break; |
| 55 } |
| 56 case OperandType::kRegOutTriple: { |
| 57 interpreter::Register r = accessor.GetRegisterOperand(i); |
| 58 if (!r.is_parameter()) { |
| 59 DCHECK(!interpreter::Register(r.index() + 1).is_parameter()); |
| 60 DCHECK(!interpreter::Register(r.index() + 2).is_parameter()); |
| 61 in_liveness.Remove(r.index()); |
| 62 in_liveness.Remove(r.index() + 1); |
| 63 in_liveness.Remove(r.index() + 2); |
| 64 } |
| 65 break; |
| 66 } |
| 67 default: |
| 68 DCHECK(!Bytecodes::IsRegisterOutputOperandType(operand_types[i])); |
| 69 break; |
| 70 } |
| 71 } |
| 72 |
| 73 if (accumulator_use == AccumulatorUse::kRead) { |
| 74 in_liveness.Add(in_liveness.length() - 1); |
| 75 } |
| 76 for (int i = 0; i < num_operands; ++i) { |
| 77 switch (operand_types[i]) { |
| 78 case OperandType::kReg: { |
| 79 interpreter::Register r = accessor.GetRegisterOperand(i); |
| 80 if (!r.is_parameter()) { |
| 81 in_liveness.Add(r.index()); |
| 82 } |
| 83 break; |
| 84 } |
| 85 case OperandType::kRegPair: { |
| 86 interpreter::Register r = accessor.GetRegisterOperand(i); |
| 87 if (!r.is_parameter()) { |
| 88 DCHECK(!interpreter::Register(r.index() + 1).is_parameter()); |
| 89 in_liveness.Add(r.index()); |
| 90 in_liveness.Add(r.index() + 1); |
| 91 } |
| 92 break; |
| 93 } |
| 94 case OperandType::kRegList: { |
| 95 interpreter::Register r = accessor.GetRegisterOperand(i++); |
| 96 uint32_t reg_count = accessor.GetRegisterCountOperand(i); |
| 97 if (!r.is_parameter()) { |
| 98 for (uint32_t j = 0; j < reg_count; ++j) { |
| 99 DCHECK(!interpreter::Register(r.index() + j).is_parameter()); |
| 100 in_liveness.Add(r.index() + j); |
| 101 } |
| 102 } |
| 103 } |
| 104 default: |
| 105 DCHECK(!Bytecodes::IsRegisterInputOperandType(operand_types[i])); |
| 106 break; |
| 107 } |
| 108 } |
| 109 } |
| 110 |
| 111 void UpdateOutLiveness(Bytecode bytecode, BitVector& out_liveness, |
| 112 const BytecodeArrayAccessor& accessor, |
| 113 const BytecodeLivenessMap& liveness_map) { |
| 114 int current_offset = accessor.current_offset(); |
| 115 const Handle<BytecodeArray>& bytecode_array = accessor.bytecode_array(); |
| 116 |
| 117 // Update from jump target (if any). Skip loops, we update these manually in |
| 118 // the liveness iterations. |
| 119 if (Bytecodes::IsForwardJump(bytecode)) { |
| 120 int target_offset = accessor.GetJumpTargetOffset(); |
| 121 out_liveness.Union(*liveness_map.GetInLiveness(target_offset)); |
| 122 } |
| 123 |
| 124 // Update from next bytecode (unless this is an unconditional jump). |
| 125 if (!Bytecodes::IsUnconditionalJump(bytecode)) { |
| 126 int next_offset = current_offset + accessor.current_bytecode_size(); |
| 127 if (next_offset < bytecode_array->length()) { |
| 128 out_liveness.Union(*liveness_map.GetInLiveness(next_offset)); |
| 129 } |
| 130 } |
| 131 |
| 132 // Update from exception handler (if any). |
| 133 if (!interpreter::Bytecodes::IsWithoutExternalSideEffects(bytecode)) { |
| 134 int handler_context; |
| 135 // TODO(leszeks): We should look up this range only once per entry. |
| 136 HandlerTable* table = HandlerTable::cast(bytecode_array->handler_table()); |
| 137 int handler_offset = |
| 138 table->LookupRange(current_offset, &handler_context, nullptr); |
| 139 |
| 140 if (handler_offset != -1) { |
| 141 out_liveness.Union(*liveness_map.GetInLiveness(handler_offset)); |
| 142 out_liveness.Add(handler_context); |
| 143 } |
| 144 } |
| 145 } |
| 146 |
| 147 } // namespace |
21 | 148 |
22 void BytecodeAnalysis::Analyze() { | 149 void BytecodeAnalysis::Analyze() { |
23 loop_stack_.push(-1); | 150 loop_stack_.push(-1); |
24 | 151 |
25 interpreter::BytecodeArrayReverseIterator iterator(bytecode_array(), zone()); | 152 // The last JumpLoop that we haven't done a guaranteed valid liveness pass |
26 while (!iterator.done()) { | 153 // over. See the below wall of text for a more thorough explanation. |
27 interpreter::Bytecode bytecode = iterator.current_bytecode(); | 154 int last_invalid_jumploop_offset = -1; |
28 if (bytecode == interpreter::Bytecode::kJumpLoop) { | 155 |
29 PushLoop(iterator.GetJumpTargetOffset(), iterator.current_offset()); | 156 BytecodeArrayReverseIterator iterator(bytecode_array(), zone()); |
30 } else if (iterator.current_offset() == loop_stack_.top()) { | 157 for (; !iterator.done(); iterator.Advance()) { |
| 158 Bytecode bytecode = iterator.current_bytecode(); |
| 159 int current_offset = iterator.current_offset(); |
| 160 |
| 161 if (bytecode == Bytecode::kJumpLoop) { |
| 162 PushLoop(iterator.GetJumpTargetOffset(), current_offset); |
| 163 |
| 164 // Save the last offset so that we can do another pass later. |
| 165 if (last_invalid_jumploop_offset == -1) { |
| 166 last_invalid_jumploop_offset = current_offset; |
| 167 } |
| 168 } else if (current_offset == loop_stack_.top()) { |
31 loop_stack_.pop(); | 169 loop_stack_.pop(); |
32 } | 170 } |
33 iterator.Advance(); | 171 |
| 172 if (do_liveness_analysis_) { |
| 173 // The liveness vector had bits for the liveness of the registers, and one |
| 174 // more bit for the liveness of the accumulator. |
| 175 Liveness& liveness = liveness_map_.InitializeLiveness( |
| 176 current_offset, bytecode_array()->register_count() + 1, zone()); |
| 177 |
| 178 UpdateOutLiveness(bytecode, *liveness.out, iterator, liveness_map_); |
| 179 liveness.in->CopyFrom(*liveness.out); |
| 180 UpdateInLiveness(bytecode, *liveness.in, iterator); |
| 181 } |
34 } | 182 } |
35 | 183 |
36 DCHECK_EQ(loop_stack_.size(), 1u); | 184 DCHECK_EQ(loop_stack_.size(), 1u); |
37 DCHECK_EQ(loop_stack_.top(), -1); | 185 DCHECK_EQ(loop_stack_.top(), -1); |
| 186 |
| 187 if (!do_liveness_analysis_) return; |
| 188 |
| 189 // At this point, every bytecode has a valid in and out liveness, except for |
| 190 // propagating liveness across back edges (i.e. JumpLoop). Subsequent liveness |
| 191 // analysis iterations can only add additional liveness bits that are pulled |
| 192 // across these back edges. |
| 193 // |
| 194 // Furthermore, a loop header's in-liveness can only change based on any |
| 195 // bytecodes *after* the loop end -- it cannot change as a result of the |
| 196 // JumpLoop liveness being updated, as the only liveness bits than can be |
| 197 // added to the loop body are those of the loop header. |
| 198 // |
| 199 // So, if we know that the liveness of bytecodes after a loop header won't |
| 200 // change (e.g. because there are no loops in them, or we have already ensured |
| 201 // those loops are valid), we can safely update the loop end and pass over the |
| 202 // loop body, and then never have to pass over that loop end again, because we |
| 203 // have shown that its target, the loop header, can't change from the entries |
| 204 // after the loop, and can't change from any loop body pass. |
| 205 // |
| 206 // This means that in a pass, we can iterate backwards over the bytecode |
| 207 // array, process any loops that we encounter, and on subsequent passes we can |
| 208 // skip processing those loops (though we still have to process inner loops). |
| 209 |
| 210 while (last_invalid_jumploop_offset != -1) { |
| 211 // TODO(leszeks): We shouldn't need to iterate here, we should just have a |
| 212 // random access iterator. |
| 213 iterator.Reset(); |
| 214 while (last_invalid_jumploop_offset < iterator.current_offset()) { |
| 215 iterator.Advance(); |
| 216 } |
| 217 last_invalid_jumploop_offset = -1; |
| 218 |
| 219 DCHECK_EQ(iterator.current_bytecode(), Bytecode::kJumpLoop); |
| 220 |
| 221 for (; !iterator.done(); iterator.Advance()) { |
| 222 Bytecode bytecode = iterator.current_bytecode(); |
| 223 if (bytecode != Bytecode::kJumpLoop) { |
| 224 // Skip bytecodes until we hit a JumpLoop. This check isn't needed for |
| 225 // the first loop we see (thanks to saving its offset), but it is for |
| 226 // subsequent ones we want to process on this pass. |
| 227 continue; |
| 228 } |
| 229 |
| 230 int header_offset = iterator.GetJumpTargetOffset(); |
| 231 int end_offset = iterator.current_offset(); |
| 232 |
| 233 Liveness& header_liveness = liveness_map_.GetLiveness(header_offset); |
| 234 Liveness& end_liveness = liveness_map_.GetLiveness(end_offset); |
| 235 |
| 236 if (end_liveness.out->UnionIsChanged(*header_liveness.in)) { |
| 237 // Only update the loop body if the loop end liveness changed. |
| 238 end_liveness.in->CopyFrom(*end_liveness.out); |
| 239 |
| 240 // Advance into the loop body. |
| 241 iterator.Advance(); |
| 242 for (; iterator.current_offset() > header_offset; iterator.Advance()) { |
| 243 bytecode = iterator.current_bytecode(); |
| 244 if (bytecode == Bytecode::kJumpLoop) { |
| 245 // We can't validate this loop at the moment because we can't |
| 246 // guarantee that its header is valid yet. Save it for later. |
| 247 if (last_invalid_jumploop_offset == -1) { |
| 248 last_invalid_jumploop_offset = iterator.current_offset(); |
| 249 } |
| 250 } |
| 251 |
| 252 int current_offset = iterator.current_offset(); |
| 253 Liveness& liveness = liveness_map_.GetLiveness(current_offset); |
| 254 |
| 255 UpdateOutLiveness(bytecode, *liveness.out, iterator, liveness_map_); |
| 256 liveness.in->CopyFrom(*liveness.out); |
| 257 UpdateInLiveness(bytecode, *liveness.in, iterator); |
| 258 } |
| 259 // Now we are at the loop header. Since the in-liveness of the header |
| 260 // can't change, we need only to update the out-liveness. |
| 261 bytecode = iterator.current_bytecode(); |
| 262 UpdateOutLiveness(bytecode, *header_liveness.out, iterator, |
| 263 liveness_map_); |
| 264 } |
| 265 |
| 266 // Keep the iterator going so that we can find other loops. |
| 267 } |
| 268 } |
| 269 |
| 270 DCHECK(LivenessIsValid()); |
38 } | 271 } |
39 | 272 |
40 void BytecodeAnalysis::PushLoop(int loop_header, int loop_end) { | 273 void BytecodeAnalysis::PushLoop(int loop_header, int loop_end) { |
41 DCHECK(loop_header < loop_end); | 274 DCHECK(loop_header < loop_end); |
42 DCHECK(loop_stack_.top() < loop_header); | 275 DCHECK(loop_stack_.top() < loop_header); |
43 DCHECK(end_to_header_.find(loop_end) == end_to_header_.end()); | 276 DCHECK(end_to_header_.find(loop_end) == end_to_header_.end()); |
44 DCHECK(header_to_parent_.find(loop_header) == header_to_parent_.end()); | 277 DCHECK(header_to_parent_.find(loop_header) == header_to_parent_.end()); |
45 | 278 |
46 end_to_header_.insert(ZoneMap<int, int>::value_type(loop_end, loop_header)); | 279 end_to_header_.insert(ZoneMap<int, int>::value_type(loop_end, loop_header)); |
47 header_to_parent_.insert( | 280 header_to_parent_.insert( |
(...skipping 37 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
85 | 318 |
86 return header_to_parent_.upper_bound(offset)->second; | 319 return header_to_parent_.upper_bound(offset)->second; |
87 } | 320 } |
88 | 321 |
89 int BytecodeAnalysis::GetParentLoopFor(int header_offset) const { | 322 int BytecodeAnalysis::GetParentLoopFor(int header_offset) const { |
90 DCHECK(IsLoopHeader(header_offset)); | 323 DCHECK(IsLoopHeader(header_offset)); |
91 | 324 |
92 return header_to_parent_.find(header_offset)->second; | 325 return header_to_parent_.find(header_offset)->second; |
93 } | 326 } |
94 | 327 |
| 328 const BitVector* BytecodeAnalysis::GetInLivenessFor(int offset) const { |
| 329 if (!do_liveness_analysis_) return nullptr; |
| 330 |
| 331 return liveness_map_.GetInLiveness(offset); |
| 332 } |
| 333 |
| 334 const BitVector* BytecodeAnalysis::GetOutLivenessFor(int offset) const { |
| 335 if (!do_liveness_analysis_) return nullptr; |
| 336 |
| 337 return liveness_map_.GetOutLiveness(offset); |
| 338 } |
| 339 |
| 340 std::ostream& BytecodeAnalysis::PrintLivenessTo(std::ostream& os) const { |
| 341 interpreter::BytecodeArrayIterator iterator(bytecode_array()); |
| 342 |
| 343 for (; !iterator.done(); iterator.Advance()) { |
| 344 int current_offset = iterator.current_offset(); |
| 345 |
| 346 const BitVector* in_liveness = GetInLivenessFor(current_offset); |
| 347 const BitVector* out_liveness = GetOutLivenessFor(current_offset); |
| 348 |
| 349 for (int i = 0; i < in_liveness->length(); ++i) { |
| 350 os << (in_liveness->Contains(i) ? "L" : "."); |
| 351 } |
| 352 os << " -> "; |
| 353 |
| 354 for (int i = 0; i < out_liveness->length(); ++i) { |
| 355 os << (out_liveness->Contains(i) ? "L" : "."); |
| 356 } |
| 357 |
| 358 os << " | " << current_offset << ": "; |
| 359 iterator.PrintTo(os) << std::endl; |
| 360 } |
| 361 |
| 362 return os; |
| 363 } |
| 364 |
| 365 #if DEBUG |
| 366 bool BytecodeAnalysis::LivenessIsValid() { |
| 367 BytecodeArrayReverseIterator iterator(bytecode_array(), zone()); |
| 368 |
| 369 BitVector previous_liveness(bytecode_array()->register_count() + 1, zone()); |
| 370 |
| 371 int invalid_offset = -1; |
| 372 int which_invalid = -1; |
| 373 |
| 374 // Ensure that there are no liveness changes if we iterate one more time. |
| 375 for (iterator.Reset(); !iterator.done(); iterator.Advance()) { |
| 376 Bytecode bytecode = iterator.current_bytecode(); |
| 377 |
| 378 int current_offset = iterator.current_offset(); |
| 379 |
| 380 Liveness& liveness = liveness_map_.GetLiveness(current_offset); |
| 381 |
| 382 previous_liveness.CopyFrom(*liveness.out); |
| 383 |
| 384 UpdateOutLiveness(bytecode, *liveness.out, iterator, liveness_map_); |
| 385 // UpdateOutLiveness skips kJumpLoop, so we update it manually. |
| 386 if (bytecode == Bytecode::kJumpLoop) { |
| 387 int target_offset = iterator.GetJumpTargetOffset(); |
| 388 liveness.out->Union(*liveness_map_.GetInLiveness(target_offset)); |
| 389 } |
| 390 |
| 391 if (!liveness.out->Equals(previous_liveness)) { |
| 392 // Reset the invalid liveness. |
| 393 liveness.out->CopyFrom(previous_liveness); |
| 394 invalid_offset = current_offset; |
| 395 which_invalid = 1; |
| 396 break; |
| 397 } |
| 398 |
| 399 previous_liveness.CopyFrom(*liveness.in); |
| 400 |
| 401 liveness.in->CopyFrom(*liveness.out); |
| 402 UpdateInLiveness(bytecode, *liveness.in, iterator); |
| 403 |
| 404 if (!liveness.in->Equals(previous_liveness)) { |
| 405 // Reset the invalid liveness. |
| 406 liveness.in->CopyFrom(previous_liveness); |
| 407 invalid_offset = current_offset; |
| 408 which_invalid = 0; |
| 409 break; |
| 410 } |
| 411 } |
| 412 |
| 413 if (invalid_offset != -1) { |
| 414 OFStream of(stderr); |
| 415 of << "Invalid liveness:" << std::endl; |
| 416 |
| 417 // Dump the bytecode, annotated with the liveness and marking loops. |
| 418 |
| 419 int loop_indent = 0; |
| 420 |
| 421 BytecodeArrayIterator forward_iterator(bytecode_array()); |
| 422 for (; !forward_iterator.done(); forward_iterator.Advance()) { |
| 423 int current_offset = forward_iterator.current_offset(); |
| 424 BitVector* in_liveness = liveness_map_.GetInLiveness(current_offset); |
| 425 BitVector* out_liveness = liveness_map_.GetOutLiveness(current_offset); |
| 426 |
| 427 for (int i = 0; i < in_liveness->length(); ++i) { |
| 428 of << (in_liveness->Contains(i) ? 'L' : '.'); |
| 429 } |
| 430 |
| 431 of << " | "; |
| 432 |
| 433 for (int i = 0; i < out_liveness->length(); ++i) { |
| 434 of << (out_liveness->Contains(i) ? 'L' : '.'); |
| 435 } |
| 436 |
| 437 of << " : " << current_offset << " : "; |
| 438 |
| 439 // Draw loop back edges by indentin everything between loop headers and |
| 440 // jump loop instructions. |
| 441 if (forward_iterator.current_bytecode() == Bytecode::kJumpLoop) { |
| 442 loop_indent--; |
| 443 } |
| 444 for (int i = 0; i < loop_indent; ++i) { |
| 445 of << " | "; |
| 446 } |
| 447 if (forward_iterator.current_bytecode() == Bytecode::kJumpLoop) { |
| 448 of << " `-" << current_offset; |
| 449 } else if (IsLoopHeader(current_offset)) { |
| 450 of << " .>" << current_offset; |
| 451 loop_indent++; |
| 452 } |
| 453 forward_iterator.PrintTo(of) << std::endl; |
| 454 |
| 455 if (current_offset == invalid_offset) { |
| 456 // Underline the invalid liveness. |
| 457 if (which_invalid == 0) { |
| 458 for (int i = 0; i < in_liveness->length(); ++i) { |
| 459 of << '^'; |
| 460 } |
| 461 } else { |
| 462 for (int i = 0; i < in_liveness->length() + 3; ++i) { |
| 463 of << ' '; |
| 464 } |
| 465 for (int i = 0; i < out_liveness->length(); ++i) { |
| 466 of << '^'; |
| 467 } |
| 468 } |
| 469 |
| 470 // Make sure to draw the loop indentation marks on this additional line. |
| 471 of << " : " << current_offset << " : "; |
| 472 for (int i = 0; i < loop_indent; ++i) { |
| 473 of << " | "; |
| 474 } |
| 475 |
| 476 of << std::endl; |
| 477 } |
| 478 } |
| 479 } |
| 480 |
| 481 return invalid_offset == -1; |
| 482 } |
| 483 #endif |
| 484 |
95 } // namespace compiler | 485 } // namespace compiler |
96 } // namespace internal | 486 } // namespace internal |
97 } // namespace v8 | 487 } // namespace v8 |
OLD | NEW |