Constraint analysis for code generation: Basic techniques and applicationsin FACTS

Code generation methods for digital signal processors are increasingly hamp ered by the combination of tight timing constraints imposed by signal proce ssing applications and resource constraints implied by the processor archit ecture. In particular, limited resource availability (e.g., registers) pose s a problem for traditional methods that perform code generation in separat e stages (e.g., scheduling followed by register binding). This separation o ften results in suboptimality (or even infeasibility) of the generated solu tions because it ignores the problem of phase coupling (e.g., since value l ifetimes are a result of scheduling, scheduling affects the solution space for register binding). As a result, traditional methods need an increasing amount of help from the programmer (or designer) to arrive at a feasible so lution. Because this requires an excessive amount of design time and extens ive knowledge of the processor architecture, there is a need for automated techniques that can cope with the different kinds of constraints during sch eduling. By exploiting these constraints to prune the schedule search space , the scheduler is often prevented from making a decision that inevitably v iolates one or more constraints. FACTS is a research tool developed for thi s purpose. In this paper we will elucidate the philosophy and concepts of F ACTS and demonstrate them on a number of examples.