[cfe-dev] Expression Templates for AST matchers

[Manuel Klimek]

We actually went from a more expression templatey to a less expression
templatey design. Sam has worked on making clang tidy use cases faster. I
expect in the end the right thing is to do less duplicate work which I
think we will be able to do with modules.

On Tue, Apr 7, 2015, 3:31 PM Sean Silva <chisophugis at gmail.com> wrote:

> Although I'm mostly an armchair spectator right now w.r.t. clang tooling
> stuff, I think that use cases like clang-query and in general the dynamic
> AST matchers suggests that expression templates aren't a very good solution
> because they will require reimplementing things from scratch for the
> "dynamic" case.
>
> Regardless, I don't think that the primary bottleneck is not doing enough
> at compile time (of the matchers). Rather we aren't effectively indexing
> the underlying data set we are trying to query (right now, we're more like
> grep and less like google). Indexing starts paying off once you have to do
> multiple queries* and can amortize the indexing cost across all those
> queries. I think most uses for clang-tidy have enough ast matching in them
> for indexing to pay off. Note that indexing doesn't have to return results
> immediately; it just needs to prune the search space enough to pay off (a
> good example is using a trigram index to prune the search space for regexp
> matching http://swtch.com/~rsc/regexp/regexp4.html).
>
> * "multiple" here also scales numerically with the number of TU's. An
> index can avoid visiting certain TU's at all in many cases.
>
> -- Sean Silva
>
> On Tue, Apr 7, 2015 at 2:01 PM, Richard <legalize at xmission.com> wrote:
>
>> OCLint, a lint checker using clang tooling, says:
>> <http://docs.oclint.org/en/dev/internals/rules.html>
>>
>>     "Using AST matchers has more restrictions than AST visitor, and it
>>     takes much longer time in analysis, this could lower the
>>     performance of the tool. So, we always have to consider the
>>     trade-off, and choose wisely."
>>
>> It seems that AST matchers, while convenient, are not the best
>> performing option for processing source files.  I've done some simplistic
>> measurements on clang-tidy and found that the majority of the execution
>> time is spent in the matchers.  I believe this is the result of the
>> matchers building runtime structures to match nodes.
>>
>> Has anyone investigated using the technique of expression templates to
>> get the convenience of an AST matching domain-specific language (DSL)
>> with the runtime efficiency of an AST visitor?
>>
>> If we were to pursue such a direction, would it be possible to use an
>> expression template library like those in Boost for the implementation?
>> I don't see any existing use of Boost in the LLVM/clang code base, so
>> I infer that there is some avoidance of Boost for whatever reason.  I
>> haven't done any expression template coding beyond using existing
>> expression template based libraries like Boost.Spirit.  I have no idea
>> what it would take to create an expression template based AST matcher
>> DSL for clang, but it seems like it would be worthwhile as it would
>> speed up all the tools that want to use the AST matcher style
>> interface.
>>
>> Does anyone have any thoughts about this?  Pehraps Manuel Klimek?
>>
> --
>> "The Direct3D Graphics Pipeline" free book <
>> http://tinyurl.com/d3d-pipeline>
>>      The Computer Graphics Museum <http://ComputerGraphicsMuseum.org>
>>          The Terminals Wiki <http://terminals.classiccmp.org>
>>   Legalize Adulthood! (my blog) <http://LegalizeAdulthood.wordpress.com>
>>
> _______________________________________________
>> cfe-dev mailing list
>> cfe-dev at cs.uiuc.edu
>> http://lists.cs.uiuc.edu/mailman/listinfo/cfe-dev
>>
>
> _______________________________________________
> cfe-dev mailing list
> cfe-dev at cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/cfe-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/cfe-dev/attachments/20150407/d1b292e6/attachment.html>