bug in loop counters generates code that crashes

[tthsqe12]

compile the C code in the next post with clang15 and something roughly equivalent to "%clang -std=c11 -O0 -fno-unroll-loops -fno-tree-vectorize %s -S -emit-llvm -o - %newLoadClangEnzyme". The most important thing is -O0 so that things are clear. The code is really quite minimal in terms of both manifesting the bug in the llvm and at run time.

Some important variables to keep in mind when reading the llvm in my next post:
%10 is A's tape
%iv is A's loop counter

problem no. 1

The problem occurs when the original code exits via the B block. In this case the block return.loopexit is reached and the following is obviously a problem.

return.loopexit:
  %19 = getelementptr inbounds i64, ptr %.lcssa27, i64 undef ; BAD
  %20 = load i64, ptr %19, align 8, !invariant.group !6 ; %20 is supposed to be B's loop counter as loaded off of A's tape

problem no. 2
"iv'ac.0" is used in invertA as A's reverse loop counter. This variable comes from the following places:

invertA:
  %"iv'ac.0" = phi i64 [ %"iv'ac.1", %invertif.else ], [ %iv.lcssa, %invertA.loopexit9 ]

invertA.loopexit9:
  %iv.lcssa = phi i64 [ %iv, %__enzyme_exponentialallocation.exit ]                     ; all good

invertif.else:
  %"iv'ac.1" = phi i64 [ %40, %incinvertA ], [ %"iv'ac.2", %invertB.preheader ]         ; all good. note %40 = %"iv'ac.0" - 1

invertB:
  %"iv'ac.2" = phi i64 [ %"iv'ac.3", %invertif.else35 ], [ undef, %return.loopexit ]    ; second is BAD

invertif.else35:
  %"iv'ac.3" = phi i64 [ %40, %invertA.loopexit ], [ %"iv'ac.2", %incinvertB ]          ; all good

Again, it is clear that enzyme has gotten confused about invertA's loop counter when coming from invertB.

[tthsqe12]

C code

C code

#include <stdio.h>

void f(double x[2])
{
 double t;
A:
 t    = 4*__builtin_cos(x[0] + x[1]);
 x[0] = 3*__builtin_sin(2*x[0] + x[1]);
 x[1] = t;
 if (x[0]*x[0] < x[1])
    return;
 else if (x[0] > 0)
    goto A;
 else
    goto B;

B:
 t    = 4*__builtin_sin(2*x[0] + x[1]);
 x[0] = 4*__builtin_cos(x[0] + 2*x[1]);
 x[1] = t;
 if (x[0]*x[0] < x[1])
    return;
 else if (x[0] > 0)
    goto A;
 else
    goto B;
}

extern void* __enzyme_augmentfwd(void*, double*, double*);
extern void __enzyme_reverse(void*, double*, double*, void*);

int main()
{
 double x[2], x_b[2];
 x[0] = 0.9;
 x[1] = 0.7;
 x_b[0] = 1;
 x_b[1] = 2;

 void* tape = __enzyme_augmentfwd((void*)f, x, x_b);
 printf("tape: %p\n", tape);
 __enzyme_reverse((void*)f, x, x_b, tape);
 printf("x: %f, %f | x_b: %f, %f\n", x[0], x[1], x_b[0], x_b[1]);
}

resulting LLVM

LLVM

; Function Attrs: mustprogress noinline nounwind willreturn uwtable
define internal fastcc void @diffef(ptr nocapture %"x'") unnamed_addr #5 {
entry:
%truetape.unpack = load ptr, ptr inttoptr (i64 4 to ptr), align 8
%truetape.unpack1 = load ptr, ptr inttoptr (i64 12 to ptr), align 8
%truetape.unpack2 = load ptr, ptr inttoptr (i64 20 to ptr), align 8
%truetape.unpack3 = load ptr, ptr inttoptr (i64 28 to ptr), align 8
%truetape.unpack4 = load ptr, ptr inttoptr (i64 36 to ptr), align 8
%truetape.unpack5 = load ptr, ptr inttoptr (i64 44 to ptr), align 8
%truetape.unpack6 = load ptr, ptr inttoptr (i64 52 to ptr), align 8
%truetape.unpack7 = load ptr, ptr inttoptr (i64 60 to ptr), align 8
tail call void @free(ptr nonnull inttoptr (i64 4 to ptr))
br label %A

