RECONSTRUCTING PROGRAM CONTROL FLOW

• US 20120159458A1
• Filed: 12/17/2010
• Published: 06/21/2012
• Est. Priority Date: 12/17/2010
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Levanoni, Yosseff, Zhu, Weirong, Zhang, Lingli, Rapp, John Lee, Bliss, Andrew L.
• Granted Patent: US 8,510,724 B2
• Time in Patent Office: Days
• US Class Current: 717/136
• CPC Class Codes: G06F 8/51 Source to source
• CPC Class Codes: G06F 8/53 Decompilation; Disassembly

Abstract

The present invention extends to methods, systems, and computer program products for reconstructing program control flow. Embodiments include implementing or morphing a control flow graph (“CFG”) into an arbitrary loop structure to reconstruct (preserve) control flow from original source code. Loop structures can be optimized and can adhere to target platform constraints. In some embodiments, C++ source code (a first higher level format) is translated into a CFG (a lower level format). The CFG is then translated into HLSL source code (a second different higher level format) for subsequent compilation into SLSL bytecode (that can then be executed at a Graphical Processing Unit (“GPU”)). The control flow from the C++ source code is preserved in the HLSL source code.

Claims

1. At a computer system including one or more processors and system memory, a method for reconstructing control flow for higher level code from the contents of lower level code, the method comprising:

an act of accessing a plurality of instructions of lower level code that were translated from corresponding statements and expressions of first higher level code, the first higher level code in a first format, the plurality of instructions of lower level code representing a control flow of the first higher level code, a portion of the control flow defined by one or more branch instructions, the branch instructions selected from among conditional branch instructions and unconditional branch instructions; and

an act of translating the plurality of instructions of lower level code into a corresponding plurality of statements and expressions of second higher level code that have control flow equivalent to the control flow of the first higher level code, the second higher level code in a second different higher level format, the translation including;

an act of identifying a plurality of basic blocks within the lower level code based on the arrangement of the one or more branch instructions within the plurality of instructions of lower level code, each basic block including one or more instructions of the lower level code configured to execute as a group;

an act of defining a block guard variable for each basic block in the plurality of basic blocks;

for each basic block in the plurality of basic blocks subsequent to defining the block guard variables;

an act of generating statements and expressions in the second higher level format to represent the functionality expressed in the basic block;

an act of generating statements and expressions in the second higher level format to represent assignment of values to a plurality of the block guard variables, the plurality of block guard variables including the block guard variable for the basic block and a block guard variable for at least one other basic block, assignments to the plurality of block guard variables for implementing the control flow of the first higher level code, including the portion of the control flow defined by the one or more branch instructions;

an act of generating statements and expressions in the second higher level format to represent a conditional statement, satisfying the conditional statement dependent on the value assigned to the block guard variable for the basic block; and

an act of nesting the functionality expressed in the basic block and the assignment of values to the plurality of the block guard variables within the conditional statement;

an act of generating statements and expressions in the second higher level format representing a while statement, the condition on the while statement set to TRUE; and

an act of nesting any conditional statements within the while statement.

2. The method as recited in claim 1, wherein the act of accessing a plurality of instructions of lower level code that were translated from corresponding statements and expressions of first higher level code comprises an act of accessing control flow graph (“

CFG”

) that was translated from the C++ source code.

3. The method as recited in claim 1, wherein the act of translating the plurality of instructions of lower level code into a corresponding plurality of statements and expressions of second higher level code comprises an act of translating the plurality of instructions of lower level code into source code, the source code compilable into an executable program for running on a graphical processing unit (“

GPU”

).

4. The method as recited in claim 1, wherein the act of translating the plurality of instructions of lower level code into a corresponding plurality of statements and expressions of second higher level code comprises an act of a translating a control flow graph (“

CFG”

) into High Level Shader Language (“

HLSL”

) source code.

5. The method as recited in claim 1, further comprising:

an act of generating statements and expressions in the second higher level format to represent one or more additional loops;

