1; RUN: opt %loadPolly -basic-aa -polly-scops -polly-allow-nonaffine-branches \ 2; RUN: -polly-allow-nonaffine-loops=false \ 3; RUN: -analyze < %s | FileCheck %s --check-prefix=INNERMOST 4; RUN: opt %loadPolly -basic-aa -polly-scops -polly-allow-nonaffine-branches \ 5; RUN: -polly-allow-nonaffine-loops=true \ 6; RUN: -analyze < %s | FileCheck %s --check-prefix=INNERMOST 7; RUN: opt %loadPolly -basic-aa -polly-scops -polly-allow-nonaffine \ 8; RUN: -polly-allow-nonaffine-branches -polly-allow-nonaffine-loops=true \ 9; RUN: -analyze < %s | FileCheck %s \ 10; RUN: --check-prefix=ALL 11; 12; Here we have a non-affine loop (in the context of the loop nest) 13; and also a non-affine access (A[k]). While we can always model the 14; innermost loop as a SCoP of depth 1, we can overapproximate the 15; innermost loop in the whole loop nest and model A[k] as a non-affine 16; access. 17; 18; INNERMOST: Function: f 19; INNERMOST-NEXT: Region: %bb15---%bb13 20; INNERMOST-NEXT: Max Loop Depth: 1 21; INNERMOST-NEXT: Invariant Accesses: { 22; INNERMOST-NEXT: } 23; INNERMOST-NEXT: Context: 24; INNERMOST-NEXT: [p_0, p_1, p_2] -> { : 0 <= p_0 <= 1048576 and 0 <= p_1 <= 1024 and 0 <= p_2 <= 1024 } 25; INNERMOST-NEXT: Assumed Context: 26; INNERMOST-NEXT: [p_0, p_1, p_2] -> { : } 27; INNERMOST-NEXT: Invalid Context: 28; INNERMOST-NEXT: [p_0, p_1, p_2] -> { : false } 29; INNERMOST-NEXT: p0: {0,+,{0,+,1}<nuw><nsw><%bb11>}<nuw><nsw><%bb13> 30; INNERMOST-NEXT: p1: {0,+,1}<nuw><nsw><%bb11> 31; INNERMOST-NEXT: p2: {0,+,1}<nuw><nsw><%bb13> 32; INNERMOST-NEXT: Arrays { 33; INNERMOST-NEXT: i32 MemRef_A[*]; // Element size 4 34; INNERMOST-NEXT: i64 MemRef_indvars_iv_next6; // Element size 8 35; INNERMOST-NEXT: i64 MemRef_indvars_iv_next4; // Element size 8 36; INNERMOST-NEXT: } 37; INNERMOST-NEXT: Arrays (Bounds as pw_affs) { 38; INNERMOST-NEXT: i32 MemRef_A[*]; // Element size 4 39; INNERMOST-NEXT: i64 MemRef_indvars_iv_next6; // Element size 8 40; INNERMOST-NEXT: i64 MemRef_indvars_iv_next4; // Element size 8 41; INNERMOST-NEXT: } 42; INNERMOST-NEXT: Alias Groups (0): 43; INNERMOST-NEXT: n/a 44; INNERMOST-NEXT: Statements { 45; INNERMOST-NEXT: Stmt_bb16 46; INNERMOST-NEXT: Domain := 47; INNERMOST-NEXT: [p_0, p_1, p_2] -> { Stmt_bb16[i0] : 0 <= i0 <= 1023 - p_0 }; 48; INNERMOST-NEXT: Schedule := 49; INNERMOST-NEXT: [p_0, p_1, p_2] -> { Stmt_bb16[i0] -> [0, i0] }; 50; INNERMOST-NEXT: ReadAccess := [Reduction Type: NONE] [Scalar: 0] 51; INNERMOST-NEXT: [p_0, p_1, p_2] -> { Stmt_bb16[i0] -> MemRef_A[p_1] }; 52; INNERMOST-NEXT: ReadAccess := [Reduction Type: NONE] [Scalar: 0] 53; INNERMOST-NEXT: [p_0, p_1, p_2] -> { Stmt_bb16[i0] -> MemRef_A[p_2] }; 54; INNERMOST-NEXT: ReadAccess := [Reduction Type: +] [Scalar: 0] 55; INNERMOST-NEXT: [p_0, p_1, p_2] -> { Stmt_bb16[i0] -> MemRef_A[p_0 + i0] }; 56; INNERMOST-NEXT: MustWriteAccess := [Reduction Type: +] [Scalar: 0] 57; INNERMOST-NEXT: [p_0, p_1, p_2] -> { Stmt_bb16[i0] -> MemRef_A[p_0 + i0] }; 58; INNERMOST-NEXT: Stmt_bb26 59; INNERMOST-NEXT: Domain := 60; INNERMOST-NEXT: [p_0, p_1, p_2] -> { Stmt_bb26[] : p_0 <= 1024 }; 61; INNERMOST-NEXT: Schedule := 62; INNERMOST-NEXT: [p_0, p_1, p_2] -> { Stmt_bb26[] -> [1, 0] }; 63; INNERMOST-NEXT: MustWriteAccess := [Reduction Type: NONE] [Scalar: 1] 64; INNERMOST-NEXT: [p_0, p_1, p_2] -> { Stmt_bb26[] -> MemRef_indvars_iv_next6[] }; 65; INNERMOST-NEXT: MustWriteAccess := [Reduction Type: NONE] [Scalar: 1] 66; INNERMOST-NEXT: [p_0, p_1, p_2] -> { Stmt_bb26[] -> MemRef_indvars_iv_next4[] }; 67; INNERMOST-NEXT: } 68 69; ALL: Function: f 70; ALL-NEXT: Region: %bb11---%bb29 71; ALL-NEXT: Max Loop Depth: 2 72; ALL-NEXT: Invariant Accesses: { 73; ALL-NEXT: } 74; ALL-NEXT: Context: 75; ALL-NEXT: { : } 76; ALL-NEXT: Assumed Context: 77; ALL-NEXT: { : } 78; ALL-NEXT: Invalid Context: 79; ALL-NEXT: { : false } 80; ALL-NEXT: Arrays { 81; ALL-NEXT: i32 MemRef_A[*]; // Element size 4 82; ALL-NEXT: } 83; ALL-NEXT: Arrays (Bounds as pw_affs) { 84; ALL-NEXT: i32 MemRef_A[*]; // Element size 4 85; ALL-NEXT: } 86; ALL-NEXT: Alias Groups (0): 87; ALL-NEXT: n/a 88; ALL-NEXT: Statements { 89; ALL-NEXT: Stmt_bb15__TO__bb25 90; ALL-NEXT: Domain := 91; ALL-NEXT: { Stmt_bb15__TO__bb25[i0, i1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 }; 92; ALL-NEXT: Schedule := 93; ALL-NEXT: { Stmt_bb15__TO__bb25[i0, i1] -> [i0, i1] }; 94; ALL-NEXT: ReadAccess := [Reduction Type: NONE] [Scalar: 0] 95; ALL-NEXT: { Stmt_bb15__TO__bb25[i0, i1] -> MemRef_A[i0] }; 96; ALL-NEXT: ReadAccess := [Reduction Type: NONE] [Scalar: 0] 97; ALL-NEXT: { Stmt_bb15__TO__bb25[i0, i1] -> MemRef_A[i1] }; 98; ALL-NEXT: ReadAccess := [Reduction Type: NONE] [Scalar: 0] 99; ALL-NEXT: { Stmt_bb15__TO__bb25[i0, i1] -> MemRef_A[o0] : 0 <= o0 <= 2305843009213693951 }; 100; ALL-NEXT: MayWriteAccess := [Reduction Type: NONE] [Scalar: 0] 101; ALL-NEXT: { Stmt_bb15__TO__bb25[i0, i1] -> MemRef_A[o0] : 0 <= o0 <= 2305843009213693951 }; 102; ALL-NEXT: } 103; 104; void f(int *A) { 105; for (int i = 0; i < 1024; i++) 106; for (int j = 0; j < 1024; j++) 107; for (int k = i *j; k < 1024; k++) 108; A[k] += A[i] + A[j]; 109; } 110; 111target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" 112 113define void @f(i32* %A) { 114bb: 115 br label %bb11 116 117bb11: ; preds = %bb28, %bb 118 %indvars.iv8 = phi i64 [ %indvars.iv.next9, %bb28 ], [ 0, %bb ] 119 %indvars.iv1 = phi i64 [ %indvars.iv.next2, %bb28 ], [ 0, %bb ] 120 %exitcond10 = icmp ne i64 %indvars.iv8, 1024 121 br i1 %exitcond10, label %bb12, label %bb29 122 123bb12: ; preds = %bb11 124 br label %bb13 125 126bb13: ; preds = %bb26, %bb12 127 %indvars.iv5 = phi i64 [ %indvars.iv.next6, %bb26 ], [ 0, %bb12 ] 128 %indvars.iv3 = phi i64 [ %indvars.iv.next4, %bb26 ], [ 0, %bb12 ] 129 %exitcond7 = icmp ne i64 %indvars.iv5, 1024 130 br i1 %exitcond7, label %bb14, label %bb27 131 132bb14: ; preds = %bb13 133 br label %bb15 134 135bb15: ; preds = %bb24, %bb14 136 %indvars.iv = phi i64 [ %indvars.iv.next, %bb24 ], [ %indvars.iv3, %bb14 ] 137 %exitcond = icmp ne i64 %indvars.iv, 1024 138 br i1 %exitcond, label %bb16, label %bb25 139 140bb16: ; preds = %bb15 141 %tmp = getelementptr inbounds i32, i32* %A, i64 %indvars.iv8 142 %tmp17 = load i32, i32* %tmp, align 4 143 %tmp18 = getelementptr inbounds i32, i32* %A, i64 %indvars.iv5 144 %tmp19 = load i32, i32* %tmp18, align 4 145 %tmp20 = add nsw i32 %tmp17, %tmp19 146 %tmp21 = getelementptr inbounds i32, i32* %A, i64 %indvars.iv 147 %tmp22 = load i32, i32* %tmp21, align 4 148 %tmp23 = add nsw i32 %tmp22, %tmp20 149 store i32 %tmp23, i32* %tmp21, align 4 150 br label %bb24 151 152bb24: ; preds = %bb16 153 %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1 154 br label %bb15 155 156bb25: ; preds = %bb15 157 br label %bb26 158 159bb26: ; preds = %bb25 160 %indvars.iv.next6 = add nuw nsw i64 %indvars.iv5, 1 161 %indvars.iv.next4 = add nuw nsw i64 %indvars.iv3, %indvars.iv1 162 br label %bb13 163 164bb27: ; preds = %bb13 165 br label %bb28 166 167bb28: ; preds = %bb27 168 %indvars.iv.next9 = add nuw nsw i64 %indvars.iv8, 1 169 %indvars.iv.next2 = add nuw nsw i64 %indvars.iv1, 1 170 br label %bb11 171 172bb29: ; preds = %bb11 173 ret void 174} 175