LoopAnalysis

LoopAnalysis.md

Step 1: Define Loop Forms

A loop in a control flow graph (CFG) can generally be classified into the following forms:

1. Single Basic Block Loop: Contains the condition and body in one block.

Example: while (condition) { body }

2. Multi-Block Loop:

Loop header: Contains the condition or start of the loop.

Loop body: One or more blocks executed during each iteration.

Exit block: A block that breaks out of the loop.

For nested loops, these forms are repeated within the body of an outer loop.

---

Rules for Loop Analysis

1. Dominance Relationship:

A block B belongs to a loop if it is dominated by the loop header and has a path back to the header (a back edge).

2. Back Edges:

A back edge exists if a successor block (header) dominates its predecessor (current).

3. Loop Header:

A block with a back edge pointing to it is a potential loop header.

4. Natural Loop:

The natural loop of a back edge (tail → header) includes:

The header.

All blocks that can reach tail without going through header.

5. Nested Loops:

A loop is nested if its blocks are a subset of another loop's blocks.

---

Code Example for Loop Analysis

Here's a Rust function for analyzing loops, including nested ones:

use std::collections::{HashSet, VecDeque};

#[derive(Debug, Clone)]
struct Loop {
    header: usize,            // Block ID of the loop header
    body: HashSet<usize>,     // All blocks in the loop
    parent: Option<usize>,    // Parent loop (for nested loops)
}

fn find_loops(cfg: &CFG) -> Vec<Loop> {
    let mut loops = Vec::new();
    let dominator_tree = cfg.compute_dominators(); // Precompute dominators
    
    // Step 1: Identify back edges
    let back_edges = cfg.find_back_edges(&dominator_tree);

    for (tail, header) in back_edges {
        // Step 2: Collect blocks forming the natural loop
        let mut loop_blocks = HashSet::new();
        let mut worklist = VecDeque::new();
        worklist.push_back(tail);

        while let Some(block) = worklist.pop_front() {
            if !loop_blocks.contains(&block) {
                loop_blocks.insert(block);
                let preds = cfg.get_predecessors(block);
                for &pred in &preds {
                    if pred != header { // Exclude header to prevent infinite loops
                        worklist.push_back(pred);
                    }
                }
            }
        }

        loop_blocks.insert(header); // Include the header in the loop

        // Step 3: Determine nesting
        let parent = loops.iter().find(|l| l.body.is_superset(&loop_blocks)).map(|l| l.header);

        loops.push(Loop {
            header,
            body: loop_blocks,
            parent,
        });
    }

    loops
}

impl CFG {
    fn find_back_edges(&self, dominator_tree: &DominatorTree) -> Vec<(usize, usize)> {
        let mut back_edges = Vec::new();
        for (block_id, successors) in self.blocks.iter().enumerate() {
            for &succ in successors {
                if dominator_tree.dominates(succ, block_id) {
                    back_edges.push((block_id, succ)); // tail → header
                }
            }
        }
        back_edges
    }

    fn compute_dominators(&self) -> DominatorTree {
        // Implement a dominator tree computation algorithm, e.g., Lengauer-Tarjan
        DominatorTree::new(self)
    }
}

---

Explanation of Code

1. Back Edge Detection:

Uses the dominator tree to identify back edges.

2. Natural Loop Construction:

Gathers all blocks that form a loop using a worklist-based traversal.

3. Nested Loops:

Checks if a loop is entirely within another loop and assigns a parent loop if so.

---