Struct cranelift_codegen::loop_analysis::LoopLevel

pub struct LoopLevel(_);

A level in a loop nest.

Implementations

impl LoopLevel

pub fn root() -> Self

Get the root level (no loop).

Examples found in repository

src/egraph.rs (line 394)

    fn default() -> Self {
        Self {
            loop_level: LoopLevel::root(),
        }
    }
}

impl cranelift_egraph::Analysis for Analysis {
    type L = NodeCtx;
    type Value = AnalysisValue;

    fn for_node(
        &self,
        ctx: &NodeCtx,
        n: &Node,
        values: &SecondaryMap<Id, AnalysisValue>,
    ) -> AnalysisValue {
        let loop_level = match n {
            &Node::Pure { ref args, .. } => args
                .as_slice(&ctx.args)
                .iter()
                .map(|&arg| values[arg].loop_level)
                .max()
                .unwrap_or(LoopLevel::root()),
            &Node::Load { addr, .. } => values[addr].loop_level,
            &Node::Result { value, .. } => values[value].loop_level,
            &Node::Inst { loop_level, .. } | &Node::Param { loop_level, .. } => loop_level,
        };

        AnalysisValue { loop_level }
    }

src/loop_analysis.rs (line 308)

    fn assign_loop_levels(&mut self) {
        let mut stack: SmallVec<[Loop; 8]> = smallvec![];
        for lp in self.loops.keys() {
            if self.loops[lp].level == LoopLevel::invalid() {
                stack.push(lp);
                while let Some(&lp) = stack.last() {
                    if let Some(parent) = self.loops[lp].parent.into() {
                        if self.loops[parent].level != LoopLevel::invalid() {
                            self.loops[lp].level = self.loops[parent].level.inc();
                            stack.pop();
                        } else {
                            stack.push(parent);
                        }
                    } else {
                        self.loops[lp].level = LoopLevel::root().inc();
                        stack.pop();
                    }
                }
            }
        }
    }

pub fn level(self) -> usize

Get the loop level.

Examples found in repository

src/opts.rs (line 202)

    fn at_loop_level(&mut self, eclass: Id) -> (u8, Id) {
        (
            self.egraph.egraph.analysis_value(eclass).loop_level.level() as u8,
            eclass,
        )
    }

src/egraph/node.rs (line 269)

    pub(crate) fn at_level(&self, loop_level: LoopLevel) -> Cost {
        let loop_level = std::cmp::min(2, loop_level.level());
        let multiplier = 1u32 << ((10 * loop_level) as u32);
        Cost(self.0.saturating_mul(multiplier)).finite()
    }

pub fn invalid() -> Self

Invalid loop level.

Examples found in repository

src/loop_analysis.rs (line 73)

    fn default() -> Self {
        LoopLevel::invalid()
    }
}

impl LoopData {
    /// Creates a `LoopData` object with the loop header and its eventual parent in the loop tree.
    pub fn new(header: Block, parent: Option<Loop>) -> Self {
        Self {
            header,
            parent: parent.into(),
            level: LoopLevel::invalid(),
        }
    }
}

/// Methods for querying the loop analysis.
impl LoopAnalysis {
    /// Allocate a new blank loop analysis struct. Use `compute` to compute the loop analysis for
    /// a function.
    pub fn new() -> Self {
        Self {
            valid: false,
            loops: PrimaryMap::new(),
            block_loop_map: SecondaryMap::new(),
        }
    }

    /// Returns all the loops contained in a function.
    pub fn loops(&self) -> Keys<Loop> {
        self.loops.keys()
    }

    /// Returns the header block of a particular loop.
    ///
    /// The characteristic property of a loop header block is that it dominates some of its
    /// predecessors.
    pub fn loop_header(&self, lp: Loop) -> Block {
        self.loops[lp].header
    }

    /// Return the eventual parent of a loop in the loop tree.
    pub fn loop_parent(&self, lp: Loop) -> Option<Loop> {
        self.loops[lp].parent.expand()
    }

    /// Return the innermost loop for a given block.
    pub fn innermost_loop(&self, block: Block) -> Option<Loop> {
        self.block_loop_map[block].expand()
    }

    /// Determine if a Block is a loop header. If so, return the loop.
    pub fn is_loop_header(&self, block: Block) -> Option<Loop> {
        self.innermost_loop(block)
            .filter(|&lp| self.loop_header(lp) == block)
    }

