NFC: restructure code for CreateControlFlowHub()

[bcahoon]

Summary

This is just moving code around to make it easy to follow and prepare
for the next change to reduce number of live values.

[bcahoon]

Just rebasing. No change intended.

[arsenm]

llvm/lib/Transforms/Utils/BasicBlockUtils.cpp

1634

Don't need .\n

[bcahoon]

Remove \n from assert.

[sameerds]

LGTM, with just one nit.

llvm/lib/Transforms/Utils/BasicBlockUtils.cpp

1667

missing end of sentence?

llvm/lib/Transforms/Utils/BasicBlockUtils.cpp

 //
 // - condition is non-null iff the branch is conditional.
 // - Succ1 is non-null iff the sole/taken target is an outgoing block.
 // - Succ2 is non-null iff condition is non-null and the fallthrough
 //         target is an outgoing block.
 static std::tuple<Value *, BasicBlock *, BasicBlock *>
 redirectToHub(BasicBlock *BB, BasicBlock *FirstGuardBlock,
               const BBSetVector &Outgoing) {
+  assert(isa<BranchInst>(BB->getTerminator()) &&
+         "Only support branch terminator.\n");
   auto Branch = cast<BranchInst>(BB->getTerminator());
   auto Condition = Branch->isConditional() ? Branch->getCondition() : nullptr;
 
   BasicBlock *Succ0 = Branch->getSuccessor(0);
   BasicBlock *Succ1 = nullptr;
   Succ0 = Outgoing.count(Succ0) ? Succ0 : nullptr;
 
   if (Branch->isUnconditional()) {
if (Succ0 && !Succ1) {
       Branch->eraseFromParent();
       BranchInst::Create(FirstGuardBlock, BB);
     }
   }
 
   assert(Succ0 || Succ1);
   return std::make_tuple(Condition, Succ0, Succ1);
 }
+// Setup the branch instructions for guard blocks.
+//
+// Each guard block terminates in a conditional branch that transfers
+// control to the corresponding outgoing block or the next guard
+// block. The last guard block has two outgoing blocks as successors
+// since the condition for the final outgoing block is trivially
+static void setupBranchForGuard(SmallVectorImpl<BasicBlock *> &GuardBlocks,
+                                const BBSetVector &Outgoing,
+                                BBPredicates &GuardPredicates) {
+  // To help keep the loop simple, temporarily append the last
+  // outgoing block to the list of guard blocks.
+  GuardBlocks.push_back(Outgoing.back());
+
+  for (int i = 0, e = GuardBlocks.size() - 1; i != e; ++i) {
+    auto Out = Outgoing[i];
+    assert(GuardPredicates.count(Out));
+    BranchInst::Create(Out, GuardBlocks[i + 1], GuardPredicates[Out],
+                       GuardBlocks[i]);
+  }
+
+  // Remove the last block from the guard list.
+  GuardBlocks.pop_back();
+}
 
 // Capture the existing control flow as guard predicates, and redirect
-// control flow from every incoming block to the first guard block in
-// the hub.
+// control flow from \p Incoming block through the \p GuardBlocks to the
+// \p Outgoing blocks.
 //
 // There is one guard predicate for each outgoing block OutBB. The
