Skip to main content

cranelift_codegen/
loop_analysis.rs

1//! A loop analysis represented as mappings of loops to their header Block
2//! and parent in the loop tree.
3
4use 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/// A opaque reference to a code loop.
19#[derive(Copy, Clone, PartialEq, Eq, Hash, PartialOrd, Ord)]
20pub struct Loop(u32);
21entity_impl!(Loop, "loop");
22
23/// Loop tree information for a single function.
24///
25/// Loops are referenced by the Loop object, and for each loop you can access its header block,
26/// its eventual parent in the loop tree and all the block belonging to the loop.
27pub 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    /// Position assigned when a depth-first traversal enters this loop.
38    preorder: u32,
39    /// First position after this loop and all its descendants.
40    subtree_end: u32,
41}
42
43/// A level in a loop nest.
44#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
45pub struct LoopLevel(u8);
46impl LoopLevel {
47    const INVALID: u8 = u8::MAX;
48
49    /// Get the root level (no loop).
50    pub fn root() -> Self {
51        Self(0)
52    }
53    /// Get the loop level.
54    pub fn level(self) -> usize {
55        self.0 as usize
56    }
57    /// Invalid loop level.
58    pub fn invalid() -> Self {
59        Self(Self::INVALID)
60    }
61    /// One loop level deeper.
62    pub fn inc(self) -> Self {
63        if self.0 == (Self::INVALID - 1) {
64            self
65        } else {
66            Self(self.0 + 1)
67        }
68    }
69    /// A clamped loop level from a larger-width (usize) depth.
70    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    /// Creates a `LoopData` object with the loop header and its eventual parent in the loop tree.
86    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
97/// Methods for querying the loop analysis.
98impl LoopAnalysis {
99    /// Allocate a new blank loop analysis struct. Use `compute` to compute the loop analysis for
100    /// a function.
101    pub fn new() -> Self {
102        Self {
103            valid: false,
104            loops: PrimaryMap::new(),
105            block_loop_map: SecondaryMap::new(),
106        }
107    }
108
109    /// Returns all the loops contained in a function.
110    pub fn loops(&self) -> Keys<Loop> {
111        self.loops.keys()
112    }
113
114    /// Returns the header block of a particular loop.
115    ///
116    /// The characteristic property of a loop header block is that it dominates some of its
117    /// predecessors.
118    pub fn loop_header(&self, lp: Loop) -> Block {
119        self.loops[lp].header
120    }
121
122    /// Return the eventual parent of a loop in the loop tree.
123    pub fn loop_parent(&self, lp: Loop) -> Option<Loop> {
124        self.loops[lp].parent.expand()
125    }
126
127    /// Return the innermost common ancestor of two loops.
128    pub fn common_ancestor(&self, mut a: Loop, mut b: Loop) -> Option<Loop> {
129        loop {
130            // Because loops are ordered in RPO, a parent loop is guaranteed to
131            // have a lower index than a child loop. We can just walk up the
132            // tree until we find a common loop.
133            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    /// Return the innermost loop for a given block.
142    pub fn innermost_loop(&self, block: Block) -> Option<Loop> {
143        self.block_loop_map[block].expand()
144    }
145
146    /// Determine if a Block is a loop header. If so, return the loop.
147    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    /// Determine in constant time if a block belongs to a loop.
153    ///
154    /// Returns `true` if `block` is in loop `lp`.
155    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    /// Returns whether `child` is `parent` or one of its descendants.
164    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    /// Returns the loop-nest level of a given block.
171    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    /// Detects the loops in a function. Needs the control flow graph and the dominator tree.
179    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    /// Check if the loop analysis is in a valid state.
191    ///
192    /// Note that this doesn't perform any kind of validity checks. It simply checks if the
193    /// `compute()` method has been called since the last `clear()`. It does not check that the
194    /// loop analysis is consistent with the CFG.
195    pub fn is_valid(&self) -> bool {
196        self.valid
197    }
198
199    /// Clear all the data structures contained in the loop analysis. This will leave the
200    /// analysis in a similar state to a context returned by `new()` except that allocated
201    /// memory be retained.
202    pub fn clear(&mut self) {
203        self.loops.clear();
204        self.block_loop_map.clear();
205        self.valid = false;
206    }
207
208    // Determines if a block dominates any predecessor
209    // and thus is a loop header.
210    fn is_block_loop_header(block: Block, cfg: &ControlFlowGraph, domtree: &DominatorTree) -> bool {
211        // A block is a loop header if it dominates any of its predecessors.
212        cfg.pred_iter(block)
213            .any(|pred| domtree.block_dominates(block, pred.block))
214    }
215
216    // Traverses the CFG in reverse postorder and create a loop object for every block having a
217    // back edge.
218    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            // This block is a loop header, so we create its associated loop
224            let lp = self.loops.push(LoopData::new(block, None));
225            self.block_loop_map[block] = lp.into();
226        }
227    }
228
229    // Intended to be called after `find_loop_headers`. For each detected loop header,
230    // discovers all the block belonging to the loop and its inner loops. After a call to this
231    // function, the loop tree is fully constructed.
232    fn discover_loop_blocks(&mut self, cfg: &ControlFlowGraph, domtree: &DominatorTree) {
233        let mut stack: Vec<Block> = Vec::new();
234        // We handle each loop header in reverse order, corresponding to a pseudo postorder
235        // traversal of the graph.
236        for lp in self.loops().rev() {
237            // Push all predecessors of this header that it dominates onto the stack.
238            stack.extend(
239                cfg.pred_iter(self.loops[lp].header)
240                    .filter(|pred| {
241                        // We follow the back edges
242                        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                        // The node hasn't been visited yet, we tag it as part of the loop
251                        self.block_loop_map[node] = PackedOption::from(lp);
252                        continue_dfs = Some(node);
253                    }
254                    Some(node_loop) => {
255                        // We copy the node_loop into a mutable reference passed along the while
256                        let mut node_loop = node_loop;
257                        // The node is part of a loop, which can be lp or an inner loop
258                        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                                // We have encountered lp so we stop (already visited)
262                                break;
263                            } else {
264                                //
265                                node_loop = node_loop_parent;
266                                // We lookup the parent loop
267                                node_loop_parent_option = self.loops[node_loop].parent;
268                            }
269                        }
270                        // Now node_loop_parent is either:
271                        // - None and node_loop is an new inner loop of lp
272                        // - Some(...) and the initial node_loop was a known inner loop of lp
273                        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                                    // If lp is a one-block loop then we make sure we stop
281                                    continue_dfs = None
282                                }
283                            }
284                        }
285                    }
286                }
287                // Now we have handled the popped node and need to continue the DFS by adding the
288                // predecessors of that node
289                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            // In reverse postorder the parent has already been visited.
308            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        // Number loops when entering them in the loop forest. On exit, every
319        // descendant has been numbered, so `next` is the exclusive upper bound.
320        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        // CFG reverse postorder can place a different root between a loop and
353        // its child. Each root still needs its own disjoint subtree range.
354        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}