1db800c26SBardia Mahjour; RUN: opt < %s -disable-output "-passes=print<ddg>" 2>&1 | FileCheck %s 2db800c26SBardia Mahjour 3db800c26SBardia Mahjour; CHECK-LABEL: 'DDG' for loop 'test1.for.body': 4bec37c3fSbmahjour 586acaa94SBardia Mahjour; CHECK: Node Address:[[N1:0x[0-9a-f]*]]:pi-block 62dd82a1cSBardia Mahjour; CHECK-NEXT:--- start of nodes in pi-block --- 786acaa94SBardia Mahjour; CHECK: Node Address:[[N2:0x[0-9a-f]*]]:single-instruction 82dd82a1cSBardia Mahjour; CHECK-NEXT: Instructions: 92dd82a1cSBardia Mahjour; CHECK-NEXT: %i.02 = phi i64 [ %inc, %test1.for.body ], [ 1, %test1.for.body.preheader ] 102dd82a1cSBardia Mahjour; CHECK-NEXT: Edges: 1186acaa94SBardia Mahjour; CHECK-NEXT: [def-use] to [[N3:0x[0-9a-f]*]] 1286acaa94SBardia Mahjour 1386acaa94SBardia Mahjour; CHECK: Node Address:[[N3]]:single-instruction 1486acaa94SBardia Mahjour; CHECK-NEXT: Instructions: 1586acaa94SBardia Mahjour; CHECK-NEXT: %inc = add i64 %i.02, 1 1686acaa94SBardia Mahjour; CHECK-NEXT: Edges: 1786acaa94SBardia Mahjour; CHECK-NEXT: [def-use] to [[N2]] 182dd82a1cSBardia Mahjour; CHECK-NEXT:--- end of nodes in pi-block --- 192dd82a1cSBardia Mahjour; CHECK-NEXT: Edges: 202dd82a1cSBardia Mahjour; CHECK-NEXT: [def-use] to [[N4:0x[0-9a-f]*]] 2186acaa94SBardia Mahjour; CHECK-NEXT: [def-use] to [[N5:0x[0-9a-f]*]] 222dd82a1cSBardia Mahjour; CHECK-NEXT: [def-use] to [[N6:0x[0-9a-f]*]] 232dd82a1cSBardia Mahjour; CHECK-NEXT: [def-use] to [[N7:0x[0-9a-f]*]] 242dd82a1cSBardia Mahjour 250a2626d0SBardia Mahjour; CHECK: Node Address:[[N7]]:multi-instruction 262dd82a1cSBardia Mahjour; CHECK-NEXT: Instructions: 272dd82a1cSBardia Mahjour; CHECK-NEXT: %cmp = icmp ult i64 %inc, %sub 282dd82a1cSBardia Mahjour; CHECK-NEXT: br i1 %cmp, label %test1.for.body, label %for.end.loopexit 292dd82a1cSBardia Mahjour; CHECK-NEXT: Edges:none! 302dd82a1cSBardia Mahjour 312dd82a1cSBardia Mahjour; CHECK: Node Address:[[N6]]:single-instruction 322dd82a1cSBardia Mahjour; CHECK-NEXT: Instructions: 33*7cf55817SMatt Arsenault; CHECK-NEXT: %arrayidx3 = getelementptr inbounds float, ptr %a, i64 %i.02 34f0af11d8Sbmahjour; CHECK-NEXT: Edges: 350a2626d0SBardia Mahjour; CHECK-NEXT: [def-use] to [[N8:0x[0-9a-f]*]] 36db800c26SBardia Mahjour 370a2626d0SBardia Mahjour; CHECK: Node Address:[[N5]]:multi-instruction 38db800c26SBardia Mahjour; CHECK-NEXT: Instructions: 3986acaa94SBardia Mahjour; CHECK-NEXT: %sub1 = add i64 %i.02, -1 40*7cf55817SMatt Arsenault; CHECK-NEXT: %arrayidx2 = getelementptr inbounds float, ptr %a, i64 %sub1 410a2626d0SBardia Mahjour; CHECK-NEXT: Edges: 420a2626d0SBardia Mahjour; CHECK-NEXT: [def-use] to [[N8]] 430a2626d0SBardia Mahjour 440a2626d0SBardia Mahjour; CHECK: Node Address:[[N4]]:multi-instruction 450a2626d0SBardia Mahjour; CHECK-NEXT: Instructions: 46*7cf55817SMatt Arsenault; CHECK-NEXT: %arrayidx = getelementptr inbounds float, ptr %b, i64 %i.02 47*7cf55817SMatt Arsenault; CHECK-NEXT: %0 = load float, ptr %arrayidx, align 4 480a2626d0SBardia Mahjour; CHECK-NEXT: Edges: 490a2626d0SBardia Mahjour; CHECK-NEXT: [def-use] to [[N8]] 500a2626d0SBardia Mahjour 510a2626d0SBardia Mahjour; CHECK: Node Address:[[N8]]:pi-block 520a2626d0SBardia Mahjour; CHECK-NEXT: --- start of nodes in pi-block --- 530a2626d0SBardia Mahjour; CHECK: Node Address:[[N9:0x[0-9a-f]*]]:single-instruction 540a2626d0SBardia Mahjour; CHECK-NEXT: Instructions: 55*7cf55817SMatt Arsenault; CHECK-NEXT: %1 = load float, ptr %arrayidx2, align 4 5686acaa94SBardia Mahjour; CHECK-NEXT: Edges: 5786acaa94SBardia Mahjour; CHECK-NEXT: [def-use] to [[N10:0x[0-9a-f]*]] 5886acaa94SBardia Mahjour 5986acaa94SBardia Mahjour; CHECK: Node Address:[[N10]]:single-instruction 6086acaa94SBardia Mahjour; CHECK-NEXT: Instructions: 610a2626d0SBardia Mahjour; CHECK-NEXT: %add = fadd float %0, %1 622dd82a1cSBardia Mahjour; CHECK-NEXT: Edges: 6386acaa94SBardia Mahjour; CHECK-NEXT: [def-use] to [[N11:0x[0-9a-f]*]] 642dd82a1cSBardia Mahjour 6586acaa94SBardia Mahjour; CHECK: Node Address:[[N11]]:single-instruction 662dd82a1cSBardia Mahjour; CHECK-NEXT: Instructions: 67*7cf55817SMatt Arsenault; CHECK-NEXT: store float %add, ptr %arrayidx3, align 4 68db800c26SBardia Mahjour; CHECK-NEXT: Edges: 690a2626d0SBardia Mahjour; CHECK-NEXT: [memory] to [[N9]] 70f0af11d8Sbmahjour; CHECK-NEXT:--- end of nodes in pi-block --- 71f0af11d8Sbmahjour; CHECK-NEXT: Edges:none! 72db800c26SBardia Mahjour 73db800c26SBardia Mahjour 74db800c26SBardia Mahjour 75db800c26SBardia Mahjour;; Loop-carried dependence requiring edge-reversal to expose a cycle 76db800c26SBardia Mahjour;; in the graph. 77*7cf55817SMatt Arsenault;; void test(unsigned long n, ptr restrict a, ptr restrict b) { 78db800c26SBardia Mahjour;; for (unsigned long i = 1; i < n-1; i++) 79db800c26SBardia Mahjour;; a[i] = b[i] + a[i-1]; 80db800c26SBardia Mahjour;; } 81db800c26SBardia Mahjour 82*7cf55817SMatt Arsenaultdefine void @test1(i64 %n, ptr noalias %a, ptr noalias %b) { 83db800c26SBardia Mahjourentry: 84db800c26SBardia Mahjour %sub = add i64 %n, -1 85db800c26SBardia Mahjour %cmp1 = icmp ult i64 1, %sub 86db800c26SBardia Mahjour br i1 %cmp1, label %test1.for.body, label %for.end 87db800c26SBardia Mahjour 88db800c26SBardia Mahjourtest1.for.body: ; preds = %entry, %test1.for.body 89db800c26SBardia Mahjour %i.02 = phi i64 [ %inc, %test1.for.body ], [ 1, %entry ] 90*7cf55817SMatt Arsenault %arrayidx = getelementptr inbounds float, ptr %b, i64 %i.02 91*7cf55817SMatt Arsenault %0 = load float, ptr %arrayidx, align 4 92db800c26SBardia Mahjour %sub1 = add i64 %i.02, -1 93*7cf55817SMatt Arsenault %arrayidx2 = getelementptr inbounds float, ptr %a, i64 %sub1 94*7cf55817SMatt Arsenault %1 = load float, ptr %arrayidx2, align 4 95db800c26SBardia Mahjour %add = fadd float %0, %1 96*7cf55817SMatt Arsenault %arrayidx3 = getelementptr inbounds float, ptr %a, i64 %i.02 97*7cf55817SMatt Arsenault store float %add, ptr %arrayidx3, align 4 98db800c26SBardia Mahjour %inc = add i64 %i.02, 1 99db800c26SBardia Mahjour %cmp = icmp ult i64 %inc, %sub 100db800c26SBardia Mahjour br i1 %cmp, label %test1.for.body, label %for.end 101db800c26SBardia Mahjour 102db800c26SBardia Mahjourfor.end: ; preds = %test1.for.body, %entry 103db800c26SBardia Mahjour ret void 104db800c26SBardia Mahjour} 105db800c26SBardia Mahjour 106db800c26SBardia Mahjour; CHECK-LABEL: 'DDG' for loop 'test2.for.body': 107db800c26SBardia Mahjour 10886acaa94SBardia Mahjour; CHECK: Node Address:[[N1:0x[0-9a-f]*]]:pi-block 109f0af11d8Sbmahjour; CHECK-NEXT:--- start of nodes in pi-block --- 110f0af11d8Sbmahjour 11186acaa94SBardia Mahjour; CHECK: Node Address:[[N2:0x[0-9a-f]*]]:single-instruction 112f0af11d8Sbmahjour; CHECK-NEXT: Instructions: 113f0af11d8Sbmahjour; CHECK-NEXT: %i.02 = phi i64 [ %inc, %test2.for.body ], [ 1, %test2.for.body.preheader ] 114f0af11d8Sbmahjour; CHECK-NEXT: Edges: 11586acaa94SBardia Mahjour; CHECK-NEXT: [def-use] to [[N3:0x[0-9a-f]*]] 11686acaa94SBardia Mahjour 11786acaa94SBardia Mahjour; CHECK: Node Address:[[N3]]:single-instruction 11886acaa94SBardia Mahjour; CHECK-NEXT: Instructions: 11986acaa94SBardia Mahjour; CHECK-NEXT: %inc = add i64 %i.02, 1 12086acaa94SBardia Mahjour; CHECK-NEXT: Edges: 12186acaa94SBardia Mahjour; CHECK-NEXT: [def-use] to [[N2]] 122f0af11d8Sbmahjour; CHECK-NEXT:--- end of nodes in pi-block --- 123f0af11d8Sbmahjour; CHECK-NEXT: Edges: 1242dd82a1cSBardia Mahjour; CHECK-NEXT: [def-use] to [[N4:0x[0-9a-f]*]] 12586acaa94SBardia Mahjour; CHECK-NEXT: [def-use] to [[N5:0x[0-9a-f]*]] 12686acaa94SBardia Mahjour; CHECK-NEXT: [def-use] to [[N6:0x[0-9a-f]*]] 12786acaa94SBardia Mahjour; CHECK-NEXT: [def-use] to [[N7:0x[0-9a-f]*]] 1282dd82a1cSBardia Mahjour 1290a2626d0SBardia Mahjour; CHECK: Node Address:[[N7]]:multi-instruction 1302dd82a1cSBardia Mahjour; CHECK-NEXT: Instructions: 1312dd82a1cSBardia Mahjour; CHECK-NEXT: %cmp = icmp ult i64 %inc, %sub 13286acaa94SBardia Mahjour; CHECK-NEXT: br i1 %cmp, label %test2.for.body, label %for.end.loopexit 13386acaa94SBardia Mahjour; CHECK-NEXT: Edges:none! 13486acaa94SBardia Mahjour 13586acaa94SBardia Mahjour; CHECK: Node Address:[[N6]]:single-instruction 13686acaa94SBardia Mahjour; CHECK-NEXT: Instructions: 137*7cf55817SMatt Arsenault; CHECK-NEXT: %arrayidx3 = getelementptr inbounds float, ptr %a, i64 %i.02 13886acaa94SBardia Mahjour; CHECK-NEXT: Edges: 1390a2626d0SBardia Mahjour; CHECK-NEXT: [def-use] to [[N8:0x[0-9a-f]*]] 14086acaa94SBardia Mahjour 1410a2626d0SBardia Mahjour; CHECK: Node Address:[[N5]]:multi-instruction 14286acaa94SBardia Mahjour; CHECK-NEXT: Instructions: 14386acaa94SBardia Mahjour; CHECK-NEXT: %add1 = add i64 %i.02, 1 144*7cf55817SMatt Arsenault; CHECK-NEXT: %arrayidx2 = getelementptr inbounds float, ptr %a, i64 %add1 145*7cf55817SMatt Arsenault; CHECK-NEXT: %1 = load float, ptr %arrayidx2, align 4 1462dd82a1cSBardia Mahjour; CHECK-NEXT: Edges: 1470a2626d0SBardia Mahjour; CHECK-NEXT: [def-use] to [[N9:0x[0-9a-f]*]] 1480a2626d0SBardia Mahjour; CHECK-NEXT: [memory] to [[N8]] 1492dd82a1cSBardia Mahjour 1500a2626d0SBardia Mahjour; CHECK: Node Address:[[N4]]:multi-instruction 1512dd82a1cSBardia Mahjour; CHECK-NEXT: Instructions: 152*7cf55817SMatt Arsenault; CHECK-NEXT: %arrayidx = getelementptr inbounds float, ptr %b, i64 %i.02 153*7cf55817SMatt Arsenault; CHECK-NEXT: %0 = load float, ptr %arrayidx, align 4 1542dd82a1cSBardia Mahjour; CHECK-NEXT: Edges: 15586acaa94SBardia Mahjour; CHECK-NEXT: [def-use] to [[N9]] 1562dd82a1cSBardia Mahjour 15786acaa94SBardia Mahjour; CHECK: Node Address:[[N9]]:single-instruction 1582dd82a1cSBardia Mahjour; CHECK-NEXT: Instructions: 1590a2626d0SBardia Mahjour; CHECK-NEXT: %add = fadd float %0, %1 1600a2626d0SBardia Mahjour; CHECK-NEXT: Edges: 1610a2626d0SBardia Mahjour; CHECK-NEXT: [def-use] to [[N8]] 1620a2626d0SBardia Mahjour 1630a2626d0SBardia Mahjour; CHECK: Node Address:[[N8]]:single-instruction 1640a2626d0SBardia Mahjour; CHECK-NEXT: Instructions: 165*7cf55817SMatt Arsenault; CHECK-NEXT: store float %add, ptr %arrayidx3, align 4 1662dd82a1cSBardia Mahjour; CHECK-NEXT: Edges:none! 167f0af11d8Sbmahjour 168db800c26SBardia Mahjour 169db800c26SBardia Mahjour;; Forward loop-carried dependence *not* causing a cycle. 170*7cf55817SMatt Arsenault;; void test2(unsigned long n, ptr restrict a, ptr restrict b) { 171db800c26SBardia Mahjour;; for (unsigned long i = 1; i < n-1; i++) 172db800c26SBardia Mahjour;; a[i] = b[i] + a[i+1]; 173db800c26SBardia Mahjour;; } 174db800c26SBardia Mahjour 175*7cf55817SMatt Arsenaultdefine void @test2(i64 %n, ptr noalias %a, ptr noalias %b) { 176db800c26SBardia Mahjourentry: 177db800c26SBardia Mahjour %sub = add i64 %n, -1 178db800c26SBardia Mahjour %cmp1 = icmp ult i64 1, %sub 179db800c26SBardia Mahjour br i1 %cmp1, label %test2.for.body, label %for.end 180db800c26SBardia Mahjour 181db800c26SBardia Mahjourtest2.for.body: ; preds = %entry, %test2.for.body 182db800c26SBardia Mahjour %i.02 = phi i64 [ %inc, %test2.for.body ], [ 1, %entry ] 183*7cf55817SMatt Arsenault %arrayidx = getelementptr inbounds float, ptr %b, i64 %i.02 184*7cf55817SMatt Arsenault %0 = load float, ptr %arrayidx, align 4 185db800c26SBardia Mahjour %add1 = add i64 %i.02, 1 186*7cf55817SMatt Arsenault %arrayidx2 = getelementptr inbounds float, ptr %a, i64 %add1 187*7cf55817SMatt Arsenault %1 = load float, ptr %arrayidx2, align 4 188db800c26SBardia Mahjour %add = fadd float %0, %1 189*7cf55817SMatt Arsenault %arrayidx3 = getelementptr inbounds float, ptr %a, i64 %i.02 190*7cf55817SMatt Arsenault store float %add, ptr %arrayidx3, align 4 191db800c26SBardia Mahjour %inc = add i64 %i.02, 1 192db800c26SBardia Mahjour %cmp = icmp ult i64 %inc, %sub 193db800c26SBardia Mahjour br i1 %cmp, label %test2.for.body, label %for.end 194db800c26SBardia Mahjour 195db800c26SBardia Mahjourfor.end: ; preds = %test2.for.body, %entry 196db800c26SBardia Mahjour ret void 197db800c26SBardia Mahjour} 198