| 1 | //! Adversarial test cases generated during the mid-pipeline audit. |
| 2 | //! |
| 3 | //! Each test is named after a finding it pins down. Tests that **fail** |
| 4 | //! against current code expose real bugs; tests that **pass** prove the |
| 5 | //! audited behavior is correct so we won't regress later. |
| 6 | |
| 7 | #![cfg(test)] |
| 8 | |
| 9 | use super::const_fold::ConstFold; |
| 10 | use super::const_prop::ConstProp; |
| 11 | use super::dce::Dce; |
| 12 | use super::licm::Licm; |
| 13 | use super::pass::Pass; |
| 14 | use super::strength_reduce::StrengthReduce; |
| 15 | use crate::ir::inst::*; |
| 16 | use crate::ir::types::{FloatWidth, IntWidth, IrType}; |
| 17 | use crate::ir::verify::verify_module; |
| 18 | use crate::lexer::{Position, Span}; |
| 19 | |
| 20 | fn dummy_span() -> Span { |
| 21 | let p = Position { line: 1, col: 1 }; |
| 22 | Span { |
| 23 | start: p, |
| 24 | end: p, |
| 25 | file_id: 0, |
| 26 | } |
| 27 | } |
| 28 | |
| 29 | fn push(f: &mut Function, kind: InstKind, ty: IrType) -> ValueId { |
| 30 | let id = f.next_value_id(); |
| 31 | let entry = f.entry; |
| 32 | f.block_mut(entry).insts.push(Inst { |
| 33 | id, |
| 34 | kind, |
| 35 | ty, |
| 36 | span: dummy_span(), |
| 37 | }); |
| 38 | id |
| 39 | } |
| 40 | |
| 41 | // ============================================================= |
| 42 | // FINDING M-1: const_fold IntToFloat doesn't round to f32 |
| 43 | // ============================================================= |
| 44 | // |
| 45 | // Round-to-even at f32 precision for i32 16777217 should yield 16777216. |
| 46 | // Currently `signed as f64` stores the exact integer value, which is |
| 47 | // outside f32 mantissa precision. Downstream FCmp/FloatToInt folds will |
| 48 | // see a value that disagrees with what runtime would compute. |
| 49 | #[test] |
| 50 | fn audit_const_fold_int_to_f32_must_round() { |
| 51 | let mut m = Module::new("t".into()); |
| 52 | let mut f = Function::new("f".into(), vec![], IrType::Float(FloatWidth::F32)); |
| 53 | let i = push( |
| 54 | &mut f, |
| 55 | InstKind::ConstInt(16_777_217, IntWidth::I32), |
| 56 | IrType::Int(IntWidth::I32), |
| 57 | ); |
| 58 | let cv = push( |
| 59 | &mut f, |
| 60 | InstKind::IntToFloat(i, FloatWidth::F32), |
| 61 | IrType::Float(FloatWidth::F32), |
| 62 | ); |
| 63 | let entry = f.entry; |
| 64 | f.block_mut(entry).terminator = Some(Terminator::Return(Some(cv))); |
| 65 | m.add_function(f); |
| 66 | |
| 67 | ConstFold.run(&mut m); |
| 68 | let folded = m.functions[0].blocks[0] |
| 69 | .insts |
| 70 | .iter() |
| 71 | .find(|i| i.id == cv) |
| 72 | .unwrap(); |
| 73 | match folded.kind { |
| 74 | InstKind::ConstFloat(v, FloatWidth::F32) => { |
| 75 | assert_eq!( |
| 76 | v, 16_777_216.0, |
| 77 | "expected f32-precision result 16_777_216.0, got {}", |
| 78 | v |
| 79 | ); |
| 80 | } |
| 81 | ref other => panic!("expected ConstFloat, got {:?}", other), |
| 82 | } |
| 83 | } |
| 84 | |
| 85 | // ============================================================= |
| 86 | // FINDING M-2: FloatExtend / FloatTrunc preserves source precision |
| 87 | // ============================================================= |
| 88 | // |
| 89 | // FloatTrunc to f32 should round through f32. Test it directly. |
| 90 | #[test] |
| 91 | fn audit_const_fold_float_trunc_must_round() { |
| 92 | let mut m = Module::new("t".into()); |
| 93 | let mut f = Function::new("f".into(), vec![], IrType::Float(FloatWidth::F32)); |
| 94 | let d = push( |
| 95 | &mut f, |
| 96 | InstKind::ConstFloat(16_777_217.0, FloatWidth::F64), |
| 97 | IrType::Float(FloatWidth::F64), |
| 98 | ); |
| 99 | let cv = push( |
| 100 | &mut f, |
| 101 | InstKind::FloatTrunc(d, FloatWidth::F32), |
| 102 | IrType::Float(FloatWidth::F32), |
| 103 | ); |
| 104 | let entry = f.entry; |
| 105 | f.block_mut(entry).terminator = Some(Terminator::Return(Some(cv))); |
| 106 | m.add_function(f); |
| 107 | |
| 108 | ConstFold.run(&mut m); |
| 109 | let folded = m.functions[0].blocks[0] |
| 110 | .insts |
| 111 | .iter() |
| 112 | .find(|i| i.id == cv) |
| 113 | .unwrap(); |
| 114 | match folded.kind { |
| 115 | InstKind::ConstFloat(v, FloatWidth::F32) => { |
| 116 | assert_eq!(v, 16_777_216.0, "expected f32-rounded value, got {}", v); |
| 117 | } |
| 118 | _ => panic!(), |
| 119 | } |
| 120 | } |
| 121 | |
| 122 | // ============================================================= |
| 123 | // FINDING M-3: strength_reduce chained identities |
| 124 | // ============================================================= |
| 125 | // |
| 126 | // Convince ourselves chains of identity rewrites land on the right |
| 127 | // terminal value. This documents the reverse-order processing. |
| 128 | #[test] |
| 129 | fn audit_strength_reduce_chained_identities() { |
| 130 | let mut m = Module::new("t".into()); |
| 131 | let mut f = Function::new("f".into(), vec![], IrType::Int(IntWidth::I32)); |
| 132 | let x = push( |
| 133 | &mut f, |
| 134 | InstKind::ConstInt(7, IntWidth::I32), |
| 135 | IrType::Int(IntWidth::I32), |
| 136 | ); |
| 137 | let one1 = push( |
| 138 | &mut f, |
| 139 | InstKind::ConstInt(1, IntWidth::I32), |
| 140 | IrType::Int(IntWidth::I32), |
| 141 | ); |
| 142 | let mul1 = push(&mut f, InstKind::IMul(x, one1), IrType::Int(IntWidth::I32)); |
| 143 | let one2 = push( |
| 144 | &mut f, |
| 145 | InstKind::ConstInt(1, IntWidth::I32), |
| 146 | IrType::Int(IntWidth::I32), |
| 147 | ); |
| 148 | let mul2 = push( |
| 149 | &mut f, |
| 150 | InstKind::IMul(mul1, one2), |
| 151 | IrType::Int(IntWidth::I32), |
| 152 | ); |
| 153 | let zero = push( |
| 154 | &mut f, |
| 155 | InstKind::ConstInt(0, IntWidth::I32), |
| 156 | IrType::Int(IntWidth::I32), |
| 157 | ); |
| 158 | let add = push( |
| 159 | &mut f, |
| 160 | InstKind::IAdd(mul2, zero), |
| 161 | IrType::Int(IntWidth::I32), |
| 162 | ); |
| 163 | let entry = f.entry; |
| 164 | f.block_mut(entry).terminator = Some(Terminator::Return(Some(add))); |
| 165 | m.add_function(f); |
| 166 | |
| 167 | StrengthReduce.run(&mut m); |
| 168 | // After three chained identities, the return must reference x. |
| 169 | let term = m.functions[0].blocks[0].terminator.as_ref().unwrap(); |
| 170 | match term { |
| 171 | Terminator::Return(Some(v)) => { |
| 172 | assert_eq!(*v, x, "expected return %{} (x), got %{}", x.0, v.0) |
| 173 | } |
| 174 | other => panic!("expected Return(x), got {:?}", other), |
| 175 | } |
| 176 | // And the IR must still verify. |
| 177 | let errs = verify_module(&m); |
| 178 | assert!( |
| 179 | errs.is_empty(), |
| 180 | "verifier errors after chained rewrites: {:?}", |
| 181 | errs |
| 182 | ); |
| 183 | } |
| 184 | |
| 185 | // ============================================================= |
| 186 | // FINDING M-4: strength_reduce ShlByConst inserts new ConstInt |
| 187 | // in same block as a chain Identity. Verifier must still pass. |
| 188 | // ============================================================= |
| 189 | #[test] |
| 190 | fn audit_strength_reduce_mixed_shl_and_identity_in_block() { |
| 191 | // %0 = const 7 |
| 192 | // %1 = const 8 ; pow-of-two |
| 193 | // %2 = imul %0, %1 ; will become shl |
| 194 | // %3 = const 1 |
| 195 | // %4 = imul %2, %3 ; identity → pass through %2 |
| 196 | // ret %4 |
| 197 | let mut m = Module::new("t".into()); |
| 198 | let mut f = Function::new("f".into(), vec![], IrType::Int(IntWidth::I32)); |
| 199 | let x = push( |
| 200 | &mut f, |
| 201 | InstKind::ConstInt(7, IntWidth::I32), |
| 202 | IrType::Int(IntWidth::I32), |
| 203 | ); |
| 204 | let eight = push( |
| 205 | &mut f, |
| 206 | InstKind::ConstInt(8, IntWidth::I32), |
| 207 | IrType::Int(IntWidth::I32), |
| 208 | ); |
| 209 | let mul1 = push(&mut f, InstKind::IMul(x, eight), IrType::Int(IntWidth::I32)); |
| 210 | let one = push( |
| 211 | &mut f, |
| 212 | InstKind::ConstInt(1, IntWidth::I32), |
| 213 | IrType::Int(IntWidth::I32), |
| 214 | ); |
| 215 | let mul2 = push( |
| 216 | &mut f, |
| 217 | InstKind::IMul(mul1, one), |
| 218 | IrType::Int(IntWidth::I32), |
| 219 | ); |
| 220 | let entry = f.entry; |
| 221 | f.block_mut(entry).terminator = Some(Terminator::Return(Some(mul2))); |
| 222 | m.add_function(f); |
| 223 | |
| 224 | StrengthReduce.run(&mut m); |
| 225 | let errs = verify_module(&m); |
| 226 | assert!(errs.is_empty(), "verifier errors: {:?}", errs); |
| 227 | |
| 228 | // The return must transitively reach the shl (identity passed through). |
| 229 | let block = &m.functions[0].blocks[0]; |
| 230 | let term_val = match block.terminator.as_ref().unwrap() { |
| 231 | Terminator::Return(Some(v)) => *v, |
| 232 | _ => panic!(), |
| 233 | }; |
| 234 | let term_kind = &block.insts.iter().find(|i| i.id == term_val).unwrap().kind; |
| 235 | assert!( |
| 236 | matches!(term_kind, InstKind::Shl(..)), |
| 237 | "expected return value to define a Shl, got {:?}", |
| 238 | term_kind |
| 239 | ); |
| 240 | } |
| 241 | |
| 242 | // ============================================================= |
| 243 | // FINDING M-5: const_fold integer division narrow-width overflow |
| 244 | // ============================================================= |
| 245 | // |
| 246 | // i8: -128 / -1 wraps to -128 in two's-complement. The fold should |
| 247 | // match what AArch64 SDIV produces. |
| 248 | #[test] |
| 249 | fn audit_const_fold_idiv_i8_min_neg_one() { |
| 250 | let mut m = Module::new("t".into()); |
| 251 | let mut f = Function::new("f".into(), vec![], IrType::Int(IntWidth::I8)); |
| 252 | let a = push( |
| 253 | &mut f, |
| 254 | InstKind::ConstInt(-128, IntWidth::I8), |
| 255 | IrType::Int(IntWidth::I8), |
| 256 | ); |
| 257 | let b = push( |
| 258 | &mut f, |
| 259 | InstKind::ConstInt(-1, IntWidth::I8), |
| 260 | IrType::Int(IntWidth::I8), |
| 261 | ); |
| 262 | let q = push(&mut f, InstKind::IDiv(a, b), IrType::Int(IntWidth::I8)); |
| 263 | let entry = f.entry; |
| 264 | f.block_mut(entry).terminator = Some(Terminator::Return(Some(q))); |
| 265 | m.add_function(f); |
| 266 | |
| 267 | ConstFold.run(&mut m); |
| 268 | let folded = m.functions[0].blocks[0] |
| 269 | .insts |
| 270 | .iter() |
| 271 | .find(|i| i.id == q) |
| 272 | .unwrap(); |
| 273 | // Either we fold to -128 (match hardware), or we leave the IDiv alone. |
| 274 | // Anything else would be a divergence. |
| 275 | match folded.kind { |
| 276 | InstKind::ConstInt(v, IntWidth::I8) => { |
| 277 | assert_eq!(v, -128, "expected -128 (i8 wraparound), got {}", v) |
| 278 | } |
| 279 | InstKind::IDiv(..) => { /* left alone, also acceptable */ } |
| 280 | ref other => panic!("unexpected fold: {:?}", other), |
| 281 | } |
| 282 | } |
| 283 | |
| 284 | // ============================================================= |
| 285 | // FINDING C-1 / Med-5: DCE removes dead block parameters and |
| 286 | // rewrites predecessor branch args in lockstep |
| 287 | // ============================================================= |
| 288 | #[test] |
| 289 | fn audit_dce_removes_dead_block_param() { |
| 290 | let mut m = Module::new("t".into()); |
| 291 | let mut f = Function::new("f".into(), vec![], IrType::Void); |
| 292 | let target = f.create_block("target"); |
| 293 | let param_id = f.next_value_id(); |
| 294 | f.block_mut(target).params.push(BlockParam { |
| 295 | id: param_id, |
| 296 | ty: IrType::Int(IntWidth::I32), |
| 297 | }); |
| 298 | let init = push( |
| 299 | &mut f, |
| 300 | InstKind::ConstInt(0, IntWidth::I32), |
| 301 | IrType::Int(IntWidth::I32), |
| 302 | ); |
| 303 | let entry = f.entry; |
| 304 | f.block_mut(entry).terminator = Some(Terminator::Branch(target, vec![init])); |
| 305 | f.block_mut(target).terminator = Some(Terminator::Return(None)); |
| 306 | m.add_function(f); |
| 307 | |
| 308 | assert!(Dce.run(&mut m), "DCE should report change"); |
| 309 | let f = &m.functions[0]; |
| 310 | assert_eq!( |
| 311 | f.block(target).params.len(), |
| 312 | 0, |
| 313 | "dead block param must be removed" |
| 314 | ); |
| 315 | // The predecessor's branch arg list must shrink in lockstep. |
| 316 | let entry_term = f.block(f.entry).terminator.as_ref().unwrap(); |
| 317 | match entry_term { |
| 318 | Terminator::Branch(_, args) => assert_eq!( |
| 319 | args.len(), |
| 320 | 0, |
| 321 | "predecessor branch arg must be dropped alongside the dead param" |
| 322 | ), |
| 323 | _ => panic!(), |
| 324 | } |
| 325 | // The const(0) inst is now unreferenced and should also be DCE'd. |
| 326 | let const_remains = f |
| 327 | .blocks |
| 328 | .iter() |
| 329 | .flat_map(|b| b.insts.iter()) |
| 330 | .any(|i| matches!(i.kind, InstKind::ConstInt(0, _))); |
| 331 | assert!( |
| 332 | !const_remains, |
| 333 | "const(0) should also be DCE'd after its only use disappears" |
| 334 | ); |
| 335 | } |
| 336 | |
| 337 | #[test] |
| 338 | fn audit_dce_keeps_live_block_param() { |
| 339 | // A block param that IS used inside the block must NOT be removed. |
| 340 | let mut m = Module::new("t".into()); |
| 341 | let mut f = Function::new("f".into(), vec![], IrType::Int(IntWidth::I32)); |
| 342 | let target = f.create_block("target"); |
| 343 | let param_id = f.next_value_id(); |
| 344 | f.block_mut(target).params.push(BlockParam { |
| 345 | id: param_id, |
| 346 | ty: IrType::Int(IntWidth::I32), |
| 347 | }); |
| 348 | let init = push( |
| 349 | &mut f, |
| 350 | InstKind::ConstInt(7, IntWidth::I32), |
| 351 | IrType::Int(IntWidth::I32), |
| 352 | ); |
| 353 | let entry = f.entry; |
| 354 | f.block_mut(entry).terminator = Some(Terminator::Branch(target, vec![init])); |
| 355 | f.block_mut(target).terminator = Some(Terminator::Return(Some(param_id))); |
| 356 | m.add_function(f); |
| 357 | |
| 358 | Dce.run(&mut m); |
| 359 | let f = &m.functions[0]; |
| 360 | assert_eq!( |
| 361 | f.block(target).params.len(), |
| 362 | 1, |
| 363 | "live block param must survive" |
| 364 | ); |
| 365 | } |
| 366 | |
| 367 | #[test] |
| 368 | fn audit_dce_removes_one_of_two_block_params_keeps_correct_arg() { |
| 369 | // target(p0:i32, p1:i32): ret p1 |
| 370 | // entry: br target(c0, c1) |
| 371 | // p0 is dead, p1 is live. Removing p0 must drop the matching |
| 372 | // arg slot but keep p1 → c1. |
| 373 | let mut m = Module::new("t".into()); |
| 374 | let mut f = Function::new("f".into(), vec![], IrType::Int(IntWidth::I32)); |
| 375 | let target = f.create_block("target"); |
| 376 | let p0 = f.next_value_id(); |
| 377 | let p1 = f.next_value_id(); |
| 378 | f.block_mut(target).params.push(BlockParam { |
| 379 | id: p0, |
| 380 | ty: IrType::Int(IntWidth::I32), |
| 381 | }); |
| 382 | f.block_mut(target).params.push(BlockParam { |
| 383 | id: p1, |
| 384 | ty: IrType::Int(IntWidth::I32), |
| 385 | }); |
| 386 | let c0 = push( |
| 387 | &mut f, |
| 388 | InstKind::ConstInt(10, IntWidth::I32), |
| 389 | IrType::Int(IntWidth::I32), |
| 390 | ); |
| 391 | let c1 = push( |
| 392 | &mut f, |
| 393 | InstKind::ConstInt(20, IntWidth::I32), |
| 394 | IrType::Int(IntWidth::I32), |
| 395 | ); |
| 396 | let entry = f.entry; |
| 397 | f.block_mut(entry).terminator = Some(Terminator::Branch(target, vec![c0, c1])); |
| 398 | f.block_mut(target).terminator = Some(Terminator::Return(Some(p1))); |
| 399 | m.add_function(f); |
| 400 | |
| 401 | Dce.run(&mut m); |
| 402 | |
| 403 | let f = &m.functions[0]; |
| 404 | let target_block = f.block(target); |
| 405 | assert_eq!(target_block.params.len(), 1, "p0 should be removed"); |
| 406 | assert_eq!(target_block.params[0].id, p1, "p1 should remain at index 0"); |
| 407 | |
| 408 | let entry_term = f.block(f.entry).terminator.as_ref().unwrap(); |
| 409 | match entry_term { |
| 410 | Terminator::Branch(_, args) => { |
| 411 | assert_eq!(args.len(), 1); |
| 412 | assert_eq!(args[0], c1, "the surviving arg must be c1, not c0"); |
| 413 | } |
| 414 | _ => panic!(), |
| 415 | } |
| 416 | |
| 417 | // Now const(10) is dead — should also be gone after the |
| 418 | // outer-loop re-runs the inner DCE. |
| 419 | let c0_remains = f |
| 420 | .blocks |
| 421 | .iter() |
| 422 | .flat_map(|b| b.insts.iter()) |
| 423 | .any(|i| i.id == c0); |
| 424 | assert!( |
| 425 | !c0_remains, |
| 426 | "const(10) should be DCE'd after its arg slot is gone" |
| 427 | ); |
| 428 | } |
| 429 | |
| 430 | // ============================================================= |
| 431 | // FINDING Med-5 / N-2 (cascading): DCE must iterate its outer |
| 432 | // loop until a fixpoint — removing one block param in round 1 |
| 433 | // can expose a *different* block param as dead in round 2. |
| 434 | // ============================================================= |
| 435 | // |
| 436 | // Shape (audit N-2 — the previous version of this test had both |
| 437 | // params dead from the start and could be satisfied in a single |
| 438 | // outer iteration, so it didn't actually pin cascading): |
| 439 | // |
| 440 | // entry: |
| 441 | // %c = const 5 |
| 442 | // br other(%c) ; passes %c → p_other |
| 443 | // |
| 444 | // other(p_other): |
| 445 | // %u = ineg p_other ; ONLY use of p_other |
| 446 | // br target(%u) ; passes %u → p_target |
| 447 | // |
| 448 | // target(p_target): ; p_target is dead |
| 449 | // ret |
| 450 | // |
| 451 | // Required rounds: |
| 452 | // R1: remove p_target, drop branch arg %u from other. |
| 453 | // R1 inner DCE: %u is now dead, remove it. Now p_other is |
| 454 | // unreferenced. |
| 455 | // R2: remove p_other, drop branch arg %c from entry. |
| 456 | // R2 inner DCE: %c is now dead, remove it. |
| 457 | // R3: no more params to remove, exit. |
| 458 | // |
| 459 | // If the outer loop were stuck at 1 iteration, p_other would |
| 460 | // survive. |
| 461 | #[test] |
| 462 | fn audit_dce_cascading_across_outer_iterations() { |
| 463 | let mut m = Module::new("t".into()); |
| 464 | let mut f = Function::new("f".into(), vec![], IrType::Void); |
| 465 | |
| 466 | // entry: computes %c, branches to other |
| 467 | let c = push( |
| 468 | &mut f, |
| 469 | InstKind::ConstInt(5, IntWidth::I32), |
| 470 | IrType::Int(IntWidth::I32), |
| 471 | ); |
| 472 | |
| 473 | // other: has param p_other, computes %u = ineg p_other, branches to target |
| 474 | let other = f.create_block("other"); |
| 475 | let p_other = f.next_value_id(); |
| 476 | f.block_mut(other).params.push(BlockParam { |
| 477 | id: p_other, |
| 478 | ty: IrType::Int(IntWidth::I32), |
| 479 | }); |
| 480 | let u = f.next_value_id(); |
| 481 | f.block_mut(other).insts.push(Inst { |
| 482 | id: u, |
| 483 | kind: InstKind::INeg(p_other), |
| 484 | ty: IrType::Int(IntWidth::I32), |
| 485 | span: dummy_span(), |
| 486 | }); |
| 487 | |
| 488 | // target: has param p_target, returns (p_target never used). |
| 489 | let target = f.create_block("target"); |
| 490 | let p_target = f.next_value_id(); |
| 491 | f.block_mut(target).params.push(BlockParam { |
| 492 | id: p_target, |
| 493 | ty: IrType::Int(IntWidth::I32), |
| 494 | }); |
| 495 | f.block_mut(target).terminator = Some(Terminator::Return(None)); |
| 496 | |
| 497 | // Wire: entry → other(%c), other → target(%u) |
| 498 | let entry = f.entry; |
| 499 | f.block_mut(entry).terminator = Some(Terminator::Branch(other, vec![c])); |
| 500 | f.block_mut(other).terminator = Some(Terminator::Branch(target, vec![u])); |
| 501 | m.add_function(f); |
| 502 | |
| 503 | Dce.run(&mut m); |
| 504 | |
| 505 | let f = &m.functions[0]; |
| 506 | |
| 507 | // Both block params must be gone. |
| 508 | assert_eq!( |
| 509 | f.block(target).params.len(), |
| 510 | 0, |
| 511 | "p_target should be removed in round 1" |
| 512 | ); |
| 513 | assert_eq!( |
| 514 | f.block(other).params.len(), |
| 515 | 0, |
| 516 | "p_other should be removed in round 2 (cascading)" |
| 517 | ); |
| 518 | |
| 519 | // Entry's branch arg list must be empty. |
| 520 | match f.block(f.entry).terminator.as_ref().unwrap() { |
| 521 | Terminator::Branch(_, args) => assert_eq!( |
| 522 | args.len(), |
| 523 | 0, |
| 524 | "entry's branch to other should have no args after cascade" |
| 525 | ), |
| 526 | _ => panic!(), |
| 527 | } |
| 528 | // other's branch to target must also have no args. |
| 529 | match f.block(other).terminator.as_ref().unwrap() { |
| 530 | Terminator::Branch(_, args) => assert_eq!( |
| 531 | args.len(), |
| 532 | 0, |
| 533 | "other's branch to target should have no args" |
| 534 | ), |
| 535 | _ => panic!(), |
| 536 | } |
| 537 | |
| 538 | // All formerly-live values should be DCE'd: %c, %u. |
| 539 | let any_inst = f |
| 540 | .blocks |
| 541 | .iter() |
| 542 | .flat_map(|b| b.insts.iter()) |
| 543 | .any(|i| i.id == c || i.id == u); |
| 544 | assert!( |
| 545 | !any_inst, |
| 546 | "dead instructions %c (const) and %u (ineg) should be DCE'd after the cascade" |
| 547 | ); |
| 548 | } |
| 549 | |
| 550 | // ============================================================= |
| 551 | // FINDING M-4 (nested loops): natural-loop discovery must not |
| 552 | // inflate an outer loop's body by following back-edges of an |
| 553 | // inner loop into paths that only reach the outer header |
| 554 | // through the inner loop. |
| 555 | // ============================================================= |
| 556 | // |
| 557 | // CFG: |
| 558 | // entry → outer_header → inner_header → inner_latch → inner_header |
| 559 | // ↑ ↓ |
| 560 | // outer_latch ←───────────────────────── ↓ |
| 561 | // ↓ |
| 562 | // exit |
| 563 | // |
| 564 | // Two loops: |
| 565 | // - Inner: header=inner_header, latch=inner_latch. |
| 566 | // Body = {inner_header, inner_latch}. |
| 567 | // - Outer: header=outer_header, latch=outer_latch. |
| 568 | // Body = {outer_header, inner_header, inner_latch, outer_latch}. |
| 569 | // |
| 570 | // The concern is that when computing the outer loop's body by |
| 571 | // walking preds(outer_latch) backwards, the BFS must correctly |
| 572 | // walk THROUGH the inner loop body. It must NOT absorb blocks |
| 573 | // outside both loops, and it MUST stop at the outer header. |
| 574 | #[test] |
| 575 | fn audit_licm_nested_loop_body_computation() { |
| 576 | use crate::opt::util::find_natural_loops; |
| 577 | |
| 578 | let mut m = Module::new("t".into()); |
| 579 | let mut f = Function::new("f".into(), vec![], IrType::Void); |
| 580 | |
| 581 | let outer_header = f.create_block("outer_header"); |
| 582 | let inner_header = f.create_block("inner_header"); |
| 583 | let inner_latch = f.create_block("inner_latch"); |
| 584 | let outer_latch = f.create_block("outer_latch"); |
| 585 | let exit = f.create_block("exit"); |
| 586 | let entry = f.entry; |
| 587 | |
| 588 | // entry → outer_header |
| 589 | f.block_mut(entry).terminator = Some(Terminator::Branch(outer_header, vec![])); |
| 590 | |
| 591 | // outer_header: cond_br → inner_header / exit |
| 592 | let c1 = f.next_value_id(); |
| 593 | f.block_mut(outer_header).insts.push(Inst { |
| 594 | id: c1, |
| 595 | kind: InstKind::ConstBool(true), |
| 596 | ty: IrType::Bool, |
| 597 | span: dummy_span(), |
| 598 | }); |
| 599 | f.block_mut(outer_header).terminator = Some(Terminator::CondBranch { |
| 600 | cond: c1, |
| 601 | true_dest: inner_header, |
| 602 | true_args: vec![], |
| 603 | false_dest: exit, |
| 604 | false_args: vec![], |
| 605 | }); |
| 606 | |
| 607 | // inner_header: cond_br → inner_latch / outer_latch |
| 608 | let c2 = f.next_value_id(); |
| 609 | f.block_mut(inner_header).insts.push(Inst { |
| 610 | id: c2, |
| 611 | kind: InstKind::ConstBool(true), |
| 612 | ty: IrType::Bool, |
| 613 | span: dummy_span(), |
| 614 | }); |
| 615 | f.block_mut(inner_header).terminator = Some(Terminator::CondBranch { |
| 616 | cond: c2, |
| 617 | true_dest: inner_latch, |
| 618 | true_args: vec![], |
| 619 | false_dest: outer_latch, |
| 620 | false_args: vec![], |
| 621 | }); |
| 622 | |
| 623 | // inner_latch → inner_header (back-edge) |
| 624 | f.block_mut(inner_latch).terminator = Some(Terminator::Branch(inner_header, vec![])); |
| 625 | |
| 626 | // outer_latch → outer_header (back-edge) |
| 627 | f.block_mut(outer_latch).terminator = Some(Terminator::Branch(outer_header, vec![])); |
| 628 | |
| 629 | // exit: return |
| 630 | f.block_mut(exit).terminator = Some(Terminator::Return(None)); |
| 631 | |
| 632 | m.add_function(f); |
| 633 | |
| 634 | let loops = find_natural_loops(&m.functions[0]); |
| 635 | assert_eq!(loops.len(), 2, "expected exactly two natural loops"); |
| 636 | |
| 637 | // Find the inner and outer loops by their headers. |
| 638 | let inner = loops |
| 639 | .iter() |
| 640 | .find(|l| l.header == inner_header) |
| 641 | .expect("inner loop not found"); |
| 642 | let outer = loops |
| 643 | .iter() |
| 644 | .find(|l| l.header == outer_header) |
| 645 | .expect("outer loop not found"); |
| 646 | |
| 647 | // Inner loop body: {inner_header, inner_latch}. |
| 648 | assert_eq!( |
| 649 | inner.body.len(), |
| 650 | 2, |
| 651 | "inner body should be {{inner_header, inner_latch}}, got {:?}", |
| 652 | inner.body |
| 653 | ); |
| 654 | assert!(inner.body.contains(&inner_header)); |
| 655 | assert!(inner.body.contains(&inner_latch)); |
| 656 | |
| 657 | // Outer loop body: {outer_header, inner_header, inner_latch, outer_latch}. |
| 658 | // MUST NOT contain entry or exit. |
| 659 | assert_eq!( |
| 660 | outer.body.len(), |
| 661 | 4, |
| 662 | "outer body should be {{outer_header, inner_header, inner_latch, outer_latch}}, got {:?}", |
| 663 | outer.body |
| 664 | ); |
| 665 | assert!(outer.body.contains(&outer_header)); |
| 666 | assert!(outer.body.contains(&inner_header)); |
| 667 | assert!(outer.body.contains(&inner_latch)); |
| 668 | assert!(outer.body.contains(&outer_latch)); |
| 669 | assert!( |
| 670 | !outer.body.contains(&entry), |
| 671 | "outer body must not include entry" |
| 672 | ); |
| 673 | assert!( |
| 674 | !outer.body.contains(&exit), |
| 675 | "outer body must not include exit" |
| 676 | ); |
| 677 | } |
| 678 | |
| 679 | // ============================================================= |
| 680 | // FINDING M-7 (multi-latch): a loop with both a self-loop on |
| 681 | // the header AND a separate distinct latch. |
| 682 | // ============================================================= |
| 683 | // |
| 684 | // CFG: |
| 685 | // entry → header |
| 686 | // header → header (self-loop, true_dest = header itself) |
| 687 | // header → other |
| 688 | // other → header (back-edge from a separate latch) |
| 689 | // header → exit (one of the cond branches) |
| 690 | // |
| 691 | // Both latches map to the same header. The body should include |
| 692 | // {header, other}, NOT entry. find_preheader should still pick |
| 693 | // entry as the preheader. |
| 694 | #[test] |
| 695 | fn audit_licm_multi_latch_with_self_loop() { |
| 696 | use crate::opt::util::find_natural_loops; |
| 697 | |
| 698 | let mut m = Module::new("t".into()); |
| 699 | let mut f = Function::new("f".into(), vec![], IrType::Void); |
| 700 | let header = f.create_block("header"); |
| 701 | let other = f.create_block("other"); |
| 702 | let exit = f.create_block("exit"); |
| 703 | let entry = f.entry; |
| 704 | |
| 705 | // entry → header |
| 706 | f.block_mut(entry).terminator = Some(Terminator::Branch(header, vec![])); |
| 707 | // header → header (true) or other (false), with cond |
| 708 | let cond = f.next_value_id(); |
| 709 | f.block_mut(header).insts.push(Inst { |
| 710 | id: cond, |
| 711 | kind: InstKind::ConstBool(true), |
| 712 | ty: IrType::Bool, |
| 713 | span: dummy_span(), |
| 714 | }); |
| 715 | f.block_mut(header).terminator = Some(Terminator::CondBranch { |
| 716 | cond, |
| 717 | true_dest: header, |
| 718 | true_args: vec![], |
| 719 | false_dest: other, |
| 720 | false_args: vec![], |
| 721 | }); |
| 722 | // other → header (back edge) or exit |
| 723 | let cond2 = f.next_value_id(); |
| 724 | f.block_mut(other).insts.push(Inst { |
| 725 | id: cond2, |
| 726 | kind: InstKind::ConstBool(false), |
| 727 | ty: IrType::Bool, |
| 728 | span: dummy_span(), |
| 729 | }); |
| 730 | f.block_mut(other).terminator = Some(Terminator::CondBranch { |
| 731 | cond: cond2, |
| 732 | true_dest: header, |
| 733 | true_args: vec![], |
| 734 | false_dest: exit, |
| 735 | false_args: vec![], |
| 736 | }); |
| 737 | f.block_mut(exit).terminator = Some(Terminator::Return(None)); |
| 738 | m.add_function(f); |
| 739 | |
| 740 | let loops = find_natural_loops(&m.functions[0]); |
| 741 | assert_eq!(loops.len(), 1, "expected exactly one natural loop"); |
| 742 | let lp = &loops[0]; |
| 743 | assert_eq!(lp.header, header); |
| 744 | // Body must include header and other, NOT entry. |
| 745 | assert!(lp.body.contains(&header), "body must include header"); |
| 746 | assert!(lp.body.contains(&other), "body must include other"); |
| 747 | assert!( |
| 748 | !lp.body.contains(&entry), |
| 749 | "body must NOT include the preheader (entry)" |
| 750 | ); |
| 751 | assert!( |
| 752 | !lp.body.contains(&exit), |
| 753 | "body must NOT include the exit block" |
| 754 | ); |
| 755 | // Latches: both header (self-loop) and other (back edge). |
| 756 | assert_eq!(lp.latches.len(), 2, "expected two latches"); |
| 757 | assert!(lp.latches.contains(&header)); |
| 758 | assert!(lp.latches.contains(&other)); |
| 759 | } |
| 760 | |
| 761 | // ============================================================= |
| 762 | // FINDING C-2 (closed): LICM now hoists memory-clean local loads |
| 763 | // ============================================================= |
| 764 | // |
| 765 | // Mirrors the loop_sum.f90 IR shape with the strongest safe case: the |
| 766 | // loop reads a stack slot that is initialized before the loop and never |
| 767 | // written again inside the loop. LICM should hoist both the invariant |
| 768 | // const and the invariant load into the preheader. |
| 769 | #[test] |
| 770 | fn audit_licm_hoists_clean_alloca_load() { |
| 771 | let mut m = Module::new("t".into()); |
| 772 | let mut f = Function::new("f".into(), vec![], IrType::Void); |
| 773 | let slot = push( |
| 774 | &mut f, |
| 775 | InstKind::Alloca(IrType::Int(IntWidth::I32)), |
| 776 | IrType::Ptr(Box::new(IrType::Int(IntWidth::I32))), |
| 777 | ); |
| 778 | let init = push( |
| 779 | &mut f, |
| 780 | InstKind::ConstInt(0, IntWidth::I32), |
| 781 | IrType::Int(IntWidth::I32), |
| 782 | ); |
| 783 | push(&mut f, InstKind::Store(init, slot), IrType::Void); |
| 784 | |
| 785 | let header = f.create_block("header"); |
| 786 | let i_param = f.next_value_id(); |
| 787 | f.block_mut(header).params.push(BlockParam { |
| 788 | id: i_param, |
| 789 | ty: IrType::Int(IntWidth::I32), |
| 790 | }); |
| 791 | let v = f.next_value_id(); |
| 792 | f.block_mut(header).insts.push(Inst { |
| 793 | id: v, |
| 794 | kind: InstKind::Load(slot), |
| 795 | ty: IrType::Int(IntWidth::I32), |
| 796 | span: dummy_span(), |
| 797 | }); |
| 798 | let one = f.next_value_id(); |
| 799 | f.block_mut(header).insts.push(Inst { |
| 800 | id: one, |
| 801 | kind: InstKind::ConstInt(1, IntWidth::I32), |
| 802 | ty: IrType::Int(IntWidth::I32), |
| 803 | span: dummy_span(), |
| 804 | }); |
| 805 | let next = f.next_value_id(); |
| 806 | f.block_mut(header).insts.push(Inst { |
| 807 | id: next, |
| 808 | kind: InstKind::IAdd(v, one), |
| 809 | ty: IrType::Int(IntWidth::I32), |
| 810 | span: dummy_span(), |
| 811 | }); |
| 812 | let exit = f.create_block("exit"); |
| 813 | f.block_mut(exit).terminator = Some(Terminator::Return(None)); |
| 814 | f.block_mut(header).terminator = Some(Terminator::CondBranch { |
| 815 | cond: i_param, // phony cond, just to have a back edge |
| 816 | true_dest: header, |
| 817 | true_args: vec![next], |
| 818 | false_dest: exit, |
| 819 | false_args: vec![], |
| 820 | }); |
| 821 | let entry = f.entry; |
| 822 | f.block_mut(entry).terminator = Some(Terminator::Branch(header, vec![init])); |
| 823 | m.add_function(f); |
| 824 | |
| 825 | // The const(1) inside the header IS loop-invariant — LICM should hoist it. |
| 826 | Licm.run(&mut m); |
| 827 | let entry_block = m.functions[0].block(m.functions[0].entry); |
| 828 | let const1_in_entry = entry_block |
| 829 | .insts |
| 830 | .iter() |
| 831 | .any(|i| matches!(i.kind, InstKind::ConstInt(1, IntWidth::I32))); |
| 832 | assert!( |
| 833 | const1_in_entry, |
| 834 | "LICM should have hoisted const(1) into the preheader" |
| 835 | ); |
| 836 | // The load is now loop-invariant too: no loop store/call can clobber it. |
| 837 | let header_block = &m.functions[0].blocks[1]; |
| 838 | let load_still_in_header = header_block |
| 839 | .insts |
| 840 | .iter() |
| 841 | .any(|i| matches!(i.kind, InstKind::Load(_))); |
| 842 | assert!( |
| 843 | !load_still_in_header, |
| 844 | "LICM should hoist a load when the loop is memory-clean" |
| 845 | ); |
| 846 | let load_in_entry = entry_block |
| 847 | .insts |
| 848 | .iter() |
| 849 | .any(|i| matches!(i.kind, InstKind::Load(_))); |
| 850 | assert!( |
| 851 | load_in_entry, |
| 852 | "LICM should move the memory-clean load into the preheader" |
| 853 | ); |
| 854 | } |
| 855 | |
| 856 | // ============================================================= |
| 857 | // FINDING M-8: LICM must not corrupt the IR through PassManager |
| 858 | // ============================================================= |
| 859 | // |
| 860 | // Run a synthetic loop module through the full O2 pipeline. Anything |
| 861 | // that fails the verifier was a real soundness bug. |
| 862 | #[test] |
| 863 | fn audit_pipeline_o2_e2e_loop_through_passmanager() { |
| 864 | use crate::opt::{build_pipeline, OptLevel}; |
| 865 | |
| 866 | let mut m = Module::new("t".into()); |
| 867 | let mut f = Function::new("f".into(), vec![], IrType::Void); |
| 868 | // Build: entry { %0=const 0; br header(%0) } |
| 869 | // header(%i:i32) { %k=const 5; %i2=iadd %i, %k; %lim=const 10; |
| 870 | // %d=icmp ge %i, %lim; cbr %d, exit, latch(%i2) } |
| 871 | // latch(%i_in:i32) { %1=const 1; %n=iadd %i_in, %1; br header(%n) } |
| 872 | // exit { ret } |
| 873 | let init = push( |
| 874 | &mut f, |
| 875 | InstKind::ConstInt(0, IntWidth::I32), |
| 876 | IrType::Int(IntWidth::I32), |
| 877 | ); |
| 878 | |
| 879 | let header = f.create_block("header"); |
| 880 | let i_param = f.next_value_id(); |
| 881 | f.block_mut(header).params.push(BlockParam { |
| 882 | id: i_param, |
| 883 | ty: IrType::Int(IntWidth::I32), |
| 884 | }); |
| 885 | |
| 886 | let k = f.next_value_id(); |
| 887 | f.block_mut(header).insts.push(Inst { |
| 888 | id: k, |
| 889 | kind: InstKind::ConstInt(5, IntWidth::I32), |
| 890 | ty: IrType::Int(IntWidth::I32), |
| 891 | span: dummy_span(), |
| 892 | }); |
| 893 | let i2 = f.next_value_id(); |
| 894 | f.block_mut(header).insts.push(Inst { |
| 895 | id: i2, |
| 896 | kind: InstKind::IAdd(i_param, k), |
| 897 | ty: IrType::Int(IntWidth::I32), |
| 898 | span: dummy_span(), |
| 899 | }); |
| 900 | let lim = f.next_value_id(); |
| 901 | f.block_mut(header).insts.push(Inst { |
| 902 | id: lim, |
| 903 | kind: InstKind::ConstInt(10, IntWidth::I32), |
| 904 | ty: IrType::Int(IntWidth::I32), |
| 905 | span: dummy_span(), |
| 906 | }); |
| 907 | let done = f.next_value_id(); |
| 908 | f.block_mut(header).insts.push(Inst { |
| 909 | id: done, |
| 910 | kind: InstKind::ICmp(CmpOp::Ge, i_param, lim), |
| 911 | ty: IrType::Bool, |
| 912 | span: dummy_span(), |
| 913 | }); |
| 914 | |
| 915 | let latch = f.create_block("latch"); |
| 916 | let i_in = f.next_value_id(); |
| 917 | f.block_mut(latch).params.push(BlockParam { |
| 918 | id: i_in, |
| 919 | ty: IrType::Int(IntWidth::I32), |
| 920 | }); |
| 921 | let one = f.next_value_id(); |
| 922 | f.block_mut(latch).insts.push(Inst { |
| 923 | id: one, |
| 924 | kind: InstKind::ConstInt(1, IntWidth::I32), |
| 925 | ty: IrType::Int(IntWidth::I32), |
| 926 | span: dummy_span(), |
| 927 | }); |
| 928 | let next = f.next_value_id(); |
| 929 | f.block_mut(latch).insts.push(Inst { |
| 930 | id: next, |
| 931 | kind: InstKind::IAdd(i_in, one), |
| 932 | ty: IrType::Int(IntWidth::I32), |
| 933 | span: dummy_span(), |
| 934 | }); |
| 935 | f.block_mut(latch).terminator = Some(Terminator::Branch(header, vec![next])); |
| 936 | |
| 937 | let exit = f.create_block("exit"); |
| 938 | f.block_mut(exit).terminator = Some(Terminator::Return(None)); |
| 939 | |
| 940 | let entry = f.entry; |
| 941 | f.block_mut(entry).terminator = Some(Terminator::Branch(header, vec![init])); |
| 942 | f.block_mut(header).terminator = Some(Terminator::CondBranch { |
| 943 | cond: done, |
| 944 | true_dest: exit, |
| 945 | true_args: vec![], |
| 946 | false_dest: latch, |
| 947 | false_args: vec![i2], |
| 948 | }); |
| 949 | m.add_function(f); |
| 950 | |
| 951 | // verify the input is well-formed |
| 952 | assert!(verify_module(&m).is_empty(), "test setup invalid"); |
| 953 | |
| 954 | let pm = build_pipeline(OptLevel::O2); |
| 955 | pm.run(&mut m); |
| 956 | |
| 957 | // Final IR must verify. |
| 958 | let errs = verify_module(&m); |
| 959 | assert!( |
| 960 | errs.is_empty(), |
| 961 | "O2 pipeline left an invalid module: {:?}", |
| 962 | errs |
| 963 | ); |
| 964 | } |
| 965 | |
| 966 | // ============================================================= |
| 967 | // FINDING (interaction): const_prop drops a block whose ONLY use |
| 968 | // of a value is now gone — does DCE then drop the value too? |
| 969 | // ============================================================= |
| 970 | // |
| 971 | // Pipeline: const_prop folds CondBranch and prunes the dead arm, |
| 972 | // which removes the only consumer of some constant. DCE should then |
| 973 | // remove the constant. Verify the cooperation works end-to-end. |
| 974 | #[test] |
| 975 | fn audit_interaction_const_prop_then_dce_removes_orphan_const() { |
| 976 | use crate::opt::{build_pipeline, OptLevel}; |
| 977 | |
| 978 | let mut m = Module::new("t".into()); |
| 979 | let mut f = Function::new("f".into(), vec![], IrType::Void); |
| 980 | let cond = push(&mut f, InstKind::ConstBool(true), IrType::Bool); |
| 981 | // This constant is ONLY used in the about-to-be-dead else block. |
| 982 | let dead_only = push( |
| 983 | &mut f, |
| 984 | InstKind::ConstInt(99, IntWidth::I32), |
| 985 | IrType::Int(IntWidth::I32), |
| 986 | ); |
| 987 | |
| 988 | let then_b = f.create_block("then"); |
| 989 | let else_b = f.create_block("else"); |
| 990 | |
| 991 | // Use dead_only inside else (will be dropped by const_prop). |
| 992 | let unused = f.next_value_id(); |
| 993 | f.block_mut(else_b).insts.push(Inst { |
| 994 | id: unused, |
| 995 | kind: InstKind::INeg(dead_only), |
| 996 | ty: IrType::Int(IntWidth::I32), |
| 997 | span: dummy_span(), |
| 998 | }); |
| 999 | f.block_mut(else_b).terminator = Some(Terminator::Return(None)); |
| 1000 | f.block_mut(then_b).terminator = Some(Terminator::Return(None)); |
| 1001 | |
| 1002 | let entry = f.entry; |
| 1003 | f.block_mut(entry).terminator = Some(Terminator::CondBranch { |
| 1004 | cond, |
| 1005 | true_dest: then_b, |
| 1006 | true_args: vec![], |
| 1007 | false_dest: else_b, |
| 1008 | false_args: vec![], |
| 1009 | }); |
| 1010 | m.add_function(f); |
| 1011 | |
| 1012 | let pm = build_pipeline(OptLevel::O2); |
| 1013 | pm.run(&mut m); |
| 1014 | |
| 1015 | let post = verify_module(&m); |
| 1016 | assert!(post.is_empty(), "post-pipeline IR invalid: {:?}", post); |
| 1017 | |
| 1018 | // After: else block gone, const(99) and ineg gone too. |
| 1019 | let f = &m.functions[0]; |
| 1020 | assert!( |
| 1021 | !f.blocks.iter().any(|b| b.id == else_b), |
| 1022 | "else block should be pruned" |
| 1023 | ); |
| 1024 | let dead_remains = f |
| 1025 | .blocks |
| 1026 | .iter() |
| 1027 | .flat_map(|b| b.insts.iter()) |
| 1028 | .any(|i| matches!(i.kind, InstKind::ConstInt(99, _))); |
| 1029 | assert!( |
| 1030 | !dead_remains, |
| 1031 | "const(99) should be DCE'd after const_prop drops its only use" |
| 1032 | ); |
| 1033 | } |
| 1034 | |
| 1035 | // ============================================================= |
| 1036 | // FINDING (interaction): strength_reduce + DCE remove the orphan |
| 1037 | // constant created by an Identity rewrite. |
| 1038 | // ============================================================= |
| 1039 | #[test] |
| 1040 | fn audit_interaction_strength_reduce_orphans_get_dced() { |
| 1041 | use crate::opt::{build_pipeline, OptLevel}; |
| 1042 | |
| 1043 | let mut m = Module::new("t".into()); |
| 1044 | let mut f = Function::new("f".into(), vec![], IrType::Int(IntWidth::I32)); |
| 1045 | let x = push( |
| 1046 | &mut f, |
| 1047 | InstKind::ConstInt(42, IntWidth::I32), |
| 1048 | IrType::Int(IntWidth::I32), |
| 1049 | ); |
| 1050 | let one = push( |
| 1051 | &mut f, |
| 1052 | InstKind::ConstInt(1, IntWidth::I32), |
| 1053 | IrType::Int(IntWidth::I32), |
| 1054 | ); |
| 1055 | let mul = push(&mut f, InstKind::IMul(x, one), IrType::Int(IntWidth::I32)); |
| 1056 | let entry = f.entry; |
| 1057 | f.block_mut(entry).terminator = Some(Terminator::Return(Some(mul))); |
| 1058 | m.add_function(f); |
| 1059 | |
| 1060 | let pm = build_pipeline(OptLevel::O2); |
| 1061 | pm.run(&mut m); |
| 1062 | |
| 1063 | // strength_reduce makes mul an identity (passes through to x), then |
| 1064 | // turns the original mul inst into Const(0). DCE should remove that. |
| 1065 | let post = verify_module(&m); |
| 1066 | assert!(post.is_empty(), "post-pipeline IR invalid: {:?}", post); |
| 1067 | |
| 1068 | let f = &m.functions[0]; |
| 1069 | // The terminator should now reference x directly. |
| 1070 | let term_val = match f.blocks[0].terminator.as_ref().unwrap() { |
| 1071 | Terminator::Return(Some(v)) => *v, |
| 1072 | _ => panic!(), |
| 1073 | }; |
| 1074 | assert_eq!(term_val, x, "expected return to be x directly"); |
| 1075 | |
| 1076 | // The orphan placeholder should be gone. |
| 1077 | let extra_const = f.blocks[0] |
| 1078 | .insts |
| 1079 | .iter() |
| 1080 | .filter(|i| matches!(i.kind, InstKind::ConstInt(0, _))) |
| 1081 | .count(); |
| 1082 | assert_eq!( |
| 1083 | extra_const, 0, |
| 1084 | "strength_reduce orphan placeholder Const(0) should be DCE'd" |
| 1085 | ); |
| 1086 | } |
| 1087 | |
| 1088 | // ============================================================= |
| 1089 | // FINDING M-B: const_fold Shl with count == width must NOT |
| 1090 | // fold to 0 (AArch64 LSL masks the count, not zeros it). |
| 1091 | // ============================================================= |
| 1092 | #[test] |
| 1093 | fn audit_const_fold_shl_at_width_bails() { |
| 1094 | // shl 1_i32, 32_i32 — count equals width, AArch64 masks to 0, |
| 1095 | // so the runtime answer is 1. The fold MUST NOT silently emit 0. |
| 1096 | let mut m = Module::new("t".into()); |
| 1097 | let mut f = Function::new("f".into(), vec![], IrType::Int(IntWidth::I32)); |
| 1098 | let v = push( |
| 1099 | &mut f, |
| 1100 | InstKind::ConstInt(1, IntWidth::I32), |
| 1101 | IrType::Int(IntWidth::I32), |
| 1102 | ); |
| 1103 | let cnt = push( |
| 1104 | &mut f, |
| 1105 | InstKind::ConstInt(32, IntWidth::I32), |
| 1106 | IrType::Int(IntWidth::I32), |
| 1107 | ); |
| 1108 | let s = push(&mut f, InstKind::Shl(v, cnt), IrType::Int(IntWidth::I32)); |
| 1109 | let entry = f.entry; |
| 1110 | f.block_mut(entry).terminator = Some(Terminator::Return(Some(s))); |
| 1111 | m.add_function(f); |
| 1112 | |
| 1113 | ConstFold.run(&mut m); |
| 1114 | let folded = m.functions[0].blocks[0] |
| 1115 | .insts |
| 1116 | .iter() |
| 1117 | .find(|i| i.id == s) |
| 1118 | .unwrap(); |
| 1119 | // Acceptable outcomes: leave the Shl alone, OR mask the count. |
| 1120 | // NOT acceptable: ConstInt(0, _). |
| 1121 | if let InstKind::ConstInt(0, _) = folded.kind { |
| 1122 | panic!("audit M-B: shl with count==width folded to 0 — diverges from AArch64 LSL"); |
| 1123 | } |
| 1124 | } |
| 1125 | |
| 1126 | // ============================================================= |
| 1127 | // FINDING M-C: const_fold Shl with negative count must not fold to 0 |
| 1128 | // ============================================================= |
| 1129 | #[test] |
| 1130 | fn audit_const_fold_shl_negative_count_bails() { |
| 1131 | let mut m = Module::new("t".into()); |
| 1132 | let mut f = Function::new("f".into(), vec![], IrType::Int(IntWidth::I32)); |
| 1133 | let v = push( |
| 1134 | &mut f, |
| 1135 | InstKind::ConstInt(7, IntWidth::I32), |
| 1136 | IrType::Int(IntWidth::I32), |
| 1137 | ); |
| 1138 | let cnt = push( |
| 1139 | &mut f, |
| 1140 | InstKind::ConstInt(-1, IntWidth::I32), |
| 1141 | IrType::Int(IntWidth::I32), |
| 1142 | ); |
| 1143 | let s = push(&mut f, InstKind::Shl(v, cnt), IrType::Int(IntWidth::I32)); |
| 1144 | let entry = f.entry; |
| 1145 | f.block_mut(entry).terminator = Some(Terminator::Return(Some(s))); |
| 1146 | m.add_function(f); |
| 1147 | |
| 1148 | ConstFold.run(&mut m); |
| 1149 | let folded = m.functions[0].blocks[0] |
| 1150 | .insts |
| 1151 | .iter() |
| 1152 | .find(|i| i.id == s) |
| 1153 | .unwrap(); |
| 1154 | if let InstKind::ConstInt(0, _) = folded.kind { |
| 1155 | panic!("audit M-C: shl with negative count folded to 0 — wrong on AArch64"); |
| 1156 | } |
| 1157 | } |
| 1158 | |
| 1159 | // ============================================================= |
| 1160 | // FINDING M-C: same for LShr / AShr |
| 1161 | // ============================================================= |
| 1162 | #[test] |
| 1163 | fn audit_const_fold_lshr_negative_count_bails() { |
| 1164 | let mut m = Module::new("t".into()); |
| 1165 | let mut f = Function::new("f".into(), vec![], IrType::Int(IntWidth::I32)); |
| 1166 | let v = push( |
| 1167 | &mut f, |
| 1168 | InstKind::ConstInt(64, IntWidth::I32), |
| 1169 | IrType::Int(IntWidth::I32), |
| 1170 | ); |
| 1171 | let cnt = push( |
| 1172 | &mut f, |
| 1173 | InstKind::ConstInt(-2, IntWidth::I32), |
| 1174 | IrType::Int(IntWidth::I32), |
| 1175 | ); |
| 1176 | let s = push(&mut f, InstKind::LShr(v, cnt), IrType::Int(IntWidth::I32)); |
| 1177 | let entry = f.entry; |
| 1178 | f.block_mut(entry).terminator = Some(Terminator::Return(Some(s))); |
| 1179 | m.add_function(f); |
| 1180 | |
| 1181 | ConstFold.run(&mut m); |
| 1182 | let folded = m.functions[0].blocks[0] |
| 1183 | .insts |
| 1184 | .iter() |
| 1185 | .find(|i| i.id == s) |
| 1186 | .unwrap(); |
| 1187 | if let InstKind::ConstInt(0, _) = folded.kind { |
| 1188 | panic!("audit M-C: lshr with negative count folded to 0"); |
| 1189 | } |
| 1190 | } |
| 1191 | |
| 1192 | // ============================================================= |
| 1193 | // FINDING N-1 / N-9 (re-re-audit): width drift in integer |
| 1194 | // arithmetic folds. The B-1 Select fix was applied only to |
| 1195 | // Select; the same shape exists in every binary int op. The N-9 |
| 1196 | // root-cause fix normalizes at `Const::from_inst`, so every |
| 1197 | // downstream fold now operates on canonical (sign-extended) |
| 1198 | // values regardless of how the source ConstInt is stored. |
| 1199 | // ============================================================= |
| 1200 | // |
| 1201 | // Each test builds a synthetic i32 operation whose operands are |
| 1202 | // ConstInt(_, I8) with raw values that represent different signed |
| 1203 | // values. Without N-9, the folds would compute on the raw i64 |
| 1204 | // storage and produce wrong results. With N-9, the stored values |
| 1205 | // are canonicalized at insert, so the fold gets the correct |
| 1206 | // signed interpretation. |
| 1207 | |
| 1208 | #[test] |
| 1209 | fn audit_const_fold_width_drift_iadd() { |
| 1210 | // a: ConstInt(255, I8) = -1 at i8 |
| 1211 | // b: ConstInt(2, I8) = 2 at i8 |
| 1212 | // declared IAdd type: i32 |
| 1213 | // Expected: -1 + 2 = 1 |
| 1214 | // Pre-fix: 255 + 2 = 257 (wrong) |
| 1215 | let mut m = Module::new("t".into()); |
| 1216 | let mut f = Function::new("f".into(), vec![], IrType::Int(IntWidth::I32)); |
| 1217 | let a = f.next_value_id(); |
| 1218 | f.block_mut(f.entry).insts.push(Inst { |
| 1219 | id: a, |
| 1220 | kind: InstKind::ConstInt(255, IntWidth::I8), |
| 1221 | ty: IrType::Int(IntWidth::I8), |
| 1222 | span: dummy_span(), |
| 1223 | }); |
| 1224 | let b = f.next_value_id(); |
| 1225 | f.block_mut(f.entry).insts.push(Inst { |
| 1226 | id: b, |
| 1227 | kind: InstKind::ConstInt(2, IntWidth::I8), |
| 1228 | ty: IrType::Int(IntWidth::I8), |
| 1229 | span: dummy_span(), |
| 1230 | }); |
| 1231 | let sum = f.next_value_id(); |
| 1232 | f.block_mut(f.entry).insts.push(Inst { |
| 1233 | id: sum, |
| 1234 | kind: InstKind::IAdd(a, b), |
| 1235 | ty: IrType::Int(IntWidth::I32), |
| 1236 | span: dummy_span(), |
| 1237 | }); |
| 1238 | let entry = f.entry; |
| 1239 | f.block_mut(entry).terminator = Some(Terminator::Return(Some(sum))); |
| 1240 | m.add_function(f); |
| 1241 | |
| 1242 | ConstFold.run(&mut m); |
| 1243 | let folded = m.functions[0].blocks[0] |
| 1244 | .insts |
| 1245 | .iter() |
| 1246 | .find(|i| i.id == sum) |
| 1247 | .unwrap(); |
| 1248 | match folded.kind { |
| 1249 | InstKind::ConstInt(1, IntWidth::I32) => { /* good */ } |
| 1250 | InstKind::ConstInt(v, w) => panic!( |
| 1251 | "audit N-1 IAdd: expected ConstInt(1, I32), got ConstInt({}, {:?}) — width drift", |
| 1252 | v, w |
| 1253 | ), |
| 1254 | ref other => panic!("expected ConstInt fold, got {:?}", other), |
| 1255 | } |
| 1256 | } |
| 1257 | |
| 1258 | #[test] |
| 1259 | fn audit_const_fold_width_drift_isub() { |
| 1260 | // a: ConstInt(250, I8) = -6 |
| 1261 | // b: ConstInt(1, I8) = 1 |
| 1262 | // Expected: -6 - 1 = -7 |
| 1263 | let mut m = Module::new("t".into()); |
| 1264 | let mut f = Function::new("f".into(), vec![], IrType::Int(IntWidth::I32)); |
| 1265 | let a = f.next_value_id(); |
| 1266 | f.block_mut(f.entry).insts.push(Inst { |
| 1267 | id: a, |
| 1268 | kind: InstKind::ConstInt(250, IntWidth::I8), |
| 1269 | ty: IrType::Int(IntWidth::I8), |
| 1270 | span: dummy_span(), |
| 1271 | }); |
| 1272 | let b = f.next_value_id(); |
| 1273 | f.block_mut(f.entry).insts.push(Inst { |
| 1274 | id: b, |
| 1275 | kind: InstKind::ConstInt(1, IntWidth::I8), |
| 1276 | ty: IrType::Int(IntWidth::I8), |
| 1277 | span: dummy_span(), |
| 1278 | }); |
| 1279 | let diff = f.next_value_id(); |
| 1280 | f.block_mut(f.entry).insts.push(Inst { |
| 1281 | id: diff, |
| 1282 | kind: InstKind::ISub(a, b), |
| 1283 | ty: IrType::Int(IntWidth::I32), |
| 1284 | span: dummy_span(), |
| 1285 | }); |
| 1286 | let entry = f.entry; |
| 1287 | f.block_mut(entry).terminator = Some(Terminator::Return(Some(diff))); |
| 1288 | m.add_function(f); |
| 1289 | |
| 1290 | ConstFold.run(&mut m); |
| 1291 | let folded = m.functions[0].blocks[0] |
| 1292 | .insts |
| 1293 | .iter() |
| 1294 | .find(|i| i.id == diff) |
| 1295 | .unwrap(); |
| 1296 | match folded.kind { |
| 1297 | InstKind::ConstInt(-7, IntWidth::I32) => { /* good */ } |
| 1298 | ref other => panic!( |
| 1299 | "audit N-1 ISub: expected ConstInt(-7, I32), got {:?}", |
| 1300 | other |
| 1301 | ), |
| 1302 | } |
| 1303 | } |
| 1304 | |
| 1305 | #[test] |
| 1306 | fn audit_const_fold_width_drift_imul() { |
| 1307 | // a: ConstInt(255, I8) = -1 |
| 1308 | // b: ConstInt(3, I8) = 3 |
| 1309 | // Expected: -1 * 3 = -3 |
| 1310 | let mut m = Module::new("t".into()); |
| 1311 | let mut f = Function::new("f".into(), vec![], IrType::Int(IntWidth::I32)); |
| 1312 | let a = f.next_value_id(); |
| 1313 | f.block_mut(f.entry).insts.push(Inst { |
| 1314 | id: a, |
| 1315 | kind: InstKind::ConstInt(255, IntWidth::I8), |
| 1316 | ty: IrType::Int(IntWidth::I8), |
| 1317 | span: dummy_span(), |
| 1318 | }); |
| 1319 | let b = f.next_value_id(); |
| 1320 | f.block_mut(f.entry).insts.push(Inst { |
| 1321 | id: b, |
| 1322 | kind: InstKind::ConstInt(3, IntWidth::I8), |
| 1323 | ty: IrType::Int(IntWidth::I8), |
| 1324 | span: dummy_span(), |
| 1325 | }); |
| 1326 | let prod = f.next_value_id(); |
| 1327 | f.block_mut(f.entry).insts.push(Inst { |
| 1328 | id: prod, |
| 1329 | kind: InstKind::IMul(a, b), |
| 1330 | ty: IrType::Int(IntWidth::I32), |
| 1331 | span: dummy_span(), |
| 1332 | }); |
| 1333 | let entry = f.entry; |
| 1334 | f.block_mut(entry).terminator = Some(Terminator::Return(Some(prod))); |
| 1335 | m.add_function(f); |
| 1336 | |
| 1337 | ConstFold.run(&mut m); |
| 1338 | let folded = m.functions[0].blocks[0] |
| 1339 | .insts |
| 1340 | .iter() |
| 1341 | .find(|i| i.id == prod) |
| 1342 | .unwrap(); |
| 1343 | match folded.kind { |
| 1344 | InstKind::ConstInt(-3, IntWidth::I32) => { /* good */ } |
| 1345 | ref other => panic!( |
| 1346 | "audit N-1 IMul: expected ConstInt(-3, I32), got {:?}", |
| 1347 | other |
| 1348 | ), |
| 1349 | } |
| 1350 | } |
| 1351 | |
| 1352 | #[test] |
| 1353 | fn audit_const_fold_width_drift_idiv() { |
| 1354 | // a: ConstInt(255, I8) = -1 |
| 1355 | // b: ConstInt(2, I8) = 2 |
| 1356 | // Expected: -1 / 2 = 0 (toward zero) |
| 1357 | // Pre-fix: 255 / 2 = 127 (very wrong) |
| 1358 | let mut m = Module::new("t".into()); |
| 1359 | let mut f = Function::new("f".into(), vec![], IrType::Int(IntWidth::I32)); |
| 1360 | let a = f.next_value_id(); |
| 1361 | f.block_mut(f.entry).insts.push(Inst { |
| 1362 | id: a, |
| 1363 | kind: InstKind::ConstInt(255, IntWidth::I8), |
| 1364 | ty: IrType::Int(IntWidth::I8), |
| 1365 | span: dummy_span(), |
| 1366 | }); |
| 1367 | let b = f.next_value_id(); |
| 1368 | f.block_mut(f.entry).insts.push(Inst { |
| 1369 | id: b, |
| 1370 | kind: InstKind::ConstInt(2, IntWidth::I8), |
| 1371 | ty: IrType::Int(IntWidth::I8), |
| 1372 | span: dummy_span(), |
| 1373 | }); |
| 1374 | let q = f.next_value_id(); |
| 1375 | f.block_mut(f.entry).insts.push(Inst { |
| 1376 | id: q, |
| 1377 | kind: InstKind::IDiv(a, b), |
| 1378 | ty: IrType::Int(IntWidth::I32), |
| 1379 | span: dummy_span(), |
| 1380 | }); |
| 1381 | let entry = f.entry; |
| 1382 | f.block_mut(entry).terminator = Some(Terminator::Return(Some(q))); |
| 1383 | m.add_function(f); |
| 1384 | |
| 1385 | ConstFold.run(&mut m); |
| 1386 | let folded = m.functions[0].blocks[0] |
| 1387 | .insts |
| 1388 | .iter() |
| 1389 | .find(|i| i.id == q) |
| 1390 | .unwrap(); |
| 1391 | match folded.kind { |
| 1392 | InstKind::ConstInt(0, IntWidth::I32) => { /* good */ } |
| 1393 | ref other => panic!("audit N-1 IDiv: expected ConstInt(0, I32), got {:?}", other), |
| 1394 | } |
| 1395 | } |
| 1396 | |
| 1397 | #[test] |
| 1398 | fn audit_const_fold_width_drift_icmp() { |
| 1399 | // a: ConstInt(255, I8) = -1 |
| 1400 | // b: ConstInt(0, I8) = 0 |
| 1401 | // ICmp Lt: -1 < 0 → true |
| 1402 | // Pre-fix (if ICmp also discarded widths): 255 < 0 → false |
| 1403 | let mut m = Module::new("t".into()); |
| 1404 | let mut f = Function::new("f".into(), vec![], IrType::Bool); |
| 1405 | let a = f.next_value_id(); |
| 1406 | f.block_mut(f.entry).insts.push(Inst { |
| 1407 | id: a, |
| 1408 | kind: InstKind::ConstInt(255, IntWidth::I8), |
| 1409 | ty: IrType::Int(IntWidth::I8), |
| 1410 | span: dummy_span(), |
| 1411 | }); |
| 1412 | let b = f.next_value_id(); |
| 1413 | f.block_mut(f.entry).insts.push(Inst { |
| 1414 | id: b, |
| 1415 | kind: InstKind::ConstInt(0, IntWidth::I8), |
| 1416 | ty: IrType::Int(IntWidth::I8), |
| 1417 | span: dummy_span(), |
| 1418 | }); |
| 1419 | let lt = f.next_value_id(); |
| 1420 | f.block_mut(f.entry).insts.push(Inst { |
| 1421 | id: lt, |
| 1422 | kind: InstKind::ICmp(CmpOp::Lt, a, b), |
| 1423 | ty: IrType::Bool, |
| 1424 | span: dummy_span(), |
| 1425 | }); |
| 1426 | let entry = f.entry; |
| 1427 | f.block_mut(entry).terminator = Some(Terminator::Return(Some(lt))); |
| 1428 | m.add_function(f); |
| 1429 | |
| 1430 | ConstFold.run(&mut m); |
| 1431 | let folded = m.functions[0].blocks[0] |
| 1432 | .insts |
| 1433 | .iter() |
| 1434 | .find(|i| i.id == lt) |
| 1435 | .unwrap(); |
| 1436 | match folded.kind { |
| 1437 | InstKind::ConstBool(true) => { /* good */ } |
| 1438 | ref other => panic!("audit N-1 ICmp: expected ConstBool(true), got {:?}", other), |
| 1439 | } |
| 1440 | } |
| 1441 | |
| 1442 | // ============================================================= |
| 1443 | // FINDING B-8: CSE must dedupe semantically-equal ConstInts |
| 1444 | // stored at different bit patterns at the same width. |
| 1445 | // ============================================================= |
| 1446 | // |
| 1447 | // `ConstInt(255, I8)` and `ConstInt(-1, I8)` both encode -1 at i8 |
| 1448 | // precision. After the B-8 fix, CSE keys on the sign-extended |
| 1449 | // value, so the two should collapse to a single SSA name. |
| 1450 | #[test] |
| 1451 | fn audit_cse_dedupes_const_int_bit_pattern() { |
| 1452 | use crate::opt::LocalCse; |
| 1453 | let mut m = Module::new("t".into()); |
| 1454 | let mut f = Function::new("f".into(), vec![], IrType::Int(IntWidth::I8)); |
| 1455 | let a = push( |
| 1456 | &mut f, |
| 1457 | InstKind::ConstInt(255, IntWidth::I8), |
| 1458 | IrType::Int(IntWidth::I8), |
| 1459 | ); |
| 1460 | let b = push( |
| 1461 | &mut f, |
| 1462 | InstKind::ConstInt(-1, IntWidth::I8), |
| 1463 | IrType::Int(IntWidth::I8), |
| 1464 | ); |
| 1465 | // Use a in some op and b in another so neither is dead. |
| 1466 | let neg_a = push(&mut f, InstKind::INeg(a), IrType::Int(IntWidth::I8)); |
| 1467 | let neg_b = push(&mut f, InstKind::INeg(b), IrType::Int(IntWidth::I8)); |
| 1468 | // Add them so both are live to the terminator. |
| 1469 | let sum = push( |
| 1470 | &mut f, |
| 1471 | InstKind::IAdd(neg_a, neg_b), |
| 1472 | IrType::Int(IntWidth::I8), |
| 1473 | ); |
| 1474 | let entry = f.entry; |
| 1475 | f.block_mut(entry).terminator = Some(Terminator::Return(Some(sum))); |
| 1476 | m.add_function(f); |
| 1477 | |
| 1478 | LocalCse.run(&mut m); |
| 1479 | |
| 1480 | // After CSE, one of {a, b} has been rewritten to point at the |
| 1481 | // other. The two INegs should now reference the same value. |
| 1482 | let f = &m.functions[0]; |
| 1483 | let neg_a_inst = f.blocks[0].insts.iter().find(|i| i.id == neg_a).unwrap(); |
| 1484 | let neg_b_inst = f.blocks[0].insts.iter().find(|i| i.id == neg_b).unwrap(); |
| 1485 | let neg_a_op = match &neg_a_inst.kind { |
| 1486 | InstKind::INeg(v) => *v, |
| 1487 | _ => panic!(), |
| 1488 | }; |
| 1489 | let neg_b_op = match &neg_b_inst.kind { |
| 1490 | InstKind::INeg(v) => *v, |
| 1491 | _ => panic!(), |
| 1492 | }; |
| 1493 | assert_eq!( |
| 1494 | neg_a_op, neg_b_op, |
| 1495 | "audit B-8: ConstInt(255, I8) and ConstInt(-1, I8) should CSE-dedupe \ |
| 1496 | (both represent -1 at i8 precision), but the INeg operands differ" |
| 1497 | ); |
| 1498 | } |
| 1499 | |
| 1500 | // ============================================================= |
| 1501 | // FINDING M-C: same for AShr (was missing from first round) |
| 1502 | // ============================================================= |
| 1503 | #[test] |
| 1504 | fn audit_const_fold_ashr_negative_count_bails() { |
| 1505 | let mut m = Module::new("t".into()); |
| 1506 | let mut f = Function::new("f".into(), vec![], IrType::Int(IntWidth::I32)); |
| 1507 | let v = push( |
| 1508 | &mut f, |
| 1509 | InstKind::ConstInt(-128, IntWidth::I32), |
| 1510 | IrType::Int(IntWidth::I32), |
| 1511 | ); |
| 1512 | let cnt = push( |
| 1513 | &mut f, |
| 1514 | InstKind::ConstInt(-3, IntWidth::I32), |
| 1515 | IrType::Int(IntWidth::I32), |
| 1516 | ); |
| 1517 | let s = push(&mut f, InstKind::AShr(v, cnt), IrType::Int(IntWidth::I32)); |
| 1518 | let entry = f.entry; |
| 1519 | f.block_mut(entry).terminator = Some(Terminator::Return(Some(s))); |
| 1520 | m.add_function(f); |
| 1521 | |
| 1522 | ConstFold.run(&mut m); |
| 1523 | let folded = m.functions[0].blocks[0] |
| 1524 | .insts |
| 1525 | .iter() |
| 1526 | .find(|i| i.id == s) |
| 1527 | .unwrap(); |
| 1528 | if let InstKind::ConstInt(0, _) = folded.kind { |
| 1529 | panic!("audit M-C: ashr with negative count folded to 0 — wrong on AArch64"); |
| 1530 | } |
| 1531 | } |
| 1532 | |
| 1533 | // ============================================================= |
| 1534 | // FINDING Med-6: LICM must not hoist trap-prone IDiv |
| 1535 | // ============================================================= |
| 1536 | #[test] |
| 1537 | fn audit_licm_does_not_hoist_idiv() { |
| 1538 | // Build a loop with an invariant `idiv a, b` in the body. |
| 1539 | // Without the fix, LICM would happily hoist it to the preheader, |
| 1540 | // potentially executing it when the original loop would have |
| 1541 | // skipped it (causing SIGFPE on b == 0). |
| 1542 | let mut m = Module::new("t".into()); |
| 1543 | let mut f = Function::new("f".into(), vec![], IrType::Void); |
| 1544 | let a = push( |
| 1545 | &mut f, |
| 1546 | InstKind::ConstInt(100, IntWidth::I32), |
| 1547 | IrType::Int(IntWidth::I32), |
| 1548 | ); |
| 1549 | let b = push( |
| 1550 | &mut f, |
| 1551 | InstKind::ConstInt(5, IntWidth::I32), |
| 1552 | IrType::Int(IntWidth::I32), |
| 1553 | ); |
| 1554 | let init = push( |
| 1555 | &mut f, |
| 1556 | InstKind::ConstInt(0, IntWidth::I32), |
| 1557 | IrType::Int(IntWidth::I32), |
| 1558 | ); |
| 1559 | |
| 1560 | let header = f.create_block("header"); |
| 1561 | let i_param = f.next_value_id(); |
| 1562 | f.block_mut(header).params.push(BlockParam { |
| 1563 | id: i_param, |
| 1564 | ty: IrType::Int(IntWidth::I32), |
| 1565 | }); |
| 1566 | |
| 1567 | // Inside the body: %q = idiv a, b — both operands invariant. |
| 1568 | let q = f.next_value_id(); |
| 1569 | f.block_mut(header).insts.push(Inst { |
| 1570 | id: q, |
| 1571 | kind: InstKind::IDiv(a, b), |
| 1572 | ty: IrType::Int(IntWidth::I32), |
| 1573 | span: dummy_span(), |
| 1574 | }); |
| 1575 | // %sum = iadd i_param, q — depends on q, not invariant. |
| 1576 | let sum = f.next_value_id(); |
| 1577 | f.block_mut(header).insts.push(Inst { |
| 1578 | id: sum, |
| 1579 | kind: InstKind::IAdd(i_param, q), |
| 1580 | ty: IrType::Int(IntWidth::I32), |
| 1581 | span: dummy_span(), |
| 1582 | }); |
| 1583 | let limit = f.next_value_id(); |
| 1584 | f.block_mut(header).insts.push(Inst { |
| 1585 | id: limit, |
| 1586 | kind: InstKind::ConstInt(10, IntWidth::I32), |
| 1587 | ty: IrType::Int(IntWidth::I32), |
| 1588 | span: dummy_span(), |
| 1589 | }); |
| 1590 | let done = f.next_value_id(); |
| 1591 | f.block_mut(header).insts.push(Inst { |
| 1592 | id: done, |
| 1593 | kind: InstKind::ICmp(CmpOp::Ge, sum, limit), |
| 1594 | ty: IrType::Bool, |
| 1595 | span: dummy_span(), |
| 1596 | }); |
| 1597 | |
| 1598 | let exit = f.create_block("exit"); |
| 1599 | f.block_mut(exit).terminator = Some(Terminator::Return(None)); |
| 1600 | f.block_mut(header).terminator = Some(Terminator::CondBranch { |
| 1601 | cond: done, |
| 1602 | true_dest: exit, |
| 1603 | true_args: vec![], |
| 1604 | false_dest: header, |
| 1605 | false_args: vec![sum], |
| 1606 | }); |
| 1607 | let entry = f.entry; |
| 1608 | f.block_mut(entry).terminator = Some(Terminator::Branch(header, vec![init])); |
| 1609 | m.add_function(f); |
| 1610 | |
| 1611 | Licm.run(&mut m); |
| 1612 | let f = &m.functions[0]; |
| 1613 | // The IDiv must STILL be in the header block, not in entry. |
| 1614 | let header_block = f |
| 1615 | .blocks |
| 1616 | .iter() |
| 1617 | .find(|b| b.name.starts_with("header")) |
| 1618 | .unwrap(); |
| 1619 | let entry_block = f.block(f.entry); |
| 1620 | let idiv_in_header = header_block |
| 1621 | .insts |
| 1622 | .iter() |
| 1623 | .any(|i| matches!(i.kind, InstKind::IDiv(..))); |
| 1624 | let idiv_in_entry = entry_block |
| 1625 | .insts |
| 1626 | .iter() |
| 1627 | .any(|i| matches!(i.kind, InstKind::IDiv(..))); |
| 1628 | assert!( |
| 1629 | idiv_in_header, |
| 1630 | "audit Med-6: LICM should leave IDiv in body (trap-prone)" |
| 1631 | ); |
| 1632 | assert!( |
| 1633 | !idiv_in_entry, |
| 1634 | "audit Med-6: LICM must not hoist IDiv into preheader" |
| 1635 | ); |
| 1636 | } |
| 1637 | |
| 1638 | // ============================================================= |
| 1639 | // FINDING C-C: const_fold Select must use the Select's declared |
| 1640 | // type, not the chosen branch's source width. |
| 1641 | // ============================================================= |
| 1642 | // |
| 1643 | // Happy-path test: same widths everywhere. Pinned for regression |
| 1644 | // against the simple form of the bug. |
| 1645 | #[test] |
| 1646 | fn audit_const_fold_select_uses_declared_type() { |
| 1647 | let mut m = Module::new("t".into()); |
| 1648 | let mut f = Function::new("f".into(), vec![], IrType::Int(IntWidth::I32)); |
| 1649 | let a = push( |
| 1650 | &mut f, |
| 1651 | InstKind::ConstInt(1, IntWidth::I32), |
| 1652 | IrType::Int(IntWidth::I32), |
| 1653 | ); |
| 1654 | let b = push( |
| 1655 | &mut f, |
| 1656 | InstKind::ConstInt(99, IntWidth::I32), |
| 1657 | IrType::Int(IntWidth::I32), |
| 1658 | ); |
| 1659 | let cond = push(&mut f, InstKind::ConstBool(true), IrType::Bool); |
| 1660 | let sel = push( |
| 1661 | &mut f, |
| 1662 | InstKind::Select(cond, a, b), |
| 1663 | IrType::Int(IntWidth::I32), |
| 1664 | ); |
| 1665 | let entry = f.entry; |
| 1666 | f.block_mut(entry).terminator = Some(Terminator::Return(Some(sel))); |
| 1667 | m.add_function(f); |
| 1668 | |
| 1669 | ConstFold.run(&mut m); |
| 1670 | let folded = m.functions[0].blocks[0] |
| 1671 | .insts |
| 1672 | .iter() |
| 1673 | .find(|i| i.id == sel) |
| 1674 | .unwrap(); |
| 1675 | match folded.kind { |
| 1676 | InstKind::ConstInt(1, IntWidth::I32) => { /* good */ } |
| 1677 | ref other => panic!("expected ConstInt(1, I32), got {:?}", other), |
| 1678 | } |
| 1679 | assert_eq!(folded.ty, IrType::Int(IntWidth::I32)); |
| 1680 | } |
| 1681 | |
| 1682 | // ============================================================= |
| 1683 | // FINDING B-1 (re-audit): C-C fix is incomplete for width-drift |
| 1684 | // within `IrType::Int(_)`. Pin the bug with an adversarial test |
| 1685 | // that would have failed BEFORE the B-1 fix. |
| 1686 | // ============================================================= |
| 1687 | // |
| 1688 | // Build a Select declared `i64` whose chosen branch is a |
| 1689 | // `ConstInt(255, I8)` — that's `-1` at i8 precision. Without |
| 1690 | // source-width sign extension, the fold produces `ConstInt(255, |
| 1691 | // I64)` instead of `ConstInt(-1, I64)`. |
| 1692 | // |
| 1693 | // We construct the IR by manually inserting a ConstInt with a |
| 1694 | // declared `inst.ty` of `Int(I8)` AND a Select whose `inst.ty` is |
| 1695 | // `Int(I64)`. The verifier wouldn't normally allow this (operand |
| 1696 | // types should match the Select's type), but the verifier only |
| 1697 | // checks `is_int()`, not bit width — exactly the gap C-C was |
| 1698 | // trying to defend against. |
| 1699 | #[test] |
| 1700 | fn audit_const_fold_select_width_drift_int() { |
| 1701 | let mut m = Module::new("t".into()); |
| 1702 | let mut f = Function::new("f".into(), vec![], IrType::Int(IntWidth::I64)); |
| 1703 | |
| 1704 | // Manually emit a ConstInt(255, I8). The stored value is 255. |
| 1705 | // At i8 precision the "true" value is -1 (sign bit set). |
| 1706 | let a = f.next_value_id(); |
| 1707 | let entry = f.entry; |
| 1708 | f.block_mut(entry).insts.push(Inst { |
| 1709 | id: a, |
| 1710 | kind: InstKind::ConstInt(255, IntWidth::I8), |
| 1711 | ty: IrType::Int(IntWidth::I8), |
| 1712 | span: dummy_span(), |
| 1713 | }); |
| 1714 | let b = push( |
| 1715 | &mut f, |
| 1716 | InstKind::ConstInt(99, IntWidth::I64), |
| 1717 | IrType::Int(IntWidth::I64), |
| 1718 | ); |
| 1719 | let cond = push(&mut f, InstKind::ConstBool(true), IrType::Bool); |
| 1720 | |
| 1721 | // Select declared as i64, chosen branch is i8 (255 → -1). |
| 1722 | let sel = f.next_value_id(); |
| 1723 | f.block_mut(entry).insts.push(Inst { |
| 1724 | id: sel, |
| 1725 | kind: InstKind::Select(cond, a, b), |
| 1726 | ty: IrType::Int(IntWidth::I64), |
| 1727 | span: dummy_span(), |
| 1728 | }); |
| 1729 | f.block_mut(entry).terminator = Some(Terminator::Return(Some(sel))); |
| 1730 | m.add_function(f); |
| 1731 | |
| 1732 | ConstFold.run(&mut m); |
| 1733 | let folded = m.functions[0].blocks[0] |
| 1734 | .insts |
| 1735 | .iter() |
| 1736 | .find(|i| i.id == sel) |
| 1737 | .unwrap(); |
| 1738 | match folded.kind { |
| 1739 | InstKind::ConstInt(-1, IntWidth::I64) => { /* good — i8 -1 sign-extended to i64 */ } |
| 1740 | InstKind::ConstInt(v, w) => panic!( |
| 1741 | "audit B-1: expected ConstInt(-1, I64), got ConstInt({}, {:?}). \ |
| 1742 | Source width was discarded — width drift slipped through.", |
| 1743 | v, w |
| 1744 | ), |
| 1745 | ref other => panic!("expected ConstInt fold, got {:?}", other), |
| 1746 | } |
| 1747 | } |
| 1748 | |
| 1749 | // ============================================================= |
| 1750 | // FINDING C-A (structural pin): strength_reduce must NOT replace |
| 1751 | // the orphan instruction's kind with a placeholder Const(0). |
| 1752 | // ============================================================= |
| 1753 | // |
| 1754 | // The original C-A bug was inside a `_ => continue` branch that |
| 1755 | // silently dropped `changed = true` after writing a Const(0) |
| 1756 | // placeholder for non-int/non-bool result types. The structural |
| 1757 | // fix removes the placeholder machinery entirely. Pin the fix by |
| 1758 | // asserting the orphan instruction's kind is *unchanged* after a |
| 1759 | // run of strength_reduce, then DCE removes it cleanly. |
| 1760 | // |
| 1761 | // Before the structural fix, the orphan would have its kind |
| 1762 | // rewritten to `ConstInt(0, _)`. After the fix, it stays as |
| 1763 | // `IMul(_, _)` until DCE removes it. |
| 1764 | #[test] |
| 1765 | fn audit_strength_reduce_identity_does_not_write_placeholder() { |
| 1766 | let mut m = Module::new("t".into()); |
| 1767 | let mut f = Function::new("f".into(), vec![], IrType::Int(IntWidth::I32)); |
| 1768 | let x = push( |
| 1769 | &mut f, |
| 1770 | InstKind::ConstInt(42, IntWidth::I32), |
| 1771 | IrType::Int(IntWidth::I32), |
| 1772 | ); |
| 1773 | let one = push( |
| 1774 | &mut f, |
| 1775 | InstKind::ConstInt(1, IntWidth::I32), |
| 1776 | IrType::Int(IntWidth::I32), |
| 1777 | ); |
| 1778 | let mul = push(&mut f, InstKind::IMul(x, one), IrType::Int(IntWidth::I32)); |
| 1779 | let entry = f.entry; |
| 1780 | f.block_mut(entry).terminator = Some(Terminator::Return(Some(mul))); |
| 1781 | m.add_function(f); |
| 1782 | |
| 1783 | StrengthReduce.run(&mut m); |
| 1784 | // The orphan instruction at `mul`'s ID must still exist and |
| 1785 | // have its original kind. The earlier (broken) version would |
| 1786 | // have replaced its kind with ConstInt(0, _). |
| 1787 | let orphan = m.functions[0].blocks[0] |
| 1788 | .insts |
| 1789 | .iter() |
| 1790 | .find(|i| i.id == mul) |
| 1791 | .unwrap(); |
| 1792 | match orphan.kind { |
| 1793 | InstKind::IMul(_, _) => { /* good — original kind preserved */ } |
| 1794 | InstKind::ConstInt(0, _) => panic!( |
| 1795 | "audit C-A: orphan was rewritten to placeholder Const(0). \ |
| 1796 | The structural fix should leave the original kind alone." |
| 1797 | ), |
| 1798 | ref other => panic!("unexpected orphan kind: {:?}", other), |
| 1799 | } |
| 1800 | } |
| 1801 | |
| 1802 | // ============================================================= |
| 1803 | // FINDING C-A: strength_reduce Identity rewrites must always set |
| 1804 | // `changed = true`, even if the placeholder branch is taken. |
| 1805 | // (After the fix, no placeholder is written at all.) |
| 1806 | // ============================================================= |
| 1807 | #[test] |
| 1808 | fn audit_strength_reduce_identity_reports_changed() { |
| 1809 | let mut m = Module::new("t".into()); |
| 1810 | let mut f = Function::new("f".into(), vec![], IrType::Int(IntWidth::I32)); |
| 1811 | let x = push( |
| 1812 | &mut f, |
| 1813 | InstKind::ConstInt(42, IntWidth::I32), |
| 1814 | IrType::Int(IntWidth::I32), |
| 1815 | ); |
| 1816 | let one = push( |
| 1817 | &mut f, |
| 1818 | InstKind::ConstInt(1, IntWidth::I32), |
| 1819 | IrType::Int(IntWidth::I32), |
| 1820 | ); |
| 1821 | let mul = push(&mut f, InstKind::IMul(x, one), IrType::Int(IntWidth::I32)); |
| 1822 | let entry = f.entry; |
| 1823 | f.block_mut(entry).terminator = Some(Terminator::Return(Some(mul))); |
| 1824 | m.add_function(f); |
| 1825 | |
| 1826 | let changed = StrengthReduce.run(&mut m); |
| 1827 | assert!( |
| 1828 | changed, |
| 1829 | "strength_reduce must report `changed = true` after Identity rewrite" |
| 1830 | ); |
| 1831 | |
| 1832 | // The terminator now references x. |
| 1833 | match m.functions[0].blocks[0].terminator.as_ref().unwrap() { |
| 1834 | Terminator::Return(Some(v)) => assert_eq!(*v, x), |
| 1835 | _ => panic!(), |
| 1836 | } |
| 1837 | } |
| 1838 | |
| 1839 | // ============================================================= |
| 1840 | // FINDING M-D: ICmp must sign-extend each operand at its OWN width |
| 1841 | // ============================================================= |
| 1842 | // |
| 1843 | // Construct a synthetic ICmp where the two ConstInt operands have |
| 1844 | // different declared widths and the same low-bits-as-stored value. |
| 1845 | // Per M-D, before the fix the fold uses operand a's width for both, |
| 1846 | // silently producing a wrong answer when widths differ. |
| 1847 | #[test] |
| 1848 | fn audit_const_fold_icmp_uses_each_operand_width() { |
| 1849 | // We can't easily produce mismatched widths through normal |
| 1850 | // lowering because the verifier would catch operand types in |
| 1851 | // most cases. Construct directly: a is i32 holding 255, b is i8 |
| 1852 | // holding 255 (which represents -1 at i8 precision). Eq should |
| 1853 | // be FALSE: 255 != -1. |
| 1854 | let mut m = Module::new("t".into()); |
| 1855 | let mut f = Function::new("f".into(), vec![], IrType::Bool); |
| 1856 | let a = push( |
| 1857 | &mut f, |
| 1858 | InstKind::ConstInt(255, IntWidth::I32), |
| 1859 | IrType::Int(IntWidth::I32), |
| 1860 | ); |
| 1861 | let b = push( |
| 1862 | &mut f, |
| 1863 | InstKind::ConstInt(255, IntWidth::I8), |
| 1864 | IrType::Int(IntWidth::I8), |
| 1865 | ); |
| 1866 | let eq = push(&mut f, InstKind::ICmp(CmpOp::Eq, a, b), IrType::Bool); |
| 1867 | let entry = f.entry; |
| 1868 | f.block_mut(entry).terminator = Some(Terminator::Return(Some(eq))); |
| 1869 | m.add_function(f); |
| 1870 | |
| 1871 | ConstFold.run(&mut m); |
| 1872 | let folded = m.functions[0].blocks[0] |
| 1873 | .insts |
| 1874 | .iter() |
| 1875 | .find(|i| i.id == eq) |
| 1876 | .unwrap(); |
| 1877 | match folded.kind { |
| 1878 | // After the M-D fix: bv sign-extended at i8 → -1; av at i32 → 255. |
| 1879 | // 255 == -1 → false. |
| 1880 | InstKind::ConstBool(false) => { /* good */ } |
| 1881 | // Before the fix: both sign-extended at i32 → 255 == 255 → true. |
| 1882 | InstKind::ConstBool(true) => panic!( |
| 1883 | "audit M-D: ICmp folded as if both operands were i32-width \ |
| 1884 | (lost b's i8 width). Expected ConstBool(false)." |
| 1885 | ), |
| 1886 | ref other => panic!("expected ConstBool, got {:?}", other), |
| 1887 | } |
| 1888 | } |
| 1889 | |
| 1890 | // ============================================================= |
| 1891 | // FINDING M-E (auto-fixed by M-1): FCmp on f32 ConstFloats agrees |
| 1892 | // with runtime f32 precision |
| 1893 | // ============================================================= |
| 1894 | #[test] |
| 1895 | fn audit_const_fold_fcmp_f32_after_m1_fix() { |
| 1896 | // After M-1, IntToFloat(16777217:i32, F32) folds to ConstFloat |
| 1897 | // with the f32-rounded value (16777216.0). FCmp Eq against |
| 1898 | // ConstFloat(16777216.0, F32) should now return true. |
| 1899 | let mut m = Module::new("t".into()); |
| 1900 | let mut f = Function::new("f".into(), vec![], IrType::Bool); |
| 1901 | let i = push( |
| 1902 | &mut f, |
| 1903 | InstKind::ConstInt(16_777_217, IntWidth::I32), |
| 1904 | IrType::Int(IntWidth::I32), |
| 1905 | ); |
| 1906 | let fv_a = push( |
| 1907 | &mut f, |
| 1908 | InstKind::IntToFloat(i, FloatWidth::F32), |
| 1909 | IrType::Float(FloatWidth::F32), |
| 1910 | ); |
| 1911 | let fv_b = push( |
| 1912 | &mut f, |
| 1913 | InstKind::ConstFloat(16_777_216.0, FloatWidth::F32), |
| 1914 | IrType::Float(FloatWidth::F32), |
| 1915 | ); |
| 1916 | let eq = push(&mut f, InstKind::FCmp(CmpOp::Eq, fv_a, fv_b), IrType::Bool); |
| 1917 | let entry = f.entry; |
| 1918 | f.block_mut(entry).terminator = Some(Terminator::Return(Some(eq))); |
| 1919 | m.add_function(f); |
| 1920 | |
| 1921 | ConstFold.run(&mut m); |
| 1922 | let folded = m.functions[0].blocks[0] |
| 1923 | .insts |
| 1924 | .iter() |
| 1925 | .find(|i| i.id == eq) |
| 1926 | .unwrap(); |
| 1927 | assert!( |
| 1928 | matches!(folded.kind, InstKind::ConstBool(true)), |
| 1929 | "audit M-E: FCmp on f32-rounded values should return true, got {:?}", |
| 1930 | folded.kind |
| 1931 | ); |
| 1932 | } |
| 1933 | |
| 1934 | // ============================================================= |
| 1935 | // FINDING M-F (auto-fixed by M-1): FloatToInt of an f32 ConstFloat |
| 1936 | // rounds correctly through f32 |
| 1937 | // ============================================================= |
| 1938 | #[test] |
| 1939 | fn audit_const_fold_floattoint_from_f32_after_m1_fix() { |
| 1940 | // IntToFloat(16777217, F32) → ConstFloat(16777216.0, F32) after M-1. |
| 1941 | // FloatToInt(_, I32) should produce 16777216, not 16777217. |
| 1942 | let mut m = Module::new("t".into()); |
| 1943 | let mut f = Function::new("f".into(), vec![], IrType::Int(IntWidth::I32)); |
| 1944 | let i = push( |
| 1945 | &mut f, |
| 1946 | InstKind::ConstInt(16_777_217, IntWidth::I32), |
| 1947 | IrType::Int(IntWidth::I32), |
| 1948 | ); |
| 1949 | let fv = push( |
| 1950 | &mut f, |
| 1951 | InstKind::IntToFloat(i, FloatWidth::F32), |
| 1952 | IrType::Float(FloatWidth::F32), |
| 1953 | ); |
| 1954 | let back = push( |
| 1955 | &mut f, |
| 1956 | InstKind::FloatToInt(fv, IntWidth::I32), |
| 1957 | IrType::Int(IntWidth::I32), |
| 1958 | ); |
| 1959 | let entry = f.entry; |
| 1960 | f.block_mut(entry).terminator = Some(Terminator::Return(Some(back))); |
| 1961 | m.add_function(f); |
| 1962 | |
| 1963 | ConstFold.run(&mut m); |
| 1964 | let folded = m.functions[0].blocks[0] |
| 1965 | .insts |
| 1966 | .iter() |
| 1967 | .find(|i| i.id == back) |
| 1968 | .unwrap(); |
| 1969 | match folded.kind { |
| 1970 | InstKind::ConstInt(16_777_216, IntWidth::I32) => { /* good */ } |
| 1971 | ref other => panic!( |
| 1972 | "audit M-F: expected ConstInt(16777216, I32), got {:?}", |
| 1973 | other |
| 1974 | ), |
| 1975 | } |
| 1976 | } |
| 1977 | |
| 1978 | // ============================================================= |
| 1979 | // FINDING Med-3: PopCount/CLZ/CTZ should respect inst.ty for output |
| 1980 | // ============================================================= |
| 1981 | #[test] |
| 1982 | fn audit_const_fold_popcount_uses_inst_ty() { |
| 1983 | // Build PopCount whose source is i32 but whose declared result |
| 1984 | // type is also i32 (the common case). After the fix, the fold |
| 1985 | // result must be tagged with inst.ty (i32), even if a future |
| 1986 | // change makes the source carry a different width. |
| 1987 | let mut m = Module::new("t".into()); |
| 1988 | let mut f = Function::new("f".into(), vec![], IrType::Int(IntWidth::I32)); |
| 1989 | let v = push( |
| 1990 | &mut f, |
| 1991 | InstKind::ConstInt(0xFF, IntWidth::I32), |
| 1992 | IrType::Int(IntWidth::I32), |
| 1993 | ); |
| 1994 | let pc = push(&mut f, InstKind::PopCount(v), IrType::Int(IntWidth::I32)); |
| 1995 | let entry = f.entry; |
| 1996 | f.block_mut(entry).terminator = Some(Terminator::Return(Some(pc))); |
| 1997 | m.add_function(f); |
| 1998 | |
| 1999 | ConstFold.run(&mut m); |
| 2000 | let folded = m.functions[0].blocks[0] |
| 2001 | .insts |
| 2002 | .iter() |
| 2003 | .find(|i| i.id == pc) |
| 2004 | .unwrap(); |
| 2005 | match folded.kind { |
| 2006 | InstKind::ConstInt(8, IntWidth::I32) => { /* good */ } |
| 2007 | ref other => panic!("expected ConstInt(8, I32), got {:?}", other), |
| 2008 | } |
| 2009 | assert_eq!(folded.ty, IrType::Int(IntWidth::I32)); |
| 2010 | } |
| 2011 | |
| 2012 | // ============================================================= |
| 2013 | // FINDING M-1 (latent): IntToFloat→FSub gives the wrong answer |
| 2014 | // ============================================================= |
| 2015 | // |
| 2016 | // Demonstrates the downstream impact of M-1: chaining IntToFloat |
| 2017 | // (f32) into FSub produces a non-zero result for two values that |
| 2018 | // should be equal after f32 rounding. Once mem2reg lands and this |
| 2019 | // IR pattern starts appearing from real Fortran (subtracting two |
| 2020 | // `real(N, 4)` expressions), the bug becomes a CRITICAL miscompile. |
| 2021 | #[test] |
| 2022 | fn audit_int_to_f32_then_fsub_wrong_answer_today() { |
| 2023 | let mut m = Module::new("t".into()); |
| 2024 | let mut f = Function::new("f".into(), vec![], IrType::Float(FloatWidth::F32)); |
| 2025 | let i_a = push( |
| 2026 | &mut f, |
| 2027 | InstKind::ConstInt(16_777_217, IntWidth::I32), |
| 2028 | IrType::Int(IntWidth::I32), |
| 2029 | ); |
| 2030 | let i_b = push( |
| 2031 | &mut f, |
| 2032 | InstKind::ConstInt(16_777_216, IntWidth::I32), |
| 2033 | IrType::Int(IntWidth::I32), |
| 2034 | ); |
| 2035 | let f_a = push( |
| 2036 | &mut f, |
| 2037 | InstKind::IntToFloat(i_a, FloatWidth::F32), |
| 2038 | IrType::Float(FloatWidth::F32), |
| 2039 | ); |
| 2040 | let f_b = push( |
| 2041 | &mut f, |
| 2042 | InstKind::IntToFloat(i_b, FloatWidth::F32), |
| 2043 | IrType::Float(FloatWidth::F32), |
| 2044 | ); |
| 2045 | let diff = push( |
| 2046 | &mut f, |
| 2047 | InstKind::FSub(f_a, f_b), |
| 2048 | IrType::Float(FloatWidth::F32), |
| 2049 | ); |
| 2050 | let entry = f.entry; |
| 2051 | f.block_mut(entry).terminator = Some(Terminator::Return(Some(diff))); |
| 2052 | m.add_function(f); |
| 2053 | |
| 2054 | ConstFold.run(&mut m); |
| 2055 | |
| 2056 | let folded = m.functions[0].blocks[0] |
| 2057 | .insts |
| 2058 | .iter() |
| 2059 | .find(|i| i.id == diff) |
| 2060 | .unwrap(); |
| 2061 | match folded.kind { |
| 2062 | // Expected: 0.0 (after correct f32 rounding both inputs are 16777216). |
| 2063 | // Bug: 1.0 (without rounding 16777217.0 - 16777216.0 = 1.0). |
| 2064 | InstKind::ConstFloat(v, FloatWidth::F32) => assert_eq!( |
| 2065 | v, 0.0, |
| 2066 | "expected 0.0 (both inputs round to 16777216 in f32), got {}", |
| 2067 | v |
| 2068 | ), |
| 2069 | ref other => panic!("expected ConstFloat, got {:?}", other), |
| 2070 | } |
| 2071 | } |
| 2072 | |
| 2073 | // ============================================================= |
| 2074 | // FINDING M-11: const_fold imul i8 overflow wraps correctly |
| 2075 | // ============================================================= |
| 2076 | #[test] |
| 2077 | fn audit_const_fold_imul_i8_overflow_wraps() { |
| 2078 | let mut m = Module::new("t".into()); |
| 2079 | let mut f = Function::new("f".into(), vec![], IrType::Int(IntWidth::I8)); |
| 2080 | let a = push( |
| 2081 | &mut f, |
| 2082 | InstKind::ConstInt(100, IntWidth::I8), |
| 2083 | IrType::Int(IntWidth::I8), |
| 2084 | ); |
| 2085 | let b = push( |
| 2086 | &mut f, |
| 2087 | InstKind::ConstInt(100, IntWidth::I8), |
| 2088 | IrType::Int(IntWidth::I8), |
| 2089 | ); |
| 2090 | let p = push(&mut f, InstKind::IMul(a, b), IrType::Int(IntWidth::I8)); |
| 2091 | let entry = f.entry; |
| 2092 | f.block_mut(entry).terminator = Some(Terminator::Return(Some(p))); |
| 2093 | m.add_function(f); |
| 2094 | |
| 2095 | ConstFold.run(&mut m); |
| 2096 | let folded = m.functions[0].blocks[0] |
| 2097 | .insts |
| 2098 | .iter() |
| 2099 | .find(|i| i.id == p) |
| 2100 | .unwrap(); |
| 2101 | match folded.kind { |
| 2102 | // 100 * 100 = 10000; low byte = 0x10 = 16; sext = 16 |
| 2103 | InstKind::ConstInt(v, IntWidth::I8) => assert_eq!(v, 16, "expected i8 wrap, got {}", v), |
| 2104 | _ => panic!(), |
| 2105 | } |
| 2106 | } |
| 2107 | |
| 2108 | // ============================================================= |
| 2109 | // FINDING N-8 (re-audit strengthened): const_fold must converge |
| 2110 | // on non-RPO block orders too, via the pass-manager fixpoint. |
| 2111 | // ============================================================= |
| 2112 | // |
| 2113 | // `const_fold` walks `func.blocks` in vector order, not in |
| 2114 | // reverse-postorder. If a fold in an early-vec block needs a |
| 2115 | // constant defined by a later-vec block (that still dominates it |
| 2116 | // in the CFG), one pass misses the fold. The pass-manager |
| 2117 | // fixpoint re-runs const_fold until it converges. |
| 2118 | // |
| 2119 | // Audit N-8: the previous version of this test explicitly said |
| 2120 | // "we don't fail if the fold didn't happen" — it only tested |
| 2121 | // that the IR was still valid, not that the fold actually |
| 2122 | // converged. This version asserts the sum is folded to `3` so a |
| 2123 | // regression that stops the fixpoint from rescuing us would fail. |
| 2124 | #[test] |
| 2125 | fn audit_const_fold_non_rpo_block_order() { |
| 2126 | use crate::opt::{build_pipeline, OptLevel}; |
| 2127 | |
| 2128 | let mut m = Module::new("t".into()); |
| 2129 | let mut f = Function::new("f".into(), vec![], IrType::Int(IntWidth::I32)); |
| 2130 | |
| 2131 | let a_block = f.create_block("a"); |
| 2132 | let b_block = f.create_block("b"); |
| 2133 | let one = push( |
| 2134 | &mut f, |
| 2135 | InstKind::ConstInt(1, IntWidth::I32), |
| 2136 | IrType::Int(IntWidth::I32), |
| 2137 | ); |
| 2138 | let entry = f.entry; |
| 2139 | f.block_mut(entry).terminator = Some(Terminator::Branch(a_block, vec![])); |
| 2140 | |
| 2141 | let two_id = f.next_value_id(); |
| 2142 | f.block_mut(a_block).insts.push(Inst { |
| 2143 | id: two_id, |
| 2144 | kind: InstKind::ConstInt(2, IntWidth::I32), |
| 2145 | ty: IrType::Int(IntWidth::I32), |
| 2146 | span: dummy_span(), |
| 2147 | }); |
| 2148 | f.block_mut(a_block).terminator = Some(Terminator::Branch(b_block, vec![])); |
| 2149 | |
| 2150 | let sum_id = f.next_value_id(); |
| 2151 | f.block_mut(b_block).insts.push(Inst { |
| 2152 | id: sum_id, |
| 2153 | kind: InstKind::IAdd(one, two_id), |
| 2154 | ty: IrType::Int(IntWidth::I32), |
| 2155 | span: dummy_span(), |
| 2156 | }); |
| 2157 | f.block_mut(b_block).terminator = Some(Terminator::Return(Some(sum_id))); |
| 2158 | |
| 2159 | // Swap A and B in the vec order (positions 1 and 2; entry is 0). |
| 2160 | f.blocks.swap(1, 2); |
| 2161 | m.add_function(f); |
| 2162 | |
| 2163 | let pre = verify_module(&m); |
| 2164 | assert!(pre.is_empty(), "test setup invalid: {:?}", pre); |
| 2165 | |
| 2166 | let pm = build_pipeline(OptLevel::O2); |
| 2167 | pm.run(&mut m); |
| 2168 | |
| 2169 | let post = verify_module(&m); |
| 2170 | assert!( |
| 2171 | post.is_empty(), |
| 2172 | "non-RPO block order broke optimization: {:?}", |
| 2173 | post |
| 2174 | ); |
| 2175 | |
| 2176 | // The fold MUST have converged: the IAdd's defining instruction |
| 2177 | // (still carrying `sum_id`) should now be the constant `3`, or |
| 2178 | // the entire dead chain should have been DCE'd and the terminator |
| 2179 | // should reference a const(3) directly. |
| 2180 | let f = &m.functions[0]; |
| 2181 | let terminator_val = f |
| 2182 | .blocks |
| 2183 | .iter() |
| 2184 | .find_map(|b| match &b.terminator { |
| 2185 | Some(Terminator::Return(Some(v))) => Some(*v), |
| 2186 | _ => None, |
| 2187 | }) |
| 2188 | .expect("no Return terminator"); |
| 2189 | let term_kind = f |
| 2190 | .blocks |
| 2191 | .iter() |
| 2192 | .flat_map(|b| b.insts.iter()) |
| 2193 | .find(|i| i.id == terminator_val) |
| 2194 | .map(|i| i.kind.clone()) |
| 2195 | .expect("terminator value has no defining inst"); |
| 2196 | match term_kind { |
| 2197 | InstKind::ConstInt(3, IntWidth::I32) => { /* good — fold converged */ } |
| 2198 | ref other => panic!( |
| 2199 | "audit N-8: the non-RPO block order broke const_fold convergence. \ |
| 2200 | Expected the return value to be ConstInt(3, I32), got {:?}", |
| 2201 | other |
| 2202 | ), |
| 2203 | } |
| 2204 | } |
| 2205 | |
| 2206 | // ============================================================= |
| 2207 | // FINDING M4-1 (fourth audit): const_fold inner fixpoint must |
| 2208 | // handle fold CHAINS that cross non-RPO vec order — not just |
| 2209 | // the simple "operands pre-collected" case. |
| 2210 | // ============================================================= |
| 2211 | // |
| 2212 | // The strengthened non-RPO test from round 3 only pinned the |
| 2213 | // pre-collection phase of the N-8 fix — every operand was already |
| 2214 | // a leaf constant, so a single inner-loop iteration was enough. |
| 2215 | // This test builds a FOLD CHAIN where block B (vec position 1) |
| 2216 | // holds an IAdd that becomes constant only after block A (vec |
| 2217 | // position 2) produces a derived constant, AND A's derived |
| 2218 | // constant comes from folding another IAdd whose operands are |
| 2219 | // in blocks C (vec position 3) and D (vec position 4). |
| 2220 | // |
| 2221 | // Required order after the vec swap (pre-collection captures |
| 2222 | // only leaf constants from C and D): |
| 2223 | // |
| 2224 | // Iter 1: fold A's IAdd → const(3). Inserts into consts map. |
| 2225 | // B's IAdd still uses the (now-folded) A result, so |
| 2226 | // it may or may not fold depending on walk order. |
| 2227 | // Iter 2: if iter-1 didn't already fold B, iter-2 catches it. |
| 2228 | // Iter 3: stable. |
| 2229 | // |
| 2230 | // A version of const_fold without the inner fixpoint would stop |
| 2231 | // after iter 1 and leave B's IAdd in place — a missed fold that |
| 2232 | // the pass manager's outer fixpoint would NOT rescue because no |
| 2233 | // other pass changes anything here. |
| 2234 | #[test] |
| 2235 | fn audit_const_fold_inner_fixpoint_across_vec_order() { |
| 2236 | let mut m = Module::new("t".into()); |
| 2237 | let mut f = Function::new("f".into(), vec![], IrType::Int(IntWidth::I32)); |
| 2238 | |
| 2239 | // Four blocks, chained: entry → b → a → c → d → return. |
| 2240 | // After vec swap, b comes *before* a in func.blocks. |
| 2241 | let a_block = f.create_block("a"); |
| 2242 | let b_block = f.create_block("b"); |
| 2243 | let c_block = f.create_block("c"); |
| 2244 | let d_block = f.create_block("d"); |
| 2245 | |
| 2246 | // Leaves in c and d (so pre-collection picks them up). |
| 2247 | let c1 = f.next_value_id(); |
| 2248 | f.block_mut(c_block).insts.push(Inst { |
| 2249 | id: c1, |
| 2250 | kind: InstKind::ConstInt(10, IntWidth::I32), |
| 2251 | ty: IrType::Int(IntWidth::I32), |
| 2252 | span: dummy_span(), |
| 2253 | }); |
| 2254 | let c2 = f.next_value_id(); |
| 2255 | f.block_mut(c_block).insts.push(Inst { |
| 2256 | id: c2, |
| 2257 | kind: InstKind::ConstInt(20, IntWidth::I32), |
| 2258 | ty: IrType::Int(IntWidth::I32), |
| 2259 | span: dummy_span(), |
| 2260 | }); |
| 2261 | |
| 2262 | // A holds a derived IAdd whose operands are the c constants. |
| 2263 | // Pre-collection does NOT capture this (it's not a Const*). |
| 2264 | let a_sum = f.next_value_id(); |
| 2265 | f.block_mut(a_block).insts.push(Inst { |
| 2266 | id: a_sum, |
| 2267 | kind: InstKind::IAdd(c1, c2), // folds to const(30) |
| 2268 | ty: IrType::Int(IntWidth::I32), |
| 2269 | span: dummy_span(), |
| 2270 | }); |
| 2271 | |
| 2272 | // B holds ANOTHER derived IAdd that uses a's result. |
| 2273 | // This can only fold AFTER a_sum has been folded. |
| 2274 | let b_sum = f.next_value_id(); |
| 2275 | let seven = f.next_value_id(); |
| 2276 | f.block_mut(d_block).insts.push(Inst { |
| 2277 | id: seven, |
| 2278 | kind: InstKind::ConstInt(7, IntWidth::I32), |
| 2279 | ty: IrType::Int(IntWidth::I32), |
| 2280 | span: dummy_span(), |
| 2281 | }); |
| 2282 | f.block_mut(b_block).insts.push(Inst { |
| 2283 | id: b_sum, |
| 2284 | kind: InstKind::IAdd(a_sum, seven), // folds to const(37) |
| 2285 | ty: IrType::Int(IntWidth::I32), |
| 2286 | span: dummy_span(), |
| 2287 | }); |
| 2288 | |
| 2289 | // Wire: entry → c → d → a → b → return(b_sum) |
| 2290 | // (but we SWAP the vec positions of a and b so a comes AFTER b). |
| 2291 | let entry = f.entry; |
| 2292 | f.block_mut(entry).terminator = Some(Terminator::Branch(c_block, vec![])); |
| 2293 | f.block_mut(c_block).terminator = Some(Terminator::Branch(d_block, vec![])); |
| 2294 | f.block_mut(d_block).terminator = Some(Terminator::Branch(a_block, vec![])); |
| 2295 | f.block_mut(a_block).terminator = Some(Terminator::Branch(b_block, vec![])); |
| 2296 | f.block_mut(b_block).terminator = Some(Terminator::Return(Some(b_sum))); |
| 2297 | |
| 2298 | // Swap a and b in func.blocks so b comes before a in vec order. |
| 2299 | // func.blocks is [entry, a, b, c, d] after create_block calls. |
| 2300 | let a_idx = f.blocks.iter().position(|blk| blk.id == a_block).unwrap(); |
| 2301 | let b_idx = f.blocks.iter().position(|blk| blk.id == b_block).unwrap(); |
| 2302 | f.blocks.swap(a_idx, b_idx); |
| 2303 | |
| 2304 | m.add_function(f); |
| 2305 | |
| 2306 | assert!(verify_module(&m).is_empty(), "test setup invalid"); |
| 2307 | |
| 2308 | // Audit F1: call `ConstFold.run()` DIRECTLY, not through the |
| 2309 | // pass manager. The pass manager's outer fixpoint would rescue |
| 2310 | // a regression in the inner fixpoint loop (because a second |
| 2311 | // `ConstFold.run()` invocation would see `a_sum` already |
| 2312 | // folded and then fold `b_sum`), so running through the |
| 2313 | // manager does NOT pin the inner fixpoint behavior. A direct |
| 2314 | // single invocation forces convergence to happen inside |
| 2315 | // `ConstFold::run` itself. |
| 2316 | ConstFold.run(&mut m); |
| 2317 | |
| 2318 | let post = verify_module(&m); |
| 2319 | assert!(post.is_empty(), "const_fold left invalid IR: {:?}", post); |
| 2320 | |
| 2321 | // The fold MUST converge in a single `ConstFold.run()` call — |
| 2322 | // the terminator's value should now define ConstInt(37) (= 10+20+7). |
| 2323 | let f = &m.functions[0]; |
| 2324 | let terminator_val = f |
| 2325 | .blocks |
| 2326 | .iter() |
| 2327 | .find_map(|blk| match &blk.terminator { |
| 2328 | Some(Terminator::Return(Some(v))) => Some(*v), |
| 2329 | _ => None, |
| 2330 | }) |
| 2331 | .expect("no Return terminator"); |
| 2332 | let term_kind = f |
| 2333 | .blocks |
| 2334 | .iter() |
| 2335 | .flat_map(|b| b.insts.iter()) |
| 2336 | .find(|i| i.id == terminator_val) |
| 2337 | .map(|i| i.kind.clone()) |
| 2338 | .expect("terminator value has no defining inst"); |
| 2339 | match term_kind { |
| 2340 | InstKind::ConstInt(37, IntWidth::I32) => { /* good — chain converged in one run() */ } |
| 2341 | ref other => panic!( |
| 2342 | "audit M4-1 / F1: const_fold inner fixpoint failed to fold chain \ |
| 2343 | across non-RPO vec order in a single `ConstFold.run()` invocation. \ |
| 2344 | Expected ConstInt(37, I32), got {:?}", |
| 2345 | other |
| 2346 | ), |
| 2347 | } |
| 2348 | } |
| 2349 | |
| 2350 | // ============================================================= |
| 2351 | // FINDING M-9: const_fold large negative i64 left shift |
| 2352 | // ============================================================= |
| 2353 | // |
| 2354 | // Verify shl wrapping at width boundaries. |
| 2355 | #[test] |
| 2356 | fn audit_const_fold_shl_full_width_wrap() { |
| 2357 | let mut m = Module::new("t".into()); |
| 2358 | let mut f = Function::new("f".into(), vec![], IrType::Int(IntWidth::I32)); |
| 2359 | let v = push( |
| 2360 | &mut f, |
| 2361 | InstKind::ConstInt(1, IntWidth::I32), |
| 2362 | IrType::Int(IntWidth::I32), |
| 2363 | ); |
| 2364 | let cnt = push( |
| 2365 | &mut f, |
| 2366 | InstKind::ConstInt(31, IntWidth::I32), |
| 2367 | IrType::Int(IntWidth::I32), |
| 2368 | ); |
| 2369 | let s = push(&mut f, InstKind::Shl(v, cnt), IrType::Int(IntWidth::I32)); |
| 2370 | let entry = f.entry; |
| 2371 | f.block_mut(entry).terminator = Some(Terminator::Return(Some(s))); |
| 2372 | m.add_function(f); |
| 2373 | |
| 2374 | ConstFold.run(&mut m); |
| 2375 | let folded = m.functions[0].blocks[0] |
| 2376 | .insts |
| 2377 | .iter() |
| 2378 | .find(|i| i.id == s) |
| 2379 | .unwrap(); |
| 2380 | match folded.kind { |
| 2381 | InstKind::ConstInt(v, IntWidth::I32) => { |
| 2382 | // 1 << 31 in i32 is INT_MIN = -2147483648. |
| 2383 | assert_eq!(v, -2147483648, "expected i32 sign bit set, got {}", v); |
| 2384 | } |
| 2385 | _ => panic!(), |
| 2386 | } |
| 2387 | } |
| 2388 | |
| 2389 | // ============================================================= |
| 2390 | // FINDING M-10: const_fold ConstInt narrow signed overflow on iadd |
| 2391 | // ============================================================= |
| 2392 | #[test] |
| 2393 | fn audit_const_fold_iadd_i16_overflow() { |
| 2394 | let mut m = Module::new("t".into()); |
| 2395 | let mut f = Function::new("f".into(), vec![], IrType::Int(IntWidth::I16)); |
| 2396 | let a = push( |
| 2397 | &mut f, |
| 2398 | InstKind::ConstInt(32000, IntWidth::I16), |
| 2399 | IrType::Int(IntWidth::I16), |
| 2400 | ); |
| 2401 | let b = push( |
| 2402 | &mut f, |
| 2403 | InstKind::ConstInt(1000, IntWidth::I16), |
| 2404 | IrType::Int(IntWidth::I16), |
| 2405 | ); |
| 2406 | let s = push(&mut f, InstKind::IAdd(a, b), IrType::Int(IntWidth::I16)); |
| 2407 | let entry = f.entry; |
| 2408 | f.block_mut(entry).terminator = Some(Terminator::Return(Some(s))); |
| 2409 | m.add_function(f); |
| 2410 | |
| 2411 | ConstFold.run(&mut m); |
| 2412 | let folded = m.functions[0].blocks[0] |
| 2413 | .insts |
| 2414 | .iter() |
| 2415 | .find(|i| i.id == s) |
| 2416 | .unwrap(); |
| 2417 | match folded.kind { |
| 2418 | InstKind::ConstInt(v, IntWidth::I16) => { |
| 2419 | // 32000 + 1000 = 33000, wraps in i16 to -32536 |
| 2420 | assert_eq!(v, -32536, "expected i16 wrap, got {}", v); |
| 2421 | } |
| 2422 | _ => panic!(), |
| 2423 | } |
| 2424 | } |
| 2425 | |
| 2426 | // ============================================================= |
| 2427 | // FINDING M-6: const_prop must not break dominance when blocks branch |
| 2428 | // to a merge that uses values from a now-dropped path. |
| 2429 | // ============================================================= |
| 2430 | // |
| 2431 | // Manually construct: entry → A or B; both → merge with a phi-style |
| 2432 | // param. Fold the entry conditional to const(true) → drops B. Merge |
| 2433 | // loses one predecessor; verifier must still accept the result. |
| 2434 | #[test] |
| 2435 | fn audit_const_prop_merge_after_drop() { |
| 2436 | let mut m = Module::new("t".into()); |
| 2437 | let mut f = Function::new("f".into(), vec![], IrType::Int(IntWidth::I32)); |
| 2438 | |
| 2439 | let cond = push(&mut f, InstKind::ConstBool(true), IrType::Bool); |
| 2440 | let v_a = push( |
| 2441 | &mut f, |
| 2442 | InstKind::ConstInt(10, IntWidth::I32), |
| 2443 | IrType::Int(IntWidth::I32), |
| 2444 | ); |
| 2445 | let v_b = push( |
| 2446 | &mut f, |
| 2447 | InstKind::ConstInt(20, IntWidth::I32), |
| 2448 | IrType::Int(IntWidth::I32), |
| 2449 | ); |
| 2450 | |
| 2451 | let a = f.create_block("a"); |
| 2452 | let b = f.create_block("b"); |
| 2453 | let merge = f.create_block("merge"); |
| 2454 | let m_param = f.next_value_id(); |
| 2455 | f.block_mut(merge).params.push(BlockParam { |
| 2456 | id: m_param, |
| 2457 | ty: IrType::Int(IntWidth::I32), |
| 2458 | }); |
| 2459 | |
| 2460 | f.block_mut(a).terminator = Some(Terminator::Branch(merge, vec![v_a])); |
| 2461 | f.block_mut(b).terminator = Some(Terminator::Branch(merge, vec![v_b])); |
| 2462 | f.block_mut(merge).terminator = Some(Terminator::Return(Some(m_param))); |
| 2463 | |
| 2464 | let entry = f.entry; |
| 2465 | f.block_mut(entry).terminator = Some(Terminator::CondBranch { |
| 2466 | cond, |
| 2467 | true_dest: a, |
| 2468 | true_args: vec![], |
| 2469 | false_dest: b, |
| 2470 | false_args: vec![], |
| 2471 | }); |
| 2472 | m.add_function(f); |
| 2473 | |
| 2474 | let pre = verify_module(&m); |
| 2475 | assert!(pre.is_empty(), "test setup not valid: {:?}", pre); |
| 2476 | |
| 2477 | ConstProp.run(&mut m); |
| 2478 | |
| 2479 | let post = verify_module(&m); |
| 2480 | assert!( |
| 2481 | post.is_empty(), |
| 2482 | "const_prop produced an invalid module after dropping the false arm: {:?}", |
| 2483 | post |
| 2484 | ); |
| 2485 | |
| 2486 | // After folding, B should be gone but merge should still exist. |
| 2487 | let f = &m.functions[0]; |
| 2488 | assert!( |
| 2489 | !f.blocks.iter().any(|bk| bk.id == b), |
| 2490 | "block B should be pruned" |
| 2491 | ); |
| 2492 | assert!( |
| 2493 | f.blocks.iter().any(|bk| bk.id == merge), |
| 2494 | "merge should remain" |
| 2495 | ); |
| 2496 | } |
| 2497 |