ѧ
JOURNAL OF SOFTWARE
1999 6 10 Vol.10 No.6 1999



ָĹڱ*
 갱һ촫
ժҪָCԵĲŻռҪĵλ,еָָֻܴ.ڽָϢʾĲĻ,һܹʾָϢıʾ,Ը׼ȷرʾָϢ.ڴ˱ʾĻ,ָĹڱ㷨.㷨ȫָı,еָ㷨ܽһЩܽЧش.
ؼʡָ,ָ,ڷ,Ż.
ͼšTP314

Intraprocedural Alias Analysis for Pointer Array
HUANG BoZANG Bin-yuYU Yi-junZHU Chuan-qi
(Institute of Parallel Processing Fudan University Shanghai 200433)
Abstract Pointer alias analysis plays an important role in the parallelizing optimization of C program, however, all the previous analyzing algorithm can only be used to analyze the pointer scalars. In this paper, an extended representation for point-to information is presented, which can represent not only the point-to information of pointer scalars, but also the point-to information of pointer arrays. Furthermore, an algorithm of intraprocedural alias analysis for pointer array is presented. This algorithm comprises both the pointer scalar analysis and pointer array analysis. It can be used to efficiently solve some problems which couldn't be solved by the previous algorithm.
Key wordsPointer alias analysis, pointer array, intraprocedural analysis, parallelizing optimization.
ڹȥ10,Żоȡ˺ܴչ.ѧȺƳٵ͵ĲŻϵͳ,ľߴԵϵͳ˹̹ѧSUIF1ݡŵѧPolaris2ݺ͸ѧAFT3ݵ.Ӹý巢ļϵͳݶԴFORTRANĲŻڳ,ĿǰоķתԴCĲŻ.FORTRAN,CԴFORTRANе﷨ص,༶ָʹáڴĶ̬䡢ݹ麯ĵõ.Щ˶CĲŻȻFORTRANĲŻĲͬ,ЩĴ,һĳ̶ɼӾCŻѶ.
ָͻߴͨ͵ַʽеĹ̵ʱ,ϵıʽͿܴͬһڴַ,ʱǳЩͬһڴַıʽΪ.ָ͵ĴڶıΪָ,ָĴCԵĵ֮һ.ĳһָϢȷʱ,еԷñصĹ,ָָб,ּȻ׼ȷԴܴӰ첢ʹŻЧ󽵵.Ϊ˼СָĴڶԲз벢б任Ӱ,ǿָķǻȡ׼ȷָϢ벢ŻЧЧʩ.ⲢŻоָֹķ411.,Ϊֹеָָֻܶб,ָʱ,еķΪ,:
int (*FunctionPointerۣ)()={Function-1,Function-2,...,Function-N};
FunctionPointeri()ĵ,iֵȷʱ,еָȡFunctionPointerָϢ,ڷʱͲȷõĸ,Ӷ(رǹ̼)ʱñصĹƷ,ȻӰ׼ȷ.Ϊ,һµָϢıʾ.ָķΧָĿķΧںָϢ,ܹʾָıϢ.ֱʾĻ,ָĹڱ㷨,ָָƹ㵽ָ,ΪCĲз벢б任ṩΪ׼ȷָϢ.
ĵ1ڽصָϢʾĻһָϢչָʾ.2ڽָܹĻ.3ڽζCеĸָķ.43Ӳ˱㷨Ӧ.5ܽ.
1 ָϢչָʾ
1.1 صĹ
ָϢʾ:(alias pair)ʾ4,5ݺָ(point-to)ʾ610.ԱʾǰѻΪıʽһԪʾ.ֱʾϢϢ̫,ֲָʾ,һָָָĿɵĶԪʾϢ,Maryam Emamiչָʾ,ڶԪĻһȷָָ־(DP),ӶʹñϢܱ׼ȷرʾʹã10.ĳһָָĿʱ,ԭָʾҪô鵱һ,ҪôֻԪ,ѳԪԪصһ.,˹̹ѧRobert P. Wilsonһλü(location set)ʾָָĿ,׼ȷرʾָָķΧ(λüһԪ(b,f,s),bڴ,fbڵƫ,sǲ,(b,f,s)ȼλü{f+is|iZ})9.ͼ1һ򵥵˵ЩָϢʾ(,S1ǰıϢΪ,ռ2ֽ). **

