[Support][NFC] Fix generic `ChildrenGetterTy` of `IDFCalculatorBase`

[zero9178]

Summary

Both IDFCalculatorBase and its accompanying DominatorTreeBase only supports pointer nodes. The template argument is the block type itself and any uses of GraphTraits is therefore done via a pointer to the node type.
However, the ChildrenGetterTy type of IDFCalculatorBase has a use on just the node type instead of a pointer to the node type. Various parts of the monorepo has worked around this issue by providing specializations of GraphTraits for the node type directly, or not been affected by using specializations instead of the generic case. These are unnecessary however and instead the generic code should be fixed instead.

An example from within Tree is eg. A use of IDFCalculatorBase in InstrRefBasedImpl.cpp. It basically instantiates a IDFCalculatorBase<MachineBasicBlock, false> but due to the bug above then goes on to specialize GraphTraits<MachineBasicBlock> although GraphTraits<MachineBasicBlock*> exists (and should be used instead).

Similar dead code exists in clang which defines redundant GraphTraits to work around this bug.

This patch fixes both the original issue and removes the dead code that was used to work around the issue.

As a side node, my own motivation was when using MLIR and using mlir::Blocks as nodes. As MLIR correctly only provides GraphTraits<mlir::Block*> I was not able to use IDFCalculatorBase.

[kuhar]

LGTM

