From: Nathan F. <fr...@gm...> - 2007-08-16 23:49:21
|
On 8/16/07, Nikodemus Siivola <nik...@ra...> wrote: > > > The problem is not that the VOPs don't exist. The problem is that > > > SBCL always considers doing arithmetic operations on fixnum (tagged) > > > values preferable to doing arithmetic operations on untagged values > > > unless it absolutely has no choice. Changing this requires major > > > surgery on the compiler backend. > > Nathan: do you have a sketch (never mind how handwavy) of how to do this, > or whatever idea you have for improving the representation selection? I haven't thought about this in a while. My last idea was to unify the VOPs fixnums/signed/unsigned numbers so that, e.g., you'd have a single VOP for + which has something like: (:types (fixnum fixnum fixnum) (signed-num signed-num signed-num) (unsigned-num unsigned-num unsigned-num) ;; something new that we could thow into the mix on x86oids (fixnum unsigned-num fixnum) ...) and then representation selection is responsible for determining some optimal assignment that satisfies the constraints of defs and uses, inserting the necessary coercions. I'm not so sure this is a tractable approach; it looks vaguely like a an ugly graph-coloring problem and I don't see any great heuristics for it. I also didn't think about having to deal with all the floating-point VOPs--they'd have to be integrated into the giant + (or whatever) VOP. Ugh. It might be possible--and this is even more of a handwavy idea than the above--to assign representations *first* and then drive the VOP selection from that. This might entail choosing particular VOPs up front--for instance, we only have one VOP to do ub8-array reffing, so that's a known quantity. And then iteratively growing the solution from there ("well, that means this index variable wants to be an unsigned-num..."). Even if backtracking is required ("hmmm, this variable should be an unsigned-num for use #1, but these other two uses want tagged-nums, so it should really be a tagged-num..."), it can probably be done fairly efficiently. And the IR2 phase is not where the bulk of the compilation time goes in any event. Another option would be to do what we're currently doing, but have a "representation optimization" phase that runs after representation selection to do some fixing-up of dumb decisions. I have even less idea how this would work. Other ideas...? I feel like I'm rambling a little, but you explicitly asked for handwavy-ness. :) I keep meaning to look at some of the papers from the functional programming community on what they call representation selection--which seems somewhat close to the problem we're attacking here--but I haven't found the time to sit down and decipher everything. -Nathan |