Last week I was preparing a lecture about the SystemC language and came across an article by Stephen A. Edwards, “The Challenges of Synthesizing Hardware from C-Like Languages,” about various C-like languages used for describing hardware. Among the various languages and tools there was a link to U.S. patent No. 6 226 776 on synthesizing C into hardware, which now supposedly belongs to Synopsys. The author of the article describes the patent as “claiming broad support for the ANSI C language”: support for pointers, recursion, and dynamic memory allocation is mentioned.
I got interested in this patent. About 85 pages out of the total 108 are examples in C and their corresponding synthesis results in Verilog. Another 14 pages are a verbal description of all the examples. And the last four pages are devoted to describing the claims of the invention. The models are mostly presented as finite-state machines, much less often as data-flow models. There was no method as such for converting C into a finite-state machine. I noticed one example in which one function called two others.
`int sum1 (int n) { int i, sum = 0; for (i = 0; i < n; i++) sum += i; return sum; }
int sum2 (int array[], int size) { int i, sum = 0; for (i = 0; i < size; i++) sum += array[i]; return sum; }
int f1() { int i; int array[10]; int size = sizeof(array)/sizeof(array); for (i = 0; i < size; i++) array[i] = i * 2; return sum1(size) + sum2(array, size); } This source code was highlighted with Source Code Highlighter.`
Before reading on, think about it: how many states does the machine need to execute this algorithm? At first it seemed to me, too, that it shouldn’t be many. But in the proposed synthesis variant, executing this algorithm requires 16 states of the machine. Since my C++ to VHDL compiler is not yet capable of compiling such code, I decided to draw the flowchart of the algorithm by hand.
All the functions have already been inlined, and it is assumed that the variables are initialized on the reset signal. Thus, this machine ends up with only seven states (see S. I. Baranov, Synthesis of Digital Machines).
What I can’t figure out is this: over there in 2001, did they not know what we had known back in 1974?