LLVM  15.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/DenseSet.h"
39 #include "llvm/ADT/Hashing.h"
40 #include "llvm/ADT/None.h"
41 #include "llvm/ADT/Optional.h"
43 #include "llvm/ADT/STLExtras.h"
44 #include "llvm/ADT/SmallPtrSet.h"
45 #include "llvm/ADT/SmallVector.h"
46 #include "llvm/ADT/Statistic.h"
48 #include "llvm/IR/BasicBlock.h"
49 #include "llvm/IR/CFG.h"
50 #include "llvm/IR/Constants.h"
51 #include "llvm/IR/Function.h"
52 #include "llvm/IR/InstrTypes.h"
53 #include "llvm/IR/Instruction.h"
54 #include "llvm/IR/Instructions.h"
55 #include "llvm/IR/PassManager.h"
56 #include "llvm/IR/Type.h"
57 #include "llvm/IR/Use.h"
58 #include "llvm/IR/Value.h"
59 #include "llvm/InitializePasses.h"
60 #include "llvm/Pass.h"
61 #include "llvm/Support/Allocator.h"
64 #include "llvm/Support/Casting.h"
65 #include "llvm/Support/Compiler.h"
66 #include "llvm/Support/Debug.h"
68 #include "llvm/Transforms/Scalar.h"
73 #include <algorithm>
74 #include <cassert>
75 #include <cstddef>
76 #include <cstdint>
77 #include <iterator>
78 #include <utility>
79 
80 using namespace llvm;
81 
82 #define DEBUG_TYPE "gvn-sink"
83 
84 STATISTIC(NumRemoved, "Number of instructions removed");
85 
86 namespace llvm {
87 namespace GVNExpression {
88 
90  print(dbgs());
91  dbgs() << "\n";
92 }
93 
94 } // end namespace GVNExpression
95 } // end namespace llvm
96 
97 namespace {
98 
99 static bool isMemoryInst(const Instruction *I) {
100  return isa<LoadInst>(I) || isa<StoreInst>(I) ||
101  (isa<InvokeInst>(I) && !cast<InvokeInst>(I)->doesNotAccessMemory()) ||
102  (isa<CallInst>(I) && !cast<CallInst>(I)->doesNotAccessMemory());
103 }
104 
105 /// Iterates through instructions in a set of blocks in reverse order from the
106 /// first non-terminator. For example (assume all blocks have size n):
107 /// LockstepReverseIterator I([B1, B2, B3]);
108 /// *I-- = [B1[n], B2[n], B3[n]];
109 /// *I-- = [B1[n-1], B2[n-1], B3[n-1]];
110 /// *I-- = [B1[n-2], B2[n-2], B3[n-2]];
111 /// ...
112 ///
113 /// It continues until all blocks have been exhausted. Use \c getActiveBlocks()
114 /// to
115 /// determine which blocks are still going and the order they appear in the
116 /// list returned by operator*.
117 class LockstepReverseIterator {
118  ArrayRef<BasicBlock *> Blocks;
119  SmallSetVector<BasicBlock *, 4> ActiveBlocks;
121  bool Fail;
122 
123 public:
124  LockstepReverseIterator(ArrayRef<BasicBlock *> Blocks) : Blocks(Blocks) {
125  reset();
126  }
127 
128  void reset() {
129  Fail = false;
130  ActiveBlocks.clear();
131  for (BasicBlock *BB : Blocks)
132  ActiveBlocks.insert(BB);
133  Insts.clear();
134  for (BasicBlock *BB : Blocks) {
135  if (BB->size() <= 1) {
136  // Block wasn't big enough - only contained a terminator.
137  ActiveBlocks.remove(BB);
138  continue;
139  }
140  Insts.push_back(BB->getTerminator()->getPrevNode());
141  }
142  if (Insts.empty())
143  Fail = true;
144  }
145 
146  bool isValid() const { return !Fail; }
147  ArrayRef<Instruction *> operator*() const { return Insts; }
148 
149  // Note: This needs to return a SmallSetVector as the elements of
150  // ActiveBlocks will be later copied to Blocks using std::copy. The
151  // resultant order of elements in Blocks needs to be deterministic.
152  // Using SmallPtrSet instead causes non-deterministic order while
153  // copying. And we cannot simply sort Blocks as they need to match the
154  // corresponding Values.
155  SmallSetVector<BasicBlock *, 4> &getActiveBlocks() { return ActiveBlocks; }
156 
157  void restrictToBlocks(SmallSetVector<BasicBlock *, 4> &Blocks) {
158  for (auto II = Insts.begin(); II != Insts.end();) {
159  if (!llvm::is_contained(Blocks, (*II)->getParent())) {
160  ActiveBlocks.remove((*II)->getParent());
161  II = Insts.erase(II);
162  } else {
163  ++II;
164  }
165  }
166  }
167 
168  void operator--() {
169  if (Fail)
170  return;
172  for (auto *Inst : Insts) {
173  if (Inst == &Inst->getParent()->front())
174  ActiveBlocks.remove(Inst->getParent());
175  else
176  NewInsts.push_back(Inst->getPrevNode());
177  }
178  if (NewInsts.empty()) {
179  Fail = true;
180  return;
181  }
182  Insts = NewInsts;
183  }
184 };
185 
186 //===----------------------------------------------------------------------===//
187 
188 /// Candidate solution for sinking. There may be different ways to
189 /// sink instructions, differing in the number of instructions sunk,
190 /// the number of predecessors sunk from and the number of PHIs
191 /// required.
192 struct SinkingInstructionCandidate {
193  unsigned NumBlocks;
194  unsigned NumInstructions;
195  unsigned NumPHIs;
196  unsigned NumMemoryInsts;
197  int Cost = -1;
199 
200  void calculateCost(unsigned NumOrigPHIs, unsigned NumOrigBlocks) {
201  unsigned NumExtraPHIs = NumPHIs - NumOrigPHIs;
202  unsigned SplitEdgeCost = (NumOrigBlocks > NumBlocks) ? 2 : 0;
203  Cost = (NumInstructions * (NumBlocks - 1)) -
204  (NumExtraPHIs *
205  NumExtraPHIs) // PHIs are expensive, so make sure they're worth it.
206  - SplitEdgeCost;
207  }
208 
209  bool operator>(const SinkingInstructionCandidate &Other) const {
210  return Cost > Other.Cost;
211  }
212 };
213 
214 #ifndef NDEBUG
215 raw_ostream &operator<<(raw_ostream &OS, const SinkingInstructionCandidate &C) {
216  OS << "<Candidate Cost=" << C.Cost << " #Blocks=" << C.NumBlocks
217  << " #Insts=" << C.NumInstructions << " #PHIs=" << C.NumPHIs << ">";
218  return OS;
219 }
220 #endif
221 
222 //===----------------------------------------------------------------------===//
223 
224 /// Describes a PHI node that may or may not exist. These track the PHIs
225 /// that must be created if we sunk a sequence of instructions. It provides
226 /// a hash function for efficient equality comparisons.
227 class ModelledPHI {
230 
231 public:
232  ModelledPHI() = default;
233 
234  ModelledPHI(const PHINode *PN) {
235  // BasicBlock comes first so we sort by basic block pointer order, then by value pointer order.
237  for (unsigned I = 0, E = PN->getNumIncomingValues(); I != E; ++I)
238  Ops.push_back({PN->getIncomingBlock(I), PN->getIncomingValue(I)});
239  llvm::sort(Ops);
240  for (auto &P : Ops) {
241  Blocks.push_back(P.first);
242  Values.push_back(P.second);
243  }
244  }
245 
246  /// Create a dummy ModelledPHI that will compare unequal to any other ModelledPHI
247  /// without the same ID.
248  /// \note This is specifically for DenseMapInfo - do not use this!
249  static ModelledPHI createDummy(size_t ID) {
250  ModelledPHI M;
251  M.Values.push_back(reinterpret_cast<Value*>(ID));
252  return M;
253  }
254 
255  /// Create a PHI from an array of incoming values and incoming blocks.
256  template <typename VArray, typename BArray>
257  ModelledPHI(const VArray &V, const BArray &B) {
258  llvm::copy(V, std::back_inserter(Values));
259  llvm::copy(B, std::back_inserter(Blocks));
260  }
261 
262  /// Create a PHI from [I[OpNum] for I in Insts].
263  template <typename BArray>
264  ModelledPHI(ArrayRef<Instruction *> Insts, unsigned OpNum, const BArray &B) {
265  llvm::copy(B, std::back_inserter(Blocks));
266  for (auto *I : Insts)
267  Values.push_back(I->getOperand(OpNum));
268  }
269 
270  /// Restrict the PHI's contents down to only \c NewBlocks.
271  /// \c NewBlocks must be a subset of \c this->Blocks.
272  void restrictToBlocks(const SmallSetVector<BasicBlock *, 4> &NewBlocks) {
273  auto BI = Blocks.begin();
274  auto VI = Values.begin();
275  while (BI != Blocks.end()) {
276  assert(VI != Values.end());
277  if (!llvm::is_contained(NewBlocks, *BI)) {
278  BI = Blocks.erase(BI);
279  VI = Values.erase(VI);
280  } else {
281  ++BI;
282  ++VI;
283  }
284  }
285  assert(Blocks.size() == NewBlocks.size());
286  }
287 
288  ArrayRef<Value *> getValues() const { return Values; }
289 
290  bool areAllIncomingValuesSame() const {
291  return llvm::all_of(Values, [&](Value *V) { return V == Values[0]; });
292  }
293 
294  bool areAllIncomingValuesSameType() const {
295  return llvm::all_of(
296  Values, [&](Value *V) { return V->getType() == Values[0]->getType(); });
297  }
298 
299  bool areAnyIncomingValuesConstant() const {
300  return llvm::any_of(Values, [&](Value *V) { return isa<Constant>(V); });
301  }
302 
303  // Hash functor
304  unsigned hash() const {
305  return (unsigned)hash_combine_range(Values.begin(), Values.end());
306  }
307 
308  bool operator==(const ModelledPHI &Other) const {
309  return Values == Other.Values && Blocks == Other.Blocks;
310  }
311 };
312 
313 template <typename ModelledPHI> struct DenseMapInfo {
314  static inline ModelledPHI &getEmptyKey() {
315  static ModelledPHI Dummy = ModelledPHI::createDummy(0);
316  return Dummy;
317  }
318 
319  static inline ModelledPHI &getTombstoneKey() {
320  static ModelledPHI Dummy = ModelledPHI::createDummy(1);
321  return Dummy;
322  }
323 
324  static unsigned getHashValue(const ModelledPHI &V) { return V.hash(); }
325 
326  static bool isEqual(const ModelledPHI &LHS, const ModelledPHI &RHS) {
327  return LHS == RHS;
328  }
329 };
330 
332 
333 //===----------------------------------------------------------------------===//
334 // ValueTable
335 //===----------------------------------------------------------------------===//
336 // This is a value number table where the value number is a function of the
337 // *uses* of a value, rather than its operands. Thus, if VN(A) == VN(B) we know
338 // that the program would be equivalent if we replaced A with PHI(A, B).
339 //===----------------------------------------------------------------------===//
340 
341 /// A GVN expression describing how an instruction is used. The operands
342 /// field of BasicExpression is used to store uses, not operands.
343 ///
344 /// This class also contains fields for discriminators used when determining
345 /// equivalence of instructions with sideeffects.
346 class InstructionUseExpr : public GVNExpression::BasicExpression {
347  unsigned MemoryUseOrder = -1;
348  bool Volatile = false;
349  ArrayRef<int> ShuffleMask;
350 
351 public:
352  InstructionUseExpr(Instruction *I, ArrayRecycler<Value *> &R,
354  : GVNExpression::BasicExpression(I->getNumUses()) {
355  allocateOperands(R, A);
356  setOpcode(I->getOpcode());
357  setType(I->getType());
358 
359  if (ShuffleVectorInst *SVI = dyn_cast<ShuffleVectorInst>(I))
360  ShuffleMask = SVI->getShuffleMask().copy(A);
361 
362  for (auto &U : I->uses())
363  op_push_back(U.getUser());
364  llvm::sort(op_begin(), op_end());
365  }
366 
367  void setMemoryUseOrder(unsigned MUO) { MemoryUseOrder = MUO; }
368  void setVolatile(bool V) { Volatile = V; }
369 
370  hash_code getHashValue() const override {
371  return hash_combine(GVNExpression::BasicExpression::getHashValue(),
372  MemoryUseOrder, Volatile, ShuffleMask);
373  }
374 
375  template <typename Function> hash_code getHashValue(Function MapFn) {
376  hash_code H = hash_combine(getOpcode(), getType(), MemoryUseOrder, Volatile,
377  ShuffleMask);
378  for (auto *V : operands())
379  H = hash_combine(H, MapFn(V));
380  return H;
381  }
382 };
383 
384 using BasicBlocksSet = SmallPtrSet<const BasicBlock *, 32>;
385 
386 class ValueTable {
387  DenseMap<Value *, uint32_t> ValueNumbering;
389  DenseMap<size_t, uint32_t> HashNumbering;
392  uint32_t nextValueNumber = 1;
393  BasicBlocksSet ReachableBBs;
394 
395  /// Create an expression for I based on its opcode and its uses. If I
396  /// touches or reads memory, the expression is also based upon its memory
397  /// order - see \c getMemoryUseOrder().
398  InstructionUseExpr *createExpr(Instruction *I) {
399  InstructionUseExpr *E =
400  new (Allocator) InstructionUseExpr(I, Recycler, Allocator);
401  if (isMemoryInst(I))
402  E->setMemoryUseOrder(getMemoryUseOrder(I));
403 
404  if (CmpInst *C = dyn_cast<CmpInst>(I)) {
405  CmpInst::Predicate Predicate = C->getPredicate();
406  E->setOpcode((C->getOpcode() << 8) | Predicate);
407  }
408  return E;
409  }
410 
411  /// Helper to compute the value number for a memory instruction
412  /// (LoadInst/StoreInst), including checking the memory ordering and
413  /// volatility.
414  template <class Inst> InstructionUseExpr *createMemoryExpr(Inst *I) {
415  if (isStrongerThanUnordered(I->getOrdering()) || I->isAtomic())
416  return nullptr;
417  InstructionUseExpr *E = createExpr(I);
418  E->setVolatile(I->isVolatile());
419  return E;
420  }
421 
422 public:
423  ValueTable() = default;
424 
425  /// Set basic blocks reachable from entry block.
426  void setReachableBBs(const BasicBlocksSet &ReachableBBs) {
427  this->ReachableBBs = ReachableBBs;
428  }
429 
430  /// Returns the value number for the specified value, assigning
431  /// it a new number if it did not have one before.
432  uint32_t lookupOrAdd(Value *V) {
433  auto VI = ValueNumbering.find(V);
434  if (VI != ValueNumbering.end())
435  return VI->second;
436 
437  if (!isa<Instruction>(V)) {
438  ValueNumbering[V] = nextValueNumber;
439  return nextValueNumber++;
440  }
441 
442  Instruction *I = cast<Instruction>(V);
443  if (!ReachableBBs.contains(I->getParent()))
444  return ~0U;
445 
446  InstructionUseExpr *exp = nullptr;
447  switch (I->getOpcode()) {
448  case Instruction::Load:
449  exp = createMemoryExpr(cast<LoadInst>(I));
450  break;
451  case Instruction::Store:
452  exp = createMemoryExpr(cast<StoreInst>(I));
453  break;
454  case Instruction::Call:
455  case Instruction::Invoke:
456  case Instruction::FNeg:
457  case Instruction::Add:
458  case Instruction::FAdd:
459  case Instruction::Sub:
460  case Instruction::FSub:
461  case Instruction::Mul:
462  case Instruction::FMul:
463  case Instruction::UDiv:
464  case Instruction::SDiv:
465  case Instruction::FDiv:
466  case Instruction::URem:
467  case Instruction::SRem:
468  case Instruction::FRem:
469  case Instruction::Shl:
470  case Instruction::LShr:
471  case Instruction::AShr:
472  case Instruction::And:
473  case Instruction::Or:
474  case Instruction::Xor:
475  case Instruction::ICmp:
476  case Instruction::FCmp:
477  case Instruction::Trunc:
478  case Instruction::ZExt:
479  case Instruction::SExt:
480  case Instruction::FPToUI:
481  case Instruction::FPToSI:
482  case Instruction::UIToFP:
483  case Instruction::SIToFP:
484  case Instruction::FPTrunc:
485  case Instruction::FPExt:
486  case Instruction::PtrToInt:
487  case Instruction::IntToPtr:
488  case Instruction::BitCast:
489  case Instruction::AddrSpaceCast:
490  case Instruction::Select:
491  case Instruction::ExtractElement:
492  case Instruction::InsertElement:
493  case Instruction::ShuffleVector:
494  case Instruction::InsertValue:
495  case Instruction::GetElementPtr:
496  exp = createExpr(I);
497  break;
498  default:
499  break;
500  }
501 
502  if (!exp) {
503  ValueNumbering[V] = nextValueNumber;
504  return nextValueNumber++;
505  }
506 
507  uint32_t e = ExpressionNumbering[exp];
508  if (!e) {
509  hash_code H = exp->getHashValue([=](Value *V) { return lookupOrAdd(V); });
510  auto I = HashNumbering.find(H);
511  if (I != HashNumbering.end()) {
512  e = I->second;
513  } else {
514  e = nextValueNumber++;
515  HashNumbering[H] = e;
516  ExpressionNumbering[exp] = e;
517  }
518  }
519  ValueNumbering[V] = e;
520  return e;
521  }
522 
523  /// Returns the value number of the specified value. Fails if the value has
524  /// not yet been numbered.
525  uint32_t lookup(Value *V) const {
526  auto VI = ValueNumbering.find(V);
527  assert(VI != ValueNumbering.end() && "Value not numbered?");
528  return VI->second;
529  }
530 
531  /// Removes all value numberings and resets the value table.
532  void clear() {
533  ValueNumbering.clear();
534  ExpressionNumbering.clear();
535  HashNumbering.clear();
537  nextValueNumber = 1;
538  }
539 
540  /// \c Inst uses or touches memory. Return an ID describing the memory state
541  /// at \c Inst such that if getMemoryUseOrder(I1) == getMemoryUseOrder(I2),
542  /// the exact same memory operations happen after I1 and I2.
543  ///
544  /// This is a very hard problem in general, so we use domain-specific
545  /// knowledge that we only ever check for equivalence between blocks sharing a
546  /// single immediate successor that is common, and when determining if I1 ==
547  /// I2 we will have already determined that next(I1) == next(I2). This
548  /// inductive property allows us to simply return the value number of the next
549  /// instruction that defines memory.
550  uint32_t getMemoryUseOrder(Instruction *Inst) {
551  auto *BB = Inst->getParent();
552  for (auto I = std::next(Inst->getIterator()), E = BB->end();
553  I != E && !I->isTerminator(); ++I) {
554  if (!isMemoryInst(&*I))
555  continue;
556  if (isa<LoadInst>(&*I))
557  continue;
558  CallInst *CI = dyn_cast<CallInst>(&*I);
559  if (CI && CI->onlyReadsMemory())
560  continue;
561  InvokeInst *II = dyn_cast<InvokeInst>(&*I);
562  if (II && II->onlyReadsMemory())
563  continue;
564  return lookupOrAdd(&*I);
565  }
566  return 0;
567  }
568 };
569 
570 //===----------------------------------------------------------------------===//
571 
572 class GVNSink {
573 public:
574  GVNSink() = default;
575 
576  bool run(Function &F) {
577  LLVM_DEBUG(dbgs() << "GVNSink: running on function @" << F.getName()
578  << "\n");
579 
580  unsigned NumSunk = 0;
582  VN.setReachableBBs(BasicBlocksSet(RPOT.begin(), RPOT.end()));
583  for (auto *N : RPOT)
584  NumSunk += sinkBB(N);
585 
586  return NumSunk > 0;
587  }
588 
589 private:
590  ValueTable VN;
591 
592  bool shouldAvoidSinkingInstruction(Instruction *I) {
593  // These instructions may change or break semantics if moved.
594  if (isa<PHINode>(I) || I->isEHPad() || isa<AllocaInst>(I) ||
595  I->getType()->isTokenTy())
596  return true;
597  return false;
598  }
599 
600  /// The main heuristic function. Analyze the set of instructions pointed to by
601  /// LRI and return a candidate solution if these instructions can be sunk, or
602  /// None otherwise.
603  Optional<SinkingInstructionCandidate> analyzeInstructionForSinking(
604  LockstepReverseIterator &LRI, unsigned &InstNum, unsigned &MemoryInstNum,
605  ModelledPHISet &NeededPHIs, SmallPtrSetImpl<Value *> &PHIContents);
606 
607  /// Create a ModelledPHI for each PHI in BB, adding to PHIs.
608  void analyzeInitialPHIs(BasicBlock *BB, ModelledPHISet &PHIs,
609  SmallPtrSetImpl<Value *> &PHIContents) {
610  for (PHINode &PN : BB->phis()) {
611  auto MPHI = ModelledPHI(&PN);
612  PHIs.insert(MPHI);
613  for (auto *V : MPHI.getValues())
614  PHIContents.insert(V);
615  }
616  }
617 
618  /// The main instruction sinking driver. Set up state and try and sink
619  /// instructions into BBEnd from its predecessors.
620  unsigned sinkBB(BasicBlock *BBEnd);
621 
622  /// Perform the actual mechanics of sinking an instruction from Blocks into
623  /// BBEnd, which is their only successor.
625 
626  /// Remove PHIs that all have the same incoming value.
627  void foldPointlessPHINodes(BasicBlock *BB) {
628  auto I = BB->begin();
629  while (PHINode *PN = dyn_cast<PHINode>(I++)) {
630  if (!llvm::all_of(PN->incoming_values(), [&](const Value *V) {
631  return V == PN->getIncomingValue(0);
632  }))
633  continue;
634  if (PN->getIncomingValue(0) != PN)
636  else
638  PN->eraseFromParent();
639  }
640  }
641 };
642 
643 Optional<SinkingInstructionCandidate> GVNSink::analyzeInstructionForSinking(
644  LockstepReverseIterator &LRI, unsigned &InstNum, unsigned &MemoryInstNum,
645  ModelledPHISet &NeededPHIs, SmallPtrSetImpl<Value *> &PHIContents) {
646  auto Insts = *LRI;
647  LLVM_DEBUG(dbgs() << " -- Analyzing instruction set: [\n"; for (auto *I
648  : Insts) {
649  I->dump();
650  } dbgs() << " ]\n";);
651 
653  for (auto *I : Insts) {
654  uint32_t N = VN.lookupOrAdd(I);
655  LLVM_DEBUG(dbgs() << " VN=" << Twine::utohexstr(N) << " for" << *I << "\n");
656  if (N == ~0U)
657  return None;
658  VNums[N]++;
659  }
660  unsigned VNumToSink =
661  std::max_element(VNums.begin(), VNums.end(),
662  [](const std::pair<uint32_t, unsigned> &I,
663  const std::pair<uint32_t, unsigned> &J) {
664  return I.second < J.second;
665  })
666  ->first;
667 
668  if (VNums[VNumToSink] == 1)
669  // Can't sink anything!
670  return None;
671 
672  // Now restrict the number of incoming blocks down to only those with
673  // VNumToSink.
674  auto &ActivePreds = LRI.getActiveBlocks();
675  unsigned InitialActivePredSize = ActivePreds.size();
677  for (auto *I : Insts) {
678  if (VN.lookup(I) != VNumToSink)
679  ActivePreds.remove(I->getParent());
680  else
681  NewInsts.push_back(I);
682  }
683  for (auto *I : NewInsts)
684  if (shouldAvoidSinkingInstruction(I))
685  return None;
686 
687  // If we've restricted the incoming blocks, restrict all needed PHIs also
688  // to that set.
689  bool RecomputePHIContents = false;
690  if (ActivePreds.size() != InitialActivePredSize) {
691  ModelledPHISet NewNeededPHIs;
692  for (auto P : NeededPHIs) {
693  P.restrictToBlocks(ActivePreds);
694  NewNeededPHIs.insert(P);
695  }
696  NeededPHIs = NewNeededPHIs;
697  LRI.restrictToBlocks(ActivePreds);
698  RecomputePHIContents = true;
699  }
700 
701  // The sunk instruction's results.
702  ModelledPHI NewPHI(NewInsts, ActivePreds);
703 
704  // Does sinking this instruction render previous PHIs redundant?
705  if (NeededPHIs.erase(NewPHI))
706  RecomputePHIContents = true;
707 
708  if (RecomputePHIContents) {
709  // The needed PHIs have changed, so recompute the set of all needed
710  // values.
711  PHIContents.clear();
712  for (auto &PHI : NeededPHIs)
713  PHIContents.insert(PHI.getValues().begin(), PHI.getValues().end());
714  }
715 
716  // Is this instruction required by a later PHI that doesn't match this PHI?
717  // if so, we can't sink this instruction.
718  for (auto *V : NewPHI.getValues())
719  if (PHIContents.count(V))
720  // V exists in this PHI, but the whole PHI is different to NewPHI
721  // (else it would have been removed earlier). We cannot continue
722  // because this isn't representable.
723  return None;
724 
725  // Which operands need PHIs?
726  // FIXME: If any of these fail, we should partition up the candidates to
727  // try and continue making progress.
728  Instruction *I0 = NewInsts[0];
729 
730  // If all instructions that are going to participate don't have the same
731  // number of operands, we can't do any useful PHI analysis for all operands.
732  auto hasDifferentNumOperands = [&I0](Instruction *I) {
733  return I->getNumOperands() != I0->getNumOperands();
734  };
735  if (any_of(NewInsts, hasDifferentNumOperands))
736  return None;
737 
738  for (unsigned OpNum = 0, E = I0->getNumOperands(); OpNum != E; ++OpNum) {
739  ModelledPHI PHI(NewInsts, OpNum, ActivePreds);
740  if (PHI.areAllIncomingValuesSame())
741  continue;
742  if (!canReplaceOperandWithVariable(I0, OpNum))
743  // We can 't create a PHI from this instruction!
744  return None;
745  if (NeededPHIs.count(PHI))
746  continue;
747  if (!PHI.areAllIncomingValuesSameType())
748  return None;
749  // Don't create indirect calls! The called value is the final operand.
750  if ((isa<CallInst>(I0) || isa<InvokeInst>(I0)) && OpNum == E - 1 &&
751  PHI.areAnyIncomingValuesConstant())
752  return None;
753 
754  NeededPHIs.reserve(NeededPHIs.size());
755  NeededPHIs.insert(PHI);
756  PHIContents.insert(PHI.getValues().begin(), PHI.getValues().end());
757  }
758 
759  if (isMemoryInst(NewInsts[0]))
760  ++MemoryInstNum;
761 
762  SinkingInstructionCandidate Cand;
763  Cand.NumInstructions = ++InstNum;
764  Cand.NumMemoryInsts = MemoryInstNum;
765  Cand.NumBlocks = ActivePreds.size();
766  Cand.NumPHIs = NeededPHIs.size();
767  append_range(Cand.Blocks, ActivePreds);
768 
769  return Cand;
770 }
771 
772 unsigned GVNSink::sinkBB(BasicBlock *BBEnd) {
773  LLVM_DEBUG(dbgs() << "GVNSink: running on basic block ";
774  BBEnd->printAsOperand(dbgs()); dbgs() << "\n");
776  for (auto *B : predecessors(BBEnd)) {
777  auto *T = B->getTerminator();
778  if (isa<BranchInst>(T) || isa<SwitchInst>(T))
779  Preds.push_back(B);
780  else
781  return 0;
782  }
783  if (Preds.size() < 2)
784  return 0;
785  llvm::sort(Preds);
786 
787  unsigned NumOrigPreds = Preds.size();
788  // We can only sink instructions through unconditional branches.
789  llvm::erase_if(Preds, [](BasicBlock *BB) {
790  return BB->getTerminator()->getNumSuccessors() != 1;
791  });
792 
793  LockstepReverseIterator LRI(Preds);
795  unsigned InstNum = 0, MemoryInstNum = 0;
796  ModelledPHISet NeededPHIs;
797  SmallPtrSet<Value *, 4> PHIContents;
798  analyzeInitialPHIs(BBEnd, NeededPHIs, PHIContents);
799  unsigned NumOrigPHIs = NeededPHIs.size();
800 
801  while (LRI.isValid()) {
802  auto Cand = analyzeInstructionForSinking(LRI, InstNum, MemoryInstNum,
803  NeededPHIs, PHIContents);
804  if (!Cand)
805  break;
806  Cand->calculateCost(NumOrigPHIs, Preds.size());
807  Candidates.emplace_back(*Cand);
808  --LRI;
809  }
810 
811  llvm::stable_sort(Candidates, std::greater<SinkingInstructionCandidate>());
812  LLVM_DEBUG(dbgs() << " -- Sinking candidates:\n"; for (auto &C
813  : Candidates) dbgs()
814  << " " << C << "\n";);
815 
816  // Pick the top candidate, as long it is positive!
817  if (Candidates.empty() || Candidates.front().Cost <= 0)
818  return 0;
819  auto C = Candidates.front();
820 
821  LLVM_DEBUG(dbgs() << " -- Sinking: " << C << "\n");
822  BasicBlock *InsertBB = BBEnd;
823  if (C.Blocks.size() < NumOrigPreds) {
824  LLVM_DEBUG(dbgs() << " -- Splitting edge to ";
825  BBEnd->printAsOperand(dbgs()); dbgs() << "\n");
826  InsertBB = SplitBlockPredecessors(BBEnd, C.Blocks, ".gvnsink.split");
827  if (!InsertBB) {
828  LLVM_DEBUG(dbgs() << " -- FAILED to split edge!\n");
829  // Edge couldn't be split.
830  return 0;
831  }
832  }
833 
834  for (unsigned I = 0; I < C.NumInstructions; ++I)
835  sinkLastInstruction(C.Blocks, InsertBB);
836 
837  return C.NumInstructions;
838 }
839 
841  BasicBlock *BBEnd) {
843  for (BasicBlock *BB : Blocks)
844  Insts.push_back(BB->getTerminator()->getPrevNode());
845  Instruction *I0 = Insts.front();
846 
847  SmallVector<Value *, 4> NewOperands;
848  for (unsigned O = 0, E = I0->getNumOperands(); O != E; ++O) {
849  bool NeedPHI = llvm::any_of(Insts, [&I0, O](const Instruction *I) {
850  return I->getOperand(O) != I0->getOperand(O);
851  });
852  if (!NeedPHI) {
853  NewOperands.push_back(I0->getOperand(O));
854  continue;
855  }
856 
857  // Create a new PHI in the successor block and populate it.
858  auto *Op = I0->getOperand(O);
859  assert(!Op->getType()->isTokenTy() && "Can't PHI tokens!");
860  auto *PN = PHINode::Create(Op->getType(), Insts.size(),
861  Op->getName() + ".sink", &BBEnd->front());
862  for (auto *I : Insts)
863  PN->addIncoming(I->getOperand(O), I->getParent());
864  NewOperands.push_back(PN);
865  }
866 
867  // Arbitrarily use I0 as the new "common" instruction; remap its operands
868  // and move it to the start of the successor block.
869  for (unsigned O = 0, E = I0->getNumOperands(); O != E; ++O)
870  I0->getOperandUse(O).set(NewOperands[O]);
871  I0->moveBefore(&*BBEnd->getFirstInsertionPt());
872 
873  // Update metadata and IR flags.
874  for (auto *I : Insts)
875  if (I != I0) {
876  combineMetadataForCSE(I0, I, true);
877  I0->andIRFlags(I);
878  }
879 
880  for (auto *I : Insts)
881  if (I != I0)
882  I->replaceAllUsesWith(I0);
883  foldPointlessPHINodes(BBEnd);
884 
885  // Finally nuke all instructions apart from the common instruction.
886  for (auto *I : Insts)
887  if (I != I0)
888  I->eraseFromParent();
889 
890  NumRemoved += Insts.size() - 1;
891 }
892 
893 ////////////////////////////////////////////////////////////////////////////////
894 // Pass machinery / boilerplate
895 
896 class GVNSinkLegacyPass : public FunctionPass {
897 public:
898  static char ID;
899 
900  GVNSinkLegacyPass() : FunctionPass(ID) {
901  initializeGVNSinkLegacyPassPass(*PassRegistry::getPassRegistry());
902  }
903 
904  bool runOnFunction(Function &F) override {
905  if (skipFunction(F))
906  return false;
907  GVNSink G;
908  return G.run(F);
909  }
910 
911  void getAnalysisUsage(AnalysisUsage &AU) const override {
913  }
914 };
915 
916 } // end anonymous namespace
917 
919  GVNSink G;
920  if (!G.run(F))
921  return PreservedAnalyses::all();
922  return PreservedAnalyses::none();
923 }
924 
925 char GVNSinkLegacyPass::ID = 0;
926 
927 INITIALIZE_PASS_BEGIN(GVNSinkLegacyPass, "gvn-sink",
928  "Early GVN sinking of Expressions", false, false)
931 INITIALIZE_PASS_END(GVNSinkLegacyPass, "gvn-sink",
933 
934 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:152
llvm::GVNExpression::BasicExpression::op_end
op_iterator op_end()
Definition: GVNExpression.h:185
llvm::createGVNSinkPass
FunctionPass * createGVNSinkPass()
Definition: GVNSink.cpp:934
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:494
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
llvm::SmallVectorImpl::erase
iterator erase(const_iterator CI)
Definition: SmallVector.h:724
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:2750
llvm::CmpInst::Predicate
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:719
AtomicOrdering.h
Scalar.h
T
llvm::Function
Definition: Function.h:60
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:1185
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:173
Allocator.h
llvm::erase_if
void erase_if(Container &C, UnaryPredicate P)
Provide a container algorithm similar to C++ Library Fundamentals v2's erase_if which is equivalent t...
Definition: STLExtras.h:1797
Local.h
Fail
#define Fail
Definition: AArch64Disassembler.cpp:281
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:155
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:1658
llvm::Optional
Definition: APInt.h:33
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:450
Hashing.h
STLExtras.h
RHS
Value * RHS
Definition: X86PartialReduction.cpp:76
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:2603
sinking
Machine code sinking
Definition: MachineSink.cpp:269
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
F
#define F(x, y, z)
Definition: MD5.cpp:55
llvm::RISCVFenceField::R
@ R
Definition: RISCVBaseInfo.h:240
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:55
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:149
llvm::User::getOperandUse
const Use & getOperandUse(unsigned i) const
Definition: User.h:182
Instruction.h
llvm::SPII::Load
@ Load
Definition: SparcInstrInfo.h:32
LHS
Value * LHS
Definition: X86PartialReduction.cpp:75
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:1366
llvm::DenseMapInfo
An information struct used to provide DenseMap with the various necessary components for a given valu...
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:1607
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:2760
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:3267
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:246
false
Definition: StackSlotColoring.cpp:141
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
llvm::Instruction
Definition: Instruction.h:42
llvm::DominatorTreeWrapperPass
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:302
GVNExpression.h
llvm::STATISTIC
STATISTIC(NumFunctions, "Total number of functions")
llvm::predecessors
auto predecessors(MachineBasicBlock *BB)
Definition: MachineSSAContext.h:30
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:54
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:1176
llvm::MCID::Call
@ Call
Definition: MCInstrDesc.h:155
llvm::SPII::Store
@ Store
Definition: SparcInstrInfo.h:33
llvm::PHINode::getNumIncomingValues
unsigned getNumIncomingValues() const
Return the number of incoming edges.
Definition: Instructions.h:2756
llvm::None
const NoneType None
Definition: None.h:24
llvm::GVNExpression::BasicExpression::op_push_back
void op_push_back(Value *Arg)
Definition: GVNExpression.h:195
llvm::CallingConv::ID
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
llvm::CallBase::onlyReadsMemory
bool onlyReadsMemory(unsigned OpNo) const
Definition: InstrTypes.h:1720
Type.h
INITIALIZE_PASS_END
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:58
CFG.h
llvm::dxil::PointerTypeAnalysis::run
PointerTypeMap run(const Module &M)
Compute the PointerTypeMap for the module M.
Definition: PointerTypeAnalysis.cpp:101
llvm::GVNExpression::BasicExpression::getType
Type * getType() const
Definition: GVNExpression.h:211
llvm::InvokeInst
Invoke instruction.
Definition: Instructions.h:3776
llvm::CmpInst
This class is the base class for the comparison instructions.
Definition: InstrTypes.h:709
G
const DataFlowGraph & G
Definition: RDFGraph.cpp:200
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:322
llvm::DenseSet
Implements a dense probed hash-table based set.
Definition: DenseSet.h:268
llvm::Use::set
void set(Value *Val)
Definition: Value.h:868
BasicBlock.h
llvm::RISCVFenceField::O
@ O
Definition: RISCVBaseInfo.h:239
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:7842
llvm::Instruction::eraseFromParent
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Definition: Instruction.cpp:77
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:112
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:2814
llvm::BumpPtrAllocatorImpl
Allocate memory in an ever growing pool, as if by bump-pointer.
Definition: Allocator.h:63
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:57
llvm::DenseMap
Definition: DenseMap.h:716
I
#define I(x, y, z)
Definition: MD5.cpp:58
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:1672
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:152
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::operator==
bool operator==(uint64_t V1, const APInt &V2)
Definition: APInt.h:2002
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:383
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:4662
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:2126
llvm::SmallPtrSetImplBase::clear
void clear()
Definition: SmallPtrSet.h:95
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:931
llvm::ArrayRef
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: APInt.h:32
None.h
Mul
BinaryOperator * Mul
Definition: X86PartialReduction.cpp:70
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:1614
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
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:529
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:1813
llvm::ilist_node_impl::getIterator
self_iterator getIterator()
Definition: ilist_node.h:82
llvm::GVNExpression::Expression::dump
LLVM_DUMP_METHOD void dump() const
Definition: GVNSink.cpp:89
llvm::GVNExpression::BasicExpression::getHashValue
hash_code getHashValue() const override
Definition: GVNExpression.h:222
llvm::ArrayRecycler
Recycle small arrays allocated from a BumpPtrAllocator.
Definition: ArrayRecycler.h:28
llvm::BasicBlock::front
const Instruction & front() const
Definition: BasicBlock.h:309
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:164
sinkLastInstruction
static bool sinkLastInstruction(ArrayRef< BasicBlock * > Blocks)
Definition: SimplifyCFG.cpp:1840
llvm::stable_sort
void stable_sort(R &&Range)
Definition: STLExtras.h:1751
H
#define H(x, y, z)
Definition: MD5.cpp:57
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:84
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:344
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:158
Casting.h
Function.h
llvm::sort
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1552
PassManager.h
llvm::GVNExpression::Expression::setOpcode
void setOpcode(unsigned opcode)
Definition: GVNExpression.h:109
llvm::SmallVectorImpl::clear
void clear()
Definition: SmallVector.h:591
isEqual
static bool isEqual(const Function &Caller, const Function &Callee)
Definition: Attributes.cpp:1834
llvm::MCID::Add
@ Add
Definition: MCInstrDesc.h:185
LiveDebugValues::ValueTable
std::unique_ptr< ValueIDNum[]> ValueTable
Type for a table of values in a block.
Definition: InstrRefBasedImpl.h:172
llvm::ReversePostOrderTraversal
Definition: PostOrderIterator.h:291
llvm::ShuffleVectorInst
This instruction constructs a fixed permutation of two input vectors.
Definition: Instructions.h:2008
isValid
static bool isValid(const char C)
Returns true if C is a valid mangled character: <0-9a-zA-Z_>.
Definition: RustDemangle.cpp:187
Instructions.h
PostOrderIterator.h
llvm::User::getNumOperands
unsigned getNumOperands() const
Definition: User.h:191
Expressions
gvn Early GVN sinking of Expressions
Definition: GVNSink.cpp:932
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:605
ArrayRecycler.h
Allocator
Basic Register Allocator
Definition: RegAllocBasic.cpp:142
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:483
llvm::Instruction::getParent
const BasicBlock * getParent() const
Definition: Instruction.h:91
llvm::GlobalsAAWrapperPass
Legacy wrapper pass to provide the GlobalsAAResult object.
Definition: GlobalsModRef.h:148
llvm::PHINode::getIncomingBlock
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
Definition: Instructions.h:2780
llvm::operator>
bool operator>(int64_t V1, const APSInt &V2)
Definition: APSInt.h:340
llvm::PHINode
Definition: Instructions.h:2664
llvm::GVNExpression::BasicExpression
Definition: GVNExpression.h:136
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:97
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:42
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:308
llvm::CallInst
This class represents a function call, abstracting a target machine's calling convention.
Definition: Instructions.h:1474
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
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:74
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:96
Other
Optional< std::vector< StOtherPiece > > Other
Definition: ELFYAML.cpp:1236
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:927
llvm::SmallPtrSetImpl::insert
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:365
llvm::ArrayRef::copy
MutableArrayRef< T > copy(Allocator &A)
Definition: ArrayRef.h:179
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:37
llvm::hash_code
An opaque object representing a hash code.
Definition: Hashing.h:73