Object code structure and method for translation of architecture independent program implementations

Abstract

Endian format affects the representation of both literal data and pointer data whether represented in a global data specification (i.e., in a data section) or as immediate operand values in-line with Intercode instructions. The present invention provides for endian-independent representation of literal data, pointer data, literal operands and pointer operands. For literal data represented in a data section, an associated data translation script provides an Intercode translator with translation instructions for transforming byte ordering within the data section on a unit-of-storage by unit-of-storage basis (if required for the particular target processor). In this way, literal data of arbitrary structure can be specified independent of endian format. For pointer data represented in the data section, the associated data translation script provides the Intercode translator with relocation expressions for transforming pointer data values to effective memory addresses. Relocation expressions compute a linear combination of relterms, wherein relterms include constants, data section addresses, function gate addresses, and translation time constants. The translation time constants evaluate to a first value if evaluated on a little-endian target processor and to a second value if evaluated on a big-endian target processor. In this way, pointer data values can be specified independent of actual runtime location of the data to which the pointer operand refers and independent of endian format. A sequence of transformation instructions and relocation expressions are provided in the form of a data translation script to allow for endian-independent representation arbitrary data structures which include both literal and pointer data.

Claims

What is claimed is:

1. An object code structure for dynamic translation of an architecture-independent program implementation into native code for a target architecture, the object code structure encoded in computer readable media and comprising:

a code section;

a data section associated with the code section and including a first representation of data organized as units of storage;

a data translation script associated with the first representation, the data translation script including an instruction sequence for reversing byte ordering within the units of storage of the first representation when the first representation is not in accordance with byte ordering of the target architecture;

wherein the first representation includes first and second units of storage, the first unit of storage representing literal data and the second unit of storage representing pointer data;

wherein the data translation script includes a translation instruction corresponding to the first unit of storage and descriptive of an endian transformation of the literal data;

wherein the data translation script further includes a relocation expression corresponding to the second unit of storage and descriptive of a transformation of the pointer data to an effective memory address, the relocation expression encoding a linear combination of terms comprising one or more terms selected from a set comprising a constant term, a data section address term, a function gate address term, and a translation time constant term;

the object code structure further comprising first and second flags associated with the data section, the first flag indicating whether the first representation is in big-endian format and the second flag indicating whether the first representation is in little-endian format;

wherein the translation instruction transforms byte ordering of the first unit of storage,

when evaluated on a big-endian target architecture, if the first flag does not indicate that the first representation is in big-endian format, and

when evaluated on a little-endian target architecture, if the second flag does not indicate that the first representation is in little-endian format,

wherein the translation time constant term, if any, evaluates to a first byte offset,

when evaluated on a big-endian target architecture, if the first representation flag does not indicate that the first representation is in big-endian format, and

when evaluated on a little-endian target architecture, if the first representation flag does not indicate that the first representation is in little-endian format; and

wherein the translation time constant term, if any, evaluates to a second byte offset, otherwise.

2. An object code structure as recited in claim 1, wherein the first and second flags are encoded separately, and wherein first and second flag indications respectively indicating that the first representation is in big-endian and little-endian format signify that the first representation is endian neutral.

3. An object code structure as recited in claim 1, wherein the first and second flags are encoded as alternate states of a single storage location.

4. An object code structure as recited in claim 1, wherein the first byte offset is non-zero and the second byte offset is zero.

5. An object code structure as recited in claim 1:

wherein the translation time constant is for evaluation under control of a translation process running on the target architecture;

wherein, when the first representation is in big-endian format, evaluation of the translation time constant supplies a non-zero byte offset term in the relocation expression if the target architecture is little-endian and supplies a zero byte offset term in the relocation expression if the target architecture is big-endian; and

wherein, when the first representation is in little-endian format, evaluation of the translation time constant supplies a non-zero byte offset term in the relocation expression if the target architecture is big-endian and supplies a zero byte offset term in the relocation expression if the target architecture is little-endian.

6. An object code structure for dynamic translation of an architecture-independent program implementation into native code for a target architecture, the object code structure encoded in computer readable media and comprising:

a code section;

a data section associated with the code section and including first and second representations of data, each organized as units of storage, the first representation including first and second units of storage and the second representation including third and fourth units of storage, the first and third units of storage representing corresponding big-endian and little-endian representations of literal data, the second and fourth units of storage representing corresponding representations of pointer data;

a first data translation script associated with the first representation, the first data translation script including a first relocation expression corresponding to the second unit of storage and descriptive of a transformation of pointer data represented therein to an effective memory address; and

a second data translation script associated with the second representation, the second data translation script including a second relocation expression corresponding to the fourth unit of storage and descriptive of a transformation of pointer data represented therein to an effective memory address;

wherein the first and second relocation expressions encode linear combinations of terms, the linear combinations of terms comprising one or more terms selected from a set comprising a constant term, a data section address term, a function gate address term, and a translation time constant term.

7. An object code structure as recited in claim 6, wherein the translation time constant term, if any, evaluates to one of a first value and a second value depending on whether the corresponding relocation expression is evaluated on a big-endian or a little-endian target architecture.

8. An object code structure as recited in claim 7, wherein the first value is a non-zero byte offset and the second value is a zero byte offset.

9. An object code structure for dynamic translation of an architecture-independent program implementation into native code for a target architecture, the object code structure encoded in computer readable media and comprising:

a code section;

a data section associated with the code section and including a first representation of data organized as units of storage; and

a data translation script associated with the first representation, the data translation script including an instruction sequence for reversing byte ordering within the units of storage of the first representation when the first representation is not in accordance with byte ordering of the target architecture;

wherein the first representation includes first and second units of storage, the first unit of storage representing literal data and the second unit of storage representing pointer data;

wherein the data translation script includes a translation instruction corresponding to the first unit of storage and descriptive of an endian transformation of the literal data;

wherein the data translation script further includes a relocation expression corresponding to the second unit of storage and descriptive of a transformation of the pointer data to an effective memory address, the relocation expression encoding a linear combination of terms comprising one or more terms selected from a set comprising a constant term, a data section address term, a function gate address term, and a translation time constant term; and

wherein the translation time constant term, if any, evaluates to a first byte offset,

