1; NOTE: Assertions have been autogenerated by utils/update_analyze_test_checks.py 2; RUN: opt -disable-output "-passes=print<scalar-evolution>" %s 2>&1 | FileCheck %s 3 4; If m is constant, exact-not-taken is umin(n, m) 5; https://alive2.llvm.org/ce/z/ZTNXgY 6define void @logical_and_m_const(i32 %n) { 7; CHECK-LABEL: 'logical_and_m_const' 8; CHECK-NEXT: Classifying expressions for: @logical_and_m_const 9; CHECK-NEXT: %i = phi i32 [ 0, %entry ], [ %i.next, %loop ] 10; CHECK-NEXT: --> {0,+,1}<%loop> U: [0,3) S: [0,3) Exits: (2 umin %n) LoopDispositions: { %loop: Computable } 11; CHECK-NEXT: %i.next = add i32 %i, 1 12; CHECK-NEXT: --> {1,+,1}<%loop> U: [1,4) S: [1,4) Exits: (1 + (2 umin %n))<nuw><nsw> LoopDispositions: { %loop: Computable } 13; CHECK-NEXT: %cond = select i1 %cond_i, i1 %cond_i2, i1 false 14; CHECK-NEXT: --> (%cond_i umin_seq %cond_i2) U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Variant } 15; CHECK-NEXT: Determining loop execution counts for: @logical_and_m_const 16; CHECK-NEXT: Loop %loop: backedge-taken count is (2 umin %n) 17; CHECK-NEXT: Loop %loop: max backedge-taken count is 2 18; CHECK-NEXT: Loop %loop: Predicated backedge-taken count is (2 umin %n) 19; CHECK-NEXT: Predicates: 20; CHECK: Loop %loop: Trip multiple is 1 21; 22entry: 23 br label %loop 24loop: 25 %i = phi i32 [0, %entry], [%i.next, %loop] 26 %i.next = add i32 %i, 1 27 %cond_i = icmp ult i32 %i, %n 28 %cond_i2 = icmp ult i32 %i, 2 29 %cond = select i1 %cond_i, i1 %cond_i2, i1 false 30 br i1 %cond, label %loop, label %exit 31exit: 32 ret void 33} 34 35; exact-not-taken is umin(2, m) because m participates in the exit branch condition. 36; https://alive2.llvm.org/ce/z/rCVMmp 37define void @logical_and_nonzero(i32 %m) { 38; CHECK-LABEL: 'logical_and_nonzero' 39; CHECK-NEXT: Classifying expressions for: @logical_and_nonzero 40; CHECK-NEXT: %i = phi i32 [ 0, %entry ], [ %i.next, %loop ] 41; CHECK-NEXT: --> {0,+,1}<%loop> U: [0,3) S: [0,3) Exits: (2 umin %m) LoopDispositions: { %loop: Computable } 42; CHECK-NEXT: %i.next = add i32 %i, 1 43; CHECK-NEXT: --> {1,+,1}<%loop> U: [1,4) S: [1,4) Exits: (1 + (2 umin %m))<nuw><nsw> LoopDispositions: { %loop: Computable } 44; CHECK-NEXT: %cond = select i1 %cond_i, i1 %cond_i2, i1 false 45; CHECK-NEXT: --> (%cond_i umin_seq %cond_i2) U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Variant } 46; CHECK-NEXT: Determining loop execution counts for: @logical_and_nonzero 47; CHECK-NEXT: Loop %loop: backedge-taken count is (2 umin %m) 48; CHECK-NEXT: Loop %loop: max backedge-taken count is 2 49; CHECK-NEXT: Loop %loop: Predicated backedge-taken count is (2 umin %m) 50; CHECK-NEXT: Predicates: 51; CHECK: Loop %loop: Trip multiple is 1 52; 53entry: 54 br label %loop 55loop: 56 %i = phi i32 [0, %entry], [%i.next, %loop] 57 %i.next = add i32 %i, 1 58 %cond_i = icmp ult i32 %i, 2 59 %cond_i2 = icmp ult i32 %i, %m 60 %cond = select i1 %cond_i, i1 %cond_i2, i1 false 61 br i1 %cond, label %loop, label %exit 62exit: 63 ret void 64} 65 66; exact-not-taken cannot be umin(0, m) because m never participates in the exit branch condition. 67; https://alive2.llvm.org/ce/z/rlaN4a 68; Instead, it should be just 0. 69define void @logical_and_zero(i32 %m) { 70; CHECK-LABEL: 'logical_and_zero' 71; CHECK-NEXT: Classifying expressions for: @logical_and_zero 72; CHECK-NEXT: %i = phi i32 [ 0, %entry ], [ %i.next, %loop ] 73; CHECK-NEXT: --> {0,+,1}<%loop> U: [0,1) S: [0,1) Exits: 0 LoopDispositions: { %loop: Computable } 74; CHECK-NEXT: %i.next = add i32 %i, 1 75; CHECK-NEXT: --> {1,+,1}<%loop> U: [1,2) S: [1,2) Exits: 1 LoopDispositions: { %loop: Computable } 76; CHECK-NEXT: %cond = select i1 %cond_i, i1 %cond_i2, i1 false 77; CHECK-NEXT: --> (%cond_i umin_seq %cond_i2) U: full-set S: full-set Exits: false LoopDispositions: { %loop: Variant } 78; CHECK-NEXT: Determining loop execution counts for: @logical_and_zero 79; CHECK-NEXT: Loop %loop: backedge-taken count is 0 80; CHECK-NEXT: Loop %loop: max backedge-taken count is 0 81; CHECK-NEXT: Loop %loop: Predicated backedge-taken count is 0 82; CHECK-NEXT: Predicates: 83; CHECK: Loop %loop: Trip multiple is 1 84; 85entry: 86 br label %loop 87loop: 88 %i = phi i32 [0, %entry], [%i.next, %loop] 89 %i.next = add i32 %i, 1 90 %cond_i = icmp ult i32 %i, 0 91 %cond_i2 = icmp ult i32 %i, %m 92 %cond = select i1 %cond_i, i1 %cond_i2, i1 false 93 br i1 %cond, label %loop, label %exit 94exit: 95 ret void 96} 97 98; exact-not-taken is umax(n, m) because both conditions (cond_i, cond_i2) participate in branching, 99; preventing them from being poison. 100; https://alive2.llvm.org/ce/z/8_p-zu 101; Currently SCEV is conservative in this case and simply returns unknown. 102define void @logical_and_inversed(i32 %n, i32 %m) { 103; CHECK-LABEL: 'logical_and_inversed' 104; CHECK-NEXT: Classifying expressions for: @logical_and_inversed 105; CHECK-NEXT: %i = phi i32 [ 0, %entry ], [ %i.next, %loop ] 106; CHECK-NEXT: --> {0,+,1}<%loop> U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Computable } 107; CHECK-NEXT: %i.next = add i32 %i, 1 108; CHECK-NEXT: --> {1,+,1}<%loop> U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Computable } 109; CHECK-NEXT: %cond = select i1 %cond_i, i1 %cond_i2, i1 false 110; CHECK-NEXT: --> (%cond_i umin_seq %cond_i2) U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Variant } 111; CHECK-NEXT: Determining loop execution counts for: @logical_and_inversed 112; CHECK-NEXT: Loop %loop: Unpredictable backedge-taken count. 113; CHECK-NEXT: Loop %loop: Unpredictable max backedge-taken count. 114; CHECK-NEXT: Loop %loop: Unpredictable predicated backedge-taken count. 115; 116entry: 117 br label %loop 118loop: 119 %i = phi i32 [0, %entry], [%i.next, %loop] 120 %i.next = add i32 %i, 1 121 %cond_i = icmp uge i32 %i, %n 122 %cond_i2 = icmp uge i32 %i, %m 123 %cond = select i1 %cond_i, i1 %cond_i2, i1 false 124 br i1 %cond, label %exit, label %loop 125exit: 126 ret void 127} 128 129; If m is constant, exact-not-taken is umin(n, m) 130; https://alive2.llvm.org/ce/z/RQmJiq 131define void @logical_or_m_const(i32 %n) { 132; CHECK-LABEL: 'logical_or_m_const' 133; CHECK-NEXT: Classifying expressions for: @logical_or_m_const 134; CHECK-NEXT: %i = phi i32 [ 0, %entry ], [ %i.next, %loop ] 135; CHECK-NEXT: --> {0,+,1}<%loop> U: [0,3) S: [0,3) Exits: (2 umin %n) LoopDispositions: { %loop: Computable } 136; CHECK-NEXT: %i.next = add i32 %i, 1 137; CHECK-NEXT: --> {1,+,1}<%loop> U: [1,4) S: [1,4) Exits: (1 + (2 umin %n))<nuw><nsw> LoopDispositions: { %loop: Computable } 138; CHECK-NEXT: %cond = select i1 %cond_i, i1 true, i1 %cond_i2 139; CHECK-NEXT: --> %cond U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Variant } 140; CHECK-NEXT: Determining loop execution counts for: @logical_or_m_const 141; CHECK-NEXT: Loop %loop: backedge-taken count is (2 umin %n) 142; CHECK-NEXT: Loop %loop: max backedge-taken count is 2 143; CHECK-NEXT: Loop %loop: Predicated backedge-taken count is (2 umin %n) 144; CHECK-NEXT: Predicates: 145; CHECK: Loop %loop: Trip multiple is 1 146; 147entry: 148 br label %loop 149loop: 150 %i = phi i32 [0, %entry], [%i.next, %loop] 151 %i.next = add i32 %i, 1 152 %cond_i = icmp uge i32 %i, %n 153 %cond_i2 = icmp uge i32 %i, 2 154 %cond = select i1 %cond_i, i1 true, i1 %cond_i2 155 br i1 %cond, label %exit, label %loop 156exit: 157 ret void 158} 159 160; exact-not-taken is umin(2, m) because m participates in exit branch condition. 161; https://alive2.llvm.org/ce/z/zcHS_d 162define void @logical_or_nonzero(i32 %m) { 163; CHECK-LABEL: 'logical_or_nonzero' 164; CHECK-NEXT: Classifying expressions for: @logical_or_nonzero 165; CHECK-NEXT: %i = phi i32 [ 0, %entry ], [ %i.next, %loop ] 166; CHECK-NEXT: --> {0,+,1}<%loop> U: [0,3) S: [0,3) Exits: (2 umin %m) LoopDispositions: { %loop: Computable } 167; CHECK-NEXT: %i.next = add i32 %i, 1 168; CHECK-NEXT: --> {1,+,1}<%loop> U: [1,4) S: [1,4) Exits: (1 + (2 umin %m))<nuw><nsw> LoopDispositions: { %loop: Computable } 169; CHECK-NEXT: %cond = select i1 %cond_i, i1 true, i1 %cond_i2 170; CHECK-NEXT: --> %cond U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Variant } 171; CHECK-NEXT: Determining loop execution counts for: @logical_or_nonzero 172; CHECK-NEXT: Loop %loop: backedge-taken count is (2 umin %m) 173; CHECK-NEXT: Loop %loop: max backedge-taken count is 2 174; CHECK-NEXT: Loop %loop: Predicated backedge-taken count is (2 umin %m) 175; CHECK-NEXT: Predicates: 176; CHECK: Loop %loop: Trip multiple is 1 177; 178entry: 179 br label %loop 180loop: 181 %i = phi i32 [0, %entry], [%i.next, %loop] 182 %i.next = add i32 %i, 1 183 %cond_i = icmp uge i32 %i, 2 184 %cond_i2 = icmp uge i32 %i, %m 185 %cond = select i1 %cond_i, i1 true, i1 %cond_i2 186 br i1 %cond, label %exit, label %loop 187exit: 188 ret void 189} 190 191; exact-not-taken cannot be umin(0, m) because m does not participate in exit branch condition. 192; https://alive2.llvm.org/ce/z/-dUmmc 193; Instead, exact-not-taken should be just 0. 194define void @logical_or_zero(i32 %m) { 195; CHECK-LABEL: 'logical_or_zero' 196; CHECK-NEXT: Classifying expressions for: @logical_or_zero 197; CHECK-NEXT: %i = phi i32 [ 0, %entry ], [ %i.next, %loop ] 198; CHECK-NEXT: --> {0,+,1}<%loop> U: [0,1) S: [0,1) Exits: 0 LoopDispositions: { %loop: Computable } 199; CHECK-NEXT: %i.next = add i32 %i, 1 200; CHECK-NEXT: --> {1,+,1}<%loop> U: [1,2) S: [1,2) Exits: 1 LoopDispositions: { %loop: Computable } 201; CHECK-NEXT: %cond = select i1 %cond_i, i1 true, i1 %cond_i2 202; CHECK-NEXT: --> %cond U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Variant } 203; CHECK-NEXT: Determining loop execution counts for: @logical_or_zero 204; CHECK-NEXT: Loop %loop: backedge-taken count is 0 205; CHECK-NEXT: Loop %loop: max backedge-taken count is 0 206; CHECK-NEXT: Loop %loop: Predicated backedge-taken count is 0 207; CHECK-NEXT: Predicates: 208; CHECK: Loop %loop: Trip multiple is 1 209; 210entry: 211 br label %loop 212loop: 213 %i = phi i32 [0, %entry], [%i.next, %loop] 214 %i.next = add i32 %i, 1 215 %cond_i = icmp uge i32 %i, 0 216 %cond_i2 = icmp uge i32 %i, %m 217 %cond = select i1 %cond_i, i1 true, i1 %cond_i2 218 br i1 %cond, label %exit, label %loop 219exit: 220 ret void 221} 222 223; exact-not-taken is umax(n, m) because both conditions (cond_i, cond_i2) participate in branching, 224; preventing them from being poison. 225; https://alive2.llvm.org/ce/z/VaCu9C 226; Currently SCEV is conservative in this case and simply returns unknown. 227define void @logical_or_inversed(i32 %n, i32 %m) { 228; CHECK-LABEL: 'logical_or_inversed' 229; CHECK-NEXT: Classifying expressions for: @logical_or_inversed 230; CHECK-NEXT: %i = phi i32 [ 0, %entry ], [ %i.next, %loop ] 231; CHECK-NEXT: --> {0,+,1}<%loop> U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Computable } 232; CHECK-NEXT: %i.next = add i32 %i, 1 233; CHECK-NEXT: --> {1,+,1}<%loop> U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Computable } 234; CHECK-NEXT: %cond = select i1 %cond_i, i1 true, i1 %cond_i2 235; CHECK-NEXT: --> %cond U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Variant } 236; CHECK-NEXT: Determining loop execution counts for: @logical_or_inversed 237; CHECK-NEXT: Loop %loop: Unpredictable backedge-taken count. 238; CHECK-NEXT: Loop %loop: Unpredictable max backedge-taken count. 239; CHECK-NEXT: Loop %loop: Unpredictable predicated backedge-taken count. 240; 241entry: 242 br label %loop 243loop: 244 %i = phi i32 [0, %entry], [%i.next, %loop] 245 %i.next = add i32 %i, 1 246 %cond_i = icmp ult i32 %i, %n 247 %cond_i2 = icmp ult i32 %i, %m 248 %cond = select i1 %cond_i, i1 true, i1 %cond_i2 249 br i1 %cond, label %loop, label %exit 250exit: 251 ret void 252} 253