Alexander Sakharov
 
     

Beyond Constant Propagation

Constant propagation is one of the best explored program optimization techniques. Later this technique was extended to so called environments. The environments helped to associate intervals with program variables. Still, environments allow propagation of a properties of individual variables only.

The original idea of my research in this area was to allow propagation of relational expressions built from expressions occurring in the analyzed program. For example, if we can propagate x=c or x>c across control flow graphs, we should also be able to propagate expressions like x<y+1. The good news is that we normally know properties of operations and relations used in expressions, and thus, we can do sophisticated reasoning about the relational expresions. For example: if x-y<c and y<d, then x<c+d. Therefore, it is possible to conduct rule-based propagation of arbitrary relational expressions connecting program variables. This propagation is executed by a worklist-based fixpoint algorithm that additionally applies rules at every iteration.

This research of mine resulted in both scientific papers and real-life applications. The first paper is pretty preliminary:
Propagation of Constants and Assertions, SIGPLAN Notices, 29(1994), #5

The second paper is more mature and incorporates some major achievements:
A Framework for Tracking Branch Conditions, Midwest Society for Programming Languages and Systems: Fall 1995 Workshop

Finally, the third paper is the most advanced. Propagation of relational expressions is done there in the context of partial evaluation as a program transformation methodology used on programs after collecting dataflow information.
Specialization of Imperative Programs Through Analysis of Relational Expressions, Lecture Notes in Computer Science, 1110 (1996)
This paper is also available online: Full Text in PDF

 

Copyright © 2003 Alexander Sakharov

Need to relax? Try brain teasers. I would recommend those marked 'cool'.