[AVR] code generation regression (mulhi3 instead of mulqi3)

[tomtor]

volatile unsigned char c;

void mod(unsigned i)
{
  if (i > 9) {
    mod(i / 10);
    mod(i % 10);
  } else {
    c = '0' + i;
  }
}

Old llvm (mid April):

000000ec <mod>:
  ec:   ef 92           push    r14
  ee:   ff 92           push    r15
  f0:   0f 93           push    r16
  f2:   1f 93           push    r17
  f4:   8c 01           movw    r16, r24
  f6:   0a 30           cpi     r16, 0x0A       ; 10
  f8:   11 05           cpc     r17, r1
  fa:   a8 f0           brcs    .+42            ; 0x126 <.Lname50+0x3>
  fc:   2d ec           ldi     r18, 0xCD       ; 205
  fe:   3c ec           ldi     r19, 0xCC       ; 204
 100:   40 e0           ldi     r20, 0x00       ; 0
 102:   50 e0           ldi     r21, 0x00       ; 0
 104:   b8 01           movw    r22, r16
 106:   ca 01           movw    r24, r20
 108:   52 d0           rcall   .+164           ; 0x1ae <__mulsi3>
 10a:   7c 01           movw    r14, r24
 10c:   f6 94           lsr     r15
 10e:   e7 94           ror     r14
 110:   f6 94           lsr     r15
 112:   e7 94           ror     r14
 114:   f6 94           lsr     r15
 116:   e7 94           ror     r14
 118:   c7 01           movw    r24, r14
 11a:   e8 df           rcall   .-48            ; 0xec <mod>
 11c:   8e 2d           mov     r24, r14
 11e:   66 ef           ldi     r22, 0xF6       ; 246
 120:   3d d0           rcall   .+122           ; 0x19c <__mulqi3>
 122:   80 0f           add     r24, r16
 124:   01 c0           rjmp    .+2             ; 0x128 <.Lname51>
 126:   80 2f           mov     r24, r16
 128:   80 63           ori     r24, 0x30       ; 48
 12a:   80 93 be 00     sts     0x00BE, r24     ; 0x8000be <c>
 12e:   1f 91           pop     r17
 130:   0f 91           pop     r16
 132:   ff 90           pop     r15
 134:   ef 90           pop     r14
 136:   08 95           ret

Current llvm:

000000ec <mod>:
  ec:   ef 92           push    r14
  ee:   ff 92           push    r15
  f0:   0f 93           push    r16
  f2:   1f 93           push    r17
  f4:   8c 01           movw    r16, r24
  f6:   0a 30           cpi     r16, 0x0A       ; 10
  f8:   11 05           cpc     r17, r1
  fa:   b0 f0           brcs    .+44            ; 0x128 <.Lname51>
  fc:   2d ec           ldi     r18, 0xCD       ; 205
  fe:   3c ec           ldi     r19, 0xCC       ; 204
 100:   40 e0           ldi     r20, 0x00       ; 0
 102:   50 e0           ldi     r21, 0x00       ; 0
 104:   b8 01           movw    r22, r16
 106:   ca 01           movw    r24, r20
 108:   63 d0           rcall   .+198           ; 0x1d0 <__mulsi3>
 10a:   7c 01           movw    r14, r24
 10c:   f6 94           lsr     r15
 10e:   e7 94           ror     r14
 110:   f6 94           lsr     r15
 112:   e7 94           ror     r14
 114:   f6 94           lsr     r15
 116:   e7 94           ror     r14
 118:   c7 01           movw    r24, r14
 11a:   e8 df           rcall   .-48            ; 0xec <mod>
 11c:   6a e0           ldi     r22, 0x0A       ; 10
 11e:   70 e0           ldi     r23, 0x00       ; 0
 120:   c7 01           movw    r24, r14
 122:   45 d0           rcall   .+138           ; 0x1ae <__mulhi3>
 124:   08 1b           sub     r16, r24
 126:   19 0b           sbc     r17, r25
 128:   00 63           ori     r16, 0x30       ; 48
 12a:   00 93 be 00     sts     0x00BE, r16     ; 0x8000be <c>
 12e:   1f 91           pop     r17
 130:   0f 91           pop     r16
 132:   ff 90           pop     r15
 134:   ef 90           pop     r14
 136:   08 95           ret

[tomtor]

@Patryk27 currently bisecting llvm....

[tomtor]

0159a26

0159a26744dd3ca332973c0e1cd8f6ccbace2927 is the first bad commit
commit 0159a26744dd3ca332973c0e1cd8f6ccbace2927
Author: Hassnaa Hamdi <hassnaa.hamdi@arm.com>
Date:   Tue May 6 11:25:37 2025 +0100

    [InlineCost]: Add a new heuristic to branch folding for better inlining decisions.
    
    Recursive functions are generally not inlined to avoid issues
    like infinite inlining or excessive code expansion. However,
    this conservative approach misses opportunities for optimization in
    cases where a recursive call is guaranteed to execute only once.
    
    This patch detects a scenario where a guarding branch condition of a recursive
    call will become false after the first iteration of the recursive function.
    If such a condition is met, and the recursion depth is confirmed to be one,
    the Inliner will now consider this recursive function for inlining.
    
    A new test case (`test/Transforms/Inline/inline-recursive-fn.ll`)
    has been added to verify this behaviour.

 llvm/lib/Analysis/InlineCost.cpp                   |  81 +++++++++
 llvm/test/Transforms/Inline/inline-recursive-fn.ll | 193 +++++++++++++++++++++
 2 files changed, 274 insertions(+)
 create mode 100644 llvm/test/Transforms/Inline/inline-recursive-fn.ll
