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