TY - GEN
T1 - Traces of control-flow graphs
AU - Campanoni, Simone
AU - Crespi Reghizzi, Stefano
PY - 2009
Y1 - 2009
N2 - This is a new applied development of trace theory to compilation. Trace theory allows to commute independent program instructions, but overlooks the differences between control and data dependencies. Control(C)-dependences, unlike data-dependences, are determined by the Control Flow Graph, modelled as a local DFA. To ensure semantic equivalence, partial commutation must preserve C-dependences. New properties are proved for C-dependences and corresponding traces. Any local language is star-connected with respect to C-dependences, hence this trace language family is recognizable. Local languages unambiguously represent traces. Within the family of local languages with the same C-dependences, we construct the language such that instructions are maximally anticipated. This language differs from the Foata-Cartier normal form. Future directions for application of trace theory to program optimization are outlined.
AB - This is a new applied development of trace theory to compilation. Trace theory allows to commute independent program instructions, but overlooks the differences between control and data dependencies. Control(C)-dependences, unlike data-dependences, are determined by the Control Flow Graph, modelled as a local DFA. To ensure semantic equivalence, partial commutation must preserve C-dependences. New properties are proved for C-dependences and corresponding traces. Any local language is star-connected with respect to C-dependences, hence this trace language family is recognizable. Local languages unambiguously represent traces. Within the family of local languages with the same C-dependences, we construct the language such that instructions are maximally anticipated. This language differs from the Foata-Cartier normal form. Future directions for application of trace theory to program optimization are outlined.
UR - http://www.scopus.com/inward/record.url?scp=69049108901&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=69049108901&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-02737-6_12
DO - 10.1007/978-3-642-02737-6_12
M3 - Conference contribution
AN - SCOPUS:69049108901
SN - 3642027369
SN - 9783642027369
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 156
EP - 169
BT - Developments in Language Theory - 13th International Conference, DLT 2009, Proceedings
T2 - 13th International Conference on Developments in Language Theory, DLT 2009
Y2 - 30 June 2009 through 3 July 2009
ER -