* ssa bootstrap problem on x86 (cmpstrsi_1 pattern) @ 2000-07-22 21:24 Geoff Keating 2000-07-23 0:50 ` Mark Mitchell 0 siblings, 1 reply; 20+ messages in thread From: Geoff Keating @ 2000-07-22 21:24 UTC (permalink / raw) To: gcc, mark Hi Mark, I've looked at the SSA bootstrap problem. It's caused by an insn in the x86 backend which looks like: (define_insn "cmpstrsi_1" [(set (reg:CC 17) (if_then_else:CC (ne (match_operand:SI 2 "register_operand" "c") (const_int 0)) (compare:SI (mem:BLK (match_operand:SI 0 "address_operand" "S")) (mem:BLK (match_operand:SI 1 "address_operand" "D"))) (const_int 0))) (use (match_operand:SI 3 "immediate_operand" "i")) (use (reg:CC 17)) (use (reg:SI 19)) (clobber (match_dup 0)) (clobber (match_dup 1)) (clobber (match_dup 2))] ...) The problem here is the match_dups. IMHO, it would be much better if these were written as match_scratch with '0', '1', and '2' constraints. Alternatively, we could detect this case in ssa.c and rewrite the insn using a SEQUENCE, copying the first three operands. We should do this detection only when the MD file contains constructs that make it necessary (specifically if an insn in the .md file has a MATCH_DUP between something it uses and something it sets), as there's likely to be a significant performance penalty. And it'll be ugly. Alternatively, we could declare that this pattern is inherently incompatible with SSA and disable its use if SSA is requested. -- - Geoffrey Keating <geoffk@cygnus.com> ^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: ssa bootstrap problem on x86 (cmpstrsi_1 pattern) 2000-07-22 21:24 ssa bootstrap problem on x86 (cmpstrsi_1 pattern) Geoff Keating @ 2000-07-23 0:50 ` Mark Mitchell 2000-07-24 11:51 ` Geoff Keating 0 siblings, 1 reply; 20+ messages in thread From: Mark Mitchell @ 2000-07-23 0:50 UTC (permalink / raw) To: geoffk; +Cc: gcc Hi Mark, I've looked at the SSA bootstrap problem. It's caused by an insn in the x86 backend which looks like: Thanks for tracking this down. (define_insn "cmpstrsi_1" [(set (reg:CC 17) (if_then_else:CC (ne (match_operand:SI 2 "register_operand" "c") (const_int 0)) (compare:SI (mem:BLK (match_operand:SI 0 "address_operand" "S")) (mem:BLK (match_operand:SI 1 "address_operand" "D"))) (const_int 0))) (use (match_operand:SI 3 "immediate_operand" "i")) (use (reg:CC 17)) (use (reg:SI 19)) (clobber (match_dup 0)) (clobber (match_dup 1)) (clobber (match_dup 2))] ...) The problem here is the match_dups. IMHO, it would be much better if these were written as match_scratch with '0', '1', and '2' constraints. So we have something like: [(SET (reg:CC 17) (if_then_else:CC (ne (reg:SI 35) (const int 0)) ...) (USE (reg:CC 17)) ... (CLOBBER (reg:SI 35))) ...] right? This just doesn't have a sensible SSA representation. I don't see how match_scratch helps. The bottom line is that moving any use of register 35 past this point is bogus. SSA doesn't really have a way of representing instructions that kill their input operands. That's why I think this kind of thing should happen later in the compiler. Right now, i386.md creates temporaries for the inputs to cmpstrsi_1, then clobbers the temporaries. Instead, we should generate some kind of placeholder here. Perhaps just: [(set (reg:CC 17) (if_then_else:CC (ne (match_operand:SI 2 "register_operand" "c") (const_int 0)) (compare:SI (mem:BLK (match_operand:SI 0 "address_operand" "S")) (mem:BLK (match_operand:SI 1 "address_operand" "D"))) (const_int 0))) (use (reg:CC 17)) (use (reg:SI 19))] Then, at some point after SSA, we should generate instructions to load the temporaries and add the clobbers. Does that make sense? -- Mark Mitchell mark@codesourcery.com CodeSourcery, LLC http://www.codesourcery.com ^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: ssa bootstrap problem on x86 (cmpstrsi_1 pattern) 2000-07-23 0:50 ` Mark Mitchell @ 2000-07-24 11:51 ` Geoff Keating 2000-07-25 3:20 ` Richard Earnshaw 2000-07-26 22:55 ` Mark Mitchell 0 siblings, 2 replies; 20+ messages in thread From: Geoff Keating @ 2000-07-24 11:51 UTC (permalink / raw) To: mark; +Cc: gcc > Cc: gcc@gcc.gnu.org > X-URL: http://www.codesourcery.com > Organization: CodeSourcery, LLC > From: Mark Mitchell <mark@codesourcery.com> > Date: Sun, 23 Jul 2000 00:50:01 -0700 > X-Dispatcher: imput version 990425(IM115) > > > Hi Mark, > > I've looked at the SSA bootstrap problem. It's caused by an insn > in the x86 backend which looks like: > > Thanks for tracking this down. > > (define_insn "cmpstrsi_1" > [(set (reg:CC 17) > (if_then_else:CC (ne (match_operand:SI 2 "register_operand" "c") > (const_int 0)) > (compare:SI (mem:BLK (match_operand:SI 0 "address_operand" "S")) > (mem:BLK (match_operand:SI 1 "address_operand" "D"))) > (const_int 0))) > (use (match_operand:SI 3 "immediate_operand" "i")) > (use (reg:CC 17)) > (use (reg:SI 19)) > (clobber (match_dup 0)) > (clobber (match_dup 1)) > (clobber (match_dup 2))] > ...) > > The problem here is the match_dups. IMHO, it would be much better if > these were written as match_scratch with '0', '1', and '2' > constraints. > > So we have something like: > > [(SET (reg:CC 17) > (if_then_else:CC (ne (reg:SI 35) (const int 0)) ...) > (USE (reg:CC 17)) > ... > (CLOBBER (reg:SI 35))) > ...] > > right? This just doesn't have a sensible SSA representation. I don't > see how match_scratch helps. The bottom line is that moving any use > of register 35 past this point is bogus. SSA doesn't really have a > way of representing instructions that kill their input operands. ... It does. I'm assuming that reg 35 is a pseudo (since SSA doesn't apply to hard registers). It looks like: (sequence [ (set (reg:SI 10035) (reg:SI 35)) (parallel [ (SET (reg:CC 17) (if_then_else:CC (ne (reg:SI 10035) (const int 0)) ...) (USE (reg:CC 17)) ... (CLOBBER (reg:SI 10035))) ...]) ]) You can see that, taken as a whole, this insn has an input that is not changed, and an outputs which is new to this insn. It's just that it now also has an extra SET, which hopefully will become no-ops but GCC isn't really good at ensuring such things. (I might add that the hard register use is going to hurt; it might be helpful to deal with that like the way we deal with SUBREGs by copying in and out of psuedos in a SEQUENCE. No doubt this would make reload much happier too.) The reason match_scratch helps is that we could just write the same pattern as (define_insn "cmpstrsi_1" [(set (reg:CC 17) (if_then_else:CC (ne (match_operand:SI 2 "register_operand" "c") (const_int 0)) (compare:SI (mem:BLK (match_operand:SI 0 "address_operand" "S")) (mem:BLK (match_operand:SI 1 "address_operand" "D"))) (const_int 0))) (use (match_operand:SI 3 "immediate_operand" "i")) (use (reg:CC 17)) (use (reg:SI 19)) (clobber (match_dup 0)) (clobber (match_dup 1)) (clobber (match_dup 2))] ...) (parallel [ (SET (reg:CC 10017) (if_then_else:CC (ne (reg:SI 35) (const int 0)) ...) (USE (reg:CC 17)) ... (CLOBBER (reg:SI 10035))) ...]) and because of the constraints on the USE and the CLOBBER's match_scratch, reload would ensure that registers 17 and 10017, and 35 and 10035, were put in the same hard register. I believe it can do this, although I'll have to try a bootstrap to make sure. -- - Geoffrey Keating <geoffk@cygnus.com> ^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: ssa bootstrap problem on x86 (cmpstrsi_1 pattern) 2000-07-24 11:51 ` Geoff Keating @ 2000-07-25 3:20 ` Richard Earnshaw 2000-07-26 22:55 ` Mark Mitchell 1 sibling, 0 replies; 20+ messages in thread From: Richard Earnshaw @ 2000-07-25 3:20 UTC (permalink / raw) To: Geoff Keating; +Cc: rearnsha > > I've looked at the SSA bootstrap problem. It's caused by an insn > > in the x86 backend which looks like: > > > > Thanks for tracking this down. > > > > (define_insn "cmpstrsi_1" > > [(set (reg:CC 17) > > (if_then_else:CC (ne (match_operand:SI 2 "register_operand" "c") > > (const_int 0)) > > (compare:SI (mem:BLK (match_operand:SI 0 "address_operand" "S")) > > (mem:BLK (match_operand:SI 1 "address_operand" "D"))) > > (const_int 0))) > > (use (match_operand:SI 3 "immediate_operand" "i")) > > (use (reg:CC 17)) > > (use (reg:SI 19)) > > (clobber (match_dup 0)) > > (clobber (match_dup 1)) > > (clobber (match_dup 2))] > > ...) > > > > The problem here is the match_dups. IMHO, it would be much better if > > these were written as match_scratch with '0', '1', and '2' > > constraints. > > I've been talking over a similar problem on the ARM with RTH. From my understanding, you cannot have a match_dup that ties an input to an output of the same insn if you want to be able to convert the insn to SSA form. You might be able to rewrite the above using ties: eg (define_insn "cmpstrsi_1" [(set (reg:CC 17) (if_then_else:CC (ne (match_operand:SI 5 "register_operand" "2") (const_int 0)) (compare:SI (mem:BLK (match_operand:SI 3 "address_operand" "0")) (mem:BLK (match_operand:SI 4 "address_operand" "1"))) (const_int 0))) (use (match_operand:SI 3 "immediate_operand" "i")) (use (reg:CC 17)) (use (reg:SI 19)) (clobber (match_operand:SI 0 "address_operand" "+S")) (clobber (match_operand:SI 1 "address_operand" "+D")) (clobber (match_operand:SI 2 "register_operand" "+c"))] Reload will then generate the necessary ties and reloads as required. R. ^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: ssa bootstrap problem on x86 (cmpstrsi_1 pattern) 2000-07-24 11:51 ` Geoff Keating 2000-07-25 3:20 ` Richard Earnshaw @ 2000-07-26 22:55 ` Mark Mitchell 2000-07-27 12:50 ` Geoff Keating 1 sibling, 1 reply; 20+ messages in thread From: Mark Mitchell @ 2000-07-26 22:55 UTC (permalink / raw) To: geoffk; +Cc: gcc I'm sorry I took a couple of days to reply. I've been staring at you mail trying to get it go into my brain in a way that makes sense to me, but I'm afraid I'm still stuck. It does. I'm assuming that reg 35 is a pseudo (since SSA doesn't apply to hard registers). It looks like: (As I've said before, it soon will. We've already got code to selectively but those hard registers into SSA form for which it makes sense. In our patches, the MD file says which hard registers should be SSA-ified.) (sequence [ (set (reg:SI 10035) (reg:SI 35)) (parallel [ (SET (reg:CC 17) (if_then_else:CC (ne (reg:SI 10035) (const int 0)) ...) (USE (reg:CC 17)) ... (CLOBBER (reg:SI 10035))) ...]) ]) You can see that, taken as a whole, this insn has an input that is not changed, and an outputs which is new to this insn. But the property that 10035 is valid in all blocks which are dominated by this block does not hold. And that is a very valuable property of SSA form. You have to know that 10035 is a special register, created only for this purpose. I understand how this could be made to work, but I still don't see an advantage over just doing: (parallel [ (SET (reg:CC 17) (if_then_else:CC (ne (reg:SI 35) (const int 0)) ...)) (USE (reg:CC 17)) ...]) ]) I'd add the CLOBBER (and make the transformation you suggest involving introducing the extra register) after leaving SSA form, or perhaps very late in the game in SSA. In other words, just postpone introducing the CLOBBER until later. To me, that makes sense. Abstractly, string-comparison doesn't alter the input operands. On the x86, it does -- but that's a hardware detail. Low-level passes, like scheduling, register allocation, and so forth need to know about that -- but high-level passes like dead-code elimination, loop unrolling, loop invariant code motion, etc. probably don't. The reason match_scratch helps is that we could just write the same pattern as (define_insn "cmpstrsi_1" [(set (reg:CC 17) (if_then_else:CC (ne (match_operand:SI 2 "register_operand" "c") (const_int 0)) (compare:SI (mem:BLK (match_operand:SI 0 "address_operand" "S")) (mem:BLK (match_operand:SI 1 "address_operand" "D"))) (const_int 0))) (use (match_operand:SI 3 "immediate_operand" "i")) (use (reg:CC 17)) (use (reg:SI 19)) (clobber (match_dup 0)) (clobber (match_dup 1)) (clobber (match_dup 2))] ...) I assume you meant to use `match_scratch' in the last three patterns? If so, I understand your point; independent of the discussion above, it would seem that we could make this change in the .md file -- if Richard thinks it make sense, and reload can handle it. -- Mark Mitchell mark@codesourcery.com CodeSourcery, LLC http://www.codesourcery.com ^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: ssa bootstrap problem on x86 (cmpstrsi_1 pattern) 2000-07-26 22:55 ` Mark Mitchell @ 2000-07-27 12:50 ` Geoff Keating 2000-07-27 13:10 ` Mark Mitchell 0 siblings, 1 reply; 20+ messages in thread From: Geoff Keating @ 2000-07-27 12:50 UTC (permalink / raw) To: mark; +Cc: gcc > Cc: gcc@gcc.gnu.org > From: Mark Mitchell <mark@codesourcery.com> > Date: Wed, 26 Jul 2000 22:54:56 -0700 > I'm sorry I took a couple of days to reply. I've been staring at you > mail trying to get it go into my brain in a way that makes sense to > me, but I'm afraid I'm still stuck. > > It does. I'm assuming that reg 35 is a pseudo (since SSA > doesn't apply to hard registers). It looks like: > > (As I've said before, it soon will. We've already got code to > selectively but those hard registers into SSA form for which it makes > sense. In our patches, the MD file says which hard registers should > be SSA-ified.) That's fine. In fact, I was wondering how we'd deal with hard registers. > (sequence [ > (set (reg:SI 10035) (reg:SI 35)) > (parallel [ > (SET (reg:CC 17) > (if_then_else:CC (ne (reg:SI 10035) (const int 0)) ...) > (USE (reg:CC 17)) > ... > (CLOBBER (reg:SI 10035))) > ...]) > ]) > > You can see that, taken as a whole, this insn has an input that is > not changed, and an outputs which is new to this insn. > > But the property that 10035 is valid in all blocks which are dominated > by this block does not hold. And that is a very valuable property of > SSA form. You have to know that 10035 is a special register, created > only for this purpose. I understand how this could be made to work, > but I still don't see an advantage over just doing: ??? 10035 is indeed valid in all such blocks. It's not _useful_, since it holds an indeterminate value, but it has certainly been set, and it has only been set once. Hopefully, any kind of dataflow analysis we do would notice that it was set by a CLOBBER and therefore does not hold a useful value. The important point is that register 35 _is_ valid. It holds the same value it held before. > > (parallel [ > (SET (reg:CC 17) > (if_then_else:CC (ne (reg:SI 35) (const int 0)) ...)) > (USE (reg:CC 17)) > ...]) > ]) > > I'd add the CLOBBER (and make the transformation you suggest involving > introducing the extra register) after leaving SSA form, or perhaps > very late in the game in SSA. In other words, just postpone > introducing the CLOBBER until later. You could do it in unssa, but then the problem is that you have to have special code to recognise this as a valid insn while it is in SSA form. > To me, that makes sense. Abstractly, string-comparison doesn't alter > the input operands. On the x86, it does -- but that's a hardware > detail. Low-level passes, like scheduling, register allocation, and > so forth need to know about that -- but high-level passes like > dead-code elimination, loop unrolling, loop invariant code motion, > etc. probably don't. > > The reason match_scratch helps is that we could just write the same > pattern as > > (define_insn "cmpstrsi_1" > [(set (reg:CC 17) > (if_then_else:CC (ne (match_operand:SI 2 "register_operand" "c") > (const_int 0)) > (compare:SI (mem:BLK (match_operand:SI 0 "address_operand" "S")) > (mem:BLK (match_operand:SI 1 "address_operand" "D"))) > (const_int 0))) > (use (match_operand:SI 3 "immediate_operand" "i")) > (use (reg:CC 17)) > (use (reg:SI 19)) > (clobber (match_dup 0)) > (clobber (match_dup 1)) > (clobber (match_dup 2))] > ...) > > I assume you meant to use `match_scratch' in the last three patterns? > If so, I understand your point; independent of the discussion above, > it would seem that we could make this change in the .md file -- if > Richard thinks it make sense, and reload can handle it. Oops! I must have sent the mail before I finished it. Yes, the idea would be to use (clobber (match_scratch:SI "0")) or whatever. One extra benefit of using match_scratch is that some places will add extra CLOBBERs if the insn doesn't have them and could be recognised if it had them. This may help with the recognition problem I mentioned above. -- - Geoffrey Keating <geoffk@cygnus.com> ^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: ssa bootstrap problem on x86 (cmpstrsi_1 pattern) 2000-07-27 12:50 ` Geoff Keating @ 2000-07-27 13:10 ` Mark Mitchell 2000-07-27 14:48 ` Richard Henderson 2000-07-27 15:44 ` Geoff Keating 0 siblings, 2 replies; 20+ messages in thread From: Mark Mitchell @ 2000-07-27 13:10 UTC (permalink / raw) To: geoffk; +Cc: gcc >>>>> "Geoff" == Geoff Keating <geoffk@cygnus.com> writes: Geoff> ??? 10035 is indeed valid in all such blocks. It's not Geoff> _useful_, since it holds an indeterminate value, but it has Geoff> certainly been set, and it has only been set once. Geoff> Hopefully, any kind of dataflow analysis we do would notice Geoff> that it was set by a CLOBBER and therefore does not hold a Geoff> useful value. That would work -- but it misses one of the important benefits of SSA: you don't have to do dataflow analysis. I think one of the big ideas is that if you're lower in the dominator tree you *know* what the values are for all registers in sight. Geoff> The important point is that register 35 _is_ valid. It Geoff> holds the same value it held before. Yup -- I recognized that. I'm suggesting the same invariant. Geoff> You could do it in unssa, but then the problem is that you Geoff> have to have special code to recognise this as a valid insn Geoff> while it is in SSA form. Right. I knew that, but I should have said I knew it. I'm not saying it's necessarily easy -- but I don't actually think it's that hard. Geoff> Oops! I must have sent the mail before I finished it. Geoff> Yes, the idea would be to use Geoff> (clobber (match_scratch:SI "0")) OK, I get it. I think these two aspects are orthogonal: i386.md could be perhaps improved as you suggest -- and we still have to worry about what to do with CLOBBER in SSA. I now totally understand where the motivation for your patch was coming from. But, I still think that the fix isn't correct -- any more than the current code is correct. I think we need to bite the bullet and get the CLOBBERs out of there; otherwise, we are forced to do some kind of dataflow anlaysis in SSA, and that negates one of the big wins from being in SSA form. I think I can allocate some resources to solve this problem soon. I feel clear on the concepts, now. But, if you still disagree, let's keep on hashing it out, by all means. Thanks a lot for all the analysis. -- Mark Mitchell mark@codesourcery.com CodeSourcery, LLC http://www.codesourcery.com ^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: ssa bootstrap problem on x86 (cmpstrsi_1 pattern) 2000-07-27 13:10 ` Mark Mitchell @ 2000-07-27 14:48 ` Richard Henderson 2000-07-27 15:13 ` Mark Mitchell 2000-07-27 15:44 ` Geoff Keating 1 sibling, 1 reply; 20+ messages in thread From: Richard Henderson @ 2000-07-27 14:48 UTC (permalink / raw) To: Mark Mitchell; +Cc: geoffk, gcc On Thu, Jul 27, 2000 at 01:10:11PM -0700, Mark Mitchell wrote: > I think we need to bite the bullet and get the CLOBBERs out of there; > otherwise, we are forced to do some kind of dataflow anlaysis in SSA... Not at all. We have a register set, once, to an unspecified value. That unspecified value is "valid" everywhere, just as with a register set to a useful value. r~ ^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: ssa bootstrap problem on x86 (cmpstrsi_1 pattern) 2000-07-27 14:48 ` Richard Henderson @ 2000-07-27 15:13 ` Mark Mitchell 2000-07-27 15:14 ` Richard Henderson 2000-07-27 15:46 ` Geoff Keating 0 siblings, 2 replies; 20+ messages in thread From: Mark Mitchell @ 2000-07-27 15:13 UTC (permalink / raw) To: rth; +Cc: geoffk, gcc >>>>> "Richard" == Richard Henderson <rth@cygnus.com> writes: Richard> On Thu, Jul 27, 2000 at 01:10:11PM -0700, Mark Mitchell Richard> wrote: >> I think we need to bite the bullet and get the CLOBBERs out of >> there; otherwise, we are forced to do some kind of dataflow >> anlaysis in SSA... Richard> Not at all. We have a register set, once, to an Richard> unspecified value. That unspecified value is "valid" Richard> everywhere, just as with a register set to a useful Richard> value. In Geoff's examples, I believe it was SET once, and then CLOBBERed. Did I misread? -- Mark Mitchell mark@codesourcery.com CodeSourcery, LLC http://www.codesourcery.com ^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: ssa bootstrap problem on x86 (cmpstrsi_1 pattern) 2000-07-27 15:13 ` Mark Mitchell @ 2000-07-27 15:14 ` Richard Henderson 2000-07-27 15:28 ` Mark Mitchell 2000-07-27 15:46 ` Geoff Keating 1 sibling, 1 reply; 20+ messages in thread From: Richard Henderson @ 2000-07-27 15:14 UTC (permalink / raw) To: Mark Mitchell; +Cc: geoffk, gcc On Thu, Jul 27, 2000 at 03:12:54PM -0700, Mark Mitchell wrote: > In Geoff's examples, I believe it was SET once, and then CLOBBERed. > Did I misread? The SEQUENCE construct is to be read as a unit. Therefore it was set in only one unit, therefore only set once. r~ ^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: ssa bootstrap problem on x86 (cmpstrsi_1 pattern) 2000-07-27 15:14 ` Richard Henderson @ 2000-07-27 15:28 ` Mark Mitchell 2000-07-27 15:35 ` Richard Henderson 0 siblings, 1 reply; 20+ messages in thread From: Mark Mitchell @ 2000-07-27 15:28 UTC (permalink / raw) To: rth; +Cc: geoffk, gcc >>>>> "Richard" == Richard Henderson <rth@cygnus.com> writes: Richard> The SEQUENCE construct is to be read as a unit. Richard> Therefore it was set in only one unit, therefore only set Richard> once. I understand. But, that's still confusing. For example, when given the insn where something is SET, you can't stop when you find the SET -- you have to keep looking to see if there's a CLOBBER. I guess I don't see a better alternative solution for SUBREGs, and perhaps this is analagous, but I'm unconvinced. And, as far as I can tell, we don't have a solution for the kind of constructs that appear in i386.md; we can use match_scratch there, but are we willing to forbid this kind of usage in all machine descriptions? -- Mark Mitchell mark@codesourcery.com CodeSourcery, LLC http://www.codesourcery.com ^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: ssa bootstrap problem on x86 (cmpstrsi_1 pattern) 2000-07-27 15:28 ` Mark Mitchell @ 2000-07-27 15:35 ` Richard Henderson 2000-07-27 15:42 ` Mark Mitchell 0 siblings, 1 reply; 20+ messages in thread From: Richard Henderson @ 2000-07-27 15:35 UTC (permalink / raw) To: Mark Mitchell; +Cc: geoffk, gcc On Thu, Jul 27, 2000 at 03:28:21PM -0700, Mark Mitchell wrote: > ... but are we willing to forbid this kind of usage in all machine > descriptions? I am. There are also other alternatives, mostly involving encapsulating all the block move/compare/whatever in big unspecs until we get past the early optimization passes. The only alternative is to give up on SSA on RTL entirely, and instead do it on a higher-level IL. Which might not be a bad idea anyway... r~ ^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: ssa bootstrap problem on x86 (cmpstrsi_1 pattern) 2000-07-27 15:35 ` Richard Henderson @ 2000-07-27 15:42 ` Mark Mitchell 0 siblings, 0 replies; 20+ messages in thread From: Mark Mitchell @ 2000-07-27 15:42 UTC (permalink / raw) To: rth; +Cc: geoffk, gcc >>>>> "Richard" == Richard Henderson <rth@cygnus.com> writes: Richard> I am. There are also other alternatives, mostly Richard> involving encapsulating all the block Richard> move/compare/whatever in big unspecs until we get past Richard> the early optimization passes. OK. In that case, I guess I can see how this scheme can be made to work. Would you mind approving Geoff's suggested changes to i386.md, so that then he can put back in his patch for CLOBBERs? Richard> The only alternative is to give up on SSA on RTL I take it you did not buy my suggestion? I meant it as a serious alternative. Richard> entirely, and instead do it on a higher-level IL. Which Richard> might not be a bad idea anyway... Indeed. -- Mark Mitchell mark@codesourcery.com CodeSourcery, LLC http://www.codesourcery.com ^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: ssa bootstrap problem on x86 (cmpstrsi_1 pattern) 2000-07-27 15:13 ` Mark Mitchell 2000-07-27 15:14 ` Richard Henderson @ 2000-07-27 15:46 ` Geoff Keating 1 sibling, 0 replies; 20+ messages in thread From: Geoff Keating @ 2000-07-27 15:46 UTC (permalink / raw) To: mark; +Cc: rth, gcc > From: Mark Mitchell <mark@codesourcery.com> > Date: Thu, 27 Jul 2000 15:12:54 -0700 > In Geoff's examples, I believe it was SET once, and then CLOBBERed. > Did I misread? It was SET and CLOBBERed in the same insn. -- - Geoffrey Keating <geoffk@cygnus.com> ^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: ssa bootstrap problem on x86 (cmpstrsi_1 pattern) 2000-07-27 13:10 ` Mark Mitchell 2000-07-27 14:48 ` Richard Henderson @ 2000-07-27 15:44 ` Geoff Keating 2000-07-27 16:01 ` Mark Mitchell 1 sibling, 1 reply; 20+ messages in thread From: Geoff Keating @ 2000-07-27 15:44 UTC (permalink / raw) To: mark; +Cc: gcc > Cc: gcc@gcc.gnu.org > X-URL: http://www.codesourcery.com > Organization: CodeSourcery, LLC > From: Mark Mitchell <mark@codesourcery.com> > Date: Thu, 27 Jul 2000 13:10:11 -0700 > X-Dispatcher: imput version 990425(IM115) > > >>>>> "Geoff" == Geoff Keating <geoffk@cygnus.com> writes: > > Geoff> ??? 10035 is indeed valid in all such blocks. It's not > Geoff> _useful_, since it holds an indeterminate value, but it has > Geoff> certainly been set, and it has only been set once. > Geoff> Hopefully, any kind of dataflow analysis we do would notice > Geoff> that it was set by a CLOBBER and therefore does not hold a > Geoff> useful value. > > That would work -- but it misses one of the important benefits of SSA: > you don't have to do dataflow analysis. I think one of the big ideas > is that if you're lower in the dominator tree you *know* what the > values are for all registers in sight. I don't understand. How do you know the value of a register which is, say, a function parameter? I also don't understand when you say "you don't have to do dataflow analysis". It is still not valid to turn (set (reg 93) (const_int 7)) (set (reg 94) (plus (reg 93) (reg 95)) into (set (reg 94) (plus (reg 93) (reg 95)) (set (reg 93) (const_int 7)) nor is it valid to turn (set (reg 93) (const_int 7)) (set (reg 94) (plus (reg 93) (reg 95)) into (set (reg 93) (const_int 7)) (set (reg 94) (plus (reg 95) (const_int 42)) and to check both of these, you must do dataflow analysis. SSA just makes this analysis much easier. You don't have to worry about where a register is set, you just find the one place where it is set and you know that is the place. Thus, if you see (clobber (reg 93)) and somewhere else in the program, you see (set (reg 94) (plus (reg 93) (reg 95)) you can simply turn the last insn into (clobber (reg 94)) because you _know_ that reg 93 can't ever hold anything important; you don't need to worry that there might be some other place where reg 93 gets a real value. (I'm assuming that every register here is in SSA form, of course.) > Geoff> Oops! I must have sent the mail before I finished it. > Geoff> Yes, the idea would be to use > > Geoff> (clobber (match_scratch:SI "0")) > > OK, I get it. I think these two aspects are orthogonal: i386.md could > be perhaps improved as you suggest -- and we still have to worry about > what to do with CLOBBER in SSA. How can they be orthogonal? They are causing the bug together. > I now totally understand where the motivation for your patch was > coming from. But, I still think that the fix isn't correct -- any > more than the current code is correct. I think we need to bite the > bullet and get the CLOBBERs out of there; otherwise, we are forced to > do some kind of dataflow anlaysis in SSA, and that negates one of the > big wins from being in SSA form. I think I can allocate some > resources to solve this problem soon. I am concerned you don't quite understand. CLOBBERs can carry information. Deleting them deletes information. Sometimes that information can be deduced from the rest of the RTL, but sometimes it cannot. There is nothing inherently incompatible with CLOBBER and SSA. The problem you are seeing is with MATCH_DUP and SSA. It just happens that the particular pattern that causes the trouble uses CLOBBER, but the problem would still have appeared if it used SET. Try changing the pattern so that instead of (clobber (match_dup 0)) (clobber (match_dup 1)) (clobber (match_dup 2)) it says (set (match_dup 0) (unspec [(mem:BLK (match_dup 0)) (mem:BLK (match_dup 1)) (match_dup 2) (reg:CC 17) (reg:SI 19)] 12)) (set (match_dup 1) (unspec [(mem:BLK (match_dup 0)) (mem:BLK (match_dup 1)) (match_dup 2) (reg:CC 17) (reg:SI 19)] 13)) (set (match_dup 2) (unspec [(mem:BLK (match_dup 0)) (mem:BLK (match_dup 1)) (match_dup 2) (reg:CC 17) (reg:SI 19)] 14)) which I believe is a fair statement of what this insn does, and you'll see that nothing has changed---including that the bootstrap still fails with -fssa. You could easily "fix" this, by doing the equivalent of your previous "fix" for SET instead of CLOBBER. If you can see why this would be wrong, then just switch over and you will see why the CLOBBER fix is wrong. > I feel clear on the concepts, now. But, if you still disagree, let's > keep on hashing it out, by all means. I think the reason it's not clear why that line had to be there is because the previous patch was only half of what I had planned to do. I will write a bit more of the patch and perhaps you will see. -- - Geoffrey Keating <geoffk@cygnus.com> ^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: ssa bootstrap problem on x86 (cmpstrsi_1 pattern) 2000-07-27 15:44 ` Geoff Keating @ 2000-07-27 16:01 ` Mark Mitchell 2000-07-27 16:59 ` Joern Rennecke 0 siblings, 1 reply; 20+ messages in thread From: Mark Mitchell @ 2000-07-27 16:01 UTC (permalink / raw) To: geoffk; +Cc: gcc >>>>> "Geoff" == Geoff Keating <geoffk@cygnus.com> writes: Geoff> I also don't understand when you say "you don't have to do Geoff> dataflow analysis". It is still not valid to turn I should have been more clear. You don't have to dataflow analysis to do lots of operations. Of course you have to worry about moving loads before stores, but you don't have to worry about lots of other things. Geoff> How can they be orthogonal? They are causing the bug Geoff> together. Hmm? Lots of times conincidental situations cause problems. There are two issues: - Do we want clobbers in SSA form? - Do we want match_dup or match_scratch in these patterns? We could choose not to have clobbers, but choose either match_dup or match_scratch. We would simply have to introduce the clobbers later in the game. Geoff> I am concerned you don't quite understand. CLOBBERs can Geoff> carry information. Deleting them deletes information. Geoff> Sometimes that information can be deduced from the rest of Geoff> the RTL, but sometimes it cannot. I fully understand all of that. I am not questioning the utility of clobbers. I am questioning the utility of having clobbers *until later* in the compiler. The only reason clobbers appear this early in the compiler is that GCC generates machine-specific code very early. There is no operation that I know of in any language that maps onto a clobber; those clobbers are appearing because of low-level details in particular machines. (For example, that string comparison messes with registers on the x86.) The existence of clobbers so early means that things are more complicated. I am suggesting that they would be less complicated if they happenned later. I think you are taking it as axiomatic that GCC's method of generating RTL which immediately a) contains hard registers and b) contains associated machine-specific artifacts is the only way to go. I am not. I would prefer to generate RTL that says, slightly more abstractly, what is happenning for a little longer. That's all. -- Mark Mitchell mark@codesourcery.com CodeSourcery, LLC http://www.codesourcery.com ^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: ssa bootstrap problem on x86 (cmpstrsi_1 pattern) 2000-07-27 16:01 ` Mark Mitchell @ 2000-07-27 16:59 ` Joern Rennecke 2000-07-27 17:22 ` Mark Mitchell 0 siblings, 1 reply; 20+ messages in thread From: Joern Rennecke @ 2000-07-27 16:59 UTC (permalink / raw) To: Mark Mitchell; +Cc: geoffk, gcc > The only reason clobbers appear this early in the compiler is that GCC > generates machine-specific code very early. There is no operation That is not true. When gcc synthesizes a move that is wider than the widest one available in the machine description, it first clobbers the destination, then does a series of moves into SUBREGs of the destination. ^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: ssa bootstrap problem on x86 (cmpstrsi_1 pattern) 2000-07-27 16:59 ` Joern Rennecke @ 2000-07-27 17:22 ` Mark Mitchell 2000-07-27 17:57 ` Michael Meissner 0 siblings, 1 reply; 20+ messages in thread From: Mark Mitchell @ 2000-07-27 17:22 UTC (permalink / raw) To: amylaar; +Cc: geoffk, gcc >>>>> "Joern" == Joern Rennecke <amylaar@cygnus.co.uk> writes: >> The only reason clobbers appear this early in the compiler is >> that GCC generates machine-specific code very early. There is >> no operation Joern> That is not true. When gcc synthesizes a move that is Joern> wider than the widest one available in the machine Joern> description, it first clobbers the destination, then does a Joern> series of moves into SUBREGs of the destination. But, again, isn't that a machine-specific issue? These moves could be represented directly as a SET and then resolved to an operation involving SUBREGs and CLOBBERs later. -- Mark Mitchell mark@codesourcery.com CodeSourcery, LLC http://www.codesourcery.com ^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: ssa bootstrap problem on x86 (cmpstrsi_1 pattern) 2000-07-27 17:22 ` Mark Mitchell @ 2000-07-27 17:57 ` Michael Meissner 2000-07-27 18:31 ` Mark Mitchell 0 siblings, 1 reply; 20+ messages in thread From: Michael Meissner @ 2000-07-27 17:57 UTC (permalink / raw) To: Mark Mitchell; +Cc: amylaar, geoffk, gcc On Thu, Jul 27, 2000 at 05:22:08PM -0700, Mark Mitchell wrote: > >>>>> "Joern" == Joern Rennecke <amylaar@cygnus.co.uk> writes: > > >> The only reason clobbers appear this early in the compiler is > >> that GCC generates machine-specific code very early. There is > >> no operation > > Joern> That is not true. When gcc synthesizes a move that is > Joern> wider than the widest one available in the machine > Joern> description, it first clobbers the destination, then does a > Joern> series of moves into SUBREGs of the destination. > > But, again, isn't that a machine-specific issue? These moves could be > represented directly as a SET and then resolved to an operation > involving SUBREGs and CLOBBERs later. Actually what we should do for for all arithmetic operations, including moves, is issue the generic operation (with no clobbers) in the rtl phase, and then in the post ssa phase, reissue the operations in a machine dependent manner, possibly issuing function calls, move by pieces, etc. Lets say a machine decscription has adddi3 defined as (%L accesses the lower part of the register), and no movdi instruction: (defun "adddi3" [(set (match_operand:DI 0 "register_operand" "=&r") (plus:DI (match_operand:DI 1 "register_operand" "%r") (match_operand:DI 2 "register_operand" "r"))) (clobber (match_scratch:SI 3 "=&r"))] "" "add %0,%1,%2\;add %L0,%L1,%L2\;sltu %3,%L0,%L1\;add %0,%0,%3") Thus in rtl you might have: (set (reg:DI 123) (plus:DI (reg:DI 124) (const_int 1))) Then after ssa you might have: ;; These are the movdi (reg:DI (const_int 1)) done in pieces (clobber (reg:DI 456)) (set (subreg:SI (reg:DI 456) 0) (const_int 0)) (set (subreg:SI (reg:DI 456) 1) (const_int 1)) ;; This is the rtl generated by the MD's gen_adddi3 (parallel [(set (reg:DI 123) (plus:DI (reg:DI 124) (reg:DI 456))) (clobber (match_scratch:SI))]) Thus you pretend that until after ssa, you have a perfect machine that implements all opcodes without any restrictions. I suspect you might need new rtl for representing arguments, maybe (IN_ARG <num>) and (OUT_ARG <num>). -- Michael Meissner, Red Hat, Inc. PMB 198, 174 Littleton Road #3, Westford, Massachusetts 01886, USA Work: meissner@redhat.com phone: +1 978-486-9304 Non-work: meissner@spectacle-pond.org fax: +1 978-692-4482 ^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: ssa bootstrap problem on x86 (cmpstrsi_1 pattern) 2000-07-27 17:57 ` Michael Meissner @ 2000-07-27 18:31 ` Mark Mitchell 0 siblings, 0 replies; 20+ messages in thread From: Mark Mitchell @ 2000-07-27 18:31 UTC (permalink / raw) To: meissner; +Cc: amylaar, geoffk, gcc >>>>> "Michael" == Michael Meissner <meissner@cygnus.com> writes: Michael> Actually what we should do for for all arithmetic Michael> operations, including moves, is issue the generic Michael> operation (with no clobbers) in the rtl phase, and then Michael> in the post ssa phase, reissue the operations in a Michael> machine dependent manner, possibly issuing function Michael> calls, move by pieces, etc. That is precisely what I was trying to suggest. Thanks for putting it more clearly. -- Mark Mitchell mark@codesourcery.com CodeSourcery, LLC http://www.codesourcery.com ^ permalink raw reply [flat|nested] 20+ messages in thread
end of thread, other threads:[~2000-07-27 18:31 UTC | newest] Thread overview: 20+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2000-07-22 21:24 ssa bootstrap problem on x86 (cmpstrsi_1 pattern) Geoff Keating 2000-07-23 0:50 ` Mark Mitchell 2000-07-24 11:51 ` Geoff Keating 2000-07-25 3:20 ` Richard Earnshaw 2000-07-26 22:55 ` Mark Mitchell 2000-07-27 12:50 ` Geoff Keating 2000-07-27 13:10 ` Mark Mitchell 2000-07-27 14:48 ` Richard Henderson 2000-07-27 15:13 ` Mark Mitchell 2000-07-27 15:14 ` Richard Henderson 2000-07-27 15:28 ` Mark Mitchell 2000-07-27 15:35 ` Richard Henderson 2000-07-27 15:42 ` Mark Mitchell 2000-07-27 15:46 ` Geoff Keating 2000-07-27 15:44 ` Geoff Keating 2000-07-27 16:01 ` Mark Mitchell 2000-07-27 16:59 ` Joern Rennecke 2000-07-27 17:22 ` Mark Mitchell 2000-07-27 17:57 ` Michael Meissner 2000-07-27 18:31 ` Mark Mitchell
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).