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