LCSSA.cpp 19.2 KB
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510
//===-- LCSSA.cpp - Convert loops into loop-closed SSA form ---------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// This pass transforms loops by placing phi nodes at the end of the loops for
// all values that are live across the loop boundary.  For example, it turns
// the left into the right code:
//
// for (...)                for (...)
//   if (c)                   if (c)
//     X1 = ...                 X1 = ...
//   else                     else
//     X2 = ...                 X2 = ...
//   X3 = phi(X1, X2)         X3 = phi(X1, X2)
// ... = X3 + 4             X4 = phi(X3)
//                          ... = X4 + 4
//
// This is still valid LLVM; the extra phi nodes are purely redundant, and will
// be trivially eliminated by InstCombine.  The major benefit of this
// transformation is that it makes many other loop optimizations, such as
// LoopUnswitching, simpler.
//
//===----------------------------------------------------------------------===//

#include "llvm/Transforms/Utils/LCSSA.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/BasicAliasAnalysis.h"
#include "llvm/Analysis/BranchProbabilityInfo.h"
#include "llvm/Analysis/GlobalsModRef.h"
#include "llvm/Analysis/LoopPass.h"
#include "llvm/Analysis/MemorySSA.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/IRBuilder.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/PredIteratorCache.h"
#include "llvm/InitializePasses.h"
#include "llvm/Pass.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Transforms/Utils.h"
#include "llvm/Transforms/Utils/Local.h"
#include "llvm/Transforms/Utils/LoopUtils.h"
#include "llvm/Transforms/Utils/SSAUpdater.h"
using namespace llvm;

#define DEBUG_TYPE "lcssa"

STATISTIC(NumLCSSA, "Number of live out of a loop variables");

#ifdef EXPENSIVE_CHECKS
static bool VerifyLoopLCSSA = true;
#else
static bool VerifyLoopLCSSA = false;
#endif
static cl::opt<bool, true>
    VerifyLoopLCSSAFlag("verify-loop-lcssa", cl::location(VerifyLoopLCSSA),
                        cl::Hidden,
                        cl::desc("Verify loop lcssa form (time consuming)"));

/// Return true if the specified block is in the list.
static bool isExitBlock(BasicBlock *BB,
                        const SmallVectorImpl<BasicBlock *> &ExitBlocks) {
  return is_contained(ExitBlocks, BB);
}

