Traces of control-flow graphs

Simone Campanoni*, Stefano Crespi Reghizzi

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference 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 languageEnglish (US)
Title of host publicationDevelopments in Language Theory - 13th International Conference, DLT 2009, Proceedings
Pages156-169
Number of pages14
DOIs
StatePublished - 2009
Event13th International Conference on Developments in Language Theory, DLT 2009 - Stuttgart, Germany
Duration: Jun 30 2009Jul 3 2009

Publication series

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

Other

Other13th International Conference on Developments in Language Theory, DLT 2009
CountryGermany
CityStuttgart
Period6/30/097/3/09

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

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