Logic circuit generation device and method

Patent metadata

Field	Value
Publication number	US-2016299998-A1
Application number	US-201415103793-A
Country	US
Kind code	A1
Filing date	Dec 11, 2014
Priority date	Dec 12, 2013
Publication date	Oct 13, 2016
Grant date	—

Abstract

A specific information processing function, which assumes circuit implementation, is described in a programming language, and from this description, an RTL description that can be logic synthesized is automatically generated. A logic circuit generation device includes: a control flow graph generation unit that generates a control flow graph; a control flow degenerate conversion unit that generates a control flow degenerate program by removing all condition branch instructions from the control flow graph; a data flow graph generation unit that generates a data flow graph from the control flow degenerate program; and a logic circuit description output unit that generates logic circuit description indicating a sequential circuit in which a rooted branch of the data flow graph corresponds to the wiring of the logic circuit and a node of the data flow graph corresponds to a computing element of the logic circuit.

First claim

1 . A logic circuit generation device that receives an input of a program in which an operation description, as a flow of a series of processes of hardware for a circuit design, is written, the program including a top-level function of a logic circuit generation target, and generates a logic circuit description, the logic circuit generation device comprising:
a control flow graph generation unit that generates a control flow graph from the top-level function including no loop processing part and no function call instruction; a control flow degenerate conversion unit that removes all condition branch edge instructions from the control flow graph that includes, for each variable, a single assignment instruction to the variable, and thereby generates a control flow degenerate program as a program in which a control flow is degenerated; a data flow graph generation unit that generates a data flow graph from the control flow degenerate program, by using each instruction in the control flow degenerate program as a node, and adding a directed edge from an assignment instruction to each variable to an instruction that refers to the variable; and a logic circuit description output unit that generates a logic circuit description expressing a sequential circuit in which the directed edge of the data flow graph corresponds to wiring of a logic circuit, and the node of the data flow graph corresponds to a computing element of the logic circuit, wherein a state variable expressing a state of the sequential circuit is represented in the program as a local variable or a static variable of a high-order hierarchy function calling the top-level function, and a value of the state variable before an assignment instruction to the state variable is executed expresses a current state of the sequential circuit, and a value of the state variable after the assignment instruction to the state variable is executed expresses a next state of the sequential circuit.

2 . The logic circuit generation device according to claim 1 , further comprising a static single assignment form conversion unit that coverts, when the top-level function is not of a static single assignment form which includes, for each variable, only a single assignment instruction to the variable, the control flow graph into the static single assignment form, before the control flow graph is inputted into the control flow degenerate conversion unit, wherein
the static single assignment form conversion unit includes:
a φ-function instruction insertion unit that inserts, into a position in the control flow graph where a plurality of value definitions of the same variable join, a φ-function instruction that selects a variable definition on an actually executed path out of all the variable definitions that join at the position;
a variable name conversion unit that coverts, by converting names of the variables included in the control flow graph to other names different among the assignment instructions to the variables, the control flow graph into a static single assignment form in which only a single assignment instruction is included for each variable after the name conversion; and
a state variable name re-conversion unit that re-converts, for the state variable after the name conversion, the variable names so as to match a variable name in a start point block and a variable name reaching an end point block of the control flow graph, and
the control flow degenerate conversion unit includes a φ-function instruction instantiation unit that converts the φ-function instruction into a specific operation instruction.

3 . The logic circuit generation device according to claim 1 , wherein
the program to be inputted includes an attribute description for giving an attribute to each variable, the attribute including:
a bit width attribute that designates a bit width of data of a variable;
a register attribute that designates a value of a variable to be held in a register; and
a memory attribute that designates a value of an array element of an array variable to be held in a memory, and
the logic circuit generation device generates a logic circuit description including a sequential circuit in which a state is represented using the variable to which the register attribute or the memory attribute is given as the state variable.

4 . The logic circuit generation device according to claim 3 , further comprising:
a bit width determination unit that calculates, for variables included in the data flow graph, a bit width of each of the variables, from a bit width of a variable and/or a constant to be referred in an assignment instruction to the variable and a type of operation to be executed in the assignment instruction; a computing element circuit delay evaluation unit that calculates a signal propagation delay time of a computing element, based on the bit width calculated for the variable included in the data flow graph; and a pipeline boundary arrangement unit that includes a pipeline constraint extraction unit and a number of pipeline stages decision unit, wherein the pipeline constraint extraction unit adds a pipeline boundary attribute to a directed edge between a computing element that executes an assignment instruction to the state variable in the data flow graph and a computing element that executes a reference instruction to the state variable, and the number of pipeline stages decision unit decides the number of pipeline stages that is used for generating a circuit description of a clock synchronous type pipeline circuit, in accordance with a pipeline stage-number lower limit value that is a minimum necessary number of pipeline stages determined by a constraint based on the pipeline boundary attribute, and the number of pipeline stages that is calculated from a designated clock cycle or the number of pipeline stages that is designated in advance.

5 . The logic circuit generation device according to claim 1 , further comprising:
a logic circuit input signal extraction unit that extracts an input signal of a circuit to be described by the circuit description, from an argument and a global variable of the top-level function; and a logic circuit output signal extraction unit that extracts an output signal of the circuit to be described by the circuit description, from the argument, a return value, and the global variable of the top-level function.

6 . The logic circuit generation device according to claim 1 , further comprising a non-cyclical and non-hierarchical conversion unit including:
a full inline expansion unit that, when the top-level function includes a function call instruction, subjects each function call instruction to inline expansion to convert the top-level function into a lowermost function including no function call instruction; and a full loop expansion unit that, when the lowermost function converted by the full inline expansion unit includes a loop processing part of a fixed repeat count, subjects each loop processing part of the fixed repeat count to loop expansion to convert the lowermost function into a non-cyclical type lowermost function including no loop processing part, wherein a program inputted into the logic circuit generation device is converted into a non-cyclical type lowermost function by the non-cyclical and non-hierarchical conversion unit, and then is inputted into the control flow graph generation unit.

7 . The logic circuit generation device according to claim 6 , wherein
in a case where the function call instruction is not fully expanded even with a predetermined number of repetitions of the inline expansion of the inputted function, the full inline expansion unit is configured to determine that the function is inconvertible into a lowermost function, and terminates the processing, when the in

Assignees

• Tokyo Inst Tech

Inventors

• Isshiki Tsuyoshi

Classifications

• G06F30/327 Primary

  Logic synthesis; Behaviour synthesis, e.g. mapping logic, HDL to netlist, high-level language to RTL or netlist · CPC title

• G06F30/30

  Circuit design · CPC title

• G06F30/33

  Design verification, e.g. functional simulation or model checking · CPC title

• G06F17/505 Primary

  Physics · mapped topic

• G06F30/3308

  using simulation · CPC title