Code Transformation Metadata¶

Overview
Metadata on Loops
Transformation Metadata Structure
Pass-Specific Transformation Metadata
Ambiguous Transformation Order
Leftover Transformations

Overview ¶

LLVM transformation passes can be controlled by attaching metadata to the code to transform. By default, transformation passes use heuristics to determine whether or not to perform transformations, and when doing so, other details of how the transformations are applied (e.g., which vectorization factor to select). Unless the optimizer is otherwise directed, transformations are applied conservatively. This conservatism generally allows the optimizer to avoid unprofitable transformations, but in practice, this results in the optimizer not applying transformations that would be highly profitable.

Frontends can give additional hints to LLVM passes on which transformations they should apply. This can be additional knowledge that cannot be derived from the emitted IR, or directives passed from the user/programmer. OpenMP pragmas are an example of the latter.

If any such metadata is dropped from the program, the code’s semantics must not change.

Metadata on Loops ¶

Attributes can be attached to loops as described in ‘llvm.loop’. Attributes can describe properties of the loop, disable transformations, force specific transformations and set transformation options.

Because metadata nodes are immutable (with the exception of MDNode::replaceOperandWith which is dangerous to use on uniqued metadata), in order to add or remove a loop attributes, a new MDNode must be created and assigned as the new llvm.loop metadata. Any connection between the old MDNode and the loop is lost. The llvm.loop node is also used as LoopID (Loop::getLoopID()), i.e. the loop effectively gets a new identifier. For instance, llvm.mem.parallel_loop_access references the LoopID. Therefore, if the parallel access property is to be preserved after adding/removing loop attributes, any llvm.mem.parallel_loop_access reference must be updated to the new LoopID.

Transformation Metadata Structure ¶

Some attributes describe code transformations (unrolling, vectorizing, loop distribution, etc.). They can either be a hint to the optimizer that a transformation might be beneficial, instruction to use a specific option, , or convey a specific request from the user (such as #pragma clang loop or #pragma omp simd).

If a transformation is forced but cannot be carried-out for any reason, an optimization-missed warning must be emitted. Semantic information such as a transformation being safe (e.g. llvm.mem.parallel_loop_access) can be unused by the optimizer without generating a warning.

Unless explicitly disabled, any optimization pass may heuristically determine whether a transformation is beneficial and apply it. If metadata for another transformation was specified, applying a different transformation before it might be inadvertent due to being applied on a different loop or the loop not existing anymore. To avoid having to explicitly disable an unknown number of passes, the attribute llvm.loop.disable_nonforced disables all optional, high-level, restructuring transformations.

The following example avoids the loop being altered before being vectorized, for instance being unrolled.

  br i1 %exitcond, label %for.exit, label %for.header, !llvm.loop !0
...
!0 = distinct !{!0, !1, !2}
!1 = !{!"llvm.loop.vectorize.enable", i1 true}
!2 = !{!"llvm.loop.disable_nonforced"}

After a transformation is applied, follow-up attributes are set on the transformed and/or new loop(s). This allows additional attributes including followup-transformations to be specified. Specifying multiple transformations in the same metadata node is possible for compatibility reasons, but their execution order is undefined. For instance, when llvm.loop.vectorize.enable and llvm.loop.unroll.enable are specified at the same time, unrolling may occur either before or after vectorization.

As an example, the following instructs a loop to be vectorized and only then unrolled.

!0 = distinct !{!0, !1, !2, !3}
!1 = !{!"llvm.loop.vectorize.enable", i1 true}
!2 = !{!"llvm.loop.disable_nonforced"}
!3 = !{!"llvm.loop.vectorize.followup_vectorized", !{"llvm.loop.unroll.enable"}}

If, and only if, no followup is specified, the pass may add attributes itself. For instance, the vectorizer adds a llvm.loop.isvectorized attribute and all attributes from the original loop excluding its loop vectorizer attributes. To avoid this, an empty followup attribute can be used, e.g.

!3 = !{!"llvm.loop.vectorize.followup_vectorized"}

The followup attributes of a transformation that cannot be applied will never be added to a loop and are therefore effectively ignored. This means that any followup-transformation in such attributes requires that its prior transformations are applied before the followup-transformation. The user should receive a warning about the first transformation in the transformation chain that could not be applied if it a forced transformation. All following transformations are skipped.

Pass-Specific Transformation Metadata ¶

Transformation options are specific to each transformation. In the following, we present the model for each LLVM loop optimization pass and the metadata to influence them.

Loop Vectorization and Interleaving ¶

Loop vectorization and interleaving is interpreted as a single transformation. It is interpreted as forced if !{"llvm.loop.vectorize.enable", i1 true} is set.

Assuming the pre-vectorization loop is

for (int i = 0; i < n; i+=1) // original loop
  Stmt(i);

then the code after vectorization will be approximately (assuming an SIMD width of 4):

int i = 0;
if (rtc) {
  for (; i + 3 < n; i+=4) // vectorized/interleaved loop
    Stmt(i:i+3);
}
for (; i < n; i+=1) // epilogue loop
  Stmt(i);

where rtc is a generated runtime check.

llvm.loop.vectorize.followup_vectorized will set the attributes for the vectorized loop. If not specified, llvm.loop.isvectorized is combined with the original loop’s attributes to avoid it being vectorized multiple times.

llvm.loop.vectorize.followup_epilogue will set the attributes for the remainder loop. If not specified, it will have the original loop’s attributes combined with llvm.loop.isvectorized and llvm.loop.unroll.runtime.disable (unless the original loop already has unroll metadata).

The attributes specified by llvm.loop.vectorize.followup_all are added to both loops.

When using a follow-up attribute, it replaces any automatically deduced attributes for the generated loop in question. Therefore it is recommended to add llvm.loop.isvectorized to llvm.loop.vectorize.followup_all which avoids that the loop vectorizer tries to optimize the loops again.

Loop Unrolling ¶

Unrolling is interpreted as forced any !{!"llvm.loop.unroll.enable"} metadata or option (llvm.loop.unroll.count, llvm.loop.unroll.full) is present. Unrolling can be full unrolling, partial unrolling of a loop with constant trip count or runtime unrolling of a loop with a trip count unknown at compile-time.

If the loop has been unrolled fully, there is no followup-loop. For partial/runtime unrolling, the original loop of

for (int i = 0; i < n; i+=1) // original loop
  Stmt(i);

is transformed into (using an unroll factor of 4):

int i = 0;
for (; i + 3 < n; i+=4) // unrolled loop
  Stmt(i);
  Stmt(i+1);
  Stmt(i+2);
  Stmt(i+3);
}
for (; i < n; i+=1) // remainder loop
  Stmt(i);

