Static safety analysis for control-flow linearization

A system for static safety analysis for control-flow linearization, the system comprising:

• a bus;
• a memory connected to the bus, having computer executable instructions stored thereon;
• and
• one or more processors connected to the bus, wherein at least one of the one or more processors executes the computer executable instructions of a method comprising:
• in response to receiving a control flow graph (CFG) and intermediate representation of a computer program, identifying for a given loop, all memory load instructions belonging to one side of a diamond-shape structure in the CFG;
• determining whether each address of each memory load instruction on the one side of the diamond-shape structure is also used on all other sides of the diamond-shape structure;
• in response to a determination that each address of each memory load instruction on the one side of the diamond-shape structure is also used on all other sides of the diamond-shape structure, determining whether an immediate predecessor of a top of the diamond-shape structure for the given loop post-dominates a header of the given loop;
• and
• in response to a determination the immediate predecessor of the top of the diamond-shape structure for the given loop post-dominates the header of the given loop, affirming safety of linearization of the diamond-shape in the CFG.

A computer program product comprising a computer readable storage medium having computer readable program instructions for static safety analysis for control-flow linearization thereon for causing a processor to perform a method comprising:

• in response to receiving a control flow graph (CFG) and intermediate representation of a computer program, identifying for a given loop, all memory load instructions belonging to one side of a diamond-shape structure in the CFG;
• determining whether each address of each memory load instruction on the one side of the diamond-shape structure is also used on all other sides of the diamond-shape structure;
• in response to a determination that each address of each memory load instruction on the one side of the diamond-shape structure is also used on all other sides of the diamond-shape structure, determining whether an immediate predecessor of a top of the diamond-shape structure for the given loop post-dominates a header of the given loop;
• and
• in response to a determination the immediate predecessor of the top of the diamond-shape structure for the given loop post-dominates the header of the given loop, affirming safety of linearization of the diamond-shape in the CFG.