Symbolic range propagation

William Blume, Rudolf Eigenmann

2002 · 74 citations · 11 references

Concepts

Abstract

Many analyses and transformations in a parallelizing compiler can benefit from the ability to compare arbitrary symbolic expressions. In this paper, we describe how one can compare expressions by using symbolic ranges of variables. A range is a lower and upper bound on a variable. We describe how these ranges can be efficiently computed from the program test. Symbolic range propagation has been implemented in Polaris, a parallelizing compiler being developed at the University of Illinois, and is used for symbolic dependence testing, detection of zero-trip loops, determining array sections possibly referenced by an access, and loop iteration-count estimation.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>

References

11