Predicated execution

Predicated execution

[Michael Meissner]

Of the machines that GCC currently targets, are there any machines
that would use predicated (conditional) execution?  Off the top of my
head there is the arm which does P.E. via FINAL_PRESCAN_INSN, and of
course the IA64.  I am starting to look at infrastructure needed for
P.E. for the IA64 and others.  If the port maintainers could email me
or reply to the group a brief summary of the predicated execution
support in their machine it would be appreciated.

In particular what is the form in RTL of your comparisons that enable
P.E., is it a cc0 machine (bletch), do you have multiple condition
code registers, and whether you have limitations on the instructions
executed, such as not being able to use instructions with constants
(like the 1 in a++), etc.

-- 
Michael Meissner, Cygnus Solutions
PMB 198, 174 Littleton Road #3, Westford, Massachusetts 01886
Work:	  meissner@cygnus.com		phone: 978-486-9304 fax: 978-692-4482
Non-work: meissner@spectacle-pond.org

Re: Predicated execution

[Jeffrey A Law]

  In message < 200001070348.WAA15609@tiktok.cygnus.com >you write:
  > Of the machines that GCC currently targets, are there any machines
  > that would use predicated (conditional) execution?
arm, pa would be the more popular.  You already know about the embedded
chips such as the d10v.

  > Off the top of my
  > head there is the arm which does P.E. via FINAL_PRESCAN_INSN, and of
  > course the IA64.  I am starting to look at infrastructure needed for
  > P.E. for the IA64 and others.  If the port maintainers could email me
  > or reply to the group a brief summary of the predicated execution
  > support in their machine it would be appreciated.
The PA is pretty simple.

Most instructions (arithmetic, logicals, bit stuff) will generate a set of
condition codes based on their result which can be used to control execution
of the next instruction in the instruction queue.  For example:


	add,= s0,s1,t0		s0 + s1 -> t0
	sub s2,s3,t1		if (t1 != 0) s2 + s3 -> t1

The condition specifies when the next instruction should _not_ be executed
(actually it nullifies the writeback stage in the pipeline).

We don't currently expose this at all at the RTL level.  Though we have defined
a few patterns such as cmov, min, max which generate this kind of code in the
output templates.

The first insn must be a arithmetic, logical, bit twiddle.  The second
insn could be anything, including branches, calls, etc.

jeff

Re: Predicated execution

[Richard Earnshaw]

P.E. on the ARM is very important, especially for those processors that 
don't have branch prediction or other branch acceleration techniques, or 
when optimizing for code size.  The current code in FINAL_PRESCAN_INSN is 
OK as far as it goes, but misses many possible cases because it does not 
do enough condition code analysis at code lables.

Substantially all instructions can be predicated on the single condition 
code register (there is one instruction in ARMv5 that has no predicate), 
though in a machine description, some instructions use the predicate as a 
natural part of the instruction (eg conditional branches, conditional 
moves).  An important feature of the ARM is that even instructions that 
set the condition code register can also be predicated, so we get 
interesting sequences such as

	if (a && b)
	  c++;

  which can be compiled to:

	cmp	a, #0
	cmpne	b, #0
	addne	c, #1


> In particular what is the form in RTL of your comparisons that enable
P.E.

