Tracking condition codes in translation code for different machine architectures5598560Abstract A code translator, constructed similar to a compiler, accepts as an input to be translated the assembly code written for one architecture (e.g., VAX), and produces as an output object code for a different machine architecture (e.g., RISC). The input code is converted into an intermediate language, and a flow graph is constructed. The flow graph is referenced by a flow analyzer for recognizing certain architecture-specific and calling standard-specific coding practices or idioms that cannot be automatically converted, particularly relating to stack usage, register usage, condition codes, and passing arguments for procedure calls. By tracking stack usage within routines, the compiler can distinguish up-level stack and return address references from valid local references. Also, it can inform the user of stack misalignment, which has a severe performance penalty, and can detect code segments where different flow paths may result in different stack depths at runtime, which may indicate a source code error. Register usage is likewise tracked to determine which registers are destroyed by a routine, and generate routine prologue and epilogue code which performs register saves, as well as provide register "hints" to aid the user in adding an entry point declaration or documentation for the routine. The usage of condition codes is likewise tracked, by a backward walk through the flow graph, so that code to fabricate needed values is generated. In addition, all argument pointer based memory references in the input code is tracked to determine how the same argument reference may be made in the target environment. Claims What is claimed is: Description RELATED CASES
______________________________________
LOAD Rn,J ; Load memory location J to Register N
ADD Rn,#1 ; Add constant 1 to Register N
STORE Rn,I ; Store Register N to memory location I
______________________________________
In intermediate language, however, the code is in a more elemental (and generic) form than ever RISC assembly, and would include five tuples, these being number $1, $2, $3, $4 and $5 in FIG. 3. This way of expressing the code in IL includes a tuple $2 which is a fetch represented by an item 31, with the object of the fetch being a reference to symbol J, shown in tuple #1. The next tuple is a literal, item 32, making reference to the constant "1." The next tuple, item 33, is symbol reference to "I", which will be the target of the addition operator. The last tuple is an Add, item 34, which makes reference to the source tuples $2 and $3, and to the destination tuple $4. The expression may also be expressed as a logic tree as seen in FIG. 3, where the tuples are identified by the same reference numerals. A tuple (also referred to as an n-tuple), then, is the elemental expression of a computer program, and in the form used in this invention is a data structure 35 which contains at east the elements set forth in FIG. 4, including (1) an operator field 36, e.g., Fete, Store, Add, etc., (2) a locator 37 for defining where in the input module 21 the input-code equivalent to the tuple is located, (3) operand pointers 38 to other tuples, to literal nodes or symbol nodes, such as the pointers to I and #1 tuples $1 and $2 in FIG. 3. A tuple also has attribute fields 39, which may include, for example, Label, Conditional Branch, Argument (for Calls), or SymRef (a symbol in the symbol table. The tuple has a number field 40, representing the order of this tuple in the block. Referring to FIG. 4, the front end converter 20 parses the input code 21 to identify tuples and to build an intermediate language tuple stream 41 and associated symbol table 42. The next step is performed by a flow analyzer 43 is to scan the tuple stream and identify basic blocks of code, called nodes. A block of code is defined to be a set sequence of tuples with no entry or exit between the first and last tuple. Usually a block starts with a label or routine entry and ends with a branch to another label. A talk of the converter 20 and flow analyzer 43 in the front end is to parse the input code 21 and identify the tuples and blocks (nodes), which of course requires the front end to be language specific. The tuple data structure 35 contains fields 44 and 45 that say whether or not this tuple is the beginning of a block, or the end of a block. A flow graph 46 is generated by the flow analyzer 43 in the front end. The flow graph 46 consists of nodes, which are the basic blocks of the program, and edges, which represent the flow between nodes. The flow graph is built by processing the tuples 35 (intermediate language) by the front end converter 20 of the compiler. The process of building the flow graph 46 by the flow analyzer 43 includes walking the tuples sequentially for each program section. Referring to an example of code as seen in FIG. 6, the flow analyzer 43 adds tuples to the current flow node until one of the following is encountered, thus defining when the previous node ends and a new node begins: (a) label--branches to the label LAB1 will result in an edge being created to this node; hence, the label LAB1 is the first tuple in the new node Node-3, ant it creates the edge ending Node-2; (b) routine entry point, in this case JSB.sub.-- entry (the first tuple in Node-1, which is treated like a label for purposes of flow--however, the routine entry has an additional symbol table entry Rout1 identifying it as a routine; (c) a branch instruction--the branch BEQL ends the preceding block, Node-1, and the next instruction CLRL begins a new block, Node-2; (d) a return instruction, RSB, which is treated like a branch instruction which branches to a special routine exit node; thus RSB ends Node-3, which is only one tuple in length. A branch instruction such as the BEQL of FIG. 6 also results in an edge being created, linking the node (Node-1) containing the branch to the node (Node-3) containing the label which is the branch destination (LAB1). If the branch is conditional, as here an edge to the immediately following node (Node-2) will also be created, since flow may "fall through" to it. Indeed, an edge is a bidirectional link; the flow needs to b, traceable in both forward and backward directions. Accordingly, the intermediate language used in the code translator of FIG. 1 is expressed in the tuple stream 41 and a symbol table 42, along with the flow graph 46. The primitive concept is the tuple, and the intermediate language flow graph 46 is made up to link the tuples into node or blocks representing the operations to,be executed, each tuple 35 having a data structure as in FIG. 4. These tuples 35 within nodes are tied together by pointers which represent various relations. The most important relations are the operator-operand relation (a pointer 38 from an operator to each of its operands) and the linear ordering represented as a tuple number field 51 on all the tuples in each basic block of the intermediate language flow graph 46; the order of the tuples within a node provides the execution order. As mentioned in reference to FIG. 4, each tuple 35 has various fields, including the following: (a) Generic operator 36--identifying the general operation performed by the tuple, e.g., ADD, FETCH, etc. (b) Operator type 52--a data type which, normally, determines the specific operation performed by the tuple. The operator data type is primarily of interest only on data storage tuples. Instruction tuples are by definition self-contained, and will not be referenced in later instructions; hence, their data the is null. (c) Result type 53--the data type of the value computed by this tuple. This is set only on data reference tuples, e.g., those that can be used as operands of other tuples. (d) Operands 38--an array of pointers to the operands of this tuple. The number of operands is determined by the genetic operator. Each operand pointer 38 points to another intermediate language tuple node, or, in some cases, to a symbol or literal node in the symbol table as in tuples $1 and $2 of FIG. 3. (e) Next/Prev tuple 54 and 55--pointers to the next and previous tuples in a doubly-linked list of tuples. The next tuple order is the implicit order of evaluation. (f) Locator 37--the textual location in the input module 21, i.e., in the program source of the token or tokens which are compiled in this tuple. The locator is used in constructing error messages, source correlation tables, etc. (g) Use count 56--this field is set by the analyzer to the number of references made in data reference tuples. Some types of tuples have additional fields, known as attributes 39. Instances of attributes to the code translator in an embodiment of FIG. 1 include (a) Reference attributes, which point to nodes in the symbol table 42. These are always present in LITREF SYMREF LABEL and entry point tuples, pointing to literal nodes, symbol nodes, label nodes, and entry nodes, respectively. A pointer to a literal node may also be present in a COMP.sub.-- OP tuple. These symbol table entry types are discussed in additional detail below. (b) Instruction attributes, which are VAX instruction type constants. These are present in INSTR (instruction) and CONDBR (conditional branch) tuples, and further specify the instruction or branch operation. (c) Register attributes, which are simply register numbers specified in REGREF (register reference) tuples. Other additional private fields may be introduced into the tuple structures by the analyzer or code generator; these include: (a) Condition code flags in field 57 on INSTR and CONDBR tuples. These are used by the flow analyzer 43 to indicate that the code generator 28 must instantiate one or more of the VAX condition code values for an instruction. (b) A register-loaded field 58 for SYMREF MEMREF IDXREF and FETCH tuples, used within the code generator 28 to allow re-use of addresses or values already loaded to registers. The flown graph 46 is a major component of the intermediate representation, and is constructed and used by the flow analyzer 43, then later traversed by the optimizer 26, the storage allocator 27 and code generator 28. The tuples 35 for a particular routine or program (or input module 21) are in the tuple stream 41, linked by pointers 38, 54, 55, and having blocks or nodes defined by fields 48, 49. The flow graph 46 identifies the nodes or blocks by pointers to the beginning and ending tuples of the tuple stream. Since routines, labels, etc., will have entries in the symbol table 42, the symbol table is the reference point for tracing the program, i.e., finding the blocks and their ordering. The flow graph of the code of FIG. 6 may be illustrated as In FIG. 7, where it is seen that there are two paths from Node-1, that is, to Node-3 via Node-2 if the conditional branch fails, or directly to Node-3 if the branch is taken. A routine such as that of FIG. 7 has an entry or node 59 in the symbol table 42 as seen in FIG. 5 which includes a pointer 60 to the flow node 61 in the flow graph 46, and this node 61 includes pointers 62 and 63 to the beginning and ending tuples 35 of the tuples stream 41. Each flow node 61 also has a number of other fields, e.g., for stack usage, register usage and condition code usage, as will be described. Once a pass over the tuples by the flow analyzer 43 has created the flow graph 46, the flow for each routine can be walked by the flow analyzer 43 for computing the stack, register, and condition code information of interest for certain features of the invention. A Pass is made by the flow analyzer 43 through each routine in the module 21 as represented in intermediate language as illustrated in FIG. 5. The routine node 59 in the symbol table 42 points to the flow node 61 for the entry point of the routine. The flow graph 46 is recursively traversed starting at this node; first, the tuples 35 of a node as referenced in the tuple stream 41 will be walked looking for constructs described below. Then, the graph traversal routine is called for each of its successors (nodes 61 linked by a forward edge) which has not already been visited. The recursive walk ends at nodes which have only routine exit nodes as successors. The tuples 35 of each node 61 are scanned looking for the following: (a) Register references--if the reference is a "read" reference, and the register has not yet been written in the current node, it is recorded as part of the node 61 as an "input register" to the current node, in a field 64 for input registers. If it has been written, it is removed from the "output register" set, i.e., from a field 65 for output registers. If it is a "write" reference, it is added to the "output register" set of field 65, and the "written register" set of field 66 for the current node 61. The "output register" set of field 65 is passed on to each of the successor nodes 61 visited. Then, when the flow graph 46 walk completes, this set of field 65 represents the registers which are written but not subsequently read in the routine. This set is reported to the user in a "hint" message, as possible output registers of the routine. The user may use this information to add the correct OUTPUT register clause to the routine entry point declaration. b) Stack references and modifications--modifications to the stack may be the result of explicit instructions, such as PUSH/POP ADD, etc., or due to the VAX addressing mode used, such as (SP)+, which implicitly pops the stack pointer. At the end of the tuples 35 for the current node 61, the net change to SP duel to the tuples in this node is stored in a field 67 in the flow node. The total depth thus far in the routine flow is also computed. This is passed to the node processing routine with each recursive call, and stored in the node in a field 68. Thus, at every point during this walk, the compiler has available the total stack change since routine entry. This allows it to detect code which: (i) reads the return address from the stack (ii) modifies the return address on the stack (iii) removes the return address from the stack (iv) issues a jump-subroutine JSB procedure call through the return address to implement a co-routine linkage (v) makes an up-level stack reference (vi) makes an unaligned stack reference (vi) modifies SP such that it is no longer longword aligned These are all flagged with specific errors. The first five are machine architecture and calling standard-specific coding practices which must be changed manually in the source code. The latter two are flagged due to the performance penalties of unaligned stack references. As mentioned above, successor nodes 61 in the flow graph 46 which are already marked "visited" in a field 69 are not re-visited; however, the flow analyzer 43 checks the initial stack depth stored with the node in field 68. If that depth is different than the total depth at the end of the current node 61, the compiler reports a message indicating that this point in the code can be reached with different stack depths. This may indicate a source code error, where the stack was not correctly adjusted by the user on some code path. A simplified example of this might be:
______________________________________
push1 r1
beq1 lab1
. ;instructions which do not modify SP
.
push1 r2
. ; instructions which do not modify SP
.
.
lab1: pop1 r2 ; This point may be reached with 1
; or 2 new longwords on the stack.
rsb ; In this case, it is probably an
; error, because the RSB instruction
; expects the return address
; to be on top of the stack.
______________________________________
The flow analyzer 43 the makes a second pass through each routine in the module. This time, the walk is in reverse flow order, starting at the routine exit node, and walking backward through all paths back to the routine entry point. This is also a recursive graph walk, using the edges which link each node 61 to its predecessors. This time, nodes 61 may be re-visited multiple times. The tuples 35 of each node 61 are scanned in reverse order, looking for the following: (a) instructions which read the VAX condition codes. For example, conditional branch instructions. A set of which condition codes (CCs) are currently "required" as recorded in a field 70 is updated. For example, when a BEQL is seen, the Z bit will be added to this set. (b) instructions which set the VAX CCs which are currently in the "required" set of field 70. When found, a flag 57 corresponding to the particular CC is set in the instruction tuple 35, and it is removed from the "required" set of field 70. This flag 57 in the tuple tells the code generator phase 28 that it must realize the value of that condition code for this instruction. This allows the compiler to calculate CC information only when it is absolutely required. (c) JSB instructions. If the "required" set of field 70 is not empty when a JSB instruction is encountered, the source code as written relies on a CC being set by the JSB target routine, and still intact upon return. Since the CCs are not hardware bits on some advanced RISC architectures, for example, as they are on VAX, this architecture specific coding practice must be changed--so an error message is generated. At each call to process a nodes predecessor, the current "required" set of field 70 is passed, and stored in field 70 of the predecessor node. The node is then processed as above. If the node is encountered later in another backward flow path, but the "required" set is a subset of the set previously stored, the node (and its predecessors) does not need to be revisited. However, if the new "required" set contains CCs not previously searched for, the node must be re-processed to insure the CC flag is set on the correct instruction. Also at each call to process a node's predecessor, the current node's "input register" set of field 64 (computed in the forward walk) is passed. The "input register" set of field 64 for the predecessor is then updated to include those registers in the passed set which are not in its own "written registers" set of field 66. As a result, the "input register" set for a node will eventually reflect all registers read by this node or any of its successors which are "input" to this point in the flow. Also for each node, the node's "written registers" set of field 66 is added to the "written" set for the current routine. After all reverse paths through a routine have been processed thusly, the information stored in the flow node 61 for the routine entry point is examined. If the "required" CC set of field 70 is not empty, it implies that the corresponding condition codes are expected as input to this routine. This is a VAX architecture specific coding practice, and it therefore flagged as an error; it is undesirable on some architectures and impossible on others. (This may also be indicative of a coding error, rather than an intentional interface.) The particular CCs required as inputs are reported to the user is the printout. If the "input register" set stored in this node at field 64 is not empty, those registers are reported in a compiler "hint" message as possible input registers to the routine. These registers can then be added to the entry point declaration as input registers. (Again, this may also detect a coding error, where an uninitialized register is inadvertently used.) The "written" set of field 66 for the routine is used in conjunction with the OUTPUT register declarations for the routine, to determine which registers the compiler must generate code to save. The original values of these modified registers may be saved In the source code, using, for example, PUSHL and POPL instructions. However, these instructions will only save the low 32-bits of the register value. Since the code will be executing in a 64-bit environment if code is being generated for the advanced 64-bit RISC architecture, the compiler must generate 64-bit register saves in routine prologue code, and restore them in routine epilogue code. The compiler saves those in the "written set" which are not declared to be OUTPUT (or SCRATCH) registers. (ROA 2) The following program is used to illustrate these concepts:
______________________________________
Test: .jsb.sub.-- entry
push1 r0
beq1 lab2
addl3 r1, r2, -(sp)
blss lab1
movl (sp)+, r3
brb lab2
lab1: addl2 #4, sp
lab2: popl r5
rsb
______________________________________
This same program is also shown in FIG. 8, where it is seen that the tuples are numbered $22 to $31, and the nodes are numbered Node-4 to Node-9. The flow of the nodes for this program is seen in FIG. 9. For this program, the output of the front end converter 20 is shown in Appendix A, showing how the program is represented as the tuples $22-$31 in the intermediate language. The numbers such as 1725024 are the byte addresses of the data location for the present part of a tuple, the previous part and the next part, so the data structure of FIG. 4 for a tuple 35 may be found in memory, and the ordered sequence of tuples is traceable. Also, it is seen that the operands (fields 38 of FIG. 4) are identified by pointers to the actual memory location of the specification of these elements. Next, the flow analyzer 43 output is given in Appendix B, showing the flow nodes and their linkages. Note that the tuples are re-ordered somewhat. The output code generated for this program as a result is given in Appendix C. In Appendix D, a listing is given for a different program (not that of FIG. 6) showing some of the compiler messages mentioned above. This listing is printed out by the facility ordinarily included in a compiler for producing a source code listing for use in error checking and correction. Referring to FIGS. 10-15, logic flow charts are illustrated which represent a view of the flow analysis involved in methods having features of the invention. The calling structure is summarized in the following paragraphs. The procedure referred to as Build.sub.-- Flow.sub.-- Graph, illustrated in FIG. 10, is called once per compilation, and functions to build all of the routine flow graphs for the entire module being compiled. The procedure referred to as Analyze.sub.-- Flow.sub.-- Graph, illustrated in FIG. 11, is called after Build.sub.-- Flow.sub.-- Graph, also once per compilation, and functions to perform the analysis on all the routines in the module. The procedure referred to as Traverse.sub.-- Graph.sub.-- Forward, illustrated in FIG. 12, is called by Analyze.sub.-- Flow.sub.-- Graph, and itself calls Process.sub.-- Forward.sub.-- Node of FIG. 14a, to process the tuples of the current node in forward order, and then calls itself recursively for each successor of the current node which has not already been visited. The procedure referred to as Traverse.sub.-- Graph.sub.-- Backward, illustrated in FIG. 13, is called by Analyze.sub.-- How.sub.-- Graph, and itself calls Process.sub.-- Backward.sub.-- Node of FIG. 15, to process the tuples of the current node in reverse order, and then calls itself recursively for each predecessor of the current node, unless it has been visited and the register and condition code information stored in it indicate that a re-visit is not necessary. The procedure referred to as Process.sub.-- Forward.sub.-- Node, illustrated in FIG. 14a-14b, is self-contained, and functions to simply walk the tuples in forward order. The procedure referred to as Process.sub.-- Backward.sub.-- Node, illustrated in FIG. 15, is self-confined, and functions to simply walk the tuples in reverse order. The "pseudo-variables" used in the flow charts of FIGS. 10-15 will be described, before describing the flow charts in detail. The pseudo-variables are represented in the flow charts as names in quotes, and reference to the fields of FIGS. 4 or 5 is also given: "Input.sub.-- CCs" or input condition codes (field 71)--for a flow node, "Input.sub.-- CCs" are the set of condition codes which are "required" at entry to the flow node. That is, some instructions either in this node or one of its successors read these condition codes, and the instructions which set them precede this node. "Input.sub.-- regs" or input registers (field 154)--for a flow node, "Input.sub.-- regs" are the set of registers which are read in this node or one of its successors, and the instructions which write into these registers proceed this node. "Output.sub.-- regs" or output registers (field 65)--for a flow node, "Output.sub.-- regs" are the set of registers which are written in this node or one of its predecessors, but not subsequently read by this point in the flow graph. "Written.sub.-- regs" or written registers (field 66)--for a flow node, "Written.sub.-- regs" are the set of registers which are written to in this node itself. "Required.sub.-- CCs" or required condition codes (field 70)--at each point during backward flow analysis, the set of condition codes which are read by some subsequent instruction. They are "required" because some previous instruction must set them. "Required.sub.-- regs" or required registers (field 72)--at each point during backward flow analysis, the set of registers which are read by some subsequent instruction, which have not yet been written by any instructions. Note that for the "Required.sub.-- CCs" and "Required.sub.-- regs" the reference to "subsequent" means subsequent in the normal routine flow, not subsequent in the processing pass. "Previous" means earlier in the normal routine flow. The routine is being processed backward, so reference to "subsequent" and "previous" must be clearly kept in mind. Referring now the FIG. 10, when Build.sub.-- Flow.sub.-- Graph is invoked, the selected program section, i.e., tuple stream 41, is examined, and the decision point 80 examines to see if there are more tuples in this section. If not, the procedure is exited at point 81; if so, then the next tuple is fetched as indicated by the item 82. This next ruble is examined to see if it is a label or entry point tuple, at decision point 83. If so, then the current node is ended at the previous tuple, at item 84, and this tuple is noted as starting a new node, at item 85, after which control returns to the decision point 80 via path 86. If, at decision point 83, the tuple is found not to be a label or entry point, it is examined at point 87 to see if it is an unconditional branch or return tuple. If so, the current node is ended with this tuple, as indicated by item 88, and the next tuple is noted as starting a new node, at item 89. A flow edge is created from the current node--to the branch target node--as indicated by the item 90, alter which control returns to the decision point 80 via path 86. If, at decision point 87, the tuple is found to be neither an unconditional branch or a return tuple, then it is examined to see if it is a conditional branch tuple, indicated by decision point 91. If so, again the current node is ended with this tuple, as indicated by item 92, and the next tuple is noted as starting a new node, at item 93. A flow edge is created from the current node--to the new node--as indicated by the item 94. The a flow edge is created from the current node--to the branch target node--as indicted by the item 95, after which control returns to the decision point 80 via path 86. If, at decision point 91, a conditional branch was not found, then control returns to point 80. Referring to FIG. 11, the procedure Analyze.sub.-- Flow.sub.-- Graph begins by getting the head of the routine list for the module being processed, as indicated by the item 100. Then, the list is checked to see if there are more routines in the module, at decision point 101. If so, then the procedure Traverse.sub.-- Graph.sub.-- Forward is called for the next routine, as indicated by the item 102; the Traverse.sub.-- Graph.sub.-- Forward is discussed below with reference to FIG. 12. If not, then again the head of the routine list is fetched, at item 103, and again a check is made at decision point 104 of whether here are more routines in the module. If yes, then the Traverse.sub.-- Graph.sub.-- Backward procedure is called for the next routine, as indicated by the item 105 of the flow chart, passing empty Required-CCs" and "Required-regs". As indicated by the item 106, the "Output-regs" value returned by Traverse.sub.-- Graph.sub.-- Backward is stored as output registers for the routine. If no is the result at decision point 104, then again the head of the routine list for the module is fetched, at item 107, and a test is made to see if there are more routines in the module at point 108. If not, control returns to the calling procedure at point 109; if so, the flow node at head of routine is fetched at item 110, and this data is examined at decision points 111, 112 and 113 to see if the "Input-regs", "Output-regs" and Input-CCs" are non,zero. Each of these showing non-zero results in a report hint at items 114, 115 or 116 as indicated. This is done for each flow node at head of each routine, and after the last routine control returns at point 109. Referring to FIG. 12, the Traverse.sub.-- Graph.sub.-- Forward routine, called from item 102 of FIG. 11, begins at item 120 by calling the Process.sub.-- Forward.sub.-- Node procedure of FIG. 14a, for this node. After return from the Process.sub.-- Forward.sub.-- Node call, for each node, a check is made at decision point 121 to see if there are any successor nodes. If not, control returns to item 102 of FIG. 11 via point 122. If so, information about the successor node is fetched at item 123, and checked to see if it has already been visited at decision point 124. If already visited, then at decision point 125 the initial stack depth of successor node (isd.sub.s) is compared to a value of he final stack depth of the current node (isd.sub.c); if these are equal then control returns to the item 121 via path 126, but if not the item 127 reports a "runtime stack difference" message, indicating that this code point can be reached with different stack depths. If at point 124 the successor node is found not previously visited, the item 128 is entered where the initial stack depth of the successor node (isd.sub.s) is set to the initial stack depth of the current node (isd.sub.c) plus the total stack change in the current node. Then, the Traverse.sub.-- Graph.sub.-- Forward procedure is called for the successor node, at item 129. Return from Traverse.sub.-- Graph.sub.-- Forward passes control back to the point 121, checking for any successor nodes. The Traverse.sub.-- Graph.sub.-- Backward procedure illustrated in FIG. 13 begins by calling the Process.sub.-- Backward.sub.-- Node procedure at item 130, passing "Required-CCs" as a parameter. Upon return from Process.sub.-- Backward.sub.-- Node, the item 131 is entered; in item 131 the operation is to add registers which are in "Required-regs" (but are not in the "Written-regs" set for the current node) to the "Input-regs" set for the current node. Next, at decision point 132, a check is made to see if there are any predecessor nodes. If not, the control returns to the call Traverse.sub.-- Graph.sub.-- Backward point, with "Output-regs" as a parameter, via point 133. If so, information for the predecessor node is fetched at item 134, and a check is made at point 135 of whether the predecessor node has been visited already. If already visited, a check is made at point 136 of whether the "Required-CCs" or "Required-regs" sets are different for this visit; if non control returns to point 132 to see if there are any predecessor nodes, but if so then item 137 is entered to call Traverse.sub.-- Graph.sub.-- Backward for the predecessor node, passing the Input-regs" set and "Input-CCs" set as parameters. The returned "Output-regs" which are not in the "Input-regs" or "Written-regs" sets are added to the "Output-regs" set for this node, at item 138. Control is returned to the point 132 to determine if there are any predecessor nodes. Referring to FIGS. 14a and 14b, the Process.sub.-- Forward.sub.-- Node procedure is illustrated in flow chart form. First, at point 140 of FIG. 14a, a check is made to see if there are more tuples in the node. If not, control is returned to the calling procedure, item 120 of FIG. 12. If so, the next tuple is fetched at item 141, and the next tuple is checked at point 142 to see if it is a register reference. If so, then the tuple is checked at points 143 and 144 to see if it is a read or write reference. If neither a read reference nor a write reference, control returns to point 140 via path 145. If the tuple is a read reference, the tuple is checked at point 146 to see if it is in the "Written-regs" set, and, if so, it is removed from the "Output-regs" set at item 147, but if not then the register is added to the "Input-regs" set at item 148. If the tuple is a write reference, then the register is added to the "Written-regs" set at item 149, and added to the "Output-regs" set at item 150, before returning to point 140 via path 145. If, at point 142 of FIG. 14a, it is found that the tuple is not a register reference, then flow goes to the stack check beginning point 151 of FIG. 14b. The tuple is chewed at point 152 to see if it indicates a stack pointer SP modification, and if so the stack pointer SP change is added to the total stack change for this node, at item 153, after which control is returned to the point 140 via path 154. If the tuple does not indicate a SP modification, then it is checked at point 155 to see if it is a stack pointer reference with offset less than .phi., where offset here indicates (offset specified in tuple plus the total offset at this point in the routine flow). If so, an "uplevel stack reference" error is reported at item 156, then return via path 154. If not, then the tuple is checked at point 157 to see if it is a stack pointer reference with offset equal to .phi.; if so the tuple is checked at point 158 to see if it is a "write" reference, and if a write reference a "return address modification" error is reported at item 159, but if not a write reference then a "return address reference" error is reported at item 160, before returning via path 154 in either case. A negative result from the check at point 157 results in control passing to the check at point 161 where the tuple is examined to see if it is a return-subroutine RSB instruction. If an RSB instruction, a check is made at point 162 to see if the current stack offset plus the initial stack value is greater than .phi., and if so an "alternate return address on stack" error is reported at item 163, but if not then a check is made at point 164 to see if the current stack offset plus the initial stack value is less than .phi., in which case an "uplevel return" error is reported at point 165. If the tuple is not an RSB instruction, then it is checked at point 166 to see if it is a jump-subroutine JSB instruction, in which case it is checked at point 167 to see if the JSB target is a stack pointer based location, with offset plus current stack offset plus initial stack value equal to .phi., in which case a co-routine call" error is reported at item 168. If none of the tests at points 152, 155, 157, 161, or 166 is positive, the stack is not involved, and control passes back to the point 140 of FIG. 14a via path 154. The Process.sub.-- Backward.sub.-- Node procedure illustrated in FIG. 15 begins by checking to ee if there are more tuples in the node, at point 170. If not, control returns via point 171. If so, the next tuple is fetched at item 172. Then the next tuple is examined at point 173 to determine if it represents an instruction which sets the conditional codes. If so, then the condition codes which this instruction sets are removed from the "Required-CCs" set, as indicated by the item 174. A flag is set (item 175) the tuple indicating which condition codes which were required must be realized for this instruction. If the tuple does not represent an instruction which sets condition codes, then control passes to a decision point 176 where the tuple is checked to see if it represents an instruction which reads condition codes. If so, then the condition codes which the instruction reads are added to the "Required-CCs" set at item 174. If the tuple does not represent an instruction which either sets or reads condition codes, then it is checked at point 178 to see if it represents a jump-subroutine JSB instruction, and if so then it is checked at point 179 to see if the "Required-CCs" set is empty and if not empty then a "Condition code required after JSB" error is reported at item 180. If the test at point 179 is positive, i.e., the "Required-CCs" set is empty, control returns via path 181 to the point 170. Likewise, if the tuple does not satisfy any of the tests of decision points 173, 176 or 178, control returns via path 181 to see if there are more tuples. According to another feature of the invention, argument list references are mapped across the architectures in making the code translation in the system of FIG. 1. In translating code to a different machine architecture it is typically the case that the way argument list references are handled is different. VAX assembly language routines rely on the argument list pointer (AP) established by the VAX CALLs/CALLG instructions to refer to routine parameters. Referring to the following example of VAX code:
______________________________________
.entry rout1 M<R2>
.
.
.
tstl (AP)
beql lab1
movl 4(AP),R0
mov1 8(AP),R2
.
.
.
lab 1 .
.
______________________________________
This routine rout1 is called by, for example:
______________________________________
pushl #1
pushl #5
calls #2,rout1
______________________________________
The stack thus has the literal #2 (number of arguments to be passed) at top-of-stack, and literals #1 and #5 in the next two longwords of the stack. In referencing these via the AP register established by the VAX hardware for the CALLS instruction, the code with the two movl instructions moves the first two longwords from the stack to R0 and R2. In contrast, on an advanced 64-bit RISC machine, there is no architected argument list pointer (AP), and the calling standard dictates that parameters are passed in registers, or, if necessary, on top of the stack. A RISC machine has a large number of registers, e.g., thirty-two 64-bit registers, and these are used in passing arguments, instead of memory references to stack as VAX uses. For example, the argument information may be designated to be in register-25 (R25), and R16-R21 used for arguments. Then, if there are more than six arguments to be passed, the calling routine eaves the remainder of the arguments on top of the stack. Thus, an example of code to set up for a jump to a subroutine for this type of machine, assuming there are eight arguments, is as follows:
______________________________________
LDQ R16,arg1
LDQ R17,arg2
.
.
.
LDQ R21,arg6
SUBQ SP,#16,SP
STQ R5,8(SP)
STQ R6,0(SP)
JSR R28,R24
______________________________________
The code translator, according to another feature of one embodiment of the invention, resolves this difference in the way argument lists are passed, without requiring all argument list references to be modified by hand by the user through editing the source code. The compiler examines all AP-based memory references in the input code to determine how the same argument reference may be made in the target environment. Element 0 of the argument list vector represents the argument count on VAX; in the target RISC architecture, the argument count appears in a defined register, e.g., the Argument Information Register (R25). Hence, in this instance, a memory reference of the form 0(AP) will be compiled to an R25 reference. The first six arguments are received in registers R16-R21 on in the target RISC architecture, so that 4(AP) will be compiled to use R16, 8(AP) to use R17, etc. If there are variable offsets for the arguments in the VAX code, other steps must be taken. For example, if the VAX code is of the form MOVL 4(AP)[R0],R1 so that a run-time indexed reference is made, it is necessary to make a different translation. In this case, the compiler mimics VAX argument lists by packing the quadword register and stack arguments into a longword argument list on the stack. This is referred to as argument list "homing", and occurs if the compiler detects any AP uses which may result in aliased references to the argument list, any AP references with variable indices, or any non-longword aligned AP offsets. In this case, argument list references are compiled into FP (frame pointer) based references to the homed list, which is built by code generated for the routine entry point. Thus, when a CALLS (call subroutine) instruction is encountered in the input VAX code, the storage allocator 27 of the compiler generates code to copy arguments from the stack, where they have been placed by the original source code, into the RISC argument registers. If there are more than six arguments (requiring more than R16-R21), the seventh and beyond must be copied to consecutive aligned 64-bit slots on top of the stack. The argument information register R25 receives the argument count, which, on VAX, would have been at 0(FP). Corresponding code to clean the stack after the called routine returns is also generated. Referring to FIG. 16, a logic flow chart of a procedure used in the storage allocation phase for mapping argument list references in translating VAX code to advanced 64-bit RISC machine architecture is illustrated, as used in the method of one feature of the invention, according to one embodiment. A tuple is fetched at item 190, and examined to see if it is a memref at decision point 191. If not, the control returns via path 192. If so, it memref is checked to see if the base register is AP at point 193, and if so, checked at point 194 to see if the argument list has been homed; if not then checked at point 195 to see if the offset is <28 (meaning the number of longword is less than seven). When the result at point 195 is yes, this means the argument is going to a register location, so at item the offset is divided by four to get the argument index in the registers R17 to R21, and the memory reference is changed to a register reference. If the result at point 195 is no, that means the argument is to be in the stack frame, so in item 197 the offset is divided by four to get the argument index, and 8*index is added to the stack frame size; also the memory reference is changed to an offset and the register reference is changed to the frame pointer. If it is found in decision point 194 that the argument list has been homed, then the operation in item 198 is to change the argument pointer AP to a frame pointer FP in the register reference, and add the offset to the homed list in the frame, to the offset. While this invention has been described with reference to specific embodiments, this description is not meant to be construed in a limiting sense. Various modifications of the disclosed embodiments, as well as other embodiments of the invention, will be apparent to persons skilled in the art upon reference to this description. It is therefore contemplated that the appended claims will cover any such modifications or embodiments as fall within the true scope of the invention.
|
Same subclass Same class Consider this |
||||||||||