when evaluated on a big-endian target architecture, if the first representation flag does not indicate that the first representation is in big-endian format, and

when evaluated on a little-endian target architecture, if the first representation flag does not indicate that the first representation is in little-endian format; and

wherein the translation time constant term, if any, evaluates to a second byte offset, otherwise.

10. An object code structure as recited in claim 9, wherein the first and second flags are encoded separately, and wherein first and second flag indications respectively indicating that the first representation is in big-endian and little-endian format signify that the first representation is endian neutral.

11. An object code structure as recited in claim 9, wherein the first and second flags are encoded as alternate states of a single storage location.

12. An object code structure as recited in claim 9:

wherein the translation time constant is for evaluation under control of a translation process running on the target architecture;

wherein, when the first representation is in big-endian format, evaluation of the translation time constant supplies a non-zero byte offset term in the relocation expression if the target architecture is little-endian and supplies a zero byte offset term in the relocation expression if the target architecture is big-endian; and

wherein, when the first representation is in little-endian format, evaluation of the translation time constant supplies a non-zero byte offset term in the relocation expression if the target architecture is big-endian and supplies a zero byte offset term in the relocation expression if the target architecture is little-endian.

13. An object code structure as recited in claim 9, further comprising:

first and second flags associated with the data section, the first flag indicating whether the first representation is in big-endian format and the second flag indicating whether the first representation is in little-endian format,

wherein the translation instruction transforms byte ordering of the first unit of storage,

when evaluated on a big-endian target architecture, if the first flag does not indicate that the first representation is in big-endian format, and

when evaluated on a little-endian target architecture, if the second flag does not indicate that the first representation is in little-endian format .

Description

BACKGROUND OF THE INVENTION

1. Field of the Invention

The present invention relates to a portable virtual machine architecture, and more particularly to object code structures for dynamic translation of an architecture-independent program implementation.

2. Description of the Relevant Art

There have been a number of efforts to design systems which are portable across machine architectures, i.e., systems which can operate on a variety of different hardware platforms. However, such efforts have been hampered by incompatibilities in operating system interfaces and fundamental hardware capabilities. Approaches to the portability problem have included interpreters, translators, compilers with a common intermediate format across platforms, and virtual machine architectures. Although the various approaches tend to blur together, some distinctions can be made. Interpreters are programs which accept programs written in source code and which perform the sequence of computations, i.e., of machine level instructions, implied by the source code. The UCSD Pascal system, which was the primary implementation of Pascal for the Apple II, was one of the most successful early attempts at a portable system. The system interpreted byte code which made it architecture-independent (see Apple Computer, Inc. Apple Pascal Operating System Reference Manual, 1980, pp. 229-245). Smalltalk-80 also defined a byte-code interpreter (see Adele Goldberg and David Robson, Smalltalk80: The Language and its Implementation, Addison-Wesley, 1983). One of Smalltalk-80's main advances was the clean integration of the interpreter into the system, where the system has a flexible interface to examine and control interpretation, permitting one to write portable programming tools. Some variants of the Smalltalk-80 system dynamically compiled the byte-code with some sacrifice in the above functionality.

A translator, as contrasted with an interpreter, accepts as an input a program written in a source format and produces as output an object code representation of the program. Usually, the object code is machine language for a particular processor architecture. Translators can be divided into assembler translators, which translate low level languages such as assembly language, and compilers, which translate high-level languages such as C, C++, Pascal, Ada, etc.

Compiler writers have been striving to achieve a common intermediate format for some time. A common intermediate format would enable them to produce n front ends and m back ends (n+m total components) rather than n*m compilers to compile n languages for m target machine architectures. The GNU C compiler went quite far in this direction, but the intermediate format is ad hoc and is riddled with special cases for architectural features. The Marion system (see David G. Bradlee, Robert R. Henry, and Susan J. Eggers, The Marion System for Retargetable Instruction Scheduling, Proceedings of the 1991 ACM SIGPLAN Conference on Programming Language Design and Implementation, 1991, pp. 229-240) was another attempt, but it too had to be modified for each new target architecture.

Hardware designers have attempted to institute a virtual architecture as the assembly language for their systems. The Transputer, which is a modular, scalable multiprocessor architecture is an example of such a system. The virtual architecture allows changes in the underlying physical structure of the machine architecture without program recompilation. Limited virtual architecture mechanisms can be seen in processors such as the Motorola 68040, where some instructions are emulated by traps. A related software approach is to defme an intermediate form from which programs are translated into the machine language of the target processor. Mahler was an attempt at this and the authors claim encouraging results (see David W. Wall and Michael L. Powell, The Mahler Experience: Using an Intermediate Language as the Machine Description, Proceedings of the 2nd International Conference on Architectural Support for Programming Languages and Operating Systems, 1987, pp. 100-104).

The Open Software Foundation's (OSF's) ANDF (the Architecture-Neutral Distribution Format) and its precursor TDF are other steps in this direction. See Stavros Macrakis, The Structure of ANDF: Principles and Examples, Open Software Foundation, 1993 and United Kingdom Defense Research Agency, TDF Specification, Issue 2.1 June 1993. ANDF defmes the form of data passed from an ANDF producer (which is language-dependent and machine-independent) to an ANDF installer (which is language- and machine-independent). An ANDF producer is like a compiler front-end (syntax and semantics analyzer), and an ANDF installer is end (code generator and optimizer). ANDF itself is thus a form of compiler intermediate language. Unfortunately, since ANDF (and TDF) leaves most of the compiling work to the installer, it is unsuitable for dynamic translation.

Individual machine architectures often represent data according to differing sets of representation conventions. Representations which are in accordance with the conventions of a particular machine architecture are said to be native to that machine architecture. Two common sources of variation in native representations are alignment and byte-ordering conventions.

Certain processor architectures require that data be aligned in accordance with a set of machine-specific alignment rules. For example, most RISC architectures require that data be aligned on a natural boundary in physical memory (i.e., at an address that is a multiple of the size of the data type). For a two-byte quantity (e.g., a 16-bit, or short, integer) such a natural boundary alignment requirement requires that the first byte of the two-quantity appear at an even byte address. Similarly, the first byte of a four-byte quantity (e.g., a 32-bit, or long, integer) and of an eight-byte quantity (e.g., a double precision floating point number) must appear at an address which is a multiple of 4 and 8, respectively. Other architectures, notably the 80.times.86 architecture, have no such alignment restrictions.

