This is an archive of the discontinued LLVM Phabricator instance.

[RegisterCoalescer] Limit the number of joins for large live interval with many valnos.
ClosedPublic

Authored by wmi on Mar 8 2019, 10:31 AM.

Details

Summary

Recently we found compile time out problem in several cases when SpeculativeLoadHardening was enabled. The significant compile time was spent in register coalescing pass, where register coalescer tried to join many other live intervals with some very large live intervals with many valnos.

Specifically, every time JoinVals::mapValues is called, computeAssignment will be called by getNumValNums() times of the target live interval. If the large live interval has N valnos and has N copies associated with it, trying to coalescing those copies will at least cost N^2 complexity.

The patch adds some limit to the effort trying to join those very large live intervals with others. By default, for live interval with > 100 valnos, and when it has been coalesced with other live interval by more than 100 times, we will stop coalescing for the live interval anymore. That put a compile time cap for the N^2 algorithm and effectively solves the compile time problem we saw.

Diff Detail

Repository
rL LLVM

Event Timeline

wmi created this revision.Mar 8 2019, 10:31 AM
Herald added a project: Restricted Project. · View Herald TranscriptMar 8 2019, 10:31 AM
Herald added subscribers: jdoerfert, tpr. · View Herald Transcript
qcolombet accepted this revision.Mar 8 2019, 10:38 AM

Looks reasonable to me.

lib/CodeGen/RegisterCoalescer.cpp
216 ↗(On Diff #189878)

Maybe add that the high cost means will significantly impact compile time.

This revision is now accepted and ready to land.Mar 8 2019, 10:38 AM
wmi marked an inline comment as done.Mar 8 2019, 10:46 AM

Thanks for the fast response!

lib/CodeGen/RegisterCoalescer.cpp
216 ↗(On Diff #189878)

Done.

This revision was automatically updated to reflect the committed changes.
chandlerc added inline comments.
llvm/trunk/lib/CodeGen/RegisterCoalescer.cpp
3280–3281

This does the lookup in the hashtable twice, instead bind it to a reference?

wmi marked an inline comment as done.Mar 8 2019, 3:34 PM
wmi added inline comments.
llvm/trunk/lib/CodeGen/RegisterCoalescer.cpp
3280–3281

Fixed in rL355757 and rL355759. Thanks!