Advanced Backend Optimization

Conclusion

C.1. Some open problems in backend optimizing compilation

C.1.1. Problem of instruction selection

One of the most interesting problems in backend code optimization is instruction selection, which we did not address in this book because we think that the problem is still open when instruction schedules are not fixed.

Instruction selection allows us to transform a low-level intermediate code into the assembly code of the target machine. We think that the classical model based on pattern matching (rewriting rules and trees [AHO 07]) does not exactly describe the problem of instruction selection. Indeed, such syntactic rules allow us to transform m intermediate instructions into a single assembly instruction, using a static cost model [AHO 07]. We think that a more accurate model must be based on code semantics. That is, the general problem is transforming m low-level intermediate instructions into n assembly instructions computing the same result, and this could be modeled by algorithm recognition as studied in [ALI 05]. The reason is that, with the advance of reconfigurable computing and heterogeneous architectures, some sophisticated assembly instructions (with complex semantics) may be introduced in the instruction set: mathematical functions, vector instructions, domain-specific instructions, etc. Rewriting rules based on pattern matching are fragile techniques that may not detect opportunities for transforming m low-level three address instructions into sophisticated ...