1 //===- SROA.h - Scalar Replacement Of Aggregates ----------------*- 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 /// \file 10 /// This file provides the interface for LLVM's Scalar Replacement of 11 /// Aggregates pass. This pass provides both aggregate splitting and the 12 /// primary SSA formation used in the compiler. 13 /// 14 //===----------------------------------------------------------------------===// 15 16 #ifndef LLVM_TRANSFORMS_SCALAR_SROA_H 17 #define LLVM_TRANSFORMS_SCALAR_SROA_H 18 19 #include "llvm/ADT/SetVector.h" 20 #include "llvm/ADT/SmallVector.h" 21 #include "llvm/IR/PassManager.h" 22 #include "llvm/Support/Compiler.h" 23 #include <vector> 24 25 namespace llvm { 26 27 class AllocaInst; 28 class AssumptionCache; 29 class DominatorTree; 30 class Function; 31 class Instruction; 32 class LLVMContext; 33 class PHINode; 34 class SelectInst; 35 class Use; 36 37 /// A private "module" namespace for types and utilities used by SROA. These 38 /// are implementation details and should not be used by clients. 39 namespace sroa LLVM_LIBRARY_VISIBILITY { 40 41 class AllocaSliceRewriter; 42 class AllocaSlices; 43 class Partition; 44 class SROALegacyPass; 45 46 } // end namespace sroa 47 48 /// An optimization pass providing Scalar Replacement of Aggregates. 49 /// 50 /// This pass takes allocations which can be completely analyzed (that is, they 51 /// don't escape) and tries to turn them into scalar SSA values. There are 52 /// a few steps to this process. 53 /// 54 /// 1) It takes allocations of aggregates and analyzes the ways in which they 55 /// are used to try to split them into smaller allocations, ideally of 56 /// a single scalar data type. It will split up memcpy and memset accesses 57 /// as necessary and try to isolate individual scalar accesses. 58 /// 2) It will transform accesses into forms which are suitable for SSA value 59 /// promotion. This can be replacing a memset with a scalar store of an 60 /// integer value, or it can involve speculating operations on a PHI or 61 /// select to be a PHI or select of the results. 62 /// 3) Finally, this will try to detect a pattern of accesses which map cleanly 63 /// onto insert and extract operations on a vector value, and convert them to 64 /// this form. By doing so, it will enable promotion of vector aggregates to 65 /// SSA vector values. 66 class SROA : public PassInfoMixin<SROA> { 67 LLVMContext *C = nullptr; 68 DominatorTree *DT = nullptr; 69 AssumptionCache *AC = nullptr; 70 71 /// Worklist of alloca instructions to simplify. 72 /// 73 /// Each alloca in the function is added to this. Each new alloca formed gets 74 /// added to it as well to recursively simplify unless that alloca can be 75 /// directly promoted. Finally, each time we rewrite a use of an alloca other 76 /// the one being actively rewritten, we add it back onto the list if not 77 /// already present to ensure it is re-visited. 78 SetVector<AllocaInst *, SmallVector<AllocaInst *, 16>> Worklist; 79 80 /// A collection of instructions to delete. 81 /// We try to batch deletions to simplify code and make things a bit more 82 /// efficient. 83 SetVector<Instruction *, SmallVector<Instruction *, 8>> DeadInsts; 84 85 /// Post-promotion worklist. 86 /// 87 /// Sometimes we discover an alloca which has a high probability of becoming 88 /// viable for SROA after a round of promotion takes place. In those cases, 89 /// the alloca is enqueued here for re-processing. 90 /// 91 /// Note that we have to be very careful to clear allocas out of this list in 92 /// the event they are deleted. 93 SetVector<AllocaInst *, SmallVector<AllocaInst *, 16>> PostPromotionWorklist; 94 95 /// A collection of alloca instructions we can directly promote. 96 std::vector<AllocaInst *> PromotableAllocas; 97 98 /// A worklist of PHIs to speculate prior to promoting allocas. 99 /// 100 /// All of these PHIs have been checked for the safety of speculation and by 101 /// being speculated will allow promoting allocas currently in the promotable 102 /// queue. 103 SetVector<PHINode *, SmallVector<PHINode *, 2>> SpeculatablePHIs; 104 105 /// A worklist of select instructions to speculate prior to promoting 106 /// allocas. 107 /// 108 /// All of these select instructions have been checked for the safety of 109 /// speculation and by being speculated will allow promoting allocas 110 /// currently in the promotable queue. 111 SetVector<SelectInst *, SmallVector<SelectInst *, 2>> SpeculatableSelects; 112 113 public: 114 SROA() = default; 115 116 /// Run the pass over the function. 117 PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); 118 119 private: 120 friend class sroa::AllocaSliceRewriter; 121 friend class sroa::SROALegacyPass; 122 123 /// Helper used by both the public run method and by the legacy pass. 124 PreservedAnalyses runImpl(Function &F, DominatorTree &RunDT, 125 AssumptionCache &RunAC); 126 127 bool presplitLoadsAndStores(AllocaInst &AI, sroa::AllocaSlices &AS); 128 AllocaInst *rewritePartition(AllocaInst &AI, sroa::AllocaSlices &AS, 129 sroa::Partition &P); 130 bool splitAlloca(AllocaInst &AI, sroa::AllocaSlices &AS); 131 bool runOnAlloca(AllocaInst &AI); 132 void clobberUse(Use &U); 133 bool deleteDeadInstructions(SmallPtrSetImpl<AllocaInst *> &DeletedAllocas); 134 bool promoteAllocas(Function &F); 135 }; 136 137 } // end namespace llvm 138 139 #endif // LLVM_TRANSFORMS_SCALAR_SROA_H 140