538 lines · plain
1; NOTE: Assertions have been autogenerated by utils/update_analyze_test_checks.py UTC_ARGS: --version 52; RUN: opt < %s -passes='print<delinearization>' -disable-output -delinearize-use-fixed-size-array-heuristic 2>&1 | FileCheck %s3 4; void f(int A[][8][32]) {5; for (i = 0; i < 42; i++)6; for (j = 0; j < 8; j++)7; for (k = 0; k < 32; k++)8; A[i][j][k] = 1;9; }10 11define void @a_i_j_k(ptr %a) {12; CHECK-LABEL: 'a_i_j_k'13; CHECK-NEXT: Inst: store i32 1, ptr %idx, align 414; CHECK-NEXT: AccessFunction: {{\{\{\{}}0,+,1024}<nuw><nsw><%for.i.header>,+,128}<nw><%for.j.header>,+,4}<nw><%for.k>15; CHECK-NEXT: Base offset: %a16; CHECK-NEXT: ArrayDecl[UnknownSize][8][32] with elements of 4 bytes.17; CHECK-NEXT: ArrayRef[{0,+,1}<nuw><nsw><%for.i.header>][{0,+,1}<nuw><nsw><%for.j.header>][{0,+,1}<nuw><nsw><%for.k>]18; CHECK-NEXT: Delinearization validation: Succeeded19;20entry:21 br label %for.i.header22 23for.i.header:24 %i = phi i32 [ 0, %entry ], [ %i.inc, %for.i.latch ]25 br label %for.j.header26 27for.j.header:28 %j = phi i32 [ 0, %for.i.header ], [ %j.inc, %for.j.latch ]29 br label %for.k30 31for.k:32 %k = phi i32 [ 0, %for.j.header ], [ %k.inc, %for.k ]33 %idx = getelementptr [8 x [32 x i32]], ptr %a, i32 %i, i32 %j, i32 %k34 store i32 1, ptr %idx35 %k.inc = add i32 %k, 136 %cmp.k = icmp slt i32 %k.inc, 3237 br i1 %cmp.k, label %for.k, label %for.j.latch38 39for.j.latch:40 %j.inc = add i32 %j, 141 %cmp.j = icmp slt i32 %j.inc, 842 br i1 %cmp.j, label %for.j.header, label %for.i.latch43 44for.i.latch:45 %i.inc = add i32 %i, 146 %cmp.i = icmp slt i32 %i.inc, 4247 br i1 %cmp.i, label %for.i.header, label %exit48 49exit:50 ret void51}52 53; void f(int A[][8][32]) {54; for (i = 0; i < 42; i++)55; for (j = 0; j < 8; j++)56; for (k = 0; k < 32; k++)57; A[i][7-j][k] = 1;58; }59 60define void @a_i_nj_k(ptr %a) {61; CHECK-LABEL: 'a_i_nj_k'62; CHECK-NEXT: Inst: store i32 1, ptr %idx, align 463; CHECK-NEXT: AccessFunction: {{\{\{\{}}896,+,1024}<nuw><nsw><%for.i.header>,+,-128}<nw><%for.j.header>,+,4}<nw><%for.k>64; CHECK-NEXT: Base offset: %a65; CHECK-NEXT: ArrayDecl[UnknownSize][8][32] with elements of 4 bytes.66; CHECK-NEXT: ArrayRef[{0,+,1}<nuw><nsw><%for.i.header>][{7,+,-1}<nsw><%for.j.header>][{0,+,1}<nuw><nsw><%for.k>]67; CHECK-NEXT: Delinearization validation: Succeeded68;69entry:70 br label %for.i.header71 72for.i.header:73 %i = phi i32 [ 0, %entry ], [ %i.inc, %for.i.latch ]74 br label %for.j.header75 76for.j.header:77 %j = phi i32 [ 0, %for.i.header ], [ %j.inc, %for.j.latch ]78 %j.subscript = sub i32 7, %j79 br label %for.k80 81for.k:82 %k = phi i32 [ 0, %for.j.header ], [ %k.inc, %for.k ]83 %idx = getelementptr [8 x [32 x i32]], ptr %a, i32 %i, i32 %j.subscript, i32 %k84 store i32 1, ptr %idx85 %k.inc = add i32 %k, 186 %cmp.k = icmp slt i32 %k.inc, 3287 br i1 %cmp.k, label %for.k, label %for.j.latch88 89for.j.latch:90 %j.inc = add i32 %j, 191 %cmp.j = icmp slt i32 %j.inc, 892 br i1 %cmp.j, label %for.j.header, label %for.i.latch93 94for.i.latch:95 %i.inc = add i32 %i, 196 %cmp.i = icmp slt i32 %i.inc, 4297 br i1 %cmp.i, label %for.i.header, label %exit98 99exit:100 ret void101}102 103; In the following code, the access functions for both stores are represented104; in the same way in SCEV, so the delinearization results are also the same. We105; don't have any type information of the underlying objects.106;107; void f(int A[][4][64], int B[][8][32]) {108; for (i = 0; i < 42; i++)109; for (j = 0; j < 4; j++)110; for (k = 0; k < 32; k++) {111; A[i][j][k] = 1;112; B[i][2*j][k] = 1;113; }114; }115 116define void @a_ijk_b_i2jk(ptr %a, ptr %b) {117; CHECK-LABEL: 'a_ijk_b_i2jk'118; CHECK-NEXT: Inst: store i32 1, ptr %a.idx, align 4119; CHECK-NEXT: AccessFunction: {{\{\{\{}}0,+,1024}<nuw><nsw><%for.i.header>,+,256}<nw><%for.j.header>,+,4}<nw><%for.k>120; CHECK-NEXT: Base offset: %a121; CHECK-NEXT: ArrayDecl[UnknownSize][4][64] with elements of 4 bytes.122; CHECK-NEXT: ArrayRef[{0,+,1}<nuw><nsw><%for.i.header>][{0,+,1}<nuw><nsw><%for.j.header>][{0,+,1}<nuw><nsw><%for.k>]123; CHECK-NEXT: Delinearization validation: Succeeded124; CHECK-EMPTY:125; CHECK-NEXT: Inst: store i32 1, ptr %b.idx, align 4126; CHECK-NEXT: AccessFunction: {{\{\{\{}}0,+,1024}<nuw><nsw><%for.i.header>,+,256}<nw><%for.j.header>,+,4}<nw><%for.k>127; CHECK-NEXT: Base offset: %b128; CHECK-NEXT: ArrayDecl[UnknownSize][4][64] with elements of 4 bytes.129; CHECK-NEXT: ArrayRef[{0,+,1}<nuw><nsw><%for.i.header>][{0,+,1}<nuw><nsw><%for.j.header>][{0,+,1}<nuw><nsw><%for.k>]130; CHECK-NEXT: Delinearization validation: Succeeded131;132entry:133 br label %for.i.header134 135for.i.header:136 %i = phi i32 [ 0, %entry ], [ %i.inc, %for.i.latch ]137 br label %for.j.header138 139for.j.header:140 %j = phi i32 [ 0, %for.i.header ], [ %j.inc, %for.j.latch ]141 %j2 = shl i32 %j, 1142 br label %for.k143 144for.k:145 %k = phi i32 [ 0, %for.j.header ], [ %k.inc, %for.k ]146 %a.idx = getelementptr [4 x [64 x i32]], ptr %a, i32 %i, i32 %j, i32 %k147 %b.idx = getelementptr [8 x [32 x i32]], ptr %b, i32 %i, i32 %j2, i32 %k148 store i32 1, ptr %a.idx149 store i32 1, ptr %b.idx150 %k.inc = add i32 %k, 1151 %cmp.k = icmp slt i32 %k.inc, 32152 br i1 %cmp.k, label %for.k, label %for.j.latch153 154for.j.latch:155 %j.inc = add i32 %j, 1156 %cmp.j = icmp slt i32 %j.inc, 4157 br i1 %cmp.j, label %for.j.header, label %for.i.latch158 159for.i.latch:160 %i.inc = add i32 %i, 1161 %cmp.i = icmp slt i32 %i.inc, 42162 br i1 %cmp.i, label %for.i.header, label %exit163 164exit:165 ret void166}167 168; The type information of the underlying object is not available, so the169; delinearization result is different from the original array size. In this170; case, the underlying object is a type of int[][8][32], but the171; delinearization result is like int[][4][64].172;173; void f(int A[][8][32]) {174; for (i = 0; i < 42; i++)175; for (j = 0; j < 3; j++)176; for (k = 0; k < 32; k++)177; A[i][2*j+1][k] = 1;178; }179 180define void @a_i_2j1_k(ptr %a) {181; CHECK-LABEL: 'a_i_2j1_k'182; CHECK-NEXT: Inst: store i32 1, ptr %idx, align 4183; CHECK-NEXT: AccessFunction: {{\{\{\{}}128,+,1024}<nuw><nsw><%for.i.header>,+,256}<nw><%for.j.header>,+,4}<nw><%for.k>184; CHECK-NEXT: Base offset: %a185; CHECK-NEXT: ArrayDecl[UnknownSize][4][64] with elements of 4 bytes.186; CHECK-NEXT: ArrayRef[{0,+,1}<nuw><nsw><%for.i.header>][{0,+,1}<nuw><%for.j.header>][{32,+,1}<nw><%for.k>]187; CHECK-NEXT: Delinearization validation: Succeeded188;189entry:190 br label %for.i.header191 192for.i.header:193 %i = phi i32 [ 0, %entry ], [ %i.inc, %for.i.latch ]194 br label %for.j.header195 196for.j.header:197 %j = phi i32 [ 0, %for.i.header ], [ %j.inc, %for.j.latch ]198 %j2 = shl i32 %j, 1199 %j.subscript = add i32 %j2, 1200 br label %for.k201 202for.k:203 %k = phi i32 [ 0, %for.j.header ], [ %k.inc, %for.k ]204 %idx = getelementptr [8 x [32 x i32]], ptr %a, i32 %i, i32 %j.subscript, i32 %k205 store i32 1, ptr %idx206 %k.inc = add i32 %k, 1207 %cmp.k = icmp slt i32 %k.inc, 32208 br i1 %cmp.k, label %for.k, label %for.j.latch209 210for.j.latch:211 %j.inc = add i32 %j, 1212 %cmp.j = icmp slt i32 %j.inc, 3213 br i1 %cmp.j, label %for.j.header, label %for.i.latch214 215for.i.latch:216 %i.inc = add i32 %i, 1217 %cmp.i = icmp slt i32 %i.inc, 42218 br i1 %cmp.i, label %for.i.header, label %exit219 220exit:221 ret void222}223 224; Fail to delinearize because the step recurrence value of the i-loop is not225; divisible by that of the j-loop.226;227; void f(int A[][8][32]) {228; for (i = 0; i < 42; i++)229; for (j = 0; j < 2; j++)230; for (k = 0; k < 42; k++)231; A[i][3*j][k] = 1;232; }233 234define void @a_i_3j_k(ptr %a) {235; CHECK-LABEL: 'a_i_3j_k'236; CHECK-NEXT: Inst: store i32 1, ptr %idx, align 4237; CHECK-NEXT: AccessFunction: {{\{\{\{}}0,+,1024}<nuw><nsw><%for.i.header>,+,384}<nw><%for.j.header>,+,4}<nw><%for.k>238; CHECK-NEXT: failed to delinearize239;240entry:241 br label %for.i.header242 243for.i.header:244 %i = phi i32 [ 0, %entry ], [ %i.inc, %for.i.latch ]245 br label %for.j.header246 247for.j.header:248 %j = phi i32 [ 0, %for.i.header ], [ %j.inc, %for.j.latch ]249 %j.subscript = mul i32 %j, 3250 br label %for.k251 252for.k:253 %k = phi i32 [ 0, %for.j.header ], [ %k.inc, %for.k ]254 %idx = getelementptr [8 x [32 x i32]], ptr %a, i32 %i, i32 %j.subscript, i32 %k255 store i32 1, ptr %idx256 %k.inc = add i32 %k, 1257 %cmp.k = icmp slt i32 %k.inc, 42258 br i1 %cmp.k, label %for.k, label %for.j.latch259 260for.j.latch:261 %j.inc = add i32 %j, 1262 %cmp.j = icmp slt i32 %j.inc, 2263 br i1 %cmp.j, label %for.j.header, label %for.i.latch264 265for.i.latch:266 %i.inc = add i32 %i, 1267 %cmp.i = icmp slt i32 %i.inc, 42268 br i1 %cmp.i, label %for.i.header, label %exit269 270exit:271 ret void272}273 274; Although the step recurrence value of j-loop is not divisible by that of the275; k-loop, delinearization is possible because we know that the "actual" stride276; width for the last dimension is 4 instead of 12.277;278; void f(int A[][8][32]) {279; for (i = 0; i < 42; i++)280; for (j = 0; j < 8; j++)281; for (k = 0; k < 10; k++)282; A[i][j][3*k] = 1;283; }284 285define void @a_i_j_3k(ptr %a) {286; CHECK-LABEL: 'a_i_j_3k'287; CHECK-NEXT: Inst: store i32 1, ptr %idx, align 4288; CHECK-NEXT: AccessFunction: {{\{\{\{}}0,+,1024}<nuw><nsw><%for.i.header>,+,128}<nw><%for.j.header>,+,12}<nw><%for.k>289; CHECK-NEXT: Base offset: %a290; CHECK-NEXT: ArrayDecl[UnknownSize][8][32] with elements of 4 bytes.291; CHECK-NEXT: ArrayRef[{0,+,1}<nuw><nsw><%for.i.header>][{0,+,1}<nuw><nsw><%for.j.header>][{0,+,3}<nuw><nsw><%for.k>]292; CHECK-NEXT: Delinearization validation: Succeeded293;294entry:295 br label %for.i.header296 297for.i.header:298 %i = phi i32 [ 0, %entry ], [ %i.inc, %for.i.latch ]299 br label %for.j.header300 301for.j.header:302 %j = phi i32 [ 0, %for.i.header ], [ %j.inc, %for.j.latch ]303 br label %for.k304 305for.k:306 %k = phi i32 [ 0, %for.j.header ], [ %k.inc, %for.k ]307 %k.subscript = mul i32 %k, 3308 %idx = getelementptr [8 x [32 x i32]], ptr %a, i32 %i, i32 %j, i32 %k.subscript309 store i32 1, ptr %idx310 %k.inc = add i32 %k, 1311 %cmp.k = icmp slt i32 %k.inc, 10312 br i1 %cmp.k, label %for.k, label %for.j.latch313 314for.j.latch:315 %j.inc = add i32 %j, 1316 %cmp.j = icmp slt i32 %j.inc, 8317 br i1 %cmp.j, label %for.j.header, label %for.i.latch318 319for.i.latch:320 %i.inc = add i32 %i, 1321 %cmp.i = icmp slt i32 %i.inc, 42322 br i1 %cmp.i, label %for.i.header, label %exit323 324exit:325 ret void326}327 328; Fail to delinearize because i is used in multiple subscripts that are not adjacent.329;330; void f(int A[][8][32]) {331; for (i = 0; i < 32; i++)332; for (j = 0; j < 2; j++)333; for (k = 0; k < 4; k++)334; A[i][2*j+k][i] = 1;335; }336 337define void @a_i_j2k_i(ptr %a) {338; CHECK-LABEL: 'a_i_j2k_i'339; CHECK-NEXT: Inst: store i32 1, ptr %idx, align 4340; CHECK-NEXT: AccessFunction: {{\{\{\{}}0,+,1028}<%for.i.header>,+,256}<nw><%for.j.header>,+,128}<nw><%for.k>341; CHECK-NEXT: failed to delinearize342;343entry:344 br label %for.i.header345 346for.i.header:347 %i = phi i32 [ 0, %entry ], [ %i.inc, %for.i.latch ]348 br label %for.j.header349 350for.j.header:351 %j = phi i32 [ 0, %for.i.header ], [ %j.inc, %for.j.latch ]352 br label %for.k353 354for.k:355 %k = phi i32 [ 0, %for.j.header ], [ %k.inc, %for.k ]356 %j2 = shl i32 %j, 1357 %j2.k = add i32 %j2, %k358 %idx = getelementptr [8 x [32 x i32]], ptr %a, i32 %i, i32 %j2.k, i32 %i359 store i32 1, ptr %idx360 %k.inc = add i32 %k, 1361 %cmp.k = icmp slt i32 %k.inc, 4362 br i1 %cmp.k, label %for.k, label %for.j.latch363 364for.j.latch:365 %j.inc = add i32 %j, 1366 %cmp.j = icmp slt i32 %j.inc, 2367 br i1 %cmp.j, label %for.j.header, label %for.i.latch368 369for.i.latch:370 %i.inc = add i32 %i, 1371 %cmp.i = icmp slt i32 %i.inc, 32372 br i1 %cmp.i, label %for.i.header, label %exit373 374exit:375 ret void376}377 378; Can delinearize, but the result is different from the original array size. In379; this case, the outermost two dimensions are melded into one.380;381; void f(int A[][8][32]) {382; for (i = 0; i < 8; i++)383; for (j = 0; j < 10; j++)384; for (k = 0; k < 10; k++)385; A[i][i][j+k] = 1;386; }387 388define void @a_i_i_jk(ptr %a) {389; CHECK-LABEL: 'a_i_i_jk'390; CHECK-NEXT: Inst: store i32 1, ptr %idx, align 4391; CHECK-NEXT: AccessFunction: {{\{\{\{}}0,+,1152}<%for.i.header>,+,4}<nw><%for.j.header>,+,4}<nw><%for.k>392; CHECK-NEXT: Base offset: %a393; CHECK-NEXT: ArrayDecl[UnknownSize][288] with elements of 4 bytes.394; CHECK-NEXT: ArrayRef[{0,+,1}<nuw><nsw><%for.i.header>][{{\{\{}}0,+,1}<nuw><nsw><%for.j.header>,+,1}<nuw><nsw><%for.k>]395; CHECK-NEXT: Delinearization validation: Succeeded396;397entry:398 br label %for.i.header399 400for.i.header:401 %i = phi i32 [ 0, %entry ], [ %i.inc, %for.i.latch ]402 br label %for.j.header403 404for.j.header:405 %j = phi i32 [ 0, %for.i.header ], [ %j.inc, %for.j.latch ]406 br label %for.k407 408for.k:409 %k = phi i32 [ 0, %for.j.header ], [ %k.inc, %for.k ]410 %jk = add i32 %j, %k411 %idx = getelementptr [8 x [32 x i32]], ptr %a, i32 %i, i32 %i, i32 %jk412 store i32 1, ptr %idx413 %k.inc = add i32 %k, 1414 %cmp.k = icmp slt i32 %k.inc, 10415 br i1 %cmp.k, label %for.k, label %for.j.latch416 417for.j.latch:418 %j.inc = add i32 %j, 1419 %cmp.j = icmp slt i32 %j.inc, 10420 br i1 %cmp.j, label %for.j.header, label %for.i.latch421 422for.i.latch:423 %i.inc = add i32 %i, 1424 %cmp.i = icmp slt i32 %i.inc, 8425 br i1 %cmp.i, label %for.i.header, label %exit426 427exit:428 ret void429}430 431; void f(int A[][8][32]) {432; for (i = 0; i < 8; i++)433; for (j = 0; j < 4; j++)434; for (k = 0; k < 4; k++)435; for (l = 0; l < 32; l++)436; A[i][j+k][l] = 1;437; }438 439define void @a_i_jk_l(ptr %a) {440; CHECK-LABEL: 'a_i_jk_l'441; CHECK-NEXT: Inst: store i32 1, ptr %idx, align 4442; CHECK-NEXT: AccessFunction: {{\{\{\{\{}}0,+,1024}<nuw><nsw><%for.i.header>,+,128}<nw><%for.j.header>,+,128}<nw><%for.k.header>,+,4}<nw><%for.l>443; CHECK-NEXT: Base offset: %a444; CHECK-NEXT: ArrayDecl[UnknownSize][8][32] with elements of 4 bytes.445; CHECK-NEXT: ArrayRef[{0,+,1}<nuw><nsw><%for.i.header>][{{\{\{}}0,+,1}<nuw><nsw><%for.j.header>,+,1}<nuw><nsw><%for.k.header>][{0,+,1}<nuw><nsw><%for.l>]446; CHECK-NEXT: Delinearization validation: Succeeded447;448entry:449 br label %for.i.header450 451for.i.header:452 %i = phi i32 [ 0, %entry ], [ %i.inc, %for.i.latch ]453 br label %for.j.header454 455for.j.header:456 %j = phi i32 [ 0, %for.i.header ], [ %j.inc, %for.j.latch ]457 br label %for.k.header458 459for.k.header:460 %k = phi i32 [ 0, %for.j.header ], [ %k.inc, %for.k.latch ]461 %jk = add i32 %j, %k462 br label %for.l463 464for.l:465 %l = phi i32 [ 0, %for.k.header ], [ %l.inc, %for.l ]466 %idx = getelementptr [8 x [32 x i32]], ptr %a, i32 %i, i32 %jk, i32 %l467 store i32 1, ptr %idx468 %l.inc = add i32 %l, 1469 %cmp.l = icmp slt i32 %l.inc, 32470 br i1 %cmp.l, label %for.l, label %for.k.latch471 472for.k.latch:473 %k.inc = add i32 %k, 1474 %cmp.k = icmp slt i32 %k.inc, 4475 br i1 %cmp.k, label %for.k.header, label %for.j.latch476 477for.j.latch:478 %j.inc = add i32 %j, 1479 %cmp.j = icmp slt i32 %j.inc, 4480 br i1 %cmp.j, label %for.j.header, label %for.i.latch481 482for.i.latch:483 %i.inc = add i32 %i, 1484 %cmp.i = icmp slt i32 %i.inc, 8485 br i1 %cmp.i, label %for.i.header, label %exit486 487exit:488 ret void489}490 491; Reject if the address is not a multiple of the element size.492;493; void f(int *A) {494; for (i = 0; i < 42; i++)495; for (j = 0; j < 8; j++)496; for (k = 0; k < 32; k++)497; *((int *)((char *)A + i*256 + j*32 + k)) = 1;498; }499 500define void @non_divisible_by_element_size(ptr %a) {501; CHECK-LABEL: 'non_divisible_by_element_size'502; CHECK-NEXT: Inst: store i32 1, ptr %idx, align 4503; CHECK-NEXT: AccessFunction: {{\{\{\{}}0,+,256}<nuw><nsw><%for.i.header>,+,32}<nw><%for.j.header>,+,1}<nw><%for.k>504; CHECK-NEXT: failed to delinearize505;506entry:507 br label %for.i.header508 509for.i.header:510 %i = phi i32 [ 0, %entry ], [ %i.inc, %for.i.latch ]511 br label %for.j.header512 513for.j.header:514 %j = phi i32 [ 0, %for.i.header ], [ %j.inc, %for.j.latch ]515 br label %for.k516 517for.k:518 %k = phi i32 [ 0, %for.j.header ], [ %k.inc, %for.k ]519 %idx = getelementptr [8 x [32 x i8]], ptr %a, i32 %i, i32 %j, i32 %k520 store i32 1, ptr %idx521 %k.inc = add i32 %k, 1522 %cmp.k = icmp slt i32 %k.inc, 32523 br i1 %cmp.k, label %for.k, label %for.j.latch524 525for.j.latch:526 %j.inc = add i32 %j, 1527 %cmp.j = icmp slt i32 %j.inc, 8528 br i1 %cmp.j, label %for.j.header, label %for.i.latch529 530for.i.latch:531 %i.inc = add i32 %i, 1532 %cmp.i = icmp slt i32 %i.inc, 42533 br i1 %cmp.i, label %for.i.header, label %exit534 535exit:536 ret void537}538