Live range reduction to enhance register allocation of structured control flow programs

A computer-implemented method of reducing live range of variables for register allocation of structured control-flow programs, the method comprising:

• using a number of processors to perform:
• defining an affine expression for each static single assignment (SSA) variable contained in an input program for a computer compiler;
• substituting affine expressions of input operands involved in computation of the SSA variables into the SSA variables;
• removing at least one overlapping dependence edge between nodes representing the SSA variables in a dependence graph according to the substitution of the affine expressions into the SSA variables, wherein each overlapping dependent edge represents a required register in a processor;
• and
• adjusting register allocation for the input program for a computer compiler by reducing a number of registers for static single assignment (SSA) variables contained in the input program based on removal of the overlapping dependence edges.

A computer-implemented method of reducing live range of variables for register allocation of structured control-flow programs, the method comprising:

• using a number of processors to perform:
• creating an affine expression for each constant static single assignment (SSA) variable in an input program for a computer compiler, wherein expression values are the constant value of those variables;
• for non-constant SSA variables in the input program, creating an affine expression with expression value being itself via an identity map;
• inserting the constant SSA variables into a queue;
• for each SSA variable in the queue:
• popping the SSA variable from the queue;
• getting the affine expression of the popped SSA variable;
• for each operation that uses the SSA variable, substituting the affine expression of the variable in affine expressions of the operation results and simplifying the resultant expression linear algebraically;
• responsive to a determination the simplified expression is different from an original expression before substitution, inserting the results of the operation into the queue;
• removing at least one overlapping dependence edge between nodes representing the SSA variables in a dependence graph according to the substitution of the affine expressions, wherein each overlapping dependent edge represents a required register in a processor;
• and
• adjusting register allocation for the input program for a computer compiler by reducing number of required registers for the SSA variables contained in the input program based on removal of the overlapping dependence edges.

A system for reducing live range of variables for register allocation of structured control-flow programs, the system comprising:

• a storage device that stores program instructions;
• one or more processors operably connected to the storage device and configured to execute the program instructions to cause the system to:
• define an affine expression for each static single assignment (SSA) variable contained in an input program for a computer compiler;
• derive the affine expression of an SSA variable in the input program by substitution of affine expressions of input operands involved in computation of the SSA variable;
• define dependence edges between nodes representing the SSA variables in a dependence graph, wherein source and destination of dependence edges represent definition and use of the SSA variables;
• identify one or more overlapping dependence edges with a same source among the dependence edges;
• eliminate the longer of the overlapping dependence edges according to the derived affine expressions;
• and
• adjust register allocation for the input program for a computer compiler by reducing a number of registers for the SSA variables contained in the input program based on elimination of the overlapping dependence edges.

A computer program product for reducing live range of variables for register allocation of structured control-flow programs, the computer program product comprising:

• a persistent storage medium having program instructions configured to cause one or more processors to:
• define an affine expression for each static single assignment (SSA) variable contained in an input program for a computer compiler;
• derive the affine expression of an SSA variable in the input program by substitution of affine expressions of input operands involved in computation of the SSA variable;
• define dependence edges between nodes representing the SSA variables in a dependence graph, wherein source and destination of dependence edges represent definition and use of the SSA variables;
• identify one or more overlapping dependence edges with a same source among the dependence edges;
• eliminate the longer of the overlapping dependence edges according to the derived affine expressions;
• and
• adjust register allocation for the input program for a computer compiler by reducing a number of registers for the SSA variables contained in the input program based on elimination of the overlapping dependence edges.