llvm/test/Analysis/DDG/basic-loopnest.ll

   1 ; RUN: opt < %s -disable-output "-passes=print<ddg>" 2>&1 | FileCheck %s
   2
   3
   4 ; CHECK-LABEL: 'DDG' for loop 'test1.for.cond1.preheader':
   5
   6 ; CHECK: Node Address:[[N1:0x[0-9a-f]*]]:pi-block
   7 ; CHECK-NEXT:--- start of nodes in pi-block ---
   8 ; CHECK: Node Address:[[N2:0x[0-9a-f]*]]:single-instruction
   9 ; CHECK-NEXT: Instructions:
  10 ; CHECK-NEXT:    %j.02 = phi i64 [ %inc, %for.body4 ], [ 1, %for.body4.preheader ]
  11 ; CHECK-NEXT: Edges:
  12 ; CHECK-NEXT:  [def-use] to [[N3:0x[0-9a-f]*]]
  13
  14 ; CHECK: Node Address:[[N3]]:single-instruction
  15 ; CHECK-NEXT: Instructions:
  16 ; CHECK-NEXT:    %inc = add i64 %j.02, 1
  17 ; CHECK-NEXT: Edges:
  18 ; CHECK-NEXT:  [def-use] to [[N2]]
  19 ; CHECK-NEXT:--- end of nodes in pi-block ---
  20 ; CHECK-NEXT: Edges:
  21 ; CHECK-NEXT:  [def-use] to [[N4:0x[0-9a-f]*]]
  22 ; CHECK-NEXT:  [def-use] to [[N5:0x[0-9a-f]*]]
  23 ; CHECK-NEXT:  [def-use] to [[N6:0x[0-9a-f]*]]
  24 ; CHECK-NEXT:  [def-use] to [[N7:0x[0-9a-f]*]]
  25
  26 ; CHECK: Node Address:[[N5]]:single-instruction
  27 ; CHECK-NEXT: Instructions:
  28 ; CHECK-NEXT:    %sub7 = add i64 %j.02, -1
  29 ; CHECK-NEXT: Edges:
  30 ; CHECK-NEXT:  [def-use] to [[N8:0x[0-9a-f]*]]
  31
  32 ; CHECK: Node Address:[[N9:0x[0-9a-f]*]]:pi-block
  33 ; CHECK-NEXT:--- start of nodes in pi-block ---
  34 ; CHECK: Node Address:[[N10:0x[0-9a-f]*]]:single-instruction
  35 ; CHECK-NEXT: Instructions:
  36 ; CHECK-NEXT:    %i.04 = phi i64 [ %inc13, %for.inc12 ], [ 0, %test1.for.cond1.preheader.preheader ]
  37 ; CHECK-NEXT: Edges:
  38 ; CHECK-NEXT:  [def-use] to [[N11:0x[0-9a-f]*]]
  39
  40 ; CHECK: Node Address:[[N11]]:single-instruction
  41 ; CHECK-NEXT: Instructions:
  42 ; CHECK-NEXT:    %inc13 = add i64 %i.04, 1
  43 ; CHECK-NEXT: Edges:
  44 ; CHECK-NEXT:  [def-use] to [[N10]]
  45 ; CHECK-NEXT:--- end of nodes in pi-block ---
  46 ; CHECK-NEXT: Edges:
  47 ; CHECK-NEXT:  [def-use] to [[N12:0x[0-9a-f]*]]
  48 ; CHECK-NEXT:  [def-use] to [[N13:0x[0-9a-f]*]]
  49 ; CHECK-NEXT:  [def-use] to [[N14:0x[0-9a-f]*]]
  50 ; CHECK-NEXT:  [def-use] to [[N15:0x[0-9a-f]*]]
  51
  52 ; CHECK: Node Address:[[N15]]:multi-instruction
  53 ; CHECK-NEXT: Instructions:
  54 ; CHECK-NEXT:    %exitcond = icmp ne i64 %inc13, %n
  55 ; CHECK-NEXT:    br i1 %exitcond, label %test1.for.cond1.preheader, label %for.end14.loopexit
  56 ; CHECK-NEXT: Edges:none!
  57
  58 ; CHECK: Node Address:[[N14]]:multi-instruction
  59 ; CHECK-NEXT: Instructions:
  60 ; CHECK-NEXT:    %4 = mul nsw i64 %i.04, %n
  61 ; CHECK-NEXT:    %arrayidx10 = getelementptr inbounds float, ptr %a, i64 %4
  62 ; CHECK-NEXT: Edges:
  63 ; CHECK-NEXT:  [def-use] to [[N6]]
  64
  65 ; CHECK: Node Address:[[N6]]:single-instruction
  66 ; CHECK-NEXT: Instructions:
  67 ; CHECK-NEXT:    %arrayidx11 = getelementptr inbounds float, ptr %arrayidx10, i64 %j.02
  68 ; CHECK-NEXT: Edges:
  69 ; CHECK-NEXT:  [def-use] to [[N18:0x[0-9a-f]*]]
  70
  71 ; CHECK: Node Address:[[N13]]:multi-instruction
  72 ; CHECK-NEXT: Instructions:
  73 ; CHECK-NEXT:    %2 = mul nsw i64 %i.04, %n
  74 ; CHECK-NEXT:    %arrayidx6 = getelementptr inbounds float, ptr %a, i64 %2
  75 ; CHECK-NEXT: Edges:
  76 ; CHECK-NEXT:  [def-use] to [[N8]]
  77
  78 ; CHECK: Node Address:[[N8]]:single-instruction
  79 ; CHECK-NEXT: Instructions:
  80 ; CHECK-NEXT:    %arrayidx8 = getelementptr inbounds float, ptr %arrayidx6, i64 %sub7
  81 ; CHECK-NEXT: Edges:
  82 ; CHECK-NEXT:  [def-use] to [[N18]]
  83
  84 ; CHECK: Node Address:[[N12]]:multi-instruction
  85 ; CHECK-NEXT: Instructions:
  86 ; CHECK-NEXT:    %0 = mul nsw i64 %i.04, %n
  87 ; CHECK-NEXT:    %arrayidx = getelementptr inbounds float, ptr %b, i64 %0
  88 ; CHECK-NEXT: Edges:
  89 ; CHECK-NEXT:  [def-use] to [[N4]]
  90
  91 ; CHECK: Node Address:[[N4]]:multi-instruction
  92 ; CHECK-NEXT: Instructions:
  93 ; CHECK-NEXT:    %arrayidx5 = getelementptr inbounds float, ptr %arrayidx, i64 %j.02
  94 ; CHECK-NEXT:    %1 = load float, ptr %arrayidx5, align 4
  95 ; CHECK-NEXT: Edges:
  96 ; CHECK-NEXT:  [def-use] to [[N18]]
  97
  98 ; CHECK: Node Address:[[N18]]:pi-block
  99 ; CHECK-NEXT:--- start of nodes in pi-block ---
 100 ; CHECK: Node Address:[[N22:0x[0-9a-f]*]]:single-instruction
 101 ; CHECK-NEXT: Instructions:
 102 ; CHECK-NEXT:    %3 = load float, ptr %arrayidx8, align 4
 103 ; CHECK-NEXT: Edges:
 104 ; CHECK-NEXT:  [def-use] to [[N23:0x[0-9a-f]*]]
 105
 106 ; CHECK: Node Address:[[N23]]:single-instruction
 107 ; CHECK-NEXT: Instructions:
 108 ; CHECK-NEXT:    %add = fadd float %1, %3
 109 ; CHECK-NEXT: Edges:
 110 ; CHECK-NEXT:  [def-use] to [[N24:0x[0-9a-f]*]]
 111
 112 ; CHECK: Node Address:[[N24]]:single-instruction
 113 ; CHECK-NEXT: Instructions:
 114 ; CHECK-NEXT:    store float %add, ptr %arrayidx11, align 4
 115 ; CHECK-NEXT: Edges:
 116 ; CHECK-NEXT:  [memory] to [[N22]]
 117 ; CHECK-NEXT:--- end of nodes in pi-block ---
 118 ; CHECK-NEXT: Edges:none!
 119
 120 ; CHECK: Node Address:[[N25:0x[0-9a-f]*]]:single-instruction
 121 ; CHECK-NEXT: Instructions:
 122 ; CHECK-NEXT:    br label %for.inc12
 123 ; CHECK-NEXT: Edges:none!
 124
 125 ; CHECK: Node Address:[[N26:0x[0-9a-f]*]]:single-instruction
 126 ; CHECK-NEXT: Instructions:
 127 ; CHECK-NEXT:    br label %for.body4
 128 ; CHECK-NEXT: Edges:none!
 129
 130 ; CHECK: Node Address:[[N27:0x[0-9a-f]*]]:single-instruction
 131 ; CHECK-NEXT: Instructions:
 132 ; CHECK-NEXT:    %sub = add i64 %n, -1
 133 ; CHECK-NEXT: Edges:
 134 ; CHECK-NEXT:  [def-use] to [[N7]]
 135 ; CHECK-NEXT:  [def-use] to [[N28:0x[0-9a-f]*]]
 136
 137 ; CHECK: Node Address:[[N28]]:multi-instruction
 138 ; CHECK-NEXT: Instructions:
 139 ; CHECK-NEXT:    %cmp21 = icmp ult i64 1, %sub
 140 ; CHECK-NEXT:    br i1 %cmp21, label %for.body4.preheader, label %for.inc12
 141 ; CHECK-NEXT: Edges:none!
 142
 143 ; CHECK: Node Address:[[N7]]:multi-instruction
 144 ; CHECK-NEXT: Instructions:
 145 ; CHECK-NEXT:    %cmp2 = icmp ult i64 %inc, %sub
 146 ; CHECK-NEXT:    br i1 %cmp2, label %for.body4, label %for.inc12.loopexit
 147 ; CHECK-NEXT: Edges:none!
 148
 149
 150 ;; This test has a cycle.
 151 ;; void test1(unsigned long n, float a[][n], float b[][n]) {
 152 ;;  for (unsigned long i = 0; i < n; i++)
 153 ;;    for (unsigned long j = 1; j < n-1; j++)
 154 ;;      a[i][j] = b[i][j] + a[i][j-1];
 155 ;; }
 156
 157 define void @test1(i64 %n, ptr noalias %a, ptr noalias %b) {
 158 entry:
 159   %exitcond3 = icmp ne i64 0, %n
 160   br i1 %exitcond3, label %test1.for.cond1.preheader, label %for.end14
 161
 162 test1.for.cond1.preheader:                              ; preds = %entry, %for.inc12
 163   %i.04 = phi i64 [ %inc13, %for.inc12 ], [ 0, %entry ]
 164   %sub = add i64 %n, -1
 165   %cmp21 = icmp ult i64 1, %sub
 166   br i1 %cmp21, label %for.body4, label %for.inc12
 167
 168 for.body4:                                        ; preds = %test1.for.cond1.preheader, %for.body4
 169   %j.02 = phi i64 [ %inc, %for.body4 ], [ 1, %test1.for.cond1.preheader ]
 170   %0 = mul nsw i64 %i.04, %n
 171   %arrayidx = getelementptr inbounds float, ptr %b, i64 %0
 172   %arrayidx5 = getelementptr inbounds float, ptr %arrayidx, i64 %j.02
 173   %1 = load float, ptr %arrayidx5, align 4
 174   %2 = mul nsw i64 %i.04, %n
 175   %arrayidx6 = getelementptr inbounds float, ptr %a, i64 %2
 176   %sub7 = add i64 %j.02, -1
 177   %arrayidx8 = getelementptr inbounds float, ptr %arrayidx6, i64 %sub7
 178   %3 = load float, ptr %arrayidx8, align 4
 179   %add = fadd float %1, %3
 180   %4 = mul nsw i64 %i.04, %n
 181   %arrayidx10 = getelementptr inbounds float, ptr %a, i64 %4
 182   %arrayidx11 = getelementptr inbounds float, ptr %arrayidx10, i64 %j.02
 183   store float %add, ptr %arrayidx11, align 4
 184   %inc = add i64 %j.02, 1
 185   %cmp2 = icmp ult i64 %inc, %sub
 186   br i1 %cmp2, label %for.body4, label %for.inc12
 187
 188 for.inc12:                                        ; preds = %for.body4, %test1.for.cond1.preheader
 189   %inc13 = add i64 %i.04, 1
 190   %exitcond = icmp ne i64 %inc13, %n
 191   br i1 %exitcond, label %test1.for.cond1.preheader, label %for.end14
 192
 193 for.end14:                                        ; preds = %for.inc12, %entry
 194   ret void
 195 }
 196
 197
 198
 199 ; CHECK-LABEL: 'DDG' for loop 'test2.for.cond1.preheader':
 200
 201 ; CHECK: Node Address:[[PI1:0x[0-9a-f]*]]:pi-block
 202 ; CHECK-NEXT:--- start of nodes in pi-block ---
 203 ; CHECK: Node Address:[[N1:0x[0-9a-f]*]]:single-instruction
 204 ; CHECK-NEXT: Instructions:
 205 ; CHECK-NEXT:    %j.02 = phi i64 [ %inc, %for.body4 ], [ 1, %for.body4.preheader ]
 206 ; CHECK-NEXT: Edges:
 207 ; CHECK-NEXT:  [def-use] to [[N2:0x[0-9a-f]*]]
 208
 209 ; CHECK: Node Address:[[N2]]:single-instruction
 210 ; CHECK-NEXT: Instructions:
 211 ; CHECK-NEXT:    %inc = add i64 %j.02, 1
 212 ; CHECK-NEXT: Edges:
 213 ; CHECK-NEXT:  [def-use] to [[N1]]
 214 ; CHECK-NEXT:--- end of nodes in pi-block ---
 215 ; CHECK-NEXT: Edges:
 216 ; CHECK-NEXT:  [def-use] to [[N3:0x[0-9a-f]*]]
 217 ; CHECK-NEXT:  [def-use] to [[N4:0x[0-9a-f]*]]
 218 ; CHECK-NEXT:  [def-use] to [[N5:0x[0-9a-f]*]]
 219 ; CHECK-NEXT:  [def-use] to [[N6:0x[0-9a-f]*]]
 220
 221 ; CHECK: Node Address:[[N4]]:single-instruction
 222 ; CHECK-NEXT: Instructions:
 223 ; CHECK-NEXT:    %add7 = add i64 %j.02, 1
 224 ; CHECK-NEXT: Edges:
 225 ; CHECK-NEXT:  [def-use] to [[N7:0x[0-9a-f]*]]
 226
 227 ; CHECK: Node Address:[[N8:0x[0-9a-f]*]]:pi-block
 228 ; CHECK-NEXT:--- start of nodes in pi-block ---
 229 ; CHECK: Node Address:[[N9:0x[0-9a-f]*]]:single-instruction
 230 ; CHECK-NEXT: Instructions:
 231 ; CHECK-NEXT:    %i.04 = phi i64 [ %inc13, %for.inc12 ], [ 0, %test2.for.cond1.preheader.preheader ]
 232 ; CHECK-NEXT: Edges:
 233 ; CHECK-NEXT:  [def-use] to [[N10:0x[0-9a-f]*]]
 234
 235 ; CHECK: Node Address:[[N10]]:single-instruction
 236 ; CHECK-NEXT: Instructions:
 237 ; CHECK-NEXT:    %inc13 = add i64 %i.04, 1
 238 ; CHECK-NEXT: Edges:
 239 ; CHECK-NEXT:  [def-use] to [[N9]]
 240 ; CHECK-NEXT:--- end of nodes in pi-block ---
 241 ; CHECK-NEXT: Edges:
 242 ; CHECK-NEXT:  [def-use] to [[N11:0x[0-9a-f]*]]
 243 ; CHECK-NEXT:  [def-use] to [[N12:0x[0-9a-f]*]]
 244 ; CHECK-NEXT:  [def-use] to [[N13:0x[0-9a-f]*]]
 245 ; CHECK-NEXT:  [def-use] to [[N14:0x[0-9a-f]*]]
 246
 247 ; CHECK: Node Address:[[N14]]:multi-instruction
 248 ; CHECK-NEXT: Instructions:
 249 ; CHECK-NEXT:    %exitcond = icmp ne i64 %inc13, %n
 250 ; CHECK-NEXT:    br i1 %exitcond, label %test2.for.cond1.preheader, label %for.end14.loopexit
 251 ; CHECK-NEXT: Edges:none!
 252
 253 ; CHECK: Node Address:[[N13]]:multi-instruction
 254 ; CHECK-NEXT: Instructions:
 255 ; CHECK-NEXT:    %4 = mul nsw i64 %i.04, %n
 256 ; CHECK-NEXT:    %arrayidx10 = getelementptr inbounds float, ptr %a, i64 %4
 257 ; CHECK-NEXT: Edges:
 258 ; CHECK-NEXT:  [def-use] to [[N5]]
 259
 260 ; CHECK: Node Address:[[N5]]:single-instruction
 261 ; CHECK-NEXT: Instructions:
 262 ; CHECK-NEXT:    %arrayidx11 = getelementptr inbounds float, ptr %arrayidx10, i64 %j.02
 263 ; CHECK-NEXT: Edges:
 264 ; CHECK-NEXT:  [def-use] to [[N17:0x[0-9a-f]*]]
 265
 266 ; CHECK: Node Address:[[N12]]:multi-instruction
 267 ; CHECK-NEXT: Instructions:
 268 ; CHECK-NEXT:    %2 = mul nsw i64 %i.04, %n
 269 ; CHECK-NEXT:    %arrayidx6 = getelementptr inbounds float, ptr %a, i64 %2
 270 ; CHECK-NEXT: Edges:
 271 ; CHECK-NEXT:  [def-use] to [[N7]]
 272
 273 ; CHECK: Node Address:[[N7]]:multi-instruction
 274 ; CHECK-NEXT: Instructions:
 275 ; CHECK-NEXT:    %arrayidx8 = getelementptr inbounds float, ptr %arrayidx6, i64 %add7
 276 ; CHECK-NEXT:    %3 = load float, ptr %arrayidx8, align 4
 277 ; CHECK-NEXT: Edges:
 278 ; CHECK-NEXT:  [def-use] to [[N20:0x[0-9a-f]*]]
 279 ; CHECK-NEXT:  [memory] to [[N17]]
 280
 281 ; CHECK: Node Address:[[N11]]:multi-instruction
 282 ; CHECK-NEXT: Instructions:
 283 ; CHECK-NEXT:    %0 = mul nsw i64 %i.04, %n
 284 ; CHECK-NEXT:    %arrayidx = getelementptr inbounds float, ptr %b, i64 %0
 285 ; CHECK-NEXT: Edges:
 286 ; CHECK-NEXT:  [def-use] to [[N3]]
 287
 288 ; CHECK: Node Address:[[N3]]:multi-instruction
 289 ; CHECK-NEXT: Instructions:
 290 ; CHECK-NEXT:    %arrayidx5 = getelementptr inbounds float, ptr %arrayidx, i64 %j.02
 291 ; CHECK-NEXT:    %1 = load float, ptr %arrayidx5, align 4
 292 ; CHECK-NEXT: Edges:
 293 ; CHECK-NEXT:  [def-use] to [[N20]]
 294
 295 ; CHECK: Node Address:[[N20]]:single-instruction
 296 ; CHECK-NEXT: Instructions:
 297 ; CHECK-NEXT:    %add = fadd float %1, %3
 298 ; CHECK-NEXT: Edges:
 299 ; CHECK-NEXT:  [def-use] to [[N17]]
 300
 301 ; CHECK: Node Address:[[N17]]:single-instruction
 302 ; CHECK-NEXT: Instructions:
 303 ; CHECK-NEXT:    store float %add, ptr %arrayidx11, align 4
 304 ; CHECK-NEXT: Edges:none!
 305
 306 ; CHECK: Node Address:[[N23:0x[0-9a-f]*]]:single-instruction
 307 ; CHECK-NEXT: Instructions:
 308 ; CHECK-NEXT:    br label %for.inc12
 309 ; CHECK-NEXT: Edges:none!
 310
 311 ; CHECK: Node Address:[[N24:0x[0-9a-f]*]]:single-instruction
 312 ; CHECK-NEXT: Instructions:
 313 ; CHECK-NEXT:    br label %for.body4
 314 ; CHECK-NEXT: Edges:none!
 315
 316 ; CHECK: Node Address:[[N25:0x[0-9a-f]*]]:single-instruction
 317 ; CHECK-NEXT: Instructions:
 318 ; CHECK-NEXT:    %sub = add i64 %n, -1
 319 ; CHECK-NEXT: Edges:
 320 ; CHECK-NEXT:  [def-use] to [[N6]]
 321 ; CHECK-NEXT:  [def-use] to [[N26:0x[0-9a-f]*]]
 322
 323 ; CHECK: Node Address:[[N26]]:multi-instruction
 324 ; CHECK-NEXT: Instructions:
 325 ; CHECK-NEXT:    %cmp21 = icmp ult i64 1, %sub
 326 ; CHECK-NEXT:    br i1 %cmp21, label %for.body4.preheader, label %for.inc12
 327 ; CHECK-NEXT: Edges:none!
 328
 329 ; CHECK: Node Address:[[N6]]:multi-instruction
 330 ; CHECK-NEXT: Instructions:
 331 ; CHECK-NEXT:    %cmp2 = icmp ult i64 %inc, %sub
 332 ; CHECK-NEXT:    br i1 %cmp2, label %for.body4, label %for.inc12.loopexit
 333 ; CHECK-NEXT: Edges:none!
 334
 335
 336 ;; This test has no cycles.
 337 ;; void test2(unsigned long n, float a[][n], float b[][n]) {
 338 ;;  for (unsigned long i = 0; i < n; i++)
 339 ;;    for (unsigned long j = 1; j < n-1; j++)
 340 ;;      a[i][j] = b[i][j] + a[i][j+1];
 341 ;; }
 342
 343 define void @test2(i64 %n, ptr noalias %a, ptr noalias %b) {
 344 entry:
 345   %exitcond3 = icmp ne i64 0, %n
 346   br i1 %exitcond3, label %test2.for.cond1.preheader, label %for.end14
 347
 348 test2.for.cond1.preheader:                              ; preds = %entry, %for.inc12
 349   %i.04 = phi i64 [ %inc13, %for.inc12 ], [ 0, %entry ]
 350   %sub = add i64 %n, -1
 351   %cmp21 = icmp ult i64 1, %sub
 352   br i1 %cmp21, label %for.body4, label %for.inc12
 353
 354 for.body4:                                        ; preds = %test2.for.cond1.preheader, %for.body4
 355   %j.02 = phi i64 [ %inc, %for.body4 ], [ 1, %test2.for.cond1.preheader ]
 356   %0 = mul nsw i64 %i.04, %n
 357   %arrayidx = getelementptr inbounds float, ptr %b, i64 %0
 358   %arrayidx5 = getelementptr inbounds float, ptr %arrayidx, i64 %j.02
 359   %1 = load float, ptr %arrayidx5, align 4
 360   %2 = mul nsw i64 %i.04, %n
 361   %arrayidx6 = getelementptr inbounds float, ptr %a, i64 %2
 362   %add7 = add i64 %j.02, 1
 363   %arrayidx8 = getelementptr inbounds float, ptr %arrayidx6, i64 %add7
 364   %3 = load float, ptr %arrayidx8, align 4
 365   %add = fadd float %1, %3
 366   %4 = mul nsw i64 %i.04, %n
 367   %arrayidx10 = getelementptr inbounds float, ptr %a, i64 %4
 368   %arrayidx11 = getelementptr inbounds float, ptr %arrayidx10, i64 %j.02
 369   store float %add, ptr %arrayidx11, align 4
 370   %inc = add i64 %j.02, 1
 371   %cmp2 = icmp ult i64 %inc, %sub
 372   br i1 %cmp2, label %for.body4, label %for.inc12
 373
 374 for.inc12:                                        ; preds = %for.body4, %test2.for.cond1.preheader
 375   %inc13 = add i64 %i.04, 1
 376   %exitcond = icmp ne i64 %inc13, %n
 377   br i1 %exitcond, label %test2.for.cond1.preheader, label %for.end14
 378
 379 for.end14:                                        ; preds = %for.inc12, %entry
 380   ret void
 381 }