[gicombiner] Process the MatchDag such that every node is reachable from the roots

[dsanders]

Summary

When we build the walk across these DAG's we need to be able to reach every node
from the roots. Flip and traversal edges (so that use->def becomes def->uses)
that make nodes unreachable. Note that early on we'll just error out on these
flipped edges as def->uses edges are more complicated to match due to their
one->many nature.

Depends on D69077

[dsanders]

llvm/utils/TableGen/GICombinerEmitter.cpp

146

During an off-list review it was pointed out that this is quadratic in the worst case. I haven't fixed that yet but I don't think it's likely to be an issue in practice. This is partly due to the DAG's tending to be small (1-5 instr nodes) but is mostly due to the common case for the shape of the DAG.

The quadratic case is a 'straight-line' DAG of the form:

A->B->C->D->E

which can occasionally occur but is rarely more than 3 nodes long. The best case is a fan-out like:

A->{B,C,D,E}

which is linear but most DAGs will be roughly nlogn. For example:

A->{B,C}
B->{D,E}

If it becomes a bottleneck then I can improve this

[volkan]

LGTM with a couple of nits.

llvm/utils/TableGen/GICombinerEmitter.cpp

160

No need to create a new set for each edge, this can be moved outside of the loop.

189

Looks like there is no other debug output in this functions, is it worth keeping this?

[dsanders]

llvm/utils/TableGen/GICombinerEmitter.cpp

189

It's useful for seeing where the overall tablegen pass has got to.

[dsanders]

