1 //===- GVNHoist.cpp - Hoist scalar and load expressions -------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This pass hoists expressions from branches to a common dominator. It uses
11 // GVN (global value numbering) to discover expressions computing the same
12 // values. The primary goals of code-hoisting are:
13 // 1. To reduce the code size.
14 // 2. In some cases reduce critical path (by exposing more ILP).
16 // The algorithm factors out the reachability of values such that multiple
17 // queries to find reachability of values are fast. This is based on finding the
18 // ANTIC points in the CFG which do not change during hoisting. The ANTIC points
19 // are basically the dominance-frontiers in the inverse graph. So we introduce a
20 // data structure (CHI nodes) to keep track of values flowing out of a basic
21 // block. We only do this for values with multiple occurrences in the function
22 // as they are the potential hoistable candidates. This approach allows us to
23 // hoist instructions to a basic block with more than two successors, as well as
24 // deal with infinite loops in a trivial way.
26 // Limitations: This pass does not hoist fully redundant expressions because
27 // they are already handled by GVN-PRE. It is advisable to run gvn-hoist before
28 // and after gvn-pre because gvn-pre creates opportunities for more instructions
31 // Hoisting may affect the performance in some cases. To mitigate that, hoisting
32 // is disabled in the following cases.
33 // 1. Scalars across calls.
34 // 2. geps when corresponding load/store cannot be hoisted.
35 //===----------------------------------------------------------------------===//
37 #include "llvm/ADT/DenseMap.h"
38 #include "llvm/ADT/DenseSet.h"
39 #include "llvm/ADT/STLExtras.h"
40 #include "llvm/ADT/SmallPtrSet.h"
41 #include "llvm/ADT/SmallVector.h"
42 #include "llvm/ADT/Statistic.h"
43 #include "llvm/ADT/iterator_range.h"
44 #include "llvm/Analysis/AliasAnalysis.h"
45 #include "llvm/Analysis/GlobalsModRef.h"
46 #include "llvm/Analysis/IteratedDominanceFrontier.h"
47 #include "llvm/Analysis/MemoryDependenceAnalysis.h"
48 #include "llvm/Analysis/MemorySSA.h"
49 #include "llvm/Analysis/MemorySSAUpdater.h"
50 #include "llvm/Analysis/PostDominators.h"
51 #include "llvm/Transforms/Utils/Local.h"
52 #include "llvm/Analysis/ValueTracking.h"
53 #include "llvm/IR/Argument.h"
54 #include "llvm/IR/BasicBlock.h"
55 #include "llvm/IR/CFG.h"
56 #include "llvm/IR/Constants.h"
57 #include "llvm/IR/Dominators.h"
58 #include "llvm/IR/Function.h"
59 #include "llvm/IR/InstrTypes.h"
60 #include "llvm/IR/Instruction.h"
61 #include "llvm/IR/Instructions.h"
62 #include "llvm/IR/IntrinsicInst.h"
63 #include "llvm/IR/Intrinsics.h"
64 #include "llvm/IR/LLVMContext.h"
65 #include "llvm/IR/PassManager.h"
66 #include "llvm/IR/Use.h"
67 #include "llvm/IR/User.h"
68 #include "llvm/IR/Value.h"
69 #include "llvm/Pass.h"
70 #include "llvm/Support/Casting.h"
71 #include "llvm/Support/CommandLine.h"
72 #include "llvm/Support/Debug.h"
73 #include "llvm/Support/raw_ostream.h"
74 #include "llvm/Transforms/Scalar.h"
75 #include "llvm/Transforms/Scalar/GVN.h"
85 #define DEBUG_TYPE "gvn-hoist"
87 STATISTIC(NumHoisted, "Number of instructions hoisted");
88 STATISTIC(NumRemoved, "Number of instructions removed");
89 STATISTIC(NumLoadsHoisted, "Number of loads hoisted");
90 STATISTIC(NumLoadsRemoved, "Number of loads removed");
91 STATISTIC(NumStoresHoisted, "Number of stores hoisted");
92 STATISTIC(NumStoresRemoved, "Number of stores removed");
93 STATISTIC(NumCallsHoisted, "Number of calls hoisted");
94 STATISTIC(NumCallsRemoved, "Number of calls removed");
97 MaxHoistedThreshold("gvn-max-hoisted", cl::Hidden, cl::init(-1),
98 cl::desc("Max number of instructions to hoist "
99 "(default unlimited = -1)"));
101 static cl::opt<int> MaxNumberOfBBSInPath(
102 "gvn-hoist-max-bbs", cl::Hidden, cl::init(4),
103 cl::desc("Max number of basic blocks on the path between "
104 "hoisting locations (default = 4, unlimited = -1)"));
106 static cl::opt<int> MaxDepthInBB(
107 "gvn-hoist-max-depth", cl::Hidden, cl::init(100),
108 cl::desc("Hoist instructions from the beginning of the BB up to the "
109 "maximum specified depth (default = 100, unlimited = -1)"));
112 MaxChainLength("gvn-hoist-max-chain-length", cl::Hidden, cl::init(10),
113 cl::desc("Maximum length of dependent chains to hoist "
114 "(default = 10, unlimited = -1)"));
118 using BBSideEffectsSet = DenseMap<const BasicBlock *, bool>;
119 using SmallVecInsn = SmallVector<Instruction *, 4>;
120 using SmallVecImplInsn = SmallVectorImpl<Instruction *>;
122 // Each element of a hoisting list contains the basic block where to hoist and
123 // a list of instructions to be hoisted.
124 using HoistingPointInfo = std::pair<BasicBlock *, SmallVecInsn>;
126 using HoistingPointList = SmallVector<HoistingPointInfo, 4>;
128 // A map from a pair of VNs to all the instructions with those VNs.
129 using VNType = std::pair<unsigned, unsigned>;
131 using VNtoInsns = DenseMap<VNType, SmallVector<Instruction *, 4>>;
133 // CHI keeps information about values flowing out of a basic block. It is
134 // similar to PHI but in the inverse graph, and used for outgoing values on each
135 // edge. For conciseness, it is computed only for instructions with multiple
136 // occurrences in the CFG because they are the only hoistable candidates.
137 // A (CHI[{V, B, I1}, {V, C, I2}]
141 // The Value number for both I1 and I2 is V, the CHI node will save the
142 // instruction as well as the edge where the value is flowing to.
146 // Edge destination (shows the direction of flow), may not be where the I is.
149 // The instruction (VN) which uses the values flowing out of CHI.
152 bool operator==(const CHIArg &A) { return VN == A.VN; }
153 bool operator!=(const CHIArg &A) { return !(*this == A); }
156 using CHIIt = SmallVectorImpl<CHIArg>::iterator;
157 using CHIArgs = iterator_range<CHIIt>;
158 using OutValuesType = DenseMap<BasicBlock *, SmallVector<CHIArg, 2>>;
160 DenseMap<BasicBlock *, SmallVector<std::pair<VNType, Instruction *>, 2>>;
162 // An invalid value number Used when inserting a single value number into
164 enum : unsigned { InvalidVN = ~2U };
166 // Records all scalar instructions candidate for code hoisting.
168 VNtoInsns VNtoScalars;
171 // Inserts I and its value number in VNtoScalars.
172 void insert(Instruction *I, GVN::ValueTable &VN) {
173 // Scalar instruction.
174 unsigned V = VN.lookupOrAdd(I);
175 VNtoScalars[{V, InvalidVN}].push_back(I);
178 const VNtoInsns &getVNTable() const { return VNtoScalars; }
181 // Records all load instructions candidate for code hoisting.
186 // Insert Load and the value number of its memory address in VNtoLoads.
187 void insert(LoadInst *Load, GVN::ValueTable &VN) {
188 if (Load->isSimple()) {
189 unsigned V = VN.lookupOrAdd(Load->getPointerOperand());
190 VNtoLoads[{V, InvalidVN}].push_back(Load);
194 const VNtoInsns &getVNTable() const { return VNtoLoads; }
197 // Records all store instructions candidate for code hoisting.
199 VNtoInsns VNtoStores;
202 // Insert the Store and a hash number of the store address and the stored
203 // value in VNtoStores.
204 void insert(StoreInst *Store, GVN::ValueTable &VN) {
205 if (!Store->isSimple())
207 // Hash the store address and the stored value.
208 Value *Ptr = Store->getPointerOperand();
209 Value *Val = Store->getValueOperand();
210 VNtoStores[{VN.lookupOrAdd(Ptr), VN.lookupOrAdd(Val)}].push_back(Store);
213 const VNtoInsns &getVNTable() const { return VNtoStores; }
216 // Records all call instructions candidate for code hoisting.
218 VNtoInsns VNtoCallsScalars;
219 VNtoInsns VNtoCallsLoads;
220 VNtoInsns VNtoCallsStores;
223 // Insert Call and its value numbering in one of the VNtoCalls* containers.
224 void insert(CallInst *Call, GVN::ValueTable &VN) {
225 // A call that doesNotAccessMemory is handled as a Scalar,
226 // onlyReadsMemory will be handled as a Load instruction,
227 // all other calls will be handled as stores.
228 unsigned V = VN.lookupOrAdd(Call);
229 auto Entry = std::make_pair(V, InvalidVN);
231 if (Call->doesNotAccessMemory())
232 VNtoCallsScalars[Entry].push_back(Call);
233 else if (Call->onlyReadsMemory())
234 VNtoCallsLoads[Entry].push_back(Call);
236 VNtoCallsStores[Entry].push_back(Call);
239 const VNtoInsns &getScalarVNTable() const { return VNtoCallsScalars; }
240 const VNtoInsns &getLoadVNTable() const { return VNtoCallsLoads; }
241 const VNtoInsns &getStoreVNTable() const { return VNtoCallsStores; }
244 static void combineKnownMetadata(Instruction *ReplInst, Instruction *I) {
245 static const unsigned KnownIDs[] = {
246 LLVMContext::MD_tbaa, LLVMContext::MD_alias_scope,
247 LLVMContext::MD_noalias, LLVMContext::MD_range,
248 LLVMContext::MD_fpmath, LLVMContext::MD_invariant_load,
249 LLVMContext::MD_invariant_group};
250 combineMetadata(ReplInst, I, KnownIDs);
253 // This pass hoists common computations across branches sharing common
254 // dominator. The primary goal is to reduce the code size, and in some
255 // cases reduce critical path (by exposing more ILP).
258 GVNHoist(DominatorTree *DT, PostDominatorTree *PDT, AliasAnalysis *AA,
259 MemoryDependenceResults *MD, MemorySSA *MSSA)
260 : DT(DT), PDT(PDT), AA(AA), MD(MD), MSSA(MSSA),
261 MSSAUpdater(llvm::make_unique<MemorySSAUpdater>(MSSA)) {}
263 bool run(Function &F) {
264 NumFuncArgs = F.arg_size();
266 VN.setAliasAnalysis(AA);
269 // Perform DFS Numbering of instructions.
271 for (const BasicBlock *BB : depth_first(&F.getEntryBlock())) {
272 DFSNumber[BB] = ++BBI;
274 for (auto &Inst : *BB)
275 DFSNumber[&Inst] = ++I;
280 // FIXME: use lazy evaluation of VN to avoid the fix-point computation.
282 if (MaxChainLength != -1 && ++ChainLength >= MaxChainLength)
285 auto HoistStat = hoistExpressions(F);
286 if (HoistStat.first + HoistStat.second == 0)
289 if (HoistStat.second > 0)
290 // To address a limitation of the current GVN, we need to rerun the
291 // hoisting after we hoisted loads or stores in order to be able to
292 // hoist all scalars dependent on the hoisted ld/st.
301 // Copied from NewGVN.cpp
302 // This function provides global ranking of operations so that we can place
303 // them in a canonical order. Note that rank alone is not necessarily enough
304 // for a complete ordering, as constants all have the same rank. However,
305 // generally, we will simplify an operation with all constants so that it
306 // doesn't matter what order they appear in.
307 unsigned int rank(const Value *V) const {
308 // Prefer constants to undef to anything else
309 // Undef is a constant, have to check it first.
310 // Prefer smaller constants to constantexprs
311 if (isa<ConstantExpr>(V))
313 if (isa<UndefValue>(V))
315 if (isa<Constant>(V))
317 else if (auto *A = dyn_cast<Argument>(V))
318 return 3 + A->getArgNo();
320 // Need to shift the instruction DFS by number of arguments + 3 to account
321 // for the constant and argument ranking above.
322 auto Result = DFSNumber.lookup(V);
324 return 4 + NumFuncArgs + Result;
325 // Unreachable or something else, just return a really large number.
332 PostDominatorTree *PDT;
334 MemoryDependenceResults *MD;
336 std::unique_ptr<MemorySSAUpdater> MSSAUpdater;
337 DenseMap<const Value *, unsigned> DFSNumber;
338 BBSideEffectsSet BBSideEffects;
339 DenseSet<const BasicBlock *> HoistBarrier;
340 SmallVector<BasicBlock *, 32> IDFBlocks;
341 unsigned NumFuncArgs;
342 const bool HoistingGeps = false;
344 enum InsKind { Unknown, Scalar, Load, Store };
346 // Return true when there are exception handling in BB.
347 bool hasEH(const BasicBlock *BB) {
348 auto It = BBSideEffects.find(BB);
349 if (It != BBSideEffects.end())
352 if (BB->isEHPad() || BB->hasAddressTaken()) {
353 BBSideEffects[BB] = true;
357 if (BB->getTerminator()->mayThrow()) {
358 BBSideEffects[BB] = true;
362 BBSideEffects[BB] = false;
366 // Return true when a successor of BB dominates A.
367 bool successorDominate(const BasicBlock *BB, const BasicBlock *A) {
368 for (const BasicBlock *Succ : BB->getTerminator()->successors())
369 if (DT->dominates(Succ, A))
375 // Return true when I1 appears before I2 in the instructions of BB.
376 bool firstInBB(const Instruction *I1, const Instruction *I2) {
377 assert(I1->getParent() == I2->getParent());
378 unsigned I1DFS = DFSNumber.lookup(I1);
379 unsigned I2DFS = DFSNumber.lookup(I2);
380 assert(I1DFS && I2DFS);
381 return I1DFS < I2DFS;
384 // Return true when there are memory uses of Def in BB.
385 bool hasMemoryUse(const Instruction *NewPt, MemoryDef *Def,
386 const BasicBlock *BB) {
387 const MemorySSA::AccessList *Acc = MSSA->getBlockAccesses(BB);
391 Instruction *OldPt = Def->getMemoryInst();
392 const BasicBlock *OldBB = OldPt->getParent();
393 const BasicBlock *NewBB = NewPt->getParent();
394 bool ReachedNewPt = false;
396 for (const MemoryAccess &MA : *Acc)
397 if (const MemoryUse *MU = dyn_cast<MemoryUse>(&MA)) {
398 Instruction *Insn = MU->getMemoryInst();
400 // Do not check whether MU aliases Def when MU occurs after OldPt.
401 if (BB == OldBB && firstInBB(OldPt, Insn))
404 // Do not check whether MU aliases Def when MU occurs before NewPt.
407 if (firstInBB(Insn, NewPt))
412 if (MemorySSAUtil::defClobbersUseOrDef(Def, MU, *AA))
419 bool hasEHhelper(const BasicBlock *BB, const BasicBlock *SrcBB,
420 int &NBBsOnAllPaths) {
421 // Stop walk once the limit is reached.
422 if (NBBsOnAllPaths == 0)
425 // Impossible to hoist with exceptions on the path.
429 // No such instruction after HoistBarrier in a basic block was
430 // selected for hoisting so instructions selected within basic block with
431 // a hoist barrier can be hoisted.
432 if ((BB != SrcBB) && HoistBarrier.count(BB))
438 // Return true when there are exception handling or loads of memory Def
439 // between Def and NewPt. This function is only called for stores: Def is
440 // the MemoryDef of the store to be hoisted.
442 // Decrement by 1 NBBsOnAllPaths for each block between HoistPt and BB, and
443 // return true when the counter NBBsOnAllPaths reaces 0, except when it is
444 // initialized to -1 which is unlimited.
445 bool hasEHOrLoadsOnPath(const Instruction *NewPt, MemoryDef *Def,
446 int &NBBsOnAllPaths) {
447 const BasicBlock *NewBB = NewPt->getParent();
448 const BasicBlock *OldBB = Def->getBlock();
449 assert(DT->dominates(NewBB, OldBB) && "invalid path");
450 assert(DT->dominates(Def->getDefiningAccess()->getBlock(), NewBB) &&
451 "def does not dominate new hoisting point");
453 // Walk all basic blocks reachable in depth-first iteration on the inverse
454 // CFG from OldBB to NewBB. These blocks are all the blocks that may be
455 // executed between the execution of NewBB and OldBB. Hoisting an expression
456 // from OldBB into NewBB has to be safe on all execution paths.
457 for (auto I = idf_begin(OldBB), E = idf_end(OldBB); I != E;) {
458 const BasicBlock *BB = *I;
460 // Stop traversal when reaching HoistPt.
465 if (hasEHhelper(BB, OldBB, NBBsOnAllPaths))
468 // Check that we do not move a store past loads.
469 if (hasMemoryUse(NewPt, Def, BB))
472 // -1 is unlimited number of blocks on all paths.
473 if (NBBsOnAllPaths != -1)
482 // Return true when there are exception handling between HoistPt and BB.
483 // Decrement by 1 NBBsOnAllPaths for each block between HoistPt and BB, and
484 // return true when the counter NBBsOnAllPaths reaches 0, except when it is
485 // initialized to -1 which is unlimited.
486 bool hasEHOnPath(const BasicBlock *HoistPt, const BasicBlock *SrcBB,
487 int &NBBsOnAllPaths) {
488 assert(DT->dominates(HoistPt, SrcBB) && "Invalid path");
490 // Walk all basic blocks reachable in depth-first iteration on
491 // the inverse CFG from BBInsn to NewHoistPt. These blocks are all the
492 // blocks that may be executed between the execution of NewHoistPt and
493 // BBInsn. Hoisting an expression from BBInsn into NewHoistPt has to be safe
494 // on all execution paths.
495 for (auto I = idf_begin(SrcBB), E = idf_end(SrcBB); I != E;) {
496 const BasicBlock *BB = *I;
498 // Stop traversal when reaching NewHoistPt.
503 if (hasEHhelper(BB, SrcBB, NBBsOnAllPaths))
506 // -1 is unlimited number of blocks on all paths.
507 if (NBBsOnAllPaths != -1)
516 // Return true when it is safe to hoist a memory load or store U from OldPt
518 bool safeToHoistLdSt(const Instruction *NewPt, const Instruction *OldPt,
519 MemoryUseOrDef *U, InsKind K, int &NBBsOnAllPaths) {
520 // In place hoisting is safe.
524 const BasicBlock *NewBB = NewPt->getParent();
525 const BasicBlock *OldBB = OldPt->getParent();
526 const BasicBlock *UBB = U->getBlock();
528 // Check for dependences on the Memory SSA.
529 MemoryAccess *D = U->getDefiningAccess();
530 BasicBlock *DBB = D->getBlock();
531 if (DT->properlyDominates(NewBB, DBB))
532 // Cannot move the load or store to NewBB above its definition in DBB.
535 if (NewBB == DBB && !MSSA->isLiveOnEntryDef(D))
536 if (auto *UD = dyn_cast<MemoryUseOrDef>(D))
537 if (!firstInBB(UD->getMemoryInst(), NewPt))
538 // Cannot move the load or store to NewPt above its definition in D.
541 // Check for unsafe hoistings due to side effects.
542 if (K == InsKind::Store) {
543 if (hasEHOrLoadsOnPath(NewPt, dyn_cast<MemoryDef>(U), NBBsOnAllPaths))
545 } else if (hasEHOnPath(NewBB, OldBB, NBBsOnAllPaths))
549 if (DT->properlyDominates(DBB, NewBB))
552 assert(MSSA->locallyDominates(D, U));
555 // No side effects: it is safe to hoist.
559 // Return true when it is safe to hoist scalar instructions from all blocks in
561 bool safeToHoistScalar(const BasicBlock *HoistBB, const BasicBlock *BB,
562 int &NBBsOnAllPaths) {
563 return !hasEHOnPath(HoistBB, BB, NBBsOnAllPaths);
566 // In the inverse CFG, the dominance frontier of basic block (BB) is the
567 // point where ANTIC needs to be computed for instructions which are going
568 // to be hoisted. Since this point does not change during gvn-hoist,
569 // we compute it only once (on demand).
570 // The ides is inspired from:
571 // "Partial Redundancy Elimination in SSA Form"
572 // ROBERT KENNEDY, SUN CHAN, SHIN-MING LIU, RAYMOND LO, PENG TU and FRED CHOW
573 // They use similar idea in the forward graph to find fully redundant and
574 // partially redundant expressions, here it is used in the inverse graph to
575 // find fully anticipable instructions at merge point (post-dominator in
577 // Returns the edge via which an instruction in BB will get the values from.
579 // Returns true when the values are flowing out to each edge.
580 bool valueAnticipable(CHIArgs C, TerminatorInst *TI) const {
581 if (TI->getNumSuccessors() > (unsigned)size(C))
582 return false; // Not enough args in this CHI.
585 BasicBlock *Dest = CHI.Dest;
586 // Find if all the edges have values flowing out of BB.
587 bool Found = llvm::any_of(TI->successors(), [Dest](const BasicBlock *BB) {
588 return BB == Dest; });
595 // Check if it is safe to hoist values tracked by CHI in the range
596 // [Begin, End) and accumulate them in Safe.
597 void checkSafety(CHIArgs C, BasicBlock *BB, InsKind K,
598 SmallVectorImpl<CHIArg> &Safe) {
599 int NumBBsOnAllPaths = MaxNumberOfBBSInPath;
601 Instruction *Insn = CHI.I;
602 if (!Insn) // No instruction was inserted in this CHI.
604 if (K == InsKind::Scalar) {
605 if (safeToHoistScalar(BB, Insn->getParent(), NumBBsOnAllPaths))
608 MemoryUseOrDef *UD = MSSA->getMemoryAccess(Insn);
609 if (safeToHoistLdSt(BB->getTerminator(), Insn, UD, K, NumBBsOnAllPaths))
615 using RenameStackType = DenseMap<VNType, SmallVector<Instruction *, 2>>;
617 // Push all the VNs corresponding to BB into RenameStack.
618 void fillRenameStack(BasicBlock *BB, InValuesType &ValueBBs,
619 RenameStackType &RenameStack) {
620 auto it1 = ValueBBs.find(BB);
621 if (it1 != ValueBBs.end()) {
622 // Iterate in reverse order to keep lower ranked values on the top.
623 for (std::pair<VNType, Instruction *> &VI : reverse(it1->second)) {
624 // Get the value of instruction I
625 LLVM_DEBUG(dbgs() << "\nPushing on stack: " << *VI.second);
626 RenameStack[VI.first].push_back(VI.second);
631 void fillChiArgs(BasicBlock *BB, OutValuesType &CHIBBs,
632 RenameStackType &RenameStack) {
633 // For each *predecessor* (because Post-DOM) of BB check if it has a CHI
634 for (auto Pred : predecessors(BB)) {
635 auto P = CHIBBs.find(Pred);
636 if (P == CHIBBs.end()) {
639 LLVM_DEBUG(dbgs() << "\nLooking at CHIs in: " << Pred->getName(););
640 // A CHI is found (BB -> Pred is an edge in the CFG)
641 // Pop the stack until Top(V) = Ve.
642 auto &VCHI = P->second;
643 for (auto It = VCHI.begin(), E = VCHI.end(); It != E;) {
646 auto si = RenameStack.find(C.VN);
647 // The Basic Block where CHI is must dominate the value we want to
648 // track in a CHI. In the PDom walk, there can be values in the
649 // stack which are not control dependent e.g., nested loop.
650 if (si != RenameStack.end() && si->second.size() &&
651 DT->properlyDominates(Pred, si->second.back()->getParent())) {
652 C.Dest = BB; // Assign the edge
653 C.I = si->second.pop_back_val(); // Assign the argument
655 << "\nCHI Inserted in BB: " << C.Dest->getName() << *C.I
656 << ", VN: " << C.VN.first << ", " << C.VN.second);
658 // Move to next CHI of a different value
659 It = std::find_if(It, VCHI.end(),
660 [It](CHIArg &A) { return A != *It; });
667 // Walk the post-dominator tree top-down and use a stack for each value to
668 // store the last value you see. When you hit a CHI from a given edge, the
669 // value to use as the argument is at the top of the stack, add the value to
671 void insertCHI(InValuesType &ValueBBs, OutValuesType &CHIBBs) {
672 auto Root = PDT->getNode(nullptr);
675 // Depth first walk on PDom tree to fill the CHIargs at each PDF.
676 RenameStackType RenameStack;
677 for (auto Node : depth_first(Root)) {
678 BasicBlock *BB = Node->getBlock();
682 // Collect all values in BB and push to stack.
683 fillRenameStack(BB, ValueBBs, RenameStack);
685 // Fill outgoing values in each CHI corresponding to BB.
686 fillChiArgs(BB, CHIBBs, RenameStack);
690 // Walk all the CHI-nodes to find ones which have a empty-entry and remove
691 // them Then collect all the instructions which are safe to hoist and see if
692 // they form a list of anticipable values. OutValues contains CHIs
693 // corresponding to each basic block.
694 void findHoistableCandidates(OutValuesType &CHIBBs, InsKind K,
695 HoistingPointList &HPL) {
696 auto cmpVN = [](const CHIArg &A, const CHIArg &B) { return A.VN < B.VN; };
698 // CHIArgs now have the outgoing values, so check for anticipability and
699 // accumulate hoistable candidates in HPL.
700 for (std::pair<BasicBlock *, SmallVector<CHIArg, 2>> &A : CHIBBs) {
701 BasicBlock *BB = A.first;
702 SmallVectorImpl<CHIArg> &CHIs = A.second;
703 // Vector of PHIs contains PHIs for different instructions.
704 // Sort the args according to their VNs, such that identical
705 // instructions are together.
706 std::stable_sort(CHIs.begin(), CHIs.end(), cmpVN);
707 auto TI = BB->getTerminator();
708 auto B = CHIs.begin();
709 // [PreIt, PHIIt) form a range of CHIs which have identical VNs.
710 auto PHIIt = std::find_if(CHIs.begin(), CHIs.end(),
711 [B](CHIArg &A) { return A != *B; });
712 auto PrevIt = CHIs.begin();
713 while (PrevIt != PHIIt) {
714 // Collect values which satisfy safety checks.
715 SmallVector<CHIArg, 2> Safe;
716 // We check for safety first because there might be multiple values in
717 // the same path, some of which are not safe to be hoisted, but overall
718 // each edge has at least one value which can be hoisted, making the
719 // value anticipable along that path.
720 checkSafety(make_range(PrevIt, PHIIt), BB, K, Safe);
722 // List of safe values should be anticipable at TI.
723 if (valueAnticipable(make_range(Safe.begin(), Safe.end()), TI)) {
724 HPL.push_back({BB, SmallVecInsn()});
725 SmallVecInsn &V = HPL.back().second;
732 PHIIt = std::find_if(PrevIt, CHIs.end(),
733 [PrevIt](CHIArg &A) { return A != *PrevIt; });
738 // Compute insertion points for each values which can be fully anticipated at
739 // a dominator. HPL contains all such values.
740 void computeInsertionPoints(const VNtoInsns &Map, HoistingPointList &HPL,
742 // Sort VNs based on their rankings
743 std::vector<VNType> Ranks;
744 for (const auto &Entry : Map) {
745 Ranks.push_back(Entry.first);
748 // TODO: Remove fully-redundant expressions.
749 // Get instruction from the Map, assume that all the Instructions
750 // with same VNs have same rank (this is an approximation).
751 llvm::sort(Ranks.begin(), Ranks.end(),
752 [this, &Map](const VNType &r1, const VNType &r2) {
753 return (rank(*Map.lookup(r1).begin()) <
754 rank(*Map.lookup(r2).begin()));
757 // - Sort VNs according to their rank, and start with lowest ranked VN
758 // - Take a VN and for each instruction with same VN
759 // - Find the dominance frontier in the inverse graph (PDF)
760 // - Insert the chi-node at PDF
761 // - Remove the chi-nodes with missing entries
762 // - Remove values from CHI-nodes which do not truly flow out, e.g.,
763 // modified along the path.
764 // - Collect the remaining values that are still anticipable
765 SmallVector<BasicBlock *, 2> IDFBlocks;
766 ReverseIDFCalculator IDFs(*PDT);
767 OutValuesType OutValue;
768 InValuesType InValue;
769 for (const auto &R : Ranks) {
770 const SmallVecInsn &V = Map.lookup(R);
773 const VNType &VN = R;
774 SmallPtrSet<BasicBlock *, 2> VNBlocks;
776 BasicBlock *BBI = I->getParent();
778 VNBlocks.insert(BBI);
780 // Compute the Post Dominance Frontiers of each basic block
781 // The dominance frontier of a live block X in the reverse
782 // control graph is the set of blocks upon which X is control
783 // dependent. The following sequence computes the set of blocks
784 // which currently have dead terminators that are control
785 // dependence sources of a block which is in NewLiveBlocks.
786 IDFs.setDefiningBlocks(VNBlocks);
787 IDFs.calculate(IDFBlocks);
789 // Make a map of BB vs instructions to be hoisted.
790 for (unsigned i = 0; i < V.size(); ++i) {
791 InValue[V[i]->getParent()].push_back(std::make_pair(VN, V[i]));
793 // Insert empty CHI node for this VN. This is used to factor out
794 // basic blocks where the ANTIC can potentially change.
795 for (auto IDFB : IDFBlocks) { // TODO: Prune out useless CHI insertions.
796 for (unsigned i = 0; i < V.size(); ++i) {
797 CHIArg C = {VN, nullptr, nullptr};
798 // Ignore spurious PDFs.
799 if (DT->properlyDominates(IDFB, V[i]->getParent())) {
800 OutValue[IDFB].push_back(C);
801 LLVM_DEBUG(dbgs() << "\nInsertion a CHI for BB: " << IDFB->getName()
802 << ", for Insn: " << *V[i]);
808 // Insert CHI args at each PDF to iterate on factored graph of
809 // control dependence.
810 insertCHI(InValue, OutValue);
811 // Using the CHI args inserted at each PDF, find fully anticipable values.
812 findHoistableCandidates(OutValue, K, HPL);
815 // Return true when all operands of Instr are available at insertion point
816 // HoistPt. When limiting the number of hoisted expressions, one could hoist
817 // a load without hoisting its access function. So before hoisting any
818 // expression, make sure that all its operands are available at insert point.
819 bool allOperandsAvailable(const Instruction *I,
820 const BasicBlock *HoistPt) const {
821 for (const Use &Op : I->operands())
822 if (const auto *Inst = dyn_cast<Instruction>(&Op))
823 if (!DT->dominates(Inst->getParent(), HoistPt))
829 // Same as allOperandsAvailable with recursive check for GEP operands.
830 bool allGepOperandsAvailable(const Instruction *I,
831 const BasicBlock *HoistPt) const {
832 for (const Use &Op : I->operands())
833 if (const auto *Inst = dyn_cast<Instruction>(&Op))
834 if (!DT->dominates(Inst->getParent(), HoistPt)) {
835 if (const GetElementPtrInst *GepOp =
836 dyn_cast<GetElementPtrInst>(Inst)) {
837 if (!allGepOperandsAvailable(GepOp, HoistPt))
839 // Gep is available if all operands of GepOp are available.
841 // Gep is not available if it has operands other than GEPs that are
842 // defined in blocks not dominating HoistPt.
849 // Make all operands of the GEP available.
850 void makeGepsAvailable(Instruction *Repl, BasicBlock *HoistPt,
851 const SmallVecInsn &InstructionsToHoist,
852 Instruction *Gep) const {
853 assert(allGepOperandsAvailable(Gep, HoistPt) &&
854 "GEP operands not available");
856 Instruction *ClonedGep = Gep->clone();
857 for (unsigned i = 0, e = Gep->getNumOperands(); i != e; ++i)
858 if (Instruction *Op = dyn_cast<Instruction>(Gep->getOperand(i))) {
859 // Check whether the operand is already available.
860 if (DT->dominates(Op->getParent(), HoistPt))
863 // As a GEP can refer to other GEPs, recursively make all the operands
864 // of this GEP available at HoistPt.
865 if (GetElementPtrInst *GepOp = dyn_cast<GetElementPtrInst>(Op))
866 makeGepsAvailable(ClonedGep, HoistPt, InstructionsToHoist, GepOp);
869 // Copy Gep and replace its uses in Repl with ClonedGep.
870 ClonedGep->insertBefore(HoistPt->getTerminator());
872 // Conservatively discard any optimization hints, they may differ on the
874 ClonedGep->dropUnknownNonDebugMetadata();
876 // If we have optimization hints which agree with each other along different
877 // paths, preserve them.
878 for (const Instruction *OtherInst : InstructionsToHoist) {
879 const GetElementPtrInst *OtherGep;
880 if (auto *OtherLd = dyn_cast<LoadInst>(OtherInst))
881 OtherGep = cast<GetElementPtrInst>(OtherLd->getPointerOperand());
883 OtherGep = cast<GetElementPtrInst>(
884 cast<StoreInst>(OtherInst)->getPointerOperand());
885 ClonedGep->andIRFlags(OtherGep);
888 // Replace uses of Gep with ClonedGep in Repl.
889 Repl->replaceUsesOfWith(Gep, ClonedGep);
892 void updateAlignment(Instruction *I, Instruction *Repl) {
893 if (auto *ReplacementLoad = dyn_cast<LoadInst>(Repl)) {
894 ReplacementLoad->setAlignment(
895 std::min(ReplacementLoad->getAlignment(),
896 cast<LoadInst>(I)->getAlignment()));
898 } else if (auto *ReplacementStore = dyn_cast<StoreInst>(Repl)) {
899 ReplacementStore->setAlignment(
900 std::min(ReplacementStore->getAlignment(),
901 cast<StoreInst>(I)->getAlignment()));
903 } else if (auto *ReplacementAlloca = dyn_cast<AllocaInst>(Repl)) {
904 ReplacementAlloca->setAlignment(
905 std::max(ReplacementAlloca->getAlignment(),
906 cast<AllocaInst>(I)->getAlignment()));
907 } else if (isa<CallInst>(Repl)) {
912 // Remove all the instructions in Candidates and replace their usage with Repl.
913 // Returns the number of instructions removed.
914 unsigned rauw(const SmallVecInsn &Candidates, Instruction *Repl,
915 MemoryUseOrDef *NewMemAcc) {
917 for (Instruction *I : Candidates) {
920 updateAlignment(I, Repl);
922 // Update the uses of the old MSSA access with NewMemAcc.
923 MemoryAccess *OldMA = MSSA->getMemoryAccess(I);
924 OldMA->replaceAllUsesWith(NewMemAcc);
925 MSSAUpdater->removeMemoryAccess(OldMA);
929 combineKnownMetadata(Repl, I);
930 I->replaceAllUsesWith(Repl);
931 // Also invalidate the Alias Analysis cache.
932 MD->removeInstruction(I);
933 I->eraseFromParent();
939 // Replace all Memory PHI usage with NewMemAcc.
940 void raMPHIuw(MemoryUseOrDef *NewMemAcc) {
941 SmallPtrSet<MemoryPhi *, 4> UsePhis;
942 for (User *U : NewMemAcc->users())
943 if (MemoryPhi *Phi = dyn_cast<MemoryPhi>(U))
946 for (MemoryPhi *Phi : UsePhis) {
947 auto In = Phi->incoming_values();
948 if (llvm::all_of(In, [&](Use &U) { return U == NewMemAcc; })) {
949 Phi->replaceAllUsesWith(NewMemAcc);
950 MSSAUpdater->removeMemoryAccess(Phi);
955 // Remove all other instructions and replace them with Repl.
956 unsigned removeAndReplace(const SmallVecInsn &Candidates, Instruction *Repl,
957 BasicBlock *DestBB, bool MoveAccess) {
958 MemoryUseOrDef *NewMemAcc = MSSA->getMemoryAccess(Repl);
959 if (MoveAccess && NewMemAcc) {
960 // The definition of this ld/st will not change: ld/st hoisting is
961 // legal when the ld/st is not moved past its current definition.
962 MSSAUpdater->moveToPlace(NewMemAcc, DestBB, MemorySSA::End);
965 // Replace all other instructions with Repl with memory access NewMemAcc.
966 unsigned NR = rauw(Candidates, Repl, NewMemAcc);
968 // Remove MemorySSA phi nodes with the same arguments.
974 // In the case Repl is a load or a store, we make all their GEPs
975 // available: GEPs are not hoisted by default to avoid the address
976 // computations to be hoisted without the associated load or store.
977 bool makeGepOperandsAvailable(Instruction *Repl, BasicBlock *HoistPt,
978 const SmallVecInsn &InstructionsToHoist) const {
979 // Check whether the GEP of a ld/st can be synthesized at HoistPt.
980 GetElementPtrInst *Gep = nullptr;
981 Instruction *Val = nullptr;
982 if (auto *Ld = dyn_cast<LoadInst>(Repl)) {
983 Gep = dyn_cast<GetElementPtrInst>(Ld->getPointerOperand());
984 } else if (auto *St = dyn_cast<StoreInst>(Repl)) {
985 Gep = dyn_cast<GetElementPtrInst>(St->getPointerOperand());
986 Val = dyn_cast<Instruction>(St->getValueOperand());
987 // Check that the stored value is available.
989 if (isa<GetElementPtrInst>(Val)) {
990 // Check whether we can compute the GEP at HoistPt.
991 if (!allGepOperandsAvailable(Val, HoistPt))
993 } else if (!DT->dominates(Val->getParent(), HoistPt))
998 // Check whether we can compute the Gep at HoistPt.
999 if (!Gep || !allGepOperandsAvailable(Gep, HoistPt))
1002 makeGepsAvailable(Repl, HoistPt, InstructionsToHoist, Gep);
1004 if (Val && isa<GetElementPtrInst>(Val))
1005 makeGepsAvailable(Repl, HoistPt, InstructionsToHoist, Val);
1010 std::pair<unsigned, unsigned> hoist(HoistingPointList &HPL) {
1011 unsigned NI = 0, NL = 0, NS = 0, NC = 0, NR = 0;
1012 for (const HoistingPointInfo &HP : HPL) {
1013 // Find out whether we already have one of the instructions in HoistPt,
1014 // in which case we do not have to move it.
1015 BasicBlock *DestBB = HP.first;
1016 const SmallVecInsn &InstructionsToHoist = HP.second;
1017 Instruction *Repl = nullptr;
1018 for (Instruction *I : InstructionsToHoist)
1019 if (I->getParent() == DestBB)
1020 // If there are two instructions in HoistPt to be hoisted in place:
1021 // update Repl to be the first one, such that we can rename the uses
1022 // of the second based on the first.
1023 if (!Repl || firstInBB(I, Repl))
1026 // Keep track of whether we moved the instruction so we know whether we
1027 // should move the MemoryAccess.
1028 bool MoveAccess = true;
1030 // Repl is already in HoistPt: it remains in place.
1031 assert(allOperandsAvailable(Repl, DestBB) &&
1032 "instruction depends on operands that are not available");
1035 // When we do not find Repl in HoistPt, select the first in the list
1036 // and move it to HoistPt.
1037 Repl = InstructionsToHoist.front();
1039 // We can move Repl in HoistPt only when all operands are available.
1040 // The order in which hoistings are done may influence the availability
1042 if (!allOperandsAvailable(Repl, DestBB)) {
1043 // When HoistingGeps there is nothing more we can do to make the
1044 // operands available: just continue.
1048 // When not HoistingGeps we need to copy the GEPs.
1049 if (!makeGepOperandsAvailable(Repl, DestBB, InstructionsToHoist))
1053 // Move the instruction at the end of HoistPt.
1054 Instruction *Last = DestBB->getTerminator();
1055 MD->removeInstruction(Repl);
1056 Repl->moveBefore(Last);
1058 DFSNumber[Repl] = DFSNumber[Last]++;
1061 NR += removeAndReplace(InstructionsToHoist, Repl, DestBB, MoveAccess);
1063 if (isa<LoadInst>(Repl))
1065 else if (isa<StoreInst>(Repl))
1067 else if (isa<CallInst>(Repl))
1073 NumHoisted += NL + NS + NC + NI;
1075 NumLoadsHoisted += NL;
1076 NumStoresHoisted += NS;
1077 NumCallsHoisted += NC;
1078 return {NI, NL + NC + NS};
1081 // Hoist all expressions. Returns Number of scalars hoisted
1082 // and number of non-scalars hoisted.
1083 std::pair<unsigned, unsigned> hoistExpressions(Function &F) {
1088 for (BasicBlock *BB : depth_first(&F.getEntryBlock())) {
1089 int InstructionNb = 0;
1090 for (Instruction &I1 : *BB) {
1091 // If I1 cannot guarantee progress, subsequent instructions
1092 // in BB cannot be hoisted anyways.
1093 if (!isGuaranteedToTransferExecutionToSuccessor(&I1)) {
1094 HoistBarrier.insert(BB);
1097 // Only hoist the first instructions in BB up to MaxDepthInBB. Hoisting
1098 // deeper may increase the register pressure and compilation time.
1099 if (MaxDepthInBB != -1 && InstructionNb++ >= MaxDepthInBB)
1102 // Do not value number terminator instructions.
1103 if (isa<TerminatorInst>(&I1))
1106 if (auto *Load = dyn_cast<LoadInst>(&I1))
1107 LI.insert(Load, VN);
1108 else if (auto *Store = dyn_cast<StoreInst>(&I1))
1109 SI.insert(Store, VN);
1110 else if (auto *Call = dyn_cast<CallInst>(&I1)) {
1111 if (auto *Intr = dyn_cast<IntrinsicInst>(Call)) {
1112 if (isa<DbgInfoIntrinsic>(Intr) ||
1113 Intr->getIntrinsicID() == Intrinsic::assume ||
1114 Intr->getIntrinsicID() == Intrinsic::sideeffect)
1117 if (Call->mayHaveSideEffects())
1120 if (Call->isConvergent())
1123 CI.insert(Call, VN);
1124 } else if (HoistingGeps || !isa<GetElementPtrInst>(&I1))
1125 // Do not hoist scalars past calls that may write to memory because
1126 // that could result in spills later. geps are handled separately.
1127 // TODO: We can relax this for targets like AArch64 as they have more
1128 // registers than X86.
1133 HoistingPointList HPL;
1134 computeInsertionPoints(II.getVNTable(), HPL, InsKind::Scalar);
1135 computeInsertionPoints(LI.getVNTable(), HPL, InsKind::Load);
1136 computeInsertionPoints(SI.getVNTable(), HPL, InsKind::Store);
1137 computeInsertionPoints(CI.getScalarVNTable(), HPL, InsKind::Scalar);
1138 computeInsertionPoints(CI.getLoadVNTable(), HPL, InsKind::Load);
1139 computeInsertionPoints(CI.getStoreVNTable(), HPL, InsKind::Store);
1144 class GVNHoistLegacyPass : public FunctionPass {
1148 GVNHoistLegacyPass() : FunctionPass(ID) {
1149 initializeGVNHoistLegacyPassPass(*PassRegistry::getPassRegistry());
1152 bool runOnFunction(Function &F) override {
1153 if (skipFunction(F))
1155 auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
1156 auto &PDT = getAnalysis<PostDominatorTreeWrapperPass>().getPostDomTree();
1157 auto &AA = getAnalysis<AAResultsWrapperPass>().getAAResults();
1158 auto &MD = getAnalysis<MemoryDependenceWrapperPass>().getMemDep();
1159 auto &MSSA = getAnalysis<MemorySSAWrapperPass>().getMSSA();
1161 GVNHoist G(&DT, &PDT, &AA, &MD, &MSSA);
1165 void getAnalysisUsage(AnalysisUsage &AU) const override {
1166 AU.addRequired<DominatorTreeWrapperPass>();
1167 AU.addRequired<PostDominatorTreeWrapperPass>();
1168 AU.addRequired<AAResultsWrapperPass>();
1169 AU.addRequired<MemoryDependenceWrapperPass>();
1170 AU.addRequired<MemorySSAWrapperPass>();
1171 AU.addPreserved<DominatorTreeWrapperPass>();
1172 AU.addPreserved<MemorySSAWrapperPass>();
1173 AU.addPreserved<GlobalsAAWrapperPass>();
1177 } // end namespace llvm
1179 PreservedAnalyses GVNHoistPass::run(Function &F, FunctionAnalysisManager &AM) {
1180 DominatorTree &DT = AM.getResult<DominatorTreeAnalysis>(F);
1181 PostDominatorTree &PDT = AM.getResult<PostDominatorTreeAnalysis>(F);
1182 AliasAnalysis &AA = AM.getResult<AAManager>(F);
1183 MemoryDependenceResults &MD = AM.getResult<MemoryDependenceAnalysis>(F);
1184 MemorySSA &MSSA = AM.getResult<MemorySSAAnalysis>(F).getMSSA();
1185 GVNHoist G(&DT, &PDT, &AA, &MD, &MSSA);
1187 return PreservedAnalyses::all();
1189 PreservedAnalyses PA;
1190 PA.preserve<DominatorTreeAnalysis>();
1191 PA.preserve<MemorySSAAnalysis>();
1192 PA.preserve<GlobalsAA>();
1196 char GVNHoistLegacyPass::ID = 0;
1198 INITIALIZE_PASS_BEGIN(GVNHoistLegacyPass, "gvn-hoist",
1199 "Early GVN Hoisting of Expressions", false, false)
1200 INITIALIZE_PASS_DEPENDENCY(MemoryDependenceWrapperPass)
1201 INITIALIZE_PASS_DEPENDENCY(MemorySSAWrapperPass)
1202 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
1203 INITIALIZE_PASS_DEPENDENCY(PostDominatorTreeWrapperPass)
1204 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
1205 INITIALIZE_PASS_END(GVNHoistLegacyPass, "gvn-hoist",
1206 "Early GVN Hoisting of Expressions", false, false)
1208 FunctionPass *llvm::createGVNHoistPass() { return new GVNHoistLegacyPass(); }