tree 68ff101831fc8900686746b9c7100ea1029f4c45
parent 13875dc513fe6284a415ffa2efb4cad353ec1a7f
author Florian Hahn <flo@fhahn.com> 1757015649 +0100
committer GitHub <noreply@github.com> 1757015649 +0100
gpgsig -----BEGIN PGP SIGNATURE-----
 
 wsFcBAABCAAQBQJoue5hCRC1aQ7uu5UhlAAAuA0QAGsPG0XmR3rI07KttC6EKP6G
 /6UVv1SyEd38CbdnSwARTQp8ZRE2YV+omy/cf0aZxZatVPm/y0wCPHWL/rlhWIdh
 4fvizDhpKkm0g+1f90OR8qOz7St9SEBUAENW4Xg3caJfHlrjr7E4Kq2tMEa2beRO
 wuU+WFU5TK9rPk/xiM90X9R3OSN0VFxq4M9MRolDIx2JjFuSCteXYRqnNpC/VXxb
 22uYLN6NzhodVBeF9kjQhRr8ei8/W+0+f1bvHr43u1Nyy9ENKn89VXO0LKY+ydlZ
 mmKX0YRojN8ak2IGvFacf6VzGJnG0c89vfWTi/x7d5GckOvd/X6SFZAtz/Db0v4X
 vyaC0vg458gtCAxoqAQnqBNI17RP5q9c7HkiMghoKX7eHjPWKwDWd4czeqrVrOCP
 XOvqyQ1YZJ8bFKH2CHZbjq+/BVDtIym+OOIJk4Zif/22Le3Sthqxq2FRrK3zMRco
 6tigGBcizurmbBAVP3dnrOeGr/+8q7RtrlSkC9nTt3HmgKd2m6YCh/Drsqu0KJNb
 t2pn+Py4csFkF9572Os5cXZvktijIFz97T0m317Q1mk9Gt+/0VDOK++GXs/qGgg4
 VKZat69JHmFym1aJSRg0a6Z7catFwTW6ZU2PN9aaEepCnuKd49Sa7bdBy/QcJhbk
 5TvkDN75dirWDn7KeYWx
 =/lWk
 -----END PGP SIGNATURE-----
 

[LoopUnroll] Introduce parallel reduction phis when unrolling. (#149470)

When partially or runtime unrolling loops with reductions, currently the
reductions are performed in-order in the loop, negating most benefits
from unrolling such loops.

This patch extends unrolling code-gen to keep a parallel reduction phi
per unrolled iteration and combining the final result after the loop.
For out-of-order CPUs, this allows executing mutliple reduction chains
in parallel.

For now, the initial transformation is restricted to cases where we
unroll a small number of iterations (hard-coded to 4, but should maybe
be capped by TTI depending on the execution units), to avoid introducing
an excessive amount of parallel phis.

It also requires single block loops for now, where the unrolled
iterations are known to not exit the loop (either due to runtime
unrolling or partial unrolling). This ensures that the unrolled loop
will have a single basic block, with a single exit block where we can
place the final reduction value computation.

The initial implementation also only supports parallelizing loops with a
single reduction and only integer reductions. Those restrictions are
just to keep the initial implementation simpler, and can easily be
lifted as follow-ups.

With corresponding TTI to the AArch64 unrolling preferences which I will
also share soon, this triggers in ~300 loops across a wide range of
workloads, including LLVM itself, ffmgep, av1aom, sqlite, blender,
brotli, zstd and more.

PR: https://github.com/llvm/llvm-project/pull/149470