/// For every instruction from the worklist, check to see if it has any uses
/// that are outside the current loop.  If so, insert LCSSA PHI nodes and
/// rewrite the uses.
bool llvm::formLCSSAForInstructions(SmallVectorImpl<Instruction *> &Worklist,
                                    const DominatorTree &DT, const LoopInfo &LI,
                                    ScalarEvolution *SE, IRBuilderBase &Builder,
                                    SmallVectorImpl<PHINode *> *PHIsToRemove) {
  SmallVector<Use *, 16> UsesToRewrite;
  SmallSetVector<PHINode *, 16> LocalPHIsToRemove;
  PredIteratorCache PredCache;
  bool Changed = false;

  IRBuilderBase::InsertPointGuard InsertPtGuard(Builder);

  // Cache the Loop ExitBlocks across this loop.  We expect to get a lot of
  // instructions within the same loops, computing the exit blocks is
  // expensive, and we're not mutating the loop structure.
  SmallDenseMap<Loop*, SmallVector<BasicBlock *,1>> LoopExitBlocks;

  while (!Worklist.empty()) {
    UsesToRewrite.clear();

    Instruction *I = Worklist.pop_back_val();
    assert(!I->getType()->isTokenTy() && "Tokens shouldn't be in the worklist");
    BasicBlock *InstBB = I->getParent();
    Loop *L = LI.getLoopFor(InstBB);
    assert(L && "Instruction belongs to a BB that's not part of a loop");
    if (!LoopExitBlocks.count(L))
      L->getExitBlocks(LoopExitBlocks[L]);
    assert(LoopExitBlocks.count(L));
    const SmallVectorImpl<BasicBlock *> &ExitBlocks = LoopExitBlocks[L];

    if (ExitBlocks.empty())
      continue;

    for (Use &U : I->uses()) {
      Instruction *User = cast<Instruction>(U.getUser());
      BasicBlock *UserBB = User->getParent();
      if (auto *PN = dyn_cast<PHINode>(User))
        UserBB = PN->getIncomingBlock(U);

      if (InstBB != UserBB && !L->contains(UserBB))
        UsesToRewrite.push_back(&U);
    }

    // If there are no uses outside the loop, exit with no change.
    if (UsesToRewrite.empty())
      continue;

    ++NumLCSSA; // We are applying the transformation

    // Invoke instructions are special in that their result value is not
    // available along their unwind edge. The code below tests to see whether
    // DomBB dominates the value, so adjust DomBB to the normal destination
    // block, which is effectively where the value is first usable.
    BasicBlock *DomBB = InstBB;
    if (auto *Inv = dyn_cast<InvokeInst>(I))
      DomBB = Inv->getNormalDest();

    const DomTreeNode *DomNode = DT.getNode(DomBB);

    SmallVector<PHINode *, 16> AddedPHIs;
    SmallVector<PHINode *, 8> PostProcessPHIs;

    SmallVector<PHINode *, 4> InsertedPHIs;
    SSAUpdater SSAUpdate(&InsertedPHIs);
    SSAUpdate.Initialize(I->getType(), I->getName());

    // Force re-computation of I, as some users now need to use the new PHI
    // node.
    if (SE)
      SE->forgetValue(I);

    // Insert the LCSSA phi's into all of the exit blocks dominated by the
    // value, and add them to the Phi's map.
    for (BasicBlock *ExitBB : ExitBlocks) {
      if (!DT.dominates(DomNode, DT.getNode(ExitBB)))
        continue;

      // If we already inserted something for this BB, don't reprocess it.
      if (SSAUpdate.HasValueForBlock(ExitBB))
        continue;
      Builder.SetInsertPoint(&ExitBB->front());
      PHINode *PN = Builder.CreatePHI(I->getType(), PredCache.size(ExitBB),
                                      I->getName() + ".lcssa");
      // Get the debug location from the original instruction.
      PN->setDebugLoc(I->getDebugLoc());
      // Add inputs from inside the loop for this PHI.
      for (BasicBlock *Pred : PredCache.get(ExitBB)) {
        PN->addIncoming(I, Pred);

        // If the exit block has a predecessor not within the loop, arrange for
        // the incoming value use corresponding to that predecessor to be
        // rewritten in terms of a different LCSSA PHI.
        if (!L->contains(Pred))
          UsesToRewrite.push_back(
              &PN->getOperandUse(PN->getOperandNumForIncomingValue(
                  PN->getNumIncomingValues() - 1)));
      }

      AddedPHIs.push_back(PN);

      // Remember that this phi makes the value alive in this block.
      SSAUpdate.AddAvailableValue(ExitBB, PN);

      // LoopSimplify might fail to simplify some loops (e.g. when indirect
      // branches are involved). In such situations, it might happen that an
      // exit for Loop L1 is the header of a disjoint Loop L2. Thus, when we
      // create PHIs in such an exit block, we are also inserting PHIs into L2's
      // header. This could break LCSSA form for L2 because these inserted PHIs
      // can also have uses outside of L2. Remember all PHIs in such situation
      // as to revisit than later on. FIXME: Remove this if indirectbr support
      // into LoopSimplify gets improved.
      if (auto *OtherLoop = LI.getLoopFor(ExitBB))
        if (!L->contains(OtherLoop))
          PostProcessPHIs.push_back(PN);
    }

    // Rewrite all uses outside the loop in terms of the new PHIs we just
    // inserted.
    for (Use *UseToRewrite : UsesToRewrite) {
      // If this use is in an exit block, rewrite to use the newly inserted PHI.
      // This is required for correctness because SSAUpdate doesn't handle uses
      // in the same block.  It assumes the PHI we inserted is at the end of the
      // block.
      Instruction *User = cast<Instruction>(UseToRewrite->getUser());
      BasicBlock *UserBB = User->getParent();
      if (auto *PN = dyn_cast<PHINode>(User))
        UserBB = PN->getIncomingBlock(*UseToRewrite);

      if (isa<PHINode>(UserBB->begin()) && isExitBlock(UserBB, ExitBlocks)) {
        UseToRewrite->set(&UserBB->front());
        continue;
      }

      // If we added a single PHI, it must dominate all uses and we can directly
      // rename it.
      if (AddedPHIs.size() == 1) {
        UseToRewrite->set(AddedPHIs[0]);
        continue;
      }

      // Otherwise, do full PHI insertion.
      SSAUpdate.RewriteUse(*UseToRewrite);
    }

    SmallVector<DbgValueInst *, 4> DbgValues;
    llvm::findDbgValues(DbgValues, I);

    // Update pre-existing debug value uses that reside outside the loop.
    auto &Ctx = I->getContext();
    for (auto DVI : DbgValues) {
      BasicBlock *UserBB = DVI->getParent();
      if (InstBB == UserBB || L->contains(UserBB))
        continue;
      // We currently only handle debug values residing in blocks that were
      // traversed while rewriting the uses. If we inserted just a single PHI,
      // we will handle all relevant debug values.
      Value *V = AddedPHIs.size() == 1 ? AddedPHIs[0]
                                       : SSAUpdate.FindValueForBlock(UserBB);
      if (V)
        DVI->setOperand(0, MetadataAsValue::get(Ctx, ValueAsMetadata::get(V)));
    }

    // SSAUpdater might have inserted phi-nodes inside other loops. We'll need
    // to post-process them to keep LCSSA form.
    for (PHINode *InsertedPN : InsertedPHIs) {
      if (auto *OtherLoop = LI.getLoopFor(InsertedPN->getParent()))
        if (!L->contains(OtherLoop))
          PostProcessPHIs.push_back(InsertedPN);
    }

    // Post process PHI instructions that were inserted into another disjoint
    // loop and update their exits properly.
    for (auto *PostProcessPN : PostProcessPHIs)
      if (!PostProcessPN->use_empty())
        Worklist.push_back(PostProcessPN);

    // Keep track of PHI nodes that we want to remove because they did not have
    // any uses rewritten. If the new PHI is used, store it so that we can
    // try to propagate dbg.value intrinsics to it.
    SmallVector<PHINode *, 2> NeedDbgValues;
    for (PHINode *PN : AddedPHIs)
      if (PN->use_empty())
        LocalPHIsToRemove.insert(PN);
      else
        NeedDbgValues.push_back(PN);
    insertDebugValuesForPHIs(InstBB, NeedDbgValues);
    Changed = true;
  }

  // Remove PHI nodes that did not have any uses rewritten or add them to
  // PHIsToRemove, so the caller can remove them after some additional cleanup.
  // We need to redo the use_empty() check here, because even if the PHI node
  // wasn't used when added to LocalPHIsToRemove, later added PHI nodes can be
  // using it.  This cleanup is not guaranteed to handle trees/cycles of PHI
  // nodes that only are used by each other. Such situations has only been
  // noticed when the input IR contains unreachable code, and leaving some extra
  // redundant PHI nodes in such situations is considered a minor problem.
  if (PHIsToRemove) {
    PHIsToRemove->append(LocalPHIsToRemove.begin(), LocalPHIsToRemove.end());
  } else {
    for (PHINode *PN : LocalPHIsToRemove)
      if (PN->use_empty())
        PN->eraseFromParent();
  }
  return Changed;
}

