Mutable AST -- Advice Needed --

classic Classic list List threaded Threaded
9 messages Options
Reply | Threaded
Open this post in threaded view
|

Mutable AST -- Advice Needed --

steveneliuk
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/

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

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

Kindest Regards,
Reply | Threaded
Open this post in threaded view
|

Re: Mutable AST -- Advice Needed --

David Blaikie



On Tue, May 28, 2013 at 10:57 AM, steveneliuk <[hidden email]> wrote:
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.
 
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,



--
View this message in context: http://clang-developers.42468.n3.nabble.com/Mutable-AST-Advice-Needed-tp4032339.html
Sent from the Clang Developers mailing list archive at Nabble.com.
_______________________________________________
cfe-dev mailing list
[hidden email]
http://lists.cs.uiuc.edu/mailman/listinfo/cfe-dev


_______________________________________________
cfe-dev mailing list
[hidden email]
http://lists.cs.uiuc.edu/mailman/listinfo/cfe-dev
Reply | Threaded
Open this post in threaded view
|

Re: Mutable AST -- Advice Needed --

Richard Smith
In reply to this post by steveneliuk
On Tue, May 28, 2013 at 10:57 AM, steveneliuk <[hidden email]> wrote:
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,

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?

_______________________________________________
cfe-dev mailing list
[hidden email]
http://lists.cs.uiuc.edu/mailman/listinfo/cfe-dev
Reply | Threaded
Open this post in threaded view
|

Re: Mutable AST -- Advice Needed --

steveneliuk
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,
Reply | Threaded
Open this post in threaded view
|

Re: Mutable AST -- Advice Needed --

Richard Smith
On Tue, May 28, 2013 at 11:31 AM, steveneliuk <[hidden email]> wrote:
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.

_______________________________________________
cfe-dev mailing list
[hidden email]
http://lists.cs.uiuc.edu/mailman/listinfo/cfe-dev
Reply | Threaded
Open this post in threaded view
|

Re: Mutable AST -- Advice Needed --

Mehdi AMINI-2
In reply to this post by steveneliuk
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
_______________________________________________
cfe-dev mailing list
[hidden email]
http://lists.cs.uiuc.edu/mailman/listinfo/cfe-dev
Reply | Threaded
Open this post in threaded view
|

Re: Mutable AST -- Advice Needed --

steveneliuk
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.
Reply | Threaded
Open this post in threaded view
|

Re: Mutable AST -- Advice Needed --

Sean Silva-2
In reply to this post by Richard Smith



On Tue, May 28, 2013 at 11:42 AM, Richard Smith <[hidden email]> wrote:
On Tue, May 28, 2013 at 11:31 AM, steveneliuk <[hidden email]> wrote:
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.


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 

_______________________________________________
cfe-dev mailing list
[hidden email]
http://lists.cs.uiuc.edu/mailman/listinfo/cfe-dev
Reply | Threaded
Open this post in threaded view
|

Re: Mutable AST -- Advice Needed --

steveneliuk
Thank you all for the valuable feedback,

Your help is greatly appreciated,