On 11/13/24 12:03 PM, Richard Sandiford wrote:
Andrew Carlotti <andrew.carlo...@arm.com> writes:
I think this is mostly my ignorance of the code, and would be obvious
if I tried it out locally, but: why do we need to do this after
computing the kills bitmap? For mode-switching, the kills bitmap
is the inverse of the transparency bitmap, but it sounds like here
you want the kills bitmap to be more selective.
I had to work through the entire LCM algorithm before I understood how these
bitmaps were being used (and I intend to update the documentation to make this
more obvious). In summary, the kills and avail bitmaps indicate whether the
result of an earlier expression is still available and up-to-date, whereas the
transparent and anticipatable bitmaps indicate whether a later assignment can
be moved earlier.
Right. That part is pretty standard.
For the existing hoist/PRE passes these are the same - this is because new
pseduoregs are used to hold the result of relocated computations, so the only
obstruction is if the values of the inputs to the expression are changed.
For the new hardreg PRE pass the bitmaps are different in one case - if the
content of the hardreg is used, then the result of the expression remains
available after the use, but it isn't possible to anticipate a future
assignment by moving that assignment before the earlier use.
But what I meant was: doesn't an assignment to the hard register block
movement/reuse in both directions? We can't move R:=X up through a block B
that requires R==Y (so X is not transparent in B). We also can't
reuse R:=X after a block that requires R==Y (because B kills X).
That's why I was expecting the kill set to be updated too, not just the
transparency set.
In general, yes, I would expect transparency and kill to be inverses of
each other.
I suspect (but would have to do a fair amount of archaeology to be sure)
that we probably had kills computed for some other problem (classic gcse
or const/copy propagation perhaps) and we just inverted it to work
with the LCM algorithm which wants to query transparency. Flipping
kills once into transparency seems better than using kills and having to
flip it every time we visit a block during the global propagation step.
jeff
