Hi Vladimir, I have just begun working for Icera Inc, on a private port of GCC, and my first task has been to investigate the performance impact of using the Chaitin-Briggs algorithm of IRA vs the priority algorithm that we currently have enabled in our production compiler (due to not defining IRA_COVER_CLASSES).
After running various tests, I measured little performance changes except for some test cases that have regressed quite considerably. My suspicion was that these regressions were due to our architecture having some instructions that can only use a subset of the register bank, so I set about trying to understand IRA enough to confirm this. I now believe I have now reached a point where I understand IRA enough to start thinking about how I can improve these regressed cases, but I thought it might be a good idea to formulate an email with my current understanding of IRA in it, so you could correct any errors before I continue. (I figure this exchange between us will also serve useful to other newbies in the field of GCC register allocation!) Without further ado, here is my current understanding of IRA (numbered for ease of reference). 1. You can enable full IRA, with Chaitin-Briggs coloring, by defining IRA_COVER_CLASSES, but you can just as easily disable it again by supplying -fira-algorithm=priority at the command line. (The latter is useful to know because it means you can compare two versions without recompiling.) 2. The priority algorithm allocates in an order determined by the allocno_priority_compare_func and calls into assign_hard_reg in that order to determine which allocno gets what register (or memory). 3. The CB algorithm puts allocnos into colored and uncolored buckets, according to conflicts between allocnos. The more conflicts, the more chance of being put in the uncolored bucket. Being in the uncolored bucket increases an allocno's chance of being spilled; being in the colored bucket guarantees that it will get a hard register. 4. When you run at -O0, the conflicts aspect of IRA is disabled (ira_conflict_p is set to false), and this subsequently causes the fast_allocation function to be used instead of the do_coloring IRA function. (This makes sense since you cannot separate into buckets without inspecting conflicts.) 5. Assuming ira_conflicts_p is enabled and you are using the CB algorithm, the two buckets are sorted using a bucket_allocno_compare_func, and this ordering is important, since it dictates the order each allocno will be pushed onto the stack and hence the order it will be popped from it (and assign_hard_reg called). 6. Allocnos from the colorable bucket always go on the stack first (in the order they were sorted) and then uncolorable ones, in an order based on which is the best candidate for spilling. Each time an allocno is added to the stack, conflicts may be reduced and there is the possibility of moving one or more allocnos from the uncolorable bucket to the colorable one (so they end up being added to the stack sooner than the other uncolorable ones). Near the end of processing the uncolorable bucket, there comes an opportunity to move all remaining allocnos to the colorable bucket (due to few remaining conflicts) and these get put on the stack last, and hence popped first, and so they all get registers. These final uncolorables will be those that had the highest spill cost and/or the most remaining conflicts. 7. The spill cost and priority calculation for determining which uncolorable to put on the stack first is important, for two main reasons: firstly, whichever allocno is picked is a more likely candidate for spilling; secondly, it will free other allocnos up to be added to the nicer colored bucket, from which an allocno always receives a hard register. If you could let me know if and where I've gone wrong with any of the above, I would be extremely grateful. Then, once we are on the same page, I hope you could also make some suggestions as to how I might help IRA work well with our instructions that can only use a subset of the register bank. Best regards, Ian Bolton (Compiler Engineer, Icera Inc.)
