[Bug rtl-optimization/92281] Inconsistent canonicalization of (minus (minus A B) C)
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=92281 Martin Liška changed: What|Removed |Added Status|UNCONFIRMED |NEW Last reconfirmed||2020-01-29 CC||marxin at gcc dot gnu.org Ever confirmed|0 |1
[Bug rtl-optimization/92281] Inconsistent canonicalization of (minus (minus A B) C)
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=92281 --- Comment #6 from Segher Boessenkool --- (In reply to Richard Earnshaw from comment #5) > What I've shown is equivalent to (minus (minus (A) (B)) (C)), which is what > combine produces today. Are you saying that the documentation disagrees on > the overall shape of this and the compilers output right now? I am saying that a lot of what combine forms is not canonical form. There simply is no canonical form for many expressions. Every combine attempt results in one form, that is a very important feature as well as one of the main weaknesses of combine; but that one form is *not* canonical. > Minus isn't commutative, but in a 3-way version (A - B - C), the order of B > and C does not matter. ... - B - C is the same as ... - C - B. So you can > re-order the nesting to produce a canonical form. Sure. And where there isn't a canonical form, you can reorder it whatever way you want. That is why there *are* canonical forms: to reduce the number of forms everything has to deal with. But this does not always help, and some times it works *against* this goal. > > > > What targets would it break, and how? > > > > > > Hard to tell, until we try it. Mostly the 'breakage' would be some > > > combine > > > patterns might no-longer match if the target only had one and the ordering > > > were not canonical (leading to some missed optimizations). On targets > > > that > > > have both orderings, some patterns might become redundant and never match > > > unless directly generated by the back-end. > > > > The breakage will be that many targets optimise worse than they did before. > > And this is non-obvious to detect, usually. > > At present it's entirely random, since there's no attempt to create order. It usually preserves ordering. Simply by not changing things that do not need any change. But sometimes things are changed for no apparent reason. > Any matching that does occur is more by good luck (or overkill in providing > all the redundant variant forms). Yes, but any change that degrades code quality is still a regression, whether those targets just got lucky or that was by design. > > A lot of what combine does is *not* canonicalisation. But combine comes up > > with only one result for every attempted combination, making that a kind-of > > de-facto canonicalisation. > > > > And yes, that is what I asked: in both cases it combined the same insn with > > a simple pseudo move, in both cases on the RHS in that insn. And it came > > up with different results. > > > > This may be unavoidable, or combine does something weird, or the RTL that > > combine started with was non-canonical or unexpected in some other way, etc. > > > > So I'd like to know where the difference was introduced. Was it in combine > > at all, to start with? It can be in simplify-rtx as well for example. > > Combine is the prime user of simplify-rtx - perhaps I'm conflating the two, > but this is, in part, combine's problem because it's during the combine pass > that having matchers for all these variants becomes most important. I am not asking to shift the blame. I am asking to start to solve the problem. To do that we need to know where the problem *is*, if there actually is a problem, etc. Just more information is needed. simplify-rtx is very different from combine. Everything simplify-rtx does is a simplification(*). Many things combine does are *not*. That is one of the reasons combine still has its own "simplifier": it is not a simplifier. Some of what that does is good and useful. Some of it is questionable. Some of it is actively bad. (*) There are a few cases where simplify-rtx does a non-simplification. I try to weed those out.
[Bug rtl-optimization/92281] Inconsistent canonicalization of (minus (minus A B) C)
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=92281 --- Comment #5 from Richard Earnshaw --- (In reply to Segher Boessenkool from comment #4) > (In reply to Richard Earnshaw from comment #2) > > Yes, but since > > (A - B) - C = A - B - C = A - C - B = (A - C) - B > > we can clearly swap the order of the two RHS operands here. > > My intent was to show the two rtx shapes, and that neither is a defined > canonical form. > > > This would be > > a special rule similar to the rules that we have that rewrite > > A - (B + C) > > as > > (A - B) - C. > > That isn't a canonical form, either! Not according to the documentation, > anyway. > What I've shown is equivalent to (minus (minus (A) (B)) (C)), which is what combine produces today. Are you saying that the documentation disagrees on the overall shape of this and the compilers output right now? > > My suggestion would be that we should have a rule here that re-orders things > > so > > that B is the most 'complex' operation and C the simplest, using the normal > > precedence ordering (complex > REG > CONST). > > But minus isn't commutative, and reordering with minus introduces negs which > is wrong (it is canonical to *remove* such negs). > Minus isn't commutative, but in a 3-way version (A - B - C), the order of B and C does not matter. ... - B - C is the same as ... - C - B. So you can re-order the nesting to produce a canonical form. > > > What targets would it break, and how? > > > > Hard to tell, until we try it. Mostly the 'breakage' would be some combine > > patterns might no-longer match if the target only had one and the ordering > > were not canonical (leading to some missed optimizations). On targets that > > have both orderings, some patterns might become redundant and never match > > unless directly generated by the back-end. > > The breakage will be that many targets optimise worse than they did before. > And this is non-obvious to detect, usually. At present it's entirely random, since there's no attempt to create order. Any matching that does occur is more by good luck (or overkill in providing all the redundant variant forms). > > > > What makes combine come up with something else for these two cases? > > > > Sorry, I don't understand what you're asking here? Why does it produce > > these two separate canoncializations in one compilation? I've no idea, > > hence the bug report. > > A lot of what combine does is *not* canonicalisation. But combine comes up > with only one result for every attempted combination, making that a kind-of > de-facto canonicalisation. > > And yes, that is what I asked: in both cases it combined the same insn with > a simple pseudo move, in both cases on the RHS in that insn. And it came > up with different results. > > This may be unavoidable, or combine does something weird, or the RTL that > combine started with was non-canonical or unexpected in some other way, etc. > > So I'd like to know where the difference was introduced. Was it in combine > at all, to start with? It can be in simplify-rtx as well for example. Combine is the prime user of simplify-rtx - perhaps I'm conflating the two, but this is, in part, combine's problem because it's during the combine pass that having matchers for all these variants becomes most important.
[Bug rtl-optimization/92281] Inconsistent canonicalization of (minus (minus A B) C)
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=92281 --- Comment #4 from Segher Boessenkool --- (In reply to Richard Earnshaw from comment #2) > Yes, but since > (A - B) - C = A - B - C = A - C - B = (A - C) - B > we can clearly swap the order of the two RHS operands here. My intent was to show the two rtx shapes, and that neither is a defined canonical form. > This would be > a special rule similar to the rules that we have that rewrite > A - (B + C) > as > (A - B) - C. That isn't a canonical form, either! Not according to the documentation, anyway. > My suggestion would be that we should have a rule here that re-orders things > so > that B is the most 'complex' operation and C the simplest, using the normal > precedence ordering (complex > REG > CONST). But minus isn't commutative, and reordering with minus introduces negs which is wrong (it is canonical to *remove* such negs). > > What targets would it break, and how? > > Hard to tell, until we try it. Mostly the 'breakage' would be some combine > patterns might no-longer match if the target only had one and the ordering > were not canonical (leading to some missed optimizations). On targets that > have both orderings, some patterns might become redundant and never match > unless directly generated by the back-end. The breakage will be that many targets optimise worse than they did before. And this is non-obvious to detect, usually. > > What makes combine come up with something else for these two cases? > > Sorry, I don't understand what you're asking here? Why does it produce > these two separate canoncializations in one compilation? I've no idea, > hence the bug report. A lot of what combine does is *not* canonicalisation. But combine comes up with only one result for every attempted combination, making that a kind-of de-facto canonicalisation. And yes, that is what I asked: in both cases it combined the same insn with a simple pseudo move, in both cases on the RHS in that insn. And it came up with different results. This may be unavoidable, or combine does something weird, or the RTL that combine started with was non-canonical or unexpected in some other way, etc. So I'd like to know where the difference was introduced. Was it in combine at all, to start with? It can be in simplify-rtx as well for example.
[Bug rtl-optimization/92281] Inconsistent canonicalization of (minus (minus A B) C)
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=92281 --- Comment #3 from Richard Earnshaw --- As for 'special' regs and their ordering, I'm not sure. I would suggest that if we have a commutative operation with two registers and one of the registers is marked as a pointer, then it should appear first. But other than that, I don't have any other suggestions here.
[Bug rtl-optimization/92281] Inconsistent canonicalization of (minus (minus A B) C)
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=92281 --- Comment #2 from Richard Earnshaw --- (In reply to Segher Boessenkool from comment #1) > (In reply to Richard Earnshaw from comment #0) > > > Failed to match this instruction: > > (set (reg:SI 125 [+4 ]) > > (minus:SI (minus:SI (reg:SI 127) > > (reg:SI 121 [ b+4 ])) > > (ltu:SI (reg:CC 100 cc) > > (const_int 0 [0] > > > (set (reg:SI 125 [+4 ]) > > (minus:SI (minus:SI (reg:SI 127) > > (reg:SI 121 [ b+4 ])) > > (ltu:SI (reg:CC 100 cc) > > (const_int 0 [0] > > That is > > (set D (minus (minus A B) (X C 0))) > > > Successfully matched this instruction: > > (set (reg:SI 125 [+4 ]) > > (minus:SI (minus:SI (reg:SI 119 [ a+4 ]) > > (ltu:SI (reg:CC 100 cc) > > (const_int 0 [0]))) > > (reg:SI 129))) > > And this is > > (set D (minus (minus A (X C 0)) B)) > Yes, but since (A - B) - C = A - B - C = A - C - B = (A - C) - B we can clearly swap the order of the two RHS operands here. This would be a special rule similar to the rules that we have that rewrite A - (B + C) as (A - B) - C. My suggestion would be that we should have a rule here that re-orders things so that B is the most 'complex' operation and C the simplest, using the normal precedence ordering (complex > REG > CONST). > There are no rules for that afaics. > > > These are mathematically equivalent, but because we do not produce > > consistent RTL for them we need two patterns if we are to match both > > alternatives. > > Yes; the same is true for quite a few other unusual combinations. Or > not even so very unusual: > (ior (ashift X N) (lshiftrt Y M)) > vs. > (ior (lshiftrt Y M) (ashift X N)) > is one nasty example, but also reg+reg+reg where one of the regs is > "special" can appear in multiple forms. > > > I think both should be canonicalized with the LTU inside the inner MINUS > > expression, but I wouldn't mind if the other were chosen, as long as we were > > consistent. > > What would the rule become? See suggestion above. I think we might also have a rule that within 'complex' the ordering might be by RTX code number, but that's somewhat arbitrary; thought it is likely to be fairly stable. It would produce a strict canonical ordering for your IOR case above, however. > What targets would it break, and how? Hard to tell, until we try it. Mostly the 'breakage' would be some combine patterns might no-longer match if the target only had one and the ordering were not canonical (leading to some missed optimizations). On targets that have both orderings, some patterns might become redundant and never match unless directly generated by the back-end. > > What makes combine come up with something else for these two cases? Sorry, I don't understand what you're asking here? Why does it produce these two separate canoncializations in one compilation? I've no idea, hence the bug report.
[Bug rtl-optimization/92281] Inconsistent canonicalization of (minus (minus A B) C)
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=92281 Segher Boessenkool changed: What|Removed |Added CC||segher at gcc dot gnu.org --- Comment #1 from Segher Boessenkool --- (In reply to Richard Earnshaw from comment #0) > Failed to match this instruction: > (set (reg:SI 125 [+4 ]) > (minus:SI (minus:SI (reg:SI 127) > (reg:SI 121 [ b+4 ])) > (ltu:SI (reg:CC 100 cc) > (const_int 0 [0] > (set (reg:SI 125 [+4 ]) > (minus:SI (minus:SI (reg:SI 127) > (reg:SI 121 [ b+4 ])) > (ltu:SI (reg:CC 100 cc) > (const_int 0 [0] That is (set D (minus (minus A B) (X C 0))) > Successfully matched this instruction: > (set (reg:SI 125 [+4 ]) > (minus:SI (minus:SI (reg:SI 119 [ a+4 ]) > (ltu:SI (reg:CC 100 cc) > (const_int 0 [0]))) > (reg:SI 129))) And this is (set D (minus (minus A (X C 0)) B)) There are no rules for that afaics. > These are mathematically equivalent, but because we do not produce > consistent RTL for them we need two patterns if we are to match both > alternatives. Yes; the same is true for quite a few other unusual combinations. Or not even so very unusual: (ior (ashift X N) (lshiftrt Y M)) vs. (ior (lshiftrt Y M) (ashift X N)) is one nasty example, but also reg+reg+reg where one of the regs is "special" can appear in multiple forms. > I think both should be canonicalized with the LTU inside the inner MINUS > expression, but I wouldn't mind if the other were chosen, as long as we were > consistent. What would the rule become? What targets would it break, and how? What makes combine come up with something else for these two cases?
