LLVM 18.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 <variant>
25#include <vector>
27namespace llvm {
29class AllocaInst;
30class LoadInst;
31class StoreInst;
32class AssumptionCache;
33class DominatorTree;
34class DomTreeUpdater;
35class Function;
36class LLVMContext;
37class PHINode;
38class SelectInst;
39class Use;
41/// A private "module" namespace for types and utilities used by SROA. These
42/// are implementation details and should not be used by clients.
46class AllocaSlices;
47class Partition;
48class SROALegacyPass;
51 unsigned char Storage = 0; // None are speculatable by default.
52 using TrueVal = Bitfield::Element<bool, 0, 1>; // Low 0'th bit.
53 using FalseVal = Bitfield::Element<bool, 1, 1>; // Low 1'th bit.
56 SelectHandSpeculativity &setAsSpeculatable(bool isTrueVal);
57 bool isSpeculatable(bool isTrueVal) const;
58 bool areAllSpeculatable() const;
59 bool areAnySpeculatable() const;
60 bool areNoneSpeculatable() const;
61 // For interop as int half of PointerIntPair.
62 explicit operator intptr_t() const { return static_cast<intptr_t>(Storage); }
63 explicit SelectHandSpeculativity(intptr_t Storage_) : Storage(Storage_) {}
65static_assert(sizeof(SelectHandSpeculativity) == sizeof(unsigned char));
71 std::variant<PossiblySpeculatableLoad, UnspeculatableStore>;
74} // end namespace sroa
76enum class SROAOptions : bool { ModifyCFG, PreserveCFG };
78/// An optimization pass providing Scalar Replacement of Aggregates.
80/// This pass takes allocations which can be completely analyzed (that is, they
81/// don't escape) and tries to turn them into scalar SSA values. There are
82/// a few steps to this process.
84/// 1) It takes allocations of aggregates and analyzes the ways in which they
85/// are used to try to split them into smaller allocations, ideally of
86/// a single scalar data type. It will split up memcpy and memset accesses
87/// as necessary and try to isolate individual scalar accesses.
88/// 2) It will transform accesses into forms which are suitable for SSA value
89/// promotion. This can be replacing a memset with a scalar store of an
90/// integer value, or it can involve speculating operations on a PHI or
91/// select to be a PHI or select of the results.
92/// 3) Finally, this will try to detect a pattern of accesses which map cleanly
93/// onto insert and extract operations on a vector value, and convert them to
94/// this form. By doing so, it will enable promotion of vector aggregates to
95/// SSA vector values.
96class SROAPass : public PassInfoMixin<SROAPass> {
97 LLVMContext *C = nullptr;
98 DomTreeUpdater *DTU = nullptr;
99 AssumptionCache *AC = nullptr;
100 const bool PreserveCFG;
102 /// Worklist of alloca instructions to simplify.
103 ///
104 /// Each alloca in the function is added to this. Each new alloca formed gets
105 /// added to it as well to recursively simplify unless that alloca can be
106 /// directly promoted. Finally, each time we rewrite a use of an alloca other
107 /// the one being actively rewritten, we add it back onto the list if not
108 /// already present to ensure it is re-visited.
111 /// A collection of instructions to delete.
112 /// We try to batch deletions to simplify code and make things a bit more
113 /// efficient. We also make sure there is no dangling pointers.
114 SmallVector<WeakVH, 8> DeadInsts;
116 /// Post-promotion worklist.
117 ///
118 /// Sometimes we discover an alloca which has a high probability of becoming
119 /// viable for SROA after a round of promotion takes place. In those cases,
120 /// the alloca is enqueued here for re-processing.
121 ///
122 /// Note that we have to be very careful to clear allocas out of this list in
123 /// the event they are deleted.
124 SmallSetVector<AllocaInst *, 16> PostPromotionWorklist;
126 /// A collection of alloca instructions we can directly promote.
127 std::vector<AllocaInst *> PromotableAllocas;
129 /// A worklist of PHIs to speculate prior to promoting allocas.
130 ///
131 /// All of these PHIs have been checked for the safety of speculation and by
132 /// being speculated will allow promoting allocas currently in the promotable
133 /// queue.
134 SmallSetVector<PHINode *, 8> SpeculatablePHIs;
136 /// A worklist of select instructions to rewrite prior to promoting
137 /// allocas.
140 /// Select instructions that use an alloca and are subsequently loaded can be
141 /// rewritten to load both input pointers and then select between the result,
142 /// allowing the load of the alloca to be promoted.
143 /// From this:
144 /// %P2 = select i1 %cond, ptr %Alloca, ptr %Other
145 /// %V = load <type>, ptr %P2
146 /// to:
147 /// %V1 = load <type>, ptr %Alloca -> will be mem2reg'd
148 /// %V2 = load <type>, ptr %Other
149 /// %V = select i1 %cond, <type> %V1, <type> %V2
150 ///
151 /// We can do this to a select if its only uses are loads
152 /// and if either the operand to the select can be loaded unconditionally,
153 /// or if we are allowed to perform CFG modifications.
154 /// If found an intervening bitcast with a single use of the load,
155 /// allow the promotion.
156 static std::optional<sroa::RewriteableMemOps>
157 isSafeSelectToSpeculate(SelectInst &SI, bool PreserveCFG);
160 /// If \p PreserveCFG is set, then the pass is not allowed to modify CFG
161 /// in any way, even if it would update CFG analyses.
164 /// Run the pass over the function.
168 function_ref<StringRef(StringRef)> MapClassName2PassName);
174 /// Helper used by both the public run method and by the legacy pass.
176 AssumptionCache &RunAC);
178 AssumptionCache &RunAC);
180 bool presplitLoadsAndStores(AllocaInst &AI, sroa::AllocaSlices &AS);
181 AllocaInst *rewritePartition(AllocaInst &AI, sroa::AllocaSlices &AS,
183 bool splitAlloca(AllocaInst &AI, sroa::AllocaSlices &AS);
184 std::pair<bool /*Changed*/, bool /*CFGChanged*/> runOnAlloca(AllocaInst &AI);
185 void clobberUse(Use &U);
186 bool deleteDeadInstructions(SmallPtrSetImpl<AllocaInst *> &DeletedAllocas);
187 bool promoteAllocas(Function &F);
190} // end namespace llvm
Definition: Compiler.h:131
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.
Definition: SROA.cpp:5206
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
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:96
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Run the pass over the function.
Definition: SROA.cpp:5143
void printPipeline(raw_ostream &OS, function_ref< StringRef(StringRef)> MapClassName2PassName)
Definition: SROA.cpp:5149
This class represents the LLVM 'select' instruction.
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:345
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:370
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:2447
Representation of the alloca slices.
Definition: SROA.cpp:442
A partition of the slices.
Definition: SROA.cpp:574
A legacy pass for the legacy pass manager that wraps the SROA pass.
Definition: SROA.cpp:5163
SelectHandSpeculativity(intptr_t Storage_)
Definition: SROA.h:63
NodeAddr< UseNode * > Use
Definition: RDFGraph.h:385
std::variant< PossiblySpeculatableLoad, UnspeculatableStore > RewriteableMemOp
Definition: SROA.h:71
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
Definition: SROA.h:76
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:233