80#define DEBUG_TYPE "gvn-sink"
82STATISTIC(NumRemoved,
"Number of instructions removed");
85namespace GVNExpression {
98 return isa<LoadInst>(
I) || isa<StoreInst>(
I) ||
99 (isa<InvokeInst>(
I) && !cast<InvokeInst>(
I)->doesNotAccessMemory()) ||
100 (isa<CallInst>(
I) && !cast<CallInst>(
I)->doesNotAccessMemory());
115class LockstepReverseIterator {
128 ActiveBlocks.
clear();
133 if (BB->size() <= 1) {
138 Insts.
push_back(BB->getTerminator()->getPrevNode());
156 for (
auto II = Insts.
begin(); II != Insts.
end();) {
157 if (!Blocks.
contains((*II)->getParent())) {
158 ActiveBlocks.
remove((*II)->getParent());
159 II = Insts.
erase(II);
170 for (
auto *Inst : Insts) {
171 if (Inst == &Inst->getParent()->front())
172 ActiveBlocks.
remove(Inst->getParent());
176 if (NewInsts.
empty()) {
190struct SinkingInstructionCandidate {
192 unsigned NumInstructions;
194 unsigned NumMemoryInsts;
198 void calculateCost(
unsigned NumOrigPHIs,
unsigned NumOrigBlocks) {
199 unsigned NumExtraPHIs = NumPHIs - NumOrigPHIs;
200 unsigned SplitEdgeCost = (NumOrigBlocks > NumBlocks) ? 2 : 0;
201 Cost = (NumInstructions * (NumBlocks - 1)) -
214 OS <<
"<Candidate Cost=" <<
C.Cost <<
" #Blocks=" <<
C.NumBlocks
215 <<
" #Insts=" <<
C.NumInstructions <<
" #PHIs=" <<
C.NumPHIs <<
">";
230 ModelledPHI() =
default;
232 ModelledPHI(
const PHINode *PN) {
238 for (
auto &
P : Ops) {
247 static ModelledPHI createDummy(
size_t ID) {
249 M.Values.push_back(
reinterpret_cast<Value*
>(
ID));
254 template <
typename VArray,
typename BArray>
255 ModelledPHI(
const VArray &V,
const BArray &
B) {
261 template <
typename BArray>
264 for (
auto *
I : Insts)
271 auto BI = Blocks.
begin();
273 while (BI != Blocks.
end()) {
276 BI = Blocks.
erase(BI);
288 bool areAllIncomingValuesSame()
const {
292 bool areAllIncomingValuesSameType()
const {
294 Values, [&](
Value *V) {
return V->getType() == Values[0]->
getType(); });
297 bool areAnyIncomingValuesConstant()
const {
302 unsigned hash()
const {
307 return Values ==
Other.Values && Blocks ==
Other.Blocks;
312 static inline ModelledPHI &getEmptyKey() {
313 static ModelledPHI
Dummy = ModelledPHI::createDummy(0);
317 static inline ModelledPHI &getTombstoneKey() {
318 static ModelledPHI
Dummy = ModelledPHI::createDummy(1);
322 static unsigned getHashValue(
const ModelledPHI &V) {
return V.hash(); }
324 static bool isEqual(
const ModelledPHI &LHS,
const ModelledPHI &RHS) {
345 unsigned MemoryUseOrder = -1;
352 : GVNExpression::BasicExpression(
I->getNumUses()) {
358 ShuffleMask = SVI->getShuffleMask().
copy(
A);
360 for (
auto &U :
I->uses())
365 void setMemoryUseOrder(
unsigned MUO) { MemoryUseOrder = MUO; }
366 void setVolatile(
bool V) {
Volatile =
V; }
370 MemoryUseOrder, Volatile, ShuffleMask);
391 BasicBlocksSet ReachableBBs;
397 InstructionUseExpr *
E =
400 E->setMemoryUseOrder(getMemoryUseOrder(
I));
412 template <
class Inst> InstructionUseExpr *createMemoryExpr(Inst *
I) {
415 InstructionUseExpr *
E = createExpr(
I);
416 E->setVolatile(
I->isVolatile());
424 void setReachableBBs(
const BasicBlocksSet &ReachableBBs) {
425 this->ReachableBBs = ReachableBBs;
431 auto VI = ValueNumbering.
find(V);
432 if (VI != ValueNumbering.
end())
435 if (!isa<Instruction>(V)) {
436 ValueNumbering[
V] = nextValueNumber;
437 return nextValueNumber++;
441 if (!ReachableBBs.contains(
I->getParent()))
444 InstructionUseExpr *exp =
nullptr;
445 switch (
I->getOpcode()) {
446 case Instruction::Load:
447 exp = createMemoryExpr(cast<LoadInst>(
I));
449 case Instruction::Store:
450 exp = createMemoryExpr(cast<StoreInst>(
I));
452 case Instruction::Call:
453 case Instruction::Invoke:
454 case Instruction::FNeg:
455 case Instruction::Add:
456 case Instruction::FAdd:
457 case Instruction::Sub:
458 case Instruction::FSub:
459 case Instruction::Mul:
460 case Instruction::FMul:
461 case Instruction::UDiv:
462 case Instruction::SDiv:
463 case Instruction::FDiv:
464 case Instruction::URem:
465 case Instruction::SRem:
466 case Instruction::FRem:
467 case Instruction::Shl:
468 case Instruction::LShr:
469 case Instruction::AShr:
470 case Instruction::And:
471 case Instruction::Or:
472 case Instruction::Xor:
473 case Instruction::ICmp:
474 case Instruction::FCmp:
475 case Instruction::Trunc:
476 case Instruction::ZExt:
477 case Instruction::SExt:
478 case Instruction::FPToUI:
479 case Instruction::FPToSI:
480 case Instruction::UIToFP:
481 case Instruction::SIToFP:
482 case Instruction::FPTrunc:
483 case Instruction::FPExt:
484 case Instruction::PtrToInt:
485 case Instruction::IntToPtr:
486 case Instruction::BitCast:
487 case Instruction::AddrSpaceCast:
488 case Instruction::Select:
489 case Instruction::ExtractElement:
490 case Instruction::InsertElement:
491 case Instruction::ShuffleVector:
492 case Instruction::InsertValue:
493 case Instruction::GetElementPtr:
501 ValueNumbering[
V] = nextValueNumber;
502 return nextValueNumber++;
507 hash_code H = exp->getHashValue([=](
Value *V) {
return lookupOrAdd(V); });
508 auto I = HashNumbering.
find(
H);
509 if (
I != HashNumbering.
end()) {
512 e = nextValueNumber++;
513 HashNumbering[
H] =
e;
514 ExpressionNumbering[exp] =
e;
517 ValueNumbering[
V] =
e;
524 auto VI = ValueNumbering.
find(V);
525 assert(VI != ValueNumbering.
end() &&
"Value not numbered?");
531 ValueNumbering.
clear();
532 ExpressionNumbering.
clear();
533 HashNumbering.
clear();
551 I !=
E && !
I->isTerminator(); ++
I) {
552 if (!isMemoryInst(&*
I))
554 if (isa<LoadInst>(&*
I))
562 return lookupOrAdd(&*
I);
578 unsigned NumSunk = 0;
580 VN.setReachableBBs(BasicBlocksSet(RPOT.begin(), RPOT.end()));
582 NumSunk += sinkBB(
N);
592 if (isa<PHINode>(
I) ||
I->isEHPad() || isa<AllocaInst>(
I) ||
593 I->getType()->isTokenTy())
601 std::optional<SinkingInstructionCandidate> analyzeInstructionForSinking(
602 LockstepReverseIterator &LRI,
unsigned &InstNum,
unsigned &MemoryInstNum,
606 void analyzeInitialPHIs(
BasicBlock *BB, ModelledPHISet &PHIs,
609 auto MPHI = ModelledPHI(&PN);
611 for (
auto *V : MPHI.getValues())
627 while (
PHINode *PN = dyn_cast<PHINode>(
I++)) {
629 return V == PN->getIncomingValue(0);
641std::optional<SinkingInstructionCandidate>
642GVNSink::analyzeInstructionForSinking(LockstepReverseIterator &LRI,
644 unsigned &MemoryInstNum,
645 ModelledPHISet &NeededPHIs,
648 LLVM_DEBUG(
dbgs() <<
" -- Analyzing instruction set: [\n";
for (
auto *
I
651 }
dbgs() <<
" ]\n";);
654 for (
auto *
I : Insts) {
661 unsigned VNumToSink =
664 if (VNums[VNumToSink] == 1)
670 auto &ActivePreds = LRI.getActiveBlocks();
671 unsigned InitialActivePredSize = ActivePreds.size();
673 for (
auto *
I : Insts) {
674 if (VN.lookup(
I) != VNumToSink)
675 ActivePreds.remove(
I->getParent());
679 for (
auto *
I : NewInsts)
680 if (shouldAvoidSinkingInstruction(
I))
685 bool RecomputePHIContents =
false;
686 if (ActivePreds.size() != InitialActivePredSize) {
687 ModelledPHISet NewNeededPHIs;
688 for (
auto P : NeededPHIs) {
689 P.restrictToBlocks(ActivePreds);
690 NewNeededPHIs.insert(
P);
692 NeededPHIs = NewNeededPHIs;
693 LRI.restrictToBlocks(ActivePreds);
694 RecomputePHIContents =
true;
698 ModelledPHI NewPHI(NewInsts, ActivePreds);
701 if (NeededPHIs.erase(NewPHI))
702 RecomputePHIContents =
true;
704 if (RecomputePHIContents) {
708 for (
auto &
PHI : NeededPHIs)
709 PHIContents.
insert(
PHI.getValues().begin(),
PHI.getValues().end());
714 for (
auto *V : NewPHI.getValues())
715 if (PHIContents.
count(V))
731 if (
any_of(NewInsts, hasDifferentNumOperands))
735 ModelledPHI
PHI(NewInsts, OpNum, ActivePreds);
736 if (
PHI.areAllIncomingValuesSame())
741 if (NeededPHIs.count(
PHI))
743 if (!
PHI.areAllIncomingValuesSameType())
746 if ((isa<CallInst>(I0) || isa<InvokeInst>(I0)) && OpNum ==
E - 1 &&
747 PHI.areAnyIncomingValuesConstant())
750 NeededPHIs.reserve(NeededPHIs.size());
751 NeededPHIs.insert(
PHI);
752 PHIContents.
insert(
PHI.getValues().begin(),
PHI.getValues().end());
755 if (isMemoryInst(NewInsts[0]))
758 SinkingInstructionCandidate Cand;
759 Cand.NumInstructions = ++InstNum;
760 Cand.NumMemoryInsts = MemoryInstNum;
761 Cand.NumBlocks = ActivePreds.size();
762 Cand.NumPHIs = NeededPHIs.size();
773 auto *
T =
B->getTerminator();
774 if (isa<BranchInst>(
T) || isa<SwitchInst>(
T))
779 if (Preds.size() < 2)
783 unsigned NumOrigPreds = Preds.size();
789 LockstepReverseIterator LRI(Preds);
791 unsigned InstNum = 0, MemoryInstNum = 0;
792 ModelledPHISet NeededPHIs;
794 analyzeInitialPHIs(BBEnd, NeededPHIs, PHIContents);
795 unsigned NumOrigPHIs = NeededPHIs.size();
797 while (LRI.isValid()) {
798 auto Cand = analyzeInstructionForSinking(LRI, InstNum, MemoryInstNum,
799 NeededPHIs, PHIContents);
802 Cand->calculateCost(NumOrigPHIs, Preds.size());
810 <<
" " <<
C <<
"\n";);
813 if (Candidates.empty() || Candidates.front().Cost <= 0)
815 auto C = Candidates.front();
819 if (
C.Blocks.size() < NumOrigPreds) {
830 for (
unsigned I = 0;
I <
C.NumInstructions; ++
I)
833 return C.NumInstructions;
855 assert(!
Op->getType()->isTokenTy() &&
"Can't PHI tokens!");
857 Op->getName() +
".sink", &BBEnd->
front());
858 for (
auto *
I : Insts)
870 for (
auto *
I : Insts)
876 for (
auto *
I : Insts)
878 I->replaceAllUsesWith(I0);
879 foldPointlessPHINodes(BBEnd);
882 for (
auto *
I : Insts)
884 I->eraseFromParent();
886 NumRemoved += Insts.size() - 1;
This file defines the BumpPtrAllocator interface.
Atomic ordering constants.
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
This file contains the declarations for the subclasses of Constant, which represent the different fla...
static void clear(coro::Shape &Shape)
This file defines the DenseMap class.
This file defines the DenseSet and SmallDenseSet classes.
std::optional< std::vector< StOtherPiece > > Other
The header file for the GVN pass that contains expression handling classes.
This file provides the interface for LLVM's Global Value Numbering pass which eliminates fully redund...
This is the interface for a simple mod/ref and alias analysis over globals.
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
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.
This header defines various interfaces for pass management in LLVM.
This file builds on the ADT/GraphTraits.h file to build a generic graph post order iterator.
static bool isValid(const char C)
Returns true if C is a valid mangled character: <0-9a-zA-Z_>.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
static bool sinkLastInstruction(ArrayRef< BasicBlock * > Blocks)
This file defines the SmallPtrSet class.
This file defines the SmallVector class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
static SymbolRef::Type getType(const Symbol *Sym)
This defines the Use class.
A container for analyses that lazily runs them and caches their results.
Recycle small arrays allocated from a BumpPtrAllocator.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
MutableArrayRef< T > copy(Allocator &A)
LLVM Basic Block Representation.
iterator begin()
Instruction iterator methods.
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
const_iterator getFirstInsertionPt() const
Returns an iterator to the first instruction in this block that is suitable for inserting a non-PHI i...
const Instruction & front() const
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Allocate memory in an ever growing pool, as if by bump-pointer.
bool onlyReadsMemory(unsigned OpNo) const
This class represents a function call, abstracting a target machine's calling convention.
This class is the base class for the comparison instructions.
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
iterator find(const_arg_type_t< KeyT > Val)
Implements a dense probed hash-table based set.
void allocateOperands(RecyclerType &Recycler, BumpPtrAllocator &Allocator)
void op_push_back(Value *Arg)
hash_code getHashValue() const override
iterator_range< op_iterator > operands()
unsigned getOpcode() const
LLVM_DUMP_METHOD void dump() const
void setOpcode(unsigned opcode)
void print(raw_ostream &OS) const
void andIRFlags(const Value *V)
Logical 'and' of any supported wrapping, exact, and fast-math flags of V and this instruction.
const BasicBlock * getParent() const
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
void moveBefore(Instruction *MovePos)
Unlink this instruction from its current basic block and insert it into the basic block that MovePos ...
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
op_range incoming_values()
static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
unsigned getNumIncomingValues() const
Return the number of incoming edges.
static PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
A set of analyses that are preserved following a run of a transformation pass.
static PreservedAnalyses none()
Convenience factory function for the empty preserved set.
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Recycler - This class manages a linked-list of deallocated nodes and facilitates reusing deallocated ...
void clear(AllocatorType &Allocator)
clear - Release all the tracked allocations to the allocator.
size_type size() const
Determine the number of elements in the SetVector.
bool contains(const key_type &key) const
Check if the SetVector contains the given key.
bool remove(const value_type &X)
Remove an item from the set vector.
bool insert(const value_type &X)
Insert a new element into the SetVector.
void clear()
Completely clear the SetVector.
This instruction constructs a fixed permutation of two input vectors.
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
A SetVector that performs no allocations if smaller than a certain size.
reference emplace_back(ArgTypes &&... Args)
iterator erase(const_iterator CI)
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
static Twine utohexstr(const uint64_t &Val)
const Use & getOperandUse(unsigned i) const
Value * getOperand(unsigned i) const
unsigned getNumOperands() const
LLVM Value Representation.
Type * getType() const
All values are typed, get the type of this value.
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
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.
An opaque object representing a hash code.
self_iterator getIterator()
This class implements an extremely fast bulk output stream that can only output to a stream.
std::unique_ptr< ValueIDNum[]> ValueTable
Type for a table of values in a block.
ArchKind & operator--(ArchKind &Kind)
@ C
The default llvm calling convention, compatible with C.
Predicate
Predicate - These are "(BI << 5) | BO" for various predicates.
PointerTypeMap run(const Module &M)
Compute the PointerTypeMap for the module M.
This is an optimization pass for GlobalISel generic memory operations.
void stable_sort(R &&Range)
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
bool isEqual(const GCNRPTracker::LiveRegSet &S1, const GCNRPTracker::LiveRegSet &S2)
APInt operator*(APInt a, uint64_t RHS)
void append_range(Container &C, Range &&R)
Wrapper function to append a range to a container.
bool isStrongerThanUnordered(AtomicOrdering AO)
bool operator==(const AddressRangeValuePair &LHS, const AddressRangeValuePair &RHS)
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
bool operator>(int64_t V1, const APSInt &V2)
void sort(IteratorTy Start, IteratorTy End)
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
void combineMetadataForCSE(Instruction *K, const Instruction *J, bool DoesKMove)
Combine the metadata of two instructions so that K can replace J.
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...
bool canReplaceOperandWithVariable(const Instruction *I, unsigned OpIdx)
Given an instruction, is it legal to set operand OpIdx to a non-constant value?
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
OutputIt copy(R &&Range, OutputIt Out)
void erase_if(Container &C, UnaryPredicate P)
Provide a container algorithm similar to C++ Library Fundamentals v2's erase_if which is equivalent t...
auto predecessors(const MachineBasicBlock *BB)
bool all_equal(std::initializer_list< T > Values)
Returns true if all Values in the initializer lists are equal or the list.
hash_code hash_combine(const Ts &...args)
Combine values into a single hash_code.
hash_code hash_combine_range(InputIteratorT first, InputIteratorT last)
Compute a hash_code for a sequence of values.
An information struct used to provide DenseMap with the various necessary components for a given valu...
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Run the pass over the function.
Function object to check whether the second component of a container supported by std::get (like std:...