1 //===- SROA.h - Scalar Replacement Of Aggregates ----------------*- 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 /// \file 9 /// This file provides the interface for LLVM's Scalar Replacement of 10 /// Aggregates pass. This pass provides both aggregate splitting and the 11 /// primary SSA formation used in the compiler. 12 /// 13 //===----------------------------------------------------------------------===// 14 15 #ifndef LLVM_TRANSFORMS_SCALAR_SROA_H 16 #define LLVM_TRANSFORMS_SCALAR_SROA_H 17 18 #include "llvm/ADT/MapVector.h" 19 #include "llvm/ADT/PointerIntPair.h" 20 #include "llvm/ADT/SetVector.h" 21 #include "llvm/ADT/SmallVector.h" 22 #include "llvm/IR/PassManager.h" 23 #include "llvm/IR/ValueHandle.h" 24 #include <variant> 25 #include <vector> 26 27 namespace llvm { 28 29 class AllocaInst; 30 class LoadInst; 31 class StoreInst; 32 class AssumptionCache; 33 class DominatorTree; 34 class DomTreeUpdater; 35 class Function; 36 class LLVMContext; 37 class PHINode; 38 class SelectInst; 39 class Use; 40 41 /// A private "module" namespace for types and utilities used by SROA. These 42 /// are implementation details and should not be used by clients. 43 namespace LLVM_LIBRARY_VISIBILITY sroa { 44 45 class AllocaSliceRewriter; 46 class AllocaSlices; 47 class Partition; 48 class SROALegacyPass; 49 50 class SelectHandSpeculativity { 51 unsigned char Storage = 0; // None are speculatable by default. 52 using TrueVal = Bitfield::Element<bool, 0, 1>; // Low 0'th bit. 53 using FalseVal = Bitfield::Element<bool, 1, 1>; // Low 1'th bit. 54 public: 55 SelectHandSpeculativity() = default; 56 SelectHandSpeculativity &setAsSpeculatable(bool isTrueVal); 57 bool isSpeculatable(bool isTrueVal) const; 58 bool areAllSpeculatable() const; 59 bool areAnySpeculatable() const; 60 bool areNoneSpeculatable() const; 61 // For interop as int half of PointerIntPair. 62 explicit operator intptr_t() const { return static_cast<intptr_t>(Storage); } 63 explicit SelectHandSpeculativity(intptr_t Storage_) : Storage(Storage_) {} 64 }; 65 static_assert(sizeof(SelectHandSpeculativity) == sizeof(unsigned char)); 66 67 using PossiblySpeculatableLoad = 68 PointerIntPair<LoadInst *, 2, sroa::SelectHandSpeculativity>; 69 using UnspeculatableStore = StoreInst *; 70 using RewriteableMemOp = 71 std::variant<PossiblySpeculatableLoad, UnspeculatableStore>; 72 using RewriteableMemOps = SmallVector<RewriteableMemOp, 2>; 73 74 } // end namespace sroa 75 76 enum class SROAOptions : bool { ModifyCFG, PreserveCFG }; 77 78 /// An optimization pass providing Scalar Replacement of Aggregates. 79 /// 80 /// This pass takes allocations which can be completely analyzed (that is, they 81 /// don't escape) and tries to turn them into scalar SSA values. There are 82 /// a few steps to this process. 83 /// 84 /// 1) It takes allocations of aggregates and analyzes the ways in which they 85 /// are used to try to split them into smaller allocations, ideally of 86 /// a single scalar data type. It will split up memcpy and memset accesses 87 /// as necessary and try to isolate individual scalar accesses. 88 /// 2) It will transform accesses into forms which are suitable for SSA value 89 /// promotion. This can be replacing a memset with a scalar store of an 90 /// integer value, or it can involve speculating operations on a PHI or 91 /// select to be a PHI or select of the results. 92 /// 3) Finally, this will try to detect a pattern of accesses which map cleanly 93 /// onto insert and extract operations on a vector value, and convert them to 94 /// this form. By doing so, it will enable promotion of vector aggregates to 95 /// SSA vector values. 96 class SROAPass : public PassInfoMixin<SROAPass> { 97 LLVMContext *C = nullptr; 98 DomTreeUpdater *DTU = nullptr; 99 AssumptionCache *AC = nullptr; 100 const bool PreserveCFG; 101 102 /// Worklist of alloca instructions to simplify. 103 /// 104 /// Each alloca in the function is added to this. Each new alloca formed gets 105 /// added to it as well to recursively simplify unless that alloca can be 106 /// directly promoted. Finally, each time we rewrite a use of an alloca other 107 /// the one being actively rewritten, we add it back onto the list if not 108 /// already present to ensure it is re-visited. 109 SmallSetVector<AllocaInst *, 16> Worklist; 110 111 /// A collection of instructions to delete. 112 /// We try to batch deletions to simplify code and make things a bit more 113 /// efficient. We also make sure there is no dangling pointers. 114 SmallVector<WeakVH, 8> DeadInsts; 115 116 /// Post-promotion worklist. 117 /// 118 /// Sometimes we discover an alloca which has a high probability of becoming 119 /// viable for SROA after a round of promotion takes place. In those cases, 120 /// the alloca is enqueued here for re-processing. 121 /// 122 /// Note that we have to be very careful to clear allocas out of this list in 123 /// the event they are deleted. 124 SmallSetVector<AllocaInst *, 16> PostPromotionWorklist; 125 126 /// A collection of alloca instructions we can directly promote. 127 std::vector<AllocaInst *> PromotableAllocas; 128 129 /// A worklist of PHIs to speculate prior to promoting allocas. 130 /// 131 /// All of these PHIs have been checked for the safety of speculation and by 132 /// being speculated will allow promoting allocas currently in the promotable 133 /// queue. 134 SmallSetVector<PHINode *, 8> SpeculatablePHIs; 135 136 /// A worklist of select instructions to rewrite prior to promoting 137 /// allocas. 138 SmallMapVector<SelectInst *, sroa::RewriteableMemOps, 8> SelectsToRewrite; 139 140 /// Select instructions that use an alloca and are subsequently loaded can be 141 /// rewritten to load both input pointers and then select between the result, 142 /// allowing the load of the alloca to be promoted. 143 /// From this: 144 /// %P2 = select i1 %cond, ptr %Alloca, ptr %Other 145 /// %V = load <type>, ptr %P2 146 /// to: 147 /// %V1 = load <type>, ptr %Alloca -> will be mem2reg'd 148 /// %V2 = load <type>, ptr %Other 149 /// %V = select i1 %cond, <type> %V1, <type> %V2 150 /// 151 /// We can do this to a select if its only uses are loads 152 /// and if either the operand to the select can be loaded unconditionally, 153 /// or if we are allowed to perform CFG modifications. 154 /// If found an intervening bitcast with a single use of the load, 155 /// allow the promotion. 156 static std::optional<sroa::RewriteableMemOps> 157 isSafeSelectToSpeculate(SelectInst &SI, bool PreserveCFG); 158 159 public: 160 /// If \p PreserveCFG is set, then the pass is not allowed to modify CFG 161 /// in any way, even if it would update CFG analyses. 162 SROAPass(SROAOptions PreserveCFG); 163 164 /// Run the pass over the function. 165 PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); 166 167 void printPipeline(raw_ostream &OS, 168 function_ref<StringRef(StringRef)> MapClassName2PassName); 169 170 private: 171 friend class sroa::AllocaSliceRewriter; 172 friend class sroa::SROALegacyPass; 173 174 /// Helper used by both the public run method and by the legacy pass. 175 PreservedAnalyses runImpl(Function &F, DomTreeUpdater &RunDTU, 176 AssumptionCache &RunAC); 177 PreservedAnalyses runImpl(Function &F, DominatorTree &RunDT, 178 AssumptionCache &RunAC); 179 180 bool presplitLoadsAndStores(AllocaInst &AI, sroa::AllocaSlices &AS); 181 AllocaInst *rewritePartition(AllocaInst &AI, sroa::AllocaSlices &AS, 182 sroa::Partition &P); 183 bool splitAlloca(AllocaInst &AI, sroa::AllocaSlices &AS); 184 std::pair<bool /*Changed*/, bool /*CFGChanged*/> runOnAlloca(AllocaInst &AI); 185 void clobberUse(Use &U); 186 bool deleteDeadInstructions(SmallPtrSetImpl<AllocaInst *> &DeletedAllocas); 187 bool promoteAllocas(Function &F); 188 }; 189 190 } // end namespace llvm 191 192 #endif // LLVM_TRANSFORMS_SCALAR_SROA_H 193