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, float* %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, float* %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, float* %b, i64 %i.02 47; CHECK-NEXT: %0 = load float, float* %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, float* %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, float* %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, float * restrict a, float * restrict b) { 78;; for (unsigned long i = 1; i < n-1; i++) 79;; a[i] = b[i] + a[i-1]; 80;; } 81 82define void @test1(i64 %n, float* noalias %a, float* noalias %b) { 83entry: 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 88test1.for.body: ; preds = %entry, %test1.for.body 89 %i.02 = phi i64 [ %inc, %test1.for.body ], [ 1, %entry ] 90 %arrayidx = getelementptr inbounds float, float* %b, i64 %i.02 91 %0 = load float, float* %arrayidx, align 4 92 %sub1 = add i64 %i.02, -1 93 %arrayidx2 = getelementptr inbounds float, float* %a, i64 %sub1 94 %1 = load float, float* %arrayidx2, align 4 95 %add = fadd float %0, %1 96 %arrayidx3 = getelementptr inbounds float, float* %a, i64 %i.02 97 store float %add, float* %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 102for.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, float* %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, float* %a, i64 %add1 145; CHECK-NEXT: %1 = load float, float* %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, float* %b, i64 %i.02 153; CHECK-NEXT: %0 = load float, float* %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, float* %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, float * restrict a, float * restrict b) { 171;; for (unsigned long i = 1; i < n-1; i++) 172;; a[i] = b[i] + a[i+1]; 173;; } 174 175define void @test2(i64 %n, float* noalias %a, float* noalias %b) { 176entry: 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 181test2.for.body: ; preds = %entry, %test2.for.body 182 %i.02 = phi i64 [ %inc, %test2.for.body ], [ 1, %entry ] 183 %arrayidx = getelementptr inbounds float, float* %b, i64 %i.02 184 %0 = load float, float* %arrayidx, align 4 185 %add1 = add i64 %i.02, 1 186 %arrayidx2 = getelementptr inbounds float, float* %a, i64 %add1 187 %1 = load float, float* %arrayidx2, align 4 188 %add = fadd float %0, %1 189 %arrayidx3 = getelementptr inbounds float, float* %a, i64 %i.02 190 store float %add, float* %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 195for.end: ; preds = %test2.for.body, %entry 196 ret void 197} 198