GVNSink: add test to show GVN-aware sinking

[artagnon]

Summary

As a follow-up to D156451, add a test corresponding to the following
program, after running it through GVN:

void BeamFormWeights(int a[20000], int beam) {
  for (int i = 0; i < 10000; ++i) {
    if (i == beam)
      a[2 * i] = 0;
    else
      a[2 * i] = 1;
  }
}

Sinking in this particular case is particularly challenging, and can
only be done by a GVN-aware sinking pass.

[nikic]

llvm/test/Transforms/GVNSink/gvn-awareness.ll

51

Please at least run this through SROA. The test is a weird mix of completely unoptimized IR plus a GVN replacement.

[artagnon]

llvm/test/Transforms/GVNSink/gvn-awareness.ll

51

When I run it through SROA, gvn-sink no longer works.

[xbolva00]

llvm/test/Transforms/GVNSink/gvn-awareness.ll

51

Maybe also add phaseordering test?

If this fails to work after sroa, than this optimization will not work anyway with -O2/-O3

[artagnon]

Address review comment; run test through opt pipeline until gvn-sink.

[artagnon]

llvm/test/Transforms/GVNSink/gvn-awareness.ll

51

Sorry, what do you mean by a phaseordering test?

[nikic]

llvm/test/Transforms/GVNSink/gvn-awareness.ll

51

A phase ordering test checks the whole O3 pipeline. In cases like these where optimization depends on precise pass ordering, a phase ordering test ensures that the correct pass interaction is preserved going forward.

I've committed a phase ordering test for your motivating case in https://github.com/llvm/llvm-project/commit/bbe2887f5e9ca005b0f1b96c858969ee3ba646f4 and submitted D156532 for a possible fix that does not rely on GVNSink.

[artagnon]

llvm/test/Transforms/GVNSink/gvn-awareness.ll

51

Thanks a lot for this! Since the motivating example is fixed, and since gvn-sink only seems to cause regressions on benchmarks, I'm tempted to stop working on gvn-sink. Do you think we should abandon this patch?

llvm/test/Transforms/GVNSink/gvn-awareness.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --version 2
+; Test to show a sinking operation that would have been impossible without
+; GVN-awareness.
+; RUN: opt -passes=gvn-sink -S < %s | FileCheck %s
+
+define void @gvn_awareness(ptr nocapture writeonly %a, i32 %beam) {
+; CHECK-LABEL: define void @gvn_awareness
+; CHECK-SAME: (ptr nocapture writeonly [[A:%.*]], i32 [[BEAM:%.*]]) {
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[FOR_COND:%.*]]
+; CHECK:       for.cond:
+; CHECK-NEXT:    [[I_0:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[INC:%.*]], [[FOR_INC:%.*]] ]
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i32 [[I_0]], 10000
+; CHECK-NEXT:    br i1 [[CMP]], label [[FOR_BODY:%.*]], label [[FOR_COND_CLEANUP:%.*]]
+; CHECK:       for.cond.cleanup:
+; CHECK-NEXT:    ret void
+; CHECK:       for.body:
+; CHECK-NEXT:    [[CMP1:%.*]] = icmp eq i32 [[I_0]], [[BEAM]]
+; CHECK-NEXT:    br i1 [[CMP1]], label [[IF_THEN:%.*]], label [[IF_ELSE:%.*]]
+; CHECK:       if.then:
+; CHECK-NEXT:    br label [[FOR_INC]]
+; CHECK:       if.else:
+; CHECK-NEXT:    br label [[FOR_INC]]
+; CHECK:       for.inc:
+; CHECK-NEXT:    [[DOTSINK:%.*]] = phi i32 [ 0, [[IF_THEN]] ], [ 1, [[IF_ELSE]] ]
+; CHECK-NEXT:    [[MUL:%.*]] = shl nuw nsw i32 [[I_0]], 1
+; CHECK-NEXT:    [[IDXPROM:%.*]] = zext i32 [[MUL]] to i64
+; CHECK-NEXT:    [[ARRAYIDX:%.*]] = getelementptr inbounds i32, ptr [[A]], i64 [[IDXPROM]]
+; CHECK-NEXT:    store i32 [[DOTSINK]], ptr [[ARRAYIDX]], align 4
+; CHECK-NEXT:    [[INC]] = add nuw nsw i32 [[I_0]], 1
+; CHECK-NEXT:    br label [[FOR_COND]]
+;
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+  %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ]
+  %cmp = icmp ult i32 %i.0, 10000
+  br i1 %cmp, label %for.body, label %for.cond.cleanup
+
+for.cond.cleanup:                                 ; preds = %for.cond
+  ret void
+
+for.body:                                         ; preds = %for.cond
+  %cmp1 = icmp eq i32 %i.0, %beam
+  br i1 %cmp1, label %if.then, label %if.else
+
+if.then:                                          ; preds = %for.body
+  %mul = shl nuw nsw i32 %i.0, 1
+  %idxprom = zext i32 %mul to i64
+  %arrayidx = getelementptr inbounds i32, ptr %a, i64 %idxprom
+  store i32 0, ptr %arrayidx, align 4
+  br label %for.inc
+
+if.else:                                          ; preds = %for.body
+  %mul2 = shl nuw nsw i32 %i.0, 1
+  %idxprom3 = zext i32 %mul2 to i64
+  %arrayidx4 = getelementptr inbounds i32, ptr %a, i64 %idxprom3
+  store i32 1, ptr %arrayidx4, align 4
+  br label %for.inc
+
+for.inc:                                          ; preds = %if.then, %if.else
+  %inc = add nuw nsw i32 %i.0, 1
+  br label %for.cond
+}