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