Separate Machine IR from CodeGen: Move SplitCriticalEdge out of MachineBasicBlock

[arphaman]

Summary

This patch is related to my proposal for separating machine IR from CodeGen: http://lists.cs.uiuc.edu/pipermail/llvmdev/2015-May/086063.html.

This patch moves the SplitCriticalEdge method out of MachineBasicBlock class so that MachineBasicBlock.cpp won't have to include several header
files that declare passes that won't be moved from CodeGen to the new Machine IR library.

[arphaman]

I've updated the patch based on Duncan's comments:

• Renamed the cpp + header files 'MachineIRUtils' to 'SplitCriticalEdge'
• Fixed the function's name (it starts with lowercase now)
• Got rid of unnecessary namespace
• Fixed the function's comment

include/llvm/CodeGen/MachineBasicBlock.h

 
 #include "llvm/ADT/GraphTraits.h"
 #include "llvm/CodeGen/MachineInstr.h"
 #include "llvm/Support/DataTypes.h"
 #include <functional>
 
 namespace llvm {
 
-class Pass;
 class BasicBlock;
 class MachineFunction;
 class MCSymbol;
 class SlotIndexes;
 class StringRef;
 class raw_ostream;
 class MachineBranchProbabilityInfo;
 
public:
   /// and return an instr_iterator instead.
   instr_iterator getFirstInstrTerminator();
 
   /// getLastNonDebugInstr - returns an iterator to the last non-debug
   /// instruction in the basic block, or end()
   iterator getLastNonDebugInstr();
   const_iterator getLastNonDebugInstr() const;
 
-  /// SplitCriticalEdge - Split the critical edge from this block to the
-  /// given successor block, and return the newly created block, or null
-  /// if splitting is not possible.
-  ///
-  /// This function updates LiveVariables, MachineDominatorTree, and
-  /// MachineLoopInfo, as applicable.
-  MachineBasicBlock *SplitCriticalEdge(MachineBasicBlock *Succ, Pass *P);
-
   void pop_front() { Insts.pop_front(); }
   void pop_back() { Insts.pop_back(); }
   void push_back(MachineInstr *MI) { Insts.push_back(MI); }
 
   /// Insert MI into the instruction list before I, possibly inside a bundle.
   ///
   /// If the insertion point is inside a bundle, MI will be added to the bundle,
   /// otherwise MI will not be added to any bundle. That means this function

include/llvm/CodeGen/SplitCriticalEdge.h

+//===-- llvm/CodeGen/SplitCriticalEdge.h ------------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file declares a function that splits a critical edge from a basic block.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CODEGEN_SPLITCRITICALEDGE_H
+#define LLVM_CODEGEN_SPLITCRITICALEDGE_H
+
+namespace llvm {
+
+class Pass;
+class MachineBasicBlock;
+
+/// Split the critical edge from the block BB to the given successor block, and
+/// return the newly created block, or null if splitting is not possible.
+///
+/// This function updates LiveVariables, MachineDominatorTree, and
+/// MachineLoopInfo, as applicable.
+MachineBasicBlock *splitCriticalEdge(MachineBasicBlock *BB,
+                                     MachineBasicBlock *Succ, Pass *P);
+
+} // End namespace llvm
+
+#endif

lib/CodeGen/CMakeLists.txt

add_llvm_library(LLVMCodeGen
   ScheduleDAGPrinter.cpp
   ScoreboardHazardRecognizer.cpp
   ShrinkWrap.cpp
   ShadowStackGC.cpp
   ShadowStackGCLowering.cpp
   SjLjEHPrepare.cpp
   SlotIndexes.cpp
   SpillPlacement.cpp
+  SplitCriticalEdge.cpp
   SplitKit.cpp
   StackColoring.cpp
   StackProtector.cpp
   StackSlotColoring.cpp
   StackMapLivenessAnalysis.cpp
   StackMaps.cpp
   StatepointExampleGC.cpp
   TailDuplication.cpp

lib/CodeGen/MachineBasicBlock.cpp

 //===-- llvm/CodeGen/MachineBasicBlock.cpp ----------------------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // Collect the sequence of machine instructions for a basic block.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/CodeGen/MachineBasicBlock.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallString.h"
-#include "llvm/CodeGen/LiveIntervalAnalysis.h"
-#include "llvm/CodeGen/LiveVariables.h"
-#include "llvm/CodeGen/MachineDominators.h"
 #include "llvm/CodeGen/MachineFunction.h"
 #include "llvm/CodeGen/MachineInstrBuilder.h"
-#include "llvm/CodeGen/MachineLoopInfo.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/CodeGen/SlotIndexes.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/MC/MCAsmInfo.h"
 #include "llvm/MC/MCContext.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
bool MachineBasicBlock::canFallThrough() {
   // doesn't fall through.
   if (Cond.empty()) return false;
 
   // Otherwise, if it is conditional and has no explicit false block, it falls
   // through.
   return FBB == nullptr;
 }
 
-MachineBasicBlock *
-MachineBasicBlock::SplitCriticalEdge(MachineBasicBlock *Succ, Pass *P) {
-  // Splitting the critical edge to a landing pad block is non-trivial. Don't do
-  // it in this generic function.
-  if (Succ->isLandingPad())
-    return nullptr;
-
-  MachineFunction *MF = getParent();
-  DebugLoc dl;  // FIXME: this is nowhere
-
-  // Performance might be harmed on HW that implements branching using exec mask
-  // where both sides of the branches are always executed.
-  if (MF->getTarget().requiresStructuredCFG())
-    return nullptr;
-
-  // We may need to update this's terminator, but we can't do that if
-  // AnalyzeBranch fails. If this uses a jump table, we won't touch it.
-  const TargetInstrInfo *TII = MF->getSubtarget().getInstrInfo();
-  MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
-  SmallVector<MachineOperand, 4> Cond;
-  if (TII->AnalyzeBranch(*this, TBB, FBB, Cond))
-    return nullptr;
-
-  // Avoid bugpoint weirdness: A block may end with a conditional branch but
-  // jumps to the same MBB is either case. We have duplicate CFG edges in that
-  // case that we can't handle. Since this never happens in properly optimized
-  // code, just skip those edges.
-  if (TBB && TBB == FBB) {
-    DEBUG(dbgs() << "Won't split critical edge after degenerate BB#"
-                 << getNumber() << '\n');
-    return nullptr;
-  }
-
-  MachineBasicBlock *NMBB = MF->CreateMachineBasicBlock();
-  MF->insert(std::next(MachineFunction::iterator(this)), NMBB);
-  DEBUG(dbgs() << "Splitting critical edge:"
-        " BB#" << getNumber()
-        << " -- BB#" << NMBB->getNumber()
-        << " -- BB#" << Succ->getNumber() << '\n');
-
-  LiveIntervals *LIS = P->getAnalysisIfAvailable<LiveIntervals>();
-  SlotIndexes *Indexes = P->getAnalysisIfAvailable<SlotIndexes>();
-  if (LIS)
-    LIS->insertMBBInMaps(NMBB);
-  else if (Indexes)
-    Indexes->insertMBBInMaps(NMBB);
-
-  // On some targets like Mips, branches may kill virtual registers. Make sure
-  // that LiveVariables is properly updated after updateTerminator replaces the
-  // terminators.
-  LiveVariables *LV = P->getAnalysisIfAvailable<LiveVariables>();
-
-  // Collect a list of virtual registers killed by the terminators.
-  SmallVector<unsigned, 4> KilledRegs;
-  if (LV)
-    for (instr_iterator I = getFirstInstrTerminator(), E = instr_end();
-         I != E; ++I) {
-      MachineInstr *MI = I;
-      for (MachineInstr::mop_iterator OI = MI->operands_begin(),
-           OE = MI->operands_end(); OI != OE; ++OI) {
-        if (!OI->isReg() || OI->getReg() == 0 ||
-            !OI->isUse() || !OI->isKill() || OI->isUndef())
-          continue;
-        unsigned Reg = OI->getReg();
-        if (TargetRegisterInfo::isPhysicalRegister(Reg) ||
-            LV->getVarInfo(Reg).removeKill(MI)) {
-          KilledRegs.push_back(Reg);
-          DEBUG(dbgs() << "Removing terminator kill: " << *MI);
-          OI->setIsKill(false);
-        }
-      }
-    }
-
-  SmallVector<unsigned, 4> UsedRegs;
-  if (LIS) {
-    for (instr_iterator I = getFirstInstrTerminator(), E = instr_end();
-         I != E; ++I) {
-      MachineInstr *MI = I;
-
-      for (MachineInstr::mop_iterator OI = MI->operands_begin(),
-           OE = MI->operands_end(); OI != OE; ++OI) {
-        if (!OI->isReg() || OI->getReg() == 0)
-          continue;
-
-        unsigned Reg = OI->getReg();
-        if (std::find(UsedRegs.begin(), UsedRegs.end(), Reg) == UsedRegs.end())
-          UsedRegs.push_back(Reg);
-      }
-    }
-  }
-
-  ReplaceUsesOfBlockWith(Succ, NMBB);
-
-  // If updateTerminator() removes instructions, we need to remove them from
-  // SlotIndexes.
-  SmallVector<MachineInstr*, 4> Terminators;
-  if (Indexes) {
-    for (instr_iterator I = getFirstInstrTerminator(), E = instr_end();
-         I != E; ++I)
-      Terminators.push_back(I);
-  }
-
-  updateTerminator();
-
-  if (Indexes) {
-    SmallVector<MachineInstr*, 4> NewTerminators;
-    for (instr_iterator I = getFirstInstrTerminator(), E = instr_end();
-         I != E; ++I)
-      NewTerminators.push_back(I);
-
-    for (SmallVectorImpl<MachineInstr*>::iterator I = Terminators.begin(),
-        E = Terminators.end(); I != E; ++I) {
-      if (std::find(NewTerminators.begin(), NewTerminators.end(), *I) ==
-          NewTerminators.end())
-       Indexes->removeMachineInstrFromMaps(*I);
-    }
-  }
-
-  // Insert unconditional "jump Succ" instruction in NMBB if necessary.
-  NMBB->addSuccessor(Succ);
-  if (!NMBB->isLayoutSuccessor(Succ)) {
-    Cond.clear();
-    MF->getSubtarget().getInstrInfo()->InsertBranch(*NMBB, Succ, nullptr, Cond,
-                                                    dl);
-
-    if (Indexes) {
-      for (instr_iterator I = NMBB->instr_begin(), E = NMBB->instr_end();
-           I != E; ++I) {
-        // Some instructions may have been moved to NMBB by updateTerminator(),
-        // so we first remove any instruction that already has an index.
-        if (Indexes->hasIndex(I))
-          Indexes->removeMachineInstrFromMaps(I);
-        Indexes->insertMachineInstrInMaps(I);
-      }
-    }
-  }
-
-  // Fix PHI nodes in Succ so they refer to NMBB instead of this
-  for (MachineBasicBlock::instr_iterator
-         i = Succ->instr_begin(),e = Succ->instr_end();
-       i != e && i->isPHI(); ++i)
-    for (unsigned ni = 1, ne = i->getNumOperands(); ni != ne; ni += 2)
-      if (i->getOperand(ni+1).getMBB() == this)
-        i->getOperand(ni+1).setMBB(NMBB);
-
-  // Inherit live-ins from the successor
-  for (MachineBasicBlock::livein_iterator I = Succ->livein_begin(),
-         E = Succ->livein_end(); I != E; ++I)
-    NMBB->addLiveIn(*I);
-
-  // Update LiveVariables.
-  const TargetRegisterInfo *TRI = MF->getSubtarget().getRegisterInfo();
-  if (LV) {
-    // Restore kills of virtual registers that were killed by the terminators.
-    while (!KilledRegs.empty()) {
-      unsigned Reg = KilledRegs.pop_back_val();
-      for (instr_iterator I = instr_end(), E = instr_begin(); I != E;) {
-        if (!(--I)->addRegisterKilled(Reg, TRI, /* addIfNotFound= */ false))
-          continue;
-        if (TargetRegisterInfo::isVirtualRegister(Reg))
-          LV->getVarInfo(Reg).Kills.push_back(I);
-        DEBUG(dbgs() << "Restored terminator kill: " << *I);
-        break;
-      }
-    }
-    // Update relevant live-through information.
-    LV->addNewBlock(NMBB, this, Succ);
-  }
-
-  if (LIS) {
-    // After splitting the edge and updating SlotIndexes, live intervals may be
-    // in one of two situations, depending on whether this block was the last in
-    // the function. If the original block was the last in the function, all live
-    // intervals will end prior to the beginning of the new split block. If the
-    // original block was not at the end of the function, all live intervals will
-    // extend to the end of the new split block.
-
-    bool isLastMBB =
-      std::next(MachineFunction::iterator(NMBB)) == getParent()->end();
-
-    SlotIndex StartIndex = Indexes->getMBBEndIdx(this);
-    SlotIndex PrevIndex = StartIndex.getPrevSlot();
-    SlotIndex EndIndex = Indexes->getMBBEndIdx(NMBB);
-
-    // Find the registers used from NMBB in PHIs in Succ.
-    SmallSet<unsigned, 8> PHISrcRegs;
-    for (MachineBasicBlock::instr_iterator
-         I = Succ->instr_begin(), E = Succ->instr_end();
-         I != E && I->isPHI(); ++I) {
-      for (unsigned ni = 1, ne = I->getNumOperands(); ni != ne; ni += 2) {
-        if (I->getOperand(ni+1).getMBB() == NMBB) {
-          MachineOperand &MO = I->getOperand(ni);
-          unsigned Reg = MO.getReg();
-          PHISrcRegs.insert(Reg);
-          if (MO.isUndef())
-            continue;
-
-          LiveInterval &LI = LIS->getInterval(Reg);
-          VNInfo *VNI = LI.getVNInfoAt(PrevIndex);
-          assert(VNI && "PHI sources should be live out of their predecessors.");
-          LI.addSegment(LiveInterval::Segment(StartIndex, EndIndex, VNI));
-        }
-      }
-    }
-
-    MachineRegisterInfo *MRI = &getParent()->getRegInfo();
-    for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
-      unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
-      if (PHISrcRegs.count(Reg) || !LIS->hasInterval(Reg))
-        continue;
-
-      LiveInterval &LI = LIS->getInterval(Reg);
-      if (!LI.liveAt(PrevIndex))
-        continue;
-
-      bool isLiveOut = LI.liveAt(LIS->getMBBStartIdx(Succ));
-      if (isLiveOut && isLastMBB) {
-        VNInfo *VNI = LI.getVNInfoAt(PrevIndex);
-        assert(VNI && "LiveInterval should have VNInfo where it is live.");
-        LI.addSegment(LiveInterval::Segment(StartIndex, EndIndex, VNI));
-      } else if (!isLiveOut && !isLastMBB) {
-        LI.removeSegment(StartIndex, EndIndex);
-      }
-    }
-
-    // Update all intervals for registers whose uses may have been modified by
-    // updateTerminator().
-    LIS->repairIntervalsInRange(this, getFirstTerminator(), end(), UsedRegs);
-  }
-
-  if (MachineDominatorTree *MDT =
-      P->getAnalysisIfAvailable<MachineDominatorTree>())
-    MDT->recordSplitCriticalEdge(this, Succ, NMBB);
-
-  if (MachineLoopInfo *MLI = P->getAnalysisIfAvailable<MachineLoopInfo>())
-    if (MachineLoop *TIL = MLI->getLoopFor(this)) {
-      // If one or the other blocks were not in a loop, the new block is not
-      // either, and thus LI doesn't need to be updated.
-      if (MachineLoop *DestLoop = MLI->getLoopFor(Succ)) {
-        if (TIL == DestLoop) {
-          // Both in the same loop, the NMBB joins loop.
-          DestLoop->addBasicBlockToLoop(NMBB, MLI->getBase());
-        } else if (TIL->contains(DestLoop)) {
-          // Edge from an outer loop to an inner loop.  Add to the outer loop.
-          TIL->addBasicBlockToLoop(NMBB, MLI->getBase());
-        } else if (DestLoop->contains(TIL)) {
-          // Edge from an inner loop to an outer loop.  Add to the outer loop.
-          DestLoop->addBasicBlockToLoop(NMBB, MLI->getBase());
-        } else {
-          // Edge from two loops with no containment relation.  Because these
-          // are natural loops, we know that the destination block must be the
-          // header of its loop (adding a branch into a loop elsewhere would
-          // create an irreducible loop).
-          assert(DestLoop->getHeader() == Succ &&
-                 "Should not create irreducible loops!");
-          if (MachineLoop *P = DestLoop->getParentLoop())
-            P->addBasicBlockToLoop(NMBB, MLI->getBase());
-        }
-      }
-    }
-
-  return NMBB;
-}
-
 /// Prepare MI to be removed from its bundle. This fixes bundle flags on MI's
 /// neighboring instructions so the bundle won't be broken by removing MI.
 static void unbundleSingleMI(MachineInstr *MI) {
   // Removing the first instruction in a bundle.
   if (MI->isBundledWithSucc() && !MI->isBundledWithPred())
     MI->unbundleFromSucc();
   // Removing the last instruction in a bundle.
   if (MI->isBundledWithPred() && !MI->isBundledWithSucc())

lib/CodeGen/MachineLICM.cpp

 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/CodeGen/MachineDominators.h"
 #include "llvm/CodeGen/MachineFrameInfo.h"
 #include "llvm/CodeGen/MachineLoopInfo.h"
 #include "llvm/CodeGen/MachineMemOperand.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/CodeGen/PseudoSourceValue.h"
+#include "llvm/CodeGen/SplitCriticalEdge.h"
 #include "llvm/MC/MCInstrItineraries.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Target/TargetInstrInfo.h"
 #include "llvm/Target/TargetLowering.h"
 #include "llvm/Target/TargetMachine.h"
 #include "llvm/Target/TargetRegisterInfo.h"
if (!CurPreheader) {
     CurPreheader = CurLoop->getLoopPreheader();
     if (!CurPreheader) {
       MachineBasicBlock *Pred = CurLoop->getLoopPredecessor();
       if (!Pred) {
         CurPreheader = reinterpret_cast<MachineBasicBlock *>(-1);
         return nullptr;
       }
 
-      CurPreheader = Pred->SplitCriticalEdge(CurLoop->getHeader(), this);
+      CurPreheader = splitCriticalEdge(Pred, CurLoop->getHeader(), this);
       if (!CurPreheader) {
         CurPreheader = reinterpret_cast<MachineBasicBlock *>(-1);
         return nullptr;
       }
     }
   }
   return CurPreheader;
 }

lib/CodeGen/MachineSink.cpp

 #include "llvm/ADT/SparseBitVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
 #include "llvm/CodeGen/MachineDominators.h"
 #include "llvm/CodeGen/MachineLoopInfo.h"
 #include "llvm/CodeGen/MachinePostDominators.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
+#include "llvm/CodeGen/SplitCriticalEdge.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Target/TargetInstrInfo.h"
 #include "llvm/Target/TargetRegisterInfo.h"
 #include "llvm/Target/TargetSubtargetInfo.h"
 using namespace llvm;
 
while (1) {
     CEBCandidates.clear();
     ToSplit.clear();
     for (MachineFunction::iterator I = MF.begin(), E = MF.end();
          I != E; ++I)
       MadeChange |= ProcessBlock(*I);
 
     // If we have anything we marked as toSplit, split it now.
     for (auto &Pair : ToSplit) {
-      auto NewSucc = Pair.first->SplitCriticalEdge(Pair.second, this);
+      auto NewSucc = splitCriticalEdge(Pair.first, Pair.second, this);
       if (NewSucc != nullptr) {
         DEBUG(dbgs() << " *** Splitting critical edge:"
               " BB#" << Pair.first->getNumber()
               << " -- BB#" << NewSucc->getNumber()
               << " -- BB#" << Pair.second->getNumber() << '\n');
         MadeChange = true;
         ++NumSplit;
       } else

lib/CodeGen/PHIElimination.cpp

 #include "llvm/ADT/Statistic.h"
 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
 #include "llvm/CodeGen/LiveVariables.h"
 #include "llvm/CodeGen/MachineDominators.h"
 #include "llvm/CodeGen/MachineInstr.h"
 #include "llvm/CodeGen/MachineInstrBuilder.h"
 #include "llvm/CodeGen/MachineLoopInfo.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
+#include "llvm/CodeGen/SplitCriticalEdge.h"
 #include "llvm/IR/Function.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Compiler.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Target/TargetInstrInfo.h"
 #include "llvm/Target/TargetSubtargetInfo.h"
 #include <algorithm>
for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2) {
         // This edge could be entering a loop, exiting a loop, or it could be
         // both: Jumping directly form one loop to the header of a sibling
         // loop.
         // Split unless this edge is entering CurLoop from an outer loop.
         ShouldSplit = PreLoop && !PreLoop->contains(CurLoop);
       }
       if (!ShouldSplit && !SplitAllCriticalEdges)
         continue;
-      if (!PreMBB->SplitCriticalEdge(&MBB, this)) {
+      if (!splitCriticalEdge(PreMBB, &MBB, this)) {
         DEBUG(dbgs() << "Failed to split critical edge.\n");
         continue;
       }
       Changed = true;
       ++NumCriticalEdgesSplit;
     }
   }
   return Changed;

lib/CodeGen/SplitCriticalEdge.cpp

+//===-- llvm/CodeGen/SplitCriticalEdge.cpp ----------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements a function that splits a critical edge from a basic
+// block.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/CodeGen/SplitCriticalEdge.h"
+#include "llvm/CodeGen/LiveIntervalAnalysis.h"
+#include "llvm/CodeGen/LiveVariables.h"
+#include "llvm/CodeGen/MachineDominators.h"
+#include "llvm/CodeGen/MachineFunction.h"
+#include "llvm/CodeGen/MachineLoopInfo.h"
+#include "llvm/CodeGen/MachineRegisterInfo.h"
+#include "llvm/CodeGen/SlotIndexes.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/raw_ostream.h"
+#include "llvm/Target/TargetInstrInfo.h"
+#include "llvm/Target/TargetMachine.h"
+#include "llvm/Target/TargetRegisterInfo.h"
+#include <algorithm>
+using namespace llvm;
+
+#define DEBUG_TYPE "codegen"
+
+MachineBasicBlock *llvm::splitCriticalEdge(MachineBasicBlock *BB,
+                                           MachineBasicBlock *Succ, Pass *P) {
+  // Splitting the critical edge to a landing pad block is non-trivial. Don't do
+  // it in this generic function.
+  if (Succ->isLandingPad())
+    return nullptr;
+
+  MachineFunction *MF = BB->getParent();
+  DebugLoc dl; // FIXME: this is nowhere
+
+  // Performance might be harmed on HW that implements branching using exec mask
+  // where both sides of the branches are always executed.
+  if (MF->getTarget().requiresStructuredCFG())
+    return nullptr;
+
+  // We may need to update this's terminator, but we can't do that if
+  // AnalyzeBranch fails. If this uses a jump table, we won't touch it.
+  const TargetInstrInfo *TII = MF->getSubtarget().getInstrInfo();
+  MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
+  SmallVector<MachineOperand, 4> Cond;
+  if (TII->AnalyzeBranch(*BB, TBB, FBB, Cond))
+    return nullptr;
+
+  // Avoid bugpoint weirdness: A block may end with a conditional branch but
+  // jumps to the same MBB is either case. We have duplicate CFG edges in that
+  // case that we can't handle. Since this never happens in properly optimized
+  // code, just skip those edges.
+  if (TBB && TBB == FBB) {
+    DEBUG(dbgs() << "Won't split critical edge after degenerate BB#"
+                 << BB->getNumber() << '\n');
+    return nullptr;
+  }
+
+  MachineBasicBlock *NMBB = MF->CreateMachineBasicBlock();
+  MF->insert(std::next(MachineFunction::iterator(BB)), NMBB);
+  DEBUG(dbgs() << "Splitting critical edge:"
+                  " BB#" << BB->getNumber() << " -- BB#" << NMBB->getNumber()
+               << " -- BB#" << Succ->getNumber() << '\n');
+
+  LiveIntervals *LIS = P->getAnalysisIfAvailable<LiveIntervals>();
+  SlotIndexes *Indexes = P->getAnalysisIfAvailable<SlotIndexes>();
+  if (LIS)
+    LIS->insertMBBInMaps(NMBB);
+  else if (Indexes)
+    Indexes->insertMBBInMaps(NMBB);
+
+  // On some targets like Mips, branches may kill virtual registers. Make sure
+  // that LiveVariables is properly updated after updateTerminator replaces the
+  // terminators.
+  LiveVariables *LV = P->getAnalysisIfAvailable<LiveVariables>();
+
+  // Collect a list of virtual registers killed by the terminators.
+  SmallVector<unsigned, 4> KilledRegs;
+  if (LV)
+    for (MachineBasicBlock::instr_iterator I = BB->getFirstInstrTerminator(),
+                                           E = BB->instr_end();
+         I != E; ++I) {
+      MachineInstr *MI = I;
+      for (MachineInstr::mop_iterator OI = MI->operands_begin(),
+                                      OE = MI->operands_end();
+           OI != OE; ++OI) {
+        if (!OI->isReg() || OI->getReg() == 0 || !OI->isUse() ||
+            !OI->isKill() || OI->isUndef())
+          continue;
+        unsigned Reg = OI->getReg();
+        if (TargetRegisterInfo::isPhysicalRegister(Reg) ||
+            LV->getVarInfo(Reg).removeKill(MI)) {
+          KilledRegs.push_back(Reg);
+          DEBUG(dbgs() << "Removing terminator kill: " << *MI);
+          OI->setIsKill(false);
+        }
+      }
+    }
+
+  SmallVector<unsigned, 4> UsedRegs;
+  if (LIS) {
+    for (MachineBasicBlock::instr_iterator I = BB->getFirstInstrTerminator(),
+                                           E = BB->instr_end();
+         I != E; ++I) {
+      MachineInstr *MI = I;
+
+      for (MachineInstr::mop_iterator OI = MI->operands_begin(),
+                                      OE = MI->operands_end();
+           OI != OE; ++OI) {
+        if (!OI->isReg() || OI->getReg() == 0)
+          continue;
+
+        unsigned Reg = OI->getReg();
+        if (std::find(UsedRegs.begin(), UsedRegs.end(), Reg) == UsedRegs.end())
+          UsedRegs.push_back(Reg);
+      }
+    }
+  }
+
+  BB->ReplaceUsesOfBlockWith(Succ, NMBB);
+
+  // If updateTerminator() removes instructions, we need to remove them from
+  // SlotIndexes.
+  SmallVector<MachineInstr *, 4> Terminators;
+  if (Indexes) {
+    for (MachineBasicBlock::instr_iterator I = BB->getFirstInstrTerminator(),
+                                           E = BB->instr_end();
+         I != E; ++I)
+      Terminators.push_back(I);
+  }
+
+  BB->updateTerminator();
+
+  if (Indexes) {
+    SmallVector<MachineInstr *, 4> NewTerminators;
+    for (MachineBasicBlock::instr_iterator I = BB->getFirstInstrTerminator(),
+                                           E = BB->instr_end();
+         I != E; ++I)
+      NewTerminators.push_back(I);
+
+    for (SmallVectorImpl<MachineInstr *>::iterator I = Terminators.begin(),
+                                                   E = Terminators.end();
+         I != E; ++I) {
+      if (std::find(NewTerminators.begin(), NewTerminators.end(), *I) ==
+          NewTerminators.end())
+        Indexes->removeMachineInstrFromMaps(*I);
+    }
+  }
+
+  // Insert unconditional "jump Succ" instruction in NMBB if necessary.
+  NMBB->addSuccessor(Succ);
+  if (!NMBB->isLayoutSuccessor(Succ)) {
+    Cond.clear();
+    MF->getSubtarget().getInstrInfo()->InsertBranch(*NMBB, Succ, nullptr, Cond,
+                                                    dl);
+
+    if (Indexes) {
+      for (MachineBasicBlock::instr_iterator I = NMBB->instr_begin(),
+                                             E = NMBB->instr_end();
+           I != E; ++I) {
+        // Some instructions may have been moved to NMBB by updateTerminator(),
+        // so we first remove any instruction that already has an index.
+        if (Indexes->hasIndex(I))
+          Indexes->removeMachineInstrFromMaps(I);
+        Indexes->insertMachineInstrInMaps(I);
+      }
+    }
+  }
+
+  // Fix PHI nodes in Succ so they refer to NMBB instead of this
+  for (MachineBasicBlock::instr_iterator i = Succ->instr_begin(),
+                                         e = Succ->instr_end();
+       i != e && i->isPHI(); ++i)
+    for (unsigned ni = 1, ne = i->getNumOperands(); ni != ne; ni += 2)
+      if (i->getOperand(ni + 1).getMBB() == BB)
+        i->getOperand(ni + 1).setMBB(NMBB);
+
+  // Inherit live-ins from the successor
+  for (MachineBasicBlock::livein_iterator I = Succ->livein_begin(),
+                                          E = Succ->livein_end();
+       I != E; ++I)
+    NMBB->addLiveIn(*I);
+
+  // Update LiveVariables.
+  const TargetRegisterInfo *TRI = MF->getSubtarget().getRegisterInfo();
+  if (LV) {
+    // Restore kills of virtual registers that were killed by the terminators.
+    while (!KilledRegs.empty()) {
+      unsigned Reg = KilledRegs.pop_back_val();
+      for (MachineBasicBlock::instr_iterator I = BB->instr_end(),
+                                             E = BB->instr_begin();
+           I != E;) {
+        if (!(--I)->addRegisterKilled(Reg, TRI, /* addIfNotFound= */ false))
+          continue;
+        if (TargetRegisterInfo::isVirtualRegister(Reg))
+          LV->getVarInfo(Reg).Kills.push_back(I);
+        DEBUG(dbgs() << "Restored terminator kill: " << *I);
+        break;
+      }
+    }
+    // Update relevant live-through information.
+    LV->addNewBlock(NMBB, BB, Succ);
+  }
+
+  if (LIS) {
+    // After splitting the edge and updating SlotIndexes, live intervals may be
+    // in one of two situations, depending on whether this block was the last in
+    // the function. If the original block was the last in the function, all
+    // live
+    // intervals will end prior to the beginning of the new split block. If the
+    // original block was not at the end of the function, all live intervals
+    // will
+    // extend to the end of the new split block.
+
+    bool isLastMBB = std::next(MachineFunction::iterator(NMBB)) == MF->end();
+
+    SlotIndex StartIndex = Indexes->getMBBEndIdx(BB);
+    SlotIndex PrevIndex = StartIndex.getPrevSlot();
+    SlotIndex EndIndex = Indexes->getMBBEndIdx(NMBB);
+
+    // Find the registers used from NMBB in PHIs in Succ.
+    SmallSet<unsigned, 8> PHISrcRegs;
+    for (MachineBasicBlock::instr_iterator I = Succ->instr_begin(),
+                                           E = Succ->instr_end();
+         I != E && I->isPHI(); ++I) {
+      for (unsigned ni = 1, ne = I->getNumOperands(); ni != ne; ni += 2) {
+        if (I->getOperand(ni + 1).getMBB() == NMBB) {
+          MachineOperand &MO = I->getOperand(ni);
+          unsigned Reg = MO.getReg();
+          PHISrcRegs.insert(Reg);
+          if (MO.isUndef())
+            continue;
+
+          LiveInterval &LI = LIS->getInterval(Reg);
+          VNInfo *VNI = LI.getVNInfoAt(PrevIndex);
+          assert(VNI &&
+                 "PHI sources should be live out of their predecessors.");
+          LI.addSegment(LiveInterval::Segment(StartIndex, EndIndex, VNI));
+        }
+      }
+    }
+
+    MachineRegisterInfo *MRI = &MF->getRegInfo();
+    for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
+      unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
+      if (PHISrcRegs.count(Reg) || !LIS->hasInterval(Reg))
+        continue;
+
+      LiveInterval &LI = LIS->getInterval(Reg);
+      if (!LI.liveAt(PrevIndex))
+        continue;
+
+      bool isLiveOut = LI.liveAt(LIS->getMBBStartIdx(Succ));
+      if (isLiveOut && isLastMBB) {
+        VNInfo *VNI = LI.getVNInfoAt(PrevIndex);
+        assert(VNI && "LiveInterval should have VNInfo where it is live.");
+        LI.addSegment(LiveInterval::Segment(StartIndex, EndIndex, VNI));
+      } else if (!isLiveOut && !isLastMBB) {
+        LI.removeSegment(StartIndex, EndIndex);
+      }
+    }
+
+    // Update all intervals for registers whose uses may have been modified by
+    // updateTerminator().
+    LIS->repairIntervalsInRange(BB, BB->getFirstTerminator(), BB->end(),
+                                UsedRegs);
+  }
+
+  if (MachineDominatorTree *MDT =
+          P->getAnalysisIfAvailable<MachineDominatorTree>())
+    MDT->recordSplitCriticalEdge(BB, Succ, NMBB);
+
+  if (MachineLoopInfo *MLI = P->getAnalysisIfAvailable<MachineLoopInfo>())
+    if (MachineLoop *TIL = MLI->getLoopFor(BB)) {
+      // If one or the other blocks were not in a loop, the new block is not
+      // either, and thus LI doesn't need to be updated.
+      if (MachineLoop *DestLoop = MLI->getLoopFor(Succ)) {
+        if (TIL == DestLoop) {
+          // Both in the same loop, the NMBB joins loop.
+          DestLoop->addBasicBlockToLoop(NMBB, MLI->getBase());
+        } else if (TIL->contains(DestLoop)) {
+          // Edge from an outer loop to an inner loop.  Add to the outer loop.
+          TIL->addBasicBlockToLoop(NMBB, MLI->getBase());
+        } else if (DestLoop->contains(TIL)) {
+          // Edge from an inner loop to an outer loop.  Add to the outer loop.
+          DestLoop->addBasicBlockToLoop(NMBB, MLI->getBase());
+        } else {
+          // Edge from two loops with no containment relation.  Because these
+          // are natural loops, we know that the destination block must be the
+          // header of its loop (adding a branch into a loop elsewhere would
+          // create an irreducible loop).
+          assert(DestLoop->getHeader() == Succ &&
+                 "Should not create irreducible loops!");
+          if (MachineLoop *P = DestLoop->getParentLoop())
+            P->addBasicBlockToLoop(NMBB, MLI->getBase());
+        }
+      }
+    }
+
+  return NMBB;
+}