next up previous
Next: Code Generation Up: Application of The Previous: Eliminate false dependence

Counting Solutions to Presburger Formulas

In the paper [3], the omega test is used to development new methods that are able to count the number of integer solutions to selected free variables of the presburger formula. Presburger formulas are those formulas that can be built up out of linear constraints over integer variables, logical connectives, and universal and existential quantifiers. This new methods, which uses the omega test, have a number of applications in analysis and transformations of scientific programs. Within programs with affine loop bounds, guards and subscriptions, some formulas can be defined who's solutions correspond to the flops executed by loop, the memory locations touched by a loop, the cache lines touched by a loop. By counting the number of solution to these formulas, execution time of a code segment could be estimated, the memory bandwidth requirements and the flop counts of a code segment could be compared, which loop would flush the cache could be determined.



Generated by latex2html-95.1
Fri Jul 12 14:53:37 EDT 1996