contrib/llvm/include/llvm/Transforms/Scalar/SpeculateAroundPHIs.h

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