freenode/#clasp - IRC Chatlog
Search
14:41:04
Bike
don't expect any huge performance improvements. but if you have ideas about what more transforms i can put in i can do that
20:37:29
pnp
Hi all. I have a doubt related to predecessors in a graph. If you consider the example here https://en.wikipedia.org/wiki/Dominator_(graph_theory) is node 5 a predecessor of node 2? I know is not related with the topic but i'm asking trying to understand the iterative construction of the dominator. If i consider only node 1 as predecessor
20:47:17
Bike
Starting at node 1, there is no way to reach node 5 without passing through node 2. So node 2 dominates node 5.
21:02:49
pnp
right... but i understand that since 5 doesn't dominates 2 is not a predecessor... If i have a region of a CFG with two nodes and a cycle between them you understand the problem applying that algorithm. The question arises from this situation
21:03:42
Bike
I don't understand. Is what I said ambiguous? From node 1 there is no way to reach node 5 without going through node 2. Do you think that's wrong?
21:04:40
Bike
That is what domination is. The fact that 5 is also a predecessor of 2 is irrelevant - if i'm not mistaken the dominator tree is the same with or without that edge.
21:06:47
pnp
what you say is not wrong but i would like to construct that tree applying the algorithm that you find there
21:09:31
Bike
OK. So for each node it sets the dominators to be the union of the node itself, with the intersection of the dominator sets of all the node's predecessors. There is no order specified.
21:09:33
pnp
there is a sort of "cyclic dependency" in calculation of dom(2) and dom(5) if i assume node 5 a predecessor of node 2
21:11:00
Bike
So we look at node 2 first. It has nodes 1 and 5 as predecessors. Node 1's dominator set is {1} and Node 5's is {1,2,3,4,5,6}. The intersection of these is {1}, so 2's dominator set becomes {1,2}.
21:26:57
Bike
drmeister: do you remember the purpose of this commit? https://github.com/clasp-developers/clasp/commit/97f9f147a35d9b18d9581bcd7c816aa45aecd894
21:27:51
Bike
As far as I understand, it delays process-run-function and stuff from returning until the thread is just about ready to call the lisp function
21:30:35
Bike
the stuff in the critical section includes mps registration, allocating and initializing the thread local state, getting the dynamic variables set up