128 lines · plain
1; RUN: opt < %s -mattr=+sve2 -passes=loop-vectorize,instcombine -enable-histogram-loop-vectorization -sve-gather-overhead=2 -sve-scatter-overhead=2 -force-vector-interleave=1 -debug-only=loop-vectorize --disable-output -S 2>&1 | FileCheck %s2; REQUIRES: asserts3 4target triple = "aarch64-unknown-linux-gnu"5 6;; Based on the following C code:7;;8;; void simple_histogram(int *buckets, unsigned *indices, int N) {9;; for (int i = 0; i < N; ++i)10;; buckets[indices[i]]++;11;; }12 13;; Check that the scalar plan contains the original instructions.14; CHECK: VPlan 'Initial VPlan for VF={1},UF>=1' {15; CHECK-NEXT: Live-in [[VF:.*]] = VF16; CHECK-NEXT: Live-in [[VFxUF:.*]] = VF * UF17; CHECK-NEXT: Live-in [[VTC:.*]] = vector-trip-count18; CHECK-NEXT: Live-in [[OTC:.*]] = original trip-count19; CHECK-EMPTY:20; CHECK-NEXT: ir-bb<entry>:21; CHECK-NEXT: Successor(s): scalar.ph, vector.ph22; CHECK-EMPTY:23; CHECK-NEXT: vector.ph:24; CHECK-NEXT: Successor(s): vector loop25; CHECK-EMPTY:26; CHECK-NEXT: <x1> vector loop: {27; CHECK-NEXT: vector.body:28; CHECK-NEXT: EMIT [[IV:.*]] = CANONICAL-INDUCTION ir<0>, [[IV_NEXT:.*]]29; CHECK-NEXT: [[STEPS:vp.*]] = SCALAR-STEPS [[IV]], ir<1>, [[VF]]30; CHECK-NEXT: CLONE [[GEP_IDX:.*]] = getelementptr inbounds ir<%indices>, [[STEPS]]31; CHECK-NEXT: CLONE [[IDX:.*]] = load [[GEP_IDX]]32; CHECK-NEXT: CLONE [[EXT_IDX:.*]] = zext [[IDX]]33; CHECK-NEXT: CLONE [[GEP_BUCKET:.*]] = getelementptr inbounds ir<%buckets>, [[EXT_IDX]]34; CHECK-NEXT: CLONE [[HISTVAL:.*]] = load [[GEP_BUCKET]]35; CHECK-NEXT: CLONE [[UPDATE:.*]] = add nsw [[HISTVAL]], ir<1>36; CHECK-NEXT: CLONE store [[UPDATE]], [[GEP_BUCKET]]37; CHECK-NEXT: EMIT [[IV_NEXT]] = add nuw [[IV]], [[VFxUF]]38; CHECK-NEXT: EMIT branch-on-count [[IV_NEXT]], [[VTC]]39; CHECK-NEXT: No successors40; CHECK-NEXT: }41; CHECK-NEXT: Successor(s): middle.block42; CHECK-EMPTY:43; CHECK-NEXT: middle.block:44; CHECK-NEXT: EMIT [[TC_CHECK:.*]] = icmp eq [[OTC:.*]], [[VTC]]45; CHECK-NEXT: EMIT branch-on-cond [[TC_CHECK]]46; CHECK-NEXT: Successor(s): ir-bb<for.exit>, scalar.ph47; CHECK-EMPTY:48; CHECK-NEXT: ir-bb<for.exit>:49; CHECK-NEXT: No successors50; CHECK-EMPTY:51; CHECK-NEXT: scalar.ph:52; CHECK-NEXT: EMIT-SCALAR vp<[[RESUME:%.+]]> = phi [ [[VTC]], middle.block ], [ ir<0>, ir-bb<entry> ]53; CHECK-NEXT: Successor(s): ir-bb<for.body>54; CHECK-EMPTY:55; CHECK-NEXT: ir-bb<for.body>:56; CHECK-NEXT: IR %iv = phi i64 [ 0, %entry ], [ %iv.next, %for.body ] (extra operand: vp<[[RESUME]]> from scalar.ph)57; CHECK: IR %exitcond = icmp eq i64 %iv.next, %N58; CHECK-NEXT: No successors59; CHECK-NEXT: }60 61;; Check that the vectorized plan contains a histogram recipe instead.62; CHECK: VPlan 'Initial VPlan for VF={vscale x 2,vscale x 4},UF>=1' {63; CHECK-NEXT: Live-in [[VF:.*]] = VF64; CHECK-NEXT: Live-in [[VFxUF:.*]] = VF * UF65; CHECK-NEXT: Live-in [[VTC:.*]] = vector-trip-count66; CHECK-NEXT: Live-in [[OTC:.*]] = original trip-count67; CHECK-EMPTY:68; CHECK-NEXT: ir-bb<entry>:69; CHECK-NEXT: Successor(s): scalar.ph, vector.ph70; CHECK-EMPTY:71; CHECK-NEXT: vector.ph:72; CHECK-NEXT: Successor(s): vector loop73; CHECK-EMPTY:74; CHECK-NEXT: <x1> vector loop: {75; CHECK-NEXT: vector.body:76; CHECK-NEXT: EMIT [[IV:.*]] = CANONICAL-INDUCTION ir<0>, [[IV_NEXT:.*]]77; CHECK-NEXT: [[STEPS:vp.*]] = SCALAR-STEPS [[IV]], ir<1>, [[VF]]78; CHECK-NEXT: CLONE [[GEP_IDX:.*]] = getelementptr inbounds ir<%indices>, [[STEPS]]79; CHECK-NEXT: [[VECP_IDX:vp.*]] = vector-pointer inbounds [[GEP_IDX]]80; CHECK-NEXT: WIDEN [[IDX:.*]] = load [[VECP_IDX]]81; CHECK-NEXT: WIDEN-CAST [[EXT_IDX:.*]] = zext [[IDX]] to i6482; CHECK-NEXT: WIDEN-GEP Inv[Var] [[GEP_BUCKET:.*]] = getelementptr inbounds ir<%buckets>, [[EXT_IDX]]83; CHECK-NEXT: WIDEN-HISTOGRAM buckets: [[GEP_BUCKET]], inc: ir<1>84; CHECK-NEXT: EMIT [[IV_NEXT]] = add nuw [[IV]], [[VFxUF]]85; CHECK-NEXT: EMIT branch-on-count [[IV_NEXT]], [[VTC]]86; CHECK-NEXT: No successors87; CHECK-NEXT: }88; CHECK-NEXT: Successor(s): middle.block89; CHECK-EMPTY:90; CHECK-NEXT: middle.block:91; CHECK-NEXT: EMIT [[TC_CHECK:.*]] = icmp eq [[OTC]], [[VTC]]92; CHECK-NEXT: EMIT branch-on-cond [[TC_CHECK]]93; CHECK-NEXT: Successor(s): ir-bb<for.exit>, scalar.ph94; CHECK-EMPTY:95; CHECK-NEXT: ir-bb<for.exit>:96; CHECK-NEXT: No successors97; CHECK-EMPTY:98; CHECK-NEXT: scalar.ph:99; CHECK-NEXT: EMIT-SCALAR vp<[[RESUME:%.+]]> = phi [ [[VTC]], middle.block ], [ ir<0>, ir-bb<entry> ]100; CHECK-NEXT: Successor(s): ir-bb<for.body>101; CHECK-EMPTY:102; CHECK-NEXT: ir-bb<for.body>:103; CHECK-NEXT: IR %iv = phi i64 [ 0, %entry ], [ %iv.next, %for.body ] (extra operand: vp<[[RESUME]]> from scalar.ph)104; CHECK: IR %exitcond = icmp eq i64 %iv.next, %N105; CHECK-NEXT: No successors106; CHECK-NEXT: }107 108define void @simple_histogram(ptr noalias %buckets, ptr readonly %indices, i64 %N) {109entry:110 br label %for.body111 112for.body:113 %iv = phi i64 [ 0, %entry ], [ %iv.next, %for.body ]114 %gep.indices = getelementptr inbounds i32, ptr %indices, i64 %iv115 %l.idx = load i32, ptr %gep.indices, align 4116 %idxprom1 = zext i32 %l.idx to i64117 %gep.bucket = getelementptr inbounds i32, ptr %buckets, i64 %idxprom1118 %l.bucket = load i32, ptr %gep.bucket, align 4119 %inc = add nsw i32 %l.bucket, 1120 store i32 %inc, ptr %gep.bucket, align 4121 %iv.next = add nuw nsw i64 %iv, 1122 %exitcond = icmp eq i64 %iv.next, %N123 br i1 %exitcond, label %for.exit, label %for.body124 125for.exit:126 ret void127}128