Keep call site info valid through the backend

[djtodoro]

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

[aprantl]

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]

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]

-Add a lookup in call site info
-Rebase

[NikolaPrica]

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?

[djtodoro]

-Rebase

[aprantl]

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]

-Addressing suggestions

[NikolaPrica]

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]

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]

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?

[djtodoro]

-Handle a deletion in the LiveRangeEdit

[NikolaPrica]

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.

2. 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]

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

[NikolaPrica]

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

[aprantl]

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!

[djtodoro]

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

[djtodoro]

@aprantl The comment looks OK? :)

[aprantl]

looks good!

llvm/include/llvm/CodeGen/MachineFunction.h

void addCallArgsForwardingRegs(const MachineInstr *CallI,
     assert(CallI->isCall());
     CallSitesInfo[CallI] = std::move(CallInfo);
   }
 
   const CallSiteInfoMap &getCallSitesInfo() const {
     return CallSitesInfo;
   }
 
+  /// Update call sites info by deleting entry for \p Old call instruction.
+  /// If \p New is present then transfer \p Old call info to it. This function
+  /// should be called before removing call instruction or before replacing
+  /// call instruction with new one.
+  void updateCallSiteInfo(const MachineInstr *Old,
+                          const MachineInstr *New = nullptr);
 };
 
 //===--------------------------------------------------------------------===//
 // GraphTraits specializations for function basic block graphs (CFGs)
 //===--------------------------------------------------------------------===//
 
 // Provide specializations of GraphTraits to be able to treat a
 // machine function as a graph of machine basic blocks... these are

llvm/lib/CodeGen/InlineSpiller.cpp

for (MIBundleOperands MO(*MI); MO.isValid(); ++MO) {
     LIS.removePhysRegDefAt(Reg, Idx);
   }
 
   int FI;
   if (TII.isStoreToStackSlot(*MI, FI) &&
       HSpiller.rmFromMergeableSpills(*MI, FI))
     --NumSpills;
   LIS.ReplaceMachineInstrInMaps(*MI, *FoldMI);
+  if (MI->isCall())
+    MI->getMF()->updateCallSiteInfo(MI, FoldMI);
   MI->eraseFromParent();
 
   // Insert any new instructions other than FoldMI into the LIS maps.
   assert(!MIS.empty() && "Unexpected empty span of instructions!");
   for (MachineInstr &MI : MIS)
     if (&MI != FoldMI)
       LIS.InsertMachineInstrInMaps(MI);
 

llvm/lib/CodeGen/LiveRangeEdit.cpp

if (UseMI->readsWritesVirtualRegister(LI->reg, &Ops).second)
     return false;
 
   MachineInstr *FoldMI = TII.foldMemoryOperand(*UseMI, Ops, *DefMI, &LIS);
   if (!FoldMI)
     return false;
   LLVM_DEBUG(dbgs() << "                folded: " << *FoldMI);
   LIS.ReplaceMachineInstrInMaps(*UseMI, *FoldMI);
   UseMI->eraseFromParent();
