Patent ID: 8589888
Filing Date: 2013-11-19
Classification: G06F

Abstract:
1. A computer-implemented method for identifying alias sets for selected pointers, comprising steps for: receiving a computer program; constructing a program expression graph (PEG) from the computer program, such that each program expression is represented by a “node” in the PEG and edges between nodes are either an “assignment edge” or a “dereference edge”; modeling a “value alias” relation between nodes with a first context-free grammar such that two program expressions are value aliases if and only if there exists such a path between them on the PEG that the sequence of labels along the path belongs to a first context-free language generated by the first context-free grammar; constructing a first pushdown automaton for the first context-free grammar such that the first pushdown automaton accepts a sequence of labels if and only if it belongs to the first context-free language generated by the first context-free grammar constructing a modified PEG by evaluating the computer program to add new edges between nodes for corresponding field relations with corresponding structure assignments based on the computer program; modeling field-sensitive value alias relations with a second context-free grammar such that two expressions are field-sensitive value aliases if and only if there exists such a path between them on the PEG that the sequence of labels along the path belongs to both the first context-free language and a second context-free language generated by the second context-free grammar; constructing a second pushdown automaton for the second context-free grammar such that the second pushdown automaton accepts a sequence of labels if and only if it belongs to the second context-free language for a selected expression of the computer program; and recursively traversing the PEG and evaluating the generated sequence of labels with the first and second pushdown automata, and adding a particular node into a value alias set of the selective expression if the corresponding sequence of labels are accepted by both the first and second pushdown automata.