ͼ1ָϢʾıȽ
 ,ЩָϢıʾܱʾָıϢ,ڶCŻĹָʱȡصĹ,ȻӰ첢ŻЧ.Ϊ˱ʾָıϢ,һµָϢıʾ.
1.2 չָʾ
ĲһչָʾʾָϢ,ֱʾµʽ:p,t,c,PR,TR).pʾָָ;tʾpָĿĿ;cʾָָϵȷָǿָ,ȡֵΪDP,Dʾȷָ,Pʾָ,ͬʱPD֮Ļӡ,ľ:DD=D,DP=P,PD=P,PP=P.PRTRĺ:pʱ,PRʾpԪصķΧ,,PR=;t̬һڴ(̬ڴ)ʱ,TRʾtԪػ̬ڴԪصķΧ;,TR=.
PRTRԱʾΪ{(Si,Ii,Ei)|1in}.Ԫ(Si,Ii,Ei),Siʾʼλ,Eiʾֹλ,IiʾĲ,Ƕ,ֽΪ㵥λ.Ҳ˵PRTRԪرҲǼ,ҸԪؼ֮䲻ཻ.ˣPRPR֮TRTR֮ǸԵԪؼ֮.
ĳһԪռֽΪES,Ԫ(S,I,E)ʾʵ൱µֽڼ(Bʾ׵ַ):
{B+S,B+S+1,...,B+S+ES-1;B+S+I,B+S+I+1,...,
B+S+I+ES-1;...,B+E-ES+1,...,B+E-1,B+E}
1. RΪPRTR,ĵ1ԪR0ɱʾΪ{(0,ES,ES-1)},i+1(i0)ԪRiɱʾΪ{(i*ES,ES,(i+1)*ES-1)}.
1. ö1еıʾʾRiRj,ji,RiRj={(i*ES,(j-i)*ES,(j+1)*ES-1)}֤ԣ.
1. in-in-1=in-1-in-2=...=i1-i0,Ri0Ri1...Rin={(i0*ES,(i1-i0)*ES,(in+1)*ES-1)}.
2. An,R0R1...Rn-1ɱʾΪ{(0,ES,n*ES-1)}.
Ķڽ鷶Χĺϲʱ,ں̶ܴϽ򻯽Χıʾ.
2. R=(S,I,E),R=(S,I,E),RR=ҽRR,

1ǶһЩָ븳ֵ(ָ븳ֵĸڵ3.1ڶ)ָϢıʾ(Ϊ,׵ַΪ0).
1һЩָ븳ֵָϢıʾ

ָϢ
int a,*p;p=&a{(p,a,D,,)}
void q();void(*f)();f=q;{(f,q,D,,)}
int*p10,a;p0=&a;{(p,a,D,PR0,)},PR0={(0,4,3)}
int a100,b,*q; 
if (a0ݣb)
q=&b;
else q=a;{(q,b,P,,),
(q,a,P,,TR0)}
TR0={(0,2,1)}
struct STTYPE{int a,b;float fN;}S;
float*p;p=&s.f10;{(p,s.f,D,,TRf10)}
TRf10={(40,4,43)}
int*p10,qN; P0=q+i;{(p,q,D,PR0,TRi)}
PR0={(0,4,3)},TRi={(2i,2,2i+1)}


