1// Copyright 2019 The Rust Project Developers. See the COPYRIGHT
2// file at the top-level directory of this distribution and at
3// http://rust-lang.org/COPYRIGHT.
4//
5// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
8// option. This file may not be copied, modified, or distributed
9// except according to those terms.
10
11//! An implementation of the origin liveness calculation logic
12
13use std::collections::BTreeSet;
14use std::time::Instant;
15
16use crate::facts::FactTypes;
17use crate::output::{LivenessContext, Output};
18
19use datafrog::{Iteration, Relation, RelationLeaper};
20
21pub(super) fn compute_live_origins<T: FactTypes>(
22 ctx: LivenessContext<T>,
23 cfg_edge: &Relation<(T::Point, T::Point)>,
24 var_maybe_partly_initialized_on_exit: Relation<(T::Variable, T::Point)>,
25 output: &mut Output<T>,
26) -> Vec<(T::Origin, T::Point)> {
27 let timer = Instant::now();
28 let mut iteration = Iteration::new();
29
30 // Relations
31 let var_defined_at: Relation<(T::Variable, T::Point)> = ctx.var_defined_at.into();
32 let cfg_edge_reverse: Relation<(T::Point, T::Point)> = cfg_edge
33 .iter()
34 .map(|&(point1, point2)| (point2, point1))
35 .collect();
36 let use_of_var_derefs_origin: Relation<(T::Variable, T::Origin)> =
37 ctx.use_of_var_derefs_origin.into();
38 let drop_of_var_derefs_origin: Relation<(T::Variable, T::Origin)> =
39 ctx.drop_of_var_derefs_origin.into();
40 let var_dropped_at: Relation<((T::Variable, T::Point), ())> = ctx
41 .var_dropped_at
42 .into_iter()
43 .map(|(var, point)| ((var, point), ()))
44 .collect();
45
46 // Variables
47
48 // `var_live_on_entry`: variable `var` is live upon entry at `point`
49 let var_live_on_entry = iteration.variable::<(T::Variable, T::Point)>("var_live_on_entry");
50 // `var_drop_live_on_entry`: variable `var` is drop-live (will be used for a drop) upon entry in `point`
51 let var_drop_live_on_entry =
52 iteration.variable::<(T::Variable, T::Point)>("var_drop_live_on_entry");
53
54 // This is what we are actually calculating:
55 let origin_live_on_entry = iteration.variable::<(T::Origin, T::Point)>("origin_live_on_entry");
56
57 // This propagates the relation `var_live_on_entry(var, point) :- var_used_at(var, point)`:
58 var_live_on_entry.insert(ctx.var_used_at.into());
59
60 // var_maybe_partly_initialized_on_entry(var, point2) :-
61 // var_maybe_partly_initialized_on_exit(var, point1),
62 // cfg_edge(point1, point2).
63 let var_maybe_partly_initialized_on_entry = Relation::from_leapjoin(
64 &var_maybe_partly_initialized_on_exit,
65 cfg_edge.extend_with(|&(_var, point1)| point1),
66 |&(var, _point1), &point2| ((var, point2), ()),
67 );
68
69 // var_drop_live_on_entry(var, point) :-
70 // var_dropped_at(var, point),
71 // var_maybe_partly_initialized_on_entry(var, point).
72 var_drop_live_on_entry.insert(Relation::from_join(
73 &var_dropped_at,
74 &var_maybe_partly_initialized_on_entry,
75 |&(var, point), _, _| (var, point),
76 ));
77
78 while iteration.changed() {
79 // origin_live_on_entry(origin, point) :-
80 // var_drop_live_on_entry(var, point),
81 // drop_of_var_derefs_origin(var, origin).
82 origin_live_on_entry.from_join(
83 &var_drop_live_on_entry,
84 &drop_of_var_derefs_origin,
85 |_var, &point, &origin| (origin, point),
86 );
87
88 // origin_live_on_entry(origin, point) :-
89 // var_live_on_entry(var, point),
90 // use_of_var_derefs_origin(var, origin).
91 origin_live_on_entry.from_join(
92 &var_live_on_entry,
93 &use_of_var_derefs_origin,
94 |_var, &point, &origin| (origin, point),
95 );
96
97 // var_live_on_entry(var, point1) :-
98 // var_live_on_entry(var, point2),
99 // cfg_edge(point1, point2),
100 // !var_defined(var, point1).
101 var_live_on_entry.from_leapjoin(
102 &var_live_on_entry,
103 (
104 var_defined_at.extend_anti(|&(var, _point2)| var),
105 cfg_edge_reverse.extend_with(|&(_var, point2)| point2),
106 ),
107 |&(var, _point2), &point1| (var, point1),
108 );
109
110 // var_drop_live_on_entry(Var, SourceNode) :-
111 // var_drop_live_on_entry(Var, TargetNode),
112 // cfg_edge(SourceNode, TargetNode),
113 // !var_defined_at(Var, SourceNode),
114 // var_maybe_partly_initialized_on_exit(Var, SourceNode).
115 var_drop_live_on_entry.from_leapjoin(
116 &var_drop_live_on_entry,
117 (
118 var_defined_at.extend_anti(|&(var, _target_node)| var),
119 cfg_edge_reverse.extend_with(|&(_var, target_node)| target_node),
120 var_maybe_partly_initialized_on_exit.extend_with(|&(var, _target_node)| var),
121 ),
122 |&(var, _targetnode), &source_node| (var, source_node),
123 );
124 }
125
126 let origin_live_on_entry = origin_live_on_entry.complete();
127
128 info!(
129 "compute_live_origins() completed: {} tuples, {:?}",
130 origin_live_on_entry.len(),
131 timer.elapsed(),
132 );
133
134 if output.dump_enabled {
135 let var_drop_live_on_entry = var_drop_live_on_entry.complete();
136 for &(var, location) in var_drop_live_on_entry.iter() {
137 output
138 .var_drop_live_on_entry
139 .entry(location)
140 .or_default()
141 .push(var);
142 }
143
144 let var_live_on_entry = var_live_on_entry.complete();
145 for &(var, location) in var_live_on_entry.iter() {
146 output
147 .var_live_on_entry
148 .entry(location)
149 .or_default()
150 .push(var);
151 }
152 }
153
154 origin_live_on_entry.elements
155}
156
157pub(super) fn make_universal_regions_live<T: FactTypes>(
158 origin_live_on_entry: &mut Vec<(T::Origin, T::Point)>,
159 cfg_node: &BTreeSet<T::Point>,
160 universal_regions: &[T::Origin],
161) {
162 debug!("make_universal_regions_live()");
163
164 origin_live_on_entry.reserve(additional:universal_regions.len() * cfg_node.len());
165 for &origin: ::Origin in universal_regions.iter() {
166 for &point: ::Point in cfg_node.iter() {
167 origin_live_on_entry.push((origin, point));
168 }
169 }
170}
171