198 lines · plain
1; RUN: opt < %s -disable-output "-passes=print<ddg>" 2>&1 | FileCheck %s2 3; CHECK-LABEL: 'DDG' for loop 'test1.for.body':4 5; CHECK: Node Address:[[N1:0x[0-9a-f]*]]:pi-block6; CHECK-NEXT:--- start of nodes in pi-block ---7; CHECK: Node Address:[[N2:0x[0-9a-f]*]]:single-instruction8; 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-instruction14; CHECK-NEXT: Instructions:15; CHECK-NEXT: %inc = add i64 %i.02, 116; 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-instruction26; CHECK-NEXT: Instructions:27; CHECK-NEXT: %cmp = icmp ult i64 %inc, %sub28; CHECK-NEXT: br i1 %cmp, label %test1.for.body, label %for.end.loopexit29; CHECK-NEXT: Edges:none!30 31; CHECK: Node Address:[[N6]]:single-instruction32; CHECK-NEXT: Instructions:33; CHECK-NEXT: %arrayidx3 = getelementptr inbounds float, ptr %a, i64 %i.0234; CHECK-NEXT: Edges:35; CHECK-NEXT: [def-use] to [[N8:0x[0-9a-f]*]]36 37; CHECK: Node Address:[[N5]]:multi-instruction38; CHECK-NEXT: Instructions:39; CHECK-NEXT: %sub1 = add i64 %i.02, -140; CHECK-NEXT: %arrayidx2 = getelementptr inbounds float, ptr %a, i64 %sub141; CHECK-NEXT: Edges:42; CHECK-NEXT: [def-use] to [[N8]]43 44; CHECK: Node Address:[[N4]]:multi-instruction45; CHECK-NEXT: Instructions:46; CHECK-NEXT: %arrayidx = getelementptr inbounds float, ptr %b, i64 %i.0247; CHECK-NEXT: %0 = load float, ptr %arrayidx, align 448; CHECK-NEXT: Edges:49; CHECK-NEXT: [def-use] to [[N8]]50 51; CHECK: Node Address:[[N8]]:pi-block52; CHECK-NEXT: --- start of nodes in pi-block ---53; CHECK: Node Address:[[N9:0x[0-9a-f]*]]:single-instruction54; CHECK-NEXT: Instructions:55; CHECK-NEXT: %1 = load float, ptr %arrayidx2, align 456; CHECK-NEXT: Edges:57; CHECK-NEXT: [def-use] to [[N10:0x[0-9a-f]*]]58 59; CHECK: Node Address:[[N10]]:single-instruction60; CHECK-NEXT: Instructions:61; CHECK-NEXT: %add = fadd float %0, %162; CHECK-NEXT: Edges:63; CHECK-NEXT: [def-use] to [[N11:0x[0-9a-f]*]]64 65; CHECK: Node Address:[[N11]]:single-instruction66; CHECK-NEXT: Instructions:67; CHECK-NEXT: store float %add, ptr %arrayidx3, align 468; 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 cycle76;; 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 82define void @test1(i64 %n, ptr noalias %a, ptr noalias %b) {83entry:84 %sub = add i64 %n, -185 %cmp1 = icmp ult i64 1, %sub86 br i1 %cmp1, label %test1.for.body, label %for.end87 88test1.for.body: ; preds = %entry, %test1.for.body89 %i.02 = phi i64 [ %inc, %test1.for.body ], [ 1, %entry ]90 %arrayidx = getelementptr inbounds float, ptr %b, i64 %i.0291 %0 = load float, ptr %arrayidx, align 492 %sub1 = add i64 %i.02, -193 %arrayidx2 = getelementptr inbounds float, ptr %a, i64 %sub194 %1 = load float, ptr %arrayidx2, align 495 %add = fadd float %0, %196 %arrayidx3 = getelementptr inbounds float, ptr %a, i64 %i.0297 store float %add, ptr %arrayidx3, align 498 %inc = add i64 %i.02, 199 %cmp = icmp ult i64 %inc, %sub100 br i1 %cmp, label %test1.for.body, label %for.end101 102for.end: ; preds = %test1.for.body, %entry103 ret void104}105 106; CHECK-LABEL: 'DDG' for loop 'test2.for.body':107 108; CHECK: Node Address:[[N1:0x[0-9a-f]*]]:pi-block109; CHECK-NEXT:--- start of nodes in pi-block ---110 111; CHECK: Node Address:[[N2:0x[0-9a-f]*]]:single-instruction112; 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-instruction118; CHECK-NEXT: Instructions:119; CHECK-NEXT: %inc = add i64 %i.02, 1120; 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-instruction130; CHECK-NEXT: Instructions:131; CHECK-NEXT: %cmp = icmp ult i64 %inc, %sub132; CHECK-NEXT: br i1 %cmp, label %test2.for.body, label %for.end.loopexit133; CHECK-NEXT: Edges:none!134 135; CHECK: Node Address:[[N6]]:single-instruction136; CHECK-NEXT: Instructions:137; CHECK-NEXT: %arrayidx3 = getelementptr inbounds float, ptr %a, i64 %i.02138; CHECK-NEXT: Edges:139; CHECK-NEXT: [def-use] to [[N8:0x[0-9a-f]*]]140 141; CHECK: Node Address:[[N5]]:multi-instruction142; CHECK-NEXT: Instructions:143; CHECK-NEXT: %add1 = add i64 %i.02, 1144; CHECK-NEXT: %arrayidx2 = getelementptr inbounds float, ptr %a, i64 %add1145; CHECK-NEXT: %1 = load float, ptr %arrayidx2, align 4146; 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-instruction151; CHECK-NEXT: Instructions:152; CHECK-NEXT: %arrayidx = getelementptr inbounds float, ptr %b, i64 %i.02153; CHECK-NEXT: %0 = load float, ptr %arrayidx, align 4154; CHECK-NEXT: Edges:155; CHECK-NEXT: [def-use] to [[N9]]156 157; CHECK: Node Address:[[N9]]:single-instruction158; CHECK-NEXT: Instructions:159; CHECK-NEXT: %add = fadd float %0, %1160; CHECK-NEXT: Edges:161; CHECK-NEXT: [def-use] to [[N8]]162 163; CHECK: Node Address:[[N8]]:single-instruction164; CHECK-NEXT: Instructions:165; CHECK-NEXT: store float %add, ptr %arrayidx3, align 4166; 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 175define void @test2(i64 %n, ptr noalias %a, ptr noalias %b) {176entry:177 %sub = add i64 %n, -1178 %cmp1 = icmp ult i64 1, %sub179 br i1 %cmp1, label %test2.for.body, label %for.end180 181test2.for.body: ; preds = %entry, %test2.for.body182 %i.02 = phi i64 [ %inc, %test2.for.body ], [ 1, %entry ]183 %arrayidx = getelementptr inbounds float, ptr %b, i64 %i.02184 %0 = load float, ptr %arrayidx, align 4185 %add1 = add i64 %i.02, 1186 %arrayidx2 = getelementptr inbounds float, ptr %a, i64 %add1187 %1 = load float, ptr %arrayidx2, align 4188 %add = fadd float %0, %1189 %arrayidx3 = getelementptr inbounds float, ptr %a, i64 %i.02190 store float %add, ptr %arrayidx3, align 4191 %inc = add i64 %i.02, 1192 %cmp = icmp ult i64 %inc, %sub193 br i1 %cmp, label %test2.for.body, label %for.end194 195for.end: ; preds = %test2.for.body, %entry196 ret void197}198