CвɱشڴĶ̬,ͨķʽЩ̬ڴбʶ,ָϢЩָָ.һּ򵥵,ö̬ڴڵļڵкżѭ(˶̬ڴѭ)ʶ.ʵ,һڴһʹʱ,ڽָķʱǰֶ̬ڴͬһ. 
2 ָڱĿ
ڵָͨԹڵνб,ڹ̳ڴָϢ.û۹̵ָϢӰ,ʵϣȡָϢǺҪ,ף5,6,911ݶԴ˽о.˹ָĿ,øʽĹ̼ͲѰָƹ㵽̼.ǰָϢıʾܺܺõرʾָıϢ,ָܰϢıʾ,ˣĽָܵڱĿʵͬʱָָı.ĳϽָָһ,ָıڸȫָ̺ı.
ڽָڱĻǰ,Ƚܼ.
ڸĳͼCFGڵһS,A-IN(S) ΪS֮ǰָϢ(AliasSet);A-OUT(S)Ϊ뿪Sĳָ֮Ϣ;PRED(S)ΪͼSǰɵļ.弰һָܵϢıʾ,ָĹڱµĿʾ:
for each statement S in the procedure{
A-IN(S)=;
A-OUT(S)=StmtAnalysis(S,,CFG);
}
do{
Changed=FALSE;
for each Statement S in depth first order{
OldA-IN(S)=A-IN(S);

if (OldA-IN(S)A-IN(S)) {
Changed=TRUE;
A-OUT(S)=StmtAnalysis(S,A-IN(S),CFG);
}
}
}whileChanged
ϵָڱĻ,StmtAnalysisɶSָָϢķ,ľʵֽڵ3ڽ.MergeʵֵǶָϢĺϲ,ԺϲָϢΪķֵ,Mergeʵֵľ.
㷨. ָϢĺϲ㷨.
AliasSetMerge(AliasSet AS)
{
for each Pointer variable p exists in element of AS {
if ((p,x,D,PR1,TR1)AS and (p,y,D,PR2,TR2)AS and
((PR1= and PR2=) or PR1PR2) and xy){
change (p,x,D,PR1,TR1) to (p,x,P,PR1,TR1);
change (p,y,D,PR2,TR2) to (p,y,P,PR2,TR2);
}
if ((p,x,P,PR1,TR1)AS and (p,y,D,PR2,TR2)AS and xy)
change (p,y,D,PR2,TR2) to (p,y,P,PR2,TR2);
if ((p,x,c1,PR1,TR1)AS and (p,x,c2,PR2,TR2)AS){
PR=PR1PR2;
TR=TR1TR2;
delete (p,x,c1,PR1,TR1) from AS;
delete (p,x,c2,PR2,TR2) from AS;
if (PR==&& TR==)
c=c1c2;
else
c=P;
AS=AS{(p,x,c,PR,TR)};
}
}
return AS;
}
ָϢĺϲ㷨,һֺϲǰѶϢ򻯳һϢ,ӶָϢеԪظ.pΪָ,pָĿΪ,pвͬԪָͬһʱ,ֺϲܻһЩָϢĲȷ.ʵʳȽϺ,ڽָıʱֺϲĻ,ӰҲͺС.
3 ָ
3.1 ָ븳ֵ
ڷ漰ĶָϢĸıҪָ븳ֵ.ָ븳ֵĶ.
3. ֵ󲿱ʽֵΪָʱ,˸ֵΪָ븳ֵ.
ָ븳ִֵнʹֵ󲿴ָ(ָָ)ָĿ귢ı,ӶʹָϢӦı仯.
4. ָ븳ֵָɵļϳΪĿ꼯,L-Target(S);ָ븳ֵҲʽָĿ꼯ϳΪĿ꼯,ΪR-Target(S).
Ŀ꼯Ŀ꼯еԪԪ(t,c,R)ʾ.Ŀ꼯,tΪָָ,Ŀ꼯,tı(Զ̬ڴ).cʾtȷĿ껹ǿĿ,ȡֵ1ָϢʾеcͬ,RĺʾPRTR,tΪ̬ڴʱ,RʾĿķΧ,Ϊ.ǿתıĿ꼯Ŀ꼯,ָ븳ֵĿ꼯Ŀ꼯ļ2(1бʽֵΪָڴĵַ,IMPOSSIBLEʾָ븳ֵ䲻Ե1еıʽΪ,offset(f)ʾfڽṹڵƫ,ֽΪλ,ESʾԪռֽ),δгͨۺϴ˱еóӦĿ꼯Ŀ꼯.
2ָ븳ֵĿ꼯Ŀ꼯

