Add a PreRASplit pass to enable more shrinkwrap

[wmi]

Summary

The patch is to solve the problem mentioned in PR29154.

This pass tries to split the live ranges of params which are passed via hard registers and live across calls inside the function. The live range of such param could be split into two parts: The first part contains the copy from param passing register and will never live across call, so it gets the freedom to be allocated to any non-CSR (Callee-Saved-Register). The second part will live across calls and will only be allocated to CSR.

The benefit of doing the split is we may get a better chance to do shrinkwrap. Another benefit is param passing copy may be sinked from entry to a colder branch (The fact that copy from hardreg cannot be sinked by machine sinking pass makes this patch more meaningful).

We get 2% performance improvement for an internal protobuf benchmark (https://github.com/google/protobuf) on SandyBridge. I am getting more performance number using spec2000.

[qcolombet]

Hi Wei,

This goes against the paradigm used in LLVM, which is aggressive coalescing then split on demand.
If we start having pre-splitting heuristics on top of the existing heuristics I am afraid we are making our future life worse.

Instead I would rather improve the splitting heuristics. For instance, I would encourage to pursue the approach taken in https://reviews.llvm.org/D27366.

Cheers,
-Quentin

[wmi]

Ah, raising CSR cost to be high enough and using existing splitting is indeed a simpler approach. I didn't think of the idea even after you hinted this in PR. I just tried https://reviews.llvm.org/D27366 and it can cover the simple testcases I have. I can help to evaluate the performance on x86 and see how the overall performance looks. Thanks!

[wmi]

Hi Nemanja,

I tried your testcase with my experimental patch (got from here: http://lists.llvm.org/pipermail/llvm-dev/2017-February/109977.html) and saw that the testcase was not shrinkwrap optimized (cmd I used: clang -O2 -target powerpc64le-grtev4-linux-gnu -S 1.c).

Existing reg splitting for live range across function calls took effect. After splitting, the sub vreg across call got CSR register assigned, and the other sub vreg got a non-CSR register. These all work as we expect. However, during tryHintRecoloring, the two sub vregs are coalesced again.

I add a simple logic in tryHIntRecoloring: If we are going to switch from a non-CSR reg to a CSR reg, only when the recoloring cost difference is larger than CSRCost, we will do such recoloring. In other words, to justify the planning recoloring, the benefit must be at least larger than the potential negative impact on shrinkwrapping.

With the change, the testcase is shrinkwrap optimized. I attach the changed experimental patch.

csrsplit.v2.txt4 KBDownload

Thanks,
Wei.

[wmi]

Sorry, wrong reply. Drop the patch and try to push https://reviews.llvm.org/D27366

include/llvm/CodeGen/Passes.h

/// MachineDominanaceFrontier - This pass is a machine dominators analysis pass.
   extern char &RegisterCoalescerID;
 
   /// MachineScheduler - This pass schedules machine instructions.
   extern char &MachineSchedulerID;
 
   /// PostMachineScheduler - This pass schedules machine instructions postRA.
   extern char &PostMachineSchedulerID;
 
+  /// PreRASplit pass. Split physical register passing params before register
+  /// allocation.
+  extern char &PreRASplitID;
+
   /// SpillPlacement analysis. Suggest optimal placement of spill code between
   /// basic blocks.
   extern char &SpillPlacementID;
 
   /// ShrinkWrap pass. Look for the best place to insert save and restore
   // instruction and update the MachineFunctionInfo with that information.
   extern char &ShrinkWrapID;
 

include/llvm/InitializePasses.h

 void initializePostDomOnlyViewerPass(PassRegistry&);
 void initializePostDomPrinterPass(PassRegistry&);
 void initializePostDomViewerPass(PassRegistry&);
 void initializePostDominatorTreeWrapperPassPass(PassRegistry&);
 void initializePostMachineSchedulerPass(PassRegistry&);
 void initializePostOrderFunctionAttrsLegacyPassPass(PassRegistry&);
 void initializePostRAHazardRecognizerPass(PassRegistry&);
 void initializePostRASchedulerPass(PassRegistry&);
+void initializePreRASplitPass(PassRegistry &);
 void initializePreISelIntrinsicLoweringLegacyPassPass(PassRegistry&);
 void initializePrintBasicBlockPassPass(PassRegistry&);
 void initializePrintFunctionPassWrapperPass(PassRegistry&);
 void initializePrintModulePassWrapperPass(PassRegistry&);
 void initializeProcessImplicitDefsPass(PassRegistry&);
 void initializeProfileSummaryInfoWrapperPassPass(PassRegistry &);
 void initializePromoteLegacyPassPass(PassRegistry &);
 void initializePruneEHPass(PassRegistry&);

lib/CodeGen/CMakeLists.txt

add_llvm_library(LLVMCodeGen
   MIRPrintingPass.cpp
   OptimizePHIs.cpp
   ParallelCG.cpp
   PeepholeOptimizer.cpp
   PHIElimination.cpp
   PHIEliminationUtils.cpp
   PostRAHazardRecognizer.cpp
   PostRASchedulerList.cpp
+  PreRASplit.cpp
   PreISelIntrinsicLowering.cpp
   ProcessImplicitDefs.cpp
   PrologEpilogInserter.cpp
   PseudoSourceValue.cpp
   RegAllocBase.cpp
   RegAllocBasic.cpp
   RegAllocFast.cpp
   RegAllocGreedy.cpp

lib/CodeGen/CodeGen.cpp

void llvm::initializeCodeGen(PassRegistry &Registry) {
   initializePatchableFunctionPass(Registry);
   initializeOptimizePHIsPass(Registry);
   initializePEIPass(Registry);
   initializePHIEliminationPass(Registry);
   initializePeepholeOptimizerPass(Registry);
   initializePostMachineSchedulerPass(Registry);
   initializePostRAHazardRecognizerPass(Registry);
   initializePostRASchedulerPass(Registry);
+  initializePreRASplitPass(Registry);
   initializePreISelIntrinsicLoweringLegacyPassPass(Registry);
   initializeProcessImplicitDefsPass(Registry);
   initializeRAGreedyPass(Registry);
   initializeRegisterCoalescerPass(Registry);
   initializeRenameIndependentSubregsPass(Registry);
   initializeShrinkWrapPass(Registry);
   initializeSlotIndexesPass(Registry);
   initializeStackColoringPass(Registry);

lib/CodeGen/PreRASplit.cpp

+//===- PreRASplit.cpp - Split For Params Before Register Allocation -------==//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This pass tries to split the live ranges of params which are passed via
+// hard registers and live across calls inside the function. The live range
+// of such param could be split into two parts: The first part contains the
+// copy from param passing register and will never live across call, so it
+// gets the freedom to be allocated to any non-CSR (CSR: Callee-Saved-Register)
+// The second part will live across calls and will only be allocated to CSR.
+// The split is before register allocation so we name it as PreRASplit.
+//
+// The benefit of doing the split is if only the split point is colder than
+// function entry, we get a better chance to do shrink wrapping or move the
+// param passing copy from entry to the split point.
+//
+// Here is a simple example:
+// Without PreRASplit, t1 will be allocated to CSR since it lives across
+// goo. As a result, CSR is defined in entry block and no shrink wrapping
+// is possible.
+//
+//   void foo () {
+//     t1 = PARAM_PASSING_REG1;
+//     if (__builtin_expect(cond, 0)) {
+//       goo();
+//       use t1;
+//     }
+//     use t1;
+//     hoo();
+//   }
+//
+// With PreRASplit, t1 is split into t1_a and t1_b. t1_b will be allocated
+// to CSR. t1_a can be allocated to the same register as PARAM_PASSING_REG1.
+// As a result, we only have the copy from PARAM_PASSING_REG1 to t1_b inside
+// the cold branch and shrink wrapping is enabled.
+//
+//   void foo () {
+//     t1_a = PARAM_PASSING_REG1;
+//     if (__builtin_expect(cond, 0)) {
+//       t1_b = t1_a;
+//       goo();
+//       use t1_b;
+//     }
+//     use t1_a;
+//     hoo();
+//   }
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/ADT/SmallSet.h"
+#include "llvm/ADT/Statistic.h"
+#include "llvm/CodeGen/LiveIntervalAnalysis.h"
+#include "llvm/CodeGen/LiveRangeEdit.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/Passes.h"
+#include "llvm/Pass.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Target/TargetInstrInfo.h"
+#include <algorithm>
+using namespace llvm;
+
+#define DEBUG_TYPE "regalloc"
+
+STATISTIC(numPreSplits, "Number of intervals splitted during PreRASplit");
+
+static cl::opt<bool> VerifyPreRASplit(
+    "verify-pre-ra-split",
+    cl::desc("Verify machine instrs before and after PreRASplit"),
+    cl::init(false), cl::Hidden);
+
+namespace {
+class PreRASplit : public MachineFunctionPass {
+  MachineFunction *MF;
+  MachineRegisterInfo *MRI;
+  const TargetMachine *TM;
+  const TargetRegisterInfo *TRI;
+  const TargetInstrInfo *TII;
+  LiveIntervals *LIS;
+  const MachineLoopInfo *Loops;
+  MachineDominatorTree *MDT;
+  // BBs reachable from interesting callsites.
+  SmallPtrSet<MachineBasicBlock *, 20> Reachable;
+  // BBs containing all the interesting callsites and interesting uses.
+  SmallPtrSet<MachineBasicBlock *, 20> InterestingBBs;
+  // Candidate copies with target register to be split.
+  SmallVector<MachineInstr *, 8> CandCopies;
+
+  bool findCandidateCopies();
+  bool findInterestingCalls();
+  void findInterestingUses();
+  MachineBasicBlock *findSplitBB();
+  void implementSplit(MachineBasicBlock *SplitBB);
+  void updateRegUse(unsigned Reg, LiveInterval &LI);
+  void SplitParams();
+
+public:
+  static char ID; ///< Class identification, replacement for typeinfo
+  PreRASplit() : MachineFunctionPass(ID) {
+    initializePreRASplitPass(*PassRegistry::getPassRegistry());
+  }
+
+  void getAnalysisUsage(AnalysisUsage &AU) const override;
+
+  void releaseMemory() override;
+
+  /// This is the pass entry point.
+  bool runOnMachineFunction(MachineFunction &) override;
+};
+} // end anonymous namespace
+
+char PreRASplit::ID = 0;
+char &llvm::PreRASplitID = PreRASplit::ID;
+
+INITIALIZE_PASS_BEGIN(PreRASplit, "pre-ra-splitting", "Pre RegAlloc Splitting",
+                      false, false)
+INITIALIZE_PASS_DEPENDENCY(LiveIntervals)
+INITIALIZE_PASS_DEPENDENCY(SlotIndexes)
+INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
+INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
+INITIALIZE_PASS_END(PreRASplit, "pre-ra-splitting", "Pre RegAlloc Splitting",
+                    false, false)
+
+void PreRASplit::getAnalysisUsage(AnalysisUsage &AU) const {
+  AU.setPreservesCFG();
+  AU.addRequired<LiveIntervals>();
+  AU.addPreserved<LiveIntervals>();
+  AU.addRequired<SlotIndexes>();
+  AU.addPreserved<SlotIndexes>();
+  AU.addRequired<MachineLoopInfo>();
+  AU.addPreserved<MachineLoopInfo>();
+  AU.addRequired<MachineDominatorTree>();
+  AU.addPreserved<MachineDominatorTree>();
+  MachineFunctionPass::getAnalysisUsage(AU);
+}
+
+void PreRASplit::releaseMemory() {
+  Reachable.clear();
+  InterestingBBs.clear();
+  CandCopies.clear();
+}
+
+/// Find candidate copies whose target registers will be split.
+bool PreRASplit::findCandidateCopies() {
+  MachineBasicBlock &Entry = *MF->begin();
+  for (auto &MI : Entry) {
+    if (MI.isCopy() &&
+        TargetRegisterInfo::isVirtualRegister(MI.getOperand(0).getReg()) &&
+        TargetRegisterInfo::isPhysicalRegister(MI.getOperand(1).getReg())) {
+      CandCopies.push_back(&MI);
+      DEBUG(dbgs() << "Candidate copy instruction: " << MI);
+    }
+  }
+  return !CandCopies.empty();
+}
+
+/// Given a set of BBs in \p WorkList, return all the BBs reachable from the
+/// seed in \p ReachableSet.
+static void findReachable(SmallVectorImpl<MachineBasicBlock *> &WorkList,
+                          SmallPtrSet<MachineBasicBlock *, 20> &ReachableSet) {
+  while (!WorkList.empty()) {
+    MachineBasicBlock *MBB = WorkList.pop_back_val();
+    ReachableSet.insert(MBB);
+    std::copy_if(
+        MBB->succ_begin(), MBB->succ_end(), std::back_inserter(WorkList),
+        [&](MachineBasicBlock *Succ) { return !ReachableSet.count(Succ); });
+  }
+}
+
+/// Collect interesting callsites where there is candidate register living
+/// through and return true if at least one such callsite is found. Also find
+/// all the BBs reachable from interesting callsites.
+bool PreRASplit::findInterestingCalls() {
+  SmallVector<MachineBasicBlock *, 20> WorkList;
+  for (auto &MBB : *MF) {
+    for (auto &MI : MBB) {
+      if (MI.isCall()) {
+        SlotIndex SI = LIS->getInstructionIndex(MI).getRegSlot();
+        for (auto Copy : CandCopies) {
+          LiveInterval &LI = LIS->getInterval(Copy->getOperand(0).getReg());
+          if (!LI.Query(SI).valueIn())
+            continue;
+          WorkList.push_back(MI.getParent());
+          InterestingBBs.insert(MI.getParent());
+        }
+      }
+    }
+  }
+
+  findReachable(WorkList, Reachable);
+  return !InterestingBBs.empty();
+}
+
+/// Find all the register uses of split candidate which are reachable from
+/// interesting callsites.
+void PreRASplit::findInterestingUses() {
+  for (auto Copy : CandCopies)
+    for (auto &Inst : MRI->reg_nodbg_instructions(Copy->getOperand(0).getReg()))
+      if (Reachable.count(Inst.getParent()))
+        InterestingBBs.insert(Inst.getParent());
+}
+
+/// Find a common dominator for interesting callsites and interesting uses
+/// as the BB to split. The dominator should also be outside of any loop.
+MachineBasicBlock *PreRASplit::findSplitBB() {
+  MachineBasicBlock *Dom = *InterestingBBs.begin();
+  for (auto MBB : InterestingBBs)
+    if (MBB != Dom)
+      Dom = MDT->findNearestCommonDominator(MBB, Dom);
+
+  // The split point should be outside of any loop, otherwise the live
+  // range of the split candidate will still be live through out the loop.
+  while (Loops->getLoopDepth(Dom) > 0)
+    Dom = (*MDT)[Dom]->getIDom()->getBlock();
+
+  // Dom is the func entry. Nothing to do.
+  if (Dom == &*MF->begin()) {
+    DEBUG(dbgs() << "Split location is func entry. Nothing to do.\n");
+    return nullptr;
+  }
+
+  SmallPtrSet<MachineBasicBlock *, 20> DomReachable;
+  SmallVector<MachineBasicBlock *, 20> WorkList;
+  WorkList.append(Dom->succ_begin(), Dom->succ_end());
+  findReachable(WorkList, DomReachable);
+  // Exit if Dom is inside of an irregular loop.
+  if (DomReachable.count(Dom)) {
+    DEBUG(dbgs() << "Split location is in an irregular loop\n");
+    return nullptr;
+  }
+  DomReachable.insert(Dom);
+
+  // If we have a use reachable by Dom but not dominated by Dom, we cannot
+  // use pruneValue/extendToIndices to do a simple update after the split
+  // but need to recalculate the live range from scratch. Simply punt for
+  // such case since it is not common.
+  // FIXME: If there is important cases missed here, consider to walk up
+  // the dominator tree and find dom node dominating all the reachable uses,
+  // or change the live interval update to be more general.
+  for (auto Copy : CandCopies) {
+    unsigned Dst = Copy->getOperand(0).getReg();
+    if (!LIS->getInterval(Dst).Query(LIS->getMBBStartIdx(Dom)).valueIn())
+      continue;
+    for (auto &MO : MRI->reg_nodbg_operands(Dst)) {
+      if (MO.isDef())
+        continue;
+      MachineInstr *Inst = MO.getParent();
+      // Punt if a use is reachable from Dom but not dominated by Dom.
+      if (DomReachable.count(Inst->getParent()) &&
+          !MDT->dominates(Dom, Inst->getParent())) {
+        DEBUG(dbgs() << "Use reachable but not dominated by SplitBB\n");
+        return nullptr;
+      }
+    }
+  }
+
+  return Dom;
+}
+
+/// Replace the references of \p Reg to LI.reg according to live range of \p LI.
+void PreRASplit::updateRegUse(unsigned Reg, LiveInterval &LI) {
+  SmallPtrSet<MachineInstr *, 8> Visited;
+  for (MachineRegisterInfo::reg_nodbg_iterator I = MRI->reg_nodbg_begin(Reg),
+                                               E = MRI->reg_nodbg_end();
+       I != E;) {
+    MachineOperand &MO = *(I++);
+    MachineInstr *MI = MO.getParent();
+
+    const SlotIndex Idx = LIS->getInstructionIndex(*MI);
+    LiveQueryResult LRQ = LI.Query(Idx);
+    if (MO.isUse()) {
+      if (LRQ.valueIn())
+        MO.substVirtReg(LI.reg, 0, *TRI);
+    } else {
+      if (LRQ.valueDefined())
+        MO.substVirtReg(LI.reg, 0, *TRI);
+    }
+  }
+}
+
+/// Insert the split instruction, update live interval and update reg
+/// references.
+void PreRASplit::implementSplit(MachineBasicBlock *SplitBB) {
+  SmallVector<SlotIndex, 8> EndPoints;
+  SmallVector<unsigned, 4> NewVRegs;
+  LiveRangeEdit Edit(nullptr, NewVRegs, *MF, *LIS, nullptr);
+
+  DEBUG(dbgs() << "PreRASplit done at BB" << SplitBB->getNumber() << ":\n");
+
+  // Set the beginning of SplitBB to be the split location.
+  MachineBasicBlock::iterator InsertIt = SplitBB->getFirstNonDebugInstr();
+  SlotIndex InsertSlot = (InsertIt == SplitBB->end())
+                             ? LIS->getMBBEndIdx(SplitBB)
+                             : LIS->getInstructionIndex(*InsertIt).getRegSlot();
+  for (auto Copy : CandCopies) {
+    unsigned Dst = Copy->getOperand(0).getReg();
+    LiveInterval &LI = LIS->getInterval(Dst);
+    if (!LI.Query(InsertSlot).valueIn())
+      continue;
+
+    numPreSplits++;
+
+    LiveInterval &NewLI = Edit.createEmptyIntervalFrom(Dst);
+    // Insert split copy.
+    MachineInstrBuilder MIB = BuildMI(*SplitBB, InsertIt, Copy->getDebugLoc(),
+                                      TII->get(TargetOpcode::COPY), NewLI.reg);
+    MIB.addReg(Dst);
+    SlotIndex NewIndex = LIS->InsertMachineInstrInMaps(*MIB);
+
+    DEBUG(dbgs() << "Split copy inserted: " << *MIB);
+    DEBUG(dbgs() << "Old LI before split: " << LI << "\n");
+
+    // Update segments killed by the split copy. Note there should not be use
+    // of LI.reg reachable by SplitBB but not dominated by SplitBB. Otherwise
+    // EndPoints will not be jointly dominated by the split copy.
+    NewLI.createDeadDef(NewIndex.getRegSlot(), LIS->getVNInfoAllocator());
+    LIS->pruneValue(LI, NewIndex.getRegSlot(), &EndPoints);
+    LIS->extendToIndices(NewLI, EndPoints);
+    EndPoints.clear();
+
+    // For segments with def dominated by split copy, move the segment to NewLI.
+    SmallVector<LiveRange::Segment, 8> ToRemove;
+    for (LiveRange::const_iterator I = LI.begin(), E = LI.end(); I != E;) {
+      LiveRange::Segment S = *(I++);
+      SlotIndex Def = S.valno->def;
+      MachineBasicBlock *DefBB = LIS->getMBBFromIndex(Def);
+      if (SplitBB == DefBB && S.valno->isPHIDef())
+        continue;
+      if (MDT->dominates(SplitBB, DefBB))
+        ToRemove.push_back(S);
+    }
+    for (auto &S : ToRemove) {
+      NewLI.addSegment(S);
+      LI.removeSegment(S);
+    }
+    LI.RenumberValues();
+    NewLI.RenumberValues();
+    DEBUG(dbgs() << "Old LI after split: " << LI << "\n");
+    DEBUG(dbgs() << "New LI: " << NewLI << "\n\n");
+
+    // Update reg references according to NewLI.
+    updateRegUse(Dst, NewLI);
+  }
+}
+
+/// Choose a BB and do the split at its beginning.
+/// The target registers of copies from hard register inside entry BB are
+/// the candidates to be split. We will collect all the callsites with
+/// split candiates living through, get all the candidate uses reachable
+/// from those callsites, and find a common dominator for the interesting
+/// callsites and reachable candidate uses. The common dominator is the
+/// the location to split.
+void PreRASplit::SplitParams() {
+  if (!findCandidateCopies()) {
+    DEBUG(dbgs() << "No candidate copies to split\n");
+    return;
+  }
+  if (!findInterestingCalls()) {
+    DEBUG(dbgs() << "No interesting calls found\n");
+    return;
+  }
+  findInterestingUses();
+
+  MachineBasicBlock *SplitBB;
+  if (!(SplitBB = findSplitBB()))
+    return;
+  implementSplit(SplitBB);
+}
+
+bool PreRASplit::runOnMachineFunction(MachineFunction &fn) {
+  MF = &fn;
+  MRI = &fn.getRegInfo();
+  TM = &fn.getTarget();
+  const TargetSubtargetInfo &STI = fn.getSubtarget();
+  TRI = STI.getRegisterInfo();
+  TII = STI.getInstrInfo();
+  LIS = &getAnalysis<LiveIntervals>();
+  Loops = &getAnalysis<MachineLoopInfo>();
+  MDT = &getAnalysis<MachineDominatorTree>();
+  DEBUG(dbgs() << "********** PRE RA REGISTER SPLITTING  **********\n"
+               << "********** Function: " << MF->getName() << '\n');
+
+  if (VerifyPreRASplit)
+    MF->verify(this, "Before PreRASplit");
+
+  SplitParams();
+
+  if (VerifyPreRASplit)
+    MF->verify(this, "After PreRASplit");
+  DEBUG(dbgs() << "********** PRE RA REGISTER SPLITTING Done **********\n\n");
+  return true;
+}

lib/CodeGen/RegAllocBasic.cpp

 
 char RABasic::ID = 0;
 
 } // end anonymous namespace
 
 RABasic::RABasic(): MachineFunctionPass(ID) {
   initializeLiveDebugVariablesPass(*PassRegistry::getPassRegistry());
   initializeLiveIntervalsPass(*PassRegistry::getPassRegistry());
+  initializePreRASplitPass(*PassRegistry::getPassRegistry());
   initializeSlotIndexesPass(*PassRegistry::getPassRegistry());
   initializeRegisterCoalescerPass(*PassRegistry::getPassRegistry());
   initializeMachineSchedulerPass(*PassRegistry::getPassRegistry());
   initializeLiveStacksPass(*PassRegistry::getPassRegistry());
   initializeMachineDominatorTreePass(*PassRegistry::getPassRegistry());
   initializeMachineLoopInfoPass(*PassRegistry::getPassRegistry());
   initializeVirtRegMapPass(*PassRegistry::getPassRegistry());
   initializeLiveRegMatrixPass(*PassRegistry::getPassRegistry());

lib/CodeGen/TargetPassConfig.cpp

 static cl::opt<bool> DisableConstantHoisting("disable-constant-hoisting",
     cl::Hidden, cl::desc("Disable ConstantHoisting"));
 static cl::opt<bool> DisableCGP("disable-cgp", cl::Hidden,
     cl::desc("Disable Codegen Prepare"));
 static cl::opt<bool> DisableCopyProp("disable-copyprop", cl::Hidden,
     cl::desc("Disable Copy Propagation pass"));
 static cl::opt<bool> DisablePartialLibcallInlining("disable-partial-libcall-inlining",
     cl::Hidden, cl::desc("Disable Partial Libcall Inlining"));
+static cl::opt<bool> DisablePreRASplit("disable-pre-ra-split", cl::Hidden,
+    cl::desc("Disable Pre RA Split pass"));
 static cl::opt<bool> EnableImplicitNullChecks(
     "enable-implicit-null-checks",
     cl::desc("Fold null checks into faulting memory operations"),
     cl::init(false));
 static cl::opt<bool> PrintLSR("print-lsr-output", cl::Hidden,
     cl::desc("Print LLVM IR produced by the loop-reduce pass"));
 static cl::opt<bool> PrintISelInput("print-isel-input", cl::Hidden,
     cl::desc("Print LLVM IR input to isel pass"));
if (StandardID == &TargetPassConfig::PostRAMachineLICMID)
     return applyDisable(TargetID, DisablePostRAMachineLICM);
 
   if (StandardID == &MachineSinkingID)
     return applyDisable(TargetID, DisableMachineSink);
 
   if (StandardID == &MachineCopyPropagationID)
     return applyDisable(TargetID, DisableCopyProp);
 
+  if (StandardID == &PreRASplitID)
+    return applyDisable(TargetID, DisablePreRASplit);
+
   return TargetID;
 }
 
 //===---------------------------------------------------------------------===//
 /// TargetPassConfig
 //===---------------------------------------------------------------------===//
 
 INITIALIZE_PASS(TargetPassConfig, "targetpassconfig",
void TargetPassConfig::addOptimizedRegAlloc(FunctionPass *RegAllocPass) {
   addPass(&PHIEliminationID, false);
 
   // Eventually, we want to run LiveIntervals before PHI elimination.
   if (EarlyLiveIntervals)
     addPass(&LiveIntervalsID, false);
 
   addPass(&TwoAddressInstructionPassID, false);
   addPass(&RegisterCoalescerID);
+  addPass(&PreRASplitID);
 
   // The machine scheduler may accidentally create disconnected components
   // when moving subregister definitions around, avoid this by splitting them to
   // separate vregs before. Splitting can also improve reg. allocation quality.
   addPass(&RenameIndependentSubregsID);
 
   // PreRA instruction scheduling.
   addPass(&MachineSchedulerID);

test/CodeGen/Thumb2/cbnz.ll

-; RUN: llc -mtriple thumbv7-unknown-linux -o - %s | FileCheck %s
+; RUN: llc -mtriple thumbv7-unknown-linux -disable-pre-ra-split -o - %s | FileCheck %s
 
 declare void @x()
 declare void @y()
 
 define void @f(i32 %x, i32 %y) {
   ; CHECK-LABEL: f:
   ; CHECK: cbnz
   %p = icmp eq i32 %x, 0

test/CodeGen/X86/fold-call-oper.ll

-; RUN: llc < %s -mtriple=x86_64-apple-darwin | FileCheck %s
+; RUN: llc < %s -mtriple=x86_64-apple-darwin -disable-pre-ra-split | FileCheck %s
 ;
 ; PR18396: Assertion: MO->isDead "Cannot fold physreg def".
 ; InlineSpiller::foldMemoryOperand needs to handle undef call operands.
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 
 @a = external global i32**, align 8
 @b = external global i32, align 4

test/CodeGen/X86/half.ll

 ; CHECK-F16C-NEXT: retq
   %a = load half, half* %p, align 2
   %r = fptoui half %a to i64
   ret i64 %r
 }
 
 define void @test_uitofp_i64(i64 %a, half* %p) #0 {
 ; CHECK-LABEL: test_uitofp_i64:
-; CHECK-LIBCALL-NEXT: pushq [[ADDR:%[a-z0-9]+]]
-; CHECK-LIBCALL-NEXT: movq %rsi, [[ADDR]]
 ; CHECK-NEXT: testq %rdi, %rdi
 ; CHECK-NEXT: js [[LABEL1:.LBB[0-9_]+]]
 
 ; simple conversion to float if non-negative
 ; CHECK-LIBCALL-NEXT: cvtsi2ssq %rdi, [[REG1:%[a-z0-9]+]]
 ; CHECK-F16C-NEXT: vcvtsi2ssq %rdi, [[REG1:%[a-z0-9]+]], [[REG1]]
 ; CHECK-NEXT: jmp [[LABEL2:.LBB[0-9_]+]]
 
 ; convert using shift+or if negative
 ; CHECK-NEXT: [[LABEL1]]:
 ; CHECK-NEXT: movq %rdi, %rax
 ; CHECK-NEXT: shrq %rax
 ; CHECK-NEXT: andl $1, %edi
 ; CHECK-NEXT: orq %rax, [[REG2:%[a-z0-9]+]]
 ; CHECK-LIBCALL-NEXT: cvtsi2ssq [[REG2]], [[REG3:%[a-z0-9]+]]
 ; CHECK-LIBCALL-NEXT: addss [[REG3]], [[REG1]]
 ; CHECK-F16C-NEXT: vcvtsi2ssq [[REG2]], [[REG3:%[a-z0-9]+]], [[REG3]]
 ; CHECK-F16C-NEXT: vaddss [[REG3]], [[REG3]], [[REG1:[%a-z0-9]+]]
 
 ; convert float to half
 ; CHECK-NEXT: [[LABEL2]]:
+; CHECK-LIBCALL-NEXT: pushq [[ADDR:%[a-z0-9]+]]
+; CHECK-LIBCALL-NEXT: movq %rsi, [[ADDR]]
 ; CHECK-LIBCALL-NEXT: callq __gnu_f2h_ieee
 ; CHECK-LIBCALL-NEXT: movw %ax, ([[ADDR]])
 ; CHECK-LIBCALL-NEXT: popq [[ADDR]]
 ; CHECK-F16C-NEXT: vcvtps2ph $4, [[REG1]], [[REG4:%[a-z0-9]+]]
 ; CHECK-F16C-NEXT: vmovd [[REG4]], %eax
 ; CHECK-F16C-NEXT: movw %ax, (%rsi)
 ; CHECK-NEXT: retq
 

test/CodeGen/X86/pr20020.ll

-; RUN: llc < %s -mtriple=x86_64-apple-macosx -disable-lsr -post-RA-scheduler=1 -break-anti-dependencies=critical  | FileCheck %s
+; RUN: llc < %s -mtriple=x86_64-apple-macosx -disable-lsr -post-RA-scheduler=1 -break-anti-dependencies=critical -disable-pre-ra-split | FileCheck %s
 
 ; In PR20020, the critical anti-dependency breaker algorithm mistakenly
 ; changes the register operands of an 'xorl %eax, %eax' to 'xorl %ecx, %ecx'
 ; and then immediately reloads %rcx with a value based on the wrong %rax
 
 ; CHECK-NOT: xorl %ecx, %ecx
 ; CHECK: leaq 1(%rax), %rcx
 

test/CodeGen/X86/pre-ra-split1.ll

+; RUN: llc -mtriple=x86_64-unknown-linux-gnu -verify-pre-ra-split < %s | FileCheck %s
+; Check PreRASplit can work properly for tests below.
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+@cond = common local_unnamed_addr global i64 0, align 8
+@ret = common local_unnamed_addr global i64 0, align 8
+@p = common local_unnamed_addr global i64* null, align 8
+declare void @foo(i64, i64, i64)
+
+; After PreRASplit, ShrinkWrap is enabled and prologue are moved from entry
+; to BB#1.
+;
+; CHECK-LABEL: test1:
+; CHECK-NEXT: # BB#0:
+; CHECK-NEXT:   cmpq
+; CHECK-NEXT:   je
+; CHECK-NEXT: # BB#1:
+; CHECK-NEXT:   push
+; CHECK-NEXT:   push
+; CHECK-NEXT:   push
+define void @test1(i64 %i, i64 %j, i64 %k) nounwind {
+entry:
+  %t0 = load i64, i64* @cond, align 8
+  %tobool = icmp eq i64 %t0, 0
+  br i1 %tobool, label %if.end, label %if.then
+
+if.then:                                          ; preds = %entry
+  tail call void @foo(i64 %i, i64 %j, i64 %k)
+  %add = add nsw i64 %j, %i
+  %add1 = add nsw i64 %add, %k
+  store i64 %add1, i64* @ret, align 8
+  br label %if.end
+
+if.end:                                           ; preds = %entry, %if.then
+  %t1 = load i64*, i64** @p, align 8
+  store volatile i64 3, i64* %t1, align 8
+  ret void
+}
+
+; After PreRASplit, even if ShrinkWrap is not enabled because stack
+; alloc space is used. param passing moves still can be moved from
+; prologue to BB#1.
+;
+; CHECK-LABEL: test2:
+; CHECK-NEXT: # BB#0:
+; CHECK-NEXT:   pushq %rbp
+; CHECK-NEXT:   movq  %rsp, %rbp
+; CHECK-NEXT:   pushq %r15
+; CHECK-NEXT:   pushq %r14
+; CHECK-NEXT:   pushq %rbx
+; CHECK-NEXT:   pushq %rax
+; CHECK-NEXT:   cmpq
+; CHECK-NEXT:   je
+; CHECK-NEXT: # BB#1:
+; CHECK-NEXT:   movq  %rdx,
+; CHECK-NEXT:   movq  %rsi,
+; CHECK-NEXT:   movq  %rdi,
+; CHECK-NEXT:   callq foo
+;
+define void @test2(i64 %i, i64 %j, i64 %k) nounwind {
+entry:
+  %t0 = load i64, i64* @cond, align 8
+  %tobool = icmp eq i64 %t0, 0
+  br i1 %tobool, label %if.end, label %if.then
+
+if.then:                                          ; preds = %entry
+  tail call void @foo(i64 %i, i64 %j, i64 %k)
+  %add = add nsw i64 %j, %i
+  %add1 = add nsw i64 %add, %k
+  store i64 %add1, i64* @ret, align 8
+  br label %if.end
+
+if.end:                                           ; preds = %entry, %if.then
+  %t1 = alloca [3 x i8], align 16
+  store [3 x i8]* %t1, [3 x i8]** bitcast (i64** @p to [3 x i8]**), align 8
+  ret void
+}

test/CodeGen/X86/pre-ra-split2.ll

+; RUN: llc -mtriple=x86_64-unknown-linux-gnu -verify-pre-ra-split < %s
+; Check PreRASplit will not do split in an irregular loop, which will lead to error exit
+; when verify-pre-ra-split is enabled.
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+%class.C = type { i8 }
+%class.B = type { %class.A*, i32, %class.A* }
+%class.A = type { %class.A*, i32 }
+@a = local_unnamed_addr global i32 0, align 4
+declare void @_ZN1BIiE5m_fn2Ev(%class.B*)
+declare void @_ZN1C5m_fn5Ei(%class.C*, i32)
+
+define void @_ZN1C5m_fn4Ev(%class.C* %this) align 2 {
+entry:
+  %e = alloca %class.B, align 8
+  %t0 = bitcast %class.B* %e to i8*
+  %fCurElem.i = getelementptr inbounds %class.B, %class.B* %e, i64 0, i32 0
+  store %class.A* null, %class.A** %fCurElem.i, align 8
+  %fCurHash.i = getelementptr inbounds %class.B, %class.B* %e, i64 0, i32 1
+  store i32 0, i32* %fCurHash.i, align 8
+  %fToEnum.i = getelementptr inbounds %class.B, %class.B* %e, i64 0, i32 2
+  store %class.A* null, %class.A** %fToEnum.i, align 8
+  %t1 = load i32, i32* inttoptr (i64 8 to i32*), align 8
+  %cmp.i.i = icmp eq i32 %t1, 0
+  br i1 %cmp.i.i, label %while.cond, label %while.cond.thread
+
+while.cond.thread:                                ; preds = %entry
+  store %class.A* null, %class.A** %fCurElem.i, align 8
+  br label %while.body
+
+while.cond:                                       ; preds = %entry, %while.body
+  %.pr = phi %class.A* [ %.pr.pre, %while.body ], [ null, %entry ]
+  %tobool.i = icmp eq %class.A* %.pr, null
+  br i1 %tobool.i, label %while.body, label %while.end
+
+while.body:                                       ; preds = %while.cond.thread, %while.cond
+  call void @_ZN1BIiE5m_fn2Ev(%class.B* nonnull %e)
+  %t2 = load i32, i32* @a, align 4
+  call void @_ZN1C5m_fn5Ei(%class.C* %this, i32 %t2)
+  %.pr.pre = load %class.A*, %class.A** %fCurElem.i, align 8
+  br label %while.cond
+
+while.end:                                        ; preds = %while.cond
+  ret void
+}