Adding upstream version 86.0.1.upstream/86.0.1upstream

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 350 insertions, 0 deletions

diff --git a/third_party/rust/cranelift-codegen/src/flowgraph.rs b/third_party/rust/cranelift-codegen/src/flowgraph.rs
new file mode 100644
index 0000000000..9c6ccbaea5
--- /dev/null
+++ b/third_party/rust/cranelift-codegen/src/flowgraph.rs
@@ -0,0 +1,350 @@
+//! A control flow graph represented as mappings of basic blocks to their predecessors
+//! and successors.
+//!
+//! Successors are represented as basic blocks while predecessors are represented by basic
+//! blocks. Basic blocks are denoted by tuples of block and branch/jump instructions. Each
+//! predecessor tuple corresponds to the end of a basic block.
+//!
+//! ```c
+//!     Block0:
+//!         ...          ; beginning of basic block
+//!
+//!         ...
+//!
+//!         brz vx, Block1 ; end of basic block
+//!
+//!         ...          ; beginning of basic block
+//!
+//!         ...
+//!
+//!         jmp Block2     ; end of basic block
+//! ```
+//!
+//! Here `Block1` and `Block2` would each have a single predecessor denoted as `(Block0, brz)`
+//! and `(Block0, jmp Block2)` respectively.
+
+use crate::bforest;
+use crate::entity::SecondaryMap;
+use crate::ir::instructions::BranchInfo;
+use crate::ir::{Block, Function, Inst};
+use crate::timing;
+use core::mem;
+
+/// A basic block denoted by its enclosing Block and last instruction.
+#[derive(Debug, PartialEq, Eq)]
+pub struct BlockPredecessor {
+    /// Enclosing Block key.
+    pub block: Block,
+    /// Last instruction in the basic block.
+    pub inst: Inst,
+}
+
+impl BlockPredecessor {
+    /// Convenient method to construct new BlockPredecessor.
+    pub fn new(block: Block, inst: Inst) -> Self {
+        Self { block, inst }
+    }
+}
+
+/// A container for the successors and predecessors of some Block.
+#[derive(Clone, Default)]
+struct CFGNode {
+    /// Instructions that can branch or jump to this block.
+    ///
+    /// This maps branch instruction -> predecessor block which is redundant since the block containing
+    /// the branch instruction is available from the `layout.inst_block()` method. We store the
+    /// redundant information because:
+    ///
+    /// 1. Many `pred_iter()` consumers want the block anyway, so it is handily available.
+    /// 2. The `invalidate_block_successors()` may be called *after* branches have been removed from
+    ///    their block, but we still need to remove them form the old block predecessor map.
+    ///
+    /// The redundant block stored here is always consistent with the CFG successor lists, even after
+    /// the IR has been edited.
+    pub predecessors: bforest::Map<Inst, Block>,
+
+    /// Set of blocks that are the targets of branches and jumps in this block.
+    /// The set is ordered by block number, indicated by the `()` comparator type.
+    pub successors: bforest::Set<Block>,
+}
+
+/// The Control Flow Graph maintains a mapping of blocks to their predecessors
+/// and successors where predecessors are basic blocks and successors are
+/// basic blocks.
+pub struct ControlFlowGraph {
+    data: SecondaryMap<Block, CFGNode>,
+    pred_forest: bforest::MapForest<Inst, Block>,
+    succ_forest: bforest::SetForest<Block>,
+    valid: bool,
+}
+
+impl ControlFlowGraph {
+    /// Allocate a new blank control flow graph.
+    pub fn new() -> Self {
+        Self {
+            data: SecondaryMap::new(),
+            valid: false,
+            pred_forest: bforest::MapForest::new(),
+            succ_forest: bforest::SetForest::new(),
+        }
+    }
+
+    /// Clear all data structures in this control flow graph.
+    pub fn clear(&mut self) {
+        self.data.clear();
+        self.pred_forest.clear();
+        self.succ_forest.clear();
+        self.valid = false;
+    }
+
+    /// Allocate and compute the control flow graph for `func`.
+    pub fn with_function(func: &Function) -> Self {
+        let mut cfg = Self::new();
+        cfg.compute(func);
+        cfg
+    }
+
+    /// Compute the control flow graph of `func`.
+    ///
+    /// This will clear and overwrite any information already stored in this data structure.
+    pub fn compute(&mut self, func: &Function) {
+        let _tt = timing::flowgraph();
+        self.clear();
+        self.data.resize(func.dfg.num_blocks());
+
+        for block in &func.layout {
+            self.compute_block(func, block);
+        }
+
+        self.valid = true;
+    }
+
+    fn compute_block(&mut self, func: &Function, block: Block) {
+        for inst in func.layout.block_likely_branches(block) {
+            match func.dfg.analyze_branch(inst) {
+                BranchInfo::SingleDest(dest, _) => {
+                    self.add_edge(block, inst, dest);
+                }
+                BranchInfo::Table(jt, dest) => {
+                    if let Some(dest) = dest {
+                        self.add_edge(block, inst, dest);
+                    }
+                    for dest in func.jump_tables[jt].iter() {
+                        self.add_edge(block, inst, *dest);
+                    }
+                }
+                BranchInfo::NotABranch => {}
+            }
+        }
+    }
+
+    fn invalidate_block_successors(&mut self, block: Block) {
+        // Temporarily take ownership because we need mutable access to self.data inside the loop.
+        // Unfortunately borrowck cannot see that our mut accesses to predecessors don't alias
+        // our iteration over successors.
+        let mut successors = mem::replace(&mut self.data[block].successors, Default::default());
+        for succ in successors.iter(&self.succ_forest) {
+            self.data[succ]
+                .predecessors
+                .retain(&mut self.pred_forest, |_, &mut e| e != block);
+        }
+        successors.clear(&mut self.succ_forest);
+    }
+
+    /// Recompute the control flow graph of `block`.
+    ///
+    /// This is for use after modifying instructions within a specific block. It recomputes all edges
+    /// from `block` while leaving edges to `block` intact. Its functionality a subset of that of the
+    /// more expensive `compute`, and should be used when we know we don't need to recompute the CFG
+    /// from scratch, but rather that our changes have been restricted to specific blocks.
+    pub fn recompute_block(&mut self, func: &Function, block: Block) {
+        debug_assert!(self.is_valid());
+        self.invalidate_block_successors(block);
+        self.compute_block(func, block);
+    }
+
+    fn add_edge(&mut self, from: Block, from_inst: Inst, to: Block) {
+        self.data[from]
+            .successors
+            .insert(to, &mut self.succ_forest, &());
+        self.data[to]
+            .predecessors
+            .insert(from_inst, from, &mut self.pred_forest, &());
+    }
+
+    /// Get an iterator over the CFG predecessors to `block`.
+    pub fn pred_iter(&self, block: Block) -> PredIter {
+        PredIter(self.data[block].predecessors.iter(&self.pred_forest))
+    }
+
+    /// Get an iterator over the CFG successors to `block`.
+    pub fn succ_iter(&self, block: Block) -> SuccIter {
+        debug_assert!(self.is_valid());
+        self.data[block].successors.iter(&self.succ_forest)
+    }
+
+    /// Check if the CFG 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
+    /// CFG is consistent with the function.
+    pub fn is_valid(&self) -> bool {
+        self.valid
+    }
+}
+
+/// An iterator over block predecessors. The iterator type is `BlockPredecessor`.
+///
+/// Each predecessor is an instruction that branches to the block.
+pub struct PredIter<'a>(bforest::MapIter<'a, Inst, Block>);
+
+impl<'a> Iterator for PredIter<'a> {
+    type Item = BlockPredecessor;
+
+    fn next(&mut self) -> Option<BlockPredecessor> {
+        self.0.next().map(|(i, e)| BlockPredecessor::new(e, i))
+    }
+}
+
+/// An iterator over block successors. The iterator type is `Block`.
+pub type SuccIter<'a> = bforest::SetIter<'a, Block>;
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+    use crate::cursor::{Cursor, FuncCursor};
+    use crate::ir::{types, Function, InstBuilder};
+    use alloc::vec::Vec;
+
+    #[test]
+    fn empty() {
+        let func = Function::new();
+        ControlFlowGraph::with_function(&func);
+    }
+
+    #[test]
+    fn no_predecessors() {
+        let mut func = Function::new();
+        let block0 = func.dfg.make_block();
+        let block1 = func.dfg.make_block();
+        let block2 = func.dfg.make_block();
+        func.layout.append_block(block0);
+        func.layout.append_block(block1);
+        func.layout.append_block(block2);
+
+        let cfg = ControlFlowGraph::with_function(&func);
+
+        let mut fun_blocks = func.layout.blocks();
+        for block in func.layout.blocks() {
+            assert_eq!(block, fun_blocks.next().unwrap());
+            assert_eq!(cfg.pred_iter(block).count(), 0);
+            assert_eq!(cfg.succ_iter(block).count(), 0);
+        }
+    }
+
+    #[test]
+    fn branches_and_jumps() {
+        let mut func = Function::new();
+        let block0 = func.dfg.make_block();
+        let cond = func.dfg.append_block_param(block0, types::I32);
+        let block1 = func.dfg.make_block();
+        let block2 = func.dfg.make_block();
+
+        let br_block0_block2;
+        let br_block1_block1;
+        let jmp_block0_block1;
+        let jmp_block1_block2;
+
+        {
+            let mut cur = FuncCursor::new(&mut func);
+
+            cur.insert_block(block0);
+            br_block0_block2 = cur.ins().brnz(cond, block2, &[]);
+            jmp_block0_block1 = cur.ins().jump(block1, &[]);
+
+            cur.insert_block(block1);
+            br_block1_block1 = cur.ins().brnz(cond, block1, &[]);
+            jmp_block1_block2 = cur.ins().jump(block2, &[]);
+
+            cur.insert_block(block2);
+        }
+
+        let mut cfg = ControlFlowGraph::with_function(&func);
+
+        {
+            let block0_predecessors = cfg.pred_iter(block0).collect::<Vec<_>>();
+            let block1_predecessors = cfg.pred_iter(block1).collect::<Vec<_>>();
+            let block2_predecessors = cfg.pred_iter(block2).collect::<Vec<_>>();
+
+            let block0_successors = cfg.succ_iter(block0).collect::<Vec<_>>();
+            let block1_successors = cfg.succ_iter(block1).collect::<Vec<_>>();
+            let block2_successors = cfg.succ_iter(block2).collect::<Vec<_>>();
+
+            assert_eq!(block0_predecessors.len(), 0);
+            assert_eq!(block1_predecessors.len(), 2);
+            assert_eq!(block2_predecessors.len(), 2);
+
+            assert_eq!(
+                block1_predecessors.contains(&BlockPredecessor::new(block0, jmp_block0_block1)),
+                true
+            );
+            assert_eq!(
+                block1_predecessors.contains(&BlockPredecessor::new(block1, br_block1_block1)),
+                true
+            );
+            assert_eq!(
+                block2_predecessors.contains(&BlockPredecessor::new(block0, br_block0_block2)),
+                true
+            );
+            assert_eq!(
+                block2_predecessors.contains(&BlockPredecessor::new(block1, jmp_block1_block2)),
+                true
+            );
+
+            assert_eq!(block0_successors, [block1, block2]);
+            assert_eq!(block1_successors, [block1, block2]);
+            assert_eq!(block2_successors, []);
+        }
+
+        // Change some instructions and recompute block0
+        func.dfg.replace(br_block0_block2).brnz(cond, block1, &[]);
+        func.dfg.replace(jmp_block0_block1).return_(&[]);
+        cfg.recompute_block(&mut func, block0);
+        let br_block0_block1 = br_block0_block2;
+
+        {
+            let block0_predecessors = cfg.pred_iter(block0).collect::<Vec<_>>();
+            let block1_predecessors = cfg.pred_iter(block1).collect::<Vec<_>>();
+            let block2_predecessors = cfg.pred_iter(block2).collect::<Vec<_>>();
+
+            let block0_successors = cfg.succ_iter(block0);
+            let block1_successors = cfg.succ_iter(block1);
+            let block2_successors = cfg.succ_iter(block2);
+
+            assert_eq!(block0_predecessors.len(), 0);
+            assert_eq!(block1_predecessors.len(), 2);
+            assert_eq!(block2_predecessors.len(), 1);
+
+            assert_eq!(
+                block1_predecessors.contains(&BlockPredecessor::new(block0, br_block0_block1)),
+                true
+            );
+            assert_eq!(
+                block1_predecessors.contains(&BlockPredecessor::new(block1, br_block1_block1)),
+                true
+            );
+            assert_eq!(
+                block2_predecessors.contains(&BlockPredecessor::new(block0, br_block0_block2)),
+                false
+            );
+            assert_eq!(
+                block2_predecessors.contains(&BlockPredecessor::new(block1, jmp_block1_block2)),
+                true
+            );
+
+            assert_eq!(block0_successors.collect::<Vec<_>>(), [block1]);
+            assert_eq!(block1_successors.collect::<Vec<_>>(), [block1, block2]);
+            assert_eq!(block2_successors.collect::<Vec<_>>(), []);
+        }
+    }
+}