    /// Determine if a Block belongs to a loop by running a finger along the loop tree.
    ///
    /// Returns `true` if `block` is in loop `lp`.
    pub fn is_in_loop(&self, block: Block, lp: Loop) -> bool {
        let block_loop = self.block_loop_map[block];
        match block_loop.expand() {
            None => false,
            Some(block_loop) => self.is_child_loop(block_loop, lp),
        }
    }

    /// Determines if a loop is contained in another loop.
    ///
    /// `is_child_loop(child,parent)` returns `true` if and only if `child` is a child loop of
    /// `parent` (or `child == parent`).
    pub fn is_child_loop(&self, child: Loop, parent: Loop) -> bool {
        let mut finger = Some(child);
        while let Some(finger_loop) = finger {
            if finger_loop == parent {
                return true;
            }
            finger = self.loop_parent(finger_loop);
        }
        false
    }

    /// Returns the loop-nest level of a given block.
    pub fn loop_level(&self, block: Block) -> LoopLevel {
        self.innermost_loop(block)
            .map_or(LoopLevel(0), |lp| self.loops[lp].level)
    }
}

impl LoopAnalysis {
    /// Detects the loops in a function. Needs the control flow graph and the dominator tree.
    pub fn compute(&mut self, func: &Function, cfg: &ControlFlowGraph, domtree: &DominatorTree) {
        let _tt = timing::loop_analysis();
        self.loops.clear();
        self.block_loop_map.clear();
        self.block_loop_map.resize(func.dfg.num_blocks());
        self.find_loop_headers(cfg, domtree, &func.layout);
        self.discover_loop_blocks(cfg, domtree, &func.layout);
        self.assign_loop_levels();
        self.valid = true;
    }

    /// Check if the loop analysis is in a valid state.
    ///
    /// Note that this doesn't perform any kind of validity checks. It simply checks if the
    /// `compute()` method has been called since the last `clear()`. It does not check that the
    /// loop analysis is consistent with the CFG.
    pub fn is_valid(&self) -> bool {
        self.valid
    }

    /// Clear all the data structures contained in the loop analysis. This will leave the
    /// analysis in a similar state to a context returned by `new()` except that allocated
    /// memory be retained.
    pub fn clear(&mut self) {
        self.loops.clear();
        self.block_loop_map.clear();
        self.valid = false;
    }

    // Traverses the CFG in reverse postorder and create a loop object for every block having a
    // back edge.
    fn find_loop_headers(
        &mut self,
        cfg: &ControlFlowGraph,
        domtree: &DominatorTree,
        layout: &Layout,
    ) {
        // We traverse the CFG in reverse postorder
        for &block in domtree.cfg_postorder().iter().rev() {
            for BlockPredecessor {
                inst: pred_inst, ..
            } in cfg.pred_iter(block)
            {
                // If the block dominates one of its predecessors it is a back edge
                if domtree.dominates(block, pred_inst, layout) {
                    // This block is a loop header, so we create its associated loop
                    let lp = self.loops.push(LoopData::new(block, None));
                    self.block_loop_map[block] = lp.into();
                    break;
                    // We break because we only need one back edge to identify a loop header.
                }
            }
        }
    }

    // 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.
    fn discover_loop_blocks(
        &mut self,
        cfg: &ControlFlowGraph,
        domtree: &DominatorTree,
        layout: &Layout,
    ) {
        let mut stack: Vec<Block> = Vec::new();
        // We handle each loop header in reverse order, corresponding to a pseudo postorder
        // traversal of the graph.
        for lp in self.loops().rev() {
            for BlockPredecessor {
                block: pred,
                inst: pred_inst,
            } in cfg.pred_iter(self.loops[lp].header)
            {
                // We follow the back edges
                if domtree.dominates(self.loops[lp].header, pred_inst, layout) {
                    stack.push(pred);
                }
            }
            while let Some(node) = stack.pop() {
                let continue_dfs: Option<Block>;
                match self.block_loop_map[node].expand() {
                    None => {
                        // The node hasn't been visited yet, we tag it as part of the loop
                        self.block_loop_map[node] = PackedOption::from(lp);
                        continue_dfs = Some(node);
                    }
                    Some(node_loop) => {
                        // We copy the node_loop into a mutable reference passed along the while
                        let mut node_loop = node_loop;
                        // The node is part of a loop, which can be lp or an inner loop
                        let mut node_loop_parent_option = self.loops[node_loop].parent;
                        while let Some(node_loop_parent) = node_loop_parent_option.expand() {
                            if node_loop_parent == lp {
                                // We have encountered lp so we stop (already visited)
                                break;
                            } else {
                                //
                                node_loop = node_loop_parent;
                                // We lookup the parent loop
                                node_loop_parent_option = self.loops[node_loop].parent;
                            }
                        }
                        // Now node_loop_parent is either:
                        // - None and node_loop is an new inner loop of lp
                        // - Some(...) and the initial node_loop was a known inner loop of lp
                        match node_loop_parent_option.expand() {
                            Some(_) => continue_dfs = None,
                            None => {
                                if node_loop != lp {
                                    self.loops[node_loop].parent = lp.into();
                                    continue_dfs = Some(self.loops[node_loop].header)
                                } else {
                                    // If lp is a one-block loop then we make sure we stop
                                    continue_dfs = None
                                }
                            }
                        }
                    }
                }
                // Now we have handled the popped node and need to continue the DFS by adding the
                // predecessors of that node
                if let Some(continue_dfs) = continue_dfs {
                    for BlockPredecessor { block: pred, .. } in cfg.pred_iter(continue_dfs) {
                        stack.push(pred)
                    }
                }
            }
        }
    }

