On Mon, 20 Nov 2023, Maxim Kuvyrkov wrote:
> > On Nov 20, 2023, at 17:52, Alexander Monakov <amona...@ispras.ru> wrote: > > > > > > On Mon, 20 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. > > > > 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? Alexander
