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