Index: flang/include/flang/Parser/parse-tree-visitor.h =================================================================== --- flang/include/flang/Parser/parse-tree-visitor.h +++ flang/include/flang/Parser/parse-tree-visitor.h @@ -16,6 +16,7 @@ #include #include #include +#include /// Parse tree visitor /// Call Walk(x, visitor) to visit x and, by default, each node under x. @@ -483,20 +484,76 @@ mutator.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 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 +static void IterativeWalk(A &start, V &visitor) { + struct ExprWorkList { + ExprWorkList(A &x) : expr(&x) {} + bool doPostExpr{false}, doPostOpr{false}; + A *expr; + }; + std::vector 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) { + unary = &y; + } else if constexpr (std::is_convertible_v) { + 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()); + } + } + } + } while (!stack.empty()); +} template void Walk(const Expr &x, V &visitor) { - if (visitor.Pre(x)) { - Walk(x.source, visitor); - Walk(x.u, visitor); - visitor.Post(x); - } + IterativeWalk(x, visitor); } template void Walk(Expr &x, M &mutator) { - if (mutator.Pre(x)) { - Walk(x.source, mutator); - Walk(x.u, mutator); - mutator.Post(x); - } + IterativeWalk( + x, mutator); } + template void Walk(const Designator &x, V &visitor) { if (visitor.Pre(x)) { Walk(x.source, visitor); Index: flang/include/flang/Semantics/expression.h =================================================================== --- flang/include/flang/Semantics/expression.h +++ flang/include/flang/Semantics/expression.h @@ -378,6 +378,8 @@ 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 impliedDos_; // values are INTEGER kinds @@ -387,6 +389,7 @@ bool inWhereBody_{false}; bool inDataStmtConstant_{false}; bool inStmtFunctionDefinition_{false}; + bool iterativelyAnalyzingSubexpressions_{false}; friend class ArgumentAnalyzer; }; Index: flang/lib/Semantics/expression.cpp =================================================================== --- flang/lib/Semantics/expression.cpp +++ flang/lib/Semantics/expression.cpp @@ -29,6 +29,7 @@ #include #include #include +#include // Typedef for optional generic expressions (ubiquitous in this file) using MaybeExpr = @@ -3207,6 +3208,12 @@ result = Analyze(x.u); } if (result) { + if constexpr (std::is_same_v) { + 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 { @@ -3222,15 +3229,76 @@ } } +// 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 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) { + // Don't evaluate a constant operand to Negate + if (!std::holds_alternative( + y.v.value().u)) { + unary = &y; + } + } else if constexpr (std::is_convertible_v) { + 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) { - return expr.typedExpr->v; + bool wasIterativelyAnalyzing{iterativelyAnalyzingSubexpressions_}; + MaybeExpr result; + if (useSavedTypedExprs_) { + if (expr.typedExpr) { + return expr.typedExpr->v; + } + if (!wasIterativelyAnalyzing) { + iterativelyAnalyzingSubexpressions_ = true; + result = IterativelyAnalyzeSubexpressions(expr); + } } - 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 (!result) { + result = ExprOrVariable(expr, expr.source); } + iterativelyAnalyzingSubexpressions_ = wasIterativelyAnalyzing; return result; } @@ -3898,7 +3966,7 @@ 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); Index: flang/test/Evaluate/big-expr-tree.F90 =================================================================== --- /dev/null +++ flang/test/Evaluate/big-expr-tree.F90 @@ -0,0 +1,9 @@ +! RUN: %python %S/test_folding.py %s %flang_fc1 +! Exercise parsing, expression analysis, and folding on a very tall expression tree +! 32*32*32 = 32768 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 +#define M2(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**3 .EQ. M2(M1(M0(1))) +end module