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