// Compute the set of BasicBlocks in the loop `L` dominating at least one exit.
static void computeBlocksDominatingExits(
    Loop &L, const DominatorTree &DT, SmallVector<BasicBlock *, 8> &ExitBlocks,
    SmallSetVector<BasicBlock *, 8> &BlocksDominatingExits) {
  SmallVector<BasicBlock *, 8> BBWorklist;

  // We start from the exit blocks, as every block trivially dominates itself
  // (not strictly).
  for (BasicBlock *BB : ExitBlocks)
    BBWorklist.push_back(BB);

  while (!BBWorklist.empty()) {
    BasicBlock *BB = BBWorklist.pop_back_val();

    // Check if this is a loop header. If this is the case, we're done.
    if (L.getHeader() == BB)
      continue;

    // Otherwise, add its immediate predecessor in the dominator tree to the
    // worklist, unless we visited it already.
    BasicBlock *IDomBB = DT.getNode(BB)->getIDom()->getBlock();

    // Exit blocks can have an immediate dominator not beloinging to the
    // loop. For an exit block to be immediately dominated by another block
    // outside the loop, it implies not all paths from that dominator, to the
    // exit block, go through the loop.
    // Example:
    //
    // |---- A
    // |     |
    // |     B<--
    // |     |  |
    // |---> C --
    //       |
    //       D
    //
    // C is the exit block of the loop and it's immediately dominated by A,
    // which doesn't belong to the loop.
    if (!L.contains(IDomBB))
      continue;

    if (BlocksDominatingExits.insert(IDomBB))
      BBWorklist.push_back(IDomBB);
  }
}

