On Tue, 21 Nov 2023, Maxim Kuvyrkov wrote:
> >>>> This patch avoids sched-deps.cc:find_inc() creating exponential number > >>>> of dependencies, which become memory and compilation time hogs. > >>>> Consider example (simplified from PR96388) ... > >>>> === > >>>> sp=sp-4 // sp_insnA > >>>> mem_insnA1[sp+A1] > >>>> ... > >>>> mem_insnAN[sp+AN] > >>>> sp=sp-4 // sp_insnB > >>>> mem_insnB1[sp+B1] > >>>> ... > >>>> mem_insnBM[sp+BM] > >>>> === > >>>> ... in this example find_modifiable_mems() will arrange for mem_insnA* > >>>> to be able to pass sp_insnA, and, while doing this, will create > >>>> dependencies between all mem_insnA*s and sp_insnB -- because sp_insnB > >>>> is a consumer of sp_insnA. After this sp_insnB will have N new > >>>> backward dependencies. > >>>> Then find_modifiable_mems() gets to mem_insnB*s and starts to create > >>>> N new dependencies for _every_ mem_insnB*. This gets us N*M new > >>>> dependencies. > >> > >> [For avoidance of doubt, below discussion is about the general > >> implementation > >> of find_modifiable_mems() and not about the patch.] > > > > I was saying the commit message is hard to read (unless it's just me). > > > >>> It's a bit hard to read this without knowing which value of 'backwards' > >>> is assumed. > > Oh, sorry, I misunderstood your comment. > > In the above example I want to describe outcome that current code generates, > without going into details about exactly how it does it. I'm not sure how to > make it more readable, and would appreciate suggestions. I think it would be easier to follow if you could fix a specific value of 'backwards' up front, and then ensure all following statements are consistent with that, like I did in my explanation. Please feel free to pick up my text into the commit message, if it helps. > >>> Say 'backwards' is true and we are inspecting producer sp_insnB of > >>> mem_insnB1. > >>> This is a true dependency. We know we can break it by adjusting B1 by -4, > >>> but > >>> we need to be careful not to move such modified mem_insnB1 above > >>> sp_insnA, so > >>> we need to iterate over *incoming true dependencies* of sp_insnB and add > >>> them. > >>> > >>> But the code seems to be iterating over *all incoming dependencies*, so it > >>> will e.g. take anti-dependency mem_insnA1 -> sp_insnB and create a true > >>> dependency mem_insnA1 -> mem_insnB1'. This seems utterly inefficient, if > >>> my > >>> understanding is correct. > >> > >> Yeap, your understanding is correct. However, this is what > >> find_modifiable_mems() has to do to avoid complicated analysis of > >> second-level > >> dependencies. > > > > What is the reason it cannot simply skip anti-dependencies in the > > 'if (backwards)' loop, and true dependencies in the 'else' loop? > > I /think/, this should be possible. However, rather than improving current > implementation my preference is to rework it by integrating with the main > dependency analysis. This should provide both faster and more precise > dependency analysis, which would generate breakable addr/mem dependencies. I see, thank you. Alexander
