llvm / llvm/llvm-project

[LoopVectorize] - Unable to vectorize the loop with runtime checks for an unknown TC via function args.

Open
#221,915 4 comments 0 reactions 0 assignees View on GitHub
missed-optimization vectorizers
Dominant language
LLVM
Stars
40.5k
Forks
18.7k
PR merge metrics
PR metrics pending

Description

Loop Vectorizer is unable to vectorize this particular loop with runtime checks, however GCC is able to emit runtime checks and vectorize the loop, the performance on a RISCV64 Linux machine nearly doubles with this particular loop ( But this is a target independent issue ). This is an example taken from TSVC suite.

LoopVectorize should support runtime stride versioning, emit if (stride == 1) guard and vectorize the unit-stride copy.

```llvm
; ModuleID = 'v096-simple.c'
target datalayout = "e-m:e-p:64:64-i64:64-i128:128-n32:64-S128"
target triple = "riscv64-unknown-linux-gnu"

; Function Attrs: nofree norecurse nosync nounwind memory(argmem: readwrite) uwtable vscale_range(4,1024)
define dso_local void @v096(i32 noundef signext %n, ptr noalias nofree noundef captures(none) %a, ptr noalias nofree noundef readonly captures(none) %b, ptr noalias nofree noundef readonly captures(none) %c, i32 noundef signext %inc) local_unnamed_addr #0 {
entry:
%cmp.not14 = icmp sgt i32 %n, 0
br i1 %cmp.not14, label %if.end.preheader, label %L20

if.end.preheader: ; preds = %entry
%0 = sext i32 %inc to i64
%1 = zext nneg i32 %n to i64
br label %if.end

if.end: ; preds = %if.end.preheader, %if.end
%indvars.iv = phi i64 [ 0, %if.end.preheader ], [ %indvars.iv.next, %if.end ]
%arrayidx = getelementptr inbounds [4 x i8], ptr %a, i64 %indvars.iv
%2 = load i32, ptr %arrayidx, align 4, !tbaa !13
%arrayidx2 = getelementptr inbounds [4 x i8], ptr %b, i64 %indvars.iv
%3 = load i32, ptr %arrayidx2, align 4, !tbaa !13
%arrayidx4 = getelementptr inbounds [4 x i8], ptr %c, i64 %indvars.iv
%4 = load i32, ptr %arrayidx4, align 4, !tbaa !13
%mul = mul nsw i32 %4, %3
%add = add nsw i32 %mul, %2
store i32 %add, ptr %arrayidx, align 4, !tbaa !13
%indvars.iv.next = add nsw i64 %indvars.iv, %0
%cmp.not = icmp slt i64 %indvars.iv.next, %1
br i1 %cmp.not, label %if.end, label %L20

L20: ; preds = %if.end, %entry
ret void
}

attributes #0 = { nofree norecurse nosync nounwind memory(argmem: readwrite) uwtable vscale_range(4,1024) "no-trapping-math"="true" "stack-protector-buffer-size"="8" "target-cpu"="spacemit-x60" "target-features"="+64bit,+a,+b,+c,+d,+f,+i,+m,+relax,+ssccptr,+sscofpmf,+sscounterenw,+sstc,+sstvala,+sstvecd,+svade,+svbare,+svinval,+svnapot,+svpbmt,+unaligned-scalar-mem,+v,+xsmtvdot,+za64rs,+zaamo,+zalrsc,+zba,+zbb,+zbc,+zbkc,+zbs,+zca,+zcd,+zfh,+zfhmin,+zic64b,+zicbom,+zicbop,+zicboz,+ziccamoa,+ziccif,+zicclsm,+ziccrse,+zicntr,+zicond,+zicsr,+zifencei,+zihintpause,+zihpm,+zkt,+zmmul,+zve32f,+zve32x,+zve64d,+zve64f,+zve64x,+zvfh,+zvfhmin,+zvkt,+zvl128b,+zvl256b,+zvl32b,+zvl64b,-e,-experimental-p,-experimental-smcsps,-experimental-smehv,-experimental-smijt,-experimental-smip,-experimental-smpmpmt,-experimental-sscsps,-experimental-ssehv,-experimental-ssijt,-experimental-ssip,-experimental-svukte,-experimental-xqccmt,-experimental-xsfmclic,-experimental-xsfsclic,-experimental-y,-experimental-zibi,-experimental-zicfilp,-experimental-zilx,-experimental-zvabd,-experimental-zvbc32e,-experimental-zvdot4a8i,-experimental-zvfbdota32f,-experimental-zvfbfa,-experimental-zvfofp8min,-experimental-zvfqwbdota8f,-experimental-zvfqwdota8f,-experimental-zvfwbdota16bf,-experimental-zvfwdota16bf,-experimental-zvkgs,-experimental-zvqwbdota16i,-experimental-zvqwbdota8i,-experimental-zvqwdota16i,-experimental-zvqwdota8i,-experimental-zvvfmm,-experimental-zvvmm,-experimental-zvvmtls,-experimental-zvvmttls,-experimental-zvzip,-h,-q,-sdext,-sdtrig,-sha,-shcounterenw,-shgatpa,-shlcofideleg,-shtvala,-shvsatpa,-shvstvala,-shvstvecd,-smaia,-smcdeleg,-smcntrpmf,-smcsrind,-smctr,-smdbltrp,-smepmp,-smmpm,-smnpm,-smrnmi,-smstateen,-ssaia,-ssccfg,-sscsrind,-ssctr,-ssdbltrp,-ssnpm,-sspm,-ssqosid,-ssstateen,-ssstrict,-ssu64xl,-supm,-svadu,-svrsw60t59b,-svvptc,-xaifet,-xandesbfhcvt,-xandesperf,-xandesvbfhcvt,-xandesvdot,-xandesvpackfph,-xandesvsinth,-xandesvsintload,-xcheriot,-xcvalu,-xcvbi,-xcvbitmanip,-xcvelw,-xcvmac,-xcvmem,-xcvsimd,-xmipscbop,-xmipscmov,-xmipsexectl,-xmipslsp,-xqccmp,-xqci,-xqcia,-xqciac,-xqcibi,-xqcibm,-xqcicli,-xqcicm,-xqcics,-xqcicsr,-xqciint,-xqciio,-xqcilb,-xqcili,-xqcilia,-xqcilo,-xqcilsm,-xqcisim,-xqcisls,-xqcisync,-xsfcease,-xsfmm128t,-xsfmm16t,-xsfmm32a,-xsfmm32a16f,-xsfmm32a32f,-xsfmm32a8f,-xsfmm32a8i,-xsfmm32t,-xsfmm64a64f,-xsfmm64t,-xsfmmbase,-xsfvcp,-xsfvfbfexp16e,-xsfvfexp16e,-xsfvfexp32e,-xsfvfexpa,-xsfvfexpa64e,-xsfvfnrclipxfqf,-xsfvfwmaccqqq,-xsfvqmaccdod,-xsfvqmaccqoq,-xsifivecdiscarddlone,-xsifivecflushdlone,-xsmtvdotii,-xtheadba,-xtheadbb,-xtheadbs,-xtheadcmo,-xtheadcondmov,-xtheadfmemidx,-xtheadmac,-xtheadmemidx,-xtheadmempair,-xtheadsync,-xtheadvdot,-xventanacondops,-xwchc,-za128rs,-zabha,-zacas,-zalasr,-zama16b,-zawrs,-zbkb,-zbkx,-zcb,-zce,-zcf,-zclsd,-zcmop,-zcmp,-zcmt,-zdinx,-zfa,-zfbfmin,-zfinx,-zhinx,-zhinxmin,-ziccamoc,-ziccid,-zicfiss,-zihintntl,-zilsd,-zimop,-zk,-zkn,-zknd,-zkne,-zknh,-zkr,-zks,-zksed,-zksh,-ztso,-zvbb,-zvbc,-zvfbfmin,-zvfbfwma,-zvkb,-zvkg,-zvkn,-zvknc,-zvkned,-zvkng,-zvknha,-zvknhb,-zvks,-zvksc,-zvksed,-zvksg,-zvksh,-zvl1024b,-zvl16384b,-zvl2048b,-zvl32768b,-zvl4096b,-zvl512b,-zvl65536b,-zvl8192b" }

!llvm.module.flags = !{!0, !1, !3, !4, !5, !6}
!llvm.ident = !{!7}
!llvm.errno.tbaa = !{!8}

!0 = !{i32 1, !"target-abi", !"lp64d"}
!1 = !{i32 6, !"riscv-isa", !2}
!2 = !{!"rv64i2p1_m2p0_a2p1_f2p2_d2p2_c2p0_b1p0_v1p0_zic64b1p0_zicbom1p0_zicbop1p0_zicboz1p0_ziccamoa1p0_ziccif1p0_zicclsm1p0_ziccrse1p0_zicntr2p0_zicond1p0_zicsr2p0_zifencei2p0_zihintpause2p0_zihpm2p0_zmmul1p0_za64rs1p0_zaamo1p0_zalrsc1p0_zfh1p0_zfhmin1p0_zca1p0_zcd1p0_zba1p0_zbb1p0_zbc1p0_zbkc1p0_zbs1p0_zkt1p0_zve32f1p0_zve32x1p0_zve64d1p0_zve64f1p0_zve64x1p0_zvfh1p0_zvfhmin1p0_zvkt1p0_zvl128b1p0_zvl256b1p0_zvl32b1p0_zvl64b1p0_ssccptr1p0_sscofpmf1p0_sscounterenw1p0_sstc1p0_sstvala1p0_sstvecd1p0_svade1p0_svbare1p0_svinval1p0_svnapot1p0_svpbmt1p0_xsmtvdot1p0"}
!3 = !{i32 8, !"PIC Level", i32 2}
!4 = !{i32 7, !"PIE Level", i32 2}
!5 = !{i32 7, !"uwtable", i32 2}
!6 = !{i32 8, !"SmallDataLimit", i32 0}
!7 = !{!"clang version 24.0.0git (clang 73e729f7b2f030390095db1eaa162cbd666be3e7)"}
!8 = !{!9, !10, i64 0}
!9 = !{!"__libc_errno", !10, i64 0}
!10 = !{!"int", !11, i64 0}
!11 = !{!"omnipotent char", !12, i64 0}
!12 = !{!"Simple C/C++ TBAA"}
!13 = !{!10, !10, i64 0}
```

