Intended to be called after `find_loop_headers`. For each detected loop header, discovers all the block belonging to the loop and its inner loops. After a call to this function, the loop tree is fully constructed.
(&mut self, cfg: &ControlFlowGraph, domtree: &DominatorTree)
| 215 | // discovers all the block belonging to the loop and its inner loops. After a call to this |
| 216 | // function, the loop tree is fully constructed. |
| 217 | fn discover_loop_blocks(&mut self, cfg: &ControlFlowGraph, domtree: &DominatorTree) { |
| 218 | let mut stack: Vec<Block> = Vec::new(); |
| 219 | // We handle each loop header in reverse order, corresponding to a pseudo postorder |
| 220 | // traversal of the graph. |
| 221 | for lp in self.loops().rev() { |
| 222 | // Push all predecessors of this header that it dominates onto the stack. |
| 223 | stack.extend( |
| 224 | cfg.pred_iter(self.loops[lp].header) |
| 225 | .filter(|pred| { |
| 226 | // We follow the back edges |
| 227 | domtree.block_dominates(self.loops[lp].header, pred.block) |
| 228 | }) |
| 229 | .map(|pred| pred.block), |
| 230 | ); |
| 231 | while let Some(node) = stack.pop() { |
| 232 | let continue_dfs: Option<Block>; |
| 233 | match self.block_loop_map[node].expand() { |
| 234 | None => { |
| 235 | // The node hasn't been visited yet, we tag it as part of the loop |
| 236 | self.block_loop_map[node] = PackedOption::from(lp); |
| 237 | continue_dfs = Some(node); |
| 238 | } |
| 239 | Some(node_loop) => { |
| 240 | // We copy the node_loop into a mutable reference passed along the while |
| 241 | let mut node_loop = node_loop; |
| 242 | // The node is part of a loop, which can be lp or an inner loop |
| 243 | let mut node_loop_parent_option = self.loops[node_loop].parent; |
| 244 | while let Some(node_loop_parent) = node_loop_parent_option.expand() { |
| 245 | if node_loop_parent == lp { |
| 246 | // We have encountered lp so we stop (already visited) |
| 247 | break; |
| 248 | } else { |
| 249 | // |
| 250 | node_loop = node_loop_parent; |
| 251 | // We lookup the parent loop |
| 252 | node_loop_parent_option = self.loops[node_loop].parent; |
| 253 | } |
| 254 | } |
| 255 | // Now node_loop_parent is either: |
| 256 | // - None and node_loop is an new inner loop of lp |
| 257 | // - Some(...) and the initial node_loop was a known inner loop of lp |
| 258 | match node_loop_parent_option.expand() { |
| 259 | Some(_) => continue_dfs = None, |
| 260 | None => { |
| 261 | if node_loop != lp { |
| 262 | self.loops[node_loop].parent = lp.into(); |
| 263 | continue_dfs = Some(self.loops[node_loop].header) |
| 264 | } else { |
| 265 | // If lp is a one-block loop then we make sure we stop |
| 266 | continue_dfs = None |
| 267 | } |
| 268 | } |
| 269 | } |
| 270 | } |
| 271 | } |
| 272 | // Now we have handled the popped node and need to continue the DFS by adding the |
| 273 | // predecessors of that node |
| 274 | if let Some(continue_dfs) = continue_dfs { |