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