[InstCombine] Simplify phis with incoming pointer-casts.

[fhahn]

Summary

If the incoming values of a phi are pointer casts of the same original
value, replace the phi with a single cast. Such redundant phis are
somewhat common after loop-rotate and removing them can avoid some
unnecessary code bloat, e.g. because an iteration of a loop is peeled
off to make the phi invariant. It should also simplify further analysis
on its own.

InstCombine already uses stripPointerCasts in a couple of places and
also simplifies phis based on the incoming values, so the patch should
fit in the existing scope.

The patch causes binary changes in 47 out of 237 benchmarks in
MultiSource/SPEC2000/SPEC2006 with -O3 -flto on X86.

[lebedev.ri]

llvm/lib/Transforms/InstCombine/InstCombinePHI.cpp

1316

I think you want to extend foldPHIArgOpIntoPHI().

[nikic]

This needs tests for addrspacecast, I don't think it's handled correctly.

[fhahn]

In D98058#2607220, @nikic wrote:

This needs tests for addrspacecast, I don't think it's handled correctly.

Right, stripPointerCasts also looks through addrspacecast. I updated the code to use CastInst::CreatePointerCast, which should automatically use the right type of cast.

[fhahn]

llvm/lib/Transforms/InstCombine/InstCombinePHI.cpp

1316

I'm not sure. The checks for foldPHIArgOpIntoPHI are more restrictive than what is needed for pointer casts I think (e.g. the incoming values need to be instructions with matching opcodes and the first one must only have a single user).

I don't think we need to be that restrictive for most pointer casts. For bit casts/geps, which should effectively be no-ops in the end, it should always be safe to replace a PHI with a bit cast. For addrspacecast, that may not be true and replacing a phi might add an extra 'real' instruction (if the incoming values are used elsewhere). I'd prefer to not handle addrspacecast here if we can get away with less restrictions in the bit cast case.

[lebedev.ri]

This indeed won't really work with foldPHIArgOpIntoPHI(), first because we actually don't create a new PHI,
secondly, this transform does not use-count restrictions, while foldPHIArgOpIntoPHI() has some.

llvm/lib/Transforms/InstCombine/InstCombinePHI.cpp

1322–1328

I would recommend s/Inc/IV/

1325–1327

I would recommend a less brute-force approach.
Add a map<IV, stripped>, and don't redo the work if the result is known.

1325–1327

Well, i guess map is an overkill, just set<IV> should be plenty enough.

[fhahn]

Adjust names, use set to avoid re-doing work.

[fhahn]

llvm/lib/Transforms/InstCombine/InstCombinePHI.cpp

1322–1328

Updated all the names

1325–1327

Done, although I am not sure how often this will trigger. It will at least for the initial step. Not sure if you had something different in mind?

[lebedev.ri]

LGTM, thank you.

llvm/lib/Transforms/InstCombine/InstCombinePHI.cpp

1325–1327

This seems fine, thanks.
This is mostly to avoid worst-case scenarios with switches.

1326–1327

I'm being super nitpicky, but i'd suggest s/KnownEqual/CheckedIVs/

[fhahn]

llvm/lib/Transforms/InstCombine/InstCombinePHI.cpp

1326–1327

Done

llvm/lib/Transforms/InstCombine/InstCombinePHI.cpp

