| 92 | type Item = (Event, ir::Block); |
| 93 | |
| 94 | fn next(&mut self) -> Option<(Event, ir::Block)> { |
| 95 | loop { |
| 96 | let (event, block) = self.dfs.stack.pop()?; |
| 97 | |
| 98 | if event == Event::Enter { |
| 99 | let first_time_seeing = self.dfs.seen.insert(block); |
| 100 | if !first_time_seeing { |
| 101 | continue; |
| 102 | } |
| 103 | |
| 104 | self.dfs.stack.push((Event::Exit, block)); |
| 105 | self.dfs.stack.extend( |
| 106 | self.func |
| 107 | .block_successors(block) |
| 108 | // Heuristic: chase the children in reverse. This puts |
| 109 | // the first successor block first in the postorder, all |
| 110 | // other things being equal, which tends to prioritize |
| 111 | // loop backedges over out-edges, putting the edge-block |
| 112 | // closer to the loop body and minimizing live-ranges in |
| 113 | // linear instruction space. This heuristic doesn't have |
| 114 | // any effect on the computation of dominators, and is |
| 115 | // purely for other consumers of the postorder we cache |
| 116 | // here. |
| 117 | .rev() |
| 118 | // This is purely an optimization to avoid additional |
| 119 | // iterations of the loop, and is not required; it's |
| 120 | // merely inlining the check from the outer conditional |
| 121 | // of this case to avoid the extra loop iteration. This |
| 122 | // also avoids potential excess stack growth. |
| 123 | .filter(|block| !self.dfs.seen.contains(*block)) |
| 124 | .map(|block| (Event::Enter, block)), |
| 125 | ); |
| 126 | } |
| 127 | |
| 128 | return Some((event, block)); |
| 129 | } |
| 130 | } |
| 131 | } |
| 132 | |
| 133 | /// An iterator that yields `ir::Block` items during a depth-first, pre-order |