NDLI: Static analysis of large programs (invited talk) (abstract only):some experiences

Please wait, while we are loading the content...

Volume 34, Issue 12, Dec. 1999

Volume 34, Issue 11, Nov. 1999

Static analysis of large programs (invited talk) (abstract only)

Towards partially evaluating reflection in Java

Online-and-offline partial evaluation (extended abstract)

The second Futamura projection for type-directed partial evaluation

On the logical foundations of staged computation (invited talk)

A sound reduction semantics for untyped CBN multi-stage computation. Or, the theory of MetaML is non-trival

Using regular approximations for generalisation during partial evalution

Non pair-sharing and freeness analysis through linear refinement

Calculating sized types

From recursion to iteration

Operating systems specialization (invited talk) (abstract only)

Type-based useless variable elimination

Program analysis with partial transfer functions

Symbolic pointer analysis for detecting memory leaks

Volume 34, Issue 10, Oct. 1999

Volume 34, Issue 9, Sept. 1999

Volume 34, Issue 8, Aug. 1999

Volume 34, Issue 7, July 1999

Volume 34, Issue 6, June 1999

Volume 34, Issue 5, May 1999

Volume 34, Issue 4, April 1999

Volume 34, Issue 3, March 1999

Volume 34, Issue 2, Feb. 1999

Volume 34, Issue 1, Jan. 1999

Static analysis of large programs (invited talk) (abstract only):some experiences

Content Provider	ACM Digital Library
Author	Das, Manuvir
Abstract	Our research group at Microsoft has spent some effort over the last few years attempting to apply static analysis methods to large application programs (over a million lines of code). In the first part of the talk, I will share some of the insights we have gained along the way. The first insight is that the static analysis method of interest must scale to large programs. It must scale in terms of performance, both running time and memory requirements. The interesting complexity metric is average-case behaviour. The analysis must also scale in terms of the quality of information produced. This metric is hard to measure, and depends on the problem to be solved. The second insight is that large commercial applications differ from the benchmark programs typically used in the literature in many ways beyond sheer size: For instance, they routinely circumvent the type system, they make use of every conceivable language feature, they use large shared libraries, they contain some very large automatically generated functions, they define functions with large numbers of call sites, and they include many indirect call sites. All of these characteristics make analysis hard. In particular, they make the implementation of a scalable analysis an exercise in careful engineering.In the second part of the talk, I will make the claim that it is possible to develop scalable static analysis methods for large programs, using the following approach: First, implement an efficient algorithm, and carefully engineer it to scale. Important requirements are modularity, a complete parser, and some form of garbage collection. Next, identify the conceptual limitations of the efficient algorithm, and examine the test programs to identify common cases or idioms in the code that expose these limitations. Finally, extend the original algorithm in a principled manner to account for these common cases, without compromising performance. I will use my work on pointer analysis of large programs as an example of this approach. The key insight is that it is possible to identify common idioms in the code that are the bottlenecks for efficient algorithms. A scalable static analysis method can be developed if these idioms can be identified and accommodated.
File Format	PDF
ISSN	03621340 15581160
DOI	10.1145/328691.328692
Journal	ACM SIGPLAN Notices (SIGP)
Volume Number	34
Issue Number	11
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	1983-05-01
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Content Type	Text
Resource Type	Article
Subject	Computer Graphics and Computer-Aided Design Software

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in