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