Another source of architecture-specific variation is byte-ordering. In some processor architectures, bytes are ordered according to a scheme where the least significant byte is stored in the lowest byte address. This scheme is known as little-endian byte ordering. In many other architectures, bytes are ordered according to a big-endian scheme where the least significant byte is stored in the highest byte address. FIG. 1A illustrates the representation of the number 1,000,000 (i.e., 0F4240 in hexadecimal) as a 32-bit integer in accordance with the big-endian scheme. FIG. 1B illustrates the corresponding little-endian representation. Most microprocessor architectures including the Motorola 680.times.0 and 88.times.00 series, the PowerPC, the MIPS R.times.000 series microprocessors adhere to the big-endian scheme. However, several architectures, notably the Intel 80.times.86 series and the DEC VAX architectures, are little-endian.

SUMMARY OF THE INVENTION

It has been discovered that a high degree of architectural independence can be achieved by providing a compiler which generates a machine independent object code format (i.e., Intercode object code) which is translated at run-time into native code for a particular target machine architecture. Such run-time translation involves the conversion of Intercode instruction sequences to native code sequences and the conversion of static data formats to native data formats. In particular, the present invention includes data translation scripts compiled into the Intercode object code which provide for run-time relocation of pointers and for run-time byte order conversion of data from bigendian format to little-endian format (or vice versa). The specific relocations and byte order conversions performed at run-time are responsive to native data formats of the target machine architecture. In this way, a common distribution format is provided for programs which can efficiently run on both big- and little-endian machine architectures.

Endian format affects the representation of both literal data and pointer data whether represented in a global data specification (i.e., in a data section) or as immediate operand values in-line with Intercode instructions. The present invention provides for endian-independent representation of literal data, pointer data, literal operands and pointer operands.

For literal data represented in a data section, an associated data translation script provides an Intercode translator with translation instructions for transforming byte ordering within the data section on a unit-of-storage by unit-of-storage basis (if required for the particular target processor). In this way, literal data of arbitrary structure can be specified independent of endian format. For pointer data represented in the data section, the associated data translation script provides the Intercode translator with relocation expressions for transforming pointer data values to effective memory addresses. Relocation expressions compute a linear combination of relterms, where such relterms include constants, data section addresses, function gate addresses, and translation time constants. The translation time constants evaluate to a first value if evaluated on a little-endian target processor and to a second value if evaluated on a big-endian target processor. In this way, pointer data values can be specified independent of actual runtirne location of the data to which the pointer operand refers and independent of endian format. A sequence of transformation instructions and relocation expressions are provided in the form of a data translation script to allow for endian-independent representation of arbitrary data structures which include both literal and pointer data.

For literal operands represented as immediate values in-line with Intercode instructions, the storage size of a literal operand representation correlates with the associated Intercode instruction opcode and, for certain integer operands, with the particular operand encoding. Since literal operand values for Intercode instructions are encoded in a known endian format (namely, big-endian) and since the storage size of an individual immediate operand is encoded either by the associated Intercode instruction or by the operand encoding itself, an Intercode translator can perform the appropriate byte ordering transformation (if the target processor requires little endian format). For pointer operands represented as immediate values in-line with Intercode instructions, individual pointer operands are represented as relocation expressions. As before, relocation expressions compute a linear combination of relterms, wherein the translation time constants included therein evaluate to a first value if evaluated on a little-endian target processor and to a second value if evaluated on a big-endian target processor. In this way, pointer operand values can be specified independent of actual runtime location of the data to which the pointer operand refers and independent of endian format.

In one embodiment, an object code structure encoded in computer readable media includes a code section, a data section associated with the code section, and a data translation script. The data section includes a first representation of data organized as units of storage and the data translation script is associated with the first representation. The data translation script includes an instruction sequence for reversing byte ordering within the units of storage of the first representation when the first representation is not in accordance with byte ordering of the target architecture.

In a further embodiment, the first representation includes a first unit of storage representing literal data and the data translation script includes a translation instruction corresponding to the first unit of storage and descriptive of an endian tranformation of the literal data.

In yet a further embodiment, the first representation further includes a second unit of storage representing pointer data and the data translation script further includes a relocation expression corresponding to the second unit of storage and descriptive of a transformation of the pointer data to an effective memory address.

In still yet a further embodiment, the relocation expression encodes a linear combination of terms including one or more terms selected from a set including a constant term, a data section address term, a function gate address term, and a translation time constant term. The translation time constant term, if any, evaluates to either a first value or a second value depending on whether the relocation expression is evaluated on a big-endian or a little-endian target architecture.

In another embodiment, an object code structure encoded in computer readable media includes a code section; a data section associated with the code section and first and second first data translation scripts. The data section includes first and second representations of data, each organized as units of storage. The first representation includes first and second units of storage and the second representation includes third and fourth units of storage. The first and third units of storage represent corresponding big-endian and little-endian representations of literal data and the second and fourth units of storage represent corresponding representations of pointer data. The first data translation script is associated with the first representation and includes a first relocation expression which corresponds to the second unit of storage and which is descriptive of a transformation of pointer data represented therein to an effective memory address. The second data translation script is associated with the second representation and includes a second relocation expression which corresponds to the fourth unit of storage and which is descriptive of a transformation of pointer data represented therein to an effective memory address.

In still yet another embodiment, a method for translating an architecture-independent program implementation into native code for a target architecture includes a data section reading step, a data translation script reading step, and a byte order reversing step. The data section is read from computer readable media and includes a representation of data organized as units of storage. The data translation script is also read from computer readable media. The data translation script is associated with the representation and has a sequence of instructions corresponding to the units of storage. During the byte order reversing step, byte ordering of literal data represented in a first one of the units of storage is reversed in accordance with the corresponding instruction from the data translation script when the literal data is not in accordance with byte ordering of the target architecture.

