Use iteration instead of recursion in CFIInserter

[sanjoy]

Summary

This recursive step can overflow the stack.

[dberris]

lib/CodeGen/CFIInstrInserter.cpp

225–228

Does this change the order of iteration here? It looks like because you're using a stack and going from the top of the stack, it's slightly different from the BFS nature of the recursion, no?

Some questions: does it matter, and if it does, maybe use a queue?

237

Consider using Stack.append(...) instead, to reduce the requirement for incrementally growing the stack?

[sanjoy]

lib/CodeGen/CFIInstrInserter.cpp

225–228

I didn't worry about this too much since no tests broke.

Having said that, I don't know if it matters. In fact I don't know this code at all. I'm hoping the original authors will chime in with any inputs.

[sanjoy]

• Use SmallVector::append

[petarj]

@violetav can you take a look?

[violetav]

Incoming offset/register values of each successor block should match outgoing offset/register values of its predecessors.

This change potentially won't set correct offset/register to indirect successors - you always set incoming values to all successors to be the outgoing values of the current block, which can turn out to be the same as outgoing values of their direct predecessor, but not necessarily. Consider this example:

# RUN: llc -o - %s -mtriple=x86_64-- -verify-cfiinstrs -run-pass=cfi-instr-inserter

--- |
  define void @foo() { ret void }
...
---
name: foo
body: |
  bb.0:
    JE_1 %bb.3, implicit $eflags
  bb.1:
    CFI_INSTRUCTION def_cfa_offset 24
  bb.2:
    CFI_INSTRUCTION def_cfa_offset 8
  bb.3:
    RET 0
...

bb2 will have incoming offset set to 8, from bb0, and not 24, from bb1.

[sanjoy]

In D46671#1094451, @violetav wrote:

Incoming offset/register values of each successor block should match outgoing offset/register values of its predecessors.

You're right, the propagation logic is wrong. I've rewritten the code to be clearer, and added the test case you mentioned.

[sanjoy]

• fix bug + test case

[violetav]

lib/CodeGen/CFIInstrInserter.cpp

250

You could add

if (SuccInfo.Processed) continue;

above this to avoid setting incoming values and pushing the block onto the stack multiple times.

294

Could you print out the function name as well? Seems it might be useful.

[violetav]

LGTM, with these few nits, thanks!

lib/CodeGen/CFIInstrInserter.cpp

#endif
   MBBInfo.Processed = true;
 
   // Update outgoing CFA info.
   MBBInfo.OutgoingCFAOffset = SetOffset;
   MBBInfo.OutgoingCFARegister = SetRegister;
 }
 
 void CFIInstrInserter::updateSuccCFAInfo(MBBCFAInfo &MBBInfo) {
-  for (MachineBasicBlock *Succ : MBBInfo.MBB->successors()) {
+  SmallVector<MachineBasicBlock *, 4> Stack(MBBInfo.MBB->successors().begin(),
+                                            MBBInfo.MBB->successors().end());
+
+  while (!Stack.empty()) {
+    MachineBasicBlock *Succ = Stack.pop_back_val();
     MBBCFAInfo &SuccInfo = MBBVector[Succ->getNumber()];
-    if (SuccInfo.Processed) continue;
+    if (SuccInfo.Processed)
+      continue;
+
     SuccInfo.IncomingCFAOffset = MBBInfo.OutgoingCFAOffset;
     SuccInfo.IncomingCFARegister = MBBInfo.OutgoingCFARegister;
     calculateOutgoingCFAInfo(SuccInfo);
-    updateSuccCFAInfo(SuccInfo);
+    llvm::copy(SuccInfo.MBB->successors(), std::back_inserter(Stack));
   }
 }
 
 bool CFIInstrInserter::insertCFIInstrs(MachineFunction &MF) {
   const MBBCFAInfo *PrevMBBInfo = &MBBVector[MF.front().getNumber()];
   const TargetInstrInfo *TII = MF.getSubtarget().getInstrInfo();
   bool InsertedCFIInstr = false;
 
   for (MachineBasicBlock &MBB : MF) {
     // Skip the first MBB in a function
     if (MBB.getNumber() == MF.front().getNumber()) continue;
 
     const MBBCFAInfo &MBBInfo = MBBVector[MBB.getNumber()];
     auto MBBI = MBBInfo.MBB->begin();
     DebugLoc DL = MBBInfo.MBB->findDebugLoc(MBBI);
 
     if (PrevMBBInfo->OutgoingCFAOffset != MBBInfo.IncomingCFAOffset) {
       // If both outgoing offset and register of a previous block don't match
       // incoming offset and register of this block, add a def_cfa instruction
       // with the correct offset and register for this block.
       if (PrevMBBInfo->OutgoingCFARegister != MBBInfo.IncomingCFARegister) {
for (MachineBasicBlock &MBB : MF) {
     PrevMBBInfo = &MBBInfo;
   }
   return InsertedCFIInstr;
 }
 
 void CFIInstrInserter::report(const MBBCFAInfo &Pred,
                               const MBBCFAInfo &Succ) {
   errs() << "*** Inconsistent CFA register and/or offset between pred and succ "
             "***\n";
   errs() << "Pred: " << Pred.MBB->getName()
          << " outgoing CFA Reg:" << Pred.OutgoingCFARegister << "\n";
   errs() << "Pred: " << Pred.MBB->getName()
          << " outgoing CFA Offset:" << Pred.OutgoingCFAOffset << "\n";
   errs() << "Succ: " << Succ.MBB->getName()
          << " incoming CFA Reg:" << Succ.IncomingCFARegister << "\n";
   errs() << "Succ: " << Succ.MBB->getName()
          << " incoming CFA Offset:" << Succ.IncomingCFAOffset << "\n";