test/Transforms/LoopVectorize/skip-iterations.ll

   1 ; RUN: opt < %s  -loop-vectorize -force-vector-width=4 -dce -instcombine -S | FileCheck %s
   2
   3 target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128"
   4
   5 ; tests skipping iterations within a VF through break/continue/gotos.
   6
   7 ; The main difficulty in vectorizing these loops in test1,test2 and test3 is
   8 ; safely speculating that the widened load of A[i] should not fault if the
   9 ; scalarized loop does not fault. For example, the
  10 ; original load in the scalar loop may not fault, but the last iteration of the
  11 ; vectorized load can fault (if it crosses a page boudary for example).
  12 ; This last vector iteration is where *one* of the
  13 ; scalar iterations lead to the early exit.
  14
  15 ; int test(int *A, int Length) {
  16 ;   for (int i = 0; i < Length; i++) {
  17 ;     if (A[i] > 10.0) goto end;
  18 ;     A[i] = 0;
  19 ;   }
  20 ; end:
  21 ;   return 0;
  22 ; }
  23 ; CHECK-LABEL: test1(
  24 ; CHECK-NOT: <4 x i32>
  25 define i32 @test1(i32* nocapture %A, i32 %Length) {
  26 entry:
  27   %cmp8 = icmp sgt i32 %Length, 0
  28   br i1 %cmp8, label %for.body.preheader, label %end
  29
  30 for.body.preheader:                               ; preds = %entry
  31   br label %for.body
  32
  33 for.body:                                         ; preds = %for.body.preheader, %if.else
  34   %indvars.iv = phi i64 [ %indvars.iv.next, %if.else ], [ 0, %for.body.preheader ]
  35   %arrayidx = getelementptr inbounds i32, i32* %A, i64 %indvars.iv
  36   %0 = load i32, i32* %arrayidx, align 4, !tbaa !15
  37   %cmp1 = icmp sgt i32 %0, 10
  38   br i1 %cmp1, label %end.loopexit, label %if.else
  39
  40 if.else:                                          ; preds = %for.body
  41   store i32 0, i32* %arrayidx, align 4, !tbaa !15
  42   %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
  43   %1 = trunc i64 %indvars.iv.next to i32
  44   %cmp = icmp slt i32 %1, %Length
  45   br i1 %cmp, label %for.body, label %end.loopexit
  46
  47 end.loopexit:                                     ; preds = %if.else, %for.body
  48   br label %end
  49
  50 end:                                              ; preds = %end.loopexit, %entry
  51   ret i32 0
  52 }
  53
  54 ; We don't use anything from within the loop at the early exit path
  55 ; so we do not need to know which iteration caused the early exit path.
  56 ; bool test2(int *A, int Length, int K) {
  57 ;   for (int i = 0; i < Length; i++) {
  58 ;     if (A[i] == K) return true;
  59 ;   }
  60 ;   return false;
  61 ; }
  62 ; TODO: Today we do not vectorize this, but we could teach the vectorizer, once
  63 ; the hard part of proving/speculating A[i:VF - 1] loads does not fault is handled by the
  64 ; compiler/hardware.
  65
  66 ; CHECK-LABEL: test2(
  67 ; CHECK-NOT: <4 x i32>
  68 define i32 @test2(i32* nocapture %A, i32 %Length, i32 %K) {
  69 entry:
  70   %cmp8 = icmp sgt i32 %Length, 0
  71   br i1 %cmp8, label %for.body.preheader, label %end
  72
  73 for.body.preheader:                               ; preds = %entry
  74   br label %for.body
  75
  76 for.body:                                         ; preds = %for.body.preheader, %if.else
  77   %indvars.iv = phi i64 [ %indvars.iv.next, %if.else ], [ 0, %for.body.preheader ]
  78   %arrayidx = getelementptr inbounds i32, i32* %A, i64 %indvars.iv
  79   %ld = load i32, i32* %arrayidx, align 4
  80   %cmp1 = icmp eq i32 %ld, %K
  81   br i1 %cmp1, label %end.loopexit, label %if.else
  82
  83 if.else:                                          ; preds = %for.body
  84   %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
  85   %trunc = trunc i64 %indvars.iv.next to i32
  86   %cmp = icmp slt i32 %trunc, %Length
  87   br i1 %cmp, label %for.body, label %end.loopexit
  88
  89 end.loopexit:                                     ; preds = %if.else, %for.body
  90   %result.lcssa = phi i32 [ 1, %for.body ], [ 0, %if.else ]
  91   br label %end
  92
  93 end:                                              ; preds = %end.loopexit, %entry
  94   %result = phi i32 [ %result.lcssa, %end.loopexit ], [ 0, %entry ]
  95   ret i32 %result
  96 }
  97
  98 ; We use the IV in the early exit
  99 ; so we need to know which iteration caused the early exit path.
 100 ; int test3(int *A, int Length, int K) {
 101 ;   for (int i = 0; i < Length; i++) {
 102 ;     if (A[i] == K) return i;
 103 ;   }
 104 ;   return -1;
 105 ; }
 106 ; TODO: Today we do not vectorize this, but we could teach the vectorizer (once
 107 ; we handle the speculation safety of the widened load).
 108 ; CHECK-LABEL: test3(
 109 ; CHECK-NOT: <4 x i32>
 110 define i32 @test3(i32* nocapture %A, i32 %Length, i32 %K) {
 111 entry:
 112   %cmp8 = icmp sgt i32 %Length, 0
 113   br i1 %cmp8, label %for.body.preheader, label %end
 114
 115 for.body.preheader:                               ; preds = %entry
 116   br label %for.body
 117
 118 for.body:                                         ; preds = %for.body.preheader, %if.else
 119   %indvars.iv = phi i64 [ %indvars.iv.next, %if.else ], [ 0, %for.body.preheader ]
 120   %arrayidx = getelementptr inbounds i32, i32* %A, i64 %indvars.iv
 121   %ld = load i32, i32* %arrayidx, align 4
 122   %cmp1 = icmp eq i32 %ld, %K
 123   br i1 %cmp1, label %end.loopexit, label %if.else
 124
 125 if.else:                                          ; preds = %for.body
 126   %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
 127   %trunc = trunc i64 %indvars.iv.next to i32
 128   %cmp = icmp slt i32 %trunc, %Length
 129   br i1 %cmp, label %for.body, label %end.loopexit
 130
 131 end.loopexit:                                     ; preds = %if.else, %for.body
 132   %result.lcssa = phi i64 [ %indvars.iv, %for.body ], [ -1, %if.else ]
 133   %res.trunc = trunc i64 %result.lcssa to i32
 134   br label %end
 135
 136 end:                                              ; preds = %end.loopexit, %entry
 137   %result = phi i32 [ %res.trunc, %end.loopexit ], [ -1, %entry ]
 138   ret i32 %result
 139 }
 140
 141 ; bool test4(int *A, int Length, int K, int J) {
 142 ;   for (int i = 0; i < Length; i++) {
 143 ;     if (A[i] == K) continue;
 144 ;     A[i] = J;
 145 ;   }
 146 ; }
 147 ; For this test, we vectorize and generate predicated stores to A[i].
 148 ; CHECK-LABEL: test4(
 149 ; CHECK: <4 x i32>
 150 define void @test4(i32* nocapture %A, i32 %Length, i32 %K, i32 %J) {
 151 entry:
 152   %cmp8 = icmp sgt i32 %Length, 0
 153   br i1 %cmp8, label %for.body.preheader, label %end.loopexit
 154
 155 for.body.preheader:                               ; preds = %entry
 156   br label %for.body
 157
 158 for.body:                                         ; preds = %for.body.preheader, %if.else
 159   %indvars.iv = phi i64 [ %indvars.iv.next, %latch ], [ 0, %for.body.preheader ]
 160   %arrayidx = getelementptr inbounds i32, i32* %A, i64 %indvars.iv
 161   %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
 162   %trunc = trunc i64 %indvars.iv.next to i32
 163   %ld = load i32, i32* %arrayidx, align 4
 164   %cmp1 = icmp eq i32 %ld, %K
 165   br i1 %cmp1, label %latch, label %if.else
 166
 167 if.else:
 168   store i32 %J, i32* %arrayidx, align 4
 169   br label %latch
 170
 171 latch:                                          ; preds = %for.body
 172   %cmp = icmp slt i32 %trunc, %Length
 173   br i1 %cmp, label %for.body, label %end.loopexit
 174
 175 end.loopexit:                                     ; preds = %if.else, %for.body
 176   ret void
 177 }
 178 !15 = !{!16, !16, i64 0}
 179 !16 = !{!"int", !17, i64 0}
 180 !17 = !{!"omnipotent char", !18, i64 0}
 181 !18 = !{!"Simple C/C++ TBAA"}