Use iteration instead of recursion in CFIInserter

[sanjoy]

Summary

This recursive step can overflow the stack.

[dberris]

lib/CodeGen/CFIInstrInserter.cpp

225–228 ↗

(On Diff #146048)

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 ↗

(On Diff #146048)

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

[sanjoy]

lib/CodeGen/CFIInstrInserter.cpp

225–228 ↗

(On Diff #146048)

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

236 ↗

(On Diff #146153)

You could add

if (SuccInfo.Processed) continue;

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

295 ↗

(On Diff #146153)

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

[violetav]

LGTM, with these few nits, thanks!

llvm/trunk/lib/CodeGen/CFIInstrInserter.cpp

void CFIInstrInserter::calculateCFAInfo(MachineFunction &MF) {
   }
 
   // Set in/out cfa info for all blocks in the function. This traversal is based
   // on the assumption that the first block in the function is the entry block
   // i.e. that it has initial cfa offset and register values as incoming CFA
   // information.
   for (MachineBasicBlock &MBB : MF) {
     if (MBBVector[MBB.getNumber()].Processed) continue;
-    calculateOutgoingCFAInfo(MBBVector[MBB.getNumber()]);
     updateSuccCFAInfo(MBBVector[MBB.getNumber()]);
   }
 }
 
 void CFIInstrInserter::calculateOutgoingCFAInfo(MBBCFAInfo &MBBInfo) {
   // Outgoing cfa offset set by the block.
   int SetOffset = MBBInfo.IncomingCFAOffset;
   // Outgoing cfa register set by the block.
#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;
+  Stack.push_back(MBBInfo.MBB);
+
+  do {
+    MachineBasicBlock *Current = Stack.pop_back_val();
+    MBBCFAInfo &CurrentInfo = MBBVector[Current->getNumber()];
+    if (CurrentInfo.Processed)
+      continue;
+
+    calculateOutgoingCFAInfo(CurrentInfo);
+    for (auto *Succ : CurrentInfo.MBB->successors()) {
       MBBCFAInfo &SuccInfo = MBBVector[Succ->getNumber()];
-    if (SuccInfo.Processed) continue;
-    SuccInfo.IncomingCFAOffset = MBBInfo.OutgoingCFAOffset;
-    SuccInfo.IncomingCFARegister = MBBInfo.OutgoingCFARegister;
-    calculateOutgoingCFAInfo(SuccInfo);
-    updateSuccCFAInfo(SuccInfo);
+      if (!SuccInfo.Processed) {
+        SuccInfo.IncomingCFAOffset = CurrentInfo.OutgoingCFAOffset;
+        SuccInfo.IncomingCFARegister = CurrentInfo.OutgoingCFARegister;
+        Stack.push_back(Succ);
+      }
     }
+  } while (!Stack.empty());
 }
 
 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) {
if (PrevMBBInfo->OutgoingCFAOffset != MBBInfo.IncomingCFAOffset) {
           .addCFIIndex(CFIIndex);
       InsertedCFIInstr = true;
     }
     PrevMBBInfo = &MBBInfo;
   }
   return InsertedCFIInstr;
 }
 
-void CFIInstrInserter::report(const MBBCFAInfo &Pred,
-                              const MBBCFAInfo &Succ) {
+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()
+  errs() << "Pred: " << Pred.MBB->getName() << " #" << Pred.MBB->getNumber()
+         << " in " << Pred.MBB->getParent()->getName()
          << " outgoing CFA Reg:" << Pred.OutgoingCFARegister << "\n";
-  errs() << "Pred: " << Pred.MBB->getName()
+  errs() << "Pred: " << Pred.MBB->getName() << " #" << Pred.MBB->getNumber()
+         << " in " << Pred.MBB->getParent()->getName()
          << " outgoing CFA Offset:" << Pred.OutgoingCFAOffset << "\n";
-  errs() << "Succ: " << Succ.MBB->getName()
+  errs() << "Succ: " << Succ.MBB->getName() << " #" << Succ.MBB->getNumber()
          << " incoming CFA Reg:" << Succ.IncomingCFARegister << "\n";
-  errs() << "Succ: " << Succ.MBB->getName()
+  errs() << "Succ: " << Succ.MBB->getName() << " #" << Succ.MBB->getNumber()
          << " incoming CFA Offset:" << Succ.IncomingCFAOffset << "\n";
 }
 
 unsigned CFIInstrInserter::verify(MachineFunction &MF) {
   unsigned ErrorNum = 0;
   for (auto *CurrMBB : depth_first(&MF)) {
     const MBBCFAInfo &CurrMBBInfo = MBBVector[CurrMBB->getNumber()];
     for (MachineBasicBlock *Succ : CurrMBB->successors()) {

llvm/trunk/test/CodeGen/X86/cfi-inserter-cfg-with-merge.mir

+# 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
+...