198 lines · plain
1; REQUIRES: asserts2; RUN: opt < %s -passes=loop-interchange -verify-dom-info -verify-loop-info \3; RUN: -disable-output -debug 2>&1 | FileCheck %s4 5@a = dso_local global [256 x [256 x float]] zeroinitializer, align 46@b = dso_local global [20 x [20 x [20 x i32]]] zeroinitializer, align 47 8;; for (int n = 0; n < 100; ++n)9;; for (int i = 0; i < 256; ++i)10;; for (int j = 1; j < 256; ++j)11;; a[j - 1][i] += a[j][i];12;;13;; The direction vector of `a` is [* = <]. We can interchange the innermost14;; two loops, The direction vector after interchanging will be [* < =].15 16; CHECK: Dependency matrix before interchange:17; CHECK-NEXT: * = <18; CHECK-NEXT: * = =19; CHECK-NEXT: Processing InnerLoopId = 2 and OuterLoopId = 120; CHECK-NEXT: Checking if loops are tightly nested21; CHECK-NEXT: Checking instructions in Loop header and Loop latch22; CHECK-NEXT: Loops are perfectly nested23; CHECK-NEXT: Loops are legal to interchange24 25define void @all_eq_lt() {26entry:27 br label %for.n.header28 29for.n.header:30 %n = phi i32 [ 0, %entry ], [ %n.inc, %for.n.latch ]31 br label %for.i.header32 33for.i.header:34 %i = phi i32 [ 0, %for.n.header ], [ %i.inc, %for.i.latch ]35 br label %for.j36 37for.j:38 %j = phi i32 [ 1, %for.i.header ], [ %j.inc, %for.j ]39 %j.dec = sub nsw i32 %j, 140 %idx.store = getelementptr inbounds [256 x [256 x float]], ptr @a, i32 0, i32 %j.dec, i32 %i41 %idx.load = getelementptr inbounds [256 x [256 x float]], ptr @a, i32 0, i32 %j, i32 %i42 %0 = load float, ptr %idx.load, align 443 %1 = load float, ptr %idx.store, align 444 %add = fadd fast float %0, %145 store float %add, ptr %idx.store, align 446 %j.inc = add nuw nsw i32 %j, 147 %cmp.j = icmp slt i32 %j.inc, 25648 br i1 %cmp.j, label %for.j, label %for.i.latch49 50for.i.latch:51 %i.inc = add nuw nsw i32 %i, 152 %cmp.i = icmp slt i32 %i.inc, 25653 br i1 %cmp.i, label %for.i.header, label %for.n.latch54 55for.n.latch:56 %n.inc = add nuw nsw i32 %n, 157 %cmp.n = icmp slt i32 %n.inc, 10058 br i1 %cmp.n, label %for.n.header, label %exit59 60exit:61 ret void62}63 64;; for (int i = 0; i < 256; ++i)65;; for (int j = 1; j < 256; ++j)66;; a[j - 1][i] = a[j][255 - i];67;;68;; The direction vector of `a` is [* <]. We cannot interchange the loops69;; because we must handle a `*` dependence conservatively.70 71; CHECK: Dependency matrix before interchange:72; CHECK-NEXT: * <73; CHECK-NEXT: Processing InnerLoopId = 1 and OuterLoopId = 074; CHECK-NEXT: Failed interchange InnerLoopId = 1 and OuterLoopId = 0 due to dependence75; CHECK-NEXT: Not interchanging loops. Cannot prove legality.76 77define void @all_lt() {78entry:79 br label %for.i.header80 81for.i.header:82 %i = phi i32 [ 0, %entry ], [ %i.inc, %for.i.latch ]83 %i.rev = sub nsw i32 255, %i84 br label %for.j85 86for.j:87 %j = phi i32 [ 1, %for.i.header ], [ %j.inc, %for.j ]88 %j.dec = sub nsw i32 %j, 189 %idx.store = getelementptr inbounds [256 x [256 x float]], ptr @a, i32 0, i32 %j.dec, i32 %i90 %idx.load = getelementptr inbounds [256 x [256 x float]], ptr @a, i32 0, i32 %j, i32 %i.rev91 %0 = load float, ptr %idx.load, align 492 store float %0, ptr %idx.store, align 493 %j.inc = add nuw nsw i32 %j, 194 %cmp.j = icmp slt i32 %j.inc, 25695 br i1 %cmp.j, label %for.j, label %for.i.latch96 97for.i.latch:98 %i.inc = add nuw nsw i32 %i, 199 %cmp.i = icmp slt i32 %i.inc, 256100 br i1 %cmp.i, label %for.i.header, label %exit101 102exit:103 ret void104}105 106;; for (int i = 0; i < 255; ++i)107;; for (int j = 1; j < 256; ++j)108;; a[j][i] = a[j - 1][i + 1];109;;110;; The direciton vector of `a` is [< >]. We cannot interchange the loops111;; because the read/write order for `a` cannot be changed.112 113; CHECK: Dependency matrix before interchange:114; CHECK-NEXT: < >115; CHECK-NEXT: Processing InnerLoopId = 1 and OuterLoopId = 0116; CHECK-NEXT: Failed interchange InnerLoopId = 1 and OuterLoopId = 0 due to dependence117; CHECK-NEXT: Not interchanging loops. Cannot prove legality.118 119define void @lt_gt() {120entry:121 br label %for.i.header122 123for.i.header:124 %i = phi i32 [ 0, %entry ], [ %i.inc, %for.i.latch ]125 %i.inc = add nuw nsw i32 %i, 1126 br label %for.j127 128for.j:129 %j = phi i32 [ 1, %for.i.header ], [ %j.inc, %for.j ]130 %j.dec = sub nsw i32 %j, 1131 %idx.store = getelementptr inbounds [256 x [256 x float]], ptr @a, i32 0, i32 %j, i32 %i132 %idx.load = getelementptr inbounds [256 x [256 x float]], ptr @a, i32 0, i32 %j.dec, i32 %i.inc133 %0 = load float, ptr %idx.load, align 4134 store float %0, ptr %idx.store, align 4135 %j.inc = add nuw nsw i32 %j, 1136 %cmp.j = icmp slt i32 %j.inc, 256137 br i1 %cmp.j, label %for.j, label %for.i.latch138 139for.i.latch:140 %cmp.i = icmp slt i32 %i.inc, 255141 br i1 %cmp.i, label %for.i.header, label %exit142 143exit:144 ret void145}146 147;; for (int i = 0; i < 20; i++)148;; for (int j = 0; j < 20; j++)149;; for (int k = 0; k < 19; k++)150;; b[i][j][k] = b[i][5][k + 1];151;;152;; The direction vector of `b` is [= * *]. We cannot interchange all the loops.153 154; CHECK: Dependency matrix before interchange:155; CHECK-NEXT: = * *156; CHECK-NEXT: Processing InnerLoopId = 2 and OuterLoopId = 1157; CHECK-NEXT: Failed interchange InnerLoopId = 2 and OuterLoopId = 1 due to dependence158; CHECK-NEXT: Not interchanging loops. Cannot prove legality.159; CHECK-NEXT: Processing InnerLoopId = 1 and OuterLoopId = 0160; CHECK-NEXT: Failed interchange InnerLoopId = 1 and OuterLoopId = 0 due to dependence161; CHECK-NEXT: Not interchanging loops. Cannot prove legality.162 163define void @eq_all_lt() {164entry:165 br label %for.i.header166 167for.i.header:168 %i = phi i32 [ 0, %entry ], [ %i.inc, %for.i.latch ]169 br label %for.j.header170 171for.j.header:172 %j = phi i32 [ 0, %for.i.header ], [ %j.inc, %for.j.latch ]173 br label %for.k174 175for.k:176 %k = phi i32 [ 0, %for.j.header ], [ %k.inc, %for.k ]177 %k.inc = add nuw nsw i32 %k, 1178 %idx.store = getelementptr inbounds [20 x [20 x [20 x i32]]], ptr @b, i32 0, i32 %i, i32 %j, i32 %k179 %idx.load = getelementptr inbounds [20 x [20 x [20 x i32]]], ptr @b, i32 0, i32 %i, i32 5, i32 %k.inc180 %0 = load i32, ptr %idx.load, align 4181 store i32 %0, ptr %idx.store, align 4182 %cmp.k = icmp slt i32 %k.inc, 19183 br i1 %cmp.k, label %for.k, label %for.j.latch184 185for.j.latch:186 %j.inc = add nuw nsw i32 %j, 1187 %cmp.j = icmp slt i32 %j.inc, 20188 br i1 %cmp.j, label %for.j.header, label %for.i.latch189 190for.i.latch:191 %i.inc = add nuw nsw i32 %i, 1192 %cmp.i = icmp slt i32 %i.inc, 20193 br i1 %cmp.i, label %for.i.header, label %exit194 195exit:196 ret void197}198