[InstCombine] insert a new shuffle in a safe place (PR25999)

[spatel]

Summary

Limit this transform to a basic block, so we don't cause chaos.
Hopefully, this fixes the remaining failures in PR25999:
https://llvm.org/bugs/show_bug.cgi?id=25999

[ab]

Looks reasonable; fixes 444.namd/ComputeNonbondedUtil.c for me; so far no other problems in SPEC.

LGTM.

test/Transforms/InstCombine/insert-extract-shuffle.ll

130

%c2 isn't actually used, sorry about that.

[spatel]

After thinking about it some more, this doesn't work either.

It will fail if the vector that we're extracting from is defined in the same block:

define <4 x double> @t(i1 %c, <2 x double> %a, <4 x double> %b) {
bb1:
  br i1 %c, label %bb2, label %bb3

bb2:
  %r = call <2 x double> @dummy(<2 x double> %a)
  br label %bb3

bb3:
  %tmp1 = phi <2 x double> [ %a, %bb1 ], [ %r, %bb2 ]
  %tmp2 = phi <4 x double> [ %b, %bb1 ], [ zeroinitializer, %bb2 ]
  %d = fadd <2 x double> %tmp1, %tmp1
  %tmp3 = extractelement <2 x double> %d, i32 0
  %tmp4 = insertelement <4 x double> %tmp2, double %tmp3, i32 2
  ret <4 x double> %tmp4
}

declare <2 x double> @dummy(<2 x double>)

We need a way to insert the shuffle at the later of a safe insertion point and the define of the vector that we're extracting from, but I'm not sure how to code that. This sort of thing must exist somewhere else in LLVM?

[spatel]

Patch updated:
I don't see any existing APIs to do what we want, so just check for the PHI case explicitly.
Also, add another test case.

[spatel]

I checked in a variant of this patch at:
http://reviews.llvm.org/rL257133

lib/Transforms/InstCombine/InstCombineVectorOps.cpp

static void replaceExtractElements(InsertElementInst *InsElt,
   for (unsigned i = NumExtElts; i < NumInsElts; ++i)
     ExtendMask.push_back(UndefValue::get(IntType));
 
   Value *ExtVecOp = ExtElt->getVectorOperand();
   auto *WideVec = new ShuffleVectorInst(ExtVecOp, UndefValue::get(ExtVecType),
                                         ConstantVector::get(ExtendMask));
 
   // Insert the new shuffle after the vector operand of the extract is defined
-  // or at the start of the basic block, so any subsequent extracts can use it.
-  bool ReplaceAllExtUsers;
-  if (auto *ExtVecOpInst = dyn_cast<Instruction>(ExtVecOp)) {
-    WideVec->insertAfter(ExtVecOpInst);
-    ReplaceAllExtUsers = true;
-  } else {
-    // TODO: Insert at start of function, so it's always safe to replace all?
+  // or at the start of the basic block of the extract, so any subsequent
+  // extracts in the same basic block can use it.
+  auto *ExtVecOpInst = dyn_cast<Instruction>(ExtVecOp);
+  if (!ExtVecOpInst || isa<PHINode>(ExtVecOpInst))
     IC.InsertNewInstWith(WideVec, *ExtElt->getParent()->getFirstInsertionPt());
-    ReplaceAllExtUsers = false;
-  }
+  else
+    WideVec->insertAfter(ExtVecOpInst);
 
   // Replace extracts from the original narrow vector with extracts from the new
   // wide vector.
   for (User *U : ExtVecOp->users()) {
     ExtractElementInst *OldExt = dyn_cast<ExtractElementInst>(U);
-    if (!OldExt ||
-        (!ReplaceAllExtUsers && OldExt->getParent() != WideVec->getParent()))
+    if (!OldExt || OldExt->getParent() != WideVec->getParent())
       continue;
     auto *NewExt = ExtractElementInst::Create(WideVec, OldExt->getOperand(1));
     NewExt->insertAfter(WideVec);
     IC.ReplaceInstUsesWith(*OldExt, NewExt);
   }
 }
 
 /// We are building a shuffle to create V, which is a sequence of insertelement,