A.loopexit:                                       ; preds = %if.else35
%iv2.lcssa25 = phi i64 [ %iv2, %if.else35 ]
%0 = getelementptr inbounds i64, ptr %10, i64 %iv
store i64 %iv2.lcssa25, ptr %0, align 8, !invariant.group !6
br label %A.backedge

A:                                                ; preds = %A.backedge, %entry
%loopLimit_cache2.0 = phi ptr [ null, %entry ], [ %10, %A.backedge ]
%iv = phi i64 [ 0, %entry ], [ %iv.next, %A.backedge ]
%iv.next = add nuw nsw i64 %iv, 1
%1 = and i64 %iv.next, 1
%2 = icmp ne i64 %1, 0
%3 = tail call i64 @llvm.ctpop.i64(i64 %iv.next), !range !7
%4 = icmp ult i64 %3, 3
%5 = and i1 %4, %2
br i1 %5, label %grow.i, label %__enzyme_exponentialallocation.exit

grow.i:                                           ; preds = %A
%6 = tail call i64 @llvm.ctlz.i64(i64 %iv.next, i1 true), !range !8
%7 = sub nuw nsw i64 64, %6
%8 = shl i64 8, %7
%9 = tail call ptr @realloc(ptr %loopLimit_cache2.0, i64 %8) #7
br label %__enzyme_exponentialallocation.exit

__enzyme_exponentialallocation.exit:              ; preds = %A, %grow.i
%10 = phi ptr [ %9, %grow.i ], [ %loopLimit_cache2.0, %A ]
%11 = getelementptr inbounds i1, ptr %truetape.unpack4, i64 %iv
%cmp = load i1, ptr %11, align 1, !invariant.group !9
br i1 %cmp, label %invertA.loopexit9, label %if.else

if.else:                                          ; preds = %__enzyme_exponentialallocation.exit
%12 = getelementptr inbounds i1, ptr %truetape.unpack5, i64 %iv
%cmp14 = load i1, ptr %12, align 1, !invariant.group !10
br i1 %cmp14, label %A.backedge, label %B.preheader

A.backedge:                                       ; preds = %if.else, %A.loopexit
br label %A

B.preheader:                                      ; preds = %if.else
%13 = getelementptr inbounds ptr, ptr %truetape.unpack6, i64 %iv
%14 = getelementptr inbounds ptr, ptr %truetape.unpack7, i64 %iv
%.pre133 = load ptr, ptr %13, align 8, !invariant.group !11
br label %B

B:                                                ; preds = %if.else35, %B.preheader
%iv2 = phi i64 [ 0, %B.preheader ], [ %iv.next3, %if.else35 ]
%15 = getelementptr inbounds i1, ptr %.pre133, i64 %iv2
%cmp33 = load i1, ptr %15, align 1, !invariant.group !12
br i1 %cmp33, label %return.loopexit, label %if.else35

if.else35:                                        ; preds = %B
%iv.next3 = add nuw nsw i64 %iv2, 1
%16 = load ptr, ptr %14, align 8, !dereferenceable !13, !invariant.group !14
%17 = getelementptr inbounds i1, ptr %16, i64 %iv2
%cmp37 = load i1, ptr %17, align 1, !invariant.group !15
br i1 %cmp37, label %A.loopexit, label %B

return.loopexit:                                  ; preds = %B
%.lcssa27 = phi ptr [ %10, %B ]
%iv.lcssa26 = phi i64 [ %iv, %B ]
%iv2.lcssa = phi i64 [ %iv2, %B ]
%"arrayidx1'ipg.le" = getelementptr inbounds double, ptr %"x'", i64 1
%18 = getelementptr inbounds i64, ptr %.lcssa27, i64 %iv.lcssa26
store i64 %iv2.lcssa, ptr %18, align 8, !invariant.group !6
%19 = getelementptr inbounds i64, ptr %.lcssa27, i64 undef
%20 = load i64, ptr %19, align 8, !invariant.group !6
%.pre134 = load double, ptr %"arrayidx1'ipg.le", align 8, !alias.scope !16, !noalias !19
%.pre135 = load double, ptr %"x'", align 8, !alias.scope !16, !noalias !19
br label %invertB

