| 414 | } |
| 415 | |
| 416 | fn compute_preds_from_succs(&mut self) { |
| 417 | // Do a linear-time counting sort: first determine how many |
| 418 | // times each block appears as a successor. |
| 419 | let mut starts = vec![0u32; self.vcode.num_blocks()]; |
| 420 | for succ in &self.vcode.block_succs { |
| 421 | starts[succ.index()] += 1; |
| 422 | } |
| 423 | |
| 424 | // Determine for each block the starting index where that |
| 425 | // block's predecessors should go. This is equivalent to the |
| 426 | // ranges we need to store in block_pred_range. |
| 427 | self.vcode.block_pred_range.reserve(starts.len()); |
| 428 | let mut end = 0; |
| 429 | for count in starts.iter_mut() { |
| 430 | let start = end; |
| 431 | end += *count; |
| 432 | *count = start; |
| 433 | self.vcode.block_pred_range.push_end(end as usize); |
| 434 | } |
| 435 | let end = end as usize; |
| 436 | debug_assert_eq!(end, self.vcode.block_succs.len()); |
| 437 | |
| 438 | // Walk over the successors again, this time grouped by |
| 439 | // predecessor, and push the predecessor at the current |
| 440 | // starting position of each of its successors. We build |
| 441 | // each group of predecessors in whatever order Ranges::iter |
| 442 | // returns them; regalloc2 doesn't care. |
| 443 | self.vcode.block_preds.resize(end, BlockIndex::invalid()); |
| 444 | for (pred, range) in self.vcode.block_succ_range.iter() { |
| 445 | let pred = BlockIndex::new(pred); |
| 446 | for succ in &self.vcode.block_succs[range] { |
| 447 | let pos = &mut starts[succ.index()]; |
| 448 | self.vcode.block_preds[*pos as usize] = pred; |
| 449 | *pos += 1; |
| 450 | } |
| 451 | } |
| 452 | debug_assert!(self.vcode.block_preds.iter().all(|pred| pred.is_valid())); |
| 453 | } |
| 454 | |
| 455 | /// Called once, when a build in Backward order is complete, to |
| 456 | /// perform the overall reversal (into final forward order) and |