Method and apparatus for compiling source code using symbolic execution

• US 6,588,009 B1
• Filed: 11/29/1999
• Issued: 07/01/2003
• Est. Priority Date: 11/29/1999
• Status: Expired due to Term

• Current Assignee: u-blox Cambridge Ltd. (u-blox Holding AG)
• Original Assignee: Adelante Technologies B.V.
• Inventors: Pont, Kurt Du, Guffens, Jan
• Primary Examiner(s): Morse, Gregory
• Assistant Examiner(s): ZHEN, WEI Y
• Application Number:
  US09/450,325
• Time in Patent Office: 1,310 Days
• Field of Search: 717/140-144, 717/149, 717/150-159, 717/160-161, 712/241, 709/102-108, 707/1, 707/100, 707/101, 707/102, 707/104.1, 707/200, 707/204, 711/100, 711/167-169
• US Class Current: 717/161
• CPC Class Codes: G06F 8/45 Exploiting coarse grain parallelism in compilation, i.e. parallelism between groups of instructions
• CPC Class Codes: G06F 8/49 Partial evaluation

Abstract

A method and apparatus for optimizing the compilation of a computer program by exposing parallelism are disclosed. Information describing the operations in the program and their sequence is extracted and stored in a data structure. The operations in the program which involve index expressions are identified and symbolically executed, producing information describing the memory accesses by the program. Operations which can be executed in parallel are identified based on the information describing memory accesses. The program is interrogated with questions in a question data structure relating to how the program accesses memory. The answers to the questions are accumulated in index sets and back annotated into the question data structure.

Claims

1. A method of compiling a computer program, the program comprising a plurality of operations having a sequence, the method comprising:

extracting from the computer program, information describing the operations and the sequence of the operations and storing the extracted information as a data structure;

identifying operations in the computer program which involve index expressions;

symbolically executing the operations in the computer program which involve index expressions, thereby producing information describing memory accesses; and

identifying the operations which can be executed in parallel based on the information describing memory accesses.

2. The method of claim 1 further comprising the step of generating a symbolic execution data structure comprising a representation of the operations in the computer program which involve the memory accesses and index expressions.

3. The method of claim 2 wherein the symbolic execution data structure comprises a data flow problem graph.

4. The method of claim 2, wherein the step of symbolically executing the operations comprises executing the symbolic execution data structure and noting memory locations addressed by the computer program.

5. The method of claim 1 further comprising the step of generating a question data structure comprising questions relating to how the computer program accesses memory.

6. The method of claim 5 further comprising the steps of analyzing the computer program by interrogating the computer program with the questions, thereby obtaining answers to the questions, and back annotating the answers into the question data structure.

7. The method of claim 5 wherein the symbolic execution data structure comprises a data flow problem graph and further comprising the steps of analyzing the data flow problem graph by interrogating the computer program with the questions, thereby obtaining answers to the questions, and back annotating the answers into the question data structure.

8. The method of claim 1 further comprising the step of generating index sets relating to memory access by the operations of the program which involve index expressions and wherein the step of executing the operations in the computer program which involve index expressions comprises filling the index sets.

9. An apparatus for compiling computer code, the apparatus comprising:

first signal flow analysis means for creating a signal flow data structure for index expressions used by the computer code, wherein the first signal flow analysis means comprises;

means for identifying an index path in the computer code, the index path comprising operations involved in computing indices used in memory accesses by index expressions;

symbolic execution means for executing the index path, thereby extracting information relating to index expression memory accesses.

10. The apparatus of claim 9 further comprising a question database comprising questions relating to memory accesses by index expressions.

11. The apparatus of claim 10 further comprising means for generating index sets comprising responses to questions in the question database.

12. The apparatus of claim 9 further comprising second signal flow analysis means for creating a signal flow data structure for scalar variables used by the computer code.

13. The apparatus of claim 9 wherein the signal flow data structure is a signal flow graph.

14. A method of exposing parallelism in a computer program, comprising:

extracting from the computer program, information describing a plurality of operations specified by the computer program, and the sequence of the operations and storing the extracted information as a data structure;

identifying operations in the computer program which involve at least non-linear index expressions;

symbolically executing the operations specified by the computer program which involve at least non-linear index expressions, thereby producing information describing memory accesses; and

identifying the operations which can be executed in parallel based on the information describing memory accesses.

15. The method of claim 14, further comprising generating a question database comprising questions relating to how the computer program accesses memory;

interrogating the information extracted from the computer program; and

responsive to interrogating, receiving answers.

16. The method of claim 15, wherein the answers comprise data in a format selected from the group consisting a Boolean yes/no, a bitvector, and index set containing memory locations.

17. The method of claim 15, wherein the questions are asked for at least one relevant triplet of fetch, store and loop in an index path.

18. The method of claim 17, wherein the interrogation determines at least whether memory accesses are disjoint.

19. The method of claim 18, wherein the interrogation determines at least whether data flows from a first loop iteration to the next sequential loop iteration.

20. The method of claim 19, wherein the interrogation determines at least