247 lines · plain
1; NOTE: Assertions have been autogenerated by utils/update_analyze_test_checks.py2; RUN: opt -disable-output "-passes=print<scalar-evolution>" %s 2>&1 | FileCheck %s3 4; If m is constant, exact-not-taken is umin(n, m)5; https://alive2.llvm.org/ce/z/ZTNXgY6define void @logical_and_m_const(i32 %n) {7; CHECK-LABEL: 'logical_and_m_const'8; CHECK-NEXT: Classifying expressions for: @logical_and_m_const9; 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, 112; 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 false14; 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_const16; CHECK-NEXT: Loop %loop: backedge-taken count is (2 umin %n)17; CHECK-NEXT: Loop %loop: constant max backedge-taken count is i32 218; CHECK-NEXT: Loop %loop: symbolic max backedge-taken count is (2 umin %n)19; CHECK-NEXT: Loop %loop: Trip multiple is 120;21entry:22 br label %loop23loop:24 %i = phi i32 [0, %entry], [%i.next, %loop]25 %i.next = add i32 %i, 126 %cond_i = icmp ult i32 %i, %n27 %cond_i2 = icmp ult i32 %i, 228 %cond = select i1 %cond_i, i1 %cond_i2, i1 false29 br i1 %cond, label %loop, label %exit30exit:31 ret void32}33 34; exact-not-taken is umin(2, m) because m participates in the exit branch condition.35; https://alive2.llvm.org/ce/z/rCVMmp36define void @logical_and_nonzero(i32 %m) {37; CHECK-LABEL: 'logical_and_nonzero'38; CHECK-NEXT: Classifying expressions for: @logical_and_nonzero39; 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, 142; 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 false44; 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_nonzero46; CHECK-NEXT: Loop %loop: backedge-taken count is (2 umin %m)47; CHECK-NEXT: Loop %loop: constant max backedge-taken count is i32 248; CHECK-NEXT: Loop %loop: symbolic max backedge-taken count is (2 umin %m)49; CHECK-NEXT: Loop %loop: Trip multiple is 150;51entry:52 br label %loop53loop:54 %i = phi i32 [0, %entry], [%i.next, %loop]55 %i.next = add i32 %i, 156 %cond_i = icmp ult i32 %i, 257 %cond_i2 = icmp ult i32 %i, %m58 %cond = select i1 %cond_i, i1 %cond_i2, i1 false59 br i1 %cond, label %loop, label %exit60exit:61 ret void62}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/rlaN4a66; 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_zero70; 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, 173; 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 false75; 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_zero77; CHECK-NEXT: Loop %loop: backedge-taken count is i32 078; CHECK-NEXT: Loop %loop: constant max backedge-taken count is i32 079; CHECK-NEXT: Loop %loop: symbolic max backedge-taken count is i32 080; CHECK-NEXT: Loop %loop: Trip multiple is 181;82entry:83 br label %loop84loop:85 %i = phi i32 [0, %entry], [%i.next, %loop]86 %i.next = add i32 %i, 187 %cond_i = icmp ult i32 %i, 088 %cond_i2 = icmp ult i32 %i, %m89 %cond = select i1 %cond_i, i1 %cond_i2, i1 false90 br i1 %cond, label %loop, label %exit91exit:92 ret void93}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-zu98; 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_inversed102; 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, 1105; 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 false107; 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_inversed109; 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 %loop115loop:116 %i = phi i32 [0, %entry], [%i.next, %loop]117 %i.next = add i32 %i, 1118 %cond_i = icmp uge i32 %i, %n119 %cond_i2 = icmp uge i32 %i, %m120 %cond = select i1 %cond_i, i1 %cond_i2, i1 false121 br i1 %cond, label %exit, label %loop122exit:123 ret void124}125 126; If m is constant, exact-not-taken is umin(n, m)127; https://alive2.llvm.org/ce/z/RQmJiq128define void @logical_or_m_const(i32 %n) {129; CHECK-LABEL: 'logical_or_m_const'130; CHECK-NEXT: Classifying expressions for: @logical_or_m_const131; 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, 1134; 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_i2136; 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_const138; CHECK-NEXT: Loop %loop: backedge-taken count is (2 umin %n)139; CHECK-NEXT: Loop %loop: constant max backedge-taken count is i32 2140; CHECK-NEXT: Loop %loop: symbolic max backedge-taken count is (2 umin %n)141; CHECK-NEXT: Loop %loop: Trip multiple is 1142;143entry:144 br label %loop145loop:146 %i = phi i32 [0, %entry], [%i.next, %loop]147 %i.next = add i32 %i, 1148 %cond_i = icmp uge i32 %i, %n149 %cond_i2 = icmp uge i32 %i, 2150 %cond = select i1 %cond_i, i1 true, i1 %cond_i2151 br i1 %cond, label %exit, label %loop152exit:153 ret void154}155 156; exact-not-taken is umin(2, m) because m participates in exit branch condition.157; https://alive2.llvm.org/ce/z/zcHS_d158define void @logical_or_nonzero(i32 %m) {159; CHECK-LABEL: 'logical_or_nonzero'160; CHECK-NEXT: Classifying expressions for: @logical_or_nonzero161; 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, 1164; 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_i2166; 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_nonzero168; CHECK-NEXT: Loop %loop: backedge-taken count is (2 umin %m)169; CHECK-NEXT: Loop %loop: constant max backedge-taken count is i32 2170; CHECK-NEXT: Loop %loop: symbolic max backedge-taken count is (2 umin %m)171; CHECK-NEXT: Loop %loop: Trip multiple is 1172;173entry:174 br label %loop175loop:176 %i = phi i32 [0, %entry], [%i.next, %loop]177 %i.next = add i32 %i, 1178 %cond_i = icmp uge i32 %i, 2179 %cond_i2 = icmp uge i32 %i, %m180 %cond = select i1 %cond_i, i1 true, i1 %cond_i2181 br i1 %cond, label %exit, label %loop182exit:183 ret void184}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/-dUmmc188; 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_zero192; 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, 1195; 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_i2197; 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_zero199; CHECK-NEXT: Loop %loop: backedge-taken count is i32 0200; CHECK-NEXT: Loop %loop: constant max backedge-taken count is i32 0201; CHECK-NEXT: Loop %loop: symbolic max backedge-taken count is i32 0202; CHECK-NEXT: Loop %loop: Trip multiple is 1203;204entry:205 br label %loop206loop:207 %i = phi i32 [0, %entry], [%i.next, %loop]208 %i.next = add i32 %i, 1209 %cond_i = icmp uge i32 %i, 0210 %cond_i2 = icmp uge i32 %i, %m211 %cond = select i1 %cond_i, i1 true, i1 %cond_i2212 br i1 %cond, label %exit, label %loop213exit:214 ret void215}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/VaCu9C220; 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_inversed224; 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, 1227; 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_i2229; 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_inversed231; 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 %loop237loop:238 %i = phi i32 [0, %entry], [%i.next, %loop]239 %i.next = add i32 %i, 1240 %cond_i = icmp ult i32 %i, %n241 %cond_i2 = icmp ult i32 %i, %m242 %cond = select i1 %cond_i, i1 true, i1 %cond_i2243 br i1 %cond, label %loop, label %exit244exit:245 ret void246}247