[flang] Avoid crashing from recursion on very tall expression parse trees

[klausler]

Summary

In the parse tree visitation framework (Parser/parse-tree-visitor.h)
and in the semantic analyzer for expressions (Semantics/expression.cpp)
avoid crashing due to stack size limitations by using an iterative
traversal algorithm rather than straightforward recursive tree walking.
The iterative approach is the obvious one of building a work queue and
using it to (in the case of the parse tree visitor) call the visitor
object's Pre() and Post() routines on subexpressions in the same order
as they would have been called during a recursive traversal.

This change helps the compiler survive some artificial stress tests
and perhaps with future exposure to machine-generated source code.

[tschuett]

Have you thought about adding a fuzzer for Flang ala
https://github.com/llvm/llvm-project/blob/main/libc/fuzzing/string/strcpy_fuzz.cpp

[jeanPerier]

The code looks good to me, but the torture test seems too big for windows bot: subprocess.CalledProcessError: Command '['c:\\ws\\w32-1\\llvm-project\\premerge-checks\\build\\bin\\flang-new.exe', '-fc1', '-fdebug-dump-symbols', 'C:\\ws\\w32-1\\llvm-project\\premerge-checks\\flang\\test\\Evaluate\\big-expr-tree.F90']' returned non-zero exit status 3221225477.

It led me to try this patch with a linux debug build (I had previously tried a release with no issue), and it crashed on the test. Unless both these crashes are exposing new critical stack overflow issue, I think it might be a bit too risky to put a torture test in default regression tests. Maybe that 4096 or even 1024 repetitions in default regression tests are enough (4096 passed in debug for me).

The stack overflow segfault I saw in debug mode is quite interesting because it happens inside the parser::Program destructor... See the reverse backtrace:

[... inner backtrace]
#177348 0x0000000004ec4df5 in Fortran::parser::ProgramUnit::~ProgramUnit (this=0x9f5a0c0) at flang/include/flang/Parser/parse-tree.h:549
#177349 0x0000000004ec4dd9 in std::__1::allocator_traits<std::__1::allocator<std::__1::__list_node<Fortran::parser::ProgramUnit, void*> > >::__destroy<Fortran::parser::ProgramUnit> (__p=0x9f5a0c0) at include/c++/v1/memory:1747
#177350 0x0000000004ec4c5d in std::__1::allocator_traits<std::__1::allocator<std::__1::__list_node<Fortran::parser::ProgramUnit, void*> > >::destroy<Fortran::parser::ProgramUnit> (__a=..., __p=0x9f5a0c0) at c++/v1/memory:1595
#177351 0x0000000004ec4af6 in std::__1::__list_imp<Fortran::parser::ProgramUnit, std::__1::allocator<Fortran::parser::ProgramUnit> >::clear (this=0x7fffffffc138)  at include/c++/v1/list:762
#177352 0x0000000004ec4a35 in std::__1::__list_imp<Fortran::parser::ProgramUnit, std::__1::allocator<Fortran::parser::ProgramUnit> >::~__list_imp (this=0x7fffffffc138) at include/c++/v1/list:741
#177353 0x0000000004ec4a18 in std::__1::list<Fortran::parser::ProgramUnit, std::__1::allocator<Fortran::parser::ProgramUnit> >::~list (this=0x7fffffffc138) at include/c++/v1/list:834
#177354 0x0000000004ec49f5 in Fortran::parser::Program::~Program (this=0x7fffffffc138) at flang/include/flang/Parser/parse-tree.h:561
#177355 0x0000000004ec49da in std::__1::__optional_destruct_base<Fortran::parser::Program, false>::~__optional_destruct_base (this=0x7fffffffc138)  at include/c++/v1/optional:225
#177356 0x0000000004ec49a8 in std::__1::__optional_storage_base<Fortran::parser::Program, false>::~__optional_storage_base (this=0x7fffffffc138)  at /include/c++/v1/optional:285
#177357 0x0000000004ec4988 in std::__1::__optional_copy_base<Fortran::parser::Program, false>::~__optional_copy_base (this=0x7fffffffc138)  at include/c++/v1/optional:454
#177358 0x0000000004ec4968 in std::__1::__optional_move_base<Fortran::parser::Program, false>::~__optional_move_base (this=0x7fffffffc138)   at include/c++/v1/optional:482
#177359 0x0000000004ec4948 in std::__1::__optional_copy_assign_base<Fortran::parser::Program, false>::~__optional_copy_assign_base (this=0x7fffffffc138)    at include/c++/v1/optional:515
#177360 0x0000000004ec4928 in std::__1::__optional_move_assign_base<Fortran::parser::Program, false>::~__optional_move_assign_base (this=0x7fffffffc138)   at include/c++/v1/optional:547
#177361 0x0000000004ec33c8 in std::__1::optional<Fortran::parser::Program>::~optional (this=0x7fffffffc138)   at include/c++/v1/optional:584
[... outer backtrace in the driver]

