[SimplifyCFG] Rerun PHI deduplication after common code sinkinkg (PR51092)

[lebedev.ri]

Summary

SinkCommonCodeFromPredecessors() doesn't itself ensure that duplicate PHI nodes aren't created.
I suppose, we could teach it to do that on-the-fly (& account for the already-existing PHI nodes,
& adjust costmodel), the diff will be bigger than this.

The alternative is to schedule a new EarlyCSE pass invocation somewhere later in the pipeline.
Clearly, we don't have any EarlyCSE runs in module optimization passline, so this pattern isn't cleaned up...
That would perhaps better, but it will again have some compile time impact.

[xbolva00]

The alternative is to schedule a new EarlyCSE pass invocation somewhere later in the pipeline.
Clearly, we don't have any EarlyCSE runs in module optimization passline, so this pattern isn't cleaned up...

Maybe slowly we gather more and more motivation cases to justify another run of CSE? As https://reviews.llvm.org/rG57bb4787d72f1ae64f877b05c98d506602ac5958 pointed out, 0.26% CT regression is not so bad, I think it is OK.

I remember this PR where another CSE run would help as well.
https://bugs.llvm.org/show_bug.cgi?id=42755

[lebedev.ri]

Adjust checklines in one more test.

[RKSimon]

LGTM as a stopgap until we can decide what to do about additional CSE runs - cheers

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

6735

Add comment to explain why the early out?

llvm/test/Transforms/PhaseOrdering/X86/earlycse-after-simplifycfg-two-entry-phi-node-folding.ll

7–9

Please can you mention PR51092 in a comment here? It helps with quick triage without git log/blame trawling.

[lebedev.ri]

In D106010#2879267, @RKSimon wrote:

LGTM as a stopgap until we can decide what to do about additional CSE runs - cheers

Thank you for the review!

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

bool SimplifyCFGOpt::simplifyOnceImpl(BasicBlock *BB) {
   Changed |= removeUndefIntroducingPredecessor(BB, DTU);
 
   // Merge basic blocks into their predecessor if there is only one distinct
   // pred, and if there is only one distinct successor of the predecessor, and
   // if there are no PHI nodes.
   if (MergeBlockIntoPredecessor(BB, DTU))
     return true;
 
   if (SinkCommon && Options.SinkCommonInsts)
-    Changed |= SinkCommonCodeFromPredecessors(BB, DTU);
+    if (SinkCommonCodeFromPredecessors(BB, DTU)) {
+      // SinkCommonCodeFromPredecessors() does not automatically CSE PHI's,
+      // so we may now how duplicate PHI's.
+      // Let's rerun EliminateDuplicatePHINodes() first,
+      // before FoldTwoEntryPHINode() potentially converts them into select's,
+      // after which we'd need a whole EarlyCSE pass run to cleanup them.
+      return true;
+    }
 
   IRBuilder<> Builder(BB);
 
   if (Options.FoldTwoEntryPHINode) {
     // If there is a trivial two-entry PHI node in this basic block, and we can
     // eliminate it, do so now.
     if (auto *PN = dyn_cast<PHINode>(BB->begin()))
       if (PN->getNumIncomingValues() == 2)

llvm/test/Transforms/PGOProfile/cspgo_profile_summary.ll

 for.inc:
   %inc6 = add nuw nsw i32 %i.0, 1
   br label %for.cond
 
 for.end:
   ret void
 }
 ; PGOSUMMARY-LABEL: @bar
-; PGOSUMMARY: %odd.sink{{[0-9]*}} = select i1 %tobool{{[0-9]*}}, i32* @even, i32* @odd
+; PGOSUMMARY: %even.odd = select i1 %tobool{{[0-9]*}}, i32* @even, i32* @odd
 ; PGOSUMMARY-SAME: !prof ![[BW_PGO_BAR:[0-9]+]]
 ; CSPGOSUMMARY-LABEL: @bar
-; CSPGOSUMMARY: %odd.sink{{[0-9]*}} = select i1 %tobool{{[0-9]*}}, i32* @even, i32* @odd
+; CSPGOSUMMARY: %even.odd = select i1 %tobool{{[0-9]*}}, i32* @even, i32* @odd
 ; CSPGOSUMMARY-SAME: !prof ![[BW_CSPGO_BAR:[0-9]+]]
 
 define internal fastcc i32 @cond(i32 %i) {
 entry:
   %rem = srem i32 %i, 2
   ret i32 %rem
 }
 
for.body:
   call fastcc void @barbar()
   %add4 = add nsw i32 %call, 2
   br label %for.cond
 
 for.end:
   ret void
 }
 ; CSPGOSUMMARY-LABEL: @foo
