Talk:Register allocation

Plagiarism ?

I can't tell what direction it's in, but please see: http://www.cs.mtu.edu/~sliu/raa.pdf

Link is dead now 84.209.121.30 (talk) 17:02, 3 June 2010 (UTC)

NP-complete?

What does NP-complete mean? I don't see it defined anywhere in the article and seems to assume expert knowledge with out any references...

See NP (complexity), I added the link Madhu 23:30, 5 September 2005 (UTC)

The difference between NP-complete and NP-incomplete is that NP-incomplete can be shown to never terminate. That is, given any amount of computing power you would never converge on a solution. —Preceding unsigned comment added by 67.161.46.100 (talk) 17:43, 11 March 2010 (UTC)

R-colorable?

The defintition of "R-colorable" isn't defined. Basically the text says that a graph is R-colorable if another graph is R-colorable. —Preceding unsigned comment added by 200.86.53.221 (talk) 01:37, 15 November 2007 (UTC)

Register pressure

Register pressure redirects to this article, but this term is not explained in this article. What does it mean? (This old version may give a hint, but needs to be checked) --Abdull (talk) 11:24, 1 April 2010 (UTC)

I added a couple of sentences to the Introduction section. 84.209.121.30 (talk) 17:08, 3 June 2010 (UTC)

Graph coloring

Certain parts of the article make a frequent over-simplification that register allocation is equivalent to graph coloring. This has proven to be an inadequate explanation of the real problem of interest. For a recent summary, please see this article:

 http://www.ens-lyon.fr/LIP/Pub/Rapports/RR/RR2006/RR2006-13.pdf

in particular, one certainly cannot say that because one can reduce register allocation to an NP hard problem, then register allocation is NP-complete. The reductions for NP-hardness need to go the other way round! Again, please see the paper above or the papers cited there. — Preceding unsigned comment added by Vkuncak (talk • contribs) 19:48, 10 December 2013 (UTC)

Yeah, I have to agree with you here. There is actually a reduction in the right direction, but it is a lot more subtle than presented in the article. In particular, the register allocation problem for most actual computers seems to be easy. You only get NP hardness with certain restrictions on what a program can do. — Preceding unsigned comment added by 2003:69:CD02:FE01:2E81:58FF:FEFF:8F4B (talk) 13:44, 29 December 2013 (UTC)

Possible merge ?

Hi! We've been recently working on a literature search about register allocation. We were wondering if someone would oppose to the merging of the current register allocation wikipedia article and our current draft. The draft is available there: http://en.wiki.x.io/wiki/User:Grophi/sandbox, please note this is still a work in progress. We tried to keep the vast majority of the content proposed in the current article in the draft, but might have missed some parts. (Grophi (talk) 01:26, 9 January 2019 (UTC))

Did actually merge it today. Still open to discussions and improvements though! (Grophi (talk) 12:49, 17 January 2019 (UTC))

---

General Comments

Some bibliographic entries are duplicated ;

• Runeson, Johan; Nyström, Sven-Olof (2003). Krall, Andreas (ed.). Retargetable Graph-Coloring Register Allocation for Irregular Architectures. Berlin, Heidelberg: Springer Berlin Heidelberg. pp. 240--254. doi:10.1007/978-3-540-39920-9_17. ISBN 978-3-540-39920-9. Runeson2003. {{cite book}}: Unknown parameter |booktitle= ignored (help)
• Runeson, Johan; Nyström, Sven-Olof (2003). "Retargetable Graph-Coloring Register Allocation for Irregular Architectures". 2826: 240–254. doi:10.1007/978-3-540-39920-9_17. ISSN 0302-9743. {{cite journal}}: Cite journal requires |journal= (help)

Done! Thanks! Grophi (talk) 17:58, 21 January 2019 (UTC)

Detailed Comments

Context

Challenges of register allocation

Maybe change the line in registers or outside registers to Inside or outside registers

 Done! Grophi (talk) 20:21, 24 January 2019 (UTC)

Toomai93 (talk) 20:18, 22 January 2019 (UTC)