Instruction *InstCombinerImpl::visitPHINode(PHINode &PN) {
 
   // If all PHI operands are the same operation, pull them through the PHI,
   // reducing code size.
   if (isa<Instruction>(PN.getIncomingValue(0)) &&
       isa<Instruction>(PN.getIncomingValue(1)) &&
       cast<Instruction>(PN.getIncomingValue(0))->getOpcode() ==
           cast<Instruction>(PN.getIncomingValue(1))->getOpcode() &&
       PN.getIncomingValue(0)->hasOneUser())
     if (Instruction *Result = foldPHIArgOpIntoPHI(PN))
       return Result;
 
+  // If the incoming values are pointer casts of the same original value,
+  // replace the phi with a single cast.
+  if (PN.getType()->isPointerTy()) {
+    Value *IV0 = PN.getIncomingValue(0);
+    Value *IV0Stripped = IV0->stripPointerCasts();
+    // Set to keep track of values known to be equal to IV0Stripped after
+    // stripping pointer casts.
+    SmallPtrSet<Value *, 4> CheckedIVs;
+    CheckedIVs.insert(IV0);
+    if (IV0 != IV0Stripped &&
+        all_of(PN.incoming_values(), [&CheckedIVs, IV0Stripped](Value *IV) {
+          return !CheckedIVs.insert(IV).second ||
+                 IV0Stripped == IV->stripPointerCasts();
+        })) {
+      return CastInst::CreatePointerCast(IV0Stripped, PN.getType());
+    }
+  }
+
   // If this is a trivial cycle in the PHI node graph, remove it.  Basically, if
   // this PHI only has a single use (a PHI), and if that PHI only has one use (a
   // PHI)... break the cycle.
   if (PN.hasOneUse()) {
     if (Instruction *Result = foldIntegerTypedPHI(PN))
       return Result;
 
     Instruction *PHIUser = cast<Instruction>(PN.user_back());

llvm/test/Transforms/InstCombine/phi-pointercasts.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -instcombine -S < %s | FileCheck %s
 
 define void @test_bitcast_1(i1 %c, i32* %ptr) {
 ; CHECK-LABEL: @test_bitcast_1(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[CAST_0:%.*]] = bitcast i32* [[PTR:%.*]] to i8*
 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[B0:%.*]], label [[B1:%.*]]
 ; CHECK:       b0:
+; CHECK-NEXT:    [[CAST_0:%.*]] = bitcast i32* [[PTR:%.*]] to i8*
 ; CHECK-NEXT:    call void @use(i8* [[CAST_0]])
 ; CHECK-NEXT:    br label [[END:%.*]]
 ; CHECK:       b1:
-; CHECK-NEXT:    [[CAST_1:%.*]] = bitcast i32* [[PTR]] to i8*
 ; CHECK-NEXT:    br label [[END]]
 ; CHECK:       end:
-; CHECK-NEXT:    [[P:%.*]] = phi i8* [ [[CAST_0]], [[B0]] ], [ [[CAST_1]], [[B1]] ]
+; CHECK-NEXT:    [[P:%.*]] = bitcast i32* [[PTR]] to i8*
 ; CHECK-NEXT:    store i8 0, i8* [[P]], align 1
 ; CHECK-NEXT:    ret void
 ;
 entry:
   %cast.0 = bitcast i32* %ptr to i8*
   %cast.1 = bitcast i32* %ptr to i8*
   br i1 %c, label %b0, label %b1
 
end:
   ret void
 }
 
 define void @test_bitcast_2(i1 %c, i32* %ptr) {
 ; CHECK-LABEL: @test_bitcast_2(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[B0:%.*]], label [[B1:%.*]]
 ; CHECK:       b0:
-; CHECK-NEXT:    [[CAST_0:%.*]] = bitcast i32* [[PTR:%.*]] to i8*
 ; CHECK-NEXT:    br label [[END:%.*]]
 ; CHECK:       b1:
-; CHECK-NEXT:    [[CAST_1:%.*]] = bitcast i32* [[PTR]] to i8*
+; CHECK-NEXT:    [[CAST_1:%.*]] = bitcast i32* [[PTR:%.*]] to i8*
 ; CHECK-NEXT:    call void @use(i8* [[CAST_1]])
 ; CHECK-NEXT:    br label [[END]]
 ; CHECK:       end:
-; CHECK-NEXT:    [[P:%.*]] = phi i8* [ [[CAST_0]], [[B0]] ], [ [[CAST_1]], [[B1]] ]
+; CHECK-NEXT:    [[P:%.*]] = bitcast i32* [[PTR]] to i8*
 ; CHECK-NEXT:    store i8 0, i8* [[P]], align 1
 ; CHECK-NEXT:    ret void
 ;
 entry:
   br i1 %c, label %b0, label %b1
 
 b0:
   %cast.0 = bitcast i32* %ptr to i8*

 
 
 define void @test_bitcast_3(i1 %c, i32** %ptr) {
 ; CHECK-LABEL: @test_bitcast_3(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[LOAD_PTR:%.*]] = load i32*, i32** [[PTR:%.*]], align 8
 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[B0:%.*]], label [[B1:%.*]]
 ; CHECK:       b0:
-; CHECK-NEXT:    [[CAST_0:%.*]] = bitcast i32* [[LOAD_PTR]] to i8*
 ; CHECK-NEXT:    br label [[END:%.*]]
 ; CHECK:       b1:
 ; CHECK-NEXT:    [[CAST_1:%.*]] = bitcast i32* [[LOAD_PTR]] to i8*
 ; CHECK-NEXT:    call void @use(i8* [[CAST_1]])
 ; CHECK-NEXT:    br label [[END]]
 ; CHECK:       end:
-; CHECK-NEXT:    [[P:%.*]] = phi i8* [ [[CAST_0]], [[B0]] ], [ [[CAST_1]], [[B1]] ]
+; CHECK-NEXT:    [[P:%.*]] = bitcast i32* [[LOAD_PTR]] to i8*
 ; CHECK-NEXT:    store i8 0, i8* [[P]], align 1
 ; CHECK-NEXT:    ret void
 ;
 entry:
   %load.ptr = load i32*, i32** %ptr
   br i1 %c, label %b0, label %b1
 
 b0:

 ; CHECK-LABEL: @test_bitcast_with_extra_use(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[B0:%.*]], label [[B1:%.*]]
 ; CHECK:       b0:
 ; CHECK-NEXT:    [[CAST_0:%.*]] = bitcast i32* [[PTR:%.*]] to i8*
 ; CHECK-NEXT:    call void @use(i8* [[CAST_0]])
 ; CHECK-NEXT:    br label [[END:%.*]]
 ; CHECK:       b1:
-; CHECK-NEXT:    [[CAST_1:%.*]] = bitcast i32* [[PTR]] to i8*
 ; CHECK-NEXT:    br label [[END]]
 ; CHECK:       end:
-; CHECK-NEXT:    [[P:%.*]] = phi i8* [ [[CAST_0]], [[B0]] ], [ [[CAST_1]], [[B1]] ]
+; CHECK-NEXT:    [[P:%.*]] = bitcast i32* [[PTR]] to i8*
 ; CHECK-NEXT:    store i8 0, i8* [[P]], align 1
 ; CHECK-NEXT:    ret void
 ;
 entry:
   br i1 %c, label %b0, label %b1
 
 b0:
   %cast.0 = bitcast i32* %ptr to i8*

 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[B0:%.*]], label [[B1:%.*]]
 ; CHECK:       b0:
 ; CHECK-NEXT:    [[CAST_0:%.*]] = bitcast i32* [[PTR:%.*]] to i8*
 ; CHECK-NEXT:    call void @use(i8* [[CAST_0]])
 ; CHECK-NEXT:    br label [[END:%.*]]
 ; CHECK:       b1:
 ; CHECK-NEXT:    call void @use.i32(i32* [[PTR]])
-; CHECK-NEXT:    [[CAST_3:%.*]] = bitcast i32* [[PTR]] to i8*
 ; CHECK-NEXT:    br label [[END]]
 ; CHECK:       end:
-; CHECK-NEXT:    [[P:%.*]] = phi i8* [ [[CAST_0]], [[B0]] ], [ [[CAST_3]], [[B1]] ]
+; CHECK-NEXT:    [[P:%.*]] = bitcast i32* [[PTR]] to i8*
 ; CHECK-NEXT:    store i8 0, i8* [[P]], align 1
 ; CHECK-NEXT:    ret void
 ;
 entry:
   %gep = getelementptr i32, i32* %ptr, i32 0
   br i1 %c, label %b0, label %b1
 
 b0:

 
 end.2:
   ret void
 }
 
 define void @test_addrspacecast_1(i1 %c, i32* %ptr) {
 ; CHECK-LABEL: @test_addrspacecast_1(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[TMP0:%.*]] = bitcast i32* [[PTR:%.*]] to i8*
-; CHECK-NEXT:    [[CAST_1:%.*]] = addrspacecast i8* [[TMP0]] to i8 addrspace(1)*
 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[B0:%.*]], label [[B1:%.*]]
 ; CHECK:       b0:
