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