LLVM  16.0.0git
PromoteMemoryToRegister.cpp
Go to the documentation of this file.
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"
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/Dominators.h"
35 #include "llvm/IR/Function.h"
36 #include "llvm/IR/InstrTypes.h"
37 #include "llvm/IR/Instruction.h"
38 #include "llvm/IR/Instructions.h"
39 #include "llvm/IR/IntrinsicInst.h"
40 #include "llvm/IR/Intrinsics.h"
41 #include "llvm/IR/LLVMContext.h"
42 #include "llvm/IR/Module.h"
43 #include "llvm/IR/Type.h"
44 #include "llvm/IR/User.h"
45 #include "llvm/Support/Casting.h"
48 #include <algorithm>
49 #include <cassert>
50 #include <iterator>
51 #include <utility>
52 #include <vector>
53 
54 using namespace llvm;
55 
56 #define DEBUG_TYPE "mem2reg"
57 
58 STATISTIC(NumLocalPromoted, "Number of alloca's promoted within one block");
59 STATISTIC(NumSingleStore, "Number of alloca's promoted with a single store");
60 STATISTIC(NumDeadAlloca, "Number of dead alloca's removed");
61 STATISTIC(NumPHIInsert, "Number of PHI nodes inserted");
62 
64  // Only allow direct and non-volatile loads and stores...
65  for (const User *U : AI->users()) {
66  if (const LoadInst *LI = dyn_cast<LoadInst>(U)) {
67  // Note that atomic loads can be transformed; atomic semantics do
68  // not have any meaning for a local alloca.
69  if (LI->isVolatile() || LI->getType() != AI->getAllocatedType())
70  return false;
71  } else if (const StoreInst *SI = dyn_cast<StoreInst>(U)) {
72  if (SI->getValueOperand() == AI ||
73  SI->getValueOperand()->getType() != AI->getAllocatedType())
74  return false; // Don't allow a store OF the AI, only INTO the AI.
75  // Note that atomic stores can be transformed; atomic semantics do
76  // not have any meaning for a local alloca.
77  if (SI->isVolatile())
78  return false;
79  } else if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(U)) {
80  if (!II->isLifetimeStartOrEnd() && !II->isDroppable())
81  return false;
82  } else if (const BitCastInst *BCI = dyn_cast<BitCastInst>(U)) {
84  return false;
85  } else if (const GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(U)) {
86  if (!GEPI->hasAllZeroIndices())
87  return false;
89  return false;
90  } else if (const AddrSpaceCastInst *ASCI = dyn_cast<AddrSpaceCastInst>(U)) {
91  if (!onlyUsedByLifetimeMarkers(ASCI))
92  return false;
93  } else {
94  return false;
95  }
96  }
97 
98  return true;
99 }
100 
101 namespace {
102 
103 /// Helper for updating assignment tracking debug info when promoting allocas.
104 class AssignmentTrackingInfo {
105  /// DbgAssignIntrinsics linked to the alloca with at most one per variable
106  /// fragment. (i.e. not be a comprehensive set if there are multiple
107  /// dbg.assigns for one variable fragment).
109 
110 public:
111  void init(AllocaInst *AI) {
114  if (Vars.insert(DebugVariable(DAI)).second)
115  DbgAssigns.push_back(DAI);
116  }
117  }
118 
119  /// Update assignment tracking debug info given for the to-be-deleted store
120  /// \p ToDelete that stores to this alloca.
121  void updateForDeletedStore(StoreInst *ToDelete, DIBuilder &DIB) const {
122  // There's nothing to do if the alloca doesn't have any variables using
123  // assignment tracking.
124  if (DbgAssigns.empty()) {
125  assert(at::getAssignmentMarkers(ToDelete).empty());
126  return;
127  }
128 
129  // Just leave dbg.assign intrinsics in place and remember that we've seen
130  // one for each variable fragment.
131  SmallSet<DebugVariable, 2> VarHasDbgAssignForStore;
132  for (DbgAssignIntrinsic *DAI : at::getAssignmentMarkers(ToDelete))
133  VarHasDbgAssignForStore.insert(DebugVariable(DAI));
134 
135  // It's possible for variables using assignment tracking to have no
136  // dbg.assign linked to this store. These are variables in DbgAssigns that
137  // are missing from VarHasDbgAssignForStore. Since there isn't a dbg.assign
138  // to mark the assignment - and the store is going to be deleted - insert a
139  // dbg.value to do that now. An untracked store may be either one that
140  // cannot be represented using assignment tracking (non-const offset or
141  // size) or one that is trackable but has had its DIAssignID attachment
142  // dropped accidentally.
143  for (auto *DAI : DbgAssigns) {
144  if (VarHasDbgAssignForStore.contains(DebugVariable(DAI)))
145  continue;
146  ConvertDebugDeclareToDebugValue(DAI, ToDelete, DIB);
147  }
148  }
149 
150  /// Update assignment tracking debug info given for the newly inserted PHI \p
151  /// NewPhi.
152  void updateForNewPhi(PHINode *NewPhi, DIBuilder &DIB) const {
153  // Regardless of the position of dbg.assigns relative to stores, the
154  // incoming values into a new PHI should be the same for the (imaginary)
155  // debug-phi.
156  for (auto *DAI : DbgAssigns)
157  ConvertDebugDeclareToDebugValue(DAI, NewPhi, DIB);
158  }
159 
160  void clear() { DbgAssigns.clear(); }
161  bool empty() { return DbgAssigns.empty(); }
162 };
163 
164 struct AllocaInfo {
165  using DbgUserVec = SmallVector<DbgVariableIntrinsic *, 1>;
166 
167  SmallVector<BasicBlock *, 32> DefiningBlocks;
168  SmallVector<BasicBlock *, 32> UsingBlocks;
169 
170  StoreInst *OnlyStore;
171  BasicBlock *OnlyBlock;
172  bool OnlyUsedInOneBlock;
173 
174  /// Debug users of the alloca - does not include dbg.assign intrinsics.
175  DbgUserVec DbgUsers;
176  /// Helper to update assignment tracking debug info.
177  AssignmentTrackingInfo AssignmentTracking;
178 
179  void clear() {
180  DefiningBlocks.clear();
181  UsingBlocks.clear();
182  OnlyStore = nullptr;
183  OnlyBlock = nullptr;
184  OnlyUsedInOneBlock = true;
185  DbgUsers.clear();
186  AssignmentTracking.clear();
187  }
188 
189  /// Scan the uses of the specified alloca, filling in the AllocaInfo used
190  /// by the rest of the pass to reason about the uses of this alloca.
191  void AnalyzeAlloca(AllocaInst *AI) {
192  clear();
193 
194  // As we scan the uses of the alloca instruction, keep track of stores,
195  // and decide whether all of the loads and stores to the alloca are within
196  // the same basic block.
197  for (User *U : AI->users()) {
198  Instruction *User = cast<Instruction>(U);
199 
200  if (StoreInst *SI = dyn_cast<StoreInst>(User)) {
201  // Remember the basic blocks which define new values for the alloca
202  DefiningBlocks.push_back(SI->getParent());
203  OnlyStore = SI;
204  } else {
205  LoadInst *LI = cast<LoadInst>(User);
206  // Otherwise it must be a load instruction, keep track of variable
207  // reads.
208  UsingBlocks.push_back(LI->getParent());
209  }
210 
211  if (OnlyUsedInOneBlock) {
212  if (!OnlyBlock)
213  OnlyBlock = User->getParent();
214  else if (OnlyBlock != User->getParent())
215  OnlyUsedInOneBlock = false;
216  }
217  }
218  DbgUserVec AllDbgUsers;
219  findDbgUsers(AllDbgUsers, AI);
220  std::copy_if(AllDbgUsers.begin(), AllDbgUsers.end(),
221  std::back_inserter(DbgUsers), [](DbgVariableIntrinsic *DII) {
222  return !isa<DbgAssignIntrinsic>(DII);
223  });
224  AssignmentTracking.init(AI);
225  }
226 };
227 
228 /// Data package used by RenamePass().
229 struct RenamePassData {
230  using ValVector = std::vector<Value *>;
231  using LocationVector = std::vector<DebugLoc>;
232 
233  RenamePassData(BasicBlock *B, BasicBlock *P, ValVector V, LocationVector L)
234  : BB(B), Pred(P), Values(std::move(V)), Locations(std::move(L)) {}
235 
236  BasicBlock *BB;
237  BasicBlock *Pred;
238  ValVector Values;
239  LocationVector Locations;
240 };
241 
242 /// This assigns and keeps a per-bb relative ordering of load/store
243 /// instructions in the block that directly load or store an alloca.
244 ///
245 /// This functionality is important because it avoids scanning large basic
246 /// blocks multiple times when promoting many allocas in the same block.
247 class LargeBlockInfo {
248  /// For each instruction that we track, keep the index of the
249  /// instruction.
250  ///
251  /// The index starts out as the number of the instruction from the start of
252  /// the block.
254 
255 public:
256 
257  /// This code only looks at accesses to allocas.
258  static bool isInterestingInstruction(const Instruction *I) {
259  return (isa<LoadInst>(I) && isa<AllocaInst>(I->getOperand(0))) ||
260  (isa<StoreInst>(I) && isa<AllocaInst>(I->getOperand(1)));
261  }
262 
263  /// Get or calculate the index of the specified instruction.
264  unsigned getInstructionIndex(const Instruction *I) {
265  assert(isInterestingInstruction(I) &&
266  "Not a load/store to/from an alloca?");
267 
268  // If we already have this instruction number, return it.
270  if (It != InstNumbers.end())
271  return It->second;
272 
273  // Scan the whole block to get the instruction. This accumulates
274  // information for every interesting instruction in the block, in order to
275  // avoid gratuitus rescans.
276  const BasicBlock *BB = I->getParent();
277  unsigned InstNo = 0;
278  for (const Instruction &BBI : *BB)
279  if (isInterestingInstruction(&BBI))
280  InstNumbers[&BBI] = InstNo++;
281  It = InstNumbers.find(I);
282 
283  assert(It != InstNumbers.end() && "Didn't insert instruction?");
284  return It->second;
285  }
286 
287  void deleteValue(const Instruction *I) { InstNumbers.erase(I); }
288 
289  void clear() { InstNumbers.clear(); }
290 };
291 
292 struct PromoteMem2Reg {
293  /// The alloca instructions being promoted.
294  std::vector<AllocaInst *> Allocas;
295 
296  DominatorTree &DT;
297  DIBuilder DIB;
298 
299  /// A cache of @llvm.assume intrinsics used by SimplifyInstruction.
300  AssumptionCache *AC;
301 
302  const SimplifyQuery SQ;
303 
304  /// Reverse mapping of Allocas.
306 
307  /// The PhiNodes we're adding.
308  ///
309  /// That map is used to simplify some Phi nodes as we iterate over it, so
310  /// it should have deterministic iterators. We could use a MapVector, but
311  /// since we already maintain a map from BasicBlock* to a stable numbering
312  /// (BBNumbers), the DenseMap is more efficient (also supports removal).
314 
315  /// For each PHI node, keep track of which entry in Allocas it corresponds
316  /// to.
317  DenseMap<PHINode *, unsigned> PhiToAllocaMap;
318 
319  /// For each alloca, we keep track of the dbg.declare intrinsic that
320  /// describes it, if any, so that we can convert it to a dbg.value
321  /// intrinsic if the alloca gets promoted.
323 
324  /// For each alloca, keep an instance of a helper class that gives us an easy
325  /// way to update assignment tracking debug info if the alloca is promoted.
327 
328  /// The set of basic blocks the renamer has already visited.
330 
331  /// Contains a stable numbering of basic blocks to avoid non-determinstic
332  /// behavior.
334 
335  /// Lazily compute the number of predecessors a block has.
337 
338 public:
339  PromoteMem2Reg(ArrayRef<AllocaInst *> Allocas, DominatorTree &DT,
340  AssumptionCache *AC)
341  : Allocas(Allocas.begin(), Allocas.end()), DT(DT),
342  DIB(*DT.getRoot()->getParent()->getParent(), /*AllowUnresolved*/ false),
343  AC(AC), SQ(DT.getRoot()->getParent()->getParent()->getDataLayout(),
344  nullptr, &DT, AC) {}
345 
346  void run();
347 
348 private:
349  void RemoveFromAllocasList(unsigned &AllocaIdx) {
350  Allocas[AllocaIdx] = Allocas.back();
351  Allocas.pop_back();
352  --AllocaIdx;
353  }
354 
355  unsigned getNumPreds(const BasicBlock *BB) {
356  unsigned &NP = BBNumPreds[BB];
357  if (NP == 0)
358  NP = pred_size(BB) + 1;
359  return NP - 1;
360  }
361 
362  void ComputeLiveInBlocks(AllocaInst *AI, AllocaInfo &Info,
363  const SmallPtrSetImpl<BasicBlock *> &DefBlocks,
364  SmallPtrSetImpl<BasicBlock *> &LiveInBlocks);
365  void RenamePass(BasicBlock *BB, BasicBlock *Pred,
366  RenamePassData::ValVector &IncVals,
367  RenamePassData::LocationVector &IncLocs,
368  std::vector<RenamePassData> &Worklist);
369  bool QueuePhiNode(BasicBlock *BB, unsigned AllocaIdx, unsigned &Version);
370 };
371 
372 } // end anonymous namespace
373 
374 /// Given a LoadInst LI this adds assume(LI != null) after it.
376  Function *AssumeIntrinsic =
377  Intrinsic::getDeclaration(LI->getModule(), Intrinsic::assume);
378  ICmpInst *LoadNotNull = new ICmpInst(ICmpInst::ICMP_NE, LI,
380  LoadNotNull->insertAfter(LI);
381  CallInst *CI = CallInst::Create(AssumeIntrinsic, {LoadNotNull});
382  CI->insertAfter(LoadNotNull);
383  AC->registerAssumption(cast<AssumeInst>(CI));
384 }
385 
387  // Knowing that this alloca is promotable, we know that it's safe to kill all
388  // instructions except for load and store.
389 
390  for (Use &U : llvm::make_early_inc_range(AI->uses())) {
391  Instruction *I = cast<Instruction>(U.getUser());
392  if (isa<LoadInst>(I) || isa<StoreInst>(I))
393  continue;
394 
395  // Drop the use of AI in droppable instructions.
396  if (I->isDroppable()) {
397  I->dropDroppableUse(U);
398  continue;
399  }
400 
401  if (!I->getType()->isVoidTy()) {
402  // The only users of this bitcast/GEP instruction are lifetime intrinsics.
403  // Follow the use/def chain to erase them now instead of leaving it for
404  // dead code elimination later.
405  for (Use &UU : llvm::make_early_inc_range(I->uses())) {
406  Instruction *Inst = cast<Instruction>(UU.getUser());
407 
408  // Drop the use of I in droppable instructions.
409  if (Inst->isDroppable()) {
410  Inst->dropDroppableUse(UU);
411  continue;
412  }
413  Inst->eraseFromParent();
414  }
415  }
416  I->eraseFromParent();
417  }
418 }
419 
420 /// Rewrite as many loads as possible given a single store.
421 ///
422 /// When there is only a single store, we can use the domtree to trivially
423 /// replace all of the dominated loads with the stored value. Do so, and return
424 /// true if this has successfully promoted the alloca entirely. If this returns
425 /// false there were some loads which were not dominated by the single store
426 /// and thus must be phi-ed with undef. We fall back to the standard alloca
427 /// promotion algorithm in that case.
428 static bool rewriteSingleStoreAlloca(AllocaInst *AI, AllocaInfo &Info,
429  LargeBlockInfo &LBI, const DataLayout &DL,
430  DominatorTree &DT, AssumptionCache *AC) {
431  StoreInst *OnlyStore = Info.OnlyStore;
432  bool StoringGlobalVal = !isa<Instruction>(OnlyStore->getOperand(0));
433  BasicBlock *StoreBB = OnlyStore->getParent();
434  int StoreIndex = -1;
435 
436  // Clear out UsingBlocks. We will reconstruct it here if needed.
437  Info.UsingBlocks.clear();
438 
439  for (User *U : make_early_inc_range(AI->users())) {
440  Instruction *UserInst = cast<Instruction>(U);
441  if (UserInst == OnlyStore)
442  continue;
443  LoadInst *LI = cast<LoadInst>(UserInst);
444 
445  // Okay, if we have a load from the alloca, we want to replace it with the
446  // only value stored to the alloca. We can do this if the value is
447  // dominated by the store. If not, we use the rest of the mem2reg machinery
448  // to insert the phi nodes as needed.
449  if (!StoringGlobalVal) { // Non-instructions are always dominated.
450  if (LI->getParent() == StoreBB) {
451  // If we have a use that is in the same block as the store, compare the
452  // indices of the two instructions to see which one came first. If the
453  // load came before the store, we can't handle it.
454  if (StoreIndex == -1)
455  StoreIndex = LBI.getInstructionIndex(OnlyStore);
456 
457  if (unsigned(StoreIndex) > LBI.getInstructionIndex(LI)) {
458  // Can't handle this load, bail out.
459  Info.UsingBlocks.push_back(StoreBB);
460  continue;
461  }
462  } else if (!DT.dominates(StoreBB, LI->getParent())) {
463  // If the load and store are in different blocks, use BB dominance to
464  // check their relationships. If the store doesn't dom the use, bail
465  // out.
466  Info.UsingBlocks.push_back(LI->getParent());
467  continue;
468  }
469  }
470 
471  // Otherwise, we *can* safely rewrite this load.
472  Value *ReplVal = OnlyStore->getOperand(0);
473  // If the replacement value is the load, this must occur in unreachable
474  // code.
475  if (ReplVal == LI)
476  ReplVal = PoisonValue::get(LI->getType());
477 
478  // If the load was marked as nonnull we don't want to lose
479  // that information when we erase this Load. So we preserve
480  // it with an assume.
481  if (AC && LI->getMetadata(LLVMContext::MD_nonnull) &&
482  !isKnownNonZero(ReplVal, DL, 0, AC, LI, &DT))
483  addAssumeNonNull(AC, LI);
484 
485  LI->replaceAllUsesWith(ReplVal);
486  LI->eraseFromParent();
487  LBI.deleteValue(LI);
488  }
489 
490  // Finally, after the scan, check to see if the store is all that is left.
491  if (!Info.UsingBlocks.empty())
492  return false; // If not, we'll have to fall back for the remainder.
493 
494  DIBuilder DIB(*AI->getModule(), /*AllowUnresolved*/ false);
495  // Update assignment tracking info for the store we're going to delete.
496  Info.AssignmentTracking.updateForDeletedStore(Info.OnlyStore, DIB);
497 
498  // Record debuginfo for the store and remove the declaration's
499  // debuginfo.
500  for (DbgVariableIntrinsic *DII : Info.DbgUsers) {
501  if (DII->isAddressOfVariable()) {
502  ConvertDebugDeclareToDebugValue(DII, Info.OnlyStore, DIB);
503  DII->eraseFromParent();
504  } else if (DII->getExpression()->startsWithDeref()) {
505  DII->eraseFromParent();
506  }
507  }
508 
509  // Remove dbg.assigns linked to the alloca as these are now redundant.
511 
512  // Remove the (now dead) store and alloca.
513  Info.OnlyStore->eraseFromParent();
514  LBI.deleteValue(Info.OnlyStore);
515 
516  AI->eraseFromParent();
517  return true;
518 }
519 
520 /// Many allocas are only used within a single basic block. If this is the
521 /// case, avoid traversing the CFG and inserting a lot of potentially useless
522 /// PHI nodes by just performing a single linear pass over the basic block
523 /// using the Alloca.
524 ///
525 /// If we cannot promote this alloca (because it is read before it is written),
526 /// return false. This is necessary in cases where, due to control flow, the
527 /// alloca is undefined only on some control flow paths. e.g. code like
528 /// this is correct in LLVM IR:
529 /// // A is an alloca with no stores so far
530 /// for (...) {
531 /// int t = *A;
532 /// if (!first_iteration)
533 /// use(t);
534 /// *A = 42;
535 /// }
536 static bool promoteSingleBlockAlloca(AllocaInst *AI, const AllocaInfo &Info,
537  LargeBlockInfo &LBI,
538  const DataLayout &DL,
539  DominatorTree &DT,
540  AssumptionCache *AC) {
541  // The trickiest case to handle is when we have large blocks. Because of this,
542  // this code is optimized assuming that large blocks happen. This does not
543  // significantly pessimize the small block case. This uses LargeBlockInfo to
544  // make it efficient to get the index of various operations in the block.
545 
546  // Walk the use-def list of the alloca, getting the locations of all stores.
547  using StoresByIndexTy = SmallVector<std::pair<unsigned, StoreInst *>, 64>;
548  StoresByIndexTy StoresByIndex;
549 
550  for (User *U : AI->users())
551  if (StoreInst *SI = dyn_cast<StoreInst>(U))
552  StoresByIndex.push_back(std::make_pair(LBI.getInstructionIndex(SI), SI));
553 
554  // Sort the stores by their index, making it efficient to do a lookup with a
555  // binary search.
556  llvm::sort(StoresByIndex, less_first());
557 
558  // Walk all of the loads from this alloca, replacing them with the nearest
559  // store above them, if any.
560  for (User *U : make_early_inc_range(AI->users())) {
561  LoadInst *LI = dyn_cast<LoadInst>(U);
562  if (!LI)
563  continue;
564 
565  unsigned LoadIdx = LBI.getInstructionIndex(LI);
566 
567  // Find the nearest store that has a lower index than this load.
568  StoresByIndexTy::iterator I = llvm::lower_bound(
569  StoresByIndex,
570  std::make_pair(LoadIdx, static_cast<StoreInst *>(nullptr)),
571  less_first());
572  Value *ReplVal;
573  if (I == StoresByIndex.begin()) {
574  if (StoresByIndex.empty())
575  // If there are no stores, the load takes the undef value.
576  ReplVal = UndefValue::get(LI->getType());
577  else
578  // There is no store before this load, bail out (load may be affected
579  // by the following stores - see main comment).
580  return false;
581  } else {
582  // Otherwise, there was a store before this load, the load takes its
583  // value.
584  ReplVal = std::prev(I)->second->getOperand(0);
585  }
586 
587  // Note, if the load was marked as nonnull we don't want to lose that
588  // information when we erase it. So we preserve it with an assume.
589  if (AC && LI->getMetadata(LLVMContext::MD_nonnull) &&
590  !isKnownNonZero(ReplVal, DL, 0, AC, LI, &DT))
591  addAssumeNonNull(AC, LI);
592 
593  // If the replacement value is the load, this must occur in unreachable
594  // code.
595  if (ReplVal == LI)
596  ReplVal = PoisonValue::get(LI->getType());
597 
598  LI->replaceAllUsesWith(ReplVal);
599  LI->eraseFromParent();
600  LBI.deleteValue(LI);
601  }
602 
603  // Remove the (now dead) stores and alloca.
604  DIBuilder DIB(*AI->getModule(), /*AllowUnresolved*/ false);
605  while (!AI->use_empty()) {
606  StoreInst *SI = cast<StoreInst>(AI->user_back());
607  // Update assignment tracking info for the store we're going to delete.
608  Info.AssignmentTracking.updateForDeletedStore(SI, DIB);
609  // Record debuginfo for the store before removing it.
610  for (DbgVariableIntrinsic *DII : Info.DbgUsers) {
611  if (DII->isAddressOfVariable()) {
613  }
614  }
615  SI->eraseFromParent();
616  LBI.deleteValue(SI);
617  }
618 
619  // Remove dbg.assigns linked to the alloca as these are now redundant.
621  AI->eraseFromParent();
622 
623  // The alloca's debuginfo can be removed as well.
624  for (DbgVariableIntrinsic *DII : Info.DbgUsers)
625  if (DII->isAddressOfVariable() || DII->getExpression()->startsWithDeref())
626  DII->eraseFromParent();
627 
628  ++NumLocalPromoted;
629  return true;
630 }
631 
632 void PromoteMem2Reg::run() {
633  Function &F = *DT.getRoot()->getParent();
634 
635  AllocaDbgUsers.resize(Allocas.size());
636  AllocaATInfo.resize(Allocas.size());
637 
638  AllocaInfo Info;
639  LargeBlockInfo LBI;
640  ForwardIDFCalculator IDF(DT);
641 
642  for (unsigned AllocaNum = 0; AllocaNum != Allocas.size(); ++AllocaNum) {
643  AllocaInst *AI = Allocas[AllocaNum];
644 
645  assert(isAllocaPromotable(AI) && "Cannot promote non-promotable alloca!");
646  assert(AI->getParent()->getParent() == &F &&
647  "All allocas should be in the same function, which is same as DF!");
648 
650 
651  if (AI->use_empty()) {
652  // If there are no uses of the alloca, just delete it now.
653  AI->eraseFromParent();
654 
655  // Remove the alloca from the Allocas list, since it has been processed
656  RemoveFromAllocasList(AllocaNum);
657  ++NumDeadAlloca;
658  continue;
659  }
660 
661  // Calculate the set of read and write-locations for each alloca. This is
662  // analogous to finding the 'uses' and 'definitions' of each variable.
663  Info.AnalyzeAlloca(AI);
664 
665  // If there is only a single store to this value, replace any loads of
666  // it that are directly dominated by the definition with the value stored.
667  if (Info.DefiningBlocks.size() == 1) {
668  if (rewriteSingleStoreAlloca(AI, Info, LBI, SQ.DL, DT, AC)) {
669  // The alloca has been processed, move on.
670  RemoveFromAllocasList(AllocaNum);
671  ++NumSingleStore;
672  continue;
673  }
674  }
675 
676  // If the alloca is only read and written in one basic block, just perform a
677  // linear sweep over the block to eliminate it.
678  if (Info.OnlyUsedInOneBlock &&
679  promoteSingleBlockAlloca(AI, Info, LBI, SQ.DL, DT, AC)) {
680  // The alloca has been processed, move on.
681  RemoveFromAllocasList(AllocaNum);
682  continue;
683  }
684 
685  // If we haven't computed a numbering for the BB's in the function, do so
686  // now.
687  if (BBNumbers.empty()) {
688  unsigned ID = 0;
689  for (auto &BB : F)
690  BBNumbers[&BB] = ID++;
691  }
692 
693  // Remember the dbg.declare intrinsic describing this alloca, if any.
694  if (!Info.DbgUsers.empty())
695  AllocaDbgUsers[AllocaNum] = Info.DbgUsers;
696  if (!Info.AssignmentTracking.empty())
697  AllocaATInfo[AllocaNum] = Info.AssignmentTracking;
698 
699  // Keep the reverse mapping of the 'Allocas' array for the rename pass.
700  AllocaLookup[Allocas[AllocaNum]] = AllocaNum;
701 
702  // Unique the set of defining blocks for efficient lookup.
703  SmallPtrSet<BasicBlock *, 32> DefBlocks(Info.DefiningBlocks.begin(),
704  Info.DefiningBlocks.end());
705 
706  // Determine which blocks the value is live in. These are blocks which lead
707  // to uses.
708  SmallPtrSet<BasicBlock *, 32> LiveInBlocks;
709  ComputeLiveInBlocks(AI, Info, DefBlocks, LiveInBlocks);
710 
711  // At this point, we're committed to promoting the alloca using IDF's, and
712  // the standard SSA construction algorithm. Determine which blocks need phi
713  // nodes and see if we can optimize out some work by avoiding insertion of
714  // dead phi nodes.
715  IDF.setLiveInBlocks(LiveInBlocks);
716  IDF.setDefiningBlocks(DefBlocks);
718  IDF.calculate(PHIBlocks);
719  llvm::sort(PHIBlocks, [this](BasicBlock *A, BasicBlock *B) {
720  return BBNumbers.find(A)->second < BBNumbers.find(B)->second;
721  });
722 
723  unsigned CurrentVersion = 0;
724  for (BasicBlock *BB : PHIBlocks)
725  QueuePhiNode(BB, AllocaNum, CurrentVersion);
726  }
727 
728  if (Allocas.empty())
729  return; // All of the allocas must have been trivial!
730 
731  LBI.clear();
732 
733  // Set the incoming values for the basic block to be null values for all of
734  // the alloca's. We do this in case there is a load of a value that has not
735  // been stored yet. In this case, it will get this null value.
736  RenamePassData::ValVector Values(Allocas.size());
737  for (unsigned i = 0, e = Allocas.size(); i != e; ++i)
738  Values[i] = UndefValue::get(Allocas[i]->getAllocatedType());
739 
740  // When handling debug info, treat all incoming values as if they have unknown
741  // locations until proven otherwise.
742  RenamePassData::LocationVector Locations(Allocas.size());
743 
744  // Walks all basic blocks in the function performing the SSA rename algorithm
745  // and inserting the phi nodes we marked as necessary
746  std::vector<RenamePassData> RenamePassWorkList;
747  RenamePassWorkList.emplace_back(&F.front(), nullptr, std::move(Values),
748  std::move(Locations));
749  do {
750  RenamePassData RPD = std::move(RenamePassWorkList.back());
751  RenamePassWorkList.pop_back();
752  // RenamePass may add new worklist entries.
753  RenamePass(RPD.BB, RPD.Pred, RPD.Values, RPD.Locations, RenamePassWorkList);
754  } while (!RenamePassWorkList.empty());
755 
756  // The renamer uses the Visited set to avoid infinite loops. Clear it now.
757  Visited.clear();
758 
759  // Remove the allocas themselves from the function.
760  for (Instruction *A : Allocas) {
761  // Remove dbg.assigns linked to the alloca as these are now redundant.
763  // If there are any uses of the alloca instructions left, they must be in
764  // unreachable basic blocks that were not processed by walking the dominator
765  // tree. Just delete the users now.
766  if (!A->use_empty())
767  A->replaceAllUsesWith(PoisonValue::get(A->getType()));
768  A->eraseFromParent();
769  }
770 
771  // Remove alloca's dbg.declare intrinsics from the function.
772  for (auto &DbgUsers : AllocaDbgUsers) {
773  for (auto *DII : DbgUsers)
774  if (DII->isAddressOfVariable() || DII->getExpression()->startsWithDeref())
775  DII->eraseFromParent();
776  }
777 
778  // Loop over all of the PHI nodes and see if there are any that we can get
779  // rid of because they merge all of the same incoming values. This can
780  // happen due to undef values coming into the PHI nodes. This process is
781  // iterative, because eliminating one PHI node can cause others to be removed.
782  bool EliminatedAPHI = true;
783  while (EliminatedAPHI) {
784  EliminatedAPHI = false;
785 
786  // Iterating over NewPhiNodes is deterministic, so it is safe to try to
787  // simplify and RAUW them as we go. If it was not, we could add uses to
788  // the values we replace with in a non-deterministic order, thus creating
789  // non-deterministic def->use chains.
790  for (DenseMap<std::pair<unsigned, unsigned>, PHINode *>::iterator
791  I = NewPhiNodes.begin(),
792  E = NewPhiNodes.end();
793  I != E;) {
794  PHINode *PN = I->second;
795 
796  // If this PHI node merges one value and/or undefs, get the value.
797  if (Value *V = simplifyInstruction(PN, SQ)) {
798  PN->replaceAllUsesWith(V);
799  PN->eraseFromParent();
800  NewPhiNodes.erase(I++);
801  EliminatedAPHI = true;
802  continue;
803  }
804  ++I;
805  }
806  }
807 
808  // At this point, the renamer has added entries to PHI nodes for all reachable
809  // code. Unfortunately, there may be unreachable blocks which the renamer
810  // hasn't traversed. If this is the case, the PHI nodes may not
811  // have incoming values for all predecessors. Loop over all PHI nodes we have
812  // created, inserting undef values if they are missing any incoming values.
813  for (DenseMap<std::pair<unsigned, unsigned>, PHINode *>::iterator
814  I = NewPhiNodes.begin(),
815  E = NewPhiNodes.end();
816  I != E; ++I) {
817  // We want to do this once per basic block. As such, only process a block
818  // when we find the PHI that is the first entry in the block.
819  PHINode *SomePHI = I->second;
820  BasicBlock *BB = SomePHI->getParent();
821  if (&BB->front() != SomePHI)
822  continue;
823 
824  // Only do work here if there the PHI nodes are missing incoming values. We
825  // know that all PHI nodes that were inserted in a block will have the same
826  // number of incoming values, so we can just check any of them.
827  if (SomePHI->getNumIncomingValues() == getNumPreds(BB))
828  continue;
829 
830  // Get the preds for BB.
832 
833  // Ok, now we know that all of the PHI nodes are missing entries for some
834  // basic blocks. Start by sorting the incoming predecessors for efficient
835  // access.
836  auto CompareBBNumbers = [this](BasicBlock *A, BasicBlock *B) {
837  return BBNumbers.find(A)->second < BBNumbers.find(B)->second;
838  };
839  llvm::sort(Preds, CompareBBNumbers);
840 
841  // Now we loop through all BB's which have entries in SomePHI and remove
842  // them from the Preds list.
843  for (unsigned i = 0, e = SomePHI->getNumIncomingValues(); i != e; ++i) {
844  // Do a log(n) search of the Preds list for the entry we want.
846  Preds, SomePHI->getIncomingBlock(i), CompareBBNumbers);
847  assert(EntIt != Preds.end() && *EntIt == SomePHI->getIncomingBlock(i) &&
848  "PHI node has entry for a block which is not a predecessor!");
849 
850  // Remove the entry
851  Preds.erase(EntIt);
852  }
853 
854  // At this point, the blocks left in the preds list must have dummy
855  // entries inserted into every PHI nodes for the block. Update all the phi
856  // nodes in this block that we are inserting (there could be phis before
857  // mem2reg runs).
858  unsigned NumBadPreds = SomePHI->getNumIncomingValues();
859  BasicBlock::iterator BBI = BB->begin();
860  while ((SomePHI = dyn_cast<PHINode>(BBI++)) &&
861  SomePHI->getNumIncomingValues() == NumBadPreds) {
862  Value *UndefVal = UndefValue::get(SomePHI->getType());
863  for (BasicBlock *Pred : Preds)
864  SomePHI->addIncoming(UndefVal, Pred);
865  }
866  }
867 
868  NewPhiNodes.clear();
869 }
870 
871 /// Determine which blocks the value is live in.
872 ///
873 /// These are blocks which lead to uses. Knowing this allows us to avoid
874 /// inserting PHI nodes into blocks which don't lead to uses (thus, the
875 /// inserted phi nodes would be dead).
877  AllocaInst *AI, AllocaInfo &Info,
878  const SmallPtrSetImpl<BasicBlock *> &DefBlocks,
879  SmallPtrSetImpl<BasicBlock *> &LiveInBlocks) {
880  // To determine liveness, we must iterate through the predecessors of blocks
881  // where the def is live. Blocks are added to the worklist if we need to
882  // check their predecessors. Start with all the using blocks.
883  SmallVector<BasicBlock *, 64> LiveInBlockWorklist(Info.UsingBlocks.begin(),
884  Info.UsingBlocks.end());
885 
886  // If any of the using blocks is also a definition block, check to see if the
887  // definition occurs before or after the use. If it happens before the use,
888  // the value isn't really live-in.
889  for (unsigned i = 0, e = LiveInBlockWorklist.size(); i != e; ++i) {
890  BasicBlock *BB = LiveInBlockWorklist[i];
891  if (!DefBlocks.count(BB))
892  continue;
893 
894  // Okay, this is a block that both uses and defines the value. If the first
895  // reference to the alloca is a def (store), then we know it isn't live-in.
896  for (BasicBlock::iterator I = BB->begin();; ++I) {
897  if (StoreInst *SI = dyn_cast<StoreInst>(I)) {
898  if (SI->getOperand(1) != AI)
899  continue;
900 
901  // We found a store to the alloca before a load. The alloca is not
902  // actually live-in here.
903  LiveInBlockWorklist[i] = LiveInBlockWorklist.back();
904  LiveInBlockWorklist.pop_back();
905  --i;
906  --e;
907  break;
908  }
909 
910  if (LoadInst *LI = dyn_cast<LoadInst>(I))
911  // Okay, we found a load before a store to the alloca. It is actually
912  // live into this block.
913  if (LI->getOperand(0) == AI)
914  break;
915  }
916  }
917 
918  // Now that we have a set of blocks where the phi is live-in, recursively add
919  // their predecessors until we find the full region the value is live.
920  while (!LiveInBlockWorklist.empty()) {
921  BasicBlock *BB = LiveInBlockWorklist.pop_back_val();
922 
923  // The block really is live in here, insert it into the set. If already in
924  // the set, then it has already been processed.
925  if (!LiveInBlocks.insert(BB).second)
926  continue;
927 
928  // Since the value is live into BB, it is either defined in a predecessor or
929  // live into it to. Add the preds to the worklist unless they are a
930  // defining block.
931  for (BasicBlock *P : predecessors(BB)) {
932  // The value is not live into a predecessor if it defines the value.
933  if (DefBlocks.count(P))
934  continue;
935 
936  // Otherwise it is, add to the worklist.
937  LiveInBlockWorklist.push_back(P);
938  }
939  }
940 }
941 
942 /// Queue a phi-node to be added to a basic-block for a specific Alloca.
943 ///
944 /// Returns true if there wasn't already a phi-node for that variable
945 bool PromoteMem2Reg::QueuePhiNode(BasicBlock *BB, unsigned AllocaNo,
946  unsigned &Version) {
947  // Look up the basic-block in question.
948  PHINode *&PN = NewPhiNodes[std::make_pair(BBNumbers[BB], AllocaNo)];
949 
950  // If the BB already has a phi node added for the i'th alloca then we're done!
951  if (PN)
952  return false;
953 
954  // Create a PhiNode using the dereferenced type... and add the phi-node to the
955  // BasicBlock.
956  PN = PHINode::Create(Allocas[AllocaNo]->getAllocatedType(), getNumPreds(BB),
957  Allocas[AllocaNo]->getName() + "." + Twine(Version++),
958  &BB->front());
959  ++NumPHIInsert;
960  PhiToAllocaMap[PN] = AllocaNo;
961  return true;
962 }
963 
964 /// Update the debug location of a phi. \p ApplyMergedLoc indicates whether to
965 /// create a merged location incorporating \p DL, or to set \p DL directly.
967  bool ApplyMergedLoc) {
968  if (ApplyMergedLoc)
969  PN->applyMergedLocation(PN->getDebugLoc(), DL);
970  else
971  PN->setDebugLoc(DL);
972 }
973 
974 /// Recursively traverse the CFG of the function, renaming loads and
975 /// stores to the allocas which we are promoting.
976 ///
977 /// IncomingVals indicates what value each Alloca contains on exit from the
978 /// predecessor block Pred.
979 void PromoteMem2Reg::RenamePass(BasicBlock *BB, BasicBlock *Pred,
980  RenamePassData::ValVector &IncomingVals,
981  RenamePassData::LocationVector &IncomingLocs,
982  std::vector<RenamePassData> &Worklist) {
983 NextIteration:
984  // If we are inserting any phi nodes into this BB, they will already be in the
985  // block.
986  if (PHINode *APN = dyn_cast<PHINode>(BB->begin())) {
987  // If we have PHI nodes to update, compute the number of edges from Pred to
988  // BB.
989  if (PhiToAllocaMap.count(APN)) {
990  // We want to be able to distinguish between PHI nodes being inserted by
991  // this invocation of mem2reg from those phi nodes that already existed in
992  // the IR before mem2reg was run. We determine that APN is being inserted
993  // because it is missing incoming edges. All other PHI nodes being
994  // inserted by this pass of mem2reg will have the same number of incoming
995  // operands so far. Remember this count.
996  unsigned NewPHINumOperands = APN->getNumOperands();
997 
998  unsigned NumEdges = llvm::count(successors(Pred), BB);
999  assert(NumEdges && "Must be at least one edge from Pred to BB!");
1000 
1001  // Add entries for all the phis.
1002  BasicBlock::iterator PNI = BB->begin();
1003  do {
1004  unsigned AllocaNo = PhiToAllocaMap[APN];
1005 
1006  // Update the location of the phi node.
1007  updateForIncomingValueLocation(APN, IncomingLocs[AllocaNo],
1008  APN->getNumIncomingValues() > 0);
1009 
1010  // Add N incoming values to the PHI node.
1011  for (unsigned i = 0; i != NumEdges; ++i)
1012  APN->addIncoming(IncomingVals[AllocaNo], Pred);
1013 
1014  // The currently active variable for this block is now the PHI.
1015  IncomingVals[AllocaNo] = APN;
1016  AllocaATInfo[AllocaNo].updateForNewPhi(APN, DIB);
1017  for (DbgVariableIntrinsic *DII : AllocaDbgUsers[AllocaNo])
1018  if (DII->isAddressOfVariable())
1019  ConvertDebugDeclareToDebugValue(DII, APN, DIB);
1020 
1021  // Get the next phi node.
1022  ++PNI;
1023  APN = dyn_cast<PHINode>(PNI);
1024  if (!APN)
1025  break;
1026 
1027  // Verify that it is missing entries. If not, it is not being inserted
1028  // by this mem2reg invocation so we want to ignore it.
1029  } while (APN->getNumOperands() == NewPHINumOperands);
1030  }
1031  }
1032 
1033  // Don't revisit blocks.
1034  if (!Visited.insert(BB).second)
1035  return;
1036 
1037  for (BasicBlock::iterator II = BB->begin(); !II->isTerminator();) {
1038  Instruction *I = &*II++; // get the instruction, increment iterator
1039 
1040  if (LoadInst *LI = dyn_cast<LoadInst>(I)) {
1041  AllocaInst *Src = dyn_cast<AllocaInst>(LI->getPointerOperand());
1042  if (!Src)
1043  continue;
1044 
1045  DenseMap<AllocaInst *, unsigned>::iterator AI = AllocaLookup.find(Src);
1046  if (AI == AllocaLookup.end())
1047  continue;
1048 
1049  Value *V = IncomingVals[AI->second];
1050 
1051  // If the load was marked as nonnull we don't want to lose
1052  // that information when we erase this Load. So we preserve
1053  // it with an assume.
1054  if (AC && LI->getMetadata(LLVMContext::MD_nonnull) &&
1055  !isKnownNonZero(V, SQ.DL, 0, AC, LI, &DT))
1056  addAssumeNonNull(AC, LI);
1057 
1058  // Anything using the load now uses the current value.
1059  LI->replaceAllUsesWith(V);
1060  LI->eraseFromParent();
1061  } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) {
1062  // Delete this instruction and mark the name as the current holder of the
1063  // value
1064  AllocaInst *Dest = dyn_cast<AllocaInst>(SI->getPointerOperand());
1065  if (!Dest)
1066  continue;
1067 
1068  DenseMap<AllocaInst *, unsigned>::iterator ai = AllocaLookup.find(Dest);
1069  if (ai == AllocaLookup.end())
1070  continue;
1071 
1072  // what value were we writing?
1073  unsigned AllocaNo = ai->second;
1074  IncomingVals[AllocaNo] = SI->getOperand(0);
1075 
1076  // Record debuginfo for the store before removing it.
1077  IncomingLocs[AllocaNo] = SI->getDebugLoc();
1078  AllocaATInfo[AllocaNo].updateForDeletedStore(SI, DIB);
1079  for (DbgVariableIntrinsic *DII : AllocaDbgUsers[ai->second])
1080  if (DII->isAddressOfVariable())
1082  SI->eraseFromParent();
1083  }
1084  }
1085 
1086  // 'Recurse' to our successors.
1088  if (I == E)
1089  return;
1090 
1091  // Keep track of the successors so we don't visit the same successor twice
1092  SmallPtrSet<BasicBlock *, 8> VisitedSuccs;
1093 
1094  // Handle the first successor without using the worklist.
1095  VisitedSuccs.insert(*I);
1096  Pred = BB;
1097  BB = *I;
1098  ++I;
1099 
1100  for (; I != E; ++I)
1101  if (VisitedSuccs.insert(*I).second)
1102  Worklist.emplace_back(*I, Pred, IncomingVals, IncomingLocs);
1103 
1104  goto NextIteration;
1105 }
1106 
1108  AssumptionCache *AC) {
1109  // If there is nothing to do, bail out...
1110  if (Allocas.empty())
1111  return;
1112 
1113  PromoteMem2Reg(Allocas, DT, AC).run();
1114 }
llvm::SuccIterator
Definition: CFG.h:138
i
i
Definition: README.txt:29
llvm::DbgVariableIntrinsic::getExpression
DIExpression * getExpression() const
Definition: IntrinsicInst.h:292
AssumptionCache.h
getName
static StringRef getName(Value *V)
Definition: ProvenanceAnalysisEvaluator.cpp:20
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
llvm::ConvertDebugDeclareToDebugValue
void ConvertDebugDeclareToDebugValue(DbgVariableIntrinsic *DII, StoreInst *SI, DIBuilder &Builder)
===------------------------------------------------------------------—===// Dbg Intrinsic utilities
Definition: Local.cpp:1501
llvm::Instruction::getModule
const Module * getModule() const
Return the module owning the function this instruction belongs to or nullptr it the function does not...
Definition: Instruction.cpp:69
llvm::Value::dropDroppableUse
static void dropDroppableUse(Use &U)
Remove the droppable use U.
Definition: Value.cpp:216
llvm::AssumptionCache::registerAssumption
void registerAssumption(AssumeInst *CI)
Add an @llvm.assume intrinsic to this function's cache.
Definition: AssumptionCache.cpp:224
llvm::DataLayout
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:113
llvm::BasicBlock::iterator
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:87
llvm::BasicBlock::getParent
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:104
IntrinsicInst.h
llvm::SimplifyQuery
Definition: InstructionSimplify.h:93
llvm::DIBuilder
Definition: DIBuilder.h:42
llvm::succ_end
Interval::succ_iterator succ_end(Interval *I)
Definition: Interval.h:102
llvm::Function
Definition: Function.h:60
llvm::lower_bound
auto lower_bound(R &&Range, T &&Value)
Provide wrappers to std::lower_bound which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1922
P
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper which DAGCombine can t really do The code for turning x load into a single vector load is target independent and should be moved to the dag combiner The code for turning x load into a vector load can only handle a direct load from a global or a direct load from the stack It should be generalized to handle any load from P
Definition: README-SSE.txt:411
llvm::at::deleteAssignmentMarkers
void deleteAssignmentMarkers(const Instruction *Inst)
Delete the llvm.dbg.assign intrinsics linked to Inst.
Definition: DebugInfo.cpp:1707
llvm::BitCastInst
This class represents a no-op cast from one type to another.
Definition: Instructions.h:5253
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1199
Statistic.h
llvm::pred_size
unsigned pred_size(MachineBasicBlock *BB)
Definition: MachineSSAContext.h:32
llvm::CmpInst::ICMP_NE
@ ICMP_NE
not equal
Definition: InstrTypes.h:742
llvm::findDbgUsers
void findDbgUsers(SmallVectorImpl< DbgVariableIntrinsic * > &DbgInsts, Value *V)
Finds the debug info intrinsics describing a value.
Definition: DebugInfo.cpp:112
ValueTracking.h
Local.h
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:166
llvm::DenseMapBase::erase
bool erase(const KeyT &Val)
Definition: DenseMap.h:302
llvm::isKnownNonZero
bool isKnownNonZero(const Value *V, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)
Return true if the given value is known to be non-zero when defined.
Definition: ValueTracking.cpp:315
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::begin
iterator begin()
Definition: DenseMap.h:75
DenseMap.h
Module.h
llvm::sys::path::end
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:235
llvm::sys::path::begin
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
Definition: Path.cpp:226
llvm::SmallSet
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Definition: SmallSet.h:136
llvm::logicalview::LVWarningKind::Locations
@ Locations
llvm::DenseMapBase::count
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
Definition: DenseMap.h:145
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:450
llvm::PromoteMemToReg
void PromoteMemToReg(ArrayRef< AllocaInst * > Allocas, DominatorTree &DT, AssumptionCache *AC=nullptr)
Promote the specified list of alloca instructions into scalar registers, inserting PHI nodes as appro...
Definition: PromoteMemoryToRegister.cpp:1107
llvm::successors
auto successors(MachineBasicBlock *BB)
Definition: MachineSSAContext.h:29
STLExtras.h
ComputeLiveInBlocks
static void ComputeLiveInBlocks(const SmallPtrSetImpl< BasicBlock * > &UsingBlocks, const SmallPtrSetImpl< BasicBlock * > &DefBlocks, SmallPtrSetImpl< BasicBlock * > &LiveInBlocks, PredIteratorCache &PredCache)
Given sets of UsingBlocks and DefBlocks, compute the set of LiveInBlocks.
Definition: SSAUpdaterBulk.cpp:86
llvm::LoadInst::getPointerOperand
Value * getPointerOperand()
Definition: Instructions.h:261
llvm::ArrayRef::empty
bool empty() const
empty - Check if the array is empty.
Definition: ArrayRef.h:159
llvm::at::getAssignmentMarkers
AssignmentMarkerRange getAssignmentMarkers(DIAssignID *ID)
Return a range of dbg.assign intrinsics which use \ID as an operand.
Definition: DebugInfo.cpp:1693
F
#define F(x, y, z)
Definition: MD5.cpp:55
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:55
clear
static void clear(coro::Shape &Shape)
Definition: Coroutines.cpp:149
llvm::DominatorTree::dominates
bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
Definition: Dominators.cpp:122
Instruction.h
llvm::Instruction::insertAfter
void insertAfter(Instruction *InsertPos)
Insert an unlinked instruction into a basic block immediately after the specified instruction.
Definition: Instruction.cpp:93
llvm::coverage::CurrentVersion
@ CurrentVersion
Definition: CoverageMapping.h:1010
llvm::AddrSpaceCastInst
This class represents a conversion between pointers from one address space to another.
Definition: Instructions.h:5293
Constants.h
llvm::AllocaInst::getAllocatedType
Type * getAllocatedType() const
Return the type that is being allocated by the instruction.
Definition: Instructions.h:115
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::User
Definition: User.h:44
llvm::DbgVariableIntrinsic::isAddressOfVariable
bool isAddressOfVariable() const
Does this describe the address of a local variable.
Definition: IntrinsicInst.h:265
llvm::less_first
Function object to check whether the first component of a std::pair compares less than the first comp...
Definition: STLExtras.h:1476
Intrinsics.h
llvm::ARM_PROC::A
@ A
Definition: ARMBaseInfo.h:34
Twine.h
InstrTypes.h
llvm::CallInst::Create
static CallInst * Create(FunctionType *Ty, Value *F, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
Definition: Instructions.h:1517
SI
@ SI
Definition: SIInstrInfo.cpp:7966
llvm::Instruction::applyMergedLocation
void applyMergedLocation(const DILocation *LocA, const DILocation *LocB)
Merge 2 debug locations and apply it to the Instruction.
Definition: DebugInfo.cpp:839
llvm::Value::uses
iterator_range< use_iterator > uses()
Definition: Value.h:376
llvm::SimplifyQuery::DL
const DataLayout & DL
Definition: InstructionSimplify.h:94
false
Definition: StackSlotColoring.cpp:141
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
llvm::Instruction
Definition: Instruction.h:42
llvm::STATISTIC
STATISTIC(NumFunctions, "Total number of functions")
llvm::predecessors
auto predecessors(MachineBasicBlock *BB)
Definition: MachineSSAContext.h:30
addAssumeNonNull
static void addAssumeNonNull(AssumptionCache *AC, LoadInst *LI)
Given a LoadInst LI this adds assume(LI != null) after it.
Definition: PromoteMemoryToRegister.cpp:375
llvm::SmallVectorImpl::resize
void resize(size_type N)
Definition: SmallVector.h:642
updateForIncomingValueLocation
static void updateForIncomingValueLocation(PHINode *PN, DebugLoc DL, bool ApplyMergedLoc)
Update the debug location of a phi.
Definition: PromoteMemoryToRegister.cpp:966
llvm::UndefValue::get
static UndefValue * get(Type *T)
Static factory methods - Return an 'undef' object of the specified type.
Definition: Constants.cpp:1713
llvm::IndexedInstrProf::Version
const uint64_t Version
Definition: InstrProf.h:1056
SmallPtrSet.h
Info
Analysis containing CSE Info
Definition: CSEInfo.cpp:27
llvm::PHINode::getNumIncomingValues
unsigned getNumIncomingValues() const
Return the number of incoming edges.
Definition: Instructions.h:2789
llvm::Value::use_empty
bool use_empty() const
Definition: Value.h:344
llvm::CallingConv::ID
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
Type.h
llvm::Instruction::getMetadata
MDNode * getMetadata(unsigned KindID) const
Get the metadata of given kind attached to this Instruction.
Definition: Instruction.h:276
CFG.h
llvm::onlyUsedByLifetimeMarkersOrDroppableInsts
bool onlyUsedByLifetimeMarkersOrDroppableInsts(const Value *V)
Return true if the only users of this pointer are lifetime markers or droppable instructions.
Definition: ValueTracking.cpp:4715
llvm::dxil::PointerTypeAnalysis::run
PointerTypeMap run(const Module &M)
Compute the PointerTypeMap for the module M.
Definition: PointerTypeAnalysis.cpp:189
llvm::DominatorTreeBase::getRoot
NodeT * getRoot() const
Definition: GenericDomTree.h:461
llvm::sort
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1682
BasicBlock.h
llvm::DbgVariableIntrinsic
This is the common base class for debug info intrinsics for variables.
Definition: IntrinsicInst.h:181
llvm::StoreInst
An instruction for storing to memory.
Definition: Instructions.h:298
promoteSingleBlockAlloca
static bool promoteSingleBlockAlloca(AllocaInst *AI, const AllocaInfo &Info, LargeBlockInfo &LBI, const DataLayout &DL, DominatorTree &DT, AssumptionCache *AC)
Many allocas are only used within a single basic block.
Definition: PromoteMemoryToRegister.cpp:536
llvm::Instruction::eraseFromParent
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Definition: Instruction.cpp:81
llvm::DenseMapBase::clear
void clear()
Definition: DenseMap.h:110
llvm::ICmpInst
This instruction compares its operands according to the predicate given to the constructor.
Definition: Instructions.h:1186
llvm::count
auto count(R &&Range, const E &Element)
Wrapper function around std::count to count the number of times an element Element occurs in the give...
Definition: STLExtras.h:1895
llvm::Instruction::user_back
Instruction * user_back()
Specialize the methods defined in Value, as we know that an instruction can only be used by other ins...
Definition: Instruction.h:88
llvm::PHINode::addIncoming
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
Definition: Instructions.h:2847
move
compiles ldr LCPI1_0 ldr ldr mov lsr tst moveq r1 ldr LCPI1_1 and r0 bx lr It would be better to do something like to fold the shift into the conditional move
Definition: README.txt:546
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:53
PromoteMemToReg.h
llvm::DenseMap< const Instruction *, unsigned >
DebugInfo.h
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::succ_begin
Interval::succ_iterator succ_begin(Interval *I)
succ_begin/succ_end - define methods so that Intervals may be used just like BasicBlocks can with the...
Definition: Interval.h:99
llvm::GetElementPtrInst
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
Definition: Instructions.h:929
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:447
llvm::make_early_inc_range
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
Definition: STLExtras.h:716
llvm::DebugVariable
Identifies a unique instance of a variable.
Definition: DebugInfoMetadata.h:3659
DIBuilder.h
llvm::simplifyInstruction
Value * simplifyInstruction(Instruction *I, const SimplifyQuery &Q, OptimizationRemarkEmitter *ORE=nullptr)
See if we can compute a simplified version of this instruction.
Definition: InstructionSimplify.cpp:6600
ArrayRef.h
llvm::Instruction::setDebugLoc
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
Definition: Instruction.h:356
llvm::DenseMapBase::find
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:150
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::move
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1861
llvm::IDFCalculator
Definition: IteratedDominanceFrontier.h:39
llvm::DenseMapBase::empty
bool empty() const
Definition: DenseMap.h:98
llvm::SmallPtrSetImpl::count
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:383
llvm::User::isDroppable
bool isDroppable() const
A droppable user is a user for which uses can be dropped without affecting correctness and should be ...
Definition: User.cpp:115
llvm::SmallPtrSetImplBase::clear
void clear()
Definition: SmallPtrSet.h:95
llvm::ArrayRef
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: APInt.h:32
llvm::AssumptionCache
A cache of @llvm.assume calls within a function.
Definition: AssumptionCache.h:42
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
llvm::Value::replaceAllUsesWith
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:532
getParent
static const Function * getParent(const Value *V)
Definition: BasicAliasAnalysis.cpp:805
DL
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Definition: AArch64SLSHardening.cpp:76
llvm::DbgAssignIntrinsic
This represents the llvm.dbg.assign instruction.
Definition: IntrinsicInst.h:412
llvm::LoadInst
An instruction for reading from memory.
Definition: Instructions.h:174
llvm::Intrinsic::getDeclaration
Function * getDeclaration(Module *M, ID id, ArrayRef< Type * > Tys=std::nullopt)
Create or insert an LLVM Function declaration for an intrinsic, and return it.
Definition: Function.cpp:1481
llvm::onlyUsedByLifetimeMarkers
bool onlyUsedByLifetimeMarkers(const Value *V)
Return true if the only users of this pointer are lifetime markers.
Definition: ValueTracking.cpp:4711
Constant.h
llvm::Twine
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:81
std
Definition: BitVector.h:851
llvm::Constant::getNullValue
static Constant * getNullValue(Type *Ty)
Constructor to create a '0' constant of arbitrary type.
Definition: Constants.cpp:350
llvm::copy_if
OutputIt copy_if(R &&Range, OutputIt Out, UnaryPredicate P)
Provide wrappers to std::copy_if which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1780
llvm::DenseMapBase::end
iterator end()
Definition: DenseMap.h:84
llvm::PHINode::Create
static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...
Definition: Instructions.h:2739
Casting.h
llvm::DIExpression::startsWithDeref
bool startsWithDeref() const
Return whether the first element a DW_OP_deref.
Definition: DebugInfoMetadata.cpp:1252
Function.h
llvm::SmallVectorImpl::clear
void clear()
Definition: SmallVector.h:614
llvm::SmallSet::insert
std::pair< const_iterator, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
Definition: SmallSet.h:178
llvm::IntrinsicInst
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:47
IteratedDominanceFrontier.h
rewriteSingleStoreAlloca
static bool rewriteSingleStoreAlloca(AllocaInst *AI, AllocaInfo &Info, LargeBlockInfo &LBI, const DataLayout &DL, DominatorTree &DT, AssumptionCache *AC)
Rewrite as many loads as possible given a single store.
Definition: PromoteMemoryToRegister.cpp:428
Instructions.h
SmallVector.h
llvm::Instruction::getDebugLoc
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
Definition: Instruction.h:359
User.h
Dominators.h
llvm::Instruction::getParent
const BasicBlock * getParent() const
Definition: Instruction.h:91
InstructionSimplify.h
llvm::PHINode::getIncomingBlock
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
Definition: Instructions.h:2813
removeIntrinsicUsers
static void removeIntrinsicUsers(AllocaInst *AI)
Definition: PromoteMemoryToRegister.cpp:386
llvm::PHINode
Definition: Instructions.h:2697
llvm::SmallVectorImpl
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:42
llvm::SmallPtrSetImpl
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:344
llvm::CallInst
This class represents a function call, abstracting a target machine's calling convention.
Definition: Instructions.h:1474
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
LLVMContext.h
llvm::DebugLoc
A debug info location.
Definition: DebugLoc.h:33
llvm::AllocaInst
an instruction to allocate memory on the stack
Definition: Instructions.h:59
llvm::User::getOperand
Value * getOperand(unsigned i) const
Definition: User.h:169
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
llvm::Value::users
iterator_range< user_iterator > users()
Definition: Value.h:421
llvm::isAllocaPromotable
bool isAllocaPromotable(const AllocaInst *AI)
Return true if this alloca is legal for promotion.
Definition: PromoteMemoryToRegister.cpp:63
llvm::SmallSet::contains
bool contains(const T &V) const
Check if the SmallSet contains the given element.
Definition: SmallSet.h:235
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
llvm::SmallPtrSetImpl::insert
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:365
llvm::PoisonValue::get
static PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
Definition: Constants.cpp:1732