[AVR] Induction variable not found (missed optimization)

[tomtor]

void foo(int);
int ci[30];

void loopci()
{
  for (int i=0; i < sizeof(ci)/sizeof(ci[0]); i++)
    foo(ci[i]);
}

compiles to:

000000b4 <loopci>:
  b4:   ef 92           push    r14
  b6:   ff 92           push    r15
  b8:   0f 93           push    r16
  ba:   1f 93           push    r17
  bc:   00 e0           ldi     r16, 0x00       ; 0
  be:   10 e0           ldi     r17, 0x00       ; 0
  c0:   c8 01           movw    r24, r16
  c2:   7c 01           movw    r14, r24
  c4:   c8 01           movw    r24, r16
  c6:   88 0f           add     r24, r24
  c8:   99 1f           adc     r25, r25
  ca:   80 50           subi    r24, 0x00       ; 0
  cc:   98 4c           sbci    r25, 0xC8       ; 200
  ce:   fc 01           movw    r30, r24
  d0:   80 81           ld      r24, Z
  d2:   91 81           ldd     r25, Z+1        ; 0x01
  d4:   1a d0           rcall   .+52            ; 0x10a <foo>
  d6:   c7 01           movw    r24, r14
  d8:   01 96           adiw    r24, 0x01       ; 1
  da:   0d 31           cpi     r16, 0x1D       ; 29
  dc:   11 05           cpc     r17, r1
  de:   8c 01           movw    r16, r24
  e0:   80 f3           brcs    .-32            ; 0xc2 <.Lname26+0x3>
  e2:   1f 91           pop     r17
  e4:   0f 91           pop     r16
  e6:   ff 90           pop     r15
  e8:   ef 90           pop     r14
  ea:   08 95           ret

avr-gcc:

000000b4 <loopci>:
  b4:   cf 93           push    r28
  b6:   df 93           push    r29
  b8:   ca e1           ldi     r28, 0x1A       ; 26
  ba:   d8 e3           ldi     r29, 0x38       ; 56

000000bc <.L2>:
  bc:   89 91           ld      r24, Y+
  be:   99 91           ld      r25, Y+
  c0:   20 d0           rcall   .+64            ; 0x102 <foo>
  c2:   88 e3           ldi     r24, 0x38       ; 56
  c4:   c6 35           cpi     r28, 0x56       ; 86
  c6:   d8 07           cpc     r29, r24
  c8:   c9 f7           brne    .-14            ; 0xbc <.L2>
  ca:   df 91           pop     r29
  cc:   cf 91           pop     r28
  ce:   08 95           ret

[tomtor]

Obviously this works for other LLVM targets.

llvm/lib/Transforms/Scalar/IndVarSimplify.cpp does not find the induction var on AVR.

This causes loop strength reduction to fail also.

[tomtor]

This also shows the cost of not having Y available in functions without FP.

In addition post increment on pointers is often missed, but these are two non related issues.

[tomtor]

@Patryk27 I cannot imagine that this did not work a few years ago, looks like a regression to me.

Edit: Checked llvmorg-11.0.1 from 2022, it has the same issue....

[tomtor]

The root cause is that the IndVar code has a few:

DL.isLegalInteger(PhiWidth) which is false for 16!

Hacking so that it is true results in correct optimization (9 instructions less, but not optimal yet, no strength reduction):

000000b4 <loopci>:
  b4:   0f 93           push    r16
  b6:   1f 93           push    r17
  b8:   80 e0           ldi     r24, 0x00       ; 0
  ba:   90 e0           ldi     r25, 0x00       ; 0
  bc:   8c 01           movw    r16, r24
  be:   80 50           subi    r24, 0x00       ; 0
  c0:   98 4c           sbci    r25, 0xC8       ; 200
  c2:   fc 01           movw    r30, r24
  c4:   80 81           ld      r24, Z
  c6:   91 81           ldd     r25, Z+1        ; 0x01
  c8:   16 d0           rcall   .+44            ; 0xf6 <foo>
  ca:   c8 01           movw    r24, r16
  cc:   02 96           adiw    r24, 0x02       ; 2
  ce:   8c 33           cpi     r24, 0x3C       ; 60
  d0:   91 05           cpc     r25, r1
  d2:   a1 f7           brne    .-24            ; 0xbc <.Lname25+0x5>
  d4:   1f 91           pop     r17
  d6:   0f 91           pop     r16
  d8:   08 95           ret

[tomtor]

static const char *AVRDataLayout =
    "e-P1-p:16:8-i8:8-i16:8-i32:8-i64:8-f32:8-f64:8-n8-n16:8-a:8";

in AVRTargetMachine.cpp results in:

error: backend data layout 'e-P1-p:16:8-i8:8-i16:8-i32:8-i64:8-f32:8-f64:8-n8-n16:8-a:8' does
      not match expected target description 'e-P1-p:16:8-i8:8-i16:8-i32:8-i64:8-f32:8-f64:8-n8-a:8'

I am not sure about the correct way to fix this. @benshi001 @Patryk27 any suggestions?

[Patryk27]

Ah, that's a real quality find - I don't have time to analyze this at the moment, but I'll take a look tomorrow!

[nikic]

@tomtor You need to update the data layout in both clang/lib/Basic/Targets/AVR.h and llvm/lib/Target/AVR/AVRTargetMachine.cpp.

[benshi001]

static const char *AVRDataLayout =
    "e-P1-p:16:8-i8:8-i16:8-i32:8-i64:8-f32:8-f64:8-n8-n16:8-a:8";

