LLVM  13.0.0git
GVNSink.cpp
Go to the documentation of this file.
1 //===- GVNSink.cpp - sink expressions into successors ---------------------===//
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 /// \file GVNSink.cpp
10 /// This pass attempts to sink instructions into successors, reducing static
11 /// instruction count and enabling if-conversion.
12 ///
13 /// We use a variant of global value numbering to decide what can be sunk.
14 /// Consider:
15 ///
16 /// [ %a1 = add i32 %b, 1 ] [ %c1 = add i32 %d, 1 ]
17 /// [ %a2 = xor i32 %a1, 1 ] [ %c2 = xor i32 %c1, 1 ]
18 /// \ /
19 /// [ %e = phi i32 %a2, %c2 ]
20 /// [ add i32 %e, 4 ]
21 ///
22 ///
23 /// GVN would number %a1 and %c1 differently because they compute different
24 /// results - the VN of an instruction is a function of its opcode and the
25 /// transitive closure of its operands. This is the key property for hoisting
26 /// and CSE.
27 ///
28 /// What we want when sinking however is for a numbering that is a function of
29 /// the *uses* of an instruction, which allows us to answer the question "if I
30 /// replace %a1 with %c1, will it contribute in an equivalent way to all
31 /// successive instructions?". The PostValueTable class in GVN provides this
32 /// mapping.
33 //
34 //===----------------------------------------------------------------------===//
35 
36 #include "llvm/ADT/ArrayRef.h"
37 #include "llvm/ADT/DenseMap.h"
38 #include "llvm/ADT/DenseMapInfo.h"
39 #include "llvm/ADT/DenseSet.h"
40 #include "llvm/ADT/Hashing.h"
41 #include "llvm/ADT/None.h"
42 #include "llvm/ADT/Optional.h"
44 #include "llvm/ADT/STLExtras.h"
45 #include "llvm/ADT/SmallPtrSet.h"
46 #include "llvm/ADT/SmallVector.h"
47 #include "llvm/ADT/Statistic.h"
48 #include "llvm/ADT/StringExtras.h"
50 #include "llvm/IR/BasicBlock.h"
51 #include "llvm/IR/CFG.h"
52 #include "llvm/IR/Constants.h"
53 #include "llvm/IR/Function.h"
54 #include "llvm/IR/InstrTypes.h"
55 #include "llvm/IR/Instruction.h"
56 #include "llvm/IR/Instructions.h"
57 #include "llvm/IR/PassManager.h"
58 #include "llvm/IR/Type.h"
59 #include "llvm/IR/Use.h"
60 #include "llvm/IR/Value.h"
61 #include "llvm/InitializePasses.h"
62 #include "llvm/Pass.h"
63 #include "llvm/Support/Allocator.h"
66 #include "llvm/Support/Casting.h"
67 #include "llvm/Support/Compiler.h"
68 #include "llvm/Support/Debug.h"
70 #include "llvm/Transforms/Scalar.h"
75 #include <algorithm>
76 #include <cassert>
77 #include <cstddef>
78 #include <cstdint>
79 #include <iterator>
80 #include <utility>
81 
82 using namespace llvm;
83 
84 #define DEBUG_TYPE "gvn-sink"
85 
86 STATISTIC(NumRemoved, "Number of instructions removed");
87 
88 namespace llvm {
89 namespace GVNExpression {
90 
92  print(dbgs());
93  dbgs() << "\n";
94 }
95 
96 } // end namespace GVNExpression
97 } // end namespace llvm
98 
99 namespace {
100 
101 static bool isMemoryInst(const Instruction *I) {
102  return isa<LoadInst>(I) || isa<StoreInst>(I) ||
103  (isa<InvokeInst>(I) && !cast<InvokeInst>(I)->doesNotAccessMemory()) ||
104  (isa<CallInst>(I) && !cast<CallInst>(I)->doesNotAccessMemory());
105 }
106 
107 /// Iterates through instructions in a set of blocks in reverse order from the
108 /// first non-terminator. For example (assume all blocks have size n):
109 /// LockstepReverseIterator I([B1, B2, B3]);
110 /// *I-- = [B1[n], B2[n], B3[n]];
111 /// *I-- = [B1[n-1], B2[n-1], B3[n-1]];
112 /// *I-- = [B1[n-2], B2[n-2], B3[n-2]];
113 /// ...
114 ///
115 /// It continues until all blocks have been exhausted. Use \c getActiveBlocks()
116 /// to
117 /// determine which blocks are still going and the order they appear in the
118 /// list returned by operator*.
119 class LockstepReverseIterator {
120  ArrayRef<BasicBlock *> Blocks;
121  SmallSetVector<BasicBlock *, 4> ActiveBlocks;
123  bool Fail;
124 
125 public:
126  LockstepReverseIterator(ArrayRef<BasicBlock *> Blocks) : Blocks(Blocks) {
127  reset();
128  }
129 
130  void reset() {
131  Fail = false;
132  ActiveBlocks.clear();
133  for (BasicBlock *BB : Blocks)
134  ActiveBlocks.insert(BB);
135  Insts.clear();
136  for (BasicBlock *BB : Blocks) {
137  if (BB->size() <= 1) {
138  // Block wasn't big enough - only contained a terminator.
139  ActiveBlocks.remove(BB);
140  continue;
141  }
142  Insts.push_back(BB->getTerminator()->getPrevNode());
143  }
144  if (Insts.empty())
145  Fail = true;
146  }
147 
148  bool isValid() const { return !Fail; }
149  ArrayRef<Instruction *> operator*() const { return Insts; }
150 
151  // Note: This needs to return a SmallSetVector as the elements of
152  // ActiveBlocks will be later copied to Blocks using std::copy. The
153  // resultant order of elements in Blocks needs to be deterministic.
154  // Using SmallPtrSet instead causes non-deterministic order while
155  // copying. And we cannot simply sort Blocks as they need to match the
156  // corresponding Values.
157  SmallSetVector<BasicBlock *, 4> &getActiveBlocks() { return ActiveBlocks; }
158 
159  void restrictToBlocks(SmallSetVector<BasicBlock *, 4> &Blocks) {
160  for (auto II = Insts.begin(); II != Insts.end();) {
161  if (!llvm::is_contained(Blocks, (*II)->getParent())) {
162  ActiveBlocks.remove((*II)->getParent());
163  II = Insts.erase(II);
164  } else {
165  ++II;
166  }
167  }
168  }
169 
170  void operator--() {
171  if (Fail)
172  return;
174  for (auto *Inst : Insts) {
175  if (Inst == &Inst->getParent()->front())
176  ActiveBlocks.remove(Inst->getParent());
177  else
178  NewInsts.push_back(Inst->getPrevNode());
179  }
180  if (NewInsts.empty()) {
181  Fail = true;
182  return;
183  }
184  Insts = NewInsts;
185  }
186 };
187 
188 //===----------------------------------------------------------------------===//
189 
190 /// Candidate solution for sinking. There may be different ways to
191 /// sink instructions, differing in the number of instructions sunk,
192 /// the number of predecessors sunk from and the number of PHIs
193 /// required.
194 struct SinkingInstructionCandidate {
195  unsigned NumBlocks;
196  unsigned NumInstructions;
197  unsigned NumPHIs;
198  unsigned NumMemoryInsts;
199  int Cost = -1;
201 
202  void calculateCost(unsigned NumOrigPHIs, unsigned NumOrigBlocks) {
203  unsigned NumExtraPHIs = NumPHIs - NumOrigPHIs;
204  unsigned SplitEdgeCost = (NumOrigBlocks > NumBlocks) ? 2 : 0;
205  Cost = (NumInstructions * (NumBlocks - 1)) -
206  (NumExtraPHIs *
207  NumExtraPHIs) // PHIs are expensive, so make sure they're worth it.
208  - SplitEdgeCost;
209  }
210 
211  bool operator>(const SinkingInstructionCandidate &Other) const {
212  return Cost > Other.Cost;
213  }
214 };
215 
216 #ifndef NDEBUG
217 raw_ostream &operator<<(raw_ostream &OS, const SinkingInstructionCandidate &C) {
218  OS << "<Candidate Cost=" << C.Cost << " #Blocks=" << C.NumBlocks
219  << " #Insts=" << C.NumInstructions << " #PHIs=" << C.NumPHIs << ">";
220  return OS;
221 }
222 #endif
223 
224 //===----------------------------------------------------------------------===//
225 
226 /// Describes a PHI node that may or may not exist. These track the PHIs
227 /// that must be created if we sunk a sequence of instructions. It provides
228 /// a hash function for efficient equality comparisons.
229 class ModelledPHI {
232 
233 public:
234  ModelledPHI() = default;
235 
236  ModelledPHI(const PHINode *PN) {
237  // BasicBlock comes first so we sort by basic block pointer order, then by value pointer order.
239  for (unsigned I = 0, E = PN->getNumIncomingValues(); I != E; ++I)
240  Ops.push_back({PN->getIncomingBlock(I), PN->getIncomingValue(I)});
241  llvm::sort(Ops);
242  for (auto &P : Ops) {
243  Blocks.push_back(P.first);
244  Values.push_back(P.second);
245  }
246  }
247 
248  /// Create a dummy ModelledPHI that will compare unequal to any other ModelledPHI
249  /// without the same ID.
250  /// \note This is specifically for DenseMapInfo - do not use this!
251  static ModelledPHI createDummy(size_t ID) {
252  ModelledPHI M;
253  M.Values.push_back(reinterpret_cast<Value*>(ID));
254  return M;
255  }
256 
257  /// Create a PHI from an array of incoming values and incoming blocks.
258  template <typename VArray, typename BArray>
259  ModelledPHI(const VArray &V, const BArray &B) {
260  llvm::copy(V, std::back_inserter(Values));
261  llvm::copy(B, std::back_inserter(Blocks));
262  }
263 
264  /// Create a PHI from [I[OpNum] for I in Insts].
265  template <typename BArray>
266  ModelledPHI(ArrayRef<Instruction *> Insts, unsigned OpNum, const BArray &B) {
267  llvm::copy(B, std::back_inserter(Blocks));
268  for (auto *I : Insts)
269  Values.push_back(I->getOperand(OpNum));
270  }
271 
272  /// Restrict the PHI's contents down to only \c NewBlocks.
273  /// \c NewBlocks must be a subset of \c this->Blocks.
274  void restrictToBlocks(const SmallSetVector<BasicBlock *, 4> &NewBlocks) {
275  auto BI = Blocks.begin();
276  auto VI = Values.begin();
277  while (BI != Blocks.end()) {
278  assert(VI != Values.end());
279  if (!llvm::is_contained(NewBlocks, *BI)) {
280  BI = Blocks.erase(BI);
281  VI = Values.erase(VI);
282  } else {
283  ++BI;
284  ++VI;
285  }
286  }
287  assert(Blocks.size() == NewBlocks.size());
288  }
289 
290  ArrayRef<Value *> getValues() const { return Values; }
291 
292  bool areAllIncomingValuesSame() const {
293  return llvm::all_of(Values, [&](Value *V) { return V == Values[0]; });
294  }
295 
296  bool areAllIncomingValuesSameType() const {
297  return llvm::all_of(
298  Values, [&](Value *V) { return V->getType() == Values[0]->getType(); });
299  }
300 
301  bool areAnyIncomingValuesConstant() const {
302  return llvm::any_of(Values, [&](Value *V) { return isa<Constant>(V); });
303  }
304 
305  // Hash functor
306  unsigned hash() const {
307  return (unsigned)hash_combine_range(Values.begin(), Values.end());
308  }
309 
310  bool operator==(const ModelledPHI &Other) const {
311  return Values == Other.Values && Blocks == Other.Blocks;
312  }
313 };
314 
315 template <typename ModelledPHI> struct DenseMapInfo {
316  static inline ModelledPHI &getEmptyKey() {
317  static ModelledPHI Dummy = ModelledPHI::createDummy(0);
318  return Dummy;
319  }
320 
321  static inline ModelledPHI &getTombstoneKey() {
322  static ModelledPHI Dummy = ModelledPHI::createDummy(1);
323  return Dummy;
324  }
325 
326  static unsigned getHashValue(const ModelledPHI &V) { return V.hash(); }
327 
328  static bool isEqual(const ModelledPHI &LHS, const ModelledPHI &RHS) {
329  return LHS == RHS;
330  }
331 };
332 
334 
335 //===----------------------------------------------------------------------===//
336 // ValueTable
337 //===----------------------------------------------------------------------===//
338 // This is a value number table where the value number is a function of the
339 // *uses* of a value, rather than its operands. Thus, if VN(A) == VN(B) we know
340 // that the program would be equivalent if we replaced A with PHI(A, B).
341 //===----------------------------------------------------------------------===//
342 
343 /// A GVN expression describing how an instruction is used. The operands
344 /// field of BasicExpression is used to store uses, not operands.
345 ///
346 /// This class also contains fields for discriminators used when determining
347 /// equivalence of instructions with sideeffects.
348 class InstructionUseExpr : public GVNExpression::BasicExpression {
349  unsigned MemoryUseOrder = -1;
350  bool Volatile = false;
351  ArrayRef<int> ShuffleMask;
352 
353 public:
354  InstructionUseExpr(Instruction *I, ArrayRecycler<Value *> &R,
356  : GVNExpression::BasicExpression(I->getNumUses()) {
357  allocateOperands(R, A);
358  setOpcode(I->getOpcode());
359  setType(I->getType());
360 
361  if (ShuffleVectorInst *SVI = dyn_cast<ShuffleVectorInst>(I))
362  ShuffleMask = SVI->getShuffleMask().copy(A);
363 
364  for (auto &U : I->uses())
365  op_push_back(U.getUser());
366  llvm::sort(op_begin(), op_end());
367  }
368 
369  void setMemoryUseOrder(unsigned MUO) { MemoryUseOrder = MUO; }
370  void setVolatile(bool V) { Volatile = V; }
371 
372  hash_code getHashValue() const override {
373  return hash_combine(GVNExpression::BasicExpression::getHashValue(),
374  MemoryUseOrder, Volatile, ShuffleMask);
375  }
376 
377  template <typename Function> hash_code getHashValue(Function MapFn) {
378  hash_code H = hash_combine(getOpcode(), getType(), MemoryUseOrder, Volatile,
379  ShuffleMask);
380  for (auto *V : operands())
381  H = hash_combine(H, MapFn(V));
382  return H;
383  }
384 };
385 
386 class ValueTable {
387  DenseMap<Value *, uint32_t> ValueNumbering;
389  DenseMap<size_t, uint32_t> HashNumbering;
392  uint32_t nextValueNumber = 1;
393 
394  /// Create an expression for I based on its opcode and its uses. If I
395  /// touches or reads memory, the expression is also based upon its memory
396  /// order - see \c getMemoryUseOrder().
397  InstructionUseExpr *createExpr(Instruction *I) {
398  InstructionUseExpr *E =
399  new (Allocator) InstructionUseExpr(I, Recycler, Allocator);
400  if (isMemoryInst(I))
401  E->setMemoryUseOrder(getMemoryUseOrder(I));
402 
403  if (CmpInst *C = dyn_cast<CmpInst>(I)) {
404  CmpInst::Predicate Predicate = C->getPredicate();
405  E->setOpcode((C->getOpcode() << 8) | Predicate);
406  }
407  return E;
408  }
409 
410  /// Helper to compute the value number for a memory instruction
411  /// (LoadInst/StoreInst), including checking the memory ordering and
412  /// volatility.
413  template <class Inst> InstructionUseExpr *createMemoryExpr(Inst *I) {
414  if (isStrongerThanUnordered(I->getOrdering()) || I->isAtomic())
415  return nullptr;
416  InstructionUseExpr *E = createExpr(I);
417  E->setVolatile(I->isVolatile());
418  return E;
419  }
420 
421 public:
422  ValueTable() = default;
423 
424  /// Returns the value number for the specified value, assigning
425  /// it a new number if it did not have one before.
426  uint32_t lookupOrAdd(Value *V) {
427  auto VI = ValueNumbering.find(V);
428  if (VI != ValueNumbering.end())
429  return VI->second;
430 
431  if (!isa<Instruction>(V)) {
432  ValueNumbering[V] = nextValueNumber;
433  return nextValueNumber++;
434  }
435 
436  Instruction *I = cast<Instruction>(V);
437  InstructionUseExpr *exp = nullptr;
438  switch (I->getOpcode()) {
439  case Instruction::Load:
440  exp = createMemoryExpr(cast<LoadInst>(I));
441  break;
442  case Instruction::Store:
443  exp = createMemoryExpr(cast<StoreInst>(I));
444  break;
445  case Instruction::Call:
446  case Instruction::Invoke:
447  case Instruction::FNeg:
448  case Instruction::Add:
449  case Instruction::FAdd:
450  case Instruction::Sub:
451  case Instruction::FSub:
452  case Instruction::Mul:
453  case Instruction::FMul:
454  case Instruction::UDiv:
455  case Instruction::SDiv:
456  case Instruction::FDiv:
457  case Instruction::URem:
458  case Instruction::SRem:
459  case Instruction::FRem:
460  case Instruction::Shl:
461  case Instruction::LShr:
462  case Instruction::AShr:
463  case Instruction::And:
464  case Instruction::Or:
465  case Instruction::Xor:
466  case Instruction::ICmp:
467  case Instruction::FCmp:
468  case Instruction::Trunc:
469  case Instruction::ZExt:
470  case Instruction::SExt:
471  case Instruction::FPToUI:
472  case Instruction::FPToSI:
473  case Instruction::UIToFP:
474  case Instruction::SIToFP:
475  case Instruction::FPTrunc:
476  case Instruction::FPExt:
477  case Instruction::PtrToInt:
478  case Instruction::IntToPtr:
479  case Instruction::BitCast:
480  case Instruction::AddrSpaceCast:
481  case Instruction::Select:
482  case Instruction::ExtractElement:
483  case Instruction::InsertElement:
484  case Instruction::ShuffleVector:
485  case Instruction::InsertValue:
486  case Instruction::GetElementPtr:
487  exp = createExpr(I);
488  break;
489  default:
490  break;
491  }
492 
493  if (!exp) {
494  ValueNumbering[V] = nextValueNumber;
495  return nextValueNumber++;
496  }
497 
498  uint32_t e = ExpressionNumbering[exp];
499  if (!e) {
500  hash_code H = exp->getHashValue([=](Value *V) { return lookupOrAdd(V); });
501  auto I = HashNumbering.find(H);
502  if (I != HashNumbering.end()) {
503  e = I->second;
504  } else {
505  e = nextValueNumber++;
506  HashNumbering[H] = e;
507  ExpressionNumbering[exp] = e;
508  }
509  }
510  ValueNumbering[V] = e;
511  return e;
512  }
513 
514  /// Returns the value number of the specified value. Fails if the value has
515  /// not yet been numbered.
516  uint32_t lookup(Value *V) const {
517  auto VI = ValueNumbering.find(V);
518  assert(VI != ValueNumbering.end() && "Value not numbered?");
519  return VI->second;
520  }
521 
522  /// Removes all value numberings and resets the value table.
523  void clear() {
524  ValueNumbering.clear();
525  ExpressionNumbering.clear();
526  HashNumbering.clear();
528  nextValueNumber = 1;
529  }
530 
531  /// \c Inst uses or touches memory. Return an ID describing the memory state
532  /// at \c Inst such that if getMemoryUseOrder(I1) == getMemoryUseOrder(I2),
533  /// the exact same memory operations happen after I1 and I2.
534  ///
535  /// This is a very hard problem in general, so we use domain-specific
536  /// knowledge that we only ever check for equivalence between blocks sharing a
537  /// single immediate successor that is common, and when determining if I1 ==
538  /// I2 we will have already determined that next(I1) == next(I2). This
539  /// inductive property allows us to simply return the value number of the next
540  /// instruction that defines memory.
541  uint32_t getMemoryUseOrder(Instruction *Inst) {
542  auto *BB = Inst->getParent();
543  for (auto I = std::next(Inst->getIterator()), E = BB->end();
544  I != E && !I->isTerminator(); ++I) {
545  if (!isMemoryInst(&*I))
546  continue;
547  if (isa<LoadInst>(&*I))
548  continue;
549  CallInst *CI = dyn_cast<CallInst>(&*I);
550  if (CI && CI->onlyReadsMemory())
551  continue;
552  InvokeInst *II = dyn_cast<InvokeInst>(&*I);
553  if (II && II->onlyReadsMemory())
554  continue;
555  return lookupOrAdd(&*I);
556  }
557  return 0;
558  }
559 };
560 
561 //===----------------------------------------------------------------------===//
562 
563 class GVNSink {
564 public:
565  GVNSink() = default;
566 
567  bool run(Function &F) {
568  LLVM_DEBUG(dbgs() << "GVNSink: running on function @" << F.getName()
569  << "\n");
570 
571  unsigned NumSunk = 0;
573  for (auto *N : RPOT)
574  NumSunk += sinkBB(N);
575 
576  return NumSunk > 0;
577  }
578 
579 private:
580  ValueTable VN;
581 
582  bool shouldAvoidSinkingInstruction(Instruction *I) {
583  // These instructions may change or break semantics if moved.
584  if (isa<PHINode>(I) || I->isEHPad() || isa<AllocaInst>(I) ||
585  I->getType()->isTokenTy())
586  return true;
587  return false;
588  }
589 
590  /// The main heuristic function. Analyze the set of instructions pointed to by
591  /// LRI and return a candidate solution if these instructions can be sunk, or
592  /// None otherwise.
593  Optional<SinkingInstructionCandidate> analyzeInstructionForSinking(
594  LockstepReverseIterator &LRI, unsigned &InstNum, unsigned &MemoryInstNum,
595  ModelledPHISet &NeededPHIs, SmallPtrSetImpl<Value *> &PHIContents);
596 
597  /// Create a ModelledPHI for each PHI in BB, adding to PHIs.
598  void analyzeInitialPHIs(BasicBlock *BB, ModelledPHISet &PHIs,
599  SmallPtrSetImpl<Value *> &PHIContents) {
600  for (PHINode &PN : BB->phis()) {
601  auto MPHI = ModelledPHI(&PN);
602  PHIs.insert(MPHI);
603  for (auto *V : MPHI.getValues())
604  PHIContents.insert(V);
605  }
606  }
607 
608  /// The main instruction sinking driver. Set up state and try and sink
609  /// instructions into BBEnd from its predecessors.
610  unsigned sinkBB(BasicBlock *BBEnd);
611 
612  /// Perform the actual mechanics of sinking an instruction from Blocks into
613  /// BBEnd, which is their only successor.
615 
616  /// Remove PHIs that all have the same incoming value.
617  void foldPointlessPHINodes(BasicBlock *BB) {
618  auto I = BB->begin();
619  while (PHINode *PN = dyn_cast<PHINode>(I++)) {
620  if (!llvm::all_of(PN->incoming_values(), [&](const Value *V) {
621  return V == PN->getIncomingValue(0);
622  }))
623  continue;
624  if (PN->getIncomingValue(0) != PN)
626  else
628  PN->eraseFromParent();
629  }
630  }
631 };
632 
633 Optional<SinkingInstructionCandidate> GVNSink::analyzeInstructionForSinking(
634  LockstepReverseIterator &LRI, unsigned &InstNum, unsigned &MemoryInstNum,
635  ModelledPHISet &NeededPHIs, SmallPtrSetImpl<Value *> &PHIContents) {
636  auto Insts = *LRI;
637  LLVM_DEBUG(dbgs() << " -- Analyzing instruction set: [\n"; for (auto *I
638  : Insts) {
639  I->dump();
640  } dbgs() << " ]\n";);
641 
643  for (auto *I : Insts) {
644  uint32_t N = VN.lookupOrAdd(I);
645  LLVM_DEBUG(dbgs() << " VN=" << Twine::utohexstr(N) << " for" << *I << "\n");
646  if (N == ~0U)
647  return None;
648  VNums[N]++;
649  }
650  unsigned VNumToSink =
651  std::max_element(VNums.begin(), VNums.end(),
652  [](const std::pair<uint32_t, unsigned> &I,
653  const std::pair<uint32_t, unsigned> &J) {
654  return I.second < J.second;
655  })
656  ->first;
657 
658  if (VNums[VNumToSink] == 1)
659  // Can't sink anything!
660  return None;
661 
662  // Now restrict the number of incoming blocks down to only those with
663  // VNumToSink.
664  auto &ActivePreds = LRI.getActiveBlocks();
665  unsigned InitialActivePredSize = ActivePreds.size();
667  for (auto *I : Insts) {
668  if (VN.lookup(I) != VNumToSink)
669  ActivePreds.remove(I->getParent());
670  else
671  NewInsts.push_back(I);
672  }
673  for (auto *I : NewInsts)
674  if (shouldAvoidSinkingInstruction(I))
675  return None;
676 
677  // If we've restricted the incoming blocks, restrict all needed PHIs also
678  // to that set.
679  bool RecomputePHIContents = false;
680  if (ActivePreds.size() != InitialActivePredSize) {
681  ModelledPHISet NewNeededPHIs;
682  for (auto P : NeededPHIs) {
683  P.restrictToBlocks(ActivePreds);
684  NewNeededPHIs.insert(P);
685  }
686  NeededPHIs = NewNeededPHIs;
687  LRI.restrictToBlocks(ActivePreds);
688  RecomputePHIContents = true;
689  }
690 
691  // The sunk instruction's results.
692  ModelledPHI NewPHI(NewInsts, ActivePreds);
693 
694  // Does sinking this instruction render previous PHIs redundant?
695  if (NeededPHIs.erase(NewPHI))
696  RecomputePHIContents = true;
697 
698  if (RecomputePHIContents) {
699  // The needed PHIs have changed, so recompute the set of all needed
700  // values.
701  PHIContents.clear();
702  for (auto &PHI : NeededPHIs)
703  PHIContents.insert(PHI.getValues().begin(), PHI.getValues().end());
704  }
705 
706  // Is this instruction required by a later PHI that doesn't match this PHI?
707  // if so, we can't sink this instruction.
708  for (auto *V : NewPHI.getValues())
709  if (PHIContents.count(V))
710  // V exists in this PHI, but the whole PHI is different to NewPHI
711  // (else it would have been removed earlier). We cannot continue
712  // because this isn't representable.
713  return None;
714 
715  // Which operands need PHIs?
716  // FIXME: If any of these fail, we should partition up the candidates to
717  // try and continue making progress.
718  Instruction *I0 = NewInsts[0];
719 
720  // If all instructions that are going to participate don't have the same
721  // number of operands, we can't do any useful PHI analysis for all operands.
722  auto hasDifferentNumOperands = [&I0](Instruction *I) {
723  return I->getNumOperands() != I0->getNumOperands();
724  };
725  if (any_of(NewInsts, hasDifferentNumOperands))
726  return None;
727 
728  for (unsigned OpNum = 0, E = I0->getNumOperands(); OpNum != E; ++OpNum) {
729  ModelledPHI PHI(NewInsts, OpNum, ActivePreds);
730  if (PHI.areAllIncomingValuesSame())
731  continue;
732  if (!canReplaceOperandWithVariable(I0, OpNum))
733  // We can 't create a PHI from this instruction!
734  return None;
735  if (NeededPHIs.count(PHI))
736  continue;
737  if (!PHI.areAllIncomingValuesSameType())
738  return None;
739  // Don't create indirect calls! The called value is the final operand.
740  if ((isa<CallInst>(I0) || isa<InvokeInst>(I0)) && OpNum == E - 1 &&
741  PHI.areAnyIncomingValuesConstant())
742  return None;
743 
744  NeededPHIs.reserve(NeededPHIs.size());
745  NeededPHIs.insert(PHI);
746  PHIContents.insert(PHI.getValues().begin(), PHI.getValues().end());
747  }
748 
749  if (isMemoryInst(NewInsts[0]))
750  ++MemoryInstNum;
751 
752  SinkingInstructionCandidate Cand;
753  Cand.NumInstructions = ++InstNum;
754  Cand.NumMemoryInsts = MemoryInstNum;
755  Cand.NumBlocks = ActivePreds.size();
756  Cand.NumPHIs = NeededPHIs.size();
757  append_range(Cand.Blocks, ActivePreds);
758 
759  return Cand;
760 }
761 
762 unsigned GVNSink::sinkBB(BasicBlock *BBEnd) {
763  LLVM_DEBUG(dbgs() << "GVNSink: running on basic block ";
764  BBEnd->printAsOperand(dbgs()); dbgs() << "\n");
766  for (auto *B : predecessors(BBEnd)) {
767  auto *T = B->getTerminator();
768  if (isa<BranchInst>(T) || isa<SwitchInst>(T))
769  Preds.push_back(B);
770  else
771  return 0;
772  }
773  if (Preds.size() < 2)
774  return 0;
775  llvm::sort(Preds);
776 
777  unsigned NumOrigPreds = Preds.size();
778  // We can only sink instructions through unconditional branches.
779  for (auto I = Preds.begin(); I != Preds.end();) {
780  if ((*I)->getTerminator()->getNumSuccessors() != 1)
781  I = Preds.erase(I);
782  else
783  ++I;
784  }
785 
786  LockstepReverseIterator LRI(Preds);
788  unsigned InstNum = 0, MemoryInstNum = 0;
789  ModelledPHISet NeededPHIs;
790  SmallPtrSet<Value *, 4> PHIContents;
791  analyzeInitialPHIs(BBEnd, NeededPHIs, PHIContents);
792  unsigned NumOrigPHIs = NeededPHIs.size();
793 
794  while (LRI.isValid()) {
795  auto Cand = analyzeInstructionForSinking(LRI, InstNum, MemoryInstNum,
796  NeededPHIs, PHIContents);
797  if (!Cand)
798  break;
799  Cand->calculateCost(NumOrigPHIs, Preds.size());
800  Candidates.emplace_back(*Cand);
801  --LRI;
802  }
803 
804  llvm::stable_sort(Candidates, std::greater<SinkingInstructionCandidate>());
805  LLVM_DEBUG(dbgs() << " -- Sinking candidates:\n"; for (auto &C
806  : Candidates) dbgs()
807  << " " << C << "\n";);
808 
809  // Pick the top candidate, as long it is positive!
810  if (Candidates.empty() || Candidates.front().Cost <= 0)
811  return 0;
812  auto C = Candidates.front();
813 
814  LLVM_DEBUG(dbgs() << " -- Sinking: " << C << "\n");
815  BasicBlock *InsertBB = BBEnd;
816  if (C.Blocks.size() < NumOrigPreds) {
817  LLVM_DEBUG(dbgs() << " -- Splitting edge to ";
818  BBEnd->printAsOperand(dbgs()); dbgs() << "\n");
819  InsertBB = SplitBlockPredecessors(BBEnd, C.Blocks, ".gvnsink.split");
820  if (!InsertBB) {
821  LLVM_DEBUG(dbgs() << " -- FAILED to split edge!\n");
822  // Edge couldn't be split.
823  return 0;
824  }
825  }
826 
827  for (unsigned I = 0; I < C.NumInstructions; ++I)
828  sinkLastInstruction(C.Blocks, InsertBB);
829 
830  return C.NumInstructions;
831 }
832 
834  BasicBlock *BBEnd) {
836  for (BasicBlock *BB : Blocks)
837  Insts.push_back(BB->getTerminator()->getPrevNode());
838  Instruction *I0 = Insts.front();
839 
840  SmallVector<Value *, 4> NewOperands;
841  for (unsigned O = 0, E = I0->getNumOperands(); O != E; ++O) {
842  bool NeedPHI = llvm::any_of(Insts, [&I0, O](const Instruction *I) {
843  return I->getOperand(O) != I0->getOperand(O);
844  });
845  if (!NeedPHI) {
846  NewOperands.push_back(I0->getOperand(O));
847  continue;
848  }
849 
850  // Create a new PHI in the successor block and populate it.
851  auto *Op = I0->getOperand(O);
852  assert(!Op->getType()->isTokenTy() && "Can't PHI tokens!");
853  auto *PN = PHINode::Create(Op->getType(), Insts.size(),
854  Op->getName() + ".sink", &BBEnd->front());
855  for (auto *I : Insts)
856  PN->addIncoming(I->getOperand(O), I->getParent());
857  NewOperands.push_back(PN);
858  }
859 
860  // Arbitrarily use I0 as the new "common" instruction; remap its operands
861  // and move it to the start of the successor block.
862  for (unsigned O = 0, E = I0->getNumOperands(); O != E; ++O)
863  I0->getOperandUse(O).set(NewOperands[O]);
864  I0->moveBefore(&*BBEnd->getFirstInsertionPt());
865 
866  // Update metadata and IR flags.
867  for (auto *I : Insts)
868  if (I != I0) {
869  combineMetadataForCSE(I0, I, true);
870  I0->andIRFlags(I);
871  }
872 
873  for (auto *I : Insts)
874  if (I != I0)
875  I->replaceAllUsesWith(I0);
876  foldPointlessPHINodes(BBEnd);
877 
878  // Finally nuke all instructions apart from the common instruction.
879  for (auto *I : Insts)
880  if (I != I0)
881  I->eraseFromParent();
882 
883  NumRemoved += Insts.size() - 1;
884 }
885 
886 ////////////////////////////////////////////////////////////////////////////////
887 // Pass machinery / boilerplate
888 
889 class GVNSinkLegacyPass : public FunctionPass {
890 public:
891  static char ID;
892 
893  GVNSinkLegacyPass() : FunctionPass(ID) {
894  initializeGVNSinkLegacyPassPass(*PassRegistry::getPassRegistry());
895  }
896 
897  bool runOnFunction(Function &F) override {
898  if (skipFunction(F))
899  return false;
900  GVNSink G;
901  return G.run(F);
902  }
903 
904  void getAnalysisUsage(AnalysisUsage &AU) const override {
906  }
907 };
908 
909 } // end anonymous namespace
910 
912  GVNSink G;
913  if (!G.run(F))
914  return PreservedAnalyses::all();
915  return PreservedAnalyses::none();
916 }
917 
918 char GVNSinkLegacyPass::ID = 0;
919 
920 INITIALIZE_PASS_BEGIN(GVNSinkLegacyPass, "gvn-sink",
921  "Early GVN sinking of Expressions", false, false)
924 INITIALIZE_PASS_END(GVNSinkLegacyPass, "gvn-sink",
926 
927 FunctionPass *llvm::createGVNSinkPass() { return new GVNSinkLegacyPass(); }
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:155
llvm::GVNExpression::BasicExpression::op_end
op_iterator op_end()
Definition: GVNExpression.h:185
llvm::predecessors
pred_range predecessors(BasicBlock *BB)
Definition: CFG.h:127
llvm::SPII::Load
@ Load
Definition: SparcInstrInfo.h:32
llvm::createGVNSinkPass
FunctionPass * createGVNSinkPass()
Definition: GVNSink.cpp:927
LLVM_DUMP_METHOD
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
Definition: Compiler.h:499
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
llvm::SmallVectorImpl::erase
iterator erase(const_iterator CI)
Definition: SmallVector.h:705
M
We currently emits eax Perhaps this is what we really should generate is Is imull three or four cycles eax eax The current instruction priority is based on pattern complexity The former is more complex because it folds a load so the latter will not be emitted Perhaps we should use AddedComplexity to give LEA32r a higher priority We should always try to match LEA first since the LEA matching code does some estimate to determine whether the match is profitable if we care more about code then imull is better It s two bytes shorter than movl leal On a Pentium M
Definition: README.txt:252
Optional.h
llvm::PHINode::incoming_values
op_range incoming_values()
Definition: Instructions.h:2683
llvm::CmpInst::Predicate
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:720
AtomicOrdering.h
Scalar.h
llvm::ArrayRef::copy
ArrayRef< T > copy(Allocator &A)
Definition: ArrayRef.h:180
llvm::Function
Definition: Function.h:61
llvm::GVNExpression::Expression::getOpcode
unsigned getOpcode() const
Definition: GVNExpression.h:108
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
Pass.h
llvm::SetVector< T, SmallVector< T, N >, SmallDenseSet< T, N > >::size
size_type size() const
Determine the number of elements in the SetVector.
Definition: SetVector.h:77
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::FunctionPass::skipFunction
bool skipFunction(const Function &F) const
Optional passes call this function to check whether the pass should be skipped.
Definition: Pass.cpp:163
Allocator.h
Local.h
Fail
#define Fail
Definition: AArch64Disassembler.cpp:258
GlobalsModRef.h
llvm::FunctionPass::runOnFunction
virtual bool runOnFunction(Function &F)=0
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.
llvm::PreservedAnalyses::none
static PreservedAnalyses none()
Convenience factory function for the empty preserved set.
Definition: PassManager.h:158
DenseMap.h
INITIALIZE_PASS_BEGIN
INITIALIZE_PASS_BEGIN(GVNSinkLegacyPass, "gvn-sink", "Early GVN sinking of Expressions", false, false) INITIALIZE_PASS_END(GVNSinkLegacyPass
llvm::copy
OutputIt copy(R &&Range, OutputIt Out)
Definition: STLExtras.h:1585
llvm::Optional
Definition: APInt.h:33
T
#define T
Definition: Mips16ISelLowering.cpp:341
llvm::SmallPtrSet< Value *, 4 >
Hashing.h
STLExtras.h
Use.h
llvm::combineMetadataForCSE
void combineMetadataForCSE(Instruction *K, const Instruction *J, bool DoesKMove)
Combine the metadata of two instructions so that K can replace J.
Definition: Local.cpp:2578
sinking
Machine code sinking
Definition: MachineSink.cpp:265
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:122
F
#define F(x, y, z)
Definition: MD5.cpp:56
llvm::RISCVFenceField::R
@ R
Definition: RISCVBaseInfo.h:180
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
clear
static void clear(coro::Shape &Shape)
Definition: Coroutines.cpp:233
llvm::User::getOperandUse
const Use & getOperandUse(unsigned i) const
Definition: User.h:182
Instruction.h
llvm::SetVector< T, SmallVector< T, N >, SmallDenseSet< T, N > >::remove
bool remove(const value_type &X)
Remove an item from the set vector.
Definition: SetVector.h:157
llvm::Intrinsic::getType
FunctionType * getType(LLVMContext &Context, ID id, ArrayRef< Type * > Tys=None)
Return the function type for an intrinsic.
Definition: Function.cpp:1292
llvm::DenseMapInfo
Definition: APInt.h:34
llvm::all_of
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1534
llvm::Recycler::clear
void clear(AllocatorType &Allocator)
clear - Release all the tracked allocations to the allocator.
Definition: Recycler.h:68
Constants.h
llvm::GVNExpression::Expression::print
void print(raw_ostream &OS) const
Definition: GVNExpression.h:122
llvm::PHINode::getIncomingValue
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
Definition: Instructions.h:2693
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::GVNExpression::BasicExpression::operands
iterator_range< op_iterator > operands()
Definition: GVNExpression.h:188
C
(vector float) vec_cmpeq(*A, *B) C
Definition: README_ALTIVEC.txt:86
InstrTypes.h
llvm::canReplaceOperandWithVariable
bool canReplaceOperandWithVariable(const Instruction *I, unsigned OpIdx)
Given an instruction, is it legal to set operand OpIdx to a non-constant value?
Definition: Local.cpp:3250
llvm::PostDominatorTreeWrapperPass
Definition: PostDominators.h:73
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
DenseSet.h
llvm::BasicBlock::getFirstInsertionPt
const_iterator getFirstInsertionPt() const
Returns an iterator to the first instruction in this block that is suitable for inserting a non-PHI i...
Definition: BasicBlock.cpp:249
false
Definition: StackSlotColoring.cpp:142
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
llvm::Instruction
Definition: Instruction.h:45
llvm::DominatorTreeWrapperPass
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:281
GVNExpression.h
llvm::STATISTIC
STATISTIC(NumFunctions, "Total number of functions")
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:53
llvm::operator<<
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
Definition: APFixedPoint.h:230
llvm::codeview::ModifierOptions::Volatile
@ Volatile
GVN.h
SmallPtrSet.h
llvm::SplitBlockPredecessors
BasicBlock * SplitBlockPredecessors(BasicBlock *BB, ArrayRef< BasicBlock * > Preds, const char *Suffix, DominatorTree *DT, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, bool PreserveLCSSA=false)
This method introduces at least one new basic block into the function and moves some of the predecess...
Definition: BasicBlockUtils.cpp:1148
llvm::MCID::Call
@ Call
Definition: MCInstrDesc.h:153
llvm::PHINode::getNumIncomingValues
unsigned getNumIncomingValues() const
Return the number of incoming edges.
Definition: Instructions.h:2689
llvm::None
const NoneType None
Definition: None.h:23
llvm::GVNExpression::BasicExpression::op_push_back
void op_push_back(Value *Arg)
Definition: GVNExpression.h:195
llvm::CallBase::onlyReadsMemory
bool onlyReadsMemory(unsigned OpNo) const
Definition: InstrTypes.h:1693
Type.h
INITIALIZE_PASS_END
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:58
CFG.h
llvm::GVNExpression::BasicExpression::getType
Type * getType() const
Definition: GVNExpression.h:211
llvm::InvokeInst
Invoke instruction.
Definition: Instructions.h:3713
llvm::CmpInst
This class is the base class for the comparison instructions.
Definition: InstrTypes.h:710
G
const DataFlowGraph & G
Definition: RDFGraph.cpp:202
llvm::Instruction::andIRFlags
void andIRFlags(const Value *V)
Logical 'and' of any supported wrapping, exact, and fast-math flags of V and this instruction.
Definition: Instruction.cpp:296
llvm::DenseSet
Implements a dense probed hash-table based set.
Definition: DenseSet.h:268
llvm::Use::set
void set(Value *Val)
Definition: Value.h:860
BasicBlock.h
llvm::RISCVFenceField::O
@ O
Definition: RISCVBaseInfo.h:179
llvm::PPC::Predicate
Predicate
Predicate - These are "(BI << 5) | BO" for various predicates.
Definition: PPCPredicates.h:26
llvm::isStrongerThanUnordered
bool isStrongerThanUnordered(AtomicOrdering AO)
Definition: AtomicOrdering.h:120
VI
@ VI
Definition: SIInstrInfo.cpp:7528
llvm::Instruction::eraseFromParent
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Definition: Instruction.cpp:78
llvm::GVN
The core GVN pass object.
Definition: GVN.h:118
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::clear
void clear()
Definition: DenseMap.h:111
INITIALIZE_PASS_DEPENDENCY
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
llvm::PHINode::addIncoming
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
Definition: Instructions.h:2747
llvm::BumpPtrAllocatorImpl
Allocate memory in an ever growing pool, as if by bump-pointer.
Definition: Allocator.h:67
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:57
llvm::DenseMap
Definition: DenseMap.h:714
I
#define I(x, y, z)
Definition: MD5.cpp:59
StringExtras.h
llvm::is_contained
bool is_contained(R &&Range, const E &Element)
Wrapper function around std::find to detect if an element exists in a container.
Definition: STLExtras.h:1599
llvm::initializeGVNSinkLegacyPassPass
void initializeGVNSinkLegacyPassPass(PassRegistry &)
ArrayRef.h
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::find
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:150
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::Recycler
Recycler - This class manages a linked-list of deallocated nodes and facilitates reusing deallocated ...
Definition: Recycler.h:34
llvm::GVNExpression::BasicExpression::allocateOperands
void allocateOperands(RecyclerType &Recycler, BumpPtrAllocator &Allocator)
Definition: GVNExpression.h:202
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::Value::printAsOperand
void printAsOperand(raw_ostream &O, bool PrintType=true, const Module *M=nullptr) const
Print the name of this Value out to the specified raw_ostream.
Definition: AsmWriter.cpp:4670
llvm::SetVector< T, SmallVector< T, N >, SmallDenseSet< T, N > >::insert
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:141
llvm::NVPTXISD::Dummy
@ Dummy
Definition: NVPTXISelLowering.h:60
llvm::operator*
APInt operator*(APInt a, uint64_t RHS)
Definition: APInt.h:2154
llvm::SmallPtrSetImplBase::clear
void clear()
Definition: SmallPtrSet.h:94
sink
gvn sink
When an instruction is found to only be used outside of the loop, this function moves it to the exit ...
Definition: GVNSink.cpp:924
llvm::ArrayRef
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: APInt.h:32
None.h
llvm::any_of
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1541
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:256
llvm::AnalysisUsage::addPreserved
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
Definition: PassAnalysisSupport.h:98
llvm::Value::replaceAllUsesWith
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:520
A
* A
Definition: README_ALTIVEC.txt:89
uint32_t
Compiler.h
llvm::append_range
void append_range(Container &C, Range &&R)
Wrapper function to append a range to a container.
Definition: STLExtras.h:1724
llvm::ilist_node_impl::getIterator
self_iterator getIterator()
Definition: ilist_node.h:81
llvm::GVNExpression::Expression::dump
LLVM_DUMP_METHOD void dump() const
Definition: GVNSink.cpp:91
llvm::GVNExpression::BasicExpression::getHashValue
hash_code getHashValue() const override
Definition: GVNExpression.h:222
llvm::SPII::Store
@ Store
Definition: SparcInstrInfo.h:33
llvm::ArrayRecycler
Recycle small arrays allocated from a BumpPtrAllocator.
Definition: ArrayRecycler.h:28
llvm::BasicBlock::front
const Instruction & front() const
Definition: BasicBlock.h:308
llvm::SetVector< T, SmallVector< T, N >, SmallDenseSet< T, N > >::clear
void clear()
Completely clear the SetVector.
Definition: SetVector.h:220
llvm::MCID::Select
@ Select
Definition: MCInstrDesc.h:162
sinkLastInstruction
static bool sinkLastInstruction(ArrayRef< BasicBlock * > Blocks)
Definition: SimplifyCFG.cpp:1794
operator==
bool operator==(const StringView &LHS, const StringView &RHS)
Definition: StringView.h:112
llvm::stable_sort
void stable_sort(R &&Range)
Definition: STLExtras.h:1669
H
#define H(x, y, z)
Definition: MD5.cpp:58
get
Should compile to something r4 addze r3 instead we get
Definition: README.txt:24
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::end
iterator end()
Definition: DenseMap.h:83
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:314
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:161
Casting.h
Function.h
llvm::sort
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1475
PassManager.h
llvm::GVNExpression::Expression::setOpcode
void setOpcode(unsigned opcode)
Definition: GVNExpression.h:109
llvm::SmallVectorImpl::clear
void clear()
Definition: SmallVector.h:585
isEqual
static bool isEqual(const Function &Caller, const Function &Callee)
Definition: Attributes.cpp:1928
llvm::MCID::Add
@ Add
Definition: MCInstrDesc.h:183
llvm::ReversePostOrderTraversal
Definition: PostOrderIterator.h:290
Predicate
llvm::ShuffleVectorInst
This instruction constructs a fixed permutation of two input vectors.
Definition: Instructions.h:2011
isValid
static bool isValid(const char C)
Returns true if C is a valid mangled character: <0-9a-zA-Z_>.
Definition: RustDemangle.cpp:216
Instructions.h
PostOrderIterator.h
llvm::User::getNumOperands
unsigned getNumOperands() const
Definition: User.h:191
Expressions
gvn Early GVN sinking of Expressions
Definition: GVNSink.cpp:925
SmallVector.h
lookup
static bool lookup(const GsymReader &GR, DataExtractor &Data, uint64_t &Offset, uint64_t BaseAddr, uint64_t Addr, SourceLocations &SrcLocs, llvm::Error &Err)
A Lookup helper functions.
Definition: InlineInfo.cpp:108
llvm::hash_combine
hash_code hash_combine(const Ts &...args)
Combine values into a single hash_code.
Definition: Hashing.h:604
ArrayRecycler.h
Allocator
Basic Register Allocator
Definition: RegAllocBasic.cpp:146
N
#define N
llvm::hash_combine_range
hash_code hash_combine_range(InputIteratorT first, InputIteratorT last)
Compute a hash_code for a sequence of values.
Definition: Hashing.h:482
llvm::Instruction::getParent
const BasicBlock * getParent() const
Definition: Instruction.h:94
llvm::GlobalsAAWrapperPass
Legacy wrapper pass to provide the GlobalsAAResult object.
Definition: GlobalsModRef.h:143
llvm::PHINode::getIncomingBlock
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
Definition: Instructions.h:2713
llvm::operator>
bool operator>(int64_t V1, const APSInt &V2)
Definition: APSInt.h:339
llvm::PHINode
Definition: Instructions.h:2597
llvm::GVNExpression::BasicExpression
Definition: GVNExpression.h:136
DenseMapInfo.h
llvm::Pass::getAnalysisUsage
virtual void getAnalysisUsage(AnalysisUsage &) const
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition: Pass.cpp:93
llvm::SmallPtrSetImpl< Value * >
llvm::SmallSetVector
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:307
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:44
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:298
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
llvm::GVNExpression::BasicExpression::op_begin
op_iterator op_begin()
Definition: GVNExpression.h:184
llvm::User::getOperand
Value * getOperand(unsigned i) const
Definition: User.h:169
raw_ostream.h
BasicBlockUtils.h
Value.h
llvm::GVNExpression::BasicExpression::setType
void setType(Type *T)
Definition: GVNExpression.h:210
InitializePasses.h
llvm::Value
LLVM Value Representation.
Definition: Value.h:75
Debug.h
llvm::Instruction::moveBefore
void moveBefore(Instruction *MovePos)
Unlink this instruction from its current basic block and insert it into the basic block that MovePos ...
Definition: Instruction.cpp:97
Other
Optional< std::vector< StOtherPiece > > Other
Definition: ELFYAML.cpp:1172
of
Add support for conditional and other related patterns Instead of
Definition: README.txt:134
llvm::SmallVectorImpl::emplace_back
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:908
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::hash_code
An opaque object representing a hash code.
Definition: Hashing.h:72