WRONG code: GVN? Loop opts?

[JonPsson1]

cat wrong0.i

int printf(const char *, ...);
unsigned int IntArr[6];
unsigned int GlobIntONE = 1, GlobIntZERO = 0;
const unsigned int *GlobIntPtr = 0;
unsigned long Res;
unsigned long *ResPtr = &Res;
const unsigned int **GlobIntPtrPTr = &GlobIntPtr;
unsigned int *func() {
  int *GlobIntONEPtr = &GlobIntONE;
  for (int Idx = 0; Idx <= 7; Idx += 1) {
    int Idx2 = 1;
    if (Idx > 0) {
      for (; Idx2 <= 7; Idx2 += 1)
        ;
      return GlobIntONEPtr;
    }
  }
  0 != &GlobIntONEPtr;
  return &GlobIntZERO;
}

int main() {
  IntArr[GlobIntZERO] = GlobIntZERO;
  *GlobIntPtrPTr = func();
  unsigned char Byte = *GlobIntPtr;
  *ResPtr = Byte;
  printf("checksum = %X\n", Res);
}

In the above file, func() should obviously should return GlobIntONEPtr, but it does not if compiled with '-fno-inline -mllvm -unroll-full-max-count=1'.

clang -O0 -march=z16 wrong0.i -o a.out -w -fno-inline  ; ./a.out
checksum = 1

clang -O3 -march=z16 wrong0.i -o a.out -w -fno-inline  ; ./a.out
checksum = 1

clang -O3 -march=z16 wrong0.i -o a.out -w -fno-inline  -mllvm -unroll-full-max-count=1 ; ./a.out
checksum = 0

It may be that GVN does something wrong, as after it @func() is always returning ptr undef. Or it could very well be some of the loop optimizations that is run just before it.

A bisect shows that

d77067d08a3f56dc2d0e6c95bd2852c943df743a is the first bad commit
commit d77067d08a3f56dc2d0e6c95bd2852c943df743a
Author: Nikita Popov <[email protected]>
Date:   Wed Dec 6 14:17:18 2023 +0100

    [ValueTracking] Add dominating condition support in computeKnownBits() (#73662)

@nikic

[dtcxzyw]

Bisected to LoopUnrollFullPass:

; bin/opt -passes=loop-unroll-full -unroll-full-max-count=1 test.ll -S

@GlobIntONE = dso_local global i32 1, align 4
@GlobIntZERO = dso_local local_unnamed_addr global i32 0, align 4

define i32 @main() local_unnamed_addr {
entry:
  br label %for.body

for.body:                                         ; preds = %entry, %cleanup
  %retval.0 = phi ptr [ undef, %entry ], [ %retval.2, %cleanup ]
  %cmp1.not = phi i1 [ true, %entry ], [ false, %cleanup ]
  br i1 %cmp1.not, label %cleanup, label %for.cond2.preheader

for.cond2.preheader:                              ; preds = %for.body
  br label %cleanup.loopexit

cleanup.loopexit:                                 ; preds = %for.cond2.preheader
  br label %cleanup

cleanup:                                          ; preds = %cleanup.loopexit, %for.body
  %retval.2 = phi ptr [ %retval.0, %for.body ], [ @GlobIntONE, %cleanup.loopexit ]
  br i1 %cmp1.not, label %for.body, label %cleanup7

cleanup7:                                         ; preds = %cleanup
  %retval.2.lcssa = phi ptr [ %retval.2, %cleanup ]
  %res = load i32, ptr %retval.2.lcssa, align 4
  ret i32 %res
}

source_filename = "test.ll"

@GlobIntONE = dso_local global i32 1, align 4
@GlobIntZERO = dso_local local_unnamed_addr global i32 0, align 4

define i32 @main() local_unnamed_addr {
entry:
  br label %for.body.peel.begin

for.body.peel.begin:                              ; preds = %entry
  br label %for.body.peel

for.body.peel:                                    ; preds = %for.body.peel.begin
  br i1 true, label %cleanup.peel, label %for.cond2.preheader.peel

for.cond2.preheader.peel:                         ; preds = %for.body.peel
  br label %cleanup.loopexit.peel

cleanup.loopexit.peel:                            ; preds = %for.cond2.preheader.peel
  br label %cleanup.peel

cleanup.peel:                                     ; preds = %cleanup.loopexit.peel, %for.body.peel
  %retval.2.peel = phi ptr [ undef, %for.body.peel ], [ @GlobIntONE, %cleanup.loopexit.peel ]
  br i1 true, label %for.body.peel.next, label %cleanup7

for.body.peel.next:                               ; preds = %cleanup.peel
  br label %for.body.peel.next1

for.body.peel.next1:                              ; preds = %for.body.peel.next
  br label %entry.peel.newph

entry.peel.newph:                                 ; preds = %for.body.peel.next1
  br label %for.body

for.body:                                         ; preds = %cleanup, %entry.peel.newph
  br i1 false, label %cleanup, label %for.cond2.preheader

for.cond2.preheader:                              ; preds = %for.body
  br label %cleanup.loopexit

cleanup.loopexit:                                 ; preds = %for.cond2.preheader
  br label %cleanup

cleanup:                                          ; preds = %cleanup.loopexit, %for.body
  br i1 false, label %for.body, label %cleanup7.loopexit, !llvm.loop !0

cleanup7.loopexit:                                ; preds = %cleanup
  %retval.2.lcssa.ph = phi ptr [ %retval.2.peel, %cleanup ]
  br label %cleanup7

cleanup7:                                         ; preds = %cleanup7.loopexit, %cleanup.peel
  %retval.2.lcssa = phi ptr [ %retval.2.peel, %cleanup.peel ], [ %retval.2.lcssa.ph, %cleanup7.loopexit ]
  %res = load i32, ptr %retval.2.lcssa, align 4
  ret i32 %res
}

!0 = distinct !{!0, !1}
!1 = !{!"llvm.loop.peeled.count", i32 1}

[dtcxzyw]

simplifyLoopAfterUnroll -> simplifyLoopIVs causes the miscompilation: https://alive2.llvm.org/ce/z/yiBsZt
I will post a fix later.

[dtcxzyw]

The root cause is:

1. simplifyInstruction(%retval.2.peel) returns @GlobIntONE. Thus, ScalarEvolution::createNodeForPHI returns SCEV expr @GlobIntONE for %retval.2.peel.
2. SimplifyIndvar::replaceIVUserWithLoopInvariant tries to replace the use of %retval.2.peel in %retval.2.lcssa.ph with @GlobIntONE.
3. SCEVExpander::expand reuses %retval.2.peel = phi ptr [ undef, %for.body.peel ], [ @GlobIntONE, %cleanup.loopexit.peel ] to generate code for @GlobIntONE. It is incorrect.

Two possible solutions:

1. Set CanUseUndef to false in simplifyInstruction.
2. Block this case in ScalarEvolution::canReuseInstruction.

@nikic @preames Any thoughts?

[nikic]

I think setting CanUseUndef=false would be the correct thing to do. The reverse replacement here is particularly fishy, but more generally, if we make an assumption about the value of undef at a particular use, we have to be consistent about that assumption, and SCEV cannot really guarantee that this is the case.