Method for computing data dependence relationship in program, and computer readable storage medium

1 . A computer-implemented method for computing data dependence relationships of instructions, the computer-implemented method comprising:

constructing, by a processor, a control flow graph in a static single assignment form, wherein

the control flow graph is an abstract data structure,

the control flow graph comprises a plurality of nodes, and

in the static single assignment form, each variable is assigned a value only once;

identifying, by the processor, immediate dominators of the plurality of nodes based on Lengauer-Tarjan algorithm;

setting initial information of memory descriptors of the plurality of nodes, wherein the initial information comprises define information and kill set information of all memory descriptors of the immediate dominators, wherein the kill set information is an ordered list arranged in an order from a low address to a high address, so as to execute various intersection and union operations; and

iterating, by the processor, based on the control flow graph, wherein each iteration performs the following steps:

traversing the plurality of nodes,

computing and updating define information and kill set information of a memory descriptor, of the memory descriptors, of each node of the plurality of nodes,

updating the data dependence relationships of the instructions, wherein the data dependence relationships of the instructions are used as reference information for instruction compilation optimization, and

performing the instruction compilation optimization based on the data dependence relationships of the instructions,

wherein the instructions after compilation optimization are compiled into machine codes,

wherein the computing further includes computing and updating a memory descriptor, of the memory descriptors, used by an instruction of the instructions first, and then computing and updating a memory descriptor, of the memory descriptors, defined by the instruction,

wherein, for the memory descriptor used by the instruction, the computing further comprises:

determining whether an exact must-use memory descriptor exists;

determining whether define information of the exact must-use memory descriptor exists in a case where the exact must-use memory descriptor exists; and in a case where the define information of the exact must-use memory descriptor exists, the computing further comprises:

determining whether kill set information of the exact must-use memory descriptor is null;

determining whether define information of a may-use memory descriptor exists in a case where the kill set information of the exact must-use memory descriptor is not null; and

setting the define information of the may-use memory descriptor and define information of a must-use memory descriptor as define information of the memory descriptor used by the instruction in a case where the define information of the may-use memory descriptor exists.

2 . The computer-implemented method of claim 1 , wherein, in a case where the define information of the exact must-use memory descriptor exists, the computing further comprises:

determining whether an intersection area between the define information of the must-use memory descriptor and the define information of the may-use memory descriptor is killed in a case where the define information of the may-use memory descriptor exists; and

setting the define information of the may-use memory descriptor and the define information of the must-use memory descriptor as the define information of the memory descriptor used by the instruction in a case where the intersection area between the define information of the must-use memory descriptor and the define information of the may-use memory descriptor is not killed.

3 . The computer-implemented method of claim 1 , wherein, in a case where the define information of the exact must-use memory descriptor does not exist, the computing further comprises:

identifying all may-use memory descriptors that have define information;

determining whether an intersection area between the define information of the exact must-use memory descriptor and define information of the may-use memory descriptors is killed; and

setting the define information of the may-use memory descriptors and the define information of the must-use memory descriptor as the define information of the memory descriptor used by the instruction in a case where the intersection area between the define information of the exact must-use memory descriptor and the define information of the may-use memory descriptors is not killed.

4 . The computer-implemented method of claim 1 , wherein, in a case where the define information of the exact must-use memory descriptor does not exist, the computing further comprises:

identifying all may-use memory descriptors that have define information; and

setting define information of the may-use memory descriptors as the define information of the memory descriptor used by the instruction.

5 . The computer-implemented method of claim 1 , wherein, in a case where the exact must-use memory descriptor does not exist, the computing further comprises:

setting the define information of the must-use memory descriptor and the define information of the may-use memory descriptor as the define information of the memory descriptor used by the instruction.

6 . The computer-implemented method of claim 1 , wherein the computing further comprises:

determining whether the must-use memory descriptor exists in the memory descriptor used by the instruction; and

setting the define information of the may-use memory descriptor as the define information of the memory descriptor used by the instruction in a case where the must-use memory descriptor does not exist.

7 . The computer-implemented method of claim 1 , wherein, for the memory descriptor defined by the instruction, the computing comprises:

creating define information of a must-define memory descriptor in the memory descriptor defined by the instruction;

identifying a may-define memory descriptor of the must-define memory descriptor in the memory descriptor defined by the instruction; and

adding the define information of the must-define memory descriptor in the instruction to kill set information of the may-define memory descriptor.

8 . The computer-implemented method of claim 7 , wherein the adding comprises:

determining whether the may-define memory descriptor is killed totally;

deleting a record of the may-define memory descriptor in a case where the may-define memory descriptor is killed totally;

determining whether the kill set information of the may-define memory descriptor is null; and

adding all areas of the define information of the must-define memory descriptor in the memory descriptor defined by the instruction to the kill set information of the may-define memory descriptor in a case where the kill set information of the may-define memory descriptor is null,

wherein, in a case where the kill set information of the may-define memory descriptor is not null, the adding comprises:

creating a union area between the kill set information of the may-define memory descriptor and the define information of the must-define memory descriptor; and

adding the union area to the kill set information of the may-define memory descriptor.

