Loop manipulation in a behavioral synthesis tool

• US 7,412,684 B2
• Filed: 11/10/2004
• Issued: 08/12/2008
• Est. Priority Date: 05/28/2004
• Status: Active Grant

• Current Assignee: Siemens Industry Software Limited (Siemens AG)
• Original Assignee: Mentor Graphics Corporation (Siemens AG)
• Inventors: Takach, Andres R., Gutberlet, Peter Pius, Bowyer, Bryan Darrell
• Primary Examiner(s): WHITMORE, STACY
• Application Number:
  US10/985,398
• Publication Number:
  US 20050268271A1
• Time in Patent Office: 1,371 Days
• Field of Search: 716/18, 717150-151, 717/160, 717/136, 717/154, 717/138
• US Class Current: 716/101
• CPC Class Codes: G06F 30/327 Logic synthesis; Behaviour synthesis, e.g. mapping logic, HDL to netlist, high-level language to RTL or netlist
• CPC Class Codes: G06F 8/443 Optimisation

Abstract

Methods and apparatus for analyzing and processing loops within an integrated circuit design are described. According to one embodiment, the processing comprises unrolling loops. In another embodiment, the processing comprises pipelining loops. In yet another embodiment, the processing comprises merging loops. In any of the disclosed embodiments, loops comprise independent loops, dependent loops or some combination thereof. Other embodiments for processing loops are disclosed, as well as integrated circuits and circuit design databases resulting from the disclosed methods. Computer-executable media storing instructions for performing the disclosed methods are also disclosed.

Claims

1. In a behavioral synthesis tool used to design a hardware circuit, a method comprising:

detecting a first loop, wherein the first loop comprises a first statement that assigns a value to a first variable;

detecting a second loop, wherein the second loop comprises a second statement that uses the value of the first variable;

performing a loop dependency analysis, comprising determining that the first loop and the second loop share a data dependency based at least in part on the first statement that assigns the value to the first variable and the second statement that uses the value of the first variable;

based at least in part on results of the loop dependency analysis, performing a dependent loop merging, wherein performing the dependent loop merging comprises at least partially merging the first loop with the second loop; and

storing on a computer-readable medium circuit design information modified by the at least partially merging.

2. The method of claim 1, wherein the first loop comprises a first subloop within a first parent loop.

3. The method of claim 2, wherein the second loop comprises a second subloop within a second parent loop.

4. The method of claim 2, wherein the second loop comprises a second subloop within the first parent loop.

5. The method of claim 1, wherein performing the loop dependency analysis comprises measuring a grade of dependency.

6. The method of claim 1, wherein performing the loop dependency analysis comprises addressing at least one individual bit in an array accessed within the second loop.

7. A computer-readable medium having stored thereon computer-executable instructions for performing the method of claim 1.

8. A hardware circuit design containing a plurality of at least partially merged loops using the method of claim 1.

9. A networked computer method comprising:

receiving a plurality of dependent loops;

analyzing the plurality of dependent loops, wherein the analyzing comprises performing a loop dependency analysis that comprises determining that each of the plurality of dependent loops share at least one data dependency;

based at least in part on results of the loop dependency analysis, merging the plurality of dependent loops; and

storing on a computer-readable medium circuit design information updated by the merging.

10. A method comprising:

identifying loops within a source code representation of a hardware circuit, wherein a first loop comprises a statement that writes to a variable, and wherein a second loop reads from the variable;

performing a loop dependency analysis on at least the first loop and second loop;

based at least in part on results of the loop dependency analysis, merging at least the first loop and second loop; and

storing on a computer-readable medium circuit design information updated by the merging.

11. A system for designing integrated circuits, comprising:

an input device for receiving a source code description of an integrated circuit;

a processor for executing software;

software that identifies loops within the source code;

software that performs a loop dependency analysis on at least two loops;

software that merges the at least two loops together based at least in part on the loop dependency analysis, wherein at least one of the loops shares at least one data dependency with at least one other of the loops;

an output device for outputting at least one integrated circuit design created by the software; and

storing the integrated circuit design on a computer-readable medium.

12. A method comprising:

receiving input code, wherein the input code comprises code relating to a plurality of loops, wherein at least one of the plurality of loops comprises a dependent loop;