SCEV analysis.

```
Printing analysis 'Scalar Evolution Analysis' for function 'v096':
Classifying expressions for: @v096
%0 = sext i32 %inc to i64
--> (sext i32 %inc to i64) U: [-2147483648,2147483648) S: [-2147483648,2147483648)
%1 = zext nneg i32 %n to i64
--> (zext i32 %n to i64) U: [0,4294967296) S: [0,4294967296)
%indvars.iv = phi i64 [ 0, %if.end.preheader ], [ %indvars.iv.next, %if.end ]
--> {0,+,(sext i32 %inc to i64)}<%if.end> U: full-set S: full-set Exits: <> LoopDispositions: { %if.end: Computable }
%arrayidx = getelementptr inbounds [4 x i8], ptr %a, i64 %indvars.iv
--> {%a,+,(4 * (sext i32 %inc to i64))}<%if.end> U: full-set S: full-set Exits: <> LoopDispositions: { %if.end: Computable }
%2 = load i32, ptr %arrayidx, align 4, !tbaa !13
--> %2 U: full-set S: full-set Exits: <> LoopDispositions: { %if.end: Variant }
%arrayidx2 = getelementptr inbounds [4 x i8], ptr %b, i64 %indvars.iv
--> {%b,+,(4 * (sext i32 %inc to i64))}<%if.end> U: full-set S: full-set Exits: <> LoopDispositions: { %if.end: Computable }
%3 = load i32, ptr %arrayidx2, align 4, !tbaa !13
--> %3 U: full-set S: full-set Exits: <> LoopDispositions: { %if.end: Variant }
%arrayidx4 = getelementptr inbounds [4 x i8], ptr %c, i64 %indvars.iv
--> {%c,+,(4 * (sext i32 %inc to i64))}<%if.end> U: full-set S: full-set Exits: <> LoopDispositions: { %if.end: Computable }
%4 = load i32, ptr %arrayidx4, align 4, !tbaa !13
--> %4 U: full-set S: full-set Exits: <> LoopDispositions: { %if.end: Variant }
%mul = mul nsw i32 %4, %3
--> (%3 * %4) U: full-set S: full-set Exits: <> LoopDispositions: { %if.end: Variant }
%add = add nsw i32 %mul, %2
--> ((%3 * %4) + %2) U: full-set S: full-set Exits: <> LoopDispositions: { %if.end: Variant }
%indvars.iv.next = add nsw i64 %indvars.iv, %0
--> {(sext i32 %inc to i64),+,(sext i32 %inc to i64)}<%if.end> U: full-set S: full-set Exits: <> LoopDispositions: { %if.end: Computable }
Determining loop execution counts for: @v096
Loop %if.end: Unpredictable backedge-taken count.
Loop %if.end: Unpredictable constant max backedge-taken count.
Loop %if.end: Unpredictable symbolic max backedge-taken count.
```

Contributor guide

Open the contributing guide

Research direction

Start with the Loop Vectorizer behavior described by the LLVM IR example and inspect the accompanying Scalar Evolution analysis, especially the unknown runtime stride. Compare the result with GCC's runtime-check behavior; done means supporting stride versioning with an `if (stride == 1)` guard and vectorizing the unit-stride copy.

Written by the indexing model from the issue text.

Assessment

Tech stack
c
Domain
compilers, performance
Issue type
Feature
Difficulty
4/5
Estimated time
3-5 days
Activity status
Active
Clarity
Mostly clear
Newbie friendliness
48/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.