On Sun, Jun 9, 2024 at 1:48 AM Jeff Law <jeffreya...@gmail.com> wrote:
> > > On 6/4/24 7:41 AM, Mariam Arutunian wrote: > >/Mariam, your thoughts on whether or not those two phases could handle a > > loop with two CRC calculations inside, essentially creating two calls to > > our new builtins? / > > > > / > > / > > > > It is feasible, but it would likely demand considerable effort and > > additional work to implement effectively. > Thanks for the confirmation. I suspect it likely doesn't come up often > in practice either. > > > > > >>The key would be to only simulate the use-def cycle from the loop-closed > PHI (plus the loop control of course, but miter/SCEV should be enough > there) and just replace that LC PHI, leaving loop DCE to DCE. > > > > Thank you, this is a good idea to just replace the PHI and leave the > loop to DCE to remove only single CRC parts. > It does seem like replacing the PHI when we have an optimizable case > might simplify that aspect of the implementation. > Yes. > > > > > > The current pass only verifies cases where a single CRC calculation is > performed within the loop. During the verification phase, > > I ensure that there are no other calculations aside from those necessary > for the considered CRC computation. > > > > Also, when I was investigating the bitwise CRC implementations used in > different software, in all cases the loop was calculating just one CRC and > no other calculations were done. > > Thus, in almost all cases, the first phase will filter out non-CRCs, and > during the second phase, only real CRCs with no other calculations will be > executed. > > This ensures that unnecessary statements won't be executed in most cases. > But we may have had a degree of sampling bias here. If I remember > correctly I used the initial filtering pass as the "trigger" to report a > potential CRC case. If that initial filtering pass rejected cases with > other calculations in the loop, then we never would have seen those. Yes, you used initial filtering, but in that process, I do checks with use-def chains. So, if there were separate computations not connected with each other, the initial filtering most probably wouldn't reject those. > > > > Leaving the loop to DCE will simplify the process of removing parts > connected to a single CRC calculation. > > However, since now we detect a loop that only calculates a single CRC, > we can entirely remove it at this stage without additional checks. > Let's evaluate this option as we get to the later patches in the series. > What I like about Richard's suggestion is that it "just works" and it > will continue to work, even as the overall infrastructure changes. In > contrast a bespoke loop removal implementation in a specific pass may > need adjustment if other aspects of our infrastructure change. > Ok. > > >If we really want a separate pass (or utility to work on a single > > loop) then we might consider moving some of the final value replacement > > code that doesn’t work with only SCEV there as well. There’s also > > special code in loop distribution for strlen recognition now, not > > exactly fitting in. > > > > >>Note I had patches to do final value replacement on demand from CD-DCE > when it figures a loop has no side effects besides of its reduction outputs > (still want to pick this up at some point again). > > > > Oh, this could provide useful insights for our implementation. > Are you thinking of reusing that on-demand analysis to reduce the set of > loops we analyze? > I thought its parts would be helpful in future changes of the verification algorithm. Thanks, Mariam > Jeff > >
