CODE COMPRESSION OPTIMISATION FOR VLIW PROCESSORS

As computer programs become more complex for both embedded and large-scale applications, bloated code size continues to become an ever increasing problem. It is of particular concern in an embedded environment, where the size of the final object code greatly effects the space required for memory, which in turn contributes to overall cost. Code compression techniques have been devised as a way of battling large compiler outputs without the need to re-write hand-optimised code. The algorithms in this field require code-specific techniques (as compared with simple file or data compression) to maintain the integrity of the program and ensure its functionality. Code compression is a field where compression ratios (defined as the ratio of compressed code to uncompressed code) between compiler-generated code and subsequent compressed code are highly dependent on decisions made at compile time. Most optimisations employed by compilers tend to focus on parameters such as program performance, efficiency and minimising resource dependencies, though some effort has been made in recent years, to optimise for space as well as power savings. The effects these compiler output optimisations have on the code compression applied subsequently had not been investigated. This thesis presents the results of research into the effects of compiler optimisations on subsequent code compression for VLIW processors. The initial work looks at applying known RISC code compression algorithms to VLIW processors and investigating the effects of various levels of compiler optimisation. These compression schemes include Operand Factorisation applied to instructions, opcode/operand pairs and instruction words; simple dictionary compression with and without compression of single-use instructions; arithmetic coding as an example of a statistical compression scheme; and dictionary compression applied to single and multipleinstruction codewords. Various decompression methods are also considered based on serial decompression of individual instructions or parallel decompression of instruction fetch packets. It is shown that compression ratios are not a useful indicator of the best code size as the best results for smallest overall code size (after compiler optimisations and code compression) are obtained when the compression schemes are applied to compiler size-optimised code. Furthermore, it is shown that dictionary compression schemes are affected by compiler outputs much more so than statistical compression schemes. Program object code built with no optimisation compressed markedly better under dictionary compression rather than optimised code (a difference of 30%). However, compression ratios for statistical compression were largely independent of code optimisation. The technique of reordering parallel instructions within a VLIW compiler-issued fetch packet is also investigated, though it was found to only slightly improve compression in unoptimised code and did not affect the code compression when the benchmarks were already optimised for size. Various Vector Hamming Distance code compression techniques are investigated in this thesis, both for their own code size reduction potential, as well as how they are effected by the post-compilation technique of register re-assignment. The Vector Hamming Distance code compression technique is trialed with various dictionary selection methods including frequency, spanning and hybrid selection methods. It is shown that a dictionary selection method which considered both vector frequency as well as maximum spanning achieved better results than just considering either independently. The post-compilation technique for the greedy re-assignment of general purpose scratch registers is the final piece of research work in this thesis. The purpose of the technique is to improve Hamming distance based code compression by renumbering registers based on the register-pair frequency of the registers used by isomorphic instructions and employs a Gray coding scheme to reduce Hamming distances between similar instructions. Register reassignment had previously been successfully implemented in areas where the compiler optimisations do not include a particular metric, for example, power savings. Program values can be reassigned register numbers that reduce overall power consumption of the address bus and register file decoder, at no cost to code size or performance. This technique was shown to reduce the number dictionary entries required by over 9%