Address simplification by binary transformation

A method for optimizing executable code includes identifying a plurality of instructions in the executable code matching a predetermined instruction pattern, assessing whether the binary number conforms to a predetermined bit pattern, and transforming the plurality of instructions into transformed instructions when the binary number conforms to the bit pattern.

BACKGROUND

Converting source code into executable code is a two step process. In a first step, the source code is compiled into what is known as an object file. In a second step, the object file is processed by a linker which may combine the object file with other objects to generate the final executable file.

The linker will resolve references to undefined symbols by finding which other object defines a symbol in question, and replacing placeholders with the symbol's address. Since a compiler generally does not know where an object will reside in the program's address space, it assumes a fixed base location (for example, zero). The linker therefore arranges the objects in a program's address space by relocating code provided by each object file that assumes a specific base address to another base. Relocating machine code may involve re-targeting of absolute jumps, loads and stores. Since the compiler does not know what address it will ultimately need to load at the time of compiling, many compilers will assume a maximum address size requiring 64 bits unless explicitly told otherwise by the programmer/user. Other compilers may assume a different maximum size, depending on the processor architecture.

In reduced instruction set computing (RISC) processors, a 32 bit machine-language instruction may include a certain number of bits of a constant value for use as data. So long as the constant value can be expressed in the number of data bits made available by the instruction format, considerable time may be saved by having the number incorporated into the instruction itself. In particular, this avoids having to load the numbers from memory or registers. However, larger numbers require multiple instructions to load. In this case, a number is segmented into multiple parts and each part is loaded separately.

In the case where the constant value to be loaded is an address, the compiler may generate code that assumes a larger address then is actually eventually assigned by the linker. Thus, additional unnecessary instructions are incorporated into the final code which adversely affects the program size and speed of execution.

There is a continuing need to improve the efficiency and speed of execution of computer software. It would therefore be desirable to develop a system and method for mitigating the inefficiencies identified above.

SUMMARY

Broadly speaking, the present invention fills these needs by providing a system and method for address simplification by binary transformation.

It should be appreciated that the present invention can be implemented in numerous ways, including as a process, an apparatus, a system, a device, or a method. Several inventive embodiments of the present invention are described below.

In one embodiment, a method provides for optimizing executable code. The method includes identifying a plurality of instructions in the executable code matching a predetermined instruction pattern, assessing whether it is possible to form the binary number with fewer instructions than a number of instructions in the instruction pattern, and transforming the plurality of instructions into transformed instructions when the binary number can be loaded in fewer instructions than the number of instructions in the instruction pattern.

In another embodiment, a machine readable medium has program code embodied therein configured to optimize executable code. The machine readable medium comprises machine readable code for identifying a plurality of instructions in the executable code matching a predetermined instruction pattern, machine readable code for assessing whether it is possible to form the binary number with fewer instructions than a number of instructions in the instruction pattern, and machine readable code for transforming the plurality of instructions into transformed instructions when the binary number can be loaded in fewer instructions than the number of instructions in the instruction pattern.

In yet another embodiment, a method provides for optimizing executable code generated by a compiler. The method comprises identifying an address loading instruction pattern generated by the compiler, searching the executable code for existing instructions matching the address loading instruction pattern, determining whether the address can be loaded in fewer instructions than the existing instructions, and replacing the existing instructions with substitute instructions when the address can be loaded in fewer instructions than the existing instructions.

DETAILED DESCRIPTION

FIG. 1presents an exemplary flow diagram100depicting a process and systems for creating an optimized executable code from source code. Source code102is developed by a user/programmer in a high-level language such as C. This is input into a compiler104which generates an object file106which may be combined with other objects110by linker108to generate executable code112. Executable code112is then taken as an input file into binary transformation processor114. Binary transformation processor114processes the executable file112searching for inefficient handling of low addresses as will be described hereinafter, and outputs smaller, more efficient, optimized executable code116.

FIG. 2shows an exemplary 64 bit word120segmented into four segments identified as LO (“low”), LM (“low-middle”), HM (“high-middle”), and HH (“high-high”). LO is the least significant 10 bits of the 64 bit word, which includes bits0to9. LM is the “low middle” and comprises the next 22 bits, or bits10to31. Segment HM comprises bits32to41and segment HH (“high-high”) comprises bits42to63. An address that fits in the least significant 34 bits is identified by left-handed hatching. The 34 bit address uses all of segments LO and LM, and the least significant 2 bits of segment HM. Thus,FIG. 2depicts a bit pattern wherein the high 30 bits are zero and the remaining bits are not defined.

