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
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164

//! Program points.

use crate::entity::EntityRef;
use crate::ir::{Block, Inst, ValueDef};
use core::cmp;
use core::fmt;
use core::u32;

/// A `ProgramPoint` represents a position in a function where the live range of an SSA value can
/// begin or end. It can be either:
///
/// 1. An instruction or
/// 2. A block header.
///
/// This corresponds more or less to the lines in the textual form of Cranelift IR.
#[derive(PartialEq, Eq, Clone, Copy)]
pub struct ProgramPoint(u32);

impl From<Inst> for ProgramPoint {
    fn from(inst: Inst) -> Self {
        let idx = inst.index();
        debug_assert!(idx < (u32::MAX / 2) as usize);
        Self((idx * 2) as u32)
    }
}

impl From<Block> for ProgramPoint {
    fn from(block: Block) -> Self {
        let idx = block.index();
        debug_assert!(idx < (u32::MAX / 2) as usize);
        Self((idx * 2 + 1) as u32)
    }
}

impl From<ValueDef> for ProgramPoint {
    fn from(def: ValueDef) -> Self {
        match def {
            ValueDef::Result(inst, _) => inst.into(),
            ValueDef::Param(block, _) => block.into(),
        }
    }
}

/// An expanded program point directly exposes the variants, but takes twice the space to
/// represent.
#[derive(PartialEq, Eq, Clone, Copy)]
pub enum ExpandedProgramPoint {
    /// An instruction in the function.
    Inst(Inst),
    /// A block header.
    Block(Block),
}

impl ExpandedProgramPoint {
    /// Get the instruction we know is inside.
    pub fn unwrap_inst(self) -> Inst {
        match self {
            Self::Inst(x) => x,
            Self::Block(x) => panic!("expected inst: {}", x),
        }
    }
}

impl From<Inst> for ExpandedProgramPoint {
    fn from(inst: Inst) -> Self {
        Self::Inst(inst)
    }
}

impl From<Block> for ExpandedProgramPoint {
    fn from(block: Block) -> Self {
        Self::Block(block)
    }
}

impl From<ValueDef> for ExpandedProgramPoint {
    fn from(def: ValueDef) -> Self {
        match def {
            ValueDef::Result(inst, _) => inst.into(),
            ValueDef::Param(block, _) => block.into(),
        }
    }
}

impl From<ProgramPoint> for ExpandedProgramPoint {
    fn from(pp: ProgramPoint) -> Self {
        if pp.0 & 1 == 0 {
            Self::Inst(Inst::from_u32(pp.0 / 2))
        } else {
            Self::Block(Block::from_u32(pp.0 / 2))
        }
    }
}

impl fmt::Display for ExpandedProgramPoint {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        match *self {
            Self::Inst(x) => write!(f, "{}", x),
            Self::Block(x) => write!(f, "{}", x),
        }
    }
}

impl fmt::Display for ProgramPoint {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        let epp: ExpandedProgramPoint = (*self).into();
        epp.fmt(f)
    }
}

impl fmt::Debug for ExpandedProgramPoint {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        write!(f, "ExpandedProgramPoint({})", self)
    }
}

impl fmt::Debug for ProgramPoint {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        write!(f, "ProgramPoint({})", self)
    }
}

/// Context for ordering program points.
///
/// `ProgramPoint` objects don't carry enough information to be ordered independently, they need a
/// context providing the program order.
pub trait ProgramOrder {
    /// Compare the program points `a` and `b` relative to this program order.
    ///
    /// Return `Less` if `a` appears in the program before `b`.
    ///
    /// This is declared as a generic such that it can be called with `Inst` and `Block` arguments
    /// directly. Depending on the implementation, there is a good chance performance will be
    /// improved for those cases where the type of either argument is known statically.
    fn cmp<A, B>(&self, a: A, b: B) -> cmp::Ordering
    where
        A: Into<ExpandedProgramPoint>,
        B: Into<ExpandedProgramPoint>;

    /// Is the range from `inst` to `block` just the gap between consecutive blocks?
    ///
    /// This returns true if `inst` is the terminator in the block immediately before `block`.
    fn is_block_gap(&self, inst: Inst, block: Block) -> bool;
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::entity::EntityRef;
    use crate::ir::{Block, Inst};
    use alloc::string::ToString;

    #[test]
    fn convert() {
        let i5 = Inst::new(5);
        let b3 = Block::new(3);

        let pp1: ProgramPoint = i5.into();
        let pp2: ProgramPoint = b3.into();

        assert_eq!(pp1.to_string(), "inst5");
        assert_eq!(pp2.to_string(), "block3");
    }
}