[PATCH, MPX, 2/X] Pointers Checker [16/25] Tail recursion

[Ilya Enkovich]

2013/11/18 Jeff Law <law@redhat.com>:
> On 11/18/13 11:10, Ilya Enkovich wrote:
>>
>>
>> In SSA we are not allowed to have PARAM_DECL as call arg.
>
> Right.
>
>
>
>   The problem
>>
>> in this optimization is that when we replace a tail call with jump, we
>> replace default SSA name of input parameter with PHI node holding
>> taking original param and call's arg.
>
> ?  This would be an indication of a problem at the call site.

Consider following example with tail recursion:

test (int *param1)
{
  bounds2 = __builtin_arg_bounds (param1(D))

  _3 = __builtin_bind_bounds(param1(D), bounds2);

  _4 = some_other_call (_3);

  bounds5 = __builtin_ret_bounds(_4);

  _6 = __builtin_bind_bounds (_4, bounds5);

  test(_6);
}

With current recursion elimination we will have:

test (int *param1)
{
<bb1>:

<bb2>:
  _7 = PHI<param1(D) (bb1), _6 (bb2)>
  bounds2 = __builtin_arg_bounds (_7) -- WRONG

  _3 = __builtin_bind_bounds(_7, bounds2);

  _4 = some_other_call (_3);

  bounds5 = __builtin_ret_bounds(_4);

  _6 = __builtin_bind_bounds (_4, bounds5);

  goto <bb2>
}

What is required is:

test (int *param1)
{
<bb1>:
  bounds2 = __builtin_arg_bounds (param1(D))

<bb2>:
  _7 = PHI<param1(D) (bb1), _6 (bb2)>
  _8 = PHI<bounds2 (bb1), bounds5 (bb2)>

  _3 = __builtin_bind_bounds(_7, _8);

  _4 = some_other_call (_3);

  bounds5 = __builtin_ret_bounds(_4);

  _6 = __builtin_bind_bounds (_4, bounds5);

  goto <bb2>
}

So, optimizer has to handle _builtin_arg_bounds in a special way and
search for __builtin_bind_bounds for replaced calls to generate proper
PHI nodes for bounds.

>
> When the recursive call is transformed into a jump we should be taking
> arguments from the call site and using those as values in a PHI node at the
> target of the newly created edge
>
> See eliminate_tail_call.
>
>
>
>
>>
>> In general for not important optimizations I resolve the stability
>> issue with instrumented code and will enable optimizations later. For
>> obviously important optimizations, like inline, support is initially
>> added.
>
> To me, disabling this appears like you're got something fundamentally wrong
> with your implementation.

It would be wrong if there is no possibility to enable tail recursion
elimination without changes in instrumentation. But such possibility
exists.

Ilya
>
> Jeff