[Dominators][CodeGen] Fix MachineDominatorTree preservation in PHIElimination

[kuhar]

Summary

PHIElimination modifies CFG and marks MachineDominatorTree as preserved. Therefore, it the CFG changes it should also update the MDT, when available. This patch teaches PHIElimination to recalculate MDT when necessary.

This fixes the tailmerging_in_mbp.ll test failure discovered after switching to generic DomTree verification algorithm in MachineDominators in D67976.

[rampitec]

LGTM

[arsenm]

llvm/lib/CodeGen/PHIElimination.cpp

189–190

Isn't this basically the same as making it unpreserved? If you aren't going to update at the points it needs, I think it would be better to just stop reporting it as preserved

[hiraditya]

llvm/lib/CodeGen/PHIElimination.cpp

189–190

+1

[hiraditya]

llvm/lib/CodeGen/PHIElimination.cpp

189

Can we put auto *MDT = getAnalysisIfAvailable<MachineDominatorTree>(); when Changed is true?

[kuhar]

Thanks for the comments, @arsenm and @hiraditya.

I tried not declaring MDT as a preserved analysis at all, but I got issues with OrcJit unittests:

[2019-09-29 15:31:37.806980254] 0x54de520     Made Modification 'Simple Register Coalescing' on Function 'bar'...
[2019-09-29 15:31:37.807045279] 0x54de520      Freeing Pass 'Simple Register Coalescing' on Function 'bar'...
[2019-09-29 15:31:37.807075980] 0x54de520      Freeing Pass 'MachineDominator Tree Construction' on Function 'bar'...
[2019-09-29 15:31:37.807107079] 0x54de520     Executing Pass 'Rename Disconnected Subregister Components' on Function 'bar'...
[2019-09-29 15:31:37.807177117] 0x54de520      Freeing Pass 'Rename Disconnected Subregister Components' on Function 'bar'...
[2019-09-29 15:31:37.807204793] 0x54de520     Executing Pass 'Machine Instruction Scheduler' on Function 'bar'...
OrcJITTests: /home/kuba/llvm/llvm-project/llvm/include/llvm/PassAnalysisSupport.h:235: AnalysisType &llvm::Pass::getAnalysisID(llvm::AnalysisID) const [AnalysisType = llvm::MachineDominatorTree]: Assertion `ResultPass && "getAnalysis*() called on an analysis that was not " "'required' by pass!"' failed.

Not sure why this is the case, as I marked MDT as a required analysis for MachineScheduler. Do you have some tips here? I'm a newbie when it comes to MIR and Machine passes.

When I preserve the analysis in PHIElimination everything works.

[arsenm]

Is there some reason it’s difficult to update the tree where needed here? I would try to just handle that instead of figuring out how to unpreserve it

[kuhar]

In D68154#1687315, @arsenm wrote:

Is there some reason it’s difficult to update the tree where needed here? I would try to just handle that instead of figuring out how to unpreserve it

Will try that, we have a generic updater that we should be able to use.

[kuhar]

In D68154#1687316, @kuhar wrote:

In D68154#1687315, @arsenm wrote:

Is there some reason it’s difficult to update the tree where needed here? I would try to just handle that instead of figuring out how to unpreserve it

Will try that, we have a generic updater that we should be able to use.

The issue is that right now MachineDominatorTree has some ad-hoc updater that does (lazy) critical edge splitting before almost any domtree operation. Block splitting uses the old manual API for updating DomTree, and cannot easily be mixed with the new incremental updater.

I think a proper solution here would be to first preserve MDT and MPDT where needed, using the simple recalculation where necessary, then making sure it verifies across machine passes, and later switching to the incremental updater across machine passes instead of the lazy critical edge splitting.

[kuhar]

I'd like to commit this simple fix as-is, make sure no buildbots complain, and then introduce a proper incremental updating in a later revision.

[kuhar]

@arsenm @hiraditya
Are you fine with committing the patch as-is and exploring using the incremental updater later?

[arsenm]

LGTM

[hiraditya]

LGTM, thanks for committing.

llvm/lib/CodeGen/MachineScheduler.cpp

 
 char MachineScheduler::ID = 0;
 
 char &llvm::MachineSchedulerID = MachineScheduler::ID;
 
 INITIALIZE_PASS_BEGIN(MachineScheduler, DEBUG_TYPE,
                       "Machine Instruction Scheduler", false, false)
 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
+INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
 INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
 INITIALIZE_PASS_DEPENDENCY(SlotIndexes)
 INITIALIZE_PASS_DEPENDENCY(LiveIntervals)
 INITIALIZE_PASS_END(MachineScheduler, DEBUG_TYPE,
                     "Machine Instruction Scheduler", false, false)
 
 MachineScheduler::MachineScheduler() : MachineSchedulerBase(ID) {
   initializeMachineSchedulerPass(*PassRegistry::getPassRegistry());
 }
 
 void MachineScheduler::getAnalysisUsage(AnalysisUsage &AU) const {
   AU.setPreservesCFG();
-  AU.addRequiredID(MachineDominatorsID);
+  AU.addRequired<MachineDominatorTree>();
   AU.addRequired<MachineLoopInfo>();
   AU.addRequired<AAResultsWrapperPass>();
   AU.addRequired<TargetPassConfig>();
   AU.addRequired<SlotIndexes>();
   AU.addPreserved<SlotIndexes>();
   AU.addRequired<LiveIntervals>();
   AU.addPreserved<LiveIntervals>();
   MachineFunctionPass::getAnalysisUsage(AU);
 }
 
 char PostMachineScheduler::ID = 0;
 
 char &llvm::PostMachineSchedulerID = PostMachineScheduler::ID;
 
 INITIALIZE_PASS(PostMachineScheduler, "postmisched",
                 "PostRA Machine Instruction Scheduler", false, false)
 
 PostMachineScheduler::PostMachineScheduler() : MachineSchedulerBase(ID) {
   initializePostMachineSchedulerPass(*PassRegistry::getPassRegistry());
 }
 
 void PostMachineScheduler::getAnalysisUsage(AnalysisUsage &AU) const {
   AU.setPreservesCFG();
-  AU.addRequiredID(MachineDominatorsID);
+  AU.addRequired<MachineDominatorTree>();
   AU.addRequired<MachineLoopInfo>();
   AU.addRequired<TargetPassConfig>();
   MachineFunctionPass::getAnalysisUsage(AU);
 }
 
 MachinePassRegistry<MachineSchedRegistry::ScheduleDAGCtor>
     MachineSchedRegistry::Registry;
 

llvm/lib/CodeGen/PHIElimination.cpp

void PHIElimination::getAnalysisUsage(AnalysisUsage &AU) const {
   AU.addPreserved<MachineLoopInfo>();
   MachineFunctionPass::getAnalysisUsage(AU);
 }
 
 bool PHIElimination::runOnMachineFunction(MachineFunction &MF) {
   MRI = &MF.getRegInfo();
   LV = getAnalysisIfAvailable<LiveVariables>();
   LIS = getAnalysisIfAvailable<LiveIntervals>();
+  auto *MDT = getAnalysisIfAvailable<MachineDominatorTree>();
 
   bool Changed = false;
 
   // This pass takes the function out of SSA form.
   MRI->leaveSSA();
 
   // Split critical edges to help the coalescer.
   if (!DisableEdgeSplitting && (LV || LIS)) {
bool PHIElimination::runOnMachineFunction(MachineFunction &MF) {
 
   // Clean up the lowered PHI instructions.
   for (auto &I : LoweredPHIs) {
     if (LIS)
       LIS->RemoveMachineInstrFromMaps(*I.first);
     MF.DeleteMachineInstr(I.first);
   }
 
+  if (Changed && MDT)
+    MDT->getBase().recalculate(MF);
+
   LoweredPHIs.clear();
   ImpDefs.clear();
   VRegPHIUseCount.clear();
 
   MF.getProperties().set(MachineFunctionProperties::Property::NoPHIs);
 
   return Changed;
 }

llvm/test/CodeGen/AArch64/tailmerging_in_mbp.ll

 ; RUN: llc <%s -mtriple=aarch64-eabi -verify-machine-dom-info | FileCheck %s
-; XFAIL: *
 
 ; CHECK-LABEL: test:
 ; CHECK-LABEL: %cond.false12.i
 ; CHECK:         b.gt 
 ; CHECK-NEXT:  LBB0_8:
 ; CHECK-NEXT:    mov   x8, x9
 ; CHECK-NEXT:  LBB0_9:
 define i64 @test(i64 %n, i64* %a, i64* %b, i64* %c, i64* %d, i64* %e, i64* %f) {