Constructing control flows graphs of binary executable programs at post-link time

• US 7,207,038 B2
• Filed: 08/29/2003
• Issued: 04/17/2007
• Est. Priority Date: 08/29/2003
• Status: Expired due to Fees

• Current Assignee: Nokia Corporation
• Original Assignee: Nokia Corporation
• Inventors: Gyimothy, Tibor, Bicsak, Attila, Ferenc, Rudolf, Kiss, kos
• Primary Examiner(s): INGBERG, TODD D
• Application Number:
  US10/651,839
• Publication Number:
  US 20050060696A1
• Time in Patent Office: 1,327 Days
• Field of Search: 717/154, 717/155, 717/156, 717/157, 717/158, 717/159, 717/144, 703/23, 703/21
• US Class Current: 717/159
• CPC Class Codes: G06F 8/433 Dependency analysis; Data or control flow analysis

Abstract

A method and a system for constructing a control flow graph (CFG, 106) from an executable computer program (104). The solution detects data intermixed with instructions and instruction set changes. The method includes the steps of defining block leader types specifying basic block boundaries in the program (104), building a CFG structure (106) according to the basic blocks found in the program, and adding control flow and addressing information to the CFG (106) by propagating through the basic blocks and internals thereof. The CFG (106) may be then optimised (108) and a compacted executable (112) created as a result.

Claims

1. A method for execution on a signal processing unit for constructing a control flow graph from a computer executable program the instructions of which belong to one or more computer architecture instruction sets, said method comprising defining a number of block leader types including at least one type related to an instruction set change, block leaders specifying basic block boundaries in the program, said basic blocks including instructions or data, building a control flow graph structure comprising basic blocks found in the program, adding control flow and addressing information to said control flow graph by propagating through said basic blocks and internals of said basic blocks and stored on said memory device.

2. The method of claim 1, further comprising compacting said control flow graph by utilizing a control flow graft optimisation technique.

3. The method of claim 2, wherein said optimisation technique is at least one of the following:

unreachable eliminator, branch unconditionalizer, simple redundant eliminator, redundant load eliminator, dead code eliminator, register liveness analyser, branch rationalizer.

4. The method of claim 1, wherein said adding control flow and addressing information includes iterating through instructions of a single basic block at a time based on constant propagation information associated with said block.

5. The method of claim 1, wherein said adding control flow and addressing information includes propagating basic block emulation results from a block to another.

6. The method of claim 1, wherein said block leader types further include an entry for at least one of the following:

data symbols intermixed with instructions, program entry point, exception vector, relocation entry point, relocation target point, successor of a branch instruction, target of a branch instruction, function.

7. The method of claim 1, wherein the control flow graph comprises hierarchical levels of sections, functions and basic blocks.

8. The method of claim 1, further comprising reading data from a binary executable file.

9. The method of claim 1, further comprising re-constructing an executable from said control flow graph.

10. The method of claim 1, wherein said program is ARM or THUMB architecture specific.

11. A computer program comprising code for carrying out the steps of claim 1 for at least temporary storage in a computer readable medium.

12. A computer readable medium on which a computer executable program is stored for carrying out the steps of claim 1.

13. A system for constructing a control flow graph from a computer executable program, the instructions of which belong to one or more computer architecture instruction sets, said system comprising a processing device and a memory device for processing and storing instructions and data, and a data transfer device for accessing data, said system arranged to define a number of block leader types including at least one type related to an instruction set change, block leaders specifying basic block boundaries in the program, said basic blocks including instructions or data, said system further arranged to build a control flow graph structure comprising basic blocks found in the program, and to add control flow and addressing information to said control flow graph by propagating through said basic blocks and internals of said basic blocks and stored on said memory device.

14. The system of claim 13, further arranged to compact the control flow graph by utilizing a control flow graph optimisation technique.

15. A system for constructing a control flow graph from a computer executable program, the instructions of which belong to one or more computer architecture instruction sets, said system comprising a processing means and a memory means for processing and storing instructions and data, and a data transfer device for accessing data, said system arranged to define a number of block leader types including at least one type related to an instruction set change, block leaders specifying basic block boundaries in the program, said basic blocks including instructions or data, said system further arranged to build a control flow graph structure comprising basic blocks found in the program, and to add control flow and addressing information to said control flow graph by propagating through said basic blocks and internals of said basic blocks and stored on said memory device.