ָ븳ֵ
SңL-Target (S)R-Target(S)
&aIMPOSSIBLE{(a,D,)}
&a.fIMPOSSIBLE{(a.f,D,)}
&aiIMPOSSIBLE{(a,D, Ri)}
a(aΪָ){(a,D,)}{(x,c,TR)|(a,x,c,PR,TR)A-IN(S)}
a.f{(a.f,D,)}{(x,c,TR)|(a.f,x,c,PR,TR)A-IN(S)}
ai
(aָ){(a,D,Ri)}{(x,c,TR)|(a,x,c,PR,TR)A-IN(S),RiPR}
*a
(ʱaһ
ָ){(x,c,TR)|(a,x,c,,TR)A-IN(S)}{(y,c1c2,TR2)|(a,x,c1,,TR1)A-IN(S);(x,y,c2,PR2,TR2)A-IN(S);TR1PR2}
(*a).f
(aһָṹ
ָ,ṹ
һf,f
һָ){(y,c,TR)|(a,x,c,,TR)A-IN(S);
if (TR)/*ʱxΪһṹ*/
y=x;TR={(S,I,E)|S=S+Offset(f),
E=E+Offset(f),(S,I,E)TR,}
else
y=x.f;TR=;
}{(z,c1c2,TR2)|(a,x,c1,,TR1)A-IN(S);
if (TR1) /*ʱxΪһṹ*/
y=x;TR1={(S,I,E)|S=S+Offset(f),
E=E+Offset(f),(S,I,E)TR1}
else y=x.f;TR1=;
(y,z,c2,PR2,TR2)A-IN(S);TR1PR2}
(*a)i
(aһָָ
ָ){(x,c,TR)|(a,x,c,,TR)A-IN(S);
TR={(S,I,E)|S=S+i*ES,
E=E+i*ES,(S,I,E)TR}}{(y,c1c2,TR2)|(a,x,c1,,TR1)A-IN(S),
TR1={(S,I,E)|S=S+i*ES,E=E+i*ES,(S,I,E)TR1},(x,y,c2,PR2,TR2)A-IN(S),TR1PR2}
p+NIMPOSSIBLE{(x,c,TR)|(p,x,c,PR,TR)A-IN(S),
TR={(S,I,E)|S=S+N*sizeof(*p),
E=E+N*sizeof(*p),(S,I,E)TR}}
NULLIMPOSSIBLE{(NULL,D,)}
malloc(Type)IMPOSSIBLE{(MEM-ALLOC-NAME,D,)}
malloc(Type*N)IMPOSSIBLE{(MEM-ALLOC-NAME,D,R0)}


