Heuristic algorithms for register allocation

    Research output: Contribution to journalArticleResearchpeer-review

    Abstract

    A model to find the optimal register allocation of program variables, including large strongly connected regions (loops), is presented. The program is represented by a directed control flow graph and assumes that all variables have been allocated to memory locations. The model takes into account the cost and saving times involved in allocating variables to registers in each node of the program in order to maximise the global time saving in program execution. As the solution of this model requires exponential resources (both time and space) in the worse case, two heuristic algorithms with O(m) and O(m2) complexities have been developed. Comparisons between the performance of the two heuristic algorithms and the optimal one are made for a set of representative programs.
    Original languageEnglish
    Pages (from-to)73-80
    JournalIEE Proceedings E: Computers and Digital Techniques
    Volume139
    Issue number1
    DOIs
    Publication statusPublished - 1 Jan 1992

    Fingerprint

    Dive into the research topics of 'Heuristic algorithms for register allocation'. Together they form a unique fingerprint.

    Cite this