Yosinori Watanabe Cadence Design Systems, USA

This paper proposes a procedure for minimizing the code size of sequential programs for reactive systems. It identifies repeated code segments (a generalization of basic blocks to di-rected rooted trees) and finds a minimal covering of the input control flow graphs with code segments. The segments are dis-junct, i.e. no two segments have the same code in common. The program is minimal in the sense that the number of code segments is minimum under the property of disjunction for the given control flow specification. The procedure makes no assumption on the target proces-sor architecture, and is meant to be used between task synthe-sis algorithms from a concurrent specification and a standard compiler for the target architecture. It is aimed at optimiz-ing the size of very large, automatically generated flat code, and extends dramatically the scope of classical common sub-expression identification techniques. The potential effectiveness of the proposed approach is demonstrated through preliminary experiments.