Landed in rG520e3d66e7257c77f1226185504bbe1cb90afcfa (and re-committed in rG7ea2e5195a82bd9370d0b4362512b67c8b2cde80

llvm/include/llvm/ADT/iterator.h

template <typename RangeT, typename WrappedIteratorT =
                                decltype(std::begin(std::declval<RangeT>()))>
 iterator_range<pointer_iterator<WrappedIteratorT>>
 make_pointer_range(RangeT &&Range) {
   using PointerIteratorT = pointer_iterator<WrappedIteratorT>;
   return make_range(PointerIteratorT(std::begin(std::forward<RangeT>(Range))),
                     PointerIteratorT(std::end(std::forward<RangeT>(Range))));
 }
 
+template <typename WrappedIteratorT,
+          typename T1 = typename std::remove_reference<decltype(**std::declval<WrappedIteratorT>())>::type,
+          typename T2 = typename std::add_pointer<T1>::type>
+using raw_pointer_iterator = pointer_iterator<pointee_iterator<WrappedIteratorT, T1>, T2>;
+
 // Wrapper iterator over iterator ItType, adding DataRef to the type of ItType,
 // to create NodeRef = std::pair<InnerTypeOfItType, DataRef>.
 template <typename ItType, typename NodeRef, typename DataRef>
 class WrappedPairNodeDataIterator
     : public iterator_adaptor_base<
           WrappedPairNodeDataIterator<ItType, NodeRef, DataRef>, ItType,
           typename std::iterator_traits<ItType>::iterator_category, NodeRef,
           std::ptrdiff_t, NodeRef *, NodeRef &> {

llvm/test/TableGen/GICombinerEmitter/parse-match-pattern.td

def nonstandardroot : GICombineRule<
   (apply [{ APPLY }])>;
 
 // CHECK-LABEL: Parsed rule defs/match for 'nonstandardroot'
 
 // CHECK-NEXT: matchdag {
 // CHECK-NEXT:     (MOV 0:dst<def>, 1:src1):$__anon3_0 // $s=getOperand(0), $s2=getOperand(1)
 // CHECK-NEXT:     (MOV 0:dst<def>, 1:src1):$__anon3_2 // $d1=getOperand(0), $s=getOperand(1)
 // CHECK-NEXT:     (MOV 0:dst<def>, 1:src1):$__anon3_4 // $d2=getOperand(0), $s=getOperand(1)
-// CHECK-NEXT:     __anon3_2[src1] --[s]--> __anon3_0[dst]
-// CHECK-NEXT:     __anon3_4[src1] --[s]--> __anon3_0[dst]
+// CHECK-NEXT:     __anon3_0[dst] --[s]--> __anon3_2[src1]
+// CHECK-NEXT:     __anon3_0[dst] --[s]--> __anon3_4[src1]
 // CHECK-NEXT:     <<$mi.getOpcode() == MOV>>:$__anonpred3_1
 // CHECK-NEXT:     <<$mi.getOpcode() == MOV>>:$__anonpred3_3
 // CHECK-NEXT:     <<$mi.getOpcode() == MOV>>:$__anonpred3_5
 // CHECK-NEXT:     <<$mi0 == $mi1>>:$__anonpred3_6
 // CHECK-NEXT:     __anon3_0 ==> __anonpred3_1[mi]
 // CHECK-NEXT:     __anon3_2 ==> __anonpred3_3[mi]
 // CHECK-NEXT:     __anon3_4 ==> __anonpred3_5[mi]
 // CHECK-NEXT:     __anon3_2[src1] ==> __anonpred3_6[mi0]
 // CHECK-NEXT:     __anon3_4[src1] ==> __anonpred3_6[mi1]
 // CHECK-NEXT: {{^}$}}
 
 // CHECK-NEXT: digraph "nonstandardroot" {
 // CHECK-NEXT:   rankdir="BT"
 // CHECK-NEXT:   Node[[N1:0x[0-9a-f]+]] [shape=record,label="{{[{]{}}<s0>#0 $dst|<s1>#1 $src1}|__anon3_0|MOV|Match starts here|$s=getOperand(0), $s2=getOperand(1)|{{0x[0-9a-f]+}}|{<d0>#0 $dst|<d1>#1 $src1}}",color=red]
 // CHECK-NEXT:   Node[[N2:0x[0-9a-f]+]] [shape=record,label="{{[{]{}}<s0>#0 $dst|<s1>#1 $src1}|__anon3_2|MOV|$d1=getOperand(0), $s=getOperand(1)|{{0x[0-9a-f]+}}|{<d0>#0 $dst|<d1>#1 $src1}}"]
 // CHECK-NEXT:   Node[[N3:0x[0-9a-f]+]] [shape=record,label="{{[{]{}}<s0>#0 $dst|<s1>#1 $src1}|__anon3_4|MOV|$d2=getOperand(0), $s=getOperand(1)|{{0x[0-9a-f]+}}|{<d0>#0 $dst|<d1>#1 $src1}}"]
-// CHECK-NEXT:   Node[[N2]]:s1:n -> Node[[N1]]:d0:s [label="$s"]
-// CHECK-NEXT:   Node[[N3]]:s1:n -> Node[[N1]]:d0:s [label="$s"]
+// CHECK-NEXT:   Node[[N2]]:s1:n -> Node[[N1]]:d0:s [label="$s",dir=back,arrowtail=crow]
+// CHECK-NEXT:   Node[[N3]]:s1:n -> Node[[N1]]:d0:s [label="$s",dir=back,arrowtail=crow]
 // CHECK-NEXT:   Pred[[P1:0x[0-9a-f]+]] [shape=record,label="{{[{]{}}<s0>#0 $$|<s1>#1 $mi}|__anonpred3_1|$mi.getOpcode() == MOV|{{0x[0-9a-f]+}}|{<d0>#0 $$|<d1>#1 $mi}}",style=dotted]
 // CHECK-NEXT:   Pred[[P2:0x[0-9a-f]+]] [shape=record,label="{{[{]{}}<s0>#0 $$|<s1>#1 $mi}|__anonpred3_3|$mi.getOpcode() == MOV|{{0x[0-9a-f]+}}|{<d0>#0 $$|<d1>#1 $mi}}",style=dotted]
 // CHECK-NEXT:   Pred[[P3:0x[0-9a-f]+]] [shape=record,label="{{[{]{}}<s0>#0 $$|<s1>#1 $mi}|__anonpred3_5|$mi.getOpcode() == MOV|{{0x[0-9a-f]+}}|{<d0>#0 $$|<d1>#1 $mi}}",style=dotted]
 // CHECK-NEXT:   Pred[[P4:0x[0-9a-f]+]] [shape=record,label="{{[{]{}}<s0>#0 $$|<s1>#1 $mi0|<s2>#2 $mi1}|__anonpred3_6|$mi0 == $mi1|{{0x[0-9a-f]+}}|{<d0>#0 $$|<d1>#1 $mi0|<d2>#2 $mi1}}",style=dotted]
 // CHECK-NEXT:   Node[[N1]]:e -> Pred[[P1]]:d1:s [style=dotted]
 // CHECK-NEXT:   Node[[N2]]:e -> Pred[[P2]]:d1:s [style=dotted]
 // CHECK-NEXT:   Node[[N3]]:e -> Pred[[P3]]:d1:s [style=dotted]
 // CHECK-NEXT:   Node[[N2]]:s1:n -> Pred[[P4]]:d1:s [style=dotted]

llvm/utils/TableGen/GICombinerEmitter.cpp

 //===- GlobalCombinerEmitter.cpp - Generate a combiner --------------------===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 //
 /// \file Generate a combiner implementation for GlobalISel from a declarative
 /// syntax
 ///
 //===----------------------------------------------------------------------===//
 
+#include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/ADT/StringSet.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/ScopedPrinter.h"
 #include "llvm/Support/Timer.h"
 #include "llvm/TableGen/Error.h"
 #include "llvm/TableGen/StringMatcher.h"
 #include "llvm/TableGen/TableGenBackend.h"
public:
   const GIMatchDag &getMatchDag() const { return MatchDag; }
 
   using const_root_iterator = std::vector<RootInfo>::const_iterator;
   const_root_iterator roots_begin() const { return Roots.begin(); }
   const_root_iterator roots_end() const { return Roots.end(); }
   iterator_range<const_root_iterator> roots() const {
     return llvm::make_range(Roots.begin(), Roots.end());
   }
+
+  /// The matcher will begin from the roots and will perform the match by
+  /// traversing the edges to cover the whole DAG. This function reverses DAG
+  /// edges such that everything is reachable from a root. This is part of the
+  /// preparation work for flattening the DAG into a tree.
+  void reorientToRoots() {
+    SmallSet<const GIMatchDagInstr *, 5> Roots;
+    SmallSet<const GIMatchDagInstr *, 5> Visited;
+    SmallSet<GIMatchDagEdge *, 20> EdgesRemaining;
+
+    for (auto &I : MatchDag.roots()) {
+      Roots.insert(I);
+      Visited.insert(I);
+    }
+    for (auto &I : MatchDag.edges())
+      EdgesRemaining.insert(I);
+
+    bool Progressed = false;
+    while (!EdgesRemaining.empty()) {
+      SmallSet<GIMatchDagEdge *, 20> EdgesToRemove;
+      for (auto EI = EdgesRemaining.begin(), EE = EdgesRemaining.end();
+           EI != EE; ++EI) {
+        if (Visited.count((*EI)->getFromMI())) {
+          if (Roots.count((*EI)->getToMI()))
+            PrintError(TheDef.getLoc(), "One or more roots are unnecessary");
+          Visited.insert((*EI)->getToMI());
+          EdgesToRemove.insert(*EI);
+          Progressed = true;
+        }
+      }
+      for (GIMatchDagEdge *ToRemove : EdgesToRemove)
+        EdgesRemaining.erase(ToRemove);
+      EdgesToRemove.clear();
+
+      for (auto EI = EdgesRemaining.begin(), EE = EdgesRemaining.end();
+           EI != EE; ++EI) {
+        if (Visited.count((*EI)->getToMI())) {
+          (*EI)->reverse();
+          Visited.insert((*EI)->getToMI());
+          EdgesToRemove.insert(*EI);
+          Progressed = true;
+        }
+        for (GIMatchDagEdge *ToRemove : EdgesToRemove)
+          EdgesRemaining.erase(ToRemove);
+        EdgesToRemove.clear();
+      }
+
+      if (!Progressed) {
+        LLVM_DEBUG(dbgs() << "No progress\n");
+        return;
+      }
+      Progressed = false;
+    }
+  }
 };
 
 /// A convenience function to check that an Init refers to a specific def. This
 /// is primarily useful for testing for defs and similar in DagInit's since
 /// DagInit's support any type inside them.
 static bool isSpecificDef(const Init &N, StringRef Def) {
   if (const DefInit *OpI = dyn_cast<DefInit>(&N))
     if (OpI->getDef()->getName() == Def)

 GICombinerEmitter::makeCombineRule(const Record &TheDef) {
   std::unique_ptr<CombineRule> Rule =
       std::make_unique<CombineRule>(Target, MatchDagCtx, NumPatternTotal, TheDef);
 
   if (!Rule->parseDefs())
     return nullptr;
   if (!Rule->parseMatcher(Target))
     return nullptr;
+
+  Rule->reorientToRoots();
+
   LLVM_DEBUG(dbgs() << "Parsed rule defs/match for '" << Rule->getName()
                     << "'\n");
   LLVM_DEBUG(Rule->getMatchDag().dump());
   LLVM_DEBUG(Rule->getMatchDag().writeDOTGraph(dbgs(), Rule->getName()));
   if (StopAfterParse) {
     return Rule;
   }
 

llvm/utils/TableGen/GlobalISel/GIMatchDag.h

#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
   LLVM_DUMP_METHOD void dump() const { print(errs()); }
 #endif // if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 };
 
 class GIMatchDag {
 public:
   using InstrNodesVec = std::vector<std::unique_ptr<GIMatchDagInstr>>;
   using EdgesVec = std::vector<std::unique_ptr<GIMatchDagEdge>>;
+  using edge_iterator = raw_pointer_iterator<EdgesVec::iterator>;
+  using const_edge_iterator = raw_pointer_iterator<EdgesVec::const_iterator>;
+
   using PredicateNodesVec = std::vector<std::unique_ptr<GIMatchDagPredicate>>;
 
   using PredicateDependencyEdgesVec =
       std::vector<std::unique_ptr<GIMatchDagPredicateDependencyEdge>>;
 
 protected:
   GIMatchDagContext &Ctx;
   InstrNodesVec InstrNodes;
   PredicateNodesVec PredicateNodes;
   EdgesVec Edges;
   PredicateDependencyEdgesVec PredicateDependencies;
   std::vector<GIMatchDagInstr *> MatchRoots;
 
 public:
   GIMatchDag(GIMatchDagContext &Ctx)
       : Ctx(Ctx), InstrNodes(), PredicateNodes(), Edges(),
         PredicateDependencies() {}
   GIMatchDag(const GIMatchDag &) = delete;
 
   GIMatchDagContext &getContext() const { return Ctx; }
+  edge_iterator edges_begin() {
+    return raw_pointer_iterator<EdgesVec::iterator>(Edges.begin());
+  }
+  edge_iterator edges_end() {
+    return raw_pointer_iterator<EdgesVec::iterator>(Edges.end());
+  }
+  const_edge_iterator edges_begin() const {
+    return raw_pointer_iterator<EdgesVec::const_iterator>(Edges.begin());
+  }
+  const_edge_iterator edges_end() const {
+    return raw_pointer_iterator<EdgesVec::const_iterator>(Edges.end());
+  }
+  iterator_range<edge_iterator> edges() {
+    return make_range(edges_begin(), edges_end());
+  }
+  iterator_range<const_edge_iterator> edges() const {
+    return make_range(edges_begin(), edges_end());
+  }
+  iterator_range<std::vector<GIMatchDagInstr *>::iterator> roots() {
+    return make_range(MatchRoots.begin(), MatchRoots.end());
+  }
+  iterator_range<std::vector<GIMatchDagInstr *>::const_iterator> roots() const {
+    return make_range(MatchRoots.begin(), MatchRoots.end());
+  }
 
   template <class... Args> GIMatchDagInstr *addInstrNode(Args &&... args) {
     auto Obj =
         std::make_unique<GIMatchDagInstr>(*this, std::forward<Args>(args)...);
     auto ObjRaw = Obj.get();
     InstrNodes.push_back(std::move(Obj));
     return ObjRaw;
   }

llvm/utils/TableGen/GlobalISel/GIMatchDagEdge.h

GIMatchDagEdge(StringRef Name, const GIMatchDagInstr *FromMI, const GIMatchDagOperand *FromMO,
       : Name(Name), FromMI(FromMI), FromMO(FromMO), ToMI(ToMI), ToMO(ToMO) {}
 
   StringRef getName() const { return Name; }
   const GIMatchDagInstr *getFromMI() const { return FromMI; }
   const GIMatchDagOperand *getFromMO() const { return FromMO; }
   const GIMatchDagInstr *getToMI() const { return ToMI; }
   const GIMatchDagOperand *getToMO() const { return ToMO; }
 
+  /// Flip the direction of the edge.
+  void reverse();
+
   LLVM_DUMP_METHOD void print(raw_ostream &OS) const;
 
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
   LLVM_DUMP_METHOD void dump() const;
 #endif // if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 };
 
 raw_ostream &operator<<(raw_ostream &OS, const GIMatchDagEdge &E);
 
 } // end namespace llvm
 #endif // ifndef LLVM_UTILS_TABLEGEN_GIMATCHDAGEDGE_H

llvm/utils/TableGen/GlobalISel/GIMatchDagEdge.cpp

 using namespace llvm;
 
 LLVM_DUMP_METHOD void GIMatchDagEdge::print(raw_ostream &OS) const {
   OS << getFromMI()->getName() << "[" << getFromMO()->getName() << "] --["
      << Name << "]--> " << getToMI()->getName() << "[" << getToMO()->getName()
      << "]";
 }
 
+void GIMatchDagEdge::reverse() {
+  std::swap(FromMI, ToMI);
+  std::swap(FromMO, ToMO);
+}
+