Graph-based procedural abstraction

Dreweke A, Wörlein M, Fischer I, Schell D, Meinl T, Philippsen M (2007)

Publication Language: English

Publication Status: Published

Publication Type: Conference contribution, Conference Contribution

Publication year: 2007

Pages Range: 259-270

Article Number: 4145120

Conference Proceedings Title: International Symposium on Code Generation and Optimization (CGO'07)

Event location: San Jose, CA US

ISBN: 9780769527642

URI: http://www2.informatik.uni-erlangen.de/publication/download/cgo2007-shrink.pdf

DOI: 10.1109/CGO.2007.14

Abstract

Procedural abstraction (PA) extracts duplicate code segments into a newly created method and hence reduces code size. For embedded micro computers the amount of memory is still limited so code reduction is an important issue. This paper presents a novel approach to PA, that is especially targeted towards embedded systems. Earlier approaches of PA are blind with respect to code reordering, i.e., two code segments with the same semantic effect but with different instruction orders were not detected as candidates for PA. Instead of instruction sequences, in our approach the data flow graphs of basic blocks are considered. Compared to known PA techniques more than twice the number of instructions can be saved on a set of binaries, by detecting frequently appearing graph fragments with a graph mining tool based on the well known gSpan algorithm. The detection and extraction of graph fragments is not as straight forward as extracting sequential code fragments. NP-complete graph operations and special rules to decide which parts can be abstracted are needed. However, this effort pays off as smaller sizes significantly reduce costs on mass-produced embedded systems. © 2007 IEEE.

Authors with CRIS profile

Alexander Dreweke Lehrstuhl für Informatik 2 (Programmiersysteme) Marc Wörlein Lehrstuhl für Informatik 2 (Programmiersysteme) Michael Philippsen Lehrstuhl für Informatik 2 (Programmiersysteme)

How to cite

APA:

Dreweke, A., Wörlein, M., Fischer, I., Schell, D., Meinl, T., & Philippsen, M. (2007). Graph-based procedural abstraction. In International Symposium on Code Generation and Optimization (CGO'07) (pp. 259-270). San Jose, CA, US.

MLA:

Dreweke, Alexander, et al. "Graph-based procedural abstraction." Proceedings of the International Symposium on Code Generation and Optimization, CGO 2007, San Jose, CA 2007. 259-270.

BibTeX: Download