1996 · 283 citations · 24 references
Directed GraphEngineeringComputer ArchitectureSoftware EngineeringShape AnalysisComputer-aided DesignData StructureSoftware AnalysisPractical Shape AnalysisParallel ToolData ScienceGraph DrawingDiscrete MathematicsParallel ComputingComputational GeometryMemory ManagementProgram SlicingGeometric ModelingDynamic Data StructureGeometric Graph TheoryComputer EngineeringComputer ScienceStatic Program AnalysisGraph AlgorithmGraph TheoryCyclic GraphProgram AnalysisNatural SciencesHeap-directed PointersParallel ProgrammingSymbolic Execution
This paper reports on the design and implementation of a practical shape analysis for C. The purpose of the analysis is to aid in the disambiguation of heap-allocated data structures by estimating the shape (Tree, DAG, or Cyclic Graph) of the data structure accessible from each heap-directed pointer. This shape information can be used to improve dependence testing and in parallelization, and to guide the choice of more complex heap analyses.The method has been implemented as a context-sensitive interprocedural analysis in the McCAT conlpiler. Experimental results and observations are given for 16 benchmark programs. These results show that the analysis gives accurate and useful results for an important group of applications.
24