169 lines · plain
1; RUN: opt %loadNPMPolly -aa-pipeline=basic-aa -polly-allow-nonaffine-branches -polly-allow-nonaffine-loops=false '-passes=polly-custom<scops>' -polly-print-scops -disable-output < %s 2>&1 | FileCheck %s --check-prefix=INNERMOST2; RUN: opt %loadNPMPolly -aa-pipeline=basic-aa -polly-allow-nonaffine-branches -polly-allow-nonaffine-loops=true '-passes=polly-custom<scops>' -polly-print-scops -disable-output < %s 2>&1 | FileCheck %s --check-prefix=INNERMOST3; RUN: opt %loadNPMPolly -aa-pipeline=basic-aa -polly-allow-nonaffine-branches -polly-allow-nonaffine-loops=true -polly-allow-nonaffine '-passes=polly-custom<scops>' -polly-print-scops -disable-output < %s 2>&1 | FileCheck %s --check-prefix=ALL4;5; Here we have a non-affine loop (in the context of the loop nest)6; and also a non-affine access (A[k]). While we can always model the7; innermost loop as a SCoP of depth 1, we can overapproximate the8; innermost loop in the whole loop nest and model A[k] as a non-affine9; access.10;11; INNERMOST: Function: f12; INNERMOST-NEXT: Region: %bb15---%bb1313; INNERMOST-NEXT: Max Loop Depth: 114; INNERMOST-NEXT: Invariant Accesses: {15; INNERMOST-NEXT: }16; INNERMOST-NEXT: Context:17; INNERMOST-NEXT: [p_0, p_1, p_2] -> { : 0 <= p_0 <= 1048576 and 0 <= p_1 <= 1024 and 0 <= p_2 <= 1024 }18; INNERMOST-NEXT: Assumed Context:19; INNERMOST-NEXT: [p_0, p_1, p_2] -> { : }20; INNERMOST-NEXT: Invalid Context:21; INNERMOST-NEXT: [p_0, p_1, p_2] -> { : false }22; INNERMOST: p0: {0,+,{0,+,1}<nuw><nsw><%bb11>}<nuw><nsw><%bb13>23; INNERMOST-NEXT: p1: {0,+,1}<nuw><nsw><%bb11>24; INNERMOST-NEXT: p2: {0,+,1}<nuw><nsw><%bb13>25; INNERMOST-NEXT: Arrays {26; INNERMOST-NEXT: i32 MemRef_A[*]; // Element size 427; INNERMOST-NEXT: i64 MemRef_indvars_iv_next6; // Element size 828; INNERMOST-NEXT: i32 MemRef_indvars_iv_next4; // Element size 429; INNERMOST-NEXT: }30; INNERMOST-NEXT: Arrays (Bounds as pw_affs) {31; INNERMOST-NEXT: i32 MemRef_A[*]; // Element size 432; INNERMOST-NEXT: i64 MemRef_indvars_iv_next6; // Element size 833; INNERMOST-NEXT: i32 MemRef_indvars_iv_next4; // Element size 434; INNERMOST-NEXT: }35; INNERMOST-NEXT: Alias Groups (0):36; INNERMOST-NEXT: n/a37; INNERMOST-NEXT: Statements {38; INNERMOST-NEXT: Stmt_bb1639; INNERMOST-NEXT: Domain :=40; INNERMOST-NEXT: [p_0, p_1, p_2] -> { Stmt_bb16[i0] : 0 <= i0 < p_0 };41; INNERMOST-NEXT: Schedule :=42; INNERMOST-NEXT: [p_0, p_1, p_2] -> { Stmt_bb16[i0] -> [0, i0] };43; INNERMOST-NEXT: ReadAccess := [Reduction Type: NONE] [Scalar: 0]44; INNERMOST-NEXT: [p_0, p_1, p_2] -> { Stmt_bb16[i0] -> MemRef_A[p_1] };45; INNERMOST-NEXT: ReadAccess := [Reduction Type: NONE] [Scalar: 0]46; INNERMOST-NEXT: [p_0, p_1, p_2] -> { Stmt_bb16[i0] -> MemRef_A[p_2] };47; INNERMOST-NEXT: ReadAccess := [Reduction Type: NONE] [Scalar: 0]48; INNERMOST-NEXT: [p_0, p_1, p_2] -> { Stmt_bb16[i0] -> MemRef_A[i0] };49; INNERMOST-NEXT: MustWriteAccess := [Reduction Type: NONE] [Scalar: 0]50; INNERMOST-NEXT: [p_0, p_1, p_2] -> { Stmt_bb16[i0] -> MemRef_A[i0] };51; INNERMOST-NEXT: Stmt_bb2652; INNERMOST-NEXT: Domain :=53; INNERMOST-NEXT: [p_0, p_1, p_2] -> { Stmt_bb26[] };54; INNERMOST-NEXT: Schedule :=55; INNERMOST-NEXT: [p_0, p_1, p_2] -> { Stmt_bb26[] -> [1, 0] };56; INNERMOST-NEXT: MustWriteAccess := [Reduction Type: NONE] [Scalar: 1]57; INNERMOST-NEXT: [p_0, p_1, p_2] -> { Stmt_bb26[] -> MemRef_indvars_iv_next6[] };58; INNERMOST-NEXT: MustWriteAccess := [Reduction Type: NONE] [Scalar: 1]59; INNERMOST-NEXT: [p_0, p_1, p_2] -> { Stmt_bb26[] -> MemRef_indvars_iv_next4[] };60; INNERMOST-NEXT: }61 62; ALL: Function: f63; ALL-NEXT: Region: %bb11---%bb2964; ALL-NEXT: Max Loop Depth: 265; ALL-NEXT: Invariant Accesses: {66; ALL-NEXT: }67; ALL-NEXT: Context:68; ALL-NEXT: { : }69; ALL-NEXT: Assumed Context:70; ALL-NEXT: { : }71; ALL-NEXT: Invalid Context:72; ALL-NEXT: { : false }73; ALL: Arrays {74; ALL-NEXT: i32 MemRef_A[*]; // Element size 475; ALL-NEXT: }76; ALL-NEXT: Arrays (Bounds as pw_affs) {77; ALL-NEXT: i32 MemRef_A[*]; // Element size 478; ALL-NEXT: }79; ALL-NEXT: Alias Groups (0):80; ALL-NEXT: n/a81; ALL-NEXT: Statements {82; ALL-NEXT: Stmt_bb15__TO__bb2583; ALL-NEXT: Domain :=84; ALL-NEXT: { Stmt_bb15__TO__bb25[i0, i1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 };85; ALL-NEXT: Schedule :=86; ALL-NEXT: { Stmt_bb15__TO__bb25[i0, i1] -> [i0, i1] };87; ALL-NEXT: ReadAccess := [Reduction Type: NONE] [Scalar: 0]88; ALL-NEXT: { Stmt_bb15__TO__bb25[i0, i1] -> MemRef_A[i0] };89; ALL-NEXT: ReadAccess := [Reduction Type: NONE] [Scalar: 0]90; ALL-NEXT: { Stmt_bb15__TO__bb25[i0, i1] -> MemRef_A[i1] };91; ALL-NEXT: ReadAccess := [Reduction Type: NONE] [Scalar: 0]92; ALL-NEXT: { Stmt_bb15__TO__bb25[i0, i1] -> MemRef_A[o0] : 0 <= o0 <= 1048576 };93; ALL-NEXT: MayWriteAccess := [Reduction Type: NONE] [Scalar: 0]94; ALL-NEXT: { Stmt_bb15__TO__bb25[i0, i1] -> MemRef_A[o0] : 0 <= o0 <= 1048576 };95; ALL-NEXT: }96;97; void f(int *A) {98; for (int i = 0; i < 1024; i++)99; for (int j = 0; j < 1024; j++)100; for (int k = 0; k < i * j; k++)101; A[k] += A[i] + A[j];102; }103;104target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"105 106define void @f(ptr %A) {107bb:108 br label %bb11109 110bb11: ; preds = %bb28, %bb111 %indvars.iv8 = phi i64 [ %indvars.iv.next9, %bb28 ], [ 0, %bb ]112 %indvars.iv1 = phi i32 [ %indvars.iv.next2, %bb28 ], [ 0, %bb ]113 %exitcond10 = icmp ne i64 %indvars.iv8, 1024114 br i1 %exitcond10, label %bb12, label %bb29115 116bb12: ; preds = %bb11117 br label %bb13118 119bb13: ; preds = %bb26, %bb12120 %indvars.iv5 = phi i64 [ %indvars.iv.next6, %bb26 ], [ 0, %bb12 ]121 %indvars.iv3 = phi i32 [ %indvars.iv.next4, %bb26 ], [ 0, %bb12 ]122 %exitcond7 = icmp ne i64 %indvars.iv5, 1024123 br i1 %exitcond7, label %bb14, label %bb27124 125bb14: ; preds = %bb13126 br label %bb15127 128bb15: ; preds = %bb24, %bb14129 %indvars.iv = phi i64 [ %indvars.iv.next, %bb24 ], [ 0, %bb14 ]130 %lftr.wideiv = trunc i64 %indvars.iv to i32131 %exitcond = icmp ne i32 %lftr.wideiv, %indvars.iv3132 br i1 %exitcond, label %bb16, label %bb25133 134bb16: ; preds = %bb15135 %tmp = getelementptr inbounds i32, ptr %A, i64 %indvars.iv8136 %tmp17 = load i32, ptr %tmp, align 4137 %tmp18 = getelementptr inbounds i32, ptr %A, i64 %indvars.iv5138 %tmp19 = load i32, ptr %tmp18, align 4139 %tmp20 = add nsw i32 %tmp17, %tmp19140 %tmp21 = getelementptr inbounds i32, ptr %A, i64 %indvars.iv141 %tmp22 = load i32, ptr %tmp21, align 4142 %tmp23 = add nsw i32 %tmp22, %tmp20143 store i32 %tmp23, ptr %tmp21, align 4144 br label %bb24145 146bb24: ; preds = %bb16147 %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1148 br label %bb15149 150bb25: ; preds = %bb15151 br label %bb26152 153bb26: ; preds = %bb25154 %indvars.iv.next6 = add nuw nsw i64 %indvars.iv5, 1155 %indvars.iv.next4 = add nuw nsw i32 %indvars.iv3, %indvars.iv1156 br label %bb13157 158bb27: ; preds = %bb13159 br label %bb28160 161bb28: ; preds = %bb27162 %indvars.iv.next9 = add nuw nsw i64 %indvars.iv8, 1163 %indvars.iv.next2 = add nuw nsw i32 %indvars.iv1, 1164 br label %bb11165 166bb29: ; preds = %bb11167 ret void168}169