> On Nov 20, 2023, at 20:30, Alexander Monakov <amona...@ispras.ru> wrote: > > > 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.
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. >>> >>> 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. Thanks, -- Maxim Kuvyrkov https://www.linaro.org
