| Message ID | 20170807191205.86590-2-luc.vanoostenryck@gmail.com (mailing list archive) |
|---|---|
| State | Superseded, archived |
| Headers | show |
On Mon, Aug 7, 2017 at 12:11 PM, Luc Van Oostenryck <luc.vanoostenryck@gmail.com> wrote: > > 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). Ack. The single-store case really was always a hack to make simple things look simple. Doing proper optimization is the right approach, no question about it. Linus -- 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 Mon, Aug 7, 2017 at 5:42 PM, Linus Torvalds <torvalds@linux-foundation.org> wrote: > > Ack. The single-store case really was always a hack to make simple > things look simple. > > Doing proper optimization is the right approach, no question about it. > Totally agree. 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 10, 2017 at 2:29 AM, Christopher Li <sparse@chrisli.org> wrote: > On Mon, Aug 7, 2017 at 5:42 PM, Linus Torvalds wrote: >> >> Ack. The single-store case really was always a hack to make simple >> things look simple. >> >> Doing proper optimization is the right approach, no question about it. >> > > Totally agree. This patch (and the preceding one but not the ones that follow) is totally worth to add to the release. I've tested it (my normal tests + kernel allyesconfig) and all is OK : - lots of changes in test-linearize, of course, but only good changes - zero changes in kernel check Are you fine with this? -- 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 Wed, Aug 9, 2017 at 8:41 PM, Luc Van Oostenryck <luc.vanoostenryck@gmail.com> wrote: > > Are you fine with this? Sure. I am still writing the documents for RC5. Do you want me to merge this V4 version as it is? I will start to switch to master to do the merge. Giving up the rebase thing on sparse-next. At the same time I also want to give you patch a bit more test. Thanks 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 Mon, Aug 7, 2017 at 3:11 PM, 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 forgot (or choose) to > initialize them but they can also occurs when they > are only set (and used) in a single path and not others > or even worse when initilaizing a bitfield. > > The origin of the problme is the single store shortcut > in simplify_one_symbol() which doesn't take in account > the (absence of) dominance when loads exist without > stores. I have give it a bit more thinking. The right metal model is actually consider the every uninitialized variable has an implicit define at the entry block. The reason this short cut is wrong is that, it is not about how many store we have (single vs multiple). It is about weather all the usage(load) has one single store immediate dominates it. If it does, even exist of other stores, this optimization can still be done. The question would be if we have easy and quick way to detect that all the load are immediate dominated by the one single store. If that condition holds, we can still do the "short-cut". BTW, I consider this patch can separate out from the other patch in this series meaning wise. The other patches are about constant related transformations. This one is about proper SSA. It can still be merge as one series. That part is fine. Please let me know if you want to include this in the RC5. Give me a proper git pull address. Topic branch is fine. Thanks 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 10, 2017 at 1:01 PM, Christopher Li <sparse@chrisli.org> wrote: > > The reason this short cut is wrong is that, it is not about > how many store we have (single vs multiple). It is about > weather all the usage(load) has one single store > immediate dominates it. If it does, even exist of other stores, > this optimization can still be done. More exactly, this shortcut is wrong because it is based on the assumption that if there is a single store, then this store must necessary dominates all the loads. This assumption is, of course, wrong when the var is not explicitly defined. > The question would be if we have easy and quick way to > detect that all the load are immediate dominated by the > one single store. That's what the general case does. > If that condition holds, we can still do the "short-cut". Only for limited special cases. It's not worth, forget about it. Anyway, it's very temporary because the code still put the phi-nodes at wrong places. This simplify_one_symbol() is replaced by the new SSA construction branch. Believe it or not but this placement of phi-nodes is a much bigger issue than those undefined vars. For example, on the kernel, this patch has exactly zero (visible) effect. But every non-trivial piece of code is plainly very wrong because of those bad phi-nodes. > BTW, I consider this patch can separate out from the other > patch in this series meaning wise. Yes, it's what I said :"this patch and the preceding one (because it's needed for the test case)". > Please let me know if you want to include this in the RC5. > Give me a proper git pull address. Topic branch is fine. Yes, I'll do later. (if you want just for testing, please take the ref in the cover letter and drop the top patches. Unless comments from you, I don't have the intention to change something to these two patches) 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
On Thu, Aug 10, 2017 at 8:26 AM, Luc Van Oostenryck <luc.vanoostenryck@gmail.com> wrote: > > Anyway, it's very temporary because the code still put the > phi-nodes at wrong places. > This simplify_one_symbol() is replaced by the new SSA construction > branch. > > Believe it or not but this placement of phi-nodes is a much bigger > issue than those undefined vars. For example, on the kernel, > this patch has exactly zero (visible) effect. But every non-trivial > piece of code is plainly very wrong because of those bad phi-nodes. I can totally see that. My way to explain to myself is that, it is all about the SSA dominance property. Violate the properly == bad things can happen. I can use the property to reason about phi node placements, Also reason this patch as well. > Yes, I'll do later. > (if you want just for testing, please take the ref in the cover letter > and drop the top patches. Unless comments from you, I don't > have the intention to change something to these two patches) I can do more testing too. Thanks! 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
diff --git a/flow.c b/flow.c index 6cac21b24..6b2c879a8 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) {
Current sparse code doesn't handle very gracefully code with undefined pseudos. These can occurs, of course because the dev has forgot (or choose) to initialize them but they can also occurs when they are only set (and used) in a single path and not others or even worse when initilaizing a bitfield. The origin of the problme 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. Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com> --- flow.c | 39 ++------------------------------------- 1 file changed, 2 insertions(+), 37 deletions(-)