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 111