Use less stack in DAGISelMatcherOpt

[JonChesterfield]

Summary

Refactor a helper function, FactorNodes, to search for a push node in constant space. This resolves a problem in a not-yet-upstreamed backend where a recursive pattern blew the call stack (at a depth of 255) under a debug build of tablegen. No functional change so no new test coverage. The change is minimal to avoid disturbing existing behaviour.

[stoklund]

Looks good. I'm all for eliminating recursion.

utils/TableGen/DAGISelMatcherOpt.cpp

188 ↗

(On Diff #85577)

while (!Scope) {?

[JonChesterfield]

• Change for to while

[JonChesterfield]

Thank you for the review. Could you commit the patch? I don't have write access to the repo.

[stoklund]

Sorry, I don't have an LLVM sandbox these days. Maybe ask on llvm-commits?

[JonChesterfield]

Thanks, I hadn't spotted llvm-commits. I'll send them a message.

llvm/trunk/utils/TableGen/DAGISelMatcherOpt.cpp

 ///     OPC_CheckType i32
 ///       XYZ
 /// into:
 ///   OPC_CheckType i32
 ///     Scope
 ///       ABC
 ///       XYZ
 ///
-static void FactorNodes(std::unique_ptr<Matcher> &MatcherPtr) {
+static void FactorNodes(std::unique_ptr<Matcher> &InputMatcherPtr) {
+  // Look for a push node. Iterates instead of recurses to reduce stack usage.
+  ScopeMatcher *Scope = nullptr;
+  std::unique_ptr<Matcher> *RebindableMatcherPtr = &InputMatcherPtr;
+  while (!Scope) {
     // If we reached the end of the chain, we're done.
-  Matcher *N = MatcherPtr.get();
+    Matcher *N = RebindableMatcherPtr->get();
     if (!N) return;
-  
     // If this is not a push node, just scan for one.
-  ScopeMatcher *Scope = dyn_cast<ScopeMatcher>(N);
+    Scope = dyn_cast<ScopeMatcher>(N);
     if (!Scope)
-    return FactorNodes(N->getNextPtr());
+      RebindableMatcherPtr = &(N->getNextPtr());
+  }
+  std::unique_ptr<Matcher> &MatcherPtr = *RebindableMatcherPtr;
   
   // Okay, pull together the children of the scope node into a vector so we can
   // inspect it more easily.
   SmallVector<Matcher*, 32> OptionsToMatch;
   
   for (unsigned i = 0, e = Scope->getNumChildren(); i != e; ++i) {
     // Factor the subexpression.
     std::unique_ptr<Matcher> Child(Scope->takeChild(i));