1use core::cmp::Ordering;
5
6use crate::dominator_tree::DominatorTree;
7use crate::entity::SecondaryMap;
8use crate::entity::entity_impl;
9use crate::entity::{Keys, PrimaryMap};
10use crate::flowgraph::ControlFlowGraph;
11use crate::ir::{Block, Function};
12use crate::packed_option::PackedOption;
13use crate::timing;
14use crate::traversals::Event;
15use alloc::vec::Vec;
16use smallvec::SmallVec;
17
18#[derive(Copy, Clone, PartialEq, Eq, Hash, PartialOrd, Ord)]
20pub struct Loop(u32);
21entity_impl!(Loop, "loop");
22
23pub struct LoopAnalysis {
28 loops: PrimaryMap<Loop, LoopData>,
29 block_loop_map: SecondaryMap<Block, PackedOption<Loop>>,
30 valid: bool,
31}
32
33struct LoopData {
34 header: Block,
35 parent: PackedOption<Loop>,
36 level: LoopLevel,
37 preorder: u32,
39 subtree_end: u32,
41}
42
43#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
45pub struct LoopLevel(u8);
46impl LoopLevel {
47 const INVALID: u8 = u8::MAX;
48
49 pub fn root() -> Self {
51 Self(0)
52 }
53 pub fn level(self) -> usize {
55 self.0 as usize
56 }
57 pub fn invalid() -> Self {
59 Self(Self::INVALID)
60 }
61 pub fn inc(self) -> Self {
63 if self.0 == (Self::INVALID - 1) {
64 self
65 } else {
66 Self(self.0 + 1)
67 }
68 }
69 pub fn clamped(level: usize) -> Self {
71 Self(
72 u8::try_from(core::cmp::min(level, (Self::INVALID as usize) - 1))
73 .expect("Clamped value must always convert"),
74 )
75 }
76}
77
78impl core::default::Default for LoopLevel {
79 fn default() -> Self {
80 LoopLevel::invalid()
81 }
82}
83
84impl LoopData {
85 pub fn new(header: Block, parent: Option<Loop>) -> Self {
87 Self {
88 header,
89 parent: parent.into(),
90 level: LoopLevel::invalid(),
91 preorder: 0,
92 subtree_end: 0,
93 }
94 }
95}
96
97impl LoopAnalysis {
99 pub fn new() -> Self {
102 Self {
103 valid: false,
104 loops: PrimaryMap::new(),
105 block_loop_map: SecondaryMap::new(),
106 }
107 }
108
109 pub fn loops(&self) -> Keys<Loop> {
111 self.loops.keys()
112 }
113
114 pub fn loop_header(&self, lp: Loop) -> Block {
119 self.loops[lp].header
120 }
121
122 pub fn loop_parent(&self, lp: Loop) -> Option<Loop> {
124 self.loops[lp].parent.expand()
125 }
126
127 pub fn common_ancestor(&self, mut a: Loop, mut b: Loop) -> Option<Loop> {
129 loop {
130 match a.cmp(&b) {
134 Ordering::Less => b = self.loop_parent(b)?,
135 Ordering::Equal => return Some(a),
136 Ordering::Greater => a = self.loop_parent(a)?,
137 }
138 }
139 }
140
141 pub fn innermost_loop(&self, block: Block) -> Option<Loop> {
143 self.block_loop_map[block].expand()
144 }
145
146 pub fn is_loop_header(&self, block: Block) -> Option<Loop> {
148 self.innermost_loop(block)
149 .filter(|&lp| self.loop_header(lp) == block)
150 }
151
152 pub fn is_in_loop(&self, block: Block, lp: Loop) -> bool {
156 let block_loop = self.block_loop_map[block];
157 match block_loop.expand() {
158 None => false,
159 Some(block_loop) => self.is_child_loop(block_loop, lp),
160 }
161 }
162
163 pub fn is_child_loop(&self, child: Loop, parent: Loop) -> bool {
165 let child = &self.loops[child];
166 let parent = &self.loops[parent];
167 parent.preorder <= child.preorder && child.preorder < parent.subtree_end
168 }
169
170 pub fn loop_level(&self, block: Block) -> LoopLevel {
172 self.innermost_loop(block)
173 .map_or(LoopLevel(0), |lp| self.loops[lp].level)
174 }
175}
176
177impl LoopAnalysis {
178 pub fn compute(&mut self, func: &Function, cfg: &ControlFlowGraph, domtree: &DominatorTree) {
180 let _tt = timing::loop_analysis();
181 self.loops.clear();
182 self.block_loop_map.clear();
183 self.block_loop_map.resize(func.dfg.num_blocks());
184 self.find_loop_headers(cfg, domtree);
185 self.discover_loop_blocks(cfg, domtree);
186 self.number_loops();
187 self.valid = true;
188 }
189
190 pub fn is_valid(&self) -> bool {
196 self.valid
197 }
198
199 pub fn clear(&mut self) {
203 self.loops.clear();
204 self.block_loop_map.clear();
205 self.valid = false;
206 }
207
208 fn is_block_loop_header(block: Block, cfg: &ControlFlowGraph, domtree: &DominatorTree) -> bool {
211 cfg.pred_iter(block)
213 .any(|pred| domtree.block_dominates(block, pred.block))
214 }
215
216 fn find_loop_headers(&mut self, cfg: &ControlFlowGraph, domtree: &DominatorTree) {
219 for &block in domtree
220 .cfg_rpo()
221 .filter(|&&block| Self::is_block_loop_header(block, cfg, domtree))
222 {
223 let lp = self.loops.push(LoopData::new(block, None));
225 self.block_loop_map[block] = lp.into();
226 }
227 }
228
229 fn discover_loop_blocks(&mut self, cfg: &ControlFlowGraph, domtree: &DominatorTree) {
233 let mut stack: Vec<Block> = Vec::new();
234 for lp in self.loops().rev() {
237 stack.extend(
239 cfg.pred_iter(self.loops[lp].header)
240 .filter(|pred| {
241 domtree.block_dominates(self.loops[lp].header, pred.block)
243 })
244 .map(|pred| pred.block),
245 );
246 while let Some(node) = stack.pop() {
247 let continue_dfs: Option<Block>;
248 match self.block_loop_map[node].expand() {
249 None => {
250 self.block_loop_map[node] = PackedOption::from(lp);
252 continue_dfs = Some(node);
253 }
254 Some(node_loop) => {
255 let mut node_loop = node_loop;
257 let mut node_loop_parent_option = self.loops[node_loop].parent;
259 while let Some(node_loop_parent) = node_loop_parent_option.expand() {
260 if node_loop_parent == lp {
261 break;
263 } else {
264 node_loop = node_loop_parent;
266 node_loop_parent_option = self.loops[node_loop].parent;
268 }
269 }
270 match node_loop_parent_option.expand() {
274 Some(_) => continue_dfs = None,
275 None => {
276 if node_loop != lp {
277 self.loops[node_loop].parent = lp.into();
278 continue_dfs = Some(self.loops[node_loop].header)
279 } else {
280 continue_dfs = None
282 }
283 }
284 }
285 }
286 }
287 if let Some(continue_dfs) = continue_dfs {
290 stack.extend(cfg.pred_iter(continue_dfs).map(|pred| pred.block));
291 }
292 }
293 }
294 }
295
296 fn number_loops(&mut self) {
297 #[derive(Clone, Copy, Default)]
298 struct Links {
299 first_child: PackedOption<Loop>,
300 next_sibling: PackedOption<Loop>,
301 }
302
303 let mut links: SecondaryMap<Loop, Links> = SecondaryMap::new();
304 links.resize(self.loops.len());
305 let mut stack: SmallVec<[(Event, Loop); 8]> = SmallVec::new();
306 for lp in self.loops.keys() {
307 self.loops[lp].level = if let Some(parent) = self.loop_parent(lp) {
309 links[lp].next_sibling = links[parent].first_child;
310 links[parent].first_child = lp.into();
311 self.loops[parent].level.inc()
312 } else {
313 stack.push((Event::Enter, lp));
314 LoopLevel::root().inc()
315 };
316 }
317
318 let mut next = 0;
321 while let Some((event, lp)) = stack.pop() {
322 match event {
323 Event::Enter => {
324 self.loops[lp].preorder = next;
325 next += 1;
326 if let Some(sibling) = links[lp].next_sibling.expand() {
327 stack.push((Event::Enter, sibling));
328 }
329 stack.push((Event::Exit, lp));
330 if let Some(child) = links[lp].first_child.expand() {
331 stack.push((Event::Enter, child));
332 }
333 }
334 Event::Exit => self.loops[lp].subtree_end = next,
335 }
336 }
337 }
338}
339
340#[cfg(test)]
341mod tests {
342 use crate::cursor::{Cursor, FuncCursor};
343 use crate::dominator_tree::DominatorTree;
344 use crate::flowgraph::ControlFlowGraph;
345 use crate::ir::{Block, Function, InstBuilder, types};
346 use crate::loop_analysis::{Loop, LoopAnalysis, LoopData};
347 use alloc::vec::Vec;
348
349 #[test]
350 fn loop_ranges_with_interleaved_roots() {
351 let mut analysis = LoopAnalysis::new();
352 let outer = analysis.loops.push(LoopData::new(Block::from_u32(0), None));
355 let separate = analysis.loops.push(LoopData::new(Block::from_u32(1), None));
356 let inner = analysis
357 .loops
358 .push(LoopData::new(Block::from_u32(2), Some(outer)));
359 analysis.number_loops();
360
361 assert!(analysis.is_child_loop(inner, outer));
362 assert!(analysis.is_child_loop(outer, outer));
363 assert!(!analysis.is_child_loop(outer, inner));
364 assert!(!analysis.is_child_loop(separate, outer));
365 assert!(!analysis.is_child_loop(inner, separate));
366 }
367
368 #[test]
369 fn nested_loops_detection() {
370 let mut func = Function::new();
371 let block0 = func.dfg.make_block();
372 let block1 = func.dfg.make_block();
373 let block2 = func.dfg.make_block();
374 let block3 = func.dfg.make_block();
375 let block4 = func.dfg.make_block();
376 let cond = func.dfg.append_block_param(block0, types::I32);
377
378 {
379 let mut cur = FuncCursor::new(&mut func);
380
381 cur.insert_block(block0);
382 cur.ins().jump(block1, &[]);
383
384 cur.insert_block(block1);
385 cur.ins().jump(block2, &[]);
386
387 cur.insert_block(block2);
388 cur.ins().brif(cond, block1, &[], block3, &[]);
389
390 cur.insert_block(block3);
391 cur.ins().brif(cond, block0, &[], block4, &[]);
392
393 cur.insert_block(block4);
394 cur.ins().return_(&[]);
395 }
396
397 let mut loop_analysis = LoopAnalysis::new();
398 let mut cfg = ControlFlowGraph::new();
399 let mut domtree = DominatorTree::new();
400 cfg.compute(&func);
401 domtree.compute(&func, &cfg);
402 loop_analysis.compute(&func, &cfg, &domtree);
403
404 let loops = loop_analysis.loops().collect::<Vec<Loop>>();
405 assert_eq!(loops.len(), 2);
406 assert_eq!(loop_analysis.loop_header(loops[0]), block0);
407 assert_eq!(loop_analysis.loop_header(loops[1]), block1);
408 assert_eq!(loop_analysis.loop_parent(loops[1]), Some(loops[0]));
409 assert_eq!(loop_analysis.loop_parent(loops[0]), None);
410 assert_eq!(loop_analysis.is_in_loop(block0, loops[0]), true);
411 assert_eq!(loop_analysis.is_in_loop(block0, loops[1]), false);
412 assert_eq!(loop_analysis.is_in_loop(block1, loops[1]), true);
413 assert_eq!(loop_analysis.is_in_loop(block1, loops[0]), true);
414 assert_eq!(loop_analysis.is_in_loop(block2, loops[1]), true);
415 assert_eq!(loop_analysis.is_in_loop(block2, loops[0]), true);
416 assert_eq!(loop_analysis.is_in_loop(block3, loops[0]), true);
417 assert_eq!(loop_analysis.is_in_loop(block0, loops[1]), false);
418 assert_eq!(loop_analysis.loop_level(block0).level(), 1);
419 assert_eq!(loop_analysis.loop_level(block1).level(), 2);
420 assert_eq!(loop_analysis.loop_level(block2).level(), 2);
421 assert_eq!(loop_analysis.loop_level(block3).level(), 1);
422 assert_eq!(
423 loop_analysis.common_ancestor(loops[0], loops[1]),
424 Some(loops[0])
425 );
426 assert_eq!(
427 loop_analysis.common_ancestor(loops[1], loops[0]),
428 Some(loops[0])
429 );
430 assert_eq!(
431 loop_analysis.common_ancestor(loops[1], loops[1]),
432 Some(loops[1])
433 );
434 }
435
436 #[test]
437 fn complex_loop_detection() {
438 let mut func = Function::new();
439 let block0 = func.dfg.make_block();
440 let block1 = func.dfg.make_block();
441 let block2 = func.dfg.make_block();
442 let block3 = func.dfg.make_block();
443 let block4 = func.dfg.make_block();
444 let block5 = func.dfg.make_block();
445 let block6 = func.dfg.make_block();
446 let cond = func.dfg.append_block_param(block0, types::I32);
447
448 {
449 let mut cur = FuncCursor::new(&mut func);
450
451 cur.insert_block(block0);
452 cur.ins().brif(cond, block1, &[], block3, &[]);
453
454 cur.insert_block(block1);
455 cur.ins().jump(block2, &[]);
456
457 cur.insert_block(block2);
458 cur.ins().brif(cond, block1, &[], block5, &[]);
459
460 cur.insert_block(block3);
461 cur.ins().jump(block4, &[]);
462
463 cur.insert_block(block4);
464 cur.ins().brif(cond, block3, &[], block5, &[]);
465
466 cur.insert_block(block5);
467 cur.ins().brif(cond, block0, &[], block6, &[]);
468
469 cur.insert_block(block6);
470 cur.ins().return_(&[]);
471 }
472
473 let mut loop_analysis = LoopAnalysis::new();
474 let cfg = ControlFlowGraph::with_function(&func);
475 let domtree = DominatorTree::with_function(&func, &cfg);
476 loop_analysis.compute(&func, &cfg, &domtree);
477
478 let loops = loop_analysis.loops().collect::<Vec<Loop>>();
479 assert_eq!(loops.len(), 3);
480 assert_eq!(loop_analysis.loop_header(loops[0]), block0);
481 assert_eq!(loop_analysis.loop_header(loops[1]), block3);
482 assert_eq!(loop_analysis.loop_header(loops[2]), block1);
483 assert_eq!(loop_analysis.loop_parent(loops[1]), Some(loops[0]));
484 assert_eq!(loop_analysis.loop_parent(loops[2]), Some(loops[0]));
485 assert_eq!(loop_analysis.loop_parent(loops[0]), None);
486 assert_eq!(loop_analysis.is_in_loop(block0, loops[0]), true);
487 assert_eq!(loop_analysis.is_in_loop(block1, loops[2]), true);
488 assert_eq!(loop_analysis.is_in_loop(block2, loops[2]), true);
489 assert_eq!(loop_analysis.is_in_loop(block3, loops[1]), true);
490 assert_eq!(loop_analysis.is_in_loop(block4, loops[1]), true);
491 assert_eq!(loop_analysis.is_in_loop(block5, loops[0]), true);
492 assert!(!loop_analysis.is_child_loop(loops[1], loops[2]));
493 assert!(!loop_analysis.is_child_loop(loops[2], loops[1]));
494 assert!(!loop_analysis.is_in_loop(block6, loops[0]));
495 assert_eq!(loop_analysis.loop_level(block0).level(), 1);
496 assert_eq!(loop_analysis.loop_level(block1).level(), 2);
497 assert_eq!(loop_analysis.loop_level(block2).level(), 2);
498 assert_eq!(loop_analysis.loop_level(block3).level(), 2);
499 assert_eq!(loop_analysis.loop_level(block4).level(), 2);
500 assert_eq!(loop_analysis.loop_level(block5).level(), 1);
501 assert_eq!(
502 loop_analysis.common_ancestor(loops[1], loops[2]),
503 Some(loops[0])
504 );
505 assert_eq!(
506 loop_analysis.common_ancestor(loops[2], loops[1]),
507 Some(loops[0])
508 );
509 }
510}