Fix InlineSpiller accessing not updated dominator tree base information

[Ka-Ka]

Summary

The InlineSpiller was accessing the DominatorTreeBase directly through the public data member DT in the MachineDominatorTree. This is not a good idea as the "cached" information in SplitCriticalEdges is not applied before the access. The DominatorTreeBase must be accessed through the member function getBase() in MachineDominatorTree.

The fault was introduced in r266162.

I think the public data member DT in the MachineDominatorTree should have been made private in the original code (r215576) that introduced the concept of lazily updating the MachineDominatorTree information from
MachineBasicBlock::SplitCriticalEdge().

[qcolombet]

Hi,

The change looks good, but do you have a test case to add with it?

Thanks,
-Quentin

[Ka-Ka]

I have a reproducer for an out of target backend. I will give it a try (tomorrow) to transform it into a x86 reproducer, but I suspect that it might be hard to get it working.

[Ka-Ka]

In D27983#628114, @qcolombet wrote:

Hi,

The change looks good, but do you have a test case to add with it?

Thanks,
-Quentin

Unfortunately I'm not able to convert the reproducer we have in our out of tree backend to x86. The way split critical edges work by "caching" information in data structures (between different the passes) that is not a part of the IR make it hard to transform the reproducer to another backend as it must involve several passes. The reproducer I have in our out of tree backend work as following:

The PHIElimination pass introduce new basic blocks in PHIElimination::SplitPHIEdges(). The method MachineBasicBlock::SplitCriticalEdge() call MDT->recordSplitCriticalEdge() to update the dominator tree information, but it do not update the the dominator tree directly but instead store ("cache") the information for applying it later. Several passes execute and then when register allocator (RegAllocGreedy pass) execute InlineSpiller must access instructions in the newly introduced basic block from HoistSpillHelper::rmRedundantSpills(). The rmRedundantSpills() faulty access the dominator tree directly through the data member DT in the MachineDominatorTree (that will not apply the stored ("cached") information before the access).

To transform this reproducer to trigger the fault in another backend (x86) that have a totally different register set seems to be too tricky for me. I guess you have to either accept the changes without a testcase or leave the changes out.

Regards
/ Karl-Johan Karlsson

[qcolombet]

I guess you have to either accept the changes without a testcase or leave the changes out.

That's fine, I was expecting something like this, but thanks for double checking.

LGTM.

Cheers,
-Quentin

llvm/trunk/include/llvm/CodeGen/MachineDominators.h

class MachineDominatorTree : public MachineFunctionPass {
   /// \brief Remember all the basic blocks that are inserted during
   /// 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;
+
   /// \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
-  DominatorTreeBase<MachineBasicBlock>* DT;
 
   MachineDominatorTree();
 
   ~MachineDominatorTree() override;
 
   DominatorTreeBase<MachineBasicBlock> &getBase() {
     applySplitCriticalEdges();
     return *DT;

llvm/trunk/lib/CodeGen/InlineSpiller.cpp

void HoistSpillHelper::rmRedundantSpills(
     SmallPtrSet<MachineInstr *, 16> &Spills,
     SmallVectorImpl<MachineInstr *> &SpillsToRm,
     DenseMap<MachineDomTreeNode *, MachineInstr *> &SpillBBToSpill) {
   // For each spill saw, check SpillBBToSpill[] and see if its BB already has
   // another spill inside. If a BB contains more than one spill, only keep the
   // earlier spill with smaller SlotIndex.
   for (const auto CurrentSpill : Spills) {
     MachineBasicBlock *Block = CurrentSpill->getParent();
-    MachineDomTreeNode *Node = MDT.DT->getNode(Block);
+    MachineDomTreeNode *Node = MDT.getBase().getNode(Block);
     MachineInstr *PrevSpill = SpillBBToSpill[Node];
     if (PrevSpill) {
       SlotIndex PIdx = LIS.getInstructionIndex(*PrevSpill);
       SlotIndex CIdx = LIS.getInstructionIndex(*CurrentSpill);
       MachineInstr *SpillToRm = (CIdx > PIdx) ? CurrentSpill : PrevSpill;
       MachineInstr *SpillToKeep = (CIdx > PIdx) ? PrevSpill : CurrentSpill;
       SpillsToRm.push_back(SpillToRm);
-      SpillBBToSpill[MDT.DT->getNode(Block)] = SpillToKeep;
+      SpillBBToSpill[MDT.getBase().getNode(Block)] = SpillToKeep;
     } else {
-      SpillBBToSpill[MDT.DT->getNode(Block)] = CurrentSpill;
+      SpillBBToSpill[MDT.getBase().getNode(Block)] = CurrentSpill;
     }
   }
   for (const auto SpillToRm : SpillsToRm)
     Spills.erase(SpillToRm);
 }
 
 /// Starting from \p Root find a top-down traversal order of the dominator
 /// tree to visit all basic blocks containing the elements of \p Spills.
if (SpillToRm) {
       WorkSet.insert(NodesOnPath.begin(), NodesOnPath.end());
     }
     NodesOnPath.clear();
   }
 
   // Sort the nodes in WorkSet in top-down order and save the nodes
   // in Orders. Orders will be used for hoisting in runHoistSpills.
   unsigned idx = 0;
-  Orders.push_back(MDT.DT->getNode(Root));
+  Orders.push_back(MDT.getBase().getNode(Root));
   do {
     MachineDomTreeNode *Node = Orders[idx++];
     const std::vector<MachineDomTreeNode *> &Children = Node->getChildren();
     unsigned NumChildren = Children.size();
     for (unsigned i = 0; i != NumChildren; ++i) {
       MachineDomTreeNode *Child = Children[i];
       if (WorkSet.count(Child))
         Orders.push_back(Child);