From:                     Kendra Smith

Sent:                      Tuesday, May 09, 2000 11:29 PM

To:                         M?crosöft Research Tech Talk, Sem. Notice

Cc:                         Kendra Smith

Subject:                 UW-CSE Colloq / 5-10-2000 / Das / M?crosöft Research / Unification-Based Pointer Analysis with Directional Assignments

UW-CSE Colloq / 5-10-2000 / Das / M?crosöft Research / Unification-Based Pointer Analysis with Directional Assignments

 

NOTE: THIS LECTURE WILL *NOT* BE VIDEOTAPED.

 

UNIVERSITY OF WASHINGTON

Seattle, Washington 98195

 

Department of Computer Science and Engineering

Box 352350

(206) 543-1695

 

COLLOQUIUM

 

SPEAKER:      Manuvir Das, M?crosöft Research

 

TITLE:          Unification-Based Pointer Analysis with Directional Assignments

 

DATE:           Wednesday, May 10, 2000

 

TIME:           2:30pm

 

PLACE:                   EE1-003

 

HOST:           Susan Eggers

 

ABSTRACT:

 

This paper describes a new algorithm for flow and context

insensitive pointer analysis of C programs.  Our studies show that the

most common use of pinters in C programs is in passing the addresses

of composite objects or updateable values as arguments to procedures.

Therefore, we have designed a low-cost algorithm that handles this

common case accurately.  In terms of both precision and running time,

this algorithm lies between Steensgaard's algorithm, which treats

assignments bi-directionally using unification, and Andersen's

algorithm, which treats assignments directionally using subtyping.

Our "one level flow" algorithm uses a restricted form of subtyping to

avoid unification of symbols at the top levels of pointer chains in

the points-to graph, while using unification elsewhere in the graph.

The method scales easily to large programs.  For instance, we are able

to analyze a 1.4 MLOC (million lines of code) program in two minutes,

using less than 200mb of memory.  At the same time, the precision of

our algorithm is very close to that of Andersen's algorithm.  On all

of the interger benchmark programs from SPEC95, the one level flow

algorithm and Andersen's algorithm produce either identifical or

esseentially identical points-to information.  Therefore, we claim

that our algorithm provides a method of obtaining precise

flow-insensitive points-to information for large C programs.

 

 

Email: talk-info@cs.washington.edu

Info: http://www.cs.washington.edu