bool llvm::formLCSSA(Loop &L, const DominatorTree &DT, const LoopInfo *LI,
                     ScalarEvolution *SE) {
  bool Changed = false;

#ifdef EXPENSIVE_CHECKS
  // Verify all sub-loops are in LCSSA form already.
  for (Loop *SubLoop: L)
    assert(SubLoop->isRecursivelyLCSSAForm(DT, *LI) && "Subloop not in LCSSA!");
#endif

  SmallVector<BasicBlock *, 8> ExitBlocks;
  L.getExitBlocks(ExitBlocks);
  if (ExitBlocks.empty())
    return false;

  SmallSetVector<BasicBlock *, 8> BlocksDominatingExits;

  // We want to avoid use-scanning leveraging dominance informations.
  // If a block doesn't dominate any of the loop exits, the none of the values
  // defined in the loop can be used outside.
  // We compute the set of blocks fullfilling the conditions in advance
  // walking the dominator tree upwards until we hit a loop header.
  computeBlocksDominatingExits(L, DT, ExitBlocks, BlocksDominatingExits);

  SmallVector<Instruction *, 8> Worklist;

  // Look at all the instructions in the loop, checking to see if they have uses
  // outside the loop.  If so, put them into the worklist to rewrite those uses.
  for (BasicBlock *BB : BlocksDominatingExits) {
    // Skip blocks that are part of any sub-loops, they must be in LCSSA
    // already.
    if (LI->getLoopFor(BB) != &L)
      continue;
    for (Instruction &I : *BB) {
      // Reject two common cases fast: instructions with no uses (like stores)
      // and instructions with one use that is in the same block as this.
      if (I.use_empty() ||
          (I.hasOneUse() && I.user_back()->getParent() == BB &&
           !isa<PHINode>(I.user_back())))
        continue;

      // Tokens cannot be used in PHI nodes, so we skip over them.
      // We can run into tokens which are live out of a loop with catchswitch
      // instructions in Windows EH if the catchswitch has one catchpad which
      // is inside the loop and another which is not.
      if (I.getType()->isTokenTy())
        continue;

      Worklist.push_back(&I);
    }
  }

  IRBuilder<> Builder(L.getHeader()->getContext());
  Changed = formLCSSAForInstructions(Worklist, DT, *LI, SE, Builder);

  // If we modified the code, remove any caches about the loop from SCEV to
  // avoid dangling entries.
  // FIXME: This is a big hammer, can we clear the cache more selectively?
  if (SE && Changed)
    SE->forgetLoop(&L);

  assert(L.isLCSSAForm(DT));

  return Changed;
}

/// Process a loop nest depth first.
bool llvm::formLCSSARecursively(Loop &L, const DominatorTree &DT,
                                const LoopInfo *LI, ScalarEvolution *SE) {
  bool Changed = false;

  // Recurse depth-first through inner loops.
  for (Loop *SubLoop : L.getSubLoops())
    Changed |= formLCSSARecursively(*SubLoop, DT, LI, SE);

  Changed |= formLCSSA(L, DT, LI, SE);
  return Changed;
}

/// Process all loops in the function, inner-most out.
static bool formLCSSAOnAllLoops(const LoopInfo *LI, const DominatorTree &DT,
                                ScalarEvolution *SE) {
  bool Changed = false;
  for (auto &L : *LI)
    Changed |= formLCSSARecursively(*L, DT, LI, SE);
  return Changed;
}

