Computer Science – Programming Languages
Scientific paper
2012-02-24
Computer Science
Programming Languages
12 pages
Scientific paper
Register allocation has long been formulated as a graph coloring problem, coloring the conflict graph with physical registers. Such a formulation does not fully capture the goal of the allocation, which is to minimize the traffic between registers and memory. Linear scan has been proposed as an alternative to graph coloring, but in essence, it can be viewed as a greedy algorithm for graph coloring: coloring the vertices not in the order of their degrees, but in the order of their occurence in the program. Thus it suffers from almost the same constraints as graph coloring. In this article, I propose a new method of register allocation based on the ideas of model transformer semantics (MTS) and static cache replacement (SCR). Model transformer semantics captures the semantics of registers and the stack. Static cache replacement relaxes the assumptions made by graph coloring and linear scan, aiming directly at reducing register-memory traffic. The method explores a much larger solution space than that of graph coloring and linear scan, thus providing more opportunities of optimization. It seamlessly performs live range splitting, an optimization found in extensions to graph coloring and linear scan. Also, it simplifies the compiler, and its semantics-based approach provides possibilities of simplifying the formal verification of compilers.
Dybvig Kent R.
Wang Yin
No associations
LandOfFree
Register Allocation By Model Transformer Semantics does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Register Allocation By Model Transformer Semantics, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Register Allocation By Model Transformer Semantics will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-79591