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

//! This module contains stuff related to preserving and using information from the initial C
//! source to better decide when to produce `Multiple` structures instead of `Loop` structures.
//! By default, relooper always makes loops. This sometimes leads to some pretty ugly (but correct)
//! translations.
//!
//! For instance,
//!
//! ```c
//! if (i > 5) {
//!     while (i > 0) {
//!         i -= 3;
//!     }
//! }
//! ```
//!
//! gets translated to
//!
//! ```rust
//! let mut current_block: &'static str;
//! if i > 5i32 { current_block = "s_7"; } else { current_block = "s_14"; }
//! loop  {
//!     match current_block {
//!         "s_7" => {
//!             if !(i > 0i32) { current_block = "s_14"; continue ; }
//!             i -= 3i32;
//!             current_block = "s_7";
//!         }
//!         _ => { return; }
//!     }
//! };
//! ```
//!
//! We work around this by keeping track of branching points in the initial C source, along with all
//! of the labels that are encountered in the arms of these branches leading back to the join label.
//! We can use this information to sometimes tell relooper to make a `Multiple` structure instead of
//! a `Loop` one.
//!
//! The example from above then can be translated into
//!
//! ```rust
//! if i > 5i32 {
//!     while i > 0i32 {
//!         i -= 3i32
//!     }
//! };
//! ```

#![deny(missing_docs)]

use super::*;
use indexmap::{IndexMap, IndexSet};

/// Information about branching in a CFG.
#[derive(Clone, Debug)]
pub struct MultipleInfo<Lbl: Hash + Ord> {
    /// TODO: document me
    multiples: IndexMap<
        BTreeSet<Lbl>, // an entry set (a `BTreeSet` because it satisfies `Hash`)
        (
            Lbl,                          // label where the entries join back up
            IndexMap<Lbl, IndexSet<Lbl>>, // for each entry, what labels to expect until join label
        ),
    >,
}

impl<Lbl: Hash + Ord + Clone> MultipleInfo<Lbl> {
    #[allow(missing_docs)]
    pub fn new() -> Self {
        MultipleInfo {
            multiples: IndexMap::new(),
        }
    }

    /// Merge the information from another `MultipleInfo` into this `MultipleInfo`
    pub fn absorb(&mut self, other: MultipleInfo<Lbl>) {
        self.multiples.extend(other.multiples);
    }

    /// Rewrite nodes to take into account a node remapping. Note that the remapping is usually
    /// going to be very much _not_ injective - the whole point of remapping is to merge some nodes.
    pub fn rewrite_blocks(&mut self, rewrites: &IndexMap<Lbl, Lbl>) -> () {
        self.multiples = self
            .multiples
            .iter()
            .filter_map(|(entries, &(ref join_lbl, ref arms))| {
                let entries: BTreeSet<Lbl> = entries
                    .iter()
                    .map(|lbl| rewrites.get(lbl).unwrap_or(lbl).clone())
                    .collect();
                let join_lbl: Lbl = rewrites.get(join_lbl).unwrap_or(join_lbl).clone();
                let arms: IndexMap<Lbl, IndexSet<Lbl>> = arms
                    .iter()
                    .map(|(arm_lbl, arm_body)| {
                        let arm_lbl: Lbl = rewrites.get(arm_lbl).unwrap_or(arm_lbl).clone();
                        let arm_body: IndexSet<Lbl> = arm_body
                            .iter()
                            .map(|lbl| rewrites.get(lbl).unwrap_or(lbl).clone())
                            .collect();
                        (arm_lbl, arm_body)
                    })
                    .collect();
                if arms.len() > 1 {
                    Some((entries, (join_lbl, arms)))
                } else {
                    None
                }
            })
            .collect();
    }

    /// Add in information about a new multiple
    pub fn add_multiple(&mut self, join: Lbl, arms: Vec<(Lbl, IndexSet<Lbl>)>) -> () {
        let entry_set: BTreeSet<Lbl> = arms.iter().map(|&(ref l, _)| l.clone()).collect();
        let arm_map: IndexMap<Lbl, IndexSet<Lbl>> = arms.into_iter().collect();

        if arm_map.len() > 1 {
            self.multiples.insert(entry_set, (join, arm_map));
        }
    }

    /// Look up the multiple, if there is one, which corresponds to the given set of entry labels.
    pub fn get_multiple<'a>(
        &'a self,
        entries: &BTreeSet<Lbl>,
    ) -> Option<&'a (Lbl, IndexMap<Lbl, IndexSet<Lbl>>)> {
        self.multiples.get(entries)
    }
}