Infinite loop in MLGO regalloc advisor

[pirama-arumuga-nainar]

See reproducer at https://drive.google.com/file/d/1sdznuNjRXXl2whBczMhL0OpLlLVzXBRP/view?usp=sharing. (NB: the reproducer uses ThinLTO and was built against 99d0780)

The above reproducer hangs when building ToT LLVM with Android's regalloc models. (I haven't been able to build with official MLGO-released-models yet).

cc: @mtrofin @kongy

[mtrofin]

@boomanaiden154 ptal?

[boomanaiden154]

Do you have more detailed repro instructions? I'm struggling to see what to do with that zip folder. A BC file and ThinLTO backend invocation would be ideal, but a zip/lld command line would work too.

We saw issues like this recently on some server binaries, but fixed those by adding a threshold in 60325ab. In those cases, the compilation would eventually terminate, it just took an exceedingly long time.

[pirama-arumuga-nainar]

This is actually a lld repro file. Google Drive displays the contents of the tar file. You can download the b389543884_reprod.tar, extract it and run ld.lld @response.txt.

[kongy]

In those cases, the compilation would eventually terminate, it just took an exceedingly long time.

Yes, in this case, it eventually finished after ~4 hours.

[boomanaiden154]

I can reproduce this, and this definitely seems related to the threshold I introduced recently. Running with -mllvm -mlregalloc-max-cascade=999999 (or some other really high number) makes the issue go away and the reproducer compiles on my machine in about 30 seconds or so. Setting it to something lower like 10, or leaving the default of 20 requires a huge amount of compile time.

Not entirely sure why this is occurring, but I'll be digging. It could be an interaction with live range splitting and thus we hit the urgent case most of the time, but I wouldn't necessarily expect those patches to then increase compile time...

[boomanaiden154]

It seems like this is due primarily due to the creation of a ton of new eviction instances where none of the non-candidate LRs are evictable given the new logic setting a maximum cascade for a LR to be considered for eviction. I'm realizing now that the cascade number is also an incredibly poor approximation for how many times a LR has been evicted. I think manually keeping track of how many times a specific LR has been evicted inside MLRegAllocEvictionAdvisor would make the most sense. Will get that implemented and see how it works.