datafrog_opt.rs

gistfile1.txt

// Copyright 2017 The Rust Project Developers. See the COPYRIGHT
// file at the top-level directory of this distribution and at
// http://rust-lang.org/COPYRIGHT.
//
// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
// option. This file may not be copied, modified, or distributed
// except according to those terms.

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

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 {
    // Declare that each universal region is live at every point.
    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 = 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 and different indices for `subset`.
        let subset_pr1 = iteration.variable("subset_pr1");

        // temporaries as we perform a multi-way join, and more indices
        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_r2pq = iteration.variable_indistinct("live_to_dead_regions_r2pq");

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

        let dead_can_reach_origins =
            iteration.variable::<((Point, Region), 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");
        // nmatsakis: I tried to merge `dead_can_reach_r2q` and
        // `dead_can_reach`, but the result was ever so slightly slower, at least on clap.

        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");

        // 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 cfg_edge_rel =
            Relation::from(all_facts.cfg_edge.iter().map(|&(p, q)| (p, q)));

        let killed: Relation<(Loan, Point)> = all_facts.killed.into();

        // load initial facts.
        subset_pr1.insert(all_facts.outlives.iter().map(|&(r1,r2,p)| ((p,r1),r2)).into());
        requires_rp.insert(all_facts.borrow_region.iter().map(|&(r,b,p)| ((r,p),b)).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.into());

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

            use datafrog::leapfrog::{RelationLeaper, leapjoin_into};

            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));

            // it's now time ... to datafrog:

            // .decl subset(R1, R2, P)
            //
            // At the point P, R1 <= R2.
            //
            // subset(R1, R2, P) :- outlives(R1, R2, P).
            // -> already loaded; outlives is a static input.

            // .decl requires(R, B, P) -- at the point, things with region R
            // may depend on data from borrow B
            //
            // requires(R, B, P) :- borrow_region(R, B, P).
            // -> already loaded; borrow_region is a static input.

            // .decl live_to_dead_regions(R1, R2, P, Q)
            //
            // The regions `R1` and `R2` are "live to dead"
            // on the edge `P -> Q` if:
            //
            // - In P, `R1` <= `R2`
            // - In Q, `R1` is live but `R2` is dead.
            //
            // In that case, `Q` would like to add all the
            // live things reachable from `R2` to `R1`.
            //
            // 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).
            leapjoin_into(
                &subset_pr1,  // dynamic source
                &mut [
                    &mut cfg_edge_rel.extend_with(|&((p,_r1),_r2)| p),
                    &mut region_live_at_rel.extend_with(|&((_p,r1),_r2)| r1),
                    &mut region_live_at_rel.extend_anti(|&((_p,_r1),r2)| r2),
                ],
                &live_to_dead_regions,
                |&((p,r1),r2),&q| (r1,r2,p,q));

            // .decl dead_region_requires((R, P, Q), B)
            //
            // The region `R` requires the borrow `B`, but the
            // region `R` goes dead along the edge `P -> Q`
            //
            // dead_region_requires((R, P, Q), B) :-
            //   requires(R, B, P),
            //   !killed(B, P),
            //   cfg_edge(P, Q),
            //   !region_live_at(R, Q).
            leapjoin_into(
                &requires_rp,  // dynamic source
                &mut [
                    &mut killed.filter_anti(|&((_r,p),b)| (b,p)),
                    &mut cfg_edge_rel.extend_with(|&((_r,p),_b)| p),
                    &mut region_live_at_rel.extend_anti(|&((r,_p),_b)| r),
                ],
                &dead_region_requires,  // destination
                |&((r,p),b),&q| ((r,p,q),b));

            // .decl dead_can_reach_origins(R, P, Q)
            //
            // Contains dead regions where we are interested
            // in computing the transitive closure of things they
            // can reach.
            dead_can_reach_origins.from_map(&live_to_dead_regions, |&(_r1, r2, p, q)| ((p, r2), q));
            dead_can_reach_origins.from_map(&dead_region_requires, |&((r, p, q), _b)| ((p, r), 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_pr1, |&(p, r1), &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)| ((p, r2), (r1, q)),
            );
            dead_can_reach.from_join(
                &dead_can_reach_1,
                &subset_pr1,
                |&(p, _r2), &(r1, q), &r3| (r1, r3, p, q),
            );


            // dead_can_reach_live((R1, P, Q), R2) :- dead_can_reach(R1, R2, P, Q), region_live_at(R2, Q)
            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).
            leapjoin_into(
                &subset_pr1,  // dynamic source
                &mut [
                    &mut cfg_edge_rel.extend_with(|&((p,_r1),_r2)| p),
                    &mut region_live_at_rel.extend_with(|&((_p,r1),_r2)| r1),
                    &mut region_live_at_rel.extend_with(|&((_p,_r1),r2)| r2),
                ],
                &subset_pr1,  // destination
                |&((_p,r1),r2),&q| ((q,r1),r2));

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

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

            // requires(R, B, Q) :- requires(R, B, P), !killed(B, P), cfg_edge(P, Q), region_live_at(R, Q).
            leapjoin_into(
                &requires_rp,  // dynamic source
                &mut [
                    &mut killed.filter_anti(|&((_r,p),b)| (b,p)),
                    &mut cfg_edge_rel.extend_with(|&((_r,p),_b)| p),
                    &mut region_live_at_rel.extend_with(|&((r,_p),_b)| r),
                ],
                &requires_rp,  // destination
                |&((r,_p),b),&q| ((r,q),b));

            // .decl borrow_live_at(B, P) -- true if the restrictions of the borrow B
            // need to be enforced at the point P
            //
            // 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)
            });
        }

        if dump_enabled {
            for (region, location) in &region_live_at_rel.elements {
                result
                    .region_live_at
                    .entry(*location)
                    .or_insert(vec![])
                    .push(*region);
            }

            let subset = subset_pr1.complete();
            // println!("subset symmetries: {:?}", subset.iter().filter(|&(_,(r1,r2))| r1 == r2).count());
            for ((location, r1), r2) in &subset.elements {
                result
                    .subset
                    .entry(*location)
                    .or_insert(BTreeMap::new())
                    .entry(*r1)
                    .or_insert(BTreeSet::new())
                    .insert(*r2);
                result.region_degrees.update_degrees(*r1, *r2, *location);
            }

            let requires = requires_rp.complete();
            for ((region, location), borrow) in &requires.elements {
                result
                    .restricts
                    .entry(*location)
                    .or_insert(BTreeMap::new())
                    .entry(*region)
                    .or_insert(BTreeSet::new())
                    .insert(*borrow);
            }
        }

        borrow_live_at.complete()
    };

    if dump_enabled {
        println!(
            "borrow_live_at is complete: {} tuples, {:?}",
            borrow_live_at.len(),
            timer.elapsed()
        );
    }

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

    result
}