freenode/#clasp - IRC Chatlog
Search
7:01:43
drmeister
With *optimization-level* of 3 Compile-file time seconds real(24.4) run(24.4) llvm(13.1) link(5.3)
7:03:00
drmeister
With *optimization-level* of 0 Compile-file time seconds real(1.9) run(1.9) llvm(0.1) link(0.8)
7:07:44
drmeister
(cmp:*optimization-level* 3)Compile-file time seconds real(14.1) run(14.1) llvm(3.3) link(4.9)
7:08:01
drmeister
(cmp:*optimization-level* 0)Compile-file time seconds real(10.9) run(10.9) llvm(0.4) link(4.3)
12:59:23
beach
karlosz: Yes, and what they mean is that it won't work if you use ONLY those, without taking executability into account.
13:00:33
karlosz
yeah, but i feel like there still needs to be a clause handling merge points, even in SFA
13:01:50
beach
Yes, some variables will have several definitions. Hence the UD chains rather than just a single SSA edge.
13:03:25
karlosz
if we let v represent the merge point variable, then the UD chain would look like (v, {3, 4})
13:03:56
karlosz
i think you might be missing a clause saying that the lattice cell of the variable with multiple defs is derived from the executable defs in the UD chain
13:05:01
beach
Evaluate the expression obtaining the values of the operands from the LatticCells at the DEFINE side of the UD chains of this node.
13:11:21
karlosz
that works too, if one says to ignore TOP lattice values for that particular clause
13:14:28
beach
You need DU and UD chains because there are some variables with multiple definitions in SFA.
13:15:34
karlosz
so it could simplify the algorithm if we leveraged that and only made DU UD explicit for those merge variables with multiple defs
13:16:09
beach
They claim better complexity for SSA and complain about a quadratic number of DU and UD chains, but SSA itself can be quadratic, so the two are not quite comparable.
13:17:24
beach
Sure, you would save around half of the UD edges, but you would still have to be able to traverse the DU edge in reverse, and I think that requires the same amount of memory.
13:21:50
karlosz
i thought SFA was just put assignment instructions into each predecessor branch leading into a merge point
13:22:03
beach
Since there is no phi node, the use of such a variable can come much later, not necessarily in the successor.
13:24:44
karlosz
maybe not, but is it possible to have that information in the flow graph itself, like SSA, without actually using phi?
13:28:09
beach
::notify karlosz I believe you are right. It should be enough to know where a variable is defined and where it is used. And we have that information already. There will not be a definition that hides another definition, so the UD chains are trivial.
13:49:10
karlosz
beach: yes, the only possible defs for merge vars are in different branches, which can't overlap
13:49:10
Colleen
karlosz: beach said 21 minutes, 1 second ago: I believe you are right. It should be enough to know where a variable is defined and where it is used. And we have that information already. There will not be a definition that hides another definition, so the UD chains are trivial.
13:49:49
karlosz
so maybe SCC algorithm can be written more like the one for SSA, without the extra DU UD computations
14:07:23
karlosz
another simplification: instead of having to look up the predecessor associated with the phi input (to check if it is executable), there is no need for that in SFA because you can check which assignment instructions are executable instead. there is no need for using the indices this way
14:10:32
beach
We should remember that UD and DU chains are trivial in SFA. That information can come in handy.
14:44:36
karlosz
but the crucial observation is that you can recover the same information at a merge point because those branches cant overlap in execution
15:55:53
karlosz
beach: it occured to me that SCC could be generalized into a much more powerful algoirthm that deals with general constraints
15:56:27
karlosz
the current type inference algorithm doesn't keep track of executable branches, right?
15:56:51
karlosz
so perhaps instead of consstants in the lattice, types and other constraint information can be kept track of
15:57:30
karlosz
when i had implemented it earlier i realized that as long as the universe has the finite chain condition it should terminate and work the same