bisect found first bad commit

results in the following AVR code (much worse than current main) :/

000000ec <mod>:
  ec:   cf 92           push    r12
  ee:   df 92           push    r13
  f0:   ef 92           push    r14
  f2:   ff 92           push    r15
  f4:   0f 93           push    r16
  f6:   1f 93           push    r17
  f8:   8c 01           movw    r16, r24
  fa:   0a 30           cpi     r16, 0x0A       ; 10
  fc:   11 05           cpc     r17, r1
  fe:   08 f4           brcc    .+2             ; 0x102 <.Lname44>
 100:   36 c0           rjmp    .+108           ; 0x16e <.Lname61+0xc>
 102:   2d ec           ldi     r18, 0xCD       ; 205
 104:   3c ec           ldi     r19, 0xCC       ; 204
 106:   40 e0           ldi     r20, 0x00       ; 0
 108:   50 e0           ldi     r21, 0x00       ; 0
 10a:   b8 01           movw    r22, r16
 10c:   ca 01           movw    r24, r20
 10e:   86 d0           rcall   .+268           ; 0x21c <__mulsi3>
 110:   7c 01           movw    r14, r24
 112:   f6 94           lsr     r15
 114:   e7 94           ror     r14
 116:   f6 94           lsr     r15
 118:   e7 94           ror     r14
 11a:   f6 94           lsr     r15
 11c:   e7 94           ror     r14
 11e:   04 36           cpi     r16, 0x64       ; 100
 120:   11 05           cpc     r17, r1
 122:   08 f4           brcc    .+2             ; 0x126 <.Lname50+0x3>
 124:   26 c0           rjmp    .+76            ; 0x172 <.Lname61+0x10>
 126:   b8 01           movw    r22, r16
 128:   76 95           lsr     r23
 12a:   67 95           ror     r22
 12c:   76 95           lsr     r23
 12e:   67 95           ror     r22
 130:   2b e7           ldi     r18, 0x7B       ; 123
 132:   34 e1           ldi     r19, 0x14       ; 20
 134:   40 e0           ldi     r20, 0x00       ; 0
 136:   50 e0           ldi     r21, 0x00       ; 0
 138:   ca 01           movw    r24, r20
 13a:   6a 01           movw    r12, r20
 13c:   6f d0           rcall   .+222           ; 0x21c <__mulsi3>
 13e:   96 95           lsr     r25
 140:   87 95           ror     r24
 142:   d4 df           rcall   .-88            ; 0xec <mod>
 144:   2d ec           ldi     r18, 0xCD       ; 205
 146:   3c ec           ldi     r19, 0xCC       ; 204
 148:   b7 01           movw    r22, r14
 14a:   c6 01           movw    r24, r12
 14c:   a6 01           movw    r20, r12
 14e:   66 d0           rcall   .+204           ; 0x21c <__mulsi3>
 150:   96 95           lsr     r25
 152:   87 95           ror     r24
 154:   96 95           lsr     r25
 156:   87 95           ror     r24
 158:   96 95           lsr     r25
 15a:   87 95           ror     r24
 15c:   6a e0           ldi     r22, 0x0A       ; 10
 15e:   70 e0           ldi     r23, 0x00       ; 0
 160:   4c d0           rcall   .+152           ; 0x1fa <__mulhi3>
 162:   97 01           movw    r18, r14
 164:   28 1b           sub     r18, r24
 166:   39 0b           sbc     r19, r25
 168:   c9 01           movw    r24, r18
 16a:   c0 df           rcall   .-128           ; 0xec <mod>
 16c:   06 c0           rjmp    .+12            ; 0x17a <.Lname61+0x18>
 16e:   80 2f           mov     r24, r16
 170:   08 c0           rjmp    .+16            ; 0x182 <.Lname61+0x20>
 172:   8e 2d           mov     r24, r14
 174:   80 63           ori     r24, 0x30       ; 48
 176:   80 93 be 00     sts     0x00BE, r24     ; 0x8000be <c>
 17a:   8e 2d           mov     r24, r14
 17c:   66 ef           ldi     r22, 0xF6       ; 246
 17e:   34 d0           rcall   .+104           ; 0x1e8 <__mulqi3>
 180:   80 0f           add     r24, r16
 182:   80 63           ori     r24, 0x30       ; 48
 184:   80 93 be 00     sts     0x00BE, r24     ; 0x8000be <c>
 188:   1f 91           pop     r17
 18a:   0f 91           pop     r16
 18c:   ff 90           pop     r15
 18e:   ef 90           pop     r14
 190:   df 90           pop     r13
 192:   cf 90           pop     r12
 194:   08 95           ret

[tomtor]

Interesting is that the produced code HAS mulqi3 and obviously is no longer causing that inline expansion in the current LLVM.

The issue is is however related to recursion/inlining, because without recursion mulqi3 IS emitted instead of mulhi3

[tomtor]

Not sure how to proceed? @Patryk27 @benshi001

[tomtor]

@hassnaaHamdi I suspect that this issue is not AVR specific.

Could it be that my example function triggers some unexpected behavior that could be fixed in your original commit?

[Patryk27]

I see, yeah - I'd expect to get mulhi3 in here as well.

I should be able to take a better look tomorrow, but if you want to take a stab, I'd suggest to run llc ... -print-after-all -debug[1] for the older and newer versions and try to pinpoint the differences between both logs (usually even a simple textual diffing gets me far, possibly with some regex sanitization to remove randomized memory addresses etc.).

[1] generates a lot of data, better to &> /tmp/log.txt and browse in your favorite code editor rather than directly in terminal