llvm/test/Analysis/ScalarEvolution/incorrect-exit-count.ll

   1 ; NOTE: Assertions have been autogenerated by utils/update_analyze_test_checks.py
   2 ; RUN: opt -passes='print<scalar-evolution>' < %s -disable-output 2>&1 | FileCheck %s
   3
   4 @b = dso_local global i32 5, align 4
   5 @__const.f.g = private unnamed_addr constant [1 x [4 x i16]] [[4 x i16] [i16 1, i16 0, i16 0, i16 0]], align 2
   6 @a = common dso_local global i32 0, align 4
   7 @c = common dso_local global i32 0, align 4
   8 @d = common dso_local global i32 0, align 4
   9 @e = common dso_local global i32 0, align 4
  10
  11 ; When inner.loop is taken as an exiting block of outer.loop, we cannot use the
  12 ; addrec of %storemerge1921.3, which is {3, +, -1}<inner.loop>, to calculate the
  13 ; exit count because it doesn't belong to outer.loop.
  14 define dso_local i32 @f() {
  15 ; CHECK-LABEL: 'f'
  16 ; CHECK-NEXT:  Classifying expressions for: @f
  17 ; CHECK-NEXT:    %storemerge23 = phi i32 [ 3, %entry ], [ %dec16, %for.inc13.3 ]
  18 ; CHECK-NEXT:    --> {3,+,-1}<nsw><%outer.loop> U: [1,4) S: [1,4) Exits: <<Unknown>> LoopDispositions: { %outer.loop: Computable, %for.cond6: Invariant, %inner.loop: Invariant }
  19 ; CHECK-NEXT:    %storemerge1921 = phi i32 [ 3, %outer.loop ], [ %dec, %for.end ]
  20 ; CHECK-NEXT:    --> {3,+,-1}<nsw><%for.cond6> U: [3,4) S: [3,4) Exits: <<Unknown>> LoopDispositions: { %for.cond6: Computable, %outer.loop: Variant }
  21 ; CHECK-NEXT:    %idxprom20 = zext i32 %storemerge1921 to i64
  22 ; CHECK-NEXT:    --> (zext i32 {3,+,-1}<nsw><%for.cond6> to i64) U: [3,4) S: [3,4) Exits: <<Unknown>> LoopDispositions: { %for.cond6: Computable, %outer.loop: Variant }
  23 ; CHECK-NEXT:    %arrayidx7 = getelementptr inbounds [1 x [4 x i16]], ptr @__const.f.g, i64 0, i64 0, i64 %idxprom20
  24 ; CHECK-NEXT:    --> ((2 * (zext i32 {3,+,-1}<nsw><%for.cond6> to i64))<nuw><nsw> + @__const.f.g)<nuw> U: [8,-3) S: [-9223372036854775808,9223372036854775807) Exits: <<Unknown>> LoopDispositions: { %for.cond6: Computable, %outer.loop: Variant }
  25 ; CHECK-NEXT:    %i = load i16, ptr %arrayidx7, align 2
  26 ; CHECK-NEXT:    --> %i U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %for.cond6: Variant, %outer.loop: Variant }
  27 ; CHECK-NEXT:    %storemerge1822.lcssa.ph = phi i32 [ 0, %for.cond6 ]
  28 ; CHECK-NEXT:    --> 0 U: [0,1) S: [0,1)
  29 ; CHECK-NEXT:    %storemerge1822.lcssa.ph32 = phi i32 [ 3, %inner.loop ]
  30 ; CHECK-NEXT:    --> 3 U: [3,4) S: [3,4)
  31 ; CHECK-NEXT:    %storemerge1822.lcssa = phi i32 [ %storemerge1822.lcssa.ph, %if.end.loopexit ], [ %storemerge1822.lcssa.ph32, %if.end.loopexit31 ]
  32 ; CHECK-NEXT:    --> %storemerge1822.lcssa U: [0,4) S: [0,4)
  33 ; CHECK-NEXT:    %i1 = load i32, ptr @e, align 4
  34 ; CHECK-NEXT:    --> %i1 U: full-set S: full-set
  35 ; CHECK-NEXT:    %i2 = load volatile i32, ptr @b, align 4
  36 ; CHECK-NEXT:    --> %i2 U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %for.cond6: Variant, %outer.loop: Variant }
  37 ; CHECK-NEXT:    %dec = add nsw i32 %storemerge1921, -1
  38 ; CHECK-NEXT:    --> {2,+,-1}<nsw><%for.cond6> U: [2,3) S: [2,3) Exits: <<Unknown>> LoopDispositions: { %for.cond6: Computable, %outer.loop: Variant }
  39 ; CHECK-NEXT:    %inc.lcssa.lcssa = phi i32 [ 4, %for.inc13.3 ]
  40 ; CHECK-NEXT:    --> 4 U: [4,5) S: [4,5)
  41 ; CHECK-NEXT:    %retval.0 = phi i32 [ %i1, %if.end ], [ 0, %cleanup.loopexit ]
  42 ; CHECK-NEXT:    --> %retval.0 U: full-set S: full-set
  43 ; CHECK-NEXT:    %storemerge1921.3 = phi i32 [ 3, %for.end ], [ %dec.3, %for.end.3 ]
  44 ; CHECK-NEXT:    --> {3,+,-1}<nsw><%inner.loop> U: [3,4) S: [3,4) Exits: <<Unknown>> LoopDispositions: { %inner.loop: Computable, %outer.loop: Variant }
  45 ; CHECK-NEXT:    %idxprom20.3 = zext i32 %storemerge1921.3 to i64
  46 ; CHECK-NEXT:    --> (zext i32 {3,+,-1}<nsw><%inner.loop> to i64) U: [3,4) S: [3,4) Exits: <<Unknown>> LoopDispositions: { %inner.loop: Computable, %outer.loop: Variant }
  47 ; CHECK-NEXT:    %arrayidx7.3 = getelementptr inbounds [1 x [4 x i16]], ptr @__const.f.g, i64 0, i64 0, i64 %idxprom20.3
  48 ; CHECK-NEXT:    --> ((2 * (zext i32 {3,+,-1}<nsw><%inner.loop> to i64))<nuw><nsw> + @__const.f.g)<nuw> U: [8,-3) S: [-9223372036854775808,9223372036854775807) Exits: <<Unknown>> LoopDispositions: { %inner.loop: Computable, %outer.loop: Variant }
  49 ; CHECK-NEXT:    %i7 = load i16, ptr %arrayidx7.3, align 2
  50 ; CHECK-NEXT:    --> %i7 U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %inner.loop: Variant, %outer.loop: Variant }
  51 ; CHECK-NEXT:    %i8 = load volatile i32, ptr @b, align 4
  52 ; CHECK-NEXT:    --> %i8 U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %inner.loop: Variant, %outer.loop: Variant }
  53 ; CHECK-NEXT:    %dec.3 = add nsw i32 %storemerge1921.3, -1
  54 ; CHECK-NEXT:    --> {2,+,-1}<nsw><%inner.loop> U: [2,3) S: [2,3) Exits: <<Unknown>> LoopDispositions: { %inner.loop: Computable, %outer.loop: Variant }
  55 ; CHECK-NEXT:    %storemerge1921.lcssa25.3 = phi i32 [ %storemerge1921.3, %for.end.3 ]
  56 ; CHECK-NEXT:    --> {3,+,-1}<nsw><%inner.loop> U: [3,4) S: [3,4) Exits: <<Unknown>> LoopDispositions: { %outer.loop: Variant, %for.cond6: Variant, %inner.loop: Computable }
  57 ; CHECK-NEXT:    %dec16 = add nsw i32 %storemerge23, -1
  58 ; CHECK-NEXT:    --> {2,+,-1}<nsw><%outer.loop> U: [0,3) S: [0,3) Exits: <<Unknown>> LoopDispositions: { %outer.loop: Computable, %for.cond6: Invariant, %inner.loop: Invariant }
  59 ; CHECK-NEXT:  Determining loop execution counts for: @f
  60 ; CHECK-NEXT:  Loop %for.cond6: <multiple exits> Unpredictable backedge-taken count.
  61 ; CHECK-NEXT:    exit count for for.cond6: i32 0
  62 ; CHECK-NEXT:    exit count for for.end: ***COULDNOTCOMPUTE***
  63 ; CHECK-NEXT:  Loop %for.cond6: constant max backedge-taken count is i32 0
  64 ; CHECK-NEXT:  Loop %for.cond6: symbolic max backedge-taken count is i32 0
  65 ; CHECK-NEXT:    symbolic max exit count for for.cond6: i32 0
  66 ; CHECK-NEXT:    symbolic max exit count for for.end: ***COULDNOTCOMPUTE***
  67 ; CHECK-NEXT:  Loop %inner.loop: <multiple exits> Unpredictable backedge-taken count.
  68 ; CHECK-NEXT:    exit count for inner.loop: i32 0
  69 ; CHECK-NEXT:    exit count for for.end.3: ***COULDNOTCOMPUTE***
  70 ; CHECK-NEXT:  Loop %inner.loop: constant max backedge-taken count is i32 0
  71 ; CHECK-NEXT:  Loop %inner.loop: symbolic max backedge-taken count is i32 0
  72 ; CHECK-NEXT:    symbolic max exit count for inner.loop: i32 0
  73 ; CHECK-NEXT:    symbolic max exit count for for.end.3: ***COULDNOTCOMPUTE***
  74 ; CHECK-NEXT:  Loop %outer.loop: <multiple exits> Unpredictable backedge-taken count.
  75 ; CHECK-NEXT:    exit count for for.cond6: ***COULDNOTCOMPUTE***
  76 ; CHECK-NEXT:    exit count for inner.loop: ***COULDNOTCOMPUTE***
  77 ; CHECK-NEXT:    exit count for for.inc13.3: i32 2
  78 ; CHECK-NEXT:  Loop %outer.loop: constant max backedge-taken count is i32 2
  79 ; CHECK-NEXT:  Loop %outer.loop: symbolic max backedge-taken count is i32 2
  80 ; CHECK-NEXT:    symbolic max exit count for for.cond6: ***COULDNOTCOMPUTE***
  81 ; CHECK-NEXT:    symbolic max exit count for inner.loop: ***COULDNOTCOMPUTE***
  82 ; CHECK-NEXT:    symbolic max exit count for for.inc13.3: i32 2
  83 ;
  84 entry:
  85   store i32 3, ptr @a, align 4
  86   br label %outer.loop
  87
  88 outer.loop:                              ; preds = %for.inc13.3, %entry
  89   %storemerge23 = phi i32 [ 3, %entry ], [ %dec16, %for.inc13.3 ]
  90   br label %for.cond6
  91
  92 for.cond6:                                        ; preds = %for.end, %outer.loop
  93   %storemerge1921 = phi i32 [ 3, %outer.loop ], [ %dec, %for.end ]
  94   %idxprom20 = zext i32 %storemerge1921 to i64
  95   %arrayidx7 = getelementptr inbounds [1 x [4 x i16]], ptr @__const.f.g, i64 0, i64 0, i64 %idxprom20
  96   %i = load i16, ptr %arrayidx7, align 2
  97   %tobool8 = icmp eq i16 %i, 0
  98   br i1 %tobool8, label %if.end.loopexit, label %for.end
  99
 100 if.end.loopexit:                                  ; preds = %for.cond6
 101   %storemerge1822.lcssa.ph = phi i32 [ 0, %for.cond6 ]
 102   br label %if.end
 103
 104 if.end.loopexit31:                                ; preds = %inner.loop
 105   %storemerge1822.lcssa.ph32 = phi i32 [ 3, %inner.loop ]
 106   br label %if.end
 107
 108 if.end:                                           ; preds = %if.end.loopexit31, %if.end.loopexit
 109   %storemerge1822.lcssa = phi i32 [ %storemerge1822.lcssa.ph, %if.end.loopexit ], [ %storemerge1822.lcssa.ph32, %if.end.loopexit31 ]
 110   store i32 %storemerge1822.lcssa, ptr @c, align 4
 111   store i32 2, ptr @d, align 4
 112   %i1 = load i32, ptr @e, align 4
 113   br label %cleanup
 114
 115 for.end:                                          ; preds = %for.cond6
 116   %i2 = load volatile i32, ptr @b, align 4
 117   %tobool9 = icmp eq i32 %i2, 0
 118   %dec = add nsw i32 %storemerge1921, -1
 119   br i1 %tobool9, label %for.cond6, label %inner.loop
 120
 121 cleanup.loopexit:                                 ; preds = %for.inc13.3
 122   %inc.lcssa.lcssa = phi i32 [ 4, %for.inc13.3 ]
 123   store i32 %inc.lcssa.lcssa, ptr @c, align 4
 124   br label %cleanup
 125
 126 cleanup:                                          ; preds = %cleanup.loopexit, %if.end
 127   %retval.0 = phi i32 [ %i1, %if.end ], [ 0, %cleanup.loopexit ]
 128   ret i32 %retval.0
 129
 130 inner.loop:                                      ; preds = %for.end.3, %for.end
 131   %storemerge1921.3 = phi i32 [ 3, %for.end ], [ %dec.3, %for.end.3 ]
 132   %idxprom20.3 = zext i32 %storemerge1921.3 to i64
 133   %arrayidx7.3 = getelementptr inbounds [1 x [4 x i16]], ptr @__const.f.g, i64 0, i64 0, i64 %idxprom20.3
 134   %i7 = load i16, ptr %arrayidx7.3, align 2
 135   %tobool8.3 = icmp eq i16 %i7, 0
 136   br i1 %tobool8.3, label %if.end.loopexit31, label %for.end.3
 137
 138 for.end.3:                                        ; preds = %inner.loop
 139   %i8 = load volatile i32, ptr @b, align 4
 140   %tobool9.3 = icmp eq i32 %i8, 0
 141   %dec.3 = add nsw i32 %storemerge1921.3, -1
 142   br i1 %tobool9.3, label %inner.loop, label %for.inc13.3
 143
 144 for.inc13.3:                                      ; preds = %for.end.3
 145   %storemerge1921.lcssa25.3 = phi i32 [ %storemerge1921.3, %for.end.3 ]
 146   store i32 %storemerge1921.lcssa25.3, ptr @d, align 4
 147   %dec16 = add nsw i32 %storemerge23, -1
 148   store i32 %dec16, ptr @a, align 4
 149   %tobool = icmp eq i32 %dec16, 0
 150   br i1 %tobool, label %cleanup.loopexit, label %outer.loop
 151 }