| The problem of statically resolving virtual method calls in object-oriented(OO)programming languages has been a long standing challenge,often due to the overly complicated class hierarchy structures in modern OO programming languages such as Java,C# and C++.Traditional ways of dealing with this problem include class hierarchy analysis(CHA),variable type analysis(VTA),and retrieval of type information after a sophisticated points-to analysis.In this thesis,we tackle this problem by proposing a new approach called type flow analysis(TFA)which propagates type information as well as field access information through the syntactic structure of a program.Our methodology is purely algebraic and there is no need to explicitly construct a heap abstraction.We have assessed our methodology from two perspectives.Regarding its theoretical foundation,we have proved that in the context insensitive setting,our method is as precise as the standard Andersen's subset-based points-to analysis(PTA)regarding the derived types for variables.Since PTA possess the highest precision among all type analysis algorithms,TFA is more precise than CHA,RTA and VTA.For an experimental evaluation of TFA,we have implemented the algorithm in the Soot framework and used it to analyze the SPECjvm2008 benchmark suite.During the experiment,we have shown that our method is usually 50-110 times faster than the standard points-to analysis.Meanwhile,TFA could be as fast as CHA,the most efficient algorithm.We further conduct a range of detailed analysis based on the baseline data obtained by running a dynamic profiler,which is also implemented by us,on the SPECjvm2008.The experiment results confirm that TFA can achieve outstanding performance with acceptable accuracy when applied on real world Java programs. |
PDF Full Text Request