FIG. 3shows an exemplary instruction pattern130generated by the compiler for loading the address into a register. When referencing the executable file, binary instructions are identified herein by their assembly language equivalents. Instruction1“sethi %hh(addr), %r1” causes segment HH to be loaded into bits10-31of register r1. The sethi instruction also clears the bottom 10 bits of the identified register. Instruction2uses an “or” operator to combine segment HM with the contents of register r1, filling the bottom 32 bits of target register r2. Instruction3shifts the contents of register r232 bits to the left and places the result into register r5. Instruction4uses the “sethi” instruction again to load segment LM into bits10-21of register3. Instruction5combines the contents of registers r5and r3and loads the result into target register r4. Finally, instruction6combines the contents of register r4and segment LO providing a result in a load, store, or add statement (ld/st/add).

It will be understood by those of skill in the art that the actual registers may vary as well as the order in which the instructions are made. For example, the instructions could have been instructions1,2,4,3,5,6, and with slight modification of the instruction registers, other orderings are possible. Instruction patterns that may be operated upon can be identified by analyzing the compiler operation and/or code.

It should be noted that the step of loading segment HH is wasted when the segment contains all zeros, and furthermore that most of segment HM contains no useful data. Using available instructions for segmenting a 34 bit constant value, the same 34 bit value can be provided in as little as three instructions.

FIG. 4shows an instruction pattern transformation140comprising a series of three instructions. Transformation140provides the equivalent result of the six instructions ofFIG. 3when the constant value loaded into the register has 34 bits or fewer. The exemplary instruction pattern shown byFIG. 3can therefore be simplified to that shown by the transformation shown byFIG. 4. Instruction1ofFIG. 4loads the most significant 22 bits of the constant value to be loaded into the register into bits10-21of target register3. Instruction2then shifts the contents of register3two bits to the left and sends the result to register4. Instruction3then combines the contents of register4with the least significant 12 bits of the constant value, and sends the result to register5.

FIGS. 3 and 4graphically show the transformation from six instructions to 3 when optimizing a binary executable file. Similar transformations may be made where the compiler generates a four-instruction pattern to load 44 bits of an address that is 34 bits or fewer. Table 1 shows an exemplary transformation of this type.

If the address value to be loaded can fit in 32 bits or fewer, then a two-instruction procedure exemplified by instructions1and2ofFIG. 3can be used to load the address. These examples are consistent with the architecture and instruction sets of Sun Microsystems™ SPARC™ processors. Thus, the optimization is capable of performing the operations for SPARC™ architecture as listed in Table 2. However, it will be noted that similar improvements can be made for optimizations of machine code for other processors in a similar manner.

It should be recognized that the address-loading instructions are not likely to be presented by the compiler one after the other, but instead with intervening instructions, jumps, and procedure calls.FIG. 5shows an exemplary directed acyclic graph (DAG)150depicting a series of interconnected program execution paths identified by arrows from the top of the figure to the bottom. Along the program execution paths are vertices152identifying various statements identified by the binary transformation procedure as being part of an address loading process.FIG. 6shows a DAG160after being processed by the binary transformation procedure. Shaded vertices162are deleted statements and the remaining vertices are replaced or modified statements from DAG150presented inFIG. 5.

FIG. 7shows a flowchart170depicting an exemplary procedure for performing the binary transformation. The exemplary procedure begins at start block172and flows to operation174wherein a next “sethi” instruction is located. If the end of the input file is reached, then the procedure flows to ending block186.

It will be understood that the transformation process will search the executable input file for the equivalent binary instruction for the assembly language instruction “sethi.” Thus, when referencing the executable file, binary instructions are identified herein by their assembly language equivalents.

If a “sethi” instruction is found, the procedure flows to operation176wherein the execution path is followed to search for instructions matching the six-instruction or four-instruction pattern using data-flow information available for the registers. The data-flow information is gathered by the binary transformation tool in the form of du-chains and ud-chains. This search may result in a data structure forming a DAG such as that exemplified inFIG. 5. Persons skilled in the art will understand how to generate such a diagram using data-flow information. In broad terms, after identifying the first instruction, it is read to determine the register defined by the first instruction. Then, the du-chain for that register is followed to identify second instructions (that uses that register). There may be more than one second instruction. Once all the second instructions are identified, then the ud-chains for every one of them are followed to identify other possible first instructions. This procedure is repeated until all instructions corresponding to the instruction pattern are identified and the DAG diagram is generated in memory.

