test/Analysis/DDG/basic-b.ll

   1 ; RUN: opt < %s -disable-output "-passes=print<ddg>" 2>&1 | FileCheck %s
   2
   3 ; CHECK-LABEL: 'DDG' for loop 'test1.for.body':
   4 ; CHECK: Node Address:[[N1:0x[0-9a-f]*]]:single-instruction
   5 ; CHECK-NEXT: Instructions:
   6 ; CHECK-NEXT:    %i.02 = phi i64 [ %inc, %test1.for.body ], [ 1, %test1.for.body.preheader ]
   7 ; CHECK-NEXT: Edges:
   8 ; CHECK-NEXT:  [def-use] to [[N2:0x[0-9a-f]*]]
   9 ; CHECK-NEXT:  [def-use] to [[N3:0x[0-9a-f]*]]
  10 ; CHECK-NEXT:  [def-use] to [[N4:0x[0-9a-f]*]]
  11 ; CHECK-NEXT:  [def-use] to [[N5:0x[0-9a-f]*]]
  12
  13 ; CHECK: Node Address:[[N5]]:single-instruction
  14 ; CHECK-NEXT: Instructions:
  15 ; CHECK-NEXT:    %arrayidx = getelementptr inbounds float, float* %b, i64 %i.02
  16 ; CHECK-NEXT: Edges:
  17 ; CHECK-NEXT:  [def-use] to [[N6:0x[0-9a-f]*]]
  18
  19 ; CHECK: Node Address:[[N6]]:single-instruction
  20 ; CHECK-NEXT: Instructions:
  21 ; CHECK-NEXT:    %0 = load float, float* %arrayidx, align 4
  22 ; CHECK-NEXT: Edges:
  23 ; CHECK-NEXT:  [def-use] to [[N7:0x[0-9a-f]*]]
  24
  25 ; CHECK: Node Address:[[N4]]:single-instruction
  26 ; CHECK-NEXT: Instructions:
  27 ; CHECK-NEXT:    %sub1 = add i64 %i.02, -1
  28 ; CHECK-NEXT: Edges:
  29 ; CHECK-NEXT:  [def-use] to [[N8:0x[0-9a-f]*]]
  30
  31 ; CHECK: Node Address:[[N8]]:single-instruction
  32 ; CHECK-NEXT: Instructions:
  33 ; CHECK-NEXT:    %arrayidx2 = getelementptr inbounds float, float* %a, i64 %sub1
  34 ; CHECK-NEXT: Edges:
  35 ; CHECK-NEXT:  [def-use] to [[N9:0x[0-9a-f]*]]
  36
  37 ; CHECK: Node Address:[[N9]]:single-instruction
  38 ; CHECK-NEXT: Instructions:
  39 ; CHECK-NEXT:    %1 = load float, float* %arrayidx2, align 4
  40 ; CHECK-NEXT: Edges:
  41 ; CHECK-NEXT:  [def-use] to [[N7]]
  42
  43 ; CHECK: Node Address:[[N7]]:single-instruction
  44 ; CHECK-NEXT: Instructions:
  45 ; CHECK-NEXT:    %add = fadd float %0, %1
  46 ; CHECK-NEXT: Edges:
  47 ; CHECK-NEXT:  [def-use] to [[N10:0x[0-9a-f]*]]
  48
  49 ; CHECK: Node Address:[[N3]]:single-instruction
  50 ; CHECK-NEXT: Instructions:
  51 ; CHECK-NEXT:    %arrayidx3 = getelementptr inbounds float, float* %a, i64 %i.02
  52 ; CHECK-NEXT: Edges:
  53 ; CHECK-NEXT:  [def-use] to [[N10]]
  54
  55 ; CHECK: Node Address:[[N10]]:single-instruction
  56 ; CHECK-NEXT: Instructions:
  57 ; CHECK-NEXT:    store float %add, float* %arrayidx3, align 4
  58 ; CHECK-NEXT: Edges:
  59 ; CHECK-NEXT:  [memory] to [[N9]]
  60
  61 ; CHECK: Node Address:[[N2]]:single-instruction
  62 ; CHECK-NEXT: Instructions:
  63 ; CHECK-NEXT:    %inc = add i64 %i.02, 1
  64 ; CHECK-NEXT: Edges:
  65 ; CHECK-NEXT:  [def-use] to [[N11:0x[0-9a-f]*]]
  66 ; CHECK-NEXT:  [def-use] to [[N1]]
  67
  68 ; CHECK: Node Address:[[N11]]:single-instruction
  69 ; CHECK-NEXT: Instructions:
  70 ; CHECK-NEXT:    %cmp = icmp ult i64 %inc, %sub
  71 ; CHECK-NEXT: Edges:
  72 ; CHECK-NEXT:  [def-use] to [[N12:0x[0-9a-f]*]]
  73
  74 ; CHECK: Node Address:[[N12]]:single-instruction
  75 ; CHECK-NEXT: Instructions:
  76 ; CHECK-NEXT:    br i1 %cmp, label %test1.for.body, label %for.end.loopexit
  77 ; CHECK-NEXT: Edges:none!
  78
  79 ;; Loop-carried dependence requiring edge-reversal to expose a cycle
  80 ;; in the graph.
  81 ;; void test(unsigned long n, float * restrict a, float * restrict b) {
  82 ;;  for (unsigned long i = 1; i < n-1; i++)
  83 ;;    a[i] = b[i] + a[i-1];
  84 ;; }
  85
  86 define void @test1(i64 %n, float* noalias %a, float* noalias %b) {
  87 entry:
  88   %sub = add i64 %n, -1
  89   %cmp1 = icmp ult i64 1, %sub
  90   br i1 %cmp1, label %test1.for.body, label %for.end
  91
  92 test1.for.body:                                         ; preds = %entry, %test1.for.body
  93   %i.02 = phi i64 [ %inc, %test1.for.body ], [ 1, %entry ]
  94   %arrayidx = getelementptr inbounds float, float* %b, i64 %i.02
  95   %0 = load float, float* %arrayidx, align 4
  96   %sub1 = add i64 %i.02, -1
  97   %arrayidx2 = getelementptr inbounds float, float* %a, i64 %sub1
  98   %1 = load float, float* %arrayidx2, align 4
  99   %add = fadd float %0, %1
 100   %arrayidx3 = getelementptr inbounds float, float* %a, i64 %i.02
 101   store float %add, float* %arrayidx3, align 4
 102   %inc = add i64 %i.02, 1
 103   %cmp = icmp ult i64 %inc, %sub
 104   br i1 %cmp, label %test1.for.body, label %for.end
 105
 106 for.end:                                          ; preds = %test1.for.body, %entry
 107   ret void
 108 }
 109
 110
 111 ; CHECK-LABEL: 'DDG' for loop 'test2.for.body':
 112 ; CHECK: Node Address:[[N1:0x[0-9a-f]*]]:single-instruction
 113 ; CHECK-NEXT: Instructions:
 114 ; CHECK-NEXT:    %i.02 = phi i64 [ %inc, %test2.for.body ], [ 1, %test2.for.body.preheader ]
 115 ; CHECK-NEXT: Edges:
 116 ; CHECK-NEXT:  [def-use] to [[N2:0x[0-9a-f]*]]
 117 ; CHECK-NEXT:  [def-use] to [[N3:0x[0-9a-f]*]]
 118 ; CHECK-NEXT:  [def-use] to [[N4:0x[0-9a-f]*]]
 119 ; CHECK-NEXT:  [def-use] to [[N5:0x[0-9a-f]*]]
 120
 121 ; CHECK: Node Address:[[N5]]:single-instruction
 122 ; CHECK-NEXT: Instructions:
 123 ; CHECK-NEXT:    %arrayidx = getelementptr inbounds float, float* %b, i64 %i.02
 124 ; CHECK-NEXT: Edges:
 125 ; CHECK-NEXT:  [def-use] to [[N6:0x[0-9a-f]*]]
 126
 127 ; CHECK: Node Address:[[N6]]:single-instruction
 128 ; CHECK-NEXT: Instructions:
 129 ; CHECK-NEXT:    %0 = load float, float* %arrayidx, align 4
 130 ; CHECK-NEXT: Edges:
 131 ; CHECK-NEXT:  [def-use] to [[N7:0x[0-9a-f]*]]
 132
 133 ; CHECK: Node Address:[[N4]]:single-instruction
 134 ; CHECK-NEXT: Instructions:
 135 ; CHECK-NEXT:    %add1 = add i64 %i.02, 1
 136 ; CHECK-NEXT: Edges:
 137 ; CHECK-NEXT:  [def-use] to [[N8:0x[0-9a-f]*]]
 138
 139 ; CHECK: Node Address:[[N8]]:single-instruction
 140 ; CHECK-NEXT: Instructions:
 141 ; CHECK-NEXT:    %arrayidx2 = getelementptr inbounds float, float* %a, i64 %add1
 142 ; CHECK-NEXT: Edges:
 143 ; CHECK-NEXT:  [def-use] to [[N9:0x[0-9a-f]*]]
 144
 145 ; CHECK: Node Address:[[N9]]:single-instruction
 146 ; CHECK-NEXT: Instructions:
 147 ; CHECK-NEXT:    %1 = load float, float* %arrayidx2, align 4
 148 ; CHECK-NEXT: Edges:
 149 ; CHECK-NEXT:  [def-use] to [[N7]]
 150 ; CHECK-NEXT:  [memory] to [[N10:0x[0-9a-f]*]]
 151
 152 ; CHECK: Node Address:[[N7]]:single-instruction
 153 ; CHECK-NEXT: Instructions:
 154 ; CHECK-NEXT:    %add = fadd float %0, %1
 155 ; CHECK-NEXT: Edges:
 156 ; CHECK-NEXT:  [def-use] to [[N10]]
 157
 158 ; CHECK: Node Address:[[N3]]:single-instruction
 159 ; CHECK-NEXT: Instructions:
 160 ; CHECK-NEXT:    %arrayidx3 = getelementptr inbounds float, float* %a, i64 %i.02
 161 ; CHECK-NEXT: Edges:
 162 ; CHECK-NEXT:  [def-use] to [[N10]]
 163
 164 ; CHECK: Node Address:[[N10]]:single-instruction
 165 ; CHECK-NEXT: Instructions:
 166 ; CHECK-NEXT:    store float %add, float* %arrayidx3, align 4
 167 ; CHECK-NEXT: Edges:none!
 168
 169 ; CHECK: Node Address:[[N2]]:single-instruction
 170 ; CHECK-NEXT: Instructions:
 171 ; CHECK-NEXT:    %inc = add i64 %i.02, 1
 172 ; CHECK-NEXT: Edges:
 173 ; CHECK-NEXT:  [def-use] to [[N11:0x[0-9a-f]*]]
 174 ; CHECK-NEXT:  [def-use] to [[N1]]
 175
 176 ; CHECK: Node Address:[[N11]]:single-instruction
 177 ; CHECK-NEXT: Instructions:
 178 ; CHECK-NEXT:    %cmp = icmp ult i64 %inc, %sub
 179 ; CHECK-NEXT: Edges:
 180 ; CHECK-NEXT:  [def-use] to [[N12:0x[0-9a-f]*]]
 181
 182 ; CHECK: Node Address:[[N12]]:single-instruction
 183 ; CHECK-NEXT: Instructions:
 184 ; CHECK-NEXT:    br i1 %cmp, label %test2.for.body, label %for.end.loopexit
 185 ; CHECK-NEXT: Edges:none!
 186
 187
 188 ;; Forward loop-carried dependence *not* causing a cycle.
 189 ;; void test2(unsigned long n, float * restrict a, float * restrict b) {
 190 ;;  for (unsigned long i = 1; i < n-1; i++)
 191 ;;    a[i] = b[i] + a[i+1];
 192 ;; }
 193
 194 define void @test2(i64 %n, float* noalias %a, float* noalias %b) {
 195 entry:
 196   %sub = add i64 %n, -1
 197   %cmp1 = icmp ult i64 1, %sub
 198   br i1 %cmp1, label %test2.for.body, label %for.end
 199
 200 test2.for.body:                                         ; preds = %entry, %test2.for.body
 201   %i.02 = phi i64 [ %inc, %test2.for.body ], [ 1, %entry ]
 202   %arrayidx = getelementptr inbounds float, float* %b, i64 %i.02
 203   %0 = load float, float* %arrayidx, align 4
 204   %add1 = add i64 %i.02, 1
 205   %arrayidx2 = getelementptr inbounds float, float* %a, i64 %add1
 206   %1 = load float, float* %arrayidx2, align 4
 207   %add = fadd float %0, %1
 208   %arrayidx3 = getelementptr inbounds float, float* %a, i64 %i.02
 209   store float %add, float* %arrayidx3, align 4
 210   %inc = add i64 %i.02, 1
 211   %cmp = icmp ult i64 %inc, %sub
 212   br i1 %cmp, label %test2.for.body, label %for.end
 213
 214 for.end:                                          ; preds = %test2.for.body, %entry
 215   ret void
 216 }