1 //===- FixIrreducible.cpp - Convert irreducible control-flow into loops ---===// 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 // INPUT CFG: The blocks H and B form an irreducible cycle with two headers. 10 // 11 // Entry 12 // / \ 13 // v v 14 // H ----> B 15 // ^ /| 16 // `----' | 17 // v 18 // Exit 19 // 20 // OUTPUT CFG: Converted to a natural loop with a new header N. 21 // 22 // Entry 23 // | 24 // v 25 // N <---. 26 // / \ \ 27 // / \ | 28 // v v / 29 // H --> B --' 30 // | 31 // v 32 // Exit 33 // 34 // To convert an irreducible cycle C to a natural loop L: 35 // 36 // 1. Add a new node N to C. 37 // 2. Redirect all external incoming edges through N. 38 // 3. Redirect all edges incident on header H through N. 39 // 40 // This is sufficient to ensure that: 41 // 42 // a. Every closed path in C also exists in L, with the modification that any 43 // path passing through H now passes through N before reaching H. 44 // b. Every external path incident on any entry of C is now incident on N and 45 // then redirected to the entry. 46 // 47 // Thus, L is a strongly connected component dominated by N, and hence L is a 48 // natural loop with header N. 49 // 50 // When an irreducible cycle C with header H is transformed into a loop, the 51 // following invariants hold: 52 // 53 // 1. No new subcycles are "discovered" in the set (C-H). The only internal 54 // edges that are redirected by the transform are incident on H. Any subcycle 55 // S in (C-H), already existed prior to this transform, and is already in the 56 // list of children for this cycle C. 57 // 58 // 2. Subcycles of C are not modified by the transform. For some subcycle S of 59 // C, edges incident on the entries of S are either internal to C, or they 60 // are now redirected through N, which is outside of S. So the list of 61 // entries to S does not change. Since the transform only adds a block 62 // outside S, and redirects edges that are not internal to S, the list of 63 // blocks in S does not change. 64 // 65 // 3. Similarly, any natural loop L included in C is not affected, with one 66 // exception: L is "destroyed" by the transform iff its header is H. The 67 // backedges of such a loop are now redirected to N instead, and hence the 68 // body of this loop gets merged into the new loop with header N. 69 // 70 // The actual transformation is handled by the ControlFlowHub, which redirects 71 // specified control flow edges through a set of guard blocks. This also moves 72 // every PHINode in an outgoing block to the hub. Since the hub dominates all 73 // the outgoing blocks, each such PHINode continues to dominate its uses. Since 74 // every header in an SCC has at least two predecessors, every value used in the 75 // header (or later) but defined in a predecessor (or earlier) is represented by 76 // a PHINode in a header. Hence the above handling of PHINodes is sufficient and 77 // no further processing is required to restore SSA. 78 // 79 // Limitation: The pass cannot handle switch statements and indirect 80 // branches. Both must be lowered to plain branches first. 81 // 82 //===----------------------------------------------------------------------===// 83 84 #include "llvm/Transforms/Utils/FixIrreducible.h" 85 #include "llvm/Analysis/CycleAnalysis.h" 86 #include "llvm/Analysis/DomTreeUpdater.h" 87 #include "llvm/Analysis/LoopInfo.h" 88 #include "llvm/InitializePasses.h" 89 #include "llvm/Pass.h" 90 #include "llvm/Transforms/Utils.h" 91 #include "llvm/Transforms/Utils/BasicBlockUtils.h" 92 #include "llvm/Transforms/Utils/ControlFlowUtils.h" 93 94 #define DEBUG_TYPE "fix-irreducible" 95 96 using namespace llvm; 97 98 namespace { 99 struct FixIrreducible : public FunctionPass { 100 static char ID; 101 FixIrreducible() : FunctionPass(ID) { 102 initializeFixIrreduciblePass(*PassRegistry::getPassRegistry()); 103 } 104 105 void getAnalysisUsage(AnalysisUsage &AU) const override { 106 AU.addRequired<DominatorTreeWrapperPass>(); 107 AU.addRequired<CycleInfoWrapperPass>(); 108 AU.addPreserved<DominatorTreeWrapperPass>(); 109 AU.addPreserved<CycleInfoWrapperPass>(); 110 AU.addPreserved<LoopInfoWrapperPass>(); 111 } 112 113 bool runOnFunction(Function &F) override; 114 }; 115 } // namespace 116 117 char FixIrreducible::ID = 0; 118 119 FunctionPass *llvm::createFixIrreduciblePass() { return new FixIrreducible(); } 120 121 INITIALIZE_PASS_BEGIN(FixIrreducible, "fix-irreducible", 122 "Convert irreducible control-flow into natural loops", 123 false /* Only looks at CFG */, false /* Analysis Pass */) 124 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) 125 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass) 126 INITIALIZE_PASS_END(FixIrreducible, "fix-irreducible", 127 "Convert irreducible control-flow into natural loops", 128 false /* Only looks at CFG */, false /* Analysis Pass */) 129 130 // When a new loop is created, existing children of the parent loop may now be 131 // fully inside the new loop. Reconnect these as children of the new loop. 132 static void reconnectChildLoops(LoopInfo &LI, Loop *ParentLoop, Loop *NewLoop, 133 BasicBlock *OldHeader) { 134 auto &CandidateLoops = ParentLoop ? ParentLoop->getSubLoopsVector() 135 : LI.getTopLevelLoopsVector(); 136 // Any candidate is a child iff its header is owned by the new loop. Move all 137 // the children to a new vector. 138 auto FirstChild = std::partition( 139 CandidateLoops.begin(), CandidateLoops.end(), [&](Loop *L) { 140 return NewLoop == L || !NewLoop->contains(L->getHeader()); 141 }); 142 SmallVector<Loop *, 8> ChildLoops(FirstChild, CandidateLoops.end()); 143 CandidateLoops.erase(FirstChild, CandidateLoops.end()); 144 145 for (Loop *Child : ChildLoops) { 146 LLVM_DEBUG(dbgs() << "child loop: " << Child->getHeader()->getName() 147 << "\n"); 148 // A child loop whose header was the old cycle header gets destroyed since 149 // its backedges are removed. 150 if (Child->getHeader() == OldHeader) { 151 for (auto *BB : Child->blocks()) { 152 if (LI.getLoopFor(BB) != Child) 153 continue; 154 LI.changeLoopFor(BB, NewLoop); 155 LLVM_DEBUG(dbgs() << "moved block from child: " << BB->getName() 156 << "\n"); 157 } 158 std::vector<Loop *> GrandChildLoops; 159 std::swap(GrandChildLoops, Child->getSubLoopsVector()); 160 for (auto *GrandChildLoop : GrandChildLoops) { 161 GrandChildLoop->setParentLoop(nullptr); 162 NewLoop->addChildLoop(GrandChildLoop); 163 } 164 LI.destroy(Child); 165 LLVM_DEBUG(dbgs() << "subsumed child loop (common header)\n"); 166 continue; 167 } 168 169 Child->setParentLoop(nullptr); 170 NewLoop->addChildLoop(Child); 171 LLVM_DEBUG(dbgs() << "added child loop to new loop\n"); 172 } 173 } 174 175 static void updateLoopInfo(LoopInfo &LI, Cycle &C, 176 ArrayRef<BasicBlock *> GuardBlocks) { 177 // The parent loop is a natural loop L mapped to the cycle header H as long as 178 // H is not also the header of L. In the latter case, L is destroyed and we 179 // seek its parent instead. 180 BasicBlock *CycleHeader = C.getHeader(); 181 Loop *ParentLoop = LI.getLoopFor(CycleHeader); 182 if (ParentLoop && ParentLoop->getHeader() == CycleHeader) 183 ParentLoop = ParentLoop->getParentLoop(); 184 185 // Create a new loop from the now-transformed cycle 186 auto *NewLoop = LI.AllocateLoop(); 187 if (ParentLoop) { 188 ParentLoop->addChildLoop(NewLoop); 189 } else { 190 LI.addTopLevelLoop(NewLoop); 191 } 192 193 // Add the guard blocks to the new loop. The first guard block is 194 // the head of all the backedges, and it is the first to be inserted 195 // in the loop. This ensures that it is recognized as the 196 // header. Since the new loop is already in LoopInfo, the new blocks 197 // are also propagated up the chain of parent loops. 198 for (auto *G : GuardBlocks) { 199 LLVM_DEBUG(dbgs() << "added guard block to loop: " << G->getName() << "\n"); 200 NewLoop->addBasicBlockToLoop(G, LI); 201 } 202 203 for (auto *BB : C.blocks()) { 204 NewLoop->addBlockEntry(BB); 205 if (LI.getLoopFor(BB) == ParentLoop) { 206 LLVM_DEBUG(dbgs() << "moved block from parent: " << BB->getName() 207 << "\n"); 208 LI.changeLoopFor(BB, NewLoop); 209 } else { 210 LLVM_DEBUG(dbgs() << "added block from child: " << BB->getName() << "\n"); 211 } 212 } 213 LLVM_DEBUG(dbgs() << "header for new loop: " 214 << NewLoop->getHeader()->getName() << "\n"); 215 216 reconnectChildLoops(LI, ParentLoop, NewLoop, C.getHeader()); 217 218 LLVM_DEBUG(dbgs() << "Verify new loop.\n"; NewLoop->print(dbgs())); 219 NewLoop->verifyLoop(); 220 if (ParentLoop) { 221 LLVM_DEBUG(dbgs() << "Verify parent loop.\n"; ParentLoop->print(dbgs())); 222 ParentLoop->verifyLoop(); 223 } 224 } 225 226 // Given a set of blocks and headers in an irreducible SCC, convert it into a 227 // natural loop. Also insert this new loop at its appropriate place in the 228 // hierarchy of loops. 229 static bool fixIrreducible(Cycle &C, CycleInfo &CI, DominatorTree &DT, 230 LoopInfo *LI) { 231 if (C.isReducible()) 232 return false; 233 LLVM_DEBUG(dbgs() << "Processing cycle:\n" << CI.print(&C) << "\n";); 234 235 ControlFlowHub CHub; 236 SetVector<BasicBlock *> Predecessors; 237 238 // Redirect internal edges incident on the header. 239 BasicBlock *Header = C.getHeader(); 240 for (BasicBlock *P : predecessors(Header)) { 241 if (C.contains(P)) 242 Predecessors.insert(P); 243 } 244 245 for (BasicBlock *P : Predecessors) { 246 auto *Branch = cast<BranchInst>(P->getTerminator()); 247 // Exactly one of the two successors is the header. 248 BasicBlock *Succ0 = Branch->getSuccessor(0) == Header ? Header : nullptr; 249 BasicBlock *Succ1 = Succ0 ? nullptr : Header; 250 if (!Succ0) 251 assert(Branch->getSuccessor(1) == Header); 252 assert(Succ0 || Succ1); 253 CHub.addBranch(P, Succ0, Succ1); 254 255 LLVM_DEBUG(dbgs() << "Added internal branch: " << P->getName() << " -> " 256 << (Succ0 ? Succ0->getName() : "") << " " 257 << (Succ1 ? Succ1->getName() : "") << "\n"); 258 } 259 260 // Redirect external incoming edges. This includes the edges on the header. 261 Predecessors.clear(); 262 for (BasicBlock *E : C.entries()) { 263 for (BasicBlock *P : predecessors(E)) { 264 if (!C.contains(P)) 265 Predecessors.insert(P); 266 } 267 } 268 269 for (BasicBlock *P : Predecessors) { 270 auto *Branch = cast<BranchInst>(P->getTerminator()); 271 BasicBlock *Succ0 = Branch->getSuccessor(0); 272 Succ0 = C.contains(Succ0) ? Succ0 : nullptr; 273 BasicBlock *Succ1 = 274 Branch->isUnconditional() ? nullptr : Branch->getSuccessor(1); 275 Succ1 = Succ1 && C.contains(Succ1) ? Succ1 : nullptr; 276 CHub.addBranch(P, Succ0, Succ1); 277 278 LLVM_DEBUG(dbgs() << "Added external branch: " << P->getName() << " -> " 279 << (Succ0 ? Succ0->getName() : "") << " " 280 << (Succ1 ? Succ1->getName() : "") << "\n"); 281 } 282 283 // Redirect all the backedges through a "hub" consisting of a series 284 // of guard blocks that manage the flow of control from the 285 // predecessors to the headers. 286 SmallVector<BasicBlock *> GuardBlocks; 287 288 // Minor optimization: The cycle entries are discovered in an order that is 289 // the opposite of the order in which these blocks appear as branch targets. 290 // This results in a lot of condition inversions in the control flow out of 291 // the new ControlFlowHub, which can be mitigated if the orders match. So we 292 // reverse the entries when adding them to the hub. 293 SetVector<BasicBlock *> Entries; 294 Entries.insert(C.entry_rbegin(), C.entry_rend()); 295 296 DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager); 297 CHub.finalize(&DTU, GuardBlocks, "irr"); 298 #if defined(EXPENSIVE_CHECKS) 299 assert(DT.verify(DominatorTree::VerificationLevel::Full)); 300 #else 301 assert(DT.verify(DominatorTree::VerificationLevel::Fast)); 302 #endif 303 304 // If we are updating LoopInfo, do that now before modifying the cycle. This 305 // ensures that the first guard block is the header of a new natural loop. 306 if (LI) 307 updateLoopInfo(*LI, C, GuardBlocks); 308 309 for (auto *G : GuardBlocks) { 310 LLVM_DEBUG(dbgs() << "added guard block to cycle: " << G->getName() 311 << "\n"); 312 CI.addBlockToCycle(G, &C); 313 } 314 C.setSingleEntry(GuardBlocks[0]); 315 316 C.verifyCycle(); 317 if (Cycle *Parent = C.getParentCycle()) 318 Parent->verifyCycle(); 319 320 LLVM_DEBUG(dbgs() << "Finished one cycle:\n"; CI.print(dbgs());); 321 return true; 322 } 323 324 static bool FixIrreducibleImpl(Function &F, CycleInfo &CI, DominatorTree &DT, 325 LoopInfo *LI) { 326 LLVM_DEBUG(dbgs() << "===== Fix irreducible control-flow in function: " 327 << F.getName() << "\n"); 328 329 assert(hasOnlySimpleTerminator(F) && "Unsupported block terminator."); 330 331 bool Changed = false; 332 for (Cycle *TopCycle : CI.toplevel_cycles()) { 333 for (Cycle *C : depth_first(TopCycle)) { 334 Changed |= fixIrreducible(*C, CI, DT, LI); 335 } 336 } 337 338 if (!Changed) 339 return false; 340 341 #if defined(EXPENSIVE_CHECKS) 342 CI.verify(); 343 if (LI) { 344 LI->verify(DT); 345 } 346 #endif // EXPENSIVE_CHECKS 347 348 return true; 349 } 350 351 bool FixIrreducible::runOnFunction(Function &F) { 352 auto *LIWP = getAnalysisIfAvailable<LoopInfoWrapperPass>(); 353 LoopInfo *LI = LIWP ? &LIWP->getLoopInfo() : nullptr; 354 auto &CI = getAnalysis<CycleInfoWrapperPass>().getResult(); 355 auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree(); 356 return FixIrreducibleImpl(F, CI, DT, LI); 357 } 358 359 PreservedAnalyses FixIrreduciblePass::run(Function &F, 360 FunctionAnalysisManager &AM) { 361 auto *LI = AM.getCachedResult<LoopAnalysis>(F); 362 auto &CI = AM.getResult<CycleAnalysis>(F); 363 auto &DT = AM.getResult<DominatorTreeAnalysis>(F); 364 365 if (!FixIrreducibleImpl(F, CI, DT, LI)) 366 return PreservedAnalyses::all(); 367 368 PreservedAnalyses PA; 369 PA.preserve<LoopAnalysis>(); 370 PA.preserve<CycleAnalysis>(); 371 PA.preserve<DominatorTreeAnalysis>(); 372 return PA; 373 } 374