processing the input code, wherein the processing comprises (1) performing a loop dependency analysis on at least two of the plurality of loops, and (2) based at least in part on the loop dependency analysis, merging the at least two of the plurality of loops, wherein at least one of the at least two of the plurality of loops is a dependent loop that comprises a data dependency on another of the at least two of the plurality of loops;

providing output code, wherein the output code comprises a circuit design based at least in part on the at least two merged loops; and

storing the output code on a computer-readable medium.

13. The method of claim 12, wherein the input code comprises C++ code.

14. The method of claim 12, wherein the output code comprises register transfer level (RTL) code.

15. In a user interface for a behavioral synthesis tool, a method comprising:

receiving a plurality of choices for setting a mergeable directive corresponding to a plurality of loops, wherein at least one of the plurality of loops comprises a data dependency on at least one other of the plurality of loops;

selecting one of the plurality of choices for setting the mergeable directive; and

storing on a computer-readable medium circuit design information modified at least in part by the selecting.

16. The method of claim 15, wherein the plurality of choices comprises TRUE and FALSE.

17. The method of claim 15, further comprising receiving a default choice, wherein the default choice is based on a heuristic method.

18. In designing a hardware circuit, a method comprising:

identifying loops within a source code representation of a hardware design;

receiving via a graphical user interface (GUI) an indication to perform a dependent loop merging of a plurality of the loops, wherein at least two of the plurality of loops share at least one data dependency;

merging the plurality of loops; and

storing on a computer-readable medium circuit design information modified based at least in part on the merging.

19. The method of claim 18, further comprising later receiving an indication to not merge the identified loops.

20. A method of creating a hardware circuit design, comprising:

selecting an option relating to a possible dependent loop merging of a plurality of loops, wherein at least two of the plurality of loops comprises at least one data dependency therebetween;

receiving information regarding at least one impact the selected option might have on the hardware circuit design; and

storing modified circuit design information on a computer-readable medium, wherein the circuit design information is modified based at least in part on the information.

21. The method of claim 20, wherein one of the plurality of loops has already been merged with another of the plurality of loops.

22. A method of designing an integrated circuit, comprising:

identifying loops within a source code representation of a hardware design;

receiving via a graphical user interface (GUI) a request to analyze a potential dependent loop merging of a plurality of the loops, wherein the plurality of loops comprises a first loop that writes to at least one variable that is accessed by at least a second loop in the plurality of loops;

providing an analysis of the potential dependent loop merging of the plurality of loops;

modifying circuit design information based at least in part on the analysis; and

storing the circuit design information on a computer-readable medium.

23. A method of designing an integrated circuit, comprising:

performing a loop dependency analysis on at least a first loop and a second loop, wherein each of the first loop and the second loop use at least one variable;

at least partially unrolling the first loop, wherein the first loop comprises a dependent loop;

based at least in part on the loop dependency analysis, performing a dependent loop merging comprising merging the first loop with the second loop;

updating circuit design information based at least in part on the merging; and

storing the updated circuit design information on a computer-readable medium.

24. A method of designing an integrated circuit, comprising:

performing a loop dependency analysis on at least a first loop and a second loop that share at least one data dependency;

based at least in part on the loop dependency analysis, performing a dependent loop merging comprising merging the first loop with the second loop, wherein the second loop comprises a dependent loop;

pipelining the first loop and the second loop; and

updating circuit design information based at least in part on the merging and the pipelining; and

storing the updated circuit design information on a computer-readable medium.

25. A method, comprising:

identifying a first loop comprising at least one statement that accesses at least one variable;

identifying a second loop comprising at least one statement that accesses the at least one variable, wherein the second loop is mergeable with the first loop;

performing a loop dependency analysis on the first and second loops;

based at least in part on results of the loop dependency analysis, performing a first dependent loop merging comprising merging the first loop and the second loop together into a first merged loop; and

storing on a computer-readable medium circuit design information that is modified based at least in part on the merging.

26. The method of claim 25, further comprising:

identifying a third loop, wherein the third loop is mergeable with the first loop and the second loop; and

performing a second dependent loop merging comprising merging the first merged loop and the third loop together.

27. The method of claim 25, further comprising:

establishing a loop merging order; and

performing a second dependent loop merging comprising merging the first loop, second loop, and third loop in accordance with the loop merging order.