rapx/analysis/alias_analysis/default/graph.rs
1use super::{MopFnAliasPairs, assign::*, block::*, types::*, value::*};
2use crate::{
3 analysis::path_analysis::{
4 PathTree,
5 graph::{PathEnumerator, PathGraph},
6 },
7 compat::{FxHashMap, FxHashSet},
8 graphs::cfg::CfgBlock,
9 utils::source::*,
10};
11use rustc_middle::{
12 mir::{AggregateKind, BasicBlock, Const, Operand, Rvalue, StatementKind, Terminator},
13 ty::{self, TyCtxt, TypingEnv},
14};
15use rustc_span::{Span, def_id::DefId};
16use std::fmt;
17
18#[derive(Clone)]
19pub struct AliasGraph<'tcx> {
20 pub path_graph: PathGraph<'tcx>,
21 /// Path-sensitive state used by alias/safedrop traversal.
22 pub constants: FxHashMap<usize, usize>,
23 /// Traversal visit counter for recursion limiting.
24 pub visit_times: usize,
25 // All values (including fields) of the function.
26 // For general variables, we use its Local as the value index;
27 // For fields, the value index is determined via auto increment.
28 pub values: Vec<Value>,
29 // Alias-analysis-specific facts extracted from each MIR block.
30 pub block_facts: Vec<AliasBlockFacts<'tcx>>,
31 pub alias_sets: Vec<FxHashSet<usize>>,
32 // contains the return results for inter-procedure analysis.
33 pub ret_alias: MopFnAliasPairs,
34 pub arg_size: usize,
35 pub span: Span,
36}
37
38impl<'tcx> AliasGraph<'tcx> {
39 pub fn new(tcx: TyCtxt<'tcx>, def_id: DefId) -> AliasGraph<'tcx> {
40 let fn_name = get_fn_name(tcx, def_id);
41 rap_debug!("New an AliasGraph for: {:?}", fn_name);
42 let path_graph = PathGraph::new(tcx, def_id);
43 Self::from_path_graph(tcx, def_id, path_graph)
44 }
45
46 pub fn from_path_graph(
47 tcx: TyCtxt<'tcx>,
48 def_id: DefId,
49 path_graph: PathGraph<'tcx>,
50 ) -> AliasGraph<'tcx> {
51 let fn_name = get_fn_name(tcx, def_id);
52 rap_debug!(
53 "New an AliasGraph from existing PathGraph for: {:?}",
54 fn_name
55 );
56 // handle variables
57 let body = tcx.optimized_mir(def_id);
58 let locals = &body.local_decls;
59 let arg_size = body.arg_count;
60 let mut values = Vec::<Value>::new();
61 let ty_env = TypingEnv::post_analysis(tcx, def_id);
62 for (local, local_decl) in locals.iter_enumerated() {
63 let need_drop = local_decl.ty.needs_drop(tcx, ty_env); // the type is drop
64 let may_drop = !is_not_drop(tcx, local_decl.ty);
65 let mut node = Value::new(
66 local.as_usize(),
67 local.as_usize(),
68 need_drop,
69 need_drop || may_drop,
70 );
71 node.kind = kind(local_decl.ty);
72 values.push(node);
73 }
74
75 let basicblocks = &body.basic_blocks;
76 let mut block_facts = Vec::<AliasBlockFacts<'tcx>>::new();
77
78 // handle each basicblock
79 for i in 0..basicblocks.len() {
80 let bb = &basicblocks[BasicBlock::from(i)];
81 let mut alias_block = AliasBlockFacts::new();
82
83 // handle general statements
84 for stmt in &bb.statements {
85 let span = stmt.source_info.span;
86 match &stmt.kind {
87 StatementKind::Assign(assign) => {
88 let (place, rvalue) = &**assign;
89 let lv_place = *place;
90 let lv_local = place.local.as_usize();
91 match rvalue.clone() {
92 // rvalue is a Rvalue
93 Rvalue::Use(operand, ..) => {
94 match operand {
95 Operand::Copy(rv_place) => {
96 let rv_local = rv_place.local.as_usize();
97 if values[lv_local].may_drop && values[rv_local].may_drop {
98 let assign = Assignment::new(
99 lv_place,
100 rv_place,
101 AssignType::Copy,
102 span,
103 );
104 alias_block.assignments.push(assign);
105 }
106 }
107 Operand::Move(rv_place) => {
108 let rv_local = rv_place.local.as_usize();
109 if values[lv_local].may_drop && values[rv_local].may_drop {
110 let assign = Assignment::new(
111 lv_place,
112 rv_place,
113 AssignType::Move,
114 span,
115 );
116 alias_block.assignments.push(assign);
117 }
118 }
119 Operand::Constant(constant) => {
120 /* We should check the correctness due to the update of rustc
121 * https://doc.rust-lang.org/beta/nightly-rustc/rustc_middle/mir/enum.Const.html
122 */
123 match constant.const_ {
124 Const::Ty(_ty, const_value) => {
125 if let Some(val) =
126 const_value.try_to_target_usize(tcx)
127 {
128 alias_block.const_value.push(ConstValue::new(
129 lv_local,
130 val as usize,
131 ));
132 }
133 }
134 Const::Unevaluated(_const_value, _ty) => {}
135 Const::Val(const_value, _ty) => {
136 if let Some(scalar) =
137 const_value.try_to_scalar_int()
138 {
139 let val = scalar.to_uint(scalar.size());
140 alias_block.const_value.push(ConstValue::new(
141 lv_local,
142 val as usize,
143 ));
144 }
145 }
146 }
147 }
148 #[cfg(rapx_rustc_ge_196)]
149 Operand::RuntimeChecks(_) => {}
150 }
151 }
152 Rvalue::Ref(_, _, rv_place)
153 | Rvalue::RawPtr(_, rv_place)
154 | Rvalue::CopyForDeref(rv_place) => {
155 let rv_local = rv_place.local.as_usize();
156 if values[lv_local].may_drop && values[rv_local].may_drop {
157 let assign =
158 Assignment::new(lv_place, rv_place, AssignType::Copy, span);
159 alias_block.assignments.push(assign);
160 }
161 }
162 #[cfg(not(rapx_rustc_ge_196))]
163 Rvalue::ShallowInitBox(operand, _) => {
164 /*
165 * Original ShllowInitBox is a two-level pointer: lvl0 -> lvl1 -> lvl2
166 * Since our alias analysis does not consider multi-level pointer,
167 * We simplify it as: lvl0
168 */
169 if !values[lv_local].fields.contains_key(&0) {
170 let mut lvl0 = Value::new(values.len(), lv_local, false, true);
171 lvl0.father = Some(FatherInfo::new(lv_local, 0));
172 values[lv_local].fields.insert(0, lvl0.index);
173 values.push(lvl0);
174 }
175 match operand {
176 Operand::Copy(rv_place) | Operand::Move(rv_place) => {
177 let rv_local = rv_place.local.as_usize();
178 if values[lv_local].may_drop && values[rv_local].may_drop {
179 let assign = Assignment::new(
180 lv_place,
181 rv_place,
182 AssignType::InitBox,
183 span,
184 );
185 alias_block.assignments.push(assign);
186 }
187 }
188 Operand::Constant(_) => {}
189 }
190 }
191 Rvalue::Cast(_, operand, _) => match operand {
192 Operand::Copy(rv_place) => {
193 let rv_local = rv_place.local.as_usize();
194 if values[lv_local].may_drop && values[rv_local].may_drop {
195 let assign = Assignment::new(
196 lv_place,
197 rv_place,
198 AssignType::Copy,
199 span,
200 );
201 alias_block.assignments.push(assign);
202 }
203 }
204 Operand::Move(rv_place) => {
205 let rv_local = rv_place.local.as_usize();
206 if values[lv_local].may_drop && values[rv_local].may_drop {
207 let assign = Assignment::new(
208 lv_place,
209 rv_place,
210 AssignType::Move,
211 span,
212 );
213 alias_block.assignments.push(assign);
214 }
215 }
216 Operand::Constant(_) => {}
217 #[cfg(rapx_rustc_ge_196)]
218 Operand::RuntimeChecks(_) => {}
219 },
220 Rvalue::Aggregate(kind, operands) => {
221 match kind.as_ref() {
222 // For tuple aggregation such as _10 = (move _11, move _12)
223 // we create `_10.0 = move _11` and `_10.1 = move _12` to achieve field sensitivity
224 // and prevent transitive alias: (_10, _11) + (_10, _12) => (_11, _12)
225 AggregateKind::Tuple => {
226 let lv_ty = lv_place.ty(&body.local_decls, tcx).ty;
227 for (field_idx, operand) in operands.iter_enumerated() {
228 match operand {
229 Operand::Copy(rv_place)
230 | Operand::Move(rv_place) => {
231 let rv_local = rv_place.local.as_usize();
232 if values[lv_local].may_drop
233 && values[rv_local].may_drop
234 {
235 // Get field type from tuple or array
236 let field_ty = match lv_ty.kind() {
237 ty::Tuple(fields) => {
238 fields[field_idx.as_usize()]
239 }
240 _ => {
241 continue;
242 }
243 };
244
245 // Create lv.field_idx Place using tcx.mk_place_field
246 let lv_field_place = tcx.mk_place_field(
247 lv_place, field_idx, field_ty,
248 );
249
250 let assign = Assignment::new(
251 lv_field_place,
252 *rv_place,
253 if matches!(operand, Operand::Move(_)) {
254 AssignType::Move
255 } else {
256 AssignType::Copy
257 },
258 span,
259 );
260 alias_block.assignments.push(assign);
261 rap_debug!(
262 "Aggregate field assignment: {:?}.{} = {:?}",
263 lv_place,
264 field_idx.as_usize(),
265 rv_place
266 );
267 }
268 }
269 Operand::Constant(_) => {
270 // Constants don't need alias analysis
271 }
272 #[cfg(rapx_rustc_ge_196)]
273 Operand::RuntimeChecks(_) => {}
274 }
275 }
276 }
277 AggregateKind::Adt(_, _, _, _, _) => {
278 // For ADTs (structs/enums), handle field assignments field-sensitively.
279 // NOTE: Here we treat the ADT similarly to tuples,
280 // but fields might be named and ADT type info is available, so more precise field indexing is possible if needed.
281 let lv_ty = lv_place.ty(&body.local_decls, tcx).ty;
282 for (field_idx, operand) in operands.iter_enumerated() {
283 match operand {
284 Operand::Copy(rv_place)
285 | Operand::Move(rv_place) => {
286 let rv_local = rv_place.local.as_usize();
287 if values[lv_local].may_drop
288 && values[rv_local].may_drop
289 {
290 // If possible, resolve field type for better analysis. Here we use tuple logic as a template.
291 let field_ty = match lv_ty.kind() {
292 ty::Adt(adt_def, substs) => {
293 // Try getting the field type if available.
294 if field_idx.as_usize()
295 < adt_def.all_fields().count()
296 {
297 adt_def
298 .all_fields()
299 .nth(field_idx.as_usize())
300 .map(|f| {
301 #[cfg(not(
302 rapx_rustc_ge_198
303 ))]
304 {
305 f.ty(tcx, substs)
306 }
307 #[cfg(
308 rapx_rustc_ge_198
309 )]
310 {
311 f.ty(tcx, substs)
312 .skip_norm_wip()
313 }
314 })
315 .unwrap_or(lv_ty)
316 // fallback
317 } else {
318 lv_ty
319 }
320 }
321 _ => lv_ty,
322 };
323
324 // Create lv.field_idx Place using tcx.mk_place_field, as for tuples.
325 let lv_field_place = tcx.mk_place_field(
326 lv_place, field_idx, field_ty,
327 );
328
329 let assign = Assignment::new(
330 lv_field_place,
331 *rv_place,
332 if matches!(operand, Operand::Move(_)) {
333 AssignType::Move
334 } else {
335 AssignType::Copy
336 },
337 span,
338 );
339 alias_block.assignments.push(assign);
340 rap_debug!(
341 "Aggregate ADT field assignment: {:?}.{} = {:?}",
342 lv_place,
343 field_idx.as_usize(),
344 rv_place
345 );
346 }
347 }
348 Operand::Constant(_) => {
349 // Constants don't need alias analysis for this context.
350 }
351 #[cfg(rapx_rustc_ge_196)]
352 Operand::RuntimeChecks(_) => {}
353 }
354 }
355 }
356 // TODO: Support alias for array
357 AggregateKind::Array(_) => {}
358 // For other aggregate types, simply create an assignment for each aggregated operand
359 _ => {
360 for operand in operands {
361 match operand {
362 Operand::Copy(rv_place)
363 | Operand::Move(rv_place) => {
364 let rv_local = rv_place.local.as_usize();
365 if values[lv_local].may_drop
366 && values[rv_local].may_drop
367 {
368 let assign = Assignment::new(
369 lv_place,
370 rv_place,
371 AssignType::Copy,
372 span,
373 );
374 alias_block.assignments.push(assign);
375 }
376 }
377 Operand::Constant(_) => {}
378 #[cfg(rapx_rustc_ge_196)]
379 Operand::RuntimeChecks(_) => {}
380 }
381 }
382 }
383 }
384 }
385 Rvalue::Discriminant(rv_place) => {
386 let assign =
387 Assignment::new(lv_place, rv_place, AssignType::Variant, span);
388 alias_block.assignments.push(assign);
389 }
390 _ => {}
391 }
392 }
393 StatementKind::SetDiscriminant {
394 place: _,
395 variant_index: _,
396 } => {
397 rap_warn!("SetDiscriminant: {:?} is not handled in RAPx!", stmt);
398 }
399 _ => {}
400 }
401 }
402
403 if bb.terminator.is_none() {
404 rap_info!(
405 "Basic block BB{} has no terminator in function {:?}",
406 i,
407 fn_name
408 );
409 continue;
410 }
411 block_facts.push(alias_block);
412 }
413
414 AliasGraph {
415 path_graph,
416 constants: FxHashMap::default(),
417 visit_times: 0,
418 values,
419 block_facts,
420 alias_sets: Vec::<FxHashSet<usize>>::new(),
421 ret_alias: MopFnAliasPairs::new(arg_size),
422 arg_size,
423 span: body.span,
424 }
425 }
426
427 pub fn def_id(&self) -> DefId {
428 self.path_graph.def_id()
429 }
430
431 pub fn tcx(&self) -> TyCtxt<'tcx> {
432 self.path_graph.tcx()
433 }
434
435 pub fn arg_size(&self) -> usize {
436 self.arg_size
437 }
438
439 pub fn span(&self) -> Span {
440 self.span
441 }
442
443 pub fn cfg_block(&self, index: usize) -> &CfgBlock {
444 self.path_graph.cfg_block(index)
445 }
446
447 /// Retrieve the MIR terminator for the block at `index` on demand.
448 pub fn terminator(&self, index: usize) -> Option<&Terminator<'tcx>> {
449 self.path_graph.terminator(index)
450 }
451
452 pub fn find_scc(&mut self) {
453 self.path_graph.find_scc();
454 }
455
456 pub fn enumerate_paths(&self) -> PathTree {
457 let mut enumerator = PathEnumerator::new(&self.path_graph);
458 enumerator.enumerate_paths()
459 }
460
461 pub fn visit_times(&self) -> usize {
462 self.visit_times
463 }
464
465 pub fn increment_visit_times(&mut self) -> usize {
466 self.visit_times += 1;
467 self.visit_times
468 }
469}
470
471// Implement Display for debugging / printing purposes.
472// Prints selected fields: def_id, values, blocks, constants, discriminants, scc_indices, child_scc.
473impl<'tcx> std::fmt::Display for AliasGraph<'tcx> {
474 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
475 writeln!(f, "AliasGraph {{")?;
476 writeln!(f, " def_id: {:?}", self.def_id())?;
477 writeln!(f, " values: {:?}", self.values)?;
478 writeln!(f, " cfg_blocks: {:?}", self.path_graph.cfg.blocks)?;
479 writeln!(f, " block_facts: {:?}", self.block_facts)?;
480 writeln!(f, " constants: {:?}", self.constants)?;
481 writeln!(f, " disc_info: {:?}", self.path_graph.disc_info)?;
482 write!(f, "}}")
483 }
484}