Frame escapes and inline failed, reason recursion

[Chris Seaton]

Hi Stefan,

I too tried to implement a parser for and using Truffle at the end of last year. I did a packrat parser of a PEG, using the Katahdin algorithm (http://chrisseaton.com/katahdin) for composability of different language grammars.

I also had the vague idea that you could annotate parsing rules in your Truffle nodes. So nodes would have both an execute method, and a parse annotation. Some node would be marked as the global root and the parser would match from there.

I didn’t get far enough to measure any performance, and the Katahdin algorithm is really far too slow anyway. You might get a better result using your more conventional parsing algorithm.

Good luck!

Chris

On 22 Jul 2014, at 10:13, Stefan Fehrenbach <stefan.fehrenbach at gmail.com> wrote:

> Hi!
> 
> On 21 July 2014 13:36, Stefan Marr <java at stefan-marr.de> wrote:
>> Hi Stefan:
>> 
>> On 21 Jul 2014, at 13:19, Stefan Fehrenbach <stefan.fehrenbach at gmail.com> wrote:
>> 
>>> My question is about this message "inline failed", where it says
>>> "reason recursion". Is that a problem?
>> 
>> In my experience, that becomes only relevant after you fixed the escaping frames.
>> 
> Okay.
> 
>> This sounds strange to me. Are you using Truffle to implement a fast parser?
> Yes, indeed. A parser is basically an ahead-of-time compiled grammar.
> My code implements a grammar interpreter using Truffle for JIT
> compilation :)
> Preliminary results of my experiments with a very primitive recursive
> descent recognizer are promising.
> 
>> Or are you implementing the interpretation of the parser’s result.
>> The usual thing is the later.
>> Another thing is that I haven’t seen a trampoline-based interpreter based on Truffle yet.
>> Instead, as far as I know, they are all fully recursive and rely on Graal to make that work efficiently.
>> 
> Well, the parsing algorithm (GLL) dictates the need for a trampoline.
> It seems to work out so far. I guess I do a lot of indirect calls
> instead of partial evaluated Truffle magic, which will be slow, but I
> hope it will not be much slower than the existing non-Truffle code.
> 
>> 
>>> It just occurs to me, that my last frame escapes problem went away
>>> with an @ExplodeLoop annotation. Is the problem the loop in
>>> ParsingState.push [3]?
>>> How do I fix it? You use @ExplodeLoop to loop over children, right?
>>> The "results" are not part of the AST and they might not even be
>>> compilation final…
>> 
>> Every time I saw a new escaping frame issue it was because I introduced a loop that was not unrolled.
>> So, my guess would be that you got your root cause right there.
>> 
>> It is important that the loop bounds are going to be fixed at run time, so, I don’t know whether that is going to be the case here with your `results` set.
>> It also looks like you are not strictly implementing your interpretation as part of the AST.
>> 
>> Such loops should be in execute*() methods of Truffle nodes, and depend (in terms of number of iterations) solely on child nodes and known constant values, so that the loop unrolling triggered by @ExplodeLoop can do its magic.
>> 
> 
> So, I "fixed" the problem by removing the VirtualFrame parameter from
> a couple of methods.
> I guess you can only have execute* methods on AST nodes, but some of
> my receivers were not.
> I suspect if I want to have Truffle magic along these paths, I'll need
> to do some clever grammar analysis and rewrite to specialized nodes
> based on the results. Might be possible, I don't know yet.
> 
> Anyways, thanks for the help :)
> 
> Stefan