+  if (UseMI->isCall())
+    UseMI->getMF()->updateCallSiteInfo(UseMI, FoldMI);
   DefMI->addRegisterDead(LI->reg, nullptr);
   Dead.push_back(DefMI);
   ++NumDCEFoldedLoads;
   return true;
 }
 
 bool LiveRangeEdit::useIsKill(const LiveInterval &LI,
                               const MachineOperand &MO) const {

llvm/lib/CodeGen/MachineFunction.cpp

 }
 
 /// Delete the given MachineInstr.
 ///
 /// This function also serves as the MachineInstr destructor - the real
 /// ~MachineInstr() destructor must be empty.
 void
 MachineFunction::DeleteMachineInstr(MachineInstr *MI) {
+  // Verify that a call site info is at valid state. This assertion should
+  // be triggered during the implementation of support for the
+  // call site info of a new architecture. If the assertion is triggered,
+  // back trace will tell where to insert a call to updateCallSiteInfo().
+  assert((!MI->isCall(MachineInstr::IgnoreBundle) ||
+          CallSitesInfo.find(MI) == CallSitesInfo.end()) &&
+         "Call site info was not updated!");
   // Strip it for parts. The operand array and the MI object itself are
   // independently recyclable.
   if (MI->Operands)
     deallocateOperandArray(MI->CapOperands, MI->Operands);
   // Don't call ~MachineInstr() which must be trivial anyway because
   // ~MachineFunction drops whole lists of MachineInstrs wihout calling their
   // destructors.
   InstructionRecycler.Deallocate(Allocator, MI);
void MachineFunction::addCodeViewHeapAllocSite(MachineInstr *I, MDNode *MD) {
   MCSymbol *EndLabel = Ctx.createTempSymbol("heapallocsite", true);
   I->setPreInstrSymbol(*this, BeginLabel);
   I->setPostInstrSymbol(*this, EndLabel);
 
   DIType *DI = dyn_cast<DIType>(MD);
   CodeViewHeapAllocSites.push_back(std::make_tuple(BeginLabel, EndLabel, DI));
 }
 
+void MachineFunction::updateCallSiteInfo(const MachineInstr *Old,
+                                         const MachineInstr *New) {
+  if (!Target.Options.EnableDebugEntryValues || Old == New)
+    return;
+
+  assert(Old->isCall() && (!New || New->isCall()) &&
+         "Call site info referes only to call instructions!");
+  CallSiteInfoMap::iterator CSIt = CallSitesInfo.find(Old);
+  if (CSIt == CallSitesInfo.end())
+    return;
+  CallSiteInfo CSInfo = std::move(CSIt->second);
+  CallSitesInfo.erase(CSIt);
+  if (New)
+    CallSitesInfo[New] = CSInfo;
+}
+
 /// \}
 
 //===----------------------------------------------------------------------===//
 //  MachineJumpTableInfo implementation
 //===----------------------------------------------------------------------===//
 
 /// Return the size of each entry in the jump table.
 unsigned MachineJumpTableInfo::getEntrySize(const DataLayout &TD) const {

llvm/lib/CodeGen/MachineOutliner.cpp

for (Candidate &C : OF.Candidates) {
 
       // If the caller tracks liveness, then we need to make sure that
       // anything we outline doesn't break liveness assumptions. The outlined
       // functions themselves currently don't track liveness, but we should
       // make sure that the ranges we yank things out of aren't wrong.
       if (MBB.getParent()->getProperties().hasProperty(
               MachineFunctionProperties::Property::TracksLiveness)) {
         // Helper lambda for adding implicit def operands to the call
-        // instruction.
-        auto CopyDefs = [&CallInst](MachineInstr &MI) {
+        // instruction. It also updates call site information for moved
+        // code.
+        auto CopyDefsAndUpdateCalls = [&CallInst](MachineInstr &MI) {
           for (MachineOperand &MOP : MI.operands()) {
             // Skip over anything that isn't a register.
             if (!MOP.isReg())
               continue;
 
             // If it's a def, add it to the call instruction.
             if (MOP.isDef())
               CallInst->addOperand(MachineOperand::CreateReg(
                   MOP.getReg(), true, /* isDef = true */
                   true /* isImp = true */));
           }
+          if (MI.isCall())
+            MI.getMF()->updateCallSiteInfo(&MI);
         };
         // Copy over the defs in the outlined range.
         // First inst in outlined range <-- Anything that's defined in this
         // ...                           .. range has to be added as an
         // implicit Last inst in outlined range  <-- def to the call
-        // instruction.
-        std::for_each(CallInst, std::next(EndIt), CopyDefs);
+        // instruction. Also remove call site information for outlined block
+        // of code.
+        std::for_each(CallInst, std::next(EndIt), CopyDefsAndUpdateCalls);
       }
 
       // Erase from the point after where the call was inserted up to, and
       // including, the final instruction in the sequence.
       // Erase needs one past the end, so we need std::next there too.
       MBB.erase(std::next(StartIt), std::next(EndIt));
 
       // Keep track of what we removed by marking them all as -1.

llvm/lib/CodeGen/PeepholeOptimizer.cpp

for (MachineBasicBlock::iterator MII = MBB.begin(), MIE = MBB.end();
                     TII->optimizeLoadInstr(*MI, MRI, FoldAsLoadDefReg, DefMI)) {
               // Update LocalMIs since we replaced MI with FoldMI and deleted
               // DefMI.
               LLVM_DEBUG(dbgs() << "Replacing: " << *MI);
               LLVM_DEBUG(dbgs() << "     With: " << *FoldMI);
               LocalMIs.erase(MI);
               LocalMIs.erase(DefMI);
               LocalMIs.insert(FoldMI);
+              if (MI->isCall())
+                MI->getMF()->updateCallSiteInfo(MI, FoldMI);
               MI->eraseFromParent();
               DefMI->eraseFromParent();
               MRI->markUsesInDebugValueAsUndef(FoldedReg);
               FoldAsLoadDefCandidates.erase(FoldedReg);
               ++NumLoadFold;
 
               // MI is replaced with FoldMI so we can continue trying to fold
               Changed = true;

llvm/lib/CodeGen/TargetInstrInfo.cpp

TargetInstrInfo::ReplaceTailWithBranchTo(MachineBasicBlock::iterator Tail,
 
   // Remove all the old successors of MBB from the CFG.
   while (!MBB->succ_empty())
     MBB->removeSuccessor(MBB->succ_begin());
 
   // Save off the debug loc before erasing the instruction.
   DebugLoc DL = Tail->getDebugLoc();
 
-  // Remove all the dead instructions from the end of MBB.
-  MBB->erase(Tail, MBB->end());
+  // Update call site info and remove all the dead instructions
+  // from the end of MBB.
+  while (Tail != MBB->end()) {
+    auto MI = Tail++;
+    if (MI->isCall())
+      MBB->getParent()->updateCallSiteInfo(&*MI);
+    MBB->erase(MI);
+  }
 
   // If MBB isn't immediately before MBB, insert a branch to it.
   if (++MachineFunction::iterator(MBB) != MachineFunction::iterator(NewDest))
     insertBranch(*MBB, NewDest, nullptr, SmallVector<MachineOperand, 0>(), DL);
   MBB->addSuccessor(NewDest);
 }
 
 MachineInstr *TargetInstrInfo::commuteInstructionImpl(MachineInstr &MI,

llvm/lib/CodeGen/XRayInstrumentation.cpp

for (auto &T : MBB.terminators()) {
         Opc = TargetOpcode::PATCHABLE_TAIL_CALL;
       }
       if (Opc != 0) {
         auto MIB = BuildMI(MBB, T, T.getDebugLoc(), TII->get(Opc))
                        .addImm(T.getOpcode());
         for (auto &MO : T.operands())
           MIB.add(MO);
         Terminators.push_back(&T);
+        if (T.isCall())
+          MF.updateCallSiteInfo(&T);
       }
     }
   }
 
   for (auto &I : Terminators)
     I->eraseFromParent();
 }
 

llvm/lib/Target/X86/X86ExpandPseudo.cpp

case X86::TCRETURNmi64: {
     } else {
       JumpTarget.setIsKill();
       BuildMI(MBB, MBBI, DL, TII->get(X86::TAILJMPr))
           .add(JumpTarget);
     }
 
     MachineInstr &NewMI = *std::prev(MBBI);
     NewMI.copyImplicitOps(*MBBI->getParent()->getParent(), *MBBI);
+    MBB.getParent()->updateCallSiteInfo(&*MBBI, &NewMI);
 
     // Delete the pseudo instruction TCRETURN.
     MBB.erase(MBBI);
 
     return true;
   }
   case X86::EH_RETURN:
   case X86::EH_RETURN64: {