Heap-size analysis for assembly programs Jean-Yves Marion INPL-Loria – ´Ecole Nationale supérieure des Mines de Nancy

Our objective is to propose methods for resource-aware compila-tion 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 pro-grams, 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