rapx/analysis/alias/
tree.rs1use crate::util::mir_utils;
16use super::hazard as alias_hazard;
17use rustc_hash::FxHashMap;
18use rustc_hir::def_id::DefId;
19use rustc_middle::{
20 mir::{Local, Operand, Rvalue, StatementKind},
21 ty::{Ty, TyCtxt, TyKind},
22};
23
24pub(crate) type TagId = usize;
26
27#[derive(Clone, Debug)]
29pub(crate) struct AliasNode {
30 pub parent: Option<TagId>,
31 pub fields: Vec<usize>,
36 pub local: Local,
37}
38
39#[derive(Clone, Debug)]
41pub(crate) struct AliasTree {
42 pub nodes: Vec<AliasNode>,
43 tag_of_local: FxHashMap<Local, TagId>,
45}
46
47impl AliasTree {
48 pub(crate) fn build<'tcx>(tcx: TyCtxt<'tcx>, def_id: DefId) -> Self {
56 let body = tcx.optimized_mir(def_id);
57 let mut tree = AliasTree {
58 nodes: Vec::new(),
59 tag_of_local: FxHashMap::default(),
60 };
61
62 for local_index in 1..=body.arg_count {
63 let local = Local::from_usize(local_index);
64 let ty = body.local_decls[local].ty;
65 if classify(ty).is_some() {
66 tree.add(None, Vec::new(), local);
67 }
68 }
69
70 for block in body.basic_blocks.iter() {
71 for statement in &block.statements {
72 let StatementKind::Assign(assign) = &statement.kind else {
73 continue;
74 };
75 let (target, rvalue) = assign.as_ref();
76 match rvalue {
77 Rvalue::Use(Operand::Copy(place), ..)
82 | Rvalue::Use(Operand::Move(place), ..)
83 | Rvalue::CopyForDeref(place)
84 if field_projection(place).is_empty() =>
85 {
86 if let Some(tag) = tree.tag_of_local.get(&place.local).copied() {
87 tree.tag_of_local.insert(target.local, tag);
88 }
89 }
90 _ => {
94 if let Some(place) = mir_utils::rvalue_source_place(rvalue)
95 && let Some(parent) = tree.tag_of_local.get(&place.local).copied()
96 {
97 let ty = body.local_decls[target.local].ty;
98 if classify(ty).is_some() {
99 tree.add(Some(parent), field_projection(place), target.local);
100 }
101 }
102 }
103 }
104 }
105
106 if let rustc_middle::mir::TerminatorKind::Call {
109 func, args, destination, ..
110 } = &block.terminator().kind
111 {
112 let dest_local = destination.local;
113 let dest_ty = body.local_decls[dest_local].ty;
114 if let Some(is_owned) = classify(dest_ty) {
115 if is_owned {
116 tree.add(None, Vec::new(), dest_local);
117 } else if let Some(source_arg) = call_source_arg(tcx, func, args)
118 && let Some(place) = args[source_arg].node.place()
119 && let Some(parent) = tree.tag_of_local.get(&place.local).copied()
120 {
121 tree.add(Some(parent), field_projection(&place), dest_local);
122 }
123 }
124 }
125 }
126
127 tree
128 }
129
130 fn add(&mut self, parent: Option<TagId>, fields: Vec<usize>, local: Local) -> TagId {
131 let tag = self.nodes.len();
132 self.nodes.push(AliasNode {
133 parent,
134 fields,
135 local,
136 });
137 self.tag_of_local.insert(local, tag);
138 tag
139 }
140
141 pub(crate) fn tag_of(&self, local: Local) -> Option<TagId> {
143 self.tag_of_local.get(&local).copied()
144 }
145
146 fn resolve_to_root(&self, tag: TagId) -> (Local, Vec<usize>) {
150 let mut cur = tag;
151 let mut fields: Vec<usize> = Vec::new();
152 let mut guard = 0;
153 loop {
154 let node = &self.nodes[cur];
155 let mut combined = node.fields.clone();
156 combined.extend(fields.iter().copied());
157 fields = combined;
158 match node.parent {
159 Some(parent) => cur = parent,
160 None => return (node.local, fields),
161 }
162 guard += 1;
163 if guard > self.nodes.len() {
164 return (self.nodes[cur].local, fields);
165 }
166 }
167 }
168
169 pub(crate) fn resolve_local_to_root(&self, local: Local) -> (usize, Vec<usize>) {
172 match self.tag_of(local) {
173 Some(tag) => {
174 let (root, fields) = self.resolve_to_root(tag);
175 (root.as_usize(), fields)
176 }
177 None => (local.as_usize(), Vec::new()),
178 }
179 }
180}
181
182fn call_source_arg<'tcx>(
183 tcx: TyCtxt<'tcx>,
184 func: &Operand<'tcx>,
185 args: &[rustc_span::Spanned<Operand<'tcx>>],
186) -> Option<usize> {
187 let callee = mir_utils::dep_callee_def_id(func)?;
188 if let Some(source_arg) = alias_hazard::pointer_result_source_arg(tcx, callee) {
189 return (source_arg < args.len()).then_some(source_arg);
190 }
191 let inputs = tcx.fn_sig(callee).skip_binder().inputs().skip_binder();
192 let mut pointer_args = inputs.iter().enumerate().filter(|(index, ty)| {
193 *index < args.len() && classify(**ty).is_some()
194 });
195 let (source_arg, _) = pointer_args.next()?;
196 pointer_args.next().is_none().then_some(source_arg)
197}
198
199fn field_projection(place: &rustc_middle::mir::Place<'_>) -> Vec<usize> {
202 place
203 .projection
204 .iter()
205 .filter_map(|p| match p {
206 rustc_middle::mir::ProjectionElem::Field(idx, _) => Some(idx.as_usize()),
207 _ => None,
208 })
209 .collect()
210}
211
212fn classify(ty: Ty<'_>) -> Option<bool> {
215 match ty.kind() {
216 TyKind::Ref(_, _, _) | TyKind::RawPtr(_, _) => Some(false),
217 TyKind::Adt(_, _) => Some(true),
218 _ => None,
219 }
220}