Generating Perfect Reversals of Simple Linear-Codes

Abstract

Bi-directional execution - executing forward as well as in reverse - is useful in many contexts. However, traditional techniques for bi-directional execution are not scalable, as they require infinite storage in the presence of "destructive" assignments. We present a new approach that eliminates the scalability problem for bi-directional execution of a class of functions called linear codes, which are sequences of assignments of arbitrary linear expressions to variables. Examples of linear codes include Fibonacci-like sequence generators, and operators such as shift, swap and rotate. We present an algorithm to generate perfect forward-reverse code pair from any given linear code, and show that any linear code can be perfectly inverted despite the presence of destructive assignments and apparent singularities in the input code. While existing techniques require memory size proportional to forward execution length, the code generated by our algorithm uses bounded amount of memory. The memory is proportional only to the number of variables in the given forward code, and is independent of both forward code size and forward execution length.