OLD | NEW |
1 // Copyright (c) 2012, the Dart project authors. Please see the AUTHORS file | 1 // Copyright (c) 2012, the Dart project authors. Please see the AUTHORS file |
2 // for details. All rights reserved. Use of this source code is governed by a | 2 // for details. All rights reserved. Use of this source code is governed by a |
3 // BSD-style license that can be found in the LICENSE file. | 3 // BSD-style license that can be found in the LICENSE file. |
4 | 4 |
5 #include "vm/flow_graph_allocator.h" | 5 #include "vm/flow_graph_allocator.h" |
6 | 6 |
7 #include "vm/bit_vector.h" | 7 #include "vm/bit_vector.h" |
8 #include "vm/intermediate_language.h" | 8 #include "vm/intermediate_language.h" |
9 #include "vm/il_printer.h" | 9 #include "vm/il_printer.h" |
10 #include "vm/flow_graph_builder.h" | 10 #include "vm/flow_graph_builder.h" |
(...skipping 10 matching lines...) Expand all Loading... |
21 #define TRACE_ALLOC(m) do { \ | 21 #define TRACE_ALLOC(m) do { \ |
22 if (FLAG_trace_ssa_allocator) OS::Print m ; \ | 22 if (FLAG_trace_ssa_allocator) OS::Print m ; \ |
23 } while (0) | 23 } while (0) |
24 #else | 24 #else |
25 #define TRACE_ALLOC(m) | 25 #define TRACE_ALLOC(m) |
26 #endif | 26 #endif |
27 | 27 |
28 | 28 |
29 static const intptr_t kNoVirtualRegister = -1; | 29 static const intptr_t kNoVirtualRegister = -1; |
30 static const intptr_t kTempVirtualRegister = -2; | 30 static const intptr_t kTempVirtualRegister = -2; |
31 static UseInterval* const kPermanentlyBlocked = | |
32 reinterpret_cast<UseInterval*>(-1); | |
33 static const intptr_t kIllegalPosition = -1; | 31 static const intptr_t kIllegalPosition = -1; |
34 static const intptr_t kMaxPosition = 0x7FFFFFFF; | 32 static const intptr_t kMaxPosition = 0x7FFFFFFF; |
35 | 33 |
36 | 34 |
| 35 static intptr_t MinPosition(intptr_t a, intptr_t b) { |
| 36 return (a < b) ? a : b; |
| 37 } |
| 38 |
| 39 |
| 40 static bool IsParallelMovePosition(intptr_t pos) { |
| 41 return (pos & 1) == 0; |
| 42 } |
| 43 |
| 44 |
| 45 static bool IsInstructionPosition(intptr_t pos) { |
| 46 return (pos & 1) == 1; |
| 47 } |
| 48 |
| 49 |
| 50 static intptr_t ToParallelMove(intptr_t pos) { |
| 51 return (pos & ~1); |
| 52 } |
| 53 |
37 FlowGraphAllocator::FlowGraphAllocator( | 54 FlowGraphAllocator::FlowGraphAllocator( |
38 const GrowableArray<BlockEntryInstr*>& block_order, | 55 const GrowableArray<BlockEntryInstr*>& block_order, |
39 FlowGraphBuilder* builder) | 56 FlowGraphBuilder* builder) |
40 : builder_(builder), | 57 : builder_(builder), |
41 block_order_(block_order), | 58 block_order_(block_order), |
42 postorder_(builder->postorder_block_entries()), | 59 postorder_(builder->postorder_block_entries()), |
43 live_out_(block_order.length()), | 60 live_out_(block_order.length()), |
44 kill_(block_order.length()), | 61 kill_(block_order.length()), |
45 live_in_(block_order.length()), | 62 live_in_(block_order.length()), |
46 vreg_count_(builder->current_ssa_temp_index()), | 63 vreg_count_(builder->current_ssa_temp_index()), |
47 live_ranges_(builder->current_ssa_temp_index()) { | 64 live_ranges_(builder->current_ssa_temp_index()), |
| 65 cpu_regs_(), |
| 66 blocked_cpu_regs_() { |
48 for (intptr_t i = 0; i < vreg_count_; i++) live_ranges_.Add(NULL); | 67 for (intptr_t i = 0; i < vreg_count_; i++) live_ranges_.Add(NULL); |
49 | 68 |
50 for (intptr_t reg = 0; reg < kNumberOfCpuRegisters; reg++) { | 69 blocked_cpu_regs_[CTX] = true; |
51 cpu_regs_[reg] = NULL; | 70 if (TMP != kNoRegister) { |
| 71 blocked_cpu_regs_[TMP] = true; |
52 } | 72 } |
53 | 73 blocked_cpu_regs_[SPREG] = true; |
54 cpu_regs_[CTX] = kPermanentlyBlocked; | 74 blocked_cpu_regs_[FPREG] = true; |
55 if (TMP != kNoRegister) { | |
56 cpu_regs_[TMP] = kPermanentlyBlocked; | |
57 } | |
58 cpu_regs_[SPREG] = kPermanentlyBlocked; | |
59 cpu_regs_[FPREG] = kPermanentlyBlocked; | |
60 } | 75 } |
61 | 76 |
62 | 77 |
63 void FlowGraphAllocator::ComputeInitialSets() { | 78 void FlowGraphAllocator::ComputeInitialSets() { |
64 const intptr_t block_count = postorder_.length(); | 79 const intptr_t block_count = postorder_.length(); |
65 for (intptr_t i = 0; i < block_count; i++) { | 80 for (intptr_t i = 0; i < block_count; i++) { |
66 BlockEntryInstr* block = postorder_[i]; | 81 BlockEntryInstr* block = postorder_[i]; |
67 | 82 |
68 BitVector* kill = kill_[i]; | 83 BitVector* kill = kill_[i]; |
69 BitVector* live_in = live_in_[i]; | 84 BitVector* live_in = live_in_[i]; |
(...skipping 136 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
206 } | 221 } |
207 OS::Print("\n"); | 222 OS::Print("\n"); |
208 | 223 |
209 PrintBitVector(" live out", live_out_[i]); | 224 PrintBitVector(" live out", live_out_[i]); |
210 PrintBitVector(" kill", kill_[i]); | 225 PrintBitVector(" kill", kill_[i]); |
211 PrintBitVector(" live in", live_in_[i]); | 226 PrintBitVector(" live in", live_in_[i]); |
212 } | 227 } |
213 } | 228 } |
214 | 229 |
215 | 230 |
216 void UseInterval::Print() { | 231 void LiveRange::AddUse(intptr_t pos, Location* location_slot) { |
217 OS::Print(" [%d, %d) uses {", start_, end_); | 232 ASSERT((first_use_interval_->start_ <= pos) && |
218 for (UsePosition* use_pos = uses_; | 233 (pos <= first_use_interval_->end_)); |
219 use_pos != NULL && use_pos->pos() <= end(); | |
220 use_pos = use_pos->next()) { | |
221 if (use_pos != uses_) OS::Print(", "); | |
222 OS::Print("%d", use_pos->pos()); | |
223 } | |
224 OS::Print("}\n"); | |
225 } | |
226 | |
227 | |
228 void UseInterval::AddUse(Instruction* instr, | |
229 intptr_t pos, | |
230 Location* location_slot) { | |
231 ASSERT((start_ <= pos) && (pos <= end_)); | |
232 ASSERT((instr == NULL) || (instr->lifetime_position() == pos)); | |
233 if ((uses_ != NULL) && (uses_->pos() == pos)) { | 234 if ((uses_ != NULL) && (uses_->pos() == pos)) { |
234 if ((location_slot == NULL) || (uses_->location_slot() == location_slot)) { | 235 if ((location_slot == NULL) || (uses_->location_slot() == location_slot)) { |
235 return; | 236 return; |
236 } else if ((uses_->location_slot() == NULL) && (instr == NULL)) { | 237 } else if (uses_->location_slot() == NULL) { |
237 uses_->set_location_slot(location_slot); | 238 uses_->set_location_slot(location_slot); |
238 return; | 239 return; |
239 } | 240 } |
240 } | 241 } |
241 uses_ = new UsePosition(instr, pos, uses_, location_slot); | 242 uses_ = new UsePosition(pos, uses_, location_slot); |
242 } | 243 } |
243 | 244 |
244 | 245 |
245 void LiveRange::Print() { | 246 void LiveRange::AddUseInterval(intptr_t start, intptr_t end) { |
246 OS::Print("vreg %d live intervals:\n", vreg_); | 247 ASSERT(start < end); |
247 for (UseInterval* interval = head_; | 248 |
248 interval != NULL; | 249 // Live ranges are being build by visiting instructions in post-order. |
249 interval = interval->next_) { | 250 // This implies that use intervals will be perpended in a monotonically |
250 interval->Print(); | 251 // decreasing order. |
| 252 if (first_use_interval() != NULL) { |
| 253 // If the first use interval and the use interval we are adding |
| 254 // touch then we can just extend the first interval to cover their |
| 255 // union. |
| 256 if (start >= first_use_interval()->start()) { |
| 257 // The only case when we can add intervals with start greater than |
| 258 // start of an already created interval is BlockLocation. |
| 259 ASSERT((start == first_use_interval()->start()) || |
| 260 (vreg() == kNoVirtualRegister)); |
| 261 ASSERT(end <= first_use_interval()->end()); |
| 262 return; |
| 263 } else if (end == first_use_interval()->start()) { |
| 264 first_use_interval()->start_ = start; |
| 265 return; |
| 266 } |
| 267 |
| 268 ASSERT(end < first_use_interval()->start()); |
| 269 } |
| 270 |
| 271 first_use_interval_ = new UseInterval(start, end, first_use_interval_); |
| 272 if (last_use_interval_ == NULL) { |
| 273 ASSERT(first_use_interval_->next() == NULL); |
| 274 last_use_interval_ = first_use_interval_; |
251 } | 275 } |
252 } | 276 } |
253 | 277 |
254 | 278 |
255 void LiveRange::AddUseInterval(intptr_t start, intptr_t end) { | 279 void LiveRange::DefineAt(intptr_t pos) { |
256 if ((head_ != NULL) && (head_->start_ == end)) { | 280 // Live ranges are being build by visiting instructions in post-order. |
257 head_->start_ = start; | 281 // This implies that use intervals will be prepended in a monotonically |
258 return; | 282 // decreasing order. |
| 283 // When we encounter a use of a value inside a block we optimistically |
| 284 // expand the first use interval to cover the block from the start |
| 285 // to the last use in the block and then we shrink it if we encounter |
| 286 // definition of the value inside the same block. |
| 287 if (first_use_interval_ == NULL) { |
| 288 // Definition without a use. |
| 289 first_use_interval_ = new UseInterval(pos, pos + 1, NULL); |
| 290 last_use_interval_ = first_use_interval_; |
| 291 } else { |
| 292 // Shrink the first use interval. It was optimistically expanded to |
| 293 // cover the the block from the start to the last use in the block. |
| 294 ASSERT(first_use_interval_->start_ <= pos); |
| 295 first_use_interval_->start_ = pos; |
259 } | 296 } |
260 | |
261 head_ = new UseInterval(vreg_, start, end, head_); | |
262 } | 297 } |
263 | 298 |
264 | 299 |
265 void LiveRange::DefineAt(Instruction* instr, intptr_t pos, Location* loc) { | |
266 if (head_ != NULL) { | |
267 ASSERT(head_->start_ <= pos); | |
268 head_->start_ = pos; | |
269 } else { | |
270 // Definition without a use. | |
271 head_ = new UseInterval(vreg_, pos, pos + 1, NULL); | |
272 } | |
273 head_->AddUse(instr, pos, loc); | |
274 } | |
275 | |
276 | |
277 // TODO(vegorov): encode use_at_start vs. use_at_end in the location itself? | |
278 void LiveRange::UseAt(Instruction* instr, | |
279 intptr_t def, intptr_t use, | |
280 bool use_at_end, | |
281 Location* loc) { | |
282 if (head_ == NULL || head_->start_ != def) { | |
283 AddUseInterval(def, use + (use_at_end ? 1 : 0)); | |
284 } | |
285 head_->AddUse(instr, use, loc); | |
286 } | |
287 | |
288 | |
289 LiveRange* FlowGraphAllocator::GetLiveRange(intptr_t vreg) { | 300 LiveRange* FlowGraphAllocator::GetLiveRange(intptr_t vreg) { |
290 if (live_ranges_[vreg] == NULL) { | 301 if (live_ranges_[vreg] == NULL) { |
291 live_ranges_[vreg] = new LiveRange(vreg); | 302 live_ranges_[vreg] = new LiveRange(vreg); |
292 } | 303 } |
293 return live_ranges_[vreg]; | 304 return live_ranges_[vreg]; |
294 } | 305 } |
295 | 306 |
296 | 307 |
297 void FlowGraphAllocator::BlockLocation(Location loc, intptr_t pos) { | 308 void FlowGraphAllocator::BlockLocation(Location loc, |
| 309 intptr_t from, |
| 310 intptr_t to) { |
298 ASSERT(loc.IsRegister()); | 311 ASSERT(loc.IsRegister()); |
299 const Register reg = loc.reg(); | 312 const Register reg = loc.reg(); |
300 UseInterval* last = cpu_regs_[reg]; | 313 if (blocked_cpu_regs_[reg]) return; |
301 if (last == kPermanentlyBlocked) return; | 314 if (cpu_regs_[reg].length() == 0) { |
302 if ((last != NULL) && (last->start() == pos)) return; | 315 cpu_regs_[reg].Add(new LiveRange(kNoVirtualRegister)); |
303 cpu_regs_[reg] = new UseInterval(kNoVirtualRegister, pos, pos + 1, last); | 316 } |
| 317 cpu_regs_[reg][0]->AddUseInterval(from, to); |
304 } | 318 } |
305 | 319 |
306 | 320 |
307 void FlowGraphAllocator::Define(Instruction* instr, | 321 void LiveRange::Print() { |
308 intptr_t pos, | 322 OS::Print(" live range v%d [%d, %d)\n", vreg(), Start(), End()); |
309 intptr_t vreg, | 323 UsePosition* use_pos = uses_; |
310 Location* loc) { | 324 for (UseInterval* interval = first_use_interval_; |
311 LiveRange* range = GetLiveRange(vreg); | 325 interval != NULL; |
312 ASSERT(loc != NULL); | 326 interval = interval->next()) { |
313 if (loc->IsRegister()) { | 327 OS::Print(" use interval [%d, %d)\n", |
314 BlockLocation(*loc, pos); | 328 interval->start(), |
315 range->DefineAt(instr, pos + 1, loc); | 329 interval->end()); |
316 } else if (loc->IsUnallocated()) { | 330 while ((use_pos != NULL) && (use_pos->pos() <= interval->end())) { |
317 range->DefineAt(instr, pos, loc); | 331 OS::Print(" use at %d as %s\n", |
318 } else { | 332 use_pos->pos(), |
319 UNREACHABLE(); | 333 (use_pos->location_slot() == NULL) |
| 334 ? "-" : use_pos->location_slot()->Name()); |
| 335 use_pos = use_pos->next(); |
| 336 } |
320 } | 337 } |
321 | 338 |
322 AddToUnallocated(range->head()); | 339 if (next_sibling() != NULL) { |
323 } | 340 next_sibling()->Print(); |
324 | |
325 | |
326 void FlowGraphAllocator::UseValue(Instruction* instr, | |
327 intptr_t def_pos, | |
328 intptr_t use_pos, | |
329 intptr_t vreg, | |
330 Location* loc, | |
331 bool use_at_end) { | |
332 LiveRange* range = GetLiveRange(vreg); | |
333 if (loc == NULL) { | |
334 range->UseAt(NULL, def_pos, use_pos, true, loc); | |
335 } else if (loc->IsRegister()) { | |
336 // We have a fixed use. | |
337 BlockLocation(*loc, use_pos); | |
338 range->UseAt(instr, def_pos, use_pos, false, loc); | |
339 } else if (loc->IsUnallocated()) { | |
340 ASSERT(loc->policy() == Location::kRequiresRegister); | |
341 range->UseAt(use_at_end ? NULL : instr, def_pos, use_pos, use_at_end, loc); | |
342 } | |
343 } | |
344 | |
345 | |
346 static void PrintChain(UseInterval* chain) { | |
347 if (chain == kPermanentlyBlocked) { | |
348 OS::Print(" not for allocation\n"); | |
349 return; | |
350 } | |
351 | |
352 while (chain != NULL) { | |
353 chain->Print(); | |
354 chain = chain->next(); | |
355 } | 341 } |
356 } | 342 } |
357 | 343 |
358 | 344 |
359 void FlowGraphAllocator::PrintLiveRanges() { | 345 void FlowGraphAllocator::PrintLiveRanges() { |
360 for (intptr_t i = 0; i < unallocated_.length(); i++) { | 346 for (intptr_t i = 0; i < unallocated_.length(); i++) { |
361 OS::Print("unallocated chain for vr%d\n", unallocated_[i]->vreg()); | 347 unallocated_[i]->Print(); |
362 PrintChain(unallocated_[i]); | |
363 } | 348 } |
364 | 349 |
365 for (intptr_t reg = 0; reg < kNumberOfCpuRegisters; reg++) { | 350 for (intptr_t reg = 0; reg < kNumberOfCpuRegisters; reg++) { |
366 OS::Print("blocking chain for %s\n", | 351 if (blocked_cpu_regs_[reg]) continue; |
| 352 if (cpu_regs_[reg].length() == 0) continue; |
| 353 |
| 354 ASSERT(cpu_regs_[reg].length() == 1); |
| 355 OS::Print("blocking live range for %s\n", |
367 Location::RegisterLocation(static_cast<Register>(reg)).Name()); | 356 Location::RegisterLocation(static_cast<Register>(reg)).Name()); |
368 PrintChain(cpu_regs_[reg]); | 357 cpu_regs_[reg][0]->Print(); |
369 } | 358 } |
370 } | 359 } |
371 | 360 |
372 | 361 |
373 void FlowGraphAllocator::BuildLiveRanges() { | 362 void FlowGraphAllocator::BuildLiveRanges() { |
374 NumberInstructions(); | 363 NumberInstructions(); |
375 | 364 |
376 const intptr_t block_count = postorder_.length(); | 365 const intptr_t block_count = postorder_.length(); |
377 for (intptr_t i = 0; i < block_count; i++) { | 366 ASSERT(postorder_[block_count - 1]->IsGraphEntry()); |
| 367 for (intptr_t i = 0; i < (block_count - 1); i++) { |
378 BlockEntryInstr* block = postorder_[i]; | 368 BlockEntryInstr* block = postorder_[i]; |
379 | 369 |
380 // For every SSA value that is live out of this block create an interval | 370 // For every SSA value that is live out of this block create an interval |
381 // that covers the hole block. It will be shortened if we encounter a | 371 // that covers the hole block. It will be shortened if we encounter a |
382 // definition of this value in this block. | 372 // definition of this value in this block. |
383 for (BitVector::Iterator it(live_out_[i]); !it.Done(); it.Advance()) { | 373 for (BitVector::Iterator it(live_out_[i]); !it.Done(); it.Advance()) { |
384 LiveRange* range = GetLiveRange(it.Current()); | 374 LiveRange* range = GetLiveRange(it.Current()); |
385 range->AddUseInterval(block->start_pos(), block->end_pos()); | 375 range->AddUseInterval(block->start_pos(), block->end_pos()); |
386 } | 376 } |
387 | 377 |
388 // Position corresponding to the beginning of the last instruction in the | 378 // Connect outgoing phi-moves that were created in NumberInstructions |
389 // block. | 379 // and find last instruction that contributes to liveness. |
390 intptr_t pos = block->end_pos() - 1; | 380 Instruction* current = ConnectOutgoingPhiMoves(block); |
391 Instruction* current = block->last_instruction(); | 381 |
392 | 382 // Now process all instructions in reverse order. |
393 // Goto instructions do not contribute liveness information. | 383 while (current != block) { |
394 GotoInstr* goto_instr = current->AsGoto(); | 384 // Skip parallel moves that we insert while processing instructions. |
395 if (goto_instr != NULL) { | 385 if (!current->IsParallelMove()) { |
| 386 ProcessOneInstruction(block, current); |
| 387 } |
396 current = current->previous(); | 388 current = current->previous(); |
397 // If we have a parallel move here then the successor block must be a | 389 } |
398 // join with phis. The phi inputs contribute uses to each predecessor | 390 |
399 // block (and the phi outputs contribute definitions in the successor | 391 ConnectIncomingPhiMoves(block); |
400 // block). | 392 } |
401 // | 393 } |
402 // We record those uses at the end of the instruction preceding the | 394 |
403 // parallel move. This position is 'pos', because we do not assign | 395 // |
404 // instruction numbers to parallel moves. | 396 // When describing shape of live ranges in comments below we are going to use |
405 ParallelMoveInstr* parallel_move = current->AsParallelMove(); | 397 // the following notation: |
406 if (parallel_move != NULL) { | 398 // |
407 JoinEntryInstr* join = goto_instr->successor(); | 399 // B block entry |
408 ASSERT(join != NULL); | 400 // g goto instruction |
409 | 401 // m parallel move |
410 // Search for the index of the current block in the predecessors of | 402 // i any other instruction |
411 // the join. | 403 // |
412 // TODO(kmillikin): record the predecessor index in the goto when | 404 // - body of a use interval |
413 // building the predecessor list to avoid this search. | 405 // [ start of a use interval |
414 intptr_t pred_idx = join->IndexOfPredecessor(block); | 406 // ) end of a use interval |
415 ASSERT(pred_idx >= 0); | 407 // * use |
416 | 408 // |
417 // Record the corresponding phi input use for each phi. | 409 // For example diagram |
418 ZoneGrowableArray<PhiInstr*>* phis = join->phis(); | 410 // |
419 intptr_t move_idx = 0; | 411 // m i |
420 for (intptr_t phi_idx = 0; phi_idx < phis->length(); phi_idx++) { | 412 // value --*-) |
421 PhiInstr* phi = (*phis)[phi_idx]; | 413 // |
422 if (phi == NULL) continue; | 414 // can be read as: use interval for value starts somewhere before parallel move |
423 | 415 // and extends until currently processed instruction, there is a use of value |
424 Value* val = phi->InputAt(pred_idx); | 416 // at a position of the parallel move. |
425 MoveOperands* move = parallel_move->MoveOperandsAt(move_idx); | 417 // |
426 if (val->IsUse()) { | 418 |
427 const intptr_t virtual_register = | 419 Instruction* FlowGraphAllocator::ConnectOutgoingPhiMoves( |
428 val->AsUse()->definition()->ssa_temp_index(); | 420 BlockEntryInstr* block) { |
429 move->set_src(Location::RequiresRegister()); | 421 Instruction* last = block->last_instruction(); |
430 GetLiveRange( | 422 |
431 virtual_register)->head()->AddUse(NULL, pos, move->src_slot()); | 423 GotoInstr* goto_instr = last->AsGoto(); |
432 } else { | 424 if (goto_instr == NULL) return last; |
433 ASSERT(val->IsConstant()); | 425 |
434 move->set_src(Location::Constant(val->AsConstant()->value())); | 426 // If we have a parallel move here then the successor block must be a |
435 } | 427 // join with phis. The phi inputs contribute uses to each predecessor |
436 move_idx++; | 428 // block (and the phi outputs contribute definitions in the successor |
437 } | 429 // block). |
438 | 430 ParallelMoveInstr* parallel_move = goto_instr->previous()->AsParallelMove(); |
439 // Begin backward iteration with the instruction before the parallel | 431 if (parallel_move == NULL) return goto_instr->previous(); |
440 // move. | 432 |
441 current = current->previous(); | 433 // All uses are recorded at the position of parallel move preceding goto. |
| 434 const intptr_t pos = goto_instr->lifetime_position() - 1; |
| 435 ASSERT((pos >= 0) && IsParallelMovePosition(pos)); |
| 436 |
| 437 JoinEntryInstr* join = goto_instr->successor(); |
| 438 ASSERT(join != NULL); |
| 439 |
| 440 // Search for the index of the current block in the predecessors of |
| 441 // the join. |
| 442 const intptr_t pred_idx = join->IndexOfPredecessor(block); |
| 443 |
| 444 // Record the corresponding phi input use for each phi. |
| 445 ZoneGrowableArray<PhiInstr*>* phis = join->phis(); |
| 446 intptr_t move_idx = 0; |
| 447 for (intptr_t phi_idx = 0; phi_idx < phis->length(); phi_idx++) { |
| 448 PhiInstr* phi = (*phis)[phi_idx]; |
| 449 if (phi == NULL) continue; |
| 450 |
| 451 Value* val = phi->InputAt(pred_idx); |
| 452 MoveOperands* move = parallel_move->MoveOperandsAt(move_idx); |
| 453 if (val->IsUse()) { |
| 454 // Expected shape of live ranges: |
| 455 // |
| 456 // m g |
| 457 // value --* |
| 458 // |
| 459 |
| 460 LiveRange* range = GetLiveRange( |
| 461 val->AsUse()->definition()->ssa_temp_index()); |
| 462 |
| 463 range->AddUseInterval(block->start_pos(), pos); |
| 464 range->AddUse(pos, move->src_slot()); |
| 465 |
| 466 move->set_src(Location::PrefersRegister()); |
| 467 } else { |
| 468 ASSERT(val->IsConstant()); |
| 469 move->set_src(Location::Constant(val->AsConstant()->value())); |
| 470 } |
| 471 move_idx++; |
| 472 } |
| 473 |
| 474 // Begin backward iteration with the instruction before the parallel |
| 475 // move. |
| 476 return parallel_move->previous(); |
| 477 } |
| 478 |
| 479 |
| 480 void FlowGraphAllocator::ConnectIncomingPhiMoves(BlockEntryInstr* block) { |
| 481 // If this block is a join we need to add destinations of phi |
| 482 // resolution moves to phi's live range so that register allocator will |
| 483 // fill them with moves. |
| 484 JoinEntryInstr* join = block->AsJoinEntry(); |
| 485 if (join == NULL) return; |
| 486 |
| 487 // All uses are recorded at the start position in the block. |
| 488 const intptr_t pos = join->start_pos(); |
| 489 |
| 490 ZoneGrowableArray<PhiInstr*>* phis = join->phis(); |
| 491 if (phis != NULL) { |
| 492 intptr_t move_idx = 0; |
| 493 for (intptr_t phi_idx = 0; phi_idx < phis->length(); phi_idx++) { |
| 494 PhiInstr* phi = (*phis)[phi_idx]; |
| 495 if (phi == NULL) continue; |
| 496 |
| 497 const intptr_t vreg = phi->ssa_temp_index(); |
| 498 ASSERT(vreg != -1); |
| 499 |
| 500 // Expected shape of live range: |
| 501 // |
| 502 // B |
| 503 // phi [-------- |
| 504 // |
| 505 LiveRange* range = GetLiveRange(vreg); |
| 506 range->DefineAt(pos); // Shorten live range. |
| 507 |
| 508 for (intptr_t pred_idx = 0; pred_idx < phi->InputCount(); pred_idx++) { |
| 509 BlockEntryInstr* pred = block->PredecessorAt(pred_idx); |
| 510 ASSERT(pred->last_instruction()->IsGoto()); |
| 511 Instruction* move_instr = pred->last_instruction()->previous(); |
| 512 ASSERT(move_instr->IsParallelMove()); |
| 513 |
| 514 MoveOperands* move = |
| 515 move_instr->AsParallelMove()->MoveOperandsAt(move_idx); |
| 516 move->set_dest(Location::PrefersRegister()); |
| 517 range->AddUse(pos, move->dest_slot()); |
442 } | 518 } |
443 } | 519 |
444 | 520 // All phi resolution moves are connected. Phi's live range is |
445 // Now process all instructions in reverse order. | 521 // complete. |
446 --pos; // 'pos' is now the start position for the current instruction. | 522 AddToUnallocated(range); |
447 while (current != block) { | 523 |
448 LocationSummary* locs = current->locs(); | 524 move_idx++; |
449 | 525 } |
450 const bool output_same_as_first_input = | 526 } |
451 locs->out().IsUnallocated() && | 527 } |
452 locs->out().policy() == Location::kSameAsFirstInput; | 528 |
453 | 529 |
454 // TODO(vegorov): number of inputs should match number of input locations. | 530 // Create and update live ranges corresponding to instruction's inputs, |
455 // TODO(vegorov): generic support for writable registers? | 531 // temporaries and output. |
456 for (intptr_t j = 0; j < current->InputCount(); j++) { | 532 void FlowGraphAllocator::ProcessOneInstruction(BlockEntryInstr* block, |
457 Value* input = current->InputAt(j); | 533 Instruction* current) { |
458 if (input->IsUse()) { | 534 const intptr_t pos = current->lifetime_position(); |
459 const intptr_t use = input->AsUse()->definition()->ssa_temp_index(); | 535 ASSERT(IsInstructionPosition(pos)); |
460 | 536 |
461 Location* in_ref = (j < locs->input_count()) ? | 537 LocationSummary* locs = current->locs(); |
462 locs->in_slot(j) : NULL; | 538 |
463 const bool use_at_end = (j > 0) || (in_ref == NULL) || | 539 // TODO(vegorov): number of inputs must match number of input locations. |
464 !output_same_as_first_input; | 540 if (locs->input_count() != current->InputCount()) { |
465 UseValue(current, block->start_pos(), pos, use, in_ref, use_at_end); | 541 builder_->Bailout("ssa allocator: number of input locations mismatch"); |
466 } | 542 } |
| 543 |
| 544 const bool output_same_as_first_input = |
| 545 locs->out().IsUnallocated() && |
| 546 (locs->out().policy() == Location::kSameAsFirstInput); |
| 547 |
| 548 // Add uses from the deoptimization environment. |
| 549 if (current->env() != NULL) { |
| 550 // Any value mentioned in the deoptimization environment should survive |
| 551 // until the end of instruction but it does not need to be in the register. |
| 552 // Expected shape of live range: |
| 553 // |
| 554 // m i m |
| 555 // value -----*--) |
| 556 // |
| 557 |
| 558 Environment* env = current->env(); |
| 559 const GrowableArray<Value*>& values = env->values(); |
| 560 |
| 561 for (intptr_t j = 0; j < values.length(); j++) { |
| 562 Value* val = values[j]; |
| 563 if (val->IsUse()) { |
| 564 env->AddLocation(Location::Any()); |
| 565 const intptr_t vreg = val->AsUse()->definition()->ssa_temp_index(); |
| 566 |
| 567 LiveRange* range = GetLiveRange(vreg); |
| 568 range->AddUseInterval(block->start_pos(), pos + 1); |
| 569 range->AddUse(pos, env->LocationSlotAt(j)); |
| 570 } else { |
| 571 ASSERT(val->IsConstant()); |
| 572 env->AddLocation(Location::NoLocation()); |
467 } | 573 } |
468 | 574 } |
469 // Add uses from the deoptimization environment. | 575 } |
470 // TODO(vegorov): these uses should _not_ require register but for now | 576 |
471 // they do because we don't support spilling at all. | 577 // Process inputs. |
472 if (current->env() != NULL) { | 578 // Skip the first input if output is specified with kSameAsFirstInput policy, |
473 Environment* env = current->env(); | 579 // they will be processed together at the very end. |
474 const GrowableArray<Value*>& values = env->values(); | 580 for (intptr_t j = output_same_as_first_input ? 1 : 0; |
475 | 581 j < current->InputCount(); |
476 for (intptr_t j = 0; j < values.length(); j++) { | 582 j++) { |
477 Value* val = values[j]; | 583 Value* input = current->InputAt(j); |
478 if (val->IsUse()) { | 584 ASSERT(input->IsUse()); // Can not be a constant currently. |
479 env->AddLocation(Location::RequiresRegister()); | 585 |
480 const intptr_t use = val->AsUse()->definition()->ssa_temp_index(); | 586 const intptr_t vreg = input->AsUse()->definition()->ssa_temp_index(); |
481 UseValue(current, | 587 LiveRange* range = GetLiveRange(vreg); |
482 block->start_pos(), | 588 |
483 pos, | 589 Location* in_ref = locs->in_slot(j); |
484 use, | 590 |
485 env->LocationSlotAt(j), | 591 if (in_ref->IsRegister()) { |
486 true); | 592 // Input is expected in a fixed register. Expected shape of |
487 } else { | 593 // live ranges: |
488 env->AddLocation(Location::NoLocation()); | 594 // |
489 } | 595 // m i m |
490 } | 596 // value --* |
491 } | 597 // register [-----) |
492 | 598 // |
493 // Process temps. | 599 MoveOperands* move = |
494 for (intptr_t j = 0; j < locs->temp_count(); j++) { | 600 AddMoveAt(pos - 1, *in_ref, Location::PrefersRegister()); |
495 Location temp = locs->temp(j); | 601 BlockLocation(*in_ref, pos - 1, pos + 1); |
496 if (temp.IsRegister()) { | 602 range->AddUseInterval(block->start_pos(), pos - 1); |
497 BlockLocation(temp, pos); | 603 range->AddUse(pos - 1, move->src_slot()); |
498 } else if (temp.IsUnallocated()) { | 604 } else { |
499 UseInterval* temp_interval = new UseInterval( | 605 // Normal unallocated input. Expected shape of |
500 kTempVirtualRegister, pos, pos + 1, NULL); | 606 // live ranges: |
501 temp_interval->AddUse(NULL, pos, locs->temp_slot(j)); | 607 // |
502 AddToUnallocated(temp_interval); | 608 // m i m |
503 } else { | 609 // value -----*--) |
504 UNREACHABLE(); | 610 // |
505 } | 611 ASSERT(in_ref->IsUnallocated()); |
506 } | 612 range->AddUseInterval(block->start_pos(), pos + 1); |
507 | 613 range->AddUse(pos, in_ref); |
508 // Block all allocatable registers for calls. | 614 } |
509 if (locs->is_call()) { | 615 } |
510 for (intptr_t reg = 0; reg < kNumberOfCpuRegisters; reg++) { | 616 |
511 BlockLocation(Location::RegisterLocation(static_cast<Register>(reg)), | 617 // Process temps. |
512 pos); | 618 for (intptr_t j = 0; j < locs->temp_count(); j++) { |
513 } | 619 // Expected shape of live range: |
514 } | 620 // |
515 | 621 // m i m |
516 if (locs->out().IsRegister()) { | 622 // [--) |
517 builder_->Bailout("ssa allocator: fixed outputs are not supported"); | 623 // |
518 } | 624 |
519 | 625 Location temp = locs->temp(j); |
520 Definition* def = current->AsDefinition(); | 626 if (temp.IsRegister()) { |
521 if ((def != NULL) && (def->ssa_temp_index() >= 0)) { | 627 BlockLocation(temp, pos, pos + 1); |
522 Define(output_same_as_first_input ? current : NULL, | 628 } else if (temp.IsUnallocated()) { |
523 pos, | 629 LiveRange* range = new LiveRange(kTempVirtualRegister); |
524 def->ssa_temp_index(), | 630 range->AddUseInterval(pos, pos + 1); |
525 locs->out_slot()); | 631 range->AddUse(pos, locs->temp_slot(j)); |
526 } | 632 AddToUnallocated(range); |
527 | 633 } else { |
528 current = current->previous(); | 634 UNREACHABLE(); |
529 pos -= 2; | 635 } |
530 } | 636 } |
531 | 637 |
532 // If this block is a join we need to add destinations of phi | 638 // Block all allocatable registers for calls. |
533 // resolution moves to phi's live range so that register allocator will | 639 if (locs->is_call()) { |
534 // fill them with moves. | 640 // Expected shape of live range: |
535 JoinEntryInstr* join = block->AsJoinEntry(); | 641 // |
536 if (join != NULL) { | 642 // m i m |
537 ZoneGrowableArray<PhiInstr*>* phis = join->phis(); | 643 // [--) |
538 if (phis != NULL) { | 644 // |
539 intptr_t move_idx = 0; | 645 |
540 for (intptr_t j = 0; j < phis->length(); j++) { | 646 for (intptr_t reg = 0; reg < kNumberOfCpuRegisters; reg++) { |
541 PhiInstr* phi = (*phis)[j]; | 647 BlockLocation(Location::RegisterLocation(static_cast<Register>(reg)), |
542 if (phi == NULL) continue; | 648 pos, |
543 | 649 pos + 1); |
544 const intptr_t virtual_register = phi->ssa_temp_index(); | 650 } |
545 ASSERT(virtual_register != -1); | 651 |
546 | 652 #ifdef DEBUG |
547 LiveRange* range = GetLiveRange(virtual_register); | 653 // Verify that temps, inputs and output were specified as fixed |
548 range->DefineAt(NULL, pos, NULL); | 654 // locations. Every register is blocked now so attempt to |
549 UseInterval* interval = GetLiveRange(virtual_register)->head(); | 655 // allocate will not succeed. |
550 | 656 for (intptr_t j = 0; j < locs->temp_count(); j++) { |
551 for (intptr_t k = 0; k < phi->InputCount(); k++) { | 657 ASSERT(!locs->temp(j).IsUnallocated()); |
552 BlockEntryInstr* pred = block->PredecessorAt(k); | 658 } |
553 ASSERT(pred->last_instruction()->IsGoto()); | 659 |
554 Instruction* move_instr = pred->last_instruction()->previous(); | 660 for (intptr_t j = 0; j < locs->input_count(); j++) { |
555 ParallelMoveInstr* pmove = move_instr->AsParallelMove(); | 661 ASSERT(!locs->in(j).IsUnallocated()); |
556 ASSERT(pmove != NULL); | 662 } |
557 | 663 |
558 MoveOperands* move_operands = pmove->MoveOperandsAt(move_idx); | 664 ASSERT(!locs->out().IsUnallocated()); |
559 move_operands->set_dest(Location::RequiresRegister()); | 665 #endif |
560 interval->AddUse(NULL, pos, move_operands->dest_slot()); | 666 } |
561 } | 667 |
562 | 668 Definition* def = current->AsDefinition(); |
563 // All phi resolution moves are connected. Phi's live range is | 669 if (def == NULL) { |
564 // complete. | 670 ASSERT(locs->out().IsInvalid()); |
565 AddToUnallocated(interval); | 671 return; |
566 | 672 } |
567 move_idx++; | 673 |
568 } | 674 if (locs->out().IsInvalid()) { |
569 } | 675 ASSERT(def->ssa_temp_index() < 0); |
570 } | 676 return; |
571 } | 677 } |
572 } | 678 |
573 | 679 // We might have a definition without use. We do not assign SSA index to |
574 | 680 // such definitions. |
| 681 LiveRange* range = (def->ssa_temp_index() >= 0) ? |
| 682 GetLiveRange(def->ssa_temp_index()) : |
| 683 new LiveRange(kTempVirtualRegister); |
| 684 Location* out = locs->out_slot(); |
| 685 |
| 686 // Process output and finalize its liverange. |
| 687 if (out->IsRegister()) { |
| 688 // Fixed output location. Expected shape of live range: |
| 689 // |
| 690 // m i m |
| 691 // register [--) |
| 692 // output [------- |
| 693 // |
| 694 BlockLocation(*out, pos, pos + 1); |
| 695 |
| 696 if (range->vreg() == kTempVirtualRegister) return; |
| 697 |
| 698 // We need to emit move connecting fixed register with another location |
| 699 // that will be allocated for this output's live range. |
| 700 // Special case: fixed output followed by a fixed input last use. |
| 701 UsePosition* use = range->first_use(); |
| 702 if (use->pos() == (pos + 1)) { |
| 703 // We have a use position on the parallel move. |
| 704 ASSERT(use->location_slot()->IsUnallocated()); |
| 705 *(use->location_slot()) = *out; |
| 706 |
| 707 // Remove first use. It was allocated. |
| 708 range->set_first_use(range->first_use()->next()); |
| 709 } |
| 710 |
| 711 // Shorten live range to the point of definition, this might make the range |
| 712 // empty (if the only use immediately follows). If range is not empty add |
| 713 // move from a fixed register to an unallocated location. |
| 714 range->DefineAt(pos + 1); |
| 715 if (range->Start() == range->End()) return; |
| 716 |
| 717 MoveOperands* move = AddMoveAt(pos + 1, Location::PrefersRegister(), *out); |
| 718 range->AddUse(pos + 1, move->dest_slot()); |
| 719 } else if (output_same_as_first_input) { |
| 720 // Output register will contain a value of the first input at instruction's |
| 721 // start. Expected shape of live ranges: |
| 722 // |
| 723 // m i m |
| 724 // input #0 --* |
| 725 // output [--*---- |
| 726 // |
| 727 ASSERT(locs->in_slot(0)->Equals(Location::RequiresRegister())); |
| 728 |
| 729 // Create move that will copy value between input and output. |
| 730 locs->set_out(Location::RequiresRegister()); |
| 731 MoveOperands* move = AddMoveAt(pos - 1, |
| 732 Location::RequiresRegister(), |
| 733 Location::PrefersRegister()); |
| 734 |
| 735 // Add uses to the live range of the input. |
| 736 Value* input = current->InputAt(0); |
| 737 ASSERT(input->IsUse()); // Can not be a constant currently. |
| 738 LiveRange* input_range = GetLiveRange( |
| 739 input->AsUse()->definition()->ssa_temp_index()); |
| 740 input_range->AddUseInterval(block->start_pos(), pos - 1); |
| 741 input_range->AddUse(pos - 1, move->src_slot()); |
| 742 |
| 743 // Shorten output live range to the point of definition and add both input |
| 744 // and output uses slots to be filled by allocator. |
| 745 range->DefineAt(pos - 1); |
| 746 range->AddUse(pos - 1, out); |
| 747 range->AddUse(pos - 1, move->dest_slot()); |
| 748 range->AddUse(pos, locs->in_slot(0)); |
| 749 } else { |
| 750 // Normal unallocated location that requires a register. Expected shape of |
| 751 // live range: |
| 752 // |
| 753 // m i m |
| 754 // output [------- |
| 755 // |
| 756 ASSERT(out->IsUnallocated() && |
| 757 (out->policy() == Location::kRequiresRegister)); |
| 758 |
| 759 // Shorten live range to the point of definition and add use to be filled by |
| 760 // allocator. |
| 761 range->DefineAt(pos); |
| 762 range->AddUse(pos, out); |
| 763 } |
| 764 |
| 765 AddToUnallocated(range); |
| 766 } |
| 767 |
| 768 |
| 769 static ParallelMoveInstr* CreateParallelMoveBefore(Instruction* instr, |
| 770 intptr_t pos) { |
| 771 Instruction* prev = instr->previous(); |
| 772 ParallelMoveInstr* move = prev->AsParallelMove(); |
| 773 if ((move == NULL) || (move->lifetime_position() != pos)) { |
| 774 move = new ParallelMoveInstr(); |
| 775 move->set_next(prev->next()); |
| 776 prev->set_next(move); |
| 777 move->next()->set_previous(move); |
| 778 move->set_previous(prev); |
| 779 move->set_lifetime_position(pos); |
| 780 } |
| 781 return move; |
| 782 } |
| 783 |
| 784 |
| 785 static ParallelMoveInstr* CreateParallelMoveAfter(Instruction* instr, |
| 786 intptr_t pos) { |
| 787 Instruction* next = instr->next(); |
| 788 if (next->IsParallelMove() && (next->lifetime_position() == pos)) { |
| 789 return next->AsParallelMove(); |
| 790 } |
| 791 return CreateParallelMoveBefore(next, pos); |
| 792 } |
| 793 |
| 794 |
575 // Linearize the control flow graph. The chosen order will be used by the | 795 // Linearize the control flow graph. The chosen order will be used by the |
576 // linear-scan register allocator. Number most instructions with a pair of | 796 // linear-scan register allocator. Number most instructions with a pair of |
577 // numbers representing lifetime positions. Introduce explicit parallel | 797 // numbers representing lifetime positions. Introduce explicit parallel |
578 // move instructions in the predecessors of join nodes. The moves are used | 798 // move instructions in the predecessors of join nodes. The moves are used |
579 // for phi resolution. | 799 // for phi resolution. |
580 void FlowGraphAllocator::NumberInstructions() { | 800 void FlowGraphAllocator::NumberInstructions() { |
581 intptr_t pos = 0; | 801 intptr_t pos = 0; |
582 | 802 |
583 // The basic block order is reverse postorder. | 803 // The basic block order is reverse postorder. |
584 const intptr_t block_count = postorder_.length(); | 804 const intptr_t block_count = postorder_.length(); |
585 for (intptr_t i = block_count - 1; i >= 0; i--) { | 805 for (intptr_t i = block_count - 1; i >= 0; i--) { |
586 BlockEntryInstr* block = postorder_[i]; | 806 BlockEntryInstr* block = postorder_[i]; |
| 807 |
| 808 instructions_.Add(block); |
587 block->set_start_pos(pos); | 809 block->set_start_pos(pos); |
588 block->set_lifetime_position(pos); | 810 block->set_lifetime_position(pos + 1); |
589 pos += 2; | 811 pos += 2; |
| 812 |
590 for (ForwardInstructionIterator it(block); !it.Done(); it.Advance()) { | 813 for (ForwardInstructionIterator it(block); !it.Done(); it.Advance()) { |
591 Instruction* current = it.Current(); | 814 Instruction* current = it.Current(); |
592 // Do not assign numbers to parallel moves or goto instructions. | 815 // Do not assign numbers to parallel move instructions. |
593 if (!current->IsParallelMove() && !current->IsGoto()) { | 816 if (!current->IsParallelMove()) { |
594 current->set_lifetime_position(pos); | 817 instructions_.Add(current); |
| 818 current->set_lifetime_position(pos + 1); |
595 pos += 2; | 819 pos += 2; |
596 } | 820 } |
597 } | 821 } |
598 block->set_end_pos(pos); | 822 block->set_end_pos(pos); |
599 | 823 |
600 // For join entry predecessors create phi resolution moves if | 824 // For join entry predecessors create phi resolution moves if |
601 // necessary. They will be populated by the register allocator. | 825 // necessary. They will be populated by the register allocator. |
602 JoinEntryInstr* join = block->AsJoinEntry(); | 826 JoinEntryInstr* join = block->AsJoinEntry(); |
603 if ((join != NULL) && (join->phi_count() > 0)) { | 827 if ((join != NULL) && (join->phi_count() > 0)) { |
604 const intptr_t phi_count = join->phi_count(); | 828 const intptr_t phi_count = join->phi_count(); |
605 for (intptr_t i = 0; i < block->PredecessorCount(); i++) { | 829 for (intptr_t i = 0; i < block->PredecessorCount(); i++) { |
606 ParallelMoveInstr* move = new ParallelMoveInstr(); | 830 // Insert the move between the last two instructions of the |
| 831 // predecessor block (all such blocks have at least two instructions: |
| 832 // the block entry and goto instructions.) |
| 833 Instruction* last = block->PredecessorAt(i)->last_instruction(); |
| 834 ParallelMoveInstr* move = |
| 835 CreateParallelMoveBefore(last, last->lifetime_position() - 1); |
| 836 |
607 // Populate the ParallelMove with empty moves. | 837 // Populate the ParallelMove with empty moves. |
608 for (intptr_t j = 0; j < phi_count; j++) { | 838 for (intptr_t j = 0; j < phi_count; j++) { |
609 move->AddMove(Location::NoLocation(), Location::NoLocation()); | 839 move->AddMove(Location::NoLocation(), Location::NoLocation()); |
610 } | 840 } |
611 | |
612 // Insert the move between the last two instructions of the | |
613 // predecessor block (all such blocks have at least two instructions: | |
614 // the block entry and goto instructions.) | |
615 BlockEntryInstr* pred = block->PredecessorAt(i); | |
616 Instruction* next = pred->last_instruction(); | |
617 Instruction* previous = next->previous(); | |
618 ASSERT(next->IsGoto()); | |
619 ASSERT(!previous->IsParallelMove()); | |
620 previous->set_next(move); | |
621 move->set_previous(previous); | |
622 move->set_next(next); | |
623 next->set_previous(move); | |
624 } | 841 } |
625 } | 842 } |
626 } | 843 } |
627 } | 844 } |
628 | 845 |
629 | 846 |
| 847 Instruction* FlowGraphAllocator::InstructionAt(intptr_t pos) const { |
| 848 return instructions_[pos / 2]; |
| 849 } |
| 850 |
| 851 |
| 852 bool FlowGraphAllocator::IsBlockEntry(intptr_t pos) const { |
| 853 return InstructionAt(pos)->IsBlockEntry(); |
| 854 } |
| 855 |
| 856 |
| 857 static UsePosition* FirstUseAfter(UsePosition* use, intptr_t after) { |
| 858 while ((use != NULL) && (use->pos() < after)) { |
| 859 use = use->next(); |
| 860 } |
| 861 return use; |
| 862 } |
| 863 |
| 864 |
| 865 Location AllocationFinger::FirstHint() { |
| 866 UsePosition* use = first_hinted_use_; |
| 867 |
| 868 while (use != NULL) { |
| 869 if (use->HasHint()) return use->hint(); |
| 870 use = use->next(); |
| 871 } |
| 872 |
| 873 return Location::NoLocation(); |
| 874 } |
| 875 |
| 876 |
| 877 UsePosition* AllocationFinger::FirstRegisterUse(intptr_t after) { |
| 878 for (UsePosition* use = FirstUseAfter(first_register_use_, after); |
| 879 use != NULL; |
| 880 use = use->next()) { |
| 881 Location* loc = use->location_slot(); |
| 882 if ((loc != NULL) && |
| 883 loc->IsUnallocated() && |
| 884 (loc->policy() == Location::kRequiresRegister)) { |
| 885 first_register_use_ = use; |
| 886 return use; |
| 887 } |
| 888 } |
| 889 return NULL; |
| 890 } |
| 891 |
| 892 |
| 893 UsePosition* AllocationFinger::FirstRegisterBeneficialUse(intptr_t after) { |
| 894 for (UsePosition* use = FirstUseAfter(first_register_beneficial_use_, after); |
| 895 use != NULL; |
| 896 use = use->next()) { |
| 897 Location* loc = use->location_slot(); |
| 898 if ((loc != NULL) && |
| 899 (loc->IsRegister() || |
| 900 (loc->IsUnallocated() && loc->IsRegisterBeneficial()))) { |
| 901 first_register_beneficial_use_ = use; |
| 902 return use; |
| 903 } |
| 904 } |
| 905 return NULL; |
| 906 } |
| 907 |
| 908 |
630 intptr_t UseInterval::Intersect(UseInterval* other) { | 909 intptr_t UseInterval::Intersect(UseInterval* other) { |
631 if (this->start() <= other->start()) { | 910 if (this->start() <= other->start()) { |
632 if (other->start() < this->end()) return other->start(); | 911 if (other->start() < this->end()) return other->start(); |
633 } else if (this->start() < other->end()) { | 912 } else if (this->start() < other->end()) { |
634 return this->start(); | 913 return this->start(); |
635 } | 914 } |
636 return kIllegalPosition; | 915 return kIllegalPosition; |
637 } | 916 } |
638 | 917 |
639 | 918 |
640 static intptr_t FirstIntersection(UseInterval* a, UseInterval* u) { | 919 static intptr_t FirstIntersection(UseInterval* a, UseInterval* u) { |
641 while (a != NULL && u != NULL) { | 920 while (a != NULL && u != NULL) { |
642 const intptr_t pos = a->Intersect(u); | 921 const intptr_t pos = a->Intersect(u); |
643 if (pos != kIllegalPosition) return pos; | 922 if (pos != kIllegalPosition) return pos; |
644 | 923 |
645 if (a->start() < u->start()) { | 924 if (a->start() < u->start()) { |
646 a = a->next_allocated(); | 925 a = a->next(); |
647 } else { | 926 } else { |
648 u = u->next(); | 927 u = u->next(); |
649 } | 928 } |
650 } | 929 } |
651 | 930 |
652 return kMaxPosition; | 931 return kMaxPosition; |
653 } | 932 } |
654 | 933 |
655 | 934 |
656 static Location LookAheadForHint(UseInterval* interval) { | 935 LiveRange* LiveRange::MakeTemp(intptr_t pos, Location* location_slot) { |
657 UsePosition* use = interval->first_use(); | 936 UNREACHABLE(); |
658 | 937 return NULL; |
659 while (use != NULL) { | |
660 if (use->HasHint()) return use->hint(); | |
661 use = use->next(); | |
662 } | |
663 | |
664 return Location::NoLocation(); | |
665 } | 938 } |
666 | 939 |
667 | 940 |
668 bool FlowGraphAllocator::AllocateFreeRegister(UseInterval* unallocated) { | 941 LiveRange* LiveRange::SplitAt(intptr_t split_pos) { |
| 942 if (Start() == split_pos) return this; |
| 943 |
| 944 // Ranges can only be connected by parallel moves. |
| 945 split_pos = ToParallelMove(split_pos); |
| 946 |
| 947 UseInterval* interval = finger_.first_pending_use_interval(); |
| 948 ASSERT(interval->start() < split_pos); |
| 949 |
| 950 // Corner case. We need to start over to find previous interval. |
| 951 if (interval->start() == split_pos) interval = first_use_interval_; |
| 952 |
| 953 UseInterval* last_before_split = NULL; |
| 954 while (interval->end() <= split_pos) { |
| 955 last_before_split = interval; |
| 956 interval = interval->next(); |
| 957 } |
| 958 |
| 959 const bool split_at_start = (interval->start() == split_pos); |
| 960 |
| 961 UseInterval* first_after_split = interval; |
| 962 if (!split_at_start && interval->Contains(split_pos)) { |
| 963 first_after_split = new UseInterval(split_pos, |
| 964 interval->end(), |
| 965 interval->next()); |
| 966 interval->end_ = split_pos; |
| 967 interval->next_ = first_after_split; |
| 968 last_before_split = interval; |
| 969 } |
| 970 |
| 971 ASSERT(last_before_split->next() == first_after_split); |
| 972 ASSERT(last_before_split->end() <= split_pos); |
| 973 ASSERT(split_pos <= first_after_split->start()); |
| 974 |
| 975 UsePosition* last_use_before_split = NULL; |
| 976 UsePosition* use = uses_; |
| 977 if (split_at_start) { |
| 978 while ((use != NULL) && (use->pos() < split_pos)) { |
| 979 last_use_before_split = use; |
| 980 use = use->next(); |
| 981 } |
| 982 } else { |
| 983 while ((use != NULL) && (use->pos() <= split_pos)) { |
| 984 last_use_before_split = use; |
| 985 use = use->next(); |
| 986 } |
| 987 } |
| 988 UsePosition* first_use_after_split = use; |
| 989 |
| 990 if (last_use_before_split == NULL) { |
| 991 uses_ = NULL; |
| 992 } else { |
| 993 last_use_before_split->set_next(NULL); |
| 994 } |
| 995 |
| 996 UseInterval* last_use_interval = (last_before_split == last_use_interval_) ? |
| 997 first_after_split : last_use_interval_; |
| 998 next_sibling_ = new LiveRange(vreg(), |
| 999 first_use_after_split, |
| 1000 first_after_split, |
| 1001 last_use_interval, |
| 1002 next_sibling_); |
| 1003 |
| 1004 TRACE_ALLOC((" split sibling [%d, %d)\n", |
| 1005 next_sibling_->Start(), next_sibling_->End())); |
| 1006 |
| 1007 // Split sibling can only start at a parallel move. |
| 1008 ASSERT(IsParallelMovePosition(next_sibling_->Start())); |
| 1009 |
| 1010 last_use_interval_ = last_before_split; |
| 1011 last_use_interval_->next_ = NULL; |
| 1012 return next_sibling_; |
| 1013 } |
| 1014 |
| 1015 |
| 1016 LiveRange* FlowGraphAllocator::SplitBetween(LiveRange* range, |
| 1017 intptr_t from, |
| 1018 intptr_t to) { |
| 1019 // TODO(vegorov): select optimal split position based on loop structure. |
| 1020 TRACE_ALLOC(("split %d [%d, %d) between [%d, %d)\n", |
| 1021 range->vreg(), range->Start(), range->End(), from, to)); |
| 1022 return range->SplitAt(to); |
| 1023 } |
| 1024 |
| 1025 |
| 1026 void FlowGraphAllocator::SpillBetween(LiveRange* range, |
| 1027 intptr_t from, |
| 1028 intptr_t to) { |
| 1029 ASSERT(from < to); |
| 1030 TRACE_ALLOC(("spill %d [%d, %d) between [%d, %d)\n", |
| 1031 range->vreg(), range->Start(), range->End(), from, to)); |
| 1032 LiveRange* tail = range->SplitAt(from); |
| 1033 |
| 1034 if (tail->Start() < to) { |
| 1035 // There is an intersection of tail and [from, to). |
| 1036 LiveRange* tail_tail = SplitBetween(tail, tail->Start(), to); |
| 1037 Spill(tail); |
| 1038 AddToUnallocated(tail_tail); |
| 1039 } else { |
| 1040 // No intersection between tail and [from, to). |
| 1041 AddToUnallocated(tail); |
| 1042 } |
| 1043 } |
| 1044 |
| 1045 |
| 1046 void FlowGraphAllocator::SpillAfter(LiveRange* range, intptr_t from) { |
| 1047 TRACE_ALLOC(("spill %d [%d, %d) after %d\n", |
| 1048 range->vreg(), range->Start(), range->End(), from)); |
| 1049 LiveRange* tail = range->SplitAt(from); |
| 1050 Spill(tail); |
| 1051 } |
| 1052 |
| 1053 |
| 1054 intptr_t FlowGraphAllocator::AllocateSpillSlotFor(LiveRange* range) { |
| 1055 for (intptr_t i = 0; i < spill_slots_.length(); i++) { |
| 1056 if (spill_slots_[i] <= range->Start()) { |
| 1057 return i; |
| 1058 } |
| 1059 } |
| 1060 spill_slots_.Add(0); |
| 1061 return spill_slots_.length() - 1; |
| 1062 } |
| 1063 |
| 1064 |
| 1065 void FlowGraphAllocator::Spill(LiveRange* range) { |
| 1066 const intptr_t spill_index = AllocateSpillSlotFor(range); |
| 1067 ASSERT(spill_slots_[spill_index] < range->Start()); |
| 1068 spill_slots_[spill_index] = range->End(); |
| 1069 range->set_assigned_location(Location::SpillSlot(spill_index)); |
| 1070 ConvertAllUses(range); |
| 1071 } |
| 1072 |
| 1073 |
| 1074 intptr_t FlowGraphAllocator::FirstIntersectionWithAllocated( |
| 1075 Register reg, LiveRange* unallocated) { |
| 1076 intptr_t intersection = kMaxPosition; |
| 1077 for (intptr_t i = 0; i < cpu_regs_[reg].length(); i++) { |
| 1078 LiveRange* allocated = cpu_regs_[reg][i]; |
| 1079 if (allocated == NULL) continue; |
| 1080 |
| 1081 UseInterval* allocated_head = |
| 1082 allocated->finger()->first_pending_use_interval(); |
| 1083 if (allocated_head->start() >= intersection) continue; |
| 1084 |
| 1085 const intptr_t pos = FirstIntersection( |
| 1086 unallocated->finger()->first_pending_use_interval(), |
| 1087 allocated_head); |
| 1088 if (pos < intersection) intersection = pos; |
| 1089 } |
| 1090 return intersection; |
| 1091 } |
| 1092 |
| 1093 |
| 1094 |
| 1095 bool FlowGraphAllocator::AllocateFreeRegister(LiveRange* unallocated) { |
669 Register candidate = kNoRegister; | 1096 Register candidate = kNoRegister; |
670 intptr_t free_until = 0; | 1097 intptr_t free_until = 0; |
671 | 1098 |
672 // If hint is available try hint first. | 1099 // If hint is available try hint first. |
673 // TODO(vegorov): ensure that phis are hinted on the backedge. | 1100 // TODO(vegorov): ensure that phis are hinted on the back edge. |
674 Location hint = LookAheadForHint(unallocated); | 1101 Location hint = unallocated->finger()->FirstHint(); |
675 if (!hint.IsInvalid()) { | 1102 if (!hint.IsInvalid()) { |
676 ASSERT(hint.IsRegister()); | 1103 ASSERT(hint.IsRegister()); |
677 | 1104 |
678 if (cpu_regs_[hint.reg()] != kPermanentlyBlocked) { | 1105 if (!blocked_cpu_regs_[hint.reg()]) { |
679 free_until = FirstIntersection(cpu_regs_[hint.reg()], unallocated); | 1106 free_until = FirstIntersectionWithAllocated(hint.reg(), unallocated); |
680 candidate = hint.reg(); | 1107 candidate = hint.reg(); |
681 } | 1108 } |
682 | 1109 |
683 TRACE_ALLOC(("found hint %s for %d: free until %d\n", | 1110 TRACE_ALLOC(("found hint %s for %d: free until %d\n", |
684 hint.Name(), unallocated->vreg(), free_until)); | 1111 hint.Name(), unallocated->vreg(), free_until)); |
685 } | 1112 } |
686 | 1113 |
687 if (free_until != kMaxPosition) { | 1114 if (free_until != kMaxPosition) { |
688 for (int reg = 0; reg < kNumberOfCpuRegisters; ++reg) { | 1115 for (intptr_t reg = 0; reg < kNumberOfCpuRegisters; ++reg) { |
689 if (cpu_regs_[reg] == NULL) { | 1116 if (!blocked_cpu_regs_[reg] && cpu_regs_[reg].length() == 0) { |
690 candidate = static_cast<Register>(reg); | 1117 candidate = static_cast<Register>(reg); |
691 free_until = kMaxPosition; | 1118 free_until = kMaxPosition; |
692 break; | 1119 break; |
693 } | 1120 } |
694 } | 1121 } |
695 } | 1122 } |
696 | 1123 |
697 ASSERT(0 <= kMaxPosition); | 1124 ASSERT(0 <= kMaxPosition); |
698 if (free_until != kMaxPosition) { | 1125 if (free_until != kMaxPosition) { |
699 for (int reg = 0; reg < kNumberOfCpuRegisters; ++reg) { | 1126 for (intptr_t reg = 0; reg < kNumberOfCpuRegisters; ++reg) { |
700 if (cpu_regs_[reg] == kPermanentlyBlocked) continue; | 1127 if (blocked_cpu_regs_[reg] || (reg == candidate)) continue; |
701 if (reg == candidate) continue; | 1128 |
702 | 1129 const intptr_t intersection = |
703 const intptr_t pos = FirstIntersection(cpu_regs_[reg], unallocated); | 1130 FirstIntersectionWithAllocated(static_cast<Register>(reg), unallocated); |
704 | 1131 |
705 if (pos > free_until) { | 1132 if (intersection > free_until) { |
706 candidate = static_cast<Register>(reg); | 1133 candidate = static_cast<Register>(reg); |
707 free_until = pos; | 1134 free_until = intersection; |
708 if (free_until == kMaxPosition) break; | 1135 if (free_until == kMaxPosition) break; |
709 } | 1136 } |
710 } | 1137 } |
711 } | 1138 } |
712 | 1139 |
| 1140 if (free_until != kMaxPosition) free_until = ToParallelMove(free_until); |
| 1141 |
713 // All registers are blocked by active ranges. | 1142 // All registers are blocked by active ranges. |
714 if (free_until <= unallocated->start()) return false; | 1143 if (free_until <= unallocated->Start()) return false; |
715 | 1144 |
716 AssignFreeRegister(unallocated, candidate); | 1145 TRACE_ALLOC(("assigning free register %s to %d\n", |
| 1146 Location::RegisterLocation(candidate).Name(), |
| 1147 unallocated->vreg())); |
| 1148 |
| 1149 if (free_until != kMaxPosition) { |
| 1150 // There was an intersection. Split unallocated. |
| 1151 TRACE_ALLOC((" splitting at %d\n", free_until)); |
| 1152 LiveRange* tail = unallocated->SplitAt(free_until); |
| 1153 AddToUnallocated(tail); |
| 1154 } |
| 1155 |
| 1156 cpu_regs_[candidate].Add(unallocated); |
| 1157 unallocated->set_assigned_location(Location::RegisterLocation(candidate)); |
| 1158 |
717 return true; | 1159 return true; |
718 } | 1160 } |
719 | 1161 |
720 | 1162 |
721 UseInterval* UseInterval::Split(intptr_t pos) { | 1163 void FlowGraphAllocator::AllocateAnyRegister(LiveRange* unallocated) { |
722 if (pos == start()) return this; | 1164 UsePosition* register_use = |
723 ASSERT(Contains(pos)); | 1165 unallocated->finger()->FirstRegisterUse(unallocated->Start()); |
724 UseInterval* tail = new UseInterval(vreg(), pos, end(), next()); | 1166 if (register_use == NULL) { |
725 | 1167 Spill(unallocated); |
726 UsePosition* use = uses_; | 1168 return; |
727 while (use != NULL && use->pos() <= pos) { | 1169 } |
728 use = use->next(); | 1170 |
729 } | 1171 Register candidate = kNoRegister; |
730 | 1172 intptr_t free_until = 0; |
731 tail->uses_ = use; | 1173 intptr_t blocked_at = kMaxPosition; |
732 | 1174 |
733 end_ = pos; | 1175 for (int reg = 0; reg < kNumberOfCpuRegisters; ++reg) { |
734 | 1176 if (blocked_cpu_regs_[reg]) continue; |
735 return tail; | 1177 if (UpdateFreeUntil(static_cast<Register>(reg), |
736 } | 1178 unallocated, |
737 | 1179 &free_until, |
738 | 1180 &blocked_at)) { |
739 void FlowGraphAllocator::AssignFreeRegister(UseInterval* unallocated, | 1181 candidate = static_cast<Register>(reg); |
740 Register reg) { | 1182 } |
741 TRACE_ALLOC(("assigning free register %s to %d\n", | 1183 } |
| 1184 |
| 1185 if (free_until < register_use->pos()) { |
| 1186 // Can't acquire free register. Spill until we really need one. |
| 1187 ASSERT(unallocated->Start() < ToParallelMove(register_use->pos())); |
| 1188 SpillBetween(unallocated, unallocated->Start(), register_use->pos()); |
| 1189 return; |
| 1190 } |
| 1191 |
| 1192 if (blocked_at < unallocated->End()) { |
| 1193 LiveRange* tail = SplitBetween(unallocated, |
| 1194 unallocated->Start(), |
| 1195 blocked_at); |
| 1196 AddToUnallocated(tail); |
| 1197 } |
| 1198 |
| 1199 AssignNonFreeRegister(unallocated, candidate); |
| 1200 } |
| 1201 |
| 1202 |
| 1203 bool FlowGraphAllocator::UpdateFreeUntil(Register reg, |
| 1204 LiveRange* unallocated, |
| 1205 intptr_t* cur_free_until, |
| 1206 intptr_t* cur_blocked_at) { |
| 1207 intptr_t free_until = kMaxPosition; |
| 1208 intptr_t blocked_at = kMaxPosition; |
| 1209 const intptr_t start = unallocated->Start(); |
| 1210 |
| 1211 for (intptr_t i = 0; i < cpu_regs_[reg].length(); i++) { |
| 1212 LiveRange* allocated = cpu_regs_[reg][i]; |
| 1213 |
| 1214 UseInterval* first_pending_use_interval = |
| 1215 allocated->finger()->first_pending_use_interval(); |
| 1216 if (first_pending_use_interval->Contains(start)) { |
| 1217 // This is an active interval. |
| 1218 if (allocated->vreg() <= 0) { |
| 1219 // This register blocked by an interval that |
| 1220 // can't be spilled. |
| 1221 return false; |
| 1222 } |
| 1223 |
| 1224 const UsePosition* use = |
| 1225 allocated->finger()->FirstRegisterBeneficialUse(unallocated->Start()); |
| 1226 |
| 1227 if ((use != NULL) && ((use->pos() - start) <= 1)) { |
| 1228 // This register is blocked by interval that is used |
| 1229 // as register in the current instruction and can't |
| 1230 // be spilled. |
| 1231 return false; |
| 1232 } |
| 1233 |
| 1234 const intptr_t use_pos = (use != NULL) ? use->pos() |
| 1235 : allocated->End(); |
| 1236 |
| 1237 if (use_pos < free_until) free_until = use_pos; |
| 1238 } else { |
| 1239 // This is inactive interval. |
| 1240 const intptr_t intersection = FirstIntersection( |
| 1241 first_pending_use_interval, unallocated->first_use_interval()); |
| 1242 if (intersection != kMaxPosition) { |
| 1243 if (intersection < free_until) free_until = intersection; |
| 1244 if (allocated->vreg() == kNoVirtualRegister) blocked_at = intersection; |
| 1245 } |
| 1246 } |
| 1247 |
| 1248 if (free_until <= *cur_free_until) { |
| 1249 return false; |
| 1250 } |
| 1251 } |
| 1252 |
| 1253 ASSERT(free_until > *cur_free_until); |
| 1254 *cur_free_until = free_until; |
| 1255 *cur_blocked_at = blocked_at; |
| 1256 return true; |
| 1257 } |
| 1258 |
| 1259 |
| 1260 void FlowGraphAllocator::RemoveEvicted(Register reg, intptr_t first_evicted) { |
| 1261 intptr_t to = first_evicted; |
| 1262 intptr_t from = first_evicted + 1; |
| 1263 while (from < cpu_regs_[reg].length()) { |
| 1264 LiveRange* allocated = cpu_regs_[reg][from++]; |
| 1265 if (allocated != NULL) cpu_regs_[reg][to++] = allocated; |
| 1266 } |
| 1267 cpu_regs_[reg].TruncateTo(to); |
| 1268 } |
| 1269 |
| 1270 |
| 1271 void FlowGraphAllocator::AssignNonFreeRegister(LiveRange* unallocated, |
| 1272 Register reg) { |
| 1273 TRACE_ALLOC(("assigning blocked register %s to live range %d\n", |
742 Location::RegisterLocation(reg).Name(), | 1274 Location::RegisterLocation(reg).Name(), |
743 unallocated->vreg())); | 1275 unallocated->vreg())); |
744 | 1276 |
745 UseInterval* a = cpu_regs_[reg]; | 1277 intptr_t first_evicted = -1; |
746 if (a == NULL) { | 1278 for (intptr_t i = cpu_regs_[reg].length() - 1; i >= 0; i--) { |
747 // Register is completely free. | 1279 LiveRange* allocated = cpu_regs_[reg][i]; |
748 cpu_regs_[reg] = unallocated; | 1280 if (allocated->vreg() < 0) continue; // Can't be evicted. |
| 1281 if (EvictIntersection(allocated, |
| 1282 unallocated)) { |
| 1283 cpu_regs_[reg][i] = NULL; |
| 1284 first_evicted = i; |
| 1285 } |
| 1286 } |
| 1287 |
| 1288 // Remove evicted ranges from the array. |
| 1289 if (first_evicted != -1) RemoveEvicted(reg, first_evicted); |
| 1290 |
| 1291 cpu_regs_[reg].Add(unallocated); |
| 1292 unallocated->set_assigned_location(Location::RegisterLocation(reg)); |
| 1293 } |
| 1294 |
| 1295 |
| 1296 bool FlowGraphAllocator::EvictIntersection(LiveRange* allocated, |
| 1297 LiveRange* unallocated) { |
| 1298 UseInterval* first_unallocated = |
| 1299 unallocated->finger()->first_pending_use_interval(); |
| 1300 const intptr_t intersection = FirstIntersection( |
| 1301 allocated->finger()->first_pending_use_interval(), |
| 1302 first_unallocated); |
| 1303 if (intersection == kMaxPosition) return false; |
| 1304 |
| 1305 const intptr_t spill_position = first_unallocated->start(); |
| 1306 UsePosition* use = allocated->finger()->FirstRegisterUse(spill_position); |
| 1307 if (use == NULL) { |
| 1308 // No register uses after this point. |
| 1309 SpillAfter(allocated, spill_position); |
| 1310 } else { |
| 1311 const intptr_t restore_position = |
| 1312 (spill_position < intersection) ? MinPosition(intersection, use->pos()) |
| 1313 : use->pos(); |
| 1314 |
| 1315 SpillBetween(allocated, spill_position, restore_position); |
| 1316 } |
| 1317 |
| 1318 return true; |
| 1319 } |
| 1320 |
| 1321 |
| 1322 MoveOperands* FlowGraphAllocator::AddMoveAt(intptr_t pos, |
| 1323 Location to, |
| 1324 Location from) { |
| 1325 ASSERT(IsParallelMovePosition(pos)); |
| 1326 Instruction* instr = InstructionAt(pos); |
| 1327 ASSERT(!instr->IsBlockEntry()); |
| 1328 return CreateParallelMoveBefore(instr, pos)->AddMove(to, from); |
| 1329 } |
| 1330 |
| 1331 |
| 1332 void FlowGraphAllocator::ConvertUseTo(UsePosition* use, Location loc) { |
| 1333 ASSERT(use->location_slot() != NULL); |
| 1334 Location* slot = use->location_slot(); |
| 1335 ASSERT(slot->IsUnallocated()); |
| 1336 ASSERT((slot->policy() == Location::kRequiresRegister) || |
| 1337 (slot->policy() == Location::kPrefersRegister) || |
| 1338 (slot->policy() == Location::kAny)); |
| 1339 TRACE_ALLOC((" use at %d converted to %s\n", use->pos(), loc.Name())); |
| 1340 *slot = loc; |
| 1341 } |
| 1342 |
| 1343 |
| 1344 void FlowGraphAllocator::ConvertAllUses(LiveRange* range) { |
| 1345 if (range->vreg() == kNoVirtualRegister) return; |
| 1346 TRACE_ALLOC(("range [%d, %d) for v%d has been allocated to %s:\n", |
| 1347 range->Start(), |
| 1348 range->End(), |
| 1349 range->vreg(), |
| 1350 range->assigned_location().Name())); |
| 1351 ASSERT(!range->assigned_location().IsInvalid()); |
| 1352 const Location loc = range->assigned_location(); |
| 1353 for (UsePosition* use = range->first_use(); use != NULL; use = use->next()) { |
| 1354 ConvertUseTo(use, loc); |
| 1355 } |
| 1356 } |
| 1357 |
| 1358 |
| 1359 bool AllocationFinger::Advance(const intptr_t start) { |
| 1360 UseInterval* a = first_pending_use_interval_; |
| 1361 while (a != NULL && a->end() <= start) a = a->next(); |
| 1362 first_pending_use_interval_ = a; |
| 1363 if (first_pending_use_interval_ == NULL) { |
| 1364 return true; |
| 1365 } |
| 1366 return false; |
| 1367 } |
| 1368 |
| 1369 |
| 1370 void FlowGraphAllocator::AdvanceActiveIntervals(const intptr_t start) { |
| 1371 for (intptr_t reg = 0; reg < kNumberOfCpuRegisters; reg++) { |
| 1372 if (cpu_regs_[reg].is_empty()) continue; |
| 1373 |
| 1374 intptr_t first_evicted = -1; |
| 1375 for (intptr_t i = cpu_regs_[reg].length() - 1; i >= 0; i--) { |
| 1376 LiveRange* range = cpu_regs_[reg][i]; |
| 1377 if (range->finger()->Advance(start)) { |
| 1378 ConvertAllUses(range); |
| 1379 cpu_regs_[reg][i] = NULL; |
| 1380 first_evicted = i; |
| 1381 } |
| 1382 } |
| 1383 |
| 1384 if (first_evicted != -1) { |
| 1385 RemoveEvicted(static_cast<Register>(reg), first_evicted); |
| 1386 } |
| 1387 } |
| 1388 } |
| 1389 |
| 1390 |
| 1391 void AllocationFinger::Initialize(LiveRange* range) { |
| 1392 first_pending_use_interval_ = range->first_use_interval(); |
| 1393 first_register_use_ = range->first_use(); |
| 1394 first_register_beneficial_use_ = range->first_use(); |
| 1395 first_hinted_use_ = range->first_use(); |
| 1396 } |
| 1397 |
| 1398 |
| 1399 static inline bool ShouldBeAllocatedBefore(LiveRange* a, LiveRange* b) { |
| 1400 return a->Start() <= b->Start(); |
| 1401 } |
| 1402 |
| 1403 |
| 1404 void FlowGraphAllocator::AddToUnallocated(LiveRange* range) { |
| 1405 range->finger()->Initialize(range); |
| 1406 |
| 1407 if (unallocated_.is_empty()) { |
| 1408 unallocated_.Add(range); |
749 return; | 1409 return; |
750 } | 1410 } |
751 | 1411 |
752 UseInterval* u = unallocated; | 1412 for (intptr_t i = unallocated_.length() - 1; i >= 0; i--) { |
753 ASSERT(u->start() < a->start()); // Register is free. | 1413 if (ShouldBeAllocatedBefore(range, unallocated_[i])) { |
754 cpu_regs_[reg] = u; | 1414 unallocated_.InsertAt(i + 1, range); |
755 if (u->next() == NULL || u->next()->start() >= a->start()) { | |
756 u->set_next_allocated(a); | |
757 } | |
758 | |
759 while (a != NULL && u != NULL) { | |
760 const intptr_t pos = a->Intersect(u); | |
761 if (pos != kIllegalPosition) { | |
762 // TODO(vegorov): split live ranges might require control flow resolution | |
763 // which is not implemented yet. | |
764 builder_->Bailout("ssa allocator: control flow resolution required"); | |
765 | |
766 TRACE_ALLOC((" splitting at %d\n", pos)); | |
767 // Reached intersection | |
768 UseInterval* tail = u->Split(pos); | |
769 AddToUnallocated(tail); | |
770 ASSERT(tail == u || u->next_allocated() == a); | |
771 return; | 1415 return; |
772 } | 1416 } |
773 | 1417 } |
774 if (a->start() < u->start()) { | 1418 unallocated_.InsertAt(0, range); |
775 if (a->next_allocated() == NULL) { | 1419 } |
776 a->set_next_allocated(u); | 1420 |
777 break; | 1421 |
778 } | 1422 #ifdef DEBUG |
779 | |
780 UseInterval* next = a->next_allocated(); | |
781 if (next->start() > u->start()) { | |
782 a->set_next_allocated(u); | |
783 u->set_next_allocated(next); | |
784 } | |
785 | |
786 a = next; | |
787 } else { | |
788 UseInterval* next = u->next(); | |
789 | |
790 if (next == NULL || next->start() >= a->start()) { | |
791 u->set_next_allocated(a); | |
792 } | |
793 u = next; | |
794 } | |
795 } | |
796 } | |
797 | |
798 | |
799 static void InsertMoveBefore(Instruction* instr, Location to, Location from) { | |
800 Instruction* prev = instr->previous(); | |
801 ParallelMoveInstr* move = prev->AsParallelMove(); | |
802 if (move == NULL) { | |
803 move = new ParallelMoveInstr(); | |
804 move->set_next(prev->next()); | |
805 prev->set_next(move); | |
806 move->next()->set_previous(move); | |
807 move->set_previous(prev); | |
808 } | |
809 move->AddMove(to, from); | |
810 } | |
811 | |
812 | |
813 void UsePosition::AssignLocation(Location loc) { | |
814 if (location_slot_ == NULL) return; | |
815 | |
816 if (location_slot_->IsUnallocated()) { | |
817 if (location_slot_->policy() == Location::kSameAsFirstInput) { | |
818 Instruction* instr = this->instr(); | |
819 LocationSummary* locs = instr->locs(); | |
820 if (!locs->in(0).IsUnallocated()) { | |
821 InsertMoveBefore(instr, loc, locs->in(0)); | |
822 } | |
823 locs->set_in(0, loc); | |
824 } | |
825 TRACE_ALLOC((" use at %d converted to %s\n", pos(), loc.Name())); | |
826 *location_slot_ = loc; | |
827 } else if (location_slot_->IsRegister()) { | |
828 InsertMoveBefore(this->instr(), *location_slot_, loc); | |
829 } | |
830 } | |
831 | |
832 | |
833 void FlowGraphAllocator::FinalizeInterval(UseInterval* interval, Location loc) { | |
834 if (interval->vreg() == kNoVirtualRegister) return; | |
835 | |
836 TRACE_ALLOC(("assigning location %s to interval [%d, %d)\n", loc.Name(), | |
837 interval->start(), interval->end())); | |
838 | |
839 for (UsePosition* use = interval->first_use(); | |
840 use != NULL && use->pos() <= interval->end(); | |
841 use = use->next()) { | |
842 use->AssignLocation(loc); | |
843 } | |
844 } | |
845 | |
846 | |
847 void FlowGraphAllocator::AdvanceActiveIntervals(const intptr_t start) { | |
848 for (int reg = 0; reg < kNumberOfCpuRegisters; reg++) { | |
849 if (cpu_regs_[reg] == NULL) continue; | |
850 if (cpu_regs_[reg] == kPermanentlyBlocked) continue; | |
851 | |
852 UseInterval* a = cpu_regs_[reg]; | |
853 while (a != NULL && a->end() <= start) { | |
854 FinalizeInterval(a, | |
855 Location::RegisterLocation(static_cast<Register>(reg))); | |
856 a = a->next_allocated(); | |
857 } | |
858 | |
859 cpu_regs_[reg] = a; | |
860 } | |
861 } | |
862 | |
863 | |
864 static inline bool ShouldBeAllocatedBefore(const UseInterval& a, | |
865 const UseInterval& b) { | |
866 return a.start() <= b.start(); | |
867 } | |
868 | |
869 | |
870 void FlowGraphAllocator::AddToUnallocated(UseInterval* chain) { | |
871 if (unallocated_.is_empty()) { | |
872 unallocated_.Add(chain); | |
873 return; | |
874 } | |
875 | |
876 for (intptr_t i = unallocated_.length() - 1; i >= 0; i--) { | |
877 if (ShouldBeAllocatedBefore(*chain, *unallocated_[i])) { | |
878 unallocated_.InsertAt(i + 1, chain); | |
879 return; | |
880 } | |
881 } | |
882 unallocated_.InsertAt(0, chain); | |
883 } | |
884 | |
885 | |
886 bool FlowGraphAllocator::UnallocatedIsSorted() { | 1423 bool FlowGraphAllocator::UnallocatedIsSorted() { |
887 for (intptr_t i = unallocated_.length() - 1; i >= 1; i--) { | 1424 for (intptr_t i = unallocated_.length() - 1; i >= 1; i--) { |
888 UseInterval* a = unallocated_[i]; | 1425 LiveRange* a = unallocated_[i]; |
889 UseInterval* b = unallocated_[i - 1]; | 1426 LiveRange* b = unallocated_[i - 1]; |
890 if (!ShouldBeAllocatedBefore(*a, *b)) return false; | 1427 if (!ShouldBeAllocatedBefore(a, b)) return false; |
891 } | 1428 } |
892 return true; | 1429 return true; |
893 } | 1430 } |
| 1431 #endif |
894 | 1432 |
895 | 1433 |
896 void FlowGraphAllocator::AllocateCPURegisters() { | 1434 void FlowGraphAllocator::AllocateCPURegisters() { |
| 1435 #ifdef DEBUG |
897 ASSERT(UnallocatedIsSorted()); | 1436 ASSERT(UnallocatedIsSorted()); |
| 1437 #endif |
| 1438 |
| 1439 for (intptr_t i = 0; i < kNumberOfCpuRegisters; i++) { |
| 1440 if (cpu_regs_[i].length() == 1) { |
| 1441 LiveRange* range = cpu_regs_[i][0]; |
| 1442 range->finger()->Initialize(range); |
| 1443 } |
| 1444 } |
898 | 1445 |
899 while (!unallocated_.is_empty()) { | 1446 while (!unallocated_.is_empty()) { |
900 UseInterval* range = unallocated_.Last(); | 1447 LiveRange* range = unallocated_.Last(); |
901 unallocated_.RemoveLast(); | 1448 unallocated_.RemoveLast(); |
902 const intptr_t start = range->start(); | 1449 const intptr_t start = range->Start(); |
903 TRACE_ALLOC(("Processing interval chain for vreg %d starting at %d\n", | 1450 TRACE_ALLOC(("Processing live range for vreg %d starting at %d\n", |
904 range->vreg(), | 1451 range->vreg(), |
905 start)); | 1452 start)); |
906 | 1453 |
907 // TODO(vegorov): eagerly spill liveranges without register uses. | 1454 // TODO(vegorov): eagerly spill liveranges without register uses. |
908 AdvanceActiveIntervals(start); | 1455 AdvanceActiveIntervals(start); |
909 | 1456 |
910 if (!AllocateFreeRegister(range)) { | 1457 if (!AllocateFreeRegister(range)) { |
911 builder_->Bailout("ssa allocator: spilling required"); | 1458 AllocateAnyRegister(range); |
912 return; | |
913 } | 1459 } |
914 } | 1460 } |
915 | 1461 |
916 // All allocation decisions were done. | 1462 // All allocation decisions were done. |
917 ASSERT(unallocated_.is_empty()); | 1463 ASSERT(unallocated_.is_empty()); |
918 | 1464 |
919 // Finish allocation. | 1465 // Finish allocation. |
920 AdvanceActiveIntervals(kMaxPosition); | 1466 AdvanceActiveIntervals(kMaxPosition); |
921 TRACE_ALLOC(("Allocation completed\n")); | 1467 TRACE_ALLOC(("Allocation completed\n")); |
922 } | 1468 } |
923 | 1469 |
924 | 1470 |
| 1471 void FlowGraphAllocator::ConnectSplitSiblings(LiveRange* range, |
| 1472 BlockEntryInstr* source_block, |
| 1473 BlockEntryInstr* target_block) { |
| 1474 if (range->next_sibling() == NULL) { |
| 1475 // Nothing to connect. The whole range was allocated to the same location. |
| 1476 TRACE_ALLOC(("range %d has no siblings\n", range->vreg())); |
| 1477 return; |
| 1478 } |
| 1479 |
| 1480 const intptr_t source_pos = source_block->end_pos() - 1; |
| 1481 ASSERT(IsInstructionPosition(source_pos)); |
| 1482 |
| 1483 const intptr_t target_pos = target_block->start_pos(); |
| 1484 |
| 1485 Location target; |
| 1486 Location source; |
| 1487 |
| 1488 #ifdef DEBUG |
| 1489 LiveRange* source_cover = NULL; |
| 1490 LiveRange* target_cover = NULL; |
| 1491 #endif |
| 1492 |
| 1493 while ((range != NULL) && (source.IsInvalid() || target.IsInvalid())) { |
| 1494 if (range->CanCover(source_pos)) { |
| 1495 ASSERT(source.IsInvalid()); |
| 1496 source = range->assigned_location(); |
| 1497 #ifdef DEBUG |
| 1498 source_cover = range; |
| 1499 #endif |
| 1500 } |
| 1501 if (range->CanCover(target_pos)) { |
| 1502 ASSERT(target.IsInvalid()); |
| 1503 target = range->assigned_location(); |
| 1504 #ifdef DEBUG |
| 1505 target_cover = range; |
| 1506 #endif |
| 1507 } |
| 1508 |
| 1509 range = range->next_sibling(); |
| 1510 } |
| 1511 |
| 1512 TRACE_ALLOC(("connecting [%d, %d) [%s] to [%d, %d) [%s]\n", |
| 1513 source_cover->Start(), source_cover->End(), source.Name(), |
| 1514 target_cover->Start(), target_cover->End(), target.Name())); |
| 1515 |
| 1516 // Siblings were allocated to the same register. |
| 1517 if (source.Equals(target)) return; |
| 1518 |
| 1519 Instruction* last = source_block->last_instruction(); |
| 1520 if (last->SuccessorCount() == 1) { |
| 1521 CreateParallelMoveBefore(last, last->lifetime_position() - 1)-> |
| 1522 AddMove(target, source); |
| 1523 } else { |
| 1524 CreateParallelMoveAfter(target_block, target_block->start_pos())-> |
| 1525 AddMove(target, source); |
| 1526 } |
| 1527 } |
| 1528 |
| 1529 |
| 1530 void FlowGraphAllocator::ResolveControlFlow() { |
| 1531 // Resolve linear control flow between touching split siblings |
| 1532 // inside basic blocks. |
| 1533 for (intptr_t vreg = 0; vreg < live_ranges_.length(); vreg++) { |
| 1534 LiveRange* range = live_ranges_[vreg]; |
| 1535 if (range == NULL) continue; |
| 1536 |
| 1537 while (range->next_sibling() != NULL) { |
| 1538 LiveRange* sibling = range->next_sibling(); |
| 1539 if ((range->End() == sibling->Start()) && |
| 1540 !range->assigned_location().Equals(sibling->assigned_location()) && |
| 1541 !IsBlockEntry(range->End())) { |
| 1542 AddMoveAt(sibling->Start(), |
| 1543 sibling->assigned_location(), |
| 1544 range->assigned_location()); |
| 1545 } |
| 1546 range = sibling; |
| 1547 } |
| 1548 } |
| 1549 |
| 1550 // Resolve non-linear control flow across branches. |
| 1551 for (intptr_t i = 1; i < block_order_.length(); i++) { |
| 1552 BlockEntryInstr* block = block_order_[i]; |
| 1553 BitVector* live = live_in_[block->postorder_number()]; |
| 1554 for (BitVector::Iterator it(live); !it.Done(); it.Advance()) { |
| 1555 LiveRange* range = GetLiveRange(it.Current()); |
| 1556 for (intptr_t j = 0; j < block->PredecessorCount(); j++) { |
| 1557 ConnectSplitSiblings(range, block->PredecessorAt(j), block); |
| 1558 } |
| 1559 } |
| 1560 } |
| 1561 } |
| 1562 |
| 1563 |
925 void FlowGraphAllocator::AllocateRegisters() { | 1564 void FlowGraphAllocator::AllocateRegisters() { |
926 GraphEntryInstr* entry = block_order_[0]->AsGraphEntry(); | 1565 GraphEntryInstr* entry = block_order_[0]->AsGraphEntry(); |
927 ASSERT(entry != NULL); | 1566 ASSERT(entry != NULL); |
928 | 1567 |
929 for (intptr_t i = 0; i < entry->start_env()->values().length(); i++) { | 1568 for (intptr_t i = 0; i < entry->start_env()->values().length(); i++) { |
930 if (entry->start_env()->values()[i]->IsUse()) { | 1569 if (entry->start_env()->values()[i]->IsUse()) { |
931 builder_->Bailout("ssa allocator: unsupported start environment"); | 1570 builder_->Bailout("ssa allocator: unsupported start environment"); |
932 } | 1571 } |
933 } | 1572 } |
934 | 1573 |
935 AnalyzeLiveness(); | 1574 AnalyzeLiveness(); |
936 | 1575 |
937 BuildLiveRanges(); | 1576 BuildLiveRanges(); |
938 | 1577 |
939 if (FLAG_print_ssa_liveness) { | 1578 if (FLAG_print_ssa_liveness) { |
940 DumpLiveness(); | 1579 DumpLiveness(); |
941 } | 1580 } |
942 | 1581 |
943 if (FLAG_trace_ssa_allocator) { | 1582 if (FLAG_trace_ssa_allocator) { |
944 PrintLiveRanges(); | 1583 PrintLiveRanges(); |
945 } | 1584 } |
946 | 1585 |
947 AllocateCPURegisters(); | 1586 AllocateCPURegisters(); |
948 | 1587 |
| 1588 ResolveControlFlow(); |
| 1589 |
949 if (FLAG_trace_ssa_allocator) { | 1590 if (FLAG_trace_ssa_allocator) { |
950 OS::Print("-- ir after allocation -------------------------\n"); | 1591 OS::Print("-- ir after allocation -------------------------\n"); |
951 FlowGraphPrinter printer(Function::Handle(), block_order_, true); | 1592 FlowGraphPrinter printer(Function::Handle(), block_order_, true); |
952 printer.PrintBlocks(); | 1593 printer.PrintBlocks(); |
953 } | 1594 } |
954 } | 1595 } |
955 | 1596 |
956 | 1597 |
957 } // namespace dart | 1598 } // namespace dart |
OLD | NEW |