Do not verify MachimeDominatorTree if it is not calculated

[sepavloff]

Summary

If dominator tree is not calculated or is invalidated, set corresponding
pointer in the pass state to nullptr. Such pointer value will indicate
that operations with dominator tree are not allowed. In particular, it
allows to skip verification for such pass state. The dominator thee is
not calculated if the machine dominator pass was skipped, it occures in
the case of entities with linkage available_externally.

The change fixes some test fails observed when expensive checks
are enabled.

[fhahn]

Do you know why the machine dominator pass was skipped for test/CodeGen/Generic/externally_available.ll? Or has it been invalidated?

[sepavloff]

In D29280#661041, @fhahn wrote:

Do you know why the machine dominator pass was skipped for test/CodeGen/Generic/externally_available.ll? Or has it been invalidated?

Not only dominator pass was skipped, all machine code passes were skipped too. According to the documentation (http://llvm.org/docs/LangRef.html#linkage-types):

Globals with “available_externally” linkage are never emitted into the object file

So there is no sense to run machine code generation for them.

[fhahn]

In D29280#661308, @sepavloff wrote:

Not only dominator pass was skipped, all machine code passes were skipped too. According to the documentation (http://llvm.org/docs/LangRef.html#linkage-types):

Globals with “available_externally” linkage are never emitted into the object file

So there is no sense to run machine code generation for them.

Ah thanks that makes sense. The only thing I am still wondering about: if no machine passes are run, MachineDominatorTree::verifyAnalysis or MachineDominatorTree::verifyDomTree shouldn't be called in the first place, no?

lib/CodeGen/MachineDominators.cpp

142

Would this change here in combination with moving the allocation of the dominator tree to runOnMachineFunction be enough to skip the verification in cases runOnMachineFunction is not executed?

The change to use unique_ptr might be a worthwhile refactoring, but it looks like most of the changes in this patch are related to the change to unique_ptr instead of skipping the dominator tree verification. I think it would make it easier for reviewers if the patch would only contain the changes required to skip the dominator tree verification.

[sepavloff]

Globals with “available_externally” linkage are never emitted into the object file

So there is no sense to run machine code generation for them.

Ah thanks that makes sense. The only thing I am still wondering about: if no machine passes are run, MachineDominatorTree::verifyAnalysis or MachineDominatorTree::verifyDomTree shouldn't be called in the first place, no?

The relevant code looks as follows:

bool MachineFunctionPass::runOnFunction(Function &F) {
  // Do not codegen any 'available_externally' functions at all, they have
  // definitions outside the translation unit.
  if (F.hasAvailableExternallyLinkage())
    return false;

So the pass was run but it decided to skip processing of some functions. Pass Manager does not know if the pass actually did not make its job and calls verifyAnalysis for it. The latter obviously crashes. Solution in D27190 tried to extend Pass state so that it keeps a flag, whether or not the pass produced result, but it was decided to use a simpler solution.

Would this change here in combination with moving the allocation of the dominator tree to runOnMachineFunction be enough to skip the verification in cases runOnMachineFunction is not executed?

Dominator tree appears when runOnMachineFunction is run and is invalidated when Pass Manager releases the pass by call to releaseMemory, it looks like correct domtree lifetime.

The change to use unique_ptr might be a worthwhile refactoring, but it looks like most of the changes in this patch are related to the change to unique_ptr instead of skipping the dominator tree verification. I think it would make it easier for reviewers if the patch would only contain the changes required to skip the dominator tree verification.

The simple patch was presented in D28767. In subsequent discussion http://lists.llvm.org/pipermail/llvm-commits/Week-of-Mon-20170123/423110.html it was pointed out that dominator tree should not exist if it does not represent any function. This patch is an attempt to add lifetime management of the dominator tree.

[sepavloff]

Ping.

[sepavloff]

Is there anything I can do to make this patch acceptable?

[• dberlin]

I am fine with this at this point.

include/llvm/CodeGen/MachineDominators.h

 #define LLVM_CODEGEN_MACHINEDOMINATORS_H
 
 #include "llvm/ADT/SmallSet.h"
 #include "llvm/CodeGen/MachineBasicBlock.h"
 #include "llvm/CodeGen/MachineFunction.h"
 #include "llvm/CodeGen/MachineFunctionPass.h"
 #include "llvm/Support/GenericDomTree.h"
 #include "llvm/Support/GenericDomTreeConstruction.h"
+#include <memory>
 
 namespace llvm {
 
 template<>
 inline void DominatorTreeBase<MachineBasicBlock>::addRoot(MachineBasicBlock* MBB) {
   this->Roots.push_back(MBB);
 }
 
class MachineDominatorTree : public MachineFunctionPass {
   /// edge splitting.
   /// Invariant: NewBBs == all the basic blocks contained in the NewBB
   /// field of all the elements of CriticalEdgesToSplit.
   /// I.e., forall elt in CriticalEdgesToSplit, it exists BB in NewBBs
   /// such as BB == elt.NewBB.
   mutable SmallSet<MachineBasicBlock *, 32> NewBBs;
 
   /// The DominatorTreeBase that is used to compute a normal dominator tree
-  DominatorTreeBase<MachineBasicBlock>* DT;
+  std::unique_ptr<DominatorTreeBase<MachineBasicBlock>> DT;
 
   /// \brief Apply all the recorded critical edges to the DT.
   /// This updates the underlying DT information in a way that uses
   /// the fast query path of DT as much as possible.
   ///
   /// \post CriticalEdgesToSplit.empty().
   void applySplitCriticalEdges() const;
 
 public:
   static char ID; // Pass ID, replacement for typeid
 
   MachineDominatorTree();
 
-  ~MachineDominatorTree() override;
-
   DominatorTreeBase<MachineBasicBlock> &getBase() {
     applySplitCriticalEdges();
     return *DT;
   }
 
   void getAnalysisUsage(AnalysisUsage &AU) const override;
 
   /// getRoots -  Return the root blocks of the current CFG.  This may include
void recordSplitCriticalEdge(MachineBasicBlock *FromBB,
                               MachineBasicBlock *NewBB) {
     bool Inserted = NewBBs.insert(NewBB).second;
     (void)Inserted;
     assert(Inserted &&
            "A basic block inserted via edge splitting cannot appear twice");
     CriticalEdgesToSplit.push_back({FromBB, ToBB, NewBB});
   }
 
-  /// \brief Returns *false* if the other dominator tree matches this dominator
-  /// tree.
-  inline bool compare(const MachineDominatorTree &Other) const {
-    const MachineDomTreeNode *R = getRootNode();
-    const MachineDomTreeNode *OtherR = Other.getRootNode();
-
-    if (!R || !OtherR || R->getBlock() != OtherR->getBlock())
-      return true;
-
-    if (DT->compare(*Other.DT))
-      return true;
-
-    return false;
-  }
-
   /// \brief Verify the correctness of the domtree by re-computing it.
   ///
   /// This should only be used for debugging as it aborts the program if the
   /// verification fails.
   void verifyDomTree() const;
 };
 
 //===-------------------------------------

lib/CodeGen/MachineDominators.cpp

 void MachineDominatorTree::getAnalysisUsage(AnalysisUsage &AU) const {
   AU.setPreservesAll();
   MachineFunctionPass::getAnalysisUsage(AU);
 }
 
 bool MachineDominatorTree::runOnMachineFunction(MachineFunction &F) {
   CriticalEdgesToSplit.clear();
   NewBBs.clear();
+  DT.reset(new DominatorTreeBase<MachineBasicBlock>(false));
   DT->recalculate(F);
-
   return false;
 }
 
 MachineDominatorTree::MachineDominatorTree()
     : MachineFunctionPass(ID) {
   initializeMachineDominatorTreePass(*PassRegistry::getPassRegistry());
-  DT = new DominatorTreeBase<MachineBasicBlock>(false);
-}
-
-MachineDominatorTree::~MachineDominatorTree() {
-  delete DT;
 }
 
 void MachineDominatorTree::releaseMemory() {
-  DT->releaseMemory();
+  DT.reset(nullptr);
 }
 
 void MachineDominatorTree::verifyAnalysis() const {
-  if (VerifyMachineDomInfo)
+  if (DT && VerifyMachineDomInfo)
     verifyDomTree();
 }
 
 void MachineDominatorTree::print(raw_ostream &OS, const Module*) const {
+  if (DT)
     DT->print(OS);
 }
 
 void MachineDominatorTree::applySplitCriticalEdges() const {
   // Bail out early if there is nothing to do.
   if (CriticalEdgesToSplit.empty())
     return;
 
   // For each element in CriticalEdgesToSplit, remember whether or not element
if (IsNewIDom[Idx])
       DT->changeImmediateDominator(DT->getNode(Edge.ToBB), NewDTNode);
     ++Idx;
   }
   NewBBs.clear();
   CriticalEdgesToSplit.clear();
 }
 
 void MachineDominatorTree::verifyDomTree() const {
+  if (!DT)
+    return;
   MachineFunction &F = *getRoot()->getParent();
 
-  MachineDominatorTree OtherDT;
-  OtherDT.DT->recalculate(F);
-  if (compare(OtherDT)) {
+  DominatorTreeBase<MachineBasicBlock> OtherDT(false);
+  OtherDT.recalculate(F);
+  if (getRootNode()->getBlock() != OtherDT.getRootNode()->getBlock() ||
+      DT->compare(OtherDT)) {
     errs() << "MachineDominatorTree is not up to date!\nComputed:\n";
-    print(errs(), nullptr);
+    DT->print(errs());
     errs() << "\nActual:\n";
-    OtherDT.print(errs(), nullptr);
+    OtherDT.print(errs());
     abort();
   }
 }

test/CodeGen/Generic/externally_available.ll

-; RUN: llc < %s | not grep test_
+; RUN: llc -verify-machine-dom-info < %s | not grep test_
 
 ; test_function should not be emitted to the .s file.
 define available_externally i32 @test_function() {
   ret i32 4
 }
 
 ; test_global should not be emitted to the .s file.
 @test_global = available_externally global i32 4