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. 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. Alexander
