freenode/#sicl - IRC Chatlog
Search
14:54:06
heisig
I understand that. I justify it this way - numbering the nodes is just useful for this trick, but also for efficiently traversing all nodes exactly once.
14:59:26
heisig
Also, trying to understand your attitude of not bothering too much about performance has helped me a lot, so far.
15:00:00
heisig
Because now I am one of the few people in HPC that can deliberately 'switch off' this obsession about performance.
15:00:49
Bike
i have been considering keeping a node count in the BIR structures. With the backpointer maintenance I think it might be possible to update the count transparently, and then it can be used to make hash tables from nodes without needing to resize repeatedly (which really hurts performance)
15:02:22
heisig
It isn't. One sweep to set all counts to -1 or :INVALID, and a second sweep to assign the new numbers.
15:04:22
heisig
Oh, right. The difference is that the way I hand out numbers, they can be used directly as the 'keys' of a vector storing node information. So there is often no need for hash tables anymore.
15:10:22
Bike
https://github.com/s-expressionists/Cleavir/blob/master/Dominance/dominance.lisp#L85 It iterates through the graph to get the size, and then uses that to make a vector
17:37:23
beach
Major progress. I think the calculation for "estimated distance to use" is working. I invoke it for every IR program during bootstrapping, and I have checked that the result seems plausible. Also good news, it did not significantly impact the time to run the bootstrap procedure.
17:38:15
beach
In less than 20 minutes, my (admittedly small) family will announce that dinner is served. I will be around until then, but otherwise I am calling it a day.
17:48:57
beach
My (admittedly small) family just announced that dinner is served. I'll be back tomorrow.
19:12:34
karlosz
its useful for fast dominance algorithms too, since dfo numbering is actually useful for things like semidominator computation
19:13:50
karlosz
also, the Python algorithm for recomputing the flow order and flow order numbering is completely consless using a cool trick with the doubly linked list, but i think that requires imposing the basic block structure on the entire module and not just the per function so the algorithm knows how to deal with newly introduced and removed blocks
19:14:27
karlosz
not sure you can transparently change the numbers, but since in BIR we frequently modify while traversing we probably can't do what heisig describes
19:14:49
karlosz
Python already figured this out, by having utilities to lazily invalidate and recompute the flow order and flow order numbering
21:30:54
Bike
karlosz: you wanted to impose the block structure on the whole module anyway, right? i think i'm really starting to see the advantage