naa a22 4500 510791247 CHVBK 20180411083320.0 cr unu---uuuuu 180411e20130601xx s 000 0 eng 10.1007/s11334-013-0198-7 doi (NATIONALLICENCE)springer-10.1007/s11334-013-0198-7 Precise shape analysis using field sensitivity [Elektronische Daten] [Sandeep Dasgupta, Amey Karkare, Vinay Reddy] We present a static shape analysis technique to infer the shapes of the heap structures created by a program at run time. Our technique is field sensitive in that it uses field information to compute the shapes. The shapes of the heap structures are computed using two components: (a) Boolean functions that capture the shape transitions due to the update of a field in a structure, and (b) through path matrices that store approximate path information between two pointer variables. We classify the shapes as one of Tree, Directed Acyclic Graph (DAG) and Cycle. The novelty of our approach lies in the way we use field information to remember the fields that cause a heap structure to have a particular shape (Tree, DAG or Cycle). This allows us to easily identify the field updates that cause shape transitions from Cycle to DAG, from Cycle to Tree and from DAG to Tree. This makes our analysis more precise as compared to earlier shape analyses that ignore the fields participating in the formation of a shape. We implemented our analysis in GCC as a dynamic plug-in as an interprocedural data-flow analysis and evaluated it on some standard benchmarks against a field-insensitive shape analysis technique as a baseline approach. We are able to achieve significant precision as compared to the baseline analysis (at the cost of increase in analysis time). In particular, we are able to infer more precise shapes for 4 out 7 Olden benchmarks, and never detect more cycles than the baseline analysis. We further suggest enhancements to improve the precision of our analysis under some constraints and to improve the analysis time at the cost of precision. Springer-Verlag London, 2013 Compilers nationallicence Dataflow analysis nationallicence Static analysis nationallicence Shape analysis nationallicence Heap analysis nationallicence Dasgupta Sandeep Intel Technology India Pvt. Ltd., Banglore, India aut Karkare Amey Department of Computer Science and Engineering, Indian Institute of Technology Kanpur, Kanpur, India aut Reddy Vinay Department of Computer Science and Engineering, Indian Institute of Technology Kanpur, Kanpur, India aut Innovations in Systems and Software Engineering Springer-Verlag 9/2(2013-06-01), 79-93 1614-5046 9:2<79 2013 9 11334 https://doi.org/10.1007/s11334-013-0198-7 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s11334-013-0198-7 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Dasgupta Sandeep Intel Technology India Pvt. Ltd., Banglore, India aut NATIONALLICENCE 700 1- Karkare Amey Department of Computer Science and Engineering, Indian Institute of Technology Kanpur, Kanpur, India aut NATIONALLICENCE 700 1- Reddy Vinay Department of Computer Science and Engineering, Indian Institute of Technology Kanpur, Kanpur, India aut NATIONALLICENCE 773 0- Innovations in Systems and Software Engineering Springer-Verlag 9/2(2013-06-01), 79-93 1614-5046 9:2<79 2013 9 11334 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer