Sorting of BBs misses bug

[nunoplopes]

We miss a bug in NewGVN (llvm/llvm-project#56149) because the ordering of BBs is not optimal. We have a jump to a BB that appears before, so we never see that edge.

%for.end:
  store i32 5, ptr @a, align 4
  %0 = trunc i32 5 to i16
  %cmp2 = icmp slt i16 %0, 7
  br i1 %cmp2, label %L, label %if.end

%if.end:
  %d.0 = phi i32 [ %5, %L ], [ 0, %for.end ]
  %1 = load i32, ptr @a, align 4
  %sext = shl i32 %d.0, 16
  %conv6 = ashr i32 %sext, 16
  %cmp7.not = icmp slt i32 %1, %conv6
  br i1 %cmp7.not, label %while.cond9.preheader, label %while.cond.preheader

%L:
  %5 = load i32, ptr @a, align 4
  %and = and i32 %5, 1
  %neg = xor i32 %and, 4294967295
  store i32 %neg, ptr @a, align 4
  br label %if.end  ; backedge here for no good reason. plus it never gets unrolled

Full test:

@a = global i32 0, align 4
@b = global i32 0, align 4

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

for.end:                                          ; preds = %entry
  store i32 5, ptr @a, align 4
  %0 = trunc i32 5 to i16
  %cmp2 = icmp slt i16 %0, 7
  br i1 %cmp2, label %L, label %if.end

L:                                                ; preds = %while.end14, %for.end
  %1 = load i32, ptr @a, align 4
  %and = and i32 %1, 1
  %neg = xor i32 %and, -1
  store i32 %neg, ptr @a, align 4
  br label %if.end

if.end:                                           ; preds = %L, %for.end
  %d.0 = phi i32 [ %1, %L ], [ 0, %for.end ]
  %2 = load i32, ptr @a, align 4
  %sext = shl i32 %d.0, 16
  %conv6 = ashr i32 %sext, 16
  %cmp7.not = icmp slt i32 %2, %conv6
  br i1 %cmp7.not, label %while.cond9.preheader, label %while.cond.preheader

while.cond.preheader:                             ; preds = %if.end
  br label %while.cond.preheader

while.cond9.preheader:                            ; preds = %if.end
  %3 = load i32, ptr @a, align 4
  %cmp117 = icmp eq i32 %3, %conv6
  br i1 %cmp117, label %while.body13.preheader, label %while.end14

while.body13.preheader:                           ; preds = %while.cond9.preheader
  br label %while.body13

while.body13:                                     ; preds = %while.body13.preheader, %while.body13
  %4 = load i32, ptr @a, align 4
  %cmp11 = icmp eq i32 %4, %conv6
  br i1 %cmp11, label %while.body13, label %while.end14.loopexit

while.end14.loopexit:                             ; preds = %while.body13
  %.lcssa8 = phi i32 [ %4, %while.body13 ]
  br label %while.end14

while.end14:                                      ; preds = %while.end14.loopexit, %while.cond9.preheader
  %.lcssa = phi i32 [ %3, %while.cond9.preheader ], [ %.lcssa8, %while.end14.loopexit ]
  %5 = load i32, ptr @b, align 4
  %cmp16.not = icmp slt i32 %.lcssa, %5
  br i1 %cmp16.not, label %if.end19, label %L

if.end19:                                         ; preds = %while.end14
  ret i32 0
}