Mutable AST -- Advice Needed --

Hello,

The WebCL Working Group (WG) is requesting input from experienced Clang/LLVM
developers and contributors concerning AST mutation.

A little background,

WebCL exposes parallel processing to the web. Specifically, WebCL allows web
applications to utilize GPU\s and multi-core CPU\s directly from the
web-browser. This is about the least verbose description I could produce,
more information can be found through the following link
<http://www.khronos.org/webcl/> .
http://www.khronos.org/webcl/

There is a tight relationship between WebCL and OpenCL because WebCL employs
/orchestrated/ OpenCL-kernels to enable parallel processing on parallel
devices. The /orchestrated/ kernels provide a level of security/projection
that is not inherent/needed in OpenCL.

Typically, a web-developer produces a kernel and WebCL uses a Validator to
/orchestrate/ the kernel. The validator performs various checks such as
memory initialization, validity of pointers, static/dynamic analysis, etc
and outputs the new kernel that is web-safe.

One of the proposed directions of development is based on Clang, and going
against the grain, with a mutable AST. We understand the AST in Clang is
fundamentally treated as immutable and we respect this design choice. The
goal of the WebCL Validator does not rely on a later stage coupling with
LLVM or later stages of compilation where the modified AST could become
unstable/problematic.

Given the above information, could those with experience and expertise
please provide feedback on the proposed implementation? We are curious the
pitfalls of modifying the AST. Eventually, if the code is stable and meets
the requirements of Clang we would like to upstream/contribute the code, but
this would be in the distant future.

There is a bug open concerning the WebCL Validator development effort that
can be accessed through the following link
<https://www.khronos.org/bugzilla/show_bug.cgi?id=875> ,
https://www.khronos.org/bugzilla/show_bug.cgi?id=875

Thank you on behalf of the WebCL WG for considering our request,

Kindest Regards,

Hello,

The WebCL Working Group (WG) is requesting input from experienced
Clang/LLVM
developers and contributors concerning AST mutation.

A little background,

WebCL exposes parallel processing to the web. Specifically, WebCL allows
web
applications to utilize GPU\s and multi-core CPU\s directly from the
web-browser. This is about the least verbose description I could produce,
more information can be found through the following link
<http://www.khronos.org/webcl/> .
http://www.khronos.org/webcl/

There is a tight relationship between WebCL and OpenCL because WebCL
employs
/orchestrated/ OpenCL-kernels to enable parallel processing on parallel
devices. The /orchestrated/ kernels provide a level of security/projection
that is not inherent/needed in OpenCL.

Typically, a web-developer produces a kernel and WebCL uses a Validator to
/orchestrate/ the kernel. The validator performs various checks such as
memory initialization, validity of pointers, static/dynamic analysis, etc
and outputs the new kernel that is web-safe.

If I'm understanding you correctly you're proposing some kind of
source-to-source translation, yes?

If so, have you considered/examined the Tooling infrastructure and AST
matchers? These have been used to rewrite C++ code in various ways, but
without AST mutation. The general desire is to find the relevant source you
want to modify & then rewrite it, rather than attempting to mutate the AST
in memory & then generate new source from the AST itself.

It’s unclear to me from the above description what you actually want to do with Clang.

Are you actually trying to perform source-to-source translation or validation or something else?
If it’s source-to-source translation, is the output intended to be human-maintainable or only as the input to other tools?
If it’s a validator, why do you want a mutable AST?

Clang parses and constructs an AST quickly & effectively... likewise provides
wonderful tools for traversing the AST with ease. Utilizing these tools
provides a lot of the functionality required in the WebCL validator

Matchers provide a nice way to quickly navigate to nodes of interest, but
the modifications and consistency of the AST is not achievable through
matchers.

Furthermore, if one wants to do some analysis on the modified source it
seems to be the only way to achieve this is to modify the AST.

The readable output is not required,

There are more details on the proposed implementation in the WebCL Public
bug on the Validator development effort.

Thank you for your input,

Clang parses and constructs an AST quickly & effectively… likewise provides
wonderful tools for traversing the AST with ease. Utilizing these tools
provides a lot of the functionality required in the WebCL validator

Matchers provide a nice way to quickly navigate to nodes of interest, but
the modifications and consistency of the AST is not achievable through
matchers.

Consistency of the AST is significantly harder to achieve through direct AST manipulation than through source rewriting. There are various forms of implicitly-added AST nodes that you would need to create, and you would need to ensure that your nodes have appropriate type, value kind, and so on. None of this is necessary if you use the rewrite interface.

Furthermore, if one wants to do some analysis on the modified source it
seems to be the only way to achieve this is to modify the AST.

You could perform the modifications, re-parse the output, and then analyze it.

The readable output is not required,

This opens up some other avenues; for instance, you could implement your transformation as a set of LLVM IR passes, and add an OpenCL backend to generate code from the IR.

Hi,

One of the proposed directions of development is based on Clang, and going
against the grain, with a mutable AST. We understand the AST in Clang is
fundamentally treated as immutable and we respect this design choice. The
goal of the WebCL Validator does not rely on a later stage coupling with
LLVM or later stages of compilation where the modified AST could become
unstable/problematic.

This is something we're interested in and we are currently exploring this path.

Given the above information, could those with experience and expertise
please provide feedback on the proposed implementation? We are curious the
pitfalls of modifying the AST. Eventually, if the code is stable and meets
the requirements of Clang we would like to upstream/contribute the code, but
this would be in the distant future.

I'll certainly look at it. You may also want to have a look at this work: http://llvm.org/devmtg/2013-04/#talk9

Best,

Mehdi

In terms of rewriter and re-parse... given the real-time nature we would like
to prevent reparsing as multiple re-parses would be required because many
changes may occur.

Last, we are trying to steer clear of LLVM, given it would be a heavy weight
in terms of download size.

One of the secondary goals will be to trim down what we are using on the
Clang side in order to keep the utilities size reasonable.

This kind of transformation may be tractable for the subset of C-like
language constructs that OpenCL/WebCL needs (i.e., not needing to deal with
the full generality of C++).

-- Sean Silva

Thank you all for the valuable feedback,

Your help is greatly appreciated,