-; CHECK-NEXT:    [[TMP1:%.*]] = bitcast i32* [[PTR]] to i8*
-; CHECK-NEXT:    [[CAST_0:%.*]] = addrspacecast i8* [[TMP1]] to i8 addrspace(1)*
 ; CHECK-NEXT:    br label [[END:%.*]]
 ; CHECK:       b1:
+; CHECK-NEXT:    [[TMP0:%.*]] = bitcast i32* [[PTR:%.*]] to i8*
+; CHECK-NEXT:    [[CAST_1:%.*]] = addrspacecast i8* [[TMP0]] to i8 addrspace(1)*
 ; CHECK-NEXT:    call void @use.i8.addrspace1(i8 addrspace(1)* [[CAST_1]])
 ; CHECK-NEXT:    br label [[END]]
 ; CHECK:       end:
-; CHECK-NEXT:    [[P:%.*]] = phi i8 addrspace(1)* [ [[CAST_0]], [[B0]] ], [ [[CAST_1]], [[B1]] ]
+; CHECK-NEXT:    [[TMP1:%.*]] = bitcast i32* [[PTR]] to i8*
+; CHECK-NEXT:    [[P:%.*]] = addrspacecast i8* [[TMP1]] to i8 addrspace(1)*
 ; CHECK-NEXT:    store i8 0, i8 addrspace(1)* [[P]], align 1
 ; CHECK-NEXT:    ret void
 ;
 entry:
   %cast.0 = addrspacecast i32* %ptr to i8 addrspace(1)*
   %cast.1 = addrspacecast i32* %ptr to i8 addrspace(1)*
   br i1 %c, label %b0, label %b1