-// predicate is a PHINode with one input for each InBB which
-// represents whether the hub should transfer control flow to OutBB if
-// it arrived from InBB. These predicates are NOT ORTHOGONAL. The Hub
-// evaluates them in the same order as the Outgoing set-vector, and
-// control branches to the first outgoing block whose predicate
-// evaluates to true.
-static void convertToGuardPredicates(
-    BasicBlock *FirstGuardBlock, BBPredicates &GuardPredicates,
-    SmallVectorImpl<WeakVH> &DeletionCandidates, const BBSetVector &Incoming,
-    const BBSetVector &Outgoing) {
+// predicate represents whether the hub should transfer control flow
+// to OutBB. These predicates are NOT ORTHOGONAL. The Hub evaluates
+// them in the same order as the Outgoing set-vector, and control
+// branches to the first outgoing block whose predicate evaluates to true.
+static void
+convertToGuardPredicates(SmallVectorImpl<BasicBlock *> &GuardBlocks,
+                         SmallVectorImpl<WeakVH> &DeletionCandidates,
+                         const BBSetVector &Incoming,
+                         const BBSetVector &Outgoing, const StringRef Prefix) {
+  BBPredicates GuardPredicates;
+  auto F = Incoming.front()->getParent();
   auto &Context = Incoming.front()->getContext();
   auto BoolTrue = ConstantInt::getTrue(Context);
   auto BoolFalse = ConstantInt::getFalse(Context);
 
+  for (int i = 0, e = Outgoing.size() - 1; i != e; ++i)
+    GuardBlocks.push_back(
+        BasicBlock::Create(F->getContext(), Prefix + ".guard", F));
+
+  auto FirstGuardBlock = GuardBlocks.front();
+
   // The predicate for the last outgoing is trivially true, and so we
   // process only the first N-1 successors.
   for (int i = 0, e = Outgoing.size() - 1; i != e; ++i) {
     auto Out = Outgoing[i];
     LLVM_DEBUG(dbgs() << "Creating guard for " << Out->getName() << "\n");
+
     auto Phi =
         PHINode::Create(Type::getInt1Ty(Context), Incoming.size(),
                         StringRef("Guard.") + Out->getName(), FirstGuardBlock);
     GuardPredicates[Out] = Phi;
   }
 
   for (auto In : Incoming) {
     Value *Condition;
     BasicBlock *Succ0;
     BasicBlock *Succ1;
     std::tie(Condition, Succ0, Succ1) =
         redirectToHub(In, FirstGuardBlock, Outgoing);
 
     // Optimization: Consider an incoming block A with both successors
     // Succ0 and Succ1 in the set of outgoing blocks. The predicates
     // for Succ0 and Succ1 complement each other. If Succ0 is visited
     // first in the loop below, control will branch to Succ0 using the
     // corresponding predicate. But if that branch is not taken, then
-    // control must reach Succ1, which means that the predicate for
-    // Succ1 is always true.
+    // control must reach Succ1, which means that the incoming value of
+    // the predicate from `In` is true for Succ1.
     bool OneSuccessorDone = false;
     for (int i = 0, e = Outgoing.size() - 1; i != e; ++i) {
       auto Out = Outgoing[i];
       auto Phi = GuardPredicates[Out];
       if (Out != Succ0 && Out != Succ1) {
         Phi->addIncoming(BoolFalse, In);
-        continue;
-      }
+      } else if (!Succ0 || !Succ1 || OneSuccessorDone) {
         // Optimization: When only one successor is an outgoing block,
-      // the predicate is always true.
-      if (!Succ0 || !Succ1 || OneSuccessorDone) {
+        // the incoming predicate from `In` is always true.
         Phi->addIncoming(BoolTrue, In);
-        continue;
-      }
+      } else {
         assert(Succ0 && Succ1);
-      OneSuccessorDone = true;
         if (Out == Succ0) {
           Phi->addIncoming(Condition, In);
-        continue;
-      }
+        } else {
           auto Inverted = invertCondition(Condition);
           DeletionCandidates.push_back(Condition);
           Phi->addIncoming(Inverted, In);
         }
+        OneSuccessorDone = true;
       }
     }
-
-// For each outgoing block OutBB, create a guard block in the Hub. The
-// first guard block was already created outside, and available as the
-// first element in the vector of guard blocks.
-//
-// Each guard block terminates in a conditional branch that transfers
-// control to the corresponding outgoing block or the next guard
-// block. The last guard block has two outgoing blocks as successors
-// since the condition for the final outgoing block is trivially
-// true. So we create one less block (including the first guard block)
-// than the number of outgoing blocks.
-static void createGuardBlocks(SmallVectorImpl<BasicBlock *> &GuardBlocks,
-                              Function *F, const BBSetVector &Outgoing,
-                              BBPredicates &GuardPredicates, StringRef Prefix) {
-  for (int i = 0, e = Outgoing.size() - 2; i != e; ++i) {
-    GuardBlocks.push_back(
-        BasicBlock::Create(F->getContext(), Prefix + ".guard", F));
   }
-  assert(GuardBlocks.size() == GuardPredicates.size());
-
-  // To help keep the loop simple, temporarily append the last
-  // outgoing block to the list of guard blocks.
-  GuardBlocks.push_back(Outgoing.back());
 
-  for (int i = 0, e = GuardBlocks.size() - 1; i != e; ++i) {
-    auto Out = Outgoing[i];
-    assert(GuardPredicates.count(Out));
-    BranchInst::Create(Out, GuardBlocks[i + 1], GuardPredicates[Out],
-                       GuardBlocks[i]);
-  }
-
-  // Remove the last block from the guard list.
-  GuardBlocks.pop_back();
+  setupBranchForGuard(GuardBlocks, Outgoing, GuardPredicates);
 }
 
 BasicBlock *llvm::CreateControlFlowHub(
     DomTreeUpdater *DTU, SmallVectorImpl<BasicBlock *> &GuardBlocks,
     const BBSetVector &Incoming, const BBSetVector &Outgoing,
     const StringRef Prefix) {
-  auto F = Incoming.front()->getParent();
-  auto FirstGuardBlock =
-      BasicBlock::Create(F->getContext(), Prefix + ".guard", F);
+  if (Outgoing.size() < 2)
+    return Outgoing.front();
 
   SmallVector<DominatorTree::UpdateType, 16> Updates;
   if (DTU) {
     for (auto In : Incoming) {
-      Updates.push_back({DominatorTree::Insert, In, FirstGuardBlock});
-      for (auto Succ : successors(In)) {
+      for (auto Succ : successors(In))
         if (Outgoing.count(Succ))
           Updates.push_back({DominatorTree::Delete, In, Succ});
-      }
-    }
-  }
 
-  BBPredicates GuardPredicates;
   SmallVector<WeakVH, 8> DeletionCandidates;
-  convertToGuardPredicates(FirstGuardBlock, GuardPredicates, DeletionCandidates,
-                           Incoming, Outgoing);
+  convertToGuardPredicates(GuardBlocks, DeletionCandidates, Incoming, Outgoing,
+                           Prefix);
 
-  GuardBlocks.push_back(FirstGuardBlock);
-  createGuardBlocks(GuardBlocks, F, Outgoing, GuardPredicates, Prefix);
+  auto FirstGuardBlock = GuardBlocks.front();
 
   // Update the PHINodes in each outgoing block to match the new control flow.
-  for (int i = 0, e = GuardBlocks.size(); i != e; ++i) {
+  for (int i = 0, e = GuardBlocks.size(); i != e; ++i)
     reconnectPhis(Outgoing[i], GuardBlocks[i], Incoming, FirstGuardBlock);
-  }
+
   reconnectPhis(Outgoing.back(), GuardBlocks.back(), Incoming, FirstGuardBlock);
 
   if (DTU) {
     int NumGuards = GuardBlocks.size();
     assert((int)Outgoing.size() == NumGuards + 1);
+
+    for (auto In : Incoming)
+      Updates.push_back({DominatorTree::Insert, In, FirstGuardBlock});
+
     for (int i = 0; i != NumGuards - 1; ++i) {
       Updates.push_back({DominatorTree::Insert, GuardBlocks[i], Outgoing[i]});
       Updates.push_back(
           {DominatorTree::Insert, GuardBlocks[i], GuardBlocks[i + 1]});
     }
     Updates.push_back({DominatorTree::Insert, GuardBlocks[NumGuards - 1],
                        Outgoing[NumGuards - 1]});
     Updates.push_back({DominatorTree::Insert, GuardBlocks[NumGuards - 1],