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

   1 //===- BreakCriticalEdges.cpp - Critical Edge Elimination Pass ------------===//
   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 // BreakCriticalEdges pass - Break all of the critical edges in the CFG by
  10 // inserting a dummy basic block.  This pass may be "required" by passes that
  11 // cannot deal with critical edges.  For this usage, the structure type is
  12 // forward declared.  This pass obviously invalidates the CFG, but can update
  13 // dominator trees.
  14 //
  15 //===----------------------------------------------------------------------===//
  16
  17 #include "llvm/Transforms/Utils/BreakCriticalEdges.h"
  18 #include "llvm/ADT/SetVector.h"
  19 #include "llvm/ADT/SmallVector.h"
  20 #include "llvm/ADT/Statistic.h"
  21 #include "llvm/Analysis/BlockFrequencyInfo.h"
  22 #include "llvm/Analysis/BranchProbabilityInfo.h"
  23 #include "llvm/Analysis/CFG.h"
  24 #include "llvm/Analysis/LoopInfo.h"
  25 #include "llvm/Analysis/MemorySSAUpdater.h"
  26 #include "llvm/Analysis/PostDominators.h"
  27 #include "llvm/IR/CFG.h"
  28 #include "llvm/IR/Dominators.h"
  29 #include "llvm/IR/Instructions.h"
  30 #include "llvm/IR/Type.h"
  31 #include "llvm/InitializePasses.h"
  32 #include "llvm/Support/ErrorHandling.h"
  33 #include "llvm/Transforms/Utils.h"
  34 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
  35 #include "llvm/Transforms/Utils/Cloning.h"
  36 #include "llvm/Transforms/Utils/ValueMapper.h"
  37 using namespace llvm;
  38
  39 #define DEBUG_TYPE "break-crit-edges"
  40
  41 STATISTIC(NumBroken, "Number of blocks inserted");
  42
  43 namespace {
  44   struct BreakCriticalEdges : public FunctionPass {
  45     static char ID; // Pass identification, replacement for typeid
  46     BreakCriticalEdges() : FunctionPass(ID) {
  47       initializeBreakCriticalEdgesPass(*PassRegistry::getPassRegistry());
  48     }
  49
  50     bool runOnFunction(Function &F) override {
  51       auto *DTWP = getAnalysisIfAvailable<DominatorTreeWrapperPass>();
  52       auto *DT = DTWP ? &DTWP->getDomTree() : nullptr;
  53
  54       auto *PDTWP = getAnalysisIfAvailable<PostDominatorTreeWrapperPass>();
  55       auto *PDT = PDTWP ? &PDTWP->getPostDomTree() : nullptr;
  56
  57       auto *LIWP = getAnalysisIfAvailable<LoopInfoWrapperPass>();
  58       auto *LI = LIWP ? &LIWP->getLoopInfo() : nullptr;
  59       unsigned N =
  60           SplitAllCriticalEdges(F, CriticalEdgeSplittingOptions(DT, LI, nullptr, PDT));
  61       NumBroken += N;
  62       return N > 0;
  63     }
  64
  65     void getAnalysisUsage(AnalysisUsage &AU) const override {
  66       AU.addPreserved<DominatorTreeWrapperPass>();
  67       AU.addPreserved<LoopInfoWrapperPass>();
  68
  69       // No loop canonicalization guarantees are broken by this pass.
  70       AU.addPreservedID(LoopSimplifyID);
  71     }
  72   };
  73 }
  74
  75 char BreakCriticalEdges::ID = 0;
  76 INITIALIZE_PASS(BreakCriticalEdges, "break-crit-edges",
  77                 "Break critical edges in CFG", false, false)
  78
  79 // Publicly exposed interface to pass...
  80 char &llvm::BreakCriticalEdgesID = BreakCriticalEdges::ID;
  81 FunctionPass *llvm::createBreakCriticalEdgesPass() {
  82   return new BreakCriticalEdges();
  83 }
  84
  85 PreservedAnalyses BreakCriticalEdgesPass::run(Function &F,
  86                                               FunctionAnalysisManager &AM) {
  87   auto *DT = AM.getCachedResult<DominatorTreeAnalysis>(F);
  88   auto *LI = AM.getCachedResult<LoopAnalysis>(F);
  89   unsigned N = SplitAllCriticalEdges(F, CriticalEdgeSplittingOptions(DT, LI));
  90   NumBroken += N;
  91   if (N == 0)
  92     return PreservedAnalyses::all();
  93   PreservedAnalyses PA;
  94   PA.preserve<DominatorTreeAnalysis>();
  95   PA.preserve<LoopAnalysis>();
  96   return PA;
  97 }
  98
  99 //===----------------------------------------------------------------------===//
 100 //    Implementation of the external critical edge manipulation functions
 101 //===----------------------------------------------------------------------===//
 102
 103 BasicBlock *llvm::SplitCriticalEdge(Instruction *TI, unsigned SuccNum,
 104                                     const CriticalEdgeSplittingOptions &Options,
 105                                     const Twine &BBName) {
 106   if (!isCriticalEdge(TI, SuccNum, Options.MergeIdenticalEdges))
 107     return nullptr;
 108
 109   return SplitKnownCriticalEdge(TI, SuccNum, Options, BBName);
 110 }
 111
 112 BasicBlock *
 113 llvm::SplitKnownCriticalEdge(Instruction *TI, unsigned SuccNum,
 114                              const CriticalEdgeSplittingOptions &Options,
 115                              const Twine &BBName) {
 116   assert(!isa<IndirectBrInst>(TI) &&
 117          "Cannot split critical edge from IndirectBrInst");
 118
 119   BasicBlock *TIBB = TI->getParent();
 120   BasicBlock *DestBB = TI->getSuccessor(SuccNum);
 121
 122   // Splitting the critical edge to a pad block is non-trivial. Don't do
 123   // it in this generic function.
 124   if (DestBB->isEHPad()) return nullptr;
 125
 126   if (Options.IgnoreUnreachableDests &&
 127       isa<UnreachableInst>(DestBB->getFirstNonPHIOrDbgOrLifetime()))
 128     return nullptr;
 129
 130   auto *LI = Options.LI;
 131   SmallVector<BasicBlock *, 4> LoopPreds;
 132   // Check if extra modifications will be required to preserve loop-simplify
 133   // form after splitting. If it would require splitting blocks with IndirectBr
 134   // or CallBr terminators, bail out if preserving loop-simplify form is
 135   // requested.
 136   if (LI) {
 137     if (Loop *TIL = LI->getLoopFor(TIBB)) {
 138
 139       // The only way that we can break LoopSimplify form by splitting a
 140       // critical edge is if after the split there exists some edge from TIL to
 141       // DestBB *and* the only edge into DestBB from outside of TIL is that of
 142       // NewBB. If the first isn't true, then LoopSimplify still holds, NewBB
 143       // is the new exit block and it has no non-loop predecessors. If the
 144       // second isn't true, then DestBB was not in LoopSimplify form prior to
 145       // the split as it had a non-loop predecessor. In both of these cases,
 146       // the predecessor must be directly in TIL, not in a subloop, or again
 147       // LoopSimplify doesn't hold.
 148       for (BasicBlock *P : predecessors(DestBB)) {
 149         if (P == TIBB)
 150           continue; // The new block is known.
 151         if (LI->getLoopFor(P) != TIL) {
 152           // No need to re-simplify, it wasn't to start with.
 153           LoopPreds.clear();
 154           break;
 155         }
 156         LoopPreds.push_back(P);
 157       }
 158       // Loop-simplify form can be preserved, if we can split all in-loop
 159       // predecessors.
 160       if (any_of(LoopPreds, [](BasicBlock *Pred) {
 161             const Instruction *T = Pred->getTerminator();
 162             if (const auto *CBR = dyn_cast<CallBrInst>(T))
 163               return CBR->getDefaultDest() != Pred;
 164             return isa<IndirectBrInst>(T);
 165           })) {
 166         if (Options.PreserveLoopSimplify)
 167           return nullptr;
 168         LoopPreds.clear();
 169       }
 170     }
 171   }
 172
 173   // Create a new basic block, linking it into the CFG.
 174   BasicBlock *NewBB = nullptr;
 175   if (BBName.str() != "")
 176     NewBB = BasicBlock::Create(TI->getContext(), BBName);
 177   else
 178     NewBB = BasicBlock::Create(TI->getContext(), TIBB->getName() + "." +
 179                                                      DestBB->getName() +
 180                                                      "_crit_edge");
 181   // Create our unconditional branch.
 182   BranchInst *NewBI = BranchInst::Create(DestBB, NewBB);
 183   NewBI->setDebugLoc(TI->getDebugLoc());
 184
 185   // Insert the block into the function... right after the block TI lives in.
 186   Function &F = *TIBB->getParent();
 187   Function::iterator FBBI = TIBB->getIterator();
 188   F.getBasicBlockList().insert(++FBBI, NewBB);
 189
 190   // Branch to the new block, breaking the edge.
 191   TI->setSuccessor(SuccNum, NewBB);
 192
 193   // If there are any PHI nodes in DestBB, we need to update them so that they
 194   // merge incoming values from NewBB instead of from TIBB.
 195   {
 196     unsigned BBIdx = 0;
 197     for (BasicBlock::iterator I = DestBB->begin(); isa<PHINode>(I); ++I) {
 198       // We no longer enter through TIBB, now we come in through NewBB.
 199       // Revector exactly one entry in the PHI node that used to come from
 200       // TIBB to come from NewBB.
 201       PHINode *PN = cast<PHINode>(I);
 202
 203       // Reuse the previous value of BBIdx if it lines up.  In cases where we
 204       // have multiple phi nodes with *lots* of predecessors, this is a speed
 205       // win because we don't have to scan the PHI looking for TIBB.  This
 206       // happens because the BB list of PHI nodes are usually in the same
 207       // order.
 208       if (PN->getIncomingBlock(BBIdx) != TIBB)
 209         BBIdx = PN->getBasicBlockIndex(TIBB);
 210       PN->setIncomingBlock(BBIdx, NewBB);
 211     }
 212   }
 213
 214   // If there are any other edges from TIBB to DestBB, update those to go
 215   // through the split block, making those edges non-critical as well (and
 216   // reducing the number of phi entries in the DestBB if relevant).
 217   if (Options.MergeIdenticalEdges) {
 218     for (unsigned i = SuccNum+1, e = TI->getNumSuccessors(); i != e; ++i) {
 219       if (TI->getSuccessor(i) != DestBB) continue;
 220
 221       // Remove an entry for TIBB from DestBB phi nodes.
 222       DestBB->removePredecessor(TIBB, Options.KeepOneInputPHIs);
 223
 224       // We found another edge to DestBB, go to NewBB instead.
 225       TI->setSuccessor(i, NewBB);
 226     }
 227   }
 228
 229   // If we have nothing to update, just return.
 230   auto *DT = Options.DT;
 231   auto *PDT = Options.PDT;
 232   auto *MSSAU = Options.MSSAU;
 233   if (MSSAU)
 234     MSSAU->wireOldPredecessorsToNewImmediatePredecessor(
 235         DestBB, NewBB, {TIBB}, Options.MergeIdenticalEdges);
 236
 237   if (!DT && !PDT && !LI)
 238     return NewBB;
 239
 240   if (DT || PDT) {
 241     // Update the DominatorTree.
 242     //       ---> NewBB -----\
 243     //      /                 V
 244     //  TIBB -------\\------> DestBB
 245     //
 246     // First, inform the DT about the new path from TIBB to DestBB via NewBB,
 247     // then delete the old edge from TIBB to DestBB. By doing this in that order
 248     // DestBB stays reachable in the DT the whole time and its subtree doesn't
 249     // get disconnected.
 250     SmallVector<DominatorTree::UpdateType, 3> Updates;
 251     Updates.push_back({DominatorTree::Insert, TIBB, NewBB});
 252     Updates.push_back({DominatorTree::Insert, NewBB, DestBB});
 253     if (!llvm::is_contained(successors(TIBB), DestBB))
 254       Updates.push_back({DominatorTree::Delete, TIBB, DestBB});
 255
 256     if (DT)
 257       DT->applyUpdates(Updates);
 258     if (PDT)
 259       PDT->applyUpdates(Updates);
 260   }
 261
 262   // Update LoopInfo if it is around.
 263   if (LI) {
 264     if (Loop *TIL = LI->getLoopFor(TIBB)) {
 265       // If one or the other blocks were not in a loop, the new block is not
 266       // either, and thus LI doesn't need to be updated.
 267       if (Loop *DestLoop = LI->getLoopFor(DestBB)) {
 268         if (TIL == DestLoop) {
 269           // Both in the same loop, the NewBB joins loop.
 270           DestLoop->addBasicBlockToLoop(NewBB, *LI);
 271         } else if (TIL->contains(DestLoop)) {
 272           // Edge from an outer loop to an inner loop.  Add to the outer loop.
 273           TIL->addBasicBlockToLoop(NewBB, *LI);
 274         } else if (DestLoop->contains(TIL)) {
 275           // Edge from an inner loop to an outer loop.  Add to the outer loop.
 276           DestLoop->addBasicBlockToLoop(NewBB, *LI);
 277         } else {
 278           // Edge from two loops with no containment relation.  Because these
 279           // are natural loops, we know that the destination block must be the
 280           // header of its loop (adding a branch into a loop elsewhere would
 281           // create an irreducible loop).
 282           assert(DestLoop->getHeader() == DestBB &&
 283                  "Should not create irreducible loops!");
 284           if (Loop *P = DestLoop->getParentLoop())
 285             P->addBasicBlockToLoop(NewBB, *LI);
 286         }
 287       }
 288
 289       // If TIBB is in a loop and DestBB is outside of that loop, we may need
 290       // to update LoopSimplify form and LCSSA form.
 291       if (!TIL->contains(DestBB)) {
 292         assert(!TIL->contains(NewBB) &&
 293                "Split point for loop exit is contained in loop!");
 294
 295         // Update LCSSA form in the newly created exit block.
 296         if (Options.PreserveLCSSA) {
 297           createPHIsForSplitLoopExit(TIBB, NewBB, DestBB);
 298         }
 299
 300         if (!LoopPreds.empty()) {
 301           assert(!DestBB->isEHPad() && "We don't split edges to EH pads!");
 302           BasicBlock *NewExitBB = SplitBlockPredecessors(
 303               DestBB, LoopPreds, "split", DT, LI, MSSAU, Options.PreserveLCSSA);
 304           if (Options.PreserveLCSSA)
 305             createPHIsForSplitLoopExit(LoopPreds, NewExitBB, DestBB);
 306         }
 307       }
 308     }
 309   }
 310
 311   return NewBB;
 312 }
 313
 314 // Return the unique indirectbr predecessor of a block. This may return null
 315 // even if such a predecessor exists, if it's not useful for splitting.
 316 // If a predecessor is found, OtherPreds will contain all other (non-indirectbr)
 317 // predecessors of BB.
 318 static BasicBlock *
 319 findIBRPredecessor(BasicBlock *BB, SmallVectorImpl<BasicBlock *> &OtherPreds) {
 320   // If the block doesn't have any PHIs, we don't care about it, since there's
 321   // no point in splitting it.
 322   PHINode *PN = dyn_cast<PHINode>(BB->begin());
 323   if (!PN)
 324     return nullptr;
 325
 326   // Verify we have exactly one IBR predecessor.
 327   // Conservatively bail out if one of the other predecessors is not a "regular"
 328   // terminator (that is, not a switch or a br).
 329   BasicBlock *IBB = nullptr;
 330   for (unsigned Pred = 0, E = PN->getNumIncomingValues(); Pred != E; ++Pred) {
 331     BasicBlock *PredBB = PN->getIncomingBlock(Pred);
 332     Instruction *PredTerm = PredBB->getTerminator();
 333     switch (PredTerm->getOpcode()) {
 334     case Instruction::IndirectBr:
 335       if (IBB)
 336         return nullptr;
 337       IBB = PredBB;
 338       break;
 339     case Instruction::Br:
 340     case Instruction::Switch:
 341       OtherPreds.push_back(PredBB);
 342       continue;
 343     default:
 344       return nullptr;
 345     }
 346   }
 347
 348   return IBB;
 349 }
 350
 351 bool llvm::SplitIndirectBrCriticalEdges(Function &F,
 352                                         BranchProbabilityInfo *BPI,
 353                                         BlockFrequencyInfo *BFI) {
 354   // Check whether the function has any indirectbrs, and collect which blocks
 355   // they may jump to. Since most functions don't have indirect branches,
 356   // this lowers the common case's overhead to O(Blocks) instead of O(Edges).
 357   SmallSetVector<BasicBlock *, 16> Targets;
 358   for (auto &BB : F) {
 359     auto *IBI = dyn_cast<IndirectBrInst>(BB.getTerminator());
 360     if (!IBI)
 361       continue;
 362
 363     for (unsigned Succ = 0, E = IBI->getNumSuccessors(); Succ != E; ++Succ)
 364       Targets.insert(IBI->getSuccessor(Succ));
 365   }
 366
 367   if (Targets.empty())
 368     return false;
 369
 370   bool ShouldUpdateAnalysis = BPI && BFI;
 371   bool Changed = false;
 372   for (BasicBlock *Target : Targets) {
 373     SmallVector<BasicBlock *, 16> OtherPreds;
 374     BasicBlock *IBRPred = findIBRPredecessor(Target, OtherPreds);
 375     // If we did not found an indirectbr, or the indirectbr is the only
 376     // incoming edge, this isn't the kind of edge we're looking for.
 377     if (!IBRPred || OtherPreds.empty())
 378       continue;
 379
 380     // Don't even think about ehpads/landingpads.
 381     Instruction *FirstNonPHI = Target->getFirstNonPHI();
 382     if (FirstNonPHI->isEHPad() || Target->isLandingPad())
 383       continue;
 384
 385     // Remember edge probabilities if needed.
 386     SmallVector<BranchProbability, 4> EdgeProbabilities;
 387     if (ShouldUpdateAnalysis) {
 388       EdgeProbabilities.reserve(Target->getTerminator()->getNumSuccessors());
 389       for (unsigned I = 0, E = Target->getTerminator()->getNumSuccessors();
 390            I < E; ++I)
 391         EdgeProbabilities.emplace_back(BPI->getEdgeProbability(Target, I));
 392       BPI->eraseBlock(Target);
 393     }
 394
 395     BasicBlock *BodyBlock = Target->splitBasicBlock(FirstNonPHI, ".split");
 396     if (ShouldUpdateAnalysis) {
 397       // Copy the BFI/BPI from Target to BodyBlock.
 398       BPI->setEdgeProbability(BodyBlock, EdgeProbabilities);
 399       BFI->setBlockFreq(BodyBlock, BFI->getBlockFreq(Target).getFrequency());
 400     }
 401     // It's possible Target was its own successor through an indirectbr.
 402     // In this case, the indirectbr now comes from BodyBlock.
 403     if (IBRPred == Target)
 404       IBRPred = BodyBlock;
 405
 406     // At this point Target only has PHIs, and BodyBlock has the rest of the
 407     // block's body. Create a copy of Target that will be used by the "direct"
 408     // preds.
 409     ValueToValueMapTy VMap;
 410     BasicBlock *DirectSucc = CloneBasicBlock(Target, VMap, ".clone", &F);
 411
 412     BlockFrequency BlockFreqForDirectSucc;
 413     for (BasicBlock *Pred : OtherPreds) {
 414       // If the target is a loop to itself, then the terminator of the split
 415       // block (BodyBlock) needs to be updated.
 416       BasicBlock *Src = Pred != Target ? Pred : BodyBlock;
 417       Src->getTerminator()->replaceUsesOfWith(Target, DirectSucc);
 418       if (ShouldUpdateAnalysis)
 419         BlockFreqForDirectSucc += BFI->getBlockFreq(Src) *
 420             BPI->getEdgeProbability(Src, DirectSucc);
 421     }
 422     if (ShouldUpdateAnalysis) {
 423       BFI->setBlockFreq(DirectSucc, BlockFreqForDirectSucc.getFrequency());
 424       BlockFrequency NewBlockFreqForTarget =
 425           BFI->getBlockFreq(Target) - BlockFreqForDirectSucc;
 426       BFI->setBlockFreq(Target, NewBlockFreqForTarget.getFrequency());
 427     }
 428
 429     // Ok, now fix up the PHIs. We know the two blocks only have PHIs, and that
 430     // they are clones, so the number of PHIs are the same.
 431     // (a) Remove the edge coming from IBRPred from the "Direct" PHI
 432     // (b) Leave that as the only edge in the "Indirect" PHI.
 433     // (c) Merge the two in the body block.
 434     BasicBlock::iterator Indirect = Target->begin(),
 435                          End = Target->getFirstNonPHI()->getIterator();
 436     BasicBlock::iterator Direct = DirectSucc->begin();
 437     BasicBlock::iterator MergeInsert = BodyBlock->getFirstInsertionPt();
 438
 439     assert(&*End == Target->getTerminator() &&
 440            "Block was expected to only contain PHIs");
 441
 442     while (Indirect != End) {
 443       PHINode *DirPHI = cast<PHINode>(Direct);
 444       PHINode *IndPHI = cast<PHINode>(Indirect);
 445
 446       // Now, clean up - the direct block shouldn't get the indirect value,
 447       // and vice versa.
 448       DirPHI->removeIncomingValue(IBRPred);
 449       Direct++;
 450
 451       // Advance the pointer here, to avoid invalidation issues when the old
 452       // PHI is erased.
 453       Indirect++;
 454
 455       PHINode *NewIndPHI = PHINode::Create(IndPHI->getType(), 1, "ind", IndPHI);
 456       NewIndPHI->addIncoming(IndPHI->getIncomingValueForBlock(IBRPred),
 457                              IBRPred);
 458
 459       // Create a PHI in the body block, to merge the direct and indirect
 460       // predecessors.
 461       PHINode *MergePHI =
 462           PHINode::Create(IndPHI->getType(), 2, "merge", &*MergeInsert);
 463       MergePHI->addIncoming(NewIndPHI, Target);
 464       MergePHI->addIncoming(DirPHI, DirectSucc);
 465
 466       IndPHI->replaceAllUsesWith(MergePHI);
 467       IndPHI->eraseFromParent();
 468     }
 469
 470     Changed = true;
 471   }
 472
 473   return Changed;
 474 }