an act of defining a loop guard variable for each of the one or more additional loops, satisfying a conditional statement for the loop dependent on the value assigned to the loop guard variable for the loop;

an act of generating statements and expressions in the second higher level format to represent assignment of values to a plurality of the block guard variables;

an act of nesting the assignment of values to each of the pluralist of block guard variables within a first one or more of the conditional statements as appropriate to reconstruct the control flow of the first higher level code;

an act of nesting a second one or more conditional statements within each of the one or more additional loops as appropriate to reconstruct the control flow of the first higher level code; and

an act of nesting the one or more addition loops in the while statement.

6. The method as recited in claim 5, further comprising an act of converting statements and expressions representing at least one of one or more additional loops into statements and expressions representing a do-while loop.

7. The method as recited in claim 5, further comprising an act of converting statements and expressions representing at least one of one or more additional loops into statements and expressions representing an “

if”

statement

8. The method as recited in claim 1, wherein the act of translating the plurality of instructions of lower level code into a corresponding plurality of statements and expressions of second higher level code further comprises an act of inlining at least one basic block.

9. The method as recited in claim 1, wherein the act of translating the plurality of instructions of lower level code into a corresponding plurality of statements and expressions of second higher level code comprises an act of generating a dominance tree for the plurality of basic blocks.

10. The method as recited in claim 1, wherein an act of translating the plurality of instructions of lower level code into a corresponding plurality of statements and expressions of second higher level code comprises an act translating the plurality of instructions of lower level code into a corresponding plurality of statements and expressions of second higher level code that comply with a maximum nesting level for the second higher level format.

11. A computer program product for use at a computer system, the computer program product for implementing a method for reconstructing control flow for higher level code from the contents of lower level code, the computer program product for comprising one or more computer storage devices having stored thereon computer-executable instructions that, when executed at a processor, cause the computer system to perform the method, including the following:

access a plurality of instructions of lower level code that were translated from corresponding statements and expressions of first higher level code, the first higher level code in a first format, the plurality of instructions of lower level code representing a control flow of the first higher level code, a portion of the control flow defined by one or more branch instructions, the branch instructions selected from among conditional branch instructions and unconditional branch instructions; and

translate the plurality of instructions of lower level code into a corresponding plurality of statements and expressions of second higher level code that have control flow equivalent to the control flow of the first higher level code, the second higher level code in a second different higher level format, the translation including the following;

identify a plurality of basic blocks within the lower level code based on the arrangement of the one or more branch instructions within the plurality of instructions of lower level code, each basic block including one or more instructions of the lower level code configured to execute as a group;

define a block guard variable for each basic block in the plurality of basic blocks;

for each basic block in the plurality of basic blocks subsequent to defining the block guard variables;

generate statements and expressions in the second higher level format to represent the functionality expressed in the basic block;

generate statements and expressions in the second higher level format to represent assignment of values to a plurality of the block guard variables, the plurality of block guard variables including the block guard variable for the basic block and a block guard variable for at least one other basic block, assignments to the plurality of block guard variables for implementing the control flow of the first higher level code, including the portion of the control flow defined by the one or more branch instructions;

generate statements and expressions in the second higher level format to represent a conditional statement, satisfying the conditional statement dependent on the value assigned to the block guard variable for the basic block; and

nest the functionality expressed in the basic block and the assignment of values to the plurality of the block guard variables within the conditional statement;

generate statements and expressions in the second higher level format representing a while statement, the condition on the while statement set to TRUE; and

nest any conditional statements within the while statement.

12. The computer program product as recited in claim 11, wherein computer-executable instructions that, when executed, cause the computer system to access a plurality of instructions of lower level code that were translated from corresponding statements and expressions of first higher level code comprise computer-executable instructions that, when executed, cause the computer system to accessing control flow graph (“

CFG”

) that was translated from the C++ source code.