namespace {
struct LCSSAWrapperPass : public FunctionPass {
  static char ID; // Pass identification, replacement for typeid
  LCSSAWrapperPass() : FunctionPass(ID) {
    initializeLCSSAWrapperPassPass(*PassRegistry::getPassRegistry());
  }

  // Cached analysis information for the current function.
  DominatorTree *DT;
  LoopInfo *LI;
  ScalarEvolution *SE;

  bool runOnFunction(Function &F) override;
  void verifyAnalysis() const override {
    // This check is very expensive. On the loop intensive compiles it may cause
    // up to 10x slowdown. Currently it's disabled by default. LPPassManager
    // always does limited form of the LCSSA verification. Similar reasoning
    // was used for the LoopInfo verifier.
    if (VerifyLoopLCSSA) {
      assert(all_of(*LI,
                    [&](Loop *L) {
                      return L->isRecursivelyLCSSAForm(*DT, *LI);
                    }) &&
             "LCSSA form is broken!");
    }
  };

  /// This transformation requires natural loop information & requires that
  /// loop preheaders be inserted into the CFG.  It maintains both of these,
  /// as well as the CFG.  It also requires dominator information.
  void getAnalysisUsage(AnalysisUsage &AU) const override {
    AU.setPreservesCFG();

    AU.addRequired<DominatorTreeWrapperPass>();
    AU.addRequired<LoopInfoWrapperPass>();
    AU.addPreservedID(LoopSimplifyID);
    AU.addPreserved<AAResultsWrapperPass>();
    AU.addPreserved<BasicAAWrapperPass>();
    AU.addPreserved<GlobalsAAWrapperPass>();
    AU.addPreserved<ScalarEvolutionWrapperPass>();
    AU.addPreserved<SCEVAAWrapperPass>();
    AU.addPreserved<BranchProbabilityInfoWrapperPass>();
    AU.addPreserved<MemorySSAWrapperPass>();

    // This is needed to perform LCSSA verification inside LPPassManager
    AU.addRequired<LCSSAVerificationPass>();
    AU.addPreserved<LCSSAVerificationPass>();
  }
};
}

char LCSSAWrapperPass::ID = 0;
INITIALIZE_PASS_BEGIN(LCSSAWrapperPass, "lcssa", "Loop-Closed SSA Form Pass",
                      false, false)
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
INITIALIZE_PASS_DEPENDENCY(LCSSAVerificationPass)
INITIALIZE_PASS_END(LCSSAWrapperPass, "lcssa", "Loop-Closed SSA Form Pass",
                    false, false)

Pass *llvm::createLCSSAPass() { return new LCSSAWrapperPass(); }
char &llvm::LCSSAID = LCSSAWrapperPass::ID;

/// Transform \p F into loop-closed SSA form.
bool LCSSAWrapperPass::runOnFunction(Function &F) {
  LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
  DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
  auto *SEWP = getAnalysisIfAvailable<ScalarEvolutionWrapperPass>();
  SE = SEWP ? &SEWP->getSE() : nullptr;

  return formLCSSAOnAllLoops(LI, *DT, SE);
}

PreservedAnalyses LCSSAPass::run(Function &F, FunctionAnalysisManager &AM) {
  auto &LI = AM.getResult<LoopAnalysis>(F);
  auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
  auto *SE = AM.getCachedResult<ScalarEvolutionAnalysis>(F);
  if (!formLCSSAOnAllLoops(&LI, DT, SE))
    return PreservedAnalyses::all();

  PreservedAnalyses PA;
  PA.preserveSet<CFGAnalyses>();
  PA.preserve<BasicAA>();
  PA.preserve<GlobalsAA>();
  PA.preserve<SCEVAA>();
  PA.preserve<ScalarEvolutionAnalysis>();
  // BPI maps terminators to probabilities, since we don't modify the CFG, no
  // updates are needed to preserve it.
  PA.preserve<BranchProbabilityAnalysis>();
  PA.preserve<MemorySSAAnalysis>();
  return PA;
}