freenode/#sicl - IRC Chatlog
Search
21:32:42
karlosz
also i think douglas katzman mentioned that the bug in question seemed to be fixed in cmucl without doing this
21:34:54
karlosz
i spent quite a long time finding like some kind of explanation for this but nothing turned up
21:40:11
karlosz
what did happen though is that a lot of the comments no longer make any sense because of course not all the comments were updated
3:08:27
beach
To be clear about my opinion about SSA, let me explain. There are two main properties of SSA. One is that every value of a variable is available, a property that I shall call EVA. Another is that the notation artificially enforces the single assignment by introducing a φ operation. I shall call that property ASA.
3:08:34
beach
I have nothing against the EVA property. I think it is all good. But the ASA property ruins everything by enforcing a number and an order on the predecessors of some nodes. And all the research work I have seen (except one) takes advantage only of EVA.
3:08:35
beach
The exception is an article on value numbering that treats φ as a binary operator like the others, and in doing so, it misses plenty of opportunities for value numbering.
3:10:21
beach
I have yet to find any research that truly needs the ASA property. As a result, I must conclude that the ASA property is just a nuisance, and that we should use a notation that has the EVA property but not the ASA property.
3:12:54
Bike
i mean, i think that's common? it's what llvm does. phi nodes have an alist of (value . block) more or less
3:15:48
beach
There could very well be an assignment in each predecessor of what would otherwise be a φ node.
3:17:36
beach
This seems to me to be a case where every work that needs EVA has gone berserk and adopts SSA wholesale without realizing that the ASA property is not needed, and only represents a nuisance.
3:18:56
Bike
it's convenient to have a link in the merge variable directly to the different assignments, since each block could end with any number of em
3:21:13
no-defun-allowed
I had read some LLVM IR output before, and it didn't seem to fit how I understood SSA, so it seems they are not so strict with it.
3:21:24
beach
Bike: I don't see why it is convenient to have link to that particular assignment. If analysis techniques are used that don't rely on that particular assignment to be special in any way, then I don't see why a reference to it.
3:22:48
Bike
no-defun-allowed: the IR is in SSA. non-SSA variables are used indirectly through memory addresses which have load and store instructions.
3:23:00
beach
no-defun-allowed: I see. I guess that's my point. Most work insists on using SSA and insists that it needs SSA, but in fact, it only needs EVA, and ASA comes with it as an additional nuisance.
3:24:30
Bike
in BIR the way it works currently is that phi nodes, when they exist, compute their DEFINITIONS from the predecessor blocks when queried
3:24:34
no-defun-allowed
Bike: I remember reading some IR graph where it defined a SSA variable (which looked like %foo, not a memory address) in one basic block, then also used it before the definition, which is how I got confused.
3:24:56
beach
I am also accumulating evidence that EVA is a special case of value numbering, where anything but assignment is treated as an unknown operation.
3:25:02
no-defun-allowed
...and that basic block was in a loop. Not really how I thought of SSA, but it could be fine.
3:29:51
no-defun-allowed
It was from a tail-recursive implementation of gcd (though I suppose the CFG would be the same if you transformed it into a loop yourself), like <https://godbolt.org/z/P38vexaMs>
3:31:36
moon-child
incidentally, fun paper about basic block graphs https://link.springer.com/content/pdf/10.1007%2FBFb0026423.pdf
3:33:10
Bike
%7 is only "used before its definition" in the phi node. "%5 = phi i32 [%7,%4],[%1,%2]" means %5 is %7 if control came through block 4, or %1 if it came through block 2. Since 4 is the loop block, obviously it'll have to come from block 2 first.
3:33:12
beach
moon-child: Thanks. Interestingly, the very first words represent incorrect English grammar. :)
3:35:35
beach
moon-child: OK, I will. It is just amusing to me that they don't grab any old native speaker for proofreading.
3:39:59
beach
I guess Germans must be like Swedes; they tend to overestimate their mastery of the English language.
3:43:15
Bike
i like this graph near the end where a basic block having 30 instructions is unrealistic.
3:47:11
beach
"The advantage of edge-labeled graphs is even more drastic when looking at programs with a parallel operator" :)
3:56:35
beach
Otherwise, it's an interesting article. When I decided to use a "single instruction" graph for SICL, I had only the "higher conceptual complexity" aspect in mind.
3:58:14
beach
Plus, my reasoning was that the basic blocks could be computed on demand by a single traversal of the graph, whenever they would be convenient to have.
4:15:02
Bike
hmkay. i filed a pull request that would probably be enough for me to move to trucler in cleavir, but it changes the API a bit
4:18:04
Bike
yeah. trucler is pretty much the main block in cleavir towards actually using the ctype customization stuff
4:48:18
beach
As far as I can tell, that article doesn't really say how to represent branches in an edge-labeled SI graph. But I can see how it would be advantageous to have an explicit representation of program points. So I am considering a representation of two kinds of nodes, instructions and program points.
4:49:11
beach
An instruction would then represent a transition from a program point to one or more program points.
4:50:18
beach
But, that's not the main mission for today. I am introducing new abstractions in register allocation so as to simplify the code. That will take most of the day I imagine.