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