Instruction selection for embedded DSPs with complex instructions

Abstract{We address the problem of instruction selection in code generation for embedded digital signal processors. Recent work has shown that this task can be efciently solved bytree covering with dynamic programming, even in combination with the task of register allocation. However, performing instruction selection by tree covering only does not exploit available instructionlevel parallelism, for instance in form of multiplyaccumulate instructions or parallel data moves. In this paper we investigate how such complex instructions may a ect detection of optimal tree covers, and we present a two-phase scheme for instruction selection which exploits available instruction-level parallelism. At the expense of higher compilation time, this technique may signi cantly increase the code quality compared toprevious work, which is demonstrated for a widespread DSP. 1 1