datafrogger

gistfile1.txt

use std::collections::{BTreeMap, BTreeSet};

use crate::facts::{AllFacts, Loan, Point, Region};
use crate::output::Output;

use datafrog::{Iteration, Relation};

pub(super) fn compute(dump_enabled: bool, mut all_facts: AllFacts) -> Output {
    let all_points: BTreeSet<Point> = all_facts
        .cfg_edge
        .iter()
        .map(|&(p, _)| p)
        .chain(all_facts.cfg_edge.iter().map(|&(_, q)| q))
        .collect();

    for &r in &all_facts.universal_region {
        for &p in &all_points {
            all_facts.region_live_at.push((r, p));
        }
    }

    let timer = ::std::time::Instant::now();

    let mut result = Output::new(dump_enabled);

    let borrow_live_at = {
        // Create a new iteration context, ...
        let mut iteration = Iteration::new();

        // .. some variables, ..
        let subset = iteration.variable::<(Region, Region, Point)>("subset");
        let subset_1 = iteration.variable_indistinct("subset_1");
        let subset_2 = iteration.variable_indistinct("subset_2");
        let subset_r1p = iteration.variable_indistinct("subset_r1p");
        let subset_r2p = iteration.variable_indistinct("subset_r2p");
        let subset_p = iteration.variable_indistinct("subset_p");

        // temporaries as we perform a multi-way join.

        let requires = iteration.variable::<(Region, Loan, Point)>("requires");
        let requires_1 = iteration.variable("requires_1");
        let requires_2 = iteration.variable("requires_2");
        let requires_bp = iteration.variable("requires_bp");
        let requires_rp = iteration.variable("requires_rp");

        let borrow_live_at = iteration.variable::<(Loan, Point)>("borrow_live_at");

        let live_to_dead_regions = iteration.variable::<(Region, Region, Point, Point)>("live_to_dead_regions");
        let live_to_dead_regions_1 = iteration.variable_indistinct("live_to_dead_regions_1");
        let live_to_dead_regions_2 = iteration.variable_indistinct("live_to_dead_regions_2");
        let live_to_dead_regions_p = iteration.variable_indistinct("live_to_dead_regions_p");
        let live_to_dead_regions_r2pq = iteration.variable_indistinct("live_to_dead_regions_r2pq");

        let dead_region_requires = iteration.variable::<(Region, Loan, Point, Point)>("dead_region_requires");
        let dead_region_requires_1 = iteration.variable_indistinct("dead_region_requires_1");
        let dead_region_requires_2 = iteration.variable_indistinct("dead_region_requires_2");
        let dead_region_requires_rpq = iteration.variable_indistinct("dead_region_requires_rpq");

        let dead_can_reach_origins = iteration.variable::<((Region, Point), Point)>("dead_can_reach_origins");
        let dead_can_reach = iteration.variable::<(Region, Region, Point, Point)>("dead_can_reach");
        let dead_can_reach_1 = iteration.variable_indistinct("dead_can_reach_1");
        let dead_can_reach_r2q = iteration.variable_indistinct("dead_can_reach_r2q");

        let dead_can_reach_live = iteration.variable::<((Region, Point, Point), Region)>("dead_can_reach_live");
        let dead_can_reach_live_r1pq = iteration.variable_indistinct("dead_can_reach_live_r1pq");
        // let dead_can_reach_live_r2pq = iteration.variable("dead_can_reach_live_r2pq");

        // different indices for `subset`.

        // We need both relation and variable forms of this (for join and antijoin).
        let region_live_at_rel = Relation::from(all_facts.region_live_at.iter().map(|&(r, p)| (r, p)));
        let region_live_at_var = iteration.variable::<((Region, Point), ())>("region_live_at");

        let cfg_edge_p = iteration.variable::<(Point, Point)>("cfg_edge_p");

        let killed = Relation::from(all_facts.killed.iter().map(|&(l, p)| (l, p)));

        // load initial facts.
        subset.insert(all_facts.outlives.into());
        requires.insert(all_facts.borrow_region.into());
        region_live_at_var.insert(Relation::from(all_facts.region_live_at.iter().map(|&(r, p)| ((r, p), ()))));
        cfg_edge_p.insert(all_facts.cfg_edge.clone().into());

        // .. and then start iterating rules!
        while iteration.changed() {

            // subset(R1, R2, P) :- outlives(R1, R2, P).
            subset_r1p.from_map(&subset, |&(r1,r2,p)| ((r1,p),r2));
            subset_r2p.from_map(&subset, |&(r1,r2,p)| ((r2,p),r1));
            subset_p.from_map(&subset, |&(r1,r2,p)| (p,(r1,r2)));
            requires_bp.from_map(&requires, |&(r,b,p)| ((b,p),r));
            requires_rp.from_map(&requires, |&(r,b,p)| ((r,p),b));
            live_to_dead_regions_p.from_map(&live_to_dead_regions, |&(r1,r2,p,q)| (p, (r1,r2,q)));
            live_to_dead_regions_r2pq.from_map(&live_to_dead_regions, |&(r1,r2,p,q)| ((r2,p,q),r1));
            dead_can_reach_r2q.from_map(&dead_can_reach, |&(r1,r2,p,q)| ((r2,q),(r1,p)));
            dead_can_reach_live_r1pq.from_map(&dead_can_reach_live, |&((r1,p,q),r2)| ((r1,p,q),r2));
            // dead_can_reach_live_r2pq.from_map(&dead_can_reach_live, |&((r1,p,q),r2)| ((r2,p,q),r1));
            dead_region_requires_rpq.from_map(&dead_region_requires, |&(r,b,p,q)| ((r,p,q),b));
            // requires(R, B, P) :- Loan_region(R, B, P).

            // live_to_dead_regions(R1, R2, P, Q) :-
            //   subset(R1, R2, P),
            //   cfg_edge(P, Q),
            //   region_live_at(R1, Q),
            //   !region_live_at(R2, Q).
            live_to_dead_regions_1.from_join(&subset_p, &cfg_edge_p, |&p, &(r1,r2), &q| ((r1,q),(r2,p)));
            live_to_dead_regions_2.from_join(&live_to_dead_regions_1, &region_live_at_var, |&(r1,q), &(r2,p), &()| ((r2,q),(r1,p)));
            live_to_dead_regions.from_antijoin(&live_to_dead_regions_2, &region_live_at_rel, |&(r2,q), &(r1,p)| (r1, r2, p, q));

            // dead_region_requires(R, B, P, Q) :-
            //   requires(R, B, P),
            //   !killed(B, P),
            //   cfg_edge(P, Q),
            //   !region_live_at(R, Q).
            dead_region_requires_1.from_antijoin(&requires_bp, &killed, |&(b,p),&r| (p,(b,r)));
            dead_region_requires_2.from_join(&dead_region_requires_1, &cfg_edge_p, |&p,&(b,r),&q| ((r,q),(b,p)));
            dead_region_requires.from_antijoin(&dead_region_requires_2, &region_live_at_rel, |&(r,q),&(b,p)| (r, b, p, q));

            // let dead_can_reach_origins = {
            //     let dead_can_reach_origins0 =
            //         { live_to_dead_regions.map(|(_r1, r2, p, q)| ((r2, p), q)) };
            //     let dead_can_reach_origins1 =
            //         { dead_region_requires.map(|(r, _b, p, q)| ((r, p), q)) };
            //     dead_can_reach_origins0
            //         .concat(&dead_can_reach_origins1)
            //         .distinct_total()
            // };
            dead_can_reach_origins.from_map(&live_to_dead_regions, |&(_r1, r2, p, q)| ((r2, p), q));
            dead_can_reach_origins.from_map(&dead_region_requires, |&(r, _b, p, q)| ((r, p), q));

            // dead_can_reach(R1, R2, P, Q) :-
            //   dead_can_reach_origins(R1, P, Q),
            //   subset(R1, R2, P).
            dead_can_reach.from_join(&dead_can_reach_origins, &subset_r1p, |&(r1,p),&q,&r2| (r1,r2,p,q));

            // dead_can_reach(R1, R3, P, Q) :-
            //   dead_can_reach(R1, R2, P, Q),
            //   !region_live_at(R2, Q),
            //   subset(R2, R3, P).
            dead_can_reach_1.from_antijoin(&dead_can_reach_r2q, &region_live_at_rel, |&(r2,q),&(r1,p)| ((r2,p),(r1,q)));
            dead_can_reach.from_join(&dead_can_reach_1, &subset_r1p, |&(_r2,p),&(r1,q),&r3| (r1,r3,p,q));

            // let dead_can_reach_live = {
            //     dead_can_reach
            //         .join_core(&region_live_at_by_self, |&k, &v, _| Some((k, v)))
            //         .map(|((r2, q), (r1, p))| ((r1, p, q), r2))
            //         .arrange_by_key()
            // };
            dead_can_reach_live.from_join(&dead_can_reach_r2q, &region_live_at_var, |&(r2,q),&(r1,p),&()| ((r1,p,q),r2));

            // subset(R1, R2, Q) :-
            //   subset(R1, R2, P) :-
            //   cfg_edge(P, Q),
            //   region_live_at(R1, Q),
            //   region_live_at(R2, Q).
            subset_1.from_join(&subset_p, &cfg_edge_p, |&_p,&(r1,r2),&q| ((r1,q),r2));
            subset_2.from_join(&subset_1, &region_live_at_var, |&(r1,q),&r2,&()| ((r2,q),r1));
            subset.from_join(&subset_2, &region_live_at_var, |&(r2,q),&r1,&()| (r1,r2,q));

            // subset(R1, R3, Q) :-
            //   live_to_dead_regions(R1, R2, P, Q),
            //   dead_can_reach_live(R2, R3, P, Q).
            subset.from_join(&live_to_dead_regions_r2pq, &dead_can_reach_live_r1pq, |&(_r2,_p,q),&r1,&r3| (r1,r3,q));

            // requires(R2, B, Q) :-
            //   dead_region_requires(R1, B, P, Q),
            //   dead_can_reach_live(R1, R2, P, Q).
            requires.from_join(&dead_region_requires_rpq, &dead_can_reach_live_r1pq, |&(_r1,_p,q),&b,&r2| (r2,b,q));

            // requires(R, B, Q) :-
            //   requires(R, B, P),
            //   !killed(B, P),
            //   cfg_edge(P, Q),
            //   region_live_at(R, Q).
            requires_1.from_antijoin(&requires_bp, &killed, |&(b,p),&r| (p,(r,b)));
            requires_2.from_join(&requires_1, &cfg_edge_p, |&_p, &(r,b), &q| ((r,q),b));
            requires.from_join(&requires_2, &region_live_at_var, |&(r,q),&b,&()| (r,b,q));

            // borrow_live_at(B, P) :- requires(R, B, P), region_live_at(R, P)
            borrow_live_at.from_join(&requires_rp, &region_live_at_var, |&(_r,p), &b, &()| (b, p));
        }

        borrow_live_at.complete()
    };

    println!("{:?}\tborrow_live_at is complete: {}", timer.elapsed(), borrow_live_at.len());

    for (borrow, location) in &borrow_live_at.elements {
        result
            .borrow_live_at
            .entry(*location)
            .or_insert(Vec::new())
            .push(*borrow);
    }

    result
}