[Chapel Merge] Further compiler/next improvements

mppf1 · May 5, 2021, 8:02pm

Branch: refs/heads/master
Revision: efad74a
Author: mppf
Log Message:

Merge pull request #17609 from mppf/new-asts-dev-3

Further compiler/next improvements

This PR takes the following steps to improve upon the compiler/next code.

To address building on different systems:

uses a C file to call aligned_alloc since it is C++17 or C11, but
we currently only require C++14 and C11. This can be removed whenever
we start to require C++17.
uses the CC, CXX, and LDFLAGS settings from the rest of the Makefile
infrastructure when running cmake in compiler/next/Makefile.help.
That way, a compiler selection working with printchplenv
environment variables will be respected if make libchplcomp type
commands are used. The intention is that the compiler/next code also
support building directly with cmake but I have not put much effort
into testing that yet.

To address renaming requests from discussion of the earlier PRs:

Renames the ast namespace to uast (so that the terminology is easier
when people are talking to each other)
Renames the new AST classes to have different names from the old AST
classes. This is so that automated tools like code browsers will be
less likely to be confused. While these names are different, the
differences aren't particularly meaningful, so the expectation is that
code use the namespace (e.g. uast::Block) and conversations say e.g.
"old BlockStmt" or "new Block" to be clear.
- BlockStmt -> Block
- Expr -> Exp (including as a suffix, as in ErroneousExpr ->
  ErroneousExp)
