[InstCombine] scalarizePHI should not assume the code it sees has been CSE'd

[mkuper]

Summary

scalarizePHI only looks for phis that have exactly two users - the "latch" use, and an extract. Unfortunately, we can not assume such extracts have been CSEd, since InstCombine itself may create an extract which is a duplicate of an existing one. This extends it to handle several extracts from the same index.

This hopefully fixes the performance regression in PR27988.

[majnemer]

lib/Transforms/InstCombine/InstCombineVectorOps.cpp

69 ↗

(On Diff #59602)

Please clang-format this.

test/Transforms/InstCombine/vec_phi_extract.ll

30–32 ↗

(On Diff #59602)

Please give these instructions some operands.

[mkuper]

Thanks, David!

lib/Transforms/InstCombine/InstCombineVectorOps.cpp

69 ↗

(On Diff #59602)

Argh, I was sure I did!

test/Transforms/InstCombine/vec_phi_extract.ll

30–32 ↗

(On Diff #59602)

Yeah, should probably fix the rest of the test while I'm at it.

[mkuper]

Updated per David's comments.

[majnemer]

LGTM

llvm/trunk/lib/Transforms/InstCombine/InstCombineVectorOps.cpp

if (CmpInst *CI = dyn_cast<CmpInst>(I))
     if (CI->hasOneUse() &&
         (cheapToScalarize(CI->getOperand(0), isConstant) ||
          cheapToScalarize(CI->getOperand(1), isConstant)))
       return true;
 
   return false;
 }
 
-// If we have a PHI node with a vector type that has only 2 uses: feed
+// If we have a PHI node with a vector type that is only used to feed
 // itself and be an operand of extractelement at a constant location,
 // try to replace the PHI of the vector type with a PHI of a scalar type.
 Instruction *InstCombiner::scalarizePHI(ExtractElementInst &EI, PHINode *PN) {
-  // Verify that the PHI node has exactly 2 uses. Otherwise return NULL.
-  if (!PN->hasNUses(2))
+  SmallVector<Instruction *, 2> Extracts;
+  // The users we want the PHI to have are:
+  // 1) The EI ExtractElement (we already know this)
+  // 2) Possibly more ExtractElements with the same index.
+  // 3) Another operand, which will feed back into the PHI.
+  Instruction *PHIUser = nullptr;
+  for (auto U : PN->users()) {
+    if (ExtractElementInst *EU = dyn_cast<ExtractElementInst>(U)) {
+      if (EI.getIndexOperand() == EU->getIndexOperand())
+        Extracts.push_back(EU);
+      else
+        return nullptr;
+    } else if (!PHIUser) {
+      PHIUser = cast<Instruction>(U);
+    } else {
       return nullptr;
+    }
+  }
 
-  // If so, it's known at this point that one operand is PHI and the other is
-  // an extractelement node. Find the PHI user that is not the extractelement
-  // node.
-  auto iu = PN->user_begin();
-  Instruction *PHIUser = dyn_cast<Instruction>(*iu);
-  if (PHIUser == cast<Instruction>(&EI))
-    PHIUser = cast<Instruction>(*(++iu));
+  if (!PHIUser)
+    return nullptr;
 
   // Verify that this PHI user has one use, which is the PHI itself,
   // and that it is a binary operation which is cheap to scalarize.
   // otherwise return NULL.
   if (!PHIUser->hasOneUse() || !(PHIUser->user_back() == PN) ||
       !(isa<BinaryOperator>(PHIUser)) || !cheapToScalarize(PHIUser, true))
     return nullptr;
 
if (PHIInVal == PHIUser) {
         InsertPos = inBB->getFirstInsertionPt();
       }
 
       InsertNewInstWith(newEI, *InsertPos);
 
       scalarPHI->addIncoming(newEI, inBB);
     }
   }
-  return replaceInstUsesWith(EI, scalarPHI);
+
+  for (auto E : Extracts)
+    replaceInstUsesWith(*E, scalarPHI);
+
+  return &EI;
 }
 
 Instruction *InstCombiner::visitExtractElementInst(ExtractElementInst &EI) {
   if (Value *V = SimplifyExtractElementInst(
           EI.getVectorOperand(), EI.getIndexOperand(), DL, TLI, DT, AC))
     return replaceInstUsesWith(EI, V);
 
   // If vector val is constant with all elements the same, replace EI with

llvm/trunk/test/Transforms/InstCombine/vec_phi_extract.ll

 ; RUN: opt < %s -instcombine -S | FileCheck %s
 
 define void @f(i64 %val, i32  %limit, i32 *%ptr) {
-;CHECK: %0 = trunc i64
-;CHECK: %1 = phi i32
+; CHECK-LABEL: @f
+; CHECK: %0 = trunc i64 %val to i32
+; CHECK: %1 = phi i32 [ %0, %entry ], [ {{.*}}, %loop ]
 entry:
   %tempvector = insertelement <16 x i64> undef, i64 %val, i32 0
   %vector = shufflevector <16 x i64> %tempvector, <16 x i64> undef, <16 x i32> zeroinitializer
   %0 = add <16 x i64> %vector, <i64 0, i64 1, i64 2, i64 3, i64 4, i64 5, i64 6, i64 7, i64 8, i64 9, i64 10, i64 11, i64 12, i64 13, i64 14, i64 15>
   %1 = trunc <16 x i64> %0 to <16 x i32>
   br label %loop
 
 loop:
   %2 = phi <16 x i32> [ %1, %entry ], [ %inc, %loop ]
   %elt = extractelement <16 x i32> %2, i32 0
   %end = icmp ult i32 %elt, %limit
   %3 = add i32 10, %elt
   %4 = sext i32 %elt to i64
   %5 = getelementptr i32, i32* %ptr, i64 %4
   store i32 %3, i32* %5
   %inc = add <16 x i32> %2, <i32 16, i32 16, i32 16, i32 16, i32 16, i32 16, i32 16, i32 16, i32 16, i32 16, i32 16, i32 16, i32 16, i32 16, i32 16, i32 16>
   br i1 %end, label %loop, label %ret
 
 ret:
   ret void
 }
 
+define void @copy(i64 %val, i32  %limit, i32 *%ptr) {
+; CHECK-LABEL: @copy
+; CHECK: %0 = trunc i64 %val to i32
+; CHECK: %1 = phi i32 [ %0, %entry ], [ {{.*}}, %loop ]
+entry:
+  %tempvector = insertelement <16 x i64> undef, i64 %val, i32 0
+  %vector = shufflevector <16 x i64> %tempvector, <16 x i64> undef, <16 x i32> zeroinitializer
+  %0 = add <16 x i64> %vector, <i64 0, i64 1, i64 2, i64 3, i64 4, i64 5, i64 6, i64 7, i64 8, i64 9, i64 10, i64 11, i64 12, i64 13, i64 14, i64 15>
+  %1 = trunc <16 x i64> %0 to <16 x i32>
+  br label %loop
+
+loop:
+  %2 = phi <16 x i32> [ %1, %entry ], [ %inc, %loop ]
+  %elt = extractelement <16 x i32> %2, i32 0
+  %eltcopy = extractelement <16 x i32> %2, i32 0
+  %end = icmp ult i32 %elt, %limit
+  %3 = add i32 10, %eltcopy
+  %4 = sext i32 %elt to i64
+  %5 = getelementptr i32, i32* %ptr, i64 %4
+  store i32 %3, i32* %5
+  %inc = add <16 x i32> %2, <i32 16, i32 16, i32 16, i32 16, i32 16, i32 16, i32 16, i32 16, i32 16, i32 16, i32 16, i32 16, i32 16, i32 16, i32 16, i32 16>
+  br i1 %end, label %loop, label %ret
+
+ret:
+  ret void
+}
+
+define void @nocopy(i64 %val, i32  %limit, i32 *%ptr) {
+; CHECK-LABEL: @nocopy
+; CHECK-NOT: phi i32
+; CHECK: phi <16 x i32> [ %1, %entry ], [ %inc, %loop ]
+entry:
+  %tempvector = insertelement <16 x i64> undef, i64 %val, i32 0
+  %vector = shufflevector <16 x i64> %tempvector, <16 x i64> undef, <16 x i32> zeroinitializer
+  %0 = add <16 x i64> %vector, <i64 0, i64 1, i64 2, i64 3, i64 4, i64 5, i64 6, i64 7, i64 8, i64 9, i64 10, i64 11, i64 12, i64 13, i64 14, i64 15>
+  %1 = trunc <16 x i64> %0 to <16 x i32>
+  br label %loop
+
+loop:
+  %2 = phi <16 x i32> [ %1, %entry ], [ %inc, %loop ]
+  %elt = extractelement <16 x i32> %2, i32 0
+  %eltcopy = extractelement <16 x i32> %2, i32 1
+  %end = icmp ult i32 %elt, %limit
+  %3 = add i32 10, %eltcopy
+  %4 = sext i32 %elt to i64
+  %5 = getelementptr i32, i32* %ptr, i64 %4
+  store i32 %3, i32* %5
+  %inc = add <16 x i32> %2, <i32 16, i32 16, i32 16, i32 16, i32 16, i32 16, i32 16, i32 16, i32 16, i32 16, i32 16, i32 16, i32 16, i32 16, i32 16, i32 16>
+  br i1 %end, label %loop, label %ret
+
+ret:
+  ret void
+}
+
 define i1 @g(<3 x i32> %input_2) {
-; CHECK: extractelement
+; CHECK-LABEL: @g
+; CHECK: extractelement <3 x i32> %input_2, i32 0
 entry:
   br label %for.cond
 
 for.cond:
-; CHECK: phi i32
   %input_2.addr.0 = phi <3 x i32> [ %input_2, %entry ], [ %div45, %for.body ]
   %input_1.addr.1 = phi <3 x i32> [ undef, %entry ], [ %dec43, %for.body ]
   br i1 undef, label %for.end, label %for.body
 
-; CHECK: extractelement
+; CHECK: extractelement <3 x i32> %{{.*}}, i32 0
 for.body:
   %dec43 = add <3 x i32> %input_1.addr.1, <i32 -1, i32 -1, i32 -1>
   %sub44 = sub <3 x i32> <i32 -1, i32 -1, i32 -1>, %dec43
   %div45 = sdiv <3 x i32> %input_2.addr.0, %sub44
   br label %for.cond
 
 for.end:
   %0 = extractelement <3 x i32> %input_2.addr.0, i32 0
   %.89 = select i1 false, i32 0, i32 %0
   %tobool313 = icmp eq i32 %.89, 0
   ret i1 %tobool313
 }
 

llvm/trunk/test/Transforms/LoopVectorize/PowerPC/vsx-tsvc-s173.ll

for.end:                                          ; preds = %for.body3
   %cmp = icmp slt i32 %inc11, %mul
   br i1 %cmp, label %for.cond1.preheader, label %for.end12
 
 for.end12:                                        ; preds = %for.end, %entry
   ret i32 0
 
 ; CHECK-LABEL: @s173
 ; CHECK: load <4 x float>, <4 x float>*
-; CHECK: add nsw i64 %.lhs, 16000
+; CHECK: add nsw i64 %1, 16000
 ; CHECK: ret i32 0
 }
 
 attributes #0 = { nounwind }