Leo, Thanks for your suggestions and comments.
On Wed, 20 Oct 2004 10:35:04 +0200, Leopold Toetsch <[EMAIL PROTECTED]> wrote: > Some remargs WRT gen{3,4}.pl: > 1) While these programs exhibit some worst case register layout it's > probably not a very typical layout. Agreed. The idea was to automate and compare to gcc. There are real-world tests already in the parrot test suite, but because I can generate millions of such cases, one hope is to detect errors, and to get some kind of performance metric, even if these programs are artificial. To get real metrics that people would pay attention to, we might implement SPEC99, etc. > 2) RL programs have lexicals and globals access spread over the code like > in the generated gen.imc > 3) and that's intersparsed with highly local access to temporaries coming > from expression evaluations. I think I could modify the tests so that the variables have a Poisson distribution, as far as their usage distance goes (max number of lines away from first use). This would cause some of them to look more like temporary variables, and be a somewhat better simulation of real programs. > I'd change the simulation program to use PMCs to allow for 2). Now when > it comes to spilling, these lexicals or globals don't need a new > storage, their live range can just get discarded and at the next usage > of this lexical or global it just can be refetched[1]. Implementing this > should already vastly improve the register allocation. > > [1] The refetching can of course be into a different Parrot register. > Thus the usage of globals or lexicals wouldn't interfer and generate > huge live ranges over the whole function as it currently does. > I don't quite understand this. You think I should create PMC variables, instead of integers? It's probably a good idea to have a mix of the four types I suppose. Once thing I can say is that the interference graph is pretty conservatively generated. When a variable is reassigned, it can be treated as a new variable which can reduce register pressure, but I don't think the code is doing that yet. It sounds like you're talking about implementing the interference graph better. I may get into that too, but for now, I want to get the rester coloring (mapping vars to registers) working better. Also, I'd like to be able to capture the effects of changes in metrics (via scripts like those I posted) so we can see if different ideas will actually improve the situation or not. I don't even have any runtime checks yet, but creating a score to see how much was spilled, could be helpful. That could be incorporated into the register allocator itself (which already is, if you run with -d 0008, then grep Spill). > I don't know if we need some syntax to easily support lexicals or > globals or if the register allocation can deduce that itself. But if a > new syntax simplifies that, we put it in. My preference is to not distinguish between various types of variables, but to have the algorithms deal best with nodes based on the structure of the graph(s). > > For 3) there is already a separate pass in > imcc/reg_alloc.c:allocate_non_interfering(). Yes. This function seems to find variables whose live ranges (life ranges) are restricted to a single basic block, and assign them reg 28,29, or 30. My preference is that low hanging fruit like temporary vars should be assigned by the algorithm. Such variables will tend not to have much interference with others, and are thus probably easier to color. My experience with coloring, is that assigning low degree (aka arity, #neighbors) nodes to fixed colors first, will actually reduce the performance of the graph coloring algorithm. It's usually best to color the easy stuff last. The algorithm I'd like to use is one that happens to work very well for interference graphs, and it is very simple. This algorithm selects a node that interferes with the fewest other variables (lowest degree), and removes it from the interference graph, and puts it into a stack. It then recalculates the lower degrees of each neighbor, and iteratively removes all nodes from the graph in this way, pushing them onto the stack. It then, pops off the nodes from the stack and colors them in lifo order, using the first available color. Nodes that need a color higher that 30, or whatever the max. turns out to be, are spilled. The spilled nodes are always in the densest part of the graph, where something has to spill. I believe this is essentially the algorithm Briggs/Chaitin used, and some variation of it has been used in most compilers since the 70's. One exception is that certain variables want certain colors (want_regno) -- those should be colored first, as the current code does. A disadvantage of the above algorithm is that it tends to randomly select which nodes get spilled, among the densest parts. Another optimization to the algorithm is to incorporate a score that causes the most frequently accessed nodes not to get spilled. (The current scoring mechanism is pretty primitive right now -- someone wrote "I have no clue of how good it is") There are also other possible optimizations, like splitting the live-ranges of certain long lived, rarely used variables, to again, reduce register pressure. Currently, there are many simple optimizations to be done to the register allocation that would have a dramatic effect on, at least runtime. I think that implementing the above algorithm would be helpful, and scale with GCC as far as runtime goes. Next, probably improving the interference graph, and then the above optimizations. I am open to suggestions about the best path. I think it's important to look at experimental results as these decisions are made. With so many registers, it may be more important to focus on swapping registers in and out between subroutine calls, rather than the actual register allocation optimization. Another thing that might be worth checking, after parrot gets out of "alpha", is if reducing or increasing the number of registers will help performance. Just a thought. - Bill