385 lines · plain
1; RUN: opt < %s -disable-output "-passes=print<ddg>" 2>&1 | FileCheck %s2 3; XFAIL: *4; At the moment, DependenceAnalysis cannot infer `n` to be positive.5 6 7; CHECK-LABEL: 'DDG' for loop 'test1.for.cond1.preheader':8 9; CHECK: Node Address:[[N1:0x[0-9a-f]*]]:pi-block10; CHECK-NEXT:--- start of nodes in pi-block ---11; CHECK: Node Address:[[N2:0x[0-9a-f]*]]:single-instruction12; CHECK-NEXT: Instructions:13; CHECK-NEXT: %j.02 = phi i64 [ %inc, %for.body4 ], [ 1, %for.body4.preheader ]14; CHECK-NEXT: Edges:15; CHECK-NEXT: [def-use] to [[N3:0x[0-9a-f]*]]16 17; CHECK: Node Address:[[N3]]:single-instruction18; CHECK-NEXT: Instructions:19; CHECK-NEXT: %inc = add i64 %j.02, 120; CHECK-NEXT: Edges:21; CHECK-NEXT: [def-use] to [[N2]]22; CHECK-NEXT:--- end of nodes in pi-block ---23; CHECK-NEXT: Edges:24; CHECK-NEXT: [def-use] to [[N4:0x[0-9a-f]*]]25; CHECK-NEXT: [def-use] to [[N5:0x[0-9a-f]*]]26; CHECK-NEXT: [def-use] to [[N6:0x[0-9a-f]*]]27; CHECK-NEXT: [def-use] to [[N7:0x[0-9a-f]*]]28 29; CHECK: Node Address:[[N5]]:single-instruction30; CHECK-NEXT: Instructions:31; CHECK-NEXT: %sub7 = add i64 %j.02, -132; CHECK-NEXT: Edges:33; CHECK-NEXT: [def-use] to [[N8:0x[0-9a-f]*]]34 35; CHECK: Node Address:[[N9:0x[0-9a-f]*]]:pi-block36; CHECK-NEXT:--- start of nodes in pi-block ---37; CHECK: Node Address:[[N10:0x[0-9a-f]*]]:single-instruction38; CHECK-NEXT: Instructions:39; CHECK-NEXT: %i.04 = phi i64 [ %inc13, %for.inc12 ], [ 0, %test1.for.cond1.preheader.preheader ]40; CHECK-NEXT: Edges:41; CHECK-NEXT: [def-use] to [[N11:0x[0-9a-f]*]]42 43; CHECK: Node Address:[[N11]]:single-instruction44; CHECK-NEXT: Instructions:45; CHECK-NEXT: %inc13 = add i64 %i.04, 146; CHECK-NEXT: Edges:47; CHECK-NEXT: [def-use] to [[N10]]48; CHECK-NEXT:--- end of nodes in pi-block ---49; CHECK-NEXT: Edges:50; CHECK-NEXT: [def-use] to [[N12:0x[0-9a-f]*]]51; CHECK-NEXT: [def-use] to [[N13:0x[0-9a-f]*]]52; CHECK-NEXT: [def-use] to [[N14:0x[0-9a-f]*]]53; CHECK-NEXT: [def-use] to [[N15:0x[0-9a-f]*]]54 55; CHECK: Node Address:[[N15]]:multi-instruction56; CHECK-NEXT: Instructions:57; CHECK-NEXT: %exitcond = icmp ne i64 %inc13, %n58; CHECK-NEXT: br i1 %exitcond, label %test1.for.cond1.preheader, label %for.end14.loopexit59; CHECK-NEXT: Edges:none!60 61; CHECK: Node Address:[[N14]]:multi-instruction62; CHECK-NEXT: Instructions:63; CHECK-NEXT: %4 = mul nsw i64 %i.04, %n64; CHECK-NEXT: %arrayidx10 = getelementptr inbounds float, ptr %a, i64 %465; CHECK-NEXT: Edges:66; CHECK-NEXT: [def-use] to [[N6]]67 68; CHECK: Node Address:[[N6]]:single-instruction69; CHECK-NEXT: Instructions:70; CHECK-NEXT: %arrayidx11 = getelementptr inbounds float, ptr %arrayidx10, i64 %j.0271; CHECK-NEXT: Edges:72; CHECK-NEXT: [def-use] to [[N18:0x[0-9a-f]*]]73 74; CHECK: Node Address:[[N13]]:multi-instruction75; CHECK-NEXT: Instructions:76; CHECK-NEXT: %2 = mul nsw i64 %i.04, %n77; CHECK-NEXT: %arrayidx6 = getelementptr inbounds float, ptr %a, i64 %278; CHECK-NEXT: Edges:79; CHECK-NEXT: [def-use] to [[N8]]80 81; CHECK: Node Address:[[N8]]:single-instruction82; CHECK-NEXT: Instructions:83; CHECK-NEXT: %arrayidx8 = getelementptr inbounds float, ptr %arrayidx6, i64 %sub784; CHECK-NEXT: Edges:85; CHECK-NEXT: [def-use] to [[N18]]86 87; CHECK: Node Address:[[N12]]:multi-instruction88; CHECK-NEXT: Instructions:89; CHECK-NEXT: %0 = mul nsw i64 %i.04, %n90; CHECK-NEXT: %arrayidx = getelementptr inbounds float, ptr %b, i64 %091; CHECK-NEXT: Edges:92; CHECK-NEXT: [def-use] to [[N4]]93 94; CHECK: Node Address:[[N4]]:multi-instruction95; CHECK-NEXT: Instructions:96; CHECK-NEXT: %arrayidx5 = getelementptr inbounds float, ptr %arrayidx, i64 %j.0297; CHECK-NEXT: %1 = load float, ptr %arrayidx5, align 498; CHECK-NEXT: Edges:99; CHECK-NEXT: [def-use] to [[N18]]100 101; CHECK: Node Address:[[N18]]:pi-block102; CHECK-NEXT:--- start of nodes in pi-block ---103; CHECK: Node Address:[[N22:0x[0-9a-f]*]]:single-instruction104; CHECK-NEXT: Instructions:105; CHECK-NEXT: %3 = load float, ptr %arrayidx8, align 4106; CHECK-NEXT: Edges:107; CHECK-NEXT: [def-use] to [[N23:0x[0-9a-f]*]]108 109; CHECK: Node Address:[[N23]]:single-instruction110; CHECK-NEXT: Instructions:111; CHECK-NEXT: %add = fadd float %1, %3112; CHECK-NEXT: Edges:113; CHECK-NEXT: [def-use] to [[N24:0x[0-9a-f]*]]114 115; CHECK: Node Address:[[N24]]:single-instruction116; CHECK-NEXT: Instructions:117; CHECK-NEXT: store float %add, ptr %arrayidx11, align 4118; CHECK-NEXT: Edges:119; CHECK-NEXT: [memory] to [[N22]]120; CHECK-NEXT:--- end of nodes in pi-block ---121; CHECK-NEXT: Edges:none!122 123; CHECK: Node Address:[[N25:0x[0-9a-f]*]]:single-instruction124; CHECK-NEXT: Instructions:125; CHECK-NEXT: br label %for.inc12126; CHECK-NEXT: Edges:none!127 128; CHECK: Node Address:[[N26:0x[0-9a-f]*]]:single-instruction129; CHECK-NEXT: Instructions:130; CHECK-NEXT: br label %for.body4131; CHECK-NEXT: Edges:none!132 133; CHECK: Node Address:[[N27:0x[0-9a-f]*]]:single-instruction134; CHECK-NEXT: Instructions:135; CHECK-NEXT: %sub = add i64 %n, -1136; CHECK-NEXT: Edges:137; CHECK-NEXT: [def-use] to [[N7]]138; CHECK-NEXT: [def-use] to [[N28:0x[0-9a-f]*]]139 140; CHECK: Node Address:[[N28]]:multi-instruction141; CHECK-NEXT: Instructions:142; CHECK-NEXT: %cmp21 = icmp ult i64 1, %sub143; CHECK-NEXT: br i1 %cmp21, label %for.body4.preheader, label %for.inc12144; CHECK-NEXT: Edges:none!145 146; CHECK: Node Address:[[N7]]:multi-instruction147; CHECK-NEXT: Instructions:148; CHECK-NEXT: %cmp2 = icmp ult i64 %inc, %sub149; CHECK-NEXT: br i1 %cmp2, label %for.body4, label %for.inc12.loopexit150; CHECK-NEXT: Edges:none!151 152 153;; This test has a cycle.154;; void test1(unsigned long n, float a[][n], float b[][n]) {155;; for (unsigned long i = 0; i < n; i++)156;; for (unsigned long j = 1; j < n-1; j++)157;; a[i][j] = b[i][j] + a[i][j-1];158;; }159 160define void @test1(i64 %n, ptr noalias %a, ptr noalias %b) {161entry:162 %exitcond3 = icmp ne i64 0, %n163 br i1 %exitcond3, label %test1.for.cond1.preheader, label %for.end14164 165test1.for.cond1.preheader: ; preds = %entry, %for.inc12166 %i.04 = phi i64 [ %inc13, %for.inc12 ], [ 0, %entry ]167 %sub = add i64 %n, -1168 %cmp21 = icmp ult i64 1, %sub169 br i1 %cmp21, label %for.body4, label %for.inc12170 171for.body4: ; preds = %test1.for.cond1.preheader, %for.body4172 %j.02 = phi i64 [ %inc, %for.body4 ], [ 1, %test1.for.cond1.preheader ]173 %0 = mul nsw i64 %i.04, %n174 %arrayidx = getelementptr inbounds float, ptr %b, i64 %0175 %arrayidx5 = getelementptr inbounds float, ptr %arrayidx, i64 %j.02176 %1 = load float, ptr %arrayidx5, align 4177 %2 = mul nsw i64 %i.04, %n178 %arrayidx6 = getelementptr inbounds float, ptr %a, i64 %2179 %sub7 = add i64 %j.02, -1180 %arrayidx8 = getelementptr inbounds float, ptr %arrayidx6, i64 %sub7181 %3 = load float, ptr %arrayidx8, align 4182 %add = fadd float %1, %3183 %4 = mul nsw i64 %i.04, %n184 %arrayidx10 = getelementptr inbounds float, ptr %a, i64 %4185 %arrayidx11 = getelementptr inbounds float, ptr %arrayidx10, i64 %j.02186 store float %add, ptr %arrayidx11, align 4187 %inc = add i64 %j.02, 1188 %cmp2 = icmp ult i64 %inc, %sub189 br i1 %cmp2, label %for.body4, label %for.inc12190 191for.inc12: ; preds = %for.body4, %test1.for.cond1.preheader192 %inc13 = add i64 %i.04, 1193 %exitcond = icmp ne i64 %inc13, %n194 br i1 %exitcond, label %test1.for.cond1.preheader, label %for.end14195 196for.end14: ; preds = %for.inc12, %entry197 ret void198}199 200 201 202; CHECK-LABEL: 'DDG' for loop 'test2.for.cond1.preheader':203 204; CHECK: Node Address:[[PI1:0x[0-9a-f]*]]:pi-block205; CHECK-NEXT:--- start of nodes in pi-block ---206; CHECK: Node Address:[[N1:0x[0-9a-f]*]]:single-instruction207; CHECK-NEXT: Instructions:208; CHECK-NEXT: %j.02 = phi i64 [ %inc, %for.body4 ], [ 1, %for.body4.preheader ]209; CHECK-NEXT: Edges:210; CHECK-NEXT: [def-use] to [[N2:0x[0-9a-f]*]]211 212; CHECK: Node Address:[[N2]]:single-instruction213; CHECK-NEXT: Instructions:214; CHECK-NEXT: %inc = add i64 %j.02, 1215; CHECK-NEXT: Edges:216; CHECK-NEXT: [def-use] to [[N1]]217; CHECK-NEXT:--- end of nodes in pi-block ---218; CHECK-NEXT: Edges:219; CHECK-NEXT: [def-use] to [[N3:0x[0-9a-f]*]]220; CHECK-NEXT: [def-use] to [[N4:0x[0-9a-f]*]]221; CHECK-NEXT: [def-use] to [[N5:0x[0-9a-f]*]]222; CHECK-NEXT: [def-use] to [[N6:0x[0-9a-f]*]]223 224; CHECK: Node Address:[[N4]]:single-instruction225; CHECK-NEXT: Instructions:226; CHECK-NEXT: %add7 = add i64 %j.02, 1227; CHECK-NEXT: Edges:228; CHECK-NEXT: [def-use] to [[N7:0x[0-9a-f]*]]229 230; CHECK: Node Address:[[N8:0x[0-9a-f]*]]:pi-block231; CHECK-NEXT:--- start of nodes in pi-block ---232; CHECK: Node Address:[[N9:0x[0-9a-f]*]]:single-instruction233; CHECK-NEXT: Instructions:234; CHECK-NEXT: %i.04 = phi i64 [ %inc13, %for.inc12 ], [ 0, %test2.for.cond1.preheader.preheader ]235; CHECK-NEXT: Edges:236; CHECK-NEXT: [def-use] to [[N10:0x[0-9a-f]*]]237 238; CHECK: Node Address:[[N10]]:single-instruction239; CHECK-NEXT: Instructions:240; CHECK-NEXT: %inc13 = add i64 %i.04, 1241; CHECK-NEXT: Edges:242; CHECK-NEXT: [def-use] to [[N9]]243; CHECK-NEXT:--- end of nodes in pi-block ---244; CHECK-NEXT: Edges:245; CHECK-NEXT: [def-use] to [[N11:0x[0-9a-f]*]]246; CHECK-NEXT: [def-use] to [[N12:0x[0-9a-f]*]]247; CHECK-NEXT: [def-use] to [[N13:0x[0-9a-f]*]]248; CHECK-NEXT: [def-use] to [[N14:0x[0-9a-f]*]]249 250; CHECK: Node Address:[[N14]]:multi-instruction251; CHECK-NEXT: Instructions:252; CHECK-NEXT: %exitcond = icmp ne i64 %inc13, %n253; CHECK-NEXT: br i1 %exitcond, label %test2.for.cond1.preheader, label %for.end14.loopexit254; CHECK-NEXT: Edges:none!255 256; CHECK: Node Address:[[N13]]:multi-instruction257; CHECK-NEXT: Instructions:258; CHECK-NEXT: %4 = mul nsw i64 %i.04, %n259; CHECK-NEXT: %arrayidx10 = getelementptr inbounds float, ptr %a, i64 %4260; CHECK-NEXT: Edges:261; CHECK-NEXT: [def-use] to [[N5]]262 263; CHECK: Node Address:[[N5]]:single-instruction264; CHECK-NEXT: Instructions:265; CHECK-NEXT: %arrayidx11 = getelementptr inbounds float, ptr %arrayidx10, i64 %j.02266; CHECK-NEXT: Edges:267; CHECK-NEXT: [def-use] to [[N17:0x[0-9a-f]*]]268 269; CHECK: Node Address:[[N12]]:multi-instruction270; CHECK-NEXT: Instructions:271; CHECK-NEXT: %2 = mul nsw i64 %i.04, %n272; CHECK-NEXT: %arrayidx6 = getelementptr inbounds float, ptr %a, i64 %2273; CHECK-NEXT: Edges:274; CHECK-NEXT: [def-use] to [[N7]]275 276; CHECK: Node Address:[[N7]]:multi-instruction277; CHECK-NEXT: Instructions:278; CHECK-NEXT: %arrayidx8 = getelementptr inbounds float, ptr %arrayidx6, i64 %add7279; CHECK-NEXT: %3 = load float, ptr %arrayidx8, align 4280; CHECK-NEXT: Edges:281; CHECK-NEXT: [def-use] to [[N20:0x[0-9a-f]*]]282; CHECK-NEXT: [memory] to [[N17]]283 284; CHECK: Node Address:[[N11]]:multi-instruction285; CHECK-NEXT: Instructions:286; CHECK-NEXT: %0 = mul nsw i64 %i.04, %n287; CHECK-NEXT: %arrayidx = getelementptr inbounds float, ptr %b, i64 %0288; CHECK-NEXT: Edges:289; CHECK-NEXT: [def-use] to [[N3]]290 291; CHECK: Node Address:[[N3]]:multi-instruction292; CHECK-NEXT: Instructions:293; CHECK-NEXT: %arrayidx5 = getelementptr inbounds float, ptr %arrayidx, i64 %j.02294; CHECK-NEXT: %1 = load float, ptr %arrayidx5, align 4295; CHECK-NEXT: Edges:296; CHECK-NEXT: [def-use] to [[N20]]297 298; CHECK: Node Address:[[N20]]:single-instruction299; CHECK-NEXT: Instructions:300; CHECK-NEXT: %add = fadd float %1, %3301; CHECK-NEXT: Edges:302; CHECK-NEXT: [def-use] to [[N17]]303 304; CHECK: Node Address:[[N17]]:single-instruction305; CHECK-NEXT: Instructions:306; CHECK-NEXT: store float %add, ptr %arrayidx11, align 4307; CHECK-NEXT: Edges:none!308 309; CHECK: Node Address:[[N23:0x[0-9a-f]*]]:single-instruction310; CHECK-NEXT: Instructions:311; CHECK-NEXT: br label %for.inc12312; CHECK-NEXT: Edges:none!313 314; CHECK: Node Address:[[N24:0x[0-9a-f]*]]:single-instruction315; CHECK-NEXT: Instructions:316; CHECK-NEXT: br label %for.body4317; CHECK-NEXT: Edges:none!318 319; CHECK: Node Address:[[N25:0x[0-9a-f]*]]:single-instruction320; CHECK-NEXT: Instructions:321; CHECK-NEXT: %sub = add i64 %n, -1322; CHECK-NEXT: Edges:323; CHECK-NEXT: [def-use] to [[N6]]324; CHECK-NEXT: [def-use] to [[N26:0x[0-9a-f]*]]325 326; CHECK: Node Address:[[N26]]:multi-instruction327; CHECK-NEXT: Instructions:328; CHECK-NEXT: %cmp21 = icmp ult i64 1, %sub329; CHECK-NEXT: br i1 %cmp21, label %for.body4.preheader, label %for.inc12330; CHECK-NEXT: Edges:none!331 332; CHECK: Node Address:[[N6]]:multi-instruction333; CHECK-NEXT: Instructions:334; CHECK-NEXT: %cmp2 = icmp ult i64 %inc, %sub335; CHECK-NEXT: br i1 %cmp2, label %for.body4, label %for.inc12.loopexit336; CHECK-NEXT: Edges:none!337 338 339;; This test has no cycles.340;; void test2(unsigned long n, float a[][n], float b[][n]) {341;; for (unsigned long i = 0; i < n; i++)342;; for (unsigned long j = 1; j < n-1; j++)343;; a[i][j] = b[i][j] + a[i][j+1];344;; }345 346define void @test2(i64 %n, ptr noalias %a, ptr noalias %b) {347entry:348 %exitcond3 = icmp ne i64 0, %n349 br i1 %exitcond3, label %test2.for.cond1.preheader, label %for.end14350 351test2.for.cond1.preheader: ; preds = %entry, %for.inc12352 %i.04 = phi i64 [ %inc13, %for.inc12 ], [ 0, %entry ]353 %sub = add i64 %n, -1354 %cmp21 = icmp ult i64 1, %sub355 br i1 %cmp21, label %for.body4, label %for.inc12356 357for.body4: ; preds = %test2.for.cond1.preheader, %for.body4358 %j.02 = phi i64 [ %inc, %for.body4 ], [ 1, %test2.for.cond1.preheader ]359 %0 = mul nsw i64 %i.04, %n360 %arrayidx = getelementptr inbounds float, ptr %b, i64 %0361 %arrayidx5 = getelementptr inbounds float, ptr %arrayidx, i64 %j.02362 %1 = load float, ptr %arrayidx5, align 4363 %2 = mul nsw i64 %i.04, %n364 %arrayidx6 = getelementptr inbounds float, ptr %a, i64 %2365 %add7 = add i64 %j.02, 1366 %arrayidx8 = getelementptr inbounds float, ptr %arrayidx6, i64 %add7367 %3 = load float, ptr %arrayidx8, align 4368 %add = fadd float %1, %3369 %4 = mul nsw i64 %i.04, %n370 %arrayidx10 = getelementptr inbounds float, ptr %a, i64 %4371 %arrayidx11 = getelementptr inbounds float, ptr %arrayidx10, i64 %j.02372 store float %add, ptr %arrayidx11, align 4373 %inc = add i64 %j.02, 1374 %cmp2 = icmp ult i64 %inc, %sub375 br i1 %cmp2, label %for.body4, label %for.inc12376 377for.inc12: ; preds = %for.body4, %test2.for.cond1.preheader378 %inc13 = add i64 %i.04, 1379 %exitcond = icmp ne i64 %inc13, %n380 br i1 %exitcond, label %test2.for.cond1.preheader, label %for.end14381 382for.end14: ; preds = %for.inc12, %entry383 ret void384}385