Heap-size analysis for assembly programs

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.