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