1 //===- SimplifyCFGPass.cpp - CFG Simplification Pass ----------------------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This file implements dead code elimination and basic block merging, along 10 // with a collection of other peephole control flow optimizations. For example: 11 // 12 // * Removes basic blocks with no predecessors. 13 // * Merges a basic block into its predecessor if there is only one and the 14 // predecessor only has one successor. 15 // * Eliminates PHI nodes for basic blocks with a single predecessor. 16 // * Eliminates a basic block that only contains an unconditional branch. 17 // * Changes invoke instructions to nounwind functions to be calls. 18 // * Change things like "if (x) if (y)" into "if (x&y)". 19 // * etc.. 20 // 21 //===----------------------------------------------------------------------===// 22 23 #include "llvm/ADT/MapVector.h" 24 #include "llvm/ADT/SmallPtrSet.h" 25 #include "llvm/ADT/SmallVector.h" 26 #include "llvm/ADT/Statistic.h" 27 #include "llvm/Analysis/AssumptionCache.h" 28 #include "llvm/Analysis/CFG.h" 29 #include "llvm/Analysis/DomTreeUpdater.h" 30 #include "llvm/Analysis/GlobalsModRef.h" 31 #include "llvm/Analysis/TargetTransformInfo.h" 32 #include "llvm/IR/Attributes.h" 33 #include "llvm/IR/CFG.h" 34 #include "llvm/IR/Dominators.h" 35 #include "llvm/IR/Instructions.h" 36 #include "llvm/IR/ValueHandle.h" 37 #include "llvm/InitializePasses.h" 38 #include "llvm/Pass.h" 39 #include "llvm/Support/CommandLine.h" 40 #include "llvm/Transforms/Scalar.h" 41 #include "llvm/Transforms/Scalar/SimplifyCFG.h" 42 #include "llvm/Transforms/Utils/Local.h" 43 #include "llvm/Transforms/Utils/SimplifyCFGOptions.h" 44 #include <utility> 45 using namespace llvm; 46 47 #define DEBUG_TYPE "simplifycfg" 48 49 static cl::opt<unsigned> UserBonusInstThreshold( 50 "bonus-inst-threshold", cl::Hidden, cl::init(1), 51 cl::desc("Control the number of bonus instructions (default = 1)")); 52 53 static cl::opt<bool> UserKeepLoops( 54 "keep-loops", cl::Hidden, cl::init(true), 55 cl::desc("Preserve canonical loop structure (default = true)")); 56 57 static cl::opt<bool> UserSwitchRangeToICmp( 58 "switch-range-to-icmp", cl::Hidden, cl::init(false), 59 cl::desc( 60 "Convert switches into an integer range comparison (default = false)")); 61 62 static cl::opt<bool> UserSwitchToLookup( 63 "switch-to-lookup", cl::Hidden, cl::init(false), 64 cl::desc("Convert switches to lookup tables (default = false)")); 65 66 static cl::opt<bool> UserForwardSwitchCond( 67 "forward-switch-cond", cl::Hidden, cl::init(false), 68 cl::desc("Forward switch condition to phi ops (default = false)")); 69 70 static cl::opt<bool> UserHoistCommonInsts( 71 "hoist-common-insts", cl::Hidden, cl::init(false), 72 cl::desc("hoist common instructions (default = false)")); 73 74 static cl::opt<bool> UserHoistLoadsStoresWithCondFaulting( 75 "hoist-loads-stores-with-cond-faulting", cl::Hidden, cl::init(false), 76 cl::desc("Hoist loads/stores if the target supports conditional faulting " 77 "(default = false)")); 78 79 static cl::opt<bool> UserSinkCommonInsts( 80 "sink-common-insts", cl::Hidden, cl::init(false), 81 cl::desc("Sink common instructions (default = false)")); 82 83 static cl::opt<bool> UserSpeculateUnpredictables( 84 "speculate-unpredictables", cl::Hidden, cl::init(false), 85 cl::desc("Speculate unpredictable branches (default = false)")); 86 87 STATISTIC(NumSimpl, "Number of blocks simplified"); 88 89 static bool 90 performBlockTailMerging(Function &F, ArrayRef<BasicBlock *> BBs, 91 std::vector<DominatorTree::UpdateType> *Updates) { 92 SmallVector<PHINode *, 1> NewOps; 93 94 // We don't want to change IR just because we can. 95 // Only do that if there are at least two blocks we'll tail-merge. 96 if (BBs.size() < 2) 97 return false; 98 99 if (Updates) 100 Updates->reserve(Updates->size() + BBs.size()); 101 102 BasicBlock *CanonicalBB; 103 Instruction *CanonicalTerm; 104 { 105 auto *Term = BBs[0]->getTerminator(); 106 107 // Create a canonical block for this function terminator type now, 108 // placing it *before* the first block that will branch to it. 109 CanonicalBB = BasicBlock::Create( 110 F.getContext(), Twine("common.") + Term->getOpcodeName(), &F, BBs[0]); 111 // We'll also need a PHI node per each operand of the terminator. 112 NewOps.resize(Term->getNumOperands()); 113 for (auto I : zip(Term->operands(), NewOps)) { 114 std::get<1>(I) = PHINode::Create(std::get<0>(I)->getType(), 115 /*NumReservedValues=*/BBs.size(), 116 CanonicalBB->getName() + ".op"); 117 std::get<1>(I)->insertInto(CanonicalBB, CanonicalBB->end()); 118 } 119 // Make it so that this canonical block actually has the right 120 // terminator. 121 CanonicalTerm = Term->clone(); 122 CanonicalTerm->insertInto(CanonicalBB, CanonicalBB->end()); 123 // If the canonical terminator has operands, rewrite it to take PHI's. 124 for (auto I : zip(NewOps, CanonicalTerm->operands())) 125 std::get<1>(I) = std::get<0>(I); 126 } 127 128 // Now, go through each block (with the current terminator type) 129 // we've recorded, and rewrite it to branch to the new common block. 130 DebugLoc CommonDebugLoc; 131 for (BasicBlock *BB : BBs) { 132 auto *Term = BB->getTerminator(); 133 assert(Term->getOpcode() == CanonicalTerm->getOpcode() && 134 "All blocks to be tail-merged must be the same " 135 "(function-terminating) terminator type."); 136 137 // Aha, found a new non-canonical function terminator. If it has operands, 138 // forward them to the PHI nodes in the canonical block. 139 for (auto I : zip(Term->operands(), NewOps)) 140 std::get<1>(I)->addIncoming(std::get<0>(I), BB); 141 142 // Compute the debug location common to all the original terminators. 143 if (!CommonDebugLoc) 144 CommonDebugLoc = Term->getDebugLoc(); 145 else 146 CommonDebugLoc = 147 DebugLoc::getMergedLocation(CommonDebugLoc, Term->getDebugLoc()); 148 149 // And turn BB into a block that just unconditionally branches 150 // to the canonical block. 151 Instruction *BI = BranchInst::Create(CanonicalBB, BB); 152 BI->setDebugLoc(Term->getDebugLoc()); 153 Term->eraseFromParent(); 154 155 if (Updates) 156 Updates->push_back({DominatorTree::Insert, BB, CanonicalBB}); 157 } 158 159 CanonicalTerm->setDebugLoc(CommonDebugLoc); 160 161 return true; 162 } 163 164 static bool tailMergeBlocksWithSimilarFunctionTerminators(Function &F, 165 DomTreeUpdater *DTU) { 166 SmallMapVector<unsigned /*TerminatorOpcode*/, SmallVector<BasicBlock *, 2>, 4> 167 Structure; 168 169 // Scan all the blocks in the function, record the interesting-ones. 170 for (BasicBlock &BB : F) { 171 if (DTU && DTU->isBBPendingDeletion(&BB)) 172 continue; 173 174 // We are only interested in function-terminating blocks. 175 if (!succ_empty(&BB)) 176 continue; 177 178 auto *Term = BB.getTerminator(); 179 180 // Fow now only support `ret`/`resume` function terminators. 181 // FIXME: lift this restriction. 182 switch (Term->getOpcode()) { 183 case Instruction::Ret: 184 case Instruction::Resume: 185 break; 186 default: 187 continue; 188 } 189 190 // We can't tail-merge block that contains a musttail call. 191 if (BB.getTerminatingMustTailCall()) 192 continue; 193 194 // Calls to experimental_deoptimize must be followed by a return 195 // of the value computed by experimental_deoptimize. 196 // I.e., we can not change `ret` to `br` for this block. 197 if (auto *CI = 198 dyn_cast_or_null<CallInst>(Term->getPrevNonDebugInstruction())) { 199 if (Function *F = CI->getCalledFunction()) 200 if (Intrinsic::ID ID = F->getIntrinsicID()) 201 if (ID == Intrinsic::experimental_deoptimize) 202 continue; 203 } 204 205 // PHI nodes cannot have token type, so if the terminator has an operand 206 // with token type, we can not tail-merge this kind of function terminators. 207 if (any_of(Term->operands(), 208 [](Value *Op) { return Op->getType()->isTokenTy(); })) 209 continue; 210 211 // Canonical blocks are uniqued based on the terminator type (opcode). 212 Structure[Term->getOpcode()].emplace_back(&BB); 213 } 214 215 bool Changed = false; 216 217 std::vector<DominatorTree::UpdateType> Updates; 218 219 for (ArrayRef<BasicBlock *> BBs : make_second_range(Structure)) 220 Changed |= performBlockTailMerging(F, BBs, DTU ? &Updates : nullptr); 221 222 if (DTU) 223 DTU->applyUpdates(Updates); 224 225 return Changed; 226 } 227 228 /// Call SimplifyCFG on all the blocks in the function, 229 /// iterating until no more changes are made. 230 static bool iterativelySimplifyCFG(Function &F, const TargetTransformInfo &TTI, 231 DomTreeUpdater *DTU, 232 const SimplifyCFGOptions &Options) { 233 bool Changed = false; 234 bool LocalChange = true; 235 236 SmallVector<std::pair<const BasicBlock *, const BasicBlock *>, 32> Edges; 237 FindFunctionBackedges(F, Edges); 238 SmallPtrSet<BasicBlock *, 16> UniqueLoopHeaders; 239 for (const auto &Edge : Edges) 240 UniqueLoopHeaders.insert(const_cast<BasicBlock *>(Edge.second)); 241 242 SmallVector<WeakVH, 16> LoopHeaders(UniqueLoopHeaders.begin(), 243 UniqueLoopHeaders.end()); 244 245 unsigned IterCnt = 0; 246 (void)IterCnt; 247 while (LocalChange) { 248 assert(IterCnt++ < 1000 && "Iterative simplification didn't converge!"); 249 LocalChange = false; 250 251 // Loop over all of the basic blocks and remove them if they are unneeded. 252 for (Function::iterator BBIt = F.begin(); BBIt != F.end(); ) { 253 BasicBlock &BB = *BBIt++; 254 if (DTU) { 255 assert( 256 !DTU->isBBPendingDeletion(&BB) && 257 "Should not end up trying to simplify blocks marked for removal."); 258 // Make sure that the advanced iterator does not point at the blocks 259 // that are marked for removal, skip over all such blocks. 260 while (BBIt != F.end() && DTU->isBBPendingDeletion(&*BBIt)) 261 ++BBIt; 262 } 263 if (simplifyCFG(&BB, TTI, DTU, Options, LoopHeaders)) { 264 LocalChange = true; 265 ++NumSimpl; 266 } 267 } 268 Changed |= LocalChange; 269 } 270 return Changed; 271 } 272 273 static bool simplifyFunctionCFGImpl(Function &F, const TargetTransformInfo &TTI, 274 DominatorTree *DT, 275 const SimplifyCFGOptions &Options) { 276 DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager); 277 278 bool EverChanged = removeUnreachableBlocks(F, DT ? &DTU : nullptr); 279 EverChanged |= 280 tailMergeBlocksWithSimilarFunctionTerminators(F, DT ? &DTU : nullptr); 281 EverChanged |= iterativelySimplifyCFG(F, TTI, DT ? &DTU : nullptr, Options); 282 283 // If neither pass changed anything, we're done. 284 if (!EverChanged) return false; 285 286 // iterativelySimplifyCFG can (rarely) make some loops dead. If this happens, 287 // removeUnreachableBlocks is needed to nuke them, which means we should 288 // iterate between the two optimizations. We structure the code like this to 289 // avoid rerunning iterativelySimplifyCFG if the second pass of 290 // removeUnreachableBlocks doesn't do anything. 291 if (!removeUnreachableBlocks(F, DT ? &DTU : nullptr)) 292 return true; 293 294 do { 295 EverChanged = iterativelySimplifyCFG(F, TTI, DT ? &DTU : nullptr, Options); 296 EverChanged |= removeUnreachableBlocks(F, DT ? &DTU : nullptr); 297 } while (EverChanged); 298 299 return true; 300 } 301 302 static bool simplifyFunctionCFG(Function &F, const TargetTransformInfo &TTI, 303 DominatorTree *DT, 304 const SimplifyCFGOptions &Options) { 305 assert((!RequireAndPreserveDomTree || 306 (DT && DT->verify(DominatorTree::VerificationLevel::Full))) && 307 "Original domtree is invalid?"); 308 309 bool Changed = simplifyFunctionCFGImpl(F, TTI, DT, Options); 310 311 assert((!RequireAndPreserveDomTree || 312 (DT && DT->verify(DominatorTree::VerificationLevel::Full))) && 313 "Failed to maintain validity of domtree!"); 314 315 return Changed; 316 } 317 318 // Command-line settings override compile-time settings. 319 static void applyCommandLineOverridesToOptions(SimplifyCFGOptions &Options) { 320 if (UserBonusInstThreshold.getNumOccurrences()) 321 Options.BonusInstThreshold = UserBonusInstThreshold; 322 if (UserForwardSwitchCond.getNumOccurrences()) 323 Options.ForwardSwitchCondToPhi = UserForwardSwitchCond; 324 if (UserSwitchRangeToICmp.getNumOccurrences()) 325 Options.ConvertSwitchRangeToICmp = UserSwitchRangeToICmp; 326 if (UserSwitchToLookup.getNumOccurrences()) 327 Options.ConvertSwitchToLookupTable = UserSwitchToLookup; 328 if (UserKeepLoops.getNumOccurrences()) 329 Options.NeedCanonicalLoop = UserKeepLoops; 330 if (UserHoistCommonInsts.getNumOccurrences()) 331 Options.HoistCommonInsts = UserHoistCommonInsts; 332 if (UserHoistLoadsStoresWithCondFaulting.getNumOccurrences()) 333 Options.HoistLoadsStoresWithCondFaulting = 334 UserHoistLoadsStoresWithCondFaulting; 335 if (UserSinkCommonInsts.getNumOccurrences()) 336 Options.SinkCommonInsts = UserSinkCommonInsts; 337 if (UserSpeculateUnpredictables.getNumOccurrences()) 338 Options.SpeculateUnpredictables = UserSpeculateUnpredictables; 339 } 340 341 SimplifyCFGPass::SimplifyCFGPass() { 342 applyCommandLineOverridesToOptions(Options); 343 } 344 345 SimplifyCFGPass::SimplifyCFGPass(const SimplifyCFGOptions &Opts) 346 : Options(Opts) { 347 applyCommandLineOverridesToOptions(Options); 348 } 349 350 void SimplifyCFGPass::printPipeline( 351 raw_ostream &OS, function_ref<StringRef(StringRef)> MapClassName2PassName) { 352 static_cast<PassInfoMixin<SimplifyCFGPass> *>(this)->printPipeline( 353 OS, MapClassName2PassName); 354 OS << '<'; 355 OS << "bonus-inst-threshold=" << Options.BonusInstThreshold << ';'; 356 OS << (Options.ForwardSwitchCondToPhi ? "" : "no-") << "forward-switch-cond;"; 357 OS << (Options.ConvertSwitchRangeToICmp ? "" : "no-") 358 << "switch-range-to-icmp;"; 359 OS << (Options.ConvertSwitchToLookupTable ? "" : "no-") 360 << "switch-to-lookup;"; 361 OS << (Options.NeedCanonicalLoop ? "" : "no-") << "keep-loops;"; 362 OS << (Options.HoistCommonInsts ? "" : "no-") << "hoist-common-insts;"; 363 OS << (Options.HoistLoadsStoresWithCondFaulting ? "" : "no-") 364 << "hoist-loads-stores-with-cond-faulting;"; 365 OS << (Options.SinkCommonInsts ? "" : "no-") << "sink-common-insts;"; 366 OS << (Options.SpeculateBlocks ? "" : "no-") << "speculate-blocks;"; 367 OS << (Options.SimplifyCondBranch ? "" : "no-") << "simplify-cond-branch;"; 368 OS << (Options.SpeculateUnpredictables ? "" : "no-") 369 << "speculate-unpredictables"; 370 OS << '>'; 371 } 372 373 PreservedAnalyses SimplifyCFGPass::run(Function &F, 374 FunctionAnalysisManager &AM) { 375 auto &TTI = AM.getResult<TargetIRAnalysis>(F); 376 Options.AC = &AM.getResult<AssumptionAnalysis>(F); 377 DominatorTree *DT = nullptr; 378 if (RequireAndPreserveDomTree) 379 DT = &AM.getResult<DominatorTreeAnalysis>(F); 380 if (!simplifyFunctionCFG(F, TTI, DT, Options)) 381 return PreservedAnalyses::all(); 382 PreservedAnalyses PA; 383 if (RequireAndPreserveDomTree) 384 PA.preserve<DominatorTreeAnalysis>(); 385 return PA; 386 } 387 388 namespace { 389 struct CFGSimplifyPass : public FunctionPass { 390 static char ID; 391 SimplifyCFGOptions Options; 392 std::function<bool(const Function &)> PredicateFtor; 393 394 CFGSimplifyPass(SimplifyCFGOptions Options_ = SimplifyCFGOptions(), 395 std::function<bool(const Function &)> Ftor = nullptr) 396 : FunctionPass(ID), Options(Options_), PredicateFtor(std::move(Ftor)) { 397 398 initializeCFGSimplifyPassPass(*PassRegistry::getPassRegistry()); 399 400 // Check for command-line overrides of options for debug/customization. 401 applyCommandLineOverridesToOptions(Options); 402 } 403 404 bool runOnFunction(Function &F) override { 405 if (skipFunction(F) || (PredicateFtor && !PredicateFtor(F))) 406 return false; 407 408 Options.AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F); 409 DominatorTree *DT = nullptr; 410 if (RequireAndPreserveDomTree) 411 DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree(); 412 413 auto &TTI = getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F); 414 return simplifyFunctionCFG(F, TTI, DT, Options); 415 } 416 void getAnalysisUsage(AnalysisUsage &AU) const override { 417 AU.addRequired<AssumptionCacheTracker>(); 418 if (RequireAndPreserveDomTree) 419 AU.addRequired<DominatorTreeWrapperPass>(); 420 AU.addRequired<TargetTransformInfoWrapperPass>(); 421 if (RequireAndPreserveDomTree) 422 AU.addPreserved<DominatorTreeWrapperPass>(); 423 AU.addPreserved<GlobalsAAWrapperPass>(); 424 } 425 }; 426 } 427 428 char CFGSimplifyPass::ID = 0; 429 INITIALIZE_PASS_BEGIN(CFGSimplifyPass, "simplifycfg", "Simplify the CFG", false, 430 false) 431 INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass) 432 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker) 433 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) 434 INITIALIZE_PASS_END(CFGSimplifyPass, "simplifycfg", "Simplify the CFG", false, 435 false) 436 437 // Public interface to the CFGSimplification pass 438 FunctionPass * 439 llvm::createCFGSimplificationPass(SimplifyCFGOptions Options, 440 std::function<bool(const Function &)> Ftor) { 441 return new CFGSimplifyPass(Options, std::move(Ftor)); 442 } 443