    fn assign_loop_levels(&mut self) {
        let mut stack: SmallVec<[Loop; 8]> = smallvec![];
        for lp in self.loops.keys() {
            if self.loops[lp].level == LoopLevel::invalid() {
                stack.push(lp);
                while let Some(&lp) = stack.last() {
                    if let Some(parent) = self.loops[lp].parent.into() {
                        if self.loops[parent].level != LoopLevel::invalid() {
                            self.loops[lp].level = self.loops[parent].level.inc();
                            stack.pop();
                        } else {
                            stack.push(parent);
                        }
                    } else {
                        self.loops[lp].level = LoopLevel::root().inc();
                        stack.pop();
                    }
                }
            }
        }
    }

pub fn inc(self) -> Self

One loop level deeper.

Examples found in repository

src/loop_analysis.rs (line 302)

    fn assign_loop_levels(&mut self) {
        let mut stack: SmallVec<[Loop; 8]> = smallvec![];
        for lp in self.loops.keys() {
            if self.loops[lp].level == LoopLevel::invalid() {
                stack.push(lp);
                while let Some(&lp) = stack.last() {
                    if let Some(parent) = self.loops[lp].parent.into() {
                        if self.loops[parent].level != LoopLevel::invalid() {
                            self.loops[lp].level = self.loops[parent].level.inc();
                            stack.pop();
                        } else {
                            stack.push(parent);
                        }
                    } else {
                        self.loops[lp].level = LoopLevel::root().inc();
                        stack.pop();
                    }
                }
            }
        }
    }

pub fn clamped(level: usize) -> Self

A clamped loop level from a larger-width (usize) depth.

Trait Implementations

impl Clone for LoopLevel

fn clone(&self) -> LoopLevel

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for LoopLevel

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl Default for LoopLevel

fn default() -> Self

Returns the “default value” for a type.

impl Hash for LoopLevel

fn hash<__H: Hasher>(&self, state: &mut __H)

Feeds this value into the given Hasher.

fn hash_slice<H>(data: &[Self], state: &mut H)where
    H: Hasher,
    Self: Sized,

Feeds a slice of this type into the given Hasher.

impl Ord for LoopLevel

fn cmp(&self, other: &LoopLevel) -> Ordering

This method returns an Ordering between self and other.

fn max(self, other: Self) -> Selfwhere
    Self: Sized,

Compares and returns the maximum of two values.

fn min(self, other: Self) -> Selfwhere
    Self: Sized,

Compares and returns the minimum of two values.

fn clamp(self, min: Self, max: Self) -> Selfwhere
    Self: Sized + PartialOrd<Self>,

Restrict a value to a certain interval.

impl PartialEq<LoopLevel> for LoopLevel

fn eq(&self, other: &LoopLevel) -> bool

This method tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

This method tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl PartialOrd<LoopLevel> for LoopLevel

fn partial_cmp(&self, other: &LoopLevel) -> Option<Ordering>

This method returns an ordering between self and other values if one exists.

fn lt(&self, other: &Rhs) -> bool

This method tests less than (for self and other) and is used by the < operator.

fn le(&self, other: &Rhs) -> bool

This method tests less than or equal to (for self and other) and is used by the <= operator.

fn gt(&self, other: &Rhs) -> bool

This method tests greater than (for self and other) and is used by the > operator.

fn ge(&self, other: &Rhs) -> bool

This method tests greater than or equal to (for self and other) and is used by the >= operator.

impl Copy for LoopLevel

impl Eq for LoopLevel

impl StructuralEq for LoopLevel

impl StructuralPartialEq for LoopLevel