Loop monotonic statements
- 1 June 1995
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Software Engineering
- Vol. 21 (6) , 497-505
- https://doi.org/10.1109/32.391376
Abstract
A statement is considered to be monotonic with respect to a loop if its execution, during the successive iterations of a given execution of the loop, assigns a monotonically increasing or decreasing sequence of values to a variable. We present static analysis techniques to identify loop monotonic statements. The knowledge of loop monotonicity characteristics of statements which compute array subscript expressions is of significant value in a number of applications. We illustrate the use of this information in improving the efficiency of run-time array bound checking, run-time dependence testing, and on-the-fly detection of access anomalies. Given that a significant percentage of subscript expressions are monotonic, substantial savings can be expected by using these techniques.Keywords
This publication has 14 references indexed in Scilit:
- Beyond induction variablesPublished by Association for Computing Machinery (ACM) ,1992
- An empirical comparison of monitoring algorithms for access anomaly detectionPublished by Association for Computing Machinery (ACM) ,1990
- Automatic recognition of induction variables and recurrence relations by abstract interpretationPublished by Association for Computing Machinery (ACM) ,1990
- On-the-fly detection of access anomaliesPublished by Association for Computing Machinery (ACM) ,1989
- A unified semantic approach for the vectorization and parallelization of generalized reductionsPublished by Association for Computing Machinery (ACM) ,1989
- Automatic detection of nondeterminacy in parallel programsPublished by Association for Computing Machinery (ACM) ,1988
- A mechanism for efficient debugging of parallel programsPublished by Association for Computing Machinery (ACM) ,1988
- Dependence Analysis for SupercomputingPublished by Springer Nature ,1988
- Optimization of range checkingPublished by Association for Computing Machinery (ACM) ,1982
- Depth-First Search and Linear Graph AlgorithmsSIAM Journal on Computing, 1972