[llvm-dev] RFC: Extending loop metadata

[Michael Kruse via llvm-dev]

Hi llvm-dev,

I recently posted an RFC about extending #pragma clang loop to the
cfe-dev mailing list [1]. It proposes adding more loop transformations
to Clang, defines an execution order if multiple transformations are
specified and allow programmers to assign names to loops.
This email is about the LLVM part of the proposal. I am happy for any
feedback, especially about whether the community would accept this
approach.

The current LLVM framework unfortunately does not support such
extended loop transformations. First, the transformations must be
represented in the IR metadata. Second, a pass must carry-out all
transformations.

Regarding the first part, I suggest storing the loop transformations
in a metadata node of the parent function, e.g.:

    define func() !looptransform !3
      [...]
      br i1 %cond, label %loopheader, ... !loop !1

    !1 = distinct !{ !4, !2 } ; LoopID
    !2 = {"llvm.loop.id", "myloop"} ; Loop name

Only the loop id remains a property of the loop. The transformations
are stored in the !looptransform metadata node:

    !3 = { !3, !4, ... } ; Ordered list of loop transformations
    !4 = {"llvm.loop.reverse, !1, "rev"} ; Apply loop reversal on
                                ; "myloop", results in a new loop "rev"
    !5 = {"llvm.loop.tile", !6} ; Apply loop tiling on the loops at !6
    !6 = {!7} ; Loop(s) to tile
    !7 = {"rev", 32} ; Tile "rev" using a tile size of 32

Any loop transformation pass can apply its transformation if it is the
first in the sequence for a loop, then remove the applied
transformation from the stack. This means transformations can
currently only be applied in the order specified by the pass manager.
Chandler Carruth recently suggested that the pass manager could
revisit mutated loops [2]. This would be useful to do a fixpoint
computation until all transformations have been applied.

We are using Polly [5] to apply transformations in any order (and with
only one loop versioning copy). In the long term, I'd hope to have
powerful loop transformations to be a part of LLVM, e.g. by
introducing a loop transformation framework [3,4].

Compatibility with the current loop hint metadata can be ensured by
either converting it using IR AutoUpgrade, or passes have to look for
both kinds of metadata.

Michael


[1] https://lists.llvm.org/pipermail/cfe-dev/2018-May/058141.html
[2] https://lists.llvm.org/pipermail/llvm-commits/Week-of-Mon-20180521/555241.html
[3] https://lists.llvm.org/pipermail/llvm-dev/2017-October/118125.html
[4] https://llvm.org/devmtg/2018-04/talks.html#Talk_15
[5] https://github.com/Meinersbur/polly/tree/pragma