InstructionSimplify: Canonicalize shuffle operands. NFC-ish.

[zvi]

Summary

Apply canonicalization rules:

1. Input vectors with no elements selected from can be replaced with undef.
2. If only one input vector is constant it shall be the second one.

This allows constant-folding to cover more ad-hoc simplifications that
were in place and avoid duplication for RHS and LHS checks.

There are more rules we may want to add in the future when we see a
justification. e.g. mask elements that select undef elements can be
replaced with undef.

[RKSimon]

lib/Analysis/InstructionSimplify.cpp

4150–4151

You are calling ShuffleVectorInst::getMaskValue multiple times per element - better to call ShuffleVectorInst::getShuffleMask instead?

4171

constant

4172

Add tests for this?

4197

Add an assert here to check that NewIndices has MaskNumElts elements

[zvi]

lib/Analysis/InstructionSimplify.cpp

4150–4151

Right, this is the case even without this patch (see lines 4158 and 4188). Will add a parent patch to address that.

4172

The tests are already there and this is supposed to be a NFC patch.
This canonoicalization allowed the removal of lines 4169-4171 which are a duplication of lines 4166-4168 (or lines 4188-4190 after the patch is applied).
One test-case that should give coverage is the function 'splat_operand3' in test/Transforms/InstSimplify/shufflevector.ll

4197

Thanks for pointing this out. I didn't really intend for the newly created mask to be illegal in the case it contains an undef. Will fix this.

[zvi]

Addressing some of Simon's comments.

[zvi]

lib/Analysis/InstructionSimplify.cpp

4150–4151

This is done in a parent patch, D32388.

[spatel]

lib/Analysis/InstructionSimplify.cpp

4140–4142

I got confused by the order of the patches/dependencies. This patch is proposing to remove this check that would be added by D32293. That's because the code in this patch will tell us that MaskSelects0 && MaskSelects1 are false, and that will then fall into ConstantFoldShuffleVectorInstruction and get folded?

I would've just left this check here as an early exit for the easy case.

FWIW, this may just be a case of too many cooks in the kitchen. :)
I think the end result of these 2 patches covers everything that we want in the current set of regression tests.

[zvi]

lib/Analysis/InstructionSimplify.cpp

4140–4142

Sorry about the excessive patches, will try to structure them better next time :)

The answer to your question is yes.

I thought it would be best to remove this early exit from fear of premature optimization as i don't have any data on how often this pattern occurs in real-life workloads (though from looking at the lit tests it would appear to happen quite often - but these are engineered corner cases).
I have no problem with leaving this early-exit in place..

[zvi]

Keep the check for undef mask + early exit in place.

[spatel]

LGTM. @RKSimon / @davide , any other comments?

[RKSimon]

LGTM

[zvi]

Rebase on top of trunk

lib/Analysis/InstructionSimplify.cpp

if (RootElt != DestElt)
     return nullptr;
 
   return RootVec;
 }
 
 static Value *SimplifyShuffleVectorInst(Value *Op0, Value *Op1, Constant *Mask,
                                         Type *RetTy, const Query &Q,
                                         unsigned MaxRecurse) {
-  if (isa<UndefValue>(Mask))
-    return UndefValue::get(RetTy);
-
   Type *InVecTy = Op0->getType();
   unsigned MaskNumElts = Mask->getType()->getVectorNumElements();
   unsigned InVecNumElts = InVecTy->getVectorNumElements();
 
-  auto *Op0Const = dyn_cast<Constant>(Op0);
-  auto *Op1Const = dyn_cast<Constant>(Op1);
-
-  // If all operands are constant, constant fold the shuffle.
-  if (Op0Const && Op1Const)
-    return ConstantFoldShuffleVectorInstruction(Op0Const, Op1Const, Mask);
-
   SmallVector<int, 32> Indices;
   ShuffleVectorInst::getShuffleMask(Mask, Indices);
 
-  // If only one of the operands is constant, constant fold the shuffle if the
-  // mask does not select elements from the variable operand.
+  // Canonicalization: If mask does not select elements from an input vector,
+  // replace that input vector with undef.
   bool MaskSelects0 = false, MaskSelects1 = false;
   for (unsigned i = 0; i != MaskNumElts; ++i) {
     if (Indices[i] == -1)
       continue;
     if ((unsigned)Indices[i] < InVecNumElts)
       MaskSelects0 = true;
     else
       MaskSelects1 = true;
   }
-  if (!MaskSelects0 && Op1Const)
-    return ConstantFoldShuffleVectorInstruction(UndefValue::get(InVecTy),
-                                                Op1Const, Mask);
-  if (!MaskSelects1 && Op0Const)
-    return ConstantFoldShuffleVectorInstruction(Op0Const,
-                                                UndefValue::get(InVecTy), Mask);
+  if (!MaskSelects0)
+    Op0 = UndefValue::get(InVecTy);
+  if (!MaskSelects1)
+    Op1 = UndefValue::get(InVecTy);
+
+  auto *Op0Const = dyn_cast<Constant>(Op0);
+  auto *Op1Const = dyn_cast<Constant>(Op1);
+
+  // If all operands are constant, constant fold the shuffle.
+  if (Op0Const && Op1Const)
+    return ConstantFoldShuffleVectorInstruction(Op0Const, Op1Const, Mask);
+
+  // Canonicalization: if only one input vector is constant, it shall be the
+  // second one.
+  if (Op0Const && !Op1Const) {
+    std::swap(Op0, Op1);
+    for (auto &Idx : Indices) {
+      if (Idx == -1)
+        continue;
+      Idx = Idx < (int)MaskNumElts ? Idx + MaskNumElts : Idx - MaskNumElts;
+    }
+    Mask = ConstantDataVector::get(
+        Mask->getContext(),
+        makeArrayRef(reinterpret_cast<uint32_t *>(Indices.data()),
+                     MaskNumElts));
+  }
 
   // A shuffle of a splat is always the splat itself. Legal if the shuffle's
   // value type is same as the input vectors' type.
   if (auto *OpShuf = dyn_cast<ShuffleVectorInst>(Op0))
-    if (!MaskSelects1 && RetTy == InVecTy &&
+    if (isa<UndefValue>(Op1) && RetTy == InVecTy &&
         OpShuf->getMask()->getSplatValue())
       return Op0;
-  if (auto *OpShuf = dyn_cast<ShuffleVectorInst>(Op1))
-    if (!MaskSelects0 && RetTy == InVecTy &&
-        OpShuf->getMask()->getSplatValue())
-      return Op1;
 
   // Don't fold a shuffle with undef mask elements. This may get folded in a
   // better way using demanded bits or other analysis.
   // TODO: Should we allow this?
   if (std::find(Indices.begin(), Indices.end(), -1) != Indices.end())
     return nullptr;
 
   // Check if every element of this shuffle can be mapped back to the
   // corresponding element of a single root vector. If so, we don't need this
   // shuffle. This handles simple identity shuffles as well as chains of
   // shuffles that may widen/narrow and/or move elements across lanes and back.
   Value *RootVec = nullptr;
   for (unsigned i = 0; i != MaskNumElts; ++i) {
     // Note that recursion is limited for each vector element, so if any element
     // exceeds the limit, this will fail to simplify.