Traces of control-flow graphs

Simone Campanoni*, Stefano Crespi Reghizzi

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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
Number of pages14
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


Other13th International Conference on Developments in Language Theory, DLT 2009

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


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

Cite this