test/Analysis/ScalarEvolution/trip-count10.ll

   1 ; RUN: opt < %s -analyze -scalar-evolution | FileCheck %s
   2
   3 ; Trip counts with trivial exit conditions.
   4
   5 ; CHECK: Determining loop execution counts for: @a
   6 ; CHECK: Loop %loop: Unpredictable backedge-taken count.
   7 ; CHECK: Loop %loop: Unpredictable max backedge-taken count.
   8
   9 ; CHECK: Determining loop execution counts for: @b
  10 ; CHECK: Loop %loop: backedge-taken count is false
  11 ; CHECK: Loop %loop: max backedge-taken count is false
  12
  13 ; CHECK: Determining loop execution counts for: @c
  14 ; CHECK: Loop %loop: backedge-taken count is false
  15 ; CHECK: Loop %loop: max backedge-taken count is false
  16
  17 ; CHECK: Determining loop execution counts for: @d
  18 ; CHECK: Loop %loop: Unpredictable backedge-taken count.
  19 ; CHECK: Loop %loop: Unpredictable max backedge-taken count.
  20
  21 define void @a(i64 %n) nounwind {
  22 entry:
  23   %t0 = icmp sgt i64 %n, 0
  24   br i1 %t0, label %loop, label %return
  25
  26 loop:
  27   %i = phi i64 [ %i.next, %loop ], [ 0, %entry ]
  28   %i.next = add nsw i64 %i, 1
  29   %exitcond = icmp eq i64 %i.next, %n
  30   br i1 false, label %return, label %loop
  31
  32 return:
  33   ret void
  34 }
  35 define void @b(i64 %n) nounwind {
  36 entry:
  37   %t0 = icmp sgt i64 %n, 0
  38   br i1 %t0, label %loop, label %return
  39
  40 loop:
  41   %i = phi i64 [ %i.next, %loop ], [ 0, %entry ]
  42   %i.next = add nsw i64 %i, 1
  43   %exitcond = icmp eq i64 %i.next, %n
  44   br i1 true, label %return, label %loop
  45
  46 return:
  47   ret void
  48 }
  49 define void @c(i64 %n) nounwind {
  50 entry:
  51   %t0 = icmp sgt i64 %n, 0
  52   br i1 %t0, label %loop, label %return
  53
  54 loop:
  55   %i = phi i64 [ %i.next, %loop ], [ 0, %entry ]
  56   %i.next = add nsw i64 %i, 1
  57   %exitcond = icmp eq i64 %i.next, %n
  58   br i1 false, label %loop, label %return
  59
  60 return:
  61   ret void
  62 }
  63 define void @d(i64 %n) nounwind {
  64 entry:
  65   %t0 = icmp sgt i64 %n, 0
  66   br i1 %t0, label %loop, label %return
  67
  68 loop:
  69   %i = phi i64 [ %i.next, %loop ], [ 0, %entry ]
  70   %i.next = add nsw i64 %i, 1
  71   %exitcond = icmp eq i64 %i.next, %n
  72   br i1 true, label %loop, label %return
  73
  74 return:
  75   ret void
  76 }
  77
  78 ; Trip counts for non-polynomial iterations. It's theoretically possible
  79 ; to compute a maximum count for these, but short of that, ScalarEvolution
  80 ; should return unknown.
  81
  82 ; PR7416
  83 ; CHECK: Determining loop execution counts for: @nonpolynomial
  84 ; CHECK-NEXT: Loop %loophead: Unpredictable backedge-taken count
  85 ; CHECK-NEXT: Loop %loophead: Unpredictable max backedge-taken count
  86
  87 declare i1 @g() nounwind
  88
  89 define void @nonpolynomial() {
  90 entry:
  91   br label %loophead
  92 loophead:
  93   %x = phi i32 [0, %entry], [%x.1, %bb1], [%x.2, %bb2]
  94   %y = icmp slt i32 %x, 100
  95   br i1 %y, label %loopbody, label %retbb
  96 loopbody:
  97   %z = call i1 @g()
  98   br i1 %z, label %bb1, label %bb2
  99 bb1:
 100   %x.1 = add i32 %x, 2
 101   br label %loophead
 102 bb2:
 103   %x.2 = add i32 %x, 3
 104   br label %loophead
 105 retbb:
 106   ret void
 107 }
 108
 109 ; PHI nodes with all constant operands.
 110
 111 ; CHECK: Determining loop execution counts for: @constant_phi_operands
 112 ; CHECK: Loop %loop: backedge-taken count is 1
 113 ; CHECK: Loop %loop: max backedge-taken count is 1
 114
 115 define void @constant_phi_operands() nounwind {
 116 entry:
 117   br label %loop
 118
 119 loop:
 120   %i = phi i64 [ 1, %loop ], [ 0, %entry ]
 121   %exitcond = icmp eq i64 %i, 1
 122   br i1 %exitcond, label %return, label %loop
 123
 124 return:
 125   ret void
 126 }
 127
 128 ; PR16130: Loop exit depends on an 'or' expression.
 129 ; One side of the expression test against a value that will be skipped.
 130 ; We can't assume undefined behavior just because we have an NSW flag.
 131 ;
 132 ; CHECK: Determining loop execution counts for: @exit_orcond_nsw
 133 ; CHECK: Loop %for.body.i: Unpredictable backedge-taken count.
 134 ; CHECK: Loop %for.body.i: max backedge-taken count is 1
 135 define void @exit_orcond_nsw(i32 *%a) nounwind {
 136 entry:
 137   br label %for.body.i
 138
 139 for.body.i:                                       ; preds = %for.body.i, %entry
 140   %b.01.i = phi i32 [ 0, %entry ], [ %add.i, %for.body.i ]
 141   %tobool.i = icmp ne i32 %b.01.i, 0
 142   %add.i = add nsw i32 %b.01.i, 8
 143   %cmp.i = icmp eq i32 %add.i, 13
 144   %or.cond = or i1 %tobool.i, %cmp.i
 145   br i1 %or.cond, label %exit, label %for.body.i
 146
 147 exit:                                     ; preds = %for.body.i
 148   %b.01.i.lcssa = phi i32 [ %b.01.i, %for.body.i ]
 149   store i32 %b.01.i.lcssa, i32* %a, align 4
 150   ret void
 151 }