On Sun, Dec 01, 2024 at 03:54:25PM -0700, Jeff Law wrote: > > > 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.
Kills and transparency are genuinely different bitmaps in the context of LCM. In the context of GCC terminology (I don't know whether the naming of our bitmaps is standard elsewhere) we have: - Transparency is the extension of anticipatability to entire basic blocks. - Kills is the bitwise inverse of the extension of availability to entire basic blocks. For the existing GCSE passes, where we use a brand new pseudoreg to convey computation results between original and new locations, it turns out that the local conditions for anticipatability and availability (and hence transparency and ~kills) are the same (namely that we don't change any of the inputs to the computation). The only difference is that anticipatability ranges must end at an existing instance of the computation, and availability ranges start at an existing instance of the computation. For hardreg PRE the endpoint conditions are the essentially the same, but the local conditions for anticipatability and availability surviving an instruction are now different. This is because we are directly extending the range over which the hardreg values are live, so we need extra checks to make sure these don't conflict. For availability, we only need to check that the destination hardreg hasn't been modified, but for anticipatability we also need to check that the destination hardreg hasn't been used. This is where the asymmetry between kills and transparency arises for hardreg PRE. > 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