in AVRTargetMachine.cpp results in:

error: backend data layout 'e-P1-p:16:8-i8:8-i16:8-i32:8-i64:8-f32:8-f64:8-n8-n16:8-a:8' does
      not match expected target description 'e-P1-p:16:8-i8:8-i16:8-i32:8-i64:8-f32:8-f64:8-n8-a:8'

I am not sure about the correct way to fix this. @benshi001 @Patryk27 any suggestions?

I support to change to n8:8-n16:8 if it introduces no other error or regression.

[tomtor]

Riscv:

; Loop:
2:                                                ; preds = %0, %2
  %3 = phi i32 [ 0, %0 ], [ %6, %2 ]
  %4 = getelementptr inbounds nuw [30 x i32], ptr @ci, i32 0, i32 %3
  %5 = load i32, ptr %4, align 4, !tbaa !6
  tail call void @foo(i32 noundef %5) #3
  %6 = add nuw nsw i32 %3, 1
  %7 = icmp eq i32 %6, 30
  br i1 %7, label %1, label %2, !llvm.loop !10

; Exit blocks
1:                                                ; preds = %2
  ret void
*** IR Dump After Loop Strength Reduction (loop-reduce) ***
; Preheader:
  br label %2

; Loop:
2:                                                ; preds = %0, %2
  %3 = phi ptr [ @ci, %0 ], [ %7, %2 ]
  %4 = phi i32 [ 30, %0 ], [ %6, %2 ]
  %5 = load i32, ptr %3, align 4, !tbaa !6
  tail call void @foo(i32 noundef %5) #3
  %6 = add nsw i32 %4, -1
  %7 = getelementptr i8, ptr %3, i32 4
  %8 = icmp eq i32 %6, 0
  br i1 %8, label %1, label %2, !llvm.loop !10

AVR:

; Loop:
2:                                                ; preds = %0, %2
  %3 = phi i16 [ 0, %0 ], [ %6, %2 ]
  %4 = getelementptr inbounds nuw [30 x i16], ptr @ci, i16 0, i16 %3
  %5 = load i16, ptr %4, align 1, !tbaa !3
  tail call addrspace(1) void @foo(i16 noundef %5) #3
  %6 = add nuw nsw i16 %3, 1
  %7 = icmp eq i16 %6, 30
  br i1 %7, label %1, label %2, !llvm.loop !7

; Exit blocks
1:                                                ; preds = %2
  ret void
*** IR Dump After Loop Strength Reduction (loop-reduce) ***
; Preheader:
  br label %2

; Loop:
2:                                                ; preds = %0, %2
  %3 = phi i16 [ 0, %0 ], [ %6, %2 ]
  %4 = getelementptr i8, ptr @ci, i16 %3
  %5 = load i16, ptr %4, align 1, !tbaa !3
  tail call addrspace(1) void @foo(i16 noundef %5) #3
  %6 = add nuw nsw i16 %3, 2
  %7 = icmp eq i16 %6, 60
  br i1 %7, label %1, label %2, !llvm.loop !7

We should get a similar output as for riscv, which also has limited addressing modes.
It stores the end-of-loop address in a register, just like avr-gcc does.

addrspace(1) is the only difference in the loop-reduce pass input.

[tomtor]

  b4:   ef 92           push    r14
  b6:   ff 92           push    r15
  b8:   0f 93           push    r16
  ba:   1f 93           push    r17
  bc:   a0 e0           ldi     r26, 0x00       ; 0
  be:   b8 e3           ldi     r27, 0x38       ; 56
  c0:   0c e3           ldi     r16, 0x3C       ; 60
  c2:   18 e3           ldi     r17, 0x38       ; 56
  c4:   8d 91           ld      r24, X+
  c6:   9d 91           ld      r25, X+
  c8:   7d 01           movw    r14, r26
  ca:   17 d0           rcall   .+46            ; 0xfa <foo>
  cc:   d7 01           movw    r26, r14
  ce:   a0 17           cp      r26, r16
  d0:   b1 07           cpc     r27, r17
  d2:   c1 f7           brne    .-16            ; 0xc4 <.Lname26+0x5>
  d4:   1f 91           pop     r17
  d6:   0f 91           pop     r16
  d8:   ff 90           pop     r15
  da:   ef 90           pop     r14

After some experiments with the costs calculation :-)

[tomtor]

This looks weird:

    60 + reg(@ci) + 1*reg({-60,+,2}<nuw><nsw><%for.body>)
New best at 2 instructions 2 regs, with addrec cost 2, plus 2 setup cost.
Regs:
- {30,+,-1}<nsw><%for.body>
- {@ci,+,2}<nuw><%for.body>

New best at 3 instructions 2 regs, with addrec cost 1, plus 1 base add, plus 7 imm cost, plus 2 setup cost.
Regs:
- {0,+,2}<nuw><nsw><%for.body>
- @ci


The chosen solution requires 3 instructions 2 regs, with addrec cost 1, plus 1 base add, plus 7 imm cost, plu
s 2 setup cost:
  LSR Use: Kind=ICmpZero, Offsets={0}, widest fixup type: i16
    -60 + reg({0,+,2}<nuw><nsw><%for.body>)
  LSR Use: Kind=Address of i16 in addrspace(0), O

when we force the first selection we get the code we want, but for some reason the (more expensive?) solution is selected. I have to figure out what is causing this.