ѧ
JOURNAL OF SOFTWARE
2000Vol.11No.2P.187-194



ü㺯ģǿ
갱촫
ժҪȷ,Ҫ֧߼.Ϊ˼Чش֧,˶Ӧڳεļ㺯ģ,ڸģʾ֧߼,Ĳȷⷽ,԰ͨҪ߼תΪռ֮串ǹϵж.ڲлۺʵбȽϳĽ취.
ؼʣ㺯ģ,,֧,Omega.
ţTP314
Enhancing Dataflow Analysis with Computation Function Model
HU Shi-liangZANG Bin-yuZHU Chuan-qi
(Institute of Parallel Processing Fudan University Shanghai 200433)
AbstractA precise dataflow analysis should effectively exploit the semantic information presented by conditional branch statements.Most traditional systems,however,either ignore the logical conditions,or try hard to handle logical conditions with logical reasoning which is rather difficult and infeasible for paralleling systems.With the aim to solve this problem efficiently and effectively,the authors introduce the computation function model and then successfully convert the logical reasoning problems into problems of deciding the coverage relationship of Omega regions which are substantially more feasible to be solved by contemporary paralleling compilers.
Key wordsComputation function model,dataflow analysis,conditional branch statement,omega region.
ԲǲлǱڲԵҪ.ʵ֤,ڲлѧ,Ѿȡ˹ĳɹ1.Ȼڵ֮һ,еķ֧߼,ԳֿǱڲ.
лҪȲ.ҪлĴǳмִʱռִʱ൱Ĺؼ.Ʋʵͳƶ,Ӧóй㷺ֵ֧,ػӰڳؼεĲԷ.Ч֧ṩϢ,ôԳؼεĲԷͻڱ,ʧмľ޴.
ͳ2,3ݲط̵ļ,֧߼Ժ.ף4ݵڷ˳ԶлȻڵҪΪ,֧߼ڱ.ף5ôνʵķűʾ,ʵWolfeĦ-functionʾ.,ף6Guarded Array Region.Ƕͼνʵʩ߼ȷϢ.ź,걸Զ߼ϵͳ,ʵ̫,ɵʵûĲлﲢʵ.Ӧļ㺯ģ,ͼΪҵһּ򵥶ЧĽ.
,߼ͼ㺯ģͬһڲͬѧģµıʾ.㺯ģ߼ĺô:ϵļࡢͳһ,ģعе串ǵĸͳһĻĶ-ϵ,ıࡢͳһ;ϵͳʵ.ϵļࡢͳһʹʵڼϵͳϵع,Ŀ߼ϵͳ.
ĵ1ֽļ㺯ģ.2ֲģ֧.3͵4øģͽ֧Ҫ.ó.
֧ʽ,C/C++,Java,FORTRAN,PascalȳгֵĸIF䡢Switch䡢case,IFֵΪ㷺,Լ:ᵽIF֧京ȼ,,ԼбǷźص,1.
Table 1 Conventions for some symbols
1 йصķԼ

