[BOLT][AArch64] The implementation of MCF algorithms in BOLT

[CHNRyan]

Hi,

I’m looking to contribute to BOLT by enhancing the accuracy of edge weight estimation for the AArch64 and RISC-V platforms. This improvement would help us obtain more accurate edge weight information in these architectures. Some research papers, such as Profile Inference Revisited and Completing Incomplete Edge Profiles by Applying Minimum Cost Circulation Algorithms, propose using min-cost flow algorithms to address this issue. However, I noticed that this approach hasn’t been implemented in BOLT, and remnants of it were recently removed (#93065).

Could you provide insights into why this approach was disabled in BOLT? Was the estimated overhead of the method too high, or were the existing data structures in BOLT insufficient to support such methods? What are the main challenges and issues in implementing this solution in BOLT?

Thank you in advance for your opinions.

[maksfb]

@rafaelauler experimented with MCF when edge profile wasn't available on AArch64. IIRC, the overhead was high and we couldn't close the performance gap with edge profiling.