weirflow 0.1.0

GPU-first dataflow analysis primitives for Vyre and Santh compiler pipelines.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111

//! Reusable CFG fixtures for dominator-analysis tests.

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

use rand::{Rng, SeedableRng};

use crate::ssa::{try_compute_dominators, Block, Cfg};

#[derive(Clone, Debug)]
pub struct CfgFixture {
    pub node_count: u32,
    pub entry: u32,
    pub preds: Vec<Vec<u32>>,
    pub succs: Vec<Vec<u32>>,
    pub idoms: HashMap<u32, u32>,
}

pub struct DominatorFixture;

impl DominatorFixture {
    pub fn random_dag(node_count: u32, edge_probability: f64, seed: u64) -> CfgFixture {
        if node_count == 0 {
            return empty_fixture();
        }
        let mut rng = rand::rngs::StdRng::seed_from_u64(seed);
        let probability = edge_probability.clamp(0.0, 1.0);
        let mut succs = vec![Vec::new(); node_count as usize];

        for dst in 1..node_count {
            let parent = rng.random_range(0..dst);
            succs[parent as usize].push(dst);
        }
        for src in 0..node_count {
            for dst in (src + 1)..node_count {
                if rng.random::<f64>() < probability {
                    succs[src as usize].push(dst);
                }
            }
        }
        normalize_fixture(node_count, 0, succs)
    }

    pub fn random_irreducible(node_count: u32, edge_probability: f64, seed: u64) -> CfgFixture {
        let mut fixture = Self::random_dag(node_count, edge_probability, seed);
        if node_count > 1 {
            fixture.succs[(node_count - 1) as usize].push(0);
            if node_count > 2 {
                fixture.succs[(node_count - 1) as usize].push(1);
                fixture.succs[1].push(node_count - 1);
            }
            fixture = normalize_fixture(node_count, 0, fixture.succs);
        }
        fixture
    }
}

fn empty_fixture() -> CfgFixture {
    CfgFixture {
        node_count: 0,
        entry: 0,
        preds: Vec::new(),
        succs: Vec::new(),
        idoms: HashMap::new(),
    }
}

fn normalize_fixture(node_count: u32, entry: u32, mut succs: Vec<Vec<u32>>) -> CfgFixture {
    for targets in &mut succs {
        targets.retain(|target| *target < node_count);
        targets.sort_unstable();
        targets.dedup();
    }

    let mut preds = vec![Vec::new(); node_count as usize];
    for (src, targets) in succs.iter().enumerate() {
        for &dst in targets {
            preds[dst as usize].push(src as u32);
        }
    }
    for sources in &mut preds {
        sources.sort_unstable();
        sources.dedup();
    }

    let cfg = cfg_from_parts(entry, &preds, &succs);
    let idoms = try_compute_dominators(&cfg).unwrap_or_default();
    CfgFixture {
        node_count,
        entry,
        preds,
        succs,
        idoms,
    }
}

fn cfg_from_parts(entry: u32, preds: &[Vec<u32>], succs: &[Vec<u32>]) -> Cfg {
    let mut blocks = HashMap::with_capacity(succs.len());
    for id in 0..succs.len() as u32 {
        blocks.insert(
            id,
            Block {
                id,
                preds: preds[id as usize].clone(),
                succs: succs[id as usize].clone(),
                defs: HashSet::new(),
                uses: HashSet::new(),
            },
        );
    }
    Cfg { entry, blocks }
}