[GlobalISel] Add support for lowering vector operations to scalar.

[Sonicadvance1]

Summary

Previously when attempting to legalize operations on architectures that
don't have true vector operation support the backend would need to do
the lowering by itself. This allows the legalizer to handle this situation by itself.

Here's the bugzilla for this: https://bugs.llvm.org/show_bug.cgi?id=36618

[lebedev.ri]

1. Please *always* upload all diffs with the full context (-U999999)
2. Tests?

[Sonicadvance1]

Updated the diff with as much context as possible

[Sonicadvance1]

As far as I'm aware it is impossible to write unit tests for this unless a backend uses it?
I've attempted adding this to AArch64's GlobalISel implementation and hit other deficiencies in the backend that are unrelated but this code uncovered.

[kristof.beyls]

In D44374#1034668, @Sonicadvance1 wrote:

As far as I'm aware it is impossible to write unit tests for this unless a backend uses it?
I've attempted adding this to AArch64's GlobalISel implementation and hit other deficiencies in the backend that are unrelated but this code uncovered.

Wouldn't you be able to write unit tests for this by extending unittests/CodeGen/GlobalISel/LegalizerInfoTest.cpp?

[kristof.beyls]

lib/CodeGen/GlobalISel/LegalizerHelper.cpp

1077–1080

I guess the FIXME should be removed, and the condition in the if statement could become an assert?
Vectors are always an exact multiple of a number of individual elements?

1088

I guess the code will read more natural if you don't try to stick very closely to the variable names used in the other lowering helper methods, but e.g. instead of "NumParts" use "NumElements" here?
Similarly maybe use "ElementTy" instead of "NarrowTy" and "ElementSize" instead of "NarrowSize"?

[Sonicadvance1]

Addressed the comments about readability and added a unit test for the decomposing.
Had to add a specialization that uncovered an issue where vectors with only one element aren't allowed to be generated.

[kristof.beyls]

include/llvm/CodeGen/GlobalISel/LegalizerHelper.h

91

Just a nit pick: I think "scalarizeVector" sounds more natural and in a similar style as the other methods here than "scalarElementsVector".
What do you think?

include/llvm/CodeGen/GlobalISel/LegalizerInfo.h

75

I think that similarly, "Scalarize" here might be less confusing that "LowerScalar".
"WidenScalar" and "NarrowScalar" already exist and do something on Scalar data types - for "LowerScalar" one could then also guess it does something on scalar data types which it doesn't. I think "Scalarize" is less ambiguous.

371

To be consistent with earlier comments: maybe best to change the method name to "scalarizeFor"?

lib/CodeGen/GlobalISel/LegalizerHelper.cpp

1075

This is over 80 characters long. Please run clang-format on the whole patch.

1081

I would have assumed that G_FMA has Operands 0, 1, 2, and 3; but I see only Operands 0, 1 and 2 being handled here.
I guess either G_FMA must be removed as a case from this switch statement and an assert added here that the number of operands is exactly 3; or the code should be made more generic to be able to handle generic opcodes with more input operands?

unittests/CodeGen/GlobalISel/LegalizerInfoTest.cpp

206–210

This suggests that you need to call the setAction API for every combination of (number of elements, element size) vector.
That doesn't scale.
Can you rewrite this in a simple way to represent that all vectors - irrespective of number of elements or element size - need to be scalarized for a given opcode?
e.g. something similar to the setLegalizeVectorElementToDifferentSizeStrategy API in tests higher up in this function.
Maybe a new function call in the API at that level needs to be introduced to be able to represent this?

include/llvm/CodeGen/GlobalISel/LegalizerHelper.h

public:
   LegalizeResult fewerElementsVector(MachineInstr &MI, unsigned TypeIdx,
                                      LLT NarrowTy);
 
   /// Legalize a vector instruction by increasing the number of vector elements
   /// involved and ignoring the added elements later.
   LegalizeResult moreElementsVector(MachineInstr &MI, unsigned TypeIdx,
                                     LLT WideTy);
 
+  /// Legalize a vector instruction by splitting in to multiple scalar
+  /// components, each acting on the same scalar type as the original but
+  /// as scalar operations.
+  LegalizeResult scalarElementsVector(MachineInstr &MI, unsigned TypeIdx);
+
   /// Expose MIRBuilder so clients can set their own RecordInsertInstruction
   /// functions
   MachineIRBuilder MIRBuilder;
 
   /// Expose LegalizerInfo so the clients can re-use.
   const LegalizerInfo &getLegalizerInfo() const { return LI; }
 
 private:

include/llvm/CodeGen/GlobalISel/LegalizerInfo.h

enum LegalizeAction : std::uint8_t {
   /// rarely legal, but you might perform an <8 x i8> and then only look at
   /// the first two results.
   MoreElements,
 
