| Message ID | 20131118103733.GJ21297@msticlxl57.ims.intel.com |
|---|---|
| State | New |
| Headers | show |
On 11/18/13 03:37, Ilya Enkovich wrote: > Hi, > > Here is a patch to disable tail recursion transformation when bounds are passed by call. The reason is BUILT_IN_CHKP_ARG_BND which should always get default SSA_NAME of PARM_DECL as an argument. > > Thanks, > Ilya > -- > 2013-11-15 Ilya Enkovich <ilya.enkovich@intel.com> > > * tree-tailcall.c: Include tree-chkp.h. > (suitable_for_tail_opt_p): Disable tail > recursion for instrumented functions with bounded args. This sounds wrong. If the builtins are called with a PARAM_DECL rather than an SSA_NAME, can't they make worst case assumptions about the bounds? In general if we find ourselves disabling an optimizer to make the bounds checker happy, we've got some explaining to do. jeff
2013/11/18 Jeff Law <law@redhat.com>: > On 11/18/13 03:37, Ilya Enkovich wrote: >> >> Hi, >> >> Here is a patch to disable tail recursion transformation when bounds are >> passed by call. The reason is BUILT_IN_CHKP_ARG_BND which should always get >> default SSA_NAME of PARM_DECL as an argument. >> >> Thanks, >> Ilya >> -- >> 2013-11-15 Ilya Enkovich <ilya.enkovich@intel.com> >> >> * tree-tailcall.c: Include tree-chkp.h. >> (suitable_for_tail_opt_p): Disable tail >> recursion for instrumented functions with bounded args. > > This sounds wrong. If the builtins are called with a PARAM_DECL rather than > an SSA_NAME, can't they make worst case assumptions about the bounds? > > In general if we find ourselves disabling an optimizer to make the bounds > checker happy, we've got some explaining to do. In SSA we are not allowed to have PARAM_DECL as call arg. 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 PHI node then is used in BUILT_IN_CHKP_ARG_BND, but is should not. Optimizer has to be taught to analizy bind_bounds of replaced call and generate PHI nodes for bounds. 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. Ilya > > jeff >
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. 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. Jeff
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
On 11/18/13 12:16, Ilya Enkovich wrote: > 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 I wouldn't say it's wrong. It's conservatively correct if properly implemented. Why precisely do you consider this wrong? If your code can't handle it, it really should be fixed. Jeff
2013/11/19 Jeff Law <law@redhat.com>: > On 11/18/13 12:16, Ilya Enkovich wrote: >> >> 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 > > I wouldn't say it's wrong. It's conservatively correct if properly > implemented. Why precisely do you consider this wrong? If your code can't > handle it, it really should be fixed. It is wrong because __builtin_arg_bounds is used to get bounds of input parameter and PHI node here is not an input parameter. Correctl handling of __builtin_arg_bounds in this 'wrong' example requires adding it a PHI node semantics based on it's arg. For me it seems more complex then generating a regular PHI node for bounds and makes GIMPLE less readable. Ilya > > Jeff > >
On 11/18/13 14:03, Ilya Enkovich wrote: > 2013/11/19 Jeff Law <law@redhat.com>: >> On 11/18/13 12:16, Ilya Enkovich wrote: >>> >>> 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 >> >> I wouldn't say it's wrong. It's conservatively correct if properly >> implemented. Why precisely do you consider this wrong? If your code can't >> handle it, it really should be fixed. > > It is wrong because __builtin_arg_bounds is used to get bounds of > input parameter and PHI node here is not an input parameter. OK, now we're getting somewhere. So we've got this odd little function which only works on parameters. I can't help but feel this is a bit of mis-design coming back to haunt us and I wonder if we're going to see other instances of this kind of problem. There's something just wrong with the semantics of __builtin_arg_bounds, but I'm having trouble putting my finger on it. Correctl > handling of __builtin_arg_bounds in this 'wrong' example requires > adding it a PHI node semantics based on it's arg. For me it seems > more complex then generating a regular PHI node for bounds and makes > GIMPLE less readable. But presumably you have code to merge bound information already, right? You need that for PHI nodes. Can't you use that to walk up the use-def chains and build the bounds information? Or if you want to fix the tailcall stuff, you can start down that direction. I don't think that'll fix the nagging concerns about the overall semantics of builtin_arg_bounds, but it might be enough for you to go forward. jeff
On Tue, Nov 19, 2013 at 8:02 PM, Jeff Law <law@redhat.com> wrote: > On 11/18/13 14:03, Ilya Enkovich wrote: >> >> 2013/11/19 Jeff Law <law@redhat.com>: >>> >>> On 11/18/13 12:16, Ilya Enkovich wrote: >>>> >>>> >>>> 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 >>> >>> >>> I wouldn't say it's wrong. It's conservatively correct if properly >>> implemented. Why precisely do you consider this wrong? If your code >>> can't >>> handle it, it really should be fixed. >> >> >> It is wrong because __builtin_arg_bounds is used to get bounds of >> input parameter and PHI node here is not an input parameter. > > OK, now we're getting somewhere. So we've got this odd little function > which only works on parameters. I can't help but feel this is a bit of > mis-design coming back to haunt us and I wonder if we're going to see other > instances of this kind of problem. Right. > There's something just wrong with the semantics of __builtin_arg_bounds, but > I'm having trouble putting my finger on it. Well, the issue is that it accepts any pointer argument as input. I originally thought it may just get an integer constant argument - the argument position. It really seems to me that we have __builtin_arg_boundsN (), but to avoid having N builtins we specify N via an argument to the function. But as it may not change we should use something that cannot change - like a constant. A constant that identifies a parameter is one that gives its position for example. Note that any restrictions you impose on what is "valid" for GIMPLE should be verified in tree-cfg.c:verify_gimple_* - in the __builtin_arg_bounds call case in verify_gimple_call. Richard. > > Correctl >> >> handling of __builtin_arg_bounds in this 'wrong' example requires >> adding it a PHI node semantics based on it's arg. For me it seems >> more complex then generating a regular PHI node for bounds and makes >> GIMPLE less readable. > > But presumably you have code to merge bound information already, right? You > need that for PHI nodes. Can't you use that to walk up the use-def chains > and build the bounds information? > > Or if you want to fix the tailcall stuff, you can start down that direction. > I don't think that'll fix the nagging concerns about the overall semantics > of builtin_arg_bounds, but it might be enough for you to go forward. > > jeff
2013/11/20 Richard Biener <richard.guenther@gmail.com>: > On Tue, Nov 19, 2013 at 8:02 PM, Jeff Law <law@redhat.com> wrote: >> On 11/18/13 14:03, Ilya Enkovich wrote: >>> >>> 2013/11/19 Jeff Law <law@redhat.com>: >>>> >>>> On 11/18/13 12:16, Ilya Enkovich wrote: >>>>> >>>>> >>>>> 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 >>>> >>>> >>>> I wouldn't say it's wrong. It's conservatively correct if properly >>>> implemented. Why precisely do you consider this wrong? If your code >>>> can't >>>> handle it, it really should be fixed. >>> >>> >>> It is wrong because __builtin_arg_bounds is used to get bounds of >>> input parameter and PHI node here is not an input parameter. >> >> OK, now we're getting somewhere. So we've got this odd little function >> which only works on parameters. I can't help but feel this is a bit of >> mis-design coming back to haunt us and I wonder if we're going to see other >> instances of this kind of problem. > > Right. > >> There's something just wrong with the semantics of __builtin_arg_bounds, but >> I'm having trouble putting my finger on it. > > Well, the issue is that it accepts any pointer argument as input. > I originally thought it may just get an integer constant argument - the > argument position. It really seems to me that we have > __builtin_arg_boundsN (), but to avoid having N builtins we specify N > via an argument to the function. But as it may not change we should > use something that cannot change - like a constant. A constant > that identifies a parameter is one that gives its position for example. I have tried to pass constant for arg_bounds. It still requires additional modification of optimization passes (including tail recursion, param propagation, inline etc.) But having constant as an argument you really cannot detect errors. E.g. if you inline and do not fix inlined arg_bounds calls correctly, you may not get ICE but get wrong program which uses wrong bounds and produces false bounds violations. > > Note that any restrictions you impose on what is "valid" for GIMPLE > should be verified in tree-cfg.c:verify_gimple_* - in the > __builtin_arg_bounds call case in verify_gimple_call. Will add it. Thanks, Ilya > > Richard. > >> >> Correctl >>> >>> handling of __builtin_arg_bounds in this 'wrong' example requires >>> adding it a PHI node semantics based on it's arg. For me it seems >>> more complex then generating a regular PHI node for bounds and makes >>> GIMPLE less readable. >> >> But presumably you have code to merge bound information already, right? You >> need that for PHI nodes. Can't you use that to walk up the use-def chains >> and build the bounds information? >> >> Or if you want to fix the tailcall stuff, you can start down that direction. >> I don't think that'll fix the nagging concerns about the overall semantics >> of builtin_arg_bounds, but it might be enough for you to go forward. >> >> jeff
On Wed, Nov 20, 2013 at 11:41 AM, Ilya Enkovich <enkovich.gnu@gmail.com> wrote: > 2013/11/20 Richard Biener <richard.guenther@gmail.com>: >> On Tue, Nov 19, 2013 at 8:02 PM, Jeff Law <law@redhat.com> wrote: >>> On 11/18/13 14:03, Ilya Enkovich wrote: >>>> >>>> 2013/11/19 Jeff Law <law@redhat.com>: >>>>> >>>>> On 11/18/13 12:16, Ilya Enkovich wrote: >>>>>> >>>>>> >>>>>> 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 >>>>> >>>>> >>>>> I wouldn't say it's wrong. It's conservatively correct if properly >>>>> implemented. Why precisely do you consider this wrong? If your code >>>>> can't >>>>> handle it, it really should be fixed. >>>> >>>> >>>> It is wrong because __builtin_arg_bounds is used to get bounds of >>>> input parameter and PHI node here is not an input parameter. >>> >>> OK, now we're getting somewhere. So we've got this odd little function >>> which only works on parameters. I can't help but feel this is a bit of >>> mis-design coming back to haunt us and I wonder if we're going to see other >>> instances of this kind of problem. >> >> Right. >> >>> There's something just wrong with the semantics of __builtin_arg_bounds, but >>> I'm having trouble putting my finger on it. >> >> Well, the issue is that it accepts any pointer argument as input. >> I originally thought it may just get an integer constant argument - the >> argument position. It really seems to me that we have >> __builtin_arg_boundsN (), but to avoid having N builtins we specify N >> via an argument to the function. But as it may not change we should >> use something that cannot change - like a constant. A constant >> that identifies a parameter is one that gives its position for example. > > I have tried to pass constant for arg_bounds. It still requires > additional modification of optimization passes (including tail > recursion, param propagation, inline etc.) But having constant as an > argument you really cannot detect errors. E.g. if you inline and do > not fix inlined arg_bounds calls correctly, you may not get ICE but > get wrong program which uses wrong bounds and produces false bounds > violations. Yeah, that's why I refrained from suggesting this earlier ;) You lose the connection between "bounds for argument X" and "function entry value for argument X". Richard. >> >> Note that any restrictions you impose on what is "valid" for GIMPLE >> should be verified in tree-cfg.c:verify_gimple_* - in the >> __builtin_arg_bounds call case in verify_gimple_call. > > Will add it. > > Thanks, > Ilya > >> >> Richard. >> >>> >>> Correctl >>>> >>>> handling of __builtin_arg_bounds in this 'wrong' example requires >>>> adding it a PHI node semantics based on it's arg. For me it seems >>>> more complex then generating a regular PHI node for bounds and makes >>>> GIMPLE less readable. >>> >>> But presumably you have code to merge bound information already, right? You >>> need that for PHI nodes. Can't you use that to walk up the use-def chains >>> and build the bounds information? >>> >>> Or if you want to fix the tailcall stuff, you can start down that direction. >>> I don't think that'll fix the nagging concerns about the overall semantics >>> of builtin_arg_bounds, but it might be enough for you to go forward. >>> >>> jeff
diff --git a/gcc/tree-tailcall.c b/gcc/tree-tailcall.c index 185bf16..59845950 100644 --- a/gcc/tree-tailcall.c +++ b/gcc/tree-tailcall.c @@ -44,6 +44,7 @@ along with GCC; see the file COPYING3. If not see #include "cfgloop.h" #include "common/common-target.h" #include "ipa-utils.h" +#include "tree-chkp.h" /* The file implements the tail recursion elimination. It is also used to analyze the tail calls in general, passing the results to the rtl level @@ -141,6 +142,20 @@ suitable_for_tail_opt_p (void) if (cfun->stdarg) return false; + /* Tail recursion elimination may cause arg_bnd builtins to be called + not for PARM_DECL which is not allowed now. Avoid optimization + in such cases for now. */ + if (chkp_function_instrumented_p (current_function_decl)) + { + tree param; + + for (param = DECL_ARGUMENTS (current_function_decl); + param; + param = DECL_CHAIN (param)) + if (BOUNDED_P (param)) + return false; + } + return true; } /* Returns false when the function is not suitable for tail call optimization