13. The computer program product as recited in claim 11, wherein computer-executable instructions that, when executed, cause the computer system to translate the plurality of instructions of lower level code into a corresponding plurality of statements and expressions of second higher level code comprises computer-executable instructions that, when executed, cause the computer system to translate the plurality of instructions of lower level code into source code, the source code compilable into an executable program for running on a graphical processing unit (“

GPU”

).

14. The computer program product as recited in claim 11, wherein computer-executable instructions that, when executed, cause the computer system to translate the plurality of instructions of lower level code into a corresponding plurality of statements and expressions of second higher level code comprises computer-executable instructions that, when executed, cause the computer system to translate a control flow graph (“

CFG”

) into High Level Shader Language (“

HLSL”

) source code.

15. The computer program product as recited in claim 11, further comprising computer-executable instructions that, when executed, cause the computer system to:

generate statements and expressions in the second higher level format to represent one or more additional loops;

define a loop guard variable for each of the one or more additional loops, satisfying a conditional statement for the loop dependent on the value assigned to the loop guard variable for the loop;

generate statements and expressions in the second higher level format to represent assignment of values to a plurality of the block guard variables;

nest the assignment of values to each of the pluralist of block guard variables within a first one or more of the conditional statements as appropriate to reconstruct the control flow of the first higher level code;

nest a second one or more conditional statements within each of the one or more additional loops as appropriate to reconstruct the control flow of the first higher level code; and

nesting the one or more addition loops in the while statement.

16. The computer program product as recited in claim 11, further comprising computer-executable instructions that, when executed, cause the computer system to convert statements and expressions representing at least one of one or more additional loops into statements and expressions representing a do-while loop.

17. The computer program product as recited in claim 11, further comprising computer-executable instructions that, when executed, cause the computer system to convert statements and expressions representing at least one of one or more additional loops into statements and expressions representing an “

if”

statement

18. The computer program product as recited in claim 11, wherein computer-executable instructions that, when executed, cause the computer system to translate the plurality of instructions of lower level code into a corresponding plurality of statements and expressions of second higher level code further comprise computer-executable instructions that, when executed, cause the computer system to inline at least one basic block.

19. The computer program product as recited in claim 11, wherein computer-executable instructions that, when executed, cause the computer system to translate the plurality of instructions of lower level code into a corresponding plurality of statements and expressions of second higher level code further comprises computer-executable instructions that, when executed, cause the computer system to translate the plurality of instructions of lower level code into a corresponding plurality of statements and expressions of second higher level code that comply with a maximum nesting level for the second higher level format.

20. At a computer system including one or more processors and system memory, a method for reconstructing control flow for higher level code from the contents of lower level code, the method comprising:

an act of accessing a control flow graph (“

CFG”

) that was translated from C++ source code program, the CFG representing the control flow of the C++ source code program, a portion of the control flow in the CFG defined by one or more branch instructions, the branch instructions selected from among conditional branch instructions and unconditional branch instructions; and

an act of translating the CFG into HLSL source code program that has control flow equivalent to the control flow of the C++ source code program, the translation including;

an act of identifying a plurality of basic blocks within CFG based on the arrangement of the one or more branch instructions within the CFG, each basic block including one or more lower level instructions configured to execute as a group;

an act of defining a block guard variable for each basic block in the plurality of basic blocks;

for each basic block in the plurality of basic blocks subsequent to defining the block guard variables;

an act of generating HLSL source code to represent the functionality expressed in the basic block;

an act of generating HLSL source code to represent assignment of values to a plurality of the block guard variables, the plurality of block guard variables including the block guard variable for the basic block and a block guard variable for at least one other basic block, assignments to the plurality of block guard variables for implementing the control flow of the C++ source code, including the portion of the control flow in defined by the one or more branch instructions;

an act of generating HLSL source code to represent a conditional statement, satisfying the conditional statement dependent on the value assigned to the block guard variable for the basic block; and

an act of nesting the functionality expressed in the basic block and the assignment of values to the plurality of the block guard variables within the conditional statement;

an act of generating HLSL source code representing a while statement, the condition on the while statement set to TRUE; and

an act of nesting any conditional statements within the while statement.