1//===-- SROA.cpp - 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
9#include "mlir/Transforms/SROA.h"
10#include "mlir/Analysis/DataLayoutAnalysis.h"
11#include "mlir/Analysis/SliceAnalysis.h"
12#include "mlir/Analysis/TopologicalSortUtils.h"
13#include "mlir/Interfaces/MemorySlotInterfaces.h"
14#include "mlir/Transforms/Passes.h"
15#include "llvm/Support/DebugLog.h"
16
17namespace mlir {
18#define GEN_PASS_DEF_SROA
19#include "mlir/Transforms/Passes.h.inc"
20} // namespace mlir
21
22#define DEBUG_TYPE "sroa"
23
24using namespace mlir;
25
26namespace {
27
28/// Information computed by destructurable memory slot analysis used to perform
29/// actual destructuring of the slot. This struct is only constructed if
30/// destructuring is possible, and contains the necessary data to perform it.
31struct MemorySlotDestructuringInfo {
32 /// Set of the indices that are actually used when accessing the subelements.
33 SmallPtrSet<Attribute, 8> usedIndices;
34 /// Blocking uses of a given user of the memory slot that must be eliminated.
35 DenseMap<Operation *, SmallPtrSet<OpOperand *, 4>> userToBlockingUses;
36 /// List of potentially indirect accessors of the memory slot that need
37 /// rewiring.
38 SmallVector<DestructurableAccessorOpInterface> accessors;
39};
40
41} // namespace
42
43/// Computes information for slot destructuring. This will compute whether this
44/// slot can be destructured and data to perform the destructuring. Returns
45/// nothing if the slot cannot be destructured or if there is no useful work to
46/// be done.
47static std::optional<MemorySlotDestructuringInfo>
48computeDestructuringInfo(DestructurableMemorySlot &slot,
49 const DataLayout &dataLayout) {
50 assert(isa<DestructurableTypeInterface>(slot.valueType));
51
52 if (slot.ptr.use_empty())
53 return {};
54
55 MemorySlotDestructuringInfo info;
56
57 SmallVector<MemorySlot> usedSafelyWorklist;
58
59 auto scheduleAsBlockingUse = [&](OpOperand &use) {
60 SmallPtrSetImpl<OpOperand *> &blockingUses =
61 info.userToBlockingUses[use.getOwner()];
62 blockingUses.insert(Ptr: &use);
63 };
64
65 // Initialize the analysis with the immediate users of the slot.
66 for (OpOperand &use : slot.ptr.getUses()) {
67 if (auto accessor =
68 dyn_cast<DestructurableAccessorOpInterface>(Val: use.getOwner())) {
69 if (accessor.canRewire(slot, usedIndices&: info.usedIndices, mustBeSafelyUsed&: usedSafelyWorklist,
70 dataLayout)) {
71 info.accessors.push_back(Elt: accessor);
72 continue;
73 }
74 }
75
76 // If it cannot be shown that the operation uses the slot safely, maybe it
77 // can be promoted out of using the slot?
78 scheduleAsBlockingUse(use);
79 }
80
81 SmallPtrSet<OpOperand *, 16> visited;
82 while (!usedSafelyWorklist.empty()) {
83 MemorySlot mustBeUsedSafely = usedSafelyWorklist.pop_back_val();
84 for (OpOperand &subslotUse : mustBeUsedSafely.ptr.getUses()) {
85 if (!visited.insert(Ptr: &subslotUse).second)
86 continue;
87 Operation *subslotUser = subslotUse.getOwner();
88
89 if (auto memOp = dyn_cast<SafeMemorySlotAccessOpInterface>(Val: subslotUser))
90 if (succeeded(Result: memOp.ensureOnlySafeAccesses(
91 slot: mustBeUsedSafely, mustBeSafelyUsed&: usedSafelyWorklist, dataLayout)))
92 continue;
93
94 // If it cannot be shown that the operation uses the slot safely, maybe it
95 // can be promoted out of using the slot?
96 scheduleAsBlockingUse(subslotUse);
97 }
98 }
99
100 if (info.userToBlockingUses.empty())
101 return info;
102
103 SetVector<Operation *> forwardSlice;
104 mlir::getForwardSlice(root: slot.ptr, forwardSlice: &forwardSlice);
105 for (Operation *user : forwardSlice) {
106 // If the next operation has no blocking uses, everything is fine.
107 auto it = info.userToBlockingUses.find(Val: user);
108 if (it == info.userToBlockingUses.end())
109 continue;
110
111 SmallPtrSet<OpOperand *, 4> &blockingUses = it->second;
112 auto promotable = dyn_cast<PromotableOpInterface>(Val: user);
113
114 // An operation that has blocking uses must be promoted. If it is not
115 // promotable, destructuring must fail.
116 if (!promotable)
117 return {};
118
119 SmallVector<OpOperand *> newBlockingUses;
120 // If the operation decides it cannot deal with removing the blocking uses,
121 // destructuring must fail.
122 if (!promotable.canUsesBeRemoved(blockingUses, newBlockingUses, datalayout: dataLayout))
123 return {};
124
125 // Then, register any new blocking uses for coming operations.
126 for (OpOperand *blockingUse : newBlockingUses) {
127 assert(llvm::is_contained(user->getResults(), blockingUse->get()));
128
129 SmallPtrSetImpl<OpOperand *> &newUserBlockingUseSet =
130 info.userToBlockingUses[blockingUse->getOwner()];
131 newUserBlockingUseSet.insert(Ptr: blockingUse);
132 }
133 }
134
135 return info;
136}
137
138/// Performs the destructuring of a destructible slot given associated
139/// destructuring information. The provided slot will be destructured in
140/// subslots as specified by its allocator.
141static void destructureSlot(
142 DestructurableMemorySlot &slot,
143 DestructurableAllocationOpInterface allocator, OpBuilder &builder,
144 const DataLayout &dataLayout, MemorySlotDestructuringInfo &info,
145 SmallVectorImpl<DestructurableAllocationOpInterface> &newAllocators,
146 const SROAStatistics &statistics) {
147 OpBuilder::InsertionGuard guard(builder);
148
149 builder.setInsertionPointToStart(slot.ptr.getParentBlock());
150 DenseMap<Attribute, MemorySlot> subslots =
151 allocator.destructure(slot, usedIndices: info.usedIndices, builder, newAllocators);
152
153 if (statistics.slotsWithMemoryBenefit &&
154 slot.subelementTypes.size() != info.usedIndices.size())
155 (*statistics.slotsWithMemoryBenefit)++;
156
157 if (statistics.maxSubelementAmount)
158 statistics.maxSubelementAmount->updateMax(V: slot.subelementTypes.size());
159
160 SetVector<Operation *> usersToRewire;
161 usersToRewire.insert_range(R: llvm::make_first_range(c&: info.userToBlockingUses));
162 usersToRewire.insert_range(R&: info.accessors);
163 // Topological sorting is only needed when promoting blocking uses (whose
164 // removal relies on erasing users before defs) or when an accessor owns
165 // regions that may nest other accessors.
166 bool needsTopologicalSort =
167 !info.userToBlockingUses.empty() ||
168 llvm::any_of(Range&: info.accessors, P: [](DestructurableAccessorOpInterface op) {
169 return op->getNumRegions() > 0;
170 });
171 if (needsTopologicalSort)
172 usersToRewire = mlir::topologicalSort(toSort: usersToRewire);
173
174 llvm::SmallVector<Operation *> toErase;
175 for (Operation *toRewire : llvm::reverse(C&: usersToRewire)) {
176 builder.setInsertionPointAfter(toRewire);
177 if (auto accessor = dyn_cast<DestructurableAccessorOpInterface>(Val: toRewire)) {
178 if (accessor.rewire(slot, subslots, builder, dataLayout) ==
179 DeletionKind::Delete)
180 toErase.push_back(Elt: accessor);
181 continue;
182 }
183
184 auto promotable = cast<PromotableOpInterface>(Val: toRewire);
185 if (promotable.removeBlockingUses(blockingUses: info.userToBlockingUses[promotable],
186 builder) == DeletionKind::Delete)
187 toErase.push_back(Elt: promotable);
188 }
189
190 for (Operation *toEraseOp : toErase)
191 toEraseOp->erase();
192
193 assert(slot.ptr.use_empty() && "after destructuring, the original slot "
194 "pointer should no longer be used");
195
196 LDBG() << "Destructured memory slot: " << slot.ptr;
197
198 if (statistics.destructuredAmount)
199 (*statistics.destructuredAmount)++;
200
201 std::optional<DestructurableAllocationOpInterface> newAllocator =
202 allocator.handleDestructuringComplete(slot, builder);
203 // Add newly created allocators to the worklist for further processing.
204 if (newAllocator)
205 newAllocators.push_back(Elt: *newAllocator);
206}
207
208LogicalResult mlir::tryToDestructureMemorySlots(
209 ArrayRef<DestructurableAllocationOpInterface> allocators,
210 OpBuilder &builder, const DataLayout &dataLayout,
211 SROAStatistics statistics) {
212 bool destructuredAny = false;
213
214 SmallVector<DestructurableAllocationOpInterface> workList(allocators);
215 SmallVector<DestructurableAllocationOpInterface> newWorkList;
216 newWorkList.reserve(N: allocators.size());
217 // Destructuring a slot can allow for further destructuring of other
218 // slots, destructuring is tried until no destructuring succeeds.
219 while (true) {
220 bool changesInThisRound = false;
221
222 for (DestructurableAllocationOpInterface allocator : workList) {
223 bool destructuredAnySlot = false;
224 for (DestructurableMemorySlot slot : allocator.getDestructurableSlots()) {
225 std::optional<MemorySlotDestructuringInfo> info =
226 computeDestructuringInfo(slot, dataLayout);
227 if (!info)
228 continue;
229
230 destructureSlot(slot, allocator, builder, dataLayout, info&: *info,
231 newAllocators&: newWorkList, statistics);
232 destructuredAnySlot = true;
233
234 // A break is required, since destructuring a slot may invalidate the
235 // remaning slots of an allocator.
236 break;
237 }
238 if (!destructuredAnySlot)
239 newWorkList.push_back(Elt: allocator);
240 changesInThisRound |= destructuredAnySlot;
241 }
242
243 if (!changesInThisRound)
244 break;
245 destructuredAny |= changesInThisRound;
246
247 // Swap the vector's backing memory and clear the entries in newWorkList
248 // afterwards. This ensures that additional heap allocations can be avoided.
249 workList.swap(RHS&: newWorkList);
250 newWorkList.clear();
251 }
252
253 return success(IsSuccess: destructuredAny);
254}
255
256namespace {
257
258struct SROA : public impl::SROABase<SROA> {
259 using impl::SROABase<SROA>::SROABase;
260
261 void runOnOperation() override {
262 Operation *scopeOp = getOperation();
263
264 SROAStatistics statistics{.destructuredAmount: &destructuredAmount, .slotsWithMemoryBenefit: &slotsWithMemoryBenefit,
265 .maxSubelementAmount: &maxSubelementAmount};
266
267 auto &dataLayoutAnalysis = getAnalysis<DataLayoutAnalysis>();
268 const DataLayout &dataLayout = dataLayoutAnalysis.getAtOrAbove(operation: scopeOp);
269 bool changed = false;
270
271 for (Region &region : scopeOp->getRegions()) {
272 if (region.getBlocks().empty())
273 continue;
274
275 OpBuilder builder(&region.front(), region.front().begin());
276
277 SmallVector<DestructurableAllocationOpInterface> allocators;
278 // Build a list of allocators to attempt to destructure the slots of.
279 region.walk(callback: [&](DestructurableAllocationOpInterface allocator) {
280 allocators.emplace_back(Args&: allocator);
281 });
282
283 // Attempt to destructure as many slots as possible.
284 if (succeeded(Result: tryToDestructureMemorySlots(allocators, builder, dataLayout,
285 statistics)))
286 changed = true;
287 }
288 if (!changed)
289 markAllAnalysesPreserved();
290 }
291};
292
293} // namespace
294