TY - GEN
T1 - Polynomial constants are decidable
AU - Müller-Olm, Markus
AU - Seidl, Helmut
N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 2002.
PY - 2002
Y1 - 2002
N2 - Constant propagation aims at identifying expressions that always yield a unique constant value at run-time. It is well-known that constant propagation is undecidable for programs working on integers even if guards are ignored as in non-deterministic flow graphs. We show that polynomial constants are decidable in non-deterministic flow graphs. In polynomial constant propagation, assignment statements that use the operators +,−, ∗ are interpreted exactly but all assignments that use other operators are conservatively interpreted as non-deterministic assignments. We present a generic algorithm for constant propagation via a symbolic weakest precondition computation and show how this generic algorithm can be instantiated for polynomial constant propagation by exploiting techniques from computable ring theory.
AB - Constant propagation aims at identifying expressions that always yield a unique constant value at run-time. It is well-known that constant propagation is undecidable for programs working on integers even if guards are ignored as in non-deterministic flow graphs. We show that polynomial constants are decidable in non-deterministic flow graphs. In polynomial constant propagation, assignment statements that use the operators +,−, ∗ are interpreted exactly but all assignments that use other operators are conservatively interpreted as non-deterministic assignments. We present a generic algorithm for constant propagation via a symbolic weakest precondition computation and show how this generic algorithm can be instantiated for polynomial constant propagation by exploiting techniques from computable ring theory.
UR - http://www.scopus.com/inward/record.url?scp=84958740430&partnerID=8YFLogxK
U2 - 10.1007/3-540-45789-5_4
DO - 10.1007/3-540-45789-5_4
M3 - Conference contribution
AN - SCOPUS:84958740430
SN - 3540442359
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 4
EP - 19
BT - Static Analysis - 9th International Symposium, SAS 2002 Madrid, Spain, September 17-20, 2002 Proceedings
A2 - Hermenegildo, Manuel V.
A2 - Puebla, German
PB - Springer Verlag
T2 - 9th International Static Analysis Symposium, SAS 2002
Y2 - 17 September 2002 through 20 September 2002
ER -