freenode/#sicl - IRC Chatlog
Search
4:09:22
Bike
beach: i forgot to mention i've started on a kildall replacement, though not one that's gone far. here's an example: https://github.com/s-expressionists/Cleavir/blob/master/Liveness/liveness.lisp as you can see, it only defines the per-node info (the live-before and live-after slots), the function to call on each node (flow), and a way to mark more nodes to process (mark), and leaves the rest up to the details
4:20:36
Bike
i'd also like to be able to stop an analysis and then restart it later after some graph modifications
8:24:12
heisig
I just dug up my old Kildall code for my university assignments. It is not well documented, but the interface was very pleasant.
8:33:30
beach
Sure. The problem is that the code that remains in the top-level abstraction is so skimpy it is not worth calling it an abstraction.
8:37:36
beach
You can't assume that the meet function is associative, so you can't assume you can associate a partial result with a graph node.
8:40:48
heisig
Usually the work-list entries are basic blocks. But I guess by introducing another higher-order function, one could abstract that further.
8:47:28
beach
heisig: I apply the formula in the Cleavir documentation, which requires knowledge about what arcs are back arcs and what arcs are not.
8:50:02
beach
heisig: I can't predict whether any other domain may need a meet that is not associative.
9:08:32
heisig
I just had a look at the Clavir documentation. So the problem is that the formula for computing the EDU of a statement with multiple outgoing arcs is not associative.
9:09:33
beach
Because I am going to assign a probability of 0.9 to a back arc and 0.1 to a forward arc if there is one of each.
9:11:22
heisig
But this knowledge would be available to a meet function, if we allow arcs to have access to dominance information.
9:12:16
beach
Sure, making that knowledge available is no problem. You don't even need dominance. Just do a depth-first-search initially and record the back arcs.
9:13:36
heisig
Oh, another thing - I really like the idea of assigning probabilities of whether an arc is taken or not.
9:14:43
heisig
A very fruitful application thereof would be to assign the error paths during type checking a probability of almost zero (maybe even zero).
9:18:39
heisig
Oh, just one more thought. Are you sure we want to use floating-point values in the compiler?
9:24:39
beach
You mean for 0.1 and 0.9? I am going to truncate them. But maybe there is a better way than to use floating point.
9:26:40
heisig
The thing is floating-point values can be a problematic in terms of portability, reproducibility and implementer sanity.
9:30:56
heisig
Sure. I just wanted to make sure SICL can produce reliable results, independent of the host it is being run on.
13:45:29
Bike
to indicate branch probabilities, LLVM just uses machine integers, which are used as implicit rationals, the denominator being the maximum integer
13:46:31
Bike
so addition is just addition, and multiplication should just be multiplication followed by a shift i think
13:47:33
beach
If Common Lisp rational arithmetic becomes a problem, I'll consider something like that.