US 5,650,948 AGranted

Method and system for translating a software implementation with data-dependent conditions to a data flow graph with conditional expressions

AssigneeTexas Instruments Incorporated

InventorNeal M. Gafter

Life of this patent

Estimating the term…

Loading patent…

Abstract

A method for symbolic evaluation of an algorithm is provided. The algorithm has at least one conditional branching statement dependent on the value of at least one input datum. The method comprises the steps of converting the algorithm into a control flow graph having a plurality of nodes, each node representing at least one of the plurality of statements. The control flow graph further includes a conditional branching node for the data-dependent conditional branching statement. Reverse dominators are then computed for each of the plurality of nodes, from which a meet point node for each conditional branching node is derived. The method further provides for constructing a shadow symbol table housing the variables, and constructing a duplicate shadow symbol table for each possible value of the datum in response the conditional branching node. The method further evaluates each node symbolically in succession according to control flow, and assigns a symbolic value to each the variables in the shadow symbol tables. The conditional branching node is also evaluated by assuming each possible value of the datum for each branch and assigning symbolic values to each of the variables in the shadow symbol table. The nodes contained in each branch are evaluated until the meet point node is reached. The duplicate shadow symbol tables are then merged.

Claims12

Dependent claims

A computer implemented method, the computer including a processor and a memory, for translating a software implementation of an application stored in said memory to a data flow graph in said memory, said software implementation having a plurality of statements manipulating values of a plurality of variables, said plurality of statements including at least one data-dependent conditional branching statement, said at least one data-dependent conditional branching statement depending on the value of at least one input datum, the method comprising the steps of:

converting said software implementation into a control flow graph in said memory, said control flow graph having a plurality of nodes including a start node and an end node, each node representing at least one of said plurality of statements, and including a conditional branch node for said at least one data-dependent conditional branching statement;
computing a set of reverse dominators for each of said plurality of nodes;
deriving a meet point node for said conditional branch node in response to said set of reverse dominators associated with said conditional branch node;
constructing a shadow symbol table in said memory, said shadow symbol table having symbolic values for each of said variables;
evaluating said each of said plurality of nodes symbolically in succession according to control flow;
constructing a duplicate shadow symbol table in said memory for each possible value of said data-dependent conditional branching statement in response said evaluating step if said each of said plurality of nodes being evaluated is said conditional branch node;
assigning symbolic values to each of said variables in each of said duplicate shadow symbol tables in accordance with said each possible value of said data-dependent conditional branching statement;
evaluating said nodes in each branch of said data-dependent conditional branching statement until said meet point node is reached;
merging said duplicate shadow symbol tables in response to reaching said meet point node to generate a merged duplicate shadow symbol table;
evaluating said nodes until said end node of said control flow graph is reached;
and
generating a data flow graph in response to reaching said end node of said control flow graph, said data flow graph including a conditional expression that is no longer data-dependent in place of said data-dependent conditional branching statement, said conditional expressing derived from said merged duplicate shadow symbol tables.

9 more elements

A computer implemented system, said computer including a processor and a memory, for translating a software implementation of an application stored in said memory to a data flow graph where said software implementation has at least one conditional branching statement, said conditional branching statement includes a data-dependent condition having a value, and said conditional branching leads to at least two branches which assign different values to a variable depending on the value of the data-dependent condition, comprising:

means for converting said software implementation into a control flow graph stored in said memory, said control flow graph having a plurality of nodes said nodes including an end node and a conditional branch node which represents said conditional branching statement;
means for computing a set of reverse dominators for each of said nodes;
means for deriving, in response to said set of reverse dominators associated with said conditional branch node, a meet point node to define where in said control flow graph branches of said conditional branching statement will converge;
means for constructing a shadow symbol table in said memory;
means for symbolically evaluating said each of said nodes in said control flow graph in succession;
means for evaluating said conditional branch node, and constructing a duplicate shadow symbol table in said memory for each of said branches of said conditional branching statement in response to evaluating said conditional branch node by assuming each possible value of said data-dependent condition;
means for assigning symbolic values to said variable in said duplicate shadow symbol table in response to evaluating said each of said branches of said conditional branching statement until reaching said meet point node;
means for merging said duplicate shadow symbol tables upon reaching said meet point node;
means for evaluating all conditional branches and reaching said end node of said control flow graph;
and
means for generating a data flow graph in said memory in response to reaching said end node of said control flow graph, said data flow graph including a conditional expression that is no longer data-dependent in place of said data-dependent conditional branching statement.

8 more elements

Dependencies are inferred from the claim text.