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