LLVM  14.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/TinyPtrVector.h"
24 #include "llvm/ADT/Twine.h"
30 #include "llvm/IR/BasicBlock.h"
31 #include "llvm/IR/CFG.h"
32 #include "llvm/IR/Constant.h"
33 #include "llvm/IR/Constants.h"
34 #include "llvm/IR/DIBuilder.h"
35 #include "llvm/IR/DerivedTypes.h"
36 #include "llvm/IR/Dominators.h"
37 #include "llvm/IR/Function.h"
38 #include "llvm/IR/InstrTypes.h"
39 #include "llvm/IR/Instruction.h"
40 #include "llvm/IR/Instructions.h"
41 #include "llvm/IR/IntrinsicInst.h"
42 #include "llvm/IR/Intrinsics.h"
43 #include "llvm/IR/LLVMContext.h"
44 #include "llvm/IR/Module.h"
45 #include "llvm/IR/Type.h"
46 #include "llvm/IR/User.h"
47 #include "llvm/Support/Casting.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 
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>(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())
71  return false;
72  } else if (const StoreInst *SI = dyn_cast<StoreInst>(U)) {
73  if (SI->getOperand(0) == AI)
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 struct AllocaInfo {
104  using DbgUserVec = SmallVector<DbgVariableIntrinsic *, 1>;
105 
106  SmallVector<BasicBlock *, 32> DefiningBlocks;
107  SmallVector<BasicBlock *, 32> UsingBlocks;
108 
109  StoreInst *OnlyStore;
110  BasicBlock *OnlyBlock;
111  bool OnlyUsedInOneBlock;
112 
113  DbgUserVec DbgUsers;
114 
115  void clear() {
116  DefiningBlocks.clear();
117  UsingBlocks.clear();
118  OnlyStore = nullptr;
119  OnlyBlock = nullptr;
120  OnlyUsedInOneBlock = true;
121  DbgUsers.clear();
122  }
123 
124  /// Scan the uses of the specified alloca, filling in the AllocaInfo used
125  /// by the rest of the pass to reason about the uses of this alloca.
126  void AnalyzeAlloca(AllocaInst *AI) {
127  clear();
128 
129  // As we scan the uses of the alloca instruction, keep track of stores,
130  // and decide whether all of the loads and stores to the alloca are within
131  // the same basic block.
132  for (User *U : AI->users()) {
133  Instruction *User = cast<Instruction>(U);
134 
135  if (StoreInst *SI = dyn_cast<StoreInst>(User)) {
136  // Remember the basic blocks which define new values for the alloca
137  DefiningBlocks.push_back(SI->getParent());
138  OnlyStore = SI;
139  } else {
140  LoadInst *LI = cast<LoadInst>(User);
141  // Otherwise it must be a load instruction, keep track of variable
142  // reads.
143  UsingBlocks.push_back(LI->getParent());
144  }
145 
146  if (OnlyUsedInOneBlock) {
147  if (!OnlyBlock)
148  OnlyBlock = User->getParent();
149  else if (OnlyBlock != User->getParent())
150  OnlyUsedInOneBlock = false;
151  }
152  }
153 
154  findDbgUsers(DbgUsers, AI);
155  }
156 };
157 
158 /// Data package used by RenamePass().
159 struct RenamePassData {
160  using ValVector = std::vector<Value *>;
161  using LocationVector = std::vector<DebugLoc>;
162 
163  RenamePassData(BasicBlock *B, BasicBlock *P, ValVector V, LocationVector L)
164  : BB(B), Pred(P), Values(std::move(V)), Locations(std::move(L)) {}
165 
166  BasicBlock *BB;
167  BasicBlock *Pred;
168  ValVector Values;
169  LocationVector Locations;
170 };
171 
172 /// This assigns and keeps a per-bb relative ordering of load/store
173 /// instructions in the block that directly load or store an alloca.
174 ///
175 /// This functionality is important because it avoids scanning large basic
176 /// blocks multiple times when promoting many allocas in the same block.
177 class LargeBlockInfo {
178  /// For each instruction that we track, keep the index of the
179  /// instruction.
180  ///
181  /// The index starts out as the number of the instruction from the start of
182  /// the block.
184 
185 public:
186 
187  /// This code only looks at accesses to allocas.
188  static bool isInterestingInstruction(const Instruction *I) {
189  return (isa<LoadInst>(I) && isa<AllocaInst>(I->getOperand(0))) ||
190  (isa<StoreInst>(I) && isa<AllocaInst>(I->getOperand(1)));
191  }
192 
193  /// Get or calculate the index of the specified instruction.
194  unsigned getInstructionIndex(const Instruction *I) {
195  assert(isInterestingInstruction(I) &&
196  "Not a load/store to/from an alloca?");
197 
198  // If we already have this instruction number, return it.
200  if (It != InstNumbers.end())
201  return It->second;
202 
203  // Scan the whole block to get the instruction. This accumulates
204  // information for every interesting instruction in the block, in order to
205  // avoid gratuitus rescans.
206  const BasicBlock *BB = I->getParent();
207  unsigned InstNo = 0;
208  for (const Instruction &BBI : *BB)
209  if (isInterestingInstruction(&BBI))
210  InstNumbers[&BBI] = InstNo++;
211  It = InstNumbers.find(I);
212 
213  assert(It != InstNumbers.end() && "Didn't insert instruction?");
214  return It->second;
215  }
216 
217  void deleteValue(const Instruction *I) { InstNumbers.erase(I); }
218 
219  void clear() { InstNumbers.clear(); }
220 };
221 
222 struct PromoteMem2Reg {
223  /// The alloca instructions being promoted.
224  std::vector<AllocaInst *> Allocas;
225 
226  DominatorTree &DT;
227  DIBuilder DIB;
228 
229  /// A cache of @llvm.assume intrinsics used by SimplifyInstruction.
230  AssumptionCache *AC;
231 
232  const SimplifyQuery SQ;
233 
234  /// Reverse mapping of Allocas.
236 
237  /// The PhiNodes we're adding.
238  ///
239  /// That map is used to simplify some Phi nodes as we iterate over it, so
240  /// it should have deterministic iterators. We could use a MapVector, but
241  /// since we already maintain a map from BasicBlock* to a stable numbering
242  /// (BBNumbers), the DenseMap is more efficient (also supports removal).
244 
245  /// For each PHI node, keep track of which entry in Allocas it corresponds
246  /// to.
247  DenseMap<PHINode *, unsigned> PhiToAllocaMap;
248 
249  /// For each alloca, we keep track of the dbg.declare intrinsic that
250  /// describes it, if any, so that we can convert it to a dbg.value
251  /// intrinsic if the alloca gets promoted.
253 
254  /// The set of basic blocks the renamer has already visited.
256 
257  /// Contains a stable numbering of basic blocks to avoid non-determinstic
258  /// behavior.
260 
261  /// Lazily compute the number of predecessors a block has.
263 
264 public:
265  PromoteMem2Reg(ArrayRef<AllocaInst *> Allocas, DominatorTree &DT,
266  AssumptionCache *AC)
267  : Allocas(Allocas.begin(), Allocas.end()), DT(DT),
268  DIB(*DT.getRoot()->getParent()->getParent(), /*AllowUnresolved*/ false),
269  AC(AC), SQ(DT.getRoot()->getParent()->getParent()->getDataLayout(),
270  nullptr, &DT, AC) {}
271 
272  void run();
273 
274 private:
275  void RemoveFromAllocasList(unsigned &AllocaIdx) {
276  Allocas[AllocaIdx] = Allocas.back();
277  Allocas.pop_back();
278  --AllocaIdx;
279  }
280 
281  unsigned getNumPreds(const BasicBlock *BB) {
282  unsigned &NP = BBNumPreds[BB];
283  if (NP == 0)
284  NP = pred_size(BB) + 1;
285  return NP - 1;
286  }
287 
288  void ComputeLiveInBlocks(AllocaInst *AI, AllocaInfo &Info,
289  const SmallPtrSetImpl<BasicBlock *> &DefBlocks,
290  SmallPtrSetImpl<BasicBlock *> &LiveInBlocks);
291  void RenamePass(BasicBlock *BB, BasicBlock *Pred,
292  RenamePassData::ValVector &IncVals,
293  RenamePassData::LocationVector &IncLocs,
294  std::vector<RenamePassData> &Worklist);
295  bool QueuePhiNode(BasicBlock *BB, unsigned AllocaIdx, unsigned &Version);
296 };
297 
298 } // end anonymous namespace
299 
300 /// Given a LoadInst LI this adds assume(LI != null) after it.
302  Function *AssumeIntrinsic =
303  Intrinsic::getDeclaration(LI->getModule(), Intrinsic::assume);
304  ICmpInst *LoadNotNull = new ICmpInst(ICmpInst::ICMP_NE, LI,
306  LoadNotNull->insertAfter(LI);
307  CallInst *CI = CallInst::Create(AssumeIntrinsic, {LoadNotNull});
308  CI->insertAfter(LoadNotNull);
309  AC->registerAssumption(cast<AssumeInst>(CI));
310 }
311 
313  // Knowing that this alloca is promotable, we know that it's safe to kill all
314  // instructions except for load and store.
315 
316  for (Use &U : llvm::make_early_inc_range(AI->uses())) {
317  Instruction *I = cast<Instruction>(U.getUser());
318  if (isa<LoadInst>(I) || isa<StoreInst>(I))
319  continue;
320 
321  // Drop the use of AI in droppable instructions.
322  if (I->isDroppable()) {
323  I->dropDroppableUse(U);
324  continue;
325  }
326 
327  if (!I->getType()->isVoidTy()) {
328  // The only users of this bitcast/GEP instruction are lifetime intrinsics.
329  // Follow the use/def chain to erase them now instead of leaving it for
330  // dead code elimination later.
331  for (Use &UU : llvm::make_early_inc_range(I->uses())) {
332  Instruction *Inst = cast<Instruction>(UU.getUser());
333 
334  // Drop the use of I in droppable instructions.
335  if (Inst->isDroppable()) {
336  Inst->dropDroppableUse(UU);
337  continue;
338  }
339  Inst->eraseFromParent();
340  }
341  }
342  I->eraseFromParent();
343  }
344 }
345 
346 /// Rewrite as many loads as possible given a single store.
347 ///
348 /// When there is only a single store, we can use the domtree to trivially
349 /// replace all of the dominated loads with the stored value. Do so, and return
350 /// true if this has successfully promoted the alloca entirely. If this returns
351 /// false there were some loads which were not dominated by the single store
352 /// and thus must be phi-ed with undef. We fall back to the standard alloca
353 /// promotion algorithm in that case.
354 static bool rewriteSingleStoreAlloca(AllocaInst *AI, AllocaInfo &Info,
355  LargeBlockInfo &LBI, const DataLayout &DL,
356  DominatorTree &DT, AssumptionCache *AC) {
357  StoreInst *OnlyStore = Info.OnlyStore;
358  bool StoringGlobalVal = !isa<Instruction>(OnlyStore->getOperand(0));
359  BasicBlock *StoreBB = OnlyStore->getParent();
360  int StoreIndex = -1;
361 
362  // Clear out UsingBlocks. We will reconstruct it here if needed.
363  Info.UsingBlocks.clear();
364 
365  for (User *U : make_early_inc_range(AI->users())) {
366  Instruction *UserInst = cast<Instruction>(U);
367  if (UserInst == OnlyStore)
368  continue;
369  LoadInst *LI = cast<LoadInst>(UserInst);
370 
371  // Okay, if we have a load from the alloca, we want to replace it with the
372  // only value stored to the alloca. We can do this if the value is
373  // dominated by the store. If not, we use the rest of the mem2reg machinery
374  // to insert the phi nodes as needed.
375  if (!StoringGlobalVal) { // Non-instructions are always dominated.
376  if (LI->getParent() == StoreBB) {
377  // If we have a use that is in the same block as the store, compare the
378  // indices of the two instructions to see which one came first. If the
379  // load came before the store, we can't handle it.
380  if (StoreIndex == -1)
381  StoreIndex = LBI.getInstructionIndex(OnlyStore);
382 
383  if (unsigned(StoreIndex) > LBI.getInstructionIndex(LI)) {
384  // Can't handle this load, bail out.
385  Info.UsingBlocks.push_back(StoreBB);
386  continue;
387  }
388  } else if (!DT.dominates(StoreBB, LI->getParent())) {
389  // If the load and store are in different blocks, use BB dominance to
390  // check their relationships. If the store doesn't dom the use, bail
391  // out.
392  Info.UsingBlocks.push_back(LI->getParent());
393  continue;
394  }
395  }
396 
397  // Otherwise, we *can* safely rewrite this load.
398  Value *ReplVal = OnlyStore->getOperand(0);
399  // If the replacement value is the load, this must occur in unreachable
400  // code.
401  if (ReplVal == LI)
402  ReplVal = PoisonValue::get(LI->getType());
403 
404  // If the load was marked as nonnull we don't want to lose
405  // that information when we erase this Load. So we preserve
406  // it with an assume.
407  if (AC && LI->getMetadata(LLVMContext::MD_nonnull) &&
408  !isKnownNonZero(ReplVal, DL, 0, AC, LI, &DT))
409  addAssumeNonNull(AC, LI);
410 
411  LI->replaceAllUsesWith(ReplVal);
412  LI->eraseFromParent();
413  LBI.deleteValue(LI);
414  }
415 
416  // Finally, after the scan, check to see if the store is all that is left.
417  if (!Info.UsingBlocks.empty())
418  return false; // If not, we'll have to fall back for the remainder.
419 
420  // Record debuginfo for the store and remove the declaration's
421  // debuginfo.
422  for (DbgVariableIntrinsic *DII : Info.DbgUsers) {
423  if (DII->isAddressOfVariable()) {
424  DIBuilder DIB(*AI->getModule(), /*AllowUnresolved*/ false);
425  ConvertDebugDeclareToDebugValue(DII, Info.OnlyStore, DIB);
426  DII->eraseFromParent();
427  } else if (DII->getExpression()->startsWithDeref()) {
428  DII->eraseFromParent();
429  }
430  }
431  // Remove the (now dead) store and alloca.
432  Info.OnlyStore->eraseFromParent();
433  LBI.deleteValue(Info.OnlyStore);
434 
435  AI->eraseFromParent();
436  return true;
437 }
438 
439 /// Many allocas are only used within a single basic block. If this is the
440 /// case, avoid traversing the CFG and inserting a lot of potentially useless
441 /// PHI nodes by just performing a single linear pass over the basic block
442 /// using the Alloca.
443 ///
444 /// If we cannot promote this alloca (because it is read before it is written),
445 /// return false. This is necessary in cases where, due to control flow, the
446 /// alloca is undefined only on some control flow paths. e.g. code like
447 /// this is correct in LLVM IR:
448 /// // A is an alloca with no stores so far
449 /// for (...) {
450 /// int t = *A;
451 /// if (!first_iteration)
452 /// use(t);
453 /// *A = 42;
454 /// }
455 static bool promoteSingleBlockAlloca(AllocaInst *AI, const AllocaInfo &Info,
456  LargeBlockInfo &LBI,
457  const DataLayout &DL,
458  DominatorTree &DT,
459  AssumptionCache *AC) {
460  // The trickiest case to handle is when we have large blocks. Because of this,
461  // this code is optimized assuming that large blocks happen. This does not
462  // significantly pessimize the small block case. This uses LargeBlockInfo to
463  // make it efficient to get the index of various operations in the block.
464 
465  // Walk the use-def list of the alloca, getting the locations of all stores.
466  using StoresByIndexTy = SmallVector<std::pair<unsigned, StoreInst *>, 64>;
467  StoresByIndexTy StoresByIndex;
468 
469  for (User *U : AI->users())
470  if (StoreInst *SI = dyn_cast<StoreInst>(U))
471  StoresByIndex.push_back(std::make_pair(LBI.getInstructionIndex(SI), SI));
472 
473  // Sort the stores by their index, making it efficient to do a lookup with a
474  // binary search.
475  llvm::sort(StoresByIndex, less_first());
476 
477  // Walk all of the loads from this alloca, replacing them with the nearest
478  // store above them, if any.
479  for (User *U : make_early_inc_range(AI->users())) {
480  LoadInst *LI = dyn_cast<LoadInst>(U);
481  if (!LI)
482  continue;
483 
484  unsigned LoadIdx = LBI.getInstructionIndex(LI);
485 
486  // Find the nearest store that has a lower index than this load.
487  StoresByIndexTy::iterator I = llvm::lower_bound(
488  StoresByIndex,
489  std::make_pair(LoadIdx, static_cast<StoreInst *>(nullptr)),
490  less_first());
491  if (I == StoresByIndex.begin()) {
492  if (StoresByIndex.empty())
493  // If there are no stores, the load takes the undef value.
495  else
496  // There is no store before this load, bail out (load may be affected
497  // by the following stores - see main comment).
498  return false;
499  } else {
500  // Otherwise, there was a store before this load, the load takes its value.
501  // Note, if the load was marked as nonnull we don't want to lose that
502  // information when we erase it. So we preserve it with an assume.
503  Value *ReplVal = std::prev(I)->second->getOperand(0);
504  if (AC && LI->getMetadata(LLVMContext::MD_nonnull) &&
505  !isKnownNonZero(ReplVal, DL, 0, AC, LI, &DT))
506  addAssumeNonNull(AC, LI);
507 
508  // If the replacement value is the load, this must occur in unreachable
509  // code.
510  if (ReplVal == LI)
511  ReplVal = PoisonValue::get(LI->getType());
512 
513  LI->replaceAllUsesWith(ReplVal);
514  }
515 
516  LI->eraseFromParent();
517  LBI.deleteValue(LI);
518  }
519 
520  // Remove the (now dead) stores and alloca.
521  while (!AI->use_empty()) {
522  StoreInst *SI = cast<StoreInst>(AI->user_back());
523  // Record debuginfo for the store before removing it.
524  for (DbgVariableIntrinsic *DII : Info.DbgUsers) {
525  if (DII->isAddressOfVariable()) {
526  DIBuilder DIB(*AI->getModule(), /*AllowUnresolved*/ false);
528  }
529  }
530  SI->eraseFromParent();
531  LBI.deleteValue(SI);
532  }
533 
534  AI->eraseFromParent();
535 
536  // The alloca's debuginfo can be removed as well.
537  for (DbgVariableIntrinsic *DII : Info.DbgUsers)
538  if (DII->isAddressOfVariable() || DII->getExpression()->startsWithDeref())
539  DII->eraseFromParent();
540 
541  ++NumLocalPromoted;
542  return true;
543 }
544 
545 void PromoteMem2Reg::run() {
546  Function &F = *DT.getRoot()->getParent();
547 
548  AllocaDbgUsers.resize(Allocas.size());
549 
550  AllocaInfo Info;
551  LargeBlockInfo LBI;
552  ForwardIDFCalculator IDF(DT);
553 
554  for (unsigned AllocaNum = 0; AllocaNum != Allocas.size(); ++AllocaNum) {
555  AllocaInst *AI = Allocas[AllocaNum];
556 
557  assert(isAllocaPromotable(AI) && "Cannot promote non-promotable alloca!");
558  assert(AI->getParent()->getParent() == &F &&
559  "All allocas should be in the same function, which is same as DF!");
560 
562 
563  if (AI->use_empty()) {
564  // If there are no uses of the alloca, just delete it now.
565  AI->eraseFromParent();
566 
567  // Remove the alloca from the Allocas list, since it has been processed
568  RemoveFromAllocasList(AllocaNum);
569  ++NumDeadAlloca;
570  continue;
571  }
572 
573  // Calculate the set of read and write-locations for each alloca. This is
574  // analogous to finding the 'uses' and 'definitions' of each variable.
575  Info.AnalyzeAlloca(AI);
576 
577  // If there is only a single store to this value, replace any loads of
578  // it that are directly dominated by the definition with the value stored.
579  if (Info.DefiningBlocks.size() == 1) {
580  if (rewriteSingleStoreAlloca(AI, Info, LBI, SQ.DL, DT, AC)) {
581  // The alloca has been processed, move on.
582  RemoveFromAllocasList(AllocaNum);
583  ++NumSingleStore;
584  continue;
585  }
586  }
587 
588  // If the alloca is only read and written in one basic block, just perform a
589  // linear sweep over the block to eliminate it.
590  if (Info.OnlyUsedInOneBlock &&
591  promoteSingleBlockAlloca(AI, Info, LBI, SQ.DL, DT, AC)) {
592  // The alloca has been processed, move on.
593  RemoveFromAllocasList(AllocaNum);
594  continue;
595  }
596 
597  // If we haven't computed a numbering for the BB's in the function, do so
598  // now.
599  if (BBNumbers.empty()) {
600  unsigned ID = 0;
601  for (auto &BB : F)
602  BBNumbers[&BB] = ID++;
603  }
604 
605  // Remember the dbg.declare intrinsic describing this alloca, if any.
606  if (!Info.DbgUsers.empty())
607  AllocaDbgUsers[AllocaNum] = Info.DbgUsers;
608 
609  // Keep the reverse mapping of the 'Allocas' array for the rename pass.
610  AllocaLookup[Allocas[AllocaNum]] = AllocaNum;
611 
612  // Unique the set of defining blocks for efficient lookup.
613  SmallPtrSet<BasicBlock *, 32> DefBlocks(Info.DefiningBlocks.begin(),
614  Info.DefiningBlocks.end());
615 
616  // Determine which blocks the value is live in. These are blocks which lead
617  // to uses.
618  SmallPtrSet<BasicBlock *, 32> LiveInBlocks;
619  ComputeLiveInBlocks(AI, Info, DefBlocks, LiveInBlocks);
620 
621  // At this point, we're committed to promoting the alloca using IDF's, and
622  // the standard SSA construction algorithm. Determine which blocks need phi
623  // nodes and see if we can optimize out some work by avoiding insertion of
624  // dead phi nodes.
625  IDF.setLiveInBlocks(LiveInBlocks);
626  IDF.setDefiningBlocks(DefBlocks);
628  IDF.calculate(PHIBlocks);
629  llvm::sort(PHIBlocks, [this](BasicBlock *A, BasicBlock *B) {
630  return BBNumbers.find(A)->second < BBNumbers.find(B)->second;
631  });
632 
633  unsigned CurrentVersion = 0;
634  for (BasicBlock *BB : PHIBlocks)
635  QueuePhiNode(BB, AllocaNum, CurrentVersion);
636  }
637 
638  if (Allocas.empty())
639  return; // All of the allocas must have been trivial!
640 
641  LBI.clear();
642 
643  // Set the incoming values for the basic block to be null values for all of
644  // the alloca's. We do this in case there is a load of a value that has not
645  // been stored yet. In this case, it will get this null value.
646  RenamePassData::ValVector Values(Allocas.size());
647  for (unsigned i = 0, e = Allocas.size(); i != e; ++i)
648  Values[i] = UndefValue::get(Allocas[i]->getAllocatedType());
649 
650  // When handling debug info, treat all incoming values as if they have unknown
651  // locations until proven otherwise.
652  RenamePassData::LocationVector Locations(Allocas.size());
653 
654  // Walks all basic blocks in the function performing the SSA rename algorithm
655  // and inserting the phi nodes we marked as necessary
656  std::vector<RenamePassData> RenamePassWorkList;
657  RenamePassWorkList.emplace_back(&F.front(), nullptr, std::move(Values),
658  std::move(Locations));
659  do {
660  RenamePassData RPD = std::move(RenamePassWorkList.back());
661  RenamePassWorkList.pop_back();
662  // RenamePass may add new worklist entries.
663  RenamePass(RPD.BB, RPD.Pred, RPD.Values, RPD.Locations, RenamePassWorkList);
664  } while (!RenamePassWorkList.empty());
665 
666  // The renamer uses the Visited set to avoid infinite loops. Clear it now.
667  Visited.clear();
668 
669  // Remove the allocas themselves from the function.
670  for (Instruction *A : Allocas) {
671  // If there are any uses of the alloca instructions left, they must be in
672  // unreachable basic blocks that were not processed by walking the dominator
673  // tree. Just delete the users now.
674  if (!A->use_empty())
675  A->replaceAllUsesWith(PoisonValue::get(A->getType()));
676  A->eraseFromParent();
677  }
678 
679  // Remove alloca's dbg.declare instrinsics from the function.
680  for (auto &DbgUsers : AllocaDbgUsers) {
681  for (auto *DII : DbgUsers)
682  if (DII->isAddressOfVariable() || DII->getExpression()->startsWithDeref())
683  DII->eraseFromParent();
684  }
685 
686  // Loop over all of the PHI nodes and see if there are any that we can get
687  // rid of because they merge all of the same incoming values. This can
688  // happen due to undef values coming into the PHI nodes. This process is
689  // iterative, because eliminating one PHI node can cause others to be removed.
690  bool EliminatedAPHI = true;
691  while (EliminatedAPHI) {
692  EliminatedAPHI = false;
693 
694  // Iterating over NewPhiNodes is deterministic, so it is safe to try to
695  // simplify and RAUW them as we go. If it was not, we could add uses to
696  // the values we replace with in a non-deterministic order, thus creating
697  // non-deterministic def->use chains.
698  for (DenseMap<std::pair<unsigned, unsigned>, PHINode *>::iterator
699  I = NewPhiNodes.begin(),
700  E = NewPhiNodes.end();
701  I != E;) {
702  PHINode *PN = I->second;
703 
704  // If this PHI node merges one value and/or undefs, get the value.
705  if (Value *V = SimplifyInstruction(PN, SQ)) {
706  PN->replaceAllUsesWith(V);
707  PN->eraseFromParent();
708  NewPhiNodes.erase(I++);
709  EliminatedAPHI = true;
710  continue;
711  }
712  ++I;
713  }
714  }
715 
716  // At this point, the renamer has added entries to PHI nodes for all reachable
717  // code. Unfortunately, there may be unreachable blocks which the renamer
718  // hasn't traversed. If this is the case, the PHI nodes may not
719  // have incoming values for all predecessors. Loop over all PHI nodes we have
720  // created, inserting undef values if they are missing any incoming values.
721  for (DenseMap<std::pair<unsigned, unsigned>, PHINode *>::iterator
722  I = NewPhiNodes.begin(),
723  E = NewPhiNodes.end();
724  I != E; ++I) {
725  // We want to do this once per basic block. As such, only process a block
726  // when we find the PHI that is the first entry in the block.
727  PHINode *SomePHI = I->second;
728  BasicBlock *BB = SomePHI->getParent();
729  if (&BB->front() != SomePHI)
730  continue;
731 
732  // Only do work here if there the PHI nodes are missing incoming values. We
733  // know that all PHI nodes that were inserted in a block will have the same
734  // number of incoming values, so we can just check any of them.
735  if (SomePHI->getNumIncomingValues() == getNumPreds(BB))
736  continue;
737 
738  // Get the preds for BB.
740 
741  // Ok, now we know that all of the PHI nodes are missing entries for some
742  // basic blocks. Start by sorting the incoming predecessors for efficient
743  // access.
744  auto CompareBBNumbers = [this](BasicBlock *A, BasicBlock *B) {
745  return BBNumbers.find(A)->second < BBNumbers.find(B)->second;
746  };
747  llvm::sort(Preds, CompareBBNumbers);
748 
749  // Now we loop through all BB's which have entries in SomePHI and remove
750  // them from the Preds list.
751  for (unsigned i = 0, e = SomePHI->getNumIncomingValues(); i != e; ++i) {
752  // Do a log(n) search of the Preds list for the entry we want.
754  Preds, SomePHI->getIncomingBlock(i), CompareBBNumbers);
755  assert(EntIt != Preds.end() && *EntIt == SomePHI->getIncomingBlock(i) &&
756  "PHI node has entry for a block which is not a predecessor!");
757 
758  // Remove the entry
759  Preds.erase(EntIt);
760  }
761 
762  // At this point, the blocks left in the preds list must have dummy
763  // entries inserted into every PHI nodes for the block. Update all the phi
764  // nodes in this block that we are inserting (there could be phis before
765  // mem2reg runs).
766  unsigned NumBadPreds = SomePHI->getNumIncomingValues();
767  BasicBlock::iterator BBI = BB->begin();
768  while ((SomePHI = dyn_cast<PHINode>(BBI++)) &&
769  SomePHI->getNumIncomingValues() == NumBadPreds) {
770  Value *UndefVal = UndefValue::get(SomePHI->getType());
771  for (BasicBlock *Pred : Preds)
772  SomePHI->addIncoming(UndefVal, Pred);
773  }
774  }
775 
776  NewPhiNodes.clear();
777 }
778 
779 /// Determine which blocks the value is live in.
780 ///
781 /// These are blocks which lead to uses. Knowing this allows us to avoid
782 /// inserting PHI nodes into blocks which don't lead to uses (thus, the
783 /// inserted phi nodes would be dead).
785  AllocaInst *AI, AllocaInfo &Info,
786  const SmallPtrSetImpl<BasicBlock *> &DefBlocks,
787  SmallPtrSetImpl<BasicBlock *> &LiveInBlocks) {
788  // To determine liveness, we must iterate through the predecessors of blocks
789  // where the def is live. Blocks are added to the worklist if we need to
790  // check their predecessors. Start with all the using blocks.
791  SmallVector<BasicBlock *, 64> LiveInBlockWorklist(Info.UsingBlocks.begin(),
792  Info.UsingBlocks.end());
793 
794  // If any of the using blocks is also a definition block, check to see if the
795  // definition occurs before or after the use. If it happens before the use,
796  // the value isn't really live-in.
797  for (unsigned i = 0, e = LiveInBlockWorklist.size(); i != e; ++i) {
798  BasicBlock *BB = LiveInBlockWorklist[i];
799  if (!DefBlocks.count(BB))
800  continue;
801 
802  // Okay, this is a block that both uses and defines the value. If the first
803  // reference to the alloca is a def (store), then we know it isn't live-in.
804  for (BasicBlock::iterator I = BB->begin();; ++I) {
805  if (StoreInst *SI = dyn_cast<StoreInst>(I)) {
806  if (SI->getOperand(1) != AI)
807  continue;
808 
809  // We found a store to the alloca before a load. The alloca is not
810  // actually live-in here.
811  LiveInBlockWorklist[i] = LiveInBlockWorklist.back();
812  LiveInBlockWorklist.pop_back();
813  --i;
814  --e;
815  break;
816  }
817 
818  if (LoadInst *LI = dyn_cast<LoadInst>(I))
819  // Okay, we found a load before a store to the alloca. It is actually
820  // live into this block.
821  if (LI->getOperand(0) == AI)
822  break;
823  }
824  }
825 
826  // Now that we have a set of blocks where the phi is live-in, recursively add
827  // their predecessors until we find the full region the value is live.
828  while (!LiveInBlockWorklist.empty()) {
829  BasicBlock *BB = LiveInBlockWorklist.pop_back_val();
830 
831  // The block really is live in here, insert it into the set. If already in
832  // the set, then it has already been processed.
833  if (!LiveInBlocks.insert(BB).second)
834  continue;
835 
836  // Since the value is live into BB, it is either defined in a predecessor or
837  // live into it to. Add the preds to the worklist unless they are a
838  // defining block.
839  for (BasicBlock *P : predecessors(BB)) {
840  // The value is not live into a predecessor if it defines the value.
841  if (DefBlocks.count(P))
842  continue;
843 
844  // Otherwise it is, add to the worklist.
845  LiveInBlockWorklist.push_back(P);
846  }
847  }
848 }
849 
850 /// Queue a phi-node to be added to a basic-block for a specific Alloca.
851 ///
852 /// Returns true if there wasn't already a phi-node for that variable
853 bool PromoteMem2Reg::QueuePhiNode(BasicBlock *BB, unsigned AllocaNo,
854  unsigned &Version) {
855  // Look up the basic-block in question.
856  PHINode *&PN = NewPhiNodes[std::make_pair(BBNumbers[BB], AllocaNo)];
857 
858  // If the BB already has a phi node added for the i'th alloca then we're done!
859  if (PN)
860  return false;
861 
862  // Create a PhiNode using the dereferenced type... and add the phi-node to the
863  // BasicBlock.
864  PN = PHINode::Create(Allocas[AllocaNo]->getAllocatedType(), getNumPreds(BB),
865  Allocas[AllocaNo]->getName() + "." + Twine(Version++),
866  &BB->front());
867  ++NumPHIInsert;
868  PhiToAllocaMap[PN] = AllocaNo;
869  return true;
870 }
871 
872 /// Update the debug location of a phi. \p ApplyMergedLoc indicates whether to
873 /// create a merged location incorporating \p DL, or to set \p DL directly.
875  bool ApplyMergedLoc) {
876  if (ApplyMergedLoc)
877  PN->applyMergedLocation(PN->getDebugLoc(), DL);
878  else
879  PN->setDebugLoc(DL);
880 }
881 
882 /// Recursively traverse the CFG of the function, renaming loads and
883 /// stores to the allocas which we are promoting.
884 ///
885 /// IncomingVals indicates what value each Alloca contains on exit from the
886 /// predecessor block Pred.
887 void PromoteMem2Reg::RenamePass(BasicBlock *BB, BasicBlock *Pred,
888  RenamePassData::ValVector &IncomingVals,
889  RenamePassData::LocationVector &IncomingLocs,
890  std::vector<RenamePassData> &Worklist) {
891 NextIteration:
892  // If we are inserting any phi nodes into this BB, they will already be in the
893  // block.
894  if (PHINode *APN = dyn_cast<PHINode>(BB->begin())) {
895  // If we have PHI nodes to update, compute the number of edges from Pred to
896  // BB.
897  if (PhiToAllocaMap.count(APN)) {
898  // We want to be able to distinguish between PHI nodes being inserted by
899  // this invocation of mem2reg from those phi nodes that already existed in
900  // the IR before mem2reg was run. We determine that APN is being inserted
901  // because it is missing incoming edges. All other PHI nodes being
902  // inserted by this pass of mem2reg will have the same number of incoming
903  // operands so far. Remember this count.
904  unsigned NewPHINumOperands = APN->getNumOperands();
905 
906  unsigned NumEdges = llvm::count(successors(Pred), BB);
907  assert(NumEdges && "Must be at least one edge from Pred to BB!");
908 
909  // Add entries for all the phis.
910  BasicBlock::iterator PNI = BB->begin();
911  do {
912  unsigned AllocaNo = PhiToAllocaMap[APN];
913 
914  // Update the location of the phi node.
915  updateForIncomingValueLocation(APN, IncomingLocs[AllocaNo],
916  APN->getNumIncomingValues() > 0);
917 
918  // Add N incoming values to the PHI node.
919  for (unsigned i = 0; i != NumEdges; ++i)
920  APN->addIncoming(IncomingVals[AllocaNo], Pred);
921 
922  // The currently active variable for this block is now the PHI.
923  IncomingVals[AllocaNo] = APN;
924  for (DbgVariableIntrinsic *DII : AllocaDbgUsers[AllocaNo])
925  if (DII->isAddressOfVariable())
926  ConvertDebugDeclareToDebugValue(DII, APN, DIB);
927 
928  // Get the next phi node.
929  ++PNI;
930  APN = dyn_cast<PHINode>(PNI);
931  if (!APN)
932  break;
933 
934  // Verify that it is missing entries. If not, it is not being inserted
935  // by this mem2reg invocation so we want to ignore it.
936  } while (APN->getNumOperands() == NewPHINumOperands);
937  }
938  }
939 
940  // Don't revisit blocks.
941  if (!Visited.insert(BB).second)
942  return;
943 
944  for (BasicBlock::iterator II = BB->begin(); !II->isTerminator();) {
945  Instruction *I = &*II++; // get the instruction, increment iterator
946 
947  if (LoadInst *LI = dyn_cast<LoadInst>(I)) {
948  AllocaInst *Src = dyn_cast<AllocaInst>(LI->getPointerOperand());
949  if (!Src)
950  continue;
951 
952  DenseMap<AllocaInst *, unsigned>::iterator AI = AllocaLookup.find(Src);
953  if (AI == AllocaLookup.end())
954  continue;
955 
956  Value *V = IncomingVals[AI->second];
957 
958  // If the load was marked as nonnull we don't want to lose
959  // that information when we erase this Load. So we preserve
960  // it with an assume.
961  if (AC && LI->getMetadata(LLVMContext::MD_nonnull) &&
962  !isKnownNonZero(V, SQ.DL, 0, AC, LI, &DT))
963  addAssumeNonNull(AC, LI);
964 
965  // Anything using the load now uses the current value.
966  LI->replaceAllUsesWith(V);
967  BB->getInstList().erase(LI);
968  } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) {
969  // Delete this instruction and mark the name as the current holder of the
970  // value
971  AllocaInst *Dest = dyn_cast<AllocaInst>(SI->getPointerOperand());
972  if (!Dest)
973  continue;
974 
975  DenseMap<AllocaInst *, unsigned>::iterator ai = AllocaLookup.find(Dest);
976  if (ai == AllocaLookup.end())
977  continue;
978 
979  // what value were we writing?
980  unsigned AllocaNo = ai->second;
981  IncomingVals[AllocaNo] = SI->getOperand(0);
982 
983  // Record debuginfo for the store before removing it.
984  IncomingLocs[AllocaNo] = SI->getDebugLoc();
985  for (DbgVariableIntrinsic *DII : AllocaDbgUsers[ai->second])
986  if (DII->isAddressOfVariable())
988  BB->getInstList().erase(SI);
989  }
990  }
991 
992  // 'Recurse' to our successors.
994  if (I == E)
995  return;
996 
997  // Keep track of the successors so we don't visit the same successor twice
998  SmallPtrSet<BasicBlock *, 8> VisitedSuccs;
999 
1000  // Handle the first successor without using the worklist.
1001  VisitedSuccs.insert(*I);
1002  Pred = BB;
1003  BB = *I;
1004  ++I;
1005 
1006  for (; I != E; ++I)
1007  if (VisitedSuccs.insert(*I).second)
1008  Worklist.emplace_back(*I, Pred, IncomingVals, IncomingLocs);
1009 
1010  goto NextIteration;
1011 }
1012 
1014  AssumptionCache *AC) {
1015  // If there is nothing to do, bail out...
1016  if (Allocas.empty())
1017  return;
1018 
1019  PromoteMem2Reg(Allocas, DT, AC).run();
1020 }
llvm::SuccIterator
Definition: CFG.h:139
i
i
Definition: README.txt:29
llvm::DbgVariableIntrinsic::getExpression
DIExpression * getExpression() const
Definition: IntrinsicInst.h:257
AssumptionCache.h
llvm::predecessors
pred_range predecessors(BasicBlock *BB)
Definition: CFG.h:127
getName
static StringRef getName(Value *V)
Definition: ProvenanceAnalysisEvaluator.cpp:42
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
llvm::ConvertDebugDeclareToDebugValue
void ConvertDebugDeclareToDebugValue(DbgVariableIntrinsic *DII, StoreInst *SI, DIBuilder &Builder)
===------------------------------------------------------------------—===// Dbg Intrinsic utilities
Definition: Local.cpp:1441
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:66
llvm::Value::dropDroppableUse
static void dropDroppableUse(Use &U)
Remove the droppable use U.
Definition: Value.cpp:205
llvm::AssumptionCache::registerAssumption
void registerAssumption(AssumeInst *CI)
Add an @llvm.assume intrinsic to this function's cache.
Definition: AssumptionCache.cpp:217
llvm::DataLayout
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:112
llvm::Intrinsic::getDeclaration
Function * getDeclaration(Module *M, ID id, ArrayRef< Type * > Tys=None)
Create or insert an LLVM Function declaration for an intrinsic, and return it.
Definition: Function.cpp:1336
llvm::BasicBlock::iterator
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:90
llvm::BasicBlock::getParent
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:107
IntrinsicInst.h
llvm::SimplifyQuery
Definition: InstructionSimplify.h:94
llvm::DIBuilder
Definition: DIBuilder.h:41
llvm::succ_end
Interval::succ_iterator succ_end(Interval *I)
Definition: Interval.h:102
llvm::Function
Definition: Function.h:61
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:1657
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::BitCastInst
This class represents a no-op cast from one type to another.
Definition: Instructions.h:5194
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1168
Statistic.h
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:102
ValueTracking.h
Local.h
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:151
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:310
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:74
DenseMap.h
Module.h
llvm::sys::path::end
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:233
llvm::sys::path::begin
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
Definition: Path.cpp:224
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:449
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:1013
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:267
llvm::successors
succ_range successors(Instruction *I)
Definition: CFG.h:262
llvm::ArrayRef::empty
bool empty() const
empty - Check if the array is empty.
Definition: ArrayRef.h:160
F
#define F(x, y, z)
Definition: MD5.cpp:56
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
clear
static void clear(coro::Shape &Shape)
Definition: Coroutines.cpp:233
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:115
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:90
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:5234
Constants.h
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:231
llvm::less_first
Function object to check whether the first component of a std::pair compares less than the first comp...
Definition: STLExtras.h:1274
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:1518
llvm::Instruction::applyMergedLocation
void applyMergedLocation(const DILocation *LocA, const DILocation *LocB)
Merge 2 debug locations and apply it to the Instruction.
Definition: DebugInfo.cpp:815
llvm::Value::uses
iterator_range< use_iterator > uses()
Definition: Value.h:377
llvm::SimplifyQuery::DL
const DataLayout & DL
Definition: InstructionSimplify.h:95
false
Definition: StackSlotColoring.cpp:142
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
llvm::Instruction
Definition: Instruction.h:45
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:6246
llvm::STATISTIC
STATISTIC(NumFunctions, "Total number of functions")
addAssumeNonNull
static void addAssumeNonNull(AssumptionCache *AC, LoadInst *LI)
Given a LoadInst LI this adds assume(LI != null) after it.
Definition: PromoteMemoryToRegister.cpp:301
llvm::SmallVectorImpl::resize
void resize(size_type N)
Definition: SmallVector.h:606
updateForIncomingValueLocation
static void updateForIncomingValueLocation(PHINode *PN, DebugLoc DL, bool ApplyMergedLoc)
Update the debug location of a phi.
Definition: PromoteMemoryToRegister.cpp:874
llvm::UndefValue::get
static UndefValue * get(Type *T)
Static factory methods - Return an 'undef' object of the specified type.
Definition: Constants.cpp:1784
llvm::IndexedInstrProf::Version
const uint64_t Version
Definition: InstrProf.h:991
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:2719
llvm::Value::use_empty
bool use_empty() const
Definition: Value.h:345
Type.h
llvm::Instruction::getMetadata
MDNode * getMetadata(unsigned KindID) const
Get the metadata of given kind attached to this Instruction.
Definition: Instruction.h:282
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:4566
llvm::DominatorTreeBase::getRoot
NodeT * getRoot() const
Definition: GenericDomTree.h:461
BasicBlock.h
llvm::DbgVariableIntrinsic
This is the common base class for debug info intrinsics for variables.
Definition: IntrinsicInst.h:148
llvm::StoreInst
An instruction for storing to memory.
Definition: Instructions.h:304
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:455
llvm::Instruction::eraseFromParent
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Definition: Instruction.cpp:78
llvm::DenseMapBase::clear
void clear()
Definition: DenseMap.h:111
llvm::ICmpInst
This instruction compares its operands according to the predicate given to the constructor.
Definition: Instructions.h:1203
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:1630
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:91
llvm::PHINode::addIncoming
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
Definition: Instructions.h:2777
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:57
PromoteMemToReg.h
llvm::DenseMap< const Instruction *, unsigned >
I
#define I(x, y, z)
Definition: MD5.cpp:59
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:928
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:572
DIBuilder.h
ArrayRef.h
llvm::Instruction::setDebugLoc
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
Definition: Instruction.h:369
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:1605
SI
StandardInstrumentations SI(Debug, VerifyEach)
llvm::IDFCalculator
Definition: IteratedDominanceFrontier.h:39
TinyPtrVector.h
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:382
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:109
llvm::SmallPtrSetImplBase::clear
void clear()
Definition: SmallPtrSet.h:94
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:41
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:256
llvm::pred_size
unsigned pred_size(const BasicBlock *BB)
Get the number of predecessors of BB.
Definition: CFG.h:124
llvm::Value::replaceAllUsesWith
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:520
getParent
static const Function * getParent(const Value *V)
Definition: BasicAliasAnalysis.cpp:776
DL
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Definition: AArch64SLSHardening.cpp:76
llvm::LoadInst
An instruction for reading from memory.
Definition: Instructions.h:175
llvm::DenseMapBase::empty
LLVM_NODISCARD bool empty() const
Definition: DenseMap.h:97
llvm::onlyUsedByLifetimeMarkers
bool onlyUsedByLifetimeMarkers(const Value *V)
Return true if the only users of this pointer are lifetime markers.
Definition: ValueTracking.cpp:4562
Constant.h
llvm::Twine
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:83
std
Definition: BitVector.h:838
llvm::Constant::getNullValue
static Constant * getNullValue(Type *Ty)
Constructor to create a '0' constant of arbitrary type.
Definition: Constants.cpp:346
llvm::DenseMapBase::end
iterator end()
Definition: DenseMap.h:83
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:2669
Casting.h
Function.h
llvm::sort
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1488
llvm::SmallVectorImpl::clear
void clear()
Definition: SmallVector.h:585
llvm::IntrinsicInst
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:45
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:354
Instructions.h
SmallVector.h
llvm::Instruction::getDebugLoc
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
Definition: Instruction.h:372
User.h
Dominators.h
llvm::DIExpression::startsWithDeref
bool startsWithDeref() const
Return whether the first element a DW_OP_deref.
Definition: DebugInfoMetadata.h:2716
llvm::Instruction::getParent
const BasicBlock * getParent() const
Definition: Instruction.h:94
InstructionSimplify.h
llvm::PHINode::getIncomingBlock
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
Definition: Instructions.h:2743
removeIntrinsicUsers
static void removeIntrinsicUsers(AllocaInst *AI)
Definition: PromoteMemoryToRegister.cpp:312
llvm::PHINode
Definition: Instructions.h:2627
llvm::SmallVectorImpl
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:43
DerivedTypes.h
llvm::SmallPtrSetImpl
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:343
llvm::CallInst
This class represents a function call, abstracting a target machine's calling convention.
Definition: Instructions.h:1475
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:62
llvm::User::getOperand
Value * getOperand(unsigned i) const
Definition: User.h:169
llvm::Value
LLVM Value Representation.
Definition: Value.h:75
llvm::Value::users
iterator_range< user_iterator > users()
Definition: Value.h:422
llvm::isAllocaPromotable
bool isAllocaPromotable(const AllocaInst *AI)
Return true if this alloca is legal for promotion.
Definition: PromoteMemoryToRegister.cpp:64
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:44
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:364
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:38
llvm::PoisonValue::get
static PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
Definition: Constants.cpp:1803