This is an archive of the discontinued LLVM Phabricator instance.

Keep call site info valid through the backend
ClosedPublic

Authored by djtodoro on Apr 24 2019, 5:21 AM.

Details

Summary

Handle call instruction replacements and deletions in order to preserve valid state of call site info of MachineFunction.

NOTE: If call site info is enabled for a new target assertion in MachineFunction::DeleteMachineInstr should help to locate places where updateCallSiteInfo() should be called in order to preserve valid state of call site info.

Authors: @asowda, @NikolaPrica, @djtodoro, @ivanbaev

Diff Detail

Event Timeline

djtodoro created this revision.Apr 24 2019, 5:21 AM
aprantl added inline comments.Apr 24 2019, 12:59 PM
include/llvm/CodeGen/MachineFunction.h
965 ↗(On Diff #196427)

I think this looks up Old twice. It may be faster to do

it = CallSitesInfo.find(Old);
val = *it; // depending on how expensive this copy is..
CallSitesInfo.erase(it)
CallSitesInfo[New] = val;
lib/CodeGen/TargetInstrInfo.cpp
150 ↗(On Diff #196427)

delete

bjope added inline comments.Apr 29 2019, 12:58 AM
lib/CodeGen/MachineFunction.cpp
364 ↗(On Diff #196427)

Afaict we do not need the isCall check for correctness here. So it seems to be some kind of compile time optimization of the assert to avoid lookups in the map.
Is it worth it to do this optimization?

This is basically the destructor for a MachineInstr (and I do not know if some parts already have been taken apart such as the decoupling this node from the ilist). Also, the code here is hidden in MachineFunction.cpp rather than MachineInstr.cpp, so doing more advanced stuff such as calling methods on the MI objects seems a little bit off, maybe even fragile. I imagine the idea is to free up memory here, as simple as possible.
Someone more experienced in LLVM and the ilist design pattern should probably review this part.

djtodoro updated this revision to Diff 199218.May 13 2019, 1:41 AM

-Add a lookup in call site info
-Rebase

NikolaPrica added inline comments.May 13 2019, 3:42 AM
lib/CodeGen/MachineFunction.cpp
364 ↗(On Diff #196427)

@bjope You are right about this compile optimizations. There are not much call instruction deletion so this is an attempt avoid search in map for all machine instruction deletions. Using isCall with IgnoreBundle query type guarantees that only node of given MI will be queried with simple isCall check.
Can you add another reviewer that could check this part?

Looks mostly good now!

include/llvm/CodeGen/MachineFunction.h
974 ↗(On Diff #201511)

Please add a comment explaining to MI pass authors when this function should be called.

lib/CodeGen/MachineFunction.cpp
366 ↗(On Diff #201511)

I think the #ifndef is redundant with the assert.

369 ↗(On Diff #201511)

"was" not updated? or "is not up-to-date"?

830 ↗(On Diff #201511)

&& " message")

834 ↗(On Diff #201511)
if (New)
   CallSitesInfo[New] = CSIt->second;
if (Old != New)
  CallSitesInfo.erase(CSIt);

?

djtodoro updated this revision to Diff 201884.May 29 2019, 5:52 AM

-Addressing suggestions

NikolaPrica added inline comments.May 29 2019, 6:22 AM
lib/CodeGen/MachineFunction.cpp
834 ↗(On Diff #201511)

CSIt is DenseMap iterator. After insertion in DenseMap all iterators get invalidated. std::map does not have such constraint. Maybe we should use std::map here?

aprantl added inline comments.May 29 2019, 4:13 PM
lib/CodeGen/MachineFunction.cpp
834 ↗(On Diff #201511)

Complexity-wise, two lookups into a DenseMap are still O(1)-ish whereas one map lookup is (log n).

NikolaPrica added inline comments.Jun 3 2019, 7:38 AM
lib/CodeGen/MachineFunction.cpp
834 ↗(On Diff #201511)

Is it fine to leave it like this now? Element deletion needs to happen before insertion, so I suppose that it is fine now?

aprantl accepted this revision.Jun 3 2019, 8:55 AM
This revision is now accepted and ready to land.Jun 3 2019, 8:55 AM
djtodoro updated this revision to Diff 203338.Jun 6 2019, 6:02 AM

-Handle a deletion in the LiveRangeEdit

NikolaPrica added inline comments.Jun 6 2019, 8:13 AM
lib/CodeGen/MachineFunction.cpp
366 ↗(On Diff #201511)

We would like to revisit this part of the code since we are aware of problems that this part might produce “possibly at some point”. At the end, this part of the code is destructor of MachineInstruction and we cannot guarantee that we handled every possible situation of a CallMI deletion. We just want to state here our dilemma and to make sure that we brought right decision. We raise this question because upper assertion is triggered when we were building 32-bit GDB exe for X86, that is now fixed.
Here we had two possibilities:

  1. Use upper assertion to verify that a call site info is at valid state. Worst-case scenario is that we will end up printing invalid MIR. Second use case for it, and most important one, is to give heads-up to other architecture developers who will try to enable this feature. For that use, it is designed to be triggered. It would give back trace that will tell where to insert a call to updateCallSiteInfo().

    The assertion gives us guarantee that it will not be triggered for things that we have tested for X86 (gdb, llvm-clang, SPEC2006, chromium, and other test cases). So we cannot say with 100% certainty that it will not be triggered at some point and that is our problem with it.
  1. To be certain that the CallSiteInfo has a valid state after the instruction deletion we would need to replace upper assertion with something like this:
if (MI->isCall(MachineInstr::IgnoreBundle)) {
  auto It = CallSitesInfo.find(MI);
  if (It != CallSitesInfo.end())
    CallSitesInfo.erase(It);
}
However, this part of code might be too much for core method like this? This is basically lowering calling of `updateCallSiteInfo()` that we tried to avoid by enabling the assertion and calling it at breakage point. If we use this code, `updateCallSiteInfo()` that is used for deleting instruction can be removed, but there is a question how to recognize situations when one call instruction is replaced with another one. Leave it be?

Having in mind that this is a core method which is frequently called we did not want to touch it much. Led by this assertion we tried to pull up handling of such situations upper in implementation. But yet, we are not quite sure that we covered all possibilities for triggering this assertion on X86.

aprantl requested changes to this revision.Jun 7 2019, 2:15 PM

(marking as "request changes", so I don't forget to reply to the question, otherwise this will get lost in my inbox)

This revision now requires changes to proceed.Jun 7 2019, 2:15 PM

Ping. Do we need to explain our concern more precisely?

aprantl accepted this revision.Jun 14 2019, 1:09 PM
aprantl added inline comments.
lib/CodeGen/MachineFunction.cpp
366 ↗(On Diff #201511)

Option 1 sounds like a good compromise to me; it wouldn't hurt to put in a more elaborate comment here that tells backend authors what they need to do when they trigger this assertion (basically what you wrote in 1.). Thanks!

This revision is now accepted and ready to land.Jun 14 2019, 1:09 PM
djtodoro updated this revision to Diff 205795.Jun 20 2019, 6:34 AM

-Rebase
-Add the comment explaining the assertion when deleting instructions

Herald added a project: Restricted Project. · View Herald TranscriptJun 20 2019, 6:34 AM

@aprantl The comment looks OK? :)

looks good!

This revision was automatically updated to reflect the committed changes.