Not sure if Windows crash happens in the parse tree dtor too.

[klausler]

Reduce test size so that it passes on Windows.

[klausler]

Try again to tweak test so that it passes on Windows.

[jeanPerier]

Thanks, LGTM

flang/include/flang/Parser/parse-tree-visitor.h

 
 #include "parse-tree.h"
 #include "flang/Common/visit.h"
 #include <cstddef>
 #include <optional>
 #include <tuple>
 #include <utility>
 #include <variant>
+#include <vector>
 
 /// Parse tree visitor
 /// Call Walk(x, visitor) to visit x and, by default, each node under x.
 /// If x is non-const, the visitor member functions can modify the tree.
 ///
 /// visitor.Pre(x) is called before visiting x and its children are not
 /// visited if it returns false.
 ///
template <typename V> void Walk(const CommonStmt &x, V &visitor) {
   }
 }
 template <typename M> void Walk(CommonStmt &x, M &mutator) {
   if (mutator.Pre(x)) {
     Walk(x.blocks, mutator);
     mutator.Post(x);
   }
 }
-template <typename V> void Walk(const Expr &x, V &visitor) {
-  if (visitor.Pre(x)) {
-    Walk(x.source, visitor);
-    Walk(x.u, visitor);
-    visitor.Post(x);
+
+// Expr traversal uses iteration rather than recursion to avoid
+// blowing out the stack on very deep expression parse trees.
+// It replaces implementations that looked like:
+//   template <typename V> void Walk(const Expr &x, V visitor) {
+//     if (visitor.Pre(x)) {      // Pre on the Expr
+//       Walk(x.source, visitor);
+//       // Pre on the operator, walk the operands, Post on operator
+//       Walk(x.u, visitor);
+//       visitor.Post(x);         // Post on the Expr
+//     }
+//   }
+template <typename A, typename V, typename UNARY, typename BINARY>
+static void IterativeWalk(A &start, V &visitor) {
+  struct ExprWorkList {
+    ExprWorkList(A &x) : expr(&x) {}
+    bool doPostExpr{false}, doPostOpr{false};
+    A *expr;
+  };
+  std::vector<ExprWorkList> stack;
+  stack.emplace_back(start);
+  do {
+    A &expr{*stack.back().expr};
+    if (stack.back().doPostOpr) {
+      stack.back().doPostOpr = false;
+      common::visit([&visitor](auto &y) { visitor.Post(y); }, expr.u);
+    } else if (stack.back().doPostExpr) {
+      visitor.Post(expr);
+      stack.pop_back();
+    } else if (!visitor.Pre(expr)) {
+      stack.pop_back();
+    } else {
+      stack.back().doPostExpr = true;
+      Walk(expr.source, visitor);
+      UNARY *unary{nullptr};
+      BINARY *binary{nullptr};
+      common::visit(
+          [&unary, &binary](auto &y) {
+            if constexpr (std::is_convertible_v<decltype(&y), UNARY *>) {
+              unary = &y;
+            } else if constexpr (std::is_convertible_v<decltype(&y),
+                                     BINARY *>) {
+              binary = &y;
+            }
+          },
+          expr.u);
+      if (!unary && !binary) {
+        Walk(expr.u, visitor);
+      } else if (common::visit(
+                     [&visitor](auto &y) { return visitor.Pre(y); }, expr.u)) {
+        stack.back().doPostOpr = true;
+        if (unary) {
+          stack.emplace_back(unary->v.value());
+        } else {
+          stack.emplace_back(std::get<1>(binary->t).value());
+          stack.emplace_back(std::get<0>(binary->t).value());
         }
       }
-template <typename M> void Walk(Expr &x, M &mutator) {
-  if (mutator.Pre(x)) {
-    Walk(x.source, mutator);
-    Walk(x.u, mutator);
-    mutator.Post(x);
     }
+  } while (!stack.empty());
+}
+template <typename V> void Walk(const Expr &x, V &visitor) {
+  IterativeWalk<const Expr, V, const Expr::IntrinsicUnary,
+      const Expr::IntrinsicBinary>(x, visitor);
+}
+template <typename M> void Walk(Expr &x, M &mutator) {
+  IterativeWalk<Expr, M, Expr::IntrinsicUnary, Expr::IntrinsicBinary>(
+      x, mutator);
 }
+
 template <typename V> void Walk(const Designator &x, V &visitor) {
   if (visitor.Pre(x)) {
     Walk(x.source, visitor);
     Walk(x.u, visitor);
     visitor.Post(x);
   }
 }
 template <typename M> void Walk(Designator &x, M &mutator) {

flang/include/flang/Semantics/expression.h

MaybeExpr MakeFunctionRef(
       parser::CharBlock, ProcedureDesignator &&, ActualArguments &&);
   MaybeExpr MakeFunctionRef(parser::CharBlock intrinsic, ActualArguments &&);
   template <typename T> T Fold(T &&expr) {
     return evaluate::Fold(foldingContext_, std::move(expr));
   }
   bool CheckIsValidForwardReference(const semantics::DerivedTypeSpec &);
   MaybeExpr AnalyzeComplex(MaybeExpr &&re, MaybeExpr &&im, const char *what);
 
+  MaybeExpr IterativelyAnalyzeSubexpressions(const parser::Expr &);
+
   semantics::SemanticsContext &context_;
   FoldingContext &foldingContext_{context_.foldingContext()};
   std::map<parser::CharBlock, int> impliedDos_; // values are INTEGER kinds
   bool isWholeAssumedSizeArrayOk_{false};
   bool isNullPointerOk_{false};
   bool useSavedTypedExprs_{true};
   bool inWhereBody_{false};
   bool inDataStmtObject_{false};
   bool inDataStmtConstant_{false};
   bool inStmtFunctionDefinition_{false};
+  bool iterativelyAnalyzingSubexpressions_{false};
   friend class ArgumentAnalyzer;
 };
 
 inline bool AreConformable(int leftRank, int rightRank) {
   return leftRank == 0 || rightRank == 0 || leftRank == rightRank;
 }
 
 template <typename L, typename R>

flang/lib/Semantics/expression.cpp

 #include "flang/Semantics/semantics.h"
 #include "flang/Semantics/symbol.h"
 #include "flang/Semantics/tools.h"
 #include "llvm/Support/raw_ostream.h"
 #include <algorithm>
 #include <functional>
 #include <optional>
 #include <set>
+#include <vector>
 
 // Typedef for optional generic expressions (ubiquitous in this file)
 using MaybeExpr =
     std::optional<Fortran::evaluate::Expr<Fortran::evaluate::SomeType>>;
 
 // Much of the code that implements semantic analysis of expressions is
 // tightly coupled with their typed representations in lib/Evaluate,
 // and appears here in namespace Fortran::evaluate for convenience.
if (const auto *funcRef{
       }
     } else {
       result = Analyze(x.u);
     }
   } else {
     result = Analyze(x.u);
   }
   if (result) {
+    if constexpr (std::is_same_v<PARSED, parser::Expr>) {
+      if (!isNullPointerOk_ && IsNullPointer(*result)) {
+        Say(source,
+            "NULL() may not be used as an expression in this context"_err_en_US);
+      }
+    }
     SetExpr(x, Fold(std::move(*result)));
     return x.typedExpr->v;
   } else {
     ResetExpr(x);
     if (!context_.AnyFatalError()) {
       std::string buf;
       llvm::raw_string_ostream dump{buf};
       parser::DumpTree(dump, x);
       Say("Internal error: Expression analysis failed on: %s"_err_en_US,
           dump.str());
     }
     return std::nullopt;
   }
 }
 
+// This is an optional preliminary pass over parser::Expr subtrees.
+// Given an expression tree, iteratively traverse it in a bottom-up order
+// to analyze all of its subexpressions.  A later normal top-down analysis
+// will then be able to use the results that will have been saved in the
+// parse tree without having to recurse deeply.  This technique keeps
+// absurdly deep expression parse trees from causing the analyzer to overflow
+// its stack.
+MaybeExpr ExpressionAnalyzer::IterativelyAnalyzeSubexpressions(
+    const parser::Expr &top) {
+  std::vector<const parser::Expr *> queue, finish;
+  queue.push_back(&top);
+  do {
+    const parser::Expr &expr{*queue.back()};
+    queue.pop_back();
+    if (!expr.typedExpr) {
+      const parser::Expr::IntrinsicUnary *unary{nullptr};
+      const parser::Expr::IntrinsicBinary *binary{nullptr};
+      common::visit(
+          [&unary, &binary](auto &y) {
+            if constexpr (std::is_convertible_v<decltype(&y),
+                              decltype(unary)>) {
+              // Don't evaluate a constant operand to Negate
+              if (!std::holds_alternative<parser::LiteralConstant>(
+                      y.v.value().u)) {
+                unary = &y;
+              }
+            } else if constexpr (std::is_convertible_v<decltype(&y),
+                                     decltype(binary)>) {
+              binary = &y;
+            }
+          },
+          expr.u);
+      if (unary) {
+        queue.push_back(&unary->v.value());
+      } else if (binary) {
+        queue.push_back(&std::get<0>(binary->t).value());
+        queue.push_back(&std::get<1>(binary->t).value());
+      }
+      finish.push_back(&expr);
+    }
+  } while (!queue.empty());
+  // Analyze the collected subexpressions in bottom-up order.
+  // On an error, bail out and leave partial results in place.
+  MaybeExpr result;
+  for (auto riter{finish.rbegin()}; riter != finish.rend(); ++riter) {
+    const parser::Expr &expr{**riter};
+    result = ExprOrVariable(expr, expr.source);
+    if (!result) {
+      return result;
+    }
+  }
+  return result; // last value was from analysis of "top"
+}
+
 MaybeExpr ExpressionAnalyzer::Analyze(const parser::Expr &expr) {
-  if (useSavedTypedExprs_ && expr.typedExpr) {
+  bool wasIterativelyAnalyzing{iterativelyAnalyzingSubexpressions_};
+  MaybeExpr result;
+  if (useSavedTypedExprs_) {
+    if (expr.typedExpr) {
       return expr.typedExpr->v;
     }
-  MaybeExpr result{ExprOrVariable(expr, expr.source)};
-  if (!isNullPointerOk_ && result && IsNullPointer(*result)) {
-    Say(expr.source,
-        "NULL() may not be used as an expression in this context"_err_en_US);
+    if (!wasIterativelyAnalyzing) {
+      iterativelyAnalyzingSubexpressions_ = true;
+      result = IterativelyAnalyzeSubexpressions(expr);
+    }
+  }
+  if (!result) {
+    result = ExprOrVariable(expr, expr.source);
   }
+  iterativelyAnalyzingSubexpressions_ = wasIterativelyAnalyzing;
   return result;
 }
 
 MaybeExpr ExpressionAnalyzer::Analyze(const parser::Variable &variable) {
   if (useSavedTypedExprs_ && variable.typedExpr) {
     return variable.typedExpr->v;
   }
   return ExprOrVariable(variable, variable.GetSource());
for (const auto &actual : actuals_) {
     }
   }
 }
 
 std::optional<ActualArgument> ArgumentAnalyzer::AnalyzeExpr(
     const parser::Expr &expr) {
   source_.ExtendToCover(expr.source);
   if (const Symbol *assumedTypeDummy{AssumedTypeDummy(expr)}) {
-    expr.typedExpr.Reset(new GenericExprWrapper{}, GenericExprWrapper::Deleter);
+    ResetExpr(expr);
     if (isProcedureCall_) {
       ActualArgument arg{ActualArgument::AssumedType{*assumedTypeDummy}};
       SetArgSourceLocation(arg, expr.source);
       return std::move(arg);
     }
     context_.SayAt(expr.source,
         "TYPE(*) dummy argument may only be used as an actual argument"_err_en_US);
   } else if (MaybeExpr argExpr{AnalyzeExprOrWholeAssumedSizeArray(expr)}) {

flang/test/Evaluate/big-expr-tree.F90

+! RUN: %python %S/test_folding.py %s %flang_fc1
+! Exercise parsing, expression analysis, and folding on a very tall expression tree
+! 32*32 = 1024 repetitions
+#define M0(x) x+x+x+x+x+x+x+x+x+x+x+x+x+x+x+x+x+x+x+x+x+x+x+x+x+x+x+x+x+x+x+x
+#define M1(x) x+x+x+x+x+x+x+x+x+x+x+x+x+x+x+x+x+x+x+x+x+x+x+x+x+x+x+x+x+x+x+x
+module m
+  logical, parameter :: test_1 = 32**2 .EQ. M1(M0(1))
+end module