Melvin Smith <[EMAIL PROTECTED]> wrote: > 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. The problem is that the matrix isn't built per block but per compilation unit. And all symbols of all 4 kinds are inside one graph albeit they can't interfer. The first thing todo is probably to split the matrix into four pieces. The whole register allocation could be done in four passes too, but that adds runtime overhead. OTOH data structures get smaller. > 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. Dan posted some numbers: P 26951, S 2099, I 8878 for "evil program". The program dies because of memory shortage when setting up the register life information. > 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. Well, I think we have the information to allocate registers per basic block. It would need some rearrangment of data structures, though. Anyway, I already have added a first allocation run that allocates all temporary registers of all blocks in one bunch. This pass doesn't need life range structures. All these aready allocated registers are not part of the next computations and are not in the interference gprah any more. > -Melvin leo
