armfortas Public

Watch 0 Fork 0 Star 0
Rust · 20530 bytes Raw Blame History
1 //! Alias analysis — Fortran-specific oracle.
2 //!
3 //! Determines whether two memory pointers can refer to the same
4 //! storage location. Leverages Fortran's strong aliasing guarantees:
5 //!
6 //! - Distinct `Alloca` instructions → NoAlias (different stack slots)
7 //! - Distinct `GlobalAddr` names → NoAlias (Fortran no-alias guarantee)
8 //! - Distinct ordinary Fortran dummy arguments → NoAlias
9 //! - Same pointer value → MustAlias
10 //! - GEP from same base with different constant offsets → NoAlias
11 //! - Everything else → MayAlias (conservative)
12 //!
13 //! Used by GVN (to determine if a store kills a prior load's value)
14 //! cross-block load-store forwarding, and LICM load hoisting.
15
16 use super::loop_utils::resolve_const_int;
17 use crate::ir::inst::*;
18 use crate::ir::types::IrType;
19
20 /// Result of an alias query between two pointer values.
21 #[derive(Debug, Clone, Copy, PartialEq, Eq)]
22 pub enum AliasResult {
23 /// The pointers definitely refer to the same location.
24 MustAlias,
25 /// The pointers might refer to the same location.
26 MayAlias,
27 /// The pointers definitely refer to different locations.
28 NoAlias,
29 }
30
31 /// True if `entry_ptr` may be reachable through `call_arg` when
32 /// a call passes `call_arg` across a function boundary.
33 ///
34 /// At call boundaries the precise offset-based alias check is
35 /// unsound: the callee receives the pointer and can walk to any
36 /// offset within the same allocation. `query()` would say
37 /// `NoAlias` for `gep %0, [0]` vs `gep %0, [1]` because their
38 /// offsets differ, but a callee reading through the former can
39 /// still touch the latter. Load-store forwarding and DSE must
40 /// use this coarser predicate when reasoning about calls.
41 ///
42 /// The rule: if both pointers trace to the same underlying
43 /// allocation (same alloca, same global, same param slot), they
44 /// are considered call-reachable aliases regardless of offset.
45 /// Distinct allocations remain NoAlias by Fortran's strong
46 /// aliasing guarantee.
47 pub fn may_reach_through_call_arg(func: &Function, entry_ptr: ValueId, call_arg: ValueId) -> bool {
48 if entry_ptr == call_arg {
49 return true;
50 }
51 let base_entry = trace_base(func, entry_ptr);
52 let base_arg = trace_base(func, call_arg);
53 match (&base_entry, &base_arg) {
54 (PtrBase::Alloca(a), PtrBase::Alloca(b)) => a == b,
55 (PtrBase::Global(a), PtrBase::Global(b)) => a == b,
56 (PtrBase::Param(a), PtrBase::Param(b)) => {
57 if a == b {
58 return true;
59 }
60 !(param_is_fortran_noalias(func, *a) && param_is_fortran_noalias(func, *b))
61 }
62 (PtrBase::Unknown, _) | (_, PtrBase::Unknown) => true,
63 // Distinct kinds of allocations never alias per Fortran.
64 _ => false,
65 }
66 }
67
68 /// Query whether two pointer values may alias.
69 ///
70 /// Both `a` and `b` should be pointer-typed values (results of Alloca,
71 /// GlobalAddr, GetElementPtr, or function parameters).
72 pub fn query(func: &Function, a: ValueId, b: ValueId) -> AliasResult {
73 // Same value → must alias.
74 if a == b {
75 return AliasResult::MustAlias;
76 }
77
78 // Trace both pointers to their base + offset.
79 let base_a = trace_base(func, a);
80 let base_b = trace_base(func, b);
81
82 // Different base pointers → no alias (Fortran guarantee).
83 match (&base_a, &base_b) {
84 (PtrBase::Alloca(id_a), PtrBase::Alloca(id_b)) if id_a != id_b => {
85 return AliasResult::NoAlias;
86 }
87 (PtrBase::Global(name_a), PtrBase::Global(name_b)) if name_a != name_b => {
88 return AliasResult::NoAlias;
89 }
90 (PtrBase::Param(id_a), PtrBase::Param(id_b))
91 if id_a != id_b
92 && param_is_fortran_noalias(func, *id_a)
93 && param_is_fortran_noalias(func, *id_b) =>
94 {
95 return AliasResult::NoAlias;
96 }
97 (PtrBase::Alloca(_), PtrBase::Global(_))
98 | (PtrBase::Global(_), PtrBase::Alloca(_))
99 | (PtrBase::Alloca(_), PtrBase::Param(_))
100 | (PtrBase::Param(_), PtrBase::Alloca(_)) => {
101 return AliasResult::NoAlias;
102 }
103 _ => {}
104 }
105
106 // Same base, different constant offsets → no alias.
107 if base_a.base_id() == base_b.base_id() {
108 let off_a = trace_offset(func, a);
109 let off_b = trace_offset(func, b);
110 if let (Some(oa), Some(ob)) = (off_a, off_b) {
111 if oa != ob {
112 if pointer_points_to_aggregate(func, a) || pointer_points_to_aggregate(func, b) {
113 return AliasResult::MayAlias;
114 }
115 return AliasResult::NoAlias;
116 }
117 // Same base + same offset → must alias.
118 return AliasResult::MustAlias;
119 }
120 }
121
122 AliasResult::MayAlias
123 }
124
125 fn pointer_points_to_aggregate(func: &Function, ptr: ValueId) -> bool {
126 matches!(
127 func.value_type(ptr),
128 Some(IrType::Ptr(inner)) if matches!(inner.as_ref(), IrType::Array(..) | IrType::Struct(_))
129 )
130 }
131
132 /// Traced pointer base — the root allocation or global.
133 #[derive(Debug)]
134 enum PtrBase {
135 Alloca(ValueId),
136 Global(String),
137 Param(ValueId),
138 Unknown,
139 }
140
141 impl PtrBase {
142 fn base_id(&self) -> Option<ValueId> {
143 match self {
144 PtrBase::Alloca(id) | PtrBase::Param(id) => Some(*id),
145 _ => None,
146 }
147 }
148 }
149
150 /// Trace a pointer value back to its base allocation.
151 fn trace_base(func: &Function, ptr: ValueId) -> PtrBase {
152 // Check if this is a function parameter (pointer arg).
153 for param in &func.params {
154 if param.id == ptr {
155 return PtrBase::Param(ptr);
156 }
157 }
158
159 // Find the defining instruction.
160 let Some(inst) = find_inst(func, ptr) else {
161 return PtrBase::Unknown;
162 };
163
164 match &inst.kind {
165 InstKind::Alloca(_) => PtrBase::Alloca(ptr),
166 InstKind::GlobalAddr(name) => PtrBase::Global(name.clone()),
167 InstKind::GetElementPtr(base, _) => trace_base(func, *base),
168 InstKind::Load(addr) => trace_param_wrapper(func, *addr)
169 .map(PtrBase::Param)
170 .unwrap_or(PtrBase::Unknown),
171 _ => PtrBase::Unknown,
172 }
173 }
174
175 /// Trace a pointer to its constant byte offset from the base, if possible.
176 fn trace_offset(func: &Function, ptr: ValueId) -> Option<i64> {
177 if func.params.iter().any(|param| param.id == ptr) {
178 return Some(0);
179 }
180 let inst = find_inst(func, ptr)?;
181 match &inst.kind {
182 InstKind::Alloca(_) | InstKind::GlobalAddr(_) => Some(0),
183 InstKind::Load(addr) => trace_param_wrapper(func, *addr).map(|_| 0),
184 InstKind::GetElementPtr(base, indices) => {
185 let base_offset = trace_offset(func, *base)?;
186 if indices.len() != 1 {
187 return None;
188 }
189 let idx = resolve_const_int(func, indices[0])?;
190 let step = match &inst.ty {
191 IrType::Ptr(inner) => inner.size_bytes() as i64,
192 _ => return None,
193 };
194 Some(base_offset + idx * step)
195 }
196 _ => None,
197 }
198 }
199
200 fn param_is_fortran_noalias(func: &Function, param_id: ValueId) -> bool {
201 func.params
202 .iter()
203 .find(|param| param.id == param_id)
204 .map(|param| param.fortran_noalias)
205 .unwrap_or(false)
206 }
207
208 fn trace_param_wrapper(func: &Function, addr: ValueId) -> Option<ValueId> {
209 let slot = match find_inst(func, addr).map(|inst| &inst.kind) {
210 Some(InstKind::Alloca(_)) => addr,
211 Some(InstKind::GetElementPtr(base, _)) if trace_offset(func, addr)? == 0 => {
212 match trace_base(func, *base) {
213 PtrBase::Alloca(slot) => slot,
214 _ => return None,
215 }
216 }
217 _ => return None,
218 };
219
220 let mut stored_param = None;
221 for block in &func.blocks {
222 for inst in &block.insts {
223 let InstKind::Store(val, ptr) = &inst.kind else {
224 continue;
225 };
226 if *ptr != slot {
227 continue;
228 }
229 if !func.params.iter().any(|param| param.id == *val) {
230 return None;
231 }
232 if stored_param.replace(*val).is_some() {
233 return None;
234 }
235 }
236 }
237
238 stored_param
239 }
240
241 fn find_inst(func: &Function, vid: ValueId) -> Option<&Inst> {
242 for block in &func.blocks {
243 for inst in &block.insts {
244 if inst.id == vid {
245 return Some(inst);
246 }
247 }
248 }
249 None
250 }
251
252 // ---------------------------------------------------------------------------
253 // Tests
254 // ---------------------------------------------------------------------------
255
256 #[cfg(test)]
257 mod tests {
258 use super::*;
259 use crate::ir::types::{IntWidth, IrType};
260 use crate::lexer::{Position, Span};
261
262 fn span() -> Span {
263 let pos = Position { line: 0, col: 0 };
264 Span {
265 file_id: 0,
266 start: pos,
267 end: pos,
268 }
269 }
270
271 fn param(name: &str, id: u32, ty: IrType, fortran_noalias: bool) -> Param {
272 Param {
273 name: name.into(),
274 ty,
275 id: ValueId(id),
276 fortran_noalias,
277 }
278 }
279
280 #[test]
281 fn distinct_allocas_no_alias() {
282 let mut f = Function::new("test".into(), vec![], IrType::Void);
283 let a = f.next_value_id();
284 f.register_type(a, IrType::Ptr(Box::new(IrType::Int(IntWidth::I32))));
285 f.block_mut(f.entry).insts.push(Inst {
286 id: a,
287 ty: IrType::Ptr(Box::new(IrType::Int(IntWidth::I32))),
288 span: span(),
289 kind: InstKind::Alloca(IrType::Int(IntWidth::I32)),
290 });
291 let b = f.next_value_id();
292 f.register_type(b, IrType::Ptr(Box::new(IrType::Int(IntWidth::I32))));
293 f.block_mut(f.entry).insts.push(Inst {
294 id: b,
295 ty: IrType::Ptr(Box::new(IrType::Int(IntWidth::I32))),
296 span: span(),
297 kind: InstKind::Alloca(IrType::Int(IntWidth::I32)),
298 });
299 f.block_mut(f.entry).terminator = Some(Terminator::Return(None));
300
301 assert_eq!(query(&f, a, b), AliasResult::NoAlias);
302 }
303
304 #[test]
305 fn same_pointer_must_alias() {
306 let mut f = Function::new("test".into(), vec![], IrType::Void);
307 let a = f.next_value_id();
308 f.register_type(a, IrType::Ptr(Box::new(IrType::Int(IntWidth::I32))));
309 f.block_mut(f.entry).insts.push(Inst {
310 id: a,
311 ty: IrType::Ptr(Box::new(IrType::Int(IntWidth::I32))),
312 span: span(),
313 kind: InstKind::Alloca(IrType::Int(IntWidth::I32)),
314 });
315 f.block_mut(f.entry).terminator = Some(Terminator::Return(None));
316
317 assert_eq!(query(&f, a, a), AliasResult::MustAlias);
318 }
319
320 #[test]
321 fn mixed_width_geps_same_index_do_not_must_alias() {
322 let mut f = Function::new("test".into(), vec![], IrType::Void);
323 let base_ty = IrType::Array(Box::new(IrType::Int(IntWidth::I8)), 384);
324 let base = f.next_value_id();
325 f.register_type(base, IrType::Ptr(Box::new(base_ty.clone())));
326 f.block_mut(f.entry).insts.push(Inst {
327 id: base,
328 ty: IrType::Ptr(Box::new(base_ty)),
329 span: span(),
330 kind: InstKind::Alloca(IrType::Array(Box::new(IrType::Int(IntWidth::I8)), 384)),
331 });
332
333 let four = f.next_value_id();
334 f.register_type(four, IrType::Int(IntWidth::I64));
335 f.block_mut(f.entry).insts.push(Inst {
336 id: four,
337 ty: IrType::Int(IntWidth::I64),
338 span: span(),
339 kind: InstKind::ConstInt(4, IntWidth::I64),
340 });
341
342 let gep_i32 = f.next_value_id();
343 f.register_type(gep_i32, IrType::Ptr(Box::new(IrType::Int(IntWidth::I32))));
344 f.block_mut(f.entry).insts.push(Inst {
345 id: gep_i32,
346 ty: IrType::Ptr(Box::new(IrType::Int(IntWidth::I32))),
347 span: span(),
348 kind: InstKind::GetElementPtr(base, vec![four]),
349 });
350
351 let gep_i64 = f.next_value_id();
352 f.register_type(gep_i64, IrType::Ptr(Box::new(IrType::Int(IntWidth::I64))));
353 f.block_mut(f.entry).insts.push(Inst {
354 id: gep_i64,
355 ty: IrType::Ptr(Box::new(IrType::Int(IntWidth::I64))),
356 span: span(),
357 kind: InstKind::GetElementPtr(base, vec![four]),
358 });
359
360 f.block_mut(f.entry).terminator = Some(Terminator::Return(None));
361
362 assert_eq!(query(&f, gep_i32, gep_i64), AliasResult::NoAlias);
363 }
364
365 #[test]
366 fn gep_different_offsets_no_alias() {
367 let mut f = Function::new("test".into(), vec![], IrType::Void);
368 let base = f.next_value_id();
369 f.register_type(base, IrType::Ptr(Box::new(IrType::Int(IntWidth::I32))));
370 f.block_mut(f.entry).insts.push(Inst {
371 id: base,
372 ty: IrType::Ptr(Box::new(IrType::Int(IntWidth::I32))),
373 span: span(),
374 kind: InstKind::Alloca(IrType::Array(Box::new(IrType::Int(IntWidth::I32)), 10)),
375 });
376 // GEP at offset 0
377 let c0 = f.next_value_id();
378 f.register_type(c0, IrType::Int(IntWidth::I64));
379 f.block_mut(f.entry).insts.push(Inst {
380 id: c0,
381 ty: IrType::Int(IntWidth::I64),
382 span: span(),
383 kind: InstKind::ConstInt(0, IntWidth::I64),
384 });
385 let gep0 = f.next_value_id();
386 f.register_type(gep0, IrType::Ptr(Box::new(IrType::Int(IntWidth::I32))));
387 f.block_mut(f.entry).insts.push(Inst {
388 id: gep0,
389 ty: IrType::Ptr(Box::new(IrType::Int(IntWidth::I32))),
390 span: span(),
391 kind: InstKind::GetElementPtr(base, vec![c0]),
392 });
393 // GEP at offset 1
394 let c1 = f.next_value_id();
395 f.register_type(c1, IrType::Int(IntWidth::I64));
396 f.block_mut(f.entry).insts.push(Inst {
397 id: c1,
398 ty: IrType::Int(IntWidth::I64),
399 span: span(),
400 kind: InstKind::ConstInt(1, IntWidth::I64),
401 });
402 let gep1 = f.next_value_id();
403 f.register_type(gep1, IrType::Ptr(Box::new(IrType::Int(IntWidth::I32))));
404 f.block_mut(f.entry).insts.push(Inst {
405 id: gep1,
406 ty: IrType::Ptr(Box::new(IrType::Int(IntWidth::I32))),
407 span: span(),
408 kind: InstKind::GetElementPtr(base, vec![c1]),
409 });
410 f.block_mut(f.entry).terminator = Some(Terminator::Return(None));
411
412 assert_eq!(query(&f, gep0, gep1), AliasResult::NoAlias);
413 }
414
415 #[test]
416 fn aggregate_base_and_element_gep_may_alias() {
417 let mut f = Function::new("test".into(), vec![], IrType::Void);
418 let base = f.next_value_id();
419 f.register_type(
420 base,
421 IrType::Ptr(Box::new(IrType::Array(
422 Box::new(IrType::Int(IntWidth::I32)),
423 10,
424 ))),
425 );
426 f.block_mut(f.entry).insts.push(Inst {
427 id: base,
428 ty: IrType::Ptr(Box::new(IrType::Array(
429 Box::new(IrType::Int(IntWidth::I32)),
430 10,
431 ))),
432 span: span(),
433 kind: InstKind::Alloca(IrType::Array(Box::new(IrType::Int(IntWidth::I32)), 10)),
434 });
435
436 let c1 = f.next_value_id();
437 f.register_type(c1, IrType::Int(IntWidth::I64));
438 f.block_mut(f.entry).insts.push(Inst {
439 id: c1,
440 ty: IrType::Int(IntWidth::I64),
441 span: span(),
442 kind: InstKind::ConstInt(1, IntWidth::I64),
443 });
444
445 let gep1 = f.next_value_id();
446 f.register_type(gep1, IrType::Ptr(Box::new(IrType::Int(IntWidth::I32))));
447 f.block_mut(f.entry).insts.push(Inst {
448 id: gep1,
449 ty: IrType::Ptr(Box::new(IrType::Int(IntWidth::I32))),
450 span: span(),
451 kind: InstKind::GetElementPtr(base, vec![c1]),
452 });
453 f.block_mut(f.entry).terminator = Some(Terminator::Return(None));
454
455 assert_eq!(query(&f, base, gep1), AliasResult::MayAlias);
456 }
457
458 #[test]
459 fn distinct_globals_no_alias() {
460 let mut f = Function::new("test".into(), vec![], IrType::Void);
461 let ga = f.next_value_id();
462 f.register_type(ga, IrType::Ptr(Box::new(IrType::Int(IntWidth::I32))));
463 f.block_mut(f.entry).insts.push(Inst {
464 id: ga,
465 ty: IrType::Ptr(Box::new(IrType::Int(IntWidth::I32))),
466 span: span(),
467 kind: InstKind::GlobalAddr("array_a".into()),
468 });
469 let gb = f.next_value_id();
470 f.register_type(gb, IrType::Ptr(Box::new(IrType::Int(IntWidth::I32))));
471 f.block_mut(f.entry).insts.push(Inst {
472 id: gb,
473 ty: IrType::Ptr(Box::new(IrType::Int(IntWidth::I32))),
474 span: span(),
475 kind: InstKind::GlobalAddr("array_b".into()),
476 });
477 f.block_mut(f.entry).terminator = Some(Terminator::Return(None));
478
479 assert_eq!(query(&f, ga, gb), AliasResult::NoAlias);
480 }
481
482 #[test]
483 fn distinct_noalias_params_do_not_alias() {
484 let params = vec![
485 param(
486 "a",
487 0,
488 IrType::Ptr(Box::new(IrType::Int(IntWidth::I32))),
489 true,
490 ),
491 param(
492 "b",
493 1,
494 IrType::Ptr(Box::new(IrType::Int(IntWidth::I32))),
495 true,
496 ),
497 ];
498 let mut f = Function::new("test".into(), params, IrType::Void);
499 f.block_mut(f.entry).terminator = Some(Terminator::Return(None));
500
501 assert_eq!(query(&f, ValueId(0), ValueId(1)), AliasResult::NoAlias);
502 }
503
504 #[test]
505 fn wrapper_loads_trace_back_to_noalias_params() {
506 let params = vec![
507 param(
508 "a",
509 0,
510 IrType::Ptr(Box::new(IrType::Int(IntWidth::I32))),
511 true,
512 ),
513 param(
514 "b",
515 1,
516 IrType::Ptr(Box::new(IrType::Int(IntWidth::I32))),
517 true,
518 ),
519 ];
520 let mut f = Function::new("test".into(), params, IrType::Void);
521
522 let slot_a = f.next_value_id();
523 f.register_type(
524 slot_a,
525 IrType::Ptr(Box::new(IrType::Ptr(Box::new(IrType::Int(IntWidth::I32))))),
526 );
527 f.block_mut(f.entry).insts.push(Inst {
528 id: slot_a,
529 ty: IrType::Ptr(Box::new(IrType::Ptr(Box::new(IrType::Int(IntWidth::I32))))),
530 span: span(),
531 kind: InstKind::Alloca(IrType::Ptr(Box::new(IrType::Int(IntWidth::I32)))),
532 });
533 let slot_b = f.next_value_id();
534 f.register_type(
535 slot_b,
536 IrType::Ptr(Box::new(IrType::Ptr(Box::new(IrType::Int(IntWidth::I32))))),
537 );
538 f.block_mut(f.entry).insts.push(Inst {
539 id: slot_b,
540 ty: IrType::Ptr(Box::new(IrType::Ptr(Box::new(IrType::Int(IntWidth::I32))))),
541 span: span(),
542 kind: InstKind::Alloca(IrType::Ptr(Box::new(IrType::Int(IntWidth::I32)))),
543 });
544 let store_a = f.next_value_id();
545 f.register_type(store_a, IrType::Void);
546 f.block_mut(f.entry).insts.push(Inst {
547 id: store_a,
548 ty: IrType::Void,
549 span: span(),
550 kind: InstKind::Store(ValueId(0), slot_a),
551 });
552 let store_b = f.next_value_id();
553 f.register_type(store_b, IrType::Void);
554 f.block_mut(f.entry).insts.push(Inst {
555 id: store_b,
556 ty: IrType::Void,
557 span: span(),
558 kind: InstKind::Store(ValueId(1), slot_b),
559 });
560 let load_a = f.next_value_id();
561 f.register_type(load_a, IrType::Ptr(Box::new(IrType::Int(IntWidth::I32))));
562 f.block_mut(f.entry).insts.push(Inst {
563 id: load_a,
564 ty: IrType::Ptr(Box::new(IrType::Int(IntWidth::I32))),
565 span: span(),
566 kind: InstKind::Load(slot_a),
567 });
568 let load_b = f.next_value_id();
569 f.register_type(load_b, IrType::Ptr(Box::new(IrType::Int(IntWidth::I32))));
570 f.block_mut(f.entry).insts.push(Inst {
571 id: load_b,
572 ty: IrType::Ptr(Box::new(IrType::Int(IntWidth::I32))),
573 span: span(),
574 kind: InstKind::Load(slot_b),
575 });
576 f.block_mut(f.entry).terminator = Some(Terminator::Return(None));
577
578 assert_eq!(query(&f, load_a, load_b), AliasResult::NoAlias);
579 }
580 }
581