| Message ID | 20170816153455.97693-10-luc.vanoostenryck@gmail.com (mailing list archive) |
|---|---|
| State | Changes Requested, archived |
| Headers | show |
On Wed, Aug 16, 2017 at 11:34 AM, Luc Van Oostenryck <luc.vanoostenryck@gmail.com> wrote: > Here by 'simple' we really mean 'worth of putting in a register'. > > We select all scalar types as well as struct and unions with a > size not bigger than a long (register). > > Global and static variables, variables which address have been > taken and volatiles variables are never selected. > > Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com> > --- > symbol.h | 33 +++++++++++++++++++++++++++++++++ > 1 file changed, 33 insertions(+) > > diff --git a/symbol.h b/symbol.h > index 327449611..3f075c5bc 100644 > --- a/symbol.h > +++ b/symbol.h > @@ -407,6 +407,39 @@ static inline int is_scalar_type(struct symbol *type) > return 0; > } > > +static inline int is_simple_type(struct symbol *type) ... > + case SYM_STRUCT: > + case SYM_UNION: > + return type->bit_size <= long_ctype.bit_size; I think the function name should be some thing along the line of "type fits register" or is_registerable_type. union and struct are composite types. It is a bit confusing calling them simple, if some one just looking at the code without look at the commit message. Chris -- To unsubscribe from this list: send the line "unsubscribe linux-sparse" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Hi Chris, On 17 August 2017 at 08:19, Christopher Li <sparse@chrisli.org> wrote: > On Wed, Aug 16, 2017 at 11:34 AM, Luc Van Oostenryck > <luc.vanoostenryck@gmail.com> wrote: >> Here by 'simple' we really mean 'worth of putting in a register'. >> >> We select all scalar types as well as struct and unions with a >> size not bigger than a long (register). >> >> Global and static variables, variables which address have been >> taken and volatiles variables are never selected. >> >> Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com> >> --- >> symbol.h | 33 +++++++++++++++++++++++++++++++++ >> 1 file changed, 33 insertions(+) >> >> diff --git a/symbol.h b/symbol.h >> index 327449611..3f075c5bc 100644 >> --- a/symbol.h >> +++ b/symbol.h >> @@ -407,6 +407,39 @@ static inline int is_scalar_type(struct symbol *type) >> return 0; >> } >> >> +static inline int is_simple_type(struct symbol *type) > ... >> + case SYM_STRUCT: >> + case SYM_UNION: >> + return type->bit_size <= long_ctype.bit_size; > > I think the function name should be some thing along the > line of "type fits register" or is_registerable_type. > > union and struct are composite types. It is a bit > confusing calling them simple, if some one just looking > at the code without look at the commit message. > Apart from that I faced a problem with this and had to disable STRUCT/UNION from being treated as simple types. The problem was when generating LLVM output for https://github.com/dibyendumajumdar/dmr_c/blob/master/tests/eic/testcbrt.c. I will investigate more and report back my findings. Meanwhile I would be interested to see the results of a test with above. Regards Dibyendu -- To unsubscribe from this list: send the line "unsubscribe linux-sparse" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On Thu, Aug 17, 2017 at 9:19 AM, Christopher Li <sparse@chrisli.org> wrote: >> >> +static inline int is_simple_type(struct symbol *type) > ... >> + case SYM_STRUCT: >> + case SYM_UNION: >> + return type->bit_size <= long_ctype.bit_size; > > I think the function name should be some thing along the > line of "type fits register" or is_registerable_type. > > union and struct are composite types. It is a bit > confusing calling them simple, if some one just looking > at the code without look at the commit message. I agree it's confusing, and yes I would like a better name. OTOH 'registrable' is not exactly the conveyed meaning. 'register' is a concept that pertains to the backend, that is machine specific, a pseudo may need several registers and a register can hold several pseudos, ... Here what we really want to select is something along: 'it's interesting to see it as a flow of value' vs. 'it's better to see it as a change in state'. And yes, very often that just correspond to registers. Note: it's not even 'what can be put in a pseudo(-register)' were selecting here. It's OK to have pseudos for 'non-simple' values, They will just be transient and we won't be interested in their 'flow'. -- Luc -- To unsubscribe from this list: send the line "unsubscribe linux-sparse" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On Thu, Aug 17, 2017 at 6:59 PM, Dibyendu Majumdar <mobile@majumdar.org.uk> wrote: > > Apart from that I faced a problem with this and had to disable > STRUCT/UNION from being treated as simple types. That's only a problem/a limitation of your backend. -- Luc -- To unsubscribe from this list: send the line "unsubscribe linux-sparse" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Hi Luc, On 17 August 2017 at 20:17, Luc Van Oostenryck <luc.vanoostenryck@gmail.com> wrote: > On Thu, Aug 17, 2017 at 6:59 PM, Dibyendu Majumdar > <mobile@majumdar.org.uk> wrote: >> >> Apart from that I faced a problem with this and had to disable >> STRUCT/UNION from being treated as simple types. > > That's only a problem/a limitation of your backend. > Possibly - I haven't checked yet. Are you able to generate code / and run the test case using your LLVM backend? Regards Dibyendu -- To unsubscribe from this list: send the line "unsubscribe linux-sparse" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On Thu, Aug 17, 2017 at 9:21 PM, Dibyendu Majumdar <mobile@majumdar.org.uk> wrote: >>> Apart from that I faced a problem with this and had to disable >>> STRUCT/UNION from being treated as simple types. >> >> That's only a problem/a limitation of your backend. >> > > Possibly - I haven't checked yet. Are you able to generate code / and > run the test case using your LLVM backend? Possibly not but you're the only use of the LLVM backend, so it's yours ;) -- Luc -- To unsubscribe from this list: send the line "unsubscribe linux-sparse" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Hi Luc, On 17 August 2017 at 20:25, Luc Van Oostenryck <luc.vanoostenryck@gmail.com> wrote: > On Thu, Aug 17, 2017 at 9:21 PM, Dibyendu Majumdar > <mobile@majumdar.org.uk> wrote: >>>> Apart from that I faced a problem with this and had to disable >>>> STRUCT/UNION from being treated as simple types. >>> >>> That's only a problem/a limitation of your backend. >>> >> >> Possibly - I haven't checked yet. Are you able to generate code / and >> run the test case using your LLVM backend? > > Possibly not but you're the only use of the LLVM backend, so it's yours ;) > I will check at my end and revert with my thoughts. But I would have preferred if the SSA change was like for like initially - rather than introducing new breaking changes. That should ideally come as patches later on. Regards Dibyendu -- To unsubscribe from this list: send the line "unsubscribe linux-sparse" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On Thu, Aug 17, 2017 at 6:59 PM, Dibyendu Majumdar <mobile@majumdar.org.uk> wrote: > > Apart from that I faced a problem with this and had to disable > STRUCT/UNION from being treated as simple types. > > The problem was when generating LLVM output for > https://github.com/dibyendumajumdar/dmr_c/blob/master/tests/eic/testcbrt.c. > I will investigate more and report back my findings. There is indeed a problem with this case. It seems there is a mixup with types somewhere and sparse-llvm needs a few lines more. I'll look at it in the following days. -- Luc -- To unsubscribe from this list: send the line "unsubscribe linux-sparse" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On Thu, Aug 17, 2017 at 3:14 PM, Luc Van Oostenryck <luc.vanoostenryck@gmail.com> wrote: > > I agree it's confusing, and yes I would like a better name. > OTOH 'registrable' is not exactly the conveyed meaning. > 'register' is a concept that pertains to the backend, that > is machine specific, a pseudo may need several registers > and a register can hold several pseudos, ... Sure, I saw your new name some thing like promote-able. That is good. > > Here what we really want to select is something along: > 'it's interesting to see it as a flow of value' vs. > 'it's better to see it as a change in state'. > And yes, very often that just correspond to registers. > > Note: it's not even 'what can be put in a pseudo(-register)' > were selecting here. It's OK to have pseudos for > 'non-simple' values, They will just be transient and we > won't be interested in their 'flow'. We need to be very careful about composite type pointer alias. Any pointer alias to the member of the struct need to take into account as well. Chris -- To unsubscribe from this list: send the line "unsubscribe linux-sparse" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On Thu, Aug 17, 2017 at 3:28 PM, Dibyendu Majumdar <mobile@majumdar.org.uk> wrote: > > I will check at my end and revert with my thoughts. > > But I would have preferred if the SSA change was like for like > initially - rather than introducing new breaking changes. That should > ideally come as patches later on. I just realized another side effect of doing the SSA conversion on the AST directly. It means we will not have access to the linearization byte code before promoting the memory variable to pseudo. If you are depending on that pre-simplified byte code, then you don't have a choice not do it. Maybe later on we can consider an option to avoid doing the SSA conversion on memory variable as an option. Chris -- To unsubscribe from this list: send the line "unsubscribe linux-sparse" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On Fri, Aug 18, 2017 at 6:13 PM, Christopher Li <sparse@chrisli.org> wrote: >> >> Note: it's not even 'what can be put in a pseudo(-register)' >> were selecting here. It's OK to have pseudos for >> 'non-simple' values, They will just be transient and we >> won't be interested in their 'flow'. > > We need to be very careful about composite type pointer alias. There are only pointer aliases if there are pointers. Here, we're only interested in local variables. But, and thanks to this remarks, I added a test and realized that contrary to what I thought, the MOD_ADDRESSABLE is *not* propagated from member to parent. So for the moment, I'll need to drop this and only look at pure scalar variables. It's annoying. -- Luc -- To unsubscribe from this list: send the line "unsubscribe linux-sparse" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On Fri, Aug 18, 2017 at 6:18 PM, Christopher Li <sparse@chrisli.org> wrote: > > I just realized another side effect of doing the SSA conversion on > the AST directly. It means we will not have access to the linearization > byte code before promoting the memory variable to pseudo. Of course. But consider the other side: it means that you already have already a lot of variables promoted to pseudo *while* doing the linearization. It means that you already can know quite a bit about the 'values' during linearization and avoid to generate code that will be thrown away soon after being created. > Maybe later on we can consider an option to > avoid doing the SSA conversion on memory variable as an option. Sure, but it's a serious research topic too. Lots can be done. A few things are easy and cheap, most are quite complex and expensive. -- Luc -- To unsubscribe from this list: send the line "unsubscribe linux-sparse" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Hi Chris, On 18 August 2017 at 17:18, Christopher Li <sparse@chrisli.org> wrote: > On Thu, Aug 17, 2017 at 3:28 PM, Dibyendu Majumdar > <mobile@majumdar.org.uk> wrote: >> >> I will check at my end and revert with my thoughts. >> >> But I would have preferred if the SSA change was like for like >> initially - rather than introducing new breaking changes. That should >> ideally come as patches later on. > > I just realized another side effect of doing the SSA conversion on > the AST directly. It means we will not have access to the linearization > byte code before promoting the memory variable to pseudo. > > If you are depending on that pre-simplified byte code, then you don't > have a choice not do it. Maybe later on we can consider an option to > avoid doing the SSA conversion on memory variable as an option. > I have it setup so that if optimization is switched off I skip the CSE / Flow Simplification steps. In the older version the simplify_symbol_usage() was also being skipped but that is not used now. (Although the way I have merged this - I have the old code still there, and I can switch between the two implementations using a #define). As all my LLVM tests pass in this setup this is fine right now. I still get failures in some cases when the other subsequent stages are enabled - so there must be some incorrect simplifications occurring somewhere. I do not yet have specific tests to track down where the issues are. As I mentioned before - ideally it would be good have a SSA step that is reusable. Then you could run this step several times during the process - and allow some simplification phases to generate non SSA code. Perhaps the new SSA approach can be adapted for this. This would also allow access to the first pass linearized output without promotion to pseudos. But this should not stop us from moving forward with this change - as I think the SSA hooks into the linearization step are pretty specific and it should be relatively easy to have a mode where those steps are "dummied" - i.e. do nothing. I have a question though. For my other backend I need liveness analysis done even if I skip the other steps. Is it okay to run the liveness analysis phase while skipping the CSE / Flow simplification phases? Regards Dibyendu -- To unsubscribe from this list: send the line "unsubscribe linux-sparse" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On Fri, Aug 18, 2017 at 2:15 PM, Dibyendu Majumdar <mobile@majumdar.org.uk> wrote: > I have it setup so that if optimization is switched off I skip the CSE > / Flow Simplification steps. In the older version the > simplify_symbol_usage() was also being skipped but that is not used > now. (Although the way I have merged this - I have the old code still > there, and I can switch between the two implementations using a > #define). > > As all my LLVM tests pass in this setup this is fine right now. I > still get failures in some cases when the other subsequent stages are > enabled - so there must be some incorrect simplifications occurring > somewhere. I do not yet have specific tests to track down where the > issues are. At the point the SSA code is not merge yet. After we merger it. report back if you found some issue using the llvm back end. > > As I mentioned before - ideally it would be good have a SSA step that > is reusable. Then you could run this step several times during the > process - and allow some simplification phases to generate non SSA > code. Perhaps the new SSA approach can be adapted for this. This would > also allow access to the first pass linearized output without > promotion to pseudos. As the way this ssa conversion is implement. I actually don't know how hard it is to skip the promotion. I haven't look to that part of the code yet. I image there will be a test if this variable has been taking address or not. If so, it can't directly promote to pseudo without the load/store. That would be one possible place to insert the option to disable this. But again, let me look at the code first. > But this should not stop us from moving forward with this change - as > I think the SSA hooks into the linearization step are pretty specific > and it should be relatively easy to have a mode where those steps are > "dummied" - i.e. do nothing. > > I have a question though. For my other backend I need liveness > analysis done even if I skip the other steps. Is it okay to run the > liveness analysis phase while skipping the CSE / Flow simplification > phases? You can, but it is less effective. You will see a lot of load/store into the memory. SSA make it easy to trace the define and usage chain. Without that you can't really see well what is going on with the content of the memory. Chris -- To unsubscribe from this list: send the line "unsubscribe linux-sparse" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On Fri, Aug 18, 2017 at 8:35 PM, Christopher Li <sparse@chrisli.org> wrote: > > As the way this ssa conversion is implement. I actually don't know > how hard it is to skip the promotion. It's very easy, you just need for is_promotable() to always return false. But really, what would be the point? The points that matter to me are: 1) generate correct SSA information. This is ultra-important because with incorrect SSA a lot of the optimizations are wrong, introduce errors and infinite loops or need ugly workarounds. 2) correct any other issues sparse could have with the generated IR 3) correct any errors sparse could have with an optimization 4) add support for construct sparse doesn't support yet 5) add more features, make the sparse's code more efficient and the generated IR too. 5') do not forget that sparse is firstly the/a C checker for the kernel (and others projects). >> I have a question though. For my other backend I need liveness >> analysis done even if I skip the other steps. Is it okay to run the >> liveness analysis phase while skipping the CSE / Flow simplification >> phases? > > You can, but it is less effective. You will see a lot of load/store into the > memory. SSA make it easy to trace the define and usage chain. > Without that you can't really see well what is going on with the content > of the memory. Indeed, but I'm not very sure about Dibyendu's question here. You can have promoted all possible memory accesses to pseudos and still generating totally un-optimized code because you skipped the CSE and all others optimizations. It's two largely orthogonal things. -- Luc -- To unsubscribe from this list: send the line "unsubscribe linux-sparse" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On Fri, Aug 18, 2017 at 3:21 PM, Luc Van Oostenryck <luc.vanoostenryck@gmail.com> wrote: > > It's very easy, you just need for is_promotable() to always return > false. But really, what would be the point? I was mostly thinking debugging and verification purpose. AST to linearized byte code without the SSA conversion of memory variable is very straight forward. Also, I just realized that, promoting memory access into SSA pseudo is actually not avoidable at instruction level. After CSE and flow optimization, there might open up new chance to promote local variable into SSA form. We might need some code to promote memory access to SSA pseudo from instruction level any way. > The points that matter to me are: > 1) generate correct SSA information. > This is ultra-important because with incorrect SSA > a lot of the optimizations are wrong, introduce errors > and infinite loops or need ugly workarounds. That I totally agree. Incorrect SSA can't not use as SSA at all. > 2) correct any other issues sparse could have with the generated IR > 3) correct any errors sparse could have with an optimization > 4) add support for construct sparse doesn't support yet > 5) add more features, make the sparse's code more efficient > and the generated IR too. All agree. > 5') do not forget that sparse is firstly the/a C checker for the kernel > (and others projects). Sure. But sparse need to get good IR to perform the checking. Chris -- To unsubscribe from this list: send the line "unsubscribe linux-sparse" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On Fri, Aug 18, 2017 at 10:14 PM, Christopher Li <sparse@chrisli.org> wrote: > On Fri, Aug 18, 2017 at 3:21 PM, Luc Van Oostenryck wrote: > >> The points that matter to me are: >> 1) generate correct SSA information. >> This is ultra-important because with incorrect SSA >> a lot of the optimizations are wrong, introduce errors >> and infinite loops or need ugly workarounds. > > That I totally agree. Incorrect SSA can't not use as SSA at all. > >> 2) correct any other issues sparse could have with the generated IR >> 3) correct any errors sparse could have with an optimization >> 4) add support for construct sparse doesn't support yet >> 5) add more features, make the sparse's code more efficient >> and the generated IR too. > > All agree. > >> 5') do not forget that sparse is firstly the/a C checker for the kernel >> (and others projects). > > Sure. But sparse need to get good IR to perform the checking. Hence, points 2 & 3 :) -- Luc -- To unsubscribe from this list: send the line "unsubscribe linux-sparse" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
diff --git a/symbol.h b/symbol.h index 327449611..3f075c5bc 100644 --- a/symbol.h +++ b/symbol.h @@ -407,6 +407,39 @@ static inline int is_scalar_type(struct symbol *type) return 0; } +static inline int is_simple_type(struct symbol *type) +{ + if (type->type == SYM_NODE) + type = type->ctype.base_type; + switch (type->type) { + case SYM_ENUM: + case SYM_BITFIELD: + case SYM_PTR: + case SYM_RESTRICT: // OK, always integer types + return 1; + case SYM_STRUCT: + case SYM_UNION: + return type->bit_size <= long_ctype.bit_size; + default: + break; + } + if (type->ctype.base_type == &int_type) + return 1; + if (type->ctype.base_type == &fp_type) + return 1; + return 0; +} + +static inline int is_simple_var(struct symbol *var) +{ + if (!is_simple_type(var)) + return 0; +#define MOD_NONREG (MOD_STATIC|MOD_NONLOCAL|MOD_ADDRESSABLE|MOD_VOLATILE) + if (var->ctype.modifiers & MOD_NONREG) + return 0; + return 1; +} + static inline int is_function(struct symbol *type) { return type && type->type == SYM_FN;
Here by 'simple' we really mean 'worth of putting in a register'. We select all scalar types as well as struct and unions with a size not bigger than a long (register). Global and static variables, variables which address have been taken and volatiles variables are never selected. Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com> --- symbol.h | 33 +++++++++++++++++++++++++++++++++ 1 file changed, 33 insertions(+)