[WIP] Teach instcombine how to destroy vector GEPs/loads/stores

[reames]

Summary

This is being used as a "meta review". Actual patches are linked below. What's in this diff is pieces which need to be split out and reviewed individually once the core infrastructure has landed.

Landed:

• D57177 Demanded elements support for vector GEPs
• D57398 SimplifyDemandedVectorElts for all intrinsics
• D57247 Simply operands of masked stores and scatters based on demanded elements
• D57372 Demanded elements support for masked.load and masked.gather
• D57468 Strengthen handling of GEPs and generic calls for all undef lanes

[reames]

Another possible transform. Probably in addition to, not in place of vector->scalar+broadcast transform which still needs written.

[reames]

Decided to start from the demanded elements and work my way up to actual transforms. First two reviews are posted:

• D57177 Demanded elements support for vector GEPs
• D57247 Simply operands of masked stores and scatters based on demanded elements

Next up is to do the demanded bits for scatter and masked.load. After that, I should probably do expandload and compressedstore for completeness, though that may be done later since I've never seen their use.

Once that part is in, I'll return to the transforms for the individual instructions. Mostly as a reminder to self, the patterns of interest for each memory instruction are: splat of each operand, single element active, incrementing addresses, and inferring inactive lanes from undef. For GEPs, the main ones are scalarizing operands, scalarizing the instruction as a whole, and undef/demanded elt intersection.

The more general building blocks needed for the above discovered so far are:

• Improved splat detection
• Scalar masked store creation utilities
• Horizontal op folding (e.g. or reduce over a mask vector)
• Mask analysis utilities

Just to set expectations appropriately, I'm not promising to see all of the above through. I intend of making improvements until I stop seeing practical test cases which look painful, and that's about it. Anyone who wants to pick of a piece is very welcome to. :)

[reames]

Most of the todos have been checked in, and not an area of current focus. Likely to still post a patch here or there, but they'll be able to stand on their own now that the frameworks in place.

lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp

Value *InstCombiner::simplifyAMDGCNMemoryIntrinsicDemanded(IntrinsicInst *II,
   }
 
   Value *Shuffle =
       Builder.CreateShuffleVector(NewCall, UndefValue::get(NewTy), EltMask);
 
   return Shuffle;
 }
 
+namespace {
+Value *getSplatValue(Value *V) {
+  // insertelement undef, X, Y - all elements are undef or X, so we can treat
+  // this like a splat of X.  Note: This is the form simplify demanded elements
+  // tends to produce.
+  if (auto *IE = dyn_cast<InsertElementInst>(V))
+    if (isa<UndefValue>(IE->getOperand(0)))
+      return IE->getOperand(1);
+
+  // TODO: recognize a shuffle broadcast too
+
+  auto *CV = dyn_cast<ConstantVector>(V);
+  if (!CV)
+    return nullptr;
+  if (auto *SplatC = CV->getSplatValue())
+    return SplatC;
+  
+  Constant *Splat = nullptr;
+  for (unsigned i = 0; i < CV->getNumOperands(); i++) {
+    Constant *Elt = CV->getOperand(i);
+    if (isa<UndefValue>(Elt))
+      continue;
+    if (!Splat)
+      Splat = Elt;
+    if (Elt != Splat)
+      return nullptr;
+  }
+  return Splat;
+}
+}
+
 /// The specified value produces a vector with any number of elements.
 /// DemandedElts contains the set of elements that are actually used by the
 /// caller. This method analyzes which elements of the operand are undef and
 /// returns that information in UndefElts.
 ///
 /// If the information about demanded elements can be used to simplify the
 /// operation, the operation is simplified, then the resultant value is
 /// returned.  This returns null if no change was made.
