tests/mir-opt/jump_threading.rs

   1 // unit-test: JumpThreading
   2 // compile-flags: -Zmir-enable-passes=+Inline
   3 // EMIT_MIR_FOR_EACH_PANIC_STRATEGY
   4
   5 #![feature(control_flow_enum)]
   6 #![feature(try_trait_v2)]
   7 #![feature(custom_mir, core_intrinsics, rustc_attrs)]
   8
   9 use std::intrinsics::mir::*;
  10 use std::ops::ControlFlow;
  11
  12 fn too_complex(x: Result<i32, usize>) -> Option<i32> {
  13     // CHECK-LABEL: fn too_complex(
  14     // CHECK: bb0: {
  15     // CHECK:     switchInt(move {{_.*}}) -> [0: bb3, 1: bb1, otherwise: bb2];
  16     // CHECK: bb1: {
  17     // CHECK:     [[controlflow:_.*]] = ControlFlow::<usize, i32>::Break(
  18     // CHECK:     goto -> bb8;
  19     // CHECK: bb2: {
  20     // CHECK:     unreachable;
  21     // CHECK: bb3: {
  22     // CHECK:     [[controlflow]] = ControlFlow::<usize, i32>::Continue(
  23     // CHECK:     goto -> bb4;
  24     // CHECK: bb4: {
  25     // CHECK:     goto -> bb6;
  26     // CHECK: bb5: {
  27     // CHECK:     {{_.*}} = (([[controlflow]] as Break).0: usize);
  28     // CHECK:     _0 = Option::<i32>::None;
  29     // CHECK:     goto -> bb7;
  30     // CHECK: bb6: {
  31     // CHECK:     {{_.*}} = (([[controlflow]] as Continue).0: i32);
  32     // CHECK:     _0 = Option::<i32>::Some(
  33     // CHECK:     goto -> bb7;
  34     // CHECK: bb7: {
  35     // CHECK:     return;
  36     // CHECK: bb8: {
  37     // CHECK:     goto -> bb5;
  38     match {
  39         match x {
  40             Ok(v) => ControlFlow::Continue(v),
  41             Err(r) => ControlFlow::Break(r),
  42         }
  43     } {
  44         ControlFlow::Continue(v) => Some(v),
  45         ControlFlow::Break(r) => None,
  46     }
  47 }
  48
  49 fn identity(x: Result<i32, i32>) -> Result<i32, i32> {
  50     // CHECK-LABEL: fn identity(
  51     // CHECK: bb0: {
  52     // CHECK:     [[x:_.*]] = _1;
  53     // CHECK:     switchInt(move {{_.*}}) -> [0: bb8, 1: bb6, otherwise: bb7];
  54     // CHECK: bb1: {
  55     // CHECK:     {{_.*}} = (([[controlflow:_.*]] as Continue).0: i32);
  56     // CHECK:     _0 = Result::<i32, i32>::Ok(
  57     // CHECK:     goto -> bb4;
  58     // CHECK: bb2: {
  59     // CHECK:     unreachable;
  60     // CHECK: bb3: {
  61     // CHECK:     {{_.*}} = (([[controlflow]] as Break).0: std::result::Result<std::convert::Infallible, i32>);
  62     // CHECK:     _0 = Result::<i32, i32>::Err(
  63     // CHECK:     goto -> bb4;
  64     // CHECK: bb4: {
  65     // CHECK:     return;
  66     // CHECK: bb5: {
  67     // CHECK:     goto -> bb1;
  68     // CHECK: bb6: {
  69     // CHECK:     {{_.*}} = move (([[x]] as Err).0: i32);
  70     // CHECK:     [[controlflow]] = ControlFlow::<Result<Infallible, i32>, i32>::Break(
  71     // CHECK:     goto -> bb9;
  72     // CHECK: bb7: {
  73     // CHECK:     unreachable;
  74     // CHECK: bb8: {
  75     // CHECK:     {{_.*}} = move (([[x]] as Ok).0: i32);
  76     // CHECK:     [[controlflow]] = ControlFlow::<Result<Infallible, i32>, i32>::Continue(
  77     // CHECK:     goto -> bb5;
  78     // CHECK: bb9: {
  79     // CHECK:     goto -> bb3;
  80     Ok(x?)
  81 }
  82
  83 enum DFA {
  84     A,
  85     B,
  86     C,
  87     D,
  88 }
  89
  90 /// Check that we do not thread through a loop header,
  91 /// to avoid creating an irreducible CFG.
  92 fn dfa() {
  93     // CHECK-LABEL: fn dfa(
  94     // CHECK: bb0: {
  95     // CHECK:     {{_.*}} = DFA::A;
  96     // CHECK:     goto -> bb1;
  97     // CHECK: bb1: {
  98     // CHECK:     switchInt({{.*}}) -> [0: bb4, 1: bb5, 2: bb6, 3: bb2, otherwise: bb3];
  99     // CHECK: bb2: {
 100     // CHECK:     return;
 101     // CHECK: bb3: {
 102     // CHECK:     unreachable;
 103     // CHECK: bb4: {
 104     // CHECK:     {{_.*}} = DFA::B;
 105     // CHECK:     goto -> bb1;
 106     // CHECK: bb5: {
 107     // CHECK:     {{_.*}} = DFA::C;
 108     // CHECK:     goto -> bb1;
 109     // CHECK: bb6: {
 110     // CHECK:     {{_.*}} = DFA::D;
 111     // CHECK:     goto -> bb1;
 112     let mut state = DFA::A;
 113     loop {
 114         match state {
 115             DFA::A => state = DFA::B,
 116             DFA::B => state = DFA::C,
 117             DFA::C => state = DFA::D,
 118             DFA::D => return,
 119         }
 120     }
 121 }
 122
 123 #[repr(u8)]
 124 enum CustomDiscr {
 125     A = 35,
 126     B = 73,
 127     C = 99,
 128 }
 129
 130 /// Verify that we correctly match the discriminant value, and not its index.
 131 fn custom_discr(x: bool) -> u8 {
 132     // CHECK-LABEL: fn custom_discr(
 133     // CHECK: bb0: {
 134     // CHECK:     switchInt({{.*}}) -> [0: bb2, otherwise: bb1];
 135     // CHECK: bb1: {
 136     // CHECK:     {{_.*}} = CustomDiscr::A;
 137     // CHECK:     goto -> bb7;
 138     // CHECK: bb2: {
 139     // CHECK:     {{_.*}} = CustomDiscr::B;
 140     // CHECK:     goto -> bb3;
 141     // CHECK: bb3: {
 142     // CHECK:     goto -> bb4;
 143     // CHECK: bb4: {
 144     // CHECK:     _0 = const 13_u8;
 145     // CHECK:     goto -> bb6;
 146     // CHECK: bb5: {
 147     // CHECK:     _0 = const 5_u8;
 148     // CHECK:     goto -> bb6;
 149     // CHECK: bb6: {
 150     // CHECK:     return;
 151     // CHECK: bb7: {
 152     // CHECK:     goto -> bb5;
 153     match if x { CustomDiscr::A } else { CustomDiscr::B } {
 154         CustomDiscr::A => 5,
 155         _ => 13,
 156     }
 157 }
 158
 159 #[custom_mir(dialect = "runtime", phase = "post-cleanup")]
 160 fn multiple_match(x: u8) -> u8 {
 161     // CHECK-LABEL: fn multiple_match(
 162     mir!(
 163         {
 164             // CHECK: bb0: {
 165             // CHECK:     switchInt([[x:_.*]]) -> [3: bb1, otherwise: bb2];
 166             match x { 3 => bb1, _ => bb2 }
 167         }
 168         bb1 = {
 169             // We know `x == 3`, so we can take `bb3`.
 170             // CHECK: bb1: {
 171             // CHECK:     {{_.*}} = [[x]];
 172             // CHECK:     goto -> bb3;
 173             let y = x;
 174             match y { 3 => bb3, _ => bb4 }
 175         }
 176         bb2 = {
 177             // We know `x != 3`, so we can take `bb6`.
 178             // CHECK: bb2: {
 179             // CHECK:     [[z:_.*]] = [[x]];
 180             // CHECK:     goto -> bb6;
 181             let z = x;
 182             match z { 3 => bb5, _ => bb6 }
 183         }
 184         bb3 = {
 185             // CHECK: bb3: {
 186             // CHECK:     _0 = const 5_u8;
 187             // CHECK:     return;
 188             RET = 5;
 189             Return()
 190         }
 191         bb4 = {
 192             // CHECK: bb4: {
 193             // CHECK:     _0 = const 7_u8;
 194             // CHECK:     return;
 195             RET = 7;
 196             Return()
 197         }
 198         bb5 = {
 199             // CHECK: bb5: {
 200             // CHECK:     _0 = const 9_u8;
 201             // CHECK:     return;
 202             RET = 9;
 203             Return()
 204         }
 205         bb6 = {
 206             // We know `z != 3`, so we CANNOT take `bb7`.
 207             // CHECK: bb6: {
 208             // CHECK:     switchInt([[z]]) -> [1: bb7, otherwise: bb8];
 209             match z { 1 => bb7, _ => bb8 }
 210         }
 211         bb7 = {
 212             // CHECK: bb7: {
 213             // CHECK:     _0 = const 9_u8;
 214             // CHECK:     return;
 215             RET = 9;
 216             Return()
 217         }
 218         bb8 = {
 219             // CHECK: bb8: {
 220             // CHECK:     _0 = const 11_u8;
 221             // CHECK:     return;
 222             RET = 11;
 223             Return()
 224         }
 225     )
 226 }
 227
 228 /// Both 1-3-4 and 2-3-4 are threadable. As 1 and 2 are the only predecessors of 3,
 229 /// verify that we only thread the 3-4 part.
 230 #[custom_mir(dialect = "runtime", phase = "post-cleanup")]
 231 fn duplicate_chain(x: bool) -> u8 {
 232     // CHECK-LABEL: fn duplicate_chain(
 233     mir!(
 234         let a: u8;
 235         {
 236             // CHECK: bb0: {
 237             // CHECK:     switchInt({{.*}}) -> [1: bb1, otherwise: bb2];
 238             match x { true => bb1, _ => bb2 }
 239         }
 240         bb1 = {
 241             // CHECK: bb1: {
 242             // CHECK:     [[a:_.*]] = const 5_u8;
 243             // CHECK:     goto -> bb3;
 244             a = 5;
 245             Goto(bb3)
 246         }
 247         bb2 = {
 248             // CHECK: bb2: {
 249             // CHECK:     [[a]] = const 5_u8;
 250             // CHECK:     goto -> bb3;
 251             a = 5;
 252             Goto(bb3)
 253         }
 254         bb3 = {
 255             // CHECK: bb3: {
 256             // CHECK:     {{_.*}} = const 13_i32;
 257             // CHECK:     goto -> bb4;
 258             let b = 13;
 259             Goto(bb4)
 260         }
 261         bb4 = {
 262             // CHECK: bb4: {
 263             // CHECK:     {{_.*}} = const 15_i32;
 264             // CHECK-NOT: switchInt(
 265             // CHECK:     goto -> bb5;
 266             let c = 15;
 267             match a { 5 => bb5, _ => bb6 }
 268         }
 269         bb5 = {
 270             // CHECK: bb5: {
 271             // CHECK:     _0 = const 7_u8;
 272             // CHECK:     return;
 273             RET = 7;
 274             Return()
 275         }
 276         bb6 = {
 277             // CHECK: bb6: {
 278             // CHECK:     _0 = const 9_u8;
 279             // CHECK:     return;
 280             RET = 9;
 281             Return()
 282         }
 283     )
 284 }
 285
 286 #[rustc_layout_scalar_valid_range_start(1)]
 287 #[rustc_nonnull_optimization_guaranteed]
 288 struct NonZeroUsize(usize);
 289
 290 /// Verify that we correctly discard threads that may mutate a discriminant by aliasing.
 291 #[custom_mir(dialect = "runtime", phase = "post-cleanup")]
 292 fn mutate_discriminant() -> u8 {
 293     // CHECK-LABEL: fn mutate_discriminant(
 294     // CHECK-NOT: goto -> {{bb.*}};
 295     // CHECK: switchInt(
 296     // CHECK-NOT: goto -> {{bb.*}};
 297     mir!(
 298         let x: Option<NonZeroUsize>;
 299         {
 300             SetDiscriminant(x, 1);
 301             // This assignment overwrites the niche in which the discriminant is stored.
 302             place!(Field(Field(Variant(x, 1), 0), 0)) = 0_usize;
 303             // So we cannot know the value of this discriminant.
 304             let a = Discriminant(x);
 305             match a {
 306                 0 => bb1,
 307                 _ => bad,
 308             }
 309         }
 310         bb1 = {
 311             RET = 1;
 312             Return()
 313         }
 314         bad = {
 315             RET = 2;
 316             Unreachable()
 317         }
 318     )
 319 }
 320
 321 /// Verify that we do not try to reason when there are mutable pointers involved.
 322 fn mutable_ref() -> bool {
 323     // CHECK-LABEL: fn mutable_ref(
 324     // CHECK-NOT: goto -> {{bb.*}};
 325     // CHECK: switchInt(
 326     // CHECK: goto -> [[bbret:bb.*]];
 327     // CHECK: goto -> [[bbret]];
 328     // CHECK: [[bbret]]: {
 329     // CHECK-NOT: {{bb.*}}: {
 330     // CHECK: return;
 331     let mut x = 5;
 332     let a = std::ptr::addr_of_mut!(x);
 333     x = 7;
 334     unsafe { *a = 8 };
 335     if x == 7 {
 336         true
 337     } else {
 338         false
 339     }
 340 }
 341
 342 /// This function has 2 TOs: 1-3-4 and 0-1-3-4-6.
 343 /// We verify that the second TO does not modify 3 once the first has been applied.
 344 #[custom_mir(dialect = "runtime", phase = "post-cleanup")]
 345 fn renumbered_bb(x: bool) -> u8 {
 346     // CHECK-LABEL: fn renumbered_bb(
 347     mir!(
 348         let a: bool;
 349         let b: bool;
 350         {
 351             // CHECK: bb0: {
 352             // CHECK:     switchInt({{.*}}) -> [1: bb1, otherwise: bb2];
 353             b = false;
 354             match x { true => bb1, _ => bb2 }
 355         }
 356         bb1 = {
 357             // CHECK: bb1: {
 358             // CHECK:     goto -> bb8;
 359             a = false;
 360             Goto(bb3)
 361         }
 362         bb2 = {
 363             // CHECK: bb2: {
 364             // CHECK:     goto -> bb3;
 365             a = x;
 366             b = x;
 367             Goto(bb3)
 368         }
 369         bb3 = {
 370             // CHECK: bb3: {
 371             // CHECK:     switchInt({{.*}}) -> [0: bb4, otherwise: bb5];
 372             match a { false => bb4, _ => bb5 }
 373         }
 374         bb4 = {
 375             // CHECK: bb4: {
 376             // CHECK:     switchInt({{.*}}) -> [0: bb6, otherwise: bb7];
 377             match b { false => bb6, _ => bb7 }
 378         }
 379         bb5 = {
 380             // CHECK: bb5: {
 381             // CHECK:     _0 = const 7_u8;
 382             RET = 7;
 383             Return()
 384         }
 385         bb6 = {
 386             // CHECK: bb6: {
 387             // CHECK:     _0 = const 9_u8;
 388             RET = 9;
 389             Return()
 390         }
 391         bb7 = {
 392             // CHECK: bb7: {
 393             // CHECK:     _0 = const 11_u8;
 394             RET = 11;
 395             Return()
 396         }
 397         // Duplicate of bb3.
 398         // CHECK: bb8: {
 399         // CHECK-NEXT: goto -> bb9;
 400         // Duplicate of bb4.
 401         // CHECK: bb9: {
 402         // CHECK-NEXT: goto -> bb6;
 403     )
 404 }
 405
 406 /// This function has 3 TOs: 1-4-5, 0-1-4-7-5-8 and 3-4-7-5-6
 407 /// After applying the first TO, we create bb9 to replace 4, and rename 1-4 edge by 1-9. The
 408 /// second TO may try to thread non-existing edge 9-4.
 409 /// This test verifies that we preserve semantics by bailing out of this second TO.
 410 #[custom_mir(dialect = "runtime", phase = "post-cleanup")]
 411 fn disappearing_bb(x: u8) -> u8 {
 412     // CHECK-LABEL: fn disappearing_bb(
 413     mir!(
 414         let a: bool;
 415         let b: bool;
 416         {
 417             a = true;
 418             b = true;
 419             match x { 0 => bb3, 1 => bb3, 2 => bb1, _ => bb2 }
 420         }
 421         bb1 = {
 422             // CHECK: bb1: {
 423             // CHECK: goto -> bb9;
 424             b = false;
 425             Goto(bb4)
 426         }
 427         bb2 = {
 428             Unreachable()
 429         }
 430         bb3 = {
 431             // CHECK: bb3: {
 432             // CHECK: goto -> bb10;
 433             a = false;
 434             Goto(bb4)
 435         }
 436         bb4 = {
 437             match b { false => bb5, _ => bb7 }
 438         }
 439         bb5 = {
 440             match a { false => bb6, _ => bb8 }
 441         }
 442         bb6 = {
 443             Return()
 444         }
 445         bb7 = {
 446             Goto(bb5)
 447         }
 448         bb8 = {
 449             Goto(bb6)
 450         }
 451         // CHECK: bb9: {
 452         // CHECK: goto -> bb5;
 453         // CHECK: bb10: {
 454         // CHECK: goto -> bb6;
 455     )
 456 }
 457
 458 fn main() {
 459     too_complex(Ok(0));
 460     identity(Ok(0));
 461     custom_discr(false);
 462     dfa();
 463     multiple_match(5);
 464     duplicate_chain(false);
 465     mutate_discriminant();
 466     mutable_ref();
 467     renumbered_bb(true);
 468     disappearing_bb(7);
 469 }
 470
 471 // EMIT_MIR jump_threading.too_complex.JumpThreading.diff
 472 // EMIT_MIR jump_threading.identity.JumpThreading.diff
 473 // EMIT_MIR jump_threading.custom_discr.JumpThreading.diff
 474 // EMIT_MIR jump_threading.dfa.JumpThreading.diff
 475 // EMIT_MIR jump_threading.multiple_match.JumpThreading.diff
 476 // EMIT_MIR jump_threading.duplicate_chain.JumpThreading.diff
 477 // EMIT_MIR jump_threading.mutate_discriminant.JumpThreading.diff
 478 // EMIT_MIR jump_threading.mutable_ref.JumpThreading.diff
 479 // EMIT_MIR jump_threading.renumbered_bb.JumpThreading.diff
 480 // EMIT_MIR jump_threading.disappearing_bb.JumpThreading.diff