US 8,510,724 B2Granted

Reconstructing program control flow

AssigneeMicrosoft Corporation

InventorsYosseff Levanoni, Weirong Zhu, Lingli Zhang, John Lee Rapp, Andrew L. Bliss

Life of this patent

Estimating the term…

Loading patent…

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 High Level Shader Language (“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.

Claims20

Dependent claims

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.

11 more elements

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 comprising one or more non-volatile 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.

11 more elements

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 High Level Shader Language (“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.

12 more elements

Dependencies are inferred from the claim text.