After searching for instructions matching one of the patterns, the procedure flows to operation178wherein it is determined whether any instructions are found that match one of the two patterns. If no instructions matching the patterns are found, then the procedure flows back to operation174to seek the next “sethi” instruction. However, if instructions matching the instruction patterns is found, then the procedure flows to operation180.

In operation180, the binary number being loaded by the instructions is identified. The procedure then flows to operation182wherein it is determined whether the binary number matches a predetermined or pre-selected bit pattern that corresponds to a transformation. Each transformation will have a corresponding bit pattern associated with it to filter out binary numbers that the transformation cannot handle. For example, if the transformation can only handle numbers having 34 significant bits, then the corresponding bit pattern will look for binary numbers with 30 leading zeros, and any binary numbers having a 1 in the 30 most significant bits will be filtered out. Transformations may be ordered by hierarchy so that if more than one bit pattern matches the binary number, then the transformation having priority will be applied. Thus, for a binary number having 32 significant bits, the most significant 32 bits are zero, and the two instruction transformation is applied as mentioned above, and not the four instruction transformation used for binary numbers having 44 significant bits. If the binary number matches a bit pattern, then the procedure flows to operation184, otherwise it flows back to operation174to search for the next “sethi” instruction.

In another embodiment, operation182compares the actual number of bits being loaded with the number of bits necessary to hold the value, which is based on the number of leading zeros in the binary number. Table 2 above shows instances where this comparison yields a determination that unnecessary instructions are present. If unnecessary instructions are not present, then the procedure flows back to operation174to search for the next “sethi” instruction. However, if unnecessary instructions are present, the procedure will flow to operation184to apply the binary transformation and update the addresses affected thereby.

Operation184applies the binary transformation which may result in some instructions being deleted and other instructions being modified as discussed above with respect toFIGS. 2-6. Each time an instruction is deleted, all the instructions thereafter move up by one position which affects their absolute address and their position relative to previous instructions. Thus, the file is examined for jumps, procedure calls, etc. that may be affected by the relocation, and they are modified accordingly. After the binary transformation is complete, the procedure returns to operation174to search for the next “sethi” instruction.

Although optimizations described above relate to instances where fewer bits are needed then actually provided for by the compiler, optimizations may also be implemented using mathematic operators to generate an address in fewer instructions. For example, to generate the 64-bit value 0xffffffffffffffff, just one instruction is needed: “xnor %g0,0,%t1”. Similarly, if address values are very high, e.g., conforming to the bit pattern 0xffffffffxxxxxxxx signifying that the high 32 bits are all ones, just two instructions could be used for generating their values:

wherein YYYYYYYY represents bitwise complement of bits10-21of the addresses and ZZZ represents bitwise complement of bits0-9of the address. It should be noted that this aspect of the transformation is not limited to a particular algebraic simplification or a particular property, such as bit length, of the calculated binary number. As such, persons of skill in the art may envision many other such algebraic simplifications for optimizing address values corresponding to other bit patterns. Thus, it should be mentioned that a plurality of transformations may be provided, each corresponding to a particular bit pattern of the binary number, and the transformation selected to be applied will depend upon which particular bit pattern the binary number corresponds. If a particular binary number matches a plurality of bit patterns, then a preferred transformation based on a predetermined or selected hierarch of transformations may be applied.

It furthermore should be mentioned that it is possible to provide transformations that provide benefits other than reducing the number of instructions. For example, transformations may be made to address loading instructions for the purpose of reducing processor power draw and/or clock cycles.

Any of the operations described herein that form part of the invention are useful machine operations. The invention also relates to a device or an apparatus for performing these operations. The apparatus can be specially constructed for the required purpose, or the apparatus can be a general-purpose computer selectively activated or configured by a computer program stored in the computer. In particular, various general-purpose machines can be used with computer programs written in accordance with the teachings herein, or it may be more convenient to construct a more specialized apparatus to perform the required operations.

Embodiments of the present invention can be processed on a single computer, or using multiple computers or computer components which are interconnected. A computer, as used herein, shall include a standalone computer system having its own processor(s), its own memory, and its own storage, or a distributed computing system, which provides computer resources to a networked terminal. In some distributed computing systems, users of a computer system may actually be accessing component parts that are shared among a number of users. The users can therefore access a virtual computer over a network, which will appear to the user as a single computer customized and dedicated for a single user.