- Stmt class is removed
- Symbol -> Sym
- Type -> TypeSym
- BaseAST -> ASTBase
Renames the subdirectories not implementing a particular class to
start with a lowercase character. E.g. Frontend -> frontend.
compiler/lib/frontend/Parser stays uppercase because it is helper code
for the Parser class.
Renames header and source files not implementing a particular class to
start with a lowercase character.
Renames several "detail" headers to use `-detail.h" rather than
appending Detail.h. This more general strategy looks less strange for
headers not implementing a particular class that begin lowercase.
Renamed the FrontendQueries namespace to just frontend. Now the
namespace matches the directory name. Renamed the header/source file
from FrontendQueries to frontend-queries.
Split ASTList related definitions out of ASTTypes.h and into a new
file ASTList.h

To demonstrate and test the query framework:

frontend-queries.cpp includes new functions, resolveFile,
resolveModule, and resolveAST. These do a simplified scope resolution
on Identifiers and VariableDecls.
added several tests to check the query framework works correctly and
to test the new resolve functionality. The new tests focus more on
incremental recompilation and garbage collection.

To address deficiencies in the prototype query framework:

960a6a1fbb17321a32a4842ba19add38e1fd156e adds support for range-based
for loops enumerating over AST components. We can now use range-based
for loops to enumerate children as ASTBase* or to enumerate
statements in a block as Exp*s.
74ceef2247d8cba5eb0f92649dc8234514450098 adds a Visitor class for
visiting AST nodes. This Visitor class is automatically generated by
ASTClassesList.h but it is not used yet.
83bb86e8c4c153fcecec9f30d99a3be4311984c7 moved ErrorMessage, ID,
Location, and UniqueString out of the uast directory/namespace and to
the chpl namespace level (which is as top level as this library
gets). The rationale for this is that these types are used by the
query framework and in Context.h and so they are more fundamental
than uast. In fact, if the query framework in the future manages,
say, transformation from uast -> old AST -> LLVM IR; we will still
need these types in order to interact with the query framework in
those later steps and as a result it would be confusing if they are
under uast.
f35f1b1f47344b0a81cfcf71b8c39e5d5173abdf updates Context to be
default-constructable instead of requiring Context::build be called
to produce an owned<Context>. At the very least, a lot of tests need
to create a context so making this shorter and involve fewer concepts
seems like an improvement. (Meanwhile there is no particular reason
for this type to always be heap-allocated.)
84ee660a37b15bdd86650a1a5a7f56f364ab58aa enables generating IDs for
comments. The reason for this is that we can't effectively figure out
what file a Comment AST node came from without having an ID, in the
current design. Meanwhile, it is too early to see if giving IDs to
Comments has any significant negative impact on incremental
compilation.
Commits 805c3a307b7225f589cd2b040ec907ea0f0a0375,
4e4aa5c0f731942a6bd21dd78c2421c6d091a18c,
cbb2555263c4d64ada77e9dbd18bfce0fef2c5cd,
0571e66ca72611720ddb0e252b4b0b116b6612ad,
464601015990922b0607069f1158917bd54b592c,
4c12f53dd96e173fbaa6eb84392896320177dc1e,
5aeaba24731dc09ffd42477a0c62b072ba29d242
address problems with the query framework
- I realized that, in the existing implementation, when a query
  started, we could run it or not. But we couldn't rerun a dependency
  first to check to see if it had changed. In order to allow that,
  changed the QUERY_BEGIN call to accept the function name it is
  called in as an argument. This function name is used to save a
  function pointer so that the query can be rerun when the system
  needs to know if a dependency has changed. Meanwhile, when re-runing
  a dependency to see if it has changed, we need to be able to re-run
  a query from a QueryMapResultBase* since that the type stored in
  these dependencies. Since QueryMapResultBase does not know the
  type of the query arguments, it can't call the saved function
  pointer itself. So, it has a virtual method recompute that the
  QueryMapResult template class will override.
- Additionally, in order to implement this virtual method to rerun a
  query, I needed to save the arguments for the query in the
  QueryMapResult class. To avoid storing the arguments redundantly in
  two places, I changed from using an unordered_map to an
  unordered_set to store these QueryMapResults. Now, the
  unordered_set stores QueryMapResults but only considers the
  arguments when computing a hash or checking for equality. A related
  change here is that I marked the other fields as mutable since
  the set iterator returns a const value and we definately don't
  want to change the key from under the set.
- While adjusting QUERY_BEGIN in this manner, I removed the
  pattern of queries writing
  if (QUERY_USE_SAVED()) { return QUERY_GET_SAVED();
  since while it made the operation clearer it
  was hard to remember. Now we write
  QUERY_BEGIN(...); ... code ...; return QUERY_END(result)
  and the QUERY_BEGIN macro takes care
  of the check and early return.
- Because the change from unordered_map to unordered_set
  described above required the code to initialize a QueryMapResult
  with just the key information, now it is required that result types
  be default construct-able. I made use of this property to also
  simplify some of the query framework code. Before, the Context had a
  stack of information that would be stored in the QueryMapResult once
  it is constructed. Now, the QueryMapResult is constructed right away
  when starting the query and the details are filled in as needed.
- Because UniqueStrings are backed by a map apart from the query
  system but they are still garbage collected, I needed some way to
  know which UniqueStrings are used in the results of the queries that
  ran. In the event that the result is freshly computed (whether or
  not it changed), there is not a problem here since the construction
  of these UniqueStrings will mark the shared string as being used in
  this revision (so it won't be garbage collected). The problem comes
  up when a result is re-used, say if the dependencies have all been
  rerun but none of them changed. In that event, we need to be able to
  mark the UniqueStrings stored in the result so they are not garbage
  collected. This mainly comes up today in the parseFile query where
  AST nodes are storing UniqueStrings. To that end, I added a
  struct mark<Type> template that is similar to update but is used to mark
  the unique strings when the query result is reused. Unlike update
  this does not need to be implemented for all types.
- This PR changes the approach in ASTBase::updateAST /
  updateASTList. Before this PR, an AST node containing other AST
  nodes would not get a new address and so would not be considered
  "changed" for queries accepting the node pointer as input. (For
  example, if we had a Block { a; } and then we change it to
  { a; b; }, the Block* would remain the same). This behavior caused
  problems for queries like the resolveModule query which use an AST
  pointer as a key for the query. In particular, even though the
  contents of the module changed, the resolveModule would not be
  rerun, since the module pointer did not change. Instead, with this
  PR, an AST node pointer is reused only if it is an exact match
  (including all child AST nodes). If there is any difference at all
  it is not reused. However, in the case that it is not an exact
  match, we can still reuse some of the child nodes even while making
  the containing node different. For example, imagine a Module
  containing two different Functions. If something inside of the first
  Function changes, the Module and that Function will get new AST
  nodes (and new addresses). But the second Function can be reused
  because it is still in the same place in the tree (indicated by its
  ID) and it still has the same contents. The result of all of this is
  that queries can use the intuitive property that a Module*
  argument will cause that query to be rerun if anything contained in
  that module changes. This property applies more generally to other
  AST nodes. I expect this to be useful as we are expecting to add
  quite a few queries that work on a Function at a time.

Reviewed by @e-kayrakli and @dlongnecke-cray - thanks!

Testing:

make test-libchplcomp works on a Mac OS X system, an Ubuntu 20.04 system, and a SLES 12 system

Modified Files:
A compiler/next/include/chpl/config/config.h.cmake
A compiler/next/include/chpl/frontend/Parser.h
A compiler/next/include/chpl/frontend/frontend-queries.h
A compiler/next/include/chpl/queries/Context-detail.h
A compiler/next/include/chpl/queries/Context.h
A compiler/next/include/chpl/queries/ErrorMessage.h
A compiler/next/include/chpl/queries/ID.h
A compiler/next/include/chpl/queries/Location.h
A compiler/next/include/chpl/queries/UniqueString-detail.h
A compiler/next/include/chpl/queries/UniqueString.h
A compiler/next/include/chpl/queries/query-impl.h
A compiler/next/include/chpl/uast/ASTBase.h
A compiler/next/include/chpl/uast/ASTClassesList.h
A compiler/next/include/chpl/uast/ASTList.h
A compiler/next/include/chpl/uast/ASTTag.h
A compiler/next/include/chpl/uast/ASTTypes.h
A compiler/next/include/chpl/uast/Block.h
A compiler/next/include/chpl/uast/Builder.h
A compiler/next/include/chpl/uast/Call.h
A compiler/next/include/chpl/uast/Comment.h
A compiler/next/include/chpl/uast/Decl.h
A compiler/next/include/chpl/uast/ErroneousExp.h
A compiler/next/include/chpl/uast/Exp.h
A compiler/next/include/chpl/uast/FnCall.h
A compiler/next/include/chpl/uast/Identifier.h
A compiler/next/include/chpl/uast/Literal.h
A compiler/next/include/chpl/uast/Module.h
A compiler/next/include/chpl/uast/ModuleDecl.h
A compiler/next/include/chpl/uast/OpCall.h
A compiler/next/include/chpl/uast/PrimCall.h
A compiler/next/include/chpl/uast/Sym.h
A compiler/next/include/chpl/uast/Variable.h
A compiler/next/include/chpl/uast/VariableDecl.h
A compiler/next/include/chpl/uast/Visitor.h
A compiler/next/include/chpl/util/memory.h
A compiler/next/lib/frontend/CMakeLists.txt
A compiler/next/lib/frontend/Parser.cpp
A compiler/next/lib/frontend/Parser/CMakeLists.txt
A compiler/next/lib/frontend/Parser/ParserContext.h
A compiler/next/lib/frontend/Parser/ParserContextImpl.h
A compiler/next/lib/frontend/Parser/README
A compiler/next/lib/frontend/Parser/chapel.lex
A compiler/next/lib/frontend/Parser/chapel.ypp
A compiler/next/lib/frontend/Parser/lexer-help.h
A compiler/next/lib/frontend/Parser/parser-dependencies.h
A compiler/next/lib/frontend/Parser/parser-help.h
A compiler/next/lib/frontend/frontend-queries.cpp
A compiler/next/lib/queries/CMakeLists.txt
A compiler/next/lib/queries/Context.cpp
A compiler/next/lib/queries/ErrorMessage.cpp
A compiler/next/lib/queries/ID.cpp
A compiler/next/lib/queries/UniqueString.cpp
A compiler/next/lib/queries/my_aligned_alloc.c
A compiler/next/lib/queries/my_aligned_alloc.h
A compiler/next/lib/uast/ASTBase.cpp
A compiler/next/lib/uast/ASTList.cpp
A compiler/next/lib/uast/ASTTag.cpp
A compiler/next/lib/uast/Block.cpp
A compiler/next/lib/uast/Builder.cpp
A compiler/next/lib/uast/CMakeLists.txt
A compiler/next/lib/uast/Comment.cpp
A compiler/next/lib/uast/Decl.cpp
A compiler/next/lib/uast/ErroneousExp.cpp
A compiler/next/lib/uast/Exp.cpp
A compiler/next/lib/uast/Identifier.cpp
A compiler/next/lib/uast/Module.cpp
A compiler/next/lib/uast/ModuleDecl.cpp
A compiler/next/lib/uast/Sym.cpp
A compiler/next/lib/uast/Variable.cpp
A compiler/next/lib/uast/VariableDecl.cpp
A compiler/next/lib/uast/Visitor.cpp
A compiler/next/lib/util/CMakeLists.txt
A compiler/next/lib/util/bswap.h
A compiler/next/lib/util/files.cpp
A compiler/next/lib/util/files.h
A compiler/next/lib/util/mystrerror.cpp
A compiler/next/lib/util/mystrerror.h
A compiler/next/lib/util/sys_basic.h
A compiler/next/test/frontend/CMakeLists.txt
A compiler/next/test/frontend/testFrontendQueries.cpp
A compiler/next/test/frontend/testInteractive.cpp
A compiler/next/test/frontend/testParse.cpp
A compiler/next/test/frontend/testResolve.cpp
A compiler/next/test/queries/CMakeLists.txt
A compiler/next/test/queries/testDependencies.cpp
A compiler/next/test/queries/testRecursionFails.cpp
A compiler/next/test/uast/CMakeLists.txt
A compiler/next/test/uast/testBuildIDs.cpp
A compiler/next/test/uast/testUniqueString.cpp
R compiler/next/include/chpl/AST/ASTClassesList.h
R compiler/next/include/chpl/AST/ASTTag.h
R compiler/next/include/chpl/AST/ASTTypes.h
R compiler/next/include/chpl/AST/BaseAST.h
R compiler/next/include/chpl/AST/BlockStmt.h
R compiler/next/include/chpl/AST/Builder.h
R compiler/next/include/chpl/AST/CallExpr.h
R compiler/next/include/chpl/AST/Comment.h
R compiler/next/include/chpl/AST/Decl.h
R compiler/next/include/chpl/AST/ErroneousExpr.h
R compiler/next/include/chpl/AST/ErrorMessage.h
R compiler/next/include/chpl/AST/Expr.h
R compiler/next/include/chpl/AST/FnCallExpr.h
R compiler/next/include/chpl/AST/ID.h
R compiler/next/include/chpl/AST/Identifier.h
R compiler/next/include/chpl/AST/Literal.h
R compiler/next/include/chpl/AST/Location.h
R compiler/next/include/chpl/AST/Module.h
R compiler/next/include/chpl/AST/ModuleDecl.h
R compiler/next/include/chpl/AST/OpCallExpr.h
R compiler/next/include/chpl/AST/PrimCallExpr.h
R compiler/next/include/chpl/AST/README
R compiler/next/include/chpl/AST/Stmt.h
R compiler/next/include/chpl/AST/Symbol.h
R compiler/next/include/chpl/AST/UniqueString.h
R compiler/next/include/chpl/AST/UniqueStringDetail.h
R compiler/next/include/chpl/AST/Variable.h
R compiler/next/include/chpl/AST/VariableDecl.h
R compiler/next/include/chpl/Config/config.h.cmake
R compiler/next/include/chpl/Frontend/FrontendQueries.h
R compiler/next/include/chpl/Frontend/Parser.h
R compiler/next/include/chpl/Queries/Context.h
R compiler/next/include/chpl/Queries/ContextDetail.h
R compiler/next/include/chpl/Queries/QueryImpl.h
R compiler/next/include/chpl/Util/memory.h
R compiler/next/lib/AST/ASTTag.cpp
R compiler/next/lib/AST/ASTTypes.cpp
R compiler/next/lib/AST/BaseAST.cpp
R compiler/next/lib/AST/BlockStmt.cpp
R compiler/next/lib/AST/Builder.cpp
R compiler/next/lib/AST/CMakeLists.txt
R compiler/next/lib/AST/Comment.cpp
R compiler/next/lib/AST/Decl.cpp
R compiler/next/lib/AST/ErroneousExpr.cpp
R compiler/next/lib/AST/ErrorMessage.cpp
R compiler/next/lib/AST/Expr.cpp
R compiler/next/lib/AST/ID.cpp
R compiler/next/lib/AST/Identifier.cpp
R compiler/next/lib/AST/Module.cpp
R compiler/next/lib/AST/ModuleDecl.cpp
R compiler/next/lib/AST/Stmt.cpp
R compiler/next/lib/AST/Symbol.cpp
R compiler/next/lib/AST/UniqueString.cpp
R compiler/next/lib/AST/Variable.cpp
R compiler/next/lib/AST/VariableDecl.cpp
R compiler/next/lib/Frontend/CMakeLists.txt
R compiler/next/lib/Frontend/FrontendQueries.cpp
R compiler/next/lib/Frontend/Parser.cpp
R compiler/next/lib/Frontend/Parser/CMakeLists.txt
R compiler/next/lib/Frontend/Parser/ParserContext.h
R compiler/next/lib/Frontend/Parser/ParserContextImpl.h
R compiler/next/lib/Frontend/Parser/ParserDependencies.h
R compiler/next/lib/Frontend/Parser/README
R compiler/next/lib/Frontend/Parser/chapel.lex
R compiler/next/lib/Frontend/Parser/chapel.ypp
R compiler/next/lib/Frontend/Parser/lexer-help.h
R compiler/next/lib/Frontend/Parser/parser-help.h
R compiler/next/lib/Queries/CMakeLists.txt
R compiler/next/lib/Queries/Context.cpp
R compiler/next/lib/Util/CMakeLists.txt
R compiler/next/lib/Util/bswap.h
R compiler/next/lib/Util/files.cpp
R compiler/next/lib/Util/files.h
R compiler/next/lib/Util/mystrerror.cpp
R compiler/next/lib/Util/mystrerror.h
R compiler/next/lib/Util/sys_basic.h
R compiler/next/test/AST/CMakeLists.txt
R compiler/next/test/AST/testBuildIDs.cpp
R compiler/next/test/AST/testUniqueString.cpp
R compiler/next/test/Frontend/CMakeLists.txt
R compiler/next/test/Frontend/testFrontendQueries.cpp
R compiler/next/test/Frontend/testInteractive.cpp
R compiler/next/test/Frontend/testParse.cpp
M compiler/next/CMakeLists.txt
M compiler/next/Makefile.help
M compiler/next/lib/CMakeLists.txt
M compiler/next/test/CMakeLists.txt
M doc/util/nitpick_ignore

Compare: Comparing df492363e3f4...efad74ad6388 · chapel-lang/chapel · GitHub