248 lines · plain
1; RUN: opt -passes=loop-unroll -enable-peeling-for-iv -disable-output \2; RUN: -pass-remarks-output=- %s | FileCheck %s3; RUN: opt -passes=loop-unroll-full -enable-peeling-for-iv -disable-output \4; RUN: -pass-remarks-output=- %s | FileCheck %s5 6; void g(int);7declare void @g(i32)8 9; Check that phi analysis can handle a binary operator with an addition or a10; subtraction on loop-invariants or IVs. In the following case, the phis for x,11; y, a, and b become IVs by peeling.12;13;14; void g(int);15; void binary() {16; int x = 0;17; int y = 0;18; int a = 42;19; int b = 314;20; for(int i = 0; i <100000; ++i) {21; g(x);22; g(b);23; x = y;24; y = a + 1;25; a = i - 2;26; b = i + a;27; }28; }29;30;31; Consider the calls to g:32;33; | i | g(x) | g(b) | x | y | a | b |34; ---------------|-----|---------|----------|-----|-----|-----|-------|35; 1st iteration | 0 | g(0) | g(314) | 0 | 43 | -2 | -2 |36; 2nd iteration | 1 | g(0) | g(-2) | 43 | -1 | -1 | 0 |37; 3rd iteration | 2 | g(43) | g(0) | -1 | 0 | 0 | 2 |38; 4th iteration | 3 | g(-1) | g(2) | 0 | 1 | 1 | 4 |39; 5th iteration | 4 | g(0) | g(4) | 1 | 2 | 2 | 6 |40; i-th iteration | i | g(i-5) | g(2*i-4) | i-4 | i-3 | i-2 | 2*i-4 |41;42; After the 4th iteration, the arguments to g become IVs, so peeling 3 times43; converts all PHIs into IVs.44;45 46; CHECK: --- !Passed47; CHECK-NEXT: Pass: loop-unroll48; CHECK-NEXT: Name: Peeled49; CHECK-NEXT: Function: binary_induction50; CHECK-NEXT: Args:51; CHECK-NEXT: - String: ' peeled loop by '52; CHECK-NEXT: - PeelCount: '3'53; CHECK-NEXT: - String: ' iterations'54; CHECK-NEXT: ...55define void @binary_induction() {56entry:57 br label %for.body58 59exit:60 ret void61 62for.body:63 %i = phi i32 [ 0, %entry ], [ %i.next, %for.body ]64 %x = phi i32 [ 0, %entry ], [ %y, %for.body ]65 %y = phi i32 [ 0, %entry ], [ %y.next, %for.body ]66 %a = phi i32 [ 42, %entry ], [ %a.next, %for.body ]67 %b = phi i32 [ 314, %entry ], [ %b.next, %for.body ]68 tail call void @g(i32 %x)69 tail call void @g(i32 %b)70 %i.next = add i32 %i, 171 %y.next = add i32 %a, 172 %a.next = sub i32 %i, 273 %b.next = add i32 %i, %a74 %cmp = icmp ne i32 %i.next, 10000075 br i1 %cmp, label %for.body, label %exit76}77 78; Check that peeling works fine in the following case. This is based on TSVC79; s291, where peeling 1 time makes the variable im an IV so we can vectorize80; the loop.81;82; #define N 10083; void f(float * restrict a, float * restrict b) {84; int im = N - 1;85; for (int i = 0; i < N; i++) {86; a[i] = b[i] + b[im];87; im = i;88; }89; }90;91 92; CHECK: --- !Passed93; CHECK-NEXT: Pass: loop-unroll94; CHECK-NEXT: Name: Peeled95; CHECK-NEXT: Function: tsvc_s29196; CHECK-NEXT: Args:97; CHECK-NEXT: - String: ' peeled loop by '98; CHECK-NEXT: - PeelCount: '1'99; CHECK-NEXT: - String: ' iterations'100; CHECK-NEXT: ...101define void @tsvc_s291(ptr noalias %a, ptr noalias %b) {102entry:103 br label %for.body104 105for.body:106 %i = phi i32 [0, %entry], [ %i.next, %for.body ]107 %im = phi i32 [ 99, %entry ], [ %i, %for.body ]108 %a.idx = getelementptr inbounds float, ptr %a, i32 %i109 %b.idx.0 = getelementptr inbounds float, ptr %b, i32 %i110 %b.idx.1 = getelementptr inbounds float, ptr %b, i32 %im111 %lhs = load float, ptr %b.idx.0, align 4112 %rhs = load float, ptr %b.idx.1, align 4113 %sum = fadd float %lhs, %rhs114 store float %sum, ptr %a.idx, align 4115 %i.next = add i32 %i, 1116 %cmp = icmp ne i32 %i.next, 100117 br i1 %cmp, label %for.body, label %exit118 119exit:120 ret void121}122 123; Check that the unnecessary peeling occurs in the following case. The cause is124; that the analyzer determines a casted IV as a non-IV.125;126; for (unsigned int i=0; i<10000; i++)127; a[(unsigned long)j] = 10;128;129 130; CHECK: --- !Passed131; CHECK-NEXT: Pass: loop-unroll132; CHECK-NEXT: Name: Peeled133; CHECK-NEXT: Function: induction_undesirable_peel1134; CHECK-NEXT: Args:135; CHECK-NEXT: - String: ' peeled loop by '136; CHECK-NEXT: - PeelCount: '1'137; CHECK-NEXT: - String: ' iterations'138; CHECK-NEXT: ...139define void @induction_undesirable_peel1(ptr %a) {140entry:141 br label %for.body142 143for.body:144 %conv = phi i64 [ 0, %entry ], [ %conv.next, %for.body ]145 %iv = phi i32 [ 0, %entry ], [ %iv.next, %for.body ]146 %arrayidx = getelementptr inbounds nuw i32, ptr %a, i64 %conv147 store i32 10, ptr %arrayidx, align 4148 %iv.next = add nsw nuw i32 %iv, 1149 %conv.next = zext i32 %iv.next to i64150 %cmp = icmp ugt i64 10000, %conv.next151 br i1 %cmp, label %for.body, label %exit152 153exit:154 ret void155}156 157; Check that the unnecessary peeling occurs in the following case. The analyzer158; cannot detect that the difference between the initial value of %i and %j is159; equal to the step value of the %i.160;161; int j = 0;162; for (int i=1; i<N; i++) {163; a[j] = 10;164; j = i;165; }166 167; CHECK: --- !Passed168; CHECK-NEXT: Pass: loop-unroll169; CHECK-NEXT: Name: Peeled170; CHECK-NEXT: Function: induction_undesirable_peel2171; CHECK-NEXT: Args:172; CHECK-NEXT: - String: ' peeled loop by '173; CHECK-NEXT: - PeelCount: '1'174; CHECK-NEXT: - String: ' iterations'175; CHECK-NEXT: ...176define void @induction_undesirable_peel2(ptr %a) {177entry:178 br label %for.body179 180for.body:181 %i = phi i32 [ 1, %entry ], [ %i.next, %for.body ]182 %j = phi i32 [ 0, %entry ], [ %i, %for.body ]183 %arrayidx = getelementptr i32, ptr %a, i32 %j184 store i32 10, ptr %arrayidx, align 4185 %i.next = add i32 %i, 1186 %cmp = icmp slt i32 %i, 10000187 br i1 %cmp, label %for.body, label %exit188 189exit:190 ret void191}192 193; Check that phi analysis can handle a binary operator with an addition or a194; subtraction on loop-invariants or IVs. In the following case, the phis for x,195; y, a, and b become IVs by peeling.196;197;198; void g(int);199; void binary() {200; int x = 2;201; for(int i = 0; i <100000; ++i) {202; g(x);203; tmp = i - 2;204; x = i - tmp;205; }206; }207;208;209; Consider the calls to g:210;211; | i | g(x) | tmp | x |212; ---------------|---|------|-----|---|213; 1st iteration | 0 | g(2) | -2 | 2 |214; 2nd iteration | 1 | g(2) | -1 | 2 |215; 3rd iteration | 2 | g(2) | 0 | 2 |216; 4th iteration | 3 | g(2) | 1 | 2 |217;218; In this case, the value of x is always 2. However, the analyzer recognizes219; the expression "i - tmp" as an IV.220;221 222; CHECK: --- !Passed223; CHECK-NEXT: Pass: loop-unroll224; CHECK-NEXT: Name: Peeled225; CHECK-NEXT: Function: induction_undesirable_peel3226; CHECK-NEXT: Args:227; CHECK-NEXT: - String: ' peeled loop by '228; CHECK-NEXT: - PeelCount: '1'229; CHECK-NEXT: - String: ' iterations'230; CHECK-NEXT: ...231define void @induction_undesirable_peel3() {232entry:233 br label %for.body234 235exit:236 ret void237 238for.body:239 %i = phi i32 [ 0, %entry ], [ %i.next, %for.body ]240 %x = phi i32 [ 0, %entry ], [ %x.next, %for.body ]241 tail call void @g(i32 %x)242 %tmp = sub i32 %i, 2243 %x.next = sub i32 %i, %tmp244 %i.next = add i32 %i, 1245 %cmp = icmp ne i32 %i.next, 100000246 br i1 %cmp, label %for.body, label %exit247}248