HomePhabricator

[PassManager] Run additional LICM before LoopRotate

Authored by lebedev.ri on Apr 2 2021, 12:40 AM.

Description

[PassManager] Run additional LICM before LoopRotate

Loop rotation often has to perform code duplication
from header into preheader, which introduces PHI nodes.

In D99204, @thopre wrote:

With loop peeling, it is important that unnecessary PHIs be avoided or
it will leads to spurious peeling. One source of such PHIs is loop
rotation which creates PHIs for invariant loads. Those PHIs are
particularly problematic since loop peeling is now run as part of simple
loop unrolling before GVN is run, and are thus a source of spurious
peeling.

Note that while some of the load can be hoisted and eventually
eliminated by instruction combine, this is not always possible due to
alignment issue. In particular, the motivating example [1] was a load
inside a class instance which cannot be hoisted because the `this'
pointer has an alignment of 1.

[1] http://lists.llvm.org/pipermail/llvm-dev/attachments/20210312/4ce73c47/attachment.cpp

Now, we could enhance LoopRotate to avoid duplicating code when not needed,
but instead hoist loop-invariant code, but isn't that a code duplication? (*sic*)
We have LICM, and in fact we already run it right after LoopRotation.

We could try to move it to before LoopRotation,
that is basically free from compile-time perspective:
https://llvm-compile-time-tracker.com/compare.php?from=6c93eb4477d88af046b915bc955c03693b2cbb58&to=a4bee6d07732b1184c436da489040b912f0dc271&stat=instructions
But, looking at stats, i think it isn't great that we would no longer do LICM after LoopRotation, in particular:

statistic nameLoopRotate-LICMLICM-LoopRotateΔ%abs(%)
asm-printer.EmittedInsts90159309015799-1310.00%0.00%
indvars.NumElimCmp3536354480.23%0.23%
indvars.NumElimExt3672536580-145-0.39%0.39%
indvars.NumElimIV11971187-10-0.84%0.84%
indvars.NumElimIdentity143136-7-4.90%4.90%
indvars.NumElimRem45125.00%25.00%
indvars.NumLFTR2984229890480.16%0.16%
indvars.NumReplaced22932227-66-2.88%2.88%
indvars.NumSimplifiedSDiv68233.33%33.33%
indvars.NumWidened2643826329-109-0.41%0.41%
instcount.TotalBlocks11783381173840-4498-0.38%0.38%
instcount.TotalFuncs11182511182940.00%0.00%
instcount.TotalInsts99054429896139-9303-0.09%0.09%
lcssa.NumLCSSA425871423961-1910-0.45%0.45%
licm.NumHoisted3783573787533960.10%0.10%
licm.NumMovedCalls21932208150.68%0.68%
licm.NumMovedLoads3589931821-4078-11.36%11.36%
licm.NumPromoted1117811154-24-0.21%0.21%
licm.NumSunk13359135872281.71%1.71%
loop-delete.NumDeleted85478402-145-1.70%1.70%
loop-instsimplify.NumSimplified1287611890-986-7.66%7.66%
loop-peel.NumPeeled1008925-83-8.23%8.23%
loop-rotate.NumNotRotatedDueToHeaderSize368365-3-0.82%0.82%
loop-rotate.NumRotated4201542003-12-0.03%0.03%
loop-simplifycfg.NumLoopBlocksDeleted24024220.83%0.83%
loop-simplifycfg.NumLoopExitsDeleted49720-477-95.98%95.98%
loop-simplifycfg.NumTerminatorsFolded618336-282-45.63%45.63%
loop-unroll.NumCompletelyUnrolled110281103240.04%0.04%
loop-unroll.NumUnrolled1260812529-79-0.63%0.63%
mem2reg.NumDeadAlloca1022210221-1-0.01%0.01%
mem2reg.NumPHIInsert192110192106-40.00%0.00%
mem2reg.NumSingleStore637650637643-70.00%0.00%
scalar-evolution.NumBruteForceTripCountsComputed814812-2-0.25%0.25%
scalar-evolution.NumTripCountsComputed283108282934-174-0.06%0.06%
scalar-evolution.NumTripCountsNotComputed10671210671860.01%0.01%
simple-loop-unswitch.NumBranches51784752-426-8.23%8.23%
simple-loop-unswitch.NumCostMultiplierSkipped914503-411-44.97%44.97%
simple-loop-unswitch.NumSwitches2018-2-10.00%10.00%
simple-loop-unswitch.NumTrivial18395-88-48.09%48.09%

... but that actually regresses LICM (-12% licm.NumMovedLoads),
loop-simplifycfg (NumLoopExitsDeleted, NumTerminatorsFolded),
simple-loop-unswitch (NumTrivial).

What if we instead have LICM both before and after LoopRotate?

statistic nameLoopRotate-LICMLICM-LoopRotate-LICMΔ%abs(%)
asm-printer.EmittedInsts90159309014474-1456-0.02%0.02%
indvars.NumElimCmp35363546100.28%0.28%
indvars.NumElimExt3672536681-44-0.12%0.12%
indvars.NumElimIV11971185-12-1.00%1.00%
indvars.NumElimIdentity14314632.10%2.10%
indvars.NumElimRem45125.00%25.00%
indvars.NumLFTR2984229899570.19%0.19%
indvars.NumReplaced2293229960.26%0.26%
indvars.NumSimplifiedSDiv68233.33%33.33%
indvars.NumWidened2643826404-34-0.13%0.13%
instcount.TotalBlocks11783381173652-4686-0.40%0.40%
instcount.TotalFuncs11182511182940.00%0.00%
instcount.TotalInsts99054429895452-9990-0.10%0.10%
lcssa.NumLCSSA425871425373-498-0.12%0.12%
licm.NumHoisted37835738335249951.32%1.32%
licm.NumMovedCalls21932204110.50%0.50%
licm.NumMovedLoads3589935755-144-0.40%0.40%
licm.NumPromoted1117811163-15-0.13%0.13%
licm.NumSunk13359143219627.20%7.20%
loop-delete.NumDeleted85478538-9-0.11%0.11%
loop-instsimplify.NumSimplified1287612041-835-6.48%6.48%
loop-peel.NumPeeled1008924-84-8.33%8.33%
loop-rotate.NumNotRotatedDueToHeaderSize368365-3-0.82%0.82%
loop-rotate.NumRotated4201542005-10-0.02%0.02%
loop-simplifycfg.NumLoopBlocksDeleted24024110.42%0.42%
loop-simplifycfg.NumTerminatorsFolded61861910.16%0.16%
loop-unroll.NumCompletelyUnrolled110281102910.01%0.01%
loop-unroll.NumUnrolled1260812525-83-0.66%0.66%
mem2reg.NumPHIInsert192110192073-37-0.02%0.02%
mem2reg.NumSingleStore63765063765220.00%0.00%
scalar-evolution.NumTripCountsComputed283108282998-110-0.04%0.04%
scalar-evolution.NumTripCountsNotComputed106712106691-21-0.02%0.02%
simple-loop-unswitch.NumBranches5178518570.14%0.14%
simple-loop-unswitch.NumCostMultiplierSkipped914925111.20%1.20%
simple-loop-unswitch.NumTrivial183179-4-2.19%2.19%
simple-loop-unswitch.NumBranches51784752-426-8.23%8.23%
simple-loop-unswitch.NumCostMultiplierSkipped914503-411-44.97%44.97%
simple-loop-unswitch.NumSwitches2018-2-10.00%10.00%
simple-loop-unswitch.NumTrivial18395-88-48.09%48.09%

I.e. we end up with less instructions, less peeling, more LICM activity,
also note how none of those 4 regressions are here. Namely:

statistic nameLICM-LoopRotateLICM-LoopRotate-LICMΔ%abs(%)
asm-printer.EmittedInsts90157999014474-1325-0.01%0.01%
indvars.NumElimCmp3544354620.06%0.06%
indvars.NumElimExt36580366811010.28%0.28%
indvars.NumElimIV11871185-2-0.17%0.17%
indvars.NumElimIdentity136146107.35%7.35%
indvars.NumLFTR298902989990.03%0.03%
indvars.NumReplaced22272299723.23%3.23%
indvars.NumWidened2632926404750.28%0.28%
instcount.TotalBlocks11738401173652-188-0.02%0.02%
instcount.TotalInsts98961399895452-687-0.01%0.01%
lcssa.NumLCSSA42396142537314120.33%0.33%
licm.NumHoisted37875338335245991.21%1.21%
licm.NumMovedCalls22082204-4-0.18%0.18%
licm.NumMovedLoads3182135755393412.36%12.36%
licm.NumPromoted111541116390.08%0.08%
licm.NumSunk13587143217345.40%5.40%
loop-delete.NumDeleted840285381361.62%1.62%
loop-instsimplify.NumSimplified11890120411511.27%1.27%
loop-peel.NumPeeled925924-1-0.11%0.11%
loop-rotate.NumRotated420034200520.00%0.00%
loop-simplifycfg.NumLoopBlocksDeleted242241-1-0.41%0.41%
loop-simplifycfg.NumLoopExitsDeleted204974772385.00%2385.00%
loop-simplifycfg.NumTerminatorsFolded33661928384.23%84.23%
loop-unroll.NumCompletelyUnrolled1103211029-3-0.03%0.03%
loop-unroll.NumUnrolled1252912525-4-0.03%0.03%
mem2reg.NumDeadAlloca102211022210.01%0.01%
mem2reg.NumPHIInsert192106192073-33-0.02%0.02%
mem2reg.NumSingleStore63764363765290.00%0.00%
scalar-evolution.NumBruteForceTripCountsComputed81281420.25%0.25%
scalar-evolution.NumTripCountsComputed282934282998640.02%0.02%
scalar-evolution.NumTripCountsNotComputed106718106691-27-0.03%0.03%
simple-loop-unswitch.NumBranches475251854339.11%9.11%
simple-loop-unswitch.NumCostMultiplierSkipped50392542283.90%83.90%
simple-loop-unswitch.NumSwitches1820211.11%11.11%
simple-loop-unswitch.NumTrivial951798488.42%88.42%


(this is vanilla llvm testsuite + rawspeed + darktable)

As an example of the code where early LICM only is bad, see:
https://godbolt.org/z/GzEbacs4K

This does have an observable compile-time regression of +~0.5% geomean
https://llvm-compile-time-tracker.com/compare.php?from=7c5222e4d1a3a14f029e5f614c9aefd0fa505f1e&to=5d81826c3411982ca26e46b9d0aff34c80577664&stat=instructions
but i think that's basically nothing, and there's potential that it might
be avoidable in the future by fixing clang to produce alignment information
on function arguments, thus making the second run unneeded.

Differential Revision: https://reviews.llvm.org/D99249

Details