In a further embodiment, the data translation script reading step includes reading a translation instruction which corresponds to a first one of the units of storage and which is descriptive of an endian transformation of literal data represented therein. In another further embodiment, the data translation script reading step includes reading a relocation expression which corresponds to a second one of the units of storage and which is descriptive of a transformation of pointer data to an effective memory address represented therein.

In a further embodiment the method further includes relocating pointer data encoded within the second one of the units of storage in accordance with the corresponding relocation expression from the data translation script.

In yet a further embodiment, the pointer relocating step includes selectively supplying a byte offset term as part of the relocation expression. When the representation is in little-endian format, a non-zero byte offset term is supplied as part of the relocation expression if the target architecture is big-endian and a zero byte offset term is supplied as part of the relocation expression if the target architecture is little-endian. When the representation is in big-endian format, a non-zero byte offset term is supplied as part of the relocation expression if the target architecture is little-endian and a zero byte offset term is supplied as part of the relocation expression if the target architecture is big-endian.

In still yet another embodiment, a system for supplying an architecture-independent program implementation includes an object code structure encoded in computer readable media and a translator executable on a target architecture. The object code structure includes a code section, a data section associated with the code section and which includes a first representation of data organized as units of storage, and a data translation script associated with the first representation. The data translation script includes an instruction sequence for reversing byte ordering within the units of storage when the first representation is not in accordance with byte ordering of a target architecture. The translator is executable on the target architecture for reading the first representation and the data translation script. The translator reverses byte ordering of the literal data represented in first ones of the units of storage in accordance with corresponding instructions from the data translation script when literal data so represented is not in accordance with byte ordering of the target architecture.

BRIEF DESCRIPTION OF THE DRAWINGS

The present invention may be better understood, and its numerous objects, features, and advantages made apparent to those skilled in the art by referencing the accompanying drawings.

FIG. 1A is a pictorial illustration of the big-endian byte ordering of a 32-bit word.

FIG. 1B is a pictorial illustration of the little-endian byte ordering of a 32-bit word.

FIG. 2 is a functional block diagram of a system for providing a portable machine architecture in accordance with the teachings of the present invention.

FIG. 3 is a data structure diagram depicting the organization of a Multicode segment for representing object code and data for a machine independent program representation in accordance with the teachings of the present invention.

FIG. 4 is a pictorial illustration of variable length bnum encodings of integer data in accordance with the teachings of the present invention.

FIG. 5 is a data structure diagram depicting the functional interrelationship between function descriptors and object code representations in a Multicode segment constructed in accordance with the teachings of the present invention.

FIG. 6 is a data structure diagram depicting the functional interrelationships between multiple representations of section data in a global data specification for a Multicode segment constructed in accordance with the teachings of the present invention.

FIG. 7 is a pictorial illustration of multiple encoding formats for data translation directives and special directives of a data translation script in accordance with the teachings of the present invention.

FIG. 8A is pictorial illustration of the structure of a relocation expression, including multiple relterms, constructed in accordance with the teachings of the present invention.

FIG. 8B is a pictorial illustration of multiple encoding formats for relterms of a relocation expression constructed in accordance with the teachings of the present invention.

FIG. 9A is a pictorial illustration of an Intercode instruction in accordance with the teachings of the present invention.

FIG. 9B is a pictorial illustration of literal operand encodings for Intercode instructions in accordance with the teachings of the present invention.

DETAILED DESCRIPTION OF THE INVENTION

The following sets forth a detailed description of the best contemplated mode for carrying out the invention. The description is indented to be illustrative of the invention and should not be taken to be limiting.

The Intercode.TM. object code format is an architecture-independent object code format, with an emphasis on space efficiency, designed for use in lightweight portable computers. Though the Intercode object code format is well suited to the power and memory limitations of portable, handheld computers and personal digital assistants (PDAs), architecture-independent character of Intercode object code make it suitable for a wide variety of architecture-independent distribution media applications. A program compiled into Intercode object code can be executed on an extensible set of modem 32-bit microprocessors. Advantageously, such Intercode programs can be placed in ROM and then dynamically translated by an Intercode translator into native code. Almost all C and C++ programs can be compiled into Intercode object code without changes, although the Intercode object code format is not C-specific--other procedural languages can also be supported.

An Intercode translator can be run in one of two modes: batch or caching. Batch mode provides the best performance--typically only 2% slower than optimized native MIPS gcc (Gnu C compiler) output for a 14000-line C++ program--but requires that the entire translated program fit in memory. Caching mode has fixed RAM requirements--typically about 50K for a code cache--but incurs at least a 30% speed penalty for compute-bound code. In terms of space, Intercode object code is about 25% smaller than fully optimized, nonrelocatable native MIPS code.

Containers for functions represented in Intercode object code, i.e., Intercode functions, are called Multicode.TM. segments. A Multicode segment contains code and static data, both of which can be represented in a variety of different formats. Code can be in any mix of Intercode object code and native object code formats on a function-by-function level of granularity. Thus, performance-critical sections of a program can be optimized for particular target architectures and provided as native code, while Intercode object code is also provided, thereby preserving the ability to run the program on any architecture that provides an Intercode translator. A Multicode segment can also serve a container for compressed native code in situations where architecture neutrality is not important.

FIG. 2 depicts a system 200 for providing an architecture-independent program implementation using Multicode segments and Intercode function representations. System 200 accepts (as an input) application source code 240 and supplies (as a run-time output) native code for execution on a series of target processors (231, 232, and 233). System 200 includes a series of compilers 203, 204, and 205 for compiling object code from source code 240 and a series of run-time translators 220a, 220b, and 220c for supplying native code for respective target processors (231, 232, and 233). Multicode segment 210 is a compiled intermediate object code format which is supplied to each target processor for run-time translation to an object code format native to the target processor. Individual functions and procedures may be represented as compiled Intercode representations, as compiled code representations native to a target processor (i.e., native code), or as both Intercode and native code representations. Compiled native code representations are directly executed (i.e., no translations is required), while compiled Intercode representations are translated at run-time into native code for execution on the target processor.

