There are two techniques for reducing the space required to execute a program. One is code compression and the other is code compaction. code compression transforms a block of executable code into a highly-compressed, non-executable block of data. On the other hand, code compaction compresses a block of executable code into a executable form. The first method results in a smaller compressed respresentation than the second, but it requires the overhead of decompression before execution. Furthermore, it requires the additional space to place the decompressed code. So we focus on code compacion in this thesis.
Cooper and McIntosh obtain a code size reduction of about 4 ~ 5% on the average using code compaction with exactly matched blocks and Debray and Evans obtain an additional code size reduction of about 0.4 ~ 0.6% on the average using code compaction with partially matched blocks. The obtained profit from Debray and Evan`s experiment was so small. Because code compaction with partially matched blocks requires additional branch instructions for managing control flow.
The other hand, the instruction set of recent processors offer support for branch-free execution of conditional statement in the form of so-called conditional instructions. A conditional instruction consists of a conditional code and a regular machine instruction.
In this thesis, we explore how conditional codes of instruction set can be used to reduce overheads of code compacion with partially matched blocks. We made experiment with our idea on ARM processor. Experiment results say that our method can reduce 3 ~ 4% of code size additionally.