llvm/test/Analysis/LoopAccessAnalysis/memcheck-wrapping-pointers.ll

   1 ; RUN: opt -basic-aa -loop-accesses -analyze -enable-new-pm=0 < %s | FileCheck %s
   2 ; RUN: opt -passes=print-access-info %s -disable-output 2>&1 | FileCheck %s
   3
   4 target datalayout = "e-m:e-i8:8:32-i16:16:32-i64:64-i128:128-n32:64-S128"
   5
   6 ; i and i + 1 can overflow in the following kernel:
   7 ; void test1(unsigned long long x, int *a, int *b) {
   8 ;  for (unsigned i = 0; i < x; ++i)
   9 ;    b[i] = a[i+1] + 1;
  10 ; }
  11 ;
  12 ; If accesses to a and b can alias, we need to emit a run-time alias check
  13 ; between accesses to a and b. However, when i and i + 1 can wrap, their
  14 ; SCEV expression is not an AddRec. We need to create SCEV predicates and
  15 ; coerce the expressions to AddRecs in order to be able to emit the run-time
  16 ; alias check.
  17 ;
  18 ; The accesses at b[i] and a[i+1] correspond to the addresses %arrayidx and
  19 ; %arrayidx4 in the test. The SCEV expressions for these are:
  20 ;  ((4 * (zext i32 {1,+,1}<%for.body> to i64))<nuw><nsw> + %a)<nsw>
  21 ;  ((4 * (zext i32 {0,+,1}<%for.body> to i64))<nuw><nsw> + %b)<nsw>
  22 ;
  23 ; The transformed expressions are:
  24 ;  i64 {(4 + %a),+,4}<%for.body>
  25 ;  i64 {(4 + %b),+,4}<%for.body>
  26
  27 ; CHECK-LABEL: test1
  28 ; CHECK:         Memory dependences are safe with run-time checks
  29 ; CHECK-NEXT:    Dependences:
  30 ; CHECK-NEXT:    Run-time memory checks:
  31 ; CHECK-NEXT:    Check 0:
  32 ; CHECK-NEXT:      Comparing group
  33 ; CHECK-NEXT:        %arrayidx = getelementptr inbounds i32, i32* %a, i64 %idxprom
  34 ; CHECK-NEXT:      Against group
  35 ; CHECK-NEXT:        %arrayidx4 = getelementptr inbounds i32, i32* %b, i64 %conv11
  36 ; CHECK-NEXT:    Grouped accesses:
  37 ; CHECK-NEXT:      Group
  38 ; CHECK-NEXT:        (Low: (4 + %a) High: (4 + (4 * (1 umax %x)) + %a))
  39 ; CHECK-NEXT:          Member: {(4 + %a),+,4}<%for.body>
  40 ; CHECK-NEXT:      Group
  41 ; CHECK-NEXT:        (Low: %b High: ((4 * (1 umax %x)) + %b))
  42 ; CHECK-NEXT:          Member: {%b,+,4}<%for.body>
  43 ; CHECK:         Non vectorizable stores to invariant address were not found in loop.
  44 ; CHECK-NEXT:    SCEV assumptions:
  45 ; CHECK-NEXT:    {1,+,1}<%for.body> Added Flags: <nusw>
  46 ; CHECK-NEXT:    {0,+,1}<%for.body> Added Flags: <nusw>
  47 ; CHECK:         Expressions re-written:
  48 ; CHECK-NEXT:    [PSE]  %arrayidx = getelementptr inbounds i32, i32* %a, i64 %idxprom:
  49 ; CHECK-NEXT:      ((4 * (zext i32 {1,+,1}<%for.body> to i64))<nuw><nsw> + %a)<nuw>
  50 ; CHECK-NEXT:      --> {(4 + %a),+,4}<%for.body>
  51 ; CHECK-NEXT:    [PSE]  %arrayidx4 = getelementptr inbounds i32, i32* %b, i64 %conv11:
  52 ; CHECK-NEXT:      ((4 * (zext i32 {0,+,1}<%for.body> to i64))<nuw><nsw> + %b)<nuw>
  53 ; CHECK-NEXT:      --> {%b,+,4}<%for.body>
  54 define void @test1(i64 %x, i32* %a, i32* %b) {
  55 entry:
  56   br label %for.body
  57
  58 for.body:                                         ; preds = %for.body.preheader, %for.body
  59   %conv11 = phi i64 [ %conv, %for.body ], [ 0, %entry ]
  60   %i.010 = phi i32 [ %add, %for.body ], [ 0, %entry ]
  61   %add = add i32 %i.010, 1
  62   %idxprom = zext i32 %add to i64
  63   %arrayidx = getelementptr inbounds i32, i32* %a, i64 %idxprom
  64   %ld = load i32, i32* %arrayidx, align 4
  65   %add2 = add nsw i32 %ld, 1
  66   %arrayidx4 = getelementptr inbounds i32, i32* %b, i64 %conv11
  67   store i32 %add2, i32* %arrayidx4, align 4
  68   %conv = zext i32 %add to i64
  69   %cmp = icmp ult i64 %conv, %x
  70   br i1 %cmp, label %for.body, label %exit
  71
  72 exit:
  73   ret void
  74 }
  75
  76 ; i can overflow in the following kernel:
  77 ; void test2(unsigned long long x, int *a) {
  78 ;   for (unsigned i = 0; i < x; ++i)
  79 ;     a[i] = a[i] + 1;
  80 ; }
  81 ;
  82 ; We need to check that i doesn't wrap, but we don't need a run-time alias
  83 ; check. We also need an extra no-wrap check to get the backedge taken count.
  84
  85 ; CHECK-LABEL: test2
  86 ; CHECK: Memory dependences are safe
  87 ; CHECK: SCEV assumptions:
  88 ; CHECK-NEXT:   {1,+,1}<%for.body> Added Flags: <nusw>
  89 ; CHECK-NEXT:   {0,+,1}<%for.body> Added Flags: <nusw>
  90  define void @test2(i64 %x, i32* %a) {
  91 entry:
  92   br label %for.body
  93
  94 for.body:
  95   %conv11 = phi i64 [ %conv, %for.body ], [ 0, %entry ]
  96   %i.010 = phi i32 [ %inc, %for.body ], [ 0, %entry ]
  97   %arrayidx = getelementptr inbounds i32, i32* %a, i64 %conv11
  98   %ld = load i32, i32* %arrayidx, align 4
  99   %add = add nsw i32 %ld, 1
 100   store i32 %add, i32* %arrayidx, align 4
 101   %inc = add i32 %i.010, 1
 102   %conv = zext i32 %inc to i64
 103   %cmp = icmp ult i64 %conv, %x
 104   br i1 %cmp, label %for.body, label %exit
 105
 106 exit:
 107   ret void
 108 }