   /// The operation itself must be expressed in terms of simpler actions on
   /// this target. E.g. a SREM replaced by an SDIV and subtraction.
   Lower,
 
+  /// The (vector) operation should be implemented by splitting it in to
+  /// scalar operations. For example a <8 x s64> add will be implemented as
+  /// 8 separate s64 adds.
+  LowerScalar,
+
   /// The operation should be implemented as a call to some kind of runtime
   /// support library. For example this usually happens on machines that don't
   /// support floating-point operations natively.
   Libcall,
 
   /// The target wants to do something special with this combination of
   /// operand and type. A callback will be issued when it is needed.
   Custom,
public:
   }
   /// Remove elements to reach the type selected by the mutation if the
   /// predicate is true.
   LegalizeRuleSet &fewerElementsIf(LegalityPredicate Predicate,
                                    LegalizeMutation Mutation) {
     return actionIf(LegalizeAction::FewerElements, Predicate, Mutation);
   }
 
+  /// Lower the element to scalar operations of the same element type
+  LegalizeRuleSet &lowerScalarFor(std::initializer_list<LLT> Types) {
+    return actionFor(LegalizeAction::LowerScalar, Types);
+  }
+
   /// The instruction is unsupported.
   LegalizeRuleSet &unsupported() {
     return actionIf(LegalizeAction::Unsupported, always);
   }
   LegalizeRuleSet &unsupportedIf(LegalityPredicate Predicate) {
     return actionIf(LegalizeAction::Unsupported, Predicate);
   }
 

lib/CodeGen/GlobalISel/LegalizerHelper.cpp

case WidenScalar:
     DEBUG(dbgs() << ".. Widen scalar\n");
     return widenScalar(MI, Step.TypeIdx, Step.NewType);
   case Lower:
     DEBUG(dbgs() << ".. Lower\n");
     return lower(MI, Step.TypeIdx, Step.NewType);
   case FewerElements:
     DEBUG(dbgs() << ".. Reduce number of elements\n");
     return fewerElementsVector(MI, Step.TypeIdx, Step.NewType);
+  case LowerScalar:
+    DEBUG(dbgs() << ".. Reduce vector to scalar\n");
+    return scalarElementsVector(MI, Step.TypeIdx);
   case Custom:
     DEBUG(dbgs() << ".. Custom legalization\n");
     return LI.legalizeCustom(MI, MRI, MIRBuilder) ? Legalized
                                                   : UnableToLegalize;
   default:
     DEBUG(dbgs() << ".. Unable to legalize\n");
     return UnableToLegalize;
   }
case TargetOpcode::G_ADD: {
     }
 
     MIRBuilder.buildMerge(DstReg, DstRegs);
     MI.eraseFromParent();
     return Legalized;
   }
   }
 }
+LegalizerHelper::LegalizeResult
+LegalizerHelper::scalarElementsVector(MachineInstr &MI, unsigned TypeIdx) {
+  assert(TypeIdx == 0 && "Don't know how to handle secondary types yet");
+  switch (MI.getOpcode()) {
+  default:
+    return UnableToLegalize;
+  case TargetOpcode::G_ADD:
+  case TargetOpcode::G_AND:
+  case TargetOpcode::G_MUL:
+  case TargetOpcode::G_OR:
+  case TargetOpcode::G_XOR:
+  case TargetOpcode::G_SUB:
+  case TargetOpcode::G_FADD:
+  case TargetOpcode::G_FSUB:
+  case TargetOpcode::G_FMUL:
+  case TargetOpcode::G_FDIV:
+  case TargetOpcode::G_FMA:
+  case TargetOpcode::G_FPOW:
+  case TargetOpcode::G_FREM: {
+    unsigned DstReg = MI.getOperand(0).getReg();
+    LLT Type = MRI.getType(DstReg);
+    LLT ElementTy = Type.getElementType();
+    unsigned ElementSize = ElementTy.getSizeInBits();
+    unsigned Size = Type.getSizeInBits();
+    int NumElements = Size / ElementSize;
+    assert(Size % ElementSize == 0 && "Don't know how to handle situation where vector isn't the same size");
+
+    MIRBuilder.setInstr(MI);
+
+    SmallVector<unsigned, 4> Src1Regs, Src2Regs, DstRegs;
+    extractParts(MI.getOperand(1).getReg(), ElementTy, NumElements, Src1Regs);
+    extractParts(MI.getOperand(2).getReg(), ElementTy, NumElements, Src2Regs);
+
+    for (int i = 0; i < NumElements; ++i) {
+      unsigned DstReg = MRI.createGenericVirtualRegister(ElementTy);
+      MIRBuilder.buildInstr(MI.getOpcode())
+        .addDef(DstReg)
+        .addUse(Src1Regs[i])
+        .addUse(Src2Regs[i]);
+      DstRegs.push_back(DstReg);
+    }
+
+    MIRBuilder.buildMerge(DstReg, DstRegs);
+    MI.eraseFromParent();
+    return Legalized;
+  }
+  }
+}

