77#define DEBUG_TYPE "gvn-sink"
79STATISTIC(NumRemoved,
"Number of instructions removed");
82namespace GVNExpression {
95 return isa<LoadInst>(
I) || isa<StoreInst>(
I) ||
96 (isa<InvokeInst>(
I) && !cast<InvokeInst>(
I)->doesNotAccessMemory()) ||
97 (isa<CallInst>(
I) && !cast<CallInst>(
I)->doesNotAccessMemory());
112class LockstepReverseIterator {
125 ActiveBlocks.
clear();
130 if (BB->size() <= 1) {
135 Insts.
push_back(BB->getTerminator()->getPrevNode());
153 for (
auto II = Insts.
begin(); II != Insts.
end();) {
154 if (!
Blocks.contains((*II)->getParent())) {
155 ActiveBlocks.
remove((*II)->getParent());
156 II = Insts.
erase(II);
167 for (
auto *Inst : Insts) {
168 if (Inst == &Inst->getParent()->front())
169 ActiveBlocks.
remove(Inst->getParent());
173 if (NewInsts.
empty()) {
187struct SinkingInstructionCandidate {
189 unsigned NumInstructions;
191 unsigned NumMemoryInsts;
195 void calculateCost(
unsigned NumOrigPHIs,
unsigned NumOrigBlocks) {
196 unsigned NumExtraPHIs = NumPHIs - NumOrigPHIs;
197 unsigned SplitEdgeCost = (NumOrigBlocks > NumBlocks) ? 2 : 0;
198 Cost = (NumInstructions * (NumBlocks - 1)) -
211 OS <<
"<Candidate Cost=" <<
C.Cost <<
" #Blocks=" <<
C.NumBlocks
212 <<
" #Insts=" <<
C.NumInstructions <<
" #PHIs=" <<
C.NumPHIs <<
">";
227 ModelledPHI() =
default;
229 ModelledPHI(
const PHINode *PN) {
235 for (
auto &
P : Ops) {
244 static ModelledPHI createDummy(
size_t ID) {
246 M.Values.push_back(
reinterpret_cast<Value*
>(
ID));
251 template <
typename VArray,
typename BArray>
252 ModelledPHI(
const VArray &V,
const BArray &
B) {
258 template <
typename BArray>
261 for (
auto *
I : Insts)
270 while (BI !=
Blocks.end()) {
285 bool areAllIncomingValuesSame()
const {
289 bool areAllIncomingValuesSameType()
const {
291 Values, [&](
Value *V) {
return V->getType() == Values[0]->
getType(); });
294 bool areAnyIncomingValuesConstant()
const {
299 unsigned hash()
const {
309 static inline ModelledPHI &getEmptyKey() {
310 static ModelledPHI
Dummy = ModelledPHI::createDummy(0);
314 static inline ModelledPHI &getTombstoneKey() {
315 static ModelledPHI
Dummy = ModelledPHI::createDummy(1);
319 static unsigned getHashValue(
const ModelledPHI &V) {
return V.hash(); }
321 static bool isEqual(
const ModelledPHI &LHS,
const ModelledPHI &RHS) {
342 unsigned MemoryUseOrder = -1;
349 : GVNExpression::BasicExpression(
I->getNumUses()) {
355 ShuffleMask = SVI->getShuffleMask().
copy(
A);
357 for (
auto &U :
I->uses())
362 void setMemoryUseOrder(
unsigned MUO) { MemoryUseOrder = MUO; }
363 void setVolatile(
bool V) {
Volatile =
V; }
367 MemoryUseOrder, Volatile, ShuffleMask);
388 BasicBlocksSet ReachableBBs;
394 InstructionUseExpr *
E =
397 E->setMemoryUseOrder(getMemoryUseOrder(
I));
409 template <
class Inst> InstructionUseExpr *createMemoryExpr(Inst *
I) {
412 InstructionUseExpr *
E = createExpr(
I);
413 E->setVolatile(
I->isVolatile());
421 void setReachableBBs(
const BasicBlocksSet &ReachableBBs) {
422 this->ReachableBBs = ReachableBBs;
428 auto VI = ValueNumbering.
find(V);
429 if (VI != ValueNumbering.
end())
432 if (!isa<Instruction>(V)) {
433 ValueNumbering[
V] = nextValueNumber;
434 return nextValueNumber++;
438 if (!ReachableBBs.contains(
I->getParent()))
441 InstructionUseExpr *exp =
nullptr;
442 switch (
I->getOpcode()) {
443 case Instruction::Load:
444 exp = createMemoryExpr(cast<LoadInst>(
I));
446 case Instruction::Store:
447 exp = createMemoryExpr(cast<StoreInst>(
I));
449 case Instruction::Call:
450 case Instruction::Invoke:
451 case Instruction::FNeg:
452 case Instruction::Add:
453 case Instruction::FAdd:
454 case Instruction::Sub:
455 case Instruction::FSub:
456 case Instruction::Mul:
457 case Instruction::FMul:
458 case Instruction::UDiv:
459 case Instruction::SDiv:
460 case Instruction::FDiv:
461 case Instruction::URem:
462 case Instruction::SRem:
463 case Instruction::FRem:
464 case Instruction::Shl:
465 case Instruction::LShr:
466 case Instruction::AShr:
467 case Instruction::And:
468 case Instruction::Or:
469 case Instruction::Xor:
470 case Instruction::ICmp:
471 case Instruction::FCmp:
472 case Instruction::Trunc:
473 case Instruction::ZExt:
474 case Instruction::SExt:
475 case Instruction::FPToUI:
476 case Instruction::FPToSI:
477 case Instruction::UIToFP:
478 case Instruction::SIToFP:
479 case Instruction::FPTrunc:
480 case Instruction::FPExt:
481 case Instruction::PtrToInt:
482 case Instruction::IntToPtr:
483 case Instruction::BitCast:
484 case Instruction::AddrSpaceCast:
485 case Instruction::Select:
486 case Instruction::ExtractElement:
487 case Instruction::InsertElement:
488 case Instruction::ShuffleVector:
489 case Instruction::InsertValue:
490 case Instruction::GetElementPtr:
498 ValueNumbering[
V] = nextValueNumber;
499 return nextValueNumber++;
504 hash_code H = exp->getHashValue([=](
Value *V) {
return lookupOrAdd(V); });
505 auto I = HashNumbering.
find(
H);
506 if (
I != HashNumbering.
end()) {
509 e = nextValueNumber++;
510 HashNumbering[
H] =
e;
511 ExpressionNumbering[exp] =
e;
514 ValueNumbering[
V] =
e;
521 auto VI = ValueNumbering.
find(V);
522 assert(VI != ValueNumbering.
end() &&
"Value not numbered?");
528 ValueNumbering.
clear();
529 ExpressionNumbering.
clear();
530 HashNumbering.
clear();
548 I !=
E && !
I->isTerminator(); ++
I) {
549 if (!isMemoryInst(&*
I))
551 if (isa<LoadInst>(&*
I))
559 return lookupOrAdd(&*
I);
575 unsigned NumSunk = 0;
577 VN.setReachableBBs(BasicBlocksSet(RPOT.begin(), RPOT.end()));
579 NumSunk += sinkBB(
N);
589 if (isa<PHINode>(
I) ||
I->isEHPad() || isa<AllocaInst>(
I) ||
590 I->getType()->isTokenTy())
598 std::optional<SinkingInstructionCandidate> analyzeInstructionForSinking(
599 LockstepReverseIterator &LRI,
unsigned &InstNum,
unsigned &MemoryInstNum,
603 void analyzeInitialPHIs(
BasicBlock *BB, ModelledPHISet &PHIs,
606 auto MPHI = ModelledPHI(&PN);
608 for (
auto *V : MPHI.getValues())
624 while (
PHINode *PN = dyn_cast<PHINode>(
I++)) {
626 return V == PN->getIncomingValue(0);
638std::optional<SinkingInstructionCandidate>
639GVNSink::analyzeInstructionForSinking(LockstepReverseIterator &LRI,
641 unsigned &MemoryInstNum,
642 ModelledPHISet &NeededPHIs,
645 LLVM_DEBUG(
dbgs() <<
" -- Analyzing instruction set: [\n";
for (
auto *
I
648 }
dbgs() <<
" ]\n";);
651 for (
auto *
I : Insts) {
658 unsigned VNumToSink =
661 if (VNums[VNumToSink] == 1)
667 auto &ActivePreds = LRI.getActiveBlocks();
668 unsigned InitialActivePredSize = ActivePreds.size();
670 for (
auto *
I : Insts) {
671 if (VN.lookup(
I) != VNumToSink)
672 ActivePreds.remove(
I->getParent());
676 for (
auto *
I : NewInsts)
677 if (shouldAvoidSinkingInstruction(
I))
682 bool RecomputePHIContents =
false;
683 if (ActivePreds.size() != InitialActivePredSize) {
684 ModelledPHISet NewNeededPHIs;
685 for (
auto P : NeededPHIs) {
686 P.restrictToBlocks(ActivePreds);
687 NewNeededPHIs.insert(
P);
689 NeededPHIs = NewNeededPHIs;
690 LRI.restrictToBlocks(ActivePreds);
691 RecomputePHIContents =
true;
695 ModelledPHI NewPHI(NewInsts, ActivePreds);
698 if (NeededPHIs.erase(NewPHI))
699 RecomputePHIContents =
true;
701 if (RecomputePHIContents) {
705 for (
auto &
PHI : NeededPHIs)
706 PHIContents.
insert(
PHI.getValues().begin(),
PHI.getValues().end());
711 for (
auto *V : NewPHI.getValues())
712 if (PHIContents.
count(V))
728 if (
any_of(NewInsts, hasDifferentNumOperands))
732 ModelledPHI
PHI(NewInsts, OpNum, ActivePreds);
733 if (
PHI.areAllIncomingValuesSame())
738 if (NeededPHIs.count(
PHI))
740 if (!
PHI.areAllIncomingValuesSameType())
743 if ((isa<CallInst>(I0) || isa<InvokeInst>(I0)) && OpNum ==
E - 1 &&
744 PHI.areAnyIncomingValuesConstant())
747 NeededPHIs.reserve(NeededPHIs.size());
748 NeededPHIs.insert(
PHI);
749 PHIContents.
insert(
PHI.getValues().begin(),
PHI.getValues().end());
752 if (isMemoryInst(NewInsts[0]))
755 SinkingInstructionCandidate Cand;
756 Cand.NumInstructions = ++InstNum;
757 Cand.NumMemoryInsts = MemoryInstNum;
758 Cand.NumBlocks = ActivePreds.size();
759 Cand.NumPHIs = NeededPHIs.size();
770 auto *
T =
B->getTerminator();
771 if (isa<BranchInst>(
T) || isa<SwitchInst>(
T))
776 if (Preds.size() < 2)
780 unsigned NumOrigPreds = Preds.size();
786 LockstepReverseIterator LRI(Preds);
788 unsigned InstNum = 0, MemoryInstNum = 0;
789 ModelledPHISet NeededPHIs;
791 analyzeInitialPHIs(BBEnd, NeededPHIs, PHIContents);
792 unsigned NumOrigPHIs = NeededPHIs.size();
794 while (LRI.isValid()) {
795 auto Cand = analyzeInstructionForSinking(LRI, InstNum, MemoryInstNum,
796 NeededPHIs, PHIContents);
799 Cand->calculateCost(NumOrigPHIs, Preds.size());
807 <<
" " <<
C <<
"\n";);
810 if (Candidates.empty() || Candidates.front().Cost <= 0)
812 auto C = Candidates.front();
816 if (
C.Blocks.size() < NumOrigPreds) {
827 for (
unsigned I = 0;
I <
C.NumInstructions; ++
I)
830 return C.NumInstructions;
852 assert(!
Op->getType()->isTokenTy() &&
"Can't PHI tokens!");
856 for (
auto *
I : Insts)
868 for (
auto *
I : Insts)
874 for (
auto *
I : Insts)
876 I->replaceAllUsesWith(I0);
877 foldPointlessPHINodes(BBEnd);
880 for (
auto *
I : Insts)
882 I->eraseFromParent();
884 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
DenseMap< Block *, BlockRelaxAux > Blocks
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 * 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.
This class represents an Operation in the Expression.
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 insertBefore(Instruction *InsertPos)
Insert an unlinked instruction into a basic block immediately before the specified instruction.
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
InstListType::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.
bool remove(const value_type &X)
Remove an item from the set vector.
size_type size() const
Determine the number of elements in the SetVector.
void clear()
Completely clear the SetVector.
bool insert(const value_type &X)
Insert a new element into the SetVector.
bool contains(const key_type &key) const
Check if the SetVector contains the given key.
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 range R to container C.
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:...