llvm.loop.unroll.followup_unrolled will set the loop attributes of the unrolled loop. If not specified, the attributes of the original loop without the llvm.loop.unroll.* attributes are copied and llvm.loop.unroll.disable added to it.

llvm.loop.unroll.followup_remainder defines the attributes of the remainder loop. If not specified the remainder loop will have no attributes. The remainder loop might not be present due to being fully unrolled in which case this attribute has no effect.

Attributes defined in llvm.loop.unroll.followup_all are added to the unrolled and remainder loops.

To avoid that the partially unrolled loop is unrolled again, it is recommended to add llvm.loop.unroll.disable to llvm.loop.unroll.followup_all. If no follow-up attribute specified for a generated loop, it is added automatically.

Unroll-And-Jam ¶

Unroll-and-jam uses the following transformation model (here with an unroll factor if 2). Currently, it does not support a fallback version when the transformation is unsafe.

for (int i = 0; i < n; i+=1) { // original outer loop
  Fore(i);
  for (int j = 0; j < m; j+=1) // original inner loop
    SubLoop(i, j);
  Aft(i);
}

int i = 0;
for (; i + 1 < n; i+=2) { // unrolled outer loop
  Fore(i);
  Fore(i+1);
  for (int j = 0; j < m; j+=1) { // unrolled inner loop
    SubLoop(i, j);
    SubLoop(i+1, j);
  }
  Aft(i);
  Aft(i+1);
}
for (; i < n; i+=1) { // remainder outer loop
  Fore(i);
  for (int j = 0; j < m; j+=1) // remainder inner loop
    SubLoop(i, j);
  Aft(i);
}

llvm.loop.unroll_and_jam.followup_outer will set the loop attributes of the unrolled outer loop. If not specified, the attributes of the original outer loop without the llvm.loop.unroll.* attributes are copied and llvm.loop.unroll.disable added to it.

llvm.loop.unroll_and_jam.followup_inner will set the loop attributes of the unrolled inner loop. If not specified, the attributes of the original inner loop are used unchanged.

llvm.loop.unroll_and_jam.followup_remainder_outer sets the loop attributes of the outer remainder loop. If not specified it will not have any attributes. The remainder loop might not be present due to being fully unrolled.

llvm.loop.unroll_and_jam.followup_remainder_inner sets the loop attributes of the inner remainder loop. If not specified it will have the attributes of the original inner loop. It the outer remainder loop is unrolled, the inner remainder loop might be present multiple times.

Attributes defined in llvm.loop.unroll_and_jam.followup_all are added to all of the aforementioned output loops.

