From: Denys R. <rt...@ma...> - 2007-08-17 18:11:06
|
>>>> 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 minimal. 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. Regards, Denis Rtveliashvili |