9 . The computer-implemented method of claim 1 , wherein, for the memory descriptor defined by the instruction, the computing further comprises:

determining whether a must-define memory descriptor in the memory descriptor defined by the instruction is exact;

in a case where the must-define memory descriptor in the memory descriptor defined by the instruction is exact:

creating define information of the must-define memory descriptor in the memory descriptor defined by the instruction; and

identifying a may-define memory descriptor of the must-define memory descriptor in the memory descriptor defined by the instruction; and

in a case where the must-define memory descriptor in the memory descriptor defined by the instruction is not exact:

determining whether the may-define memory descriptor has define information; and

noting that the may-define memory descriptor is killed in a case where the may-define memory descriptor has the define information.

10 . The computer-implemented method of claim 1 , wherein, for the memory descriptor defined by the instruction, the computing comprises:

determining whether a must-define memory descriptor exists in the memory descriptor defined by the instruction; and

performing the following steps in a case where the must-define memory descriptor does not exist in the memory descriptor defined by the instruction:

identifying all may-define memory descriptors;

excluding a may-define memory descriptor that is overwritten by other may-define memory descriptors in the all may-define memory descriptors;

excluding a may-define memory descriptor that already has define information in the all may-define memory descriptors; and

creating define information of a may-define memory descriptor that is not excluded in the all may-define memory descriptors.

11 . The computer-implemented method of claim 1 , wherein, for the memory descriptor defined by the instruction, the computing comprises:

determining whether a must-define memory descriptor exists in the memory descriptor defined by the instruction; and

creating define information of all may-define memory descriptors in a case where the must- define memory descriptor does not exist in the memory descriptor defined by the instruction.

12 . The computer-implemented method of claim 1 , wherein, for the memory descriptor defined by the instruction, the computing comprises:

determining whether a must-define memory descriptor of the memory descriptor defined by the instruction is predicated; and

creating define information of the must-define memory descriptor of the memory descriptor defined by the instruction in a case where the must-define memory descriptor of the memory descriptor defined by the instruction is predicated.

13 . The computer-implemented method of claim 12 , wherein creating the define information of the must-define memory descriptor of the memory descriptor defined by the instruction comprises:

determining whether the must-define memory descriptor of the memory descriptor defined by the instruction has the define information;

adding the memory descriptor defined by the instruction to the define information of the must-define memory descriptor of the memory descriptor defined by the instruction in a case where the must-define memory descriptor of the memory descriptor defined by the instruction has the define information; and

creating new define information of the must-define memory descriptor of the memory descriptor defined by the instruction in a case where the must-define memory descriptor of the memory descriptor defined by the instruction does not have the define information.

14 . The computer-implemented method of claim 1 , wherein the computing comprises:

traverse an instruction of each basic block,

determine whether a successor basic block of each basic block is a PHI node; and

perform the following steps in a case where the successor basic block of each basic block is the PHI node:

setting define information of each basic block as define information of a memory descriptor of the PHI node;

creating an intersection area of kill set information of all basic blocks; and

setting the intersection area as kill set information of the PHI node.

15 . A non-transitory computer readable medium, having stored thereon computer executable instructions, which when executed by a processor, cause the processor to execute operations, the operations comprising:

constructing a control flow graph in a static single assignment form, wherein

the control flow graph is an abstract data structure,

the control flow graph comprises a plurality of nodes, and

in the static single assignment form, each variable is assigned a value only once;

identifying immediate dominators of the plurality of nodes based on Lengauer-Tarjan algorithm;

setting initial information of memory descriptors of the plurality of nodes, wherein the initial information comprises define information and kill set information of all memory descriptors of immediate dominators, wherein the kill set information is an ordered list arranged in an order from a low address to a high address, so as to execute various intersection and union operations; and

iterating based on the control flow graph, wherein each iteration performs the following steps:

traversing the plurality of nodes,

computing and updating define information and kill set information of a memory descriptor, of the memory descriptors, of each node of the plurality of nodes,

updating data dependence relationships of instructions, wherein the data dependence relationships of the instructions are used as reference information for instruction compilation optimization; and

performing the instruction compilation optimization based on the data dependence relationships of the instructions,

wherein the instructions after compilation optimization are compiled into machine codes,

wherein the computing further includes computing and updating a memory descriptor, of the memory descriptors, used by an instruction of the instructions first, and then computing and updating a memory descriptor, of the memory descriptors, defined by the instruction,

wherein, for the memory descriptor used by the instruction, the computing further comprises:

determining whether an exact must-use memory descriptor exists;

determining whether define information of the exact must-use memory descriptor exists in a case where the exact must-use memory descriptor exists; and

in a case where the define information of the exact must-use memory descriptor exists, the computing further comprises:

determining whether kill set information of the exact must-use memory descriptor is null;

determining whether define information of a may-use memory descriptor exists in a case where the kill set information of the exact must-use memory descriptor is not null; and

setting the define information of the may-use memory descriptor and define information of a must-use memory descriptor as define information of the memory descriptor used by the instruction in a case where the define information of the may-use memory descriptor exists.