Methods and apparatus for transforming machine language program control into high-level language constructs by manipulating graphical program representations

A method of automatically transforming an initial program flow representation of a computer program into a modified program flow representation, the computer program containing sequentially-ordered blocks of consecutive instructions written in a first computer language, and the initial program flow representation including a plurality of nodes each representing a different one of the blocks of instructions, wherein the nodes in the initial program flow representation are connected in paths reflective of the possible sequences which the blocks of instructions may be executed in accordance with the computer program, and wherein the connection, in any of the paths, of a first one of the nodes representing a first block of instructions to a second one of the nodes representing a second block of instructions to reflect the execution in the computer program of the first block of instructions immediately prior to the execution of the second block of instructions makes the first node a predecessor node of the second node and the second node a successor node of the first node, the method comprising the steps, performed by a computer, of:

• creating an instruction list containing a representation of the instructions in the blocks of consecutive instructions;
• creating a node list containing information about each of the nodes and identifying the corresponding block of instructions by reference to the instruction list;
• creating arc lists containing information about the paths in the initial program flow representation;
• examining the paths in the initial program flow representation to identify the ones of the nodes which are members of loops and the ones of the nodes which are path search exit nodes,
• loops including ones of the paths that reflect sequences of repetitive instruction block execution, and the ones of the nodes lying in the paths in loops being deemed members of a loop, and
• path search exit nodes being the ones of the nodes which occur at the exit of a control substructure in the program flow representation and in the modified program flow representation;
• setting a loop member flag in the corresponding entry of the node list for those of the nodes which are loop members;
• setting a path exit flag in the corresponding entry of the node list for those of the nodes which are path search exit nodes;
• examining the node list to select the ones of the nodes which have multiple predecessor nodes and a single successor node, for which the loop member flag is not set and for which the predecessor node does not have its loop member flag set, and for which the path exit flag is not set;
• replicating each of the node list entries for selected ones of the selected nodes such that a different copy of each of the node list entries for a corresponding one of the selected nodes is formed for each predecessor node of the corresponding selected node;
• replacing each of the selected nodes in the initial program flow representation with the copies of that selected node by adding the replicated node list entries to the node list;
• and
• connecting each replicated node list entry to a corresponding entry in the arc lists such that the nodes corresponding to the replicated node list entries are connected to the single successor node and to the corresponding predecessor node,
• the replication of the node list entries and their connection to the arc list entries forming the modified program flow representation.

A method of automatically preparing a first computer program written in a first computer language and containing sequentially-ordered blocks of consecutive instructions for translation into a second computer program written in a second computer language, the method comprising the steps, performed by a computer, of:

• converting the first program into an initial program flow representation including a plurality of nodes each representing a different one of the blocks of instructions, the nodes being connected in paths reflective of the possible sequences which the blocks of instructions in the program may be executed in accordance with the first computer program, and the connection in any of the paths of a first one of the nodes representing a first block of instructions to a second one of the nodes representing a second block of instructions to reflect the execution in the first computer program of the first block of instructions immediately prior to the execution of the second block of instructions makes the first node a predecessor node of the second node and the second node a successor node of the first nodes;
• examining the paths in the initial program flow representation to identify the ones of the nodes which are members of loops and the ones of the nodes which are path search exit nodes,
• loops including ones of the paths that reflect sequences of repetitive instruction block execution, and the ones of the nodes lying in the paths in loops being deemed members of a loop, and
• path search exit nodes being the ones of the nodes which occur at the exit of a control substructure in the program flow representation and in the modified program flow representation;
• selecting the ones of the nodes which have multiple predecessor nodes and a single successor node, which are not loop members, which have no predecessors that are loop members, and which are not path search exit nodes;
• replicating selected ones of the selected nodes such that a different copy of each selected node is formed to correspond to each predecessor node of that selected node;
• replacing each of the selected nodes in the initial program flow representation with the copies of that selected node;
• and
• connecting each of the copies of each of the selected nodes to the predecessor node corresponding to that selected node and to the single successor node of that selected node,
• the replication of selected nodes and the connection of the copies thereby forming a modified program flow representation for use in generating the second computer program written in the second computer language.