• Spilling: Adding some examples ? the utility/drawbacks of this strategy.
• Assignment: Adding some examples ? the utility/drawbacks of this strategy.

SelimLakhdar (talk) 09:06, 28 January 2019 (UTC)

Common problems raised in register allocation

Aliasing

• Weird formulation in when an assignment to one register can affect the value of another., maybe change to In some architectures,an assignment to one register can affect the value of another

• Also maybe explain why it can affect the value of another register with aliasing, I don't know if it is outside of the scope of this article

Toomai93 (talk) 20:26, 22 January 2019 (UTC)

 Added an example and rephrased (Grophi (talk) 17:38, 29 January 2019 (UTC))

• How can we mitigate those problems ?

SelimLakhdar (talk) 09:06, 28 January 2019 (UTC)

 Someone willing to cope with register allocation will have to face these problems. The idea is that the techniques described in the article mitigate or try to avoid some of these problems. I'll add an introductory sentence stating this. Thanks! (Grophi (talk) 18:07, 29 January 2019 (UTC))

Register allocation techniques

Graph-coloring allocation

• In Graph-coloring allocation is the predominant approach to solve register allocation., maybe a source to corroborate the affirmation

 Done ! (Grophi (talk) 19:14, 29 January 2019 (UTC))

• Add an inside link to the Graph-coloring page

 There is one the first time graph coloring in mentioned in the paragraph (in: "Register allocation then reduces to the graph coloring problem in which colors (registers)"...). Were you thinking about that kind of link or something more explicit like a "see also" at the beginning of the section? Grophi 

(talk) 20:18, 24 January 2019 (UTC)

My bad, I didn't see this one, perfect.

Toomai93 (talk) 18:08, 25 January 2019 (UTC)

• Maybe a graph to illustrate the graph-coloring

Toomai93 (talk) 20:33, 22 January 2019 (UTC)

 I agree with your remark and will try to make a gif showing the process, which would indeed help to understand the algorithm. (Grophi (talk) 10:37, 25 January 2019 (UTC))

Principle

Spill cost

• Maybe add an example ?

Toomai93 (talk) 16:23, 23 January 2019 (UTC)

Drawbacks and further improvements

• I find the first paragraph a bit confusing, maybe split it before Furthermore

Is now less confused?

--Boinclement (talk) 18:55, 29 January 2019 (UTC)

• I don't understand the abbreviation (resp. before, resp. use,...), maybe add an explanation

We removed the abbreviation, Is it more clear for you ?

--Boinclement (talk) 18:55, 29 January 2019 (UTC)

Toomai93 (talk) 20:49, 22 January 2019 (UTC)

Linear Scan

• Maybe change the approach currently in use in to the approach currently used in

Toomai93 (talk) 20:53, 22 January 2019 (UTC)

 Done! Grophi (talk) 20:13, 24 January 2019 (UTC)

• Once the live ranges of all variables have been figured out, the intervals are traversed chronologically. Although this traversal could help identifying variables whose live ranges interfere, no interference graph is being built and the variables are allocated in a greedy way. ==> greedy ? : on which selection the greedy algo relies on ?

SelimLakhdar (talk) 09:06, 28 January 2019 (UTC)

Drawbacks and further improvements

• First, the time spent in data flow graph analysis, aimed at building the lifetime intervals, is reduced, namely because variables are unique [36]. It consequently produces shorter live intervals, because each new assignment corresponds to a new live interval [37][38] ==> reformulate it ?

SelimLakhdar (talk) 09:06, 28 January 2019 (UTC)

We added an image to illustrate this sentence.

--Boinclement (talk) 19:13, 29 January 2019 (UTC)

Rematerialization

• Briggs and Al extends Chaitin's work to take advantage of rematerialization opportunities for complex, multi-valued live ranges. They found that each value needs to be tagged with enough information to allow the allocator to handle it correctly. Briggs's approach is the following: first, split each live range into its component values, then propagate rematerialization tags to each value, and form new live ranges from connected values having identical tags. ==> drawbacks of this technique ? the additional space for the extra data ?

SelimLakhdar (talk) 09:06, 28 January 2019 (UTC)

