static bool attemptBranchRemovalFromPhiNodes()

in lib/Optimizer/Scalar/SimplifyCFG.cpp [86:215]
89 lines of code
33 McCabe index (conditional complexity)

static bool attemptBranchRemovalFromPhiNodes(BasicBlock *BB) {
  // Only handle blocks that are a single, unconditional branch.
  if (BB->getTerminator() != &*(BB->begin()) ||
      BB->getTerminator()->getKind() != ValueKind::BranchInstKind) {
    return false;
  }

  // Find our parents and also ensure that there aren't
  // any instructions we can't handle.
  llvh::SmallPtrSet<BasicBlock *, 8> blockParents;
  // Keep unique parents by the original order, which is deterministic.
  llvh::SmallVector<BasicBlock *, 8> orderedParents;
  for (const auto *user : BB->getUsers()) {
    switch (user->getKind()) {
      case ValueKind::BranchInstKind:
      case ValueKind::CondBranchInstKind:
      case ValueKind::SwitchInstKind:
      case ValueKind::GetPNamesInstKind:
      case ValueKind::GetNextPNameInstKind:
        // This is an instruction where the branch argument is a simple
        // jump target that can be substituted for any other branch.
        if (blockParents.count(user->getParent()) == 0) {
          orderedParents.push_back(user->getParent());
        }
        blockParents.insert(user->getParent());
        break;
      case ValueKind::PhiInstKind:
        // The branch argument is not a jump target, but we know how
        // to rewrite them.
        break;
      default:
        // This is some other instruction where we don't know whether we can
        // unconditionally substitute another branch. Bail for safety.
        return false;
    }
  }

  if (blockParents.empty()) {
    return false;
  }

  BasicBlock *phiBlock = nullptr;

  // Verify that we'll be able to rewrite all relevant Phi nodes.
  for (auto *user : BB->getUsers()) {
    if (auto *phi = llvh::dyn_cast<PhiInst>(user)) {
      if (phiBlock && phi->getParent() != phiBlock) {
        // We have PhiInsts in multiple blocks referencing BB, but BB is a
        // single static branch. This is invalid, but the bug is elsewhere.
        llvm_unreachable(
            "Different BBs use Phi for BB with single static jump");
      }
      phiBlock = phi->getParent();

      Value *ourValue = nullptr;
      for (unsigned int i = 0; i < phi->getNumEntries(); i++) {
        auto entry = phi->getEntry(i);
        if (entry.second == BB) {
          if (ourValue) {
            // The incoming phi node is invalid. The problem is not here.
            llvm_unreachable("Phi node has multiple entries for a branch.");
          }
          ourValue = entry.first;
        }
      }

      if (!ourValue) {
        llvm_unreachable("getUsers returned a non-user PhiInst");
      }

      for (unsigned int i = 0; i < phi->getNumEntries(); i++) {
        auto entry = phi->getEntry(i);
        if (blockParents.count(entry.second)) {
          // We have a PhiInst referencing our block BB and its parent, e.g.
          // %BB0:
          // CondBranchInst %1, %BB1, %BB2
          // %BB1:
          // BranchInst %BB2
          // %BB2:
          // PhiInst ??, %BB0, ??, %BB1
          if (entry.first == ourValue) {
            // Fortunately, the two values are equal, so we can rewrite to:
            // PhiInst ??, %BB0
          } else {
            // Unfortunately, the value is different in each case,
            // which naively would have led to an invalid rewrite like:
            // PhiInst %1, %BB0, %2, %BB0
            return false;
          }
        }
      }
    }
  }
  if (!phiBlock) {
    llvm_unreachable("We shouldn't be in this function if there are no Phis.");
  }

  // This branch is removable. Start by rewriting the Phi nodes.
  for (auto *user : BB->getUsers()) {
    if (auto *phi = llvh::dyn_cast<PhiInst>(user)) {
      Value *ourValue = nullptr;

      const unsigned int numEntries = phi->getNumEntries();
      for (unsigned int i = 0; i < numEntries; i++) {
        auto entry = phi->getEntry(i);
        if (entry.second == BB) {
          ourValue = entry.first;
        }
      }
      assert(ourValue && "getUsers returned a non-user PhiInst");

      for (int i = phi->getNumEntries() - 1; i >= 0; i--) {
        auto pair = phi->getEntry(i);
        if (pair.second == BB || blockParents.count(pair.second)) {
          phi->removeEntry(i);
        }
      }

      // Add parents back in sorted order to avoid any non-determinism
      for (BasicBlock *parent : orderedParents) {
        phi->addEntry(ourValue, parent);
      }
    }
  }
  // We verified earlier that all uses are branches and phis, so now that
  // we've rewritten the phis, we can have all branches jump there directly.
  BB->replaceAllUsesWith(phiBlock);
  BB->eraseFromParent();
  return true;
}