| Message ID | 20170809193806.30975-3-luc.vanoostenryck@gmail.com (mailing list archive) |
|---|---|
| State | Superseded, archived |
| Headers | show |
Hi Luc, This this change independent of the rest of changes in the series - i.e. can I just apply this change? Regards Dibyendu On 9 August 2017 at 20:37, Luc Van Oostenryck <luc.vanoostenryck@gmail.com> wrote: > Current sparse code doesn't handle very gracefully > code with undefined pseudos. These can occurs, of > course because the dev has not initialize them, > maybe by error, but they can also occurs when they > are only set (and used) in a single path or even worse, > hen initiializing a bitfield. > > The origin of the problem is the single store shortcut > in simplify_one_symbol() which doesn't take in account > the (absence of) dominance when loads exist without > stores. > > Fix this by removing this single-store shortcut and leave > all the work for the general case which handle this > situation quite well (and/but set those variables to 0). > > Warning: this change impact the performance. > > Note: this patch will also avoid internal infinite loops > occuring when processing undefined vars present > during the SSA construction. > > Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com> > --- > flow.c | 39 ++------------------------------------- > validation/infinite-loop0.c | 1 - > 2 files changed, 2 insertions(+), 38 deletions(-) > > diff --git a/flow.c b/flow.c > index c7161d47e..5a3d55f76 100644 > --- a/flow.c > +++ b/flow.c > @@ -650,11 +650,10 @@ void check_access(struct instruction *insn) > > static void simplify_one_symbol(struct entrypoint *ep, struct symbol *sym) > { > - pseudo_t pseudo, src; > + pseudo_t pseudo; > struct pseudo_user *pu; > - struct instruction *def; > unsigned long mod; > - int all, stores, complex; > + int all; > > /* Never used as a symbol? */ > pseudo = sym->pseudo; > @@ -670,17 +669,12 @@ static void simplify_one_symbol(struct entrypoint *ep, struct symbol *sym) > if (mod) > goto external_visibility; > > - def = NULL; > - stores = 0; > - complex = 0; > FOR_EACH_PTR(pseudo->users, pu) { > /* We know that the symbol-pseudo use is the "src" in the instruction */ > struct instruction *insn = pu->insn; > > switch (insn->opcode) { > case OP_STORE: > - stores++; > - def = insn; > break; > case OP_LOAD: > break; > @@ -697,37 +691,8 @@ static void simplify_one_symbol(struct entrypoint *ep, struct symbol *sym) > default: > warning(sym->pos, "symbol '%s' pseudo used in unexpected way", show_ident(sym->ident)); > } > - complex |= insn->offset; > } END_FOR_EACH_PTR(pu); > > - if (complex) > - goto complex_def; > - if (stores > 1) > - goto multi_def; > - > - /* > - * Goodie, we have a single store (if even that) in the whole > - * thing. Replace all loads with moves from the pseudo, > - * replace the store with a def. > - */ > - src = VOID; > - if (def) > - src = def->target; > - > - FOR_EACH_PTR(pseudo->users, pu) { > - struct instruction *insn = pu->insn; > - if (insn->opcode == OP_LOAD) { > - check_access(insn); > - convert_load_instruction(insn, src); > - } > - } END_FOR_EACH_PTR(pu); > - > - /* Turn the store into a no-op */ > - kill_store(def); > - return; > - > -multi_def: > -complex_def: > external_visibility: > all = 1; > FOR_EACH_PTR_REVERSE(pseudo->users, pu) { > diff --git a/validation/infinite-loop0.c b/validation/infinite-loop0.c > index a28492307..0e3e3805c 100644 > --- a/validation/infinite-loop0.c > +++ b/validation/infinite-loop0.c > @@ -8,5 +8,4 @@ void foo(void) > * check-name: internal infinite loop (0) > * check-command: sparse -Wno-decl $file > * check-timeout: > - * check-known-to-fail > */ > -- > 2.14.0 > > -- > 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 -- 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 Wed, Aug 9, 2017 at 9:47 PM, Dibyendu Majumdar <mobile@majumdar.org.uk> wrote: > Hi Luc, > > This this change independent of the rest of changes in the series - > i.e. can I just apply this change? Absolutely. -- 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 9 August 2017 at 21:02, Luc Van Oostenryck <luc.vanoostenryck@gmail.com> wrote: > On Wed, Aug 9, 2017 at 9:47 PM, Dibyendu Majumdar > <mobile@majumdar.org.uk> wrote: >> Hi Luc, >> >> This this change independent of the rest of changes in the series - >> i.e. can I just apply this change? > > Absolutely. > Thank you. I am trying out this change as I am hoping it will help avoid the incorrect simplifications we saw in some cases. So far my findings are: It solves the bit field access issue: i.e. this test works (https://github.com/dibyendumajumdar/dmr_c/blob/master/tests/set1/onebit.c). But it doesn't help with the issue with pseudos defined in one branch of the code (https://github.com/dibyendumajumdar/dmr_c/blob/master/tests/bugs/simplifybug.c). Is there another fix / patch that you made to overcome above issue or would you expect both issues to be fixed by this change? I will run my test cases with this change and report if anything breaks. 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 10, 2017 at 12:23 AM, Dibyendu Majumdar <mobile@majumdar.org.uk> wrote: > > Thank you. I am trying out this change as I am hoping it will help > avoid the incorrect simplifications we saw in some cases. So far my > findings are: > > It solves the bit field access issue: i.e. this test works > (https://github.com/dibyendumajumdar/dmr_c/blob/master/tests/set1/onebit.c). Yes, it's the one I used for the patches. > But it doesn't help with the issue with pseudos defined in one branch > of the code (https://github.com/dibyendumajumdar/dmr_c/blob/master/tests/bugs/simplifybug.c). > > Is there another fix / patch that you made to overcome above issue or > would you expect both issues to be fixed by this change? I don't know exactly what you have as problem with this other test. I quickly looked at the output of test-linearize and I saw no problem with self-defined pseudos. The phi-nodes are very wrong though but that's another problem. You may try the new SSA construction at : https://github.com/lucvoo/sparse/tree/sssa It will help a lot. But in both case, I saw that sparse-llvm crashes (which is normal as none of the LLVM fixes are applied here). In the coming days, I'll do a branch that aggregates all the good stuff. But until then, can you explain exactly what is wrong with this second test? > I will run my test cases with this change and report if anything breaks. Thanks. Testing in other environments, with other goals, is very useful. -- 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 10 August 2017 at 00:15, Luc Van Oostenryck <luc.vanoostenryck@gmail.com> wrote: > On Thu, Aug 10, 2017 at 12:23 AM, Dibyendu Majumdar > <mobile@majumdar.org.uk> wrote: >> >> Thank you. I am trying out this change as I am hoping it will help >> avoid the incorrect simplifications we saw in some cases. So far my >> findings are: >> > >> But it doesn't help with the issue with pseudos defined in one branch >> of the code (https://github.com/dibyendumajumdar/dmr_c/blob/master/tests/bugs/simplifybug.c). >> >> Is there another fix / patch that you made to overcome above issue or >> would you expect both issues to be fixed by this change? > > I don't know exactly what you have as problem with this other test. > I quickly looked at the output of test-linearize and I saw no problem > with self-defined pseudos. The phi-nodes are very wrong though but that's > another problem. > Yes I suppose that is what it is. LLVM complains that 'instruction does not dominate all uses'. The unsimplified IR works fine (https://github.com/dibyendumajumdar/dmr_c/blob/master/tests/bugs/simplifybug.lin). The simplified IR has an issue (https://github.com/dibyendumajumdar/dmr_c/blob/master/tests/bugs/simplifybug_O1.lin). > You may try the new SSA construction at : > https://github.com/lucvoo/sparse/tree/sssa > It will help a lot. > Is that a standalone change I can apply? > But in both case, I saw that sparse-llvm crashes > (which is normal as none of the LLVM fixes are applied here). > > In the coming days, I'll do a branch that aggregates all the good stuff. > I think that this is a very good idea. Since the official sparse repo is so behind - it will be good if you maintain a branch in your repo that has all the things that you have tested thoroughly and are happy with - this can be the "next sparse version" for testing. I would suggest aggregating only changes that you are 100% confident about. It will allow me (and others like me) to test the changes and report back if any issues are found. > But until then, can you explain exactly what is wrong with this second test? > >> I will run my test cases with this change and report if anything breaks. > > Thanks. > Testing in other environments, with other goals, is very useful. > So far I haven't found any breaks which is good. I will continue testing tomorrow. 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 10, 2017 at 1:32 AM, Dibyendu Majumdar <mobile@majumdar.org.uk> wrote: > > Yes I suppose that is what it is. LLVM complains that 'instruction > does not dominate all uses'. > The unsimplified IR works fine > (https://github.com/dibyendumajumdar/dmr_c/blob/master/tests/bugs/simplifybug.lin). > The simplified IR has an issue > (https://github.com/dibyendumajumdar/dmr_c/blob/master/tests/bugs/simplifybug_O1.lin). Yes, I saw now. It's hopeless. It's a problem with the SSA construction (happen between linearization and simplification), basically, it puts the phi-nodes where there is a load but it's often too late, they need to be put where paths join. >> You may try the new SSA construction at : >> https://github.com/lucvoo/sparse/tree/sssa >> It will help a lot. >> > > Is that a standalone change I can apply? Arf ... in a sense yes but it's really a 40 patches series (but most changes are isolated, maybe not too much work for you I don't know). > I think that this is a very good idea. Since the official sparse repo > is so behind - it will be good if you maintain a branch in your repo > that has all the things that you have tested thoroughly and are happy > with - this can be the "next sparse version" for testing. I would > suggest aggregating only changes that you are 100% confident about. It > will allow me (and others like me) to test the changes and report back > if any issues are found. It's the idea. Only that the 100% confident will be "confident that it won't break but improve situations I know about". Regards, -- 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 10 August 2017 at 00:51, Luc Van Oostenryck <luc.vanoostenryck@gmail.com> wrote: > On Thu, Aug 10, 2017 at 1:32 AM, Dibyendu Majumdar > <mobile@majumdar.org.uk> wrote: >> >> Yes I suppose that is what it is. LLVM complains that 'instruction >> does not dominate all uses'. >> The unsimplified IR works fine >> (https://github.com/dibyendumajumdar/dmr_c/blob/master/tests/bugs/simplifybug.lin). >> The simplified IR has an issue >> (https://github.com/dibyendumajumdar/dmr_c/blob/master/tests/bugs/simplifybug_O1.lin). > > Yes, I saw now. It's hopeless. > It's a problem with the SSA construction (happen between linearization > and simplification), basically, it puts the phi-nodes where there is a load > but it's often too late, they need to be put where paths join. > >>> You may try the new SSA construction at : >>> https://github.com/lucvoo/sparse/tree/sssa >>> It will help a lot. >>> >> >> Is that a standalone change I can apply? > > Arf ... in a sense yes but it's really a 40 patches series > (but most changes are isolated, maybe not too much work for you > I don't know). > I am merging the current changes in RC5 to my repository. When that is done, I would like to try out your new SSA construction approach. Please let me know if this is complete (i.e. functional). I had a look at the branch above, but not all commits appeared to be related to the SSA construction, so any pointer to the list of changes I should pick would be very helpful. I can test the new approach in my repository and report back. 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 Sat, Aug 12, 2017 at 8:51 PM, Dibyendu Majumdar <mobile@majumdar.org.uk> wrote: > > ..., I would like to try out your new SSA construction approach. > Please let me know if this is complete (i.e. functional). It's more than simply functional, it seems to work pretty well: - it passes the testsuite - it doesn't crash while using it on the kernel or any of my tests (I have plenty of tests I can't upstream or doesn't make sense to be upstreamed) - the generated code handle correctly the placement of phi-nodes - the generated code handle correctly undefined vars/pseudos - it's a bit faster than the current sparse and use less memory But: - it needs more testing - code needs some polish here & there - it's not a panacea for all current issues. In my opinion, it's a HUGE step forward. > I had a look > at the branch above, but not all commits appeared to be related to the > SSA construction, so any pointer to the list of changes I should pick > would be very helpful. True, the first commits are some small improvement, bug fixes or even optimization fixes I need for testing during development. Currently, I'm busy to aggregate the others changes, the LLVM ones and friends. There are a few merge conflicts to solve but not much. The next step will be to make the SSA more usable. -- 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 12 August 2017 at 20:28, Luc Van Oostenryck <luc.vanoostenryck@gmail.com> wrote: > On Sat, Aug 12, 2017 at 8:51 PM, Dibyendu Majumdar > <mobile@majumdar.org.uk> wrote: >> >> ..., I would like to try out your new SSA construction approach. >> Please let me know if this is complete (i.e. functional). > > It's more than simply functional, it seems to work pretty well: > - it passes the testsuite > - it doesn't crash while using it on the kernel or any of my tests > (I have plenty of tests I can't upstream or doesn't make sense > to be upstreamed) > - the generated code handle correctly the placement of phi-nodes > - the generated code handle correctly undefined vars/pseudos > - it's a bit faster than the current sparse and use less memory > > But: > - it needs more testing > - code needs some polish here & there > - it's not a panacea for all current issues. > > In my opinion, it's a HUGE step forward. > That sounds very good. >> I had a look >> at the branch above, but not all commits appeared to be related to the >> SSA construction, so any pointer to the list of changes I should pick >> would be very helpful. > > True, the first commits are some small improvement, bug fixes or > even optimization fixes I need for testing during development. > > Currently, I'm busy to aggregate the others changes, the LLVM ones > and friends. There are a few merge conflicts to solve but not much. > The next step will be to make the SSA more usable. > Okay please let me know when you are ready for me to try and incorporate this work. I will be finished merging the RC5 changes in the next few days. 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 Sat, Aug 12, 2017 at 9:55 PM, Dibyendu Majumdar <mobile@majumdar.org.uk> wrote: > > Okay please let me know when you are ready for me to try and > incorporate this work. I will be finished merging the RC5 changes in > the next few days. I guess it will be done in a few days too. -- 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/flow.c b/flow.c index c7161d47e..5a3d55f76 100644 --- a/flow.c +++ b/flow.c @@ -650,11 +650,10 @@ void check_access(struct instruction *insn) static void simplify_one_symbol(struct entrypoint *ep, struct symbol *sym) { - pseudo_t pseudo, src; + pseudo_t pseudo; struct pseudo_user *pu; - struct instruction *def; unsigned long mod; - int all, stores, complex; + int all; /* Never used as a symbol? */ pseudo = sym->pseudo; @@ -670,17 +669,12 @@ static void simplify_one_symbol(struct entrypoint *ep, struct symbol *sym) if (mod) goto external_visibility; - def = NULL; - stores = 0; - complex = 0; FOR_EACH_PTR(pseudo->users, pu) { /* We know that the symbol-pseudo use is the "src" in the instruction */ struct instruction *insn = pu->insn; switch (insn->opcode) { case OP_STORE: - stores++; - def = insn; break; case OP_LOAD: break; @@ -697,37 +691,8 @@ static void simplify_one_symbol(struct entrypoint *ep, struct symbol *sym) default: warning(sym->pos, "symbol '%s' pseudo used in unexpected way", show_ident(sym->ident)); } - complex |= insn->offset; } END_FOR_EACH_PTR(pu); - if (complex) - goto complex_def; - if (stores > 1) - goto multi_def; - - /* - * Goodie, we have a single store (if even that) in the whole - * thing. Replace all loads with moves from the pseudo, - * replace the store with a def. - */ - src = VOID; - if (def) - src = def->target; - - FOR_EACH_PTR(pseudo->users, pu) { - struct instruction *insn = pu->insn; - if (insn->opcode == OP_LOAD) { - check_access(insn); - convert_load_instruction(insn, src); - } - } END_FOR_EACH_PTR(pu); - - /* Turn the store into a no-op */ - kill_store(def); - return; - -multi_def: -complex_def: external_visibility: all = 1; FOR_EACH_PTR_REVERSE(pseudo->users, pu) { diff --git a/validation/infinite-loop0.c b/validation/infinite-loop0.c index a28492307..0e3e3805c 100644 --- a/validation/infinite-loop0.c +++ b/validation/infinite-loop0.c @@ -8,5 +8,4 @@ void foo(void) * check-name: internal infinite loop (0) * check-command: sparse -Wno-decl $file * check-timeout: - * check-known-to-fail */
Current sparse code doesn't handle very gracefully code with undefined pseudos. These can occurs, of course because the dev has not initialize them, maybe by error, but they can also occurs when they are only set (and used) in a single path or even worse, hen initiializing a bitfield. The origin of the problem is the single store shortcut in simplify_one_symbol() which doesn't take in account the (absence of) dominance when loads exist without stores. Fix this by removing this single-store shortcut and leave all the work for the general case which handle this situation quite well (and/but set those variables to 0). Warning: this change impact the performance. Note: this patch will also avoid internal infinite loops occuring when processing undefined vars present during the SSA construction. Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com> --- flow.c | 39 ++------------------------------------- validation/infinite-loop0.c | 1 - 2 files changed, 2 insertions(+), 38 deletions(-)