LLVM 17.0.0git
GVNHoist.cpp
Go to the documentation of this file.
1//===- GVNHoist.cpp - Hoist scalar and load expressions -------------------===//
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// This pass hoists expressions from branches to a common dominator. It uses
10// GVN (global value numbering) to discover expressions computing the same
11// values. The primary goals of code-hoisting are:
12// 1. To reduce the code size.
13// 2. In some cases reduce critical path (by exposing more ILP).
14//
15// The algorithm factors out the reachability of values such that multiple
16// queries to find reachability of values are fast. This is based on finding the
17// ANTIC points in the CFG which do not change during hoisting. The ANTIC points
18// are basically the dominance-frontiers in the inverse graph. So we introduce a
19// data structure (CHI nodes) to keep track of values flowing out of a basic
20// block. We only do this for values with multiple occurrences in the function
21// as they are the potential hoistable candidates. This approach allows us to
22// hoist instructions to a basic block with more than two successors, as well as
23// deal with infinite loops in a trivial way.
24//
25// Limitations: This pass does not hoist fully redundant expressions because
26// they are already handled by GVN-PRE. It is advisable to run gvn-hoist before
27// and after gvn-pre because gvn-pre creates opportunities for more instructions
28// to be hoisted.
29//
30// Hoisting may affect the performance in some cases. To mitigate that, hoisting
31// is disabled in the following cases.
32// 1. Scalars across calls.
33// 2. geps when corresponding load/store cannot be hoisted.
34//===----------------------------------------------------------------------===//
35
36#include "llvm/ADT/DenseMap.h"
37#include "llvm/ADT/DenseSet.h"
38#include "llvm/ADT/STLExtras.h"
41#include "llvm/ADT/Statistic.h"
51#include "llvm/IR/Argument.h"
52#include "llvm/IR/BasicBlock.h"
53#include "llvm/IR/CFG.h"
54#include "llvm/IR/Constants.h"
55#include "llvm/IR/Dominators.h"
56#include "llvm/IR/Function.h"
57#include "llvm/IR/Instruction.h"
60#include "llvm/IR/LLVMContext.h"
61#include "llvm/IR/PassManager.h"
62#include "llvm/IR/Use.h"
63#include "llvm/IR/User.h"
64#include "llvm/IR/Value.h"
66#include "llvm/Pass.h"
69#include "llvm/Support/Debug.h"
74#include <algorithm>
75#include <cassert>
76#include <iterator>
77#include <memory>
78#include <utility>
79#include <vector>
80
81using namespace llvm;
82
83#define DEBUG_TYPE "gvn-hoist"
84
85STATISTIC(NumHoisted, "Number of instructions hoisted");
86STATISTIC(NumRemoved, "Number of instructions removed");
87STATISTIC(NumLoadsHoisted, "Number of loads hoisted");
88STATISTIC(NumLoadsRemoved, "Number of loads removed");
89STATISTIC(NumStoresHoisted, "Number of stores hoisted");
90STATISTIC(NumStoresRemoved, "Number of stores removed");
91STATISTIC(NumCallsHoisted, "Number of calls hoisted");
92STATISTIC(NumCallsRemoved, "Number of calls removed");
93
94static cl::opt<int>
95 MaxHoistedThreshold("gvn-max-hoisted", cl::Hidden, cl::init(-1),
96 cl::desc("Max number of instructions to hoist "
97 "(default unlimited = -1)"));
98
100 "gvn-hoist-max-bbs", cl::Hidden, cl::init(4),
101 cl::desc("Max number of basic blocks on the path between "
102 "hoisting locations (default = 4, unlimited = -1)"));
103
105 "gvn-hoist-max-depth", cl::Hidden, cl::init(100),
106 cl::desc("Hoist instructions from the beginning of the BB up to the "
107 "maximum specified depth (default = 100, unlimited = -1)"));
108
109static cl::opt<int>
110 MaxChainLength("gvn-hoist-max-chain-length", cl::Hidden, cl::init(10),
111 cl::desc("Maximum length of dependent chains to hoist "
112 "(default = 10, unlimited = -1)"));
113
114namespace llvm {
115
119
120// Each element of a hoisting list contains the basic block where to hoist and
121// a list of instructions to be hoisted.
122using HoistingPointInfo = std::pair<BasicBlock *, SmallVecInsn>;
123
125
126// A map from a pair of VNs to all the instructions with those VNs.
127using VNType = std::pair<unsigned, uintptr_t>;
128
130
131// CHI keeps information about values flowing out of a basic block. It is
132// similar to PHI but in the inverse graph, and used for outgoing values on each
133// edge. For conciseness, it is computed only for instructions with multiple
134// occurrences in the CFG because they are the only hoistable candidates.
135// A (CHI[{V, B, I1}, {V, C, I2}]
136// / \
137// / \
138// B(I1) C (I2)
139// The Value number for both I1 and I2 is V, the CHI node will save the
140// instruction as well as the edge where the value is flowing to.
141struct CHIArg {
143
144 // Edge destination (shows the direction of flow), may not be where the I is.
146
147 // The instruction (VN) which uses the values flowing out of CHI.
149
150 bool operator==(const CHIArg &A) const { return VN == A.VN; }
151 bool operator!=(const CHIArg &A) const { return !(*this == A); }
152};
153
159
160// An invalid value number Used when inserting a single value number into
161// VNtoInsns.
162enum : uintptr_t { InvalidVN = ~(uintptr_t)2 };
163
164// Records all scalar instructions candidate for code hoisting.
165class InsnInfo {
166 VNtoInsns VNtoScalars;
167
168public:
169 // Inserts I and its value number in VNtoScalars.
171 // Scalar instruction.
172 unsigned V = VN.lookupOrAdd(I);
173 VNtoScalars[{V, InvalidVN}].push_back(I);
174 }
175
176 const VNtoInsns &getVNTable() const { return VNtoScalars; }
177};
178
179// Records all load instructions candidate for code hoisting.
180class LoadInfo {
181 VNtoInsns VNtoLoads;
182
183public:
184 // Insert Load and the value number of its memory address in VNtoLoads.
186 if (Load->isSimple()) {
187 unsigned V = VN.lookupOrAdd(Load->getPointerOperand());
188 // With opaque pointers we may have loads from the same pointer with
189 // different result types, which should be disambiguated.
190 VNtoLoads[{V, (uintptr_t)Load->getType()}].push_back(Load);
191 }
192 }
193
194 const VNtoInsns &getVNTable() const { return VNtoLoads; }
195};
196
197// Records all store instructions candidate for code hoisting.
199 VNtoInsns VNtoStores;
200
201public:
202 // Insert the Store and a hash number of the store address and the stored
203 // value in VNtoStores.
205 if (!Store->isSimple())
206 return;
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);
211 }
212
213 const VNtoInsns &getVNTable() const { return VNtoStores; }
214};
215
216// Records all call instructions candidate for code hoisting.
217class CallInfo {
218 VNtoInsns VNtoCallsScalars;
219 VNtoInsns VNtoCallsLoads;
220 VNtoInsns VNtoCallsStores;
221
222public:
223 // Insert Call and its value numbering in one of the VNtoCalls* containers.
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);
230
231 if (Call->doesNotAccessMemory())
232 VNtoCallsScalars[Entry].push_back(Call);
233 else if (Call->onlyReadsMemory())
234 VNtoCallsLoads[Entry].push_back(Call);
235 else
236 VNtoCallsStores[Entry].push_back(Call);
237 }
238
239 const VNtoInsns &getScalarVNTable() const { return VNtoCallsScalars; }
240 const VNtoInsns &getLoadVNTable() const { return VNtoCallsLoads; }
241 const VNtoInsns &getStoreVNTable() const { return VNtoCallsStores; }
242};
243
245 static const unsigned KnownIDs[] = {LLVMContext::MD_tbaa,
246 LLVMContext::MD_alias_scope,
247 LLVMContext::MD_noalias,
248 LLVMContext::MD_range,
249 LLVMContext::MD_fpmath,
250 LLVMContext::MD_invariant_load,
251 LLVMContext::MD_invariant_group,
252 LLVMContext::MD_access_group};
253 combineMetadata(ReplInst, I, KnownIDs, true);
254}
255
256// This pass hoists common computations across branches sharing common
257// dominator. The primary goal is to reduce the code size, and in some
258// cases reduce critical path (by exposing more ILP).
259class GVNHoist {
260public:
263 : DT(DT), PDT(PDT), AA(AA), MD(MD), MSSA(MSSA),
264 MSSAUpdater(std::make_unique<MemorySSAUpdater>(MSSA)) {
265 MSSA->ensureOptimizedUses();
266 }
267
268 bool run(Function &F);
269
270 // Copied from NewGVN.cpp
271 // This function provides global ranking of operations so that we can place
272 // them in a canonical order. Note that rank alone is not necessarily enough
273 // for a complete ordering, as constants all have the same rank. However,
274 // generally, we will simplify an operation with all constants so that it
275 // doesn't matter what order they appear in.
276 unsigned int rank(const Value *V) const;
277
278private:
280 DominatorTree *DT;
282 AliasAnalysis *AA;
284 MemorySSA *MSSA;
285 std::unique_ptr<MemorySSAUpdater> MSSAUpdater;
287 BBSideEffectsSet BBSideEffects;
288 DenseSet<const BasicBlock *> HoistBarrier;
290 unsigned NumFuncArgs;
291 const bool HoistingGeps = false;
292
293 enum InsKind { Unknown, Scalar, Load, Store };
294
295 // Return true when there are exception handling in BB.
296 bool hasEH(const BasicBlock *BB);
297
298 // Return true when I1 appears before I2 in the instructions of BB.
299 bool firstInBB(const Instruction *I1, const Instruction *I2) {
300 assert(I1->getParent() == I2->getParent());
301 unsigned I1DFS = DFSNumber.lookup(I1);
302 unsigned I2DFS = DFSNumber.lookup(I2);
303 assert(I1DFS && I2DFS);
304 return I1DFS < I2DFS;
305 }
306
307 // Return true when there are memory uses of Def in BB.
308 bool hasMemoryUse(const Instruction *NewPt, MemoryDef *Def,
309 const BasicBlock *BB);
310
311 bool hasEHhelper(const BasicBlock *BB, const BasicBlock *SrcBB,
312 int &NBBsOnAllPaths);
313
314 // Return true when there are exception handling or loads of memory Def
315 // between Def and NewPt. This function is only called for stores: Def is
316 // the MemoryDef of the store to be hoisted.
317
318 // Decrement by 1 NBBsOnAllPaths for each block between HoistPt and BB, and
319 // return true when the counter NBBsOnAllPaths reaces 0, except when it is
320 // initialized to -1 which is unlimited.
321 bool hasEHOrLoadsOnPath(const Instruction *NewPt, MemoryDef *Def,
322 int &NBBsOnAllPaths);
323
324 // Return true when there are exception handling between HoistPt and BB.
325 // Decrement by 1 NBBsOnAllPaths for each block between HoistPt and BB, and
326 // return true when the counter NBBsOnAllPaths reaches 0, except when it is
327 // initialized to -1 which is unlimited.
328 bool hasEHOnPath(const BasicBlock *HoistPt, const BasicBlock *SrcBB,
329 int &NBBsOnAllPaths);
330
331 // Return true when it is safe to hoist a memory load or store U from OldPt
332 // to NewPt.
333 bool safeToHoistLdSt(const Instruction *NewPt, const Instruction *OldPt,
334 MemoryUseOrDef *U, InsKind K, int &NBBsOnAllPaths);
335
336 // Return true when it is safe to hoist scalar instructions from all blocks in
337 // WL to HoistBB.
338 bool safeToHoistScalar(const BasicBlock *HoistBB, const BasicBlock *BB,
339 int &NBBsOnAllPaths) {
340 return !hasEHOnPath(HoistBB, BB, NBBsOnAllPaths);
341 }
342
343 // In the inverse CFG, the dominance frontier of basic block (BB) is the
344 // point where ANTIC needs to be computed for instructions which are going
345 // to be hoisted. Since this point does not change during gvn-hoist,
346 // we compute it only once (on demand).
347 // The ides is inspired from:
348 // "Partial Redundancy Elimination in SSA Form"
349 // ROBERT KENNEDY, SUN CHAN, SHIN-MING LIU, RAYMOND LO, PENG TU and FRED CHOW
350 // They use similar idea in the forward graph to find fully redundant and
351 // partially redundant expressions, here it is used in the inverse graph to
352 // find fully anticipable instructions at merge point (post-dominator in
353 // the inverse CFG).
354 // Returns the edge via which an instruction in BB will get the values from.
355
356 // Returns true when the values are flowing out to each edge.
357 bool valueAnticipable(CHIArgs C, Instruction *TI) const;
358
359 // Check if it is safe to hoist values tracked by CHI in the range
360 // [Begin, End) and accumulate them in Safe.
361 void checkSafety(CHIArgs C, BasicBlock *BB, InsKind K,
363
364 using RenameStackType = DenseMap<VNType, SmallVector<Instruction *, 2>>;
365
366 // Push all the VNs corresponding to BB into RenameStack.
367 void fillRenameStack(BasicBlock *BB, InValuesType &ValueBBs,
368 RenameStackType &RenameStack);
369
370 void fillChiArgs(BasicBlock *BB, OutValuesType &CHIBBs,
371 RenameStackType &RenameStack);
372
373 // Walk the post-dominator tree top-down and use a stack for each value to
374 // store the last value you see. When you hit a CHI from a given edge, the
375 // value to use as the argument is at the top of the stack, add the value to
376 // CHI and pop.
377 void insertCHI(InValuesType &ValueBBs, OutValuesType &CHIBBs) {
378 auto Root = PDT->getNode(nullptr);
379 if (!Root)
380 return;
381 // Depth first walk on PDom tree to fill the CHIargs at each PDF.
382 for (auto *Node : depth_first(Root)) {
383 BasicBlock *BB = Node->getBlock();
384 if (!BB)
385 continue;
386
387 RenameStackType RenameStack;
388 // Collect all values in BB and push to stack.
389 fillRenameStack(BB, ValueBBs, RenameStack);
390
391 // Fill outgoing values in each CHI corresponding to BB.
392 fillChiArgs(BB, CHIBBs, RenameStack);
393 }
394 }
395
396 // Walk all the CHI-nodes to find ones which have a empty-entry and remove
397 // them Then collect all the instructions which are safe to hoist and see if
398 // they form a list of anticipable values. OutValues contains CHIs
399 // corresponding to each basic block.
400 void findHoistableCandidates(OutValuesType &CHIBBs, InsKind K,
401 HoistingPointList &HPL);
402
403 // Compute insertion points for each values which can be fully anticipated at
404 // a dominator. HPL contains all such values.
405 void computeInsertionPoints(const VNtoInsns &Map, HoistingPointList &HPL,
406 InsKind K) {
407 // Sort VNs based on their rankings
408 std::vector<VNType> Ranks;
409 for (const auto &Entry : Map) {
410 Ranks.push_back(Entry.first);
411 }
412
413 // TODO: Remove fully-redundant expressions.
414 // Get instruction from the Map, assume that all the Instructions
415 // with same VNs have same rank (this is an approximation).
416 llvm::sort(Ranks, [this, &Map](const VNType &r1, const VNType &r2) {
417 return (rank(*Map.lookup(r1).begin()) < rank(*Map.lookup(r2).begin()));
418 });
419
420 // - Sort VNs according to their rank, and start with lowest ranked VN
421 // - Take a VN and for each instruction with same VN
422 // - Find the dominance frontier in the inverse graph (PDF)
423 // - Insert the chi-node at PDF
424 // - Remove the chi-nodes with missing entries
425 // - Remove values from CHI-nodes which do not truly flow out, e.g.,
426 // modified along the path.
427 // - Collect the remaining values that are still anticipable
429 ReverseIDFCalculator IDFs(*PDT);
430 OutValuesType OutValue;
431 InValuesType InValue;
432 for (const auto &R : Ranks) {
433 const SmallVecInsn &V = Map.lookup(R);
434 if (V.size() < 2)
435 continue;
436 const VNType &VN = R;
438 for (const auto &I : V) {
439 BasicBlock *BBI = I->getParent();
440 if (!hasEH(BBI))
441 VNBlocks.insert(BBI);
442 }
443 // Compute the Post Dominance Frontiers of each basic block
444 // The dominance frontier of a live block X in the reverse
445 // control graph is the set of blocks upon which X is control
446 // dependent. The following sequence computes the set of blocks
447 // which currently have dead terminators that are control
448 // dependence sources of a block which is in NewLiveBlocks.
449 IDFs.setDefiningBlocks(VNBlocks);
450 IDFBlocks.clear();
451 IDFs.calculate(IDFBlocks);
452
453 // Make a map of BB vs instructions to be hoisted.
454 for (unsigned i = 0; i < V.size(); ++i) {
455 InValue[V[i]->getParent()].push_back(std::make_pair(VN, V[i]));
456 }
457 // Insert empty CHI node for this VN. This is used to factor out
458 // basic blocks where the ANTIC can potentially change.
459 CHIArg EmptyChi = {VN, nullptr, nullptr};
460 for (auto *IDFBB : IDFBlocks) {
461 for (unsigned i = 0; i < V.size(); ++i) {
462 // Ignore spurious PDFs.
463 if (DT->properlyDominates(IDFBB, V[i]->getParent())) {
464 OutValue[IDFBB].push_back(EmptyChi);
465 LLVM_DEBUG(dbgs() << "\nInserting a CHI for BB: "
466 << IDFBB->getName() << ", for Insn: " << *V[i]);
467 }
468 }
469 }
470 }
471
472 // Insert CHI args at each PDF to iterate on factored graph of
473 // control dependence.
474 insertCHI(InValue, OutValue);
475 // Using the CHI args inserted at each PDF, find fully anticipable values.
476 findHoistableCandidates(OutValue, K, HPL);
477 }
478
479 // Return true when all operands of Instr are available at insertion point
480 // HoistPt. When limiting the number of hoisted expressions, one could hoist
481 // a load without hoisting its access function. So before hoisting any
482 // expression, make sure that all its operands are available at insert point.
483 bool allOperandsAvailable(const Instruction *I,
484 const BasicBlock *HoistPt) const;
485
486 // Same as allOperandsAvailable with recursive check for GEP operands.
487 bool allGepOperandsAvailable(const Instruction *I,
488 const BasicBlock *HoistPt) const;
489
490 // Make all operands of the GEP available.
491 void makeGepsAvailable(Instruction *Repl, BasicBlock *HoistPt,
492 const SmallVecInsn &InstructionsToHoist,
493 Instruction *Gep) const;
494
495 void updateAlignment(Instruction *I, Instruction *Repl);
496
497 // Remove all the instructions in Candidates and replace their usage with
498 // Repl. Returns the number of instructions removed.
499 unsigned rauw(const SmallVecInsn &Candidates, Instruction *Repl,
500 MemoryUseOrDef *NewMemAcc);
501
502 // Replace all Memory PHI usage with NewMemAcc.
503 void raMPHIuw(MemoryUseOrDef *NewMemAcc);
504
505 // Remove all other instructions and replace them with Repl.
506 unsigned removeAndReplace(const SmallVecInsn &Candidates, Instruction *Repl,
507 BasicBlock *DestBB, bool MoveAccess);
508
509 // In the case Repl is a load or a store, we make all their GEPs
510 // available: GEPs are not hoisted by default to avoid the address
511 // computations to be hoisted without the associated load or store.
512 bool makeGepOperandsAvailable(Instruction *Repl, BasicBlock *HoistPt,
513 const SmallVecInsn &InstructionsToHoist) const;
514
515 std::pair<unsigned, unsigned> hoist(HoistingPointList &HPL);
516
517 // Hoist all expressions. Returns Number of scalars hoisted
518 // and number of non-scalars hoisted.
519 std::pair<unsigned, unsigned> hoistExpressions(Function &F);
520};
521
523 NumFuncArgs = F.arg_size();
524 VN.setDomTree(DT);
525 VN.setAliasAnalysis(AA);
526 VN.setMemDep(MD);
527 bool Res = false;
528 // Perform DFS Numbering of instructions.
529 unsigned BBI = 0;
530 for (const BasicBlock *BB : depth_first(&F.getEntryBlock())) {
531 DFSNumber[BB] = ++BBI;
532 unsigned I = 0;
533 for (const auto &Inst : *BB)
534 DFSNumber[&Inst] = ++I;
535 }
536
537 int ChainLength = 0;
538
539 // FIXME: use lazy evaluation of VN to avoid the fix-point computation.
540 while (true) {
541 if (MaxChainLength != -1 && ++ChainLength >= MaxChainLength)
542 return Res;
543
544 auto HoistStat = hoistExpressions(F);
545 if (HoistStat.first + HoistStat.second == 0)
546 return Res;
547
548 if (HoistStat.second > 0)
549 // To address a limitation of the current GVN, we need to rerun the
550 // hoisting after we hoisted loads or stores in order to be able to
551 // hoist all scalars dependent on the hoisted ld/st.
552 VN.clear();
553
554 Res = true;
555 }
556
557 return Res;
558}
559
560unsigned int GVNHoist::rank(const Value *V) const {
561 // Prefer constants to undef to anything else
562 // Undef is a constant, have to check it first.
563 // Prefer smaller constants to constantexprs
564 if (isa<ConstantExpr>(V))
565 return 2;
566 if (isa<UndefValue>(V))
567 return 1;
568 if (isa<Constant>(V))
569 return 0;
570 else if (auto *A = dyn_cast<Argument>(V))
571 return 3 + A->getArgNo();
572
573 // Need to shift the instruction DFS by number of arguments + 3 to account
574 // for the constant and argument ranking above.
575 auto Result = DFSNumber.lookup(V);
576 if (Result > 0)
577 return 4 + NumFuncArgs + Result;
578 // Unreachable or something else, just return a really large number.
579 return ~0;
580}
581
582bool GVNHoist::hasEH(const BasicBlock *BB) {
583 auto It = BBSideEffects.find(BB);
584 if (It != BBSideEffects.end())
585 return It->second;
586
587 if (BB->isEHPad() || BB->hasAddressTaken()) {
588 BBSideEffects[BB] = true;
589 return true;
590 }
591
592 if (BB->getTerminator()->mayThrow()) {
593 BBSideEffects[BB] = true;
594 return true;
595 }
596
597 BBSideEffects[BB] = false;
598 return false;
599}
600
601bool GVNHoist::hasMemoryUse(const Instruction *NewPt, MemoryDef *Def,
602 const BasicBlock *BB) {
603 const MemorySSA::AccessList *Acc = MSSA->getBlockAccesses(BB);
604 if (!Acc)
605 return false;
606
607 Instruction *OldPt = Def->getMemoryInst();
608 const BasicBlock *OldBB = OldPt->getParent();
609 const BasicBlock *NewBB = NewPt->getParent();
610 bool ReachedNewPt = false;
611
612 for (const MemoryAccess &MA : *Acc)
613 if (const MemoryUse *MU = dyn_cast<MemoryUse>(&MA)) {
614 Instruction *Insn = MU->getMemoryInst();
615
616 // Do not check whether MU aliases Def when MU occurs after OldPt.
617 if (BB == OldBB && firstInBB(OldPt, Insn))
618 break;
619
620 // Do not check whether MU aliases Def when MU occurs before NewPt.
621 if (BB == NewBB) {
622 if (!ReachedNewPt) {
623 if (firstInBB(Insn, NewPt))
624 continue;
625 ReachedNewPt = true;
626 }
627 }
628 if (MemorySSAUtil::defClobbersUseOrDef(Def, MU, *AA))
629 return true;
630 }
631
632 return false;
633}
634
635bool GVNHoist::hasEHhelper(const BasicBlock *BB, const BasicBlock *SrcBB,
636 int &NBBsOnAllPaths) {
637 // Stop walk once the limit is reached.
638 if (NBBsOnAllPaths == 0)
639 return true;
640
641 // Impossible to hoist with exceptions on the path.
642 if (hasEH(BB))
643 return true;
644
645 // No such instruction after HoistBarrier in a basic block was
646 // selected for hoisting so instructions selected within basic block with
647 // a hoist barrier can be hoisted.
648 if ((BB != SrcBB) && HoistBarrier.count(BB))
649 return true;
650
651 return false;
652}
653
654bool GVNHoist::hasEHOrLoadsOnPath(const Instruction *NewPt, MemoryDef *Def,
655 int &NBBsOnAllPaths) {
656 const BasicBlock *NewBB = NewPt->getParent();
657 const BasicBlock *OldBB = Def->getBlock();
658 assert(DT->dominates(NewBB, OldBB) && "invalid path");
659 assert(DT->dominates(Def->getDefiningAccess()->getBlock(), NewBB) &&
660 "def does not dominate new hoisting point");
661
662 // Walk all basic blocks reachable in depth-first iteration on the inverse
663 // CFG from OldBB to NewBB. These blocks are all the blocks that may be
664 // executed between the execution of NewBB and OldBB. Hoisting an expression
665 // from OldBB into NewBB has to be safe on all execution paths.
666 for (auto I = idf_begin(OldBB), E = idf_end(OldBB); I != E;) {
667 const BasicBlock *BB = *I;
668 if (BB == NewBB) {
669 // Stop traversal when reaching HoistPt.
670 I.skipChildren();
671 continue;
672 }
673
674 if (hasEHhelper(BB, OldBB, NBBsOnAllPaths))
675 return true;
676
677 // Check that we do not move a store past loads.
678 if (hasMemoryUse(NewPt, Def, BB))
679 return true;
680
681 // -1 is unlimited number of blocks on all paths.
682 if (NBBsOnAllPaths != -1)
683 --NBBsOnAllPaths;
684
685 ++I;
686 }
687
688 return false;
689}
690
691bool GVNHoist::hasEHOnPath(const BasicBlock *HoistPt, const BasicBlock *SrcBB,
692 int &NBBsOnAllPaths) {
693 assert(DT->dominates(HoistPt, SrcBB) && "Invalid path");
694
695 // Walk all basic blocks reachable in depth-first iteration on
696 // the inverse CFG from BBInsn to NewHoistPt. These blocks are all the
697 // blocks that may be executed between the execution of NewHoistPt and
698 // BBInsn. Hoisting an expression from BBInsn into NewHoistPt has to be safe
699 // on all execution paths.
700 for (auto I = idf_begin(SrcBB), E = idf_end(SrcBB); I != E;) {
701 const BasicBlock *BB = *I;
702 if (BB == HoistPt) {
703 // Stop traversal when reaching NewHoistPt.
704 I.skipChildren();
705 continue;
706 }
707
708 if (hasEHhelper(BB, SrcBB, NBBsOnAllPaths))
709 return true;
710
711 // -1 is unlimited number of blocks on all paths.
712 if (NBBsOnAllPaths != -1)
713 --NBBsOnAllPaths;
714
715 ++I;
716 }
717
718 return false;
719}
720
721bool GVNHoist::safeToHoistLdSt(const Instruction *NewPt,
722 const Instruction *OldPt, MemoryUseOrDef *U,
723 GVNHoist::InsKind K, int &NBBsOnAllPaths) {
724 // In place hoisting is safe.
725 if (NewPt == OldPt)
726 return true;
727
728 const BasicBlock *NewBB = NewPt->getParent();
729 const BasicBlock *OldBB = OldPt->getParent();
730 const BasicBlock *UBB = U->getBlock();
731
732 // Check for dependences on the Memory SSA.
733 MemoryAccess *D = U->getDefiningAccess();
734 BasicBlock *DBB = D->getBlock();
735 if (DT->properlyDominates(NewBB, DBB))
736 // Cannot move the load or store to NewBB above its definition in DBB.
737 return false;
738
739 if (NewBB == DBB && !MSSA->isLiveOnEntryDef(D))
740 if (auto *UD = dyn_cast<MemoryUseOrDef>(D))
741 if (!firstInBB(UD->getMemoryInst(), NewPt))
742 // Cannot move the load or store to NewPt above its definition in D.
743 return false;
744
745 // Check for unsafe hoistings due to side effects.
746 if (K == InsKind::Store) {
747 if (hasEHOrLoadsOnPath(NewPt, cast<MemoryDef>(U), NBBsOnAllPaths))
748 return false;
749 } else if (hasEHOnPath(NewBB, OldBB, NBBsOnAllPaths))
750 return false;
751
752 if (UBB == NewBB) {
753 if (DT->properlyDominates(DBB, NewBB))
754 return true;
755 assert(UBB == DBB);
756 assert(MSSA->locallyDominates(D, U));
757 }
758
759 // No side effects: it is safe to hoist.
760 return true;
761}
762
763bool GVNHoist::valueAnticipable(CHIArgs C, Instruction *TI) const {
764 if (TI->getNumSuccessors() > (unsigned)size(C))
765 return false; // Not enough args in this CHI.
766
767 for (auto CHI : C) {
768 // Find if all the edges have values flowing out of BB.
769 if (!llvm::is_contained(successors(TI), CHI.Dest))
770 return false;
771 }
772 return true;
773}
774
775void GVNHoist::checkSafety(CHIArgs C, BasicBlock *BB, GVNHoist::InsKind K,
777 int NumBBsOnAllPaths = MaxNumberOfBBSInPath;
778 const Instruction *T = BB->getTerminator();
779 for (auto CHI : C) {
780 Instruction *Insn = CHI.I;
781 if (!Insn) // No instruction was inserted in this CHI.
782 continue;
783 // If the Terminator is some kind of "exotic terminator" that produces a
784 // value (such as InvokeInst, CallBrInst, or CatchSwitchInst) which the CHI
785 // uses, it is not safe to hoist the use above the def.
786 if (!T->use_empty() && is_contained(Insn->operands(), cast<const Value>(T)))
787 continue;
788 if (K == InsKind::Scalar) {
789 if (safeToHoistScalar(BB, Insn->getParent(), NumBBsOnAllPaths))
790 Safe.push_back(CHI);
791 } else {
792 if (MemoryUseOrDef *UD = MSSA->getMemoryAccess(Insn))
793 if (safeToHoistLdSt(T, Insn, UD, K, NumBBsOnAllPaths))
794 Safe.push_back(CHI);
795 }
796 }
797}
798
799void GVNHoist::fillRenameStack(BasicBlock *BB, InValuesType &ValueBBs,
800 GVNHoist::RenameStackType &RenameStack) {
801 auto it1 = ValueBBs.find(BB);
802 if (it1 != ValueBBs.end()) {
803 // Iterate in reverse order to keep lower ranked values on the top.
804 LLVM_DEBUG(dbgs() << "\nVisiting: " << BB->getName()
805 << " for pushing instructions on stack";);
806 for (std::pair<VNType, Instruction *> &VI : reverse(it1->second)) {
807 // Get the value of instruction I
808 LLVM_DEBUG(dbgs() << "\nPushing on stack: " << *VI.second);
809 RenameStack[VI.first].push_back(VI.second);
810 }
811 }
812}
813
814void GVNHoist::fillChiArgs(BasicBlock *BB, OutValuesType &CHIBBs,
815 GVNHoist::RenameStackType &RenameStack) {
816 // For each *predecessor* (because Post-DOM) of BB check if it has a CHI
817 for (auto *Pred : predecessors(BB)) {
818 auto P = CHIBBs.find(Pred);
819 if (P == CHIBBs.end()) {
820 continue;
821 }
822 LLVM_DEBUG(dbgs() << "\nLooking at CHIs in: " << Pred->getName(););
823 // A CHI is found (BB -> Pred is an edge in the CFG)
824 // Pop the stack until Top(V) = Ve.
825 auto &VCHI = P->second;
826 for (auto It = VCHI.begin(), E = VCHI.end(); It != E;) {
827 CHIArg &C = *It;
828 if (!C.Dest) {
829 auto si = RenameStack.find(C.VN);
830 // The Basic Block where CHI is must dominate the value we want to
831 // track in a CHI. In the PDom walk, there can be values in the
832 // stack which are not control dependent e.g., nested loop.
833 if (si != RenameStack.end() && si->second.size() &&
834 DT->properlyDominates(Pred, si->second.back()->getParent())) {
835 C.Dest = BB; // Assign the edge
836 C.I = si->second.pop_back_val(); // Assign the argument
838 << "\nCHI Inserted in BB: " << C.Dest->getName() << *C.I
839 << ", VN: " << C.VN.first << ", " << C.VN.second);
840 }
841 // Move to next CHI of a different value
842 It = std::find_if(It, VCHI.end(), [It](CHIArg &A) { return A != *It; });
843 } else
844 ++It;
845 }
846 }
847}
848
849void GVNHoist::findHoistableCandidates(OutValuesType &CHIBBs,
850 GVNHoist::InsKind K,
851 HoistingPointList &HPL) {
852 auto cmpVN = [](const CHIArg &A, const CHIArg &B) { return A.VN < B.VN; };
853
854 // CHIArgs now have the outgoing values, so check for anticipability and
855 // accumulate hoistable candidates in HPL.
856 for (std::pair<BasicBlock *, SmallVector<CHIArg, 2>> &A : CHIBBs) {
857 BasicBlock *BB = A.first;
858 SmallVectorImpl<CHIArg> &CHIs = A.second;
859 // Vector of PHIs contains PHIs for different instructions.
860 // Sort the args according to their VNs, such that identical
861 // instructions are together.
862 llvm::stable_sort(CHIs, cmpVN);
863 auto TI = BB->getTerminator();
864 auto B = CHIs.begin();
865 // [PreIt, PHIIt) form a range of CHIs which have identical VNs.
866 auto PHIIt = llvm::find_if(CHIs, [B](CHIArg &A) { return A != *B; });
867 auto PrevIt = CHIs.begin();
868 while (PrevIt != PHIIt) {
869 // Collect values which satisfy safety checks.
871 // We check for safety first because there might be multiple values in
872 // the same path, some of which are not safe to be hoisted, but overall
873 // each edge has at least one value which can be hoisted, making the
874 // value anticipable along that path.
875 checkSafety(make_range(PrevIt, PHIIt), BB, K, Safe);
876
877 // List of safe values should be anticipable at TI.
878 if (valueAnticipable(make_range(Safe.begin(), Safe.end()), TI)) {
879 HPL.push_back({BB, SmallVecInsn()});
880 SmallVecInsn &V = HPL.back().second;
881 for (auto B : Safe)
882 V.push_back(B.I);
883 }
884
885 // Check other VNs
886 PrevIt = PHIIt;
887 PHIIt = std::find_if(PrevIt, CHIs.end(),
888 [PrevIt](CHIArg &A) { return A != *PrevIt; });
889 }
890 }
891}
892
893bool GVNHoist::allOperandsAvailable(const Instruction *I,
894 const BasicBlock *HoistPt) const {
895 for (const Use &Op : I->operands())
896 if (const auto *Inst = dyn_cast<Instruction>(&Op))
897 if (!DT->dominates(Inst->getParent(), HoistPt))
898 return false;
899
900 return true;
901}
902
903bool GVNHoist::allGepOperandsAvailable(const Instruction *I,
904 const BasicBlock *HoistPt) const {
905 for (const Use &Op : I->operands())
906 if (const auto *Inst = dyn_cast<Instruction>(&Op))
907 if (!DT->dominates(Inst->getParent(), HoistPt)) {
908 if (const GetElementPtrInst *GepOp =
909 dyn_cast<GetElementPtrInst>(Inst)) {
910 if (!allGepOperandsAvailable(GepOp, HoistPt))
911 return false;
912 // Gep is available if all operands of GepOp are available.
913 } else {
914 // Gep is not available if it has operands other than GEPs that are
915 // defined in blocks not dominating HoistPt.
916 return false;
917 }
918 }
919 return true;
920}
921
922void GVNHoist::makeGepsAvailable(Instruction *Repl, BasicBlock *HoistPt,
923 const SmallVecInsn &InstructionsToHoist,
924 Instruction *Gep) const {
925 assert(allGepOperandsAvailable(Gep, HoistPt) && "GEP operands not available");
926
927 Instruction *ClonedGep = Gep->clone();
928 for (unsigned i = 0, e = Gep->getNumOperands(); i != e; ++i)
929 if (Instruction *Op = dyn_cast<Instruction>(Gep->getOperand(i))) {
930 // Check whether the operand is already available.
931 if (DT->dominates(Op->getParent(), HoistPt))
932 continue;
933
934 // As a GEP can refer to other GEPs, recursively make all the operands
935 // of this GEP available at HoistPt.
936 if (GetElementPtrInst *GepOp = dyn_cast<GetElementPtrInst>(Op))
937 makeGepsAvailable(ClonedGep, HoistPt, InstructionsToHoist, GepOp);
938 }
939
940 // Copy Gep and replace its uses in Repl with ClonedGep.
941 ClonedGep->insertBefore(HoistPt->getTerminator());
942
943 // Conservatively discard any optimization hints, they may differ on the
944 // other paths.
945 ClonedGep->dropUnknownNonDebugMetadata();
946
947 // If we have optimization hints which agree with each other along different
948 // paths, preserve them.
949 for (const Instruction *OtherInst : InstructionsToHoist) {
950 const GetElementPtrInst *OtherGep;
951 if (auto *OtherLd = dyn_cast<LoadInst>(OtherInst))
952 OtherGep = cast<GetElementPtrInst>(OtherLd->getPointerOperand());
953 else
954 OtherGep = cast<GetElementPtrInst>(
955 cast<StoreInst>(OtherInst)->getPointerOperand());
956 ClonedGep->andIRFlags(OtherGep);
957 }
958
959 // Replace uses of Gep with ClonedGep in Repl.
960 Repl->replaceUsesOfWith(Gep, ClonedGep);
961}
962
963void GVNHoist::updateAlignment(Instruction *I, Instruction *Repl) {
964 if (auto *ReplacementLoad = dyn_cast<LoadInst>(Repl)) {
965 ReplacementLoad->setAlignment(
966 std::min(ReplacementLoad->getAlign(), cast<LoadInst>(I)->getAlign()));
967 ++NumLoadsRemoved;
968 } else if (auto *ReplacementStore = dyn_cast<StoreInst>(Repl)) {
969 ReplacementStore->setAlignment(
970 std::min(ReplacementStore->getAlign(), cast<StoreInst>(I)->getAlign()));
971 ++NumStoresRemoved;
972 } else if (auto *ReplacementAlloca = dyn_cast<AllocaInst>(Repl)) {
973 ReplacementAlloca->setAlignment(std::max(ReplacementAlloca->getAlign(),
974 cast<AllocaInst>(I)->getAlign()));
975 } else if (isa<CallInst>(Repl)) {
976 ++NumCallsRemoved;
977 }
978}
979
980unsigned GVNHoist::rauw(const SmallVecInsn &Candidates, Instruction *Repl,
981 MemoryUseOrDef *NewMemAcc) {
982 unsigned NR = 0;
983 for (Instruction *I : Candidates) {
984 if (I != Repl) {
985 ++NR;
986 updateAlignment(I, Repl);
987 if (NewMemAcc) {
988 // Update the uses of the old MSSA access with NewMemAcc.
989 MemoryAccess *OldMA = MSSA->getMemoryAccess(I);
990 OldMA->replaceAllUsesWith(NewMemAcc);
991 MSSAUpdater->removeMemoryAccess(OldMA);
992 }
993
994 Repl->andIRFlags(I);
995 combineKnownMetadata(Repl, I);
996 I->replaceAllUsesWith(Repl);
997 // Also invalidate the Alias Analysis cache.
998 MD->removeInstruction(I);
999 I->eraseFromParent();
1000 }
1001 }
1002 return NR;
1003}
1004
1005void GVNHoist::raMPHIuw(MemoryUseOrDef *NewMemAcc) {
1007 for (User *U : NewMemAcc->users())
1008 if (MemoryPhi *Phi = dyn_cast<MemoryPhi>(U))
1009 UsePhis.insert(Phi);
1010
1011 for (MemoryPhi *Phi : UsePhis) {
1012 auto In = Phi->incoming_values();
1013 if (llvm::all_of(In, [&](Use &U) { return U == NewMemAcc; })) {
1014 Phi->replaceAllUsesWith(NewMemAcc);
1015 MSSAUpdater->removeMemoryAccess(Phi);
1016 }
1017 }
1018}
1019
1020unsigned GVNHoist::removeAndReplace(const SmallVecInsn &Candidates,
1021 Instruction *Repl, BasicBlock *DestBB,
1022 bool MoveAccess) {
1023 MemoryUseOrDef *NewMemAcc = MSSA->getMemoryAccess(Repl);
1024 if (MoveAccess && NewMemAcc) {
1025 // The definition of this ld/st will not change: ld/st hoisting is
1026 // legal when the ld/st is not moved past its current definition.
1027 MSSAUpdater->moveToPlace(NewMemAcc, DestBB, MemorySSA::BeforeTerminator);
1028 }
1029
1030 // Replace all other instructions with Repl with memory access NewMemAcc.
1031 unsigned NR = rauw(Candidates, Repl, NewMemAcc);
1032
1033 // Remove MemorySSA phi nodes with the same arguments.
1034 if (NewMemAcc)
1035 raMPHIuw(NewMemAcc);
1036 return NR;
1037}
1038
1039bool GVNHoist::makeGepOperandsAvailable(
1040 Instruction *Repl, BasicBlock *HoistPt,
1041 const SmallVecInsn &InstructionsToHoist) const {
1042 // Check whether the GEP of a ld/st can be synthesized at HoistPt.
1043 GetElementPtrInst *Gep = nullptr;
1044 Instruction *Val = nullptr;
1045 if (auto *Ld = dyn_cast<LoadInst>(Repl)) {
1046 Gep = dyn_cast<GetElementPtrInst>(Ld->getPointerOperand());
1047 } else if (auto *St = dyn_cast<StoreInst>(Repl)) {
1048 Gep = dyn_cast<GetElementPtrInst>(St->getPointerOperand());
1049 Val = dyn_cast<Instruction>(St->getValueOperand());
1050 // Check that the stored value is available.
1051 if (Val) {
1052 if (isa<GetElementPtrInst>(Val)) {
1053 // Check whether we can compute the GEP at HoistPt.
1054 if (!allGepOperandsAvailable(Val, HoistPt))
1055 return false;
1056 } else if (!DT->dominates(Val->getParent(), HoistPt))
1057 return false;
1058 }
1059 }
1060
1061 // Check whether we can compute the Gep at HoistPt.
1062 if (!Gep || !allGepOperandsAvailable(Gep, HoistPt))
1063 return false;
1064
1065 makeGepsAvailable(Repl, HoistPt, InstructionsToHoist, Gep);
1066
1067 if (Val && isa<GetElementPtrInst>(Val))
1068 makeGepsAvailable(Repl, HoistPt, InstructionsToHoist, Val);
1069
1070 return true;
1071}
1072
1073std::pair<unsigned, unsigned> GVNHoist::hoist(HoistingPointList &HPL) {
1074 unsigned NI = 0, NL = 0, NS = 0, NC = 0, NR = 0;
1075 for (const HoistingPointInfo &HP : HPL) {
1076 // Find out whether we already have one of the instructions in HoistPt,
1077 // in which case we do not have to move it.
1078 BasicBlock *DestBB = HP.first;
1079 const SmallVecInsn &InstructionsToHoist = HP.second;
1080 Instruction *Repl = nullptr;
1081 for (Instruction *I : InstructionsToHoist)
1082 if (I->getParent() == DestBB)
1083 // If there are two instructions in HoistPt to be hoisted in place:
1084 // update Repl to be the first one, such that we can rename the uses
1085 // of the second based on the first.
1086 if (!Repl || firstInBB(I, Repl))
1087 Repl = I;
1088
1089 // Keep track of whether we moved the instruction so we know whether we
1090 // should move the MemoryAccess.
1091 bool MoveAccess = true;
1092 if (Repl) {
1093 // Repl is already in HoistPt: it remains in place.
1094 assert(allOperandsAvailable(Repl, DestBB) &&
1095 "instruction depends on operands that are not available");
1096 MoveAccess = false;
1097 } else {
1098 // When we do not find Repl in HoistPt, select the first in the list
1099 // and move it to HoistPt.
1100 Repl = InstructionsToHoist.front();
1101
1102 // We can move Repl in HoistPt only when all operands are available.
1103 // The order in which hoistings are done may influence the availability
1104 // of operands.
1105 if (!allOperandsAvailable(Repl, DestBB)) {
1106 // When HoistingGeps there is nothing more we can do to make the
1107 // operands available: just continue.
1108 if (HoistingGeps)
1109 continue;
1110
1111 // When not HoistingGeps we need to copy the GEPs.
1112 if (!makeGepOperandsAvailable(Repl, DestBB, InstructionsToHoist))
1113 continue;
1114 }
1115
1116 // Move the instruction at the end of HoistPt.
1117 Instruction *Last = DestBB->getTerminator();
1118 MD->removeInstruction(Repl);
1119 Repl->moveBefore(Last);
1120
1121 DFSNumber[Repl] = DFSNumber[Last]++;
1122 }
1123
1124 // Drop debug location as per debug info update guide.
1125 Repl->dropLocation();
1126 NR += removeAndReplace(InstructionsToHoist, Repl, DestBB, MoveAccess);
1127
1128 if (isa<LoadInst>(Repl))
1129 ++NL;
1130 else if (isa<StoreInst>(Repl))
1131 ++NS;
1132 else if (isa<CallInst>(Repl))
1133 ++NC;
1134 else // Scalar
1135 ++NI;
1136 }
1137
1138 if (MSSA && VerifyMemorySSA)
1139 MSSA->verifyMemorySSA();
1140
1141 NumHoisted += NL + NS + NC + NI;
1142 NumRemoved += NR;
1143 NumLoadsHoisted += NL;
1144 NumStoresHoisted += NS;
1145 NumCallsHoisted += NC;
1146 return {NI, NL + NC + NS};
1147}
1148
1149std::pair<unsigned, unsigned> GVNHoist::hoistExpressions(Function &F) {
1150 InsnInfo II;
1151 LoadInfo LI;
1152 StoreInfo SI;
1153 CallInfo CI;
1154 for (BasicBlock *BB : depth_first(&F.getEntryBlock())) {
1155 int InstructionNb = 0;
1156 for (Instruction &I1 : *BB) {
1157 // If I1 cannot guarantee progress, subsequent instructions
1158 // in BB cannot be hoisted anyways.
1160 HoistBarrier.insert(BB);
1161 break;
1162 }
1163 // Only hoist the first instructions in BB up to MaxDepthInBB. Hoisting
1164 // deeper may increase the register pressure and compilation time.
1165 if (MaxDepthInBB != -1 && InstructionNb++ >= MaxDepthInBB)
1166 break;
1167
1168 // Do not value number terminator instructions.
1169 if (I1.isTerminator())
1170 break;
1171
1172 if (auto *Load = dyn_cast<LoadInst>(&I1))
1173 LI.insert(Load, VN);
1174 else if (auto *Store = dyn_cast<StoreInst>(&I1))
1175 SI.insert(Store, VN);
1176 else if (auto *Call = dyn_cast<CallInst>(&I1)) {
1177 if (auto *Intr = dyn_cast<IntrinsicInst>(Call)) {
1178 if (isa<DbgInfoIntrinsic>(Intr) ||
1179 Intr->getIntrinsicID() == Intrinsic::assume ||
1180 Intr->getIntrinsicID() == Intrinsic::sideeffect)
1181 continue;
1182 }
1183 if (Call->mayHaveSideEffects())
1184 break;
1185
1186 if (Call->isConvergent())
1187 break;
1188
1189 CI.insert(Call, VN);
1190 } else if (HoistingGeps || !isa<GetElementPtrInst>(&I1))
1191 // Do not hoist scalars past calls that may write to memory because
1192 // that could result in spills later. geps are handled separately.
1193 // TODO: We can relax this for targets like AArch64 as they have more
1194 // registers than X86.
1195 II.insert(&I1, VN);
1196 }
1197 }
1198
1200 computeInsertionPoints(II.getVNTable(), HPL, InsKind::Scalar);
1201 computeInsertionPoints(LI.getVNTable(), HPL, InsKind::Load);
1202 computeInsertionPoints(SI.getVNTable(), HPL, InsKind::Store);
1203 computeInsertionPoints(CI.getScalarVNTable(), HPL, InsKind::Scalar);
1204 computeInsertionPoints(CI.getLoadVNTable(), HPL, InsKind::Load);
1205 computeInsertionPoints(CI.getStoreVNTable(), HPL, InsKind::Store);
1206 return hoist(HPL);
1207}
1208
1209} // end namespace llvm
1210
1216 MemorySSA &MSSA = AM.getResult<MemorySSAAnalysis>(F).getMSSA();
1217 GVNHoist G(&DT, &PDT, &AA, &MD, &MSSA);
1218 if (!G.run(F))
1219 return PreservedAnalyses::all();
1220
1224 return PA;
1225}
SmallVector< AArch64_IMM::ImmInsnModel, 4 > Insn
unsigned Intr
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
This file contains the declarations for the subclasses of Constant, which represent the different fla...
#define LLVM_DEBUG(X)
Definition: Debug.h:101
This file defines the DenseMap class.
This file defines the DenseSet and SmallDenseSet classes.
#define NL
static cl::opt< int > MaxHoistedThreshold("gvn-max-hoisted", cl::Hidden, cl::init(-1), cl::desc("Max number of instructions to hoist " "(default unlimited = -1)"))
static cl::opt< int > MaxChainLength("gvn-hoist-max-chain-length", cl::Hidden, cl::init(10), cl::desc("Maximum length of dependent chains to hoist " "(default = 10, unlimited = -1)"))
static cl::opt< int > MaxDepthInBB("gvn-hoist-max-depth", cl::Hidden, cl::init(100), cl::desc("Hoist instructions from the beginning of the BB up to the " "maximum specified depth (default = 100, unlimited = -1)"))
static cl::opt< int > MaxNumberOfBBSInPath("gvn-hoist-max-bbs", cl::Hidden, cl::init(4), cl::desc("Max number of basic blocks on the path between " "hoisting locations (default = 4, unlimited = -1)"))
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...
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
#define G(x, y, z)
Definition: MD5.cpp:56
This file exposes an interface to building/using memory SSA to walk memory instructions using a use/d...
#define P(N)
This header defines various interfaces for pass management in LLVM.
static void r2(uint32_t &A, uint32_t &B, uint32_t &C, uint32_t &D, uint32_t &E, int I, uint32_t *Buf)
Definition: SHA1.cpp:51
static void r1(uint32_t &A, uint32_t &B, uint32_t &C, uint32_t &D, uint32_t &E, int I, uint32_t *Buf)
Definition: SHA1.cpp:45
@ SI
@ VI
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file contains some templates that are useful if you are working with the STL at all.
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)
Definition: Statistic.h:167
This defines the Use class.
A manager for alias analyses.
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:620
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:774
LLVM Basic Block Representation.
Definition: BasicBlock.h:56
bool hasAddressTaken() const
Returns true if there are any uses of this basic block other than direct branches,...
Definition: BasicBlock.h:495
bool isEHPad() const
Return true if this basic block is an exception handling block.
Definition: BasicBlock.h:512
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...
Definition: BasicBlock.h:127
void insert(CallInst *Call, GVNPass::ValueTable &VN)
Definition: GVNHoist.cpp:224
const VNtoInsns & getLoadVNTable() const
Definition: GVNHoist.cpp:240
const VNtoInsns & getScalarVNTable() const
Definition: GVNHoist.cpp:239
const VNtoInsns & getStoreVNTable() const
Definition: GVNHoist.cpp:241
This class represents a function call, abstracting a target machine's calling convention.
ValueT lookup(const_arg_type_t< KeyT > Val) const
lookup - Return the entry for the specified key, or a default constructed value if no such entry exis...
Definition: DenseMap.h:202
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:155
iterator end()
Definition: DenseMap.h:84
Implements a dense probed hash-table based set.
Definition: DenseSet.h:271
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:279
DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
bool properlyDominates(const DomTreeNodeBase< NodeT > *A, const DomTreeNodeBase< NodeT > *B) const
properlyDominates - Returns true iff A dominates B and A != B.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:166
bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
Definition: Dominators.cpp:122
bool run(Function &F)
Definition: GVNHoist.cpp:522
GVNHoist(DominatorTree *DT, PostDominatorTree *PDT, AliasAnalysis *AA, MemoryDependenceResults *MD, MemorySSA *MSSA)
Definition: GVNHoist.cpp:261
unsigned int rank(const Value *V) const
Definition: GVNHoist.cpp:560
This class holds the mapping between values and value numbers.
Definition: GVN.h:151
uint32_t lookupOrAdd(Value *V)
lookup_or_add - Returns the value number for the specified value, assigning it a new number if it did...
Definition: GVN.cpp:588
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
Definition: Instructions.h:940
const VNtoInsns & getVNTable() const
Definition: GVNHoist.cpp:176
void insert(Instruction *I, GVNPass::ValueTable &VN)
Definition: GVNHoist.cpp:170
Instruction * clone() const
Create a copy of 'this' instruction that is identical in all ways except the following:
unsigned getNumSuccessors() const LLVM_READONLY
Return the number of successors that this instruction has.
void dropLocation()
Drop the instruction's debug location.
Definition: DebugInfo.cpp:919
void insertBefore(Instruction *InsertPos)
Insert an unlinked instruction into a basic block immediately before the specified instruction.
Definition: Instruction.cpp:88
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
Definition: Instruction.h:90
bool mayThrow() const LLVM_READONLY
Return true if this instruction may throw an exception.
void moveBefore(Instruction *MovePos)
Unlink this instruction from its current basic block and insert it into the basic block that MovePos ...
void dropUnknownNonDebugMetadata(ArrayRef< unsigned > KnownIDs)
Drop all unknown metadata except for debug locations.
Definition: Metadata.cpp:1401
const VNtoInsns & getVNTable() const
Definition: GVNHoist.cpp:194
void insert(LoadInst *Load, GVNPass::ValueTable &VN)
Definition: GVNHoist.cpp:185
An instruction for reading from memory.
Definition: Instructions.h:177
Represents a read-write access to memory, whether it is a must-alias, or a may-alias.
Definition: MemorySSA.h:372
An analysis that produces MemoryDependenceResults for a function.
Provides a lazy, caching interface for making common memory aliasing information queries,...
void removeInstruction(Instruction *InstToRemove)
Removes an instruction from the dependence analysis, updating the dependence of instructions that pre...
Represents phi nodes for memory accesses.
Definition: MemorySSA.h:479
An analysis that produces MemorySSA for a function.
Definition: MemorySSA.h:936
static bool defClobbersUseOrDef(MemoryDef *MD, const MemoryUseOrDef *MU, AliasAnalysis &AA)
Definition: MemorySSA.cpp:343
Encapsulates MemorySSA, including all data associated with memory accesses.
Definition: MemorySSA.h:700
const AccessList * getBlockAccesses(const BasicBlock *BB) const
Return the list of MemoryAccess's for a given basic block.
Definition: MemorySSA.h:757
void verifyMemorySSA(VerificationLevel=VerificationLevel::Fast) const
Verify that MemorySSA is self consistent (IE definitions dominate all uses, uses appear in the right ...
Definition: MemorySSA.cpp:1862
MemoryUseOrDef * getMemoryAccess(const Instruction *I) const
Given a memory Mod/Ref'ing instruction, get the MemorySSA access associated with it.
Definition: MemorySSA.h:717
void ensureOptimizedUses()
By default, uses are not optimized during MemorySSA construction.
Definition: MemorySSA.cpp:2142
bool locallyDominates(const MemoryAccess *A, const MemoryAccess *B) const
Given two memory accesses in the same basic block, determine whether MemoryAccess A dominates MemoryA...
Definition: MemorySSA.cpp:2084
bool isLiveOnEntryDef(const MemoryAccess *MA) const
Return true if MA represents the live on entry value.
Definition: MemorySSA.h:737
Class that has the common methods + fields of memory uses/defs.
Definition: MemorySSA.h:252
Represents read-only accesses to memory.
Definition: MemorySSA.h:312
Analysis pass which computes a PostDominatorTree.
PostDominatorTree Class - Concrete subclass of DominatorTree that is used to compute the post-dominat...
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:158
void preserve()
Mark an analysis as preserved.
Definition: PassManager.h:173
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:365
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:450
typename SuperClass::iterator iterator
Definition: SmallVector.h:581
void push_back(const T &Elt)
Definition: SmallVector.h:416
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
void insert(StoreInst *Store, GVNPass::ValueTable &VN)
Definition: GVNHoist.cpp:204
const VNtoInsns & getVNTable() const
Definition: GVNHoist.cpp:213
An instruction for storing to memory.
Definition: Instructions.h:301
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
bool replaceUsesOfWith(Value *From, Value *To)
Replace uses of one Value with another.
Definition: User.cpp:21
Value * getOperand(unsigned i) const
Definition: User.h:169
unsigned getNumOperands() const
Definition: User.h:191
LLVM Value Representation.
Definition: Value.h:74
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:532
iterator_range< user_iterator > users()
Definition: Value.h:421
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:308
std::pair< iterator, bool > insert(const ValueT &V)
Definition: DenseSet.h:206
size_type count(const_arg_type_t< ValueT > V) const
Return 1 if the specified key is in the set, 0 otherwise.
Definition: DenseSet.h:97
An intrusive list with ownership and callbacks specified/controlled by ilist_traits,...
Definition: ilist.h:392
A range adaptor for a pair of iterators.
This provides a very simple, boring adaptor for a begin and end iterator into a range type.
@ C
The default llvm calling convention, compatible with C.
Definition: CallingConv.h:34
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:445
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
void stable_sort(R &&Range)
Definition: STLExtras.h:2063
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1819
auto size(R &&Range, std::enable_if_t< std::is_base_of< std::random_access_iterator_tag, typename std::iterator_traits< decltype(Range.begin())>::iterator_category >::value, void > *=nullptr)
Get the size of a range.
Definition: STLExtras.h:1777
auto successors(const MachineBasicBlock *BB)
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
static void combineKnownMetadata(Instruction *ReplInst, Instruction *I)
Definition: GVNHoist.cpp:244
const Value * getPointerOperand(const Value *V)
A helper function that returns the pointer operand of a load, store or GEP instruction.
std::pair< BasicBlock *, SmallVecInsn > HoistingPointInfo
Definition: GVNHoist.cpp:122
auto reverse(ContainerTy &&C)
Definition: STLExtras.h:511
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1744
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
SmallVectorImpl< CHIArg >::iterator CHIIt
Definition: GVNHoist.cpp:154
idf_iterator< T > idf_end(const T &G)
void combineMetadata(Instruction *K, const Instruction *J, ArrayRef< unsigned > KnownIDs, bool DoesKMove)
Combine the metadata of two instructions so that K can replace J.
Definition: Local.cpp:2644
bool VerifyMemorySSA
Enables verification of MemorySSA.
Definition: MemorySSA.cpp:89
idf_iterator< T > idf_begin(const T &G)
bool isGuaranteedToTransferExecutionToSuccessor(const Instruction *I)
Return true if this function can prove that the instruction I will always transfer execution to one o...
auto find_if(R &&Range, UnaryPredicate P)
Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1846
auto predecessors(const MachineBasicBlock *BB)
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
Definition: STLExtras.h:1976
SmallVector< Instruction *, 4 > SmallVecInsn
Definition: GVNHoist.cpp:117
iterator_range< df_iterator< T > > depth_first(const T &G)
std::pair< unsigned, uintptr_t > VNType
Definition: GVNHoist.cpp:127
@ InvalidVN
Definition: GVNHoist.cpp:162
Definition: BitVector.h:858
#define NC
Definition: regutils.h:42
bool operator!=(const CHIArg &A) const
Definition: GVNHoist.cpp:151
BasicBlock * Dest
Definition: GVNHoist.cpp:145
Instruction * I
Definition: GVNHoist.cpp:148
bool operator==(const CHIArg &A) const
Definition: GVNHoist.cpp:150
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Run the pass over the function.
Definition: GVNHoist.cpp:1211
Utility type to build an inheritance chain that makes it easy to rank overload candidates.
Definition: STLExtras.h:1566