armfortas Public

Watch 0 Fork 0 Star 0
Rust · 11719 bytes Raw Blame History
1 //! Dead Store Elimination.
2 //!
3 //! A store `Store(value, ptr)` is dead if `ptr` is written again
4 //! before it is read, with no intervening call that could observe the
5 //! stored value through that pointer.
6 //!
7 //! This pass performs a simple forward walk within each basic block.
8 //! It tracks unread stores and marks earlier ones dead when a later
9 //! store is proven `MustAlias`-equivalent via alias analysis.
10 //!
11 //! ### Scope
12 //!
13 //! * Operates within a single basic block (intraprocedural, no
14 //! dataflow across block boundaries).
15 //! * Uses alias analysis:
16 //! - later `MustAlias` store kills the earlier unread store
17 //! - `Load`/call pointer args flush any pending store that is not `NoAlias`
18 //! * Calls with no pointer args leave pending stores intact.
19 //!
20 //! ### Effect
21 //!
22 //! Primarily removes double-stores to scalar allocas that mem2reg did
23 //! not promote (e.g., `character` kind locals, variables whose address
24 //! escapes through a GEP that is later GEP'd again). Also cleans up
25 //! initialization sequences where a variable is zeroed and then
26 //! immediately written with the real value.
27
28 use super::alias::{self, AliasResult};
29 use super::pass::Pass;
30 use crate::ir::inst::*;
31 use crate::ir::types::IrType;
32 use std::collections::HashSet;
33
34 /// Eliminate dead stores within a single basic block.
35 /// Returns true if any instructions were removed.
36 fn dse_block(func: &mut Function, block_idx: usize) -> bool {
37 #[derive(Clone, Copy)]
38 struct PendingStore {
39 ptr: ValueId,
40 inst_idx: usize,
41 }
42
43 let block = &func.blocks[block_idx];
44 let mut pending: Vec<PendingStore> = Vec::new();
45 let mut dead: HashSet<usize> = HashSet::new();
46
47 for (i, inst) in block.insts.iter().enumerate() {
48 match &inst.kind {
49 InstKind::Store(_, ptr) => {
50 let mut next_pending = Vec::with_capacity(pending.len() + 1);
51 for entry in pending {
52 match alias::query(func, entry.ptr, *ptr) {
53 AliasResult::MustAlias => {
54 dead.insert(entry.inst_idx);
55 }
56 AliasResult::MayAlias | AliasResult::NoAlias => {
57 next_pending.push(entry);
58 }
59 }
60 }
61 next_pending.push(PendingStore {
62 ptr: *ptr,
63 inst_idx: i,
64 });
65 pending = next_pending;
66 }
67
68 InstKind::Load(ptr) => {
69 pending.retain(|entry| {
70 matches!(alias::query(func, entry.ptr, *ptr), AliasResult::NoAlias)
71 });
72 }
73
74 InstKind::Call(_, args) | InstKind::RuntimeCall(_, args) => {
75 // Call boundaries use the coarser predicate — same fix
76 // as LocalLsf / GlobalLsf. A callee that receives a
77 // pointer into an allocation can walk to any offset
78 // within it, so `gep %a,[0]` passed as an arg must
79 // invalidate a pending store to `gep %a,[1]` even
80 // though their precise offsets differ. Currently the
81 // Fortran programs we compile don't expose a
82 // triggering DSE pattern, but the code is structurally
83 // identical to the other LSF passes so we fix it
84 // defensively.
85 let pointer_args: Vec<ValueId> = args
86 .iter()
87 .copied()
88 .filter(|arg| matches!(func.value_type(*arg), Some(IrType::Ptr(_))))
89 .collect();
90 if !pointer_args.is_empty() {
91 pending.retain(|entry| {
92 pointer_args
93 .iter()
94 .all(|arg| !alias::may_reach_through_call_arg(func, entry.ptr, *arg))
95 });
96 }
97 }
98
99 // Memset/memcpy wrappers (external calls) are handled above via Call.
100 // All other instructions are pure reads of their operands — they
101 // cannot modify memory so they don't affect pending stores.
102 _ => {}
103 }
104 }
105 // Note: remaining entries in `pending` at block exit are stores to locals
106 // whose value has never been read in this block. We conservatively keep
107 // them — they might be read in a successor block. A full dataflow DSE
108 // (liveness across blocks) could remove them, but is deferred.
109
110 if dead.is_empty() {
111 return false;
112 }
113
114 let block = &mut func.blocks[block_idx];
115 let mut idx = 0usize;
116 block.insts.retain(|_| {
117 let keep = !dead.contains(&idx);
118 idx += 1;
119 keep
120 });
121 true
122 }
123
124 fn dse_function(func: &mut Function) -> bool {
125 let mut changed = false;
126 for block_idx in 0..func.blocks.len() {
127 if dse_block(func, block_idx) {
128 changed = true;
129 }
130 }
131 changed
132 }
133
134 pub struct Dse;
135
136 impl Pass for Dse {
137 fn name(&self) -> &'static str {
138 "dse"
139 }
140 fn run(&self, module: &mut Module) -> bool {
141 let mut changed = false;
142 for func in &mut module.functions {
143 if dse_function(func) {
144 changed = true;
145 }
146 }
147 changed
148 }
149 }
150
151 #[cfg(test)]
152 mod tests {
153 use super::*;
154 use crate::ir::types::{IntWidth, IrType};
155 use crate::lexer::{Position, Span};
156
157 fn dummy_span() -> Span {
158 let p = Position { line: 1, col: 1 };
159 Span {
160 start: p,
161 end: p,
162 file_id: 0,
163 }
164 }
165
166 fn push(f: &mut Function, kind: InstKind, ty: IrType) -> ValueId {
167 let id = f.next_value_id();
168 let entry = f.entry;
169 f.block_mut(entry).insts.push(Inst {
170 id,
171 kind,
172 ty,
173 span: dummy_span(),
174 });
175 id
176 }
177
178 fn ptr_ty() -> IrType {
179 IrType::Ptr(Box::new(IrType::Int(IntWidth::I32)))
180 }
181 fn alloca_ty() -> IrType {
182 IrType::Int(IntWidth::I32)
183 }
184 fn i32_ty() -> IrType {
185 IrType::Int(IntWidth::I32)
186 }
187
188 /// %ptr = alloca i32
189 /// store 1, %ptr
190 /// store 2, %ptr ← first store is dead
191 /// load %ptr
192 #[test]
193 fn double_store_kills_first() {
194 let mut m = Module::new("t".into());
195 let mut f = Function::new("f".into(), vec![], IrType::Void);
196 let ptr = push(&mut f, InstKind::Alloca(alloca_ty()), ptr_ty());
197 let v1 = push(&mut f, InstKind::ConstInt(1, IntWidth::I32), i32_ty());
198 let v2 = push(&mut f, InstKind::ConstInt(2, IntWidth::I32), i32_ty());
199 push(&mut f, InstKind::Store(v1, ptr), IrType::Void); // dead
200 push(&mut f, InstKind::Store(v2, ptr), IrType::Void); // live
201 let _loaded = push(&mut f, InstKind::Load(ptr), i32_ty());
202 let entry = f.entry;
203 f.block_mut(entry).terminator = Some(Terminator::Return(None));
204 m.add_function(f);
205
206 assert!(Dse.run(&mut m), "DSE should remove the dead store");
207 // alloca, v1, v2, live_store, load = 5 remaining (store 1 gone)
208 let insts = &m.functions[0].blocks[0].insts;
209 assert_eq!(insts.len(), 5, "first store should be eliminated");
210 // The surviving Store should use v2.
211 let stores: Vec<_> = insts
212 .iter()
213 .filter(|i| matches!(i.kind, InstKind::Store(..)))
214 .collect();
215 assert_eq!(stores.len(), 1);
216 assert!(matches!(stores[0].kind, InstKind::Store(v, _) if v == v2));
217 }
218
219 /// store then load: first store is live (must not be removed).
220 #[test]
221 fn store_then_load_is_live() {
222 let mut m = Module::new("t".into());
223 let mut f = Function::new("f".into(), vec![], i32_ty());
224 let ptr = push(&mut f, InstKind::Alloca(alloca_ty()), ptr_ty());
225 let v1 = push(&mut f, InstKind::ConstInt(42, IntWidth::I32), i32_ty());
226 push(&mut f, InstKind::Store(v1, ptr), IrType::Void);
227 let loaded = push(&mut f, InstKind::Load(ptr), i32_ty());
228 let entry = f.entry;
229 f.block_mut(entry).terminator = Some(Terminator::Return(Some(loaded)));
230 m.add_function(f);
231
232 assert!(!Dse.run(&mut m), "nothing should be removed");
233 assert_eq!(m.functions[0].blocks[0].insts.len(), 4);
234 }
235
236 /// Same base + same offset through distinct GEP values still aliases.
237 #[test]
238 fn same_offset_geps_kill_earlier_store() {
239 let mut m = Module::new("t".into());
240 let mut f = Function::new("f".into(), vec![], IrType::Void);
241 let arr_ty = IrType::Array(Box::new(IrType::Int(IntWidth::I32)), 4);
242 let arr_ptr_ty = IrType::Ptr(Box::new(arr_ty.clone()));
243 let ptr = push(&mut f, InstKind::Alloca(arr_ty), arr_ptr_ty);
244 let off0 = push(&mut f, InstKind::ConstInt(0, IntWidth::I32), i32_ty());
245 let off1 = push(&mut f, InstKind::ConstInt(0, IntWidth::I32), i32_ty());
246 let gep0 = push(
247 &mut f,
248 InstKind::GetElementPtr(ptr, vec![off0]),
249 IrType::Ptr(Box::new(IrType::Int(IntWidth::I8))),
250 );
251 let gep1 = push(
252 &mut f,
253 InstKind::GetElementPtr(ptr, vec![off1]),
254 IrType::Ptr(Box::new(IrType::Int(IntWidth::I8))),
255 );
256 let v1 = push(&mut f, InstKind::ConstInt(1, IntWidth::I32), i32_ty());
257 let v2 = push(&mut f, InstKind::ConstInt(2, IntWidth::I32), i32_ty());
258 push(&mut f, InstKind::Store(v1, gep0), IrType::Void); // dead
259 push(&mut f, InstKind::Store(v2, gep1), IrType::Void); // live
260 let entry = f.entry;
261 f.block_mut(entry).terminator = Some(Terminator::Return(None));
262 m.add_function(f);
263
264 assert!(Dse.run(&mut m));
265 let stores: Vec<_> = m.functions[0].blocks[0]
266 .insts
267 .iter()
268 .filter(|i| matches!(i.kind, InstKind::Store(..)))
269 .collect();
270 assert_eq!(
271 stores.len(),
272 1,
273 "must-alias GEP overwrite should kill the first store"
274 );
275 assert!(matches!(stores[0].kind, InstKind::Store(v, _) if v == v2));
276 }
277
278 /// Three consecutive stores to the same address: only the last is live.
279 #[test]
280 fn triple_store_keeps_last() {
281 let mut m = Module::new("t".into());
282 let mut f = Function::new("f".into(), vec![], IrType::Void);
283 let ptr = push(&mut f, InstKind::Alloca(alloca_ty()), ptr_ty());
284 let v1 = push(&mut f, InstKind::ConstInt(1, IntWidth::I32), i32_ty());
285 let v2 = push(&mut f, InstKind::ConstInt(2, IntWidth::I32), i32_ty());
286 let v3 = push(&mut f, InstKind::ConstInt(3, IntWidth::I32), i32_ty());
287 push(&mut f, InstKind::Store(v1, ptr), IrType::Void); // dead
288 push(&mut f, InstKind::Store(v2, ptr), IrType::Void); // dead
289 push(&mut f, InstKind::Store(v3, ptr), IrType::Void); // live (block exit)
290 let entry = f.entry;
291 f.block_mut(entry).terminator = Some(Terminator::Return(None));
292 m.add_function(f);
293
294 // After DSE: alloca + v1 + v2 + v3 + store(v3) = 5
295 // (stores of v1 and v2 are dead; store of v3 remains because it
296 // might be read in a successor — we don't do cross-block analysis)
297 assert!(Dse.run(&mut m));
298 let stores: Vec<_> = m.functions[0].blocks[0]
299 .insts
300 .iter()
301 .filter(|i| matches!(i.kind, InstKind::Store(..)))
302 .collect();
303 // Two dead stores removed, one survives.
304 assert_eq!(stores.len(), 1);
305 assert!(matches!(stores[0].kind, InstKind::Store(v, _) if v == v3));
306 }
307 }
308