[InstCombine] Teach instcombine not to create extra PHI nodes when folding GEPs

[sbaranga]

Summary

InstCombine tries to transform GEP(PHI(GEP1, GEP2, ..)) into GEP(GEP(PHI(...))
when possible. However, this may leave the old PHI node around. Even if we
do end up folding the GEPs, having an extra PHI node might not be beneficial.

This change makes the transformation more conservative. We now only do this if
the PHI has only one use, and can therefore be removed after the transformation.

[sbaranga]

Benchmark results (lnt, spec2k, spec2k6):

spec.cpu2000.ref.300_twolf -1.96%
spec.cpu2006.ref.400_perlbench -1.55%
lnt.MultiSource/Applications/sqlite3/sqlite3 -1.48%
lnt.MultiSource/Benchmarks/Olden/tsp/tsp -1.26%
spec.cpu2000.ref.176_gcc -1.02%

[sbaranga]

Ping?

[mcrosier]

This look fairly reasonable to me, but I'd prefer input from the other reviewers before signing off on this change.

[majnemer]

This looks straightforward enough, LGTM. It might be interesting to investigate if we should canonicalize multiple PHIs into a single PHI in cases where the IR ended up like this for other reasons.

lib/Transforms/InstCombine/InstructionCombining.cpp

for (auto I = PN->op_begin()+1, E = PN->op_end(); I !=E; ++I) {
             CurTy = CT->getTypeAtIndex(Op1->getOperand(J));
           } else {
             CurTy = nullptr;
           }
         }
       }
     }
 
-    GetElementPtrInst *NewGEP = cast<GetElementPtrInst>(Op1->clone());
+    // If not all GEPs are identical we'll have to create a new PHI node.
+    // Check that the old PHI node has only one use so that it will get
+    // removed.
+    if (DI != -1 && !PN->hasOneUse())
+      return nullptr;
 
+    GetElementPtrInst *NewGEP = cast<GetElementPtrInst>(Op1->clone());
     if (DI == -1) {
       // All the GEPs feeding the PHI are identical. Clone one down into our
       // BB so that it can be merged with the current GEP.
       GEP.getParent()->getInstList().insert(
           GEP.getParent()->getFirstInsertionPt(), NewGEP);
     } else {
       // All the GEPs feeding the PHI differ at a single offset. Clone a GEP
       // into the current block so it can be merged, and create a new PHI to

test/Transforms/InstCombine/gepphigep.ll

exit:
   %incptr3 = getelementptr inbounds i8, i8* %ptr2, i64 1
   ret i8* %incptr3
 
 ; CHECK-LABEL: @test4(
 ; CHECK: loop.body:
 ; CHECK: getelementptr{{.*}}i64 1
 ; CHECK: exit:
 }
+
+@.str.4 = external unnamed_addr constant [100 x i8], align 1
+
+; Instcombine shouldn't add new PHI nodes while folding GEPs if that will leave
+; old PHI nodes behind as this is not clearly beneficial.
+; CHECK-LABEL: @test5(
+define void @test5(i16 *%idx, i8 **%in) #0 {
+entry:
+  %0 = load i8*, i8** %in
+  %incdec.ptr = getelementptr inbounds i8, i8* %0, i32 1
+  %1 = load i8, i8* %incdec.ptr, align 1
+  %cmp23 = icmp eq i8 %1, 54
+  br i1 %cmp23, label %while.cond, label %if.then.25
+
+if.then.25:
+  call void @g(i8* getelementptr inbounds ([100 x i8], [100 x i8]* @.str.4, i32 0, i32 0))
+  br label %while.cond
+
+while.cond:
+; CHECK-LABEL: while.cond
+; CHECK-NOT: phi i8* [ %0, %entry ], [ %Ptr, %while.body ], [ %0, %if.then.25 ]
+  %Ptr = phi i8* [ %incdec.ptr, %entry ], [ %incdec.ptr32, %while.body], [%incdec.ptr, %if.then.25 ]
+  %2 = load i8, i8* %Ptr
+  %and = and i8 %2, 64
+  %lnot = icmp eq i8 %and, 0
+  br i1 %lnot, label %while.body, label %while.cond.33
+
+while.body:
+  %incdec.ptr32 = getelementptr inbounds i8, i8* %Ptr, i32 1
+  br label %while.cond
+
+while.cond.33:
+  %incdec.ptr34 = getelementptr inbounds i8, i8* %Ptr, i32 1
+  br label %while.cond.57
+
+while.cond.57:
+  %3 = load i8, i8* %incdec.ptr34, align 1
+  %conv59 = zext i8 %3 to i32
+  %arrayidx61 = getelementptr inbounds i16, i16* %idx, i32 %conv59
+  %4 = load i16, i16* %arrayidx61, align 2
+  %and63 = and i16 %4, 2048
+  %tobool64 = icmp eq i16 %and63, 0
+  br i1 %tobool64, label %while.cond.73, label %while.cond.57
+
+while.cond.73:
+  br label %while.cond.73
+
+}
+
+declare void @g(i8*)