|
||
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:
The second paper is more mature and incorporates some major achievements:
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.
Propagation of Constants and Assertions,
SIGPLAN
Notices, 29(1994), #5
A Framework for Tracking Branch Conditions,
Midwest Society for Programming Languages and Systems: Fall 1995 Workshop
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
Need to relax? Try brain teasers. I would recommend those marked 'cool'.