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