1895 lines · 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-exception6//7//===----------------------------------------------------------------------===//8//9// This family of functions perform manipulations on basic blocks, and10// 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/IR/BasicBlock.h"25#include "llvm/IR/CFG.h"26#include "llvm/IR/Constants.h"27#include "llvm/IR/DebugInfo.h"28#include "llvm/IR/DebugInfoMetadata.h"29#include "llvm/IR/Dominators.h"30#include "llvm/IR/Function.h"31#include "llvm/IR/IRBuilder.h"32#include "llvm/IR/InstrTypes.h"33#include "llvm/IR/Instruction.h"34#include "llvm/IR/Instructions.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/CommandLine.h"42#include "llvm/Support/Debug.h"43#include "llvm/Support/raw_ostream.h"44#include "llvm/Transforms/Utils/Local.h"45#include <cassert>46#include <cstdint>47#include <string>48#include <utility>49#include <vector>50 51using namespace llvm;52 53#define DEBUG_TYPE "basicblock-utils"54 55static cl::opt<unsigned> MaxDeoptOrUnreachableSuccessorCheckDepth(56 "max-deopt-or-unreachable-succ-check-depth", cl::init(8), cl::Hidden,57 cl::desc("Set the maximum path length when checking whether a basic block "58 "is followed by a block that either has a terminating "59 "deoptimizing call or is terminated with an unreachable"));60 61/// Zap all the instructions in the block and replace them with an unreachable62/// instruction and notify the basic block's successors that one of their63/// predecessors is going away.64static void65emptyAndDetachBlock(BasicBlock *BB,66 SmallVectorImpl<DominatorTree::UpdateType> *Updates,67 bool KeepOneInputPHIs) {68 // Loop through all of our successors and make sure they know that one69 // of their predecessors is going away.70 SmallPtrSet<BasicBlock *, 4> UniqueSuccessors;71 for (BasicBlock *Succ : successors(BB)) {72 Succ->removePredecessor(BB, KeepOneInputPHIs);73 if (Updates && UniqueSuccessors.insert(Succ).second)74 Updates->push_back({DominatorTree::Delete, BB, Succ});75 }76 77 // Zap all the instructions in the block.78 while (!BB->empty()) {79 Instruction &I = BB->back();80 // If this instruction is used, replace uses with an arbitrary value.81 // Because control flow can't get here, we don't care what we replace the82 // value with. Note that since this block is unreachable, and all values83 // contained within it must dominate their uses, that all uses will84 // eventually be removed (they are themselves dead).85 if (!I.use_empty())86 I.replaceAllUsesWith(PoisonValue::get(I.getType()));87 BB->back().eraseFromParent();88 }89 new UnreachableInst(BB->getContext(), BB);90 assert(BB->size() == 1 && isa<UnreachableInst>(BB->getTerminator()) &&91 "The successor list of BB isn't empty before "92 "applying corresponding DTU updates.");93}94 95static bool HasLoopOrEntryConvergenceToken(const BasicBlock *BB) {96 for (const Instruction &I : *BB) {97 const ConvergenceControlInst *CCI = dyn_cast<ConvergenceControlInst>(&I);98 if (CCI && (CCI->isLoop() || CCI->isEntry()))99 return true;100 }101 return false;102}103 104void llvm::detachDeadBlocks(ArrayRef<BasicBlock *> BBs,105 SmallVectorImpl<DominatorTree::UpdateType> *Updates,106 bool KeepOneInputPHIs) {107 SmallPtrSet<BasicBlock *, 4> UniqueEHRetBlocksToDelete;108 for (auto *BB : BBs) {109 auto NonFirstPhiIt = BB->getFirstNonPHIIt();110 if (NonFirstPhiIt != BB->end()) {111 Instruction &I = *NonFirstPhiIt;112 // Exception handling funclets need to be explicitly addressed.113 // These funclets must begin with cleanuppad or catchpad and end with114 // cleanupred or catchret. The return instructions can be in different115 // basic blocks than the pad instruction. If we would only delete the116 // first block, the we would have possible cleanupret and catchret117 // instructions with poison arguments, which wouldn't be valid.118 if (isa<FuncletPadInst>(I)) {119 UniqueEHRetBlocksToDelete.clear();120 121 for (User *User : I.users()) {122 Instruction *ReturnInstr = dyn_cast<Instruction>(User);123 // If we have a cleanupret or catchret block, replace it with just an124 // unreachable. The other alternative, that may use a catchpad is a125 // catchswitch. That does not need special handling for now.126 if (isa<CatchReturnInst>(ReturnInstr) ||127 isa<CleanupReturnInst>(ReturnInstr)) {128 BasicBlock *ReturnInstrBB = ReturnInstr->getParent();129 UniqueEHRetBlocksToDelete.insert(ReturnInstrBB);130 }131 }132 133 for (BasicBlock *EHRetBB : UniqueEHRetBlocksToDelete)134 emptyAndDetachBlock(EHRetBB, Updates, KeepOneInputPHIs);135 }136 }137 138 UniqueEHRetBlocksToDelete.clear();139 140 // Detaching and emptying the current basic block.141 emptyAndDetachBlock(BB, Updates, KeepOneInputPHIs);142 }143}144 145void llvm::DeleteDeadBlock(BasicBlock *BB, DomTreeUpdater *DTU,146 bool KeepOneInputPHIs) {147 DeleteDeadBlocks({BB}, DTU, KeepOneInputPHIs);148}149 150void llvm::DeleteDeadBlocks(ArrayRef <BasicBlock *> BBs, DomTreeUpdater *DTU,151 bool KeepOneInputPHIs) {152#ifndef NDEBUG153 // Make sure that all predecessors of each dead block is also dead.154 SmallPtrSet<BasicBlock *, 4> Dead(llvm::from_range, BBs);155 assert(Dead.size() == BBs.size() && "Duplicating blocks?");156 for (auto *BB : Dead)157 for (BasicBlock *Pred : predecessors(BB))158 assert(Dead.count(Pred) && "All predecessors must be dead!");159#endif160 161 SmallVector<DominatorTree::UpdateType, 4> Updates;162 detachDeadBlocks(BBs, DTU ? &Updates : nullptr, KeepOneInputPHIs);163 164 if (DTU)165 DTU->applyUpdates(Updates);166 167 for (BasicBlock *BB : BBs)168 if (DTU)169 DTU->deleteBB(BB);170 else171 BB->eraseFromParent();172}173 174bool llvm::EliminateUnreachableBlocks(Function &F, DomTreeUpdater *DTU,175 bool KeepOneInputPHIs) {176 df_iterator_default_set<BasicBlock*> Reachable;177 178 // Mark all reachable blocks.179 for (BasicBlock *BB : depth_first_ext(&F, Reachable))180 (void)BB/* Mark all reachable blocks */;181 182 // Collect all dead blocks.183 std::vector<BasicBlock*> DeadBlocks;184 for (BasicBlock &BB : F)185 if (!Reachable.count(&BB))186 DeadBlocks.push_back(&BB);187 188 // Delete the dead blocks.189 DeleteDeadBlocks(DeadBlocks, DTU, KeepOneInputPHIs);190 191 return !DeadBlocks.empty();192}193 194bool llvm::FoldSingleEntryPHINodes(BasicBlock *BB,195 MemoryDependenceResults *MemDep) {196 if (!isa<PHINode>(BB->begin()))197 return false;198 199 while (PHINode *PN = dyn_cast<PHINode>(BB->begin())) {200 if (PN->getIncomingValue(0) != PN)201 PN->replaceAllUsesWith(PN->getIncomingValue(0));202 else203 PN->replaceAllUsesWith(PoisonValue::get(PN->getType()));204 205 if (MemDep)206 MemDep->removeInstruction(PN); // Memdep updates AA itself.207 208 PN->eraseFromParent();209 }210 return true;211}212 213bool llvm::DeleteDeadPHIs(BasicBlock *BB, const TargetLibraryInfo *TLI,214 MemorySSAUpdater *MSSAU) {215 // Recursively deleting a PHI may cause multiple PHIs to be deleted216 // or RAUW'd undef, so use an array of WeakTrackingVH for the PHIs to delete.217 SmallVector<WeakTrackingVH, 8> PHIs(llvm::make_pointer_range(BB->phis()));218 219 bool Changed = false;220 for (const auto &PHI : PHIs)221 if (PHINode *PN = dyn_cast_or_null<PHINode>(PHI.operator Value *()))222 Changed |= RecursivelyDeleteDeadPHINode(PN, TLI, MSSAU);223 224 return Changed;225}226 227bool llvm::MergeBlockIntoPredecessor(BasicBlock *BB, DomTreeUpdater *DTU,228 LoopInfo *LI, MemorySSAUpdater *MSSAU,229 MemoryDependenceResults *MemDep,230 bool PredecessorWithTwoSuccessors,231 DominatorTree *DT) {232 if (BB->hasAddressTaken())233 return false;234 235 // Can't merge if there are multiple predecessors, or no predecessors.236 BasicBlock *PredBB = BB->getUniquePredecessor();237 if (!PredBB) return false;238 239 // Don't break self-loops.240 if (PredBB == BB) return false;241 242 // Don't break unwinding instructions or terminators with other side-effects.243 Instruction *PTI = PredBB->getTerminator();244 if (PTI->isSpecialTerminator() || PTI->mayHaveSideEffects())245 return false;246 247 // Can't merge if there are multiple distinct successors.248 if (!PredecessorWithTwoSuccessors && PredBB->getUniqueSuccessor() != BB)249 return false;250 251 // Currently only allow PredBB to have two predecessors, one being BB.252 // Update BI to branch to BB's only successor instead of BB.253 BranchInst *PredBB_BI;254 BasicBlock *NewSucc = nullptr;255 unsigned FallThruPath;256 if (PredecessorWithTwoSuccessors) {257 if (!(PredBB_BI = dyn_cast<BranchInst>(PTI)))258 return false;259 BranchInst *BB_JmpI = dyn_cast<BranchInst>(BB->getTerminator());260 if (!BB_JmpI || !BB_JmpI->isUnconditional())261 return false;262 NewSucc = BB_JmpI->getSuccessor(0);263 FallThruPath = PredBB_BI->getSuccessor(0) == BB ? 0 : 1;264 }265 266 // Can't merge if there is PHI loop.267 for (PHINode &PN : BB->phis())268 if (llvm::is_contained(PN.incoming_values(), &PN))269 return false;270 271 // Don't break if both the basic block and the predecessor contain loop or272 // entry convergent intrinsics, since there may only be one convergence token273 // per block.274 if (HasLoopOrEntryConvergenceToken(BB) &&275 HasLoopOrEntryConvergenceToken(PredBB))276 return false;277 278 LLVM_DEBUG(dbgs() << "Merging: " << BB->getName() << " into "279 << PredBB->getName() << "\n");280 281 // Begin by getting rid of unneeded PHIs.282 SmallVector<AssertingVH<Value>, 4> IncomingValues;283 if (isa<PHINode>(BB->front())) {284 for (PHINode &PN : BB->phis())285 if (!isa<PHINode>(PN.getIncomingValue(0)) ||286 cast<PHINode>(PN.getIncomingValue(0))->getParent() != BB)287 IncomingValues.push_back(PN.getIncomingValue(0));288 FoldSingleEntryPHINodes(BB, MemDep);289 }290 291 if (DT) {292 assert(!DTU && "cannot use both DT and DTU for updates");293 DomTreeNode *PredNode = DT->getNode(PredBB);294 DomTreeNode *BBNode = DT->getNode(BB);295 if (PredNode) {296 assert(BBNode && "PredNode unreachable but BBNode reachable?");297 for (DomTreeNode *C : to_vector(BBNode->children()))298 C->setIDom(PredNode);299 }300 }301 // DTU update: Collect all the edges that exit BB.302 // These dominator edges will be redirected from Pred.303 std::vector<DominatorTree::UpdateType> Updates;304 if (DTU) {305 assert(!DT && "cannot use both DT and DTU for updates");306 // To avoid processing the same predecessor more than once.307 SmallPtrSet<BasicBlock *, 8> SeenSuccs;308 SmallPtrSet<BasicBlock *, 2> SuccsOfPredBB(llvm::from_range,309 successors(PredBB));310 Updates.reserve(Updates.size() + 2 * succ_size(BB) + 1);311 // Add insert edges first. Experimentally, for the particular case of two312 // blocks that can be merged, with a single successor and single predecessor313 // respectively, it is beneficial to have all insert updates first. Deleting314 // edges first may lead to unreachable blocks, followed by inserting edges315 // making the blocks reachable again. Such DT updates lead to high compile316 // times. We add inserts before deletes here to reduce compile time.317 for (BasicBlock *SuccOfBB : successors(BB))318 // This successor of BB may already be a PredBB's successor.319 if (!SuccsOfPredBB.contains(SuccOfBB))320 if (SeenSuccs.insert(SuccOfBB).second)321 Updates.push_back({DominatorTree::Insert, PredBB, SuccOfBB});322 SeenSuccs.clear();323 for (BasicBlock *SuccOfBB : successors(BB))324 if (SeenSuccs.insert(SuccOfBB).second)325 Updates.push_back({DominatorTree::Delete, BB, SuccOfBB});326 Updates.push_back({DominatorTree::Delete, PredBB, BB});327 }328 329 Instruction *STI = BB->getTerminator();330 Instruction *Start = &*BB->begin();331 // If there's nothing to move, mark the starting instruction as the last332 // instruction in the block. Terminator instruction is handled separately.333 if (Start == STI)334 Start = PTI;335 336 // Move all definitions in the successor to the predecessor...337 PredBB->splice(PTI->getIterator(), BB, BB->begin(), STI->getIterator());338 339 if (MSSAU)340 MSSAU->moveAllAfterMergeBlocks(BB, PredBB, Start);341 342 // Make all PHI nodes that referred to BB now refer to Pred as their343 // source...344 BB->replaceAllUsesWith(PredBB);345 346 if (PredecessorWithTwoSuccessors) {347 // Delete the unconditional branch from BB.348 BB->back().eraseFromParent();349 350 // Update branch in the predecessor.351 PredBB_BI->setSuccessor(FallThruPath, NewSucc);352 } else {353 // Delete the unconditional branch from the predecessor.354 PredBB->back().eraseFromParent();355 356 // Move terminator instruction.357 BB->back().moveBeforePreserving(*PredBB, PredBB->end());358 359 // Terminator may be a memory accessing instruction too.360 if (MSSAU)361 if (MemoryUseOrDef *MUD = cast_or_null<MemoryUseOrDef>(362 MSSAU->getMemorySSA()->getMemoryAccess(PredBB->getTerminator())))363 MSSAU->moveToPlace(MUD, PredBB, MemorySSA::End);364 }365 // Add unreachable to now empty BB.366 new UnreachableInst(BB->getContext(), BB);367 368 // Inherit predecessors name if it exists.369 if (!PredBB->hasName())370 PredBB->takeName(BB);371 372 if (LI)373 LI->removeBlock(BB);374 375 if (MemDep)376 MemDep->invalidateCachedPredecessors();377 378 if (DTU)379 DTU->applyUpdates(Updates);380 381 if (DT) {382 assert(succ_empty(BB) &&383 "successors should have been transferred to PredBB");384 DT->eraseNode(BB);385 }386 387 // Finally, erase the old block and update dominator info.388 DeleteDeadBlock(BB, DTU);389 390 return true;391}392 393bool llvm::MergeBlockSuccessorsIntoGivenBlocks(394 SmallPtrSetImpl<BasicBlock *> &MergeBlocks, Loop *L, DomTreeUpdater *DTU,395 LoopInfo *LI) {396 assert(!MergeBlocks.empty() && "MergeBlocks should not be empty");397 398 bool BlocksHaveBeenMerged = false;399 while (!MergeBlocks.empty()) {400 BasicBlock *BB = *MergeBlocks.begin();401 BasicBlock *Dest = BB->getSingleSuccessor();402 if (Dest && (!L || L->contains(Dest))) {403 BasicBlock *Fold = Dest->getUniquePredecessor();404 (void)Fold;405 if (MergeBlockIntoPredecessor(Dest, DTU, LI)) {406 assert(Fold == BB &&407 "Expecting BB to be unique predecessor of the Dest block");408 MergeBlocks.erase(Dest);409 BlocksHaveBeenMerged = true;410 } else411 MergeBlocks.erase(BB);412 } else413 MergeBlocks.erase(BB);414 }415 return BlocksHaveBeenMerged;416}417 418/// Remove redundant instructions within sequences of consecutive dbg.value419/// instructions. This is done using a backward scan to keep the last dbg.value420/// describing a specific variable/fragment.421///422/// BackwardScan strategy:423/// ----------------------424/// Given a sequence of consecutive DbgValueInst like this425///426/// dbg.value ..., "x", FragmentX1 (*)427/// dbg.value ..., "y", FragmentY1428/// dbg.value ..., "x", FragmentX2429/// dbg.value ..., "x", FragmentX1 (**)430///431/// then the instruction marked with (*) can be removed (it is guaranteed to be432/// obsoleted by the instruction marked with (**) as the latter instruction is433/// describing the same variable using the same fragment info).434///435/// Possible improvements:436/// - Check fully overlapping fragments and not only identical fragments.437static bool removeRedundantDbgInstrsUsingBackwardScan(BasicBlock *BB) {438 SmallVector<DbgVariableRecord *, 8> ToBeRemoved;439 SmallDenseSet<DebugVariable> VariableSet;440 for (auto &I : reverse(*BB)) {441 for (DbgVariableRecord &DVR :442 reverse(filterDbgVars(I.getDbgRecordRange()))) {443 DebugVariable Key(DVR.getVariable(), DVR.getExpression(),444 DVR.getDebugLoc()->getInlinedAt());445 auto R = VariableSet.insert(Key);446 // If the same variable fragment is described more than once it is enough447 // to keep the last one (i.e. the first found since we for reverse448 // iteration).449 if (R.second)450 continue;451 452 if (DVR.isDbgAssign()) {453 // Don't delete dbg.assign intrinsics that are linked to instructions.454 if (!at::getAssignmentInsts(&DVR).empty())455 continue;456 // Unlinked dbg.assign intrinsics can be treated like dbg.values.457 }458 459 ToBeRemoved.push_back(&DVR);460 }461 // Sequence with consecutive dbg.value instrs ended. Clear the map to462 // restart identifying redundant instructions if case we find another463 // dbg.value sequence.464 VariableSet.clear();465 }466 467 for (auto &DVR : ToBeRemoved)468 DVR->eraseFromParent();469 470 return !ToBeRemoved.empty();471}472 473/// Remove redundant dbg.value instructions using a forward scan. This can474/// remove a dbg.value instruction that is redundant due to indicating that a475/// variable has the same value as already being indicated by an earlier476/// dbg.value.477///478/// ForwardScan strategy:479/// ---------------------480/// Given two identical dbg.value instructions, separated by a block of481/// instructions that isn't describing the same variable, like this482///483/// dbg.value X1, "x", FragmentX1 (**)484/// <block of instructions, none being "dbg.value ..., "x", ...">485/// dbg.value X1, "x", FragmentX1 (*)486///487/// then the instruction marked with (*) can be removed. Variable "x" is already488/// described as being mapped to the SSA value X1.489///490/// Possible improvements:491/// - Keep track of non-overlapping fragments.492static bool removeRedundantDbgInstrsUsingForwardScan(BasicBlock *BB) {493 bool RemovedAny = false;494 SmallDenseMap<DebugVariable,495 std::pair<SmallVector<Value *, 4>, DIExpression *>, 4>496 VariableMap;497 for (auto &I : *BB) {498 for (DbgVariableRecord &DVR :499 make_early_inc_range(filterDbgVars(I.getDbgRecordRange()))) {500 if (DVR.getType() == DbgVariableRecord::LocationType::Declare)501 continue;502 DebugVariable Key(DVR.getVariable(), std::nullopt,503 DVR.getDebugLoc()->getInlinedAt());504 auto [VMI, Inserted] = VariableMap.try_emplace(Key);505 // A dbg.assign with no linked instructions can be treated like a506 // dbg.value (i.e. can be deleted).507 bool IsDbgValueKind =508 (!DVR.isDbgAssign() || at::getAssignmentInsts(&DVR).empty());509 510 // Update the map if we found a new value/expression describing the511 // variable, or if the variable wasn't mapped already.512 SmallVector<Value *, 4> Values(DVR.location_ops());513 if (Inserted || VMI->second.first != Values ||514 VMI->second.second != DVR.getExpression()) {515 if (IsDbgValueKind)516 VMI->second = {Values, DVR.getExpression()};517 else518 VMI->second = {Values, nullptr};519 continue;520 }521 // Don't delete dbg.assign intrinsics that are linked to instructions.522 if (!IsDbgValueKind)523 continue;524 // Found an identical mapping. Remember the instruction for later removal.525 DVR.eraseFromParent();526 RemovedAny = true;527 }528 }529 530 return RemovedAny;531}532 533/// Remove redundant undef dbg.assign intrinsic from an entry block using a534/// forward scan.535/// Strategy:536/// ---------------------537/// Scanning forward, delete dbg.assign intrinsics iff they are undef, not538/// linked to an intrinsic, and don't share an aggregate variable with a debug539/// intrinsic that didn't meet the criteria. In other words, undef dbg.assigns540/// that come before non-undef debug intrinsics for the variable are541/// deleted. Given:542///543/// dbg.assign undef, "x", FragmentX1 (*)544/// <block of instructions, none being "dbg.value ..., "x", ...">545/// dbg.value %V, "x", FragmentX2546/// <block of instructions, none being "dbg.value ..., "x", ...">547/// dbg.assign undef, "x", FragmentX1548///549/// then (only) the instruction marked with (*) can be removed.550/// Possible improvements:551/// - Keep track of non-overlapping fragments.552static bool removeUndefDbgAssignsFromEntryBlock(BasicBlock *BB) {553 assert(BB->isEntryBlock() && "expected entry block");554 bool RemovedAny = false;555 DenseSet<DebugVariableAggregate> SeenDefForAggregate;556 557 // Remove undef dbg.assign intrinsics that are encountered before558 // any non-undef intrinsics from the entry block.559 for (auto &I : *BB) {560 for (DbgVariableRecord &DVR :561 make_early_inc_range(filterDbgVars(I.getDbgRecordRange()))) {562 if (!DVR.isDbgValue() && !DVR.isDbgAssign())563 continue;564 bool IsDbgValueKind =565 (DVR.isDbgValue() || at::getAssignmentInsts(&DVR).empty());566 567 DebugVariableAggregate Aggregate(&DVR);568 if (!SeenDefForAggregate.contains(Aggregate)) {569 bool IsKill = DVR.isKillLocation() && IsDbgValueKind;570 if (!IsKill) {571 SeenDefForAggregate.insert(Aggregate);572 } else if (DVR.isDbgAssign()) {573 DVR.eraseFromParent();574 RemovedAny = true;575 }576 }577 }578 }579 580 return RemovedAny;581}582 583bool llvm::RemoveRedundantDbgInstrs(BasicBlock *BB) {584 bool MadeChanges = false;585 // By using the "backward scan" strategy before the "forward scan" strategy we586 // can remove both dbg.value (2) and (3) in a situation like this:587 //588 // (1) dbg.value V1, "x", DIExpression()589 // ...590 // (2) dbg.value V2, "x", DIExpression()591 // (3) dbg.value V1, "x", DIExpression()592 //593 // The backward scan will remove (2), it is made obsolete by (3). After594 // getting (2) out of the way, the foward scan will remove (3) since "x"595 // already is described as having the value V1 at (1).596 MadeChanges |= removeRedundantDbgInstrsUsingBackwardScan(BB);597 if (BB->isEntryBlock() &&598 isAssignmentTrackingEnabled(*BB->getParent()->getParent()))599 MadeChanges |= removeUndefDbgAssignsFromEntryBlock(BB);600 MadeChanges |= removeRedundantDbgInstrsUsingForwardScan(BB);601 602 if (MadeChanges)603 LLVM_DEBUG(dbgs() << "Removed redundant dbg instrs from: "604 << BB->getName() << "\n");605 return MadeChanges;606}607 608void llvm::ReplaceInstWithValue(BasicBlock::iterator &BI, Value *V) {609 Instruction &I = *BI;610 // Replaces all of the uses of the instruction with uses of the value611 I.replaceAllUsesWith(V);612 613 // Make sure to propagate a name if there is one already.614 if (I.hasName() && !V->hasName())615 V->takeName(&I);616 617 // Delete the unnecessary instruction now...618 BI = BI->eraseFromParent();619}620 621void llvm::ReplaceInstWithInst(BasicBlock *BB, BasicBlock::iterator &BI,622 Instruction *I) {623 assert(I->getParent() == nullptr &&624 "ReplaceInstWithInst: Instruction already inserted into basic block!");625 626 // Copy debug location to newly added instruction, if it wasn't already set627 // by the caller.628 if (!I->getDebugLoc())629 I->setDebugLoc(BI->getDebugLoc());630 631 // Insert the new instruction into the basic block...632 BasicBlock::iterator New = I->insertInto(BB, BI);633 634 // Replace all uses of the old instruction, and delete it.635 ReplaceInstWithValue(BI, I);636 637 // Move BI back to point to the newly inserted instruction638 BI = New;639}640 641bool llvm::IsBlockFollowedByDeoptOrUnreachable(const BasicBlock *BB) {642 // Remember visited blocks to avoid infinite loop643 SmallPtrSet<const BasicBlock *, 8> VisitedBlocks;644 unsigned Depth = 0;645 while (BB && Depth++ < MaxDeoptOrUnreachableSuccessorCheckDepth &&646 VisitedBlocks.insert(BB).second) {647 if (isa<UnreachableInst>(BB->getTerminator()) ||648 BB->getTerminatingDeoptimizeCall())649 return true;650 BB = BB->getUniqueSuccessor();651 }652 return false;653}654 655void llvm::ReplaceInstWithInst(Instruction *From, Instruction *To) {656 BasicBlock::iterator BI(From);657 ReplaceInstWithInst(From->getParent(), BI, To);658}659 660BasicBlock *llvm::SplitEdge(BasicBlock *BB, BasicBlock *Succ, DominatorTree *DT,661 LoopInfo *LI, MemorySSAUpdater *MSSAU,662 const Twine &BBName) {663 unsigned SuccNum = GetSuccessorNumber(BB, Succ);664 665 Instruction *LatchTerm = BB->getTerminator();666 667 CriticalEdgeSplittingOptions Options =668 CriticalEdgeSplittingOptions(DT, LI, MSSAU).setPreserveLCSSA();669 670 if ((isCriticalEdge(LatchTerm, SuccNum, Options.MergeIdenticalEdges))) {671 // If this is a critical edge, let SplitKnownCriticalEdge do it.672 return SplitKnownCriticalEdge(LatchTerm, SuccNum, Options, BBName);673 }674 675 // If the edge isn't critical, then BB has a single successor or Succ has a676 // single pred. Split the block.677 if (BasicBlock *SP = Succ->getSinglePredecessor()) {678 // If the successor only has a single pred, split the top of the successor679 // block.680 assert(SP == BB && "CFG broken");681 (void)SP;682 return SplitBlock(Succ, &Succ->front(), DT, LI, MSSAU, BBName,683 /*Before=*/true);684 }685 686 // Otherwise, if BB has a single successor, split it at the bottom of the687 // block.688 assert(BB->getTerminator()->getNumSuccessors() == 1 &&689 "Should have a single succ!");690 return SplitBlock(BB, BB->getTerminator(), DT, LI, MSSAU, BBName);691}692 693/// Helper function to update the cycle or loop information after inserting a694/// new block between a callbr instruction and one of its target blocks. Adds695/// the new block to the innermost cycle or loop that the callbr instruction and696/// the original target block share.697/// \p LCI cycle or loop information to update698/// \p CallBrBlock block containing the callbr instruction699/// \p CallBrTarget new target block of the callbr instruction700/// \p Succ original target block of the callbr instruction701template <typename TI, typename T>702static bool updateCycleLoopInfo(TI *LCI, BasicBlock *CallBrBlock,703 BasicBlock *CallBrTarget, BasicBlock *Succ) {704 static_assert(std::is_same_v<TI, CycleInfo> || std::is_same_v<TI, LoopInfo>,705 "type must be CycleInfo or LoopInfo");706 if (!LCI)707 return false;708 709 T *LC;710 if constexpr (std::is_same_v<TI, CycleInfo>)711 LC = LCI->getSmallestCommonCycle(CallBrBlock, Succ);712 else713 LC = LCI->getSmallestCommonLoop(CallBrBlock, Succ);714 if (!LC)715 return false;716 717 if constexpr (std::is_same_v<TI, CycleInfo>)718 LCI->addBlockToCycle(CallBrTarget, LC);719 else720 LC->addBasicBlockToLoop(CallBrTarget, *LCI);721 722 return true;723}724 725BasicBlock *llvm::SplitCallBrEdge(BasicBlock *CallBrBlock, BasicBlock *Succ,726 unsigned SuccIdx, DomTreeUpdater *DTU,727 CycleInfo *CI, LoopInfo *LI,728 bool *UpdatedLI) {729 CallBrInst *CallBr = dyn_cast<CallBrInst>(CallBrBlock->getTerminator());730 assert(CallBr && "expected callbr terminator");731 assert(SuccIdx < CallBr->getNumSuccessors() &&732 Succ == CallBr->getSuccessor(SuccIdx) && "invalid successor index");733 734 // Create a new block between callbr and the specified successor.735 // splitBlockBefore cannot be re-used here since it cannot split if the split736 // point is a PHI node (because BasicBlock::splitBasicBlockBefore cannot737 // handle that). But we don't need to rewire every part of a potential PHI738 // node. We only care about the edge between CallBrBlock and the original739 // successor.740 BasicBlock *CallBrTarget =741 BasicBlock::Create(CallBrBlock->getContext(),742 CallBrBlock->getName() + ".target." + Succ->getName(),743 CallBrBlock->getParent());744 // Rewire control flow from the new target block to the original successor.745 Succ->replacePhiUsesWith(CallBrBlock, CallBrTarget);746 // Rewire control flow from callbr to the new target block.747 CallBr->setSuccessor(SuccIdx, CallBrTarget);748 // Jump from the new target block to the original successor.749 BranchInst::Create(Succ, CallBrTarget);750 751 bool Updated =752 updateCycleLoopInfo<LoopInfo, Loop>(LI, CallBrBlock, CallBrTarget, Succ);753 if (UpdatedLI)754 *UpdatedLI = Updated;755 updateCycleLoopInfo<CycleInfo, Cycle>(CI, CallBrBlock, CallBrTarget, Succ);756 if (DTU) {757 DTU->applyUpdates({{DominatorTree::Insert, CallBrBlock, CallBrTarget}});758 if (DTU->getDomTree().dominates(CallBrBlock, Succ))759 DTU->applyUpdates({{DominatorTree::Delete, CallBrBlock, Succ},760 {DominatorTree::Insert, CallBrTarget, Succ}});761 }762 763 return CallBrTarget;764}765 766void llvm::setUnwindEdgeTo(Instruction *TI, BasicBlock *Succ) {767 if (auto *II = dyn_cast<InvokeInst>(TI))768 II->setUnwindDest(Succ);769 else if (auto *CS = dyn_cast<CatchSwitchInst>(TI))770 CS->setUnwindDest(Succ);771 else if (auto *CR = dyn_cast<CleanupReturnInst>(TI))772 CR->setUnwindDest(Succ);773 else774 llvm_unreachable("unexpected terminator instruction");775}776 777void llvm::updatePhiNodes(BasicBlock *DestBB, BasicBlock *OldPred,778 BasicBlock *NewPred, PHINode *Until) {779 int BBIdx = 0;780 for (PHINode &PN : DestBB->phis()) {781 // We manually update the LandingPadReplacement PHINode and it is the last782 // PHI Node. So, if we find it, we are done.783 if (Until == &PN)784 break;785 786 // Reuse the previous value of BBIdx if it lines up. In cases where we787 // have multiple phi nodes with *lots* of predecessors, this is a speed788 // win because we don't have to scan the PHI looking for TIBB. This789 // happens because the BB list of PHI nodes are usually in the same790 // order.791 if (PN.getIncomingBlock(BBIdx) != OldPred)792 BBIdx = PN.getBasicBlockIndex(OldPred);793 794 assert(BBIdx != -1 && "Invalid PHI Index!");795 PN.setIncomingBlock(BBIdx, NewPred);796 }797}798 799BasicBlock *llvm::ehAwareSplitEdge(BasicBlock *BB, BasicBlock *Succ,800 LandingPadInst *OriginalPad,801 PHINode *LandingPadReplacement,802 const CriticalEdgeSplittingOptions &Options,803 const Twine &BBName) {804 805 auto PadInst = Succ->getFirstNonPHIIt();806 if (!LandingPadReplacement && !PadInst->isEHPad())807 return SplitEdge(BB, Succ, Options.DT, Options.LI, Options.MSSAU, BBName);808 809 auto *LI = Options.LI;810 SmallVector<BasicBlock *, 4> LoopPreds;811 // Check if extra modifications will be required to preserve loop-simplify812 // form after splitting. If it would require splitting blocks with IndirectBr813 // terminators, bail out if preserving loop-simplify form is requested.814 if (Options.PreserveLoopSimplify && LI) {815 if (Loop *BBLoop = LI->getLoopFor(BB)) {816 817 // The only way that we can break LoopSimplify form by splitting a818 // critical edge is when there exists some edge from BBLoop to Succ *and*819 // the only edge into Succ from outside of BBLoop is that of NewBB after820 // the split. If the first isn't true, then LoopSimplify still holds,821 // NewBB is the new exit block and it has no non-loop predecessors. If the822 // second isn't true, then Succ was not in LoopSimplify form prior to823 // the split as it had a non-loop predecessor. In both of these cases,824 // the predecessor must be directly in BBLoop, not in a subloop, or again825 // LoopSimplify doesn't hold.826 for (BasicBlock *P : predecessors(Succ)) {827 if (P == BB)828 continue; // The new block is known.829 if (LI->getLoopFor(P) != BBLoop) {830 // Loop is not in LoopSimplify form, no need to re simplify after831 // splitting edge.832 LoopPreds.clear();833 break;834 }835 LoopPreds.push_back(P);836 }837 // Loop-simplify form can be preserved, if we can split all in-loop838 // predecessors.839 if (any_of(LoopPreds, [](BasicBlock *Pred) {840 return isa<IndirectBrInst>(Pred->getTerminator());841 })) {842 return nullptr;843 }844 }845 }846 847 auto *NewBB =848 BasicBlock::Create(BB->getContext(), BBName, BB->getParent(), Succ);849 setUnwindEdgeTo(BB->getTerminator(), NewBB);850 updatePhiNodes(Succ, BB, NewBB, LandingPadReplacement);851 852 if (LandingPadReplacement) {853 auto *NewLP = OriginalPad->clone();854 auto *Terminator = BranchInst::Create(Succ, NewBB);855 NewLP->insertBefore(Terminator->getIterator());856 LandingPadReplacement->addIncoming(NewLP, NewBB);857 } else {858 Value *ParentPad = nullptr;859 if (auto *FuncletPad = dyn_cast<FuncletPadInst>(PadInst))860 ParentPad = FuncletPad->getParentPad();861 else if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(PadInst))862 ParentPad = CatchSwitch->getParentPad();863 else if (auto *CleanupPad = dyn_cast<CleanupPadInst>(PadInst))864 ParentPad = CleanupPad->getParentPad();865 else if (auto *LandingPad = dyn_cast<LandingPadInst>(PadInst))866 ParentPad = LandingPad->getParent();867 else868 llvm_unreachable("handling for other EHPads not implemented yet");869 870 auto *NewCleanupPad = CleanupPadInst::Create(ParentPad, {}, BBName, NewBB);871 CleanupReturnInst::Create(NewCleanupPad, Succ, NewBB);872 }873 874 auto *DT = Options.DT;875 auto *MSSAU = Options.MSSAU;876 if (!DT && !LI)877 return NewBB;878 879 if (DT) {880 DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Lazy);881 SmallVector<DominatorTree::UpdateType, 3> Updates;882 883 Updates.push_back({DominatorTree::Insert, BB, NewBB});884 Updates.push_back({DominatorTree::Insert, NewBB, Succ});885 Updates.push_back({DominatorTree::Delete, BB, Succ});886 887 DTU.applyUpdates(Updates);888 DTU.flush();889 890 if (MSSAU) {891 MSSAU->applyUpdates(Updates, *DT);892 if (VerifyMemorySSA)893 MSSAU->getMemorySSA()->verifyMemorySSA();894 }895 }896 897 if (LI) {898 if (Loop *BBLoop = LI->getLoopFor(BB)) {899 // If one or the other blocks were not in a loop, the new block is not900 // either, and thus LI doesn't need to be updated.901 if (Loop *SuccLoop = LI->getLoopFor(Succ)) {902 if (BBLoop == SuccLoop) {903 // Both in the same loop, the NewBB joins loop.904 SuccLoop->addBasicBlockToLoop(NewBB, *LI);905 } else if (BBLoop->contains(SuccLoop)) {906 // Edge from an outer loop to an inner loop. Add to the outer loop.907 BBLoop->addBasicBlockToLoop(NewBB, *LI);908 } else if (SuccLoop->contains(BBLoop)) {909 // Edge from an inner loop to an outer loop. Add to the outer loop.910 SuccLoop->addBasicBlockToLoop(NewBB, *LI);911 } else {912 // Edge from two loops with no containment relation. Because these913 // are natural loops, we know that the destination block must be the914 // header of its loop (adding a branch into a loop elsewhere would915 // create an irreducible loop).916 assert(SuccLoop->getHeader() == Succ &&917 "Should not create irreducible loops!");918 if (Loop *P = SuccLoop->getParentLoop())919 P->addBasicBlockToLoop(NewBB, *LI);920 }921 }922 923 // If BB is in a loop and Succ is outside of that loop, we may need to924 // update LoopSimplify form and LCSSA form.925 if (!BBLoop->contains(Succ)) {926 assert(!BBLoop->contains(NewBB) &&927 "Split point for loop exit is contained in loop!");928 929 // Update LCSSA form in the newly created exit block.930 if (Options.PreserveLCSSA) {931 createPHIsForSplitLoopExit(BB, NewBB, Succ);932 }933 934 if (!LoopPreds.empty()) {935 BasicBlock *NewExitBB = SplitBlockPredecessors(936 Succ, LoopPreds, "split", DT, LI, MSSAU, Options.PreserveLCSSA);937 if (Options.PreserveLCSSA)938 createPHIsForSplitLoopExit(LoopPreds, NewExitBB, Succ);939 }940 }941 }942 }943 944 return NewBB;945}946 947void llvm::createPHIsForSplitLoopExit(ArrayRef<BasicBlock *> Preds,948 BasicBlock *SplitBB, BasicBlock *DestBB) {949 // SplitBB shouldn't have anything non-trivial in it yet.950 assert((&*SplitBB->getFirstNonPHIIt() == SplitBB->getTerminator() ||951 SplitBB->isLandingPad()) &&952 "SplitBB has non-PHI nodes!");953 954 // For each PHI in the destination block.955 for (PHINode &PN : DestBB->phis()) {956 int Idx = PN.getBasicBlockIndex(SplitBB);957 assert(Idx >= 0 && "Invalid Block Index");958 Value *V = PN.getIncomingValue(Idx);959 960 // If the input is a PHI which already satisfies LCSSA, don't create961 // a new one.962 if (const PHINode *VP = dyn_cast<PHINode>(V))963 if (VP->getParent() == SplitBB)964 continue;965 966 // Otherwise a new PHI is needed. Create one and populate it.967 PHINode *NewPN = PHINode::Create(PN.getType(), Preds.size(), "split");968 BasicBlock::iterator InsertPos =969 SplitBB->isLandingPad() ? SplitBB->begin()970 : SplitBB->getTerminator()->getIterator();971 NewPN->insertBefore(InsertPos);972 for (BasicBlock *BB : Preds)973 NewPN->addIncoming(V, BB);974 975 // Update the original PHI.976 PN.setIncomingValue(Idx, NewPN);977 }978}979 980unsigned981llvm::SplitAllCriticalEdges(Function &F,982 const CriticalEdgeSplittingOptions &Options) {983 unsigned NumBroken = 0;984 for (BasicBlock &BB : F) {985 Instruction *TI = BB.getTerminator();986 if (TI->getNumSuccessors() > 1 && !isa<IndirectBrInst>(TI))987 for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i)988 if (SplitCriticalEdge(TI, i, Options))989 ++NumBroken;990 }991 return NumBroken;992}993 994static BasicBlock *SplitBlockImpl(BasicBlock *Old, BasicBlock::iterator SplitPt,995 DomTreeUpdater *DTU, DominatorTree *DT,996 LoopInfo *LI, MemorySSAUpdater *MSSAU,997 const Twine &BBName, bool Before) {998 if (Before) {999 DomTreeUpdater LocalDTU(DT, DomTreeUpdater::UpdateStrategy::Lazy);1000 return splitBlockBefore(Old, SplitPt,1001 DTU ? DTU : (DT ? &LocalDTU : nullptr), LI, MSSAU,1002 BBName);1003 }1004 BasicBlock::iterator SplitIt = SplitPt;1005 while (isa<PHINode>(SplitIt) || SplitIt->isEHPad()) {1006 ++SplitIt;1007 assert(SplitIt != SplitPt->getParent()->end());1008 }1009 std::string Name = BBName.str();1010 BasicBlock *New = Old->splitBasicBlock(1011 SplitIt, Name.empty() ? Old->getName() + ".split" : Name);1012 1013 // The new block lives in whichever loop the old one did. This preserves1014 // LCSSA as well, because we force the split point to be after any PHI nodes.1015 if (LI)1016 if (Loop *L = LI->getLoopFor(Old))1017 L->addBasicBlockToLoop(New, *LI);1018 1019 if (DTU) {1020 SmallVector<DominatorTree::UpdateType, 8> Updates;1021 // Old dominates New. New node dominates all other nodes dominated by Old.1022 SmallPtrSet<BasicBlock *, 8> UniqueSuccessorsOfOld;1023 Updates.push_back({DominatorTree::Insert, Old, New});1024 Updates.reserve(Updates.size() + 2 * succ_size(New));1025 for (BasicBlock *SuccessorOfOld : successors(New))1026 if (UniqueSuccessorsOfOld.insert(SuccessorOfOld).second) {1027 Updates.push_back({DominatorTree::Insert, New, SuccessorOfOld});1028 Updates.push_back({DominatorTree::Delete, Old, SuccessorOfOld});1029 }1030 1031 DTU->applyUpdates(Updates);1032 } else if (DT)1033 // Old dominates New. New node dominates all other nodes dominated by Old.1034 if (DomTreeNode *OldNode = DT->getNode(Old)) {1035 std::vector<DomTreeNode *> Children(OldNode->begin(), OldNode->end());1036 1037 DomTreeNode *NewNode = DT->addNewBlock(New, Old);1038 for (DomTreeNode *I : Children)1039 DT->changeImmediateDominator(I, NewNode);1040 }1041 1042 // Move MemoryAccesses still tracked in Old, but part of New now.1043 // Update accesses in successor blocks accordingly.1044 if (MSSAU)1045 MSSAU->moveAllAfterSpliceBlocks(Old, New, &*(New->begin()));1046 1047 return New;1048}1049 1050BasicBlock *llvm::SplitBlock(BasicBlock *Old, BasicBlock::iterator SplitPt,1051 DominatorTree *DT, LoopInfo *LI,1052 MemorySSAUpdater *MSSAU, const Twine &BBName,1053 bool Before) {1054 return SplitBlockImpl(Old, SplitPt, /*DTU=*/nullptr, DT, LI, MSSAU, BBName,1055 Before);1056}1057BasicBlock *llvm::SplitBlock(BasicBlock *Old, BasicBlock::iterator SplitPt,1058 DomTreeUpdater *DTU, LoopInfo *LI,1059 MemorySSAUpdater *MSSAU, const Twine &BBName,1060 bool Before) {1061 return SplitBlockImpl(Old, SplitPt, DTU, /*DT=*/nullptr, LI, MSSAU, BBName,1062 Before);1063}1064 1065BasicBlock *llvm::splitBlockBefore(BasicBlock *Old, BasicBlock::iterator SplitPt,1066 DomTreeUpdater *DTU, LoopInfo *LI,1067 MemorySSAUpdater *MSSAU,1068 const Twine &BBName) {1069 1070 BasicBlock::iterator SplitIt = SplitPt;1071 while (isa<PHINode>(SplitIt) || SplitIt->isEHPad())1072 ++SplitIt;1073 std::string Name = BBName.str();1074 BasicBlock *New = Old->splitBasicBlock(1075 SplitIt, Name.empty() ? Old->getName() + ".split" : Name,1076 /* Before=*/true);1077 1078 // The new block lives in whichever loop the old one did. This preserves1079 // LCSSA as well, because we force the split point to be after any PHI nodes.1080 if (LI)1081 if (Loop *L = LI->getLoopFor(Old))1082 L->addBasicBlockToLoop(New, *LI);1083 1084 if (DTU) {1085 SmallVector<DominatorTree::UpdateType, 8> DTUpdates;1086 // New dominates Old. The predecessor nodes of the Old node dominate1087 // New node.1088 SmallPtrSet<BasicBlock *, 8> UniquePredecessorsOfOld;1089 DTUpdates.push_back({DominatorTree::Insert, New, Old});1090 DTUpdates.reserve(DTUpdates.size() + 2 * pred_size(New));1091 for (BasicBlock *PredecessorOfOld : predecessors(New))1092 if (UniquePredecessorsOfOld.insert(PredecessorOfOld).second) {1093 DTUpdates.push_back({DominatorTree::Insert, PredecessorOfOld, New});1094 DTUpdates.push_back({DominatorTree::Delete, PredecessorOfOld, Old});1095 }1096 1097 DTU->applyUpdates(DTUpdates);1098 1099 // Move MemoryAccesses still tracked in Old, but part of New now.1100 // Update accesses in successor blocks accordingly.1101 if (MSSAU) {1102 MSSAU->applyUpdates(DTUpdates, DTU->getDomTree());1103 if (VerifyMemorySSA)1104 MSSAU->getMemorySSA()->verifyMemorySSA();1105 }1106 }1107 return New;1108}1109 1110/// Update DominatorTree, LoopInfo, and LCCSA analysis information.1111/// Invalidates DFS Numbering when DTU or DT is provided.1112static void UpdateAnalysisInformation(BasicBlock *OldBB, BasicBlock *NewBB,1113 ArrayRef<BasicBlock *> Preds,1114 DomTreeUpdater *DTU, DominatorTree *DT,1115 LoopInfo *LI, MemorySSAUpdater *MSSAU,1116 bool PreserveLCSSA, bool &HasLoopExit) {1117 // Update dominator tree if available.1118 if (DTU) {1119 // Recalculation of DomTree is needed when updating a forward DomTree and1120 // the Entry BB is replaced.1121 if (NewBB->isEntryBlock() && DTU->hasDomTree()) {1122 // The entry block was removed and there is no external interface for1123 // the dominator tree to be notified of this change. In this corner-case1124 // we recalculate the entire tree.1125 DTU->recalculate(*NewBB->getParent());1126 } else {1127 // Split block expects NewBB to have a non-empty set of predecessors.1128 SmallVector<DominatorTree::UpdateType, 8> Updates;1129 SmallPtrSet<BasicBlock *, 8> UniquePreds;1130 Updates.push_back({DominatorTree::Insert, NewBB, OldBB});1131 Updates.reserve(Updates.size() + 2 * Preds.size());1132 for (auto *Pred : Preds)1133 if (UniquePreds.insert(Pred).second) {1134 Updates.push_back({DominatorTree::Insert, Pred, NewBB});1135 Updates.push_back({DominatorTree::Delete, Pred, OldBB});1136 }1137 DTU->applyUpdates(Updates);1138 }1139 } else if (DT) {1140 if (OldBB == DT->getRootNode()->getBlock()) {1141 assert(NewBB->isEntryBlock());1142 DT->setNewRoot(NewBB);1143 } else {1144 // Split block expects NewBB to have a non-empty set of predecessors.1145 DT->splitBlock(NewBB);1146 }1147 }1148 1149 // Update MemoryPhis after split if MemorySSA is available1150 if (MSSAU)1151 MSSAU->wireOldPredecessorsToNewImmediatePredecessor(OldBB, NewBB, Preds);1152 1153 // The rest of the logic is only relevant for updating the loop structures.1154 if (!LI)1155 return;1156 1157 if (DTU && DTU->hasDomTree())1158 DT = &DTU->getDomTree();1159 assert(DT && "DT should be available to update LoopInfo!");1160 Loop *L = LI->getLoopFor(OldBB);1161 1162 // If we need to preserve loop analyses, collect some information about how1163 // this split will affect loops.1164 bool IsLoopEntry = !!L;1165 bool SplitMakesNewLoopHeader = false;1166 for (BasicBlock *Pred : Preds) {1167 // Preds that are not reachable from entry should not be used to identify if1168 // OldBB is a loop entry or if SplitMakesNewLoopHeader. Unreachable blocks1169 // are not within any loops, so we incorrectly mark SplitMakesNewLoopHeader1170 // as true and make the NewBB the header of some loop. This breaks LI.1171 if (!DT->isReachableFromEntry(Pred))1172 continue;1173 // If we need to preserve LCSSA, determine if any of the preds is a loop1174 // exit.1175 if (PreserveLCSSA)1176 if (Loop *PL = LI->getLoopFor(Pred))1177 if (!PL->contains(OldBB))1178 HasLoopExit = true;1179 1180 // If we need to preserve LoopInfo, note whether any of the preds crosses1181 // an interesting loop boundary.1182 if (!L)1183 continue;1184 if (L->contains(Pred))1185 IsLoopEntry = false;1186 else1187 SplitMakesNewLoopHeader = true;1188 }1189 1190 // Unless we have a loop for OldBB, nothing else to do here.1191 if (!L)1192 return;1193 1194 if (IsLoopEntry) {1195 // Add the new block to the nearest enclosing loop (and not an adjacent1196 // loop). To find this, examine each of the predecessors and determine which1197 // loops enclose them, and select the most-nested loop which contains the1198 // loop containing the block being split.1199 Loop *InnermostPredLoop = nullptr;1200 for (BasicBlock *Pred : Preds) {1201 if (Loop *PredLoop = LI->getLoopFor(Pred)) {1202 // Seek a loop which actually contains the block being split (to avoid1203 // adjacent loops).1204 while (PredLoop && !PredLoop->contains(OldBB))1205 PredLoop = PredLoop->getParentLoop();1206 1207 // Select the most-nested of these loops which contains the block.1208 if (PredLoop && PredLoop->contains(OldBB) &&1209 (!InnermostPredLoop ||1210 InnermostPredLoop->getLoopDepth() < PredLoop->getLoopDepth()))1211 InnermostPredLoop = PredLoop;1212 }1213 }1214 1215 if (InnermostPredLoop)1216 InnermostPredLoop->addBasicBlockToLoop(NewBB, *LI);1217 } else {1218 L->addBasicBlockToLoop(NewBB, *LI);1219 if (SplitMakesNewLoopHeader)1220 L->moveToHeader(NewBB);1221 }1222}1223 1224/// Update the PHI nodes in OrigBB to include the values coming from NewBB.1225/// This also updates AliasAnalysis, if available.1226static void UpdatePHINodes(BasicBlock *OrigBB, BasicBlock *NewBB,1227 ArrayRef<BasicBlock *> Preds, BranchInst *BI,1228 bool HasLoopExit) {1229 // Otherwise, create a new PHI node in NewBB for each PHI node in OrigBB.1230 SmallPtrSet<BasicBlock *, 16> PredSet(llvm::from_range, Preds);1231 for (BasicBlock::iterator I = OrigBB->begin(); isa<PHINode>(I); ) {1232 PHINode *PN = cast<PHINode>(I++);1233 1234 // Check to see if all of the values coming in are the same. If so, we1235 // don't need to create a new PHI node, unless it's needed for LCSSA.1236 Value *InVal = nullptr;1237 if (!HasLoopExit) {1238 InVal = PN->getIncomingValueForBlock(Preds[0]);1239 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {1240 if (!PredSet.count(PN->getIncomingBlock(i)))1241 continue;1242 if (!InVal)1243 InVal = PN->getIncomingValue(i);1244 else if (InVal != PN->getIncomingValue(i)) {1245 InVal = nullptr;1246 break;1247 }1248 }1249 }1250 1251 if (InVal) {1252 // If all incoming values for the new PHI would be the same, just don't1253 // make a new PHI. Instead, just remove the incoming values from the old1254 // PHI.1255 PN->removeIncomingValueIf(1256 [&](unsigned Idx) {1257 return PredSet.contains(PN->getIncomingBlock(Idx));1258 },1259 /* DeletePHIIfEmpty */ false);1260 1261 // Add an incoming value to the PHI node in the loop for the preheader1262 // edge.1263 PN->addIncoming(InVal, NewBB);1264 continue;1265 }1266 1267 // If the values coming into the block are not the same, we need a new1268 // PHI.1269 // Create the new PHI node, insert it into NewBB at the end of the block1270 PHINode *NewPHI =1271 PHINode::Create(PN->getType(), Preds.size(), PN->getName() + ".ph", BI->getIterator());1272 1273 // NOTE! This loop walks backwards for a reason! First off, this minimizes1274 // the cost of removal if we end up removing a large number of values, and1275 // second off, this ensures that the indices for the incoming values aren't1276 // invalidated when we remove one.1277 for (int64_t i = PN->getNumIncomingValues() - 1; i >= 0; --i) {1278 BasicBlock *IncomingBB = PN->getIncomingBlock(i);1279 if (PredSet.count(IncomingBB)) {1280 Value *V = PN->removeIncomingValue(i, false);1281 NewPHI->addIncoming(V, IncomingBB);1282 }1283 }1284 1285 PN->addIncoming(NewPHI, NewBB);1286 }1287}1288 1289static void SplitLandingPadPredecessorsImpl(1290 BasicBlock *OrigBB, ArrayRef<BasicBlock *> Preds, const char *Suffix1,1291 const char *Suffix2, SmallVectorImpl<BasicBlock *> &NewBBs,1292 DomTreeUpdater *DTU, DominatorTree *DT, LoopInfo *LI,1293 MemorySSAUpdater *MSSAU, bool PreserveLCSSA);1294 1295static BasicBlock *1296SplitBlockPredecessorsImpl(BasicBlock *BB, ArrayRef<BasicBlock *> Preds,1297 const char *Suffix, DomTreeUpdater *DTU,1298 DominatorTree *DT, LoopInfo *LI,1299 MemorySSAUpdater *MSSAU, bool PreserveLCSSA) {1300 // Do not attempt to split that which cannot be split.1301 if (!BB->canSplitPredecessors())1302 return nullptr;1303 1304 // For the landingpads we need to act a bit differently.1305 // Delegate this work to the SplitLandingPadPredecessors.1306 if (BB->isLandingPad()) {1307 SmallVector<BasicBlock*, 2> NewBBs;1308 std::string NewName = std::string(Suffix) + ".split-lp";1309 1310 SplitLandingPadPredecessorsImpl(BB, Preds, Suffix, NewName.c_str(), NewBBs,1311 DTU, DT, LI, MSSAU, PreserveLCSSA);1312 return NewBBs[0];1313 }1314 1315 // Create new basic block, insert right before the original block.1316 BasicBlock *NewBB = BasicBlock::Create(1317 BB->getContext(), BB->getName() + Suffix, BB->getParent(), BB);1318 1319 // The new block unconditionally branches to the old block.1320 BranchInst *BI = BranchInst::Create(BB, NewBB);1321 1322 Loop *L = nullptr;1323 BasicBlock *OldLatch = nullptr;1324 // Splitting the predecessors of a loop header creates a preheader block.1325 if (LI && LI->isLoopHeader(BB)) {1326 L = LI->getLoopFor(BB);1327 // Using the loop start line number prevents debuggers stepping into the1328 // loop body for this instruction.1329 BI->setDebugLoc(L->getStartLoc());1330 1331 // If BB is the header of the Loop, it is possible that the loop is1332 // modified, such that the current latch does not remain the latch of the1333 // loop. If that is the case, the loop metadata from the current latch needs1334 // to be applied to the new latch.1335 OldLatch = L->getLoopLatch();1336 } else1337 BI->setDebugLoc(BB->getFirstNonPHIOrDbg()->getDebugLoc());1338 1339 // Move the edges from Preds to point to NewBB instead of BB.1340 for (BasicBlock *Pred : Preds) {1341 // This is slightly more strict than necessary; the minimum requirement1342 // is that there be no more than one indirectbr branching to BB. And1343 // all BlockAddress uses would need to be updated.1344 assert(!isa<IndirectBrInst>(Pred->getTerminator()) &&1345 "Cannot split an edge from an IndirectBrInst");1346 Pred->getTerminator()->replaceSuccessorWith(BB, NewBB);1347 }1348 1349 // Insert a new PHI node into NewBB for every PHI node in BB and that new PHI1350 // node becomes an incoming value for BB's phi node. However, if the Preds1351 // list is empty, we need to insert dummy entries into the PHI nodes in BB to1352 // account for the newly created predecessor.1353 if (Preds.empty()) {1354 // Insert dummy values as the incoming value.1355 for (BasicBlock::iterator I = BB->begin(); isa<PHINode>(I); ++I)1356 cast<PHINode>(I)->addIncoming(PoisonValue::get(I->getType()), NewBB);1357 }1358 1359 // Update DominatorTree, LoopInfo, and LCCSA analysis information.1360 bool HasLoopExit = false;1361 UpdateAnalysisInformation(BB, NewBB, Preds, DTU, DT, LI, MSSAU, PreserveLCSSA,1362 HasLoopExit);1363 1364 if (!Preds.empty()) {1365 // Update the PHI nodes in BB with the values coming from NewBB.1366 UpdatePHINodes(BB, NewBB, Preds, BI, HasLoopExit);1367 }1368 1369 if (OldLatch) {1370 BasicBlock *NewLatch = L->getLoopLatch();1371 if (NewLatch != OldLatch) {1372 MDNode *MD = OldLatch->getTerminator()->getMetadata(LLVMContext::MD_loop);1373 NewLatch->getTerminator()->setMetadata(LLVMContext::MD_loop, MD);1374 // It's still possible that OldLatch is the latch of another inner loop,1375 // in which case we do not remove the metadata.1376 Loop *IL = LI->getLoopFor(OldLatch);1377 if (IL && IL->getLoopLatch() != OldLatch)1378 OldLatch->getTerminator()->setMetadata(LLVMContext::MD_loop, nullptr);1379 }1380 }1381 1382 return NewBB;1383}1384 1385BasicBlock *llvm::SplitBlockPredecessors(BasicBlock *BB,1386 ArrayRef<BasicBlock *> Preds,1387 const char *Suffix, DominatorTree *DT,1388 LoopInfo *LI, MemorySSAUpdater *MSSAU,1389 bool PreserveLCSSA) {1390 return SplitBlockPredecessorsImpl(BB, Preds, Suffix, /*DTU=*/nullptr, DT, LI,1391 MSSAU, PreserveLCSSA);1392}1393BasicBlock *llvm::SplitBlockPredecessors(BasicBlock *BB,1394 ArrayRef<BasicBlock *> Preds,1395 const char *Suffix,1396 DomTreeUpdater *DTU, LoopInfo *LI,1397 MemorySSAUpdater *MSSAU,1398 bool PreserveLCSSA) {1399 return SplitBlockPredecessorsImpl(BB, Preds, Suffix, DTU,1400 /*DT=*/nullptr, LI, MSSAU, PreserveLCSSA);1401}1402 1403static void SplitLandingPadPredecessorsImpl(1404 BasicBlock *OrigBB, ArrayRef<BasicBlock *> Preds, const char *Suffix1,1405 const char *Suffix2, SmallVectorImpl<BasicBlock *> &NewBBs,1406 DomTreeUpdater *DTU, DominatorTree *DT, LoopInfo *LI,1407 MemorySSAUpdater *MSSAU, bool PreserveLCSSA) {1408 assert(OrigBB->isLandingPad() && "Trying to split a non-landing pad!");1409 1410 // Create a new basic block for OrigBB's predecessors listed in Preds. Insert1411 // it right before the original block.1412 BasicBlock *NewBB1 = BasicBlock::Create(OrigBB->getContext(),1413 OrigBB->getName() + Suffix1,1414 OrigBB->getParent(), OrigBB);1415 NewBBs.push_back(NewBB1);1416 1417 // The new block unconditionally branches to the old block.1418 BranchInst *BI1 = BranchInst::Create(OrigBB, NewBB1);1419 BI1->setDebugLoc(OrigBB->getFirstNonPHIIt()->getDebugLoc());1420 1421 // Move the edges from Preds to point to NewBB1 instead of OrigBB.1422 for (BasicBlock *Pred : Preds) {1423 // This is slightly more strict than necessary; the minimum requirement1424 // is that there be no more than one indirectbr branching to BB. And1425 // all BlockAddress uses would need to be updated.1426 assert(!isa<IndirectBrInst>(Pred->getTerminator()) &&1427 "Cannot split an edge from an IndirectBrInst");1428 Pred->getTerminator()->replaceUsesOfWith(OrigBB, NewBB1);1429 }1430 1431 bool HasLoopExit = false;1432 UpdateAnalysisInformation(OrigBB, NewBB1, Preds, DTU, DT, LI, MSSAU,1433 PreserveLCSSA, HasLoopExit);1434 1435 // Update the PHI nodes in OrigBB with the values coming from NewBB1.1436 UpdatePHINodes(OrigBB, NewBB1, Preds, BI1, HasLoopExit);1437 1438 // Move the remaining edges from OrigBB to point to NewBB2.1439 SmallVector<BasicBlock*, 8> NewBB2Preds;1440 for (pred_iterator i = pred_begin(OrigBB), e = pred_end(OrigBB);1441 i != e; ) {1442 BasicBlock *Pred = *i++;1443 if (Pred == NewBB1) continue;1444 assert(!isa<IndirectBrInst>(Pred->getTerminator()) &&1445 "Cannot split an edge from an IndirectBrInst");1446 NewBB2Preds.push_back(Pred);1447 e = pred_end(OrigBB);1448 }1449 1450 BasicBlock *NewBB2 = nullptr;1451 if (!NewBB2Preds.empty()) {1452 // Create another basic block for the rest of OrigBB's predecessors.1453 NewBB2 = BasicBlock::Create(OrigBB->getContext(),1454 OrigBB->getName() + Suffix2,1455 OrigBB->getParent(), OrigBB);1456 NewBBs.push_back(NewBB2);1457 1458 // The new block unconditionally branches to the old block.1459 BranchInst *BI2 = BranchInst::Create(OrigBB, NewBB2);1460 BI2->setDebugLoc(OrigBB->getFirstNonPHIIt()->getDebugLoc());1461 1462 // Move the remaining edges from OrigBB to point to NewBB2.1463 for (BasicBlock *NewBB2Pred : NewBB2Preds)1464 NewBB2Pred->getTerminator()->replaceUsesOfWith(OrigBB, NewBB2);1465 1466 // Update DominatorTree, LoopInfo, and LCCSA analysis information.1467 HasLoopExit = false;1468 UpdateAnalysisInformation(OrigBB, NewBB2, NewBB2Preds, DTU, DT, LI, MSSAU,1469 PreserveLCSSA, HasLoopExit);1470 1471 // Update the PHI nodes in OrigBB with the values coming from NewBB2.1472 UpdatePHINodes(OrigBB, NewBB2, NewBB2Preds, BI2, HasLoopExit);1473 }1474 1475 LandingPadInst *LPad = OrigBB->getLandingPadInst();1476 Instruction *Clone1 = LPad->clone();1477 Clone1->setName(Twine("lpad") + Suffix1);1478 Clone1->insertInto(NewBB1, NewBB1->getFirstInsertionPt());1479 1480 if (NewBB2) {1481 Instruction *Clone2 = LPad->clone();1482 Clone2->setName(Twine("lpad") + Suffix2);1483 Clone2->insertInto(NewBB2, NewBB2->getFirstInsertionPt());1484 1485 // Create a PHI node for the two cloned landingpad instructions only1486 // if the original landingpad instruction has some uses.1487 if (!LPad->use_empty()) {1488 assert(!LPad->getType()->isTokenTy() &&1489 "Split cannot be applied if LPad is token type. Otherwise an "1490 "invalid PHINode of token type would be created.");1491 PHINode *PN = PHINode::Create(LPad->getType(), 2, "lpad.phi", LPad->getIterator());1492 PN->addIncoming(Clone1, NewBB1);1493 PN->addIncoming(Clone2, NewBB2);1494 LPad->replaceAllUsesWith(PN);1495 }1496 LPad->eraseFromParent();1497 } else {1498 // There is no second clone. Just replace the landing pad with the first1499 // clone.1500 LPad->replaceAllUsesWith(Clone1);1501 LPad->eraseFromParent();1502 }1503}1504 1505void llvm::SplitLandingPadPredecessors(BasicBlock *OrigBB,1506 ArrayRef<BasicBlock *> Preds,1507 const char *Suffix1, const char *Suffix2,1508 SmallVectorImpl<BasicBlock *> &NewBBs,1509 DomTreeUpdater *DTU, LoopInfo *LI,1510 MemorySSAUpdater *MSSAU,1511 bool PreserveLCSSA) {1512 return SplitLandingPadPredecessorsImpl(OrigBB, Preds, Suffix1, Suffix2,1513 NewBBs, DTU, /*DT=*/nullptr, LI, MSSAU,1514 PreserveLCSSA);1515}1516 1517ReturnInst *llvm::FoldReturnIntoUncondBranch(ReturnInst *RI, BasicBlock *BB,1518 BasicBlock *Pred,1519 DomTreeUpdater *DTU) {1520 Instruction *UncondBranch = Pred->getTerminator();1521 // Clone the return and add it to the end of the predecessor.1522 Instruction *NewRet = RI->clone();1523 NewRet->insertInto(Pred, Pred->end());1524 1525 // If the return instruction returns a value, and if the value was a1526 // PHI node in "BB", propagate the right value into the return.1527 for (Use &Op : NewRet->operands()) {1528 Value *V = Op;1529 Instruction *NewBC = nullptr;1530 if (BitCastInst *BCI = dyn_cast<BitCastInst>(V)) {1531 // Return value might be bitcasted. Clone and insert it before the1532 // return instruction.1533 V = BCI->getOperand(0);1534 NewBC = BCI->clone();1535 NewBC->insertInto(Pred, NewRet->getIterator());1536 Op = NewBC;1537 }1538 1539 Instruction *NewEV = nullptr;1540 if (ExtractValueInst *EVI = dyn_cast<ExtractValueInst>(V)) {1541 V = EVI->getOperand(0);1542 NewEV = EVI->clone();1543 if (NewBC) {1544 NewBC->setOperand(0, NewEV);1545 NewEV->insertInto(Pred, NewBC->getIterator());1546 } else {1547 NewEV->insertInto(Pred, NewRet->getIterator());1548 Op = NewEV;1549 }1550 }1551 1552 if (PHINode *PN = dyn_cast<PHINode>(V)) {1553 if (PN->getParent() == BB) {1554 if (NewEV) {1555 NewEV->setOperand(0, PN->getIncomingValueForBlock(Pred));1556 } else if (NewBC)1557 NewBC->setOperand(0, PN->getIncomingValueForBlock(Pred));1558 else1559 Op = PN->getIncomingValueForBlock(Pred);1560 }1561 }1562 }1563 1564 // Update any PHI nodes in the returning block to realize that we no1565 // longer branch to them.1566 BB->removePredecessor(Pred);1567 UncondBranch->eraseFromParent();1568 1569 if (DTU)1570 DTU->applyUpdates({{DominatorTree::Delete, Pred, BB}});1571 1572 return cast<ReturnInst>(NewRet);1573}1574 1575Instruction *llvm::SplitBlockAndInsertIfThen(Value *Cond,1576 BasicBlock::iterator SplitBefore,1577 bool Unreachable,1578 MDNode *BranchWeights,1579 DomTreeUpdater *DTU, LoopInfo *LI,1580 BasicBlock *ThenBlock) {1581 SplitBlockAndInsertIfThenElse(1582 Cond, SplitBefore, &ThenBlock, /* ElseBlock */ nullptr,1583 /* UnreachableThen */ Unreachable,1584 /* UnreachableElse */ false, BranchWeights, DTU, LI);1585 return ThenBlock->getTerminator();1586}1587 1588Instruction *llvm::SplitBlockAndInsertIfElse(Value *Cond,1589 BasicBlock::iterator SplitBefore,1590 bool Unreachable,1591 MDNode *BranchWeights,1592 DomTreeUpdater *DTU, LoopInfo *LI,1593 BasicBlock *ElseBlock) {1594 SplitBlockAndInsertIfThenElse(1595 Cond, SplitBefore, /* ThenBlock */ nullptr, &ElseBlock,1596 /* UnreachableThen */ false,1597 /* UnreachableElse */ Unreachable, BranchWeights, DTU, LI);1598 return ElseBlock->getTerminator();1599}1600 1601void llvm::SplitBlockAndInsertIfThenElse(Value *Cond, BasicBlock::iterator SplitBefore,1602 Instruction **ThenTerm,1603 Instruction **ElseTerm,1604 MDNode *BranchWeights,1605 DomTreeUpdater *DTU, LoopInfo *LI) {1606 BasicBlock *ThenBlock = nullptr;1607 BasicBlock *ElseBlock = nullptr;1608 SplitBlockAndInsertIfThenElse(1609 Cond, SplitBefore, &ThenBlock, &ElseBlock, /* UnreachableThen */ false,1610 /* UnreachableElse */ false, BranchWeights, DTU, LI);1611 1612 *ThenTerm = ThenBlock->getTerminator();1613 *ElseTerm = ElseBlock->getTerminator();1614}1615 1616void llvm::SplitBlockAndInsertIfThenElse(1617 Value *Cond, BasicBlock::iterator SplitBefore, BasicBlock **ThenBlock,1618 BasicBlock **ElseBlock, bool UnreachableThen, bool UnreachableElse,1619 MDNode *BranchWeights, DomTreeUpdater *DTU, LoopInfo *LI) {1620 assert((ThenBlock || ElseBlock) &&1621 "At least one branch block must be created");1622 assert((!UnreachableThen || !UnreachableElse) &&1623 "Split block tail must be reachable");1624 1625 SmallVector<DominatorTree::UpdateType, 8> Updates;1626 SmallPtrSet<BasicBlock *, 8> UniqueOrigSuccessors;1627 BasicBlock *Head = SplitBefore->getParent();1628 if (DTU) {1629 UniqueOrigSuccessors.insert_range(successors(Head));1630 Updates.reserve(4 + 2 * UniqueOrigSuccessors.size());1631 }1632 1633 LLVMContext &C = Head->getContext();1634 BasicBlock *Tail = Head->splitBasicBlock(SplitBefore);1635 BasicBlock *TrueBlock = Tail;1636 BasicBlock *FalseBlock = Tail;1637 bool ThenToTailEdge = false;1638 bool ElseToTailEdge = false;1639 1640 // Encapsulate the logic around creation/insertion/etc of a new block.1641 auto handleBlock = [&](BasicBlock **PBB, bool Unreachable, BasicBlock *&BB,1642 bool &ToTailEdge) {1643 if (PBB == nullptr)1644 return; // Do not create/insert a block.1645 1646 if (*PBB)1647 BB = *PBB; // Caller supplied block, use it.1648 else {1649 // Create a new block.1650 BB = BasicBlock::Create(C, "", Head->getParent(), Tail);1651 if (Unreachable)1652 (void)new UnreachableInst(C, BB);1653 else {1654 (void)BranchInst::Create(Tail, BB);1655 ToTailEdge = true;1656 }1657 BB->getTerminator()->setDebugLoc(SplitBefore->getDebugLoc());1658 // Pass the new block back to the caller.1659 *PBB = BB;1660 }1661 };1662 1663 handleBlock(ThenBlock, UnreachableThen, TrueBlock, ThenToTailEdge);1664 handleBlock(ElseBlock, UnreachableElse, FalseBlock, ElseToTailEdge);1665 1666 Instruction *HeadOldTerm = Head->getTerminator();1667 BranchInst *HeadNewTerm =1668 BranchInst::Create(/*ifTrue*/ TrueBlock, /*ifFalse*/ FalseBlock, Cond);1669 HeadNewTerm->setMetadata(LLVMContext::MD_prof, BranchWeights);1670 ReplaceInstWithInst(HeadOldTerm, HeadNewTerm);1671 1672 if (DTU) {1673 Updates.emplace_back(DominatorTree::Insert, Head, TrueBlock);1674 Updates.emplace_back(DominatorTree::Insert, Head, FalseBlock);1675 if (ThenToTailEdge)1676 Updates.emplace_back(DominatorTree::Insert, TrueBlock, Tail);1677 if (ElseToTailEdge)1678 Updates.emplace_back(DominatorTree::Insert, FalseBlock, Tail);1679 for (BasicBlock *UniqueOrigSuccessor : UniqueOrigSuccessors)1680 Updates.emplace_back(DominatorTree::Insert, Tail, UniqueOrigSuccessor);1681 for (BasicBlock *UniqueOrigSuccessor : UniqueOrigSuccessors)1682 Updates.emplace_back(DominatorTree::Delete, Head, UniqueOrigSuccessor);1683 DTU->applyUpdates(Updates);1684 }1685 1686 if (LI) {1687 if (Loop *L = LI->getLoopFor(Head); L) {1688 if (ThenToTailEdge)1689 L->addBasicBlockToLoop(TrueBlock, *LI);1690 if (ElseToTailEdge)1691 L->addBasicBlockToLoop(FalseBlock, *LI);1692 L->addBasicBlockToLoop(Tail, *LI);1693 }1694 }1695}1696 1697std::pair<Instruction *, Value *>1698llvm::SplitBlockAndInsertSimpleForLoop(Value *End,1699 BasicBlock::iterator SplitBefore) {1700 BasicBlock *LoopPred = SplitBefore->getParent();1701 BasicBlock *LoopBody = SplitBlock(SplitBefore->getParent(), SplitBefore);1702 BasicBlock *LoopExit = SplitBlock(SplitBefore->getParent(), SplitBefore);1703 1704 auto *Ty = End->getType();1705 auto &DL = SplitBefore->getDataLayout();1706 const unsigned Bitwidth = DL.getTypeSizeInBits(Ty);1707 1708 IRBuilder<> Builder(LoopBody->getTerminator());1709 auto *IV = Builder.CreatePHI(Ty, 2, "iv");1710 auto *IVNext =1711 Builder.CreateAdd(IV, ConstantInt::get(Ty, 1), IV->getName() + ".next",1712 /*HasNUW=*/true, /*HasNSW=*/Bitwidth != 2);1713 auto *IVCheck = Builder.CreateICmpEQ(IVNext, End,1714 IV->getName() + ".check");1715 Builder.CreateCondBr(IVCheck, LoopExit, LoopBody);1716 LoopBody->getTerminator()->eraseFromParent();1717 1718 // Populate the IV PHI.1719 IV->addIncoming(ConstantInt::get(Ty, 0), LoopPred);1720 IV->addIncoming(IVNext, LoopBody);1721 1722 return std::make_pair(&*LoopBody->getFirstNonPHIIt(), IV);1723}1724 1725void llvm::SplitBlockAndInsertForEachLane(1726 ElementCount EC, Type *IndexTy, BasicBlock::iterator InsertBefore,1727 std::function<void(IRBuilderBase &, Value *)> Func) {1728 1729 IRBuilder<> IRB(InsertBefore->getParent(), InsertBefore);1730 1731 if (EC.isScalable()) {1732 Value *NumElements = IRB.CreateElementCount(IndexTy, EC);1733 1734 auto [BodyIP, Index] =1735 SplitBlockAndInsertSimpleForLoop(NumElements, InsertBefore);1736 1737 IRB.SetInsertPoint(BodyIP);1738 Func(IRB, Index);1739 return;1740 }1741 1742 unsigned Num = EC.getFixedValue();1743 for (unsigned Idx = 0; Idx < Num; ++Idx) {1744 IRB.SetInsertPoint(InsertBefore);1745 Func(IRB, ConstantInt::get(IndexTy, Idx));1746 }1747}1748 1749void llvm::SplitBlockAndInsertForEachLane(1750 Value *EVL, BasicBlock::iterator InsertBefore,1751 std::function<void(IRBuilderBase &, Value *)> Func) {1752 1753 IRBuilder<> IRB(InsertBefore->getParent(), InsertBefore);1754 Type *Ty = EVL->getType();1755 1756 if (!isa<ConstantInt>(EVL)) {1757 auto [BodyIP, Index] = SplitBlockAndInsertSimpleForLoop(EVL, InsertBefore);1758 IRB.SetInsertPoint(BodyIP);1759 Func(IRB, Index);1760 return;1761 }1762 1763 unsigned Num = cast<ConstantInt>(EVL)->getZExtValue();1764 for (unsigned Idx = 0; Idx < Num; ++Idx) {1765 IRB.SetInsertPoint(InsertBefore);1766 Func(IRB, ConstantInt::get(Ty, Idx));1767 }1768}1769 1770BranchInst *llvm::GetIfCondition(BasicBlock *BB, BasicBlock *&IfTrue,1771 BasicBlock *&IfFalse) {1772 PHINode *SomePHI = dyn_cast<PHINode>(BB->begin());1773 BasicBlock *Pred1 = nullptr;1774 BasicBlock *Pred2 = nullptr;1775 1776 if (SomePHI) {1777 if (SomePHI->getNumIncomingValues() != 2)1778 return nullptr;1779 Pred1 = SomePHI->getIncomingBlock(0);1780 Pred2 = SomePHI->getIncomingBlock(1);1781 } else {1782 pred_iterator PI = pred_begin(BB), PE = pred_end(BB);1783 if (PI == PE) // No predecessor1784 return nullptr;1785 Pred1 = *PI++;1786 if (PI == PE) // Only one predecessor1787 return nullptr;1788 Pred2 = *PI++;1789 if (PI != PE) // More than two predecessors1790 return nullptr;1791 }1792 1793 // We can only handle branches. Other control flow will be lowered to1794 // branches if possible anyway.1795 BranchInst *Pred1Br = dyn_cast<BranchInst>(Pred1->getTerminator());1796 BranchInst *Pred2Br = dyn_cast<BranchInst>(Pred2->getTerminator());1797 if (!Pred1Br || !Pred2Br)1798 return nullptr;1799 1800 // Eliminate code duplication by ensuring that Pred1Br is conditional if1801 // either are.1802 if (Pred2Br->isConditional()) {1803 // If both branches are conditional, we don't have an "if statement". In1804 // reality, we could transform this case, but since the condition will be1805 // required anyway, we stand no chance of eliminating it, so the xform is1806 // probably not profitable.1807 if (Pred1Br->isConditional())1808 return nullptr;1809 1810 std::swap(Pred1, Pred2);1811 std::swap(Pred1Br, Pred2Br);1812 }1813 1814 if (Pred1Br->isConditional()) {1815 // The only thing we have to watch out for here is to make sure that Pred21816 // doesn't have incoming edges from other blocks. If it does, the condition1817 // doesn't dominate BB.1818 if (!Pred2->getSinglePredecessor())1819 return nullptr;1820 1821 // If we found a conditional branch predecessor, make sure that it branches1822 // to BB and Pred2Br. If it doesn't, this isn't an "if statement".1823 if (Pred1Br->getSuccessor(0) == BB &&1824 Pred1Br->getSuccessor(1) == Pred2) {1825 IfTrue = Pred1;1826 IfFalse = Pred2;1827 } else if (Pred1Br->getSuccessor(0) == Pred2 &&1828 Pred1Br->getSuccessor(1) == BB) {1829 IfTrue = Pred2;1830 IfFalse = Pred1;1831 } else {1832 // We know that one arm of the conditional goes to BB, so the other must1833 // go somewhere unrelated, and this must not be an "if statement".1834 return nullptr;1835 }1836 1837 return Pred1Br;1838 }1839 1840 // Ok, if we got here, both predecessors end with an unconditional branch to1841 // BB. Don't panic! If both blocks only have a single (identical)1842 // predecessor, and THAT is a conditional branch, then we're all ok!1843 BasicBlock *CommonPred = Pred1->getSinglePredecessor();1844 if (CommonPred == nullptr || CommonPred != Pred2->getSinglePredecessor())1845 return nullptr;1846 1847 // Otherwise, if this is a conditional branch, then we can use it!1848 BranchInst *BI = dyn_cast<BranchInst>(CommonPred->getTerminator());1849 if (!BI) return nullptr;1850 1851 assert(BI->isConditional() && "Two successors but not conditional?");1852 if (BI->getSuccessor(0) == Pred1) {1853 IfTrue = Pred1;1854 IfFalse = Pred2;1855 } else {1856 IfTrue = Pred2;1857 IfFalse = Pred1;1858 }1859 return BI;1860}1861 1862void llvm::InvertBranch(BranchInst *PBI, IRBuilderBase &Builder) {1863 Value *NewCond = PBI->getCondition();1864 // If this is a "cmp" instruction, only used for branching (and nowhere1865 // else), then we can simply invert the predicate.1866 if (NewCond->hasOneUse() && isa<CmpInst>(NewCond)) {1867 CmpInst *CI = cast<CmpInst>(NewCond);1868 CI->setPredicate(CI->getInversePredicate());1869 } else1870 NewCond = Builder.CreateNot(NewCond, NewCond->getName() + ".not");1871 1872 PBI->setCondition(NewCond);1873 PBI->swapSuccessors();1874}1875 1876bool llvm::hasOnlySimpleTerminator(const Function &F) {1877 for (auto &BB : F) {1878 auto *Term = BB.getTerminator();1879 if (!(isa<ReturnInst>(Term) || isa<UnreachableInst>(Term) ||1880 isa<BranchInst>(Term)))1881 return false;1882 }1883 return true;1884}1885 1886Printable llvm::printBasicBlock(const BasicBlock *BB) {1887 return Printable([BB](raw_ostream &OS) {1888 if (!BB) {1889 OS << "<nullptr>";1890 return;1891 }1892 BB->printAsOperand(OS);1893 });1894}1895