Heuristic Algorithms for Register Allocation

E. Luque, A. Ripoll, T. Díez

    Research output: Contribution to journalArticleResearchpeer-review


    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
    Issue number1
    Publication statusPublished - 1 Jun 1992


    Dive into the research topics of 'Heuristic Algorithms for Register Allocation'. Together they form a unique fingerprint.

    Cite this