-; CSPGOSUMMARY: %odd.sink.i{{[0-9]*}} = select i1 %tobool.i{{[0-9]*}}, i32* @even, i32* @odd
+; CSPGOSUMMARY: %even.odd.i = select i1 %tobool.i{{[0-9]*}}, i32* @even, i32* @odd
 ; CSPGOSUMMARY-SAME: !prof ![[BW_CSPGO_BAR]]
-; CSPGOSUMMARY: %odd.sink.i{{[0-9]*}} = select i1 %tobool.i{{[0-9]*}}, i32* @even, i32* @odd
+; CSPGOSUMMARY: %even.odd.i2 = select i1 %tobool.i{{[0-9]*}}, i32* @even, i32* @odd
 ; CSPGOSUMMARY-SAME: !prof ![[BW_CSPGO_BAR]]
 
 declare dso_local i32 @bar_m(i32)
 declare dso_local i32 @bar_m2(i32)
 
 define internal fastcc void @barbar() {
 entry:
   %0 = load i32, i32* @odd, align 4

llvm/test/Transforms/PhaseOrdering/X86/earlycse-after-simplifycfg-two-entry-phi-node-folding.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -O3 -S -enable-new-pm=0 < %s   | FileCheck %s --check-prefixes=ALL
 ; RUN: opt -passes='default<O3>' -S < %s  | FileCheck %s --check-prefixes=ALL
 
 target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 
+; PR51092: SimplifyCFG might produce duplicate PHI's/select's.
+; We need to deduplicate them so that further transformations are possible.
 define dso_local void @foo(i32* %in, i64 %lo, i64 %hi, i32 %ishi) #0 {
 ; ALL-LABEL: @foo(
 ; ALL-NEXT:  entry:
 ; ALL-NEXT:    [[TOBOOL_NOT:%.*]] = icmp eq i32 [[ISHI:%.*]], 0
-; ALL-NEXT:    [[ARRAYIDX1:%.*]] = getelementptr inbounds i32, i32* [[IN:%.*]], i64 [[LO:%.*]]
-; ALL-NEXT:    [[ARRAYIDX:%.*]] = getelementptr inbounds i32, i32* [[IN]], i64 [[HI:%.*]]
-; ALL-NEXT:    [[ARRAYIDX1_SINK1:%.*]] = select i1 [[TOBOOL_NOT]], i32* [[ARRAYIDX1]], i32* [[ARRAYIDX]]
-; ALL-NEXT:    [[ARRAYIDX1_SINK:%.*]] = select i1 [[TOBOOL_NOT]], i32* [[ARRAYIDX1]], i32* [[ARRAYIDX]]
-; ALL-NEXT:    [[ARRAYVAL2:%.*]] = load i32, i32* [[ARRAYIDX1_SINK1]], align 4
+; ALL-NEXT:    [[LO_HI:%.*]] = select i1 [[TOBOOL_NOT]], i64 [[LO:%.*]], i64 [[HI:%.*]]
+; ALL-NEXT:    [[ARRAYIDX1:%.*]] = getelementptr inbounds i32, i32* [[IN:%.*]], i64 [[LO_HI]]
+; ALL-NEXT:    [[ARRAYVAL2:%.*]] = load i32, i32* [[ARRAYIDX1]], align 4
 ; ALL-NEXT:    [[INC2:%.*]] = add nsw i32 [[ARRAYVAL2]], 1
-; ALL-NEXT:    store i32 [[INC2]], i32* [[ARRAYIDX1_SINK]], align 4
+; ALL-NEXT:    store i32 [[INC2]], i32* [[ARRAYIDX1]], align 4
 ; ALL-NEXT:    ret void
 ;
 entry:
   %in.addr = alloca i32*, align 8
   %lo.addr = alloca i64, align 8
   %hi.addr = alloca i64, align 8
   %ishi.addr = alloca i32, align 4
   store i32* %in, i32** %in.addr, align 8

llvm/test/Transforms/SimplifyCFG/X86/sink-common-code.ll

if.end:
   ret i1 %tobool4
 }
 
 declare i32 @foo(i32, i32) nounwind readnone
 
 define i32 @test3(i1 zeroext %flag, i32 %x, i32 %y) {
 ; CHECK-LABEL: @test3(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[Y_SINK1:%.*]] = select i1 [[FLAG:%.*]], i32 [[X:%.*]], i32 [[Y:%.*]]
-; CHECK-NEXT:    [[Y_SINK:%.*]] = select i1 [[FLAG]], i32 [[X]], i32 [[Y]]
-; CHECK-NEXT:    [[X1:%.*]] = call i32 @foo(i32 [[Y_SINK1]], i32 0) #[[ATTR0:[0-9]+]]
-; CHECK-NEXT:    [[Y1:%.*]] = call i32 @foo(i32 [[Y_SINK]], i32 1) #[[ATTR0]]
+; CHECK-NEXT:    [[X_Y:%.*]] = select i1 [[FLAG:%.*]], i32 [[X:%.*]], i32 [[Y:%.*]]
+; CHECK-NEXT:    [[X1:%.*]] = call i32 @foo(i32 [[X_Y]], i32 0) #[[ATTR0:[0-9]+]]
+; CHECK-NEXT:    [[Y1:%.*]] = call i32 @foo(i32 [[X_Y]], i32 1) #[[ATTR0]]
 ; CHECK-NEXT:    [[RET:%.*]] = add i32 [[X1]], [[Y1]]
 ; CHECK-NEXT:    ret i32 [[RET]]
 ;
 entry:
   br i1 %flag, label %if.then, label %if.else
 
 if.then:
   %x0 = call i32 @foo(i32 %x, i32 0) nounwind readnone
if.end:
   %ret = add i32 %xx, %yy
   ret i32 %ret
 }
 
 
 define i32 @test4(i1 zeroext %flag, i32 %x, i32* %y) {
 ; CHECK-LABEL: @test4(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[DOTSINK:%.*]] = select i1 [[FLAG:%.*]], i32 5, i32 7
-; CHECK-NEXT:    [[B:%.*]] = add i32 [[X:%.*]], [[DOTSINK]]
+; CHECK-NEXT:    [[DOT:%.*]] = select i1 [[FLAG:%.*]], i32 5, i32 7
+; CHECK-NEXT:    [[B:%.*]] = add i32 [[X:%.*]], [[DOT]]
 ; CHECK-NEXT:    store i32 [[B]], i32* [[Y:%.*]], align 4
 ; CHECK-NEXT:    ret i32 1
 ;
 entry:
   br i1 %flag, label %if.then, label %if.else
 
 if.then:
   %a = add i32 %x, 5

 if.end:
   ret i32 1
 }
 
 
 define i32 @test6(i1 zeroext %flag, i32 %x, i32* %y) {
 ; CHECK-LABEL: @test6(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[DOTSINK:%.*]] = select i1 [[FLAG:%.*]], i32 5, i32 7
-; CHECK-NEXT:    [[B:%.*]] = add i32 [[X:%.*]], [[DOTSINK]]
+; CHECK-NEXT:    [[DOT:%.*]] = select i1 [[FLAG:%.*]], i32 5, i32 7
+; CHECK-NEXT:    [[B:%.*]] = add i32 [[X:%.*]], [[DOT]]
 ; CHECK-NEXT:    store volatile i32 [[B]], i32* [[Y:%.*]], align 4
 ; CHECK-NEXT:    ret i32 1
 ;
 entry:
   br i1 %flag, label %if.then, label %if.else
 
 if.then:
   %a = add i32 %x, 5
   store volatile i32 %a, i32* %y
   br label %if.end
 
 if.else:
   %b = add i32 %x, 7
   store volatile i32 %b, i32* %y
   br label %if.end
 
 if.end:
   ret i32 1
 }
 
 
 define i32 @test7(i1 zeroext %flag, i32 %x, i32* %y) {
 ; CHECK-LABEL: @test7(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[DOTSINK:%.*]] = select i1 [[FLAG:%.*]], i32 5, i32 7
+; CHECK-NEXT:    [[DOT:%.*]] = select i1 [[FLAG:%.*]], i32 5, i32 7
 ; CHECK-NEXT:    [[W:%.*]] = load volatile i32, i32* [[Y:%.*]], align 4
-; CHECK-NEXT:    [[B:%.*]] = add i32 [[W]], [[DOTSINK]]
+; CHECK-NEXT:    [[B:%.*]] = add i32 [[W]], [[DOT]]
 ; CHECK-NEXT:    store volatile i32 [[B]], i32* [[Y]], align 4
 ; CHECK-NEXT:    ret i32 1
 ;
 entry:
   br i1 %flag, label %if.then, label %if.else
 
 if.then:
   %z = load volatile i32, i32* %y

 declare i32 @llvm.ctlz.i32(i32 %x, i1 immarg) readnone
 declare i32 @llvm.cttz.i32(i32 %x, i1 immarg) readnone
 
 
 ; The TBAA metadata should be properly combined.
 define i32 @test13(i1 zeroext %flag, i32 %x, i32* %y) {
 ; CHECK-LABEL: @test13(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[DOTSINK:%.*]] = select i1 [[FLAG:%.*]], i32 5, i32 7
+; CHECK-NEXT:    [[DOT:%.*]] = select i1 [[FLAG:%.*]], i32 5, i32 7
 ; CHECK-NEXT:    [[W:%.*]] = load volatile i32, i32* [[Y:%.*]], align 4
-; CHECK-NEXT:    [[B:%.*]] = add i32 [[W]], [[DOTSINK]]
+; CHECK-NEXT:    [[B:%.*]] = add i32 [[W]], [[DOT]]
 ; CHECK-NEXT:    store volatile i32 [[B]], i32* [[Y]], align 4, !tbaa [[TBAA4:![0-9]+]]
 ; CHECK-NEXT:    ret i32 1
 ;
 entry:
   br i1 %flag, label %if.then, label %if.else
 
 if.then:
   %z = load volatile i32, i32* %y

 !3 = !{ !"const float", !2, i64 0 }
 !4 = !{ !"special float", !2, i64 1 }
 
 
 ; The call should be commoned.
 define i32 @test13a(i1 zeroext %flag, i32 %w, i32 %x, i32 %y) {
 ; CHECK-LABEL: @test13a(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[Y_SINK:%.*]] = select i1 [[FLAG:%.*]], i32 [[X:%.*]], i32 [[Y:%.*]]
-; CHECK-NEXT:    [[SV2:%.*]] = call i32 @bar(i32 [[Y_SINK]])
+; CHECK-NEXT:    [[X_Y:%.*]] = select i1 [[FLAG:%.*]], i32 [[X:%.*]], i32 [[Y:%.*]]
+; CHECK-NEXT:    [[SV2:%.*]] = call i32 @bar(i32 [[X_Y]])
 ; CHECK-NEXT:    ret i32 1
 ;
 entry:
   br i1 %flag, label %if.then, label %if.else
 
 if.then:
   %sv1 = call i32 @bar(i32 %x)
   br label %if.end
 
 if.else:
   %sv2 = call i32 @bar(i32 %y)
   br label %if.end
 
 if.end:
   %p = phi i32 [ %sv1, %if.then ], [ %sv2, %if.else ]
   ret i32 1
 }
 declare i32 @bar(i32)
 
 
 ; The load should be commoned.
 define i32 @test14(i1 zeroext %flag, i32 %w, i32 %x, i32 %y, %struct.anon* %s) {
 ; CHECK-LABEL: @test14(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[DOTSINK1:%.*]] = select i1 [[FLAG:%.*]], i32 1, i32 4
-; CHECK-NEXT:    [[DOTSINK:%.*]] = select i1 [[FLAG]], i32 56, i32 57
-; CHECK-NEXT:    [[DUMMY2:%.*]] = add i32 [[X:%.*]], [[DOTSINK1]]
+; CHECK-NEXT:    [[DOT:%.*]] = select i1 [[FLAG:%.*]], i32 1, i32 4
+; CHECK-NEXT:    [[DOT2:%.*]] = select i1 [[FLAG]], i32 56, i32 57
+; CHECK-NEXT:    [[DUMMY2:%.*]] = add i32 [[X:%.*]], [[DOT]]
 ; CHECK-NEXT:    [[GEPB:%.*]] = getelementptr inbounds [[STRUCT_ANON:%.*]], %struct.anon* [[S:%.*]], i32 0, i32 1
 ; CHECK-NEXT:    [[SV2:%.*]] = load i32, i32* [[GEPB]], align 4
-; CHECK-NEXT:    [[CMP2:%.*]] = icmp eq i32 [[SV2]], [[DOTSINK]]
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp eq i32 [[SV2]], [[DOT2]]
 ; CHECK-NEXT:    ret i32 1
 ;
 entry:
   br i1 %flag, label %if.then, label %if.else
 
 if.then:
   %dummy = add i32 %x, 1
   %gepa = getelementptr inbounds %struct.anon, %struct.anon* %s, i32 0, i32 1

 if.end:
   ret i1 true
 }
 
 
 define i32 @test_pr30373a(i1 zeroext %flag, i32 %x, i32 %y) {
 ; CHECK-LABEL: @test_pr30373a(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[Y_SINK1:%.*]] = select i1 [[FLAG:%.*]], i32 [[X:%.*]], i32 [[Y:%.*]]
-; CHECK-NEXT:    [[Y_SINK:%.*]] = select i1 [[FLAG]], i32 [[X]], i32 [[Y]]
-; CHECK-NEXT:    [[X1:%.*]] = call i32 @foo(i32 [[Y_SINK1]], i32 0) #[[ATTR0]]
-; CHECK-NEXT:    [[Y1:%.*]] = call i32 @foo(i32 [[Y_SINK]], i32 1) #[[ATTR0]]
+; CHECK-NEXT:    [[X_Y:%.*]] = select i1 [[FLAG:%.*]], i32 [[X:%.*]], i32 [[Y:%.*]]
+; CHECK-NEXT:    [[X1:%.*]] = call i32 @foo(i32 [[X_Y]], i32 0) #[[ATTR0]]
+; CHECK-NEXT:    [[Y1:%.*]] = call i32 @foo(i32 [[X_Y]], i32 1) #[[ATTR0]]
 ; CHECK-NEXT:    [[Z1:%.*]] = lshr i32 [[Y1]], 8
 ; CHECK-NEXT:    [[RET:%.*]] = add i32 [[X1]], [[Z1]]
 ; CHECK-NEXT:    ret i32 [[RET]]
 ;
 entry:
   br i1 %flag, label %if.then, label %if.else
 
 if.then:
if.end:
   %ret = add i32 %xx, %yy
   ret i32 %ret
 }
 
 
 define i32 @test_pr30373b(i1 zeroext %flag, i32 %x, i32 %y) {
 ; CHECK-LABEL: @test_pr30373b(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[Y_SINK1:%.*]] = select i1 [[FLAG:%.*]], i32 [[X:%.*]], i32 [[Y:%.*]]
-; CHECK-NEXT:    [[Y_SINK:%.*]] = select i1 [[FLAG]], i32 [[X]], i32 [[Y]]
-; CHECK-NEXT:    [[X1:%.*]] = call i32 @foo(i32 [[Y_SINK1]], i32 0) #[[ATTR0]]
-; CHECK-NEXT:    [[Y1:%.*]] = call i32 @foo(i32 [[Y_SINK]], i32 1) #[[ATTR0]]
+; CHECK-NEXT:    [[X_Y:%.*]] = select i1 [[FLAG:%.*]], i32 [[X:%.*]], i32 [[Y:%.*]]
+; CHECK-NEXT:    [[X1:%.*]] = call i32 @foo(i32 [[X_Y]], i32 0) #[[ATTR0]]
+; CHECK-NEXT:    [[Y1:%.*]] = call i32 @foo(i32 [[X_Y]], i32 1) #[[ATTR0]]
 ; CHECK-NEXT:    [[Z1:%.*]] = lshr i32 [[Y1]], 8
 ; CHECK-NEXT:    [[RET:%.*]] = add i32 [[X1]], [[Z1]]
 ; CHECK-NEXT:    ret i32 [[RET]]
 ;
 entry:
   br i1 %flag, label %if.then, label %if.else
 
 if.then:

 }
 
 
 %T = type {i32, i32}
 
 define i32 @test_insertvalue(i1 zeroext %flag, %T %P) {
 ; CHECK-LABEL: @test_insertvalue(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[DOTSINK:%.*]] = select i1 [[FLAG:%.*]], i32 0, i32 1
-; CHECK-NEXT:    [[T2:%.*]] = insertvalue [[T:%.*]] [[P:%.*]], i32 [[DOTSINK]], 0
+; CHECK-NEXT:    [[DOT:%.*]] = select i1 [[FLAG:%.*]], i32 0, i32 1
+; CHECK-NEXT:    [[T2:%.*]] = insertvalue [[T:%.*]] [[P:%.*]], i32 [[DOT]], 0
 ; CHECK-NEXT:    ret i32 1
 ;
 entry:
   br i1 %flag, label %if.then, label %if.else
 
 if.then:
   %t1 = insertvalue %T %P, i32 0, 0
   br label %if.end

 
 end:
   ret void
 }
 
 define void @indirect_caller(i1 %c, i32 %v, void (i32)* %foo, void (i32)* %bar) {
 ; CHECK-LABEL: @indirect_caller(
 ; CHECK-NEXT:  end:
-; CHECK-NEXT:    [[BAR_SINK:%.*]] = select i1 [[C:%.*]], void (i32)* [[FOO:%.*]], void (i32)* [[BAR:%.*]]
-; CHECK-NEXT:    tail call void [[BAR_SINK]](i32 [[V:%.*]])
+; CHECK-NEXT:    [[FOO_BAR:%.*]] = select i1 [[C:%.*]], void (i32)* [[FOO:%.*]], void (i32)* [[BAR:%.*]]
+; CHECK-NEXT:    tail call void [[FOO_BAR]](i32 [[V:%.*]])
 ; CHECK-NEXT:    ret void
 ;
   br i1 %c, label %call_foo, label %call_bar
 
 call_foo:
   tail call void %foo(i32 %v)
   br label %end