Heap-size analysis for assembly programs

Jean-Yves Marion (1) , Jean-Yves Moyen (2)

1 CALLIGRAMME - Linear logic, proof networks and categorial grammars
2 LIPN - Laboratoire d'Informatique de Paris-Nord

Our objective is to propose methods for resource-aware compilation inspired by the implicit complexity community. We consider a small assembly-like language and we build abstract finite machine models in order to predict a bound on the maximal heap usage of a program. We propose a polynomial time procedure to detect and certify a broad and meaningful class of non-size increasing programs, which run in a constant size heap. We end by discussing about programs running in linear heap space and discussing how to capture logarithmic space computation.

Mots clés: Non-Size increasing; program analysis

Domaines: Logique en informatique [cs.LO]

Jean-Yves Marion, Jean-Yves Moyen. Heap-size analysis for assembly programs. 2006. ⟨hal-00067838⟩