LLVM  10.0.0svn
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 <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.
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.
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  SROA() = 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
uint64_t CallInst * C
static bool runImpl(Function &F, TargetLibraryInfo &TLI, DominatorTree &DT)
This is the entry point for all transforms.
This class represents lattice values for constants.
Definition: AllocatorList.h:23
Representation of the alloca slices.
Definition: SROA.cpp:231
A cache of @llvm.assume calls within a function.
F(f)
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:343
A Use represents the edge between a Value definition and its users.
Definition: Use.h:55
A partition of the slices.
Definition: SROA.cpp:355
A CRTP mix-in to automatically provide informational APIs needed for passes.
Definition: PassManager.h:372
A legacy pass for the legacy pass manager that wraps the SROA pass.
Definition: SROA.cpp:4608
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:144
#define P(N)
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:153
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:64
sroa
Definition: SROA.cpp:4647
#define LLVM_LIBRARY_VISIBILITY
LLVM_LIBRARY_VISIBILITY - If a class marked with this attribute is linked into a shared library...
Definition: Compiler.h:115
Visitor to rewrite instructions using p particular slice of an alloca to use a new alloca...
Definition: SROA.cpp:2253
A vector that has set insertion semantics.
Definition: SetVector.h:40
An optimization pass providing Scalar Replacement of Aggregates.
Definition: SROA.h:64
This header defines various interfaces for pass management in LLVM.
an instruction to allocate memory on the stack
Definition: Instructions.h:59