Heuristic chaining in directed acyclic graphs

In this paper we look at the problem of generating code with instruction chaining from directed acyclic graphs (DAGs). The problem is shown to be NP-complete. A simple heuristic for the problem is devised and its performance is compared with existing methods. The heuristic is shown to generate good code especially when the number of registers is large. Also described is an extension to the heuristic which improves the code for a small number of registers