Balancing speed and instruction count
I came across an interesting bit of Altivec code [simdtech.org] on the Altivec mailing list [simdtech.org] today and I thought it would make a good example of how speed is not simply a matter of instruction count on the PPU and SPU.The function (modified slightly for this example):
vector unsigned short
test( vector unsigned short a, vector unsigned short b )
{
const vector unsigned short mask = (vector unsigned short)vec_cmplt( a, b );
if (vec_all_ge(a, b))
{
return (a);
}
return (mask);
}
Ingoring the function stack push/pop, we would have a very few instructions. Something like:
vcmpgtuh. v0, v3, v2
mfcr r0
rlwinm r0, r0, 27, 1
vcmpgtuh v0, v3, v2
cmpwi cr7, r0, 0
bne+ cr7, L2
vor v2, v0, v0
L2:
Ben Weiss [shellandslate.com] wrote this snippet to demonstrate that GCC does not optimize out redundant calls when Altivec instructions are called both with and without the CR-modify bit set. It's worth noting that this code (in the general case) will be a performance loss. Not only will there very likely be performance issues in these instructions themselves, but it will also affect the surrounding code by creating an optimization barrier.Read on to find out more about the issues and examine the alternative...
Tracing the redundant instruction
A problem with the emitted assembly above is that the "vcmpgtuh" is completely redundant. The "vcmpgtuh." already calculates the needed result. So why is it emitted?The predicate (CR modifying) Altivec instructions are mapped to their builtin descriptions in rs6000.c (gcc/config/rs6000)
static const struct builtin_description_predicates bdesc_altivec_preds[] =
{
{ MASK_ALTIVEC, CODE_FOR_altivec_predicate_v4sf, "*vcmpbfp.", "__builtin_altivec_vcmpbfp_p", ALTIVEC_BUILTIN_VCMPBFP_P },
{ MASK_ALTIVEC, CODE_FOR_altivec_predicate_v4sf, "*vcmpeqfp.", "__builtin_altivec_vcmpeqfp_p", ALTIVEC_BUILTIN_VCMPEQFP_P },
{ MASK_ALTIVEC, CODE_FOR_altivec_predicate_v4sf, "*vcmpgefp.", "__builtin_altivec_vcmpgefp_p", ALTIVEC_BUILTIN_VCMPGEFP_P },
{ MASK_ALTIVEC, CODE_FOR_altivec_predicate_v4sf, "*vcmpgtfp.", "__builtin_altivec_vcmpgtfp_p", ALTIVEC_BUILTIN_VCMPGTFP_P },
{ MASK_ALTIVEC, CODE_FOR_altivec_predicate_v4si, "*vcmpequw.", "__builtin_altivec_vcmpequw_p", ALTIVEC_BUILTIN_VCMPEQUW_P },
{ MASK_ALTIVEC, CODE_FOR_altivec_predicate_v4si, "*vcmpgtsw.", "__builtin_altivec_vcmpgtsw_p", ALTIVEC_BUILTIN_VCMPGTSW_P },
{ MASK_ALTIVEC, CODE_FOR_altivec_predicate_v4si, "*vcmpgtuw.", "__builtin_altivec_vcmpgtuw_p", ALTIVEC_BUILTIN_VCMPGTUW_P },
{ MASK_ALTIVEC, CODE_FOR_altivec_predicate_v8hi, "*vcmpgtuh.", "__builtin_altivec_vcmpgtuh_p", ALTIVEC_BUILTIN_VCMPGTUH_P },
{ MASK_ALTIVEC, CODE_FOR_altivec_predicate_v8hi, "*vcmpgtsh.", "__builtin_altivec_vcmpgtsh_p", ALTIVEC_BUILTIN_VCMPGTSH_P },
{ MASK_ALTIVEC, CODE_FOR_altivec_predicate_v8hi, "*vcmpequh.", "__builtin_altivec_vcmpequh_p", ALTIVEC_BUILTIN_VCMPEQUH_P },
{ MASK_ALTIVEC, CODE_FOR_altivec_predicate_v16qi, "*vcmpequb.", "__builtin_altivec_vcmpequb_p", ALTIVEC_BUILTIN_VCMPEQUB_P },
{ MASK_ALTIVEC, CODE_FOR_altivec_predicate_v16qi, "*vcmpgtsb.", "__builtin_altivec_vcmpgtsb_p", ALTIVEC_BUILTIN_VCMPGTSB_P },
{ MASK_ALTIVEC, CODE_FOR_altivec_predicate_v16qi, "*vcmpgtub.", "__builtin_altivec_vcmpgtub_p", ALTIVEC_BUILTIN_VCMPGTUB_P }
};
Then in altivec.h the predicate intrinsics e.g. vec_all_gte() directly call the builtins. There doesn't appear to be any RTL references to them at all. So the scheduler has no way of knowing the two instructions are related.For additional validation, examing the GCC debug output (*.34.sched2)
;; ======================================================
;; -- basic block 0 from 61 to 17 -- after reload
;; ======================================================
;; 0--> 61 %0=vrsave :nothing
;; 0--> 63 %12=%0|0xffffffffc0000000 :fxu_sim_cell
;; 2--> 62 [%1-0x4]=%0 :lsu_cell
;; 2--> 64 {vrsave=unspec/v[%12,vrsave] 30;clo:fxu_sim_cell
;; 4--> 14 {%6=unspec[%3,%2,`*vcmpgtuh.'] 175;:vus_cell
;; 6--> 25 %1=%2 :vus_cell
;; 8--> 16 %6=cmp(%6==0x0,0x0) :bru_cr_cell
;; 8--> 10 %0=unspec[%3,%2] 58 :vus_cell
;; 12--> 17 pc={(%6!=0x0)?L38:pc} :bru_cell
To enable debugging output in GCC, add the -dall compilation flag. For more information on the GCC debugging options see: Options for Debugging Your Program or GCC [gnu.org]
*.34.sched2 represents the final pass of the compiler and it would seem from this line
;; 4--> 14 {%6=unspec[%3,%2,`*vcmpgtuh.'] 175;:vus_cell
that "vcmpgtuh." is pretty much a text replacement.
Based on this, don't expect any of the Altivec instructions with the CR modify bit set to fold with the plain version under any conditions.
In addition to the various other reasons for avoiding the CR modifying Altivec instructions, this is a good reason to:
Avoid CR-modifying Altivec instructions (vec_any_*, vec_all_*)
What are the other problems?
On closer examination, these few lines of code have quite a few potential performance issues.
vcmpgtuh. v0, v3, v2
The "vcmpgtuh." instruction modifies the Condition Register (CR). This could cause problems because the Vector Execution Unit (VXU) must contend with the Floating Point Unit (FPU) and the Fixed Point Execution Unit (FXU) for access to the 32 bit CR. It would be resonable to expect that under fairly common conditions, this would cause a pipeline bubble.Another disadvantage to modifying the CR is the added difficulty in instruction scheduling. The CR is a very scarce resource and the options the compiler has for moving the code (to maximize throughput) is now more reliant on the availability of the 4 bits of the CR needed to store this result than the actual instruction throughput or latency.
mfcr r0
rlwinm r0, r0, 27, 1
In order to free the Altivec modified field in the condition register, the value is moved to a fixed-point register (mfcr). The CR value must also be shifted in order to create a predicate value. In this case, the "vcmpgtuh." doesn't just lock the condition register, but also takes resources from the fixed-point unit.
bne+ cr7, L2
The first problem with introducing this branch instruction is that it creates an optimization barrier for the compiler. Although sometimes possible, it is very difficult to lift code from inside a branch target and schedule it with code in another block. And GCC is especially weak at this particular optimization.
vor v2,v0,v0
The "vor" instruction simply takes the result in the default case and moves it to the return register. By itself, there is very little lost, but in this context the instruction must wait the full latency of the compare instruction in the best case, and for a full pipeline flush in the worst case, in order to execute. And because the branch introduces an optimization barrier, there is very little oportunity to schedule instructions during that period.What's the alternative?
Simply put - remove the branch.Here is one possible implementation:
const vector unsigned int zero = vec_xor( a, a );
const vector unsigned short mask_lt = vec_cmplt( a, b );
const vector unsigned short mask_e0 = vec_sld( mask_lt, mask_lt, 8 );
const vector unsigned short mask_e1 = vec_sld( mask_lt, mask_lt, 12 );
const vector unsigned short mask_e2 = vec_and( mask_lt, mask_e0 );
const vector unsigned int mask_e3 = (vector unsigned int)vec_and( mask_e2, mask_e1 );
const vector unsigned short mask_all_ge = (vector unsigned short)vec_cmpeq( mask_e3, zero );
const vector unsigned short result = vec_sel( a, mask_lt, mask_all_ge );
Which generated the following results for ppu-gcc (3.4.1) (-O3)
vspltish v0, 0
vcmpgtuh v3, v3, v2
vor v13, v2, v2
vsldoi v2, v3, v3, 8
vsldoi v1, v3, v3, 12
vand v2, v3, v2
vand v2, v2, v1
vcmpequw v2, v2, v0
vsel v2, v13, v3, v2
Examine the difference in complexity between the original and branch-free version of this function:
Original:
Branch-free:
Result
Although the branch-free code emits a slightly longer sequence,
the final complexity is lower (notice that there is only a
simple, single path - which was, of course, the point.)
About the author
Mike Acton is a Senior Architect working on PS3/Cell research at Highmoon Studios (Vivendi-Universal Games) who occasionally refers to himself in the third person. Most recently, Mike was the Lead Special Effects Programmer for Darkwatch at Highmoon Studios (previously Sammy Studios) in Carlsbad, CA. Previously Mike has held Lead Programming, Playstation 2 Engine Development and Research roles with Yuke's, VBlank and BlueSky/Titus. He worked for Sony Interactive Studios in PSX development. Mike has made regular appearances as a speaker at SCEA develpment conferences and has spoken at GDC. Mike Acton is not a framework-happy C++ programmer. He actually likes C. And assembly. In his spare time he develops hardware on FPGAs in VHDL.
He prefers vi.
Also check out the non Cell BE articles by Mike Acton.