lib/Transforms/Scalar/LICM.cpp

   1 //===-- LICM.cpp - Loop Invariant Code Motion Pass ------------------------===//
   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 performs loop invariant code motion, attempting to remove as much
  11 // code from the body of a loop as possible.  It does this by either hoisting
  12 // code into the preheader block, or by sinking code to the exit blocks if it is
  13 // safe.  This pass also promotes must-aliased memory locations in the loop to
  14 // live in registers, thus hoisting and sinking "invariant" loads and stores.
  15 //
  16 // This pass uses alias analysis for two purposes:
  17 //
  18 //  1. Moving loop invariant loads and calls out of loops.  If we can determine
  19 //     that a load or call inside of a loop never aliases anything stored to,
  20 //     we can hoist it or sink it like any other instruction.
  21 //  2. Scalar Promotion of Memory - If there is a store instruction inside of
  22 //     the loop, we try to move the store to happen AFTER the loop instead of
  23 //     inside of the loop.  This can only happen if a few conditions are true:
  24 //       A. The pointer stored through is loop invariant
  25 //       B. There are no stores or loads in the loop which _may_ alias the
  26 //          pointer.  There are no calls in the loop which mod/ref the pointer.
  27 //     If these conditions are true, we can promote the loads and stores in the
  28 //     loop of the pointer to use a temporary alloca'd variable.  We then use
  29 //     the SSAUpdater to construct the appropriate SSA form for the value.
  30 //
  31 //===----------------------------------------------------------------------===//
  32
  33 #include "llvm/Transforms/Scalar.h"
  34 #include "llvm/ADT/Statistic.h"
  35 #include "llvm/Analysis/AliasAnalysis.h"
  36 #include "llvm/Analysis/AliasSetTracker.h"
  37 #include "llvm/Analysis/ConstantFolding.h"
  38 #include "llvm/Analysis/LoopInfo.h"
  39 #include "llvm/Analysis/LoopPass.h"
  40 #include "llvm/Analysis/ScalarEvolution.h"
  41 #include "llvm/Analysis/TargetLibraryInfo.h"
  42 #include "llvm/Analysis/ValueTracking.h"
  43 #include "llvm/IR/CFG.h"
  44 #include "llvm/IR/Constants.h"
  45 #include "llvm/IR/DataLayout.h"
  46 #include "llvm/IR/DerivedTypes.h"
  47 #include "llvm/IR/Dominators.h"
  48 #include "llvm/IR/Instructions.h"
  49 #include "llvm/IR/IntrinsicInst.h"
  50 #include "llvm/IR/LLVMContext.h"
  51 #include "llvm/IR/Metadata.h"
  52 #include "llvm/IR/PredIteratorCache.h"
  53 #include "llvm/Support/CommandLine.h"
  54 #include "llvm/Support/Debug.h"
  55 #include "llvm/Support/raw_ostream.h"
  56 #include "llvm/Transforms/Utils/Local.h"
  57 #include "llvm/Transforms/Utils/LoopUtils.h"
  58 #include "llvm/Transforms/Utils/SSAUpdater.h"
  59 #include <algorithm>
  60 using namespace llvm;
  61
  62 #define DEBUG_TYPE "licm"
  63
  64 STATISTIC(NumSunk      , "Number of instructions sunk out of loop");
  65 STATISTIC(NumHoisted   , "Number of instructions hoisted out of loop");
  66 STATISTIC(NumMovedLoads, "Number of load insts hoisted or sunk");
  67 STATISTIC(NumMovedCalls, "Number of call insts hoisted or sunk");
  68 STATISTIC(NumPromoted  , "Number of memory locations promoted to registers");
  69
  70 static cl::opt<bool>
  71 DisablePromotion("disable-licm-promotion", cl::Hidden,
  72                  cl::desc("Disable memory promotion in LICM pass"));
  73
  74 static bool inSubLoop(BasicBlock *BB, Loop *CurLoop, LoopInfo *LI);
  75 static bool isNotUsedInLoop(const Instruction &I, const Loop *CurLoop);
  76 static bool hoist(Instruction &I, BasicBlock *Preheader);
  77 static bool sink(Instruction &I, const LoopInfo *LI, const DominatorTree *DT,
  78                  const Loop *CurLoop, AliasSetTracker *CurAST );
  79 static bool isGuaranteedToExecute(const Instruction &Inst,
  80                                   const DominatorTree *DT,
  81                                   const Loop *CurLoop,
  82                                   const LICMSafetyInfo *SafetyInfo);
  83 static bool isSafeToExecuteUnconditionally(const Instruction &Inst,
  84                                            const DominatorTree *DT,
  85                                            const TargetLibraryInfo *TLI,
  86                                            const Loop *CurLoop,
  87                                            const LICMSafetyInfo *SafetyInfo);
  88 static bool pointerInvalidatedByLoop(Value *V, uint64_t Size,
  89                                      const AAMDNodes &AAInfo,
  90                                      AliasSetTracker *CurAST);
  91 static Instruction *CloneInstructionInExitBlock(const Instruction &I,
  92                                                 BasicBlock &ExitBlock,
  93                                                 PHINode &PN,
  94                                                 const LoopInfo *LI);
  95 static bool canSinkOrHoistInst(Instruction &I, AliasAnalysis *AA,
  96                                DominatorTree *DT, TargetLibraryInfo *TLI,
  97                                Loop *CurLoop, AliasSetTracker *CurAST,
  98                                LICMSafetyInfo *SafetyInfo);
  99
 100 namespace {
 101   struct LICM : public LoopPass {
 102     static char ID; // Pass identification, replacement for typeid
 103     LICM() : LoopPass(ID) {
 104       initializeLICMPass(*PassRegistry::getPassRegistry());
 105     }
 106
 107     bool runOnLoop(Loop *L, LPPassManager &LPM) override;
 108
 109     /// This transformation requires natural loop information & requires that
 110     /// loop preheaders be inserted into the CFG...
 111     ///
 112     void getAnalysisUsage(AnalysisUsage &AU) const override {
 113       AU.setPreservesCFG();
 114       AU.addRequired<DominatorTreeWrapperPass>();
 115       AU.addRequired<LoopInfoWrapperPass>();
 116       AU.addRequiredID(LoopSimplifyID);
 117       AU.addPreservedID(LoopSimplifyID);
 118       AU.addRequiredID(LCSSAID);
 119       AU.addPreservedID(LCSSAID);
 120       AU.addRequired<AliasAnalysis>();
 121       AU.addPreserved<AliasAnalysis>();
 122       AU.addPreserved<ScalarEvolution>();
 123       AU.addRequired<TargetLibraryInfoWrapperPass>();
 124     }
 125
 126     using llvm::Pass::doFinalization;
 127
 128     bool doFinalization() override {
 129       assert(LoopToAliasSetMap.empty() && "Didn't free loop alias sets");
 130       return false;
 131     }
 132
 133   private:
 134     AliasAnalysis *AA;       // Current AliasAnalysis information
 135     LoopInfo      *LI;       // Current LoopInfo
 136     DominatorTree *DT;       // Dominator Tree for the current Loop.
 137
 138     TargetLibraryInfo *TLI;  // TargetLibraryInfo for constant folding.
 139
 140     // State that is updated as we process loops.
 141     bool Changed;            // Set to true when we change anything.
 142     BasicBlock *Preheader;   // The preheader block of the current loop...
 143     Loop *CurLoop;           // The current loop we are working on...
 144     AliasSetTracker *CurAST; // AliasSet information for the current loop...
 145     DenseMap<Loop*, AliasSetTracker*> LoopToAliasSetMap;
 146
 147     /// cloneBasicBlockAnalysis - Simple Analysis hook. Clone alias set info.
 148     void cloneBasicBlockAnalysis(BasicBlock *From, BasicBlock *To,
 149                                  Loop *L) override;
 150
 151     /// deleteAnalysisValue - Simple Analysis hook. Delete value V from alias
 152     /// set.
 153     void deleteAnalysisValue(Value *V, Loop *L) override;
 154
 155     /// Simple Analysis hook. Delete loop L from alias set map.
 156     void deleteAnalysisLoop(Loop *L) override;
 157   };
 158 }
 159
 160 char LICM::ID = 0;
 161 INITIALIZE_PASS_BEGIN(LICM, "licm", "Loop Invariant Code Motion", false, false)
 162 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
 163 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
 164 INITIALIZE_PASS_DEPENDENCY(LoopSimplify)
 165 INITIALIZE_PASS_DEPENDENCY(LCSSA)
 166 INITIALIZE_PASS_DEPENDENCY(ScalarEvolution)
 167 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
 168 INITIALIZE_AG_DEPENDENCY(AliasAnalysis)
 169 INITIALIZE_PASS_END(LICM, "licm", "Loop Invariant Code Motion", false, false)
 170
 171 Pass *llvm::createLICMPass() { return new LICM(); }
 172
 173 /// Hoist expressions out of the specified loop. Note, alias info for inner
 174 /// loop is not preserved so it is not a good idea to run LICM multiple
 175 /// times on one loop.
 176 ///
 177 bool LICM::runOnLoop(Loop *L, LPPassManager &LPM) {
 178   if (skipOptnoneFunction(L))
 179     return false;
 180
 181   Changed = false;
 182
 183   // Get our Loop and Alias Analysis information...
 184   LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
 185   AA = &getAnalysis<AliasAnalysis>();
 186   DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
 187
 188   TLI = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
 189
 190   assert(L->isLCSSAForm(*DT) && "Loop is not in LCSSA form.");
 191
 192   CurAST = new AliasSetTracker(*AA);
 193   // Collect Alias info from subloops.
 194   for (Loop::iterator LoopItr = L->begin(), LoopItrE = L->end();
 195        LoopItr != LoopItrE; ++LoopItr) {
 196     Loop *InnerL = *LoopItr;
 197     AliasSetTracker *InnerAST = LoopToAliasSetMap[InnerL];
 198     assert(InnerAST && "Where is my AST?");
 199
 200     // What if InnerLoop was modified by other passes ?
 201     CurAST->add(*InnerAST);
 202
 203     // Once we've incorporated the inner loop's AST into ours, we don't need the
 204     // subloop's anymore.
 205     delete InnerAST;
 206     LoopToAliasSetMap.erase(InnerL);
 207   }
 208
 209   CurLoop = L;
 210
 211   // Get the preheader block to move instructions into...
 212   Preheader = L->getLoopPreheader();
 213
 214   // Loop over the body of this loop, looking for calls, invokes, and stores.
 215   // Because subloops have already been incorporated into AST, we skip blocks in
 216   // subloops.
 217   //
 218   for (Loop::block_iterator I = L->block_begin(), E = L->block_end();
 219        I != E; ++I) {
 220     BasicBlock *BB = *I;
 221     if (LI->getLoopFor(BB) == L)        // Ignore blocks in subloops.
 222       CurAST->add(*BB);                 // Incorporate the specified basic block
 223   }
 224
 225   // Compute loop safety information.
 226   LICMSafetyInfo SafetyInfo;
 227   computeLICMSafetyInfo(&SafetyInfo, CurLoop);
 228
 229   // We want to visit all of the instructions in this loop... that are not parts
 230   // of our subloops (they have already had their invariants hoisted out of
 231   // their loop, into this loop, so there is no need to process the BODIES of
 232   // the subloops).
 233   //
 234   // Traverse the body of the loop in depth first order on the dominator tree so
 235   // that we are guaranteed to see definitions before we see uses.  This allows
 236   // us to sink instructions in one pass, without iteration.  After sinking
 237   // instructions, we perform another pass to hoist them out of the loop.
 238   //
 239   if (L->hasDedicatedExits())
 240     Changed |= sinkRegion(DT->getNode(L->getHeader()), AA, LI, DT, TLI, CurLoop,
 241                           CurAST, &SafetyInfo);
 242   if (Preheader)
 243     Changed |= hoistRegion(DT->getNode(L->getHeader()), AA, LI, DT, TLI,
 244                            CurLoop, CurAST, &SafetyInfo);
 245
 246   // Now that all loop invariants have been removed from the loop, promote any
 247   // memory references to scalars that we can.
 248   if (!DisablePromotion && (Preheader || L->hasDedicatedExits())) {
 249     SmallVector<BasicBlock *, 8> ExitBlocks;
 250     SmallVector<Instruction *, 8> InsertPts;
 251     PredIteratorCache PIC;
 252
 253     // Loop over all of the alias sets in the tracker object.
 254     for (AliasSetTracker::iterator I = CurAST->begin(), E = CurAST->end();
 255          I != E; ++I)
 256       Changed |= promoteLoopAccessesToScalars(*I, ExitBlocks, InsertPts,
 257                                               PIC, LI, DT, CurLoop,
 258                                               CurAST, &SafetyInfo);
 259
 260     // Once we have promoted values across the loop body we have to recursively
 261     // reform LCSSA as any nested loop may now have values defined within the
 262     // loop used in the outer loop.
 263     // FIXME: This is really heavy handed. It would be a bit better to use an
 264     // SSAUpdater strategy during promotion that was LCSSA aware and reformed
 265     // it as it went.
 266     if (Changed)
 267       formLCSSARecursively(*L, *DT, LI,
 268                            getAnalysisIfAvailable<ScalarEvolution>());
 269   }
 270
 271   // Check that neither this loop nor its parent have had LCSSA broken. LICM is
 272   // specifically moving instructions across the loop boundary and so it is
 273   // especially in need of sanity checking here.
 274   assert(L->isLCSSAForm(*DT) && "Loop not left in LCSSA form after LICM!");
 275   assert((!L->getParentLoop() || L->getParentLoop()->isLCSSAForm(*DT)) &&
 276          "Parent loop not left in LCSSA form after LICM!");
 277
 278   // Clear out loops state information for the next iteration
 279   CurLoop = nullptr;
 280   Preheader = nullptr;
 281
 282   // If this loop is nested inside of another one, save the alias information
 283   // for when we process the outer loop.
 284   if (L->getParentLoop())
 285     LoopToAliasSetMap[L] = CurAST;
 286   else
 287     delete CurAST;
 288   return Changed;
 289 }
 290
 291 /// Walk the specified region of the CFG (defined by all blocks dominated by
 292 /// the specified block, and that are in the current loop) in reverse depth
 293 /// first order w.r.t the DominatorTree.  This allows us to visit uses before
 294 /// definitions, allowing us to sink a loop body in one pass without iteration.
 295 ///
 296 bool llvm::sinkRegion(DomTreeNode *N, AliasAnalysis *AA, LoopInfo *LI,
 297                       DominatorTree *DT, TargetLibraryInfo *TLI, Loop *CurLoop,
 298                       AliasSetTracker *CurAST, LICMSafetyInfo *SafetyInfo) {
 299
 300   // Verify inputs.
 301   assert(N != nullptr && AA != nullptr && LI != nullptr &&
 302          DT != nullptr && CurLoop != nullptr && CurAST != nullptr &&
 303          SafetyInfo != nullptr && "Unexpected input to sinkRegion");
 304
 305   // Set changed as false.
 306   bool Changed = false;
 307   // Get basic block
 308   BasicBlock *BB = N->getBlock();
 309   // If this subregion is not in the top level loop at all, exit.
 310   if (!CurLoop->contains(BB)) return Changed;
 311
 312   // We are processing blocks in reverse dfo, so process children first.
 313   const std::vector<DomTreeNode*> &Children = N->getChildren();
 314   for (unsigned i = 0, e = Children.size(); i != e; ++i)
 315     Changed |=
 316         sinkRegion(Children[i], AA, LI, DT, TLI, CurLoop, CurAST, SafetyInfo);
 317   // Only need to process the contents of this block if it is not part of a
 318   // subloop (which would already have been processed).
 319   if (inSubLoop(BB,CurLoop,LI)) return Changed;
 320
 321   for (BasicBlock::iterator II = BB->end(); II != BB->begin(); ) {
 322     Instruction &I = *--II;
 323
 324     // If the instruction is dead, we would try to sink it because it isn't used
 325     // in the loop, instead, just delete it.
 326     if (isInstructionTriviallyDead(&I, TLI)) {
 327       DEBUG(dbgs() << "LICM deleting dead inst: " << I << '\n');
 328       ++II;
 329       CurAST->deleteValue(&I);
 330       I.eraseFromParent();
 331       Changed = true;
 332       continue;
 333     }
 334
 335     // Check to see if we can sink this instruction to the exit blocks
 336     // of the loop.  We can do this if the all users of the instruction are
 337     // outside of the loop.  In this case, it doesn't even matter if the
 338     // operands of the instruction are loop invariant.
 339     //
 340     if (isNotUsedInLoop(I, CurLoop) &&
 341         canSinkOrHoistInst(I, AA, DT, TLI, CurLoop, CurAST, SafetyInfo)) {
 342       ++II;
 343       Changed |= sink(I, LI, DT, CurLoop, CurAST);
 344     }
 345   }
 346   return Changed;
 347 }
 348
 349 /// Walk the specified region of the CFG (defined by all blocks dominated by
 350 /// the specified block, and that are in the current loop) in depth first
 351 /// order w.r.t the DominatorTree.  This allows us to visit definitions before
 352 /// uses, allowing us to hoist a loop body in one pass without iteration.
 353 ///
 354 bool llvm::hoistRegion(DomTreeNode *N, AliasAnalysis *AA, LoopInfo *LI,
 355                        DominatorTree *DT, TargetLibraryInfo *TLI, Loop *CurLoop,
 356                        AliasSetTracker *CurAST, LICMSafetyInfo *SafetyInfo) {
 357   // Verify inputs.
 358   assert(N != nullptr && AA != nullptr && LI != nullptr &&
 359          DT != nullptr && CurLoop != nullptr && CurAST != nullptr &&
 360          SafetyInfo != nullptr && "Unexpected input to hoistRegion");
 361   // Set changed as false.
 362   bool Changed = false;
 363   // Get basic block
 364   BasicBlock *BB = N->getBlock();
 365   // If this subregion is not in the top level loop at all, exit.
 366   if (!CurLoop->contains(BB)) return Changed;
 367   // Only need to process the contents of this block if it is not part of a
 368   // subloop (which would already have been processed).
 369   if (!inSubLoop(BB, CurLoop, LI))
 370     for (BasicBlock::iterator II = BB->begin(), E = BB->end(); II != E; ) {
 371       Instruction &I = *II++;
 372       // Try constant folding this instruction.  If all the operands are
 373       // constants, it is technically hoistable, but it would be better to just
 374       // fold it.
 375       if (Constant *C = ConstantFoldInstruction(
 376               &I, I.getModule()->getDataLayout(), TLI)) {
 377         DEBUG(dbgs() << "LICM folding inst: " << I << "  --> " << *C << '\n');
 378         CurAST->copyValue(&I, C);
 379         CurAST->deleteValue(&I);
 380         I.replaceAllUsesWith(C);
 381         I.eraseFromParent();
 382         continue;
 383       }
 384
 385       // Try hoisting the instruction out to the preheader.  We can only do this
 386       // if all of the operands of the instruction are loop invariant and if it
 387       // is safe to hoist the instruction.
 388       //
 389       if (CurLoop->hasLoopInvariantOperands(&I) &&
 390           canSinkOrHoistInst(I, AA, DT, TLI, CurLoop, CurAST, SafetyInfo) &&
 391           isSafeToExecuteUnconditionally(I, DT, TLI, CurLoop, SafetyInfo))
 392         Changed |= hoist(I, CurLoop->getLoopPreheader());
 393     }
 394
 395   const std::vector<DomTreeNode*> &Children = N->getChildren();
 396   for (unsigned i = 0, e = Children.size(); i != e; ++i)
 397     Changed |=
 398         hoistRegion(Children[i], AA, LI, DT, TLI, CurLoop, CurAST, SafetyInfo);
 399   return Changed;
 400 }
 401
 402 /// Computes loop safety information, checks loop body & header
 403 /// for the possiblity of may throw exception.
 404 ///
 405 void llvm::computeLICMSafetyInfo(LICMSafetyInfo * SafetyInfo, Loop * CurLoop) {
 406   assert(CurLoop != nullptr && "CurLoop cant be null");
 407   BasicBlock *Header = CurLoop->getHeader();
 408   // Setting default safety values.
 409   SafetyInfo->MayThrow = false;
 410   SafetyInfo->HeaderMayThrow = false;
 411   // Iterate over header and compute dafety info.
 412   for (BasicBlock::iterator I = Header->begin(), E = Header->end();
 413        (I != E) && !SafetyInfo->HeaderMayThrow; ++I)
 414     SafetyInfo->HeaderMayThrow |= I->mayThrow();
 415
 416   SafetyInfo->MayThrow = SafetyInfo->HeaderMayThrow;
 417   // Iterate over loop instructions and compute safety info.
 418   for (Loop::block_iterator BB = CurLoop->block_begin(),
 419        BBE = CurLoop->block_end(); (BB != BBE) && !SafetyInfo->MayThrow ; ++BB)
 420     for (BasicBlock::iterator I = (*BB)->begin(), E = (*BB)->end();
 421          (I != E) && !SafetyInfo->MayThrow; ++I)
 422       SafetyInfo->MayThrow |= I->mayThrow();
 423 }
 424
 425 /// canSinkOrHoistInst - Return true if the hoister and sinker can handle this
 426 /// instruction.
 427 ///
 428 bool canSinkOrHoistInst(Instruction &I, AliasAnalysis *AA, DominatorTree *DT,
 429                         TargetLibraryInfo *TLI, Loop *CurLoop,
 430                         AliasSetTracker *CurAST, LICMSafetyInfo *SafetyInfo) {
 431   // Loads have extra constraints we have to verify before we can hoist them.
 432   if (LoadInst *LI = dyn_cast<LoadInst>(&I)) {
 433     if (!LI->isUnordered())
 434       return false;        // Don't hoist volatile/atomic loads!
 435
 436     // Loads from constant memory are always safe to move, even if they end up
 437     // in the same alias set as something that ends up being modified.
 438     if (AA->pointsToConstantMemory(LI->getOperand(0)))
 439       return true;
 440     if (LI->getMetadata(LLVMContext::MD_invariant_load))
 441       return true;
 442
 443     // Don't hoist loads which have may-aliased stores in loop.
 444     uint64_t Size = 0;
 445     if (LI->getType()->isSized())
 446       Size = AA->getTypeStoreSize(LI->getType());
 447
 448     AAMDNodes AAInfo;
 449     LI->getAAMetadata(AAInfo);
 450
 451     return !pointerInvalidatedByLoop(LI->getOperand(0), Size, AAInfo, CurAST);
 452   } else if (CallInst *CI = dyn_cast<CallInst>(&I)) {
 453     // Don't sink or hoist dbg info; it's legal, but not useful.
 454     if (isa<DbgInfoIntrinsic>(I))
 455       return false;
 456
 457     // Handle simple cases by querying alias analysis.
 458     AliasAnalysis::ModRefBehavior Behavior = AA->getModRefBehavior(CI);
 459     if (Behavior == AliasAnalysis::DoesNotAccessMemory)
 460       return true;
 461     if (AliasAnalysis::onlyReadsMemory(Behavior)) {
 462       // If this call only reads from memory and there are no writes to memory
 463       // in the loop, we can hoist or sink the call as appropriate.
 464       bool FoundMod = false;
 465       for (AliasSetTracker::iterator I = CurAST->begin(), E = CurAST->end();
 466            I != E; ++I) {
 467         AliasSet &AS = *I;
 468         if (!AS.isForwardingAliasSet() && AS.isMod()) {
 469           FoundMod = true;
 470           break;
 471         }
 472       }
 473       if (!FoundMod) return true;
 474     }
 475
 476     // FIXME: This should use mod/ref information to see if we can hoist or
 477     // sink the call.
 478
 479     return false;
 480   }
 481
 482   // Only these instructions are hoistable/sinkable.
 483   if (!isa<BinaryOperator>(I) && !isa<CastInst>(I) && !isa<SelectInst>(I) &&
 484       !isa<GetElementPtrInst>(I) && !isa<CmpInst>(I) &&
 485       !isa<InsertElementInst>(I) && !isa<ExtractElementInst>(I) &&
 486       !isa<ShuffleVectorInst>(I) && !isa<ExtractValueInst>(I) &&
 487       !isa<InsertValueInst>(I))
 488     return false;
 489
 490   return isSafeToExecuteUnconditionally(I, DT, TLI, CurLoop, SafetyInfo);
 491 }
 492
 493 /// Returns true if a PHINode is a trivially replaceable with an
 494 /// Instruction.
 495 /// This is true when all incoming values are that instruction.
 496 /// This pattern occurs most often with LCSSA PHI nodes.
 497 ///
 498 static bool isTriviallyReplacablePHI(const PHINode &PN, const Instruction &I) {
 499   for (const Value *IncValue : PN.incoming_values())
 500     if (IncValue != &I)
 501       return false;
 502
 503   return true;
 504 }
 505
 506 /// Return true if the only users of this instruction are outside of
 507 /// the loop. If this is true, we can sink the instruction to the exit
 508 /// blocks of the loop.
 509 ///
 510 static bool isNotUsedInLoop(const Instruction &I, const Loop *CurLoop) {
 511   for (const User *U : I.users()) {
 512     const Instruction *UI = cast<Instruction>(U);
 513     if (const PHINode *PN = dyn_cast<PHINode>(UI)) {
 514       // A PHI node where all of the incoming values are this instruction are
 515       // special -- they can just be RAUW'ed with the instruction and thus
 516       // don't require a use in the predecessor. This is a particular important
 517       // special case because it is the pattern found in LCSSA form.
 518       if (isTriviallyReplacablePHI(*PN, I)) {
 519         if (CurLoop->contains(PN))
 520           return false;
 521         else
 522           continue;
 523       }
 524
 525       // Otherwise, PHI node uses occur in predecessor blocks if the incoming
 526       // values. Check for such a use being inside the loop.
 527       for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
 528         if (PN->getIncomingValue(i) == &I)
 529           if (CurLoop->contains(PN->getIncomingBlock(i)))
 530             return false;
 531
 532       continue;
 533     }
 534
 535     if (CurLoop->contains(UI))
 536       return false;
 537   }
 538   return true;
 539 }
 540
 541 static Instruction *CloneInstructionInExitBlock(const Instruction &I,
 542                                                 BasicBlock &ExitBlock,
 543                                                 PHINode &PN,
 544                                                 const LoopInfo *LI) {
 545   Instruction *New = I.clone();
 546   ExitBlock.getInstList().insert(ExitBlock.getFirstInsertionPt(), New);
 547   if (!I.getName().empty()) New->setName(I.getName() + ".le");
 548
 549   // Build LCSSA PHI nodes for any in-loop operands. Note that this is
 550   // particularly cheap because we can rip off the PHI node that we're
 551   // replacing for the number and blocks of the predecessors.
 552   // OPT: If this shows up in a profile, we can instead finish sinking all
 553   // invariant instructions, and then walk their operands to re-establish
 554   // LCSSA. That will eliminate creating PHI nodes just to nuke them when
 555   // sinking bottom-up.
 556   for (User::op_iterator OI = New->op_begin(), OE = New->op_end(); OI != OE;
 557        ++OI)
 558     if (Instruction *OInst = dyn_cast<Instruction>(*OI))
 559       if (Loop *OLoop = LI->getLoopFor(OInst->getParent()))
 560         if (!OLoop->contains(&PN)) {
 561           PHINode *OpPN =
 562               PHINode::Create(OInst->getType(), PN.getNumIncomingValues(),
 563                               OInst->getName() + ".lcssa", ExitBlock.begin());
 564           for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i)
 565             OpPN->addIncoming(OInst, PN.getIncomingBlock(i));
 566           *OI = OpPN;
 567         }
 568   return New;
 569 }
 570
 571 /// When an instruction is found to only be used outside of the loop, this
 572 /// function moves it to the exit blocks and patches up SSA form as needed.
 573 /// This method is guaranteed to remove the original instruction from its
 574 /// position, and may either delete it or move it to outside of the loop.
 575 ///
 576 static bool sink(Instruction &I, const LoopInfo *LI, const DominatorTree *DT,
 577                  const Loop *CurLoop, AliasSetTracker *CurAST ) {
 578   DEBUG(dbgs() << "LICM sinking instruction: " << I << "\n");
 579   bool Changed = false;
 580   if (isa<LoadInst>(I)) ++NumMovedLoads;
 581   else if (isa<CallInst>(I)) ++NumMovedCalls;
 582   ++NumSunk;
 583   Changed = true;
 584
 585 #ifndef NDEBUG
 586   SmallVector<BasicBlock *, 32> ExitBlocks;
 587   CurLoop->getUniqueExitBlocks(ExitBlocks);
 588   SmallPtrSet<BasicBlock *, 32> ExitBlockSet(ExitBlocks.begin(),
 589                                              ExitBlocks.end());
 590 #endif
 591
 592   // Clones of this instruction. Don't create more than one per exit block!
 593   SmallDenseMap<BasicBlock *, Instruction *, 32> SunkCopies;
 594
 595   // If this instruction is only used outside of the loop, then all users are
 596   // PHI nodes in exit blocks due to LCSSA form. Just RAUW them with clones of
 597   // the instruction.
 598   while (!I.use_empty()) {
 599     Instruction *User = I.user_back();
 600     if (!DT->isReachableFromEntry(User->getParent())) {
 601       User->replaceUsesOfWith(&I, UndefValue::get(I.getType()));
 602       continue;
 603     }
 604     // The user must be a PHI node.
 605     PHINode *PN = cast<PHINode>(User);
 606
 607     BasicBlock *ExitBlock = PN->getParent();
 608     assert(ExitBlockSet.count(ExitBlock) &&
 609            "The LCSSA PHI is not in an exit block!");
 610
 611     Instruction *New;
 612     auto It = SunkCopies.find(ExitBlock);
 613     if (It != SunkCopies.end())
 614       New = It->second;
 615     else
 616       New = SunkCopies[ExitBlock] =
 617             CloneInstructionInExitBlock(I, *ExitBlock, *PN, LI);
 618
 619     PN->replaceAllUsesWith(New);
 620     PN->eraseFromParent();
 621   }
 622
 623   CurAST->deleteValue(&I);
 624   I.eraseFromParent();
 625   return Changed;
 626 }
 627
 628 /// When an instruction is found to only use loop invariant operands that
 629 /// is safe to hoist, this instruction is called to do the dirty work.
 630 ///
 631 static bool hoist(Instruction &I, BasicBlock *Preheader) {
 632   DEBUG(dbgs() << "LICM hoisting to " << Preheader->getName() << ": "
 633         << I << "\n");
 634   // Move the new node to the Preheader, before its terminator.
 635   I.moveBefore(Preheader->getTerminator());
 636
 637   if (isa<LoadInst>(I)) ++NumMovedLoads;
 638   else if (isa<CallInst>(I)) ++NumMovedCalls;
 639   ++NumHoisted;
 640   return true;
 641 }
 642
 643 /// Only sink or hoist an instruction if it is not a trapping instruction,
 644 /// or if the instruction is known not to trap when moved to the preheader.
 645 /// or if it is a trapping instruction and is guaranteed to execute.
 646 static bool isSafeToExecuteUnconditionally(const Instruction &Inst,
 647                                            const DominatorTree *DT,
 648                                            const TargetLibraryInfo *TLI,
 649                                            const Loop *CurLoop,
 650                                            const LICMSafetyInfo *SafetyInfo) {
 651   const Instruction *CtxI = CurLoop->getLoopPreheader()->getTerminator();
 652   if (isSafeToSpeculativelyExecute(&Inst, CtxI, DT, TLI))
 653     return true;
 654
 655   return isGuaranteedToExecute(Inst, DT, CurLoop, SafetyInfo);
 656 }
 657
 658 static bool isGuaranteedToExecute(const Instruction &Inst,
 659                                   const DominatorTree *DT,
 660                                   const Loop *CurLoop,
 661                                   const LICMSafetyInfo * SafetyInfo) {
 662
 663   // We have to check to make sure that the instruction dominates all
 664   // of the exit blocks.  If it doesn't, then there is a path out of the loop
 665   // which does not execute this instruction, so we can't hoist it.
 666
 667   // If the instruction is in the header block for the loop (which is very
 668   // common), it is always guaranteed to dominate the exit blocks.  Since this
 669   // is a common case, and can save some work, check it now.
 670   if (Inst.getParent() == CurLoop->getHeader())
 671     // If there's a throw in the header block, we can't guarantee we'll reach
 672     // Inst.
 673     return !SafetyInfo->HeaderMayThrow;
 674
 675   // Somewhere in this loop there is an instruction which may throw and make us
 676   // exit the loop.
 677   if (SafetyInfo->MayThrow)
 678     return false;
 679
 680   // Get the exit blocks for the current loop.
 681   SmallVector<BasicBlock*, 8> ExitBlocks;
 682   CurLoop->getExitBlocks(ExitBlocks);
 683
 684   // Verify that the block dominates each of the exit blocks of the loop.
 685   for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i)
 686     if (!DT->dominates(Inst.getParent(), ExitBlocks[i]))
 687       return false;
 688
 689   // As a degenerate case, if the loop is statically infinite then we haven't
 690   // proven anything since there are no exit blocks.
 691   if (ExitBlocks.empty())
 692     return false;
 693
 694   return true;
 695 }
 696
 697 namespace {
 698   class LoopPromoter : public LoadAndStorePromoter {
 699     Value *SomePtr;  // Designated pointer to store to.
 700     SmallPtrSetImpl<Value*> &PointerMustAliases;
 701     SmallVectorImpl<BasicBlock*> &LoopExitBlocks;
 702     SmallVectorImpl<Instruction*> &LoopInsertPts;
 703     PredIteratorCache &PredCache;
 704     AliasSetTracker &AST;
 705     LoopInfo &LI;
 706     DebugLoc DL;
 707     int Alignment;
 708     AAMDNodes AATags;
 709
 710     Value *maybeInsertLCSSAPHI(Value *V, BasicBlock *BB) const {
 711       if (Instruction *I = dyn_cast<Instruction>(V))
 712         if (Loop *L = LI.getLoopFor(I->getParent()))
 713           if (!L->contains(BB)) {
 714             // We need to create an LCSSA PHI node for the incoming value and
 715             // store that.
 716             PHINode *PN = PHINode::Create(
 717                 I->getType(), PredCache.size(BB),
 718                 I->getName() + ".lcssa", BB->begin());
 719             for (BasicBlock *Pred : PredCache.get(BB))
 720               PN->addIncoming(I, Pred);
 721             return PN;
 722           }
 723       return V;
 724     }
 725
 726   public:
 727     LoopPromoter(Value *SP,
 728                  ArrayRef<const Instruction *> Insts,
 729                  SSAUpdater &S, SmallPtrSetImpl<Value *> &PMA,
 730                  SmallVectorImpl<BasicBlock *> &LEB,
 731                  SmallVectorImpl<Instruction *> &LIP, PredIteratorCache &PIC,
 732                  AliasSetTracker &ast, LoopInfo &li, DebugLoc dl, int alignment,
 733                  const AAMDNodes &AATags)
 734         : LoadAndStorePromoter(Insts, S), SomePtr(SP), PointerMustAliases(PMA),
 735           LoopExitBlocks(LEB), LoopInsertPts(LIP), PredCache(PIC), AST(ast),
 736           LI(li), DL(dl), Alignment(alignment), AATags(AATags) {}
 737
 738     bool isInstInList(Instruction *I,
 739                       const SmallVectorImpl<Instruction*> &) const override {
 740       Value *Ptr;
 741       if (LoadInst *LI = dyn_cast<LoadInst>(I))
 742         Ptr = LI->getOperand(0);
 743       else
 744         Ptr = cast<StoreInst>(I)->getPointerOperand();
 745       return PointerMustAliases.count(Ptr);
 746     }
 747
 748     void doExtraRewritesBeforeFinalDeletion() const override {
 749       // Insert stores after in the loop exit blocks.  Each exit block gets a
 750       // store of the live-out values that feed them.  Since we've already told
 751       // the SSA updater about the defs in the loop and the preheader
 752       // definition, it is all set and we can start using it.
 753       for (unsigned i = 0, e = LoopExitBlocks.size(); i != e; ++i) {
 754         BasicBlock *ExitBlock = LoopExitBlocks[i];
 755         Value *LiveInValue = SSA.GetValueInMiddleOfBlock(ExitBlock);
 756         LiveInValue = maybeInsertLCSSAPHI(LiveInValue, ExitBlock);
 757         Value *Ptr = maybeInsertLCSSAPHI(SomePtr, ExitBlock);
 758         Instruction *InsertPos = LoopInsertPts[i];
 759         StoreInst *NewSI = new StoreInst(LiveInValue, Ptr, InsertPos);
 760         NewSI->setAlignment(Alignment);
 761         NewSI->setDebugLoc(DL);
 762         if (AATags) NewSI->setAAMetadata(AATags);
 763       }
 764     }
 765
 766     void replaceLoadWithValue(LoadInst *LI, Value *V) const override {
 767       // Update alias analysis.
 768       AST.copyValue(LI, V);
 769     }
 770     void instructionDeleted(Instruction *I) const override {
 771       AST.deleteValue(I);
 772     }
 773   };
 774 } // end anon namespace
 775
 776 /// Try to promote memory values to scalars by sinking stores out of the
 777 /// loop and moving loads to before the loop.  We do this by looping over
 778 /// the stores in the loop, looking for stores to Must pointers which are
 779 /// loop invariant.
 780 ///
 781 bool llvm::promoteLoopAccessesToScalars(AliasSet &AS,
 782                                         SmallVectorImpl<BasicBlock*>&ExitBlocks,
 783                                         SmallVectorImpl<Instruction*>&InsertPts,
 784                                         PredIteratorCache &PIC, LoopInfo *LI,
 785                                         DominatorTree *DT, Loop *CurLoop,
 786                                         AliasSetTracker *CurAST,
 787                                         LICMSafetyInfo * SafetyInfo) {
 788   // Verify inputs.
 789   assert(LI != nullptr && DT != nullptr &&
 790          CurLoop != nullptr && CurAST != nullptr &&
 791          SafetyInfo != nullptr &&
 792          "Unexpected Input to promoteLoopAccessesToScalars");
 793   // Initially set Changed status to false.
 794   bool Changed = false;
 795   // We can promote this alias set if it has a store, if it is a "Must" alias
 796   // set, if the pointer is loop invariant, and if we are not eliminating any
 797   // volatile loads or stores.
 798   if (AS.isForwardingAliasSet() || !AS.isMod() || !AS.isMustAlias() ||
 799       AS.isVolatile() || !CurLoop->isLoopInvariant(AS.begin()->getValue()))
 800     return Changed;
 801
 802   assert(!AS.empty() &&
 803          "Must alias set should have at least one pointer element in it!");
 804
 805   Value *SomePtr = AS.begin()->getValue();
 806   BasicBlock * Preheader = CurLoop->getLoopPreheader();
 807
 808   // It isn't safe to promote a load/store from the loop if the load/store is
 809   // conditional.  For example, turning:
 810   //
 811   //    for () { if (c) *P += 1; }
 812   //
 813   // into:
 814   //
 815   //    tmp = *P;  for () { if (c) tmp +=1; } *P = tmp;
 816   //
 817   // is not safe, because *P may only be valid to access if 'c' is true.
 818   //
 819   // It is safe to promote P if all uses are direct load/stores and if at
 820   // least one is guaranteed to be executed.
 821   bool GuaranteedToExecute = false;
 822
 823   SmallVector<Instruction*, 64> LoopUses;
 824   SmallPtrSet<Value*, 4> PointerMustAliases;
 825
 826   // We start with an alignment of one and try to find instructions that allow
 827   // us to prove better alignment.
 828   unsigned Alignment = 1;
 829   AAMDNodes AATags;
 830   bool HasDedicatedExits = CurLoop->hasDedicatedExits();
 831
 832   // Check that all of the pointers in the alias set have the same type.  We
 833   // cannot (yet) promote a memory location that is loaded and stored in
 834   // different sizes.  While we are at it, collect alignment and AA info.
 835   for (AliasSet::iterator ASI = AS.begin(), E = AS.end(); ASI != E; ++ASI) {
 836     Value *ASIV = ASI->getValue();
 837     PointerMustAliases.insert(ASIV);
 838
 839     // Check that all of the pointers in the alias set have the same type.  We
 840     // cannot (yet) promote a memory location that is loaded and stored in
 841     // different sizes.
 842     if (SomePtr->getType() != ASIV->getType())
 843       return Changed;
 844
 845     for (User *U : ASIV->users()) {
 846       // Ignore instructions that are outside the loop.
 847       Instruction *UI = dyn_cast<Instruction>(U);
 848       if (!UI || !CurLoop->contains(UI))
 849         continue;
 850
 851       // If there is an non-load/store instruction in the loop, we can't promote
 852       // it.
 853       if (const LoadInst *load = dyn_cast<LoadInst>(UI)) {
 854         assert(!load->isVolatile() && "AST broken");
 855         if (!load->isSimple())
 856           return Changed;
 857       } else if (const StoreInst *store = dyn_cast<StoreInst>(UI)) {
 858         // Stores *of* the pointer are not interesting, only stores *to* the
 859         // pointer.
 860         if (UI->getOperand(1) != ASIV)
 861           continue;
 862         assert(!store->isVolatile() && "AST broken");
 863         if (!store->isSimple())
 864           return Changed;
 865         // Don't sink stores from loops without dedicated block exits. Exits
 866         // containing indirect branches are not transformed by loop simplify,
 867         // make sure we catch that. An additional load may be generated in the
 868         // preheader for SSA updater, so also avoid sinking when no preheader
 869         // is available.
 870         if (!HasDedicatedExits || !Preheader)
 871           return Changed;
 872
 873         // Note that we only check GuaranteedToExecute inside the store case
 874         // so that we do not introduce stores where they did not exist before
 875         // (which would break the LLVM concurrency model).
 876
 877         // If the alignment of this instruction allows us to specify a more
 878         // restrictive (and performant) alignment and if we are sure this
 879         // instruction will be executed, update the alignment.
 880         // Larger is better, with the exception of 0 being the best alignment.
 881         unsigned InstAlignment = store->getAlignment();
 882         if ((InstAlignment > Alignment || InstAlignment == 0) && Alignment != 0)
 883           if (isGuaranteedToExecute(*UI, DT, CurLoop, SafetyInfo)) {
 884             GuaranteedToExecute = true;
 885             Alignment = InstAlignment;
 886           }
 887
 888         if (!GuaranteedToExecute)
 889           GuaranteedToExecute = isGuaranteedToExecute(*UI, DT,
 890                                                       CurLoop, SafetyInfo);
 891
 892       } else
 893         return Changed; // Not a load or store.
 894
 895       // Merge the AA tags.
 896       if (LoopUses.empty()) {
 897         // On the first load/store, just take its AA tags.
 898         UI->getAAMetadata(AATags);
 899       } else if (AATags) {
 900         UI->getAAMetadata(AATags, /* Merge = */ true);
 901       }
 902
 903       LoopUses.push_back(UI);
 904     }
 905   }
 906
 907   // If there isn't a guaranteed-to-execute instruction, we can't promote.
 908   if (!GuaranteedToExecute)
 909     return Changed;
 910
 911   // Otherwise, this is safe to promote, lets do it!
 912   DEBUG(dbgs() << "LICM: Promoting value stored to in loop: " <<*SomePtr<<'\n');
 913   Changed = true;
 914   ++NumPromoted;
 915
 916   // Grab a debug location for the inserted loads/stores; given that the
 917   // inserted loads/stores have little relation to the original loads/stores,
 918   // this code just arbitrarily picks a location from one, since any debug
 919   // location is better than none.
 920   DebugLoc DL = LoopUses[0]->getDebugLoc();
 921
 922   // Figure out the loop exits and their insertion points, if this is the
 923   // first promotion.
 924   if (ExitBlocks.empty()) {
 925     CurLoop->getUniqueExitBlocks(ExitBlocks);
 926     InsertPts.resize(ExitBlocks.size());
 927     for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i)
 928       InsertPts[i] = ExitBlocks[i]->getFirstInsertionPt();
 929   }
 930
 931   // We use the SSAUpdater interface to insert phi nodes as required.
 932   SmallVector<PHINode*, 16> NewPHIs;
 933   SSAUpdater SSA(&NewPHIs);
 934   LoopPromoter Promoter(SomePtr, LoopUses, SSA,
 935                         PointerMustAliases, ExitBlocks,
 936                         InsertPts, PIC, *CurAST, *LI, DL, Alignment, AATags);
 937
 938   // Set up the preheader to have a definition of the value.  It is the live-out
 939   // value from the preheader that uses in the loop will use.
 940   LoadInst *PreheaderLoad =
 941     new LoadInst(SomePtr, SomePtr->getName()+".promoted",
 942                  Preheader->getTerminator());
 943   PreheaderLoad->setAlignment(Alignment);
 944   PreheaderLoad->setDebugLoc(DL);
 945   if (AATags) PreheaderLoad->setAAMetadata(AATags);
 946   SSA.AddAvailableValue(Preheader, PreheaderLoad);
 947
 948   // Rewrite all the loads in the loop and remember all the definitions from
 949   // stores in the loop.
 950   Promoter.run(LoopUses);
 951
 952   // If the SSAUpdater didn't use the load in the preheader, just zap it now.
 953   if (PreheaderLoad->use_empty())
 954     PreheaderLoad->eraseFromParent();
 955
 956   return Changed;
 957 }
 958
 959 /// Simple Analysis hook. Clone alias set info.
 960 ///
 961 void LICM::cloneBasicBlockAnalysis(BasicBlock *From, BasicBlock *To, Loop *L) {
 962   AliasSetTracker *AST = LoopToAliasSetMap.lookup(L);
 963   if (!AST)
 964     return;
 965
 966   AST->copyValue(From, To);
 967 }
 968
 969 /// Simple Analysis hook. Delete value V from alias set
 970 ///
 971 void LICM::deleteAnalysisValue(Value *V, Loop *L) {
 972   AliasSetTracker *AST = LoopToAliasSetMap.lookup(L);
 973   if (!AST)
 974     return;
 975
 976   AST->deleteValue(V);
 977 }
 978
 979 /// Simple Analysis hook. Delete value L from alias set map.
 980 ///
 981 void LICM::deleteAnalysisLoop(Loop *L) {
 982   AliasSetTracker *AST = LoopToAliasSetMap.lookup(L);
 983   if (!AST)
 984     return;
 985
 986   delete AST;
 987   LoopToAliasSetMap.erase(L);
 988 }
 989
 990
 991 /// Return true if the body of this loop may store into the memory
 992 /// location pointed to by V.
 993 ///
 994 static bool pointerInvalidatedByLoop(Value *V, uint64_t Size,
 995                                      const AAMDNodes &AAInfo,
 996                                      AliasSetTracker *CurAST) {
 997   // Check to see if any of the basic blocks in CurLoop invalidate *V.
 998   return CurAST->getAliasSetForPointer(V, Size, AAInfo).isMod();
 999 }
1000
1001 /// Little predicate that returns true if the specified basic block is in
1002 /// a subloop of the current one, not the current one itself.
1003 ///
1004 static bool inSubLoop(BasicBlock *BB, Loop *CurLoop, LoopInfo *LI) {
1005   assert(CurLoop->contains(BB) && "Only valid if BB is IN the loop");
1006   return LI->getLoopFor(BB) != CurLoop;
1007 }
1008