contrib/llvm-project/llvm/lib/Transforms/Utils/LCSSA.cpp

   1 //===-- LCSSA.cpp - Convert loops into loop-closed SSA form ---------------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // This pass transforms loops by placing phi nodes at the end of the loops for
  10 // all values that are live across the loop boundary.  For example, it turns
  11 // the left into the right code:
  12 //
  13 // for (...)                for (...)
  14 //   if (c)                   if (c)
  15 //     X1 = ...                 X1 = ...
  16 //   else                     else
  17 //     X2 = ...                 X2 = ...
  18 //   X3 = phi(X1, X2)         X3 = phi(X1, X2)
  19 // ... = X3 + 4             X4 = phi(X3)
  20 //                          ... = X4 + 4
  21 //
  22 // This is still valid LLVM; the extra phi nodes are purely redundant, and will
  23 // be trivially eliminated by InstCombine.  The major benefit of this
  24 // transformation is that it makes many other loop optimizations, such as
  25 // LoopUnswitching, simpler.
  26 //
  27 //===----------------------------------------------------------------------===//
  28
  29 #include "llvm/Transforms/Utils/LCSSA.h"
  30 #include "llvm/ADT/STLExtras.h"
  31 #include "llvm/ADT/Statistic.h"
  32 #include "llvm/Analysis/AliasAnalysis.h"
  33 #include "llvm/Analysis/BasicAliasAnalysis.h"
  34 #include "llvm/Analysis/BranchProbabilityInfo.h"
  35 #include "llvm/Analysis/GlobalsModRef.h"
  36 #include "llvm/Analysis/LoopPass.h"
  37 #include "llvm/Analysis/MemorySSA.h"
  38 #include "llvm/Analysis/ScalarEvolution.h"
  39 #include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
  40 #include "llvm/IR/Constants.h"
  41 #include "llvm/IR/Dominators.h"
  42 #include "llvm/IR/Function.h"
  43 #include "llvm/IR/Instructions.h"
  44 #include "llvm/IR/IntrinsicInst.h"
  45 #include "llvm/IR/PredIteratorCache.h"
  46 #include "llvm/InitializePasses.h"
  47 #include "llvm/Pass.h"
  48 #include "llvm/Support/CommandLine.h"
  49 #include "llvm/Transforms/Utils.h"
  50 #include "llvm/Transforms/Utils/Local.h"
  51 #include "llvm/Transforms/Utils/LoopUtils.h"
  52 #include "llvm/Transforms/Utils/SSAUpdater.h"
  53 using namespace llvm;
  54
  55 #define DEBUG_TYPE "lcssa"
  56
  57 STATISTIC(NumLCSSA, "Number of live out of a loop variables");
  58
  59 #ifdef EXPENSIVE_CHECKS
  60 static bool VerifyLoopLCSSA = true;
  61 #else
  62 static bool VerifyLoopLCSSA = false;
  63 #endif
  64 static cl::opt<bool, true>
  65     VerifyLoopLCSSAFlag("verify-loop-lcssa", cl::location(VerifyLoopLCSSA),
  66                         cl::Hidden,
  67                         cl::desc("Verify loop lcssa form (time consuming)"));
  68
  69 /// Return true if the specified block is in the list.
  70 static bool isExitBlock(BasicBlock *BB,
  71                         const SmallVectorImpl<BasicBlock *> &ExitBlocks) {
  72   return is_contained(ExitBlocks, BB);
  73 }
  74
  75 /// For every instruction from the worklist, check to see if it has any uses
  76 /// that are outside the current loop.  If so, insert LCSSA PHI nodes and
  77 /// rewrite the uses.
  78 bool llvm::formLCSSAForInstructions(SmallVectorImpl<Instruction *> &Worklist,
  79                                     DominatorTree &DT, LoopInfo &LI,
  80                                     ScalarEvolution *SE) {
  81   SmallVector<Use *, 16> UsesToRewrite;
  82   SmallSetVector<PHINode *, 16> PHIsToRemove;
  83   PredIteratorCache PredCache;
  84   bool Changed = false;
  85
  86   // Cache the Loop ExitBlocks across this loop.  We expect to get a lot of
  87   // instructions within the same loops, computing the exit blocks is
  88   // expensive, and we're not mutating the loop structure.
  89   SmallDenseMap<Loop*, SmallVector<BasicBlock *,1>> LoopExitBlocks;
  90
  91   while (!Worklist.empty()) {
  92     UsesToRewrite.clear();
  93
  94     Instruction *I = Worklist.pop_back_val();
  95     assert(!I->getType()->isTokenTy() && "Tokens shouldn't be in the worklist");
  96     BasicBlock *InstBB = I->getParent();
  97     Loop *L = LI.getLoopFor(InstBB);
  98     assert(L && "Instruction belongs to a BB that's not part of a loop");
  99     if (!LoopExitBlocks.count(L))
 100       L->getExitBlocks(LoopExitBlocks[L]);
 101     assert(LoopExitBlocks.count(L));
 102     const SmallVectorImpl<BasicBlock *> &ExitBlocks = LoopExitBlocks[L];
 103
 104     if (ExitBlocks.empty())
 105       continue;
 106
 107     for (Use &U : I->uses()) {
 108       Instruction *User = cast<Instruction>(U.getUser());
 109       BasicBlock *UserBB = User->getParent();
 110       if (auto *PN = dyn_cast<PHINode>(User))
 111         UserBB = PN->getIncomingBlock(U);
 112
 113       if (InstBB != UserBB && !L->contains(UserBB))
 114         UsesToRewrite.push_back(&U);
 115     }
 116
 117     // If there are no uses outside the loop, exit with no change.
 118     if (UsesToRewrite.empty())
 119       continue;
 120
 121     ++NumLCSSA; // We are applying the transformation
 122
 123     // Invoke instructions are special in that their result value is not
 124     // available along their unwind edge. The code below tests to see whether
 125     // DomBB dominates the value, so adjust DomBB to the normal destination
 126     // block, which is effectively where the value is first usable.
 127     BasicBlock *DomBB = InstBB;
 128     if (auto *Inv = dyn_cast<InvokeInst>(I))
 129       DomBB = Inv->getNormalDest();
 130
 131     DomTreeNode *DomNode = DT.getNode(DomBB);
 132
 133     SmallVector<PHINode *, 16> AddedPHIs;
 134     SmallVector<PHINode *, 8> PostProcessPHIs;
 135
 136     SmallVector<PHINode *, 4> InsertedPHIs;
 137     SSAUpdater SSAUpdate(&InsertedPHIs);
 138     SSAUpdate.Initialize(I->getType(), I->getName());
 139
 140     // Force re-computation of I, as some users now need to use the new PHI
 141     // node.
 142     if (SE)
 143       SE->forgetValue(I);
 144
 145     // Insert the LCSSA phi's into all of the exit blocks dominated by the
 146     // value, and add them to the Phi's map.
 147     for (BasicBlock *ExitBB : ExitBlocks) {
 148       if (!DT.dominates(DomNode, DT.getNode(ExitBB)))
 149         continue;
 150
 151       // If we already inserted something for this BB, don't reprocess it.
 152       if (SSAUpdate.HasValueForBlock(ExitBB))
 153         continue;
 154
 155       PHINode *PN = PHINode::Create(I->getType(), PredCache.size(ExitBB),
 156                                     I->getName() + ".lcssa", &ExitBB->front());
 157       // Get the debug location from the original instruction.
 158       PN->setDebugLoc(I->getDebugLoc());
 159       // Add inputs from inside the loop for this PHI.
 160       for (BasicBlock *Pred : PredCache.get(ExitBB)) {
 161         PN->addIncoming(I, Pred);
 162
 163         // If the exit block has a predecessor not within the loop, arrange for
 164         // the incoming value use corresponding to that predecessor to be
 165         // rewritten in terms of a different LCSSA PHI.
 166         if (!L->contains(Pred))
 167           UsesToRewrite.push_back(
 168               &PN->getOperandUse(PN->getOperandNumForIncomingValue(
 169                   PN->getNumIncomingValues() - 1)));
 170       }
 171
 172       AddedPHIs.push_back(PN);
 173
 174       // Remember that this phi makes the value alive in this block.
 175       SSAUpdate.AddAvailableValue(ExitBB, PN);
 176
 177       // LoopSimplify might fail to simplify some loops (e.g. when indirect
 178       // branches are involved). In such situations, it might happen that an
 179       // exit for Loop L1 is the header of a disjoint Loop L2. Thus, when we
 180       // create PHIs in such an exit block, we are also inserting PHIs into L2's
 181       // header. This could break LCSSA form for L2 because these inserted PHIs
 182       // can also have uses outside of L2. Remember all PHIs in such situation
 183       // as to revisit than later on. FIXME: Remove this if indirectbr support
 184       // into LoopSimplify gets improved.
 185       if (auto *OtherLoop = LI.getLoopFor(ExitBB))
 186         if (!L->contains(OtherLoop))
 187           PostProcessPHIs.push_back(PN);
 188     }
 189
 190     // Rewrite all uses outside the loop in terms of the new PHIs we just
 191     // inserted.
 192     for (Use *UseToRewrite : UsesToRewrite) {
 193       // If this use is in an exit block, rewrite to use the newly inserted PHI.
 194       // This is required for correctness because SSAUpdate doesn't handle uses
 195       // in the same block.  It assumes the PHI we inserted is at the end of the
 196       // block.
 197       Instruction *User = cast<Instruction>(UseToRewrite->getUser());
 198       BasicBlock *UserBB = User->getParent();
 199       if (auto *PN = dyn_cast<PHINode>(User))
 200         UserBB = PN->getIncomingBlock(*UseToRewrite);
 201
 202       if (isa<PHINode>(UserBB->begin()) && isExitBlock(UserBB, ExitBlocks)) {
 203         UseToRewrite->set(&UserBB->front());
 204         continue;
 205       }
 206
 207       // If we added a single PHI, it must dominate all uses and we can directly
 208       // rename it.
 209       if (AddedPHIs.size() == 1) {
 210         UseToRewrite->set(AddedPHIs[0]);
 211         continue;
 212       }
 213
 214       // Otherwise, do full PHI insertion.
 215       SSAUpdate.RewriteUse(*UseToRewrite);
 216     }
 217
 218     SmallVector<DbgValueInst *, 4> DbgValues;
 219     llvm::findDbgValues(DbgValues, I);
 220
 221     // Update pre-existing debug value uses that reside outside the loop.
 222     auto &Ctx = I->getContext();
 223     for (auto DVI : DbgValues) {
 224       BasicBlock *UserBB = DVI->getParent();
 225       if (InstBB == UserBB || L->contains(UserBB))
 226         continue;
 227       // We currently only handle debug values residing in blocks that were
 228       // traversed while rewriting the uses. If we inserted just a single PHI,
 229       // we will handle all relevant debug values.
 230       Value *V = AddedPHIs.size() == 1 ? AddedPHIs[0]
 231                                        : SSAUpdate.FindValueForBlock(UserBB);
 232       if (V)
 233         DVI->setOperand(0, MetadataAsValue::get(Ctx, ValueAsMetadata::get(V)));
 234     }
 235
 236     // SSAUpdater might have inserted phi-nodes inside other loops. We'll need
 237     // to post-process them to keep LCSSA form.
 238     for (PHINode *InsertedPN : InsertedPHIs) {
 239       if (auto *OtherLoop = LI.getLoopFor(InsertedPN->getParent()))
 240         if (!L->contains(OtherLoop))
 241           PostProcessPHIs.push_back(InsertedPN);
 242     }
 243
 244     // Post process PHI instructions that were inserted into another disjoint
 245     // loop and update their exits properly.
 246     for (auto *PostProcessPN : PostProcessPHIs)
 247       if (!PostProcessPN->use_empty())
 248         Worklist.push_back(PostProcessPN);
 249
 250     // Keep track of PHI nodes that we want to remove because they did not have
 251     // any uses rewritten. If the new PHI is used, store it so that we can
 252     // try to propagate dbg.value intrinsics to it.
 253     SmallVector<PHINode *, 2> NeedDbgValues;
 254     for (PHINode *PN : AddedPHIs)
 255       if (PN->use_empty())
 256         PHIsToRemove.insert(PN);
 257       else
 258         NeedDbgValues.push_back(PN);
 259     insertDebugValuesForPHIs(InstBB, NeedDbgValues);
 260     Changed = true;
 261   }
 262   // Remove PHI nodes that did not have any uses rewritten. We need to redo the
 263   // use_empty() check here, because even if the PHI node wasn't used when added
 264   // to PHIsToRemove, later added PHI nodes can be using it.  This cleanup is
 265   // not guaranteed to handle trees/cycles of PHI nodes that only are used by
 266   // each other. Such situations has only been noticed when the input IR
 267   // contains unreachable code, and leaving some extra redundant PHI nodes in
 268   // such situations is considered a minor problem.
 269   for (PHINode *PN : PHIsToRemove)
 270     if (PN->use_empty())
 271       PN->eraseFromParent();
 272   return Changed;
 273 }
 274
 275 // Compute the set of BasicBlocks in the loop `L` dominating at least one exit.
 276 static void computeBlocksDominatingExits(
 277     Loop &L, DominatorTree &DT, SmallVector<BasicBlock *, 8> &ExitBlocks,
 278     SmallSetVector<BasicBlock *, 8> &BlocksDominatingExits) {
 279   SmallVector<BasicBlock *, 8> BBWorklist;
 280
 281   // We start from the exit blocks, as every block trivially dominates itself
 282   // (not strictly).
 283   for (BasicBlock *BB : ExitBlocks)
 284     BBWorklist.push_back(BB);
 285
 286   while (!BBWorklist.empty()) {
 287     BasicBlock *BB = BBWorklist.pop_back_val();
 288
 289     // Check if this is a loop header. If this is the case, we're done.
 290     if (L.getHeader() == BB)
 291       continue;
 292
 293     // Otherwise, add its immediate predecessor in the dominator tree to the
 294     // worklist, unless we visited it already.
 295     BasicBlock *IDomBB = DT.getNode(BB)->getIDom()->getBlock();
 296
 297     // Exit blocks can have an immediate dominator not beloinging to the
 298     // loop. For an exit block to be immediately dominated by another block
 299     // outside the loop, it implies not all paths from that dominator, to the
 300     // exit block, go through the loop.
 301     // Example:
 302     //
 303     // |---- A
 304     // |     |
 305     // |     B<--
 306     // |     |  |
 307     // |---> C --
 308     //       |
 309     //       D
 310     //
 311     // C is the exit block of the loop and it's immediately dominated by A,
 312     // which doesn't belong to the loop.
 313     if (!L.contains(IDomBB))
 314       continue;
 315
 316     if (BlocksDominatingExits.insert(IDomBB))
 317       BBWorklist.push_back(IDomBB);
 318   }
 319 }
 320
 321 bool llvm::formLCSSA(Loop &L, DominatorTree &DT, LoopInfo *LI,
 322                      ScalarEvolution *SE) {
 323   bool Changed = false;
 324
 325 #ifdef EXPENSIVE_CHECKS
 326   // Verify all sub-loops are in LCSSA form already.
 327   for (Loop *SubLoop: L)
 328     assert(SubLoop->isRecursivelyLCSSAForm(DT, *LI) && "Subloop not in LCSSA!");
 329 #endif
 330
 331   SmallVector<BasicBlock *, 8> ExitBlocks;
 332   L.getExitBlocks(ExitBlocks);
 333   if (ExitBlocks.empty())
 334     return false;
 335
 336   SmallSetVector<BasicBlock *, 8> BlocksDominatingExits;
 337
 338   // We want to avoid use-scanning leveraging dominance informations.
 339   // If a block doesn't dominate any of the loop exits, the none of the values
 340   // defined in the loop can be used outside.
 341   // We compute the set of blocks fullfilling the conditions in advance
 342   // walking the dominator tree upwards until we hit a loop header.
 343   computeBlocksDominatingExits(L, DT, ExitBlocks, BlocksDominatingExits);
 344
 345   SmallVector<Instruction *, 8> Worklist;
 346
 347   // Look at all the instructions in the loop, checking to see if they have uses
 348   // outside the loop.  If so, put them into the worklist to rewrite those uses.
 349   for (BasicBlock *BB : BlocksDominatingExits) {
 350     // Skip blocks that are part of any sub-loops, they must be in LCSSA
 351     // already.
 352     if (LI->getLoopFor(BB) != &L)
 353       continue;
 354     for (Instruction &I : *BB) {
 355       // Reject two common cases fast: instructions with no uses (like stores)
 356       // and instructions with one use that is in the same block as this.
 357       if (I.use_empty() ||
 358           (I.hasOneUse() && I.user_back()->getParent() == BB &&
 359            !isa<PHINode>(I.user_back())))
 360         continue;
 361
 362       // Tokens cannot be used in PHI nodes, so we skip over them.
 363       // We can run into tokens which are live out of a loop with catchswitch
 364       // instructions in Windows EH if the catchswitch has one catchpad which
 365       // is inside the loop and another which is not.
 366       if (I.getType()->isTokenTy())
 367         continue;
 368
 369       Worklist.push_back(&I);
 370     }
 371   }
 372   Changed = formLCSSAForInstructions(Worklist, DT, *LI, SE);
 373
 374   // If we modified the code, remove any caches about the loop from SCEV to
 375   // avoid dangling entries.
 376   // FIXME: This is a big hammer, can we clear the cache more selectively?
 377   if (SE && Changed)
 378     SE->forgetLoop(&L);
 379
 380   assert(L.isLCSSAForm(DT));
 381
 382   return Changed;
 383 }
 384
 385 /// Process a loop nest depth first.
 386 bool llvm::formLCSSARecursively(Loop &L, DominatorTree &DT, LoopInfo *LI,
 387                                 ScalarEvolution *SE) {
 388   bool Changed = false;
 389
 390   // Recurse depth-first through inner loops.
 391   for (Loop *SubLoop : L.getSubLoops())
 392     Changed |= formLCSSARecursively(*SubLoop, DT, LI, SE);
 393
 394   Changed |= formLCSSA(L, DT, LI, SE);
 395   return Changed;
 396 }
 397
 398 /// Process all loops in the function, inner-most out.
 399 static bool formLCSSAOnAllLoops(LoopInfo *LI, DominatorTree &DT,
 400                                 ScalarEvolution *SE) {
 401   bool Changed = false;
 402   for (auto &L : *LI)
 403     Changed |= formLCSSARecursively(*L, DT, LI, SE);
 404   return Changed;
 405 }
 406
 407 namespace {
 408 struct LCSSAWrapperPass : public FunctionPass {
 409   static char ID; // Pass identification, replacement for typeid
 410   LCSSAWrapperPass() : FunctionPass(ID) {
 411     initializeLCSSAWrapperPassPass(*PassRegistry::getPassRegistry());
 412   }
 413
 414   // Cached analysis information for the current function.
 415   DominatorTree *DT;
 416   LoopInfo *LI;
 417   ScalarEvolution *SE;
 418
 419   bool runOnFunction(Function &F) override;
 420   void verifyAnalysis() const override {
 421     // This check is very expensive. On the loop intensive compiles it may cause
 422     // up to 10x slowdown. Currently it's disabled by default. LPPassManager
 423     // always does limited form of the LCSSA verification. Similar reasoning
 424     // was used for the LoopInfo verifier.
 425     if (VerifyLoopLCSSA) {
 426       assert(all_of(*LI,
 427                     [&](Loop *L) {
 428                       return L->isRecursivelyLCSSAForm(*DT, *LI);
 429                     }) &&
 430              "LCSSA form is broken!");
 431     }
 432   };
 433
 434   /// This transformation requires natural loop information & requires that
 435   /// loop preheaders be inserted into the CFG.  It maintains both of these,
 436   /// as well as the CFG.  It also requires dominator information.
 437   void getAnalysisUsage(AnalysisUsage &AU) const override {
 438     AU.setPreservesCFG();
 439
 440     AU.addRequired<DominatorTreeWrapperPass>();
 441     AU.addRequired<LoopInfoWrapperPass>();
 442     AU.addPreservedID(LoopSimplifyID);
 443     AU.addPreserved<AAResultsWrapperPass>();
 444     AU.addPreserved<BasicAAWrapperPass>();
 445     AU.addPreserved<GlobalsAAWrapperPass>();
 446     AU.addPreserved<ScalarEvolutionWrapperPass>();
 447     AU.addPreserved<SCEVAAWrapperPass>();
 448     AU.addPreserved<BranchProbabilityInfoWrapperPass>();
 449     AU.addPreserved<MemorySSAWrapperPass>();
 450
 451     // This is needed to perform LCSSA verification inside LPPassManager
 452     AU.addRequired<LCSSAVerificationPass>();
 453     AU.addPreserved<LCSSAVerificationPass>();
 454   }
 455 };
 456 }
 457
 458 char LCSSAWrapperPass::ID = 0;
 459 INITIALIZE_PASS_BEGIN(LCSSAWrapperPass, "lcssa", "Loop-Closed SSA Form Pass",
 460                       false, false)
 461 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
 462 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
 463 INITIALIZE_PASS_DEPENDENCY(LCSSAVerificationPass)
 464 INITIALIZE_PASS_END(LCSSAWrapperPass, "lcssa", "Loop-Closed SSA Form Pass",
 465                     false, false)
 466
 467 Pass *llvm::createLCSSAPass() { return new LCSSAWrapperPass(); }
 468 char &llvm::LCSSAID = LCSSAWrapperPass::ID;
 469
 470 /// Transform \p F into loop-closed SSA form.
 471 bool LCSSAWrapperPass::runOnFunction(Function &F) {
 472   LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
 473   DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
 474   auto *SEWP = getAnalysisIfAvailable<ScalarEvolutionWrapperPass>();
 475   SE = SEWP ? &SEWP->getSE() : nullptr;
 476
 477   return formLCSSAOnAllLoops(LI, *DT, SE);
 478 }
 479
 480 PreservedAnalyses LCSSAPass::run(Function &F, FunctionAnalysisManager &AM) {
 481   auto &LI = AM.getResult<LoopAnalysis>(F);
 482   auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
 483   auto *SE = AM.getCachedResult<ScalarEvolutionAnalysis>(F);
 484   if (!formLCSSAOnAllLoops(&LI, DT, SE))
 485     return PreservedAnalyses::all();
 486
 487   PreservedAnalyses PA;
 488   PA.preserveSet<CFGAnalyses>();
 489   PA.preserve<BasicAA>();
 490   PA.preserve<GlobalsAA>();
 491   PA.preserve<SCEVAA>();
 492   PA.preserve<ScalarEvolutionAnalysis>();
 493   // BPI maps terminators to probabilities, since we don't modify the CFG, no
 494   // updates are needed to preserve it.
 495   PA.preserve<BranchProbabilityAnalysis>();
 496   PA.preserve<MemorySSAAnalysis>();
 497   return PA;
 498 }