At 12:45 PM +0200 8/7/04, Leopold Toetsch wrote:Sean O'Rourke <[EMAIL PROTECTED]> wrote:[EMAIL PROTECTED] (Leopold Toetsch) writes:The interference_graph size is n_symbols * n_symbols * sizeof(a_pointer). This might already be too much.
2) There is a note in the source code that the interference graph could be done without the N x N graph array. Any hints welcome (Angel Faus!).
Since that is my comment I'll comment.
When I wrote the allocator, I oriented it around a basic block, and I figured a basic block would never have more than a few hundred symbols, so the N x N array was the fastest possible data structure for keeping the interference data.
I'm not sure how many symbols we are talking about here, it would help if someone threw out a number before I go and make the wrong statement.
I'm pretty sure that it would help if imcc had two modes of symbol analysis. Routine wide register allocation ends up with better quality code, but at the cost of compilation time and possible cases that can't be handled with the current design. If imcc sees too many symbols, it should try to break the sub down into basic blocks for interference analysis, but that also adds additional code requirements for when you put the basic blocks together and figure out loads, spills and reuse across basic blocks. There were a lot of things that I had planned for imcc that just never materialized. It is still very primitive when it comes to symbol analysis, even with all the work Leo has done.
-Melvin