Thanks, Rematerialization achieves better quality of spill code that Chaitin's work. But it has not introduced new major drawbacks. It shares the drawbacks of Chaitlins' work

--Boinclement (talk) 17:33, 29 January 2019 (UTC)

Coalescing

• it's just an optimization after building the graph ? => drawbacks: time consumption ??

SelimLakhdar (talk) 09:06, 28 January 2019 (UTC)

Hi, thanks. In the two first paragraphs of the Coalescing section, we tried to explain the goals and why it is useful for compiler optimisation. That's why I think it is not interesting to talk about possible drawbacks that early in the section. But, right after those two "introductory" paragraphs, there are four definitions exposing Coalescing techniques where the major drawbacks are clearly (we think) exposed.

--Boinclement (talk) 17:51, 29 January 2019 (UTC)

Aggressive coalescing

".... cloud impacts the inference graph colorability." => cloud ? could ? SelimLakhdar (talk) 09:06, 28 January 2019 (UTC)

thanks

--Boinclement (talk) 17:17, 29 January 2019 (UTC)

Mixed approaches

Hybrid allocation

• Change to optimize the register use to to optimize register's use

Toomai93 (talk) 21:04, 22 January 2019 (UTC)

Done

--Boinclement (talk) 13:22, 26 January 2019 (UTC)

Split allocation

• In the same fashion, B. Diouf et al. proposed an allocation technique relying both on offline and online behaviors, namely static and dynamic compilation. [51] · [52]. During the offline stage, a spill set is gathered and annotated. Register allocation is performed afterwards during the online stage, based on the data collected in the offline phase.[53] ==> how the spill set is gathered and annotated ??

SelimLakhdar (talk) 09:06, 28 January 2019 (UTC)

We modified this sentence by adding more informations, "During the offline stage, an optimal spill set is first gathered using Integer Linear Programming. Then, live ranges are annotated using the compressAnnotation algorithm which relies on the previously identified optimal spill set. Register allocation is performed afterwards during the online stage, based on the data collected in the offline phase.". Tell me, if the informations you need are now presents.

--Boinclement (talk) 18:35, 29 January 2019 (UTC)

Comparison between the different techniques

• Dacapo benchmark suite => a breif introduction of the benchmark would be great ! make a new wiki entry ?

SelimLakhdar (talk) 09:06, 28 January 2019 (UTC)

Robert Wagner's 1970 article

"It was first proposed by Chaitin et al." - here's an article by Robert Wagner from 1970 talking about using graph coloring for register allocation (using a macro assembler) https://hdl.handle.net/1813/5928 This article is not referenced by Chaitin's aricle, but both reference Yershov Helphelp101 (talk) 11:05, 12 April 2023 (UTC)

Copyright problem removed

Prior content in this article duplicated one or more previously published sources. The material was copied from: https://dl.acm.org/doi/pdf/10.1145/143103.143143. Copied or closely paraphrased material has been rewritten or removed and must not be restored, unless it is duly released under a compatible license. (For more information, please see "using copyrighted works from others" if you are not the copyright holder of this material, or "donating copyrighted materials" if you are.)

For legal reasons, we cannot accept copyrighted text or images borrowed from other web sites or published material; such additions will be deleted. Contributors may use copyrighted publications as a source of information, and, if allowed under fair use, may copy sentences and phrases, provided they are included in quotation marks and referenced properly. The material may also be rewritten, provided it does not infringe on the copyright of the original or plagiarize from that source. Therefore, such paraphrased portions must provide their source. Please see our guideline on non-free text for how to properly implement limited quotations of copyrighted text. Wikipedia takes copyright violations very seriously, and persistent violators will be blocked from editing. While we appreciate contributions, we must require all contributors to understand and comply with these policies. Thank you. ARandomName123 (talk)^{Ping me!} 22:13, 15 September 2023 (UTC)

Note: The copyvio content was added when User:Grophi merged their version of the article with the original article in this diff: [1] ARandomName123 (talk)^{Ping me!} 22:14, 15 September 2023 (UTC)