Traces of control-flow graphs

Simone Campanoni; Stefano Crespi Reghizzi

doi:10.1007/978-3-642-02737-6_12

Traces of control-flow graphs

Simone Campanoni^*, Stefano Crespi Reghizzi

^*Corresponding author for this work

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

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.

Original language	English (US)
Title of host publication	Developments in Language Theory - 13th International Conference, DLT 2009, Proceedings
Pages	156-169
Number of pages	14
DOIs	https://doi.org/10.1007/978-3-642-02737-6_12
State	Published - 2009
Event	13th International Conference on Developments in Language Theory, DLT 2009 - Stuttgart, Germany Duration: Jun 30 2009 → Jul 3 2009

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	5583 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	13th International Conference on Developments in Language Theory, DLT 2009
Country	Germany
City	Stuttgart
Period	6/30/09 → 7/3/09

ASJC Scopus subject areas

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/978-3-642-02737-6_12

Fingerprint Dive into the research topics of 'Traces of control-flow graphs'. Together they form a unique fingerprint.

Cite this

Campanoni, S., & Crespi Reghizzi, S. (2009). Traces of control-flow graphs. In Developments in Language Theory - 13th International Conference, DLT 2009, Proceedings (pp. 156-169). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5583 LNCS). https://doi.org/10.1007/978-3-642-02737-6_12

@inproceedings{89bd0ea1836b4d3abd343b470ac32548,

title = "Traces of control-flow graphs",

abstract = "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.",

author = "Simone Campanoni and {Crespi Reghizzi}, Stefano",

year = "2009",

doi = "10.1007/978-3-642-02737-6_12",

language = "English (US)",

isbn = "3642027369",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "156--169",

booktitle = "Developments in Language Theory - 13th International Conference, DLT 2009, Proceedings",

note = "13th International Conference on Developments in Language Theory, DLT 2009 ; Conference date: 30-06-2009 Through 03-07-2009",

}

Campanoni, S & Crespi Reghizzi, S 2009, Traces of control-flow graphs. in Developments in Language Theory - 13th International Conference, DLT 2009, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 5583 LNCS, pp. 156-169, 13th International Conference on Developments in Language Theory, DLT 2009, Stuttgart, Germany, 6/30/09. https://doi.org/10.1007/978-3-642-02737-6_12

Traces of control-flow graphs. / Campanoni, Simone; Crespi Reghizzi, Stefano.

Developments in Language Theory - 13th International Conference, DLT 2009, Proceedings. 2009. p. 156-169 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5583 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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 -