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