To avoid that the unrolled loop is unrolled again, it is recommended to add llvm.loop.unroll.disable to llvm.loop.unroll_and_jam.followup_all. It suppresses unroll-and-jam as well as an additional inner loop unrolling. If no follow-up attribute specified for a generated loop, it is added automatically.

Loop Distribution ¶

The LoopDistribution pass tries to separate vectorizable parts of a loop from the non-vectorizable part (which otherwise would make the entire loop non-vectorizable). Conceptually, it transforms a loop such as

for (int i = 1; i < n; i+=1) { // original loop
  A[i] = i;
  B[i] = 2 + B[i];
  C[i] = 3 + C[i - 1];
}

into the following code:

if (rtc) {
  for (int i = 1; i < n; i+=1) // coincident loop
    A[i] = i;
  for (int i = 1; i < n; i+=1) // coincident loop
    B[i] = 2 + B[i];
  for (int i = 1; i < n; i+=1) // sequential loop
    C[i] = 3 + C[i - 1];
} else {
  for (int i = 1; i < n; i+=1) { // fallback loop
    A[i] = i;
    B[i] = 2 + B[i];
    C[i] = 3 + C[i - 1];
  }
}

where rtc is a generated runtime check.

llvm.loop.distribute.followup_coincident sets the loop attributes of all loops without loop-carried dependencies (i.e. vectorizable loops). There might be more than one such loops. If not defined, the loops will inherit the original loop’s attributes.

llvm.loop.distribute.followup_sequential sets the loop attributes of the loop with potentially unsafe dependencies. There should be at most one such loop. If not defined, the loop will inherit the original loop’s attributes.

llvm.loop.distribute.followup_fallback defines the loop attributes for the fallback loop, which is a copy of the original loop for when loop versioning is required. If undefined, the fallback loop inherits all attributes from the original loop.

Attributes defined in llvm.loop.distribute.followup_all are added to all of the aforementioned output loops.

It is recommended to add llvm.loop.disable_nonforced to llvm.loop.distribute.followup_fallback. This avoids that the fallback version (which is likely never executed) is further optimzed which would increase the code size.

Versioning LICM ¶

The pass hoists code out of loops that are only loop-invariant when dynamic conditions apply. For instance, it transforms the loop

for (int i = 0; i < n; i+=1) // original loop
  A[i] = B[0];

into:

if (rtc) {
  auto b = B[0];
  for (int i = 0; i < n; i+=1) // versioned loop
    A[i] = b;
} else {
  for (int i = 0; i < n; i+=1) // unversioned loop
    A[i] = B[0];
}

The runtime condition (rtc) checks that the array A and the element B[0] do not alias.

Currently, this transformation does not support followup-attributes.

Loop Interchange ¶

Currently, the LoopInterchange pass does not use any metadata.

Ambiguous Transformation Order ¶

If there multiple transformations defined, the order in which they are executed depends on the order in LLVM’s pass pipeline, which is subject to change. The default optimization pipeline (anything higher than -O0) has the following order.

When using the legacy pass manager:

LoopInterchange (if enabled)

SimpleLoopUnroll/LoopFullUnroll (only performs full unrolling)

VersioningLICM (if enabled)

LoopDistribute

LoopVectorizer

LoopUnrollAndJam (if enabled)

LoopUnroll (partial and runtime unrolling)

When using the legacy pass manager with LTO:

LoopInterchange (if enabled)

SimpleLoopUnroll/LoopFullUnroll (only performs full unrolling)

LoopVectorizer

LoopUnroll (partial and runtime unrolling)

When using the new pass manager:

SimpleLoopUnroll/LoopFullUnroll (only performs full unrolling)

LoopDistribute

LoopVectorizer

LoopUnrollAndJam (if enabled)

LoopUnroll (partial and runtime unrolling)

Leftover Transformations ¶

Forced transformations that have not been applied after the last transformation pass should be reported to the user. The transformation passes themselves cannot be responsible for this reporting because they might not be in the pipeline, there might be multiple passes able to apply a transformation (e.g. LoopInterchange and Polly) or a transformation attribute may be ‘hidden’ inside another passes’ followup attribute.

The pass -transform-warning (WarnMissedTransformationsPass) emits such warnings. It should be placed after the last transformation pass.

The current pass pipeline has a fixed order in which transformations passes are executed. A transformation can be in the followup of a pass that is executed later and thus leftover. For instance, a loop nest cannot be distributed and then interchanged with the current pass pipeline. The loop distribution will execute, but there is no loop interchange pass following such that any loop interchange metadata will be ignored. The -transform-warning should emit a warning in this case.

Future versions of LLVM may fix this by executing transformations using a dynamic ordering.