lib/CodeGen/GlobalISel/LegalizerInfo.cpp

LegalizerInfo::findAction(const SizeAndActionsVec &Vec, const uint32_t Size) {
 
   LegalizeAction Action = Vec[VecIdx].second;
   switch (Action) {
   case Legal:
   case Lower:
   case Libcall:
   case Custom:
     return {Size, Action};
+  case LowerScalar:
+    return {1, LowerScalar};
   case FewerElements:
     // FIXME: is this special case still needed and correct?
     // Special case for scalarization:
     if (Vec == SizeAndActionsVec({{1, FewerElements}}))
       return {1, FewerElements};
     LLVM_FALLTHROUGH;
   case NarrowScalar: {
     // The following needs to be a loop, as for now, we do allow needing to
LegalizerInfo::findVectorLegalAction(const InstrAspect &Aspect) const {
   auto i = NumElements2Actions[OpcodeIdx].find(
       IntermediateType.getScalarSizeInBits());
   if (i == NumElements2Actions[OpcodeIdx].end()) {
     return {NotFound, IntermediateType};
   }
   const SizeAndActionsVec &NumElementsVec = (*i).second[TypeIdx];
   auto NumElementsAndAction =
       findAction(NumElementsVec, IntermediateType.getNumElements());
+
+  // Vector op decomposed in to scalar
+  if (NumElementsAndAction.second == LowerScalar) {
+    return {NumElementsAndAction.second,
+            LLT::scalar(IntermediateType.getScalarSizeInBits())};
+  }
   return {NumElementsAndAction.second,
           LLT::vector(NumElementsAndAction.first,
                       IntermediateType.getScalarSizeInBits())};
 }
 
 #ifndef NDEBUG
 // FIXME: This should be in the MachineVerifier, but it can't use the
 // LegalizerInfo as it's currently in the separate GlobalISel library.

unittests/CodeGen/GlobalISel/LegalizerInfoTest.cpp

 operator<<(std::ostream &OS, const LegalizeAction Act) {
   switch (Act) {
   case Lower: OS << "Lower"; break;
   case Legal: OS << "Legal"; break;
   case NarrowScalar: OS << "NarrowScalar"; break;
   case WidenScalar:  OS << "WidenScalar"; break;
   case FewerElements:  OS << "FewerElements"; break;
   case MoreElements:  OS << "MoreElements"; break;
+  case LowerScalar: OS << "LowerScalar"; break;
   case Libcall: OS << "Libcall"; break;
   case Custom: OS << "Custom"; break;
   case Unsupported: OS << "Unsupported"; break;
   case NotFound: OS << "NotFound"; break;
   case UseLegacyRules: OS << "UseLegacyRules"; break;
   }
   return OS;
 }
ASSERT_EQ(L.getAction({G_UREM, {LLT::scalar(9)}}),
             LegalizeActionStep(WidenScalar, 0, LLT::scalar(16)));
   ASSERT_EQ(L.getAction({G_UREM, {LLT::scalar(17)}}),
             LegalizeActionStep(WidenScalar, 0, LLT::scalar(32)));
   ASSERT_EQ(L.getAction({G_UREM, {LLT::scalar(31)}}),
             LegalizeActionStep(WidenScalar, 0, LLT::scalar(32)));
   ASSERT_EQ(L.getAction({G_UREM, {LLT::scalar(33)}}),
             LegalizeActionStep(Unsupported, 0, LLT::scalar(33)));
 }
+
+TEST(LegallizerInfoTest, ScalarDecomposeStrategy) {
+  using namespace TargetOpcode;
+  LegalizerInfo L;
+  for (unsigned Elements = 2; Elements < 16; ++Elements) {
+    for (unsigned Size : {8, 16, 32, 64}) {
+      L.setAction({G_FADD, 0, LLT::vector(Elements, Size)}, LowerScalar);
+    }
+  }
+
+  L.computeTables();
+
+  // Check we infer the correct types and actually do what we're told.
+  for (unsigned Elements = 2; Elements < 16; ++Elements) {
+    for (unsigned Size : {8, 16, 32, 64}) {
+
+      auto returnedAction = L.getAction({G_FADD, {LLT::vector(Elements, Size)}});
+      auto generatedAction = LegalizeActionStep(LowerScalar, 0, LLT::scalar(Size));
+      ASSERT_EQ(L.getAction({G_FADD, {LLT::vector(Elements, Size)}}),
+              LegalizeActionStep(LowerScalar, 0, LLT::scalar(Size)));
+    }
+  }
+}
 }