aboutsummaryrefslogtreecommitdiff
path: root/llvm/lib/Transforms/Scalar/SimplifyCFGPass.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'llvm/lib/Transforms/Scalar/SimplifyCFGPass.cpp')
-rw-r--r--llvm/lib/Transforms/Scalar/SimplifyCFGPass.cpp196
1 files changed, 106 insertions, 90 deletions
diff --git a/llvm/lib/Transforms/Scalar/SimplifyCFGPass.cpp b/llvm/lib/Transforms/Scalar/SimplifyCFGPass.cpp
index 38e7109ead57..09d59b0e884a 100644
--- a/llvm/lib/Transforms/Scalar/SimplifyCFGPass.cpp
+++ b/llvm/lib/Transforms/Scalar/SimplifyCFGPass.cpp
@@ -20,6 +20,7 @@
//
//===----------------------------------------------------------------------===//
+#include "llvm/ADT/MapVector.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
@@ -42,6 +43,7 @@
#include "llvm/Support/CommandLine.h"
#include "llvm/Transforms/Scalar.h"
#include "llvm/Transforms/Scalar/SimplifyCFG.h"
+#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Transforms/Utils/Local.h"
#include "llvm/Transforms/Utils/SimplifyCFGOptions.h"
#include <utility>
@@ -76,117 +78,131 @@ static cl::opt<bool> UserSinkCommonInsts(
STATISTIC(NumSimpl, "Number of blocks simplified");
-/// If we have more than one empty (other than phi node) return blocks,
-/// merge them together to promote recursive block merging.
-static bool mergeEmptyReturnBlocks(Function &F, DomTreeUpdater *DTU) {
- bool Changed = false;
-
- std::vector<DominatorTree::UpdateType> Updates;
- SmallVector<BasicBlock *, 8> DeadBlocks;
-
- BasicBlock *RetBlock = nullptr;
+static bool tailMergeBlocksWithSimilarFunctionTerminators(Function &F,
+ DomTreeUpdater *DTU) {
+ SmallMapVector<unsigned /*TerminatorOpcode*/, SmallVector<BasicBlock *, 2>, 4>
+ Structure;
- // Scan all the blocks in the function, looking for empty return blocks.
- for (BasicBlock &BB : make_early_inc_range(F)) {
+ // Scan all the blocks in the function, record the interesting-ones.
+ for (BasicBlock &BB : F) {
if (DTU && DTU->isBBPendingDeletion(&BB))
continue;
- // Only look at return blocks.
- ReturnInst *Ret = dyn_cast<ReturnInst>(BB.getTerminator());
- if (!Ret) continue;
+ // We are only interested in function-terminating blocks.
+ if (!succ_empty(&BB))
+ continue;
- // Only look at the block if it is empty or the only other thing in it is a
- // single PHI node that is the operand to the return.
- if (Ret != &BB.front()) {
- // Check for something else in the block.
- BasicBlock::iterator I(Ret);
- --I;
- // Skip over debug info.
- while (isa<DbgInfoIntrinsic>(I) && I != BB.begin())
- --I;
- if (!isa<DbgInfoIntrinsic>(I) &&
- (!isa<PHINode>(I) || I != BB.begin() || Ret->getNumOperands() == 0 ||
- Ret->getOperand(0) != &*I))
- continue;
- }
+ auto *Term = BB.getTerminator();
- // If this is the first returning block, remember it and keep going.
- if (!RetBlock) {
- RetBlock = &BB;
+ // Fow now only support `ret`/`resume` function terminators.
+ // FIXME: lift this restriction.
+ switch (Term->getOpcode()) {
+ case Instruction::Ret:
+ case Instruction::Resume:
+ break;
+ default:
continue;
}
- // Skip merging if this would result in a CallBr instruction with a
- // duplicate destination. FIXME: See note in CodeGenPrepare.cpp.
- bool SkipCallBr = false;
- for (pred_iterator PI = pred_begin(&BB), E = pred_end(&BB);
- PI != E && !SkipCallBr; ++PI) {
- if (auto *CBI = dyn_cast<CallBrInst>((*PI)->getTerminator()))
- for (unsigned i = 0, e = CBI->getNumSuccessors(); i != e; ++i)
- if (RetBlock == CBI->getSuccessor(i)) {
- SkipCallBr = true;
- break;
- }
+ // We can't tail-merge block that contains a musttail call.
+ if (BB.getTerminatingMustTailCall())
+ continue;
+
+ // Calls to experimental_deoptimize must be followed by a return
+ // of the value computed by experimental_deoptimize.
+ // I.e., we can not change `ret` to `br` for this block.
+ if (auto *CI =
+ dyn_cast_or_null<CallInst>(Term->getPrevNonDebugInstruction())) {
+ if (Function *F = CI->getCalledFunction())
+ if (Intrinsic::ID ID = F->getIntrinsicID())
+ if (ID == Intrinsic::experimental_deoptimize)
+ continue;
}
- if (SkipCallBr)
+
+ // PHI nodes cannot have token type, so if the terminator has an operand
+ // with token type, we can not tail-merge this kind of function terminators.
+ if (any_of(Term->operands(),
+ [](Value *Op) { return Op->getType()->isTokenTy(); }))
+ continue;
+
+ // Canonical blocks are uniqued based on the terminator type (opcode).
+ Structure[Term->getOpcode()].emplace_back(&BB);
+ }
+
+ bool Changed = false;
+
+ std::vector<DominatorTree::UpdateType> Updates;
+
+ for (ArrayRef<BasicBlock *> BBs : make_second_range(Structure)) {
+ SmallVector<PHINode *, 1> NewOps;
+
+ // We don't want to change IR just because we can.
+ // Only do that if there are at least two blocks we'll tail-merge.
+ if (BBs.size() < 2)
continue;
- // Otherwise, we found a duplicate return block. Merge the two.
Changed = true;
- // Case when there is no input to the return or when the returned values
- // agree is trivial. Note that they can't agree if there are phis in the
- // blocks.
- if (Ret->getNumOperands() == 0 ||
- Ret->getOperand(0) ==
- cast<ReturnInst>(RetBlock->getTerminator())->getOperand(0)) {
- // All predecessors of BB should now branch to RetBlock instead.
- if (DTU) {
- for (auto *Predecessor : predecessors(&BB)) {
- // But, iff Predecessor already branches to RetBlock,
- // don't (re-)add DomTree edge, because it already exists.
- if (!is_contained(successors(Predecessor), RetBlock))
- Updates.push_back({DominatorTree::Insert, Predecessor, RetBlock});
- Updates.push_back({DominatorTree::Delete, Predecessor, &BB});
- }
+ if (DTU)
+ Updates.reserve(Updates.size() + BBs.size());
+
+ BasicBlock *CanonicalBB;
+ Instruction *CanonicalTerm;
+ {
+ auto *Term = BBs[0]->getTerminator();
+
+ // Create a canonical block for this function terminator type now,
+ // placing it *before* the first block that will branch to it.
+ CanonicalBB = BasicBlock::Create(
+ F.getContext(), Twine("common.") + Term->getOpcodeName(), &F, BBs[0]);
+ // We'll also need a PHI node per each operand of the terminator.
+ NewOps.resize(Term->getNumOperands());
+ for (auto I : zip(Term->operands(), NewOps)) {
+ std::get<1>(I) = PHINode::Create(std::get<0>(I)->getType(),
+ /*NumReservedValues=*/BBs.size(),
+ CanonicalBB->getName() + ".op");
+ CanonicalBB->getInstList().push_back(std::get<1>(I));
}
- BB.replaceAllUsesWith(RetBlock);
- DeadBlocks.emplace_back(&BB);
- continue;
+ // Make it so that this canonical block actually has the right
+ // terminator.
+ CanonicalTerm = Term->clone();
+ CanonicalBB->getInstList().push_back(CanonicalTerm);
+ // If the canonical terminator has operands, rewrite it to take PHI's.
+ for (auto I : zip(NewOps, CanonicalTerm->operands()))
+ std::get<1>(I) = std::get<0>(I);
}
- // If the canonical return block has no PHI node, create one now.
- PHINode *RetBlockPHI = dyn_cast<PHINode>(RetBlock->begin());
- if (!RetBlockPHI) {
- Value *InVal = cast<ReturnInst>(RetBlock->getTerminator())->getOperand(0);
- pred_iterator PB = pred_begin(RetBlock), PE = pred_end(RetBlock);
- RetBlockPHI = PHINode::Create(Ret->getOperand(0)->getType(),
- std::distance(PB, PE), "merge",
- &RetBlock->front());
+ // Now, go through each block (with the current terminator type)
+ // we've recorded, and rewrite it to branch to the new common block.
+ const DILocation *CommonDebugLoc = nullptr;
+ for (BasicBlock *BB : BBs) {
+ auto *Term = BB->getTerminator();
+
+ // Aha, found a new non-canonical function terminator. If it has operands,
+ // forward them to the PHI nodes in the canonical block.
+ for (auto I : zip(Term->operands(), NewOps))
+ std::get<1>(I)->addIncoming(std::get<0>(I), BB);
+
+ // Compute the debug location common to all the original terminators.
+ if (!CommonDebugLoc)
+ CommonDebugLoc = Term->getDebugLoc();
+ else
+ CommonDebugLoc =
+ DILocation::getMergedLocation(CommonDebugLoc, Term->getDebugLoc());
- for (pred_iterator PI = PB; PI != PE; ++PI)
- RetBlockPHI->addIncoming(InVal, *PI);
- RetBlock->getTerminator()->setOperand(0, RetBlockPHI);
+ // And turn BB into a block that just unconditionally branches
+ // to the canonical block.
+ Term->eraseFromParent();
+ BranchInst::Create(CanonicalBB, BB);
+ if (DTU)
+ Updates.push_back({DominatorTree::Insert, BB, CanonicalBB});
}
- // Turn BB into a block that just unconditionally branches to the return
- // block. This handles the case when the two return blocks have a common
- // predecessor but that return different things.
- RetBlockPHI->addIncoming(Ret->getOperand(0), &BB);
- BB.getTerminator()->eraseFromParent();
- BranchInst::Create(RetBlock, &BB);
- if (DTU)
- Updates.push_back({DominatorTree::Insert, &BB, RetBlock});
+ CanonicalTerm->setDebugLoc(CommonDebugLoc);
}
- if (DTU) {
+ if (DTU)
DTU->applyUpdates(Updates);
- for (auto *BB : DeadBlocks)
- DTU->deleteBB(BB);
- } else {
- for (auto *BB : DeadBlocks)
- BB->eraseFromParent();
- }
return Changed;
}
@@ -239,7 +255,8 @@ static bool simplifyFunctionCFGImpl(Function &F, const TargetTransformInfo &TTI,
DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager);
bool EverChanged = removeUnreachableBlocks(F, DT ? &DTU : nullptr);
- EverChanged |= mergeEmptyReturnBlocks(F, DT ? &DTU : nullptr);
+ EverChanged |=
+ tailMergeBlocksWithSimilarFunctionTerminators(F, DT ? &DTU : nullptr);
EverChanged |= iterativelySimplifyCFG(F, TTI, DT ? &DTU : nullptr, Options);
// If neither pass changed anything, we're done.
@@ -319,7 +336,6 @@ PreservedAnalyses SimplifyCFGPass::run(Function &F,
PreservedAnalyses PA;
if (RequireAndPreserveDomTree)
PA.preserve<DominatorTreeAnalysis>();
- PA.preserve<GlobalsAA>();
return PA;
}
generated by cgit v1.3 (git 2.53.0) at 2026-09-03 15:56:09 +0000