SymbolNameExplanation
PProgram segmentA segment of program (in Fortran,C etc.)
r\wRead/write referenceRead /write reference to a variable (including array)
x,XReference,reference setReference to a variable (x can be r,ri,w,wi)
RP\WPRead/write setAll read/write reference to the inspected
variable in the program segment P
NaWrPNon anti-dependence write setThe non anti-dependence write
set of r in the program segment P*
SetP(x)Reference element setThe set of all array elements or variables referred by x in program segment P (the set is null when x isn't in the program P)


ٷ,,۽,ܳ,һαĳ,޶/д,߶Ա(,ͬ)Ķ/д,,ü,Ա(xȡֵΪr,ri,w,wi) /д,PжԱж/д,޷д,Pйr޷д,Ԫؼ,xPõб,Ԫصļ(x)PʱΪռ.
1 ļ㺯ģͼصĻ
ڿɼ,κγ򶼿Ϊһݿռ䵽ݿռĺӳ.m,nֱΪ롢ռά,ôӦӳ:(m)P:ZmZn.ͬ,,ڵǰĳP,ҲԲֺӳʽĳģ.
1.1 ļ㺯ģ
1.1.PĶIn(P)={x1,x2,...,xm}ʾPִʱ,֮ǰPδбļ,PĶΪ:Dom(P)=Dx1Dx2...Dxm.
1.2.PӳOut(P)={y1,y2,...,yn}ʾPִʱ,ұֶõı,PֵΪ:Range(P)=Dy1Dy2...Dym.
,DxixiĶ,DyiyiĶ.
1.3.Pļ㺯ģͶΪֵӳ:fP:Dom(P)Range(P).
,(subarray)Ϊһı,±ԪΪһͨ.ЩжԼνʦ(x1,x2,...,xm),ʱ,PĶӦ:
Dom(P)={(x1,x2,...,xm)|(x1,x2,...,xm)=True}.
Ϊ㺯ģ͵ĻϽ,ǻĳִзʽ.
ȷִм ڳPеκȷһ(ӦųPһʵִ):(x1,x2,...,xm)Dom(P),Pִȫȷ,ȷ԰:
PIn(P)={x1,x2,...,xm}Out(P)={y1,y2,...,yn}ȷ;
POut(P)={y1,y2,...,yn}еֵҲȷ.PȷԵĳ,fPϸѧµĺӳ;
֧תȷ.
ȷִмǺŻҪ,ҳĳһ㶼.
1.2 ȷԸ
1.4.AIn(P),A,Aеıڲִͬʵвͬȡֵʱ,In(P)Out(P)ҲڸʵĺִȡֵΪͬı,ƳPȷ.AеıֲȷԵı,ڱҪзŷ,ǳ֮Ϊؼֵű.
ǳƳPȷΪȷ,ȷҪ֧䡢ָȲ;ҲĳЩؼֵĲȷԼDOĵΧȵ.ֱ,PĳЩǷ˶дһ߼½е,дķΧĳЩֵĲȷȷ.
ȷʱ,ڱ˵,ľֵȷ,֮Ϊֵȷ.ֵȷԿɱʽ֧䡢ֵȵ.ֱۺ:PĶдȷ,Pоֵӳϵȷ.
ȷִм,ϢĲȷԴԳݵĲȷ(Dom(P)еκһ),ṹĸӶȳķ.
κγPΪĳɼ㺯fʵ,ǲһͬfȼ۵ӳfoptimized:fDom(P)ȫֵͬӦϵ,ֻfoptimizedиʺڵײģ͵ļṹԻȡ.ӳfľʵʩ,ľֵ,ֵȷԶԱ;ȷζűֵڳеĴݹϵȷ(㺯ĸϹϵȷ),Ǳڳṹʶⲻȷ.,ȷԶڱǹؼ.ڶԳһֲвԵķ任ʱ,Ҫʶ,ʱ̿ȷȷ,ԱڱʵļԼ²лŻ.,ֻڲȷԵĿܷΧصļ.
1.3 νڼ㺯ģµ
ڼ㺯ģ,Pκ֧ν,ھһı滻󶼶ӦDom(P)һض(κԼΪDom(P)).
Predicate(t1,t2,...,tk)֧е߼,t1,t2,...,tkֱӳֵı,ôPredicate(t1,t2,...,tk)=TrueȷDT=Dt1Dt2...DtkռеһT,ɳдPĶt1,t2,...,tkһϵиֵ䡢ʽȷӳϵ::(x1,x2,...,xm)(t1,t2,...,tk)֪,DTDom(P)һռ.P=-1(T)ʾPĶ,ִ֧еĳ״̬ռ.TʾڲռDT.ĦP=-1(T)±ʾ:
P={(x1,x2,...,xm)|(x1,x2,...,xm)Dom(P);(x1,x2,...,xm)=(t1,t2,...,tk)ʦT}.
ʵ,νp(x1,x2,...,xn)ǳ״̬ռеضռ㼯P.
p(x1,x2,...,xn)(x1,x2,...,xn)ʦP,(x1,x2,...,xn)Dom(P).
1.5.ԳPеνPredicate(t1,t2,...,tk)Ϊ,PĶDom(P)=Dx1Dx2...DxmȷĿռPԼбʾDom(P)ĵռDT=Dt1Dt2...DtkеTΪνʵOmega,ΪPredicateP,ڲʱ,ΪPredicate.
1.1.Pе߼νp(x1,x2,...,xn)ȷOmegaΪp,:

֤ƽ,.
1.2.ǹڳ߼νʼ,еνΪɵĦļ,㼯ϵͳ;-,,ȣ̬ͬ߼ϵͳ.
1.1֪,ӳ:ϵ̬ͬӳ,֤.
1.11.2,֧,߼νʶӦOmega,໥ĸǹϵӦ߼ν֮߼ϵ,,㺯ģ͵,԰߼任Ϊռ֮串ǹϵж.
߼νʼӦOmegaڱʾʽһµ,ǹڳĵʽ򲻵ʽ.ϵϵͳǲͬ,򸲸ǵķмں,ʵ.жOmega֮ĸǹϵʱ,ûбҪѱȫ滻ΪPĶ,ֻOmega򻮵ͬһռ伴.ף5һ𲽷ı滻.ʵó,رǿѧĳķͳƱ,֧߼νȷռ͹,͹аһŲ㼯.򡢵㼯ļ㴦(Բʽ)ڲлʵѾȽϳ.
FORTRANCԳ,ĳPǳеĸʵ:ĳӳĳ롢DOѭ,һʽ.ͳһĿƳһͳһĴ,ȿԾоֲЧ,ֿԽȫֵ̳ͨﻮ.
2 㺯ģ֧
֧һʽ:
ifif
[]P1B1;[]P1B1;
[]P2B2;[]P2B2;
...or...
[]PnBn;[]PnBn;
fifi
B1,B2,...,BnִеĲȷԵ˳ݶдĲȷ,ֲȷɸִBiǰνPi.Piȫȷ,ᵼ²ȷ.
2.1 ֧Ա
赱ǰĳP,֧бÿ¼.
.ֵȷԶ(д) μͼ1ͼ2еʾ,Ϊһ,εждȷ,ֵȷ.ʱ,IFڱǼʽһ,Ҫͼڲͬ¸ֵͬ.֧ĴòӰļṹ(ıֵIFʽDO½ʽ±ʽ)ʱ,԰Ϊһֱʽ.֧µĶӰļṹʱ,ֵȷԶǷű,Ҫзŷ.ǲıǱʾ:,ЦPνpOmega,wʾд/,ExpValʾӦļʽ.

Fig.1Fig.2
ͼ1ͼ2
.ȷԶ(д) μʾ.IFǱ,ر(array region)һµд.߼ĲȷݶùϵĲȷ,е߼尵ʾ˳ṹԼϵ.ӦԱΪ:.
֧ȷʾ:
1DO K=2,5,1
2ݡIF (RS(4+K).LE.CUT2) THEN
3ݡRL(4+K)=SQRT(RS(4+K))
4ݡENDIF
5ENDDO
6IF (KC.EQ.0) THEN
7ݡDO K=11,14,1
8ݡFF((-5)+K)=FF((-5)+K)+AB2*EXP(-B2*RL(K-5))/RL((-5)+K)
9ݡENDDO
10ENDIF
Ƿ塢RL(6:9)ǲȷ.
ȷһֵȷ,ֵȷԶȷԶڵǰP,ڳPȷԵĶһĳΧڿܻΪֵȷԶ,֮Ȼ.֧ǳ̵Ҫ,֧ڱòܼ򵥵֧ͨĴʷ﷨õ,ҪһΧڵ,ȷ.
2.2 ֧Աõ
֧ڱõ,öһ߼½е,ǳ֮Ϊ().Ӧ߼ȷOmegaǸö÷ĳ״̬,Ҳⶨ-֮ȷԵĹؼ.ڼ㺯ģ±ʾΪ

2.3 ֧Ĵ
֧䵼µĵֵȷԶԺ.ڿѧ൱һֵ֧ȷԶ,ֺԿԴļ.֧µķű,Ӧ跨Ʋֵ.ʱ,ֵϢᵼϢ.ĵ4ֽü㺯ģ͸ŷе߼.
ȷԶĴ.е߼ж-,ʱ̿ȷĲȷ.֤ĸǶǰܵOmega֮ĸǹϵ.Ҫָ,ೡµȷǲھ̬ȷ,,Ƕ̬ȷϵ.
3 ü㺯ģĲȷ
3.1 ȷҪ
ȷõԴԵóεϢಢлŻ任ǰ.,֧޶µûkillд,ǸöǰʵĶ,ɴ˵˶öͬһ洢ĶȡܶPǰʵ֮Ķ,ȷ.ֲȷζؽԴĿ,ڱ.
ڼ㺯ģ͵Ŀ¿԰Ϊ:һr:(ʾڼ㺯ģ,ͬ)ԼΪrṩԴĶ㼯,ȷWr֮ϵ.
ضA,οԼ򵥵Ƴ.PκθǶµĽṹ.
3.2 ȷԭ
3.1.дǶ.ڳPеһԶдr,w(дW),Pκִʵ:дִڶr֮ǰִвrݼдw(дW)Ķݼ,仰˵,дw(дW)ȫr,дw˶r(дW˶r),Ϊ:
.
3.1.PеһԶдr,w:wNaWrP,:
rw and SetP(r)SetP(w),
ô,дw˶r,.
֤:ڦrw,Pִжrʱ,дwҲһִе,SetP(r)SetP(w)֪,wr֮һ,,ҲǷ,:wNaWrP,wr֮ڵһ,дȫrṩ,:.
,wκͬrصд,wrȷԴ.
ݼռDataSpace ΪݱĴ洢ԪɵĴ洢ռ.SDataSpaceǱSһ洢Ԫռ;ADataSpaceAdim(A)ά洢ռ,½˵ṩ;PDataSpaceɳPб,ȫ,ɵĴ洢ռ.Ҫ漰DataSpace.
Ϊ˵дǶĳҪ,ҪOmegaĵѿ.״̬ռͳݼռĵѿ:Dom(P)DataSpaceеһض:xSetP(x).ֱ:P㦸xĳ״̬SetP(x).
3.2.Px״̬-,Ʀ,Ϊ:
xP=xPSetP(x).
xPʾڳPΧԼxOmega,ڲʱΪx,xPҲΪP(x).:.
3.2(Ƕ).ڳPеĶrдW:WNaWrP,ĳҪ:״̬-д״̬-֮:,.
֤::Ƴ.
Pκһִеrʱ,Ӧĳ״̬Ϊ:sʦr.Դ洢κһXSetP(r)ñض:
wW,ʹsʦwXSetP(w)(:ì).XSetP(r)XSetP(w),wr֮һ,,ҲǷ,:wWNaWrP,wr֮ڵһ.дǶĶ,Ե֤.
Ҫ:Ƴ.
֤:(s,XʦrP),ɸǵĶ,PsõXʱ,W޷r,費.ɼҪԳ.
1.PеһԶдr,w:wNaWrP,:
(rSetP(r))(wSetP(w)),
ô,дw˶r,.
2.rΪPеĶ,,ô,rΪPеķǱ¶.
3.ڳPеĶRдW::
,еĳҪɸǶȷ:.
1Ƕ3.1һֱʾʽ,2Ӧ˽лж,3ǸǶһֹʽ.
ɸǶ,ǿȷPضĶ㼯ܷPжr:.
4 ü㺯ģ͸ŷ
4.1 ֧ڷŷӰ
ŷھȷԲʮҪ.űһǱ,ȷЩֵʹӾȷϢ.
ڼ㺯ģ,֧ﶨķű,ֵȷԿԱʾΪ:

ȷִм֪,p1,...,pn,otherDom(P)һ.
ӦҪ:һؼֵSymbolĶR:ԼSymbolܵȡֵ:

ȷRʵʶȡSymbolֵ.
4.2 ü㺯ģֵĲȷ
ʵ,ֵȷԺȷԭһµ,ǿԵóĽ.ڳPһԹؼֵSymbolĶR:,RܹExpVali,һ㦸prɦpi.ر,prpi,RһExpVali,,Rһ{ExpVali|iD}еĳֵ.
֤ȷԵ,.
5  
κͼ֧߼õȷϢķ,϶ڲͬģ,߼бʾ.ڼ㺯ģ͵Ŀ,֧Ȼرʾ,ʽΪ:,ڸϵһع;֧µӦϢҲͨдõĦȷ.ıʾͼ㷽ʽĿǰõķʽһ,ʵֻϵͳ,һϵͳ.
ñĲȷԭ,ֹͨʽ任PERFECT Club Benchmarks,SPEC95fpȲԳʵó,ķЧ.һĹǽ㷨,Աڲлʵ.
ĿоõȻѧ(No.69633030)863߿ƳĿ(No.863-
306-ZT01-02-01)ѧĿ͹Ƽصʵһ
(No.97JS76.5.2JW0701).
߼飺1972,˶ʿ,ҪоΪֲ.
갱,1965,,ҪоΪд,ܼ.
촫,1943,,ʿʦ,ҪоΪд,ܼ.
ߵλ(ѧдо Ϻ 200433)
갱(ѧдо Ϻ 200433)
촫(ѧдо Ϻ 200433)
οף
1Zhu Chuan-qi,Zang Bin-yu,Chen Tong.An automatic parallelizer.Journal of Software,1996,7(3):180186
(촫,갱,ͮ.ԶлϵͳAFT.ѧ,1996,7(3):180186)
2Mary W Hall,Murphy B R,Amarasinghe S P et al.Interprocedural analysis for parallelization.In:Huang C-H et al eds.Proceedings of the 8th International Workshop on Languages and Compilers for Parallel Computing.Columbus,Ohio:Springer-Verlag,1995.6174
3Beatrice Creusillet,Francois Irigoin.Interprocedural array region analysis.In:Huang C-H et al eds.Proceedings of the 8th International Workshop on Languages and Compilers for Parallel Computing.Columbus,Ohio:Springer-Verlag,1995.4660
4Peng Tu,David Padua.Automatic array privatization.In:Proceedings of the 6th International Workshop on Languages and Compilers for Parallel Computing.Springer-Verlag,1993.500521
5Peng Tu,David Padua.Gated SSA-based demand-driven symbolic analysis for paralleling compilers.In:Michael Wolfe,Denis Nicole et al eds.Proceedings of the 1995 International Conference on Supercomputing.Bacelona:ACM Press,July 1995.414423
6Trung Nguyen,Gu Jun-jie,Li Zhi-yuan.An interprocedural paralleling compiler and its support for memory hierarchy research.In:Huang C-H et al eds.Proceedings of the 8th International Workshop on Languages and Compilers for Parallel Computing.Columbus,Ohio:Springer-Verlag,1995.90104
ոڣ1998-09-21
޸ڣ1999-03-09