auto simplifyAndSetOp = [&](Instruction *Inst, unsigned OpNum,
     }
   };
 
   APInt UndefElts2(VWidth, 0);
   APInt UndefElts3(VWidth, 0);
   switch (I->getOpcode()) {
   default: break;
 
+  case Instruction::GetElementPtr: {
+    // Conservatively track the demanded elements back through any vector
+    // operands we may have.  We know there must be at least one, or we
+    // wouldn't have a vector result to get here. Note that we intentionally
+    // merge the undef bits here since gepping with either an undef base or
+    // index results in undef. 
+    for (unsigned i = 0; i < I->getNumOperands(); i++)
+      if (I->getOperand(i)->getType()->isVectorTy())
+        simplifyAndSetOp(I, i, DemandedElts, UndefElts);
+
+#if 0
+    // If we can do so without changing the result type of the GEP, scalarize
+    // any operands which are simple vector splats.  A couple of notes here:
+    // 1) If we remove all vector operands, we implicitly change the result
+    //    type of the GEP to a scalar.  We can't broadcast the result here,
+    //    and instead leave that portion of the transform to our caller. 
+    // 2) We prefer to leave the last vector operand unchanged if needed to
+    //    ensure at least one argument stays vector typed.  This is arbitrary,
+    //    but biases us towards scalarizing pointer operands which seems handy.
+    // 3) We recognize constant splats w/ undef elements, and
+    //    (insertlement undef, X, Y) since both can be interpreted as
+    //    broadcasting X to all (usable) lanes. Since this is the form we tend
+    //    to produce when simplify operands w/demanded elements, it's nice to
+    //    catch that them ere.
+    
+    unsigned LastVectorOperand = I->getNumOperands();
+    for (unsigned i = 1; i < I->getNumOperands(); i++)
+      if (I->getOperand(i)->getType()->isVectorTy())
+        LastVectorOperand = i;
+    assert(LastVectorOperand < I->getNumOperands() &&
+           "must have at least one vector operand");
+    
+    for (unsigned i = 0; i < LastVectorOperand; i++)
+      if (I->getOperand(i)->getType()->isVectorTy())
+        if (auto *SplatC = getSplatValue(I->getOperand(i))) {
+          I->setOperand(i, SplatC);
+          MadeChange = true;
+        }
+
+    // TODO: either move above to caller, or use demanded elements
+    // (i.e. another use of the vector operand which needs all lanes)
+#endif    
+    break;
+  }
   case Instruction::InsertElement: {
     // If this is a variable index, we don't know which element it overwrites.
     // demand exactly the same input as we produce.
     ConstantInt *Idx = dyn_cast<ConstantInt>(I->getOperand(2));
     if (!Idx) {
       // Note that we can't propagate undef elt info, because we don't know
       // which elt is getting updated.
       simplifyAndSetOp(I, 0, DemandedElts, UndefElts2);

lib/Transforms/InstCombine/InstCombineVectorOps.cpp

if (IndexC) {
     if (Instruction *I = foldBitcastExtElt(EI, Builder, DL.isBigEndian()))
       return I;
 
     // If there's a vector PHI feeding a scalar use through this extractelement
     // instruction, try to scalarize the PHI.
     if (auto *Phi = dyn_cast<PHINode>(SrcVec))
       if (Instruction *ScalarPHI = scalarizePHI(EI, Phi))
         return ScalarPHI;
+
+    // If we have an extractelement (gep ...), where we can form a new scalar
+    // gep without forming extra instructions, prefer the scalar gep in place
+    // of the extractelement to remove uses from the vector instruction.
+    if (SrcVec->hasOneUse())
+      if (auto *GEP = dyn_cast<GetElementPtrInst>(SrcVec)) {
+        unsigned NumVectorOperands = 0;
+        for (unsigned i = 0; i < GEP->getNumOperands(); i++)
+          if (GEP->getOperand(i)->getType()->isVectorTy())
+            NumVectorOperands++;
+
+        if (NumVectorOperands == 1) {
+          auto getScalar = [&](Value *V, Value* Index) {
+            if (!V->getType()->isVectorTy())
+              return V;
+            // Hmm, should we try to match broadcasts or inserts here to avoid
+            // generating the EE?  If so, should we account for this in the
+            // cost model of the transform?
+            return Builder.CreateExtractElement(V, Index);
+          };
+          Value *NewPtr = getScalar(GEP->getPointerOperand(), Index);
+          SmallVector<Value*, 4> NewIdx;
+          NewIdx.reserve(GEP->getNumOperands());
+          for (unsigned i = 1; i < GEP->getNumOperands(); i++)
+            NewIdx.push_back(getScalar(GEP->getOperand(i), Index));
+          auto *GEP = Builder.CreateGEP(NewPtr, NewIdx, EI.getName());
+          return replaceInstUsesWith(EI, GEP);
+        }
+      }
   }
 
   BinaryOperator *BO;
   if (match(SrcVec, m_BinOp(BO)) && cheapToScalarize(SrcVec, IndexC)) {
     // extelt (binop X, Y), Index --> binop (extelt X, Index), (extelt Y, Index)
     Value *X = BO->getOperand(0), *Y = BO->getOperand(1);
     Value *E0 = Builder.CreateExtractElement(X, Index);
     Value *E1 = Builder.CreateExtractElement(Y, Index);

lib/Transforms/InstCombine/InstructionCombining.cpp

if (auto *NewBinOp = dyn_cast<BinaryOperator>(NarrowBO)) {
     if (IsSext)
       NewBinOp->setHasNoSignedWrap();
     else
       NewBinOp->setHasNoUnsignedWrap();
   }
   return CastInst::Create(CastOpc, NarrowBO, BO.getType());
 }
 
+namespace {
+Value *getSplatValue(Value *V) {
+  // TODO: merge both cases below into the existing helper function in
+  // VectorUtils after careful audit of users to ensure they're compatible.  At
+  // the moment, neither are handled by that routine.
+
+  // insertelement undef, X, Y - all elements are undef or X, so we can treat
+  // this like a splat of X.  Note: This is the form simplify demanded elements
+  // tends to produce.
+  if (auto *IE = dyn_cast<InsertElementInst>(V))
+    if (isa<UndefValue>(IE->getOperand(0)))
+      return IE->getOperand(1);
+
+  // TODO: recognize a shuffle broadcast too
+
+  auto *CV = dyn_cast<ConstantVector>(V);
+  if (!CV)
+    return nullptr;
+  if (auto *SplatC = CV->getSplatValue())
+    return SplatC;
+  
+  Constant *Splat = nullptr;
+  for (unsigned i = 0; i < CV->getNumOperands(); i++) {
+    Constant *Elt = CV->getOperand(i);
+    if (isa<UndefValue>(Elt))
+      continue;
+    if (!Splat)
+      Splat = Elt;
+    if (Elt != Splat)
+      return nullptr;
+  }
+  return Splat;
+}
+}
+
 Instruction *InstCombiner::visitGetElementPtrInst(GetElementPtrInst &GEP) {
   SmallVector<Value*, 8> Ops(GEP.op_begin(), GEP.op_end());
   Type *GEPType = GEP.getType();
   Type *GEPEltType = GEP.getSourceElementType();
   if (Value *V = SimplifyGEPInst(GEPEltType, Ops, SQ.getWithInstruction(&GEP)))
     return replaceInstUsesWith(GEP, V);
 
   Value *PtrOp = GEP.getOperand(0);
if (IndexTy != NewIndexType) {
       // This explicit cast can make subsequent optimizations more obvious.
       *I = Builder.CreateIntCast(*I, NewIndexType, true);
       MadeChange = true;
     }
   }
   if (MadeChange)
     return &GEP;
 
+  if (GEPType->isVectorTy()) {
+    // If we can do so without changing the result type of the GEP, scalarize
+    // any operands which are simple vector splats.  A couple of notes here:
+    // 1) If we remove all vector operands, we implicitly change the result
+    //    type of the GEP to a scalar. (TODO: Insert the broadcast and do the
+    //    actual conversion to a scalar GEP.)
+    // 2) We prefer to leave the last vector operand unchanged if needed to
+    //    ensure at least one argument stays vector typed.  This is arbitrary,
+    //    but biases us towards scalarizing pointer operands which seems handy.
+    // 3) We recognize constant splats w/ undef elements, and
+    //    (insertlement undef, X, Y) since both can be interpreted as
+    //    broadcasting X to all (usable) lanes. Since this is the form we tend
+    //    to produce when simplify operands w/demanded elements, it's nice to
+    //    catch that them ere.
+    
+    unsigned LastVectorOperand = GEP.getNumOperands();
+    for (unsigned i = 0; i < GEP.getNumOperands(); i++)
+      if (GEP.getOperand(i)->getType()->isVectorTy())
+        LastVectorOperand = i;
+    assert(LastVectorOperand < GEP.getNumOperands() &&
+           "must have at least one vector operand");
+    
+    for (unsigned i = 0; i < LastVectorOperand; i++)
+      if (GEP.getOperand(i)->getType()->isVectorTy())
+        if (auto *SplatC = getSplatValue(GEP.getOperand(i))) {
+          GEP.setOperand(i, SplatC);
+          MadeChange = true;
+        }
+
+    if (MadeChange)
+      return &GEP;
+  }
+
   // Check to see if the inputs to the PHI node are getelementptr instructions.
   if (auto *PN = dyn_cast<PHINode>(PtrOp)) {
     auto *Op1 = dyn_cast<GetElementPtrInst>(PN->getOperand(0));
     if (!Op1)
       return nullptr;
 
     // Don't fold a GEP into itself through a PHI node. This can only happen
     // through the back-edge of a loop. Folding a GEP into itself means that