LLVM  14.0.0git
SROA.h
Go to the documentation of this file.
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.
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.
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.
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.
111 
112 public:
113  SROA() = default;
114 
115  /// Run the pass over the function.
117 
118 private:
120  friend class sroa::SROALegacyPass;
121 
122  /// Helper used by both the public run method and by the legacy pass.
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
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:155
llvm
This file implements support for optimizing divisions by a constant.
Definition: AllocatorList.h:23
llvm::PassInfoMixin
A CRTP mix-in to automatically provide informational APIs needed for passes.
Definition: PassManager.h:374
llvm::Function
Definition: Function.h:62
P
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper which DAGCombine can t really do The code for turning x load into a single vector load is target independent and should be moved to the dag combiner The code for turning x load into a vector load can only handle a direct load from a global or a direct load from the stack It should be generalized to handle any load from P
Definition: README-SSE.txt:411
sroa
sroa
Definition: SROA.cpp:4808
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1168
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:151
llvm::sroa::SROALegacyPass
A legacy pass for the legacy pass manager that wraps the SROA pass.
Definition: SROA.cpp:4769
llvm::sroa::AllocaSlices
Representation of the alloca slices.
Definition: SROA.cpp:221
F
#define F(x, y, z)
Definition: MD5.cpp:56
llvm::SROA::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Run the pass over the function.
Definition: SROA.cpp:4760
llvm::sroa::AllocaSliceRewriter
Visitor to rewrite instructions using p particular slice of an alloca to use a new alloca.
Definition: SROA.cpp:2236
C
(vector float) vec_cmpeq(*A, *B) C
Definition: README_ALTIVEC.txt:86
runImpl
static bool runImpl(const TargetLibraryInfo &TLI, Function &F)
Definition: ReplaceWithVeclib.cpp:177
llvm::LLVMContext
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:68
llvm::SROA::SROA
SROA()=default
llvm::ReplayInlineScope::Function
@ Function
llvm::AssumptionCache
A cache of @llvm.assume calls within a function.
Definition: AssumptionCache.h:41
LLVM_LIBRARY_VISIBILITY
#define LLVM_LIBRARY_VISIBILITY
LLVM_LIBRARY_VISIBILITY - If a class marked with this attribute is linked into a shared library,...
Definition: Compiler.h:131
ValueHandle.h
PassManager.h
AllocaSlices
llvm::sroa::Partition
A partition of the slices.
Definition: SROA.cpp:353
SmallVector.h
llvm::SmallPtrSetImpl
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:343
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:44
llvm::AllocaInst
an instruction to allocate memory on the stack
Definition: Instructions.h:62
llvm::SetVector
A vector that has set insertion semantics.
Definition: SetVector.h:40
llvm::SROA
An optimization pass providing Scalar Replacement of Aggregates.
Definition: SROA.h:65
SetVector.h
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:44