This is an archive of the discontinued LLVM Phabricator instance.

[DebugInfo][InstrRef] Avoid some quadratic behaviour in LiveDebugVariables

Authored by jmorse on Nov 25 2021, 5:40 AM.



This is a performance patch -- over in D94981, it was observed that LiveDebugVariables can behave quadratically if a lot of debug instructions are inserted back into the same place. We would:

  • Pick out a slot index,
  • Step through all the debug instructions after it,
  • Then insert a debug instruction there

And if you have ~10,000 debug instructions to insert in one place (which can regrettably happen with lots of inlining), this becomes expensive very quickly.

This problem affects instruction referencing too. To get around it, whenever we insert a debug instruction at a slot index, check whether there are more debug instructions to insert at this point, and insert them too. That avoids the repeated lookup and stepping through. It relies on the container for unlinked debug instructions being recorded in-order, which is how LiveDebugVariables currently does it.

Diff Detail

Event Timeline

jmorse created this revision.Nov 25 2021, 5:40 AM
jmorse requested review of this revision.Nov 25 2021, 5:40 AM
Herald added a project: Restricted Project. · View Herald TranscriptNov 25 2021, 5:40 AM
StephenTozer accepted this revision.Nov 25 2021, 7:32 AM

Looks like a plain and simple performance improvement, LGTM (one minor nit included).


Minor nit, might be worth just adding a small string here (&& "Instrs with the same slot index should be in the same MBB" or something along those lines)? Feel free to ignore if you think it's unnecessary though.

This revision is now accepted and ready to land.Nov 25 2021, 7:32 AM