LLVM  16.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_equal(Values);
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 std::nullopt;
658  VNums[N]++;
659  }
660  unsigned VNumToSink =
661  std::max_element(VNums.begin(), VNums.end(), llvm::less_second())->first;
662 
663  if (VNums[VNumToSink] == 1)
664  // Can't sink anything!
665  return std::nullopt;
666 
667  // Now restrict the number of incoming blocks down to only those with
668  // VNumToSink.
669  auto &ActivePreds = LRI.getActiveBlocks();
670  unsigned InitialActivePredSize = ActivePreds.size();
672  for (auto *I : Insts) {
673  if (VN.lookup(I) != VNumToSink)
674  ActivePreds.remove(I->getParent());
675  else
676  NewInsts.push_back(I);
677  }
678  for (auto *I : NewInsts)
679  if (shouldAvoidSinkingInstruction(I))
680  return std::nullopt;
681 
682  // If we've restricted the incoming blocks, restrict all needed PHIs also
683  // to that set.
684  bool RecomputePHIContents = false;
685  if (ActivePreds.size() != InitialActivePredSize) {
686  ModelledPHISet NewNeededPHIs;
687  for (auto P : NeededPHIs) {
688  P.restrictToBlocks(ActivePreds);
689  NewNeededPHIs.insert(P);
690  }
691  NeededPHIs = NewNeededPHIs;
692  LRI.restrictToBlocks(ActivePreds);
693  RecomputePHIContents = true;
694  }
695 
696  // The sunk instruction's results.
697  ModelledPHI NewPHI(NewInsts, ActivePreds);
698 
699  // Does sinking this instruction render previous PHIs redundant?
700  if (NeededPHIs.erase(NewPHI))
701  RecomputePHIContents = true;
702 
703  if (RecomputePHIContents) {
704  // The needed PHIs have changed, so recompute the set of all needed
705  // values.
706  PHIContents.clear();
707  for (auto &PHI : NeededPHIs)
708  PHIContents.insert(PHI.getValues().begin(), PHI.getValues().end());
709  }
710 
711  // Is this instruction required by a later PHI that doesn't match this PHI?
712  // if so, we can't sink this instruction.
713  for (auto *V : NewPHI.getValues())
714  if (PHIContents.count(V))
715  // V exists in this PHI, but the whole PHI is different to NewPHI
716  // (else it would have been removed earlier). We cannot continue
717  // because this isn't representable.
718  return std::nullopt;
719 
720  // Which operands need PHIs?
721  // FIXME: If any of these fail, we should partition up the candidates to
722  // try and continue making progress.
723  Instruction *I0 = NewInsts[0];
724 
725  // If all instructions that are going to participate don't have the same
726  // number of operands, we can't do any useful PHI analysis for all operands.
727  auto hasDifferentNumOperands = [&I0](Instruction *I) {
728  return I->getNumOperands() != I0->getNumOperands();
729  };
730  if (any_of(NewInsts, hasDifferentNumOperands))
731  return std::nullopt;
732 
733  for (unsigned OpNum = 0, E = I0->getNumOperands(); OpNum != E; ++OpNum) {
734  ModelledPHI PHI(NewInsts, OpNum, ActivePreds);
735  if (PHI.areAllIncomingValuesSame())
736  continue;
737  if (!canReplaceOperandWithVariable(I0, OpNum))
738  // We can 't create a PHI from this instruction!
739  return std::nullopt;
740  if (NeededPHIs.count(PHI))
741  continue;
742  if (!PHI.areAllIncomingValuesSameType())
743  return std::nullopt;
744  // Don't create indirect calls! The called value is the final operand.
745  if ((isa<CallInst>(I0) || isa<InvokeInst>(I0)) && OpNum == E - 1 &&
746  PHI.areAnyIncomingValuesConstant())
747  return std::nullopt;
748 
749  NeededPHIs.reserve(NeededPHIs.size());
750  NeededPHIs.insert(PHI);
751  PHIContents.insert(PHI.getValues().begin(), PHI.getValues().end());
752  }
753 
754  if (isMemoryInst(NewInsts[0]))
755  ++MemoryInstNum;
756 
757  SinkingInstructionCandidate Cand;
758  Cand.NumInstructions = ++InstNum;
759  Cand.NumMemoryInsts = MemoryInstNum;
760  Cand.NumBlocks = ActivePreds.size();
761  Cand.NumPHIs = NeededPHIs.size();
762  append_range(Cand.Blocks, ActivePreds);
763 
764  return Cand;
765 }
766 
767 unsigned GVNSink::sinkBB(BasicBlock *BBEnd) {
768  LLVM_DEBUG(dbgs() << "GVNSink: running on basic block ";
769  BBEnd->printAsOperand(dbgs()); dbgs() << "\n");
771  for (auto *B : predecessors(BBEnd)) {
772  auto *T = B->getTerminator();
773  if (isa<BranchInst>(T) || isa<SwitchInst>(T))
774  Preds.push_back(B);
775  else
776  return 0;
777  }
778  if (Preds.size() < 2)
779  return 0;
780  llvm::sort(Preds);
781 
782  unsigned NumOrigPreds = Preds.size();
783  // We can only sink instructions through unconditional branches.
784  llvm::erase_if(Preds, [](BasicBlock *BB) {
785  return BB->getTerminator()->getNumSuccessors() != 1;
786  });
787 
788  LockstepReverseIterator LRI(Preds);
790  unsigned InstNum = 0, MemoryInstNum = 0;
791  ModelledPHISet NeededPHIs;
792  SmallPtrSet<Value *, 4> PHIContents;
793  analyzeInitialPHIs(BBEnd, NeededPHIs, PHIContents);
794  unsigned NumOrigPHIs = NeededPHIs.size();
795 
796  while (LRI.isValid()) {
797  auto Cand = analyzeInstructionForSinking(LRI, InstNum, MemoryInstNum,
798  NeededPHIs, PHIContents);
799  if (!Cand)
800  break;
801  Cand->calculateCost(NumOrigPHIs, Preds.size());
802  Candidates.emplace_back(*Cand);
803  --LRI;
804  }
805 
806  llvm::stable_sort(Candidates, std::greater<SinkingInstructionCandidate>());
807  LLVM_DEBUG(dbgs() << " -- Sinking candidates:\n"; for (auto &C
808  : Candidates) dbgs()
809  << " " << C << "\n";);
810 
811  // Pick the top candidate, as long it is positive!
812  if (Candidates.empty() || Candidates.front().Cost <= 0)
813  return 0;
814  auto C = Candidates.front();
815 
816  LLVM_DEBUG(dbgs() << " -- Sinking: " << C << "\n");
817  BasicBlock *InsertBB = BBEnd;
818  if (C.Blocks.size() < NumOrigPreds) {
819  LLVM_DEBUG(dbgs() << " -- Splitting edge to ";
820  BBEnd->printAsOperand(dbgs()); dbgs() << "\n");
821  InsertBB = SplitBlockPredecessors(BBEnd, C.Blocks, ".gvnsink.split");
822  if (!InsertBB) {
823  LLVM_DEBUG(dbgs() << " -- FAILED to split edge!\n");
824  // Edge couldn't be split.
825  return 0;
826  }
827  }
828 
829  for (unsigned I = 0; I < C.NumInstructions; ++I)
830  sinkLastInstruction(C.Blocks, InsertBB);
831 
832  return C.NumInstructions;
833 }
834 
836  BasicBlock *BBEnd) {
838  for (BasicBlock *BB : Blocks)
839  Insts.push_back(BB->getTerminator()->getPrevNode());
840  Instruction *I0 = Insts.front();
841 
842  SmallVector<Value *, 4> NewOperands;
843  for (unsigned O = 0, E = I0->getNumOperands(); O != E; ++O) {
844  bool NeedPHI = llvm::any_of(Insts, [&I0, O](const Instruction *I) {
845  return I->getOperand(O) != I0->getOperand(O);
846  });
847  if (!NeedPHI) {
848  NewOperands.push_back(I0->getOperand(O));
849  continue;
850  }
851 
852  // Create a new PHI in the successor block and populate it.
853  auto *Op = I0->getOperand(O);
854  assert(!Op->getType()->isTokenTy() && "Can't PHI tokens!");
855  auto *PN = PHINode::Create(Op->getType(), Insts.size(),
856  Op->getName() + ".sink", &BBEnd->front());
857  for (auto *I : Insts)
858  PN->addIncoming(I->getOperand(O), I->getParent());
859  NewOperands.push_back(PN);
860  }
861 
862  // Arbitrarily use I0 as the new "common" instruction; remap its operands
863  // and move it to the start of the successor block.
864  for (unsigned O = 0, E = I0->getNumOperands(); O != E; ++O)
865  I0->getOperandUse(O).set(NewOperands[O]);
866  I0->moveBefore(&*BBEnd->getFirstInsertionPt());
867 
868  // Update metadata and IR flags.
869  for (auto *I : Insts)
870  if (I != I0) {
871  combineMetadataForCSE(I0, I, true);
872  I0->andIRFlags(I);
873  }
874 
875  for (auto *I : Insts)
876  if (I != I0)
877  I->replaceAllUsesWith(I0);
878  foldPointlessPHINodes(BBEnd);
879 
880  // Finally nuke all instructions apart from the common instruction.
881  for (auto *I : Insts)
882  if (I != I0)
883  I->eraseFromParent();
884 
885  NumRemoved += Insts.size() - 1;
886 }
887 
888 ////////////////////////////////////////////////////////////////////////////////
889 // Pass machinery / boilerplate
890 
891 class GVNSinkLegacyPass : public FunctionPass {
892 public:
893  static char ID;
894 
895  GVNSinkLegacyPass() : FunctionPass(ID) {
896  initializeGVNSinkLegacyPassPass(*PassRegistry::getPassRegistry());
897  }
898 
899  bool runOnFunction(Function &F) override {
900  if (skipFunction(F))
901  return false;
902  GVNSink G;
903  return G.run(F);
904  }
905 
906  void getAnalysisUsage(AnalysisUsage &AU) const override {
908  }
909 };
910 
911 } // end anonymous namespace
912 
914  GVNSink G;
915  if (!G.run(F))
916  return PreservedAnalyses::all();
917  return PreservedAnalyses::none();
918 }
919 
920 char GVNSinkLegacyPass::ID = 0;
921 
922 INITIALIZE_PASS_BEGIN(GVNSinkLegacyPass, "gvn-sink",
923  "Early GVN sinking of Expressions", false, false)
926 INITIALIZE_PASS_END(GVNSinkLegacyPass, "gvn-sink",
928 
929 FunctionPass *llvm::createGVNSinkPass() { return new GVNSinkLegacyPass(); }
llvm::SPII::Load
@ Load
Definition: SparcInstrInfo.h:32
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::less_second
Function object to check whether the second component of a std::pair compares less than the second co...
Definition: STLExtras.h:1484
llvm::createGVNSinkPass
FunctionPass * createGVNSinkPass()
Definition: GVNSink.cpp:929
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:492
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
llvm::SmallVectorImpl::erase
iterator erase(const_iterator CI)
Definition: SmallVector.h:741
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:2783
llvm::AArch64PACKey::ID
ID
Definition: AArch64BaseInfo.h:818
llvm::CmpInst::Predicate
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:720
PHI
Rewrite undef for PHI
Definition: AMDGPURewriteUndefForPHI.cpp:101
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:1199
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:174
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:1997
Local.h
Fail
#define Fail
Definition: AArch64Disassembler.cpp:296
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:1836
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:2701
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:265
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
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::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:1734
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:2793
InlinePriorityMode::Cost
@ Cost
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:3364
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:306
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:53
llvm::operator<<
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
Definition: APFixedPoint.h:291
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:1254
llvm::MCID::Call
@ Call
Definition: MCInstrDesc.h:155
llvm::PHINode::getNumIncomingValues
unsigned getNumIncomingValues() const
Return the number of incoming edges.
Definition: Instructions.h:2789
llvm::GVNExpression::BasicExpression::op_push_back
void op_push_back(Value *Arg)
Definition: GVNExpression.h:195
llvm::ARM::operator--
ArchKind & operator--(ArchKind &Kind)
Definition: ARMTargetParser.h:201
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:1721
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:189
llvm::GVNExpression::BasicExpression::getType
Type * getType() const
Definition: GVNExpression.h:211
llvm::InvokeInst
Invoke instruction.
Definition: Instructions.h:3809
llvm::all_equal
bool all_equal(std::initializer_list< T > Values)
Returns true if all Values in the initializer lists are equal or the list.
Definition: STLExtras.h:1985
llvm::CmpInst
This class is the base class for the comparison instructions.
Definition: InstrTypes.h:710
llvm::sort
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1682
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:359
llvm::DenseSet
Implements a dense probed hash-table based set.
Definition: DenseSet.h:268
llvm::Use::set
void set(Value *Val)
Definition: Value.h:865
BasicBlock.h
llvm::RISCVFenceField::O
@ O
Definition: RISCVBaseInfo.h:264
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:7967
llvm::Instruction::eraseFromParent
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Definition: Instruction.cpp:81
llvm::DenseMapBase< 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:110
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:2847
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:53
llvm::DenseMap
Definition: DenseMap.h:714
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:1868
llvm::initializeGVNSinkLegacyPassPass
void initializeGVNSinkLegacyPassPass(PassRegistry &)
ArrayRef.h
llvm::SPII::Store
@ Store
Definition: SparcInstrInfo.h:33
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::operator==
bool operator==(uint64_t V1, const APInt &V2)
Definition: APInt.h:2010
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:4760
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
getType
static M68kRelType getType(unsigned Kind, MCSymbolRefExpr::VariantKind &Modifier, bool &IsPCRel)
Definition: M68kELFObjectWriter.cpp:48
llvm::NVPTXISD::Dummy
@ Dummy
Definition: NVPTXISelLowering.h:60
llvm::operator*
APInt operator*(APInt a, uint64_t RHS)
Definition: APInt.h:2134
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:926
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:1741
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:532
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:2013
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:318
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:1913
llvm::stable_sort
void stable_sort(R &&Range)
Definition: STLExtras.h:1947
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:348
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:158
Casting.h
Function.h
PassManager.h
llvm::GVNExpression::Expression::setOpcode
void setOpcode(unsigned opcode)
Definition: GVNExpression.h:109
llvm::SmallVectorImpl::clear
void clear()
Definition: SmallVector.h:614
isEqual
static bool isEqual(const Function &Caller, const Function &Callee)
Definition: Attributes.cpp:1954
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:207
llvm::ReversePostOrderTraversal
Definition: PostOrderIterator.h:291
llvm::ShuffleVectorInst
This instruction constructs a fixed permutation of two input vectors.
Definition: Instructions.h:2006
isValid
static bool isValid(const char C)
Returns true if C is a valid mangled character: <0-9a-zA-Z_>.
Definition: RustDemangle.cpp:184
Instructions.h
PostOrderIterator.h
llvm::User::getNumOperands
unsigned getNumOperands() const
Definition: User.h:191
Expressions
gvn Early GVN sinking of Expressions
Definition: GVNSink.cpp:927
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:608
ArrayRecycler.h
Allocator
Basic Register Allocator
Definition: RegAllocBasic.cpp:143
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:486
llvm::Instruction::getParent
const BasicBlock * getParent() const
Definition: Instruction.h:91
llvm::GlobalsAAWrapperPass
Legacy wrapper pass to provide the GlobalsAAResult object.
Definition: GlobalsModRef.h:142
llvm::PHINode::getIncomingBlock
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
Definition: Instructions.h:2813
llvm::operator>
bool operator>(int64_t V1, const APSInt &V2)
Definition: APSInt.h:348
llvm::PHINode
Definition: Instructions.h:2697
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:98
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:107
Other
Optional< std::vector< StOtherPiece > > Other
Definition: ELFYAML.cpp:1251
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:941
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::hash_code
An opaque object representing a hash code.
Definition: Hashing.h:74