Treffer: Automatic Differentiation of Compiled Programs

Algorithmic differentiation (AD) is a set of techniques to "differentiate computer programs": Given a primal program that evaluates some mathematical function, AD allows to evaluate the derivative function. Unlike numerical difference quotients, algorithmic derivatives are accurate up to machine precision and, in the "reverse mode", can be formed with respect to a large number of input variables in one stroke. When combined with gradient-based optimization algorithms, AD is therefore a powerful tool to optimize engineering designs or learn weights of neural networks, besides many other applications. Up to date, most implementations of AD access the primal program via its source code, which they require to be available and written in a limited set of programming languages, typically not supporting the full language standards without manual user intervention. In this dissertation, we present the novel AD tool Derivgrind that interacts with the machine code of the compiled primal program. Implemented in the Valgrind framework for dynamic binary instrumentation, Derivgrind augments portions of machine code with AD logic just in time before they potentially execute on the processor. Specifically, Derivgrind's forward-mode AD logic keeps track of a floating-point "dot value" for every floating-point number appearing during the execution of the primal program. These dot values store the derivatives with respect to a single input variable, and are computed alongside, using elementary differentiation rules. Derivgrind also implements reverse-mode AD, by inserting AD logic that tags all floating-point numbers with identifiers, and uses them to record the real-arithmetic evaluation graph on a datastructure called the "tape". Besides our extensive suite of regression tests and a simple numerical solver for Burgers' partial differential equation, we have tested Derivgrind on three larger software projects: the Python interpreter CPython, the spreadsheet software LibreOffice Calc