Tree transformation in clang

Hello all,

I have seen tree transformation in clang(TreeTransform.h). This is to transform one AST to another AST. But it is not clear for me how they used this header file for the transformation. I didn’t see the function for the transformation. Just they used this header file for semantic template instantiation and template deduction. Even there is no explicit command line option for the transformation. Do you guys think that the transformation is well implemented and documented? please let me know if you have any idea about the transformation that they used in clang. Thanks in advance!

I have seen tree transformation in clang(TreeTransform.h). This is to transform one AST to another AST.

Not quite. It provides a basis for building such a transformation, not an actual transformation.

But it is not clear for me how they used this header file for the transformation. I didn’t see the function for the transformation. Just they used this header file for semantic template instantiation and template deduction.

I’m not sure who “they” is, but the only real user I know of for this header is the template instantiation logic. It does instantiation through a very specific tree transformation implemented using the facilities of TreeTransform.h.

Even there is no explicit command line option for the transformation. Do you guys think that the transformation is well implemented and documented?

No, as I said, there is no single transformation. You are looking at a small, internal library used deep in Clang’s implementation. What problem are you actually trying to solve? I suspect the solution will not involve this header file, but I can know (and it is unlikely anyone on this list can help you) if you don’t say what it is you’re trying to do…

Chandler Carruth <chandlerc@...> writes:

I have seen tree transformation in
clang(TreeTransform.h). This is to transform one AST to another AST.

Not quite. It provides a basis for building such a transformation, not an

actual transformation.

But
it is not clear for me how they used this header file for the
transformation. I didn't see the function for the transformation. Just
they used this header file for semantic template instantiation and
template deduction.

I'm not sure who "they" is, but the only real user I know of for this header

is the template instantiation logic. It does instantiation through a very
specific tree transformation implemented using the facilities of TreeTransform.h.

Even there is no explicit command line option for the transformation. Do you

guys think that the transformation is well implemented and documented?

No, as I said, there is no single transformation. You are looking at a small,

internal library used deep in Clang's implementation. What problem are you
actually trying to solve? I suspect the solution will not involve this header
file, but I can know (and it is unlikely anyone on this list can help you) if
you don't say what it is you're trying to do...

First, thanks a lot for the reply. What I am trying to do is transforming one
AST to another AST, later implementing optimizations at AST level. To do this, I
want to know the existing AST transformation in clang. I thought that there is
tree to tree transformation in general, not single transformation. I need just a
pointer about the existing transformation, if any. Thanks again.

Hi,
TreeTransform is the facility used to rebuild the templated nodes of the AST once
clang has the full type/value information (for example at instantiation time). It replaces
the nodes that are marked as of dependent type with their actual instantiation type and
performs the semantic checks with the new types.

Maybe if you clarify a little bit more (and perhaps give examples) I can be more helpful.
In general TreeTransform is not meant to implement every possible tree-to-tree transformation.

Nevertheless, it can be used as model how to build your own one. Right now I am not aware of
an interface that implements arbitrary tree-to-tree transformation.
However, there are couple of interfaces that you might find useful for that. You might want to
have a look at clang::ASTConsumer, clang::SemaConsumer and clang::RecursiveASTVisitor

Depending on what is the exact idea of the transformation you could also use clang’s
rewrite subsystem, which is pretty powerful, but it AFAIK it doesn’t work on AST level. It is more
source-to-source transformation.

Vassil

Hello Vasil,

Thanks for your detail explanation. The main thing what I want to do is AST level optimization. But before implementing optimizations, I need to transform the resulting AST which is build by clang after parsing the given source code. That mean i want to transform this AST to another AST. Later it will be easy to implement optimizations on the new AST. When i read clang source files, I got TreeTransformation.h file. I thought that there is tree to tree transformation that is already implemented inside clang. But I couldn’t get the implementation. Now am getting information from you guys that this file is just a facility or base for implementation other transformations. So, this is good information that I got from you guys. Now am going to do the transformation by my self and implementing optimizations later on. If there was implemented tree to tree transformation, i don’t need to go implement tree transformation.

Hope you got my idea. It is just my ideal design and didn’t go further. I will start the tasks soon. Do you have any idea or suggestion how to go? Thanks again.

Hi,
TreeTransform is part of the “curiously recurring template pattern” used all around in clang.
You could define your own transformation that uses that pattern. It is very efficient because it
allows to have sort-of inheritance without having vtables.
Example code you can find in:
/lib/Sema/SemaTemplateInstantiate.cpp
/lib/Sema/SemaTemplateDeduction.cpp
/lib/Sema/SemaTemplate.cpp
However, TreeTransform is not public interface…

There were a lot of changes in it recently and maybe my experience is old-dated but
I tried to use it once and I had hard time when I wanted to replace one node with 2 or more
nodes or when I tried to remove nodes. For 1:1 transformation I think is very good interface, though.

Talking about optimizations: Have you consider the LLVM bitcode - it is SSA based and IMHO
is much more suitable for optimizations?

Vassil

Hi Vassil,

Sorry I was out for dinner. Its so great explanation and it is much helpful. Thanks a lot.

For optimization, I know it is easier to do it at LLVM bitcode level. But my intention is to do it at AST level. Most optimization passes are already implemented at LLVM level. Later, I will implement optimizations at llvm level. Thanks again.