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.