invertentry:                                      ; preds = %invertA
tail call void @free(ptr nonnull %23)
tail call void @free(ptr nonnull %truetape.unpack)
tail call void @free(ptr nonnull %truetape.unpack1)
tail call void @free(ptr nonnull %truetape.unpack2)
tail call void @free(ptr nonnull %truetape.unpack4)
tail call void @free(ptr nonnull %truetape.unpack5)
tail call void @free(ptr nonnull %truetape.unpack3)
tail call void @free(ptr nonnull %truetape.unpack6)
tail call void @free(ptr nonnull %truetape.unpack7)
ret void

invertA.loopexit:                                 ; preds = %incinvertA
%21 = getelementptr inbounds i64, ptr %23, i64 %40
%22 = load i64, ptr %21, align 8, !invariant.group !6
br label %invertif.else35

invertA.loopexit9:                                ; preds = %__enzyme_exponentialallocation.exit
%.lcssa = phi ptr [ %10, %__enzyme_exponentialallocation.exit ]
%iv.lcssa = phi i64 [ %iv, %__enzyme_exponentialallocation.exit ]
%"arrayidx1'ipg.le18" = getelementptr inbounds double, ptr %"x'", i64 1
br label %invertA

invertA:                                          ; preds = %invertA.loopexit9, %invertif.else
%23 = phi ptr [ %43, %invertif.else ], [ %.lcssa, %invertA.loopexit9 ]
%"arrayidx1'ipg14" = phi ptr [ %"arrayidx1'ipg15", %invertif.else ], [ %"arrayidx1'ipg.le18", %invertA.loopexit9 ]
%"iv'ac.0" = phi i64 [ %"iv'ac.1", %invertif.else ], [ %iv.lcssa, %invertA.loopexit9 ]
%24 = load double, ptr %"arrayidx1'ipg14", align 8, !alias.scope !16, !noalias !19
store double 0.000000e+00, ptr %"arrayidx1'ipg14", align 8, !alias.scope !16, !noalias !19
%25 = load double, ptr %"x'", align 8, !alias.scope !16, !noalias !19
store double 0.000000e+00, ptr %"x'", align 8, !alias.scope !16, !noalias !19
%26 = fmul fast double %25, 3.000000e+00
%27 = getelementptr inbounds double, ptr %truetape.unpack, i64 %"iv'ac.0"
%28 = load double, ptr %27, align 8, !invariant.group !21
%29 = tail call fast double @llvm.cos.f64(double %28)
%30 = fmul fast double %26, %29
%31 = fmul fast double %30, 2.000000e+00
store double %30, ptr %"arrayidx1'ipg14", align 8, !alias.scope !16, !noalias !19
store double %31, ptr %"x'", align 8, !alias.scope !16, !noalias !19
%32 = getelementptr inbounds double, ptr %truetape.unpack3, i64 %"iv'ac.0"
%33 = load double, ptr %32, align 8, !invariant.group !22
%34 = tail call fast double @llvm.sin.f64(double %33)
%35 = fmul fast double %24, -4.000000e+00
%36 = fmul fast double %35, %34
%37 = fadd fast double %36, %30
store double %37, ptr %"arrayidx1'ipg14", align 8, !alias.scope !16, !noalias !19
%38 = fadd fast double %36, %31
store double %38, ptr %"x'", align 8, !alias.scope !16, !noalias !19
%39 = icmp eq i64 %"iv'ac.0", 0
br i1 %39, label %invertentry, label %incinvertA

incinvertA:                                       ; preds = %invertA
%40 = add nsw i64 %"iv'ac.0", -1
%41 = getelementptr inbounds i1, ptr %truetape.unpack5, i64 %40
%42 = load i1, ptr %41, align 1, !invariant.group !23
br i1 %42, label %invertif.else, label %invertA.loopexit

invertif.else:                                    ; preds = %invertB.preheader, %incinvertA
%43 = phi ptr [ %23, %incinvertA ], [ %44, %invertB.preheader ]
%"arrayidx1'ipg15" = phi ptr [ %"arrayidx1'ipg14", %incinvertA ], [ %"arrayidx1'ipg16", %invertB.preheader ]
%"iv'ac.1" = phi i64 [ %40, %incinvertA ], [ %"iv'ac.2", %invertB.preheader ]
br label %invertA