FIG. 2 depicts a Multicode segment 210 including three object code modules corresponding to function.sub.1 241. The first module, which is the object code output of the C language compiler for target processor.sub.1 (native compiler 203), is native code module 212. The second, which is the object code output of the C language compiler for target processor.sub.2 (native compiler 204), is native code module 214. The third, which is the object code output of Intercode compiler 205, is an Intercode module 216. Multicode segment 210 also includes an Intercode module 218 corresponding to function.sub.2 242. Intercode module 218 is the object code output of the Intercode compiler's (205) compilation of C++ function.sub.2. The structure of Multicode segments such as Multicode segment 210 and of Intercode modules such as Intercode modules 216 and 218 is described below in greater detail.

Illustratively, system 200 provides each of the three target processors (i.e., target processors 231, 232, and 233) with a copy of Multicode segment 210. Each target processor receives the same Multicode segment as the others on, in, or as part of any suitable distribution media, such as ROM, disc media, CD-ROM, non-volatile RAM, PCMCIA card, etc. Other suitable distribution media will be apparent to those of ordinary skill in the art and provision of a Multicode segment such as 210 to a target processor such as 231, 232, or 233 is by any such suitable medium.

In general, object code native to a target processor can be directly executed on that target processor, or alternatively, an Intercode module can be translated to native code for execution. Since Multicode segment 210 includes a native code representation 212 corresponding to function.sub.1 that native code representation (212) is directly executed on target processor.sub.1 231 when function.sub.1 is called or invoked. In contrast, Multicode segment 210 does not include an object code representation of function.sub.2 which is native to target processor.sub.1. As a result, the Intercode module 218 of Multicode segment 210 which corresponds to function.sub.2 must be translated to native code by Intercode translator 220a before execution on processor.sub.1. Similarly, Intercode module 218 must be translated to native code by Intercode translator 220b before execution on processor.sub.2. While Multicode segment 210 includes native code representations of function.sub.1 for processor.sub.1 and processor.sub.2, there is no corresponding native code module for processor.sub.3. As a result, both function.sub.1 and function.sub.2 must be translated by Intercode translator 220c before execution on processor.

In FIGS. 3-8, software structures and encodings are shown which implement Multicode segments. These structures and encodings establish functional interrelationships between a Multicode segment and its component architecture-independent and architecture-dependent representations of code and data. In addition, these structures and encodings establish functional interrelationships between an Intercode translator and the component Intercode object code and data representations of the Multicode segment.

Multicode format is an extensible format for laying out segments of code and data. A program is represented in one or more Multicode segments, such as Multicode segment 210, which, in turn, include Intercode representations of code and data. These Multicode segments can themselves be represented in a suitable container such as a binary data file. Dynamically linked libraries, object representations such as Magic Cap.TM. objects, etc. are also suitable containers. An Intercode translator (e.g., 220a, 220b, or 220c) does not concern itself with how the Multicode segments are found and instead uses the segments which are made available to it. Code in a Multicode segment can refer to external functions and data by name, and the Intercode translator dynamically links these references to other segments or system libraries.

Multicode Segments

Referring now to FIG. 3, a typical Multicode segment, illustratively Multicode segment 300, includes a segment header 310, a function list 320, function descriptors (e.g., function descriptors 331, 332, 333, and 334), and a global data specification 340. Segment header 310 includes of an attribute count 311 and a set of attributes. In a presently preferred embodiment, each attribute includes an attribute tag (e.g., 312) and a corresponding data word (e.g., 313), although alternate representations are also suitable. If representation of a particular attribute requires more than 32 bits of data, the data word is a pointer to the attribute data Some attributes are required, while others are optional. Data are represented in big-endian format (most significant byte first) unless otherwise specified, and pointers are actually offsets relative to the beginning of the segment, thus making the segment relocatable. Except for the segment header 310, which, in a presently preferred embodiment, appears at the beginning of the segment, all other components of Multicode segment 300 can appear in an arbitrary order. Alternative embodiments may further relax, or additionally constrain, the ordering and/or placement of components in a Multicode segment.

In the embodiment of FIG. 3, segment attribute 313 points to function list 320, which, in a presently preferred embodiment, is structured as a count followed by an array of pointers to function descriptors. A function and its associated function descriptor within a Multicode segment are assigned unique, consecutively assigned virtual function numbers starting with one (1), although alternative conventions would also be suitable. All persistent outside references to functions within the segment use the virtual function numbers rather than direct offsets into the segment. Other segment attributes, illustratively those represented by 314, 340, and 351, describe version information, the global data sections, and entry gates that are needed for code that explicitly takes the address of a function. Still other segment attributes may be defined in a given Multicode segment to specify the segment's symbol table, external linkages, and debugging information.

Notation and Conventions

The following terminology is used throughout this specification to refer to units of storage:

A byte is 8 bits.

A halfword or short is 16 bits.

A word or long is 32 bits.

A doubleword is 64 bits. Plain numbers are decimal. Hexadecimal numbers are preceded by a dollar sign ($), and binary numbers are preceded by a percent sign (%). Leading zeros do not indicate octal numbers in this specification. This terminology is provided solely for the purpose of descriptive consistency, and is not meant as a limitation. Those of ordinary skill in the art will recognize that designs and implementations based on alternate unit of storage definitions are within the spirit and scope of the present invention.

All numbers are stored in big-endian format unless specified otherwise. The relative order of many data structures is undefined, but they should be stored to satisfy the natural alignment requirements of their most restrictive component. In other words, all structures should be aligned on a word boundary, and structures containing a double or a doubleword should be aligned on a doubleword boundary. Components should also be properly aligned within structures.

To optimize for small values, some integers are stored in the bnum format, which includes of one or more bytes as shown in FIG. 4. A bnum is a variable-length representation of integer data. Representations 410, 420, 430, 440, 450, and 460 provide increasing ranges of representable integer values. For example, in bnum representation 410, a single byte encodes values between 0 and 239, whereas in bnum representation 460, a first byte encodes the range (i.e., -2.sup.63 . . . 2.sup.63 -1) and eight subsequent words encode the integer value. Representations 420, 430, 440, and 450 encode intermediate ranges of integer values, providing a gradation of alternatives providing increasing range, albeit with increasing space requirements.

Multicode Segment Attributes