clang/include/clang/Analysis/Analyses/Dominators.h

 } // end of namespace clang
 
 namespace llvm {
 namespace IDFCalculatorDetail {
 
 /// Specialize ChildrenGetterTy to skip nullpointer successors.
 template <bool IsPostDom>
 struct ChildrenGetterTy<clang::CFGBlock, IsPostDom> {
-  using NodeRef = typename GraphTraits<clang::CFGBlock>::NodeRef;
+  using NodeRef = typename GraphTraits<clang::CFGBlock *>::NodeRef;
   using ChildrenTy = SmallVector<NodeRef, 8>;
 
   ChildrenTy get(const NodeRef &N) {
     using OrderedNodeTy =
         typename IDFCalculatorBase<clang::CFGBlock, IsPostDom>::OrderedNodeTy;
 
     auto Children = children<OrderedNodeTy>(N);
     ChildrenTy Ret{Children.begin(), Children.end()};

clang/include/clang/Analysis/CFG.h

template <> struct GraphTraits< ::clang::CFGBlock *> {
   using NodeRef = ::clang::CFGBlock *;
   using ChildIteratorType = ::clang::CFGBlock::succ_iterator;
 
   static NodeRef getEntryNode(::clang::CFGBlock *BB) { return BB; }
   static ChildIteratorType child_begin(NodeRef N) { return N->succ_begin(); }
   static ChildIteratorType child_end(NodeRef N) { return N->succ_end(); }
 };
 
-template <> struct GraphTraits<clang::CFGBlock>
-    : GraphTraits<clang::CFGBlock *> {};
-
 template <> struct GraphTraits< const ::clang::CFGBlock *> {
   using NodeRef = const ::clang::CFGBlock *;
   using ChildIteratorType = ::clang::CFGBlock::const_succ_iterator;
 
   static NodeRef getEntryNode(const clang::CFGBlock *BB) { return BB; }
   static ChildIteratorType child_begin(NodeRef N) { return N->succ_begin(); }
   static ChildIteratorType child_end(NodeRef N) { return N->succ_end(); }
 };
 
-template <> struct GraphTraits<const clang::CFGBlock>
-    : GraphTraits<clang::CFGBlock *> {};
-
 template <> struct GraphTraits<Inverse< ::clang::CFGBlock *>> {
   using NodeRef = ::clang::CFGBlock *;
   using ChildIteratorType = ::clang::CFGBlock::const_pred_iterator;
 
   static NodeRef getEntryNode(Inverse<::clang::CFGBlock *> G) {
     return G.Graph;
   }
 
   static ChildIteratorType child_begin(NodeRef N) { return N->pred_begin(); }
   static ChildIteratorType child_end(NodeRef N) { return N->pred_end(); }
 };
 
-template <> struct GraphTraits<Inverse<clang::CFGBlock>>
-    : GraphTraits<clang::CFGBlock *> {};
-
 template <> struct GraphTraits<Inverse<const ::clang::CFGBlock *>> {
   using NodeRef = const ::clang::CFGBlock *;
   using ChildIteratorType = ::clang::CFGBlock::const_pred_iterator;
 
   static NodeRef getEntryNode(Inverse<const ::clang::CFGBlock *> G) {
     return G.Graph;
   }
 
   static ChildIteratorType child_begin(NodeRef N) { return N->pred_begin(); }
   static ChildIteratorType child_end(NodeRef N) { return N->pred_end(); }
 };
 
-template <> struct GraphTraits<const Inverse<clang::CFGBlock>>
-    : GraphTraits<clang::CFGBlock *> {};
-
 // Traits for: CFG
 
 template <> struct GraphTraits< ::clang::CFG* >
     : public GraphTraits< ::clang::CFGBlock *>  {
   using nodes_iterator = ::clang::CFG::iterator;
 
   static NodeRef getEntryNode(::clang::CFG *F) { return &F->getEntry(); }
   static nodes_iterator nodes_begin(::clang::CFG* F) { return F->nodes_begin();}

llvm/include/llvm/Support/GenericIteratedDominanceFrontier.h

 namespace llvm {
 
 namespace IDFCalculatorDetail {
 
 /// Generic utility class used for getting the children of a basic block.
 /// May be specialized if, for example, one wouldn't like to return nullpointer
 /// successors.
 template <class NodeTy, bool IsPostDom> struct ChildrenGetterTy {
-  using NodeRef = typename GraphTraits<NodeTy>::NodeRef;
+  using NodeRef = typename GraphTraits<NodeTy *>::NodeRef;
   using ChildrenTy = SmallVector<NodeRef, 8>;
 
   ChildrenTy get(const NodeRef &N);
 };
 
 } // end of namespace IDFCalculatorDetail
 
 /// Determine the iterated dominance frontier, given a set of defining

llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.cpp

while (!Worklist.empty() || !Pending.empty()) {
     // worklist
     assert(Pending.empty() && "Pending should be empty");
   }
 
   // Once all the live-ins don't change on mlocJoin(), we've eliminated all
   // redundant PHIs.
 }
 
-// Boilerplate for feeding MachineBasicBlocks into IDF calculator. Provide
-// template specialisations for graph traits and a successor enumerator.
-namespace llvm {
-template <> struct GraphTraits<MachineBasicBlock> {
-  using NodeRef = MachineBasicBlock *;
-  using ChildIteratorType = MachineBasicBlock::succ_iterator;
-
-  static NodeRef getEntryNode(MachineBasicBlock *BB) { return BB; }
-  static ChildIteratorType child_begin(NodeRef N) { return N->succ_begin(); }
-  static ChildIteratorType child_end(NodeRef N) { return N->succ_end(); }
-};
-
-template <> struct GraphTraits<const MachineBasicBlock> {
-  using NodeRef = const MachineBasicBlock *;
-  using ChildIteratorType = MachineBasicBlock::const_succ_iterator;
-
-  static NodeRef getEntryNode(const MachineBasicBlock *BB) { return BB; }
-  static ChildIteratorType child_begin(NodeRef N) { return N->succ_begin(); }
-  static ChildIteratorType child_end(NodeRef N) { return N->succ_end(); }
-};
-
-using MachineDomTreeBase = DomTreeBase<MachineBasicBlock>::NodeType;
-using MachineDomTreeChildGetter =
-    typename IDFCalculatorDetail::ChildrenGetterTy<MachineDomTreeBase, false>;
-
-namespace IDFCalculatorDetail {
-template <>
-typename MachineDomTreeChildGetter::ChildrenTy
-MachineDomTreeChildGetter::get(const NodeRef &N) {
-  return {N->succ_begin(), N->succ_end()};
-}
-} // namespace IDFCalculatorDetail
-} // namespace llvm
-
 void InstrRefBasedLDV::BlockPHIPlacement(
     const SmallPtrSetImpl<MachineBasicBlock *> &AllBlocks,
     const SmallPtrSetImpl<MachineBasicBlock *> &DefBlocks,
     SmallVectorImpl<MachineBasicBlock *> &PHIBlocks) {
   // Apply IDF calculator to the designated set of location defs, storing
   // required PHIs into PHIBlocks. Uses the dominator tree stored in the
   // InstrRefBasedLDV object.
-  IDFCalculatorDetail::ChildrenGetterTy<MachineDomTreeBase, false> foo;
-  IDFCalculatorBase<MachineDomTreeBase, false> IDF(DomTree->getBase(), foo);
+  IDFCalculatorBase<MachineBasicBlock, false> IDF(DomTree->getBase());
 
   IDF.setLiveInBlocks(AllBlocks);
   IDF.setDefiningBlocks(DefBlocks);
   IDF.calculate(PHIBlocks);
 }
 
 Optional<ValueIDNum> InstrRefBasedLDV::pickVPHILoc(
     const MachineBasicBlock &MBB, const DebugVariable &Var,