ccp.rs

extern crate hercules_ir;

use std::collections::HashMap;
use std::iter::zip;

use self::hercules_ir::dataflow::*;
use self::hercules_ir::def_use::*;
use self::hercules_ir::ir::*;

/*
 * The ccp lattice tracks, for each node, the following information:
 * 1. Reachability - is it possible for this node to be reached during any
 *    execution?
 * 2. Constant - does this node evaluate to a constant expression?
 * The ccp lattice is formulated as a combination of consistuent lattices. The
 * flow function for the ccp dataflow analysis "crosses" information across the
 * sub lattices - for example, whether a condition is constant may inform
 * whether a branch target is reachable. This analysis uses interpreted
 * constants, so constant one plus constant one results in constant two.
 */
#[derive(Debug, Clone, PartialEq, Eq, Hash)]
pub struct CCPLattice {
    reachability: ReachabilityLattice,
    constant: ConstantLattice,
}

#[derive(Debug, Clone, PartialEq, Eq, Hash)]
pub enum ReachabilityLattice {
    Unreachable,
    Reachable,
}

#[derive(Debug, Clone, PartialEq, Eq, Hash)]
pub enum ConstantLattice {
    Top,
    Constant(Constant),
    Bottom,
}

impl CCPLattice {
    fn is_reachable(&self) -> bool {
        self.reachability == ReachabilityLattice::Reachable
    }

    fn get_constant(&self) -> Option<Constant> {
        if let ConstantLattice::Constant(cons) = &self.constant {
            Some(cons.clone())
        } else {
            None
        }
    }
}

impl ConstantLattice {
    fn is_top(&self) -> bool {
        *self == ConstantLattice::Top
    }

    fn is_bottom(&self) -> bool {
        *self == ConstantLattice::Bottom
    }
}

impl Semilattice for CCPLattice {
    fn meet(a: &Self, b: &Self) -> Self {
        CCPLattice {
            reachability: ReachabilityLattice::meet(&a.reachability, &b.reachability),
            constant: ConstantLattice::meet(&a.constant, &b.constant),
        }
    }