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

   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 // An irreducible SCC is one which has multiple "header" blocks, i.e., blocks
  10 // with control-flow edges incident from outside the SCC.  This pass converts a
  11 // irreducible SCC into a natural loop by applying the following transformation:
  12 //
  13 // 1. Collect the set of headers H of the SCC.
  14 // 2. Collect the set of predecessors P of these headers. These may be inside as
  15 //    well as outside the SCC.
  16 // 3. Create block N and redirect every edge from set P to set H through N.
  17 //
  18 // This converts the SCC into a natural loop with N as the header: N is the only
  19 // block with edges incident from outside the SCC, and all backedges in the SCC
  20 // are incident on N, i.e., for every backedge, the head now dominates the tail.
  21 //
  22 // INPUT CFG: The blocks A and B form an irreducible loop with two headers.
  23 //
  24 //                        Entry
  25 //                       /     \
  26 //                      v       v
  27 //                      A ----> B
  28 //                      ^      /|
  29 //                       `----' |
  30 //                              v
  31 //                             Exit
  32 //
  33 // OUTPUT CFG: Edges incident on A and B are now redirected through a
  34 // new block N, forming a natural loop consisting of N, A and B.
  35 //
  36 //                        Entry
  37 //                          |
  38 //                          v
  39 //                    .---> N <---.
  40 //                   /     / \     \
  41 //                  |     /   \     |
  42 //                  \    v     v    /
  43 //                   `-- A     B --'
  44 //                             |
  45 //                             v
  46 //                            Exit
  47 //
  48 // The transformation is applied to every maximal SCC that is not already
  49 // recognized as a loop. The pass operates on all maximal SCCs found in the
  50 // function body outside of any loop, as well as those found inside each loop,
  51 // including inside any newly created loops. This ensures that any SCC hidden
  52 // inside a maximal SCC is also transformed.
  53 //
  54 // The actual transformation is handled by function CreateControlFlowHub, which
  55 // takes a set of incoming blocks (the predecessors) and outgoing blocks (the
  56 // headers). The function also moves every PHINode in an outgoing block to the
  57 // hub. Since the hub dominates all the outgoing blocks, each such PHINode
  58 // continues to dominate its uses. Since every header in an SCC has at least two
  59 // predecessors, every value used in the header (or later) but defined in a
  60 // predecessor (or earlier) is represented by a PHINode in a header. Hence the
  61 // above handling of PHINodes is sufficient and no further processing is
  62 // required to restore SSA.
  63 //
  64 // Limitation: The pass cannot handle switch statements and indirect
  65 //             branches. Both must be lowered to plain branches first.
  66 //
  67 //===----------------------------------------------------------------------===//
  68
  69 #include "llvm/ADT/SCCIterator.h"
  70 #include "llvm/Analysis/LoopIterator.h"
  71 #include "llvm/InitializePasses.h"
  72 #include "llvm/Pass.h"
  73 #include "llvm/Transforms/Utils.h"
  74 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
  75
  76 #define DEBUG_TYPE "fix-irreducible"
  77
  78 using namespace llvm;
  79
  80 namespace {
  81 struct FixIrreducible : public FunctionPass {
  82   static char ID;
  83   FixIrreducible() : FunctionPass(ID) {
  84     initializeFixIrreduciblePass(*PassRegistry::getPassRegistry());
  85   }
  86
  87   void getAnalysisUsage(AnalysisUsage &AU) const override {
  88     AU.addRequiredID(LowerSwitchID);
  89     AU.addRequired<DominatorTreeWrapperPass>();
  90     AU.addRequired<LoopInfoWrapperPass>();
  91     AU.addPreservedID(LowerSwitchID);
  92     AU.addPreserved<DominatorTreeWrapperPass>();
  93     AU.addPreserved<LoopInfoWrapperPass>();
  94   }
  95
  96   bool runOnFunction(Function &F) override;
  97 };
  98 } // namespace
  99
 100 char FixIrreducible::ID = 0;
 101
 102 FunctionPass *llvm::createFixIrreduciblePass() { return new FixIrreducible(); }
 103
 104 INITIALIZE_PASS_BEGIN(FixIrreducible, "fix-irreducible",
 105                       "Convert irreducible control-flow into natural loops",
 106                       false /* Only looks at CFG */, false /* Analysis Pass */)
 107 INITIALIZE_PASS_DEPENDENCY(LowerSwitch)
 108 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
 109 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
 110 INITIALIZE_PASS_END(FixIrreducible, "fix-irreducible",
 111                     "Convert irreducible control-flow into natural loops",
 112                     false /* Only looks at CFG */, false /* Analysis Pass */)
 113
 114 // When a new loop is created, existing children of the parent loop may now be
 115 // fully inside the new loop. Reconnect these as children of the new loop.
 116 static void reconnectChildLoops(LoopInfo &LI, Loop *ParentLoop, Loop *NewLoop,
 117                                 SetVector<BasicBlock *> &Blocks,
 118                                 SetVector<BasicBlock *> &Headers) {
 119   auto &CandidateLoops = ParentLoop ? ParentLoop->getSubLoopsVector()
 120                                     : LI.getTopLevelLoopsVector();
 121   // The new loop cannot be its own child, and any candidate is a
 122   // child iff its header is owned by the new loop. Move all the
 123   // children to a new vector.
 124   auto FirstChild = std::partition(
 125       CandidateLoops.begin(), CandidateLoops.end(), [&](Loop *L) {
 126         return L == NewLoop || Blocks.count(L->getHeader()) == 0;
 127       });
 128   SmallVector<Loop *, 8> ChildLoops(FirstChild, CandidateLoops.end());
 129   CandidateLoops.erase(FirstChild, CandidateLoops.end());
 130
 131   for (auto II = ChildLoops.begin(), IE = ChildLoops.end(); II != IE; ++II) {
 132     auto Child = *II;
 133     LLVM_DEBUG(dbgs() << "child loop: " << Child->getHeader()->getName()
 134                       << "\n");
 135     // TODO: A child loop whose header is also a header in the current
 136     // SCC gets destroyed since its backedges are removed. That may
 137     // not be necessary if we can retain such backedges.
 138     if (Headers.count(Child->getHeader())) {
 139       for (auto BB : Child->blocks()) {
 140         LI.changeLoopFor(BB, NewLoop);
 141         LLVM_DEBUG(dbgs() << "moved block from child: " << BB->getName()
 142                           << "\n");
 143       }
 144       LI.destroy(Child);
 145       LLVM_DEBUG(dbgs() << "subsumed child loop (common header)\n");
 146       continue;
 147     }
 148
 149     Child->setParentLoop(nullptr);
 150     NewLoop->addChildLoop(Child);
 151     LLVM_DEBUG(dbgs() << "added child loop to new loop\n");
 152   }
 153 }
 154
 155 // Given a set of blocks and headers in an irreducible SCC, convert it into a
 156 // natural loop. Also insert this new loop at its appropriate place in the
 157 // hierarchy of loops.
 158 static void createNaturalLoopInternal(LoopInfo &LI, DominatorTree &DT,
 159                                       Loop *ParentLoop,
 160                                       SetVector<BasicBlock *> &Blocks,
 161                                       SetVector<BasicBlock *> &Headers) {
 162 #ifndef NDEBUG
 163   // All headers are part of the SCC
 164   for (auto H : Headers) {
 165     assert(Blocks.count(H));
 166   }
 167 #endif
 168
 169   SetVector<BasicBlock *> Predecessors;
 170   for (auto H : Headers) {
 171     for (auto P : predecessors(H)) {
 172       Predecessors.insert(P);
 173     }
 174   }
 175
 176   LLVM_DEBUG(
 177       dbgs() << "Found predecessors:";
 178       for (auto P : Predecessors) {
 179         dbgs() << " " << P->getName();
 180       }
 181       dbgs() << "\n");
 182
 183   // Redirect all the backedges through a "hub" consisting of a series
 184   // of guard blocks that manage the flow of control from the
 185   // predecessors to the headers.
 186   SmallVector<BasicBlock *, 8> GuardBlocks;
 187   DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager);
 188   CreateControlFlowHub(&DTU, GuardBlocks, Predecessors, Headers, "irr");
 189 #if defined(EXPENSIVE_CHECKS)
 190   assert(DT.verify(DominatorTree::VerificationLevel::Full));
 191 #else
 192   assert(DT.verify(DominatorTree::VerificationLevel::Fast));
 193 #endif
 194
 195   // Create a new loop from the now-transformed cycle
 196   auto NewLoop = LI.AllocateLoop();
 197   if (ParentLoop) {
 198     ParentLoop->addChildLoop(NewLoop);
 199   } else {
 200     LI.addTopLevelLoop(NewLoop);
 201   }
 202
 203   // Add the guard blocks to the new loop. The first guard block is
 204   // the head of all the backedges, and it is the first to be inserted
 205   // in the loop. This ensures that it is recognized as the
 206   // header. Since the new loop is already in LoopInfo, the new blocks
 207   // are also propagated up the chain of parent loops.
 208   for (auto G : GuardBlocks) {
 209     LLVM_DEBUG(dbgs() << "added guard block: " << G->getName() << "\n");
 210     NewLoop->addBasicBlockToLoop(G, LI);
 211   }
 212
 213   // Add the SCC blocks to the new loop.
 214   for (auto BB : Blocks) {
 215     NewLoop->addBlockEntry(BB);
 216     if (LI.getLoopFor(BB) == ParentLoop) {
 217       LLVM_DEBUG(dbgs() << "moved block from parent: " << BB->getName()
 218                         << "\n");
 219       LI.changeLoopFor(BB, NewLoop);
 220     } else {
 221       LLVM_DEBUG(dbgs() << "added block from child: " << BB->getName() << "\n");
 222     }
 223   }
 224   LLVM_DEBUG(dbgs() << "header for new loop: "
 225                     << NewLoop->getHeader()->getName() << "\n");
 226
 227   reconnectChildLoops(LI, ParentLoop, NewLoop, Blocks, Headers);
 228
 229   NewLoop->verifyLoop();
 230   if (ParentLoop) {
 231     ParentLoop->verifyLoop();
 232   }
 233 #if defined(EXPENSIVE_CHECKS)
 234   LI.verify(DT);
 235 #endif // EXPENSIVE_CHECKS
 236 }
 237
 238 namespace llvm {
 239 // Enable the graph traits required for traversing a Loop body.
 240 template <> struct GraphTraits<Loop> : LoopBodyTraits {};
 241 } // namespace llvm
 242
 243 // Overloaded wrappers to go with the function template below.
 244 static BasicBlock *unwrapBlock(BasicBlock *B) { return B; }
 245 static BasicBlock *unwrapBlock(LoopBodyTraits::NodeRef &N) { return N.second; }
 246
 247 static void createNaturalLoop(LoopInfo &LI, DominatorTree &DT, Function *F,
 248                               SetVector<BasicBlock *> &Blocks,
 249                               SetVector<BasicBlock *> &Headers) {
 250   createNaturalLoopInternal(LI, DT, nullptr, Blocks, Headers);
 251 }
 252
 253 static void createNaturalLoop(LoopInfo &LI, DominatorTree &DT, Loop &L,
 254                               SetVector<BasicBlock *> &Blocks,
 255                               SetVector<BasicBlock *> &Headers) {
 256   createNaturalLoopInternal(LI, DT, &L, Blocks, Headers);
 257 }
 258
 259 // Convert irreducible SCCs; Graph G may be a Function* or a Loop&.
 260 template <class Graph>
 261 static bool makeReducible(LoopInfo &LI, DominatorTree &DT, Graph &&G) {
 262   bool Changed = false;
 263   for (auto Scc = scc_begin(G); !Scc.isAtEnd(); ++Scc) {
 264     if (Scc->size() < 2)
 265       continue;
 266     SetVector<BasicBlock *> Blocks;
 267     LLVM_DEBUG(dbgs() << "Found SCC:");
 268     for (auto N : *Scc) {
 269       auto BB = unwrapBlock(N);
 270       LLVM_DEBUG(dbgs() << " " << BB->getName());
 271       Blocks.insert(BB);
 272     }
 273     LLVM_DEBUG(dbgs() << "\n");
 274
 275     // Minor optimization: The SCC blocks are usually discovered in an order
 276     // that is the opposite of the order in which these blocks appear as branch
 277     // targets. This results in a lot of condition inversions in the control
 278     // flow out of the new ControlFlowHub, which can be mitigated if the orders
 279     // match. So we discover the headers using the reverse of the block order.
 280     SetVector<BasicBlock *> Headers;
 281     LLVM_DEBUG(dbgs() << "Found headers:");
 282     for (auto BB : reverse(Blocks)) {
 283       for (const auto P : predecessors(BB)) {
 284         // Skip unreachable predecessors.
 285         if (!DT.isReachableFromEntry(P))
 286           continue;
 287         if (!Blocks.count(P)) {
 288           LLVM_DEBUG(dbgs() << " " << BB->getName());
 289           Headers.insert(BB);
 290           break;
 291         }
 292       }
 293     }
 294     LLVM_DEBUG(dbgs() << "\n");
 295
 296     if (Headers.size() == 1) {
 297       assert(LI.isLoopHeader(Headers.front()));
 298       LLVM_DEBUG(dbgs() << "Natural loop with a single header: skipped\n");
 299       continue;
 300     }
 301     createNaturalLoop(LI, DT, G, Blocks, Headers);
 302     Changed = true;
 303   }
 304   return Changed;
 305 }
 306
 307 bool FixIrreducible::runOnFunction(Function &F) {
 308   LLVM_DEBUG(dbgs() << "===== Fix irreducible control-flow in function: "
 309                     << F.getName() << "\n");
 310   auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
 311   auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
 312
 313   bool Changed = false;
 314   SmallVector<Loop *, 8> WorkList;
 315
 316   LLVM_DEBUG(dbgs() << "visiting top-level\n");
 317   Changed |= makeReducible(LI, DT, &F);
 318
 319   // Any SCCs reduced are now already in the list of top-level loops, so simply
 320   // add them all to the worklist.
 321   for (auto L : LI) {
 322     WorkList.push_back(L);
 323   }
 324
 325   while (!WorkList.empty()) {
 326     auto L = WorkList.back();
 327     WorkList.pop_back();
 328     LLVM_DEBUG(dbgs() << "visiting loop with header "
 329                       << L->getHeader()->getName() << "\n");
 330     Changed |= makeReducible(LI, DT, *L);
 331     // Any SCCs reduced are now already in the list of child loops, so simply
 332     // add them all to the worklist.
 333     WorkList.append(L->begin(), L->end());
 334   }
 335
 336   return Changed;
 337 }