ϱ,MEM-ALLOC-NAMEΪһ,ݶ̬ڴڵļкżѭ(˶̬ڴѭ)Ϣһʶ. 
3.2 ָ븳ֵָ
ͼCFGָ븳ֵSSǰָϢA-IN,ָ븳ֵָ㷨:
AliasSetPointerAssignmentAnalysis(AssignStmt S,AliasSet A-IN,Graph CFG)
{ A-KILL={(p,t,c,PR,TR)|(p,D,PR)L-Target(S),(p,t,c,PR,TR)A-IN};
A-CHANGE={(p,t,D,PR,TR)|(p,P,PR)L-Target(S),(p,t,D,PR,TR)A-IN};
A-GEN={(p,t,c1c2,PR,TR)|(p,c1,PR)L-Target(S),(t,c2,TR)R-Target(S)};
CHANGED-SET=(A-INA-CHANGE){(p,t,P,PR,TR)|(p,t,D,PR,TR)A-CHANGE};
return Merge((CHANGED-SETA-KILL)A-GEN))
}
3.3 ָ
ȻC԰ṹ,ṹ淶,еĿƽṹԹΪ˳ѭ3.ڶһָķʱ,ݴ(ڼ䡢˳䡢䡢ѭеһ),ֱòָͬ,ָ(оиõıʽڳ淶бȼ۵ıʽ(),ָϢᱻ淶καʽı).ڹڷ,ָֻ븳ֵָܶϢ޸,ڶԼ(縳ֵ䡢break䡢continue)ָʱ,ֻҪжϴǲָ븳ֵ,ָ븳ֵ,ڴָϢڴָϢһ,ָ븳ֵָ㷨ָϢ.˳ѭ3ֿƽṹ,ǵָڱĿοף10еķ.
4 Ӧþ
ȿ:
int aM,*P,*q,i; 
...
p=a;
q=a+1;
i=0;
while (iN){
s1:*p=...;
s2:...=*q;
...
s3:p=p+2;
s4:q=q+2;
i=i+1;
}
...
㷨ָ,ѭÿ,ָϢΪ{(p,a,D,,TR),(q,a,D,,TR)},TR={(4i,2,4i+1)},TR={(4i+2,2,4i+3)},0iN-1.TRTR=,ڽԷʱ,ָͨϢжϳs1s2κ,Ӷͨs3s4ĹԼذѭ任ɲѭ.
صǰٵǸ,:int (*FunctionPointerۣ)()={Function-1,Function-2,...,Function-N}; ,ָıϢ:{(FunctionPointer,Function-1,D,PR0,), (FunctionPointer,Function-2,D,PR1,),..., (FunctionPointer,Function-N,D,PRN-1,)}, FunctionPointeri()ĵ,iֵȷʱ,i=1,ͨFunctionPointerPR1ָϢȷǶ Function-2ĵ,ǿ׼ȷչԭعƵĵͼ,Ӷʹ÷ԽFunction-2̻ȡϢ.
ٷгʵ.
typed struct DataStruct{
KEYWORD key;
CONTENT content;
struct DataStruct* next;
}DS;
DS*DataBaseN,q; int i;
...
/*Construct the data table*/
i=0;
while (iN){
s1: DataBasei=q=NULL;
...
while (...){
...
if (q==NULL)
s2:DataBasei=q=(DS*)malloc(sizeof(DS));
else
s3:q-next=(DS*)malloc(sizeof(DS));
...
if (q-next!=NULL)
s4:q=q-next;
i++
}
}
...
ͨǰ㷨ķɵµָϢ:{(DataBase,NULL,P,PRi,), (DataBase,MEM-ALLOC-s2-i,P,PRi,), (q,NULL,P,,), (q,MEM-ALLOC-s2-i,P,,), (q,MEM-ALLOC-s3-i,P,,), (MEM-ALLOC-s2-i.next,MEM-ALLOC-s3-i,P,,), (MEM-ALLOC-s3-i.next,MEM-ALLOC-s3-i.next,P,,)}(0iN-1).ɴ˿֪,ѭĲͬѭ,DataBaseqָĿ꼯ཻ.ͨ˽лжϳ:ָqѭ˽б,DataBaseѭ˽,,ѭԱ任ɲѭ.
3ӿԿ:ָĹڱ㷨ܶCָָıϢЧؽз,Ӷں̶ܴ˲ŻЧ.
5  
ԪʽչָϢָʾ,ָָϢıʾںһ,ӾȷرʾָϢ,ڴ˻ϸָڱĻָϢȡ㷨,ӶָϢķָƹ㵽ָ,γһָϵ.㷨ܹͬʱЧ׼ȷָָıϢ,ӶԵCŻЧ.
*оõȻѧ𡢹863߿ƼĿ͹ҽʿ
**û˵нԼٵռ2ֽڣʵռ4ֽڣ32λѰַsizeo(int*)=(float*)=4
߼顡Ʋ1973ʿҪоΪб롣
갱1965ڣҪоΪб롣
һ1972ʿҪоΪб롣
촫1943ڣʿʦҪоΪд
ͨϵˣƲֹ 200433ѧдо
ߵλѧдо Ϻ 200433
ο
1Stanford Compiler Group. The SUIF parallelizing compiler guide. Technique Report, Standford University, 1994
2Blume B, Eigenmann R, Faigin K et al. The next generation in parallelizing compiler. In: Proceedings of the 7th Workshop on LCPC. 1994
3촫,갱,ͮ.Զлϵͳ.ѧ,1996,7(3):180186
(Zhu Chuan-qi, Zang Bin-yu, Chen Tong. An automatic parallelizer. Journal of Software, 1996,7(3):180186)
4Spillman T C. Exposing side effect in a PL/I optimizing compiler. In: Proceedings of the IFIP Conference. North-Holland, 1971. 376381
5Allen F E. Interprocedual data flow analysis. In: Proceedings of the IFIP Conference. North-Holland, Amsterdam, 1974. 398402
6Barth J M. A practical interprocedual data flow analysis algorithm. Communication of ACM, 1978,21(9):724736
7Aho A V, Sethi R, Ullman J D. Compilers Principles, Techniques and Tools. Reading, MA: Addison-Weslsy Publishing Company, 1986. 648660
8Wolfe M. High Performance Compilers for Parallel Computing. Reading, MA: Addison-Weslsy Publishing Company, 1995. 277287
9Wilson R P, Lam M S. Efficient context-sentive pointer analysis for C programs. In: Proceedings of ACM SIGPLAN '95 Conference on Programming Language Design and Implementation. La Jolla, CA, 1995. 112
10Emami M, Ghiya R, Hendren L. Context-sensitive interprocedual points-to analysis in the presence of function pointers. In: Proceedings of ACM SIGPLAN'94 Conference on Programming Language Design and Implementation. 1994. 242256
11Liu Qiang, Zhang Zhao-qing, Ji Xiao-mei. Eliminating two kinds of data flow inaccuracy in the presence of pointer aliasing. In: Proceedings of the 1997 Conference on Advances in Parallel and Distributed Computing. Los Alamitors, CA: IEEE Computer Society Press, 1997. 410415
1998-01-24յԭ壬1998-06-30յ޸ĸ
