Abstract
This session was dedicated to the production of efficient circuits and software codes from Esterel programs. It began with the case of loops in circuit translation, which poses the particularly tricky problem of instruction reincarnation, i.e. the possibility of executing the same instruction several times in succession but simultaneously during the same reaction. This poses no difficulty for an interpreter, but for efficient compilation, some of these instructions must be copied a sufficient number of times.
We showed how to move gradually from a trivial but exponential method to quadratic and then quasi-linear methods, adopted in industrial compilers, recalling why constructive semantics leads to correct circuits even if they include combinatorics cycles (see the lecture of March 26, 2014).
The lecture then briefly introduced a radically different, more efficient compilation method for software targets, initiated by Stephen Edwards at Columbia University. Once reincarnation has been dealt with, and by taking advantage of subtle state encoding and the fact that software tests evaluate only one branch while Boolean propagation always traverses both in circuits, this method leads to better performance than that achieved by circuit translation, possibly even becoming sublinear in program size. A variant has been implemented in the Esterel v7 industrial compiler from Esterel technologies, whose development I directed.
