Cutting costly representations shouldn't be that hard.
If the cost of converting from representation X to representation Y is
C_xy, then for any point in a chain of VOPs, you can cut the search if
the cost of using X at this point and forward is larger than the cost
of using Y + C_xy.
On 8/17/07, Denys Rtveliashvili <rtvd@...> 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.
> Hi Nathan,
> I'm trying to understand this task better. Please, let me know if I am
> not right about my assumptions.
> I assume that the scope of optimization is a single function (possibly,
> with some other functions inlined), and that the function is a list of
> consequent operations which can map to a variety of VOPs.
> Each VOP has a number of related values. And each of these values is
> typed. So, it is necessary to select the VOPs keeping in mind that they
> need to have their values/variables matched.
> Then, I assume that the values which are received by the function and
> returned by it are tagged. This assumption is a minor point and I am
> probably wrong about it.
> The solution is a sequence of VOPs, mapped from the given operations
> that their related values match and the overall cost of the chain is
> Another assumption is that there is no automatic conversion between
> possible representations of a value If it, the scheme will be a bit
> different but let's not consider it now.
> So, we have n operations and m values. As long as available VOPs can
> have different types of incoming and outgoing values, each of the values
> can have a limited set of possible types. Let's say that the m-th value
> has Vm possible types.
> In this case, the number of possible solutions is not larger than
> V1*V2*..*Vm. This is probably a big number. I guess it could be close to
> 4^m for VOPs related to fixnums only.
> Also, each operation can be represented as a number of VOPs. If we say
> that the n-th operation has Om mappings to VOPs then we can also say
> that the number of possible solutions is not larger than O1*O2*..*On.
> This is a very big number as well.
> However, in reality no one will be willing to check all the
> possibilities. And the chosen VOP influences the types of the values.
> So, here are some heuristics and optimizations which might be useful:
> 1. For each step when a VOP has to be selected the amount of possible
> options is narrower than just all VOPs related to the operation. Only
> VOPs which can accept values of types predefined by the steps before can
> be used. This makes the search narrower, and I guess the invalid VOPs
> can be filtered out in liner time.
> 2. Then, for each value involved, I propose to estimate a "costs" of
> each of its types as a simple sum of the cost of all VOPs referencing
> the value of the same type.
> 3. An inevitable step is choosing the sequence of VOPs. It is necessary
> to try all possible variants (ideally). The task is computationally
> heavy, and on each step it is necessary to estimate the cost of the
> sequence and compare it with previous possibilities. Here I propose to
> chose VOPs based on the "cost" of the related values and starting from
> those with smaller cost. In case the cost is the same, a VOP with the
> smaller "cost" should be chosen first. Of course, the order of selection
> for VOPs should be determined beforehand. The search can be artificially
> limited by a predefined number of tries (100, for instance), just to
> evade problems on long sequences.
> 4. Another possible way to optimize this would be splitting the sequence
> of VOPs into loosely-coupled chunks. It will be much easier to estimate
> costs of different possibilities in each of the chunks for each possible
> set of types of the values shared between the chunks.
> Denis Rtveliashvili
> This SF.net email is sponsored by: Splunk Inc.
> Still grepping through log files to find problems? Stop.
> Now Search log events and configuration files using AJAX and a browser.
> Download your FREE copy of Splunk now >> http://get.splunk.com/
> Sbcl-devel mailing list