Struct Loops

Source

pub struct Loops { /* private fields */ }

Expand description

The loops of a function, nested.

Implementations§

Source §

impl Loops

Source

pub fn new(cfg: &Cfg, doms: &Dominators) -> Self

Finds the loops.

Linear in the graph per level of nesting, so linear with a small constant on the code people write. Section 7.8 says this is not the part of loop analysis to worry about.

Source

pub fn count(&self) -> usize

How many loops there are, counting nested ones.

Source

pub fn all(&self) -> impl Iterator<Item = LoopId> + use<>

Every loop, outer before inner.

Source

pub fn roots(&self) -> &[LoopId]

The loops nothing encloses.

The one block every path into the loop arrives at.

Source

pub fn blocks(&self, id: LoopId) -> &[Block] ⓘ

Every block in the loop, including the blocks of the loops nested in it.

Source

pub fn latches(&self, id: LoopId) -> &[Block] ⓘ

The blocks with an edge back to the header.

Canonical form wants exactly one of these, and section 7.3 says why: it is what makes “the last thing that happens in an iteration” a place rather than a question.

Source

pub fn exits(&self, id: LoopId) -> &[Exit]

Every edge that leaves the loop.

Source

pub fn parent(&self, id: LoopId) -> Option<LoopId>

The loop this one is nested in.

Source

pub fn children(&self, id: LoopId) -> &[LoopId]

The loops nested directly in this one.

Source

pub fn depth(&self, id: LoopId) -> u32

How many loops enclose this one, counting from zero for one nothing encloses.

Source

pub fn innermost(&self, block: Block) -> Option<LoopId>

The innermost loop holding this block, if any holds it.

Source

pub fn contains(&self, id: LoopId, block: Block) -> bool

Whether the block is in this loop or in a loop nested in it.

Source

pub fn preheader(&self, cfg: &Cfg, id: LoopId) -> Option<Block>

The block outside the loop that every path in comes through, when there is exactly one such block and its only successor is the header.

This is the preheader of section 7.3, which is where loop invariant code motion puts what it hoists. None means the loop is not in canonical form yet, and the answer is to run the canonicalizer rather than to split an edge here.

Source

pub fn irreducible(&self) -> &[Block] ⓘ

Blocks that are in a cycle and in no natural loop.

These are the irreducible regions of section 7.1, which is what goto into a loop body and some state machines written as a switch inside a for produce. rucc does not turn them into reducible ones: node splitting can blow up code size exponentially and the payoff is a handful of loop optimizations applying to code that is rare and usually cold. GCC does not do it either. The analysis reports them, the loop passes decline them, and the value level passes are unaffected because they only need dominance.

The search stops at an irreducible region rather than looking inside it, so a back edge buried in one does not become a loop even when its head dominates its tail. That loses a self loop inside a two entry region and nothing else anyone has produced, and it loses nothing in practice because a loop pass skips those blocks either way. What it buys is that “in a loop” and “irreducible” are decided by one walk, so they cannot disagree.

Source

pub fn is_irreducible(&self, block: Block) -> bool

Whether this block is in a cycle that is not a natural loop.

Source

pub fn is_invariant(&self, func: &Func, id: LoopId, value: Value) -> bool

Whether the value is the same on every iteration of this loop.

The second of the four questions section 7.6 says this analysis answers. A value is invariant when what defines it is outside the loop, which covers the function’s arguments and everything computed before the loop was entered. A value defined inside can still be invariant, when everything it reads is, and answering that is a walk this deliberately does not do: the caller that wants it is loop invariant code motion, which has to walk the body in order anyway and gets the transitive answer for free as it goes.

Source

pub fn problems(&self, cfg: &Cfg, doms: &Dominators) -> Vec<String>

What is wrong with the forest, which on a forest this built is nothing.

Section 7.2 asks for the equivalent of GCC’s verify_loop_structure, and it is a separate thing from document 04.3’s check that a pass did not lie about what it preserved. That one catches a pass claiming to have kept the forest when it changed the graph under it. This one catches a pass that rebuilt the forest into something malformed, which is a different mistake and is the one that follows from an edit near a header.

This does not check canonical form. A preheader, a single latch, loop-closed SSA and a dedicated exit are what document 26’s canonicalizer establishes before the loop pipeline runs, and a forest read off an arbitrary function has none of them.