LLVM  15.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 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 SROAPass : public PassInfoMixin<SROAPass> {
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.
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. We also make sure there is no dangling pointers.
81  SmallVector<WeakVH, 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.
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.
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.
110 
111 public:
112  SROAPass() = default;
113 
114  /// Run the pass over the function.
116 
117 private:
119  friend class sroa::SROALegacyPass;
120 
121  /// Helper used by both the public run method and by the legacy pass.
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
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
llvm::PassInfoMixin
A CRTP mix-in to automatically provide informational APIs needed for passes.
Definition: PassManager.h:371
llvm::Function
Definition: Function.h:60
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:4815
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1185
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:166
llvm::sroa::SROALegacyPass
A legacy pass for the legacy pass manager that wraps the SROA pass.
Definition: SROA.cpp:4776
llvm::SROAPass::SROAPass
SROAPass()=default
llvm::SROAPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Run the pass over the function.
Definition: SROA.cpp:4767
llvm::sroa::AllocaSlices
Representation of the alloca slices.
Definition: SROA.cpp:218
F
#define F(x, y, z)
Definition: MD5.cpp:55
llvm::sroa::AllocaSliceRewriter
Visitor to rewrite instructions using p particular slice of an alloca to use a new alloca.
Definition: SROA.cpp:2245
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:176
llvm::LLVMContext
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:68
llvm::AssumptionCache
A cache of @llvm.assume calls within a function.
Definition: AssumptionCache.h:42
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:125
ValueHandle.h
PassManager.h
llvm::SROAPass
An optimization pass providing Scalar Replacement of Aggregates.
Definition: SROA.h:64
AllocaSlices
llvm::sroa::Partition
A partition of the slices.
Definition: SROA.cpp:350
SmallVector.h
llvm::SmallPtrSetImpl
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:344
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:42
llvm::AllocaInst
an instruction to allocate memory on the stack
Definition: Instructions.h:58
llvm::SetVector
A vector that has set insertion semantics.
Definition: SetVector.h:40
llvm::codeview::PublicSymFlags::Function
@ Function
SetVector.h
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43