Article

Symbolic range propagation

Authors:

William Blume,

Rudolf EigenmannAuthors Info & Claims

IPPS '95: Proceedings of the 9th International Symposium on Parallel Processing

Pages 357 - 363

Published: 25 April 1995 Publication History

Publisher Site

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.

Cited By

View all

Rodrigues MGuimarães BPereira FKandemir MJimborean AMoseley T(2019)Generation of in-bounds inputs for arrays in memory-unsafe languagesProceedings of the 2019 IEEE/ACM International Symposium on Code Generation and Optimization10.5555/3314872.3314890(136-148)Online publication date: 16-Feb-2019
https://dl.acm.org/doi/10.5555/3314872.3314890
Maalej MPaisante VMagno Quinto Pereira FGonnord L(2018)Combining range and inequality information for pointer disambiguationScience of Computer Programming10.1016/j.scico.2017.10.014152:C(161-184)Online publication date: 15-Jan-2018
https://dl.acm.org/doi/10.1016/j.scico.2017.10.014
Anand KElwazeer KKotha ASmithson MBarua RKeromytis A(2016)A Stack Memory Abstraction and Symbolic Analysis Framework for ExecutablesACM Transactions on Software Engineering and Methodology10.1145/289751125:2(1-38)Online publication date: 27-Apr-2016
https://dl.acm.org/doi/10.1145/2897511
Show More Cited By

Symbolic range propagation
1. Software and its engineering
  1. Software notations and tools
2. Theory of computation
  1. Models of computation
    1. Concurrency

Recommendations

Parallelizing while loops for multiprocessor systems
IPPS '95: Proceedings of the 9th International Symposium on Parallel Processing

Current parallelizing compilers treat while loops and do loops with conditional exits as sequential constructs because their iteration space is unknown. Because these types of loops arise frequently in practice, we have developed techniques that can ...
(R) Compiler Support for Privatization on Distributed - Memory Machines
ICPP '96: Proceedings of the Proceedings of the 1996 International Conference on Parallel Processing - Volume 3

Abstract: The practice of using temporary scalar or array variables to store the results of common subexpressions presents several challenges to a parallelizing compiler. Not only does dependence analysis and, as a result, parallelization suffer; but ...
Interactive and symbolic data dependence analysis based on ranges of expressions
Abstract
Traditional data dependence testing algorithms have become very accurate and efficient for simple subscript expressions, but they cannot handle symbolic expressions because of the complexity of data-flow and lack of the semantic information of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

IPPS '95: Proceedings of the 9th International Symposium on Parallel Processing

April 1995

661 pages

ISBN:0818670746

Publisher

IEEE Computer Society

United States

Publication History

Published: 25 April 1995

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

36
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Rodrigues MGuimarães BPereira FKandemir MJimborean AMoseley T(2019)Generation of in-bounds inputs for arrays in memory-unsafe languagesProceedings of the 2019 IEEE/ACM International Symposium on Code Generation and Optimization10.5555/3314872.3314890(136-148)Online publication date: 16-Feb-2019
https://dl.acm.org/doi/10.5555/3314872.3314890
Maalej MPaisante VMagno Quinto Pereira FGonnord L(2018)Combining range and inequality information for pointer disambiguationScience of Computer Programming10.1016/j.scico.2017.10.014152:C(161-184)Online publication date: 15-Jan-2018
https://dl.acm.org/doi/10.1016/j.scico.2017.10.014
Anand KElwazeer KKotha ASmithson MBarua RKeromytis A(2016)A Stack Memory Abstraction and Symbolic Analysis Framework for ExecutablesACM Transactions on Software Engineering and Methodology10.1145/289751125:2(1-38)Online publication date: 27-Apr-2016
https://dl.acm.org/doi/10.1145/2897511
Sperle Campos VAlves PNazaré Santos HQuintão Pereira FZaks AHermenegildo M(2016)Restrictification of function argumentsProceedings of the 25th International Conference on Compiler Construction10.1145/2892208.2892225(163-173)Online publication date: 17-Mar-2016
https://dl.acm.org/doi/10.1145/2892208.2892225
Paisante VMaalej MBarbosa LGonnord LQuintão Pereira FFranke BWu YRastello F(2016)Symbolic range analysis of pointersProceedings of the 2016 International Symposium on Code Generation and Optimization10.1145/2854038.2854050(171-181)Online publication date: 29-Feb-2016
https://dl.acm.org/doi/10.1145/2854038.2854050
Nazaré HMaffra ISantos WBarbosa LGonnord LQuintão Pereira F(2014)Validation of memory accesses through symbolic analysesACM SIGPLAN Notices10.1145/2714064.266020549:10(791-809)Online publication date: 15-Oct-2014
https://dl.acm.org/doi/10.1145/2714064.2660205
Nazaré HMaffra ISantos WBarbosa LGonnord LQuintão Pereira FBlack AMillstein T(2014)Validation of memory accesses through symbolic analysesProceedings of the 2014 ACM International Conference on Object Oriented Programming Systems Languages & Applications10.1145/2660193.2660205(791-809)Online publication date: 15-Oct-2014
https://dl.acm.org/doi/10.1145/2660193.2660205
Henriksen TOancea C(2014)Bounds CheckingProceedings of ACM SIGPLAN International Workshop on Libraries, Languages, and Compilers for Array Programming10.1145/2627373.2627388(88-94)Online publication date: 9-Jun-2014
https://dl.acm.org/doi/10.1145/2627373.2627388
Zhou XGiacalone JGarzarán MKuhn RNi YPadua DEidt CHoller ASrinivasan UAmarasinghe S(2012)Hierarchical overlapped tilingProceedings of the Tenth International Symposium on Code Generation and Optimization10.1145/2259016.2259044(207-218)Online publication date: 31-Mar-2012
https://dl.acm.org/doi/10.1145/2259016.2259044
Cappaert JPreneel BAl-Shaer EJin HJoye M(2010)A general model for hiding control flowProceedings of the tenth annual ACM workshop on Digital rights management10.1145/1866870.1866877(35-42)Online publication date: 4-Oct-2010
https://dl.acm.org/doi/10.1145/1866870.1866877
Show More Cited By

Abstract

Cited By

Recommendations

Parallelizing while loops for multiprocessor systems

(R) Compiler Support for Privatization on Distributed - Memory Machines

Interactive and symbolic data dependence analysis based on ranges of expressions

Comments

Information

Published In

Publisher

Publication History

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations