[AArch64][BOLT] llvm-bolt annotateCFIState Assertion `!StateStack.empty() && "corrupt CFI stack"' failed.

[ilinpv]

BOLT version: af15027 crashes on MySQL binary:
llvm-bolt mysqld -o mysqld-bolt -instrument --print-disasm -v 1 > mysqld.disasm

...
BOLT-WARNING: failed to post-process indirect branches for _ZL13get_next_timePK9Time_zonePllli13interval_type/1(*2)
BOLT-WARNING: failed to post-process indirect branches for _ZN24Field_iterator_table_ref13end_of_fieldsEv/1(*2)
BOLT-WARNING: failed to post-process indirect branches for _ZN16Event_parse_data13init_intervalEP3THD
llvm-bolt: llvm-project/bolt/lib/Core/BinaryFunction.cpp:2652: void llvm::bolt::BinaryFunction::annotateCFIState(): Assertion `!StateStack.empty() && "corrupt CFI stack"' failed.

Presumably that was caused by incorrect remember-restore CFI sequences in the binary.

[llvmbot]

@llvm/issue-subscribers-bolt

Author: Pavel Iliin (ilinpv)

BOLT version: af15027 crashes on [MySQL binary](https://github.com/ilinpv/bolt-tests/raw/0403b9cfe9e9c150fb523122f9962daa1b2150f2/test/AArch64/Inputs/mysqld.zst): `llvm-bolt mysqld -o mysqld-bolt -instrument --print-disasm -v 1 > mysqld.disasm` ``` ... BOLT-WARNING: failed to post-process indirect branches for _ZL13get_next_timePK9Time_zonePllli13interval_type/1(*2) BOLT-WARNING: failed to post-process indirect branches for _ZN24Field_iterator_table_ref13end_of_fieldsEv/1(*2) BOLT-WARNING: failed to post-process indirect branches for _ZN16Event_parse_data13init_intervalEP3THD llvm-bolt: llvm-project/bolt/lib/Core/BinaryFunction.cpp:2652: void llvm::bolt::BinaryFunction::annotateCFIState(): Assertion `!StateStack.empty() && "corrupt CFI stack"' failed. ``` Presumably that was caused by incorrect remember-restore CFI sequences in the binary.

[bgergely0]

Hi! I have pushed a workaround patch for this, you can find it in the linked PR.

[momchil-velikov]

I had a look at this issue.

First let's determine which is the interesting function with this patch:

diff --git a/bolt/lib/Core/BinaryFunction.cpp b/bolt/lib/Core/BinaryFunction.cpp
index 838555157609..c1ff7a730b40 100644
--- a/bolt/lib/Core/BinaryFunction.cpp
+++ b/bolt/lib/Core/BinaryFunction.cpp
@@ -2530,6 +2530,8 @@ void BinaryFunction::annotateCFIState() {
         EffectiveState = State;
         break;
       case MCCFIInstruction::OpRestoreState:
+        if (StateStack.empty())
+          dbgs() << "Failure in function at address: " << format("%x\n", getAddress());
         assert(!StateStack.empty() && "corrupt CFI stack");
         EffectiveState = StateStack.top();
         StateStack.pop();

Running that on the supplied mysqld yields:

chill@morgoth release % ./bin/llvm-bolt mysqld -o mysqld-bolt -instrument 
...
Failure in function at address: 23bd340
...

Let's disasemble the function and dump the unwind info:

chill@morgoth release % ./bin/llvm-objdump -d mysqld > x.txt   
chill@morgoth release % ./bin/llvm-readelf --unwind mysqld > u.txt

Extracting just the relevant parts yields:

00000000023bd340 <_ZNK5boost8geometry6detail7overlay15side_calculatorINS1_9get_turns29unique_sub_range_from_sectionILb1ENS0_7sectionINS0_5model3boxIN3gis15Cartesian_pointEEELm2EEESA_NS0_22ever_circling_iteratorIN9__gnu_cxx17__normal_iteratorIPKSA_St6vectorISA_16Malloc_allocatorISA_EEEEEENS0_10strategies6relate9cartesianIvEENS1_17no_rescale_policyEEENS5_ILb1ESC_SA_NSD_INS_9iterators16reverse_iteratorISM_EEEESR_SS_EESR_E9pj_wrt_q1Ev>:
 23bd340: d2e7fe09     	mov	x9, #0x3ff0000000000000 // =4607182418800017408
 23bd344: aa0003e8     	mov	x8, x0
 23bd348: a9bf27fe     	stp	x30, x9, [sp, #-0x10]!
 23bd34c: 910023e3     	add	x3, sp, #0x8
 23bd350: aa0103e0     	mov	x0, x1
 23bd354: aa0203e1     	mov	x1, x2
 23bd358: aa0803e2     	mov	x2, x8
 23bd35c: 97fc2ab9     	bl	0x22c7e40 <_ZN5boost8geometry8strategy4side16side_by_triangleIvE18compute_side_valueIddLb0EE5applyIN3gis15Cartesian_pointES9_S9_NS4_10eps_policyINS0_4math6detail20equals_factor_policyIdLb1EEEEEEEdRKT_RKT0_RKT1_RT2_>
 23bd360: 1e602008     	fcmp	d0, #0.0
 23bd364: 54000081     	b.ne	0x23bd374 <_ZNK5boost8geometry6detail7overlay15side_calculatorINS1_9get_turns29unique_sub_range_from_sectionILb1ENS0_7sectionINS0_5model3boxIN3gis15Cartesian_pointEEELm2EEESA_NS0_22ever_circling_iteratorIN9__gnu_cxx17__normal_iteratorIPKSA_St6vectorISA_16Malloc_allocatorISA_EEEEEENS0_10strategies6relate9cartesianIvEENS1_17no_rescale_policyEEENS5_ILb1ESC_SA_NSD_INS_9iterators16reverse_iteratorISM_EEEESR_SS_EESR_E9pj_wrt_q1Ev+0x34>
 23bd368: 2a1f03e0     	mov	w0, wzr
 23bd36c: f84107fe     	ldr	x30, [sp], #0x10
 23bd370: d65f03c0     	ret
 23bd374: 9e660008     	fmov	x8, d0
 23bd378: d2effe09     	mov	x9, #0x7ff0000000000000 // =9218868437227405312
 23bd37c: 9240f908     	and	x8, x8, #0x7fffffffffffffff
 23bd380: eb09011f     	cmp	x8, x9
 23bd384: 540000cb     	b.lt	0x23bd39c <_ZNK5boost8geometry6detail7overlay15side_calculatorINS1_9get_turns29unique_sub_range_from_sectionILb1ENS0_7sectionINS0_5model3boxIN3gis15Cartesian_pointEEELm2EEESA_NS0_22ever_circling_iteratorIN9__gnu_cxx17__normal_iteratorIPKSA_St6vectorISA_16Malloc_allocatorISA_EEEEEENS0_10strategies6relate9cartesianIvEENS1_17no_rescale_policyEEENS5_ILb1ESC_SA_NSD_INS_9iterators16reverse_iteratorISM_EEEESR_SS_EESR_E9pj_wrt_q1Ev+0x5c>
 23bd388: 1e602008     	fcmp	d0, #0.0
 23bd38c: 12800008     	mov	w8, #-0x1               // =-1
 23bd390: 1a9fd500     	csinc	w0, w8, wzr, le
 23bd394: f84107fe     	ldr	x30, [sp], #0x10
 23bd398: d65f03c0     	ret
 23bd39c: fd4007e2     	ldr	d2, [sp, #0x8]
 23bd3a0: d2e79608     	mov	x8, #0x3cb0000000000000 // =4372995238176751616
 23bd3a4: 1e60c001     	fabs	d1, d0
 23bd3a8: 1e602008     	fcmp	d0, #0.0
 23bd3ac: 9e670103     	fmov	d3, x8
 23bd3b0: 12800008     	mov	w8, #-0x1               // =-1
 23bd3b4: 1a9fd500     	csinc	w0, w8, wzr, le
 23bd3b8: 1e630842     	fmul	d2, d2, d3
 23bd3bc: 1e622020     	fcmp	d1, d2
 23bd3c0: 54fffd49     	b.ls	0x23bd368 <_ZNK5boost8geometry6detail7overlay15side_calculatorINS1_9get_turns29unique_sub_range_from_sectionILb1ENS0_7sectionINS0_5model3boxIN3gis15Cartesian_pointEEELm2EEESA_NS0_22ever_circling_iteratorIN9__gnu_cxx17__normal_iteratorIPKSA_St6vectorISA_16Malloc_allocatorISA_EEEEEENS0_10strategies6relate9cartesianIvEENS1_17no_rescale_policyEEENS5_ILb1ESC_SA_NSD_INS_9iterators16reverse_iteratorISM_EEEESR_SS_EESR_E9pj_wrt_q1Ev+0x28>
 23bd3c4: 17ffffea     	b	0x23bd36c <_ZNK5boost8geometry6detail7overlay15side_calculatorINS1_9get_turns29unique_sub_range_from_sectionILb1ENS0_7sectionINS0_5model3boxIN3gis15Cartesian_pointEEELm2EEESA_NS0_22ever_circling_iteratorIN9__gnu_cxx17__normal_iteratorIPKSA_St6vectorISA_16Malloc_allocatorISA_EEEEEENS0_10strategies6relate9cartesianIvEENS1_17no_rescale_policyEEENS5_ILb1ESC_SA_NSD_INS_9iterators16reverse_iteratorISM_EEEESR_SS_EESR_E9pj_wrt_q1Ev+0x2c>



  [0x164e8b4] FDE length=32 cie=[0x15bcaac]
    initial_location: 0x23bd340
    address_range: 0x88 (end : 0x23bd3c8)

    Program:
      DW_CFA_def_cfa_offset: +16
      DW_CFA_offset: reg30 -16
      DW_CFA_remember_state:
      DW_CFA_advance_loc: 48 to 0x23bd370
      DW_CFA_def_cfa_offset: +0
      DW_CFA_restore: reg30
      DW_CFA_advance_loc: 4 to 0x23bd374
      DW_CFA_restore_state:
      DW_CFA_remember_state:
      DW_CFA_advance_loc: 36 to 0x23bd398
      DW_CFA_def_cfa_offset: +0
      DW_CFA_restore: reg30
      DW_CFA_advance_loc: 4 to 0x23bd39c
      DW_CFA_restore_state:
      DW_CFA_nop:

Note that restore/remember state are matched (which is not even neccessary as long as the stack does not underflow).
Furthermore, manually interleaving that unwind information into the dissasembly produces a result that looks correct.

00000000023bd340 <_ZNK5boost8geometry6detail7overlay15side_calculatorINS1_9get_turns29unique_sub_range_from_sectionILb1ENS0_7sectionINS0_5model3boxIN3gis15Cartesian_pointEEELm2EEESA_NS0_22ever_circling_iteratorIN9__gnu_cxx17__normal_iteratorIPKSA_St6vectorISA_16Malloc_allocatorISA_EEEEEENS0_10strategies6relate9cartesianIvEENS1_17no_rescale_policyEEENS5_ILb1ESC_SA_NSD_INS_9iterators16reverse_iteratorISM_EEEESR_SS_EESR_E9pj_wrt_q1Ev>:

      DW_CFA_def_cfa_offset: +16
      DW_CFA_offset: reg30 -16
      DW_CFA_remember_state:


 23bd340: d2e7fe09     	mov	x9, #0x3ff0000000000000 // =4607182418800017408
 23bd344: aa0003e8     	mov	x8, x0
 23bd348: a9bf27fe     	stp	x30, x9, [sp, #-0x10]!
 23bd34c: 910023e3     	add	x3, sp, #0x8
 23bd350: aa0103e0     	mov	x0, x1
 23bd354: aa0203e1     	mov	x1, x2
 23bd358: aa0803e2     	mov	x2, x8
 23bd35c: 97fc2ab9     	bl	0x22c7e40 <_ZN5boost8geometry8strategy4side16side_by_triangleIvE18compute_side_valueIddLb0EE5applyIN3gis15Cartesian_pointES9_S9_NS4_10eps_policyINS0_4math6detail20equals_factor_policyIdLb1EEEEEEEdRKT_RKT0_RKT1_RT2_>
 23bd360: 1e602008     	fcmp	d0, #0.0
 23bd364: 54000081     	b.ne	0x23bd374 <_ZNK5boost8geometry6detail7overlay15side_calculatorINS1_9get_turns29unique_sub_range_from_sectionILb1ENS0_7sectionINS0_5model3boxIN3gis15Cartesian_pointEEELm2EEESA_NS0_22ever_circling_iteratorIN9__gnu_cxx17__normal_iteratorIPKSA_St6vectorISA_16Malloc_allocatorISA_EEEEEENS0_10strategies6relate9cartesianIvEENS1_17no_rescale_policyEEENS5_ILb1ESC_SA_NSD_INS_9iterators16reverse_iteratorISM_EEEESR_SS_EESR_E9pj_wrt_q1Ev+0x34>
 23bd368: 2a1f03e0     	mov	w0, wzr
 23bd36c: f84107fe     	ldr	x30, [sp], #0x10

      DW_CFA_def_cfa_offset: +0
      DW_CFA_restore: reg30

 23bd370: d65f03c0     	ret

      DW_CFA_restore_state:
      DW_CFA_remember_state:

 23bd374: 9e660008     	fmov	x8, d0
 23bd378: d2effe09     	mov	x9, #0x7ff0000000000000 // =9218868437227405312
 23bd37c: 9240f908     	and	x8, x8, #0x7fffffffffffffff
 23bd380: eb09011f     	cmp	x8, x9
 23bd384: 540000cb     	b.lt	0x23bd39c <_ZNK5boost8geometry6detail7overlay15side_calculatorINS1_9get_turns29unique_sub_range_from_sectionILb1ENS0_7sectionINS0_5model3boxIN3gis15Cartesian_pointEEELm2EEESA_NS0_22ever_circling_iteratorIN9__gnu_cxx17__normal_iteratorIPKSA_St6vectorISA_16Malloc_allocatorISA_EEEEEENS0_10strategies6relate9cartesianIvEENS1_17no_rescale_policyEEENS5_ILb1ESC_SA_NSD_INS_9iterators16reverse_iteratorISM_EEEESR_SS_EESR_E9pj_wrt_q1Ev+0x5c>
 23bd388: 1e602008     	fcmp	d0, #0.0
 23bd38c: 12800008     	mov	w8, #-0x1               // =-1
 23bd390: 1a9fd500     	csinc	w0, w8, wzr, le
 23bd394: f84107fe     	ldr	x30, [sp], #0x10
      DW_CFA_def_cfa_offset: +0
      DW_CFA_restore: reg30

 23bd398: d65f03c0     	ret

      DW_CFA_restore_state:
      DW_CFA_nop:

 23bd39c: fd4007e2     	ldr	d2, [sp, #0x8]
 23bd3a0: d2e79608     	mov	x8, #0x3cb0000000000000 // =4372995238176751616
 23bd3a4: 1e60c001     	fabs	d1, d0
 23bd3a8: 1e602008     	fcmp	d0, #0.0
 23bd3ac: 9e670103     	fmov	d3, x8
 23bd3b0: 12800008     	mov	w8, #-0x1               // =-1
 23bd3b4: 1a9fd500     	csinc	w0, w8, wzr, le
 23bd3b8: 1e630842     	fmul	d2, d2, d3
 23bd3bc: 1e622020     	fcmp	d1, d2
 23bd3c0: 54fffd49     	b.ls	0x23bd368 <_ZNK5boost8geometry6detail7overlay15side_calculatorINS1_9get_turns29unique_sub_range_from_sectionILb1ENS0_7sectionINS0_5model3boxIN3gis15Cartesian_pointEEELm2EEESA_NS0_22ever_circling_iteratorIN9__gnu_cxx17__normal_iteratorIPKSA_St6vectorISA_16Malloc_allocatorISA_EEEEEENS0_10strategies6relate9cartesianIvEENS1_17no_rescale_policyEEENS5_ILb1ESC_SA_NSD_INS_9iterators16reverse_iteratorISM_EEEESR_SS_EESR_E9pj_wrt_q1Ev+0x28>
 23bd3c4: 17ffffea     	b	0x23bd36c <_ZNK5boost8geometry6detail7overlay15side_calculatorINS1_9get_turns29unique_sub_range_from_sectionILb1ENS0_7sectionINS0_5model3boxIN3gis15Cartesian_pointEEELm2EEESA_NS0_22ever_circling_iteratorIN9__gnu_cxx17__normal_iteratorIPKSA_St6vectorISA_16Malloc_allocatorISA_EEEEEENS0_10strategies6relate9cartesianIvEENS1_17no_rescale_policyEEENS5_ILb1ESC_SA_NSD_INS_9iterators16reverse_iteratorISM_EEEESR_SS_EESR_E9pj_wrt_q1Ev+0x2c>

OK, that's how it should look like, let's see what's BOLT's idea by dumping each instruction of the affected
function using this patch:

diff --git a/bolt/lib/Core/BinaryFunction.cpp b/bolt/lib/Core/BinaryFunction.cpp
index 838555157609..cab3b91b16ec 100644
--- a/bolt/lib/Core/BinaryFunction.cpp
+++ b/bolt/lib/Core/BinaryFunction.cpp
@@ -2514,10 +2514,16 @@ void BinaryFunction::annotateCFIState() {
   // For tracking RememberState/RestoreState sequences.
   std::stack<uint32_t> StateStack;
 
+  const bool debugFlag = getAddress() == 0x23bd340;
+
   for (BinaryBasicBlock *BB : BasicBlocks) {
     BB->setCFIState(EffectiveState);
 
     for (const MCInst &Instr : *BB) {
+
+      if (debugFlag)
+        Instr.dump();
+
       const MCCFIInstruction *CFI = getCFIFor(Instr);
       if (!CFI)
         continue;

We get this:

chill@morgoth release % ./bin/llvm-bolt mysqld -o mysqld-bolt -instrument
...
<MCInst 5248 <MCOperand Reg:248> <MCOperand Imm:16368> <MCOperand Imm:48>>
<MCInst 5341 <MCOperand Reg:247> <MCOperand Reg:14> <MCOperand Reg:239> <MCOperand Imm:0>>
<MCInst 7315 <MCOperand Reg:8> <MCOperand Reg:6> <MCOperand Reg:248> <MCOperand Reg:8> <MCOperand Imm:-2>>
<MCInst 1513 <MCOperand Reg:242> <MCOperand Reg:8> <MCOperand Imm:8> <MCOperand Imm:0>>
<MCInst 5341 <MCOperand Reg:239> <MCOperand Reg:14> <MCOperand Reg:240> <MCOperand Imm:0>>
<MCInst 5341 <MCOperand Reg:240> <MCOperand Reg:14> <MCOperand Reg:241> <MCOperand Imm:0>>
<MCInst 5341 <MCOperand Reg:241> <MCOperand Reg:14> <MCOperand Reg:247> <MCOperand Imm:0>>
<MCInst 1855 <MCOperand Expr:(_ZN5boost8geometry8strategy4side16side_by_triangleIvE18compute_side_valueIddLb0EE5applyIN3gis15Cartesian_pointES9_S9_NS4_10eps_policyINS0_4math6detail20equals_factor_policyIdLb1EEEEEEEdRKT_RKT0_RKT1_RT2_/1)> <MCOperand Inst:(NULL)> <MCOperand Imm:432345564227567644>>
<MCInst 2769 <MCOperand Reg:48>>
<MCInst 1888 <MCOperand Imm:1> <MCOperand Expr:(.Ltmp213030)> <MCOperand Inst:(NULL)> <MCOperand Imm:432345564227567652>>
<MCInst 5339 <MCOperand Reg:208> <MCOperand Reg:12> <MCOperand Reg:12> <MCOperand Imm:0> <MCOperand Inst:(NULL)> <MCOperand Imm:432345564227567656>>
<MCInst 4869 <MCOperand Reg:8> <MCOperand Reg:6> <MCOperand Reg:8> <MCOperand Imm:16>>
<MCInst 3 <MCOperand Imm:0>>
<MCInst 3 <MCOperand Imm:1>>
<MCInst 5573 <MCOperand Reg:6> <MCOperand Inst:(NULL)> <MCOperand Imm:432345564227567664>>
<MCInst 3 <MCOperand Imm:2>>

*** CRASH HERE **

As this is not very pretty, let's add some annotations:

mov x9, ...  : <MCInst 5248 <MCOperand Reg:248> <MCOperand Imm:16368> <MCOperand Imm:48>>
mov x8, ...  : <MCInst 5341 <MCOperand Reg:247> <MCOperand Reg:14> <MCOperand Reg:239> <MCOperand Imm:0>>
stp x30, ... : <MCInst 7315 <MCOperand Reg:8> <MCOperand Reg:6> <MCOperand Reg:248> <MCOperand Reg:8> <MCOperand Imm:-2>>
add x3, ...  : <MCInst 1513 <MCOperand Reg:242> <MCOperand Reg:8> <MCOperand Imm:8> <MCOperand Imm:0>>
mov x0, ...  : <MCInst 5341 <MCOperand Reg:239> <MCOperand Reg:14> <MCOperand Reg:240> <MCOperand Imm:0>>
mov x1, ...  : <MCInst 5341 <MCOperand Reg:240> <MCOperand Reg:14> <MCOperand Reg:241> <MCOperand Imm:0>>
mov x2, ...  : <MCInst 5341 <MCOperand Reg:241> <MCOperand Reg:14> <MCOperand Reg:247> <MCOperand Imm:0>>
bl ...       : <MCInst 1855  ...
fcmp d0, ... : <MCInst 2769 <MCOperand Reg:48>>
b.ne ...     : <MCInst 1888 <MCOperand Imm:1> <MCOperand Expr:(.Ltmp213030)> <MCOperand Inst:(NULL)> <MCOperand Imm:432345564227567652>>
mov w0, ...  : <MCInst 5339 <MCOperand Reg:208> <MCOperand Reg:12> <MCOperand Reg:12> <MCOperand Imm:0> <MCOperand Inst:(NULL)> <MCOperand Imm:432345564227567656>>
ldr x30, ... : <MCInst 4869 <MCOperand Reg:8> <MCOperand Reg:6> <MCOperand Reg:8> <MCOperand Imm:16>>

DW_CFA_def_cfa_offset: +0 : <MCInst 3 <MCOperand Imm:0>>
DW_CFA_restore: reg30     : <MCInst 3 <MCOperand Imm:1>>

ret : <MCInst 5573 <MCOperand Reg:6> <MCOperand Inst:(NULL)> <MCOperand Imm:432345564227567664>>

DW_CFA_restore_state: <MCInst 3 <MCOperand Imm:2>>

*** CRASH HERE ***

So, we crash just after seeing DW_CFA_restore_state, which is not at all surprising
given BOLT has not seen at all the first three CFI instructions, namely:

      DW_CFA_def_cfa_offset: +16
      DW_CFA_offset: reg30 -16
      DW_CFA_remember_state:

In conclusion, there's no evidence that the input binary is faulty and investigation ought to
figure out why BOLT does not take the first three CFI instructions.

One not very common thing with unwind informaton for this function is that it does not start
with DW_CFA_advance_loc (which is not a requiremnt AFAIK).

[Asher8118]

Started looking into this issue.
We know BOLT is not reading all CFI instructions. As Momchil pointed out, the first DW_CFA_remember_state from below is ignored :

0x164e8b4] FDE length=32 cie=[0x15bcaac]
    initial_location: 0x23bd340
    address_range: 0x88 (end : 0x23bd3c8)
    
    Program:
      DW_CFA_def_cfa_offset: +16
      DW_CFA_offset: reg30 -16
      DW_CFA_remember_state:
      DW_CFA_advance_loc: 48 to 0x23bd370
      DW_CFA_def_cfa_offset: +0
      DW_CFA_restore: reg30
      DW_CFA_advance_loc: 4 to 0x23bd374
      DW_CFA_restore_state:
      DW_CFA_remember_state:
      DW_CFA_advance_loc: 36 to 0x23bd398
      DW_CFA_def_cfa_offset: +0
      DW_CFA_restore: reg30
      DW_CFA_advance_loc: 4 to 0x23bd39c
      DW_CFA_restore_state:
      DW_CFA_nop:

This causes the assertion failure, as we're trying to pop from the stack when it's empty:

case MCCFIInstruction::OpRememberState:
        StateStack.push(EffectiveState);
        EffectiveState = State;
        break;
case MCCFIInstruction::OpRestoreState:
        assert(!StateStack.empty() && "corrupt CFI stack");
        EffectiveState = StateStack.top();
        StateStack.pop();
        break;

The approach I'm pursuing has been to look at where/how BOLT processes CFI instructions. One thing I found is that at the very least we do seem to read both remember states from the binary function:

diff --git a/bolt/lib/Core/Exceptions.cpp b/bolt/lib/Core/Exceptions.cpp
index 0b2e63b8ca6a..335710e1b8c7 100644
--- a/bolt/lib/Core/Exceptions.cpp
+++ b/bolt/lib/Core/Exceptions.cpp
@@ -565,11 +565,15 @@ bool CFIReaderWriter::fillCFIInfoFor(BinaryFunction &Function) const {
Offset, MCCFIInstruction::createRegister(nullptr, Instr.Ops[0],
Instr.Ops[1]));
break;
- case DW_CFA_remember_state:
+ case DW_CFA_remember_state:{
+ if(Function.getAddress() == 0x23bd340)
+ dbgs() << "remember_state at broken BinaryFunction address 0x23bd340 \n";
Function.addCFIInstruction(
Offset, MCCFIInstruction::createRememberState(nullptr));
break;
+ }

$ llvm-bolt mysqld -o mysqld-bolt -instrument

BOLT-INFO: Target architecture: aarch64
BOLT-INFO: BOLT version: af150272cff97c121ed4fdb76fce702fbe2f12a3
BOLT-INFO: first alloc address is 0x200000
BOLT-INFO: creating new program header table at address 0x4400000, offset 0x4200000
BOLT-INFO: enabling relocation mode
BOLT-INFO: forcing -jump-tables=move for instrumentation
remember_state at broken BinaryFunction address 0x23bd340 
remember_state at broken BinaryFunction address 0x23bd340 
llvm-bolt: /home/iridob01/HoneyBadger/llvm-project-fork/bolt/lib/Core/BinaryFunction.cpp:2663: void llvm::bolt::BinaryFunction::annotateCFIState(): Assertion `!StateStack.empty() && "corrupt CFI stack"' failed.
llvm-bolt: /home/iridob01/HoneyBadger/llvm-project-fork/bolt/lib/Core/BinaryFunction.cpp:2663: void llvm::bolt::BinaryFunction::annotateCFIState(): Assertion `!StateStack.empty() && "corrupt CFI stack"' failed.

My hunch is that we may be doing something wrong in normalizeCFIState() as we remove remember/restore states there. But I need to confirm this.

Edit: normalizeCFIState() runs after annotateCFIState() so that can't be what's causing the issue.

[Asher8118]

I've been trying to figure out why BOLT does not see the first three CFI instructions:

DW_CFA_def_cfa_offset: +16
DW_CFA_offset: reg30 -16
DW_CFA_remember_state:

BOLT adds CFI information for a given BinaryFunction using bool CFIReaderWriter::fillCFIInfoFor(BinaryFunction &Function) . This method then calls void addCFIInstruction(uint64_t Offset, MCCFIInstruction &&Inst) , which populates either CFIInstrMapType CIEFrameInstructions or CFIInstrMapType FrameInstructions. Where CFIInstrMapType = SmallVector<MCCFIInstruction, 0>;.

If the first 3 CFI instructions are not processed, then the FrameInstructions before and after filling in CFI information for each BinaryFunction should differ.
Using this patch:

diff --git a/bolt/lib/Core/BinaryFunction.cpp b/bolt/lib/Core/BinaryFunction.cpp
index b998d7160aae..2600364ccffc 100644
--- a/bolt/lib/Core/BinaryFunction.cpp
+++ b/bolt/lib/Core/BinaryFunction.cpp
@@ -2667,6 +2667,9 @@ void BinaryFunction::annotateCFIState() {
   // For tracking RememberState/RestoreState sequences.
   std::stack<uint32_t> StateStack;
 
+  const bool debugFlag = getAddress() == 0x23b6620;
+  const BinaryFunction::CFIInstrMapType &FDEProgram = getFDEProgram();
+
   for (BinaryBasicBlock *BB : BasicBlocks) {
     BB->setCFIState(EffectiveState);
 
@@ -2677,6 +2680,9 @@ void BinaryFunction::annotateCFIState() {
 
       ++State;
 
+      if(debugFlag)
+        dbgs() << "FDEProgram.size(): " << FDEProgram.size() << "\n";
+
       switch (CFI->getOperation()) {
       case MCCFIInstruction::OpRememberState:
         StateStack.push(EffectiveState);
diff --git a/bolt/lib/Core/Exceptions.cpp b/bolt/lib/Core/Exceptions.cpp
index 0b2e63b8ca6a..2d87ebc240c7 100644
--- a/bolt/lib/Core/Exceptions.cpp
+++ b/bolt/lib/Core/Exceptions.cpp
@@ -651,6 +651,11 @@ bool CFIReaderWriter::fillCFIInfoFor(BinaryFunction &Function) const {
       return false;
     }
 
+    const bool debugFlag = Address == 0x23b6620;
+    const BinaryFunction::CFIInstrMapType &FDEProgram = Function.getFDEProgram();
+    if(debugFlag)
+      dbgs() << "EXCEPTIONS.cpp FDEProgram.size(): " << FDEProgram.size() << "\n";
+
     return true;
   };
 

We obtain:

// for broken address at 0x23b6620
EXCEPTIONS.cpp FDEProgram.size(): 7 // in fillCFIInfoFor 
FDEProgram.size(): 7 // in annotateCFIState

The size matches. Additionally, the switch (Instr.Opcode) in CFIReaderWriter::fillCFIInfoFor(BinaryFunction &Function) does not miss any CFI instructions from the function. However, in void BinaryFunction::annotateCFIState(), we do miss the first 3 CFI instruction (which leads to the assertion error as we are trying to pop from the stack when it's empty).
The issue is likely introduced in how we process the given CFI information in BOLT.

[Asher8118]

Figured out where the issue stems from.

In void addCFIInstruction(uint64_t Offset, MCCFIInstruction &&Inst), we populate either CFIInstrMapType CIEFrameInstructions or CFIInstrMapType FrameInstructions.

If we populate CIEFrameInstructions, we also return:

    if (I == Instructions.begin()) {
      CIEFrameInstructions.emplace_back(std::forward<MCCFIInstruction>(Inst));
      return;
    }

In the case of our broken BinaryFunction, we split the CFI information between CFIInstrMapType CIEFrameInstructions and CFIInstrMapType FrameInstructions. We end up with the first 4 CFI Instructions in CIEFrameInstructions, including the first RememberState. The next RestoreSate, and remaining 7 CFI instructions, are placed in FrameInstructions. This split causes the issue, as we do not see the RememberState before the RestoreState.
A change such as if (I == Instructions.begin() && Inst.getOperation() != MCCFIInstruction::OpRememberState) should fix the issue. Adding this change gets rid of the crash.

[momchil-velikov]

   assert(I->first == Offset && "CFI pointing to unknown instruction");
    if (I == Instructions.begin()) {
      CIEFrameInstructions.emplace_back(std::forward<MCCFIInstruction>(Inst));
      return;
    }

I have a hard time believing this code is correct at all. It looks to me we shouldn't be adding instructions to CIEFrameInstrucitons
as these here belong to FDE, not to CIE.