Survey on Instruction Selection : An Extensive and Modern Literature Review

Instruction selection is one of three optimization problems – the other two areinstruction scheduling and register allocation – involved in codegeneration. The task of the instruction selector is to transform an inputprogram from its target-independent representation into a target-specific formby making best use of the available machine instructions. Hence instructionselection is a crucial component of generating code that is both correct andruns efficiently on a specific target machine. Despite on-going research since the late 1960s, the last comprehensive survey onthis field was written more than 30 years ago. As many new approaches andtechniques have appeared since its publication, there is a need for anup-to-date review of the current body of literature; this report addresses thatneed by presenting an extensive survey and categorization of both dated methodand the state-of-the-art of instruction selection. The report thereby supersedesand extends the previous surveys, and attempts to identify where future researchcould be directed.Qc 20131007