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

//! Performs a simple taint analysis, to find all live ranges that are reftyped.

use crate::data_structures::{
    InstPoint, Map, MoveInfo, MoveInfoElem, RangeFrag, RangeFragIx, RangeId, RealRange,
    RealRangeIx, Reg, RegClass, RegToRangesMaps, TypedIxVec, VirtualRange, VirtualRangeIx,
    VirtualReg,
};
use crate::sparse_set::{SparseSet, SparseSetU};

use log::debug;
use smallvec::SmallVec;

pub fn do_reftypes_analysis(
    // From dataflow/liveness analysis.  Modified by setting their is_ref bit.
    rlr_env: &mut TypedIxVec<RealRangeIx, RealRange>,
    vlr_env: &mut TypedIxVec<VirtualRangeIx, VirtualRange>,
    // From dataflow analysis
    frag_env: &TypedIxVec<RangeFragIx, RangeFrag>,
    reg_to_ranges_maps: &RegToRangesMaps,
    move_info: &MoveInfo,
    // As supplied by the client
    reftype_class: RegClass,
    reftyped_vregs: &Vec<VirtualReg>,
) {
    // Helper: find the RangeId (RealRange or VirtualRange) for a register at an InstPoint.
    let find_range_id_for_reg = |pt: InstPoint, reg: Reg| -> RangeId {
        if reg.is_real() {
            for &rlrix in &reg_to_ranges_maps.rreg_to_rlrs_map[reg.get_index() as usize] {
                if rlr_env[rlrix].sorted_frags.contains_pt(frag_env, pt) {
                    return RangeId::new_real(rlrix);
                }
            }
        } else {
            for &vlrix in &reg_to_ranges_maps.vreg_to_vlrs_map[reg.get_index() as usize] {
                if vlr_env[vlrix].sorted_frags.contains_pt(pt) {
                    return RangeId::new_virtual(vlrix);
                }
            }
        }
        panic!("do_reftypes_analysis::find_range_for_reg: can't find range");
    };

    // The game here is: starting with `reftyped_vregs`, find *all* the VirtualRanges and
    // RealRanges to which refness can flow, via instructions which the client's `is_move`
    // function considers to be moves.

    // This is done in three stages:
    //
    // (1) Create a mapping from source (virtual or real) ranges to sets of destination ranges.
    //     We have `move_info`, which tells us which (virtual or real) regs are connected by
    //     moves.  However, that's not directly useful -- we need to know which *ranges* are
    //     connected by moves.  `move_info` as supplied helpfully indicates both source and
    //     destination regs and ranges, so we can simply use that.
    //
    // (2) Similarly, convert `reftyped_vregs` into a set of reftyped ranges by consulting
    //     `reg_to_ranges_maps`.
    //
    // (3) Compute the transitive closure of (1) starting from the ranges in (2).  This is done
    //     by a depth first search of the graph implied by (1).

    // ====== Compute (1) above ======
    // Each entry in `succ` maps from `src` to a `SparseSet<dsts>`, so to speak.  That is, for
    // `d1`, `d2`, etc, in `dsts`, the function contains moves `d1 := src`, `d2 := src`, etc.
    let mut succ = Map::<RangeId, SparseSetU<[RangeId; 4]>>::default();
    for &MoveInfoElem { dst, src, iix, .. } in &move_info.moves {
        // Don't waste time processing moves which can't possibly be of reftyped values.
        debug_assert!(dst.get_class() == src.get_class());
        if dst.get_class() != reftype_class {
            continue;
        }
        let src_range = find_range_id_for_reg(InstPoint::new_use(iix), src);
        let dst_range = find_range_id_for_reg(InstPoint::new_def(iix), dst);
        debug!(
            "move from {:?} (range {:?}) to {:?} (range {:?}) at inst {:?}",
            src, src_range, dst, dst_range, iix
        );
        match succ.get_mut(&src_range) {
            Some(dst_ranges) => dst_ranges.insert(dst_range),
            None => {
                // Re `; 4`: we expect most copies copy a register to only a few destinations.
                let mut dst_ranges = SparseSetU::<[RangeId; 4]>::empty();
                dst_ranges.insert(dst_range);
                let r = succ.insert(src_range, dst_ranges);
                assert!(r.is_none());
            }
        }
    }

    // ====== Compute (2) above ======
    let mut reftyped_ranges = SparseSet::<RangeId>::empty();
    for vreg in reftyped_vregs {
        // If this fails, the client has been telling is that some virtual reg is reftyped, yet
        // it doesn't belong to the class of regs that it claims can carry refs.  So the client
        // is buggy.
        debug_assert!(vreg.get_class() == reftype_class);
        for vlrix in &reg_to_ranges_maps.vreg_to_vlrs_map[vreg.get_index()] {
            debug!("range {:?} is reffy due to reffy vreg {:?}", vlrix, vreg);
            reftyped_ranges.insert(RangeId::new_virtual(*vlrix));
        }
    }

    // ====== Compute (3) above ======
    // Almost all chains of copies will be less than 64 long, I would guess.
    let mut stack = SmallVec::<[RangeId; 64]>::new();
    let mut visited = reftyped_ranges.clone();
    for start_point_range in reftyped_ranges.iter() {
        // Perform DFS from `start_point_range`.
        stack.clear();
        stack.push(*start_point_range);
        while let Some(src_range) = stack.pop() {
            visited.insert(src_range);
            if let Some(dst_ranges) = succ.get(&src_range) {
                for dst_range in dst_ranges.iter() {
                    if !visited.contains(*dst_range) {
                        stack.push(*dst_range);
                    }
                }
            }
        }
    }

    // Finally, annotate rlr_env/vlr_env with the results of the analysis.  (That was the whole
    // point!)
    for range in visited.iter() {
        if range.is_real() {
            let rrange = &mut rlr_env[range.to_real()];
            debug_assert!(!rrange.is_ref);
            debug!(" -> rrange {:?} is reffy", range.to_real());
            rrange.is_ref = true;
        } else {
            let vrange = &mut vlr_env[range.to_virtual()];
            debug_assert!(!vrange.is_ref);
            debug!(" -> rrange {:?} is reffy", range.to_virtual());
            vrange.is_ref = true;
        }
    }
}