Browse Prior Art Database

Method to reduce code size in 64-bit architecture application code

IP.com Disclosure Number: IPCOM000008012D
Publication Date: 2002-May-10
Document File: 3 page(s) / 47K

Publishing Venue

The IP.com Prior Art Database

Abstract

Disclosed is a method to reduce code size in 64-bit architecture application code. Benefits include improved response time.

This text was extracted from a Microsoft Word document.
This is the abbreviated version, containing approximately 50% of the total text.

Method to reduce code size in 64-bit architecture application code

Disclosed is a method to reduce code size in 64-bit architecture application code. Benefits include improved response time.

General description

              The disclosed method provides an approach to decrease the size of generated application code from a compiler or translator. This algorithm can be implemented in any compiler as a post-pass phase as an addition to any other optimizations that the compiler might already have implemented. The algorithm enables the compiler to concentrate on minimizing the critical path while still providing a technique to generate smaller code than is conventionally produced.

              The major component of the method is the scheduling algorithm. If slack instructions (those instructions for which the compiler has freedom to choose in which cycle the instruction is placed) are selected carefully and re-schedule them, code size can be reduced. Studies have shown that fewer instructions in an instruction group generally cause more NOPs due to bundle packing and alignment. The disclosed algorithm attempts to move slack instructions from instruction groups with fewer instructions to instruction groups with more instructions.

Advantages

              Conventional 64-bit architecture compilers only attempt to minimize the critical path of the code sequence while disregarding how non-critical instructions are placed in the code stream. With the disclosed method, compilers can continue to optimize critical path processing without changes in existing optimization methods and also include a small post-pass that compacts code by approximately 5% without sacrificing critical path length.

              Compilers are able to generate smaller, and thus faster, more efficient code. The size of program files on storage media is approximately 5% smaller than conventional binaries, decreasing the size of ITLBs, reducing program load time, and generally making more efficient use of I-stream system resources.

Detailed description

              The disclosed algorithm (see Figure 1) applies to a scheduling block (a compiler-specific set of instructions that is considered as a unit for purposes of scheduling). Depending on the compiler, a scheduling block could be a basic block, a super block, or even an entire function. For each scheduling block, the algorithm calls Find_Slack_Instruction_and_Cycle_Slack(), where two topological sorts are used to find instructions on non-critical path (slack instructions) as well as compute their earliest schedulable cycle and latest schedulable cycle. The key idea of the algorithm is to reduce code size by intelligently choosing the best cycle for slack instructions within their slack range (the range of cycles they can be placed in without affecting the overall execution time of the scheduling block) such that the code size is reduced.

              This method assumes the existence of a compaction routine that takes a given a specific schedule (each instruction is mapped into a specific fixed...