freenode/#sicl - IRC Chatlog
Search
10:36:55
no-defun-allowed
So, for now, I am not worried about the choice of hash function. Here is the performance graph of tonight's work: <https://applied-langua.ge/~hayley/sicl-hash-tables.png> linear-probing-hash-table beats out bucket-hash-table at GETHASHing existing mappings, and the graph looks basically the same for misses.
11:41:05
beach
My idea for a register-allocation technique based on the page replacement algorithm OPT depends on a metric that I call "Estimated Distance to Use" or EDU, and so far I have been unable to come up with a technique for computing the EDU.
11:41:11
beach
But this morning I noticed that it is a linear-equation system. The problem, though, is that the system is large very sparse, so it would be too costly to solve it with something like Gaussian elimination.
11:41:21
beach
Otherwise, the idea is as follows: The EDU is defined for each variable at program points before each instruction.
11:41:30
beach
The EDU of a variable V before instruction I (i.e., EDU[V,I]) is 0 if I has V as an input.
11:41:44
beach
If I has two successors, and V is live in only one successor J, and we estimate the probability of the branch from I to J to be taken by probability p, then EDU[V,I] = 1/p * EDU[V,J].
11:41:46
beach
Otherwise, let J and K be the successors of I and p the probability that the branch from I to J is taken, then EDU[V,I] = p * EDU[V,I] + (1-p) * EDU[V,J].
13:10:23
beach
The only real problem is with loop inside of which some variable is live but not used. The other cases are simple.
13:11:14
beach
However, I have also hinted in the past that register allocation should be done in loops first, from the innermost to the outermost.
14:27:40
beach
So, anyway, there are two completely separate phases to my idea. Phase 1 is to compute the EDUs and phase 2 is to use those EDUs to allocate registers. So I'll put phase 1 on hold for the time being and start thinking about phase 2.
15:14:26
heisig
Solving such a linear system efficiently should not be too hard. Especially since we don't need an exact solution - an approximation would be fine.
15:14:46
beach
It is also in chapter 10 of the Cleavir documentation in SICL/Code/Cleavir/Documentation.
15:17:58
beach
In the Cleavir documentation, the equations are not linear, but I think a linear system is a fine approximation.
15:52:58
beach
... which is too bad, because I am not really that interested in that particular architecture. But that's what we have for the time being. Oh, well.
15:59:03
heisig
Hmm, x86 could actually be gone soon. They will never be able to decode more than five instructions per cycle, and that is starting to hurt.
16:09:41
beach
Bike: What semantics do we attribute to UNBOX instructions? Are the responsible for checking that the input is of one of the right types (and signaling an error otherwise) and then applying the relevant unboxing operation? If so, is there any way that the type inferencer could annotate such an instruction so that some steps could be skipped in some cases?
16:11:54
Bike
boxing and unboxing is kind of still in flux. HIR unbox definitely checked types, though.
16:13:01
beach
That's what I though. Yes, maybe. But it's tricky since more than one object type could work, and the unboxing operation would be different for each one.
16:14:25
beach
I guess it's perhaps only for the ((un)signed-byte 64) that both a fixnum and a bignum might work.