Improve InstCombiner handling of shuffles

[jonpa]

Summary

This patch improves handling of shuffles in InstCombiner.

Note that it is currently "in progress".

[efriedma]

lib/Transforms/InstCombine/InstCombineVectorOps.cpp

1395

We should try to solve this some other way; this is essentially a CSE transform.

1437

This is a variant of case 4 above? A cleaned-up version of this probably makes sense.

1514

This is essentially a version of D31509, which isn't really acceptable for the reasons outlined there.

[jonpa]

Thanks for review, but it seems the two other upcoming patches are making this less needed.

lib/Transforms/InstCombine/InstCombineVectorOps.cpp

if (LHSShuffle) {
     else if (LHSOp0Width == LHSWidth) {
       newLHS = LHSOp0;
     }
   }
   // case 3 or 4
   if (RHSShuffle && RHSOp0Width == LHSWidth) {
     newRHS = RHSOp0;
   }
+
   // case 4
-  if (LHSOp0 == RHSOp0) {
+  bool EqOp0s = (LHSOp0 == RHSOp0);
+  if (!EqOp0s && LHSOp0 != nullptr && RHSOp0 != nullptr) {
+    if (Instruction* LHSOp0Inst = dyn_cast<Instruction>(LHSOp0)) {
+      if (Instruction* RHSOp0Inst = dyn_cast<Instruction>(RHSOp0)) {
+        if (LHSOp0Inst->isIdenticalTo(RHSOp0Inst) &&
+            !LHSOp0Inst->mayHaveSideEffects() && !LHSOp0Inst->mayReadFromMemory() &&
+            !RHSOp0Inst->mayHaveSideEffects() && !RHSOp0Inst->mayReadFromMemory()) {
+          EqOp0s = true;
+        }
+      }
+    }
+  }
+  if (EqOp0s) {
     newLHS = LHSOp0;
     newRHS = nullptr;
   }
 
-  if (newLHS == LHS && newRHS == RHS)
-    return MadeChange ? &SVI : nullptr;
+  SmallVector<int, 16> newMask;
 
+  if (newLHS == LHS && newRHS == RHS) {
+    if (LHSShuffle != nullptr && RHSShuffle != nullptr) {
+      SmallVector<int, 16> LHSMask;
+      SmallVector<int, 16> RHSMask;
+      LHSMask = LHSShuffle->getShuffleMask();
+      RHSMask = RHSShuffle->getShuffleMask();
+      unsigned LHSShuffle_Width = cast<VectorType>(LHSShuffle->getOperand(0)->getType())->getNumElements();
+      for (unsigned i = 0; i < VWidth; ++i) {
+        int eltMask;
+      
+        if (Mask[i] < 0) {
+          // This element is an undef value.
+          eltMask = -1;
+        } else if (Mask[i] < (int)LHSWidth) {
+          // This element is from left hand side vector operand.
+          //
+          eltMask = LHSMask[Mask[i]];
+        } else {
+          // This element is from right hand side vector operand
+          //
+          eltMask = RHSMask[Mask[i] - LHSWidth] + LHSShuffle_Width;
+        }
+
+        newMask.push_back(eltMask);
+      }
+      newLHS = LHSShuffle->getOperand(0);
+      newRHS = RHSShuffle->getOperand(0);
+    }
+    else {
+      return MadeChange ? &SVI : nullptr;
+    }
+  }
+  else {
     SmallVector<int, 16> LHSMask;
     SmallVector<int, 16> RHSMask;
     if (newLHS != LHS)
       LHSMask = LHSShuffle->getShuffleMask();
     if (RHSShuffle && newRHS != RHS)
       RHSMask = RHSShuffle->getShuffleMask();
 
     unsigned newLHSWidth = (newLHS != LHS) ? LHSOp0Width : LHSWidth;
-  SmallVector<int, 16> newMask;
     bool isSplat = true;
     int SplatElt = -1;
     // Create a new mask for the new ShuffleVectorInst so that the new
     // ShuffleVectorInst is equivalent to the original one.
     for (unsigned i = 0; i < VWidth; ++i) {
       int eltMask;
       if (Mask[i] < 0) {
         // This element is an undef value.
         eltMask = -1;
       } else if (Mask[i] < (int)LHSWidth) {
         // This element is from left hand side vector operand.
         //
         // If LHS is going to be replaced (case 1, 2, or 4), calculate the
         // new mask value for the element.
         if (newLHS != LHS) {
           eltMask = LHSMask[Mask[i]];
           // If the value selected is an undef value, explicitly specify it
           // with a -1 mask value.
           if (eltMask >= (int)LHSOp0Width && isa<UndefValue>(LHSOp1))
             eltMask = -1;
         } else
           eltMask = Mask[i];
       } else {
         // This element is from right hand side vector operand
         //
         // If the value selected is an undef value, explicitly specify it
         // with a -1 mask value. (case 1)
         if (isa<UndefValue>(RHS))
           eltMask = -1;
         // If RHS is going to be replaced (case 3 or 4), calculate the
         // new mask value for the element.
         else if (newRHS != RHS) {
           eltMask = RHSMask[Mask[i]-LHSWidth];
           // If the value selected is an undef value, explicitly specify it
           // with a -1 mask value.
           if (eltMask >= (int)RHSOp0Width) {
             assert(isa<UndefValue>(RHSShuffle->getOperand(1))
                    && "should have been check above");
             eltMask = -1;
           }
         } else
           eltMask = Mask[i]-LHSWidth;
 
         // If LHS's width is changed, shift the mask value accordingly.
         // If newRHS == NULL, i.e. LHSOp0 == RHSOp0, we want to remap any
         // references from RHSOp0 to LHSOp0, so we don't need to shift the mask.
         // If newRHS == newLHS, we want to remap any references from newRHS to
         // newLHS so that we can properly identify splats that may occur due to
         // obfuscation across the two vectors.
         if (eltMask >= 0 && newRHS != nullptr && newLHS != newRHS)
           eltMask += newLHSWidth;
       }
 
       // Check if this could still be a splat.
       if (eltMask >= 0) {
         if (SplatElt >= 0 && SplatElt != eltMask)
           isSplat = false;
         SplatElt = eltMask;
       }
 
       newMask.push_back(eltMask);
     }
+  }
 
   // If the result mask is equal to one of the original shuffle masks,
   // or is a splat, do the replacement.
-  if (isSplat || newMask == LHSMask || newMask == RHSMask || newMask == Mask) {
+//  if (isSplat || newMask == LHSMask || newMask == RHSMask || newMask == Mask) {
     SmallVector<Constant*, 16> Elts;
     for (unsigned i = 0, e = newMask.size(); i != e; ++i) {
       if (newMask[i] < 0) {
         Elts.push_back(UndefValue::get(Int32Ty));
       } else {
         Elts.push_back(ConstantInt::get(Int32Ty, newMask[i]));
       }
     }
     if (!newRHS)
       newRHS = UndefValue::get(newLHS->getType());
-    return new ShuffleVectorInst(newLHS, newRHS, ConstantVector::get(Elts));
-  }
+//  }
 
   // If the result mask is an identity, replace uses of this instruction with
   // corresponding argument.
   bool isLHSID, isRHSID;
   recognizeIdentityMask(newMask, isLHSID, isRHSID);
   if (isLHSID && VWidth == LHSOp0Width) return replaceInstUsesWith(SVI, newLHS);
   if (isRHSID && VWidth == RHSOp0Width) return replaceInstUsesWith(SVI, newRHS);
 
   return MadeChange ? &SVI : nullptr;
 }