ssa bootstrap problem on x86 (cmpstrsi_1 pattern)

ssa bootstrap problem on x86 (cmpstrsi_1 pattern)

[Geoff Keating]

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>

Re: ssa bootstrap problem on x86 (cmpstrsi_1 pattern)

[Mark Mitchell]

  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

Re: ssa bootstrap problem on x86 (cmpstrsi_1 pattern)

[Geoff Keating]

> 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>

Re: ssa bootstrap problem on x86 (cmpstrsi_1 pattern)

[Richard Earnshaw]

> >   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.

Re: ssa bootstrap problem on x86 (cmpstrsi_1 pattern)

[Mark Mitchell]

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

Re: ssa bootstrap problem on x86 (cmpstrsi_1 pattern)

[Geoff Keating]

> 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>

Re: ssa bootstrap problem on x86 (cmpstrsi_1 pattern)

[Mark Mitchell]

>>>>> "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

Re: ssa bootstrap problem on x86 (cmpstrsi_1 pattern)

[Richard Henderson]

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~

Re: ssa bootstrap problem on x86 (cmpstrsi_1 pattern)

[Mark Mitchell]

>>>>> "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

Re: ssa bootstrap problem on x86 (cmpstrsi_1 pattern)

[Richard Henderson]

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~

Re: ssa bootstrap problem on x86 (cmpstrsi_1 pattern)

[Mark Mitchell]

>>>>> "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

Re: ssa bootstrap problem on x86 (cmpstrsi_1 pattern)

[Richard Henderson]

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~

Re: ssa bootstrap problem on x86 (cmpstrsi_1 pattern)

[Mark Mitchell]

>>>>> "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

Re: ssa bootstrap problem on x86 (cmpstrsi_1 pattern)

[Geoff Keating]

> 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>

Re: ssa bootstrap problem on x86 (cmpstrsi_1 pattern)

[Geoff Keating]

> 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>

Re: ssa bootstrap problem on x86 (cmpstrsi_1 pattern)

[Mark Mitchell]

>>>>> "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

Re: ssa bootstrap problem on x86 (cmpstrsi_1 pattern)

[Joern Rennecke]

> 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.

Re: ssa bootstrap problem on x86 (cmpstrsi_1 pattern)

[Mark Mitchell]

>>>>> "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

Re: ssa bootstrap problem on x86 (cmpstrsi_1 pattern)

[Michael Meissner]

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

Re: ssa bootstrap problem on x86 (cmpstrsi_1 pattern)

[Mark Mitchell]

>>>>> "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