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 112