1 | //===- PromoteMemoryToRegister.cpp - Convert allocas to registers ---------===// |
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 | // This file promotes memory references to be register references. It promotes |
10 | // alloca instructions which only have loads and stores as uses. An alloca is |
11 | // transformed by using iterated dominator frontiers to place PHI nodes, then |
12 | // traversing the function in depth-first order to rewrite loads and stores as |
13 | // appropriate. |
14 | // |
15 | //===----------------------------------------------------------------------===// |
16 | |
17 | #include "llvm/ADT/ArrayRef.h" |
18 | #include "llvm/ADT/DenseMap.h" |
19 | #include "llvm/ADT/STLExtras.h" |
20 | #include "llvm/ADT/SmallPtrSet.h" |
21 | #include "llvm/ADT/SmallVector.h" |
22 | #include "llvm/ADT/Statistic.h" |
23 | #include "llvm/ADT/Twine.h" |
24 | #include "llvm/Analysis/AssumptionCache.h" |
25 | #include "llvm/Analysis/InstructionSimplify.h" |
26 | #include "llvm/Analysis/IteratedDominanceFrontier.h" |
27 | #include "llvm/Analysis/ValueTracking.h" |
28 | #include "llvm/IR/BasicBlock.h" |
29 | #include "llvm/IR/CFG.h" |
30 | #include "llvm/IR/Constant.h" |
31 | #include "llvm/IR/Constants.h" |
32 | #include "llvm/IR/DIBuilder.h" |
33 | #include "llvm/IR/DebugInfo.h" |
34 | #include "llvm/IR/DebugProgramInstruction.h" |
35 | #include "llvm/IR/Dominators.h" |
36 | #include "llvm/IR/Function.h" |
37 | #include "llvm/IR/InstrTypes.h" |
38 | #include "llvm/IR/Instruction.h" |
39 | #include "llvm/IR/Instructions.h" |
40 | #include "llvm/IR/IntrinsicInst.h" |
41 | #include "llvm/IR/Intrinsics.h" |
42 | #include "llvm/IR/LLVMContext.h" |
43 | #include "llvm/IR/Module.h" |
44 | #include "llvm/IR/Type.h" |
45 | #include "llvm/IR/User.h" |
46 | #include "llvm/Support/Casting.h" |
47 | #include "llvm/Transforms/Utils/Local.h" |
48 | #include "llvm/Transforms/Utils/PromoteMemToReg.h" |
49 | #include <algorithm> |
50 | #include <cassert> |
51 | #include <iterator> |
52 | #include <utility> |
53 | #include <vector> |
54 | |
55 | using namespace llvm; |
56 | |
57 | #define DEBUG_TYPE "mem2reg" |
58 | |
59 | STATISTIC(NumLocalPromoted, "Number of alloca's promoted within one block" ); |
60 | STATISTIC(NumSingleStore, "Number of alloca's promoted with a single store" ); |
61 | STATISTIC(NumDeadAlloca, "Number of dead alloca's removed" ); |
62 | STATISTIC(NumPHIInsert, "Number of PHI nodes inserted" ); |
63 | |
64 | bool llvm::isAllocaPromotable(const AllocaInst *AI) { |
65 | // Only allow direct and non-volatile loads and stores... |
66 | for (const User *U : AI->users()) { |
67 | if (const LoadInst *LI = dyn_cast<LoadInst>(Val: U)) { |
68 | // Note that atomic loads can be transformed; atomic semantics do |
69 | // not have any meaning for a local alloca. |
70 | if (LI->isVolatile() || LI->getType() != AI->getAllocatedType()) |
71 | return false; |
72 | } else if (const StoreInst *SI = dyn_cast<StoreInst>(Val: U)) { |
73 | if (SI->getValueOperand() == AI || |
74 | SI->getValueOperand()->getType() != AI->getAllocatedType()) |
75 | return false; // Don't allow a store OF the AI, only INTO the AI. |
76 | // Note that atomic stores can be transformed; atomic semantics do |
77 | // not have any meaning for a local alloca. |
78 | if (SI->isVolatile()) |
79 | return false; |
80 | } else if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(Val: U)) { |
81 | if (!II->isLifetimeStartOrEnd() && !II->isDroppable()) |
82 | return false; |
83 | } else if (const BitCastInst *BCI = dyn_cast<BitCastInst>(Val: U)) { |
84 | if (!onlyUsedByLifetimeMarkersOrDroppableInsts(V: BCI)) |
85 | return false; |
86 | } else if (const GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(Val: U)) { |
87 | if (!GEPI->hasAllZeroIndices()) |
88 | return false; |
89 | if (!onlyUsedByLifetimeMarkersOrDroppableInsts(V: GEPI)) |
90 | return false; |
91 | } else if (const AddrSpaceCastInst *ASCI = dyn_cast<AddrSpaceCastInst>(Val: U)) { |
92 | if (!onlyUsedByLifetimeMarkers(V: ASCI)) |
93 | return false; |
94 | } else { |
95 | return false; |
96 | } |
97 | } |
98 | |
99 | return true; |
100 | } |
101 | |
102 | namespace { |
103 | |
104 | static void createDebugValue(DIBuilder &DIB, Value *NewValue, |
105 | DILocalVariable *Variable, |
106 | DIExpression *Expression, const DILocation *DI, |
107 | DbgVariableRecord *InsertBefore) { |
108 | // FIXME: Merge these two functions now that DIBuilder supports |
109 | // DbgVariableRecords. We neeed the API to accept DbgVariableRecords as an |
110 | // insert point for that to work. |
111 | (void)DIB; |
112 | DbgVariableRecord::createDbgVariableRecord(Location: NewValue, DV: Variable, Expr: Expression, DI, |
113 | InsertBefore&: *InsertBefore); |
114 | } |
115 | static void createDebugValue(DIBuilder &DIB, Value *NewValue, |
116 | DILocalVariable *Variable, |
117 | DIExpression *Expression, const DILocation *DI, |
118 | Instruction *InsertBefore) { |
119 | DIB.insertDbgValueIntrinsic(Val: NewValue, VarInfo: Variable, Expr: Expression, DL: DI, InsertBefore); |
120 | } |
121 | |
122 | /// Helper for updating assignment tracking debug info when promoting allocas. |
123 | class AssignmentTrackingInfo { |
124 | /// DbgAssignIntrinsics linked to the alloca with at most one per variable |
125 | /// fragment. (i.e. not be a comprehensive set if there are multiple |
126 | /// dbg.assigns for one variable fragment). |
127 | SmallVector<DbgVariableIntrinsic *> DbgAssigns; |
128 | SmallVector<DbgVariableRecord *> DVRAssigns; |
129 | |
130 | public: |
131 | void init(AllocaInst *AI) { |
132 | SmallSet<DebugVariable, 2> Vars; |
133 | for (DbgAssignIntrinsic *DAI : at::getAssignmentMarkers(Inst: AI)) { |
134 | if (Vars.insert(V: DebugVariable(DAI)).second) |
135 | DbgAssigns.push_back(Elt: DAI); |
136 | } |
137 | for (DbgVariableRecord *DVR : at::getDVRAssignmentMarkers(Inst: AI)) { |
138 | if (Vars.insert(V: DebugVariable(DVR)).second) |
139 | DVRAssigns.push_back(Elt: DVR); |
140 | } |
141 | } |
142 | |
143 | /// Update assignment tracking debug info given for the to-be-deleted store |
144 | /// \p ToDelete that stores to this alloca. |
145 | void updateForDeletedStore( |
146 | StoreInst *ToDelete, DIBuilder &DIB, |
147 | SmallSet<DbgAssignIntrinsic *, 8> *DbgAssignsToDelete, |
148 | SmallSet<DbgVariableRecord *, 8> *DVRAssignsToDelete) const { |
149 | // There's nothing to do if the alloca doesn't have any variables using |
150 | // assignment tracking. |
151 | if (DbgAssigns.empty() && DVRAssigns.empty()) |
152 | return; |
153 | |
154 | // Insert a dbg.value where the linked dbg.assign is and remember to delete |
155 | // the dbg.assign later. Demoting to dbg.value isn't necessary for |
156 | // correctness but does reduce compile time and memory usage by reducing |
157 | // unnecessary function-local metadata. Remember that we've seen a |
158 | // dbg.assign for each variable fragment for the untracked store handling |
159 | // (after this loop). |
160 | SmallSet<DebugVariableAggregate, 2> VarHasDbgAssignForStore; |
161 | auto InsertValueForAssign = [&](auto *DbgAssign, auto *&AssignList) { |
162 | VarHasDbgAssignForStore.insert(V: DebugVariableAggregate(DbgAssign)); |
163 | AssignList->insert(DbgAssign); |
164 | createDebugValue(DIB, DbgAssign->getValue(), DbgAssign->getVariable(), |
165 | DbgAssign->getExpression(), DbgAssign->getDebugLoc(), |
166 | DbgAssign); |
167 | }; |
168 | for (auto *Assign : at::getAssignmentMarkers(Inst: ToDelete)) |
169 | InsertValueForAssign(Assign, DbgAssignsToDelete); |
170 | for (auto *Assign : at::getDVRAssignmentMarkers(Inst: ToDelete)) |
171 | InsertValueForAssign(Assign, DVRAssignsToDelete); |
172 | |
173 | // It's possible for variables using assignment tracking to have no |
174 | // dbg.assign linked to this store. These are variables in DbgAssigns that |
175 | // are missing from VarHasDbgAssignForStore. Since there isn't a dbg.assign |
176 | // to mark the assignment - and the store is going to be deleted - insert a |
177 | // dbg.value to do that now. An untracked store may be either one that |
178 | // cannot be represented using assignment tracking (non-const offset or |
179 | // size) or one that is trackable but has had its DIAssignID attachment |
180 | // dropped accidentally. |
181 | auto ConvertUnlinkedAssignToValue = [&](auto *Assign) { |
182 | if (VarHasDbgAssignForStore.contains(V: DebugVariableAggregate(Assign))) |
183 | return; |
184 | ConvertDebugDeclareToDebugValue(Assign, ToDelete, DIB); |
185 | }; |
186 | for_each(Range: DbgAssigns, F: ConvertUnlinkedAssignToValue); |
187 | for_each(Range: DVRAssigns, F: ConvertUnlinkedAssignToValue); |
188 | } |
189 | |
190 | /// Update assignment tracking debug info given for the newly inserted PHI \p |
191 | /// NewPhi. |
192 | void updateForNewPhi(PHINode *NewPhi, DIBuilder &DIB) const { |
193 | // Regardless of the position of dbg.assigns relative to stores, the |
194 | // incoming values into a new PHI should be the same for the (imaginary) |
195 | // debug-phi. |
196 | for (auto *DAI : DbgAssigns) |
197 | ConvertDebugDeclareToDebugValue(DII: DAI, LI: NewPhi, Builder&: DIB); |
198 | for (auto *DVR : DVRAssigns) |
199 | ConvertDebugDeclareToDebugValue(DVR, LI: NewPhi, Builder&: DIB); |
200 | } |
201 | |
202 | void clear() { |
203 | DbgAssigns.clear(); |
204 | DVRAssigns.clear(); |
205 | } |
206 | bool empty() { return DbgAssigns.empty() && DVRAssigns.empty(); } |
207 | }; |
208 | |
209 | struct AllocaInfo { |
210 | using DbgUserVec = SmallVector<DbgVariableIntrinsic *, 1>; |
211 | using DPUserVec = SmallVector<DbgVariableRecord *, 1>; |
212 | |
213 | SmallVector<BasicBlock *, 32> DefiningBlocks; |
214 | SmallVector<BasicBlock *, 32> UsingBlocks; |
215 | |
216 | StoreInst *OnlyStore; |
217 | BasicBlock *OnlyBlock; |
218 | bool OnlyUsedInOneBlock; |
219 | |
220 | /// Debug users of the alloca - does not include dbg.assign intrinsics. |
221 | DbgUserVec DbgUsers; |
222 | DPUserVec DPUsers; |
223 | /// Helper to update assignment tracking debug info. |
224 | AssignmentTrackingInfo AssignmentTracking; |
225 | |
226 | void clear() { |
227 | DefiningBlocks.clear(); |
228 | UsingBlocks.clear(); |
229 | OnlyStore = nullptr; |
230 | OnlyBlock = nullptr; |
231 | OnlyUsedInOneBlock = true; |
232 | DbgUsers.clear(); |
233 | DPUsers.clear(); |
234 | AssignmentTracking.clear(); |
235 | } |
236 | |
237 | /// Scan the uses of the specified alloca, filling in the AllocaInfo used |
238 | /// by the rest of the pass to reason about the uses of this alloca. |
239 | void AnalyzeAlloca(AllocaInst *AI) { |
240 | clear(); |
241 | |
242 | // As we scan the uses of the alloca instruction, keep track of stores, |
243 | // and decide whether all of the loads and stores to the alloca are within |
244 | // the same basic block. |
245 | for (User *U : AI->users()) { |
246 | Instruction *User = cast<Instruction>(Val: U); |
247 | |
248 | if (StoreInst *SI = dyn_cast<StoreInst>(Val: User)) { |
249 | // Remember the basic blocks which define new values for the alloca |
250 | DefiningBlocks.push_back(Elt: SI->getParent()); |
251 | OnlyStore = SI; |
252 | } else { |
253 | LoadInst *LI = cast<LoadInst>(Val: User); |
254 | // Otherwise it must be a load instruction, keep track of variable |
255 | // reads. |
256 | UsingBlocks.push_back(Elt: LI->getParent()); |
257 | } |
258 | |
259 | if (OnlyUsedInOneBlock) { |
260 | if (!OnlyBlock) |
261 | OnlyBlock = User->getParent(); |
262 | else if (OnlyBlock != User->getParent()) |
263 | OnlyUsedInOneBlock = false; |
264 | } |
265 | } |
266 | DbgUserVec AllDbgUsers; |
267 | SmallVector<DbgVariableRecord *> AllDPUsers; |
268 | findDbgUsers(DbgInsts&: AllDbgUsers, V: AI, DbgVariableRecords: &AllDPUsers); |
269 | std::copy_if(first: AllDbgUsers.begin(), last: AllDbgUsers.end(), |
270 | result: std::back_inserter(x&: DbgUsers), pred: [](DbgVariableIntrinsic *DII) { |
271 | return !isa<DbgAssignIntrinsic>(Val: DII); |
272 | }); |
273 | std::copy_if(first: AllDPUsers.begin(), last: AllDPUsers.end(), |
274 | result: std::back_inserter(x&: DPUsers), |
275 | pred: [](DbgVariableRecord *DVR) { return !DVR->isDbgAssign(); }); |
276 | AssignmentTracking.init(AI); |
277 | } |
278 | }; |
279 | |
280 | /// Data package used by RenamePass(). |
281 | struct RenamePassData { |
282 | using ValVector = std::vector<Value *>; |
283 | using LocationVector = std::vector<DebugLoc>; |
284 | |
285 | RenamePassData(BasicBlock *B, BasicBlock *P, ValVector V, LocationVector L) |
286 | : BB(B), Pred(P), Values(std::move(V)), Locations(std::move(L)) {} |
287 | |
288 | BasicBlock *BB; |
289 | BasicBlock *Pred; |
290 | ValVector Values; |
291 | LocationVector Locations; |
292 | }; |
293 | |
294 | /// This assigns and keeps a per-bb relative ordering of load/store |
295 | /// instructions in the block that directly load or store an alloca. |
296 | /// |
297 | /// This functionality is important because it avoids scanning large basic |
298 | /// blocks multiple times when promoting many allocas in the same block. |
299 | class LargeBlockInfo { |
300 | /// For each instruction that we track, keep the index of the |
301 | /// instruction. |
302 | /// |
303 | /// The index starts out as the number of the instruction from the start of |
304 | /// the block. |
305 | DenseMap<const Instruction *, unsigned> InstNumbers; |
306 | |
307 | public: |
308 | |
309 | /// This code only looks at accesses to allocas. |
310 | static bool isInterestingInstruction(const Instruction *I) { |
311 | return (isa<LoadInst>(Val: I) && isa<AllocaInst>(Val: I->getOperand(i: 0))) || |
312 | (isa<StoreInst>(Val: I) && isa<AllocaInst>(Val: I->getOperand(i: 1))); |
313 | } |
314 | |
315 | /// Get or calculate the index of the specified instruction. |
316 | unsigned getInstructionIndex(const Instruction *I) { |
317 | assert(isInterestingInstruction(I) && |
318 | "Not a load/store to/from an alloca?" ); |
319 | |
320 | // If we already have this instruction number, return it. |
321 | DenseMap<const Instruction *, unsigned>::iterator It = InstNumbers.find(Val: I); |
322 | if (It != InstNumbers.end()) |
323 | return It->second; |
324 | |
325 | // Scan the whole block to get the instruction. This accumulates |
326 | // information for every interesting instruction in the block, in order to |
327 | // avoid gratuitus rescans. |
328 | const BasicBlock *BB = I->getParent(); |
329 | unsigned InstNo = 0; |
330 | for (const Instruction &BBI : *BB) |
331 | if (isInterestingInstruction(I: &BBI)) |
332 | InstNumbers[&BBI] = InstNo++; |
333 | It = InstNumbers.find(Val: I); |
334 | |
335 | assert(It != InstNumbers.end() && "Didn't insert instruction?" ); |
336 | return It->second; |
337 | } |
338 | |
339 | void deleteValue(const Instruction *I) { InstNumbers.erase(Val: I); } |
340 | |
341 | void clear() { InstNumbers.clear(); } |
342 | }; |
343 | |
344 | struct PromoteMem2Reg { |
345 | /// The alloca instructions being promoted. |
346 | std::vector<AllocaInst *> Allocas; |
347 | |
348 | DominatorTree &DT; |
349 | DIBuilder DIB; |
350 | |
351 | /// A cache of @llvm.assume intrinsics used by SimplifyInstruction. |
352 | AssumptionCache *AC; |
353 | |
354 | const SimplifyQuery SQ; |
355 | |
356 | /// Reverse mapping of Allocas. |
357 | DenseMap<AllocaInst *, unsigned> AllocaLookup; |
358 | |
359 | /// The PhiNodes we're adding. |
360 | /// |
361 | /// That map is used to simplify some Phi nodes as we iterate over it, so |
362 | /// it should have deterministic iterators. We could use a MapVector, but |
363 | /// since we already maintain a map from BasicBlock* to a stable numbering |
364 | /// (BBNumbers), the DenseMap is more efficient (also supports removal). |
365 | DenseMap<std::pair<unsigned, unsigned>, PHINode *> NewPhiNodes; |
366 | |
367 | /// For each PHI node, keep track of which entry in Allocas it corresponds |
368 | /// to. |
369 | DenseMap<PHINode *, unsigned> PhiToAllocaMap; |
370 | |
371 | /// For each alloca, we keep track of the dbg.declare intrinsic that |
372 | /// describes it, if any, so that we can convert it to a dbg.value |
373 | /// intrinsic if the alloca gets promoted. |
374 | SmallVector<AllocaInfo::DbgUserVec, 8> AllocaDbgUsers; |
375 | SmallVector<AllocaInfo::DPUserVec, 8> AllocaDPUsers; |
376 | |
377 | /// For each alloca, keep an instance of a helper class that gives us an easy |
378 | /// way to update assignment tracking debug info if the alloca is promoted. |
379 | SmallVector<AssignmentTrackingInfo, 8> AllocaATInfo; |
380 | /// A set of dbg.assigns to delete because they've been demoted to |
381 | /// dbg.values. Call cleanUpDbgAssigns to delete them. |
382 | SmallSet<DbgAssignIntrinsic *, 8> DbgAssignsToDelete; |
383 | SmallSet<DbgVariableRecord *, 8> DVRAssignsToDelete; |
384 | |
385 | /// The set of basic blocks the renamer has already visited. |
386 | SmallPtrSet<BasicBlock *, 16> Visited; |
387 | |
388 | /// Contains a stable numbering of basic blocks to avoid non-determinstic |
389 | /// behavior. |
390 | DenseMap<BasicBlock *, unsigned> BBNumbers; |
391 | |
392 | /// Lazily compute the number of predecessors a block has. |
393 | DenseMap<const BasicBlock *, unsigned> BBNumPreds; |
394 | |
395 | public: |
396 | PromoteMem2Reg(ArrayRef<AllocaInst *> Allocas, DominatorTree &DT, |
397 | AssumptionCache *AC) |
398 | : Allocas(Allocas.begin(), Allocas.end()), DT(DT), |
399 | DIB(*DT.getRoot()->getParent()->getParent(), /*AllowUnresolved*/ false), |
400 | AC(AC), SQ(DT.getRoot()->getParent()->getParent()->getDataLayout(), |
401 | nullptr, &DT, AC) {} |
402 | |
403 | void run(); |
404 | |
405 | private: |
406 | void RemoveFromAllocasList(unsigned &AllocaIdx) { |
407 | Allocas[AllocaIdx] = Allocas.back(); |
408 | Allocas.pop_back(); |
409 | --AllocaIdx; |
410 | } |
411 | |
412 | unsigned getNumPreds(const BasicBlock *BB) { |
413 | unsigned &NP = BBNumPreds[BB]; |
414 | if (NP == 0) |
415 | NP = pred_size(BB) + 1; |
416 | return NP - 1; |
417 | } |
418 | |
419 | void ComputeLiveInBlocks(AllocaInst *AI, AllocaInfo &Info, |
420 | const SmallPtrSetImpl<BasicBlock *> &DefBlocks, |
421 | SmallPtrSetImpl<BasicBlock *> &LiveInBlocks); |
422 | void RenamePass(BasicBlock *BB, BasicBlock *Pred, |
423 | RenamePassData::ValVector &IncVals, |
424 | RenamePassData::LocationVector &IncLocs, |
425 | std::vector<RenamePassData> &Worklist); |
426 | bool QueuePhiNode(BasicBlock *BB, unsigned AllocaIdx, unsigned &Version); |
427 | |
428 | /// Delete dbg.assigns that have been demoted to dbg.values. |
429 | void cleanUpDbgAssigns() { |
430 | for (auto *DAI : DbgAssignsToDelete) |
431 | DAI->eraseFromParent(); |
432 | DbgAssignsToDelete.clear(); |
433 | for (auto *DVR : DVRAssignsToDelete) |
434 | DVR->eraseFromParent(); |
435 | DVRAssignsToDelete.clear(); |
436 | } |
437 | }; |
438 | |
439 | } // end anonymous namespace |
440 | |
441 | /// Given a LoadInst LI this adds assume(LI != null) after it. |
442 | static void addAssumeNonNull(AssumptionCache *AC, LoadInst *LI) { |
443 | Function *AssumeIntrinsic = |
444 | Intrinsic::getDeclaration(M: LI->getModule(), Intrinsic::id: assume); |
445 | ICmpInst *LoadNotNull = new ICmpInst(ICmpInst::ICMP_NE, LI, |
446 | Constant::getNullValue(Ty: LI->getType())); |
447 | LoadNotNull->insertAfter(InsertPos: LI); |
448 | CallInst *CI = CallInst::Create(Func: AssumeIntrinsic, Args: {LoadNotNull}); |
449 | CI->insertAfter(InsertPos: LoadNotNull); |
450 | AC->registerAssumption(CI: cast<AssumeInst>(Val: CI)); |
451 | } |
452 | |
453 | static void convertMetadataToAssumes(LoadInst *LI, Value *Val, |
454 | const DataLayout &DL, AssumptionCache *AC, |
455 | const DominatorTree *DT) { |
456 | // If the load was marked as nonnull we don't want to lose that information |
457 | // when we erase this Load. So we preserve it with an assume. As !nonnull |
458 | // returns poison while assume violations are immediate undefined behavior, |
459 | // we can only do this if the value is known non-poison. |
460 | if (AC && LI->getMetadata(KindID: LLVMContext::MD_nonnull) && |
461 | LI->getMetadata(KindID: LLVMContext::MD_noundef) && |
462 | !isKnownNonZero(V: Val, Q: SimplifyQuery(DL, DT, AC, LI))) |
463 | addAssumeNonNull(AC, LI); |
464 | } |
465 | |
466 | static void removeIntrinsicUsers(AllocaInst *AI) { |
467 | // Knowing that this alloca is promotable, we know that it's safe to kill all |
468 | // instructions except for load and store. |
469 | |
470 | for (Use &U : llvm::make_early_inc_range(Range: AI->uses())) { |
471 | Instruction *I = cast<Instruction>(Val: U.getUser()); |
472 | if (isa<LoadInst>(Val: I) || isa<StoreInst>(Val: I)) |
473 | continue; |
474 | |
475 | // Drop the use of AI in droppable instructions. |
476 | if (I->isDroppable()) { |
477 | I->dropDroppableUse(U); |
478 | continue; |
479 | } |
480 | |
481 | if (!I->getType()->isVoidTy()) { |
482 | // The only users of this bitcast/GEP instruction are lifetime intrinsics. |
483 | // Follow the use/def chain to erase them now instead of leaving it for |
484 | // dead code elimination later. |
485 | for (Use &UU : llvm::make_early_inc_range(Range: I->uses())) { |
486 | Instruction *Inst = cast<Instruction>(Val: UU.getUser()); |
487 | |
488 | // Drop the use of I in droppable instructions. |
489 | if (Inst->isDroppable()) { |
490 | Inst->dropDroppableUse(U&: UU); |
491 | continue; |
492 | } |
493 | Inst->eraseFromParent(); |
494 | } |
495 | } |
496 | I->eraseFromParent(); |
497 | } |
498 | } |
499 | |
500 | /// Rewrite as many loads as possible given a single store. |
501 | /// |
502 | /// When there is only a single store, we can use the domtree to trivially |
503 | /// replace all of the dominated loads with the stored value. Do so, and return |
504 | /// true if this has successfully promoted the alloca entirely. If this returns |
505 | /// false there were some loads which were not dominated by the single store |
506 | /// and thus must be phi-ed with undef. We fall back to the standard alloca |
507 | /// promotion algorithm in that case. |
508 | static bool |
509 | rewriteSingleStoreAlloca(AllocaInst *AI, AllocaInfo &Info, LargeBlockInfo &LBI, |
510 | const DataLayout &DL, DominatorTree &DT, |
511 | AssumptionCache *AC, |
512 | SmallSet<DbgAssignIntrinsic *, 8> *DbgAssignsToDelete, |
513 | SmallSet<DbgVariableRecord *, 8> *DVRAssignsToDelete) { |
514 | StoreInst *OnlyStore = Info.OnlyStore; |
515 | bool StoringGlobalVal = !isa<Instruction>(Val: OnlyStore->getOperand(i_nocapture: 0)); |
516 | BasicBlock *StoreBB = OnlyStore->getParent(); |
517 | int StoreIndex = -1; |
518 | |
519 | // Clear out UsingBlocks. We will reconstruct it here if needed. |
520 | Info.UsingBlocks.clear(); |
521 | |
522 | for (User *U : make_early_inc_range(Range: AI->users())) { |
523 | Instruction *UserInst = cast<Instruction>(Val: U); |
524 | if (UserInst == OnlyStore) |
525 | continue; |
526 | LoadInst *LI = cast<LoadInst>(Val: UserInst); |
527 | |
528 | // Okay, if we have a load from the alloca, we want to replace it with the |
529 | // only value stored to the alloca. We can do this if the value is |
530 | // dominated by the store. If not, we use the rest of the mem2reg machinery |
531 | // to insert the phi nodes as needed. |
532 | if (!StoringGlobalVal) { // Non-instructions are always dominated. |
533 | if (LI->getParent() == StoreBB) { |
534 | // If we have a use that is in the same block as the store, compare the |
535 | // indices of the two instructions to see which one came first. If the |
536 | // load came before the store, we can't handle it. |
537 | if (StoreIndex == -1) |
538 | StoreIndex = LBI.getInstructionIndex(I: OnlyStore); |
539 | |
540 | if (unsigned(StoreIndex) > LBI.getInstructionIndex(I: LI)) { |
541 | // Can't handle this load, bail out. |
542 | Info.UsingBlocks.push_back(Elt: StoreBB); |
543 | continue; |
544 | } |
545 | } else if (!DT.dominates(A: StoreBB, B: LI->getParent())) { |
546 | // If the load and store are in different blocks, use BB dominance to |
547 | // check their relationships. If the store doesn't dom the use, bail |
548 | // out. |
549 | Info.UsingBlocks.push_back(Elt: LI->getParent()); |
550 | continue; |
551 | } |
552 | } |
553 | |
554 | // Otherwise, we *can* safely rewrite this load. |
555 | Value *ReplVal = OnlyStore->getOperand(i_nocapture: 0); |
556 | // If the replacement value is the load, this must occur in unreachable |
557 | // code. |
558 | if (ReplVal == LI) |
559 | ReplVal = PoisonValue::get(T: LI->getType()); |
560 | |
561 | convertMetadataToAssumes(LI, Val: ReplVal, DL, AC, DT: &DT); |
562 | LI->replaceAllUsesWith(V: ReplVal); |
563 | LI->eraseFromParent(); |
564 | LBI.deleteValue(I: LI); |
565 | } |
566 | |
567 | // Finally, after the scan, check to see if the store is all that is left. |
568 | if (!Info.UsingBlocks.empty()) |
569 | return false; // If not, we'll have to fall back for the remainder. |
570 | |
571 | DIBuilder DIB(*AI->getModule(), /*AllowUnresolved*/ false); |
572 | // Update assignment tracking info for the store we're going to delete. |
573 | Info.AssignmentTracking.updateForDeletedStore( |
574 | ToDelete: Info.OnlyStore, DIB, DbgAssignsToDelete, DVRAssignsToDelete); |
575 | |
576 | // Record debuginfo for the store and remove the declaration's |
577 | // debuginfo. |
578 | auto ConvertDebugInfoForStore = [&](auto &Container) { |
579 | for (auto *DbgItem : Container) { |
580 | if (DbgItem->isAddressOfVariable()) { |
581 | ConvertDebugDeclareToDebugValue(DbgItem, Info.OnlyStore, DIB); |
582 | DbgItem->eraseFromParent(); |
583 | } else if (DbgItem->getExpression()->startsWithDeref()) { |
584 | DbgItem->eraseFromParent(); |
585 | } |
586 | } |
587 | }; |
588 | ConvertDebugInfoForStore(Info.DbgUsers); |
589 | ConvertDebugInfoForStore(Info.DPUsers); |
590 | |
591 | // Remove dbg.assigns linked to the alloca as these are now redundant. |
592 | at::deleteAssignmentMarkers(Inst: AI); |
593 | |
594 | // Remove the (now dead) store and alloca. |
595 | Info.OnlyStore->eraseFromParent(); |
596 | LBI.deleteValue(I: Info.OnlyStore); |
597 | |
598 | AI->eraseFromParent(); |
599 | return true; |
600 | } |
601 | |
602 | /// Many allocas are only used within a single basic block. If this is the |
603 | /// case, avoid traversing the CFG and inserting a lot of potentially useless |
604 | /// PHI nodes by just performing a single linear pass over the basic block |
605 | /// using the Alloca. |
606 | /// |
607 | /// If we cannot promote this alloca (because it is read before it is written), |
608 | /// return false. This is necessary in cases where, due to control flow, the |
609 | /// alloca is undefined only on some control flow paths. e.g. code like |
610 | /// this is correct in LLVM IR: |
611 | /// // A is an alloca with no stores so far |
612 | /// for (...) { |
613 | /// int t = *A; |
614 | /// if (!first_iteration) |
615 | /// use(t); |
616 | /// *A = 42; |
617 | /// } |
618 | static bool |
619 | promoteSingleBlockAlloca(AllocaInst *AI, const AllocaInfo &Info, |
620 | LargeBlockInfo &LBI, const DataLayout &DL, |
621 | DominatorTree &DT, AssumptionCache *AC, |
622 | SmallSet<DbgAssignIntrinsic *, 8> *DbgAssignsToDelete, |
623 | SmallSet<DbgVariableRecord *, 8> *DVRAssignsToDelete) { |
624 | // The trickiest case to handle is when we have large blocks. Because of this, |
625 | // this code is optimized assuming that large blocks happen. This does not |
626 | // significantly pessimize the small block case. This uses LargeBlockInfo to |
627 | // make it efficient to get the index of various operations in the block. |
628 | |
629 | // Walk the use-def list of the alloca, getting the locations of all stores. |
630 | using StoresByIndexTy = SmallVector<std::pair<unsigned, StoreInst *>, 64>; |
631 | StoresByIndexTy StoresByIndex; |
632 | |
633 | for (User *U : AI->users()) |
634 | if (StoreInst *SI = dyn_cast<StoreInst>(Val: U)) |
635 | StoresByIndex.push_back(Elt: std::make_pair(x: LBI.getInstructionIndex(I: SI), y&: SI)); |
636 | |
637 | // Sort the stores by their index, making it efficient to do a lookup with a |
638 | // binary search. |
639 | llvm::sort(C&: StoresByIndex, Comp: less_first()); |
640 | |
641 | // Walk all of the loads from this alloca, replacing them with the nearest |
642 | // store above them, if any. |
643 | for (User *U : make_early_inc_range(Range: AI->users())) { |
644 | LoadInst *LI = dyn_cast<LoadInst>(Val: U); |
645 | if (!LI) |
646 | continue; |
647 | |
648 | unsigned LoadIdx = LBI.getInstructionIndex(I: LI); |
649 | |
650 | // Find the nearest store that has a lower index than this load. |
651 | StoresByIndexTy::iterator I = llvm::lower_bound( |
652 | Range&: StoresByIndex, |
653 | Value: std::make_pair(x&: LoadIdx, y: static_cast<StoreInst *>(nullptr)), |
654 | C: less_first()); |
655 | Value *ReplVal; |
656 | if (I == StoresByIndex.begin()) { |
657 | if (StoresByIndex.empty()) |
658 | // If there are no stores, the load takes the undef value. |
659 | ReplVal = UndefValue::get(T: LI->getType()); |
660 | else |
661 | // There is no store before this load, bail out (load may be affected |
662 | // by the following stores - see main comment). |
663 | return false; |
664 | } else { |
665 | // Otherwise, there was a store before this load, the load takes its |
666 | // value. |
667 | ReplVal = std::prev(x: I)->second->getOperand(i_nocapture: 0); |
668 | } |
669 | |
670 | convertMetadataToAssumes(LI, Val: ReplVal, DL, AC, DT: &DT); |
671 | |
672 | // If the replacement value is the load, this must occur in unreachable |
673 | // code. |
674 | if (ReplVal == LI) |
675 | ReplVal = PoisonValue::get(T: LI->getType()); |
676 | |
677 | LI->replaceAllUsesWith(V: ReplVal); |
678 | LI->eraseFromParent(); |
679 | LBI.deleteValue(I: LI); |
680 | } |
681 | |
682 | // Remove the (now dead) stores and alloca. |
683 | DIBuilder DIB(*AI->getModule(), /*AllowUnresolved*/ false); |
684 | while (!AI->use_empty()) { |
685 | StoreInst *SI = cast<StoreInst>(Val: AI->user_back()); |
686 | // Update assignment tracking info for the store we're going to delete. |
687 | Info.AssignmentTracking.updateForDeletedStore(ToDelete: SI, DIB, DbgAssignsToDelete, |
688 | DVRAssignsToDelete); |
689 | // Record debuginfo for the store before removing it. |
690 | auto DbgUpdateForStore = [&](auto &Container) { |
691 | for (auto *DbgItem : Container) { |
692 | if (DbgItem->isAddressOfVariable()) { |
693 | ConvertDebugDeclareToDebugValue(DbgItem, SI, DIB); |
694 | } |
695 | } |
696 | }; |
697 | DbgUpdateForStore(Info.DbgUsers); |
698 | DbgUpdateForStore(Info.DPUsers); |
699 | |
700 | SI->eraseFromParent(); |
701 | LBI.deleteValue(I: SI); |
702 | } |
703 | |
704 | // Remove dbg.assigns linked to the alloca as these are now redundant. |
705 | at::deleteAssignmentMarkers(Inst: AI); |
706 | AI->eraseFromParent(); |
707 | |
708 | // The alloca's debuginfo can be removed as well. |
709 | auto DbgUpdateForAlloca = [&](auto &Container) { |
710 | for (auto *DbgItem : Container) |
711 | if (DbgItem->isAddressOfVariable() || |
712 | DbgItem->getExpression()->startsWithDeref()) |
713 | DbgItem->eraseFromParent(); |
714 | }; |
715 | DbgUpdateForAlloca(Info.DbgUsers); |
716 | DbgUpdateForAlloca(Info.DPUsers); |
717 | |
718 | ++NumLocalPromoted; |
719 | return true; |
720 | } |
721 | |
722 | void PromoteMem2Reg::run() { |
723 | Function &F = *DT.getRoot()->getParent(); |
724 | |
725 | AllocaDbgUsers.resize(N: Allocas.size()); |
726 | AllocaATInfo.resize(N: Allocas.size()); |
727 | AllocaDPUsers.resize(N: Allocas.size()); |
728 | |
729 | AllocaInfo Info; |
730 | LargeBlockInfo LBI; |
731 | ForwardIDFCalculator IDF(DT); |
732 | |
733 | for (unsigned AllocaNum = 0; AllocaNum != Allocas.size(); ++AllocaNum) { |
734 | AllocaInst *AI = Allocas[AllocaNum]; |
735 | |
736 | assert(isAllocaPromotable(AI) && "Cannot promote non-promotable alloca!" ); |
737 | assert(AI->getParent()->getParent() == &F && |
738 | "All allocas should be in the same function, which is same as DF!" ); |
739 | |
740 | removeIntrinsicUsers(AI); |
741 | |
742 | if (AI->use_empty()) { |
743 | // If there are no uses of the alloca, just delete it now. |
744 | AI->eraseFromParent(); |
745 | |
746 | // Remove the alloca from the Allocas list, since it has been processed |
747 | RemoveFromAllocasList(AllocaIdx&: AllocaNum); |
748 | ++NumDeadAlloca; |
749 | continue; |
750 | } |
751 | |
752 | // Calculate the set of read and write-locations for each alloca. This is |
753 | // analogous to finding the 'uses' and 'definitions' of each variable. |
754 | Info.AnalyzeAlloca(AI); |
755 | |
756 | // If there is only a single store to this value, replace any loads of |
757 | // it that are directly dominated by the definition with the value stored. |
758 | if (Info.DefiningBlocks.size() == 1) { |
759 | if (rewriteSingleStoreAlloca(AI, Info, LBI, DL: SQ.DL, DT, AC, |
760 | DbgAssignsToDelete: &DbgAssignsToDelete, DVRAssignsToDelete: &DVRAssignsToDelete)) { |
761 | // The alloca has been processed, move on. |
762 | RemoveFromAllocasList(AllocaIdx&: AllocaNum); |
763 | ++NumSingleStore; |
764 | continue; |
765 | } |
766 | } |
767 | |
768 | // If the alloca is only read and written in one basic block, just perform a |
769 | // linear sweep over the block to eliminate it. |
770 | if (Info.OnlyUsedInOneBlock && |
771 | promoteSingleBlockAlloca(AI, Info, LBI, DL: SQ.DL, DT, AC, |
772 | DbgAssignsToDelete: &DbgAssignsToDelete, DVRAssignsToDelete: &DVRAssignsToDelete)) { |
773 | // The alloca has been processed, move on. |
774 | RemoveFromAllocasList(AllocaIdx&: AllocaNum); |
775 | continue; |
776 | } |
777 | |
778 | // If we haven't computed a numbering for the BB's in the function, do so |
779 | // now. |
780 | if (BBNumbers.empty()) { |
781 | unsigned ID = 0; |
782 | for (auto &BB : F) |
783 | BBNumbers[&BB] = ID++; |
784 | } |
785 | |
786 | // Remember the dbg.declare intrinsic describing this alloca, if any. |
787 | if (!Info.DbgUsers.empty()) |
788 | AllocaDbgUsers[AllocaNum] = Info.DbgUsers; |
789 | if (!Info.AssignmentTracking.empty()) |
790 | AllocaATInfo[AllocaNum] = Info.AssignmentTracking; |
791 | if (!Info.DPUsers.empty()) |
792 | AllocaDPUsers[AllocaNum] = Info.DPUsers; |
793 | |
794 | // Keep the reverse mapping of the 'Allocas' array for the rename pass. |
795 | AllocaLookup[Allocas[AllocaNum]] = AllocaNum; |
796 | |
797 | // Unique the set of defining blocks for efficient lookup. |
798 | SmallPtrSet<BasicBlock *, 32> DefBlocks(Info.DefiningBlocks.begin(), |
799 | Info.DefiningBlocks.end()); |
800 | |
801 | // Determine which blocks the value is live in. These are blocks which lead |
802 | // to uses. |
803 | SmallPtrSet<BasicBlock *, 32> LiveInBlocks; |
804 | ComputeLiveInBlocks(AI, Info, DefBlocks, LiveInBlocks); |
805 | |
806 | // At this point, we're committed to promoting the alloca using IDF's, and |
807 | // the standard SSA construction algorithm. Determine which blocks need phi |
808 | // nodes and see if we can optimize out some work by avoiding insertion of |
809 | // dead phi nodes. |
810 | IDF.setLiveInBlocks(LiveInBlocks); |
811 | IDF.setDefiningBlocks(DefBlocks); |
812 | SmallVector<BasicBlock *, 32> PHIBlocks; |
813 | IDF.calculate(IDFBlocks&: PHIBlocks); |
814 | llvm::sort(C&: PHIBlocks, Comp: [this](BasicBlock *A, BasicBlock *B) { |
815 | return BBNumbers.find(Val: A)->second < BBNumbers.find(Val: B)->second; |
816 | }); |
817 | |
818 | unsigned CurrentVersion = 0; |
819 | for (BasicBlock *BB : PHIBlocks) |
820 | QueuePhiNode(BB, AllocaIdx: AllocaNum, Version&: CurrentVersion); |
821 | } |
822 | |
823 | if (Allocas.empty()) { |
824 | cleanUpDbgAssigns(); |
825 | return; // All of the allocas must have been trivial! |
826 | } |
827 | LBI.clear(); |
828 | |
829 | // Set the incoming values for the basic block to be null values for all of |
830 | // the alloca's. We do this in case there is a load of a value that has not |
831 | // been stored yet. In this case, it will get this null value. |
832 | RenamePassData::ValVector Values(Allocas.size()); |
833 | for (unsigned i = 0, e = Allocas.size(); i != e; ++i) |
834 | Values[i] = UndefValue::get(T: Allocas[i]->getAllocatedType()); |
835 | |
836 | // When handling debug info, treat all incoming values as if they have unknown |
837 | // locations until proven otherwise. |
838 | RenamePassData::LocationVector Locations(Allocas.size()); |
839 | |
840 | // Walks all basic blocks in the function performing the SSA rename algorithm |
841 | // and inserting the phi nodes we marked as necessary |
842 | std::vector<RenamePassData> RenamePassWorkList; |
843 | RenamePassWorkList.emplace_back(args: &F.front(), args: nullptr, args: std::move(Values), |
844 | args: std::move(Locations)); |
845 | do { |
846 | RenamePassData RPD = std::move(RenamePassWorkList.back()); |
847 | RenamePassWorkList.pop_back(); |
848 | // RenamePass may add new worklist entries. |
849 | RenamePass(BB: RPD.BB, Pred: RPD.Pred, IncVals&: RPD.Values, IncLocs&: RPD.Locations, Worklist&: RenamePassWorkList); |
850 | } while (!RenamePassWorkList.empty()); |
851 | |
852 | // The renamer uses the Visited set to avoid infinite loops. Clear it now. |
853 | Visited.clear(); |
854 | |
855 | // Remove the allocas themselves from the function. |
856 | for (Instruction *A : Allocas) { |
857 | // Remove dbg.assigns linked to the alloca as these are now redundant. |
858 | at::deleteAssignmentMarkers(Inst: A); |
859 | // If there are any uses of the alloca instructions left, they must be in |
860 | // unreachable basic blocks that were not processed by walking the dominator |
861 | // tree. Just delete the users now. |
862 | if (!A->use_empty()) |
863 | A->replaceAllUsesWith(V: PoisonValue::get(T: A->getType())); |
864 | A->eraseFromParent(); |
865 | } |
866 | |
867 | // Remove alloca's dbg.declare intrinsics from the function. |
868 | auto RemoveDbgDeclares = [&](auto &Container) { |
869 | for (auto &DbgUsers : Container) { |
870 | for (auto *DbgItem : DbgUsers) |
871 | if (DbgItem->isAddressOfVariable() || |
872 | DbgItem->getExpression()->startsWithDeref()) |
873 | DbgItem->eraseFromParent(); |
874 | } |
875 | }; |
876 | RemoveDbgDeclares(AllocaDbgUsers); |
877 | RemoveDbgDeclares(AllocaDPUsers); |
878 | |
879 | // Loop over all of the PHI nodes and see if there are any that we can get |
880 | // rid of because they merge all of the same incoming values. This can |
881 | // happen due to undef values coming into the PHI nodes. This process is |
882 | // iterative, because eliminating one PHI node can cause others to be removed. |
883 | bool EliminatedAPHI = true; |
884 | while (EliminatedAPHI) { |
885 | EliminatedAPHI = false; |
886 | |
887 | // Iterating over NewPhiNodes is deterministic, so it is safe to try to |
888 | // simplify and RAUW them as we go. If it was not, we could add uses to |
889 | // the values we replace with in a non-deterministic order, thus creating |
890 | // non-deterministic def->use chains. |
891 | for (DenseMap<std::pair<unsigned, unsigned>, PHINode *>::iterator |
892 | I = NewPhiNodes.begin(), |
893 | E = NewPhiNodes.end(); |
894 | I != E;) { |
895 | PHINode *PN = I->second; |
896 | |
897 | // If this PHI node merges one value and/or undefs, get the value. |
898 | if (Value *V = simplifyInstruction(I: PN, Q: SQ)) { |
899 | PN->replaceAllUsesWith(V); |
900 | PN->eraseFromParent(); |
901 | NewPhiNodes.erase(I: I++); |
902 | EliminatedAPHI = true; |
903 | continue; |
904 | } |
905 | ++I; |
906 | } |
907 | } |
908 | |
909 | // At this point, the renamer has added entries to PHI nodes for all reachable |
910 | // code. Unfortunately, there may be unreachable blocks which the renamer |
911 | // hasn't traversed. If this is the case, the PHI nodes may not |
912 | // have incoming values for all predecessors. Loop over all PHI nodes we have |
913 | // created, inserting poison values if they are missing any incoming values. |
914 | for (DenseMap<std::pair<unsigned, unsigned>, PHINode *>::iterator |
915 | I = NewPhiNodes.begin(), |
916 | E = NewPhiNodes.end(); |
917 | I != E; ++I) { |
918 | // We want to do this once per basic block. As such, only process a block |
919 | // when we find the PHI that is the first entry in the block. |
920 | PHINode *SomePHI = I->second; |
921 | BasicBlock *BB = SomePHI->getParent(); |
922 | if (&BB->front() != SomePHI) |
923 | continue; |
924 | |
925 | // Only do work here if there the PHI nodes are missing incoming values. We |
926 | // know that all PHI nodes that were inserted in a block will have the same |
927 | // number of incoming values, so we can just check any of them. |
928 | if (SomePHI->getNumIncomingValues() == getNumPreds(BB)) |
929 | continue; |
930 | |
931 | // Get the preds for BB. |
932 | SmallVector<BasicBlock *, 16> Preds(predecessors(BB)); |
933 | |
934 | // Ok, now we know that all of the PHI nodes are missing entries for some |
935 | // basic blocks. Start by sorting the incoming predecessors for efficient |
936 | // access. |
937 | auto CompareBBNumbers = [this](BasicBlock *A, BasicBlock *B) { |
938 | return BBNumbers.find(Val: A)->second < BBNumbers.find(Val: B)->second; |
939 | }; |
940 | llvm::sort(C&: Preds, Comp: CompareBBNumbers); |
941 | |
942 | // Now we loop through all BB's which have entries in SomePHI and remove |
943 | // them from the Preds list. |
944 | for (unsigned i = 0, e = SomePHI->getNumIncomingValues(); i != e; ++i) { |
945 | // Do a log(n) search of the Preds list for the entry we want. |
946 | SmallVectorImpl<BasicBlock *>::iterator EntIt = llvm::lower_bound( |
947 | Range&: Preds, Value: SomePHI->getIncomingBlock(i), C: CompareBBNumbers); |
948 | assert(EntIt != Preds.end() && *EntIt == SomePHI->getIncomingBlock(i) && |
949 | "PHI node has entry for a block which is not a predecessor!" ); |
950 | |
951 | // Remove the entry |
952 | Preds.erase(CI: EntIt); |
953 | } |
954 | |
955 | // At this point, the blocks left in the preds list must have dummy |
956 | // entries inserted into every PHI nodes for the block. Update all the phi |
957 | // nodes in this block that we are inserting (there could be phis before |
958 | // mem2reg runs). |
959 | unsigned NumBadPreds = SomePHI->getNumIncomingValues(); |
960 | BasicBlock::iterator BBI = BB->begin(); |
961 | while ((SomePHI = dyn_cast<PHINode>(Val: BBI++)) && |
962 | SomePHI->getNumIncomingValues() == NumBadPreds) { |
963 | Value *PoisonVal = PoisonValue::get(T: SomePHI->getType()); |
964 | for (BasicBlock *Pred : Preds) |
965 | SomePHI->addIncoming(V: PoisonVal, BB: Pred); |
966 | } |
967 | } |
968 | |
969 | NewPhiNodes.clear(); |
970 | cleanUpDbgAssigns(); |
971 | } |
972 | |
973 | /// Determine which blocks the value is live in. |
974 | /// |
975 | /// These are blocks which lead to uses. Knowing this allows us to avoid |
976 | /// inserting PHI nodes into blocks which don't lead to uses (thus, the |
977 | /// inserted phi nodes would be dead). |
978 | void PromoteMem2Reg::ComputeLiveInBlocks( |
979 | AllocaInst *AI, AllocaInfo &Info, |
980 | const SmallPtrSetImpl<BasicBlock *> &DefBlocks, |
981 | SmallPtrSetImpl<BasicBlock *> &LiveInBlocks) { |
982 | // To determine liveness, we must iterate through the predecessors of blocks |
983 | // where the def is live. Blocks are added to the worklist if we need to |
984 | // check their predecessors. Start with all the using blocks. |
985 | SmallVector<BasicBlock *, 64> LiveInBlockWorklist(Info.UsingBlocks.begin(), |
986 | Info.UsingBlocks.end()); |
987 | |
988 | // If any of the using blocks is also a definition block, check to see if the |
989 | // definition occurs before or after the use. If it happens before the use, |
990 | // the value isn't really live-in. |
991 | for (unsigned i = 0, e = LiveInBlockWorklist.size(); i != e; ++i) { |
992 | BasicBlock *BB = LiveInBlockWorklist[i]; |
993 | if (!DefBlocks.count(Ptr: BB)) |
994 | continue; |
995 | |
996 | // Okay, this is a block that both uses and defines the value. If the first |
997 | // reference to the alloca is a def (store), then we know it isn't live-in. |
998 | for (BasicBlock::iterator I = BB->begin();; ++I) { |
999 | if (StoreInst *SI = dyn_cast<StoreInst>(Val&: I)) { |
1000 | if (SI->getOperand(i_nocapture: 1) != AI) |
1001 | continue; |
1002 | |
1003 | // We found a store to the alloca before a load. The alloca is not |
1004 | // actually live-in here. |
1005 | LiveInBlockWorklist[i] = LiveInBlockWorklist.back(); |
1006 | LiveInBlockWorklist.pop_back(); |
1007 | --i; |
1008 | --e; |
1009 | break; |
1010 | } |
1011 | |
1012 | if (LoadInst *LI = dyn_cast<LoadInst>(Val&: I)) |
1013 | // Okay, we found a load before a store to the alloca. It is actually |
1014 | // live into this block. |
1015 | if (LI->getOperand(i_nocapture: 0) == AI) |
1016 | break; |
1017 | } |
1018 | } |
1019 | |
1020 | // Now that we have a set of blocks where the phi is live-in, recursively add |
1021 | // their predecessors until we find the full region the value is live. |
1022 | while (!LiveInBlockWorklist.empty()) { |
1023 | BasicBlock *BB = LiveInBlockWorklist.pop_back_val(); |
1024 | |
1025 | // The block really is live in here, insert it into the set. If already in |
1026 | // the set, then it has already been processed. |
1027 | if (!LiveInBlocks.insert(Ptr: BB).second) |
1028 | continue; |
1029 | |
1030 | // Since the value is live into BB, it is either defined in a predecessor or |
1031 | // live into it to. Add the preds to the worklist unless they are a |
1032 | // defining block. |
1033 | for (BasicBlock *P : predecessors(BB)) { |
1034 | // The value is not live into a predecessor if it defines the value. |
1035 | if (DefBlocks.count(Ptr: P)) |
1036 | continue; |
1037 | |
1038 | // Otherwise it is, add to the worklist. |
1039 | LiveInBlockWorklist.push_back(Elt: P); |
1040 | } |
1041 | } |
1042 | } |
1043 | |
1044 | /// Queue a phi-node to be added to a basic-block for a specific Alloca. |
1045 | /// |
1046 | /// Returns true if there wasn't already a phi-node for that variable |
1047 | bool PromoteMem2Reg::QueuePhiNode(BasicBlock *BB, unsigned AllocaNo, |
1048 | unsigned &Version) { |
1049 | // Look up the basic-block in question. |
1050 | PHINode *&PN = NewPhiNodes[std::make_pair(x&: BBNumbers[BB], y&: AllocaNo)]; |
1051 | |
1052 | // If the BB already has a phi node added for the i'th alloca then we're done! |
1053 | if (PN) |
1054 | return false; |
1055 | |
1056 | // Create a PhiNode using the dereferenced type... and add the phi-node to the |
1057 | // BasicBlock. |
1058 | PN = PHINode::Create(Ty: Allocas[AllocaNo]->getAllocatedType(), NumReservedValues: getNumPreds(BB), |
1059 | NameStr: Allocas[AllocaNo]->getName() + "." + Twine(Version++)); |
1060 | PN->insertBefore(InsertPos: BB->begin()); |
1061 | ++NumPHIInsert; |
1062 | PhiToAllocaMap[PN] = AllocaNo; |
1063 | return true; |
1064 | } |
1065 | |
1066 | /// Update the debug location of a phi. \p ApplyMergedLoc indicates whether to |
1067 | /// create a merged location incorporating \p DL, or to set \p DL directly. |
1068 | static void updateForIncomingValueLocation(PHINode *PN, DebugLoc DL, |
1069 | bool ApplyMergedLoc) { |
1070 | if (ApplyMergedLoc) |
1071 | PN->applyMergedLocation(LocA: PN->getDebugLoc(), LocB: DL); |
1072 | else |
1073 | PN->setDebugLoc(DL); |
1074 | } |
1075 | |
1076 | /// Recursively traverse the CFG of the function, renaming loads and |
1077 | /// stores to the allocas which we are promoting. |
1078 | /// |
1079 | /// IncomingVals indicates what value each Alloca contains on exit from the |
1080 | /// predecessor block Pred. |
1081 | void PromoteMem2Reg::RenamePass(BasicBlock *BB, BasicBlock *Pred, |
1082 | RenamePassData::ValVector &IncomingVals, |
1083 | RenamePassData::LocationVector &IncomingLocs, |
1084 | std::vector<RenamePassData> &Worklist) { |
1085 | NextIteration: |
1086 | // If we are inserting any phi nodes into this BB, they will already be in the |
1087 | // block. |
1088 | if (PHINode *APN = dyn_cast<PHINode>(Val: BB->begin())) { |
1089 | // If we have PHI nodes to update, compute the number of edges from Pred to |
1090 | // BB. |
1091 | if (PhiToAllocaMap.count(Val: APN)) { |
1092 | // We want to be able to distinguish between PHI nodes being inserted by |
1093 | // this invocation of mem2reg from those phi nodes that already existed in |
1094 | // the IR before mem2reg was run. We determine that APN is being inserted |
1095 | // because it is missing incoming edges. All other PHI nodes being |
1096 | // inserted by this pass of mem2reg will have the same number of incoming |
1097 | // operands so far. Remember this count. |
1098 | unsigned NewPHINumOperands = APN->getNumOperands(); |
1099 | |
1100 | unsigned NumEdges = llvm::count(Range: successors(BB: Pred), Element: BB); |
1101 | assert(NumEdges && "Must be at least one edge from Pred to BB!" ); |
1102 | |
1103 | // Add entries for all the phis. |
1104 | BasicBlock::iterator PNI = BB->begin(); |
1105 | do { |
1106 | unsigned AllocaNo = PhiToAllocaMap[APN]; |
1107 | |
1108 | // Update the location of the phi node. |
1109 | updateForIncomingValueLocation(PN: APN, DL: IncomingLocs[AllocaNo], |
1110 | ApplyMergedLoc: APN->getNumIncomingValues() > 0); |
1111 | |
1112 | // Add N incoming values to the PHI node. |
1113 | for (unsigned i = 0; i != NumEdges; ++i) |
1114 | APN->addIncoming(V: IncomingVals[AllocaNo], BB: Pred); |
1115 | |
1116 | // The currently active variable for this block is now the PHI. |
1117 | IncomingVals[AllocaNo] = APN; |
1118 | AllocaATInfo[AllocaNo].updateForNewPhi(NewPhi: APN, DIB); |
1119 | auto ConvertDbgDeclares = [&](auto &Container) { |
1120 | for (auto *DbgItem : Container) |
1121 | if (DbgItem->isAddressOfVariable()) |
1122 | ConvertDebugDeclareToDebugValue(DbgItem, APN, DIB); |
1123 | }; |
1124 | ConvertDbgDeclares(AllocaDbgUsers[AllocaNo]); |
1125 | ConvertDbgDeclares(AllocaDPUsers[AllocaNo]); |
1126 | |
1127 | // Get the next phi node. |
1128 | ++PNI; |
1129 | APN = dyn_cast<PHINode>(Val&: PNI); |
1130 | if (!APN) |
1131 | break; |
1132 | |
1133 | // Verify that it is missing entries. If not, it is not being inserted |
1134 | // by this mem2reg invocation so we want to ignore it. |
1135 | } while (APN->getNumOperands() == NewPHINumOperands); |
1136 | } |
1137 | } |
1138 | |
1139 | // Don't revisit blocks. |
1140 | if (!Visited.insert(Ptr: BB).second) |
1141 | return; |
1142 | |
1143 | for (BasicBlock::iterator II = BB->begin(); !II->isTerminator();) { |
1144 | Instruction *I = &*II++; // get the instruction, increment iterator |
1145 | |
1146 | if (LoadInst *LI = dyn_cast<LoadInst>(Val: I)) { |
1147 | AllocaInst *Src = dyn_cast<AllocaInst>(Val: LI->getPointerOperand()); |
1148 | if (!Src) |
1149 | continue; |
1150 | |
1151 | DenseMap<AllocaInst *, unsigned>::iterator AI = AllocaLookup.find(Val: Src); |
1152 | if (AI == AllocaLookup.end()) |
1153 | continue; |
1154 | |
1155 | Value *V = IncomingVals[AI->second]; |
1156 | convertMetadataToAssumes(LI, Val: V, DL: SQ.DL, AC, DT: &DT); |
1157 | |
1158 | // Anything using the load now uses the current value. |
1159 | LI->replaceAllUsesWith(V); |
1160 | LI->eraseFromParent(); |
1161 | } else if (StoreInst *SI = dyn_cast<StoreInst>(Val: I)) { |
1162 | // Delete this instruction and mark the name as the current holder of the |
1163 | // value |
1164 | AllocaInst *Dest = dyn_cast<AllocaInst>(Val: SI->getPointerOperand()); |
1165 | if (!Dest) |
1166 | continue; |
1167 | |
1168 | DenseMap<AllocaInst *, unsigned>::iterator ai = AllocaLookup.find(Val: Dest); |
1169 | if (ai == AllocaLookup.end()) |
1170 | continue; |
1171 | |
1172 | // what value were we writing? |
1173 | unsigned AllocaNo = ai->second; |
1174 | IncomingVals[AllocaNo] = SI->getOperand(i_nocapture: 0); |
1175 | |
1176 | // Record debuginfo for the store before removing it. |
1177 | IncomingLocs[AllocaNo] = SI->getDebugLoc(); |
1178 | AllocaATInfo[AllocaNo].updateForDeletedStore(ToDelete: SI, DIB, DbgAssignsToDelete: &DbgAssignsToDelete, |
1179 | DVRAssignsToDelete: &DVRAssignsToDelete); |
1180 | auto ConvertDbgDeclares = [&](auto &Container) { |
1181 | for (auto *DbgItem : Container) |
1182 | if (DbgItem->isAddressOfVariable()) |
1183 | ConvertDebugDeclareToDebugValue(DbgItem, SI, DIB); |
1184 | }; |
1185 | ConvertDbgDeclares(AllocaDbgUsers[ai->second]); |
1186 | ConvertDbgDeclares(AllocaDPUsers[ai->second]); |
1187 | SI->eraseFromParent(); |
1188 | } |
1189 | } |
1190 | |
1191 | // 'Recurse' to our successors. |
1192 | succ_iterator I = succ_begin(BB), E = succ_end(BB); |
1193 | if (I == E) |
1194 | return; |
1195 | |
1196 | // Keep track of the successors so we don't visit the same successor twice |
1197 | SmallPtrSet<BasicBlock *, 8> VisitedSuccs; |
1198 | |
1199 | // Handle the first successor without using the worklist. |
1200 | VisitedSuccs.insert(Ptr: *I); |
1201 | Pred = BB; |
1202 | BB = *I; |
1203 | ++I; |
1204 | |
1205 | for (; I != E; ++I) |
1206 | if (VisitedSuccs.insert(Ptr: *I).second) |
1207 | Worklist.emplace_back(args: *I, args&: Pred, args&: IncomingVals, args&: IncomingLocs); |
1208 | |
1209 | goto NextIteration; |
1210 | } |
1211 | |
1212 | void llvm::PromoteMemToReg(ArrayRef<AllocaInst *> Allocas, DominatorTree &DT, |
1213 | AssumptionCache *AC) { |
1214 | // If there is nothing to do, bail out... |
1215 | if (Allocas.empty()) |
1216 | return; |
1217 | |
1218 | PromoteMem2Reg(Allocas, DT, AC).run(); |
1219 | } |
1220 | |