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

   1 //===- BasicBlockUtils.cpp - BasicBlock Utilities --------------------------==//
   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 family of functions perform manipulations on basic blocks, and
  10 // instructions contained within basic blocks.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
  15 #include "llvm/ADT/ArrayRef.h"
  16 #include "llvm/ADT/SmallPtrSet.h"
  17 #include "llvm/ADT/SmallVector.h"
  18 #include "llvm/ADT/Twine.h"
  19 #include "llvm/Analysis/CFG.h"
  20 #include "llvm/Analysis/DomTreeUpdater.h"
  21 #include "llvm/Analysis/LoopInfo.h"
  22 #include "llvm/Analysis/MemoryDependenceAnalysis.h"
  23 #include "llvm/Analysis/MemorySSAUpdater.h"
  24 #include "llvm/Analysis/PostDominators.h"
  25 #include "llvm/IR/BasicBlock.h"
  26 #include "llvm/IR/CFG.h"
  27 #include "llvm/IR/Constants.h"
  28 #include "llvm/IR/DebugInfoMetadata.h"
  29 #include "llvm/IR/Dominators.h"
  30 #include "llvm/IR/Function.h"
  31 #include "llvm/IR/InstrTypes.h"
  32 #include "llvm/IR/Instruction.h"
  33 #include "llvm/IR/Instructions.h"
  34 #include "llvm/IR/IntrinsicInst.h"
  35 #include "llvm/IR/LLVMContext.h"
  36 #include "llvm/IR/Type.h"
  37 #include "llvm/IR/User.h"
  38 #include "llvm/IR/Value.h"
  39 #include "llvm/IR/ValueHandle.h"
  40 #include "llvm/Support/Casting.h"
  41 #include "llvm/Support/Debug.h"
  42 #include "llvm/Support/raw_ostream.h"
  43 #include "llvm/Transforms/Utils/Local.h"
  44 #include <cassert>
  45 #include <cstdint>
  46 #include <string>
  47 #include <utility>
  48 #include <vector>
  49
  50 using namespace llvm;
  51
  52 #define DEBUG_TYPE "basicblock-utils"
  53
  54 void llvm::DetatchDeadBlocks(
  55     ArrayRef<BasicBlock *> BBs,
  56     SmallVectorImpl<DominatorTree::UpdateType> *Updates,
  57     bool KeepOneInputPHIs) {
  58   for (auto *BB : BBs) {
  59     // Loop through all of our successors and make sure they know that one
  60     // of their predecessors is going away.
  61     SmallPtrSet<BasicBlock *, 4> UniqueSuccessors;
  62     for (BasicBlock *Succ : successors(BB)) {
  63       Succ->removePredecessor(BB, KeepOneInputPHIs);
  64       if (Updates && UniqueSuccessors.insert(Succ).second)
  65         Updates->push_back({DominatorTree::Delete, BB, Succ});
  66     }
  67
  68     // Zap all the instructions in the block.
  69     while (!BB->empty()) {
  70       Instruction &I = BB->back();
  71       // If this instruction is used, replace uses with an arbitrary value.
  72       // Because control flow can't get here, we don't care what we replace the
  73       // value with.  Note that since this block is unreachable, and all values
  74       // contained within it must dominate their uses, that all uses will
  75       // eventually be removed (they are themselves dead).
  76       if (!I.use_empty())
  77         I.replaceAllUsesWith(UndefValue::get(I.getType()));
  78       BB->getInstList().pop_back();
  79     }
  80     new UnreachableInst(BB->getContext(), BB);
  81     assert(BB->getInstList().size() == 1 &&
  82            isa<UnreachableInst>(BB->getTerminator()) &&
  83            "The successor list of BB isn't empty before "
  84            "applying corresponding DTU updates.");
  85   }
  86 }
  87
  88 void llvm::DeleteDeadBlock(BasicBlock *BB, DomTreeUpdater *DTU,
  89                            bool KeepOneInputPHIs) {
  90   DeleteDeadBlocks({BB}, DTU, KeepOneInputPHIs);
  91 }
  92
  93 void llvm::DeleteDeadBlocks(ArrayRef <BasicBlock *> BBs, DomTreeUpdater *DTU,
  94                             bool KeepOneInputPHIs) {
  95 #ifndef NDEBUG
  96   // Make sure that all predecessors of each dead block is also dead.
  97   SmallPtrSet<BasicBlock *, 4> Dead(BBs.begin(), BBs.end());
  98   assert(Dead.size() == BBs.size() && "Duplicating blocks?");
  99   for (auto *BB : Dead)
 100     for (BasicBlock *Pred : predecessors(BB))
 101       assert(Dead.count(Pred) && "All predecessors must be dead!");
 102 #endif
 103
 104   SmallVector<DominatorTree::UpdateType, 4> Updates;
 105   DetatchDeadBlocks(BBs, DTU ? &Updates : nullptr, KeepOneInputPHIs);
 106
 107   if (DTU)
 108     DTU->applyUpdatesPermissive(Updates);
 109
 110   for (BasicBlock *BB : BBs)
 111     if (DTU)
 112       DTU->deleteBB(BB);
 113     else
 114       BB->eraseFromParent();
 115 }
 116
 117 bool llvm::EliminateUnreachableBlocks(Function &F, DomTreeUpdater *DTU,
 118                                       bool KeepOneInputPHIs) {
 119   df_iterator_default_set<BasicBlock*> Reachable;
 120
 121   // Mark all reachable blocks.
 122   for (BasicBlock *BB : depth_first_ext(&F, Reachable))
 123     (void)BB/* Mark all reachable blocks */;
 124
 125   // Collect all dead blocks.
 126   std::vector<BasicBlock*> DeadBlocks;
 127   for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I)
 128     if (!Reachable.count(&*I)) {
 129       BasicBlock *BB = &*I;
 130       DeadBlocks.push_back(BB);
 131     }
 132
 133   // Delete the dead blocks.
 134   DeleteDeadBlocks(DeadBlocks, DTU, KeepOneInputPHIs);
 135
 136   return !DeadBlocks.empty();
 137 }
 138
 139 void llvm::FoldSingleEntryPHINodes(BasicBlock *BB,
 140                                    MemoryDependenceResults *MemDep) {
 141   if (!isa<PHINode>(BB->begin())) return;
 142
 143   while (PHINode *PN = dyn_cast<PHINode>(BB->begin())) {
 144     if (PN->getIncomingValue(0) != PN)
 145       PN->replaceAllUsesWith(PN->getIncomingValue(0));
 146     else
 147       PN->replaceAllUsesWith(UndefValue::get(PN->getType()));
 148
 149     if (MemDep)
 150       MemDep->removeInstruction(PN);  // Memdep updates AA itself.
 151
 152     PN->eraseFromParent();
 153   }
 154 }
 155
 156 bool llvm::DeleteDeadPHIs(BasicBlock *BB, const TargetLibraryInfo *TLI,
 157                           MemorySSAUpdater *MSSAU) {
 158   // Recursively deleting a PHI may cause multiple PHIs to be deleted
 159   // or RAUW'd undef, so use an array of WeakTrackingVH for the PHIs to delete.
 160   SmallVector<WeakTrackingVH, 8> PHIs;
 161   for (PHINode &PN : BB->phis())
 162     PHIs.push_back(&PN);
 163
 164   bool Changed = false;
 165   for (unsigned i = 0, e = PHIs.size(); i != e; ++i)
 166     if (PHINode *PN = dyn_cast_or_null<PHINode>(PHIs[i].operator Value*()))
 167       Changed |= RecursivelyDeleteDeadPHINode(PN, TLI, MSSAU);
 168
 169   return Changed;
 170 }
 171
 172 bool llvm::MergeBlockIntoPredecessor(BasicBlock *BB, DomTreeUpdater *DTU,
 173                                      LoopInfo *LI, MemorySSAUpdater *MSSAU,
 174                                      MemoryDependenceResults *MemDep,
 175                                      bool PredecessorWithTwoSuccessors) {
 176   if (BB->hasAddressTaken())
 177     return false;
 178
 179   // Can't merge if there are multiple predecessors, or no predecessors.
 180   BasicBlock *PredBB = BB->getUniquePredecessor();
 181   if (!PredBB) return false;
 182
 183   // Don't break self-loops.
 184   if (PredBB == BB) return false;
 185   // Don't break unwinding instructions.
 186   if (PredBB->getTerminator()->isExceptionalTerminator())
 187     return false;
 188
 189   // Can't merge if there are multiple distinct successors.
 190   if (!PredecessorWithTwoSuccessors && PredBB->getUniqueSuccessor() != BB)
 191     return false;
 192
 193   // Currently only allow PredBB to have two predecessors, one being BB.
 194   // Update BI to branch to BB's only successor instead of BB.
 195   BranchInst *PredBB_BI;
 196   BasicBlock *NewSucc = nullptr;
 197   unsigned FallThruPath;
 198   if (PredecessorWithTwoSuccessors) {
 199     if (!(PredBB_BI = dyn_cast<BranchInst>(PredBB->getTerminator())))
 200       return false;
 201     BranchInst *BB_JmpI = dyn_cast<BranchInst>(BB->getTerminator());
 202     if (!BB_JmpI || !BB_JmpI->isUnconditional())
 203       return false;
 204     NewSucc = BB_JmpI->getSuccessor(0);
 205     FallThruPath = PredBB_BI->getSuccessor(0) == BB ? 0 : 1;
 206   }
 207
 208   // Can't merge if there is PHI loop.
 209   for (PHINode &PN : BB->phis())
 210     for (Value *IncValue : PN.incoming_values())
 211       if (IncValue == &PN)
 212         return false;
 213
 214   LLVM_DEBUG(dbgs() << "Merging: " << BB->getName() << " into "
 215                     << PredBB->getName() << "\n");
 216
 217   // Begin by getting rid of unneeded PHIs.
 218   SmallVector<AssertingVH<Value>, 4> IncomingValues;
 219   if (isa<PHINode>(BB->front())) {
 220     for (PHINode &PN : BB->phis())
 221       if (!isa<PHINode>(PN.getIncomingValue(0)) ||
 222           cast<PHINode>(PN.getIncomingValue(0))->getParent() != BB)
 223         IncomingValues.push_back(PN.getIncomingValue(0));
 224     FoldSingleEntryPHINodes(BB, MemDep);
 225   }
 226
 227   // DTU update: Collect all the edges that exit BB.
 228   // These dominator edges will be redirected from Pred.
 229   std::vector<DominatorTree::UpdateType> Updates;
 230   if (DTU) {
 231     Updates.reserve(1 + (2 * succ_size(BB)));
 232     // Add insert edges first. Experimentally, for the particular case of two
 233     // blocks that can be merged, with a single successor and single predecessor
 234     // respectively, it is beneficial to have all insert updates first. Deleting
 235     // edges first may lead to unreachable blocks, followed by inserting edges
 236     // making the blocks reachable again. Such DT updates lead to high compile
 237     // times. We add inserts before deletes here to reduce compile time.
 238     for (auto I = succ_begin(BB), E = succ_end(BB); I != E; ++I)
 239       // This successor of BB may already have PredBB as a predecessor.
 240       if (llvm::find(successors(PredBB), *I) == succ_end(PredBB))
 241         Updates.push_back({DominatorTree::Insert, PredBB, *I});
 242     for (auto I = succ_begin(BB), E = succ_end(BB); I != E; ++I)
 243       Updates.push_back({DominatorTree::Delete, BB, *I});
 244     Updates.push_back({DominatorTree::Delete, PredBB, BB});
 245   }
 246
 247   Instruction *PTI = PredBB->getTerminator();
 248   Instruction *STI = BB->getTerminator();
 249   Instruction *Start = &*BB->begin();
 250   // If there's nothing to move, mark the starting instruction as the last
 251   // instruction in the block. Terminator instruction is handled separately.
 252   if (Start == STI)
 253     Start = PTI;
 254
 255   // Move all definitions in the successor to the predecessor...
 256   PredBB->getInstList().splice(PTI->getIterator(), BB->getInstList(),
 257                                BB->begin(), STI->getIterator());
 258
 259   if (MSSAU)
 260     MSSAU->moveAllAfterMergeBlocks(BB, PredBB, Start);
 261
 262   // Make all PHI nodes that referred to BB now refer to Pred as their
 263   // source...
 264   BB->replaceAllUsesWith(PredBB);
 265
 266   if (PredecessorWithTwoSuccessors) {
 267     // Delete the unconditional branch from BB.
 268     BB->getInstList().pop_back();
 269
 270     // Update branch in the predecessor.
 271     PredBB_BI->setSuccessor(FallThruPath, NewSucc);
 272   } else {
 273     // Delete the unconditional branch from the predecessor.
 274     PredBB->getInstList().pop_back();
 275
 276     // Move terminator instruction.
 277     PredBB->getInstList().splice(PredBB->end(), BB->getInstList());
 278
 279     // Terminator may be a memory accessing instruction too.
 280     if (MSSAU)
 281       if (MemoryUseOrDef *MUD = cast_or_null<MemoryUseOrDef>(
 282               MSSAU->getMemorySSA()->getMemoryAccess(PredBB->getTerminator())))
 283         MSSAU->moveToPlace(MUD, PredBB, MemorySSA::End);
 284   }
 285   // Add unreachable to now empty BB.
 286   new UnreachableInst(BB->getContext(), BB);
 287
 288   // Eliminate duplicate/redundant dbg.values. This seems to be a good place to
 289   // do that since we might end up with redundant dbg.values describing the
 290   // entry PHI node post-splice.
 291   RemoveRedundantDbgInstrs(PredBB);
 292
 293   // Inherit predecessors name if it exists.
 294   if (!PredBB->hasName())
 295     PredBB->takeName(BB);
 296
 297   if (LI)
 298     LI->removeBlock(BB);
 299
 300   if (MemDep)
 301     MemDep->invalidateCachedPredecessors();
 302
 303   // Finally, erase the old block and update dominator info.
 304   if (DTU) {
 305     assert(BB->getInstList().size() == 1 &&
 306            isa<UnreachableInst>(BB->getTerminator()) &&
 307            "The successor list of BB isn't empty before "
 308            "applying corresponding DTU updates.");
 309     DTU->applyUpdatesPermissive(Updates);
 310     DTU->deleteBB(BB);
 311   } else {
 312     BB->eraseFromParent(); // Nuke BB if DTU is nullptr.
 313   }
 314
 315   return true;
 316 }
 317
 318 bool llvm::MergeBlockSuccessorsIntoGivenBlocks(
 319     SmallPtrSetImpl<BasicBlock *> &MergeBlocks, Loop *L, DomTreeUpdater *DTU,
 320     LoopInfo *LI) {
 321   assert(!MergeBlocks.empty() && "MergeBlocks should not be empty");
 322
 323   bool BlocksHaveBeenMerged = false;
 324   while (!MergeBlocks.empty()) {
 325     BasicBlock *BB = *MergeBlocks.begin();
 326     BasicBlock *Dest = BB->getSingleSuccessor();
 327     if (Dest && (!L || L->contains(Dest))) {
 328       BasicBlock *Fold = Dest->getUniquePredecessor();
 329       (void)Fold;
 330       if (MergeBlockIntoPredecessor(Dest, DTU, LI)) {
 331         assert(Fold == BB &&
 332                "Expecting BB to be unique predecessor of the Dest block");
 333         MergeBlocks.erase(Dest);
 334         BlocksHaveBeenMerged = true;
 335       } else
 336         MergeBlocks.erase(BB);
 337     } else
 338       MergeBlocks.erase(BB);
 339   }
 340   return BlocksHaveBeenMerged;
 341 }
 342
 343 /// Remove redundant instructions within sequences of consecutive dbg.value
 344 /// instructions. This is done using a backward scan to keep the last dbg.value
 345 /// describing a specific variable/fragment.
 346 ///
 347 /// BackwardScan strategy:
 348 /// ----------------------
 349 /// Given a sequence of consecutive DbgValueInst like this
 350 ///
 351 ///   dbg.value ..., "x", FragmentX1  (*)
 352 ///   dbg.value ..., "y", FragmentY1
 353 ///   dbg.value ..., "x", FragmentX2
 354 ///   dbg.value ..., "x", FragmentX1  (**)
 355 ///
 356 /// then the instruction marked with (*) can be removed (it is guaranteed to be
 357 /// obsoleted by the instruction marked with (**) as the latter instruction is
 358 /// describing the same variable using the same fragment info).
 359 ///
 360 /// Possible improvements:
 361 /// - Check fully overlapping fragments and not only identical fragments.
 362 /// - Support dbg.addr, dbg.declare. dbg.label, and possibly other meta
 363 ///   instructions being part of the sequence of consecutive instructions.
 364 static bool removeRedundantDbgInstrsUsingBackwardScan(BasicBlock *BB) {
 365   SmallVector<DbgValueInst *, 8> ToBeRemoved;
 366   SmallDenseSet<DebugVariable> VariableSet;
 367   for (auto &I : reverse(*BB)) {
 368     if (DbgValueInst *DVI = dyn_cast<DbgValueInst>(&I)) {
 369       DebugVariable Key(DVI->getVariable(),
 370                         DVI->getExpression(),
 371                         DVI->getDebugLoc()->getInlinedAt());
 372       auto R = VariableSet.insert(Key);
 373       // If the same variable fragment is described more than once it is enough
 374       // to keep the last one (i.e. the first found since we for reverse
 375       // iteration).
 376       if (!R.second)
 377         ToBeRemoved.push_back(DVI);
 378       continue;
 379     }
 380     // Sequence with consecutive dbg.value instrs ended. Clear the map to
 381     // restart identifying redundant instructions if case we find another
 382     // dbg.value sequence.
 383     VariableSet.clear();
 384   }
 385
 386   for (auto &Instr : ToBeRemoved)
 387     Instr->eraseFromParent();
 388
 389   return !ToBeRemoved.empty();
 390 }
 391
 392 /// Remove redundant dbg.value instructions using a forward scan. This can
 393 /// remove a dbg.value instruction that is redundant due to indicating that a
 394 /// variable has the same value as already being indicated by an earlier
 395 /// dbg.value.
 396 ///
 397 /// ForwardScan strategy:
 398 /// ---------------------
 399 /// Given two identical dbg.value instructions, separated by a block of
 400 /// instructions that isn't describing the same variable, like this
 401 ///
 402 ///   dbg.value X1, "x", FragmentX1  (**)
 403 ///   <block of instructions, none being "dbg.value ..., "x", ...">
 404 ///   dbg.value X1, "x", FragmentX1  (*)
 405 ///
 406 /// then the instruction marked with (*) can be removed. Variable "x" is already
 407 /// described as being mapped to the SSA value X1.
 408 ///
 409 /// Possible improvements:
 410 /// - Keep track of non-overlapping fragments.
 411 static bool removeRedundantDbgInstrsUsingForwardScan(BasicBlock *BB) {
 412   SmallVector<DbgValueInst *, 8> ToBeRemoved;
 413   DenseMap<DebugVariable, std::pair<Value *, DIExpression *> > VariableMap;
 414   for (auto &I : *BB) {
 415     if (DbgValueInst *DVI = dyn_cast<DbgValueInst>(&I)) {
 416       DebugVariable Key(DVI->getVariable(),
 417                         NoneType(),
 418                         DVI->getDebugLoc()->getInlinedAt());
 419       auto VMI = VariableMap.find(Key);
 420       // Update the map if we found a new value/expression describing the
 421       // variable, or if the variable wasn't mapped already.
 422       if (VMI == VariableMap.end() ||
 423           VMI->second.first != DVI->getValue() ||
 424           VMI->second.second != DVI->getExpression()) {
 425         VariableMap[Key] = { DVI->getValue(), DVI->getExpression() };
 426         continue;
 427       }
 428       // Found an identical mapping. Remember the instruction for later removal.
 429       ToBeRemoved.push_back(DVI);
 430     }
 431   }
 432
 433   for (auto &Instr : ToBeRemoved)
 434     Instr->eraseFromParent();
 435
 436   return !ToBeRemoved.empty();
 437 }
 438
 439 bool llvm::RemoveRedundantDbgInstrs(BasicBlock *BB) {
 440   bool MadeChanges = false;
 441   // By using the "backward scan" strategy before the "forward scan" strategy we
 442   // can remove both dbg.value (2) and (3) in a situation like this:
 443   //
 444   //   (1) dbg.value V1, "x", DIExpression()
 445   //       ...
 446   //   (2) dbg.value V2, "x", DIExpression()
 447   //   (3) dbg.value V1, "x", DIExpression()
 448   //
 449   // The backward scan will remove (2), it is made obsolete by (3). After
 450   // getting (2) out of the way, the foward scan will remove (3) since "x"
 451   // already is described as having the value V1 at (1).
 452   MadeChanges |= removeRedundantDbgInstrsUsingBackwardScan(BB);
 453   MadeChanges |= removeRedundantDbgInstrsUsingForwardScan(BB);
 454
 455   if (MadeChanges)
 456     LLVM_DEBUG(dbgs() << "Removed redundant dbg instrs from: "
 457                       << BB->getName() << "\n");
 458   return MadeChanges;
 459 }
 460
 461 void llvm::ReplaceInstWithValue(BasicBlock::InstListType &BIL,
 462                                 BasicBlock::iterator &BI, Value *V) {
 463   Instruction &I = *BI;
 464   // Replaces all of the uses of the instruction with uses of the value
 465   I.replaceAllUsesWith(V);
 466
 467   // Make sure to propagate a name if there is one already.
 468   if (I.hasName() && !V->hasName())
 469     V->takeName(&I);
 470
 471   // Delete the unnecessary instruction now...
 472   BI = BIL.erase(BI);
 473 }
 474
 475 void llvm::ReplaceInstWithInst(BasicBlock::InstListType &BIL,
 476                                BasicBlock::iterator &BI, Instruction *I) {
 477   assert(I->getParent() == nullptr &&
 478          "ReplaceInstWithInst: Instruction already inserted into basic block!");
 479
 480   // Copy debug location to newly added instruction, if it wasn't already set
 481   // by the caller.
 482   if (!I->getDebugLoc())
 483     I->setDebugLoc(BI->getDebugLoc());
 484
 485   // Insert the new instruction into the basic block...
 486   BasicBlock::iterator New = BIL.insert(BI, I);
 487
 488   // Replace all uses of the old instruction, and delete it.
 489   ReplaceInstWithValue(BIL, BI, I);
 490
 491   // Move BI back to point to the newly inserted instruction
 492   BI = New;
 493 }
 494
 495 void llvm::ReplaceInstWithInst(Instruction *From, Instruction *To) {
 496   BasicBlock::iterator BI(From);
 497   ReplaceInstWithInst(From->getParent()->getInstList(), BI, To);
 498 }
 499
 500 BasicBlock *llvm::SplitEdge(BasicBlock *BB, BasicBlock *Succ, DominatorTree *DT,
 501                             LoopInfo *LI, MemorySSAUpdater *MSSAU) {
 502   unsigned SuccNum = GetSuccessorNumber(BB, Succ);
 503
 504   // If this is a critical edge, let SplitCriticalEdge do it.
 505   Instruction *LatchTerm = BB->getTerminator();
 506   if (SplitCriticalEdge(
 507           LatchTerm, SuccNum,
 508           CriticalEdgeSplittingOptions(DT, LI, MSSAU).setPreserveLCSSA()))
 509     return LatchTerm->getSuccessor(SuccNum);
 510
 511   // If the edge isn't critical, then BB has a single successor or Succ has a
 512   // single pred.  Split the block.
 513   if (BasicBlock *SP = Succ->getSinglePredecessor()) {
 514     // If the successor only has a single pred, split the top of the successor
 515     // block.
 516     assert(SP == BB && "CFG broken");
 517     SP = nullptr;
 518     return SplitBlock(Succ, &Succ->front(), DT, LI, MSSAU);
 519   }
 520
 521   // Otherwise, if BB has a single successor, split it at the bottom of the
 522   // block.
 523   assert(BB->getTerminator()->getNumSuccessors() == 1 &&
 524          "Should have a single succ!");
 525   return SplitBlock(BB, BB->getTerminator(), DT, LI, MSSAU);
 526 }
 527
 528 unsigned
 529 llvm::SplitAllCriticalEdges(Function &F,
 530                             const CriticalEdgeSplittingOptions &Options) {
 531   unsigned NumBroken = 0;
 532   for (BasicBlock &BB : F) {
 533     Instruction *TI = BB.getTerminator();
 534     if (TI->getNumSuccessors() > 1 && !isa<IndirectBrInst>(TI) &&
 535         !isa<CallBrInst>(TI))
 536       for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i)
 537         if (SplitCriticalEdge(TI, i, Options))
 538           ++NumBroken;
 539   }
 540   return NumBroken;
 541 }
 542
 543 BasicBlock *llvm::SplitBlock(BasicBlock *Old, Instruction *SplitPt,
 544                              DominatorTree *DT, LoopInfo *LI,
 545                              MemorySSAUpdater *MSSAU, const Twine &BBName) {
 546   BasicBlock::iterator SplitIt = SplitPt->getIterator();
 547   while (isa<PHINode>(SplitIt) || SplitIt->isEHPad())
 548     ++SplitIt;
 549   std::string Name = BBName.str();
 550   BasicBlock *New = Old->splitBasicBlock(
 551       SplitIt, Name.empty() ? Old->getName() + ".split" : Name);
 552
 553   // The new block lives in whichever loop the old one did. This preserves
 554   // LCSSA as well, because we force the split point to be after any PHI nodes.
 555   if (LI)
 556     if (Loop *L = LI->getLoopFor(Old))
 557       L->addBasicBlockToLoop(New, *LI);
 558
 559   if (DT)
 560     // Old dominates New. New node dominates all other nodes dominated by Old.
 561     if (DomTreeNode *OldNode = DT->getNode(Old)) {
 562       std::vector<DomTreeNode *> Children(OldNode->begin(), OldNode->end());
 563
 564       DomTreeNode *NewNode = DT->addNewBlock(New, Old);
 565       for (DomTreeNode *I : Children)
 566         DT->changeImmediateDominator(I, NewNode);
 567     }
 568
 569   // Move MemoryAccesses still tracked in Old, but part of New now.
 570   // Update accesses in successor blocks accordingly.
 571   if (MSSAU)
 572     MSSAU->moveAllAfterSpliceBlocks(Old, New, &*(New->begin()));
 573
 574   return New;
 575 }
 576
 577 /// Update DominatorTree, LoopInfo, and LCCSA analysis information.
 578 static void UpdateAnalysisInformation(BasicBlock *OldBB, BasicBlock *NewBB,
 579                                       ArrayRef<BasicBlock *> Preds,
 580                                       DominatorTree *DT, LoopInfo *LI,
 581                                       MemorySSAUpdater *MSSAU,
 582                                       bool PreserveLCSSA, bool &HasLoopExit) {
 583   // Update dominator tree if available.
 584   if (DT) {
 585     if (OldBB == DT->getRootNode()->getBlock()) {
 586       assert(NewBB == &NewBB->getParent()->getEntryBlock());
 587       DT->setNewRoot(NewBB);
 588     } else {
 589       // Split block expects NewBB to have a non-empty set of predecessors.
 590       DT->splitBlock(NewBB);
 591     }
 592   }
 593
 594   // Update MemoryPhis after split if MemorySSA is available
 595   if (MSSAU)
 596     MSSAU->wireOldPredecessorsToNewImmediatePredecessor(OldBB, NewBB, Preds);
 597
 598   // The rest of the logic is only relevant for updating the loop structures.
 599   if (!LI)
 600     return;
 601
 602   assert(DT && "DT should be available to update LoopInfo!");
 603   Loop *L = LI->getLoopFor(OldBB);
 604
 605   // If we need to preserve loop analyses, collect some information about how
 606   // this split will affect loops.
 607   bool IsLoopEntry = !!L;
 608   bool SplitMakesNewLoopHeader = false;
 609   for (BasicBlock *Pred : Preds) {
 610     // Preds that are not reachable from entry should not be used to identify if
 611     // OldBB is a loop entry or if SplitMakesNewLoopHeader. Unreachable blocks
 612     // are not within any loops, so we incorrectly mark SplitMakesNewLoopHeader
 613     // as true and make the NewBB the header of some loop. This breaks LI.
 614     if (!DT->isReachableFromEntry(Pred))
 615       continue;
 616     // If we need to preserve LCSSA, determine if any of the preds is a loop
 617     // exit.
 618     if (PreserveLCSSA)
 619       if (Loop *PL = LI->getLoopFor(Pred))
 620         if (!PL->contains(OldBB))
 621           HasLoopExit = true;
 622
 623     // If we need to preserve LoopInfo, note whether any of the preds crosses
 624     // an interesting loop boundary.
 625     if (!L)
 626       continue;
 627     if (L->contains(Pred))
 628       IsLoopEntry = false;
 629     else
 630       SplitMakesNewLoopHeader = true;
 631   }
 632
 633   // Unless we have a loop for OldBB, nothing else to do here.
 634   if (!L)
 635     return;
 636
 637   if (IsLoopEntry) {
 638     // Add the new block to the nearest enclosing loop (and not an adjacent
 639     // loop). To find this, examine each of the predecessors and determine which
 640     // loops enclose them, and select the most-nested loop which contains the
 641     // loop containing the block being split.
 642     Loop *InnermostPredLoop = nullptr;
 643     for (BasicBlock *Pred : Preds) {
 644       if (Loop *PredLoop = LI->getLoopFor(Pred)) {
 645         // Seek a loop which actually contains the block being split (to avoid
 646         // adjacent loops).
 647         while (PredLoop && !PredLoop->contains(OldBB))
 648           PredLoop = PredLoop->getParentLoop();
 649
 650         // Select the most-nested of these loops which contains the block.
 651         if (PredLoop && PredLoop->contains(OldBB) &&
 652             (!InnermostPredLoop ||
 653              InnermostPredLoop->getLoopDepth() < PredLoop->getLoopDepth()))
 654           InnermostPredLoop = PredLoop;
 655       }
 656     }
 657
 658     if (InnermostPredLoop)
 659       InnermostPredLoop->addBasicBlockToLoop(NewBB, *LI);
 660   } else {
 661     L->addBasicBlockToLoop(NewBB, *LI);
 662     if (SplitMakesNewLoopHeader)
 663       L->moveToHeader(NewBB);
 664   }
 665 }
 666
 667 /// Update the PHI nodes in OrigBB to include the values coming from NewBB.
 668 /// This also updates AliasAnalysis, if available.
 669 static void UpdatePHINodes(BasicBlock *OrigBB, BasicBlock *NewBB,
 670                            ArrayRef<BasicBlock *> Preds, BranchInst *BI,
 671                            bool HasLoopExit) {
 672   // Otherwise, create a new PHI node in NewBB for each PHI node in OrigBB.
 673   SmallPtrSet<BasicBlock *, 16> PredSet(Preds.begin(), Preds.end());
 674   for (BasicBlock::iterator I = OrigBB->begin(); isa<PHINode>(I); ) {
 675     PHINode *PN = cast<PHINode>(I++);
 676
 677     // Check to see if all of the values coming in are the same.  If so, we
 678     // don't need to create a new PHI node, unless it's needed for LCSSA.
 679     Value *InVal = nullptr;
 680     if (!HasLoopExit) {
 681       InVal = PN->getIncomingValueForBlock(Preds[0]);
 682       for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
 683         if (!PredSet.count(PN->getIncomingBlock(i)))
 684           continue;
 685         if (!InVal)
 686           InVal = PN->getIncomingValue(i);
 687         else if (InVal != PN->getIncomingValue(i)) {
 688           InVal = nullptr;
 689           break;
 690         }
 691       }
 692     }
 693
 694     if (InVal) {
 695       // If all incoming values for the new PHI would be the same, just don't
 696       // make a new PHI.  Instead, just remove the incoming values from the old
 697       // PHI.
 698
 699       // NOTE! This loop walks backwards for a reason! First off, this minimizes
 700       // the cost of removal if we end up removing a large number of values, and
 701       // second off, this ensures that the indices for the incoming values
 702       // aren't invalidated when we remove one.
 703       for (int64_t i = PN->getNumIncomingValues() - 1; i >= 0; --i)
 704         if (PredSet.count(PN->getIncomingBlock(i)))
 705           PN->removeIncomingValue(i, false);
 706
 707       // Add an incoming value to the PHI node in the loop for the preheader
 708       // edge.
 709       PN->addIncoming(InVal, NewBB);
 710       continue;
 711     }
 712
 713     // If the values coming into the block are not the same, we need a new
 714     // PHI.
 715     // Create the new PHI node, insert it into NewBB at the end of the block
 716     PHINode *NewPHI =
 717         PHINode::Create(PN->getType(), Preds.size(), PN->getName() + ".ph", BI);
 718
 719     // NOTE! This loop walks backwards for a reason! First off, this minimizes
 720     // the cost of removal if we end up removing a large number of values, and
 721     // second off, this ensures that the indices for the incoming values aren't
 722     // invalidated when we remove one.
 723     for (int64_t i = PN->getNumIncomingValues() - 1; i >= 0; --i) {
 724       BasicBlock *IncomingBB = PN->getIncomingBlock(i);
 725       if (PredSet.count(IncomingBB)) {
 726         Value *V = PN->removeIncomingValue(i, false);
 727         NewPHI->addIncoming(V, IncomingBB);
 728       }
 729     }
 730
 731     PN->addIncoming(NewPHI, NewBB);
 732   }
 733 }
 734
 735 BasicBlock *llvm::SplitBlockPredecessors(BasicBlock *BB,
 736                                          ArrayRef<BasicBlock *> Preds,
 737                                          const char *Suffix, DominatorTree *DT,
 738                                          LoopInfo *LI, MemorySSAUpdater *MSSAU,
 739                                          bool PreserveLCSSA) {
 740   // Do not attempt to split that which cannot be split.
 741   if (!BB->canSplitPredecessors())
 742     return nullptr;
 743
 744   // For the landingpads we need to act a bit differently.
 745   // Delegate this work to the SplitLandingPadPredecessors.
 746   if (BB->isLandingPad()) {
 747     SmallVector<BasicBlock*, 2> NewBBs;
 748     std::string NewName = std::string(Suffix) + ".split-lp";
 749
 750     SplitLandingPadPredecessors(BB, Preds, Suffix, NewName.c_str(), NewBBs, DT,
 751                                 LI, MSSAU, PreserveLCSSA);
 752     return NewBBs[0];
 753   }
 754
 755   // Create new basic block, insert right before the original block.
 756   BasicBlock *NewBB = BasicBlock::Create(
 757       BB->getContext(), BB->getName() + Suffix, BB->getParent(), BB);
 758
 759   // The new block unconditionally branches to the old block.
 760   BranchInst *BI = BranchInst::Create(BB, NewBB);
 761   // Splitting the predecessors of a loop header creates a preheader block.
 762   if (LI && LI->isLoopHeader(BB))
 763     // Using the loop start line number prevents debuggers stepping into the
 764     // loop body for this instruction.
 765     BI->setDebugLoc(LI->getLoopFor(BB)->getStartLoc());
 766   else
 767     BI->setDebugLoc(BB->getFirstNonPHIOrDbg()->getDebugLoc());
 768
 769   // Move the edges from Preds to point to NewBB instead of BB.
 770   for (unsigned i = 0, e = Preds.size(); i != e; ++i) {
 771     // This is slightly more strict than necessary; the minimum requirement
 772     // is that there be no more than one indirectbr branching to BB. And
 773     // all BlockAddress uses would need to be updated.
 774     assert(!isa<IndirectBrInst>(Preds[i]->getTerminator()) &&
 775            "Cannot split an edge from an IndirectBrInst");
 776     assert(!isa<CallBrInst>(Preds[i]->getTerminator()) &&
 777            "Cannot split an edge from a CallBrInst");
 778     Preds[i]->getTerminator()->replaceUsesOfWith(BB, NewBB);
 779   }
 780
 781   // Insert a new PHI node into NewBB for every PHI node in BB and that new PHI
 782   // node becomes an incoming value for BB's phi node.  However, if the Preds
 783   // list is empty, we need to insert dummy entries into the PHI nodes in BB to
 784   // account for the newly created predecessor.
 785   if (Preds.empty()) {
 786     // Insert dummy values as the incoming value.
 787     for (BasicBlock::iterator I = BB->begin(); isa<PHINode>(I); ++I)
 788       cast<PHINode>(I)->addIncoming(UndefValue::get(I->getType()), NewBB);
 789   }
 790
 791   // Update DominatorTree, LoopInfo, and LCCSA analysis information.
 792   bool HasLoopExit = false;
 793   UpdateAnalysisInformation(BB, NewBB, Preds, DT, LI, MSSAU, PreserveLCSSA,
 794                             HasLoopExit);
 795
 796   if (!Preds.empty()) {
 797     // Update the PHI nodes in BB with the values coming from NewBB.
 798     UpdatePHINodes(BB, NewBB, Preds, BI, HasLoopExit);
 799   }
 800
 801   return NewBB;
 802 }
 803
 804 void llvm::SplitLandingPadPredecessors(BasicBlock *OrigBB,
 805                                        ArrayRef<BasicBlock *> Preds,
 806                                        const char *Suffix1, const char *Suffix2,
 807                                        SmallVectorImpl<BasicBlock *> &NewBBs,
 808                                        DominatorTree *DT, LoopInfo *LI,
 809                                        MemorySSAUpdater *MSSAU,
 810                                        bool PreserveLCSSA) {
 811   assert(OrigBB->isLandingPad() && "Trying to split a non-landing pad!");
 812
 813   // Create a new basic block for OrigBB's predecessors listed in Preds. Insert
 814   // it right before the original block.
 815   BasicBlock *NewBB1 = BasicBlock::Create(OrigBB->getContext(),
 816                                           OrigBB->getName() + Suffix1,
 817                                           OrigBB->getParent(), OrigBB);
 818   NewBBs.push_back(NewBB1);
 819
 820   // The new block unconditionally branches to the old block.
 821   BranchInst *BI1 = BranchInst::Create(OrigBB, NewBB1);
 822   BI1->setDebugLoc(OrigBB->getFirstNonPHI()->getDebugLoc());
 823
 824   // Move the edges from Preds to point to NewBB1 instead of OrigBB.
 825   for (unsigned i = 0, e = Preds.size(); i != e; ++i) {
 826     // This is slightly more strict than necessary; the minimum requirement
 827     // is that there be no more than one indirectbr branching to BB. And
 828     // all BlockAddress uses would need to be updated.
 829     assert(!isa<IndirectBrInst>(Preds[i]->getTerminator()) &&
 830            "Cannot split an edge from an IndirectBrInst");
 831     Preds[i]->getTerminator()->replaceUsesOfWith(OrigBB, NewBB1);
 832   }
 833
 834   bool HasLoopExit = false;
 835   UpdateAnalysisInformation(OrigBB, NewBB1, Preds, DT, LI, MSSAU, PreserveLCSSA,
 836                             HasLoopExit);
 837
 838   // Update the PHI nodes in OrigBB with the values coming from NewBB1.
 839   UpdatePHINodes(OrigBB, NewBB1, Preds, BI1, HasLoopExit);
 840
 841   // Move the remaining edges from OrigBB to point to NewBB2.
 842   SmallVector<BasicBlock*, 8> NewBB2Preds;
 843   for (pred_iterator i = pred_begin(OrigBB), e = pred_end(OrigBB);
 844        i != e; ) {
 845     BasicBlock *Pred = *i++;
 846     if (Pred == NewBB1) continue;
 847     assert(!isa<IndirectBrInst>(Pred->getTerminator()) &&
 848            "Cannot split an edge from an IndirectBrInst");
 849     NewBB2Preds.push_back(Pred);
 850     e = pred_end(OrigBB);
 851   }
 852
 853   BasicBlock *NewBB2 = nullptr;
 854   if (!NewBB2Preds.empty()) {
 855     // Create another basic block for the rest of OrigBB's predecessors.
 856     NewBB2 = BasicBlock::Create(OrigBB->getContext(),
 857                                 OrigBB->getName() + Suffix2,
 858                                 OrigBB->getParent(), OrigBB);
 859     NewBBs.push_back(NewBB2);
 860
 861     // The new block unconditionally branches to the old block.
 862     BranchInst *BI2 = BranchInst::Create(OrigBB, NewBB2);
 863     BI2->setDebugLoc(OrigBB->getFirstNonPHI()->getDebugLoc());
 864
 865     // Move the remaining edges from OrigBB to point to NewBB2.
 866     for (BasicBlock *NewBB2Pred : NewBB2Preds)
 867       NewBB2Pred->getTerminator()->replaceUsesOfWith(OrigBB, NewBB2);
 868
 869     // Update DominatorTree, LoopInfo, and LCCSA analysis information.
 870     HasLoopExit = false;
 871     UpdateAnalysisInformation(OrigBB, NewBB2, NewBB2Preds, DT, LI, MSSAU,
 872                               PreserveLCSSA, HasLoopExit);
 873
 874     // Update the PHI nodes in OrigBB with the values coming from NewBB2.
 875     UpdatePHINodes(OrigBB, NewBB2, NewBB2Preds, BI2, HasLoopExit);
 876   }
 877
 878   LandingPadInst *LPad = OrigBB->getLandingPadInst();
 879   Instruction *Clone1 = LPad->clone();
 880   Clone1->setName(Twine("lpad") + Suffix1);
 881   NewBB1->getInstList().insert(NewBB1->getFirstInsertionPt(), Clone1);
 882
 883   if (NewBB2) {
 884     Instruction *Clone2 = LPad->clone();
 885     Clone2->setName(Twine("lpad") + Suffix2);
 886     NewBB2->getInstList().insert(NewBB2->getFirstInsertionPt(), Clone2);
 887
 888     // Create a PHI node for the two cloned landingpad instructions only
 889     // if the original landingpad instruction has some uses.
 890     if (!LPad->use_empty()) {
 891       assert(!LPad->getType()->isTokenTy() &&
 892              "Split cannot be applied if LPad is token type. Otherwise an "
 893              "invalid PHINode of token type would be created.");
 894       PHINode *PN = PHINode::Create(LPad->getType(), 2, "lpad.phi", LPad);
 895       PN->addIncoming(Clone1, NewBB1);
 896       PN->addIncoming(Clone2, NewBB2);
 897       LPad->replaceAllUsesWith(PN);
 898     }
 899     LPad->eraseFromParent();
 900   } else {
 901     // There is no second clone. Just replace the landing pad with the first
 902     // clone.
 903     LPad->replaceAllUsesWith(Clone1);
 904     LPad->eraseFromParent();
 905   }
 906 }
 907
 908 ReturnInst *llvm::FoldReturnIntoUncondBranch(ReturnInst *RI, BasicBlock *BB,
 909                                              BasicBlock *Pred,
 910                                              DomTreeUpdater *DTU) {
 911   Instruction *UncondBranch = Pred->getTerminator();
 912   // Clone the return and add it to the end of the predecessor.
 913   Instruction *NewRet = RI->clone();
 914   Pred->getInstList().push_back(NewRet);
 915
 916   // If the return instruction returns a value, and if the value was a
 917   // PHI node in "BB", propagate the right value into the return.
 918   for (User::op_iterator i = NewRet->op_begin(), e = NewRet->op_end();
 919        i != e; ++i) {
 920     Value *V = *i;
 921     Instruction *NewBC = nullptr;
 922     if (BitCastInst *BCI = dyn_cast<BitCastInst>(V)) {
 923       // Return value might be bitcasted. Clone and insert it before the
 924       // return instruction.
 925       V = BCI->getOperand(0);
 926       NewBC = BCI->clone();
 927       Pred->getInstList().insert(NewRet->getIterator(), NewBC);
 928       *i = NewBC;
 929     }
 930
 931     Instruction *NewEV = nullptr;
 932     if (ExtractValueInst *EVI = dyn_cast<ExtractValueInst>(V)) {
 933       V = EVI->getOperand(0);
 934       NewEV = EVI->clone();
 935       if (NewBC) {
 936         NewBC->setOperand(0, NewEV);
 937         Pred->getInstList().insert(NewBC->getIterator(), NewEV);
 938       } else {
 939         Pred->getInstList().insert(NewRet->getIterator(), NewEV);
 940         *i = NewEV;
 941       }
 942     }
 943
 944     if (PHINode *PN = dyn_cast<PHINode>(V)) {
 945       if (PN->getParent() == BB) {
 946         if (NewEV) {
 947           NewEV->setOperand(0, PN->getIncomingValueForBlock(Pred));
 948         } else if (NewBC)
 949           NewBC->setOperand(0, PN->getIncomingValueForBlock(Pred));
 950         else
 951           *i = PN->getIncomingValueForBlock(Pred);
 952       }
 953     }
 954   }
 955
 956   // Update any PHI nodes in the returning block to realize that we no
 957   // longer branch to them.
 958   BB->removePredecessor(Pred);
 959   UncondBranch->eraseFromParent();
 960
 961   if (DTU)
 962     DTU->applyUpdates({{DominatorTree::Delete, Pred, BB}});
 963
 964   return cast<ReturnInst>(NewRet);
 965 }
 966
 967 Instruction *llvm::SplitBlockAndInsertIfThen(Value *Cond,
 968                                              Instruction *SplitBefore,
 969                                              bool Unreachable,
 970                                              MDNode *BranchWeights,
 971                                              DominatorTree *DT, LoopInfo *LI,
 972                                              BasicBlock *ThenBlock) {
 973   BasicBlock *Head = SplitBefore->getParent();
 974   BasicBlock *Tail = Head->splitBasicBlock(SplitBefore->getIterator());
 975   Instruction *HeadOldTerm = Head->getTerminator();
 976   LLVMContext &C = Head->getContext();
 977   Instruction *CheckTerm;
 978   bool CreateThenBlock = (ThenBlock == nullptr);
 979   if (CreateThenBlock) {
 980     ThenBlock = BasicBlock::Create(C, "", Head->getParent(), Tail);
 981     if (Unreachable)
 982       CheckTerm = new UnreachableInst(C, ThenBlock);
 983     else
 984       CheckTerm = BranchInst::Create(Tail, ThenBlock);
 985     CheckTerm->setDebugLoc(SplitBefore->getDebugLoc());
 986   } else
 987     CheckTerm = ThenBlock->getTerminator();
 988   BranchInst *HeadNewTerm =
 989     BranchInst::Create(/*ifTrue*/ThenBlock, /*ifFalse*/Tail, Cond);
 990   HeadNewTerm->setMetadata(LLVMContext::MD_prof, BranchWeights);
 991   ReplaceInstWithInst(HeadOldTerm, HeadNewTerm);
 992
 993   if (DT) {
 994     if (DomTreeNode *OldNode = DT->getNode(Head)) {
 995       std::vector<DomTreeNode *> Children(OldNode->begin(), OldNode->end());
 996
 997       DomTreeNode *NewNode = DT->addNewBlock(Tail, Head);
 998       for (DomTreeNode *Child : Children)
 999         DT->changeImmediateDominator(Child, NewNode);
1000
1001       // Head dominates ThenBlock.
1002       if (CreateThenBlock)
1003         DT->addNewBlock(ThenBlock, Head);
1004       else
1005         DT->changeImmediateDominator(ThenBlock, Head);
1006     }
1007   }
1008
1009   if (LI) {
1010     if (Loop *L = LI->getLoopFor(Head)) {
1011       L->addBasicBlockToLoop(ThenBlock, *LI);
1012       L->addBasicBlockToLoop(Tail, *LI);
1013     }
1014   }
1015
1016   return CheckTerm;
1017 }
1018
1019 void llvm::SplitBlockAndInsertIfThenElse(Value *Cond, Instruction *SplitBefore,
1020                                          Instruction **ThenTerm,
1021                                          Instruction **ElseTerm,
1022                                          MDNode *BranchWeights) {
1023   BasicBlock *Head = SplitBefore->getParent();
1024   BasicBlock *Tail = Head->splitBasicBlock(SplitBefore->getIterator());
1025   Instruction *HeadOldTerm = Head->getTerminator();
1026   LLVMContext &C = Head->getContext();
1027   BasicBlock *ThenBlock = BasicBlock::Create(C, "", Head->getParent(), Tail);
1028   BasicBlock *ElseBlock = BasicBlock::Create(C, "", Head->getParent(), Tail);
1029   *ThenTerm = BranchInst::Create(Tail, ThenBlock);
1030   (*ThenTerm)->setDebugLoc(SplitBefore->getDebugLoc());
1031   *ElseTerm = BranchInst::Create(Tail, ElseBlock);
1032   (*ElseTerm)->setDebugLoc(SplitBefore->getDebugLoc());
1033   BranchInst *HeadNewTerm =
1034     BranchInst::Create(/*ifTrue*/ThenBlock, /*ifFalse*/ElseBlock, Cond);
1035   HeadNewTerm->setMetadata(LLVMContext::MD_prof, BranchWeights);
1036   ReplaceInstWithInst(HeadOldTerm, HeadNewTerm);
1037 }
1038
1039 Value *llvm::GetIfCondition(BasicBlock *BB, BasicBlock *&IfTrue,
1040                              BasicBlock *&IfFalse) {
1041   PHINode *SomePHI = dyn_cast<PHINode>(BB->begin());
1042   BasicBlock *Pred1 = nullptr;
1043   BasicBlock *Pred2 = nullptr;
1044
1045   if (SomePHI) {
1046     if (SomePHI->getNumIncomingValues() != 2)
1047       return nullptr;
1048     Pred1 = SomePHI->getIncomingBlock(0);
1049     Pred2 = SomePHI->getIncomingBlock(1);
1050   } else {
1051     pred_iterator PI = pred_begin(BB), PE = pred_end(BB);
1052     if (PI == PE) // No predecessor
1053       return nullptr;
1054     Pred1 = *PI++;
1055     if (PI == PE) // Only one predecessor
1056       return nullptr;
1057     Pred2 = *PI++;
1058     if (PI != PE) // More than two predecessors
1059       return nullptr;
1060   }
1061
1062   // We can only handle branches.  Other control flow will be lowered to
1063   // branches if possible anyway.
1064   BranchInst *Pred1Br = dyn_cast<BranchInst>(Pred1->getTerminator());
1065   BranchInst *Pred2Br = dyn_cast<BranchInst>(Pred2->getTerminator());
1066   if (!Pred1Br || !Pred2Br)
1067     return nullptr;
1068
1069   // Eliminate code duplication by ensuring that Pred1Br is conditional if
1070   // either are.
1071   if (Pred2Br->isConditional()) {
1072     // If both branches are conditional, we don't have an "if statement".  In
1073     // reality, we could transform this case, but since the condition will be
1074     // required anyway, we stand no chance of eliminating it, so the xform is
1075     // probably not profitable.
1076     if (Pred1Br->isConditional())
1077       return nullptr;
1078
1079     std::swap(Pred1, Pred2);
1080     std::swap(Pred1Br, Pred2Br);
1081   }
1082
1083   if (Pred1Br->isConditional()) {
1084     // The only thing we have to watch out for here is to make sure that Pred2
1085     // doesn't have incoming edges from other blocks.  If it does, the condition
1086     // doesn't dominate BB.
1087     if (!Pred2->getSinglePredecessor())
1088       return nullptr;
1089
1090     // If we found a conditional branch predecessor, make sure that it branches
1091     // to BB and Pred2Br.  If it doesn't, this isn't an "if statement".
1092     if (Pred1Br->getSuccessor(0) == BB &&
1093         Pred1Br->getSuccessor(1) == Pred2) {
1094       IfTrue = Pred1;
1095       IfFalse = Pred2;
1096     } else if (Pred1Br->getSuccessor(0) == Pred2 &&
1097                Pred1Br->getSuccessor(1) == BB) {
1098       IfTrue = Pred2;
1099       IfFalse = Pred1;
1100     } else {
1101       // We know that one arm of the conditional goes to BB, so the other must
1102       // go somewhere unrelated, and this must not be an "if statement".
1103       return nullptr;
1104     }
1105
1106     return Pred1Br->getCondition();
1107   }
1108
1109   // Ok, if we got here, both predecessors end with an unconditional branch to
1110   // BB.  Don't panic!  If both blocks only have a single (identical)
1111   // predecessor, and THAT is a conditional branch, then we're all ok!
1112   BasicBlock *CommonPred = Pred1->getSinglePredecessor();
1113   if (CommonPred == nullptr || CommonPred != Pred2->getSinglePredecessor())
1114     return nullptr;
1115
1116   // Otherwise, if this is a conditional branch, then we can use it!
1117   BranchInst *BI = dyn_cast<BranchInst>(CommonPred->getTerminator());
1118   if (!BI) return nullptr;
1119
1120   assert(BI->isConditional() && "Two successors but not conditional?");
1121   if (BI->getSuccessor(0) == Pred1) {
1122     IfTrue = Pred1;
1123     IfFalse = Pred2;
1124   } else {
1125     IfTrue = Pred2;
1126     IfFalse = Pred1;
1127   }
1128   return BI->getCondition();
1129 }
1130
1131 // After creating a control flow hub, the operands of PHINodes in an outgoing
1132 // block Out no longer match the predecessors of that block. Predecessors of Out
1133 // that are incoming blocks to the hub are now replaced by just one edge from
1134 // the hub. To match this new control flow, the corresponding values from each
1135 // PHINode must now be moved a new PHINode in the first guard block of the hub.
1136 //
1137 // This operation cannot be performed with SSAUpdater, because it involves one
1138 // new use: If the block Out is in the list of Incoming blocks, then the newly
1139 // created PHI in the Hub will use itself along that edge from Out to Hub.
1140 static void reconnectPhis(BasicBlock *Out, BasicBlock *GuardBlock,
1141                           const SetVector<BasicBlock *> &Incoming,
1142                           BasicBlock *FirstGuardBlock) {
1143   auto I = Out->begin();
1144   while (I != Out->end() && isa<PHINode>(I)) {
1145     auto Phi = cast<PHINode>(I);
1146     auto NewPhi =
1147         PHINode::Create(Phi->getType(), Incoming.size(),
1148                         Phi->getName() + ".moved", &FirstGuardBlock->back());
1149     for (auto In : Incoming) {
1150       Value *V = UndefValue::get(Phi->getType());
1151       if (In == Out) {
1152         V = NewPhi;
1153       } else if (Phi->getBasicBlockIndex(In) != -1) {
1154         V = Phi->removeIncomingValue(In, false);
1155       }
1156       NewPhi->addIncoming(V, In);
1157     }
1158     assert(NewPhi->getNumIncomingValues() == Incoming.size());
1159     if (Phi->getNumOperands() == 0) {
1160       Phi->replaceAllUsesWith(NewPhi);
1161       I = Phi->eraseFromParent();
1162       continue;
1163     }
1164     Phi->addIncoming(NewPhi, GuardBlock);
1165     ++I;
1166   }
1167 }
1168
1169 using BBPredicates = DenseMap<BasicBlock *, PHINode *>;
1170 using BBSetVector = SetVector<BasicBlock *>;
1171
1172 // Redirects the terminator of the incoming block to the first guard
1173 // block in the hub. The condition of the original terminator (if it
1174 // was conditional) and its original successors are returned as a
1175 // tuple <condition, succ0, succ1>. The function additionally filters
1176 // out successors that are not in the set of outgoing blocks.
1177 //
1178 // - condition is non-null iff the branch is conditional.
1179 // - Succ1 is non-null iff the sole/taken target is an outgoing block.
1180 // - Succ2 is non-null iff condition is non-null and the fallthrough
1181 //         target is an outgoing block.
1182 static std::tuple<Value *, BasicBlock *, BasicBlock *>
1183 redirectToHub(BasicBlock *BB, BasicBlock *FirstGuardBlock,
1184               const BBSetVector &Outgoing) {
1185   auto Branch = cast<BranchInst>(BB->getTerminator());
1186   auto Condition = Branch->isConditional() ? Branch->getCondition() : nullptr;
1187
1188   BasicBlock *Succ0 = Branch->getSuccessor(0);
1189   BasicBlock *Succ1 = nullptr;
1190   Succ0 = Outgoing.count(Succ0) ? Succ0 : nullptr;
1191
1192   if (Branch->isUnconditional()) {
1193     Branch->setSuccessor(0, FirstGuardBlock);
1194     assert(Succ0);
1195   } else {
1196     Succ1 = Branch->getSuccessor(1);
1197     Succ1 = Outgoing.count(Succ1) ? Succ1 : nullptr;
1198     assert(Succ0 || Succ1);
1199     if (Succ0 && !Succ1) {
1200       Branch->setSuccessor(0, FirstGuardBlock);
1201     } else if (Succ1 && !Succ0) {
1202       Branch->setSuccessor(1, FirstGuardBlock);
1203     } else {
1204       Branch->eraseFromParent();
1205       BranchInst::Create(FirstGuardBlock, BB);
1206     }
1207   }
1208
1209   assert(Succ0 || Succ1);
1210   return std::make_tuple(Condition, Succ0, Succ1);
1211 }
1212
1213 // Capture the existing control flow as guard predicates, and redirect
1214 // control flow from every incoming block to the first guard block in
1215 // the hub.
1216 //
1217 // There is one guard predicate for each outgoing block OutBB. The
1218 // predicate is a PHINode with one input for each InBB which
1219 // represents whether the hub should transfer control flow to OutBB if
1220 // it arrived from InBB. These predicates are NOT ORTHOGONAL. The Hub
1221 // evaluates them in the same order as the Outgoing set-vector, and
1222 // control branches to the first outgoing block whose predicate
1223 // evaluates to true.
1224 static void convertToGuardPredicates(
1225     BasicBlock *FirstGuardBlock, BBPredicates &GuardPredicates,
1226     SmallVectorImpl<WeakVH> &DeletionCandidates, const BBSetVector &Incoming,
1227     const BBSetVector &Outgoing) {
1228   auto &Context = Incoming.front()->getContext();
1229   auto BoolTrue = ConstantInt::getTrue(Context);
1230   auto BoolFalse = ConstantInt::getFalse(Context);
1231
1232   // The predicate for the last outgoing is trivially true, and so we
1233   // process only the first N-1 successors.
1234   for (int i = 0, e = Outgoing.size() - 1; i != e; ++i) {
1235     auto Out = Outgoing[i];
1236     LLVM_DEBUG(dbgs() << "Creating guard for " << Out->getName() << "\n");
1237     auto Phi =
1238         PHINode::Create(Type::getInt1Ty(Context), Incoming.size(),
1239                         StringRef("Guard.") + Out->getName(), FirstGuardBlock);
1240     GuardPredicates[Out] = Phi;
1241   }
1242
1243   for (auto In : Incoming) {
1244     Value *Condition;
1245     BasicBlock *Succ0;
1246     BasicBlock *Succ1;
1247     std::tie(Condition, Succ0, Succ1) =
1248         redirectToHub(In, FirstGuardBlock, Outgoing);
1249
1250     // Optimization: Consider an incoming block A with both successors
1251     // Succ0 and Succ1 in the set of outgoing blocks. The predicates
1252     // for Succ0 and Succ1 complement each other. If Succ0 is visited
1253     // first in the loop below, control will branch to Succ0 using the
1254     // corresponding predicate. But if that branch is not taken, then
1255     // control must reach Succ1, which means that the predicate for
1256     // Succ1 is always true.
1257     bool OneSuccessorDone = false;
1258     for (int i = 0, e = Outgoing.size() - 1; i != e; ++i) {
1259       auto Out = Outgoing[i];
1260       auto Phi = GuardPredicates[Out];
1261       if (Out != Succ0 && Out != Succ1) {
1262         Phi->addIncoming(BoolFalse, In);
1263         continue;
1264       }
1265       // Optimization: When only one successor is an outgoing block,
1266       // the predicate is always true.
1267       if (!Succ0 || !Succ1 || OneSuccessorDone) {
1268         Phi->addIncoming(BoolTrue, In);
1269         continue;
1270       }
1271       assert(Succ0 && Succ1);
1272       OneSuccessorDone = true;
1273       if (Out == Succ0) {
1274         Phi->addIncoming(Condition, In);
1275         continue;
1276       }
1277       auto Inverted = invertCondition(Condition);
1278       DeletionCandidates.push_back(Condition);
1279       Phi->addIncoming(Inverted, In);
1280     }
1281   }
1282 }
1283
1284 // For each outgoing block OutBB, create a guard block in the Hub. The
1285 // first guard block was already created outside, and available as the
1286 // first element in the vector of guard blocks.
1287 //
1288 // Each guard block terminates in a conditional branch that transfers
1289 // control to the corresponding outgoing block or the next guard
1290 // block. The last guard block has two outgoing blocks as successors
1291 // since the condition for the final outgoing block is trivially
1292 // true. So we create one less block (including the first guard block)
1293 // than the number of outgoing blocks.
1294 static void createGuardBlocks(SmallVectorImpl<BasicBlock *> &GuardBlocks,
1295                               Function *F, const BBSetVector &Outgoing,
1296                               BBPredicates &GuardPredicates, StringRef Prefix) {
1297   for (int i = 0, e = Outgoing.size() - 2; i != e; ++i) {
1298     GuardBlocks.push_back(
1299         BasicBlock::Create(F->getContext(), Prefix + ".guard", F));
1300   }
1301   assert(GuardBlocks.size() == GuardPredicates.size());
1302
1303   // To help keep the loop simple, temporarily append the last
1304   // outgoing block to the list of guard blocks.
1305   GuardBlocks.push_back(Outgoing.back());
1306
1307   for (int i = 0, e = GuardBlocks.size() - 1; i != e; ++i) {
1308     auto Out = Outgoing[i];
1309     assert(GuardPredicates.count(Out));
1310     BranchInst::Create(Out, GuardBlocks[i + 1], GuardPredicates[Out],
1311                        GuardBlocks[i]);
1312   }
1313
1314   // Remove the last block from the guard list.
1315   GuardBlocks.pop_back();
1316 }
1317
1318 BasicBlock *llvm::CreateControlFlowHub(
1319     DomTreeUpdater *DTU, SmallVectorImpl<BasicBlock *> &GuardBlocks,
1320     const BBSetVector &Incoming, const BBSetVector &Outgoing,
1321     const StringRef Prefix) {
1322   auto F = Incoming.front()->getParent();
1323   auto FirstGuardBlock =
1324       BasicBlock::Create(F->getContext(), Prefix + ".guard", F);
1325
1326   SmallVector<DominatorTree::UpdateType, 16> Updates;
1327   if (DTU) {
1328     for (auto In : Incoming) {
1329       for (auto Succ : successors(In)) {
1330         if (Outgoing.count(Succ))
1331           Updates.push_back({DominatorTree::Delete, In, Succ});
1332       }
1333       Updates.push_back({DominatorTree::Insert, In, FirstGuardBlock});
1334     }
1335   }
1336
1337   BBPredicates GuardPredicates;
1338   SmallVector<WeakVH, 8> DeletionCandidates;
1339   convertToGuardPredicates(FirstGuardBlock, GuardPredicates, DeletionCandidates,
1340                            Incoming, Outgoing);
1341
1342   GuardBlocks.push_back(FirstGuardBlock);
1343   createGuardBlocks(GuardBlocks, F, Outgoing, GuardPredicates, Prefix);
1344
1345   // Update the PHINodes in each outgoing block to match the new control flow.
1346   for (int i = 0, e = GuardBlocks.size(); i != e; ++i) {
1347     reconnectPhis(Outgoing[i], GuardBlocks[i], Incoming, FirstGuardBlock);
1348   }
1349   reconnectPhis(Outgoing.back(), GuardBlocks.back(), Incoming, FirstGuardBlock);
1350
1351   if (DTU) {
1352     int NumGuards = GuardBlocks.size();
1353     assert((int)Outgoing.size() == NumGuards + 1);
1354     for (int i = 0; i != NumGuards - 1; ++i) {
1355       Updates.push_back({DominatorTree::Insert, GuardBlocks[i], Outgoing[i]});
1356       Updates.push_back(
1357           {DominatorTree::Insert, GuardBlocks[i], GuardBlocks[i + 1]});
1358     }
1359     Updates.push_back({DominatorTree::Insert, GuardBlocks[NumGuards - 1],
1360                        Outgoing[NumGuards - 1]});
1361     Updates.push_back({DominatorTree::Insert, GuardBlocks[NumGuards - 1],
1362                        Outgoing[NumGuards]});
1363     DTU->applyUpdates(Updates);
1364   }
1365
1366   for (auto I : DeletionCandidates) {
1367     if (I->use_empty())
1368       if (auto Inst = dyn_cast_or_null<Instruction>(I))
1369         Inst->eraseFromParent();
1370   }
1371
1372   return FirstGuardBlock;
1373 }