invertB.preheader:                                ; preds = %invertB
tail call void @free(ptr nonnull %48)
tail call void @free(ptr nonnull %57)
%_unwrap119 = getelementptr inbounds ptr, ptr %truetape.unpack6, i64 %"iv'ac.2"
%forfree120 = load ptr, ptr %_unwrap119, align 8, !dereferenceable !24, !invariant.group !11
tail call void @free(ptr nonnull %forfree120)
%_unwrap128 = getelementptr inbounds ptr, ptr %truetape.unpack7, i64 %"iv'ac.2"
%forfree129 = load ptr, ptr %_unwrap128, align 8, !dereferenceable !24, !invariant.group !14
tail call void @free(ptr nonnull %forfree129)
br label %invertif.else

invertB:                                          ; preds = %return.loopexit, %invertif.else35
%44 = phi ptr [ %67, %invertif.else35 ], [ %.lcssa27, %return.loopexit ]
%"arrayidx1'ipg16" = phi ptr [ %"arrayidx1'ipg13", %invertif.else35 ], [ %"arrayidx1'ipg.le", %return.loopexit ]
%45 = phi double [ %68, %invertif.else35 ], [ %.pre135, %return.loopexit ]
%46 = phi double [ %69, %invertif.else35 ], [ %.pre134, %return.loopexit ]
%"iv2'ac.0" = phi i64 [ %"iv2'ac.1", %invertif.else35 ], [ %20, %return.loopexit ]
%"iv'ac.2" = phi i64 [ %"iv'ac.3", %invertif.else35 ], [ undef, %return.loopexit ]
store double 0.000000e+00, ptr %"arrayidx1'ipg16", align 8, !alias.scope !16, !noalias !19
store double 0.000000e+00, ptr %"x'", align 8, !alias.scope !16, !noalias !19
%47 = getelementptr inbounds ptr, ptr %truetape.unpack1, i64 %"iv'ac.2"
%48 = load ptr, ptr %47, align 8, !dereferenceable !13, !invariant.group !25
%49 = getelementptr inbounds double, ptr %48, i64 %"iv2'ac.0"
%50 = load double, ptr %49, align 8, !invariant.group !26
%51 = tail call fast double @llvm.sin.f64(double %50)
%52 = fmul fast double %45, -4.000000e+00
%53 = fmul fast double %52, %51
%54 = fmul fast double %53, 2.000000e+00
store double %54, ptr %"arrayidx1'ipg16", align 8, !alias.scope !16, !noalias !19
store double %53, ptr %"x'", align 8, !alias.scope !16, !noalias !19
%55 = fmul fast double %46, 4.000000e+00
%56 = getelementptr inbounds ptr, ptr %truetape.unpack2, i64 %"iv'ac.2"
%57 = load ptr, ptr %56, align 8, !dereferenceable !13, !invariant.group !27
%58 = getelementptr inbounds double, ptr %57, i64 %"iv2'ac.0"
%59 = load double, ptr %58, align 8, !invariant.group !28
%60 = tail call fast double @llvm.cos.f64(double %59)
%61 = fmul fast double %55, %60
%62 = fmul fast double %61, 2.000000e+00
%63 = fadd fast double %61, %54
store double %63, ptr %"arrayidx1'ipg16", align 8, !alias.scope !16, !noalias !19
%64 = fadd fast double %62, %53
store double %64, ptr %"x'", align 8, !alias.scope !16, !noalias !19
%65 = icmp eq i64 %"iv2'ac.0", 0
br i1 %65, label %invertB.preheader, label %incinvertB

incinvertB:                                       ; preds = %invertB
%66 = add nsw i64 %"iv2'ac.0", -1
br label %invertif.else35

invertif.else35:                                  ; preds = %incinvertB, %invertA.loopexit
%67 = phi ptr [ %23, %invertA.loopexit ], [ %44, %incinvertB ]
%"arrayidx1'ipg13" = phi ptr [ %"arrayidx1'ipg14", %invertA.loopexit ], [ %"arrayidx1'ipg16", %incinvertB ]
%68 = phi double [ %38, %invertA.loopexit ], [ %64, %incinvertB ]
%69 = phi double [ %37, %invertA.loopexit ], [ %63, %incinvertB ]
%"iv2'ac.1" = phi i64 [ %22, %invertA.loopexit ], [ %66, %incinvertB ]
%"iv'ac.3" = phi i64 [ %40, %invertA.loopexit ], [ %"iv'ac.2", %incinvertB ]
br label %invertB
}

[tthsqe12]

fixed by
#1430
#1443