test/Analysis/LoopDependenceAnalysis/siv-weak-crossing.ll

   1 ; RUN: opt < %s -analyze -lda | FileCheck %s
   2
   3 @x = common global [256 x i32] zeroinitializer, align 4
   4 @y = common global [256 x i32] zeroinitializer, align 4
   5
   6 ;; for (i = 0; i < 256; i++)
   7 ;;   x[i] = x[255 - i] + y[i]
   8
   9 define void @f1(...) nounwind {
  10 entry:
  11   br label %for.body
  12
  13 for.body:
  14   %i = phi i64 [ 0, %entry ], [ %i.next, %for.body ]
  15   %i.255 = sub i64 255, %i
  16   %y.ld.addr = getelementptr [256 x i32]* @y, i64 0, i64 %i
  17   %x.ld.addr = getelementptr [256 x i32]* @x, i64 0, i64 %i.255
  18   %x.st.addr = getelementptr [256 x i32]* @x, i64 0, i64 %i
  19   %x = load i32* %x.ld.addr     ; 0
  20   %y = load i32* %y.ld.addr     ; 1
  21   %r = add i32 %y, %x
  22   store i32 %r, i32* %x.st.addr ; 2
  23 ; CHECK: 0,2: dep
  24 ; CHECK: 1,2: ind
  25   %i.next = add i64 %i, 1
  26   %exitcond = icmp eq i64 %i.next, 256
  27   br i1 %exitcond, label %for.end, label %for.body
  28
  29 for.end:
  30   ret void
  31 }
  32
  33 ;; for (i = 0; i < 100; i++)
  34 ;;   x[i] = x[255 - i] + y[i]
  35
  36 define void @f2(...) nounwind {
  37 entry:
  38   br label %for.body
  39
  40 for.body:
  41   %i = phi i64 [ 0, %entry ], [ %i.next, %for.body ]
  42   %i.255 = sub i64 255, %i
  43   %y.ld.addr = getelementptr [256 x i32]* @y, i64 0, i64 %i
  44   %x.ld.addr = getelementptr [256 x i32]* @x, i64 0, i64 %i.255
  45   %x.st.addr = getelementptr [256 x i32]* @x, i64 0, i64 %i
  46   %x = load i32* %x.ld.addr     ; 0
  47   %y = load i32* %y.ld.addr     ; 1
  48   %r = add i32 %y, %x
  49   store i32 %r, i32* %x.st.addr ; 2
  50 ; CHECK: 0,2: dep
  51 ; CHECK: 1,2: ind
  52   %i.next = add i64 %i, 1
  53   %exitcond = icmp eq i64 %i.next, 100
  54   br i1 %exitcond, label %for.end, label %for.body
  55
  56 for.end:
  57   ret void
  58 }
  59
  60 ;; // the first iteration (i=0) leads to an out-of-bounds access of x. as the
  61 ;; // result of this access is undefined, _any_ dependence result is safe.
  62 ;; for (i = 0; i < 256; i++)
  63 ;;   x[i] = x[256 - i] + y[i]
  64
  65 define void @f3(...) nounwind {
  66 entry:
  67   br label %for.body
  68
  69 for.body:
  70   %i = phi i64 [ 0, %entry ], [ %i.next, %for.body ]
  71   %i.256 = sub i64 0, %i
  72   %y.ld.addr = getelementptr [256 x i32]* @y, i64 0, i64 %i
  73   %x.ld.addr = getelementptr [256 x i32]* @x, i64 1, i64 %i.256
  74   %x.st.addr = getelementptr [256 x i32]* @x, i64 0, i64 %i
  75   %x = load i32* %x.ld.addr     ; 0
  76   %y = load i32* %y.ld.addr     ; 1
  77   %r = add i32 %y, %x
  78   store i32 %r, i32* %x.st.addr ; 2
  79 ; CHECK: 0,2: dep
  80 ; CHECK: 1,2:
  81   %i.next = add i64 %i, 1
  82   %exitcond = icmp eq i64 %i.next, 256
  83   br i1 %exitcond, label %for.end, label %for.body
  84
  85 for.end:
  86   ret void
  87 }
  88
  89 ;; // slightly contrived but valid IR for the following loop, where all
  90 ;; // accesses in all iterations are within bounds. while this example's first
  91 ;; // (ZIV-)subscript is (0, 1), accesses are dependent.
  92 ;; for (i = 1; i < 256; i++)
  93 ;;   x[i] = x[256 - i] + y[i]
  94
  95 define void @f4(...) nounwind {
  96 entry:
  97   br label %for.body
  98
  99 for.body:
 100   %i = phi i64 [ 0, %entry ], [ %i.next, %for.body ]
 101   %i.1 = add i64 1, %i
 102   %i.256 = sub i64 -1, %i
 103   %y.ld.addr = getelementptr [256 x i32]* @y, i64 0, i64 %i.1
 104   %x.ld.addr = getelementptr [256 x i32]* @x, i64 1, i64 %i.256
 105   %x.st.addr = getelementptr [256 x i32]* @x, i64 0, i64 %i.1
 106   %x = load i32* %x.ld.addr     ; 0
 107   %y = load i32* %y.ld.addr     ; 1
 108   %r = add i32 %y, %x
 109   store i32 %r, i32* %x.st.addr ; 2
 110 ; CHECK: 0,2: dep
 111 ; CHECK: 1,2: ind
 112   %i.next = add i64 %i, 1
 113   %exitcond = icmp eq i64 %i.next, 256
 114   br i1 %exitcond, label %for.end, label %for.body
 115
 116 for.end:
 117   ret void
 118 }