[cfe-dev] Recursion in Clang FE

[Yaron Keren]

There's similar limit for template recursion depth.


2015-05-26 18:43 GMT+03:00 mats petersson <mats at planetcatfish.com>:

> It is (typically) complicated to simply replace recursion in compilers
> with non-recursive variants, as that means extra code to store and restore
> the state, which is further complicated by the fact that there are so many
> different calls that can follow any particular call - in other words, the
> possible things that may follow a particular point in the code are many.
> It's relatively easy to remove recursion in a "search the best path in a
> maze" or "find the right number to solve the Sudoku puzzle with" because,
> essentially, the same steps for each recursion level, except for "which of
> the possible paths" or "which of the possible numbers". In a compiler, you
> can have MANY different paths from each particular location, and the
> information you need to save is quite different when you are in the middle
> of a struct compared to in the middle of a switch statement - but someone
> can declared a struct inside a switch that is inside a class declaration,
> and you can have a class declaration inside a struct. So using the
> call-stack makes life a lot easier to figure out "now what do we do" when
> you get back from the little excursion of parsing a particular construct
> [e.g. the struct inside the case of a switch].
>
> However, it is probably sane to check the nesting level of calls in some
> way, and aborting the parsing if the nesting level is too high. Having one
> million levels of pointer indirection is quite unlikely to be a sensible
> program of any sort, so it's perfectly OK to say "Sorry , I can't compile
> this".
>
> I'm not sure how or where this should be applied, but C++ does allow this
> to be "almost automatic" by using a static member variable that is counted
> up on entry and down on leaving a function, and adding a test that confirms
> that "we can cope with X recursive calls, which should be enough for any
> sane implementation]
>
> --
> Mats
>
> On 26 May 2015 at 16:15, Sotkin, Alexey <alexey.sotkin at intel.com> wrote:
>
>>  Hello
>>
>>
>>
>> I build Clang FE as a shared library and link with other application.
>> That application should never crash with any sources given for compilation.
>>
>> I have a test based on this one
>> https://github.com/gcc-mirror/gcc/blob/master/gcc/testsuite/gcc.c-torture/compile/limits-pointer.c
>> <https://urldefense.proofpoint.com/v2/url?u=https-3A__github.com_gcc-2Dmirror_gcc_blob_master_gcc_testsuite_gcc.c-2Dtorture_compile_limits-2Dpointer.c&d=AwMFAg&c=8hUWFZcy2Z-Za5rBPlktOQ&r=CnzuN65ENJ1H9py9XLiRvC_UQz6u3oG6GUNn7_wosSM&m=hpvxMFBlQzY8zVAcA881WxdpWZy7JXsrFyztP55mXiE&s=LaLg0LQsuWIrH2wvu5UopsNZJsw4So5PLMOaUiVmdKY&e=>
>> . But PTR4 is changed to PTR5 at the last line. I run the test with the
>> following command line:
>>
>>
>>
>> clang.exe -c C:\work\tmp\limits-pointer.c
>>
>>
>>
>> Then clang crashed with stack overflow exception caused by very deep
>> recursion during preprocessing. And that is not the only one case.
>>
>> I have noticed that there are many recursive calls in Clang’s source
>> code. And depth of recursion in many cases depends on the source code which
>> is being compiled.
>>
>>
>>
>> Is it possible to eliminate all such recursions in Clang?
>>
>> If not, how can I workaround (if it is possible) stack overflow ?
>>
>>
>>
>>
>>
>> *Best regards.*
>>
>> *Alexey Sotkin.*
>>
>>
>>
>>
>> --------------------------------------------------------------------
>> Closed Joint Stock Company Intel A/O
>> Registered legal address: Krylatsky Hills Business Park,
>> 17 Krylatskaya Str., Bldg 4, Moscow 121614,
>> Russian Federation
>>
>> This e-mail and any attachments may contain confidential material for
>> the sole use of the intended recipient(s). Any review or distribution
>> by others is strictly prohibited. If you are not the intended
>> recipient, please contact the sender and delete all copies.
>>
>> _______________________________________________
>> 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/20150526/1ecad0a5/attachment.html>