It is a set of a single hard register (reg 24).  How predicated 
instructions should be represented is less clear -- I can think of no way 
in rtl to specify that an instruction has no side effects if its predicate 
is false, for example

	ldrne	r0, [r1, #4]!

is a post-increment word load, but the increment is not performed if the 
instruction fails its predicate.

Richard

Re: Predicated execution

[Michael Meissner]

On Sat, Jan 08, 2000 at 03:17:32PM +0000, Richard Earnshaw wrote:
> P.E. on the ARM is very important, especially for those processors that 
> don't have branch prediction or other branch acceleration techniques, or 
> when optimizing for code size.  The current code in FINAL_PRESCAN_INSN is 
> OK as far as it goes, but misses many possible cases because it does not 
> do enough condition code analysis at code lables.
> 
> Substantially all instructions can be predicated on the single condition 
> code register (there is one instruction in ARMv5 that has no predicate), 
> though in a machine description, some instructions use the predicate as a 
> natural part of the instruction (eg conditional branches, conditional 
> moves).  An important feature of the ARM is that even instructions that 
> set the condition code register can also be predicated, so we get 
> interesting sequences such as
> 
> 	if (a && b)
> 	  c++;
> 
>   which can be compiled to:
> 
> 	cmp	a, #0
> 	cmpne	b, #0
> 	addne	c, #1
> 

Yes, when the IA64 support goes in, there should better support for predicated
execution.  As I recall, most of the development for the arm is now being done
on a branch.  Any idea when it will go in the mainline (or am I misremembering
things).

> > In particular what is the form in RTL of your comparisons that enable
> P.E.
> 
> It is a set of a single hard register (reg 24).  How predicated 
> instructions should be represented is less clear -- I can think of no way 
> in rtl to specify that an instruction has no side effects if its predicate 
> is false, for example
> 
> 	ldrne	r0, [r1, #4]!
> 
> is a post-increment word load, but the increment is not performed if the 
> instruction fails its predicate.

In some unreleased ports I used the syntax:

	(if_then_else (<condition>)
		      (<expr>)
		      (const_int 0))

for execute <expr> if <condition> is true, and:

	(if_then_else (<condition>)
		      (const_int 0)
		      (<expr>))

for execute <expr> if <condition> is false.  This proved to be a little to over
enthusiastic, and in the rewrite it will only accept:

	(if_then_else (ne (match_operand:CC 0 "register_operand" "c")
			  (const_int 0))
	  (match_insn "@pred")
	  (const_int 0))

where the ne might be an eq to reverse the sense of the comparison.  Note, in
my original ports, the work was being done after sched2.  We hope to move it
earlier for simple if-then and if-then-else statements, but avoid the problems
that caused HAVE_conditional_arithmetic to be commented out.

-- 
Michael Meissner, Cygnus Solutions
PMB 198, 174 Littleton Road #3, Westford, Massachusetts 01886
Work:	  meissner@cygnus.com		phone: 978-486-9304 fax: 978-692-4482
Non-work: meissner@spectacle-pond.org

Re: Predicated execution

[Richard Earnshaw]

> 
> Yes, when the IA64 support goes in, there should better support for predicated
> execution.  As I recall, most of the development for the arm is now being done
> on a branch.  Any idea when it will go in the mainline (or am I misremembering
> things).

Yes, we are developing a new arm+thumb combined back end on a branch.  At 
this time I'm not sure when this will get merged (hopefully not too long 
now -- I mainly want to sort out a few issues I have with the latest 
constant pool code).  The problem is that both Nick and I have had other 
things going on which are taking priority (in my case nothing to do with 
gcc).

> > > In particular what is the form in RTL of your comparisons that enable
> > P.E.
> > 
> > It is a set of a single hard register (reg 24).  How predicated 
> > instructions should be represented is less clear -- I can think of no way 
> > in rtl to specify that an instruction has no side effects if its predicate 
> > is false, for example
> > 
> > 	ldrne	r0, [r1, #4]!
> > 
> > is a post-increment word load, but the increment is not performed if the 
> > instruction fails its predicate.
> 
> In some unreleased ports I used the syntax:
> 
> 	(if_then_else (<condition>)
> 		      (<expr>)
> 		      (const_int 0))
> 
> for execute <expr> if <condition> is true, and:
> 
> 	(if_then_else (<condition>)
> 		      (const_int 0)
> 		      (<expr>))
> 
> for execute <expr> if <condition> is false.  

I don't see how this syntax can be used to describe an insn with side 
effects.  Or are you defining that

	(set (pc) (if_then_else (<cond>)
		   (label_ref <L>)
		   (pc)))

	(set (reg) (mem (post_inc (<expr>))))

	(code_label <L>)

can be written as

	(if_then_else (~<cond>)
	 (set (reg) (mem (post_inc (<expr>)))
	 (const_int 0))

and that the side effect does not occur if the condition is false?  This 
would be at variance with the normal definition of if_then_else where it 
is my understanding that side effects occur whichever arm is true (this is 
required so that reload can move sub-expressions out of the insn).
	(set (reg) (if_then_else (~<cond>)
		    (post_in	


> This proved to be a little to over
> enthusiastic, and in the rewrite it will only accept:
> 
> 	(if_then_else (ne (match_operand:CC 0 "register_operand" "c")
> 			  (const_int 0))
> 	  (match_insn "@pred")
> 	  (const_int 0))
> 
> where the ne might be an eq to reverse the sense of the comparison.  Note, in
> my original ports, the work was being done after sched2.  We hope to move it
> earlier for simple if-then and if-then-else statements, but avoid the problems
> that caused HAVE_conditional_arithmetic to be commented out.

Hmm, how would the @pred work?  Would we be able to match this based on an 
attribute of the target insn?  Or would there be some other way of 
describing whether an insn can be safely predicated?  I'm assuming that it 
wouldn't be necessary to have a pattern like this for every insn in the 
description that can be predicated (this would nearly double the size of 
arm.md, which is already pretty large).

Richard

Re: Predicated execution

[Jeffrey A Law]

  In message < 200001121121.LAA00503@cam-mail2.cambridge.arm.com >you write:
  > > In some unreleased ports I used the syntax:
  > > 
  > > 	(if_then_else (<condition>)
  > > 		      (<expr>)
  > > 		      (const_int 0))
  > > 
  > > for execute <expr> if <condition> is true, and:
  > > 
  > > 	(if_then_else (<condition>)
  > > 		      (const_int 0)
  > > 		      (<expr>))
  > > 
  > > for execute <expr> if <condition> is false.  
  > 
  > I don't see how this syntax can be used to describe an insn with side 
  > effects.  Or are you defining that
  > 
  > 	(set (pc) (if_then_else (<cond>)
  > 		   (label_ref <L>)
  > 		   (pc)))
  > 
  > 	(set (reg) (mem (post_inc (<expr>))))
  > 
  > 	(code_label <L>)
  > 
  > can be written as
  > 
  > 	(if_then_else (~<cond>)
  > 	 (set (reg) (mem (post_inc (<expr>)))
  > 	 (const_int 0))
  > 
  > and that the side effect does not occur if the condition is false?  This 
  > would be at variance with the normal definition of if_then_else where it 
  > is my understanding that side effects occur whichever arm is true (this is 
  > required so that reload can move sub-expressions out of the insn).
I think this is a pretty key issue.

It may be the case that we don't want to use IF_THEN_ELSE, but a new RTL
code where the semantics of whether or not the true arm is evaluated if the
predicate is false is explicit.

  > Hmm, how would the @pred work?  Would we be able to match this based on an 
  > attribute of the target insn?  Or would there be some other way of 
  > describing whether an insn can be safely predicated?  I'm assuming that it 
  > wouldn't be necessary to have a pattern like this for every insn in the 
  > description that can be predicated (this would nearly double the size of 
  > arm.md, which is already pretty large).
The @pred is stuff rth has been working on.  The basic idea is that the
@pred will be an insn in and of itself and will be passed on to a recognizer
to verify that it is a. a valid insn and b. it is valid for predication.

The general idea is to have a small number of these predicated insns in the
md file (in an ideal world, just one :-) instead of having to add a predicated
version of each existing pattern.

jeff

Re: Predicated execution

[Richard Earnshaw]

>   > 
>   > 	(if_then_else (~<cond>)
>   > 	 (set (reg) (mem (post_inc (<expr>)))
>   > 	 (const_int 0))
>   > 
>   > and that the side effect does not occur if the condition is false?  This 
>   > would be at variance with the normal definition of if_then_else where it 
>   > is my understanding that side effects occur whichever arm is true (this is 
>   > required so that reload can move sub-expressions out of the insn).
> I think this is a pretty key issue.
> 
> It may be the case that we don't want to use IF_THEN_ELSE, but a new RTL
> code where the semantics of whether or not the true arm is evaluated if the
> predicate is false is explicit.
> 

Some random thoughts...

How about a new type of insn, eg predicate_insn?  You could then convert 
an insn to being predicated by just changing the wrapper.

Eg

	(predicate_insn 111 110 112 (set (foo) (bar))
		(cond))

With this method you would probably also need predicate_call_insn and 
predicate_jump_insn as well, so there might be a problem with where in the 
insn the predicate operand was stored.  So another idea might just be

	(predicate_insn 111 110 112 (cond)
		(insn 0 0 0 (set (foo) (bar))))

Though even with this care would be needed if you still need to detect 
jump/call insns.

Feel free to shoot holes in this.

>   > Hmm, how would the @pred work?  Would we be able to match this based on an 
>   > attribute of the target insn?  Or would there be some other way of 
>   > describing whether an insn can be safely predicated?  I'm assuming that it 
>   > wouldn't be necessary to have a pattern like this for every insn in the 
>   > description that can be predicated (this would nearly double the size of 
>   > arm.md, which is already pretty large).
> The @pred is stuff rth has been working on.  The basic idea is that the
> @pred will be an insn in and of itself and will be passed on to a recognizer
> to verify that it is a. a valid insn and b. it is valid for predication.
> 
> The general idea is to have a small number of these predicated insns in the
> md file (in an ideal world, just one :-) instead of having to add a predicated
> version of each existing pattern.

I was hoping this was the case.  Good.

Re: Predicated execution

[Michael Meissner]

On Thu, Jan 13, 2000 at 10:45:52AM +0000, Richard Earnshaw wrote:
> How about a new type of insn, eg predicate_insn?  You could then convert 
> an insn to being predicated by just changing the wrapper.
> 
> Eg
> 
> 	(predicate_insn 111 110 112 (set (foo) (bar))
> 		(cond))
> 
> With this method you would probably also need predicate_call_insn and 
> predicate_jump_insn as well, so there might be a problem with where in the 
> insn the predicate operand was stored.  So another idea might just be
> 
> 	(predicate_insn 111 110 112 (cond)
> 		(insn 0 0 0 (set (foo) (bar))))
> 
> Though even with this care would be needed if you still need to detect 
> jump/call insns.
> 
> Feel free to shoot holes in this.

I've thought about this.  You wouldn't be able to convert insns in place since
predicate_insn, et. all need an additional field to specify the conditional,
unless you grow the insn, to always have the field defined.  You also have to
go through all of the sources and find the places where it knows that
INSN/CALL_INSN/JUMP_INSN are the only insn types.

I am warming to Jeff's idea of rather than overusing if_then_else, of having a
new predicated execution type.  My original work which didn't make it out to
fsf, used:

     (if_then_else
	(condition)
	(true path)
	(const 0))

and

     (if_then_else
	(condition)
	(const 0)
	(false path))

but this was judged as being too general.

> >   > Hmm, how would the @pred work?  Would we be able to match this based on an 
> >   > attribute of the target insn?  Or would there be some other way of 
> >   > describing whether an insn can be safely predicated?  I'm assuming that it 
> >   > wouldn't be necessary to have a pattern like this for every insn in the 
> >   > description that can be predicated (this would nearly double the size of 
> >   > arm.md, which is already pretty large).

With my initial work, it would triple rather than double, since you need to
provide both true cases and false cases.  However, depending on the machine,
judicious use of match_operator would cut down the number of cases.  In any
case, that was one of the faults of the original work, that we're trying to
address.

> > The @pred is stuff rth has been working on.  The basic idea is that the
> > @pred will be an insn in and of itself and will be passed on to a recognizer
> > to verify that it is a. a valid insn and b. it is valid for predication.
> > 
> > The general idea is to have a small number of these predicated insns in the
> > md file (in an ideal world, just one :-) instead of having to add a predicated
> > version of each existing pattern.
> 
> I was hoping this was the case.  Good.

-- 
Michael Meissner, Cygnus Solutions
PMB 198, 174 Littleton Road #3, Westford, Massachusetts 01886
Work:	  meissner@cygnus.com		phone: 978-486-9304 fax: 978-692-4482
Non-work: meissner@spectacle-pond.org

Re: Predicated execution

[Richard Henderson]

On Wed, Jan 12, 2000 at 11:22:44AM +0000, Richard Earnshaw wrote:
> 
> 	(set (pc) (if_then_else (<cond>)
> 		   (label_ref <L>)
> 		   (pc)))
> 
> 	(set (reg) (mem (post_inc (<expr>))))
> 
> 	(code_label <L>)
> 
> can be written as
> 
> 	(if_then_else (~<cond>)
> 	 (set (reg) (mem (post_inc (<expr>)))
> 	 (const_int 0))
> 
> and that the side effect does not occur if the condition is false?

Yes.

> This would be at variance with the normal definition of if_then_else where it 
> is my understanding that side effects occur whichever arm is true (this is 
> required so that reload can move sub-expressions out of the insn).

Reload doesn't move arbitrary sub-expressions out of the insn,
only operands.  But you do have a point wrt post_incdec.

Actually, we may be ok here, but only by accident.  The plan we've
discussed is to do "small" if-conversion during early jump, as we
do now.  Small is probably limited to one or two instructions.

More aggressive if-conversion -- particularly for ports with lots
of predicate registers -- will happen after flow2.  The reason is
to let register allocation see the control-flow structure.

Since auto_incdec is generated during flow1, and there are no jump
passes between there and reload, we won't see something of the
form you describe above until the post-reload if-converters go to
work.  I can't think of any other reloading that would be unsafe
to do unconditionally.

> Hmm, how would the @pred work?

That's some stuff I'm currently working on in genrecog and genattrtab. 

The idea is that @foo magically generates a predicate for genrecog to
use that is true iff get_attr_foo is true.  This makes it easy to 
mark which instructions are or are not predicable.

> Or would there be some other way of describing whether an insn can
> be safely predicated?

You can use any method you can code up into a boolean function.
Using attributes is almost certainly going to be easier though.

> I'm assuming that it 
> wouldn't be necessary to have a pattern like this for every insn in the 
> description that can be predicated.

No.



r~

Re: Predicated execution

[Richard Henderson]

On Thu, Jan 13, 2000 at 10:45:52AM +0000, Richard Earnshaw wrote:
> How about a new type of insn, eg predicate_insn?  You could then convert 
> an insn to being predicated by just changing the wrapper.

I spent several weeks pondering options for representation of 
predicated execution.

I did consider this one.  As far as I can figure, this buys nothing
but a modicum of pain.  You now have to add code to all the places
that look at instruction types.

Using IF_THEN_ELSE at the top level is not something we currently see,
but for the limited handling lone instances need, does not affect the
majority of the optimizers. 

As for the somewhat intensive support needed in sched2 (for it to do
a good job anyway) one representation is as good as another -- all
that's needed is to be able to quickly get at the predicate.

So the way I see it is IF_THEN_ELSE wins by having the least effect
on parts of the compiler that don't care about predicated execution.



r~

Re: Predicated execution

[Richard Earnshaw]

rth@cygnus.com said:
> Reload doesn't move arbitrary sub-expressions out of the insn, only
> operands.  But you do have a point wrt post_incdec. 

Indeed.  But (subreg (mem ())) could be an operand.  For example

(set (reg:CC 24) (compare:CC (reg:SI 99) (const_int 0)))

(set (pc) (if_then_else (eq (reg:CC 24) (const_int 0))
			(label_ref (100))
			(pc)))

(set (reg:SI 101) (plus:SI (subreg:SI (mem:DI (reg:SI 99)) 0)
			   (const_int 5)))

(code_label 100)

with an addsi3 pattern of

(define_insn "*addsi3"
 [(set
   (match_operand:SI 0 "register_operand" "=r")
   (plus:SI (match_operand:SI 1 "register_operand" "r")
	    (match_operand:SI 2 "const_int_operand" "n")))]
 ...)


Predication would turn this into

(set (reg:CC 24) (compare:CC (reg:SI 99) (const_int 0)))

(if_then_else (ne (reg:CC 24) (const_int 0))
	(set (reg:SI 101) (plus:SI (subreg:SI (mem:DI (reg:SI 99)))
			   (const_int 5)))
	(const_int 0))

Now when it comes to reloading, reload must move the (subreg (mem())) out 
of the insn (since it isn't a valid register); but it must know that in 
this case the reloaded mem must be predicated as well (after all, the 
original test was effectively ensuring that the address was not NULL).

The above is completely different behaviour from trying to reload

(set (reg) (if_then_else (comparison)
		(plus (subreg (mem)) (const_int 5))
		(reg)))

Where we assume that side effects always occur so the mem can simply be 
moved out of the insn as required.

R.

BTW, it's always struck me as being somewhat odd that register_operand 
allows (subreg (mem)) -- yes, reload will fix it up; but since we know 
this needs doing, why do we not do it explicitly instead of hiding the 
intermediate register from CSE and (maybe) the register allocator.

Re: Predicated execution

[Michael Meissner]

On Fri, Jan 14, 2000 at 02:24:18PM -0800, Richard Henderson wrote:
> > Hmm, how would the @pred work?
> 
> That's some stuff I'm currently working on in genrecog and genattrtab. 
> 
> The idea is that @foo magically generates a predicate for genrecog to
> use that is true iff get_attr_foo is true.  This makes it easy to 
> mark which instructions are or are not predicable.

Note in general, I don't think you can use attributes until after reload, since
the attribute can be different based on the register class, etc.  For a machine
that provides predicated execution in all instructions (presumably like the
IA64) it might not matter.  However, there are machines out there that only a
subset of the instructions provided can be predicated, and you might not know
what you have until register allocation has been done.

> > Or would there be some other way of describing whether an insn can
> > be safely predicated?
> 
> You can use any method you can code up into a boolean function.
> Using attributes is almost certainly going to be easier though.
> 
> > I'm assuming that it 
> > wouldn't be necessary to have a pattern like this for every insn in the 
> > description that can be predicated.
> 
> No.
> 
> 
> 
> r~

-- 
Michael Meissner, Cygnus Solutions
PMB 198, 174 Littleton Road #3, Westford, Massachusetts 01886
Work:	  meissner@cygnus.com		phone: 978-486-9304 fax: 978-692-4482
Non-work: meissner@spectacle-pond.org

Re: Predicated execution

[Jim Wilson]

In article < 200001171817.SAA01821@cam-mail2.cambridge.arm.com > you write:
>BTW, it's always struck me as being somewhat odd that register_operand 
>allows (subreg (mem)) -- yes, reload will fix it up; but since we know 
>this needs doing, why do we not do it explicitly instead of hiding the 
>intermediate register from CSE and (maybe) the register allocator.

Historical error.  The code was added maybe 12 years or so ago.  It does do
something useful for CISCs.  (subreg (mem)) is a valid general operand, and
should be accepted by general_operand.  Unfortunately, making register_operand
accept it also was a mistake.

Tiemann noticed the mistake when he wrote the instruction scheduler, and tried
to fix it, but his fix is wrong also.  This was about 10 years or so ago.
Tiemann added the #ifdef INSN_SCHEDULING to general_operand that makes it
reject (subreg (mem)) if a port enables the scheduler.  This is right for
RISCs that use the scheduler, but is wrong for CISCs, and is wrong for
RISCs that don't use the scheduler.

I believe the right fix is to make general_operand and memory_operand accept
(subreg (mem)), because it is a valid general/memory operand.  Also,
register_operand should not accept (subreg (mem)), because it is not a valid
register operand.  This makes the INSN_SCHEDULING hacks in recog.c and
combine.c obsolete, and so they should be removed.  I've never had enough
motivation and time to try to fix this since I recognized that it was a
problem a year or two ago.

Jim