use log::{debug, info};
use std::cmp::Ordering;
use crate::analysis_main::AnalysisError;
use crate::data_structures::{BlockIx, InstIx, Range, Set, TypedIxVec};
use crate::sparse_set::{SparseSetU, SparseSetUIter};
use crate::Function;
use smallvec::SmallVec;
const CROSSCHECK_DOMS: bool = false;
pub struct InstIxToBlockIxMap {
vek: TypedIxVec<BlockIx, Range<InstIx>>,
}
impl InstIxToBlockIxMap {
#[inline(never)]
pub fn new<F: Function>(func: &F) -> Self {
let mut vek = TypedIxVec::<BlockIx, Range<InstIx>>::new();
for bix in func.blocks() {
let r: Range<InstIx> = func.block_insns(bix);
assert!(r.start() <= r.last_plus1());
vek.push(r);
}
fn cmp_ranges(r1: &Range<InstIx>, r2: &Range<InstIx>) -> Ordering {
if r1.last_plus1() <= r2.first() {
return Ordering::Less;
}
if r2.last_plus1() <= r1.first() {
return Ordering::Greater;
}
if r1.first() == r2.first() && r1.last_plus1() == r2.last_plus1() {
return Ordering::Equal;
}
panic!("InstIxToBlockIxMap::cmp_ranges: overlapping InstIx ranges!");
}
vek.sort_unstable_by(|r1, r2| cmp_ranges(r1, r2));
for i in 1..vek.len() {
let r_m1 = &vek[BlockIx::new(i - 1)];
let r_m0 = &vek[BlockIx::new(i - 0)];
assert!(r_m1.last_plus1() == r_m0.first());
}
Self { vek }
}
#[inline(never)]
pub fn map(&self, iix: InstIx) -> BlockIx {
if self.vek.len() > 0 {
let mut lo = 0isize;
let mut hi = self.vek.len() as isize - 1;
loop {
if lo > hi {
break;
}
let mid = (lo + hi) / 2;
let midv = &self.vek[BlockIx::new(mid as u32)];
if iix < midv.start() {
hi = mid - 1;
continue;
}
if iix >= midv.last_plus1() {
lo = mid + 1;
continue;
}
assert!(midv.start() <= iix && iix < midv.last_plus1());
return BlockIx::new(mid as u32);
}
}
panic!("InstIxToBlockIxMap::map: can't map {:?}", iix);
}
}
#[inline(never)]
fn calc_preds_and_succs<F: Function>(
func: &F,
num_blocks: u32,
) -> (
TypedIxVec<BlockIx, SparseSetU<[BlockIx; 4]>>,
TypedIxVec<BlockIx, SparseSetU<[BlockIx; 4]>>,
) {
info!(" calc_preds_and_succs: begin");
assert!(func.blocks().len() == num_blocks as usize);
let mut succ_map = TypedIxVec::<BlockIx, SparseSetU<[BlockIx; 4]>>::new();
for b in func.blocks() {
let mut bix_set = SparseSetU::<[BlockIx; 4]>::empty();
for bix in func.block_succs(b).iter() {
bix_set.insert(*bix);
}
succ_map.push(bix_set);
}
let mut pred_map = TypedIxVec::<BlockIx, SparseSetU<[BlockIx; 4]>>::new();
pred_map.resize(num_blocks, SparseSetU::<[BlockIx; 4]>::empty());
for (src, dst_set) in (0..).zip(succ_map.iter()) {
for dst in dst_set.iter() {
pred_map[*dst].insert(BlockIx::new(src));
}
}
assert!(pred_map.len() == num_blocks);
assert!(succ_map.len() == num_blocks);
let mut n = 0;
debug!("");
for (preds, succs) in pred_map.iter().zip(succ_map.iter()) {
debug!(
"{:<3?} preds {:<16?} succs {:?}",
BlockIx::new(n),
preds,
succs
);
n += 1;
}
info!(" calc_preds_and_succs: end");
(pred_map, succ_map)
}
#[inline(never)]
fn calc_preord_and_postord<F: Function>(
func: &F,
num_blocks: u32,
succ_map: &TypedIxVec<BlockIx, SparseSetU<[BlockIx; 4]>>,
) -> Option<(Vec<BlockIx>, Vec<BlockIx>)> {
info!(" calc_preord_and_postord: begin");
let mut pre_ord = Vec::<BlockIx>::new();
let mut post_ord = Vec::<BlockIx>::new();
let mut visited = TypedIxVec::<BlockIx, bool>::new();
visited.resize(num_blocks, false);
let mut stack = SmallVec::<[(BlockIx, SparseSetUIter<[BlockIx; 4]>); 64]>::new();
let bix_entry = func.entry_block();
visited[bix_entry] = true;
pre_ord.push(bix_entry);
stack.push((bix_entry, succ_map[bix_entry].iter()));
'outer: while let Some((bix, bix_succ_iter)) = stack.last_mut() {
while let Some(bix_next_succ) = bix_succ_iter.next() {
if !visited[*bix_next_succ] {
visited[*bix_next_succ] = true;
pre_ord.push(*bix_next_succ);
stack.push((*bix_next_succ, succ_map[*bix_next_succ].iter()));
continue 'outer;
}
}
post_ord.push(*bix);
stack.pop();
}
assert!(pre_ord.len() == post_ord.len());
assert!(pre_ord.len() <= num_blocks as usize);
if pre_ord.len() < num_blocks as usize {
info!(
" calc_preord_and_postord: invalid: {} blocks, {} reachable",
num_blocks,
pre_ord.len()
);
return None;
}
assert!(pre_ord.len() == num_blocks as usize);
assert!(post_ord.len() == num_blocks as usize);
#[cfg(debug_assertions)]
{
let mut pre_ord_sorted: Vec<BlockIx> = pre_ord.clone();
let mut post_ord_sorted: Vec<BlockIx> = post_ord.clone();
pre_ord_sorted.sort_by(|bix1, bix2| bix1.get().partial_cmp(&bix2.get()).unwrap());
post_ord_sorted.sort_by(|bix1, bix2| bix1.get().partial_cmp(&bix2.get()).unwrap());
let expected: Vec<BlockIx> = (0..num_blocks).map(|u| BlockIx::new(u)).collect();
debug_assert!(pre_ord_sorted == expected);
debug_assert!(post_ord_sorted == expected);
}
info!(" calc_preord_and_postord: end. {} blocks", num_blocks);
Some((pre_ord, post_ord))
}
#[inline(never)]
fn calc_dom_sets_slow(
num_blocks: u32,
pred_map: &TypedIxVec<BlockIx, SparseSetU<[BlockIx; 4]>>,
post_ord: &Vec<BlockIx>,
start: BlockIx,
) -> TypedIxVec<BlockIx, Set<BlockIx>> {
info!(" calc_dom_sets_slow: begin");
let mut dom_map = TypedIxVec::<BlockIx, Set<BlockIx>>::new();
{
let root: BlockIx = start;
let n_set: Set<BlockIx> =
Set::from_vec((0..num_blocks).map(|bix| BlockIx::new(bix)).collect());
let mut d_set: Set<BlockIx>;
let mut t_set: Set<BlockIx>;
dom_map.resize(num_blocks, Set::<BlockIx>::empty());
dom_map[root] = Set::unit(root);
for block_i in 0..num_blocks {
let block_ix = BlockIx::new(block_i);
if block_ix != root {
dom_map[block_ix] = n_set.clone();
}
}
let mut num_iter = 0;
loop {
num_iter += 1;
info!(" calc_dom_sets_slow: outer loop {}", num_iter);
let mut change = false;
for i in 0..num_blocks {
let block_ix = post_ord[(num_blocks - 1 - i) as usize];
if block_ix == root {
continue;
}
t_set = n_set.clone();
for pred_ix in pred_map[block_ix].iter() {
t_set.intersect(&dom_map[*pred_ix]);
}
d_set = t_set.clone();
d_set.insert(block_ix);
if !d_set.equals(&dom_map[block_ix]) {
change = true;
dom_map[block_ix] = d_set;
}
}
if !change {
break;
}
}
}
debug!("");
let mut block_ix = 0;
for dom_set in dom_map.iter() {
debug!("{:<3?} dom_set {:<16?}", BlockIx::new(block_ix), dom_set);
block_ix += 1;
}
info!(" calc_dom_sets_slow: end");
dom_map
}
const DT_INVALID_POSTORD: u32 = 0xFFFF_FFFF;
const DT_INVALID_BLOCKIX: BlockIx = BlockIx::BlockIx(0xFFFF_FFFF);
fn dt_merge_sets(
idom: &TypedIxVec<BlockIx, BlockIx>,
bix2rpostord: &TypedIxVec<BlockIx, u32>,
mut node1: BlockIx,
mut node2: BlockIx,
) -> BlockIx {
while node1 != node2 {
if node1 == DT_INVALID_BLOCKIX || node2 == DT_INVALID_BLOCKIX {
return DT_INVALID_BLOCKIX;
}
let rpo1 = bix2rpostord[node1];
let rpo2 = bix2rpostord[node2];
if rpo1 > rpo2 {
node1 = idom[node1];
} else if rpo2 > rpo1 {
node2 = idom[node2];
}
}
assert!(node1 == node2);
node1
}
#[inline(never)]
fn calc_dom_tree(
num_blocks: u32,
pred_map: &TypedIxVec<BlockIx, SparseSetU<[BlockIx; 4]>>,
post_ord: &Vec<BlockIx>,
start: BlockIx,
) -> TypedIxVec<BlockIx, BlockIx> {
info!(" calc_dom_tree: begin");
assert!(num_blocks < DT_INVALID_POSTORD);
let mut bix2rpostord = TypedIxVec::<BlockIx, u32>::new();
let mut rpostord2bix = Vec::<BlockIx>::new();
bix2rpostord.resize(num_blocks, DT_INVALID_POSTORD);
rpostord2bix.resize(num_blocks as usize, DT_INVALID_BLOCKIX);
for n in 0..num_blocks {
let bix = post_ord[(num_blocks - 1 - n) as usize];
bix2rpostord[bix] = n;
rpostord2bix[n as usize] = bix;
}
for n in 0..num_blocks {
debug_assert!(bix2rpostord[BlockIx::new(n)] < num_blocks);
}
let mut idom = TypedIxVec::<BlockIx, BlockIx>::new();
idom.resize(num_blocks, DT_INVALID_BLOCKIX);
idom[start] = start;
for i in 0..num_blocks {
let block_ix = BlockIx::new(i);
let preds_of_i = &pred_map[block_ix];
if block_ix != start {
assert!(!preds_of_i.is_empty());
}
}
let mut changed = true;
while changed {
changed = false;
for n in 0..num_blocks {
let node = rpostord2bix[n as usize];
assert!(node != DT_INVALID_BLOCKIX);
let node_preds = &pred_map[node];
let rponum = bix2rpostord[node];
let mut parent = DT_INVALID_BLOCKIX;
if node_preds.is_empty() {
} else {
for pred in node_preds.iter() {
let pred_rpo = bix2rpostord[*pred];
if pred_rpo < rponum {
parent = *pred;
break;
}
}
}
if parent != DT_INVALID_BLOCKIX {
for pred in node_preds.iter() {
if *pred == parent {
continue;
}
if idom[*pred] == DT_INVALID_BLOCKIX {
continue;
}
parent = dt_merge_sets(&idom, &bix2rpostord, parent, *pred);
}
}
if parent != DT_INVALID_BLOCKIX && parent != idom[node] {
idom[node] = parent;
changed = true;
}
}
}
assert!(idom[start] == start);
for i in 0..num_blocks {
let block_ix = BlockIx::new(i);
assert!(idom[block_ix] != DT_INVALID_BLOCKIX);
assert!((idom[block_ix] == block_ix) == (block_ix == start));
}
if CROSSCHECK_DOMS {
info!(" calc_dom_tree crosscheck: begin");
let slow_sets = calc_dom_sets_slow(num_blocks, pred_map, post_ord, start);
assert!(slow_sets.len() == idom.len());
for i in 0..num_blocks {
let mut block_ix = BlockIx::new(i);
let mut set = Set::<BlockIx>::empty();
loop {
set.insert(block_ix);
let other_block_ix = idom[block_ix];
if other_block_ix == block_ix {
break;
}
block_ix = other_block_ix;
}
assert!(set.to_vec() == slow_sets[BlockIx::new(i)].to_vec());
}
info!(" calc_dom_tree crosscheck: end");
}
info!(" calc_dom_tree: end");
idom
}
#[inline(never)]
fn calc_loop_depths(
num_blocks: u32,
pred_map: &TypedIxVec<BlockIx, SparseSetU<[BlockIx; 4]>>,
succ_map: &TypedIxVec<BlockIx, SparseSetU<[BlockIx; 4]>>,
post_ord: &Vec<BlockIx>,
start: BlockIx,
) -> TypedIxVec<BlockIx, u32> {
info!(" calc_loop_depths: begin");
let idom = calc_dom_tree(num_blocks, pred_map, post_ord, start);
let mut back_edges = Set::<(BlockIx, BlockIx)>::empty();
for block_m_ix in BlockIx::new(0).dotdot(BlockIx::new(num_blocks)) {
for block_n_ix in succ_map[block_m_ix].iter() {
let mut n_dominates_m = false;
let mut block_ix = block_m_ix;
loop {
if block_ix == *block_n_ix {
n_dominates_m = true;
break;
}
let other_block_ix = idom[block_ix];
if other_block_ix == block_ix {
break;
}
block_ix = other_block_ix;
}
if n_dominates_m {
back_edges.insert((block_m_ix, *block_n_ix));
}
}
}
let mut natural_loops = Vec::<Set<BlockIx>>::new();
for (block_m_ix, block_n_ix) in back_edges.iter() {
let mut loop_set: Set<BlockIx>;
let mut stack: Vec<BlockIx>;
stack = Vec::<BlockIx>::new();
loop_set = Set::<BlockIx>::two(*block_m_ix, *block_n_ix);
if block_m_ix != block_n_ix {
stack.push(*block_m_ix);
while let Some(block_p_ix) = stack.pop() {
for block_q_ix in pred_map[block_p_ix].iter() {
if !loop_set.contains(*block_q_ix) {
loop_set.insert(*block_q_ix);
stack.push(*block_q_ix);
}
}
}
}
natural_loops.push(loop_set);
}
natural_loops.sort_by(|left_block_set, right_block_set| {
left_block_set
.card()
.partial_cmp(&right_block_set.card())
.unwrap()
});
let num_loops = natural_loops.len();
let mut loop_depths = Vec::<u32>::new();
loop_depths.resize(num_loops, 0);
for i in 0..num_loops {
let mut curr = i;
let mut depth = 1;
for j in i + 1..num_loops {
debug_assert!(curr < j);
if natural_loops[curr].is_subset_of(&natural_loops[j]) {
depth += 1;
curr = j;
}
}
loop_depths[i] = depth;
}
let mut depth_map = TypedIxVec::<BlockIx, u32>::new();
depth_map.resize(num_blocks, 0);
for (loop_block_indexes, depth) in natural_loops.iter().zip(loop_depths) {
for loop_block_ix in loop_block_indexes.iter() {
if depth_map[*loop_block_ix] < depth {
depth_map[*loop_block_ix] = depth;
}
}
}
debug_assert!(depth_map.len() == num_blocks);
let mut n = 0;
debug!("");
for (depth, idom_by) in depth_map.iter().zip(idom.iter()) {
debug!(
"{:<3?} depth {} idom {:?}",
BlockIx::new(n),
depth,
idom_by
);
n += 1;
}
info!(" calc_loop_depths: end");
depth_map
}
pub struct CFGInfo {
pub pred_map: TypedIxVec<BlockIx, SparseSetU<[BlockIx; 4]>>,
pub succ_map: TypedIxVec<BlockIx, SparseSetU<[BlockIx; 4]>>,
pub pre_ord: Vec<BlockIx>,
pub _post_ord: Vec<BlockIx>,
pub depth_map: TypedIxVec<BlockIx, u32>,
}
impl CFGInfo {
#[inline(never)]
pub fn create<F: Function>(func: &F) -> Result<Self, AnalysisError> {
info!(" CFGInfo::create: begin");
let num_blocks_usize = func.blocks().len();
if num_blocks_usize >= 1 * 1024 * 1024 {
return Err(AnalysisError::ImplementationLimitsExceeded);
}
if func.insns().len() >= 16 * 1024 * 1024 {
return Err(AnalysisError::ImplementationLimitsExceeded);
}
let num_blocks = num_blocks_usize as u32;
let (pred_map, succ_map) = calc_preds_and_succs(func, num_blocks);
assert!(pred_map.len() == num_blocks);
assert!(succ_map.len() == num_blocks);
for (src, dst_set) in (0..).zip(succ_map.iter()) {
if dst_set.card() < 2 {
continue;
}
for dst in dst_set.iter() {
if pred_map[*dst].card() >= 2 {
return Err(AnalysisError::CriticalEdge {
from: BlockIx::new(src),
to: *dst,
});
}
}
}
let mb_pre_ord_and_post_ord = calc_preord_and_postord(func, num_blocks, &succ_map);
if mb_pre_ord_and_post_ord.is_none() {
return Err(AnalysisError::UnreachableBlocks);
}
let (pre_ord, post_ord) = mb_pre_ord_and_post_ord.unwrap();
assert!(pre_ord.len() == num_blocks as usize);
assert!(post_ord.len() == num_blocks as usize);
let depth_map = calc_loop_depths(
num_blocks,
&pred_map,
&succ_map,
&post_ord,
func.entry_block(),
);
debug_assert!(depth_map.len() == num_blocks);
info!(" CFGInfo::create: end");
Ok(CFGInfo {
pred_map,
succ_map,
pre_ord,
_post_ord: post_ord,
depth_map,
})
}
}