hphp/hack/src/hackc/ir/passes/critedge.rs

   1 use analysis::PredecessorCatchMode;
   2 use analysis::PredecessorFlags;
   3 use ir_core::instr::HasEdges;
   4 use ir_core::instr::HasLoc;
   5 use ir_core::Block;
   6 use ir_core::BlockId;
   7 use ir_core::Func;
   8 use ir_core::Instr;
   9 use ir_core::LocId;
  10
  11 /// Find and split critical edges. Assumes there are no unreachable blocks,
  12 /// which is the case after rpo_sort().
  13 ///
  14 /// A critical edge is one where the source has multiple successors and the
  15 /// destination has multiple predecessors. By splitting them we ensure that we
  16 /// can always add instructions to one side of an edge which only affects that
  17 /// edge.
  18 ///
  19 /// 1. find critical edges, build a simple work list. Create new BlockIds now
  20 ///    and update the edges to the new target BlockIds.
  21 /// 2. Create the new empty blocks, then fill them in from the worklist. Order
  22 ///    doesn't matter because we recorded all BlockIds in step 1.
  23 /// 3. re-run rpo_sort().
  24 ///
  25 pub fn split_critical_edges(func: &mut Func<'_>, rpo_sort: bool) {
  26     let pred_counts = analysis::compute_num_predecessors(
  27         func,
  28         PredecessorFlags {
  29             mark_entry_blocks: false,
  30             catch: PredecessorCatchMode::Ignore,
  31         },
  32     );
  33     let mut work = Vec::new();
  34     let num_blocks = func.blocks.len();
  35     for bid in func.block_ids() {
  36         let term = func.terminator_mut(bid);
  37         let loc = term.loc_id();
  38         let edges = term.edges_mut();
  39         if edges.len() > 1 {
  40             for edge in edges {
  41                 if pred_counts[*edge] > 1 {
  42                     // cannot create new blocks and instructions while iterating
  43                     // here, so make a simple worklist
  44                     let split_bid = BlockId((num_blocks + work.len()) as u32);
  45                     work.push(WorkItem {
  46                         loc,
  47                         split_bid,
  48                         old_target: edge.clone(),
  49                     });
  50                     *edge = split_bid;
  51                 }
  52             }
  53         }
  54     }
  55     if !work.is_empty() {
  56         func.blocks
  57             .resize(num_blocks + work.len(), Block::default());
  58         for item in work.drain(..) {
  59             let _params = func.block(item.old_target).params.len();
  60             let instr = Instr::jmp(item.old_target, item.loc);
  61             func.emit(item.split_bid, instr);
  62         }
  63         if rpo_sort {
  64             crate::rpo_sort(func)
  65         }
  66     }
  67 }
  68
  69 struct WorkItem {
  70     loc: LocId,
  71     split_bid: BlockId,
  72     old_target: BlockId,
  73 }
  74
  75 #[cfg(test)]
  76 mod test {
  77     use std::sync::Arc;
  78
  79     #[test]
  80     fn basic_no_split() {
  81         let (mut func, strings) = testutils::build_test_func(&[
  82             testutils::Block::jmp_op("a", ["b", "c"]),
  83             testutils::Block::jmp("b", "d"),
  84             testutils::Block::jmp("c", "d"),
  85             testutils::Block::ret("d"),
  86         ]);
  87         let expected = func.clone();
  88
  89         super::split_critical_edges(&mut func, true);
  90         testutils::assert_func_struct_eq(&func, &expected, &strings);
  91     }
  92
  93     #[test]
  94     fn basic_split() {
  95         let (mut func, strings) = testutils::build_test_func(&[
  96             testutils::Block::jmp_op("a", ["b", "c"]),
  97             testutils::Block::jmp("b", "d"),
  98             testutils::Block::jmp_op("c", ["d", "e"]),
  99             testutils::Block::ret("d"),
 100             testutils::Block::ret("e"),
 101         ]);
 102
 103         super::split_critical_edges(&mut func, true);
 104
 105         let expected = testutils::build_test_func_with_strings(
 106             &[
 107                 testutils::Block::jmp_op("a", ["b", "c"]),
 108                 testutils::Block::jmp("b", "d"),
 109                 testutils::Block::jmp_op("c", ["f", "e"]),
 110                 testutils::Block::jmp("f", "d").unnamed(),
 111                 testutils::Block::ret("d"),
 112                 testutils::Block::ret("e"),
 113             ],
 114             Arc::clone(&strings),
 115         );
 116         testutils::assert_func_struct_eq(&func, &expected, &strings);
 117     }
 118 }