include/llvm/Transforms/Scalar/SpeculateAroundPHIs.h

   1 //===- SpeculateAroundPHIs.h - Speculate around PHIs ------------*- C++ -*-===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #ifndef LLVM_TRANSFORMS_SCALAR_SPECULATEAROUNDPHIS_H
  10 #define LLVM_TRANSFORMS_SCALAR_SPECULATEAROUNDPHIS_H
  11
  12 #include "llvm/ADT/SetVector.h"
  13 #include "llvm/Analysis/AssumptionCache.h"
  14 #include "llvm/IR/Dominators.h"
  15 #include "llvm/IR/Function.h"
  16 #include "llvm/IR/PassManager.h"
  17 #include "llvm/Support/Compiler.h"
  18 #include <vector>
  19
  20 namespace llvm {
  21
  22 /// This pass handles simple speculating of  instructions around PHIs when
  23 /// doing so is profitable for a particular target despite duplicated
  24 /// instructions.
  25 ///
  26 /// The motivating example are PHIs of constants which will require
  27 /// materializing the constants along each edge. If the PHI is used by an
  28 /// instruction where the target can materialize the constant as part of the
  29 /// instruction, it is profitable to speculate those instructions around the
  30 /// PHI node. This can reduce dynamic instruction count as well as decrease
  31 /// register pressure.
  32 ///
  33 /// Consider this IR for example:
  34 ///   ```
  35 ///   entry:
  36 ///     br i1 %flag, label %a, label %b
  37 ///
  38 ///   a:
  39 ///     br label %exit
  40 ///
  41 ///   b:
  42 ///     br label %exit
  43 ///
  44 ///   exit:
  45 ///     %p = phi i32 [ 7, %a ], [ 11, %b ]
  46 ///     %sum = add i32 %arg, %p
  47 ///     ret i32 %sum
  48 ///   ```
  49 /// To materialize the inputs to this PHI node may require an explicit
  50 /// instruction. For example, on x86 this would turn into something like
  51 ///   ```
  52 ///     testq %eax, %eax
  53 ///     movl $7, %rNN
  54 ///     jne .L
  55 ///     movl $11, %rNN
  56 ///   .L:
  57 ///     addl %edi, %rNN
  58 ///     movl %rNN, %eax
  59 ///     retq
  60 ///   ```
  61 /// When these constants can be folded directly into another instruction, it
  62 /// would be preferable to avoid the potential for register pressure (above we
  63 /// can easily avoid it, but that isn't always true) and simply duplicate the
  64 /// instruction using the PHI:
  65 ///   ```
  66 ///   entry:
  67 ///     br i1 %flag, label %a, label %b
  68 ///
  69 ///   a:
  70 ///     %sum.1 = add i32 %arg, 7
  71 ///     br label %exit
  72 ///
  73 ///   b:
  74 ///     %sum.2 = add i32 %arg, 11
  75 ///     br label %exit
  76 ///
  77 ///   exit:
  78 ///     %p = phi i32 [ %sum.1, %a ], [ %sum.2, %b ]
  79 ///     ret i32 %p
  80 ///   ```
  81 /// Which will generate something like the following on x86:
  82 ///   ```
  83 ///     testq %eax, %eax
  84 ///     addl $7, %edi
  85 ///     jne .L
  86 ///     addl $11, %edi
  87 ///   .L:
  88 ///     movl %edi, %eax
  89 ///     retq
  90 ///   ```
  91 ///
  92 /// It is important to note that this pass is never intended to handle more
  93 /// complex cases where speculating around PHIs allows simplifications of the
  94 /// IR itself or other subsequent optimizations. Those can and should already
  95 /// be handled before this pass is ever run by a more powerful analysis that
  96 /// can reason about equivalences and common subexpressions. Classically, those
  97 /// cases would be handled by a GVN-powered PRE or similar transform. This
  98 /// pass, in contrast, is *only* interested in cases where despite no
  99 /// simplifications to the IR itself, speculation is *faster* to execute. The
 100 /// result of this is that the cost models which are appropriate to consider
 101 /// here are relatively simple ones around execution and codesize cost, without
 102 /// any need to consider simplifications or other transformations.
 103 struct SpeculateAroundPHIsPass : PassInfoMixin<SpeculateAroundPHIsPass> {
 104   /// Run the pass over the function.
 105   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
 106 };
 107
 108 } // end namespace llvm
 109
 110 #endif // LLVM_TRANSFORMS_SCALAR_SPECULATEAROUNDPHIS_H