1、Autovectorization in GCC,Dorit Naishlos ,2,Vectorization in GCC - Talk Layout,Background: GCC HRL and GCC,Vectorization Background The GCC Vectorizer Developing a vectorizer in GCC Status & Results Future Work Working with an Open Source Community Concluding Remarks,3,GCC GNU Compiler Collection,Ope
2、n Source Download from gcc.gnu.orgMulti-platform 2.1 million lines of code, 15 years of development How does it work cvs mailing list: gcc-patchesgcc.gnu.org steering committee, maintainers Whos involved Volunteers Linux distributors Apple, IBM HRL (Haifa Research Lab),4,GCC Passes,machine descripti
3、on,C front-end,Java front-end,C+ front-end,parse trees,int i, a16, b16 for (i=0; i 16; i+)ai = ai + bi;,int i; int T.1, T.2, T.3;i = 0; L1:if (i 16) break;T.1 = ai ;T.2 = bi ;T.3 = T.1 + T.2;ai = T.3;i = i + 1;goto L1; L2:,int i_0, i_1, i_2; int T.1_3, T.2_4, T.3_5;i_0 = 0; L1: i_1 = PHIif (i_1 16)
4、break;T.1_3 = ai_1 ;T.2_4 = bi_1 ;T.3_5 = T.1_3 + T.2_4;ai_1 = T.3_5;i_2 = i_1 + 1;goto L1; L2:,GIMPLE:,SSA,5,GCC Passes,GCC 4.0,6,GCC Passes,The Haifa GCC team: Leehod Baruch Revital Eres Olga Golovanevsky Mustafa Hagog Razya Ladelsky Victor Leikehman Dorit Naishlos Mircea Namolaru Ira Rosen Ayal Z
5、aks,machine description,Fortran 95 front-end,IPO CP Aliasing Data layout,Vectorization,Loop unrolling,Scheduler,Modulo Scheduling,Power4,7,Vectorization in GCC - Talk Layout,Background: GCC HRL and GCC,Vectorization Background The GCC Vectorizer Developing a vectorizer in GCC Status & Results Future
6、 Work Working with an Open Source Community Concluding Remarks,8,Programming for Vector Machines,Proliferation of SIMD (Single Instruction Multiple Data) model MMX/SSE, Altivec Communications, Video, Gaming Fortran90 a0:N = b0:N + c0:N; Intrinsicsvector float vb = vec_load (0, ptr_b);vector float vc
7、 = vec_load (0, ptr_c);vector float va = vec_add (vb, vc); vec_store (va, 0, ptr_a); Autovectorization: Automatically transform serial code to vector code by the compiler.,9,a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,OP(a) OP(b) OP(c) OP(d),Data in Memory:,VOP( a, b, c, d ),VR1,What is vectorization,Vector Reg
8、isters,Data elements packed into vectors Vector length Vectorization Factor (VF),VF = 4,Vector operation,vectorization,10,Vectorization,original serial loop: for(i=0; iN; i+) ai = ai + bi; loop in vector notation: for (i=0; iN; i+=VF) ai:i+VF = ai:i+VF + bi:i+VF; ,loop in vector notation: for (i=0;
9、i(N-N%VF); i+=VF) ai:i+VF = ai:i+VF + bi:i+VF; for ( ; i N; i+) ai = ai + bi; ,vectorization,Loop based vectorization No dependences between iterations,vectorized loop,epilog loop,11,Loop Dependence Tests,for (i=0; iN; i+) for (j=0; jN; j+) Ai+1j = Aij + X,for (i=0; iN; i+) Di = Ai + Y Ai+1 = Bi + X
10、 ,for (i=0; iN; i+) Bi = Ai + Y Ai+1 = Bi + X ,12,Loop Dependence Tests,for (i=0; iN; i+) for (j=0; jN; j+) Ai+1j = Aij + X,for (i=0; iN; i+) Ai+1 = Bi + X,for (i=0; iN; i+) Di = Ai + Y,for (i=0; iN; i+) Ai+1 = Bi + X Di = Ai + Y ,for (i=0; iN; i+) Di = Ai + Y Ai+1 = Bi + X ,for (i=0; iN; i+) Bi = A
11、i + Y Ai+1 = Bi + X ,13,Classic loop vectorizer,dependence graph,int exist_dep(ref1, ref2, Loop) Separable Subscript testsZeroIndexVar SingleIndexVar MultipleIndexVar (GCD, Banerjee.) Coupled Subscript tests (Gamma, Delta, Omega),find SCCs reduce graph topological sort for all nodes:Cyclic: keep seq
12、uential loop for this nest. non Cyclic:,for ifor jfor kA5 i+1 j = AN i k,for ifor jfor kA5 i+1 i = AN i k,replace node with vector code,loop transform to break cycles,14,Vectorizer Skeleton,get candidate loops nesting, entry/exit, countable,scalar dependences,vectorizable operations data-types, VF,
13、target support,vectorize loop,known loop bound,1D aligned arrays,Basic vectorizer 01.01.2004,idiom recognition,invariants,saturation,conditional code,for (i=0; iN; i+)ai = bi + ci; ,li r9,4 li r2,0 mtctr r9 L2:lvx v0,r2,r30lvx v1,r2,r29vaddfp v0,v0,v1stvx v0,r2,r0addi r2,r2,16bdnz L2,arrays and poin
14、ters,unaligned accesses,force alignment,mainline,15,Vectorization on SSA-ed GIMPLE trees,int T.1, T.2, T.3;loop:if ( i 16 ) break; S1: T.1 = ai ; S2: T.2 = bi ; S3: T.3 = T.1 + T.2; S4: ai = T.3; S5: i = i + 1; goto loop;,loop: if (i 16) break;T.11 = ai ;T.12 = ai+1;T.13 = ai+2; T.14 = ai+3; T.21 =
15、bi ;T.22 = bi+1;T.23 = bi+2; T.24 = bi+3;T.31 = T.11 + T.21;T.32 = T.12 + T.22;T.33 = T.13 + T.23;T.34 = T.14 + T.24; ai = T.31;ai+1 = T.32;ai+2 = T.33;ai+3 = T.34;i = i + 4;goto loop;,VF = 4,“unroll by VF and replace”,int i; int aN, bN; for (i=0; i 16; i+)ai = ai + bi ;,v4si VT.1, VT.2, VT.3; v4si
16、*VPa = (v4si *)a, *VPb = (v4si *)b; int indx;loop:if ( indx 4 ) break;VT.1 = VPaindx ;VT.2 = VPbindx ;VT.3 = VT.1 + VT.2;VPaindx = VT.3;indx = indx + 1; goto loop;,16,a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,OP(c) OP(d) OP(e) OP(f),Data in Memory:,VOP( c, d, e, f ),VR3,Alignment,Vector Registers,c,d,e,f,misa
17、lign = -2,Alignment support in a multi-platform compiler General (new trees: realign_load) Efficient (new target hooks: mask_for_load) Hide low-level details,(VR1,VR2) vload (mem) mask (0,0,1,1,1,1,0,0) VR3 pack (VR1,VR2),mask VOP(VR3),17,Handling Alignment,Alignment analysis Transformations to forc
18、e alignment loop versioning loop peeling Efficient misalignment support,for (i=0; iN; i+)x = qi; /misalign(q) = unknownpi = x; /misalign(p) = unknown ,Loop versioning: if (q is aligned) for (i=0; iN; i+)x = qi; /misalign(q) = 0pi = x; /misalign(p) = -2 else for (i=0; iN; i+)x = qi; /misalign(q) = un
19、knownpi = x; /misalign(p) = -2 ,Loop peeling (for access pi): for (i = 0; i 2; i+)x = qi;pi = x; for (i = 2; i N; i+)x = qi; /misalign(q) = unknownpi = x; /misalign(p) = 0 ,Peeling for pi and versioning: for (i = 0; i 2; i+)x = qi;pi = x; if (q is aligned) for (i = 3; iN; i+)x = qi; /misalign(q) = 0
20、pi = x; /misalign(p) = 0 else for (i = 3; iN; i+)x = qi; /misalign(q) = unknownpi = x; /misalign(p) = 0 ,-2,vector *vp_q = q; vector *vp_p = p; int indx = 0, vector vx; LOOP:vx1 = vp_q1indx;vx2 = vp_q2indx;mask = target_hook_mask_for_load (q);vx = realign_load(vx1, vx2, mask)vp_pindx = vx;indx+;,vx
21、= vp_qindx;,vector *vp_q1 = q, *vp_q2 = ,int indx = 0, vector vx, vx1, vx2;,Aart J.C. Bik, Milind Girkar, Paul M. Grey, Ximmin Tian. Automatic intra-register vectorization for the intel architecture. International Journal of Parallel Programming, April 2002.,18,Vectorization in GCC - Talk Layout,Bac
22、kground: GCC HRL and GCC,Vectorization Background The GCC Vectorizer Developing a vectorizer in GCC Status & Results Future Work Working with an Open Source Community Concluding Remarks,19,Vectorizer Status,In the main GCC development trunk Will be part of the GCC 4.0 release New development branch
23、(autovect-branch) Vectorizer Developers: Dorit Naishlos Olga Golovanevsky Ira Rosen Leehod Baruch Keith Besaw (IBM US) Devang Patel (Apple),20,Preliminary Results,Pixel Blending Application - small dataset: 16x improvement - tiled large dataset: 7x improvement - large dataset with display: 3x improv
24、ement for (i = 0; i 8 + (input2i * (-1)8 ); SPEC gzip 9% improvement for (n = 0; n = WSIZE ? m-WSIZE : 0); Kernels:,lvx v0,r3,r2 vsubuhs v0,v0,v1 stvx v0,r3,r2 addi r2,r2,16 bdnz L2,21,Performance improvement (aligned accesses),22,Performance improvement (unaligned accesses),23,Future Work,Reduction
25、 Multiple data types Non-consecutive data-accesses,24,1. Reduction,Cross iteration dependence Prolog and epilog Partial sums,s = 0; for (i=0; iN; i+) s += ai * bi; ,loop: s_1 = phi (0, s_2) i_1 = phi (0, i_1) xa_1 = ai_1 xb_1 = bi_1 tmp_1 = xa * xb s_2 = s_1 + tmp_1 i_2 = i_1 + 1 if (i_2 N) goto loo
26、p,25,2. Mixed data types,short bN; int aN; for (i=0; iN; i+) ai = (int) bi; Unpack,26,3. Non-consecutive access patterns,a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,OP(a) OP(f) OP(k) OP(p),Data in Memory:,VOP( a, f, k, p ),VR5,a,f,k,p,a,f,k,p,a,f,k,p,Ai, i=0,5,10,15,; access_fn(i) = (0,+,5),(VR1,VR4) vload (mem
27、) mask (1,0,0,0,0,1,0,0,0,0,1,0,0,0,0,1) VR5 pack (VR1,VR4),mask VOP(VR5),27,Developing a generic vectorizer in a multi-platform compiler,Internal Representation machine independent high level Low-level, architecture-dependent details vectorize only if supported (efficiently) may affect benefit of v
28、ectorization may affect vectorization scheme cant be expressed using existing tree-codes,28,Vectorization in GCC - Talk Layout,Background: GCC HRL and GCC,Vectorization Background The GCC Vectorizer Developing a vectorizer in GCC Status & Results Future Work Working with an Open Source Community Con
29、cluding Remarks,29,Working with an Open Source Community - Difficulties,Its a shock “project management” ? No control Whats going on, whos doing what NoiseCulture shock Language Working conventions How to get the best for your purposes Multiplatform Politics,30,Working with an Open Source Community
30、- Advantages,World Wide Collaboration Help, Development Testing World Wide Exposure The Community,31,Concluding Remarks,GCC HRL and GCC Evolving - new SSA frameworkGCC vectorizer Developing a generic vectorizer in a multi-platform compiler Open,GCC 4.0 http:/gcc.gnu.org/projects/tree-ssa/vectorization.html,32,The End,