test/Transforms/InstCombine/insert-extract-shuffle.ll

if:
   ret <8 x i16> %t5
 
 end:
   %a1 = add i16 %t1, 4
   %t6 = insertelement <8 x i16> zeroinitializer, i16 %a1, i32 0
   ret <8 x i16> %t6
 }
 
+; The widening shuffle must be inserted at a valid point (after the PHIs). 
+
+define <4 x double> @pr25999_phis1(i1 %c, <2 x double> %a, <4 x double> %b) {
+; CHECK-LABEL: @pr25999_phis1(
+; CHECK:       %tmp1 = phi <2 x double> [ %a, %bb1 ], [ %r, %bb2 ]
+; CHECK-NEXT:  %tmp2 = phi <4 x double> [ %b, %bb1 ], [ zeroinitializer, %bb2 ]
+; CHECK-NEXT:  %[[WIDEVEC:.*]] = shufflevector <2 x double> %tmp1, <2 x double> undef, <4 x i32> <i32 0, i32 undef, i32 undef, i32 undef>
+; CHECK-NEXT:  %tmp4 = shufflevector <4 x double> %tmp2, <4 x double> %[[WIDEVEC]], <4 x i32> <i32 0, i32 1, i32 4, i32 3>
+; CHECK-NEXT:  ret <4 x double> %tmp4
+bb1:
+  br i1 %c, label %bb2, label %bb3
+
+bb2:
+  %r = call <2 x double> @dummy(<2 x double> %a)
+  br label %bb3
+
+bb3:
+  %tmp1 = phi <2 x double> [ %a, %bb1 ], [ %r, %bb2 ]
+  %tmp2 = phi <4 x double> [ %b, %bb1 ], [ zeroinitializer, %bb2 ]
+  %tmp3 = extractelement <2 x double> %tmp1, i32 0
+  %tmp4 = insertelement <4 x double> %tmp2, double %tmp3, i32 2
+  ret <4 x double> %tmp4
+}
+
+declare <2 x double> @dummy(<2 x double>)
+
+define <4 x double> @pr25999_phis2(i1 %c, <2 x double> %a, <4 x double> %b) {
+; CHECK-LABEL: @pr25999_phis2(
+; CHECK:       %tmp1 = phi <2 x double> [ %a, %bb1 ], [ %r, %bb2 ]
+; CHECK-NEXT:  %tmp2 = phi <4 x double> [ %b, %bb1 ], [ zeroinitializer, %bb2 ]
+; CHECK-NEXT:  %d = fadd <2 x double> %tmp1, %tmp1
+; CHECK-NEXT:  %[[WIDEVEC:.*]] = shufflevector <2 x double> %d, <2 x double> undef, <4 x i32> <i32 0, i32 undef, i32 undef, i32 undef>
+; CHECK-NEXT:  %tmp4 = shufflevector <4 x double> %tmp2, <4 x double> %[[WIDEVEC]], <4 x i32> <i32 0, i32 1, i32 4, i32 3>
+; CHECK-NEXT:  ret <4 x double> %tmp4
+bb1:
+  br i1 %c, label %bb2, label %bb3
+
+bb2:
+  %r = call <2 x double> @dummy(<2 x double> %a)
+  br label %bb3
+
+bb3:
+  %tmp1 = phi <2 x double> [ %a, %bb1 ], [ %r, %bb2 ]
+  %tmp2 = phi <4 x double> [ %b, %bb1 ], [ zeroinitializer, %bb2 ]
+  %d = fadd <2 x double> %tmp1, %tmp1
+  %tmp3 = extractelement <2 x double> %d, i32 0
+  %tmp4 = insertelement <4 x double> %tmp2, double %tmp3, i32 2
+  ret <4 x double> %tmp4
+}
+