Process for converting programs in high-level programming languages to a unified executable for hybrid computing platforms6983456Abstract A system and method for compiling computer code written to conform to a high-level language standard to generate a unified executable containing the hardware logic for a reconfigurable processor, the instructions for a traditional processor (instruction processor), and the associated support code for managing execution on a hybrid hardware platform. Explicit knowledge of writing hardware-level design code is not required since the problem can be represented in a high-level language syntax. A top-level driver invokes a standard-conforming compiler that provides syntactic and semantic analysis. The driver invokes a compilation phase that translates the CFG representation being generated into a hybrid controlflow-dataflow graph representation representing optimized pipelined logic which may be processed into a hardware description representation. The driver invokes a hardware description language (HDL) compiler to produce a netlist file that can be used to start the place-and-route compilation needed to produce a bitstream for the reconfigurable computer. The programming environment then provides support for taking the output from the compilation driver and combining all the necessary components together to produce a unified executable capable of running on both the instruction processor and reconfigurable processor. Claims We claim: Description COPYRIGHT NOTICE/PERMISSION
This code segment first declares three arrays (a, b, c) that will be used to hold data used in the computation. The arrays are declared in a common block, meaning their storage allocation will be in the instruction processor's memory and not a local stack space associated with the procedure. There is an external call to a procedure that can be assumed to initialize the data in the arrays. After that initialization call is a do-loop that contains the computation portion of this procedure. The portion of code that has been identified to execute on the hardware logic is determined to be the loop body enclosed by the do-loop construct. Using syntax that is recognized by the compiling system which will generate hardware logic, the Fortran code may be modified to resemble this:
Here the do-loop has been bracketed with pair of directives that will provide the information needed by the compiling system. The compiling system processes this information to build both the procedure that will run on a general purpose processor and the subprogram that will execute on hardware logic. The conversion of this single Fortran procedure into separately compilable procedures may involve several compilation phases. In one phase, the compilation system processes the individual source files contained within the program, discarding from further reconfigurable hardware logic compilation source files that do not have syntax indicating that hardware compilation is desired. When the compilation systems encounters syntax indicating that reconfigurable hardware compilation is desired, the compiling system starts to build up the infrastructure needed to implement the compilation of this source file on both the instruction processor and the bracketed portion on the hardware logic. In addition to creating source files needed for the instruction processor compilation phase and the hardware logic compilation phase, the mechanisms used to allocate, reserve, and release the hardware logic resources are also generated. The bracketing syntax may include scoping information for all variables used within the bracketed region. This scoping information may be used by the compiling system to build the correct data movement statements and to ensure that the integrity of the program remains the same as it would be if it had been run entirely on the instruction processor. Scoping data and variables as "global" indicates to the compiling system that this data is persistent across the calling boundary between the instruction processor and the hardware logic. The mechanism that moves the data to the hardware logic and retrieves the data from the hardware logic may be built into the new subprograms being created by the compiling system. Global data may be handled in a similar fashion so that the integrity of the data is preserved. Scoping data and variables as "private" indicates to the compiling system that these variables are local in scope to just the hardware logic, and therefore their resultant values do not need to persist past the point of hardware logic execution. As a variation to this syntax, there is an additional syntax that allows private data to be "copied out" to a local variable in the instruction processor version of the source file. The compiling system can use this data scoping information to generate two separate source files, each of which represents a portion of the original source file containing the bracketing syntax. One of the new source files will be compiled and executed on the instruction processor's system. The other source file will be used to generate the hardware logic. This process is illustrated in FIG. 5. High-level Language Converter A component of the compiling system that is invoked first to initiate a traditional compilation phase, similar to compilation on any instruction processor system. This component receives as input any programming language code and extracts from the source file(s) tokens which can then be parsed. While the parsing phase is taking place, semantic analysis may also be performed, so that after this phase an internal representation of the code and a symbol table may be produced. Semantic error checking is done and the appropriate diagnostic messages are issued. The internal representation of the source code now generated by this compilation phase resembles control flow blocks of code. The next step is to expand on these control flow blocks into the internal language that will be processed by the optimizer. During this expansion phase, each control flow block may be expanded into units called either basic blocks or extended basic blocks. A flow graph may be a directed graph of the basic blocks in a function, which represents the function's control flow. Each node in the graph corresponds to a basic block. The flow graph may be updated during compilation as optimizations occur. The major global optimizations performed during this step may include invariant code motion; induction variable analysis; and, global register assignment. Other optimizations may include the merging of code blocks as well as peephole optimizations that result in optimized control flow code blocks. After the global register assignment optimization, the calling parameters of the routine may be written to an intermediate file that may be used as the input into the next compilation phase. The calling parameters are written along with their data types, followed by the user symbols associated with the routine and their data types. After writing out the symbols used in the routine, the next portion of the file contains the traversal of the terminal code blocks showing the type of basic block represented and the instructions associated with the code block. Once this control flow representation has been produced, the final step produces all the instructions that were generated during the compilation of the routine. These instructions may correspond to the instructions listed in the control flow blocks. As is the case for any architecture, a compiler is required to process a program written in higher-level languages into equivalent programs in a machine language for execution on a computer. System 100 satisfies the above requirement with the ability to translate programs for a traditional instruction processor alone, or in combination with a reconfigurable processor. The compiler phase used to translate this higher-level language is based on instruction processor compiler technology. The HLL converter uses a mixed model of compilation with language-specific front-ends to generate a common high-level intermediate representation. This first level of representation is then input into various basic optimizations, including control flow analysis, so that the resulting second-level intermediate representation can be referred to as a control flow representation. The control flow representation becomes a major component in the control flow information file that is generated as output by the HLL converter. The following text provides additional details on the contents of this file and also the additional files that can be produced as a result of this stage of compilation. Input to the HLL converter can consist of two different types of source code. Any higher-level language source code can used as input into the HLL converter, provided that this code is written to conform to the language standards which it represents. Another input to the HLL converter is source code that represents control flow information for the higher-level language originally represented. This control flow information has been written to a well-defined interface specification so that control flow information from a previous compilation can be used (as described later) or control flow information that has been derived from another source, such as another uP executable, can be used. After the control flow analysis has revealed the hierarchical flow of control within each procedure, a representation of the control flow can be generated as an intermediate language. The control flow information file that is produced at this point contains, but is not necessarily limited to, the following: entry symbols, user symbols, basic blocks, and intermediate representation instructions, among others. Entry symbols represent the symbols created by the HLL converter that will be the parameters passed in a calling routine, which serves as the interface between the instruction processor portion of the executable and the hardware logic. These symbols may pass addresses of data that will accessed by the hardware logic as well as scalar values for computation. User symbols are the symbols that represent the variables in the region of code being compiled for hardware logic. These symbols correspond to variable names in the higher-level source code, including constructs such as arrays and structures. Symbols may also represent any external routine calls; it is here that hardware logic modules may be visible in the compilation process. A basic block may be a maximal sequence of instructions that can be entered only at the first of them and exited only from the last of them. The basic blocks representing the given source code are listed here. Every basic block starts with a block information header entry. This entry provides the relative block number, the source line number that this basic block represents, the label defined by this block (if one exists) as it is represented in the associated symbol table. Following this information is a list of flags representing attributes for these basic blocks. These flags provide more information about the block such as if this block contains the entry to the procedure; if this block has any external references; and, if this block's control falls through to its immediate successor. Immediately following the block information header line is a list of the instructions that represent terminal nodes. Examples of these types of instructions are stores of data to memory, unconditional or conditional branches or procedure calls. Each terminal node is represented by its relative number within the basic block, the line number which points to the "tree" of instructions representing the statement, and then flags that provide more information on that node. The instructions referenced by the basic block section may be listed in the intermediate representation instructions. This section contains the individual instructions that have been generated during compilation and used for optimizations up to this point. These instructions have been grouped into basic blocks and their relationship with one another has already been established in the previous section. They are generated here in the order that they were created during the compilation process. The first entry is the relative number of the instruction in this instruction list. Next is the instruction name, followed by each of the operands for this instruction. Information for operands may be provided if the operand is a label pointing to an entry in a table of variable and entry point names. Internally generated names from the compilation are also shown. Information may be provided about the datasizes being loaded or stored from memory. More details on the types of instructions that can be referenced in the control flow information file are given in the interface specification section. The generation of the control flow information file is based on options provided either in the compilation command line or in the source code itself. Adding an option to the compilation command designates which subprogram contained within a larger source file of subprograms is to be targeted for hardware logic. During compilation, only the designated subprogram will have its control flow information written out to a separate file for further hardware logic compilation. The remaining source code subprograms will be compiled to generate the instruction processor machine code. Control flow information files can also be generated based on the existence of partitioning, or bracketing, syntax that is recognized and parsed by the compiler. This partitioning syntax is used in conjunction with language-specific source lines such that, if this source code is compiled for a different architecture then the partitioning syntax may be ignored during compilation. Keywords defined for this syntax enable a region of the entire source code to be extracted and compiled as a separate subprogram for hardware logic. As described above with the command line option, only this specially bracketed region will have its control flow information written out to a separate control flow information file for further hardware logic compilation. If no partitioning syntax is present in the code and there is no command line option to designate a specific subprogram as being targeted for hardware logic compilation, then the compiler may default to compiling the entire source code as a candidate for hardware logic. The control flow information about each subprogram may be written out and passed along for further compilation. The next compilation step will do the analysis needed in determining the best point in the control flow for partitioning to create a subset control flow information file. This new control flow information file is passed back to the HLL converter to create the necessary MAP proxy routines needed. The compiler utilized to generate a control flow information file from a higher-level language or to process a previously generated control flow information file must also create various other procedures that provide the necessary functionality for hardware logic execution. These procedures provide functionality by supporting an interface between the execution of the code on the uP processor and the execution of the code on the reconfigurable processor. This interface functionality is termed, "MAP proxy". FIG. 6 shows an example of the interface functionality. Code contained in the control flow information file 610 may include the region of source code that will be executed on the hardware logic. That file continues through the compilation process with the result being FPGA bitstreams suitable for hardware logic execution. Code contained in the MAP proxy 615 may be scheduled for execution on the instruction processor in place of the region of control flow information that has been partitioned for execution on hardware logic. This code handles the data movement needed in support of the hardware logic execution by inserting data manipulation constructs that are appropriate for the target reconfigurable processor. The MAP proxy also may insert runtime library calls used when executing to interact with the operating system. This interaction includes the allocation of hardware logic resources; querying of hardware logic status; the release of hardware logic resources back to the system; and, the transfer of control from the instruction processor process to the hardware logic. The final step for the HLL converter is to generate the machine code needed to execute on the targeted instruction processor processor. The HLL converter produces control flow information for the entire source code and also the MAP proxy code. This information is then translated down to the machine code, so that the binary files produced from this compilation can be used as input into the linking step that will result in the unified executable. Hardware Logic Module Information Files: Concept and Structure Another component of the compilation system is a data base that describes the mapping of the operators, intrinsic function calls, and procedure calls in the source of the MAP procedure to existing (system defined) hardware logic modules. The database is called the system info file. Optionally, a user may define additional hardware logic modules which may be called as if calling a procedure in the source of a MAP procedure, or which may be used to redefine the intrinsic system defined hardware logic modules described in the system info file. In order to compile for MAP using user defined hardware logic modules, the user must provide a data base which maps the procedure name or operator overload to the user defined hardware logic module. This database is called the user info file. Every opcode in the nodes of a dataflow graph representation of the MAP procedure being compiled must be defined in an info file entry. Hardware logic module information files are used by both the CFG to CFG-DFG converter dataflow graph generator and by the CFG-DFG to HDL converter Verilog generation phases of compilation. A hardware logic module information file includes of one or more entries concatenated into a single file. Each entry describes a unique operation (op-code) represented in the dataflow graph or a function or subroutine that has been instantiated thru a call from the MAP procedure being compiled. This description includes an interface to the hardware logic module that is to be instantiated to perform the operation, including it's inputs, outputs, any input or output signals the module is to be connected to, and characteristics of the hardware logic module. Optionally, an entry may contain functionally equivalent pseudo code that may be used in dataflow graph emulation mode, or various simulation modes to emulate/simulate the modules functionality. A hardware logic module information file entry is delimited with a begin-def and end-def marker, and takes the form:
The <opcode> is the ASCII string matching the op-code in the dataflow graph corresponding to the operation, or the name of a procedure called in the source code of the MAP procedure. The <mapping and emulation information> consists of a sequence of entries, each ending with a semicolon. The order of these sections of the hardware logic module information file entries does not matter. MACRO="<macro_name>"; The <macro_name> is the ASCII string representing the name of the hardware logic module that performs the function of the operation or procedure the hardware logic module information file entry describes. LATENCY=<num>; The <num> is an integer value specifying the number of clock cycles between the presentation of data to the hardware logic module's inputs and the availability of corresponding results on the outputs. STATEFUL=YES|NO; YES indicates the hardware logic module holds state between iterations, typically in an internal register; NO indicates it does not. EXTERNAL=YES|NO; YES indicates the hardware logic module interacts with entities outside of its code block; NO indicates it does not. PIPELINED=YES|NO; YES indicates the hardware logic module is pipelined such that it can accept new inputs each clock; NO indicates it is not. INPUTS=<num>:<input specs>; OUTPUTS=<num>:<output specs>; <num> is the number of inputs or outputs to the operation or procedure in the source of the MAP procedure, or to the node which represents it in the dataflow graph. There must be <num> input or output specs specified in the INPUTS or OUTPUTS specifier. Each <input spec> takes the form: I<n>=<type><nbits> BITS (<input_port_name>) Each <output spec> takes the form: O<n>=<type><nbits> BITS (<output_port_name>) <n> is an integer that specifies the zero based input or output sequence number to the operation or procedure call in the source of the MAP procedure or in the node of the dataflow graph. The numbering of the inputs and outputs is independent; each begins at zero. <type> is the data type of the input or output. It may be INT, FLOAT, or ADDRESS. (This will be expanded to include additional types, COMPLEX, LOGICAL, REAL, INTEGER, CHAR, CHARACTER). <input_port_name> and <output_port_name> represent the corresponding input or output port names of the associated hardware logic module. IN_SIGNAL:<nbits> BITS "<macro_port_name>"="<internal_signal_name"; OUT_SIGNAL:<nbits> BITS "<macro_port_name>"="<internal_signal_name"; These describe hardware logic module connections which are not visible at the source code or dataflow graph level. <nbits> is the nuber of bits of the input or output signal. <macro_port_name> is the name of the signal into (IN_SIGNAL) or out (OUT_SIGNAL) of the hardware logic module. <internal_signal_name> is the name of the source (IN_SIGNAL) or target (OUT_SIGNAL) signal in the compiled hardware logic. There are currently three internal source signals available:
CLOCK is the clock source for all hardware logic modules. rst is the one-time global reset. code_block_reset is a reset signal that is activated anytime a hardware logic module's code block is activated. There are currently no documented signals to target. These will include error, overflow, or exception conditions detected during execution of the hardware logic module in the future. DFG=#<simcode># <simcode> is C code which is used as an functional definition of the hardware logic module's behavior during dataflow emulation. Syntax extensions are planned to the hardware logic module information file entries to specify variations of these or additional characteristics of the hardware logic modules. These characteristic variations and additions include, but are not limited to the description of hardware logic modules which can accept new inputs each n iterations, which can accept inputs for n iternations and produce i results after j clock periods, a means to specify the frequency at which a hardware logic module executes, actual code or a directory path to a file containing HDL code which define the hardware logic module for simulation, and a specification of resource requirements for the hardware logic module. Translating Hardware Logic Module Information Files In addition to the data flow graph, there is a second input file to the CFG-DFG to HDL converter. This is a CFG-DFG to HDL converter binary file containing the interfaces and information about the hardware logic modules contained in the hardware logic module information files. In an embodiment of the present invention, a small executable may be used which translates the ASCII hardware logic module information file into CFG-DFG to HDL converter internal tables and is executed during compilation prior to invoking the CFG-DFG to HDL converter. This translation program may be invoked with one required and two optional command line options. The required option, -o outfile, indicates the name of the output file where the CFG-DFG to HDL converter tables are to be written. The option -d deleted_signal indicates the name of an input or output signal in the hardware logic module information file to be ignored; that is, the translation program will skip processing of a signal named deleted_signal in an hardware logic module information file which is specified in a -d option. This allows an hardware logic module information file entry for a hardware logic module to contain test signals or signals used in simulation that may not exist when generating actual hardware logic. The second optional command line argument is -r sigval=newsigval. The translation program replaces occurrences of pin or wire names specified by sigval in the hardware logic module information file with the string newsigval in the resulting CFG-DFG to HDL converter table. This option allows renaming the hardware logic module's input and output signals which are to be connected by the CFG-DFG to HDL converter. The CFG-DFG to HDL converter may ignore any connections that are to be connected to a wire whose name begins with "unconnected_". By renaming "unconnected_" wires with this option, they may be processed by the CFG-DFG to HDL converter. As with the -d option, -r is useful when generating an HDL like Verilog which will be used in a test bench or simulation environment and that may have signals that are not actually present in the generated Verilog for the resulting hardware logic. Multiple -d and -r options may be specified. The translation program may start by initializing the CFG-DFG to HDL converter tables to be built, calling gr_tables_init in the CFG-DFG to HDL converter support library. Next the command line options may be processed. An array of character pointers is built containing the list of deleted signals specified by the -d command line options. Two parallel arrays of character pointers are built for the renamed signals (-r option). The first array contains the strings specified by sigval in the option, the second array contains the strings specified by newsigval in the option. For a given renamed signal in the first array, its corresponding new name is located at the same index in the second array. The output file name specified with the -o option is inserted into the CFG-DFG to HDL converter OUTPUT_FILES table. After tables are initialized and the command line is processed, the hardware logic module information file(s) are parsed and an array of subref data structures is constructed. There may be two hardware logic module information files containing an arbitrary number of entries. One hardware logic module information file is assumed to contain interfaces which map the opcodes which appear in nodes of the data flow graph to specific hardware logic modules known to the compilation system (the intrinsic operations). This hardware logic module information file is called the system hardware logic module information file, and is located by reading a environment variable. The second hardware logic module information file, which is optional, contains interfaces to user provided hardware logic modules which are not intrinsically know to the compiler, as well as any user provided redefinitions of any of the intrinsic hardware logic modules. Parsing of the hardware logic module information file and creation of the array of subref structures is performed by a function shared with CFG to CFG-DFG converter, fetch_all_subrefs. The parser and semantic routines of fetch_all_subrefs may be generated by the gnu tools flex and bison. A subref structure is used to store the information in the hardware logic module information files internally to the translator program and The CFG to CFG-DFG converter. As each opcode info file definition is parsed, the information is stored into a subref structure. Parsing continues until all the hardware logic module information file entries have been parsed, and an array of subref structures has been built. The translator program then enters loops thru the array processing one subref structure at a time while building the CFG-DFG to HDL converter tables which hold the hardware logic module interfaces. The CFG-DFG to HDL converter tables built from the processing of the subref structures are EQUIV_IN, EQUIV_OUT, EQUIV_IN_PRS, PIN_NAMES, HELD, BEHAV_V, and BEHAV_C. The content of each of these tables is indicated in the discussion of subref structure processing (below). There is one EQUIV_IN and one EQUIV_OUT table entry created for each subref structure processed. The table index for the EQUIV_IN and EQUIV_OUT table entries for a given subref are the same. Processing of a subref structure begins by checking the opcode name field of the subref structure. If no name was specified in the hardware logic module information file entry, an error is issued and the rest of the current subref structure is skipped. If a name is specified, the CFG-DFG to HDL converter tables built from previous subref processing are searched for a previous subref with the same opcode name. If one is found, a warning may be issued, and further processing of the duplicate named subref may be skipped; the first hardware logic module information file entry for the opcode name is used. Note that the user's info file entries are the first entries parsed, and their corresponding subref structures appear in the array of subrefs with the smallest array indices. Thus, a user may provide their own hardware logic module for any given opcode which is intrinsically known to the compiler, and due to the order of processing of the subref array, the user's info file entry for that opcode overrides any entry in the system's info file. The index of the first free entry in the EQUIV_IN_PRS is saved and will later be placed in the EQUIV_IN table entry for the current hardware logic module information file entry. This is used to locate the first input parameter for the hardware logic module. The latency for the hardware logic module is also save for later insertion into the EQUIV_OUT table entry for the current info file entry. If the latency is not specified or if it is negative, and error is issued and a value of zero is used for the latency. The output parameters may be processed first. For each output, an EQUIV_IN_PRS table entry is created. The output's bit width and the index to the EQUIV_IN/EQUIV_OUT table entries for this subref are inserted into the EQUIV_IN_PRS table entry. A flag indicating this is an output is also set in the EQUIV_IN_PRS table entry, distinguishing it from an input. A PIN_NAMES table entry is then created for the output parameter. A PIN_NAMES table entry has the output parameter's name, it's width in bits, the index to it's previously created EQUIV_IN_PRS table entry, the index of the current subref's EQUIV_IN/EQUIV_OUT table entry, and a flag indicating this is an output pin set. If this is the first PIN_NAMES table entry created for the current subref (the first output parameter processed for the module), the PIN_NAMES table index is saved for later insertion into the EQUIV_OUT table for the current subref. The output signals for the opcode are processed after the output parameters. The list of deleted signals specified by -d command line options is searched to determine if the output signal should be entered into the CFG-DFG to HDL converter HELD and PIN_NAMES tables. If it is found, the signal is skipped; otherwise a HELD table entry is created. The HELD table entry contains the index to the associated PIN_NAMES table entry for the signal, the bit width of the signal, and the name of the external signal the output signal should be connected to. The table of renamed signals specified by -r command line options may be searched to see if the signal has been remapped. If it has, the remapped signal name is used; otherwise the name specified in the hardware logic module information file is used. If no external signal name is specified, and error is issued. A PIN_NAMES table entry may then be created for the output signal. The PIN_NAMES table entry contains the EQUIV_IN/EQUIV_OUT tables index for the current subref entries, the output signal's bit width, the index of the HELD table entry created for this signal, the signal's name internal to the hardware logic module, and two flags indicating the signal is an output and that there is a HELD table entry for the signal. If this is the first signal processed for the subref structure, the index of the PIN_NAMES table entry is save for insertion in the EQUIV_OUT table entry for the subref. After the output signals are processed, the input parameters for the subref are processed. An EQUIV_IN_PRS and a PIN_NAMES table entry are created for each input. The contents of the EQUIV_IN_PRS entry may be identical in content to one made for an output parameter with the exception that the flag indicating an output parameter is not set. The PIN_NAMES table entry contains the same information as a PIN_NAMES table entry for an output parameter, except a flag indicating an input is set rather than the flag indicating an output parameter. The input signals are processed after the input parameters. For each input signal, a HELD and a PIN_NAMES table entry are created. The processing of the input signals and the resulting table entries are identical to that for output signals, except a flag indicating the signal is an input rather than an output is inserted in the PIN_NAMES table entries. The last PIN_NAMES table entry has now been made for the subref, and the last entry's index is save for insertion into the subref's EQUIV_OUT table entry. Finally the EQUIV_IN and the EQUIV_OUT table entries are generated for the subref. The EQUIV_IN table entries contain the index of the first EQUIV_IN_PRS table entry made processing this subref structure. The index of the last EQUIV_IN_PRS table entry made for this subref, and the name of the data flow graph opcode this subref defines. The EQUIV_OUT table entry contains the latency of the associated hardware logic module, the name of the hardware logic module, the index of the first PIN_NAMES table entry associated with the subref, the index of the last PIN_NAMES table entry associated with the subref. Processing of the subref is now complete. info2grf continues until all subrefs structures are processed. If no errors were found during processing, the CFG-DFG to HDL converter tables are written to the output file and a zero status code is returned. Otherwise, no tables are output and a non-zero status code is returned. The translation program may then terminate. Converting CFG into Hybrid CFG-DFG Embodiments are now described for converting CFG representations into hybrid CFG-DFG representations. The original CFG representations may include nodes and directed edges, where each node may be a basic block of code, and each edge may show a transfer of control from the exit of one block to the beginning of another. The code in a basic block may have a single point of entrance and a single exit, that is, it may represent a straight sequence of statements that cannot be branched into or out of other than at the beginning and the end, respectively. The statements in a basic block may be sequential. The hybrid CFG-DFG representations may have CFG representations at its upper level, but with dataflow graphs in each code block. In one embodient, CFG to CFG-DFG conversion may consolidate groups of basic blocks, including groups that form inner loops, into flat and possibly pipelined code blocks. FIG. 7 shows an example of a portion of a CFG that corresponding to the following code fragment:
In this example, the conditional test comparing 'a' and 'b' may be stored to a register or temporary variable, and may the last statement in its basic block. Based on the result of the comparison, control may be transferred to one of two blocks that represent the "true" and "false" parts of the conditional construct. Each of these blocks, after executing its statements, may transfer control to the block containing the code that follows the conditional. Note that the code blocks in a CFG may contain sequential statements, each of which may reference registers or variables by reading and writing them. Also, note that the directed edges between blocks may represent a transfer of control that could be viewed as a one-bit "trigger" signal. While CFG representations may be used in many compilers as an internal intermediate representation, dataflow graphs are not usually used because the dataflow execution paradigm is poorly suited to conventional von Neumann processors, due to its use of arbitrarily many functional units and its asynchronous execution. However, the dataflow model is well-suited for reconfigurable hardware. In a dataflow graph, the nodes may represent functional units (e.g., integer add). The directed edges between nodes may represent data connections that bring output data items from one functional unit to the inputs of other functional units. FIG. 4 shows a dataflow graph for the following code fragment:
The incoming values of 'b' and 'c' may be loaded at the top of the graph. Their values may flow out of the output ports (bottom) of the LOAD nodes. The dataflow graph may expose instruction-level parallelism. Here, three instructions (two multiplies and a subtract) may occur at the same time. Note that the 'd' variable may not need storage since it may be local to the graph and may exist as an edge. Also note that the intermediate value assigned to 'a' may not be stored to that variable, but simply may exists as an edge since a subsequent assignment below may create the final value of 'a'. A dataflow graph such as this may be mapped directly onto reconfigurable hardware by instantiating selected functional units. In this example one add, two subtracts and two multiplies would be created. The sequential statements in each basic block of a CFG representation may be converted to a dataflow graph, thereby producing a hybrid where the upper level nodes are code blocks with single-bit edges, and within each block may be a dataflow graph whose nodes may functional units and whose edges may be data connections. FIG. 8 shows an example of such a conversion applied to the CFG of FIG. 7. In an embodiment of the invention, subsets of basic blocks in a CFG representation may be merged into a single dataflow code block where conditionals may be handled by computing both sides and then selecting the appropriate values based on the predicate expression of the conditional. FIG. 9 also shows and example of such a code block, where the code blocks of FIG. 8 have been merged. In addition to scalar and array data types, high-level languages may have structures, which are user-specified data types that may be composites of simpler types. Conventional compiler front ends, when generating CFG representations, may deal with these by producing the appropriate address calculations in the basic blocks they produce. When such a structure may be in a local memory, the address calculations may be left unchanged when converting the graph to a control-dataflow graph. In the case of structures as local variables, the conversion process uses the type information along with the address offsets to determine which field of the structure is being referenced. Pointers may be dealt with according to the architectural details of the target machine. If the reconfigurable hardware "sees" the same memory space as the processor that has passed address parameters to it, pointer arithmetic may work with no modification. If not, an adjustment factor is computed at run-time; this factor may be the difference between an address in the processor's memory and the place the data was copied to in the reconfigurable hardware's OBM. The control-dataflow graphs are generated so that they may include the addition of this factor when referencing a pointer. Conventional high-level languages may have a small set of fixed-size arithmetic data types (e.g., 32-bit integers and 64-bit integers). This corresponds to the fact that the von Neumann processors they target may have fixed-size functional units. In reconfigurable hardware, it may be possible to instantiate functional units of any bit-width, which may achieve a saving of space by using an amount of precision needed for a given program. One way this savings may be achieved is to extend the high-level language to include new data types with user-specified bit-widths. Another approach may be to allow the user to specify the bit-width of the standard types (e.g., "int") for a section of source code. It may possible for the compiler to infer the safety of reducing the precision of some functional units and the data paths they connect to. For example, in the code:
In another embodiment, a component of the translation of CFG representations to control-dataflow graphs may be a database that describes the mapping of operators and function calls to existing hardware logic modules. This database, may be called an "info file", and may be used at various steps during compilation. Function calls may be dealt with in a variety of ways, depending on the nature of the routine being called: If the routine is associated, via the "info file", with a hardware logic module, then a single node may be produced in the dataflow graph to represent it as a functional unit. If the routine meets appropriate criteria, it may be inlined so that the call mechanism may not be needed. If the function is tail recursive, it may be converted to a loop. If a function does not fall in the above categories, then a stack-oriented call mechanism may be used. In another embodiment, LIFO stacks may be implemented in the reconfigurable logic that may hold the various instantiations of local variables as the recursion takes place. Stack information may also direct the flow of control so that the returns of the recursive calls take place correctly. The hybrid control-dataflow graph may adapt itself to multiple threads of execution within a subroutine compiled to reconfigurable hardware. While the semantics of high-level languages may specify sequential execution (where one code block may be active at any given time), parallelism at the code block level may be easy to implement when the compiler can determine that parallel execution may not produce incorrect results. This determination may come in a variety of ways, depending on the language and its possible extensions: For example, if the language contains parallel constructs, the parallelism may come in as part of the CFG representation. Also, a sequential language may be extended by user pragmas that may allow the programmer to direct the compiler to make certain parts of the code parallel. Analysis may allow the compiler to prove that certain code blocks may be safely executed in parallel. FIG. 11 shows an embodiment that has, at left, a sequential part of a CFG representation, and at right a transformed graph where two code blocks have been made concurrent. The trigger signal from the preceding block fans out to trigger both concurrent blocks, and a "join" mechanism called a LATCH_AND may used to merge the "done" signals from the two blocks. The LATCH_AND may be designed so that it latches each input signal when it goes high, so that the incoming triggers may not have to occur simultaneously. The control-dataflow graph's connectivity information may be used to improve the performance of logic placement in an FPGA. In current place-and-route tools, the placement problem may be viewed at a very low level, where the items being placed may be small logic blocks. If the hardware logic modules available to the compiler are already determined to be of specified shapes, the compiler may do placement at a much higher, hence much simpler, level of granularity, with a potentially significant speedup of the process. FIG. 12 shows the top-level process for converting a subroutine's CFG representation to a hybrid control-dataflow graph. One or more "info files" may be read to obtain information about the available hardware logic macros that may be available for implementation of the dataflow graph as reconfigurable logic. After reading the CFG representation into its internal data structure, the compiler may segregate "external" hardware logic module calls into individual blocks. This may be done because external modules interact with resources outside of their code blocks and race conditions might result if they were to execute concurrently. Next, individual blocks may be combined into larger blocks, as in the example of FIG. 10. Each block may then processed. For non-loop blocks, LOAD nodes may be created for the various scalar values that are referenced. Then the dataflow graph of the block's computation may be created. Finally, a STORE node may be created for each scalar variable to store its final value. Inner loops may require some additional handling. When the head block of an inner loop is found, the rest of the loop's blocks may be gathered and topologically sorted. Then LOAD and CIRCULATE nodes may be built for the scalars. The loop's code blocks may then be processed in a manner similar to that of non-loop blocks. After each DFG is created, delay nodes may be inserted to balance the path lengths (that may be measured in clock ticks) through the dataflow graph. Then a variety of optimizations may be performed on the graph. After all DFGs have been created, they may be written to a DFG file, and a logic emulation file may be created. The CFG representation may consist of two parts: an array of opcodes and a sequence of basic blocks. The opcodes may be read into an array of structures whose elements consist of one opcode and references to the opcode's data sources. Each basic block in the CFG representation may stored in a structure like the one shown below:
As the dataflow graph is built for a block, its nodes may be allocated in the "pool" field of the basic block structure. An example of the dataflow node structure may be show as:
In one embodiment, two files may be written as output: A dataflow graph file and an emulation logic file. The following simple C source function may be examples of these files:
The example code below shows the dataflow graph file that may be produced when the example C function is compiled:
The example dataflow graph above has two sections. The first is a list of the parameters and local variables, with name, type and kind (parameter or local). The second section is a listing of code blocks. In this example, the code blocks were not merged. Each block has a unique id number, and a set of dataflow nodes. Every block has a SRC^INITIATE node and a SRC^OUTPUT node as its beginning and ending nodes. For each node there is the following information: its function, its input and output counts, bit-width of each input, constant values for those inputs whose input is specified as constant, bit-width of each output, target list of each output (i.e., which other node input ports are fed by the output). Input and output ports may also have unique pseudo register ids in parentheses. The end of each block may specifie where control flow goes when the block is exited. Two target blocks may be specified as TRUE and FALSE targets when the block ends in a conditional. Otherwise one block may be specified, or EXIT may specified when the block is the exit of the function. FIG. 13 shows this set of code blocks in pictorial form. Along with the dataflow graph file, an emulation logic file may also written. This may be a simple C routine that may be executed as a thread, emulating the reconfigurable logic part of a program. An example of an emulation logic file for an example C function may be shown as:
In the example emulation logic file above, an infinite loop may act as the FPGA. As such, it may obey the same protocols, in this example using flag registers FR2 and FR4 as start and end handshakes, respectively. When it receives the start signal from FR2, the emulation routine may load initial values for the user subroutine's parameters. It then may call dfg_simulate, passing in the name of the DFG file to be executed. The dataflow simulator may do a token-driven simulation, returning when the EXIT code block has completed. Final values of the parameters may then be returned, followed by a FR4 handshake. The routine may then go back to the top of the loop to await another signal that it should execute. Another embodiment of the conversion of a basic block in the CFG to a code block in the DFG is now described. In this embodiment, loads/stores may be treated in two different ways, depending on whether they are scalar or array references. Scalar references may be converted to DFG edges, with a single load at the start of the block and a single store at the end. Array references may be converted to on-board memory (OBM) references. Scalar variable references for pass-by-reference parameters may differ from local variable references. The CFG output of the compiler's front end may reflect this: It may put a level of indirection into such parameter references. FIG. 14 illustrates the distinction. In another example, the following set of operations are considered: a=b+c c=b-a a=c*5 The front end may produce a set of op codes in its CFG output, shown in FIG. 15. Since this was Fortran source, the scalars may be brought in by reference, so the LDA (Load Address) nodes may perform an indirection step by fetching addresses from the addresses that may be input to them. Note that the graph sharing may not indicate common subexpressions. For example, the output of node may go to two places, representing the two reads of variable 'c' in the code. Those two reads may not produce the same value however since there may be an intervening store in between them. In an embodiment, the first step in processing a basic block may be to build dataflow graph fragments from the op codes. This may be done by a routine that starts at each anchor (bottom-most) op code and recursively builds a tree above it. There may be no sharing among the fragments, so the result of this routine may be to build the fragments shown in FIG. 16. In an embodiment, after the DFG fragments are built, the LDA nodes may be removed from beneath any ACONs (Address Constants) that carry scalar pass-by-reference parameters. This reflects the fact that the MAP compiler (i.e, the portion of the system that compiles portions of HLL source code to reconfigurable hardware) may be treating them as copy-and-restore, rather than by reference. This may leave the DFG fragments looking like those shown in FIG. 17. Next a list of all the referenced variables may be made, by starting at the anchors and looking upward to find ACONs. An INITIATE node may be created as the head of the DFG, and a layer of LD_SCALAR nodes may be created to bring in the initial values of the scalars. A temporary array of data structures may be created as a reference for the sources of each variable. An example of the structure is shown as:
The array may be initialized to refer all of the variables to their LD_SCALAR nodes. Subroutine and function calls may be processed and then the DFG fragments may be converted to a DFG. In one embodiment, the CFG-to-DFG conversion may be a routine that starts at the bottom of each DFG fragment and does the following: Scan upward to find load nodes. For each load, look at the ACON above it to determine which variable is being loaded. Remove the load node and rewire the node it targets so that it is fed by the current source of that variable. If the anchor is a store of a scalar, it looks at the right-hand input to see which variable is being stored. It then may eliminate the store node and record the node's left source as the new source for that variable. In the example, when the first anchor is processed, the LDKR nodes for values 'b' and 'c' may be found; they may be eliminated and the nodes they feed may be rewired to be fed from the LD_SCALAR nodes at the top of the DFG. Then the STKR node may be eliminated and the KADD node may be noted, in the temporary array, as being the new source of variable 'a'. When the next anchor is processed, its two LDKR nodes may be found. The 'b' value's source may still be its LD_SCALAR node, but the 'a' value's source may be the KADD. The LDKR nodes may be eliminated and their targets may be wired to the appropriate sources. The STKR node may then be eliminated and the KSUB node may be noted as the new source of variable 'c'. When the third anchor is processed, its LDKR may be eliminated and its target may be rewired to the output of the KSUB. Then the STKR may be eliminated and the KMUL may be noted as the new source of variable 'a'. Once all the anchors are processed, a layer of ST_SCALAR nodes may be created, storing the final values of the scalars by referencing the last sources of those variables. The ST_SCALARs have trigger outputs that may be gathered into a LATCH_AND node, and that node may feed an OUTPUT node at the DFG's bottom Any LD_SCALAR nodes whose outputs are unused may be removed by a dead-code elimination pass. The compiler may also looks for ST_SCALAR nodes that are storing the value that's coming from that variable's LD_SCALAR node, and may eliminate them since their values have not changed. FIG. 18 illustrates an example of the resulting DFG code block for this example. In an embodiment, the DFG generator may distinguish between loads/stores of scalar variables versus loads/stores of array elements. When it sees a load or store node (e.g. LDKR or STKR), it may determine the kind of load/store by looking at its address input. If it sees something of the form shown in FIG. 14, it may use the ACON node to find the variable's name, and it may consult an internal 'variables' data structure to find out whether it is a scalar variable. FIG. 19 shows an example of what array references may look like. Note that in this example of a hardcoded '1' index, the reference looks structurally the same as a scalar local variable reference; consultation of the 'variables' structure may tell it that this may be an array. Note also that ACON nodes may have a variable name and a constant offset. In the second example in FIG. 19, the offset of 48 comes from the fact that the reference is six elements away from the base address, and each element is eight bytes in size. The third form is where the address is fed by an expression tree. Here the ACON node for 'BB' may be given a -8 offset to compensate for the fact that the array's indices start at one. The IMUL node may multiply by 8 because addresses are byte-oriented. Load and store nodes for array references may be left in place, though each store node may be given an additional enable input. In the case of a basic block, this enable input may be fed by the block's INITIATE node. In another embodiment, as the block's CFG is being transformed into a DFG, an anchor may be a subroutine call rather than a store. Consider the code fragment: a=b+c call xyz (b, a, c) a=c*5 The front end output for this code is shown at left in FIG. 20. It may be fed by a linked list of ARGAR nodes, each bringing in one argument to the call. After the DFG generator has built the DFG fragments from the op codes, the routine may be called that finds the subroutine call anchors. For each one, it may remove the linked list of ARGAR nodes and gives the call node multiple inputs with the arguments wired to them. This requires knowledge about the subroutine, which may be drawn from the 'info' file. For a stateful node, an extra input may be created for connection to an enable signal. For an external node, an extra input and an extra output may be given for trigger and done signals. (Note that by the time this step is being performed, the extra indirection for scalar parameters may have already been removed.) The info file may specify, for each argument, whether it is a value or an address. It also may specify which are inputs and which are outputs. If an input argument is a value (but not a constant), an appropriate load node may be created. If it's an address, it may be left unchanged. For this example, assume that this is a 2-input, 1-output subroutine. The middle of FIG. 20 shows the DFG code fragment for the subroutine call after the call has been converted to DFGJSR, and LDKR nodes have been added for the two inputs. Later in the subroutine call processing, the DFGJSR node may cause another consultation with the info file. The two inputs may be handled in the same way as with inputs to other nodes: the source of the variable may be noted, the LDKR node may be removed, and the input may be wired directly to the source. For outputs, the incoming edge may be removed, the ACON node may be examined to determine which variable is receiving the output value, and that output may be noted as the new source of that variable. At right in FIG. 20 is the complete code block after conversion to DFG. Calls to intrinsic functions may show up in the CFG output as non-anchor JSR and QJSR nodes. After the subroutine calls have been handled, the JSR and QJSR nodes that remain may be function calls. An example of such a function call may be shown as: a=b+c c=min (b, a) a=c*5 The function call may yield a CFG whose second assignment is shown in FIG. 21. As with subroutine calls, its arguments form a linked list. The arguments may be flattened to multiple inputs, as shown in the middle of the figure. From this point, the building of the DFG may take place in the usual way, yielding the graph shown at right of FIG. 21. The basic block may end in a conditional branch. In this case, the second input to the OUTPUT node may be fed by the result of a compare. As an example, consider the code: a=b+c c=min (b, a) a=c*5 if (a .gt. 42) a=a+1 Note that the "a=a+1" statement is not part of the basic block; the block ends with the conditional test. The last anchor is the ICJMPZ node, and the structure above it is shown at left in FIG. 22. The QJSR, the DFRIR and the ICJMPZ nodes get replaced with a KCJMP. Later, the KCJMP may be turned into a KCMP_le. At right is the DFG for the code block, where the KCMP_le node may be fed by the final value of 'a' and its output goes to the second input of the OUTPUT. As was shown in FIGS. 9 and 10, basic blocks may be merged into a single large code block. This process may include dealing with conditionals inside the code block by computing all paths and selecting the appropriate values using multiplexers, called SELECTOR nodes. As an example, consider the code:
In this example, both expressions aa+1 and aa-1 are computed in each iteration, and the 'bb' value that is assigned to the 'BL' array is fed by a SELECTOR. The job of building a merged code block out of various basic blocks may include building the DFG segments for the individual blocks, and wiring them together using selectors and control signals derived from the predicate expressions of the conditionals. In an embodiment, the first step in creating a merged code block may include topological sorting of the merged basic blocks. This as the blocks are processed, blocks that feed control to a given block may be converted before that block is converted. In the early steps of processing, each block may be converted to a DFG similar to individual blocks. LD_SCALAR nodes may be built at the top of the DFG. Then the code blocks may be converted. The differences between a merged code block and an individual basic block may include the boolean control signals and the selector node hookup. In an example, consider an arbitrary block 'B' in a set of blocks to be merged, with three blocks able to send control to 'B', and 'B' sending control to one of two blocks when it is done. (Note: there may be any number of blocks that can send control to a block, but a given block sends control to two blocks). FIG. 23, at left, shows this. Assume that there is a one-bit signal from each of the incoming blocks that is high if it is transferring control to block 'B'. Block 'B's active signal is computed by ORing the incoming signals. Block 'B' then may compute activation signals for the two blocks that it can activate. Since 'B' can activate two blocks, it ends with a conditional. The conditional's predicate is ANDed with the block's activation signal to provide an activation signal for the "true" signal, and the inverted predicate is ANDed with the block's activation signal to provide an activation signal for the "false" signal. FIG. 23, at right, shows the nodes that compute these signals in 'B'. The basic block data structure has fields to store control information that may include: The 'incoming' field, which is a linked list of all the blocks that have control flow edges into the current block. The 'active' field, which is the id of the node whose output represents the current block's active signal, i.e. the output of the OR node sequence. The 'src_true' field, which is the id of the node that computes the "true" output control signal. The 'src_false' field, which is the id of the node that computes the "false" output control signal. After the control signals have been built, selectors are installed for the incoming data values. FIG. 23 shows the selector nodes added to the example of FIG. 24, for a variable 'x'. The outputs from the OR chain may feed these selectors. A set of selectors may be created for each variable in the loop. The conversion of an inner loop to a pipelined DFG may build on the conversion techniques described above. Consider an example of a loop shown as:
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||