LLVM 17.0.0git
Go to the documentation of this file.
1//===- SROA.h - Scalar Replacement Of Aggregates ----------------*- C++ -*-===//
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
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.
18#include "llvm/ADT/MapVector.h"
20#include "llvm/ADT/SetVector.h"
22#include "llvm/IR/PassManager.h"
23#include "llvm/IR/ValueHandle.h"
24#include <vector>
26namespace llvm {
28class AllocaInst;
29class LoadInst;
30class StoreInst;
31class AssumptionCache;
32class DominatorTree;
33class DomTreeUpdater;
34class Function;
35class LLVMContext;
36class PHINode;
37class SelectInst;
38class Use;
40/// A private "module" namespace for types and utilities used by SROA. These
41/// are implementation details and should not be used by clients.
44class AllocaSliceRewriter;
45class AllocaSlices;
46class Partition;
47class SROALegacyPass;
50 unsigned char Storage = 0; // None are speculatable by default.
51 using TrueVal = Bitfield::Element<bool, 0, 1>; // Low 0'th bit.
52 using FalseVal = Bitfield::Element<bool, 1, 1>; // Low 1'th bit.
56 bool isSpeculatable(bool isTrueVal) const;
57 bool areAllSpeculatable() const;
58 bool areAnySpeculatable() const;
59 bool areNoneSpeculatable() const;
60 // For interop as int half of PointerIntPair.
61 explicit operator intptr_t() const { return static_cast<intptr_t>(Storage); }
62 explicit SelectHandSpeculativity(intptr_t Storage_) : Storage(Storage_) {}
64static_assert(sizeof(SelectHandSpeculativity) == sizeof(unsigned char));
70 std::variant<PossiblySpeculatableLoad, UnspeculatableStore>;
73} // end namespace sroa
75enum class SROAOptions : bool { ModifyCFG, PreserveCFG };
77/// An optimization pass providing Scalar Replacement of Aggregates.
79/// This pass takes allocations which can be completely analyzed (that is, they
80/// don't escape) and tries to turn them into scalar SSA values. There are
81/// a few steps to this process.
83/// 1) It takes allocations of aggregates and analyzes the ways in which they
84/// are used to try to split them into smaller allocations, ideally of
85/// a single scalar data type. It will split up memcpy and memset accesses
86/// as necessary and try to isolate individual scalar accesses.
87/// 2) It will transform accesses into forms which are suitable for SSA value
88/// promotion. This can be replacing a memset with a scalar store of an
89/// integer value, or it can involve speculating operations on a PHI or
90/// select to be a PHI or select of the results.
91/// 3) Finally, this will try to detect a pattern of accesses which map cleanly
92/// onto insert and extract operations on a vector value, and convert them to
93/// this form. By doing so, it will enable promotion of vector aggregates to
94/// SSA vector values.
95class SROAPass : public PassInfoMixin<SROAPass> {
96 LLVMContext *C = nullptr;
97 DomTreeUpdater *DTU = nullptr;
98 AssumptionCache *AC = nullptr;
99 const bool PreserveCFG;
101 /// Worklist of alloca instructions to simplify.
102 ///
103 /// Each alloca in the function is added to this. Each new alloca formed gets
104 /// added to it as well to recursively simplify unless that alloca can be
105 /// directly promoted. Finally, each time we rewrite a use of an alloca other
106 /// the one being actively rewritten, we add it back onto the list if not
107 /// already present to ensure it is re-visited.
110 /// A collection of instructions to delete.
111 /// We try to batch deletions to simplify code and make things a bit more
112 /// efficient. We also make sure there is no dangling pointers.
113 SmallVector<WeakVH, 8> DeadInsts;
115 /// Post-promotion worklist.
116 ///
117 /// Sometimes we discover an alloca which has a high probability of becoming
118 /// viable for SROA after a round of promotion takes place. In those cases,
119 /// the alloca is enqueued here for re-processing.
120 ///
121 /// Note that we have to be very careful to clear allocas out of this list in
122 /// the event they are deleted.
125 /// A collection of alloca instructions we can directly promote.
126 std::vector<AllocaInst *> PromotableAllocas;
128 /// A worklist of PHIs to speculate prior to promoting allocas.
129 ///
130 /// All of these PHIs have been checked for the safety of speculation and by
131 /// being speculated will allow promoting allocas currently in the promotable
132 /// queue.
135 /// A worklist of select instructions to rewrite prior to promoting
136 /// allocas.
139 /// Select instructions that use an alloca and are subsequently loaded can be
140 /// rewritten to load both input pointers and then select between the result,
141 /// allowing the load of the alloca to be promoted.
142 /// From this:
143 /// %P2 = select i1 %cond, ptr %Alloca, ptr %Other
144 /// %V = load <type>, ptr %P2
145 /// to:
146 /// %V1 = load <type>, ptr %Alloca -> will be mem2reg'd
147 /// %V2 = load <type>, ptr %Other
148 /// %V = select i1 %cond, <type> %V1, <type> %V2
149 ///
150 /// We can do this to a select if its only uses are loads
151 /// and if either the operand to the select can be loaded unconditionally,
152 /// or if we are allowed to perform CFG modifications.
153 /// If found an intervening bitcast with a single use of the load,
154 /// allow the promotion.
155 static std::optional<sroa::RewriteableMemOps>
156 isSafeSelectToSpeculate(SelectInst &SI, bool PreserveCFG);
159 /// If \p PreserveCFG is set, then the pass is not allowed to modify CFG
160 /// in any way, even if it would update CFG analyses.
163 /// Run the pass over the function.
167 function_ref<StringRef(StringRef)> MapClassName2PassName);
173 /// Helper used by both the public run method and by the legacy pass.
175 AssumptionCache &RunAC);
177 AssumptionCache &RunAC);
179 bool presplitLoadsAndStores(AllocaInst &AI, sroa::AllocaSlices &AS);
180 AllocaInst *rewritePartition(AllocaInst &AI, sroa::AllocaSlices &AS,
182 bool splitAlloca(AllocaInst &AI, sroa::AllocaSlices &AS);
183 std::pair<bool /*Changed*/, bool /*CFGChanged*/> runOnAlloca(AllocaInst &AI);
184 void clobberUse(Use &U);
185 bool deleteDeadInstructions(SmallPtrSetImpl<AllocaInst *> &DeletedAllocas);
186 bool promoteAllocas(Function &F);
189} // end namespace llvm
LLVM_LIBRARY_VISIBILITY - If a class marked with this attribute is linked into a shared library,...
Definition: Compiler.h:126
static bool runImpl(Function &F, const TargetLowering &TLI)
#define F(x, y, z)
Definition: MD5.cpp:55
This file implements a map that provides insertion order iteration.
#define P(N)
This header defines various interfaces for pass management in LLVM.
This file defines the PointerIntPair class.
@ SI
Definition: SROA.cpp:5172
raw_pwrite_stream & OS
This file implements a set that has insertion order iteration characteristics.
This file defines the SmallVector class.
an instruction to allocate memory on the stack
Definition: Instructions.h:58
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:620
A cache of @llvm.assume calls within a function.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:166
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:67
SelectHandSpeculativity & setAsSpeculatable(bool isTrueVal)
PointerIntPair - This class implements a pair of a pointer and small integer.
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
An optimization pass providing Scalar Replacement of Aggregates.
Definition: SROA.h:95
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Run the pass over the function.
Definition: SROA.cpp:5109
void printPipeline(raw_ostream &OS, function_ref< StringRef(StringRef)> MapClassName2PassName)
Definition: SROA.cpp:5115
This class represents the LLVM 'select' instruction.
A vector that has set insertion semantics.
Definition: SetVector.h:40
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:344
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
An instruction for storing to memory.
Definition: Instructions.h:301
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
An efficient, type-erasing, non-owning reference to a callable.
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
Visitor to rewrite instructions using p particular slice of an alloca to use a new alloca.
Definition: SROA.cpp:2404
Representation of the alloca slices.
Definition: SROA.cpp:396
A partition of the slices.
Definition: SROA.cpp:528
A legacy pass for the legacy pass manager that wraps the SROA pass.
Definition: SROA.cpp:5129
std::variant< PossiblySpeculatableLoad, UnspeculatableStore > RewriteableMemOp
Definition: SROA.h:70
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
Definition: SROA.h:75
Describes an element of a Bitfield.
Definition: Bitfields.h:223
A CRTP mix-in to automatically provide informational APIs needed for passes.
Definition: PassManager.h:371
A MapVector that performs no allocations if smaller than a certain size.
Definition: MapVector.h:234