[Dominators][CodeGen] Add MachinePostDominatorTree verification

[kuhar]

Summary

This patch implements Machine PostDominator Tree verification and ensures that the verification doesn't fail the in-tree tests.

MPDT verification can be enabled using verify-machine-dom-info -- the same flag used by Machine Dominator Tree verification.

Flipping the flag revealed that MachineSink falsely claimed to preserve CFG and MDT/MPDT. This patch fixes that.

[kuhar]

Fix a typo

[hliao]

LGTM

[kuhar]

llvm/lib/CodeGen/MachineDominators.cpp

23

TODO: This should probably be in namespace llvm now.

[uabelho]

llvm/trunk/lib/CodeGen/MachineSink.cpp

124 ↗

(On Diff #222627)

Hi,

In my out-of-tree target I'm seeing strange problems with MachineLoopInfo with this patch and I'm wondering if perhaps we should also remove MachineLoopInfo from the preserved passes above?

Since MachineLoopInfo uses MachineDominatorTree, won't MLI also possibly be invalid if MDT is invalid?

[kuhar]

llvm/trunk/lib/CodeGen/MachineSink.cpp

124 ↗

(On Diff #222627)

Hi Mikael,

Over the last couple of days I found a few passes that modify CFG and do not update dominators while claiming to preserve them, which all should be fixed now.

I'm not familiar with MachineLI, but skimming the code it seems that any pass that introduces new blocks and doesn't add it to MLI invalidates it. This seems to be the case for MachineSink, PHIElimination, and maybe some other passes I missed. I think that in those cases the passes have to be fixes to not say they preserve MLI.

Independently, perhaps it would be worth/possible to implement verifyAnalysis for MLI and see where it currently breaks?

[uabelho]

llvm/trunk/lib/CodeGen/MachineSink.cpp

124 ↗

(On Diff #222627)

I'm not familiar with MachineLI, but skimming the code it seems that any pass that introduces new blocks
and doesn't add it to MLI invalidates it. This seems to be the case for MachineSink, PHIElimination, and
maybe some other passes I missed. I think that in those cases the passes have to be fixes to not say they
preserve MLI.

So you also think MachineSink is buggy here and that it should not say it preserves MachineLoopInfo anymore?

Independently, perhaps it would be worth/possible to implement verifyAnalysis for MLI and see where
it currently breaks?

Sounds like a good idea to me.

[kuhar]

llvm/trunk/lib/CodeGen/MachineSink.cpp

124 ↗

(On Diff #222627)

So you also think MachineSink is buggy here and that it should not say it preserves MachineLoopInfo anymore?

Seems so to me. Too know for sure I would have to see a definition of what it means for MLI to be valid.

llvm/include/llvm/CodeGen/MachinePostDominators.h

public:
   /// Returns the nearest common dominator of the given blocks.
   /// If that tree node is a virtual root, a nullptr will be returned.
   MachineBasicBlock *
   findNearestCommonDominator(ArrayRef<MachineBasicBlock *> Blocks) const;
 
   bool runOnMachineFunction(MachineFunction &MF) override;
   void getAnalysisUsage(AnalysisUsage &AU) const override;
   void releaseMemory() override { PDT.reset(nullptr); }
+  void verifyAnalysis() const override;
   void print(llvm::raw_ostream &OS, const Module *M = nullptr) const override;
 };
 } //end of namespace llvm
 
 #endif

llvm/lib/CodeGen/MachineDominators.cpp

 #include "llvm/ADT/SmallBitVector.h"
 #include "llvm/CodeGen/Passes.h"
 #include "llvm/Support/CommandLine.h"
 
 using namespace llvm;
 
 // Always verify dominfo if expensive checking is enabled.
 #ifdef EXPENSIVE_CHECKS
-static bool VerifyMachineDomInfo = true;
+bool VerifyMachineDomInfo = true;
 #else
-static bool VerifyMachineDomInfo = false;
+bool VerifyMachineDomInfo = false;
 #endif
 static cl::opt<bool, true> VerifyMachineDomInfoX(
     "verify-machine-dom-info", cl::location(VerifyMachineDomInfo), cl::Hidden,
     cl::desc("Verify machine dominator info (time consuming)"));
 
 namespace llvm {
 template class DomTreeNodeBase<MachineBasicBlock>;
 template class DominatorTreeBase<MachineBasicBlock, false>; // DomTreeBase

llvm/lib/CodeGen/MachinePostDominators.cpp

 //===- MachinePostDominators.cpp -Machine Post Dominator Calculation ------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // This file implements simple dominator construction algorithms for finding
 // post dominators on machine functions.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/CodeGen/MachinePostDominators.h"
 
-#include "llvm/ADT/STLExtras.h"
-
 using namespace llvm;
 
 namespace llvm {
 template class DominatorTreeBase<MachineBasicBlock, true>; // PostDomTreeBase
 }
 
+extern bool VerifyMachineDomInfo;
 char MachinePostDominatorTree::ID = 0;
 
 //declare initializeMachinePostDominatorTreePass
 INITIALIZE_PASS(MachinePostDominatorTree, "machinepostdomtree",
                 "MachinePostDominator Tree Construction", true, true)
 
 MachinePostDominatorTree::MachinePostDominatorTree()
     : MachineFunctionPass(ID), PDT(nullptr) {
for (MachineBasicBlock *BB : Blocks.drop_front()) {
     // Stop when the root is reached.
     if (PDT->isVirtualRoot(PDT->getNode(NCD)))
       return nullptr;
   }
 
   return NCD;
 }
 
+void MachinePostDominatorTree::verifyAnalysis() const {
+  if (PDT && (VerifyMachineDomInfo))
+    if (!PDT->verify(PostDomTreeT::VerificationLevel::Basic)) {
+      errs() << "MachinePostDominatorTree verification failed\n";
+
+      abort();
+    }
+}
+
 void MachinePostDominatorTree::print(llvm::raw_ostream &OS,
                                      const Module *M) const {
   PDT->print(OS);
 }

llvm/lib/CodeGen/MachineSink.cpp

public:
 
     MachineSinking() : MachineFunctionPass(ID) {
       initializeMachineSinkingPass(*PassRegistry::getPassRegistry());
     }
 
     bool runOnMachineFunction(MachineFunction &MF) override;
 
     void getAnalysisUsage(AnalysisUsage &AU) const override {
-      AU.setPreservesCFG();
       MachineFunctionPass::getAnalysisUsage(AU);
       AU.addRequired<AAResultsWrapperPass>();
       AU.addRequired<MachineDominatorTree>();
       AU.addRequired<MachinePostDominatorTree>();
       AU.addRequired<MachineLoopInfo>();
       AU.addRequired<MachineBranchProbabilityInfo>();
-      AU.addPreserved<MachineDominatorTree>();
-      AU.addPreserved<MachinePostDominatorTree>();
       AU.addPreserved<MachineLoopInfo>();
       if (UseBlockFreqInfo)
         AU.addRequired<MachineBlockFrequencyInfo>();
     }
 
     void releaseMemory() override {
       CEBCandidates.clear();
     }

llvm/test/CodeGen/AArch64/O3-pipeline.ll

 ; CHECK-NEXT:       Remove dead machine instructions
 ; CHECK-NEXT:       AArch64 Dead register definitions
 ; CHECK-NEXT:       Detect Dead Lanes
 ; CHECK-NEXT:       Process Implicit Definitions
 ; CHECK-NEXT:       Remove unreachable machine basic blocks
 ; CHECK-NEXT:       Live Variable Analysis
 ; CHECK-NEXT:       Eliminate PHI nodes for register allocation
 ; CHECK-NEXT:       Two-Address instruction pass
+; CHECK-NEXT:       MachineDominator Tree Construction
 ; CHECK-NEXT:       Slot index numbering
 ; CHECK-NEXT:       Live Interval Analysis
 ; CHECK-NEXT:       Simple Register Coalescing
 ; CHECK-NEXT:       Rename Disconnected Subregister Components
 ; CHECK-NEXT:       Machine Instruction Scheduler
 ; CHECK-NEXT:       Machine Block Frequency Analysis
 ; CHECK-NEXT:       Debug Variable Analysis
 ; CHECK-NEXT:       Live Stack Slot Analysis