contrib/llvm/lib/Transforms/Scalar/GVNHoist.cpp

   1 //===- GVNHoist.cpp - Hoist scalar and load expressions -------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This pass hoists expressions from branches to a common dominator. It uses
  11 // GVN (global value numbering) to discover expressions computing the same
  12 // values. The primary goals of code-hoisting are:
  13 // 1. To reduce the code size.
  14 // 2. In some cases reduce critical path (by exposing more ILP).
  15 //
  16 // Hoisting may affect the performance in some cases. To mitigate that, hoisting
  17 // is disabled in the following cases.
  18 // 1. Scalars across calls.
  19 // 2. geps when corresponding load/store cannot be hoisted.
  20 //===----------------------------------------------------------------------===//
  21
  22 #include "llvm/Transforms/Scalar/GVN.h"
  23 #include "llvm/ADT/DenseMap.h"
  24 #include "llvm/ADT/SmallPtrSet.h"
  25 #include "llvm/ADT/Statistic.h"
  26 #include "llvm/Analysis/ValueTracking.h"
  27 #include "llvm/Transforms/Scalar.h"
  28 #include "llvm/Transforms/Utils/Local.h"
  29 #include "llvm/Transforms/Utils/MemorySSA.h"
  30
  31 using namespace llvm;
  32
  33 #define DEBUG_TYPE "gvn-hoist"
  34
  35 STATISTIC(NumHoisted, "Number of instructions hoisted");
  36 STATISTIC(NumRemoved, "Number of instructions removed");
  37 STATISTIC(NumLoadsHoisted, "Number of loads hoisted");
  38 STATISTIC(NumLoadsRemoved, "Number of loads removed");
  39 STATISTIC(NumStoresHoisted, "Number of stores hoisted");
  40 STATISTIC(NumStoresRemoved, "Number of stores removed");
  41 STATISTIC(NumCallsHoisted, "Number of calls hoisted");
  42 STATISTIC(NumCallsRemoved, "Number of calls removed");
  43
  44 static cl::opt<int>
  45     MaxHoistedThreshold("gvn-max-hoisted", cl::Hidden, cl::init(-1),
  46                         cl::desc("Max number of instructions to hoist "
  47                                  "(default unlimited = -1)"));
  48 static cl::opt<int> MaxNumberOfBBSInPath(
  49     "gvn-hoist-max-bbs", cl::Hidden, cl::init(4),
  50     cl::desc("Max number of basic blocks on the path between "
  51              "hoisting locations (default = 4, unlimited = -1)"));
  52
  53 static cl::opt<int> MaxDepthInBB(
  54     "gvn-hoist-max-depth", cl::Hidden, cl::init(100),
  55     cl::desc("Hoist instructions from the beginning of the BB up to the "
  56              "maximum specified depth (default = 100, unlimited = -1)"));
  57
  58 static cl::opt<int>
  59     MaxChainLength("gvn-hoist-max-chain-length", cl::Hidden, cl::init(10),
  60                    cl::desc("Maximum length of dependent chains to hoist "
  61                             "(default = 10, unlimited = -1)"));
  62
  63 namespace {
  64
  65 // Provides a sorting function based on the execution order of two instructions.
  66 struct SortByDFSIn {
  67 private:
  68   DenseMap<const Value *, unsigned> &DFSNumber;
  69
  70 public:
  71   SortByDFSIn(DenseMap<const Value *, unsigned> &D) : DFSNumber(D) {}
  72
  73   // Returns true when A executes before B.
  74   bool operator()(const Instruction *A, const Instruction *B) const {
  75     // FIXME: libc++ has a std::sort() algorithm that will call the compare
  76     // function on the same element.  Once PR20837 is fixed and some more years
  77     // pass by and all the buildbots have moved to a corrected std::sort(),
  78     // enable the following assert:
  79     //
  80     // assert(A != B);
  81
  82     const BasicBlock *BA = A->getParent();
  83     const BasicBlock *BB = B->getParent();
  84     unsigned ADFS, BDFS;
  85     if (BA == BB) {
  86       ADFS = DFSNumber.lookup(A);
  87       BDFS = DFSNumber.lookup(B);
  88     } else {
  89       ADFS = DFSNumber.lookup(BA);
  90       BDFS = DFSNumber.lookup(BB);
  91     }
  92     assert(ADFS && BDFS);
  93     return ADFS < BDFS;
  94   }
  95 };
  96
  97 // A map from a pair of VNs to all the instructions with those VNs.
  98 typedef DenseMap<std::pair<unsigned, unsigned>, SmallVector<Instruction *, 4>>
  99     VNtoInsns;
 100 // An invalid value number Used when inserting a single value number into
 101 // VNtoInsns.
 102 enum : unsigned { InvalidVN = ~2U };
 103
 104 // Records all scalar instructions candidate for code hoisting.
 105 class InsnInfo {
 106   VNtoInsns VNtoScalars;
 107
 108 public:
 109   // Inserts I and its value number in VNtoScalars.
 110   void insert(Instruction *I, GVN::ValueTable &VN) {
 111     // Scalar instruction.
 112     unsigned V = VN.lookupOrAdd(I);
 113     VNtoScalars[{V, InvalidVN}].push_back(I);
 114   }
 115
 116   const VNtoInsns &getVNTable() const { return VNtoScalars; }
 117 };
 118
 119 // Records all load instructions candidate for code hoisting.
 120 class LoadInfo {
 121   VNtoInsns VNtoLoads;
 122
 123 public:
 124   // Insert Load and the value number of its memory address in VNtoLoads.
 125   void insert(LoadInst *Load, GVN::ValueTable &VN) {
 126     if (Load->isSimple()) {
 127       unsigned V = VN.lookupOrAdd(Load->getPointerOperand());
 128       VNtoLoads[{V, InvalidVN}].push_back(Load);
 129     }
 130   }
 131
 132   const VNtoInsns &getVNTable() const { return VNtoLoads; }
 133 };
 134
 135 // Records all store instructions candidate for code hoisting.
 136 class StoreInfo {
 137   VNtoInsns VNtoStores;
 138
 139 public:
 140   // Insert the Store and a hash number of the store address and the stored
 141   // value in VNtoStores.
 142   void insert(StoreInst *Store, GVN::ValueTable &VN) {
 143     if (!Store->isSimple())
 144       return;
 145     // Hash the store address and the stored value.
 146     Value *Ptr = Store->getPointerOperand();
 147     Value *Val = Store->getValueOperand();
 148     VNtoStores[{VN.lookupOrAdd(Ptr), VN.lookupOrAdd(Val)}].push_back(Store);
 149   }
 150
 151   const VNtoInsns &getVNTable() const { return VNtoStores; }
 152 };
 153
 154 // Records all call instructions candidate for code hoisting.
 155 class CallInfo {
 156   VNtoInsns VNtoCallsScalars;
 157   VNtoInsns VNtoCallsLoads;
 158   VNtoInsns VNtoCallsStores;
 159
 160 public:
 161   // Insert Call and its value numbering in one of the VNtoCalls* containers.
 162   void insert(CallInst *Call, GVN::ValueTable &VN) {
 163     // A call that doesNotAccessMemory is handled as a Scalar,
 164     // onlyReadsMemory will be handled as a Load instruction,
 165     // all other calls will be handled as stores.
 166     unsigned V = VN.lookupOrAdd(Call);
 167     auto Entry = std::make_pair(V, InvalidVN);
 168
 169     if (Call->doesNotAccessMemory())
 170       VNtoCallsScalars[Entry].push_back(Call);
 171     else if (Call->onlyReadsMemory())
 172       VNtoCallsLoads[Entry].push_back(Call);
 173     else
 174       VNtoCallsStores[Entry].push_back(Call);
 175   }
 176
 177   const VNtoInsns &getScalarVNTable() const { return VNtoCallsScalars; }
 178
 179   const VNtoInsns &getLoadVNTable() const { return VNtoCallsLoads; }
 180
 181   const VNtoInsns &getStoreVNTable() const { return VNtoCallsStores; }
 182 };
 183
 184 typedef DenseMap<const BasicBlock *, bool> BBSideEffectsSet;
 185 typedef SmallVector<Instruction *, 4> SmallVecInsn;
 186 typedef SmallVectorImpl<Instruction *> SmallVecImplInsn;
 187
 188 static void combineKnownMetadata(Instruction *ReplInst, Instruction *I) {
 189   static const unsigned KnownIDs[] = {
 190       LLVMContext::MD_tbaa,           LLVMContext::MD_alias_scope,
 191       LLVMContext::MD_noalias,        LLVMContext::MD_range,
 192       LLVMContext::MD_fpmath,         LLVMContext::MD_invariant_load,
 193       LLVMContext::MD_invariant_group};
 194   combineMetadata(ReplInst, I, KnownIDs);
 195 }
 196
 197 // This pass hoists common computations across branches sharing common
 198 // dominator. The primary goal is to reduce the code size, and in some
 199 // cases reduce critical path (by exposing more ILP).
 200 class GVNHoist {
 201 public:
 202   GVNHoist(DominatorTree *DT, AliasAnalysis *AA, MemoryDependenceResults *MD,
 203            MemorySSA *MSSA, bool OptForMinSize)
 204       : DT(DT), AA(AA), MD(MD), MSSA(MSSA), OptForMinSize(OptForMinSize),
 205         HoistingGeps(OptForMinSize), HoistedCtr(0) {
 206       // Hoist as far as possible when optimizing for code-size.
 207       if (OptForMinSize)
 208         MaxNumberOfBBSInPath = -1;
 209   }
 210
 211   bool run(Function &F) {
 212     VN.setDomTree(DT);
 213     VN.setAliasAnalysis(AA);
 214     VN.setMemDep(MD);
 215     bool Res = false;
 216     // Perform DFS Numbering of instructions.
 217     unsigned BBI = 0;
 218     for (const BasicBlock *BB : depth_first(&F.getEntryBlock())) {
 219       DFSNumber[BB] = ++BBI;
 220       unsigned I = 0;
 221       for (auto &Inst : *BB)
 222         DFSNumber[&Inst] = ++I;
 223     }
 224
 225     int ChainLength = 0;
 226
 227     // FIXME: use lazy evaluation of VN to avoid the fix-point computation.
 228     while (1) {
 229       if (MaxChainLength != -1 && ++ChainLength >= MaxChainLength)
 230         return Res;
 231
 232       auto HoistStat = hoistExpressions(F);
 233       if (HoistStat.first + HoistStat.second == 0)
 234         return Res;
 235
 236       if (HoistStat.second > 0)
 237         // To address a limitation of the current GVN, we need to rerun the
 238         // hoisting after we hoisted loads or stores in order to be able to
 239         // hoist all scalars dependent on the hoisted ld/st.
 240         VN.clear();
 241
 242       Res = true;
 243     }
 244
 245     return Res;
 246   }
 247
 248 private:
 249   GVN::ValueTable VN;
 250   DominatorTree *DT;
 251   AliasAnalysis *AA;
 252   MemoryDependenceResults *MD;
 253   MemorySSA *MSSA;
 254   const bool OptForMinSize;
 255   const bool HoistingGeps;
 256   DenseMap<const Value *, unsigned> DFSNumber;
 257   BBSideEffectsSet BBSideEffects;
 258   int HoistedCtr;
 259
 260   enum InsKind { Unknown, Scalar, Load, Store };
 261
 262   // Return true when there are exception handling in BB.
 263   bool hasEH(const BasicBlock *BB) {
 264     auto It = BBSideEffects.find(BB);
 265     if (It != BBSideEffects.end())
 266       return It->second;
 267
 268     if (BB->isEHPad() || BB->hasAddressTaken()) {
 269       BBSideEffects[BB] = true;
 270       return true;
 271     }
 272
 273     if (BB->getTerminator()->mayThrow()) {
 274       BBSideEffects[BB] = true;
 275       return true;
 276     }
 277
 278     BBSideEffects[BB] = false;
 279     return false;
 280   }
 281
 282   // Return true when a successor of BB dominates A.
 283   bool successorDominate(const BasicBlock *BB, const BasicBlock *A) {
 284     for (const BasicBlock *Succ : BB->getTerminator()->successors())
 285       if (DT->dominates(Succ, A))
 286         return true;
 287
 288     return false;
 289   }
 290
 291   // Return true when all paths from HoistBB to the end of the function pass
 292   // through one of the blocks in WL.
 293   bool hoistingFromAllPaths(const BasicBlock *HoistBB,
 294                             SmallPtrSetImpl<const BasicBlock *> &WL) {
 295
 296     // Copy WL as the loop will remove elements from it.
 297     SmallPtrSet<const BasicBlock *, 2> WorkList(WL.begin(), WL.end());
 298
 299     for (auto It = df_begin(HoistBB), E = df_end(HoistBB); It != E;) {
 300       // There exists a path from HoistBB to the exit of the function if we are
 301       // still iterating in DF traversal and we removed all instructions from
 302       // the work list.
 303       if (WorkList.empty())
 304         return false;
 305
 306       const BasicBlock *BB = *It;
 307       if (WorkList.erase(BB)) {
 308         // Stop DFS traversal when BB is in the work list.
 309         It.skipChildren();
 310         continue;
 311       }
 312
 313       // Check for end of function, calls that do not return, etc.
 314       if (!isGuaranteedToTransferExecutionToSuccessor(BB->getTerminator()))
 315         return false;
 316
 317       // When reaching the back-edge of a loop, there may be a path through the
 318       // loop that does not pass through B or C before exiting the loop.
 319       if (successorDominate(BB, HoistBB))
 320         return false;
 321
 322       // Increment DFS traversal when not skipping children.
 323       ++It;
 324     }
 325
 326     return true;
 327   }
 328
 329   /* Return true when I1 appears before I2 in the instructions of BB.  */
 330   bool firstInBB(const Instruction *I1, const Instruction *I2) {
 331     assert(I1->getParent() == I2->getParent());
 332     unsigned I1DFS = DFSNumber.lookup(I1);
 333     unsigned I2DFS = DFSNumber.lookup(I2);
 334     assert(I1DFS && I2DFS);
 335     return I1DFS < I2DFS;
 336   }
 337
 338   // Return true when there are memory uses of Def in BB.
 339   bool hasMemoryUse(const Instruction *NewPt, MemoryDef *Def,
 340                     const BasicBlock *BB) {
 341     const MemorySSA::AccessList *Acc = MSSA->getBlockAccesses(BB);
 342     if (!Acc)
 343       return false;
 344
 345     Instruction *OldPt = Def->getMemoryInst();
 346     const BasicBlock *OldBB = OldPt->getParent();
 347     const BasicBlock *NewBB = NewPt->getParent();
 348     bool ReachedNewPt = false;
 349
 350     for (const MemoryAccess &MA : *Acc)
 351       if (const MemoryUse *MU = dyn_cast<MemoryUse>(&MA)) {
 352         Instruction *Insn = MU->getMemoryInst();
 353
 354         // Do not check whether MU aliases Def when MU occurs after OldPt.
 355         if (BB == OldBB && firstInBB(OldPt, Insn))
 356           break;
 357
 358         // Do not check whether MU aliases Def when MU occurs before NewPt.
 359         if (BB == NewBB) {
 360           if (!ReachedNewPt) {
 361             if (firstInBB(Insn, NewPt))
 362               continue;
 363             ReachedNewPt = true;
 364           }
 365         }
 366         if (defClobbersUseOrDef(Def, MU, *AA))
 367           return true;
 368       }
 369
 370     return false;
 371   }
 372
 373   // Return true when there are exception handling or loads of memory Def
 374   // between Def and NewPt.  This function is only called for stores: Def is
 375   // the MemoryDef of the store to be hoisted.
 376
 377   // Decrement by 1 NBBsOnAllPaths for each block between HoistPt and BB, and
 378   // return true when the counter NBBsOnAllPaths reaces 0, except when it is
 379   // initialized to -1 which is unlimited.
 380   bool hasEHOrLoadsOnPath(const Instruction *NewPt, MemoryDef *Def,
 381                           int &NBBsOnAllPaths) {
 382     const BasicBlock *NewBB = NewPt->getParent();
 383     const BasicBlock *OldBB = Def->getBlock();
 384     assert(DT->dominates(NewBB, OldBB) && "invalid path");
 385     assert(DT->dominates(Def->getDefiningAccess()->getBlock(), NewBB) &&
 386            "def does not dominate new hoisting point");
 387
 388     // Walk all basic blocks reachable in depth-first iteration on the inverse
 389     // CFG from OldBB to NewBB. These blocks are all the blocks that may be
 390     // executed between the execution of NewBB and OldBB. Hoisting an expression
 391     // from OldBB into NewBB has to be safe on all execution paths.
 392     for (auto I = idf_begin(OldBB), E = idf_end(OldBB); I != E;) {
 393       if (*I == NewBB) {
 394         // Stop traversal when reaching HoistPt.
 395         I.skipChildren();
 396         continue;
 397       }
 398
 399       // Stop walk once the limit is reached.
 400       if (NBBsOnAllPaths == 0)
 401         return true;
 402
 403       // Impossible to hoist with exceptions on the path.
 404       if (hasEH(*I))
 405         return true;
 406
 407       // Check that we do not move a store past loads.
 408       if (hasMemoryUse(NewPt, Def, *I))
 409         return true;
 410
 411       // -1 is unlimited number of blocks on all paths.
 412       if (NBBsOnAllPaths != -1)
 413         --NBBsOnAllPaths;
 414
 415       ++I;
 416     }
 417
 418     return false;
 419   }
 420
 421   // Return true when there are exception handling between HoistPt and BB.
 422   // Decrement by 1 NBBsOnAllPaths for each block between HoistPt and BB, and
 423   // return true when the counter NBBsOnAllPaths reaches 0, except when it is
 424   // initialized to -1 which is unlimited.
 425   bool hasEHOnPath(const BasicBlock *HoistPt, const BasicBlock *BB,
 426                    int &NBBsOnAllPaths) {
 427     assert(DT->dominates(HoistPt, BB) && "Invalid path");
 428
 429     // Walk all basic blocks reachable in depth-first iteration on
 430     // the inverse CFG from BBInsn to NewHoistPt. These blocks are all the
 431     // blocks that may be executed between the execution of NewHoistPt and
 432     // BBInsn. Hoisting an expression from BBInsn into NewHoistPt has to be safe
 433     // on all execution paths.
 434     for (auto I = idf_begin(BB), E = idf_end(BB); I != E;) {
 435       if (*I == HoistPt) {
 436         // Stop traversal when reaching NewHoistPt.
 437         I.skipChildren();
 438         continue;
 439       }
 440
 441       // Stop walk once the limit is reached.
 442       if (NBBsOnAllPaths == 0)
 443         return true;
 444
 445       // Impossible to hoist with exceptions on the path.
 446       if (hasEH(*I))
 447         return true;
 448
 449       // -1 is unlimited number of blocks on all paths.
 450       if (NBBsOnAllPaths != -1)
 451         --NBBsOnAllPaths;
 452
 453       ++I;
 454     }
 455
 456     return false;
 457   }
 458
 459   // Return true when it is safe to hoist a memory load or store U from OldPt
 460   // to NewPt.
 461   bool safeToHoistLdSt(const Instruction *NewPt, const Instruction *OldPt,
 462                        MemoryUseOrDef *U, InsKind K, int &NBBsOnAllPaths) {
 463
 464     // In place hoisting is safe.
 465     if (NewPt == OldPt)
 466       return true;
 467
 468     const BasicBlock *NewBB = NewPt->getParent();
 469     const BasicBlock *OldBB = OldPt->getParent();
 470     const BasicBlock *UBB = U->getBlock();
 471
 472     // Check for dependences on the Memory SSA.
 473     MemoryAccess *D = U->getDefiningAccess();
 474     BasicBlock *DBB = D->getBlock();
 475     if (DT->properlyDominates(NewBB, DBB))
 476       // Cannot move the load or store to NewBB above its definition in DBB.
 477       return false;
 478
 479     if (NewBB == DBB && !MSSA->isLiveOnEntryDef(D))
 480       if (auto *UD = dyn_cast<MemoryUseOrDef>(D))
 481         if (firstInBB(NewPt, UD->getMemoryInst()))
 482           // Cannot move the load or store to NewPt above its definition in D.
 483           return false;
 484
 485     // Check for unsafe hoistings due to side effects.
 486     if (K == InsKind::Store) {
 487       if (hasEHOrLoadsOnPath(NewPt, dyn_cast<MemoryDef>(U), NBBsOnAllPaths))
 488         return false;
 489     } else if (hasEHOnPath(NewBB, OldBB, NBBsOnAllPaths))
 490       return false;
 491
 492     if (UBB == NewBB) {
 493       if (DT->properlyDominates(DBB, NewBB))
 494         return true;
 495       assert(UBB == DBB);
 496       assert(MSSA->locallyDominates(D, U));
 497     }
 498
 499     // No side effects: it is safe to hoist.
 500     return true;
 501   }
 502
 503   // Return true when it is safe to hoist scalar instructions from all blocks in
 504   // WL to HoistBB.
 505   bool safeToHoistScalar(const BasicBlock *HoistBB,
 506                          SmallPtrSetImpl<const BasicBlock *> &WL,
 507                          int &NBBsOnAllPaths) {
 508     // Enable scalar hoisting at -Oz as it is safe to hoist scalars to a place
 509     // where they are partially needed.
 510     if (OptForMinSize)
 511       return true;
 512
 513     // Check that the hoisted expression is needed on all paths.
 514     if (!hoistingFromAllPaths(HoistBB, WL))
 515       return false;
 516
 517     for (const BasicBlock *BB : WL)
 518       if (hasEHOnPath(HoistBB, BB, NBBsOnAllPaths))
 519         return false;
 520
 521     return true;
 522   }
 523
 524   // Each element of a hoisting list contains the basic block where to hoist and
 525   // a list of instructions to be hoisted.
 526   typedef std::pair<BasicBlock *, SmallVecInsn> HoistingPointInfo;
 527   typedef SmallVector<HoistingPointInfo, 4> HoistingPointList;
 528
 529   // Partition InstructionsToHoist into a set of candidates which can share a
 530   // common hoisting point. The partitions are collected in HPL. IsScalar is
 531   // true when the instructions in InstructionsToHoist are scalars. IsLoad is
 532   // true when the InstructionsToHoist are loads, false when they are stores.
 533   void partitionCandidates(SmallVecImplInsn &InstructionsToHoist,
 534                            HoistingPointList &HPL, InsKind K) {
 535     // No need to sort for two instructions.
 536     if (InstructionsToHoist.size() > 2) {
 537       SortByDFSIn Pred(DFSNumber);
 538       std::sort(InstructionsToHoist.begin(), InstructionsToHoist.end(), Pred);
 539     }
 540
 541     int NumBBsOnAllPaths = MaxNumberOfBBSInPath;
 542
 543     SmallVecImplInsn::iterator II = InstructionsToHoist.begin();
 544     SmallVecImplInsn::iterator Start = II;
 545     Instruction *HoistPt = *II;
 546     BasicBlock *HoistBB = HoistPt->getParent();
 547     MemoryUseOrDef *UD;
 548     if (K != InsKind::Scalar)
 549       UD = MSSA->getMemoryAccess(HoistPt);
 550
 551     for (++II; II != InstructionsToHoist.end(); ++II) {
 552       Instruction *Insn = *II;
 553       BasicBlock *BB = Insn->getParent();
 554       BasicBlock *NewHoistBB;
 555       Instruction *NewHoistPt;
 556
 557       if (BB == HoistBB) { // Both are in the same Basic Block.
 558         NewHoistBB = HoistBB;
 559         NewHoistPt = firstInBB(Insn, HoistPt) ? Insn : HoistPt;
 560       } else {
 561         // If the hoisting point contains one of the instructions,
 562         // then hoist there, otherwise hoist before the terminator.
 563         NewHoistBB = DT->findNearestCommonDominator(HoistBB, BB);
 564         if (NewHoistBB == BB)
 565           NewHoistPt = Insn;
 566         else if (NewHoistBB == HoistBB)
 567           NewHoistPt = HoistPt;
 568         else
 569           NewHoistPt = NewHoistBB->getTerminator();
 570       }
 571
 572       SmallPtrSet<const BasicBlock *, 2> WL;
 573       WL.insert(HoistBB);
 574       WL.insert(BB);
 575
 576       if (K == InsKind::Scalar) {
 577         if (safeToHoistScalar(NewHoistBB, WL, NumBBsOnAllPaths)) {
 578           // Extend HoistPt to NewHoistPt.
 579           HoistPt = NewHoistPt;
 580           HoistBB = NewHoistBB;
 581           continue;
 582         }
 583       } else {
 584         // When NewBB already contains an instruction to be hoisted, the
 585         // expression is needed on all paths.
 586         // Check that the hoisted expression is needed on all paths: it is
 587         // unsafe to hoist loads to a place where there may be a path not
 588         // loading from the same address: for instance there may be a branch on
 589         // which the address of the load may not be initialized.
 590         if ((HoistBB == NewHoistBB || BB == NewHoistBB ||
 591              hoistingFromAllPaths(NewHoistBB, WL)) &&
 592             // Also check that it is safe to move the load or store from HoistPt
 593             // to NewHoistPt, and from Insn to NewHoistPt.
 594             safeToHoistLdSt(NewHoistPt, HoistPt, UD, K, NumBBsOnAllPaths) &&
 595             safeToHoistLdSt(NewHoistPt, Insn, MSSA->getMemoryAccess(Insn),
 596                             K, NumBBsOnAllPaths)) {
 597           // Extend HoistPt to NewHoistPt.
 598           HoistPt = NewHoistPt;
 599           HoistBB = NewHoistBB;
 600           continue;
 601         }
 602       }
 603
 604       // At this point it is not safe to extend the current hoisting to
 605       // NewHoistPt: save the hoisting list so far.
 606       if (std::distance(Start, II) > 1)
 607         HPL.push_back({HoistBB, SmallVecInsn(Start, II)});
 608
 609       // Start over from BB.
 610       Start = II;
 611       if (K != InsKind::Scalar)
 612         UD = MSSA->getMemoryAccess(*Start);
 613       HoistPt = Insn;
 614       HoistBB = BB;
 615       NumBBsOnAllPaths = MaxNumberOfBBSInPath;
 616     }
 617
 618     // Save the last partition.
 619     if (std::distance(Start, II) > 1)
 620       HPL.push_back({HoistBB, SmallVecInsn(Start, II)});
 621   }
 622
 623   // Initialize HPL from Map.
 624   void computeInsertionPoints(const VNtoInsns &Map, HoistingPointList &HPL,
 625                               InsKind K) {
 626     for (const auto &Entry : Map) {
 627       if (MaxHoistedThreshold != -1 && ++HoistedCtr > MaxHoistedThreshold)
 628         return;
 629
 630       const SmallVecInsn &V = Entry.second;
 631       if (V.size() < 2)
 632         continue;
 633
 634       // Compute the insertion point and the list of expressions to be hoisted.
 635       SmallVecInsn InstructionsToHoist;
 636       for (auto I : V)
 637         if (!hasEH(I->getParent()))
 638           InstructionsToHoist.push_back(I);
 639
 640       if (!InstructionsToHoist.empty())
 641         partitionCandidates(InstructionsToHoist, HPL, K);
 642     }
 643   }
 644
 645   // Return true when all operands of Instr are available at insertion point
 646   // HoistPt. When limiting the number of hoisted expressions, one could hoist
 647   // a load without hoisting its access function. So before hoisting any
 648   // expression, make sure that all its operands are available at insert point.
 649   bool allOperandsAvailable(const Instruction *I,
 650                             const BasicBlock *HoistPt) const {
 651     for (const Use &Op : I->operands())
 652       if (const auto *Inst = dyn_cast<Instruction>(&Op))
 653         if (!DT->dominates(Inst->getParent(), HoistPt))
 654           return false;
 655
 656     return true;
 657   }
 658
 659   // Same as allOperandsAvailable with recursive check for GEP operands.
 660   bool allGepOperandsAvailable(const Instruction *I,
 661                                const BasicBlock *HoistPt) const {
 662     for (const Use &Op : I->operands())
 663       if (const auto *Inst = dyn_cast<Instruction>(&Op))
 664         if (!DT->dominates(Inst->getParent(), HoistPt)) {
 665           if (const GetElementPtrInst *GepOp =
 666                   dyn_cast<GetElementPtrInst>(Inst)) {
 667             if (!allGepOperandsAvailable(GepOp, HoistPt))
 668               return false;
 669             // Gep is available if all operands of GepOp are available.
 670           } else {
 671             // Gep is not available if it has operands other than GEPs that are
 672             // defined in blocks not dominating HoistPt.
 673             return false;
 674           }
 675         }
 676     return true;
 677   }
 678
 679   // Make all operands of the GEP available.
 680   void makeGepsAvailable(Instruction *Repl, BasicBlock *HoistPt,
 681                          const SmallVecInsn &InstructionsToHoist,
 682                          Instruction *Gep) const {
 683     assert(allGepOperandsAvailable(Gep, HoistPt) &&
 684            "GEP operands not available");
 685
 686     Instruction *ClonedGep = Gep->clone();
 687     for (unsigned i = 0, e = Gep->getNumOperands(); i != e; ++i)
 688       if (Instruction *Op = dyn_cast<Instruction>(Gep->getOperand(i))) {
 689
 690         // Check whether the operand is already available.
 691         if (DT->dominates(Op->getParent(), HoistPt))
 692           continue;
 693
 694         // As a GEP can refer to other GEPs, recursively make all the operands
 695         // of this GEP available at HoistPt.
 696         if (GetElementPtrInst *GepOp = dyn_cast<GetElementPtrInst>(Op))
 697           makeGepsAvailable(ClonedGep, HoistPt, InstructionsToHoist, GepOp);
 698       }
 699
 700     // Copy Gep and replace its uses in Repl with ClonedGep.
 701     ClonedGep->insertBefore(HoistPt->getTerminator());
 702
 703     // Conservatively discard any optimization hints, they may differ on the
 704     // other paths.
 705     ClonedGep->dropUnknownNonDebugMetadata();
 706
 707     // If we have optimization hints which agree with each other along different
 708     // paths, preserve them.
 709     for (const Instruction *OtherInst : InstructionsToHoist) {
 710       const GetElementPtrInst *OtherGep;
 711       if (auto *OtherLd = dyn_cast<LoadInst>(OtherInst))
 712         OtherGep = cast<GetElementPtrInst>(OtherLd->getPointerOperand());
 713       else
 714         OtherGep = cast<GetElementPtrInst>(
 715             cast<StoreInst>(OtherInst)->getPointerOperand());
 716       ClonedGep->andIRFlags(OtherGep);
 717     }
 718
 719     // Replace uses of Gep with ClonedGep in Repl.
 720     Repl->replaceUsesOfWith(Gep, ClonedGep);
 721   }
 722
 723   // In the case Repl is a load or a store, we make all their GEPs
 724   // available: GEPs are not hoisted by default to avoid the address
 725   // computations to be hoisted without the associated load or store.
 726   bool makeGepOperandsAvailable(Instruction *Repl, BasicBlock *HoistPt,
 727                                 const SmallVecInsn &InstructionsToHoist) const {
 728     // Check whether the GEP of a ld/st can be synthesized at HoistPt.
 729     GetElementPtrInst *Gep = nullptr;
 730     Instruction *Val = nullptr;
 731     if (auto *Ld = dyn_cast<LoadInst>(Repl)) {
 732       Gep = dyn_cast<GetElementPtrInst>(Ld->getPointerOperand());
 733     } else if (auto *St = dyn_cast<StoreInst>(Repl)) {
 734       Gep = dyn_cast<GetElementPtrInst>(St->getPointerOperand());
 735       Val = dyn_cast<Instruction>(St->getValueOperand());
 736       // Check that the stored value is available.
 737       if (Val) {
 738         if (isa<GetElementPtrInst>(Val)) {
 739           // Check whether we can compute the GEP at HoistPt.
 740           if (!allGepOperandsAvailable(Val, HoistPt))
 741             return false;
 742         } else if (!DT->dominates(Val->getParent(), HoistPt))
 743           return false;
 744       }
 745     }
 746
 747     // Check whether we can compute the Gep at HoistPt.
 748     if (!Gep || !allGepOperandsAvailable(Gep, HoistPt))
 749       return false;
 750
 751     makeGepsAvailable(Repl, HoistPt, InstructionsToHoist, Gep);
 752
 753     if (Val && isa<GetElementPtrInst>(Val))
 754       makeGepsAvailable(Repl, HoistPt, InstructionsToHoist, Val);
 755
 756     return true;
 757   }
 758
 759   std::pair<unsigned, unsigned> hoist(HoistingPointList &HPL) {
 760     unsigned NI = 0, NL = 0, NS = 0, NC = 0, NR = 0;
 761     for (const HoistingPointInfo &HP : HPL) {
 762       // Find out whether we already have one of the instructions in HoistPt,
 763       // in which case we do not have to move it.
 764       BasicBlock *HoistPt = HP.first;
 765       const SmallVecInsn &InstructionsToHoist = HP.second;
 766       Instruction *Repl = nullptr;
 767       for (Instruction *I : InstructionsToHoist)
 768         if (I->getParent() == HoistPt)
 769           // If there are two instructions in HoistPt to be hoisted in place:
 770           // update Repl to be the first one, such that we can rename the uses
 771           // of the second based on the first.
 772           if (!Repl || firstInBB(I, Repl))
 773             Repl = I;
 774
 775       // Keep track of whether we moved the instruction so we know whether we
 776       // should move the MemoryAccess.
 777       bool MoveAccess = true;
 778       if (Repl) {
 779         // Repl is already in HoistPt: it remains in place.
 780         assert(allOperandsAvailable(Repl, HoistPt) &&
 781                "instruction depends on operands that are not available");
 782         MoveAccess = false;
 783       } else {
 784         // When we do not find Repl in HoistPt, select the first in the list
 785         // and move it to HoistPt.
 786         Repl = InstructionsToHoist.front();
 787
 788         // We can move Repl in HoistPt only when all operands are available.
 789         // The order in which hoistings are done may influence the availability
 790         // of operands.
 791         if (!allOperandsAvailable(Repl, HoistPt)) {
 792
 793           // When HoistingGeps there is nothing more we can do to make the
 794           // operands available: just continue.
 795           if (HoistingGeps)
 796             continue;
 797
 798           // When not HoistingGeps we need to copy the GEPs.
 799           if (!makeGepOperandsAvailable(Repl, HoistPt, InstructionsToHoist))
 800             continue;
 801         }
 802
 803         // Move the instruction at the end of HoistPt.
 804         Instruction *Last = HoistPt->getTerminator();
 805         MD->removeInstruction(Repl);
 806         Repl->moveBefore(Last);
 807
 808         DFSNumber[Repl] = DFSNumber[Last]++;
 809       }
 810
 811       MemoryAccess *NewMemAcc = MSSA->getMemoryAccess(Repl);
 812
 813       if (MoveAccess) {
 814         if (MemoryUseOrDef *OldMemAcc =
 815                 dyn_cast_or_null<MemoryUseOrDef>(NewMemAcc)) {
 816           // The definition of this ld/st will not change: ld/st hoisting is
 817           // legal when the ld/st is not moved past its current definition.
 818           MemoryAccess *Def = OldMemAcc->getDefiningAccess();
 819           NewMemAcc =
 820               MSSA->createMemoryAccessInBB(Repl, Def, HoistPt, MemorySSA::End);
 821           OldMemAcc->replaceAllUsesWith(NewMemAcc);
 822           MSSA->removeMemoryAccess(OldMemAcc);
 823         }
 824       }
 825
 826       if (isa<LoadInst>(Repl))
 827         ++NL;
 828       else if (isa<StoreInst>(Repl))
 829         ++NS;
 830       else if (isa<CallInst>(Repl))
 831         ++NC;
 832       else // Scalar
 833         ++NI;
 834
 835       // Remove and rename all other instructions.
 836       for (Instruction *I : InstructionsToHoist)
 837         if (I != Repl) {
 838           ++NR;
 839           if (auto *ReplacementLoad = dyn_cast<LoadInst>(Repl)) {
 840             ReplacementLoad->setAlignment(
 841                 std::min(ReplacementLoad->getAlignment(),
 842                          cast<LoadInst>(I)->getAlignment()));
 843             ++NumLoadsRemoved;
 844           } else if (auto *ReplacementStore = dyn_cast<StoreInst>(Repl)) {
 845             ReplacementStore->setAlignment(
 846                 std::min(ReplacementStore->getAlignment(),
 847                          cast<StoreInst>(I)->getAlignment()));
 848             ++NumStoresRemoved;
 849           } else if (auto *ReplacementAlloca = dyn_cast<AllocaInst>(Repl)) {
 850             ReplacementAlloca->setAlignment(
 851                 std::max(ReplacementAlloca->getAlignment(),
 852                          cast<AllocaInst>(I)->getAlignment()));
 853           } else if (isa<CallInst>(Repl)) {
 854             ++NumCallsRemoved;
 855           }
 856
 857           if (NewMemAcc) {
 858             // Update the uses of the old MSSA access with NewMemAcc.
 859             MemoryAccess *OldMA = MSSA->getMemoryAccess(I);
 860             OldMA->replaceAllUsesWith(NewMemAcc);
 861             MSSA->removeMemoryAccess(OldMA);
 862           }
 863
 864           Repl->andIRFlags(I);
 865           combineKnownMetadata(Repl, I);
 866           I->replaceAllUsesWith(Repl);
 867           // Also invalidate the Alias Analysis cache.
 868           MD->removeInstruction(I);
 869           I->eraseFromParent();
 870         }
 871
 872       // Remove MemorySSA phi nodes with the same arguments.
 873       if (NewMemAcc) {
 874         SmallPtrSet<MemoryPhi *, 4> UsePhis;
 875         for (User *U : NewMemAcc->users())
 876           if (MemoryPhi *Phi = dyn_cast<MemoryPhi>(U))
 877             UsePhis.insert(Phi);
 878
 879         for (auto *Phi : UsePhis) {
 880           auto In = Phi->incoming_values();
 881           if (all_of(In, [&](Use &U) { return U == NewMemAcc; })) {
 882             Phi->replaceAllUsesWith(NewMemAcc);
 883             MSSA->removeMemoryAccess(Phi);
 884           }
 885         }
 886       }
 887     }
 888
 889     NumHoisted += NL + NS + NC + NI;
 890     NumRemoved += NR;
 891     NumLoadsHoisted += NL;
 892     NumStoresHoisted += NS;
 893     NumCallsHoisted += NC;
 894     return {NI, NL + NC + NS};
 895   }
 896
 897   // Hoist all expressions. Returns Number of scalars hoisted
 898   // and number of non-scalars hoisted.
 899   std::pair<unsigned, unsigned> hoistExpressions(Function &F) {
 900     InsnInfo II;
 901     LoadInfo LI;
 902     StoreInfo SI;
 903     CallInfo CI;
 904     for (BasicBlock *BB : depth_first(&F.getEntryBlock())) {
 905       int InstructionNb = 0;
 906       for (Instruction &I1 : *BB) {
 907         // Only hoist the first instructions in BB up to MaxDepthInBB. Hoisting
 908         // deeper may increase the register pressure and compilation time.
 909         if (MaxDepthInBB != -1 && InstructionNb++ >= MaxDepthInBB)
 910           break;
 911
 912         // Do not value number terminator instructions.
 913         if (isa<TerminatorInst>(&I1))
 914           break;
 915
 916         if (auto *Load = dyn_cast<LoadInst>(&I1))
 917           LI.insert(Load, VN);
 918         else if (auto *Store = dyn_cast<StoreInst>(&I1))
 919           SI.insert(Store, VN);
 920         else if (auto *Call = dyn_cast<CallInst>(&I1)) {
 921           if (auto *Intr = dyn_cast<IntrinsicInst>(Call)) {
 922             if (isa<DbgInfoIntrinsic>(Intr) ||
 923                 Intr->getIntrinsicID() == Intrinsic::assume)
 924               continue;
 925           }
 926           if (Call->mayHaveSideEffects()) {
 927             if (!OptForMinSize)
 928               break;
 929             // We may continue hoisting across calls which write to memory.
 930             if (Call->mayThrow())
 931               break;
 932           }
 933
 934           if (Call->isConvergent())
 935             break;
 936
 937           CI.insert(Call, VN);
 938         } else if (HoistingGeps || !isa<GetElementPtrInst>(&I1))
 939           // Do not hoist scalars past calls that may write to memory because
 940           // that could result in spills later. geps are handled separately.
 941           // TODO: We can relax this for targets like AArch64 as they have more
 942           // registers than X86.
 943           II.insert(&I1, VN);
 944       }
 945     }
 946
 947     HoistingPointList HPL;
 948     computeInsertionPoints(II.getVNTable(), HPL, InsKind::Scalar);
 949     computeInsertionPoints(LI.getVNTable(), HPL, InsKind::Load);
 950     computeInsertionPoints(SI.getVNTable(), HPL, InsKind::Store);
 951     computeInsertionPoints(CI.getScalarVNTable(), HPL, InsKind::Scalar);
 952     computeInsertionPoints(CI.getLoadVNTable(), HPL, InsKind::Load);
 953     computeInsertionPoints(CI.getStoreVNTable(), HPL, InsKind::Store);
 954     return hoist(HPL);
 955   }
 956 };
 957
 958 class GVNHoistLegacyPass : public FunctionPass {
 959 public:
 960   static char ID;
 961
 962   GVNHoistLegacyPass() : FunctionPass(ID) {
 963     initializeGVNHoistLegacyPassPass(*PassRegistry::getPassRegistry());
 964   }
 965
 966   bool runOnFunction(Function &F) override {
 967     if (skipFunction(F))
 968       return false;
 969     auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
 970     auto &AA = getAnalysis<AAResultsWrapperPass>().getAAResults();
 971     auto &MD = getAnalysis<MemoryDependenceWrapperPass>().getMemDep();
 972     auto &MSSA = getAnalysis<MemorySSAWrapperPass>().getMSSA();
 973
 974     GVNHoist G(&DT, &AA, &MD, &MSSA, F.optForMinSize());
 975     return G.run(F);
 976   }
 977
 978   void getAnalysisUsage(AnalysisUsage &AU) const override {
 979     AU.addRequired<DominatorTreeWrapperPass>();
 980     AU.addRequired<AAResultsWrapperPass>();
 981     AU.addRequired<MemoryDependenceWrapperPass>();
 982     AU.addRequired<MemorySSAWrapperPass>();
 983     AU.addPreserved<DominatorTreeWrapperPass>();
 984     AU.addPreserved<MemorySSAWrapperPass>();
 985   }
 986 };
 987 } // namespace
 988
 989 PreservedAnalyses GVNHoistPass::run(Function &F, FunctionAnalysisManager &AM) {
 990   DominatorTree &DT = AM.getResult<DominatorTreeAnalysis>(F);
 991   AliasAnalysis &AA = AM.getResult<AAManager>(F);
 992   MemoryDependenceResults &MD = AM.getResult<MemoryDependenceAnalysis>(F);
 993   MemorySSA &MSSA = AM.getResult<MemorySSAAnalysis>(F).getMSSA();
 994   GVNHoist G(&DT, &AA, &MD, &MSSA, F.optForMinSize());
 995   if (!G.run(F))
 996     return PreservedAnalyses::all();
 997
 998   PreservedAnalyses PA;
 999   PA.preserve<DominatorTreeAnalysis>();
1000   PA.preserve<MemorySSAAnalysis>();
1001   return PA;
1002 }
1003
1004 char GVNHoistLegacyPass::ID = 0;
1005 INITIALIZE_PASS_BEGIN(GVNHoistLegacyPass, "gvn-hoist",
1006                       "Early GVN Hoisting of Expressions", false, false)
1007 INITIALIZE_PASS_DEPENDENCY(MemoryDependenceWrapperPass)
1008 INITIALIZE_PASS_DEPENDENCY(MemorySSAWrapperPass)
1009 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
1010 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
1011 INITIALIZE_PASS_END(GVNHoistLegacyPass, "gvn-hoist",
1012                     "Early GVN Hoisting of Expressions", false, false)
1013
1014 FunctionPass *llvm::createGVNHoistPass() { return new GVNHoistLegacyPass(); }