Referring again to FIG. 3, segment header 310 is located at the beginning of a Multicode segment and, in a presently preferred embodiment, has the following structure:

    ______________________________________
    Offset Type     Value
    ______________________________________
    0      short    Number n of segment attributes
    2      n .times. short
                    Segment attribute tags
    2 + 2n padding  2 bytes of padding to align to a word boundary if
                    n is even
    4 + 4[n/2]
           n .times. long
                    Corresponding segment attribute data words
    ______________________________________

    ______________________________________
    Version
    Tag: $0001
    Data: Segment-relative pointer to data below (which should be
    word-aligned):
    Offset
          Type    Value
    ______________________________________
    0     half    Minimum version of translator required to process this
                  segment
    2     half    Version of this segment
    ______________________________________

    ______________________________________
    FunctionList
    Tag: $0002
    Data: Segment-relative pointer to data below (which should be
    word-aligned):
    Offset   Type       Value
    ______________________________________
    0        long       Number m of function descriptors
    4        m .times. long
                        Pointers to function descriptors
    ______________________________________

    ______________________________________
    FunctionNames
    Tag: $0003
    Data: Segment-relative pointer to data below (which should be
    byte-aligned):
           Type          Value
    ______________________________________
           name list     See below
           name list     See below
           . . .
           name list     See below
           byte          0
    ______________________________________

    ______________________________________
    Type         Value
    ______________________________________
    bnum         Initial function number k
    bnum         Number of functions in range m
    bnum         Length n.sub.k of name of function k
    n.sub.k characters
                 Name of function k
    bnum         Length n.sub.k+1 of name of function k + 1
    n.sub.k+1 characters
                 Name of function k + 1
    . . .
    bnum         Length n.sub.k+m-1 of name of function k + m - 1
    n.sub.k+m-1 characters
                 Name of function k + m - 1
    ______________________________________
    MainFunction
    Tag: $0004
    Data: Segment-relative pointer to data below (which should be
    word-aligned):
    Offset    Type     Value
    ______________________________________
    0         long     Number of main function in segment
    ______________________________________

    ______________________________________
    ConstructorList
    Tag: $0005
    Data: Segment-relative pointer to data below (which should be
    word-aligned):
    Offset   Type       Value
    ______________________________________
    0        long       Number m of constructor numbers
    4        m .times. long
                        Function numbers of constructors
    ______________________________________

    ______________________________________
    DestructorList
    Tag: $0006
    Data: Segment-relative pointer to data below (which should be
    word-aligned):
    Offset   Type       Value
    ______________________________________
    0        long       Number m of destructor numbers
    4        m .times. long
                        Function numbers of destructors
    ______________________________________

    ______________________________________
    EntryGateList
    Tag: $000B
    Data: Segment-relative pointer to data below (which need only start
    byte-aligned):
    Type    Value
    ______________________________________
    bnum    Number n of entry gates
    byte    Number k of bits in a function number; must be 0, 8, 16, or
            32
            Optional padding to align to a k-bit boundary
    n .times. k bits
            Table of function numbers indexed by entry gate numbers
            0 . . . n - 1
    ______________________________________

    ______________________________________
    Type         Value
    ______________________________________
    bnum         Number n of function representations
    ______________________________________

    ______________________________________
    Type  Value
    ______________________________________
    bnum  Code type
    bnum  Flags
    bnum  Offset from function descriptor to function header or entry
    ______________________________________
          point

    ______________________________________
    Code Type        Architecture
    ______________________________________
    $00              Reserved
    $01              External reference
    $02              Inter-segment reference
    $03-$0F          Reserved
    * $10            Intercode
    $18-$1F          Reserved
    * $20            MIPS Rxx00
    * $28            Motorola 680x0
    * $30            PowerPC
    * $38            80x86
    ______________________________________

    ______________________________________
    External reference variants (code type $01):
    0      Must be set for current external reference format
    Inter-segment reference variants (code type $02):
    0      Must be set for current inter-segment reference format
    Intercode variants (code types $10-$17):
    0      Must be set for current Intercode format
    MIPS R .times..times. 00 variants (code types $20-$27):
    0      R2000
    1      R3000
    3      R4000
    5      Dino
    6      Dino with load interlocks
    Motorola 680 .times. 0 variants (code types $28-$2F):
    0      68000
    1      68020 (with 68881/2 for code types $29, $2B, $2D, $2F)
    2      68040
    3      68060
    6      68349
    PowerPC variants (code types $30-$37):
    0      601
    1      603
    2      604
    3      620
    6      821
    80 .times. 86 variants (code types $38-$3F):
    0      8086
    1      80286 (with 80287 for code types $39, $3B, $3D, $3F)
    2      80386 (with 80387 for code types $39, $3B, $3D, $3F)
    3      80486
    4      Pentium
    ______________________________________

    ______________________________________
    Type               Value
    ______________________________________
    bnum               Length n of name
    n characters       Name
    ______________________________________

    ______________________________________
    Type          Value
    ______________________________________
    bnum          Target segment number
    bnum          Function number in target segment
    ______________________________________

    ______________________________________
    Type            Value
    ______________________________________
    bnum            Number n of data sections
    ______________________________________

    ______________________________________
    Type    Value
    ______________________________________
    bnum    Number of representations
    byte    Representation kind
    bnum    Offset from representation kind byte to next representation
    . . .   Representation information
    byte    Representation kind
    bnum    Offset from representation kind byte to next representation
    . . .   Representation information
    . . .
    byte    Representation kind
    bnum    Offset from representation kind byte to next section
    . . .   Representation information
    ______________________________________

    ______________________________________
    UninitData
    Kind: $01
    Additional representation information:
    Type       Value
    ______________________________________
    byte       Base-2 logarithm of required data alignment
    bnum       Data length
    ______________________________________

    ______________________________________
    ZeroData
    Kind: $02
    Additional representation information:
    Type       Value
    ______________________________________
    byte       Base-2 logarithm of required data alignment
    bnum       Data length
    ______________________________________

    ______________________________________
    ExternalData
    Kind: $03
    Additional representation information:
            Type           Value
    ______________________________________
            repskip bytes  Name
    ______________________________________

    ______________________________________
    InitData
    Kind: $04
    Additional representation information:
    Type    Value
    ______________________________________
    byte    Base-2 logarithm of required data alignment
    bnum    Data length
    bnum    Representation flags
    bnum    Offset from representation kind byte to section data
    bnum    Offset from representation kind byte to data translation
            script or 0 if none
    ______________________________________

    ______________________________________
    $01   Set if data is in the big-endian format
    $02   Set if data is in the little-endian format
    $04   Set if data translation script provides byte ordering information
    $08   Set if data translation script contains relocations
    $10   Set if section is read-only
    ______________________________________

    ______________________________________
    CompressedData
    Kind: $05
    Additional representation information:
    Type Value
    ______________________________________
    byte Base-2 logarithm of required data alignment
    bnum Data length
    bnum Representation flags
    bnum Offset from representation kind byte to compressed section data
    bnum Offset from representation kind byte to data translation script
         or 0 if none
    ______________________________________

    ______________________________________
    $0             End translation
    $1             Endblock
    $2*            Relocate byte (8 bits)
    $3*            Relocate halfword (16 bits)
    $4*            Relocate word (32 bits)
    $5*            Relocate doubleword (64 bits)
    $6*            Relocate quadword (128 bits)
    ______________________________________

    ______________________________________
    $0      Begin block
    $1*     Relocate word (32 bits)
    $2      Translate byte (8 bits)
    $3      Translate halfword (16 bits)
    $4      Translate word (32 bits)
    $5      Translate doubleword (64 bits)
    $6      Translate quadword (128 bits)
    $8      Translate single-precision floating point (32 bits)
    $9      Translate double-precision floating point (64 bits)
    $A      Translate extended-precision floating point (80 bits)
    $B      Translate quadruple-precision floating point (128
    ______________________________________
            bits)

    ______________________________________
              struct example.sub.-- struct {
                char aaaa[4];
                int bbbb;
              } example[128];
    ______________________________________

    ______________________________________
    %0000  arg
    %0001  arg + sec(1)
    %0010  arg + sec(2)
    %0011  arg + sec(3)
    %0100  arg + sec(4)
    %0101  arg + sec(5)
    %0110  arg + sec(6)
    %0111  arg + sec(7)
    %1000  sec(arg)
    %1001  gate(arg)
    %1010  staticrel(arg)
    %1011  reserved
    %1100  reserved
    %1101  reserved
    %1110  reserved
    %1111  (scaling factor relterm) multiply value of next relterm by
    ______________________________________
           arg-1

    ______________________________________
    $07          MOVE #imr,Wd    Wd.rarw.imr
    ______________________________________

    ______________________________________
              #include <stdio.h>
              int main()
               {
               printf("Hello, world!.backslash.n");
               return 0;
               }
    ______________________________________

    ______________________________________
    .SYSINCLUDE "Intersd.h"
    .MAIN  main
    ;Compiled by GCC cygnus-2.6.0-940917.
    .RODATA
    .ALIGN        4
    LC..0:
    .ASCII "Hello, world!.backslash.n"
    .BYTE         0
    .CODE
    .GLOBL        main
    .FUNC         main
    .WREG         PWO.about.
    .WREG         UWO.about.
    .WREG         VWO.about.
    .WRES         VWO
    .SIG          sig1
    .AARG         PW0
    .VARARG
    .WRES         UWO
    .START
    MOVE          #LC..0,PW0
    CALLI         sig1,#-49
    MOVE          #0,VW0
    END
    .END
    ______________________________________

    ______________________________________
    Disassembling "hello.x".
    ======================================================
    ===
    $00000020: Version attribute
    Required translator version $0174
    Segment version $0174
    ======================================================
    ===
    $00000024: FunctionList attribute
    1 functions
    $0000002C: Function 1 `main`
    001 representations
    Representation 1:
    Code type $10 (Pure integer Intercode)
    Code variant flags $01 (standard)
    Code offset $04
    4 fields
    InstCount: $03 (3 instructions)
    RegInfo: $0A
            4-bit register numbers, 3 registers, 3 popular
            PW1 : Parameter Word, dead during fpop,
    dead during double
            UW2 : Result Word, dead during fpop, dead
    during double
            TW3 : Temporary Word, dead during fpop,
    dead during double
            CallSigs: $12
            1-bit signatures, 1 signatures, 01 calls, 0 CALLIs
            Signature 1:
              01 arguments:
               Address value in PW1
              01 return values:
               Word value in UW2
              Last 01 arguments are varargs.
            ArgInfo: $0F
              0 arguments:
              01 return values:
               Word value in TW3
            Code: $1A
               MOVE  #(sec4),PW1
                               ;$07 %0001
    %111.sub.-- 0.sub.-- 000.sub.-- 0100
               CALLI S1, #-049 ;$9C %010.sub.-- $CF %1
               MOVE  #0,TW3    ;$04 %0011
               END             ;$00
    ======================================================
    ===
    $00000052: FunctionNames attribute
    Starting number: 001, count: 001
    Function 1: $04 "main"
    Starting number: 000
    ======================================================
    ===
    $0000005C: MainFunction attribute
    Main function 1 `main`
    ======================================================
    ===
    $00000060: GlobalData attribute
    004 data sections
    $00000061: Section 1
    000 data representations
    $00000062: Section 2
    000 data representations
    $00000063: Section 3
    000 data representations
    $00000064: Section 4
    001 data representations
    $00000065: InitData representation, 025 bytes of
    specification
    2 2-byte alignment
    015 bytes
    Flags: $15 (big-endian, endian translations, read-only)
    Data offset: 007
    Translation script offset: 022
    Data:
            $0: $48 $65 $6C $6C $6F $2C $20 $77
             $6F $72 $6C $64 $21 $0A $00
                             ;`Hello, world!..`
    Data translation script:
            $D2.sub.-- 0F
                   repeat 15 byte
            $00    end
    End
    ______________________________________

    __________________________________________________________________________
    0000
        0005      Five segrnent attributes
    0002
        0001      Version attribute tag
    0004
        0002      FunctionList attribute tag
    0006
        0003      FunctionNames attribute tag (optional; for debugging)
    0008
        0004      MainFunction attribute tag
    000A
        0008      GlobalData attribute tag
    000C
        00000020  Version attribute offset
    0010
        00000024  FunctionList attribute offset
    0014
        00000052  FunctionNames attribute offset (optional; for
                  debugging)
    0018
        0000005C  MainFunction attribute offset
    001C
        00000060  GlobalData attribute offset
    0020
        0174      Version: Minimum version off translator required
    0022
        0174      Version of this segment
    0024
        00000001  FunctionList: One function descriptor
    0028
        0000002C  Function 1 offset
    002C
        01        Function 1: One function representation
    002D
        10        Intercode code type
    002E
        01        Flags
    002F
        04        Offset from function descriptor to function header
    0030
        04        Function 1 header: Four header fields
    0031
        1A        Offset to Intercode instructions
    0032
        03 03     InstCount: 3 Intercode instructions
    0034
        08 0A     RegInfo: offset to register information field data
    0036
        0A 12     CallSigs: offset to call information field data
    0038
        0B 0F     ArgInfo: offset to argument and return value field data
    003A
        219A31984C
                  Register information field data
    003F
        108930    Argument and return value information field data
    0042
        0D08850CD1249080
                  Call information field data
    004A
        071E0938B3E08600
                  Intercode instructions
    0052
        01        FunctionNames: Initial function number
    0053
        01        One function in range
    0054
        04        Length of function name
    0055
        6D 61 69 6E
                  Function name
    0059
        00        End of list marker
    005A
        0000
    005C
        00000001  MainFunction: Number of main function in segment
    0060
        04        GlobalData: Four data sections
    0061
        00        Section 1: None
    0062
        00        Section 2: None
    0063
        00        Section 3: None
    0064
        01        Section 4: One representation
    0065
        04        InitData representation kind
    0066
        19        Offset from representation kind byte to next
                  representation
    0067
        02        Base-2 logarithm of required data alignment
    0068
        0F        Data length
    0069
        15        Flags: big-endian, has translation script, read-only
    006A
        07        Offset from representation kind byte to section data
    006B
        16        Offset from representation kind byte to data translation
                  script
    006C
        48 65 6C 6C
                  Data . . .
    0070
        6F 2C 20 77
                  . . . data . . .
    0074
        6F 72 6C 64
                  . . . data . . .
    0078
        21 0A 00  . . . data
    007B
        D2 0F 00  Data translation script
    __________________________________________________________________________

    __________________________________________________________________________
    1000C5A4:
          $27BDFFE8
                addiu
                   sp, sp, -24
                          ;Allocate stack frame
    1000C5A8:
          $AFBF0014
                sw ra, 20(sp)
                          ;Save return address
    1000C5AC:
          $3C041000
                lui
                   a0, 0x1000
                          ;Get the address of "Hello, world!.backslash.n"
    1000C5B0:
          $3484C48C
                ori
                   a0, a0, 0xc48c
    1000C5B4:
          $0C003147
                jal
                   0x1000c51c
                          ;CALLI(next instruction is in delay
    slot)
    1000C5B8:
          $2401FFCF
                li at, -49
                          ;Intrinsic number of printf
    1000C5BC:
          $34080000
                li t0, 0  ;Set return value to zero
    1000C5C0:
          $01001025
                move
                   v0, t0
    1000C5C4:
          $8FBF0014
                lw ra, 20(sp)
                          ;Restore return address
    1000C5C8:
          $00000000
                nop       ;(load delays lot)
    1000C5CC:
          $03E00008
                jr ra     ;Return(next instruction is in delay
    slot)
    1000C5D0:
          $27BD0018
                addiu
                   sp, sp, 24
                          ;Deallocate stack frame
    __________________________________________________________________________

    __________________________________________________________________________
    1000C6AC:
          $27BDFFE0
                addiu
                   sp, sp, -32
                          ;Allocate stack frame
    1000C6B0:
          $AFBF001C
                sw ra, 28(sp)
                          ;Save return address
    1000C6B4:
          $AFBE0018
                sw s8, 24(sp)
                          ;Save registers
    1000C6B8:
          $AFB70014
                sw s7, 20(sp)
    1000C6BC:
          $3C1F1000
                lui
                   ra, 0x1000
                          ;Get address of return gate
    1000C6C0:
          $37FFCA88
                ori
                   ra, ra, 0xcaB8
    1000C6C4:
          $341E0002
                li s8, 2  ;Get run-time function unique ID
    1000C6C8:
          $3C041000
                lui
                   a0, 0x1000
                          ;Get the address of "Hello,
                          world!.backslash.n"
    1000C6CC:
          $3484C48C
                ori
                   a0, a0, 0xc48c
    1000C6D0:
          $2401FFCF
                li at, -49
                          ;Intrinsic number of printf
    1000C6D4:
          $08003131
                j  0x1000c4c4
                          ;CALLI(next instruction is in delay
    slot)
    1000C6D8:
          $3417005C
                li s7, 92 ;Offset in function to which to
                          return
    1000C6DC:
          $34080000
                li t0, 0  ;Set return value to zero
    1000C6E0:
          $01001025
                move
                   v0, t0
    1000C6E4:
          $8FBF001C
                lw ra, 28 (sp)
                          ;Restore return address
    1000C6E8:
          $8FBE0018
                lw s8, 24 (sp)
                          ;Restore registers
    1000C6EC:
          $8FB70014
                lw s7, 20 (sp)
    1000C6F0:
          $03E00008
                jr ra     ;Return (next instruction is in delay
                          slot)
    1000C6F4:
          $27BD0020
                addiu
                   sp, sp, 32
                          ;Deallocate stack frame
    __________________________________________________________________________

• Inventors
  Horwat, Waldemar;
• Assignee
  General Magic, Inc. (Sunnyvale, CA)
• Published
  Feb-1-2000
• Current US Classes:
  717/147
  717/154
  717/159
• Application #
  692357
• International Classes
  G06F 012/10
• Field of Search
  395/705 395/500 395/707 395/898 395/380 395/200.76
• Examiner
  Trammell; James P.
• Agent
  Skjerven, Morrill, MacPherson, Franklin & Friel LLP.
• US Patent References:
  5339434
  5550987
  5574923
  5604905
  5664189
  5701423
  5701483