Newsgroups: comp.arch

Here is some data I've collected on the usefulness of
predication/nullification in PA-RISC.

Preston Briggs writes:

> (Dale Morris) posts:
> >  
> >    if(a==b)
> >      c--;
> >    else 
> >      d+=10;
> >  
> >  could be coded in PA instructions without any branches, as follows:
> >  (for clarity, let me assume that a,b,c, and d are already in registers
> >  1,2,3, and 4)
> > 	
> >  	sub,<>	r1,r2,r0	; compare a and b, nullify next if not equal
> >  	addi	-1,r3,r3	; c <- c-1
> >  	sub,=	r1,r2,r0	; compare a and b, nullify next if equal
> >  	addi	10,r4,r4	; d <- d+10
> 
> linley@hpcuhe.cup.hp.com (Linley Gwennap) writes:
> > Actually, the example can be coded in three instructions:
> > 
> >  	sub,<>	r1,r2,r0	; compare a and b, nullify next if not equal
> >  	addi,tr	-1,r3,r3	; c <- c-1, always nullify next instruction
> >  	addi	10,r4,r4	; d <- d+10
> > 
> > If a<>b, the first instruction nullifies
> > the second and executes the third.  If a==b, the second instruction is
> > executed, which nullifies the third.  Three cycles, no branches.
> 
> Can the compiler find either of these solutions from the source code?

I compiled this code:

foo(a,b,c,d)
int a,b,c,d;
{
  if(a==b)
    c--;
  else 
    d+=10;

  return(c+d);
}

using HP's 7.10 c compiler.  The newer 8.0 "snakes" c compiler gives the
same result.  (I added the return to prevent the optimizer from deleting the
entire procedure body.)  The compiler generated this code:

foo
        .PROC
        .ENTRY
        COMCLR,<>       26,25,0 ;offset 0x0
        ADDI,TR -1,24,24        ;offset 0x4
        LDO     10(23),23       ;offset 0x8
L$exit1
        BV      0(2)    ;offset 0xc
        ADD     24,23,28        ;offset 0x10
        .PROCEND ;in=23,24,25,26;out=28;


This is identical to what Linley posted.  (LDO, load offset, is essentially
an add immediate instruction.)  For an implementation with greater
instruction-level parallelism if this chained nullification were a problem,
the compiler could be easily changed to generate the code I suggested.  (I
offered that code rather than the 3 instruction sequence because I thought
it more clearly showed the feature, and because I didn't want people to
think that nullification would not map to superscalar/superpipelined/VLIW
implementations.)

The compiler does use nullification a lot.  Additionally, it is used
extensively in hand-coded libraries to good effect.

> Looks like lots of special-cases for the compiler to catch.
> Is there a general mechanism or are they handled via peephole
> optimization at the last second?  Or perhaps during instruction 
> scheduling?  Or at all?

There is a general mechanism in the compiler, both at the instruction
scheduling stage and later via peephole optimization.  For if-then
statements, the optimizer performs transformations that remove operations
from within the conditional execution portion of the graph.  This
frequently results in only a single instruction being covered by the
condition.  Other source code constructs map to nullification as well.

> How often are they used in practice, say across the SPEC benchmarks,
> versus ordinary conditional branches?

Here's some data from the 4 SPEC 1 integer benchmarks.  The numbers in the
first 3 rows are dynamic instruction counts expressed as a percentage of
total instructions executed.  The benchmarks were compiled with the snakes
8.0 compilers.

				  gcc  espresso eqntott   li
Conditional_Branches		 15.35	 21.82	 16.81	 14.78
Forward_Cond_Branches		 12.05	 13.43	  8.63	 11.38
Total_Predicates		  2.22	  1.43	 13.68	  1.25

(Total_Predicates / (Total_Predicates + Conditional_Branches)) * 100
				  12.6	   6.1	  44.9	   7.8

(Total_Predicates / (Total_Predicates + Forward_Cond_Branches)) * 100
				  15.6	   9.6	  61.3	   9.9

The counts for the conditional branches include taken and untaken.
Total_Predicates counts all arithmetic and shift instructions specifying a
nullification condition other than Never or Always.

With the last two rows, I'm trying to estimate the percentage of
conditional branches avoided.  Now, these might be a little high because
nullification might be repeated (as in my 4 instruction example earlier) to
cover more than 1 instruction.  On the other hand, the predicate counts do
not include nullification with the Always (,TR) condition.  Hence, Linley's
3 instruction example would count as only 1 predicate, but would take 1-2
conditional branches, dynamically, depending on the path taken.

The last row may be more interesting, since backward branches often
represent loop closures that cannot be mapped onto nullification.

Some data I've seen on these same benchmarks shows that newer compilers
(not yet released as products) are using nullification even more.

I picked a couple of random examples of predicated code generated by the
snakes 8.0 compiler.

The Eqntott Inner Loop
-----------------------------------------------
address  instruction
000043e4 LDHX,S	31(0,29),26
000043e8 EXTRS	25,31,16,25
000043ec EXTRS	26,31,16,26
000043f0 COMICLR,<>	2,25,0
000043f4 OR	0,0,25
000043f8 COMICLR,<>	2,26,0
000043fc OR	0,0,26
00004400 COMBT,=,N	25,26,00004418
00004404 COMBF,<,N	25,26,00004410		#probably mostly nullified
........
00004418 LDO	1(31),31
0000441c COMBT,<,N	31,23,000043e4
00004420 LDHX,S	31(0,24),25


Example in gcc
-----------------------------------------------------
This appears to a case statement selection -- index is in r14
000548cc  ADDI,<	-21,14,0		# range check part 1
000548d0  ADDI,<=	-40,14,0		# range check part 2
000548d4  B,N	00054efc			# out of range branch
000548d8  LDO	-21(14),23			# bias the index
000548dc  BLR	23,0				# and go


The usefulness of predication/nullification, like any architectural
feature, is workload/application dependent.

Obviously not all source-level conditional execution constructs will map to
nullification.  I certainly would not want to claim nullification as a
panacea; it does not permit you the luxury of doing a bad job on
conditional branches (hp still puts a lot of effort into optimizing
conditional branches), but it does help avoid some conditional branches,
and every bit helps.

[Credits to Jim Callister for the simulations - thanks Jim!]

------------------------------------------------------------------------------
Dale Morris	    |  Now is the time, and now is the record...
morris@iag.hp.com   |          of the time.
------------------------------------------------------------------------------