Reading course on integer range analysis fall 2001
This is the home page for the graduate course about inter-procedural
program analysis. Meetings will be held on Wednesdays 3 times a month at
10:00-12:00. We will usually discuss 2 papers at each meeting.
The articles should have
been read by all participants BEFORE the discussion meeting.
Meetings
Date: 2001-09-12
Time: 10.00 -12.00
Room: 1106
Patrick Cousot and Nicolas Halbwachs,
Automatic discovery of
linear constraints among variables of a program,
in Proc. of the
5th ACM Symp. on principles of programming languages (POPL), 84--96, 1978.
Date: 2001-09-26
Time: 10.00-12.00
Room: 1106
Cousot & Halbwachs, see above.
Michael P. Gerlek, Eric Stoltz and Michael Wolfe,
Beyond induction variables: detecting and classifying sequences using a
demand-driven SSA form,
ACM Trans. Program. Lang. Syst. 17, 1 (Jan. 1995), Pages 85 - 122.
Local copy.
Acm copy.
Date: 2001-10-03
Time: 10.00-12.00
Room: 1406 (Note: new location)
Priyadarshan Kolte and Michael Wolfe,
Elimination of redundant array subscript range checks,
Proceedings of the conference on Programming
language design and implementation, 1995, Pages 270-278
Local copy.
Acm copy.
Tevfik Bultan, Richard Gerber and William Pugh,
Model-checking concurrent systems with unbounded integer variables:
symbolic representations, approximations, and experimental results,
ACM Trans. Program. Lang. Syst.
21, 4 (Jul. 1999), Pages 747 - 789.
Local copy.
Acm copy.
Date: 2001-10-10
Time: 10.15-12.00 (Note! Starting time has changed.)
Room: 1406
J.R.C. Patterson. Accurate static
branch prediction by value range propagation. In Proceedings of
the ACM SIGPLAN '95 Conference on Programming Language Design and
Implementation, pages 67--78, 1995.
P. López-García, M. Hermenegildo, S. Debray, and
N. W. Lin.
Lower bound cost estimation for logic
programs. Logic Programming: Proceedings of the 1997 International
Symposium, pages 291--306, MIT Press, 1997.
Date: 2001-10-24 Note: Wednesday & changed date again.
Time: 10.15-12.00
Room: 1406
ABCD: eliminating array bounds checks on demand
Rastislav Bodík, Rajiv Gupta and Vivek Sarkar, PLDI'00,
Pages 321 - 333.
Symbolic bounds analysis of pointers, array indices, and accessed memory regions
Radu Rugina and Martin Rinard, PLDI'00,
Pages 182 - 195.
Date: 2001-10-30 Note: Tuesday.
Time: 10.15-12.00
Room: 1406
Bidwidth analysis with application to silicon compilation;
Mark Stephenson,
Jonathan Babb and Saman Amarasinghe;
Proceedings of the ACM
SIGPLAN '00 conference on Programming language design and
implementation, 2000, Pages 108 - 120
R. van Engelen, Efficient Symbolic Analysis for Optimizing Compilers
in proceedings of the International Conference on Compiler Construction,
ETAPS 2001, LNCS 2027, pp. 118-132.
Date: 2001-11-15 Note: Thursday.
Time: 10.15-12.00
Room: 1406
David Wagner, Jeffrey S. Foster, Eric A. Brewer, and Alexander
Aiken.
"
A First Step Toward Automated Detection of
Buffer Overrun Vulnerabilities."
Proceedings of the Network and
Distributed System Security Symposium, San Diego, California,
February 2000.
"Supporting Timing Analysis by Automatic Bounding of Loop Iterations"
by C. Healy, M. Sjodin, V. Rustagi, D. Whalley, and R. van Engelen,
in Real-Time Systems, May 2000, pages 121-148.
Date: 2001-11-22 Note: Thursday.
Time: 14.15-16.00
Room: 1406
W.-N. Chin and S.-C. Khoo.
Calculating sized types.
In Proceedings of
the ACM SIGPLAN 2000 Workshop on Partial Evaluation and
Semantics-Based Program Manipulation, pages 62--72. ACM, New York,
Jan. 2000.
M. Karr, Affine relationships between variables of a program,
Acta Informatica (1976), no. 6, 133--151.
(Copies of Karr's paper can be obtained from Sven-Olof.)
More Papers
Deriving Pre-conditions for Array Bound Check Elimination
Wei-Ngan Chin, Siau-Cheng Khoo, Dana N. Xu
Proceedings of 2001 Symposium on Programs as Data Objects (PADO-II), Aarhus, Danmark
Optimizing array bound checks using flow analysis; Rajiv Gupta; ACM
Lett. Program. Lang. Syst. 2, 1-4 (Mar. 1993), Pages 135 - 150
"Automatic Detection and Exploitation of Branch Constraints for Timing
Analysis"
by C. Healy and D. Whalley, in IEEE Transactions on Software
Engineering,
accepted August 2000.
W. Harvey and P. J. Stuckey, A unit two variable per inequality integer constraint solver for constraint logic programming,
in Proceedings of the Twentieth Australasian Computer Science
Conference (ACSC'97), Sydney, Australia, Macquarie University, Sydney,
1997, pp. 102--111.
Last modified: Mon Nov 26 14:00:23 MET 2001