454 lines · plain
1.. _transformation-metadata:2 3============================4Code Transformation Metadata5============================6 7.. contents::8 :local:9 10Overview11========12 13LLVM transformation passes can be controlled by attaching metadata to14the code to transform. By default, transformation passes use heuristics15to determine whether or not to perform transformations, and when doing16so, other details of how the transformations are applied (e.g., which17vectorization factor to select).18Unless the optimizer is otherwise directed, transformations are applied19conservatively. This conservatism generally allows the optimizer to20avoid unprofitable transformations, but in practice, this results in the21optimizer not applying transformations that would be highly profitable.22 23Frontends can give additional hints to LLVM passes on which24transformations they should apply. This can be additional knowledge that25cannot be derived from the emitted IR, or directives passed from the26user/programmer. OpenMP pragmas are an example of the latter.27 28If any such metadata is dropped from the program, the code's semantics29must not change.30 31Metadata on Loops32=================33 34Attributes can be attached to loops as described in :ref:`llvm.loop`.35Attributes can describe properties of the loop, disable transformations,36force specific transformations and set transformation options.37 38Because metadata nodes are immutable (with the exception of39``MDNode::replaceOperandWith`` which is dangerous to use on uniqued40metadata), in order to add or remove a loop attributes, a new ``MDNode``41must be created and assigned as the new ``llvm.loop`` metadata. Any42connection between the old ``MDNode`` and the loop is lost. The43``llvm.loop`` node is also used as LoopID (``Loop::getLoopID()``), i.e.44the loop effectively gets a new identifier. For instance,45``llvm.mem.parallel_loop_access`` references the LoopID. Therefore, if46the parallel access property is to be preserved after adding/removing47loop attributes, any ``llvm.mem.parallel_loop_access`` reference must be48updated to the new LoopID.49 50Transformation Metadata Structure51=================================52 53Some attributes describe code transformations (unrolling, vectorizing,54loop distribution, etc.). They can either be a hint to the optimizer55that a transformation might be beneficial, instruction to use a specific56option, , or convey a specific request from the user (such as57``#pragma clang loop`` or ``#pragma omp simd``).58 59If a transformation is forced but cannot be carried-out for any reason,60an optimization-missed warning must be emitted. Semantic information61such as a transformation being safe (e.g.62``llvm.mem.parallel_loop_access``) can be unused by the optimizer63without generating a warning.64 65Unless explicitly disabled, any optimization pass may heuristically66determine whether a transformation is beneficial and apply it. If67metadata for another transformation was specified, applying a different68transformation before it might be inadvertent due to being applied on a69different loop or the loop not existing anymore. To avoid having to70explicitly disable an unknown number of passes, the attribute71``llvm.loop.disable_nonforced`` disables all optional, high-level,72restructuring transformations.73 74The following example avoids the loop being altered before being75vectorized, for instance being unrolled.76 77.. code-block:: llvm78 79 br i1 %exitcond, label %for.exit, label %for.header, !llvm.loop !080 ...81 !0 = distinct !{!0, !1, !2}82 !1 = !{!"llvm.loop.vectorize.enable", i1 true}83 !2 = !{!"llvm.loop.disable_nonforced"}84 85After a transformation is applied, follow-up attributes are set on the86transformed and/or new loop(s). This allows additional attributes87including followup-transformations to be specified. Specifying multiple88transformations in the same metadata node is possible for compatibility89reasons, but their execution order is undefined. For instance, when90``llvm.loop.vectorize.enable`` and ``llvm.loop.unroll.enable`` are91specified at the same time, unrolling may occur either before or after92vectorization.93 94As an example, the following instructs a loop to be vectorized and only95then unrolled.96 97.. code-block:: llvm98 99 !0 = distinct !{!0, !1, !2, !3}100 !1 = !{!"llvm.loop.vectorize.enable", i1 true}101 !2 = !{!"llvm.loop.disable_nonforced"}102 !3 = !{!"llvm.loop.vectorize.followup_vectorized", !{"llvm.loop.unroll.enable"}}103 104If, and only if, no followup is specified, the pass may add attributes itself.105For instance, the vectorizer adds a ``llvm.loop.isvectorized`` attribute and106all attributes from the original loop excluding its loop vectorizer107attributes. To avoid this, an empty followup attribute can be used, e.g.108 109.. code-block:: llvm110 111 !3 = !{!"llvm.loop.vectorize.followup_vectorized"}112 113The followup attributes of a transformation that cannot be applied will114never be added to a loop and are therefore effectively ignored. This means115that any followup-transformation in such attributes requires that its116prior transformations are applied before the followup-transformation.117The user should receive a warning about the first transformation in the118transformation chain that could not be applied if it a forced119transformation. All following transformations are skipped.120 121Pass-Specific Transformation Metadata122=====================================123 124Transformation options are specific to each transformation. In the125following, we present the model for each LLVM loop optimization pass and126the metadata to influence them.127 128Loop Vectorization and Interleaving129-----------------------------------130 131Loop vectorization and interleaving is interpreted as a single132transformation. It is interpreted as forced if133``!{"llvm.loop.vectorize.enable", i1 true}`` is set.134 135Assuming the pre-vectorization loop is136 137.. code-block:: c138 139 for (int i = 0; i < n; i+=1) // original loop140 Stmt(i);141 142then the code after vectorization will be approximately (assuming an143SIMD width of 4):144 145.. code-block:: c146 147 int i = 0;148 if (rtc) {149 for (; i + 3 < n; i+=4) // vectorized/interleaved loop150 Stmt(i:i+3);151 }152 for (; i < n; i+=1) // epilogue loop153 Stmt(i);154 155where ``rtc`` is a generated runtime check.156 157``llvm.loop.vectorize.followup_vectorized`` will set the attributes for158the vectorized loop. If not specified, ``llvm.loop.isvectorized`` is159combined with the original loop's attributes to avoid it being160vectorized multiple times.161 162``llvm.loop.vectorize.followup_epilogue`` will set the attributes for163the remainder loop. If not specified, it will have the original loop's164attributes combined with ``llvm.loop.isvectorized`` and165``llvm.loop.unroll.runtime.disable`` (unless the original loop already166has unroll metadata).167 168The attributes specified by ``llvm.loop.vectorize.followup_all`` are169added to both loops.170 171When using a follow-up attribute, it replaces any automatically deduced172attributes for the generated loop in question. Therefore it is173recommended to add ``llvm.loop.isvectorized`` to174``llvm.loop.vectorize.followup_all`` which avoids that the loop175vectorizer tries to optimize the loops again.176 177Loop Unrolling178--------------179 180Unrolling is interpreted as forced any ``!{!"llvm.loop.unroll.enable"}``181metadata or option (``llvm.loop.unroll.count``, ``llvm.loop.unroll.full``)182is present. Unrolling can be full unrolling, partial unrolling of a loop183with constant trip count or runtime unrolling of a loop with a trip184count unknown at compile-time.185 186If the loop has been unrolled fully, there is no followup-loop. For187partial/runtime unrolling, the original loop of188 189.. code-block:: c190 191 for (int i = 0; i < n; i+=1) // original loop192 Stmt(i);193 194is transformed into (using an unroll factor of 4):195 196.. code-block:: c197 198 int i = 0;199 for (; i + 3 < n; i+=4) { // unrolled loop200 Stmt(i);201 Stmt(i+1);202 Stmt(i+2);203 Stmt(i+3);204 }205 for (; i < n; i+=1) // remainder loop206 Stmt(i);207 208``llvm.loop.unroll.followup_unrolled`` will set the loop attributes of209the unrolled loop. If not specified, the attributes of the original loop210without the ``llvm.loop.unroll.*`` attributes are copied and211``llvm.loop.unroll.disable`` added to it.212 213``llvm.loop.unroll.followup_remainder`` defines the attributes of the214remainder loop. If not specified the remainder loop will have no215attributes. The remainder loop might not be present due to being fully216unrolled in which case this attribute has no effect.217 218Attributes defined in ``llvm.loop.unroll.followup_all`` are added to the219unrolled and remainder loops.220 221To avoid that the partially unrolled loop is unrolled again, it is222recommended to add ``llvm.loop.unroll.disable`` to223``llvm.loop.unroll.followup_all``. If no follow-up attribute specified224for a generated loop, it is added automatically.225 226Unroll-And-Jam227--------------228 229Unroll-and-jam uses the following transformation model (here with an230unroll factor if 2). Currently, it does not support a fallback version231when the transformation is unsafe.232 233.. code-block:: c234 235 for (int i = 0; i < n; i+=1) { // original outer loop236 Fore(i);237 for (int j = 0; j < m; j+=1) // original inner loop238 SubLoop(i, j);239 Aft(i);240 }241 242.. code-block:: c243 244 int i = 0;245 for (; i + 1 < n; i+=2) { // unrolled outer loop246 Fore(i);247 Fore(i+1);248 for (int j = 0; j < m; j+=1) { // unrolled inner loop249 SubLoop(i, j);250 SubLoop(i+1, j);251 }252 Aft(i);253 Aft(i+1);254 }255 for (; i < n; i+=1) { // remainder outer loop256 Fore(i);257 for (int j = 0; j < m; j+=1) // remainder inner loop258 SubLoop(i, j);259 Aft(i);260 }261 262``llvm.loop.unroll_and_jam.followup_outer`` will set the loop attributes263of the unrolled outer loop. If not specified, the attributes of the264original outer loop without the ``llvm.loop.unroll.*`` attributes are265copied and ``llvm.loop.unroll.disable`` added to it.266 267``llvm.loop.unroll_and_jam.followup_inner`` will set the loop attributes268of the unrolled inner loop. If not specified, the attributes of the269original inner loop are used unchanged.270 271``llvm.loop.unroll_and_jam.followup_remainder_outer`` sets the loop272attributes of the outer remainder loop. If not specified it will not273have any attributes. The remainder loop might not be present due to274being fully unrolled.275 276``llvm.loop.unroll_and_jam.followup_remainder_inner`` sets the loop277attributes of the inner remainder loop. If not specified it will have278the attributes of the original inner loop. It the outer remainder loop279is unrolled, the inner remainder loop might be present multiple times.280 281Attributes defined in ``llvm.loop.unroll_and_jam.followup_all`` are282added to all of the aforementioned output loops.283 284To avoid that the unrolled loop is unrolled again, it is285recommended to add ``llvm.loop.unroll.disable`` to286``llvm.loop.unroll_and_jam.followup_all``. It suppresses unroll-and-jam287as well as an additional inner loop unrolling. If no follow-up288attribute specified for a generated loop, it is added automatically.289 290Loop Distribution291-----------------292 293The LoopDistribution pass tries to separate vectorizable parts of a loop294from the non-vectorizable part (which otherwise would make the entire295loop non-vectorizable). Conceptually, it transforms a loop such as296 297.. code-block:: c298 299 for (int i = 1; i < n; i+=1) { // original loop300 A[i] = i;301 B[i] = 2 + B[i];302 C[i] = 3 + C[i - 1];303 }304 305into the following code:306 307.. code-block:: c308 309 if (rtc) {310 for (int i = 1; i < n; i+=1) // coincident loop311 A[i] = i;312 for (int i = 1; i < n; i+=1) // coincident loop313 B[i] = 2 + B[i];314 for (int i = 1; i < n; i+=1) // sequential loop315 C[i] = 3 + C[i - 1];316 } else {317 for (int i = 1; i < n; i+=1) { // fallback loop318 A[i] = i;319 B[i] = 2 + B[i];320 C[i] = 3 + C[i - 1];321 }322 }323 324where ``rtc`` is a generated runtime check.325 326``llvm.loop.distribute.followup_coincident`` sets the loop attributes of327all loops without loop-carried dependencies (i.e. vectorizable loops).328There might be more than one such loops. If not defined, the loops will329inherit the original loop's attributes.330 331``llvm.loop.distribute.followup_sequential`` sets the loop attributes of the332loop with potentially unsafe dependencies. There should be at most one333such loop. If not defined, the loop will inherit the original loop's334attributes.335 336``llvm.loop.distribute.followup_fallback`` defines the loop attributes337for the fallback loop, which is a copy of the original loop for when338loop versioning is required. If undefined, the fallback loop inherits339all attributes from the original loop.340 341Attributes defined in ``llvm.loop.distribute.followup_all`` are added to342all of the aforementioned output loops.343 344It is recommended to add ``llvm.loop.disable_nonforced`` to345``llvm.loop.distribute.followup_fallback``. This avoids that the346fallback version (which is likely never executed) is further optimized347which would increase the code size.348 349Attributes defined in ``llvm.loop.isdistributed`` are added to successfully350distributed loops to prevent subsequent reprocessing.351 352As an example, the following instructs a loop to be ignored during353loop distribution.354 355.. code-block:: llvm356 357 !4 = distinct !{!4, !5, !6}358 !5 = !{!"llvm.loop.mustprogress"}359 !6 = !{!"llvm.loop.isdistributed", i32 1}360 361Versioning LICM362---------------363 364The pass hoists code out of loops that are only loop-invariant when365dynamic conditions apply. For instance, it transforms the loop366 367.. code-block:: c368 369 for (int i = 0; i < n; i+=1) // original loop370 A[i] = B[0];371 372into:373 374.. code-block:: c375 376 if (rtc) {377 auto b = B[0];378 for (int i = 0; i < n; i+=1) // versioned loop379 A[i] = b;380 } else {381 for (int i = 0; i < n; i+=1) // unversioned loop382 A[i] = B[0];383 }384 385The runtime condition (``rtc``) checks that the array ``A`` and the386element `B[0]` do not alias.387 388Currently, this transformation does not support followup-attributes.389 390Loop Interchange391----------------392 393Currently, the ``LoopInterchange`` pass does not use any metadata.394 395Ambiguous Transformation Order396==============================397 398If there multiple transformations defined, the order in which they are399executed depends on the order in LLVM's pass pipeline, which is subject400to change. The default optimization pipeline (anything higher than401``-O0``) has the following order.402 403When using the legacy pass manager:404 405 - LoopInterchange (if enabled)406 - SimpleLoopUnroll/LoopFullUnroll (only performs full unrolling)407 - VersioningLICM (if enabled)408 - LoopDistribute409 - LoopVectorizer410 - LoopUnrollAndJam (if enabled)411 - LoopUnroll (partial and runtime unrolling)412 413When using the legacy pass manager with LTO:414 415 - LoopInterchange (if enabled)416 - SimpleLoopUnroll/LoopFullUnroll (only performs full unrolling)417 - LoopVectorizer418 - LoopUnroll (partial and runtime unrolling)419 420When using the new pass manager:421 422 - SimpleLoopUnroll/LoopFullUnroll (only performs full unrolling)423 - LoopDistribute424 - LoopVectorizer425 - LoopUnrollAndJam (if enabled)426 - LoopUnroll (partial and runtime unrolling)427 428Leftover Transformations429========================430 431Forced transformations that have not been applied after the last432transformation pass should be reported to the user. The transformation433passes themselves cannot be responsible for this reporting because they434might not be in the pipeline, there might be multiple passes able to435apply a transformation (e.g. ``LoopInterchange`` and Polly) or a436transformation attribute may be 'hidden' inside another passes' followup437attribute.438 439The pass ``-transform-warning`` (``WarnMissedTransformationsPass``)440emits such warnings. It should be placed after the last transformation441pass.442 443The current pass pipeline has a fixed order in which transformations444passes are executed. A transformation can be in the followup of a pass445that is executed later and thus leftover. For instance, a loop nest446cannot be distributed and then interchanged with the current pass447pipeline. The loop distribution will execute, but there is no loop448interchange pass following such that any loop interchange metadata will449be ignored. The ``-transform-warning`` should emit a warning in this450case.451 452Future versions of LLVM may fix this by executing transformations using453a dynamic ordering.454