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