Browse Prior Art Database

Register Allocation via Critical Path Analysis

IP.com Disclosure Number: IPCOM000115094D
Original Publication Date: 1995-Mar-01
Included in the Prior Art Database: 2005-Mar-30
Document File: 4 page(s) / 69K

Publishing Venue

IBM

Related People

Komatsu, H: AUTHOR

Abstract

Disclosed is an efficient register allocation technique for instruction-level parallel processors. This technique is based on critical path analysis for target program.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 66% of the total text.

Register Allocation via Critical Path Analysis

      Disclosed is an efficient register allocation technique for
instruction-level parallel processors.  This technique is based on
critical path analysis for target program.

      In a register allocator for instruction-level parallel
processors, the following two points are essential:
  o  not to decrease instruction-level parallelism in program by the
      resource dependency caused by the register allocator
  o  to execute spill codes parallel with other instruction.

      These may not play an important role in scalar processor
system, if not, then existing register allocators do to not take
these into considerations.  Therefore, when a conventional register
allocator is applied to a instruction-level parallel processors,
parallelism in a program can not be reflected to the object program.

This register allocation algorithm will be executed as the following
steps:
  1.  Dependence Graph Generation - Dependence analyzer transformed
       source program into dependence graph form as internal
       representation.  Fig. 1 shows the example of dependence graph
       generation.
  2.  Critical Path Analysis - All path in dependence graph is
       traversed and computed length as the cost.
  3.  Path Prioritization - All path is sorted by the cost and each
       path is applied the following steps (4,5,6).  Fig. 2 shows the
       example of critical pat...