Static safety analysis for control-flow linearization

#The present invention relates to control flow usage in computer programs, and more specifically, to control-flow linearization of computer programs in a data processing system. Control-flow dependencies introduced by branches and switches within a computer program are major inhibitors to compiler optimizations, such as vectorization. Control-flow linearization is a classic technique for eliminating conditional branches that combines multiple paths of control flow of a respective computer program into a single path of conditional instructions. By converting conditional code into predicated execution, control-flow linearization exposes further optimization opportunities, including loop vectorization.

#According to an embodiment of the present invention, a computer-implemented process for static safety analysis for control-flow linearization. The computer-implemented process comprising in response to receiving a control flow graph (CFG) and an 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. A determination is made whether each representation of an 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 representation of an 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, the computer-implemented process 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. 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, the computer implemented process affirming safety of linearization of the diamond-shape structure in the CFG.

#In an alternative embodiment of the disclosure, a computer-implemented process for managing control-flow linearization, in response to receiving a control flow graph (CFG) and intermediate representation of a computer program, identifies for a given loop, all memory load instructions belonging to one side of a diamond-shape structure in the CFG. The computer implemented process further determining whether each expression used in an address computation 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 expression used in an address computation 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, the computer implemented process further 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. 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, the computer implemented process further affirming safety of linearization of the diamond-shape in the CFG.

#FIG. 1 is a textual representation of a code snippet in an example of a loop with control-flow divergence in various embodiments of the disclosure;

#FIG. 2 is a schematic representation of an overview of a compilation process used in an embodiment of the disclosure;

#FIG. 3 is a schematic of a divergence in program control, represented in a form characteristic of a diamond shape structure in a control-flow graph corresponding to an if-then-else branch in an embodiment of the disclosure;

#The description, which follows, and the embodiments described therein, is provided by way of illustration of an example, or examples, of particular embodiments of the principles of the present invention. These examples are provided for the purposes of explanation, and not limitation, of those principles and of the invention. In the description, which follows, like parts are marked throughout the specification and the drawings with the same respective reference numerals.

#The following detailed description of the embodiments of the present invention does not limit the implementation of the present invention to any particular data processing system programming language. The present invention may be implemented in any data processing system programming language provided that the Operating System (OS) provides the facilities that may support the requirements of the embodiments of the present invention. Any limitations presented may be quite likely a result of a particular type of OS, data processing system programming language, or data processing system and may not be a limitation of the embodiment of the present invention.

#The present invention may be a system, a method, and/or a computer program product at any possible technical detail level of integration. The computer program product may include a computer readable storage medium (or media) having computer readable program instructions thereon for causing a processor to carry out aspects of the present invention.