User loginNavigation 
Register Allocation By Model Transformer Semantics  need for early commentsHello, I'm drafting a paper on a new method for register allocation. But because of my limited experience, I have no idea whether someone else has done this kind of research before. So I hope to get some early comments here before I decide to submit it to a conference. I will appreciate your interest. Here is the abstract of it: "Register allocation has long been formulated as a graph coloring problem, coloring the dependency 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. Minimizing the number of allocated registers, the goal of graph coloring, is an imperfect proxy for the real goal. 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 graph vertices not in the order of 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 registermemory 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 which is only found in extensions to graph coloring and linear scan. Also, it greatly simplifies the compiler and its semanticsbased approach provides possibilities of simplifying the formal verification of compilers." Its full text can be found here. I also have given a talk at Indiana University in Nov 2011. Here are the slides [PPT] [PDF]. By yinwang0 at 20120104 21:19  LtU Forum  previous forum topic  next forum topic  other blogs  5686 reads

Browse archivesActive forum topics 
Recent comments
13 hours 44 min ago
15 hours 12 min ago
15 hours 41 min ago
1 day 21 hours ago
1 day 22 hours ago
2 days 16 hours ago
2 days 18 hours ago
2 days 18 hours ago
3 days 10 hours ago
3 days 11 hours ago