A data processor system for transforming an initial program flow representation of a computer program into a modified program flow representation, the computer program containing sequentially-ordered blocks of consecutive instructions written in a first computer language, and the initial program flow representation including a plurality of nodes each representing a different one of the blocks of instructions, wherein the nodes in the initial program flow representation are connected in paths reflective of the possible sequences which the blocks of instructions may be executed in accordance with the computer program, and wherein the connection, in any of the paths, of a first one of the nodes representing a first block of instructions to a second one of the nodes representing a second block of instructions to reflect the execution in the computer program of the first block of instructions immediately prior to the execution of the second block of instructions makes the first node a predecessor node of the second node and the second node a successor node of the first node, the data processor comprising:

• a memory system for storing the computer program, the initial program flow representation, and the modified program flow representation, the memory system including
• an instruction list containing the instructions in the blocks of consecutive instructions,
• a node list containing information about each of the nodes and identifying the corresponding block of instructions by reference to the instruction list, and
• arc lists containing information about the paths of the initial program flow representation;
• means, coupled to the memory system, for examining the paths in the initial program flow representation using the arc and node lists to identify the ones of the nodes which are members of loops and which are path search exit nodes,
• loops including ones of the paths that reflect sequences of repetitive instruction block execution, and the ones of the nodes lying in the paths in loops being deemed members of a loop, and
• path search exit nodes being the ones of the nodes which occur at the exit of a control substructure in the program flow representation and in the modified program flow representation;
• means, coupled to the memory system, for setting a loop found flag in the corresponding entry of the node list for those of the nodes which are the first loop members encountered during path examination;
• means, coupled to the memory system, for examining the node list to select the ones of the nodes which have multiple predecessor nodes and a single successor node, which have no predecessor with its loop member flag set, and for which neither the loop member flag nor path exit flag is set;
• means, coupled to the memory system, for replicating each of the node list entries for the selected nodes such that a different copy of each of the node list entries is formed for each predecessor node of the corresponding node, and for replacing each of the selected nodes in the initial program flow representation with the copies of that selected node by adding the replicated node list entries to the node list;
• and
• means, coupled to the memory system, for connecting each replicated node list entry to a corresponding entry in the arc lists such that the nodes corresponding to the replicated node list entries are connected to the corresponding single predecessor node and single successor node, the replication of the node list entries and their connection to the arc list entries forming the modified program flow representation.

A method of automatically transforming an initial program flow representation of a computer program into a modified program flow representation, the computer program containing sequentially-ordered blocks of consecutive instructions written in a first computer language, and the initial program flow representation including a plurality of nodes each representing a different one of the blocks of instructions, wherein the nodes in the initial program flow representation are connected in paths reflective of the possible sequences which the blocks of instructions may be executed in accordance with the computer program, and wherein the connection, in any of the paths, of a first one of the nodes representing a first block of instructions to a second one of the nodes representing a second block of instructions to reflect the execution in the computer program of the first block of instructions immediately prior to the execution of the second block of instructions makes the first node a predecessor node of the second node and the second node a successor node of the first node, the method comprising the steps, performed by a computer of:

• examining the paths in the initial program flow representation to identify the ones of the nodes which are members of loops and the ones of the nodes which are path search exit nodes,
• loops including ones of the paths that reflect sequences of repetitive instruction block execution, and the ones of the nodes lying in the paths in loops being deemed members of a loop, and
• path search exit nodes being the ones of the nodes which occur at the exit of a control substructure in the program flow representation and in the modified program flow representation;
• combining the loops into single nodes;
• selecting the ones of the nodes which have multiple predecessor nodes and a single successor node, and which are not path search nodes;
• replicating selected ones of the selected nodes such that a different copy of each selected node is formed to correspond to each predecessor node of that selected node;
• replacing each of the selected nodes in the initial program flow representation with the copies of that selected node;
• and
• connecting each of copies of each of the selected nodes to the predecessor node and the single successor node corresponding to that selected node,
• the replication of selected nodes and the connection of the copies forming a modified program flow representation.