[TableGen] Add not_all_same constraint check

[greened]

Summary

Add a new constraint to express that not all operands of an instruction can be
assigned the same register. This is necessary for efficient use of SVE's MOVPRFX
as MOVPRFX has a restriction that its destination register may only appear as
the tied source of the following instruction. MOVPRFX is used for two purposes,
to turn a destructive operation into a non-destructive operation and to turn a
passthru-merging predicate operation into zero-merging predicate operation.

The constraint is needed when using MOVPRFX for the latter.

As an example, consider FDIV and FDIVR, where FDIVR is a "reverse" divide:

a = FDIV  p/m, b, c  # a[i] = p[i] ? b[i] / c[i] : a[i]
a = FDIVR p/m, c, b  # a[i] = p[i] ? b[i] / c[i] : a[i]

These are defined with tied constraints (simplified from existing
AArch64SVEInstrInfo.td):

let Constraints = "$Zdn = $_Zdn" in {
  // a[i] = p[i] ? b[i] / c[i] : a[i]
  defm FDIV_MERGE  : I<(outs z:$Zdn), (ins p:$Pg, z:$_Zdn, z:$Zm)>
  // a[i] = p[i] ? b[i] / c[i] : a[i]
  defm FDIVR_MERGE : I<(outs z:$Zdn), (ins p:$Pg, z:$_Zdn, z:$Zm)>
}

There are no separate zero-merging versions of these instructions. However,
we can define pseudo-instructions that act as zero-merging instructions:

let Constraints = "not_all_same($Zdn, $_Zdn, $Zm)" in {
  // a[i] = p[i] ? b[i] / c[i] : 0
  defm FDIV_ZERO  : I<(outs z:$Zdn), (ins p:$Pg, z:$_Zdn, z:$Zm)>
  // a[i] = p[i] ? b[i] / c[i] : 0
  defm FDIVR_ZERO : I<(outs z:$Zdn), (ins p:$Pg, z:$_Zdn, z:$Zm)>
}

Instruction selection can generate one of these:

vz0 = FDIV_ZERO pz1/z, vz2, vz3

If register allocation can't easily tie vz0 and vz2, it could produce this:

z0 = FDIV_ZERO p1, z2, z3

This is trivially expandable with MOVPRFX:

z0 = MOVPRFX p1/z, z2         # Both copies and makes FDIV_MERGE zero-merging
z0 = FDIV_MERGE p1/m, z0, z3

Note that even if the register allocator could tie vz0 and vz2, we'd still need
the MOVPRFX to support zero-merging so there's no adtantage to using a tied
constraint.

But say instruction selection produces this:

vz0 = FDIV_ZERO pz1/z, vz2, vz2

Note that even though both sources use the same virtual register, we may not be
able to replace this instruction with "1.0" due to traps or IEEE conformance so
we can't jst delete it.

Let's say instead of not_all_same we'd specified the constraint as "$Zdn =
$_Zdn" (i.e. tied) or had no constraints at all. Register allocation could
produce this without any extra copies:

z0 = FDIV_ZERO p1, z0, z0     # vz2 was dead after this instruction

When we go to expand the pseudo we might naively do this:

z0 = MOVPRFX p1/z, z0
z0 = FDIV_MERGE p1/m, z0, z0

Except now we've violated the constraint on MOVPRFX that its destination can
only appear on the tied source operand and nowhere else. So we need an extra
MOV:

z1 = MOV z0                   # Satisfy the MOVPRFX constraint
z0 = MOVPRFX p1/z, z0         # Needed to make FDIV_MERGE zero-merging
z0 = FDIV_MERGE p1/m, z0, z1

If we use the not_all_same constraint instead, register allocation can assign a
different register to vz0:

z1 = FDIV_ZERO p1, z0, z0

Now we can easily expand this without an extra MOV:

z1 = MOVPRFX p1/z, z0         # Both copies and makes FDIV_MERGE zero-merging
z1 = FDIV_MERGE p1, z1, z0

Note than an @earlyclobber constraint will not save us because it would
pessimize the lowering of this:

vz0 = FDIV_ZERO vp1, vz2, vz3

If vz2 were dead after the FDIV_ZERO, we could allocate vz0 and vz2 to the same
register and trivially lower the FDIV_ZERO. If vz0 had an @earlyclobber
constraint, we would not be able to allocate vz0 and vz2 to the same register,
pessimizing register allocation. Similarly, if one of vz2 or vz3 were
@earlyclobber, then vz2 and vz3 could not be the same register, which would
require an extra MOV for our second example above.

Since neither the tied nor the @earlyclobber constraint can express the needed
semantics, we need a new constraint type that accurately expresses the register
allocation restrictions on these zero-merging pseudo-instructions, which is the
role that not_all_same plays.

[greened]

Make clang-tidy (more?) happy.

[greened]

llvm/utils/TableGen/CodeGenInstruction.cpp

16

Hmm. Is this actually a correct warning? Why would "ST" be lexigraphically before "Sm?"

[sdesmalen]

Thanks for working on this @greened!

llvm/utils/TableGen/CodeGenInstruction.cpp

256

nit: s/CStr/ConstraintString/

I keep reading this as C string, whereas it's actually a std::string :)

266

If you would pass the constraint as a StringRef, then you can use its convenient split() method and also use the trim method to trim any whitespace.

285

nit: given that it may return true/false based on success/failure, can you rename it to tryToPlaceNotAllSameConstraint?

291

Is there a reason it can only be applied to a single operand? I would expect the constraint to be applied to all the operands that are described in the constraint string.

/// This holds information about one operand of a machine instruction,
/// indicating the register class for register operands, etc.
class MCOperandInfo {
public:

  [...]

  /// The lower 16 bits are used to specify which constraints are set.
  /// The higher 16 bits are used to specify the value of constraints (4 bits
  /// each).
  uint32_t Constraints;

That suggests that multiple constraints can be set per operand?

411

nit: Maybe pull the semantic checks out into a separate function?

441

Should this be >= Operands.size() ?

llvm/utils/TableGen/InstrInfoEmitter.cpp

187

This only working for 4 operands doesn't seem very future proof. I guess you can still redefine that bitfield to take '8bits' info for each constraint, so that there are 3 bytes for the 3 constraints + one byte that specifies which constraints are enabled. New constraints that are added after this one would mean changing the int32_t -> int64_t, but given that after all these years only IsTied and EarlyClobber exist, shows doesn't need to happen very often :)

[greened]

llvm/utils/TableGen/CodeGenInstruction.cpp

256

I was following existing convention but I agree with you!

291

TableGen will not allow multiple constraints on an operand. There are checks and aborts for that. Perhaps that restriction can be lifted but that's a whole other can of worms.

llvm/utils/TableGen/InstrInfoEmitter.cpp

187

Again, I think that may be a fine change as a follow-up but I'd rather not conflate it with this change. This change is large enough already. :)

[greened]

llvm/utils/TableGen/CodeGenInstruction.cpp

291

Thinking about this some more, I'll see if I can lift this restriction. It certainly would simplify the handling of this constraint since we wouldn't need all the rigmarole around finding a (single) place for it.

I don't really understand the upper/lower 16 bit thing. If we have the ability to signal 16 different constraints on an operand, why does the comment talk about four bits of value for each constraint? That would seem to mean only four constraints are allowed at once. It's an odd partition of the 32 bits available.

llvm/utils/TableGen/InstrInfoEmitter.cpp

187

I like your 8 bit value idea though. If we think it's important to do sooner rather than later (because near-future ISAs needing this constraint will have more than four operands) perhaps I can make the 8 bit change first and then land this one. I don't really know what the implications are of changing the constraint layout though. It's been this way for so long that it makes me nervous to change it. What do you think? Important to do now or can it wait?

[sdesmalen]

llvm/utils/TableGen/CodeGenInstruction.cpp

291

Thinking about this some more, I'll see if I can lift this restriction. It certainly would simplify the handling of this constraint since we wouldn't need all the rigmarole around finding a (single) place for it.

Thanks! The tests are quite confusing on how it tries to find a suitable operand to place the constraint.

I don't really understand the upper/lower 16 bit thing. If we have the ability to signal 16 different constraints on an operand, why does the comment talk about four bits of value for each constraint? That would seem to mean only four constraints are allowed at once. It's an odd partition of the 32 bits available.

The partitioning is odd indeed, but with only two constraints I doubt there was never a need to reconsider this.

llvm/utils/TableGen/InstrInfoEmitter.cpp

187

It should be fine to fix in a follow-up patch as the instructions you're trying to target only have four operands and those will be the only instructions needing the new constraint for now.
That said, from a quick glance MCInstrDesc::getOperandConstraint seems to be the only interface directly using it (returning as an int), so I think it's worth a try to see if this a one/few line change is sufficient (and if not, to just leave it for a follow-up patch)

[greened]

This is still on my TODO list but got pushed aside for a bit due to other issues. I expect to be back on this in the next couple of weeks.

[greened]

Updated to main, implemented some suggested changes.

[greened]

llvm/utils/TableGen/CodeGenInstruction.cpp

291

I looked into this and it seems like allowing multiple contraints on an operand is going to require some major surgery. It will require that the Constraints vector in CGIOperandList::OperandInfo` become multi-dimensional, as currently the vector tracks constraints per "sub-operand."

Maybe that will be ok but I don't yet have a good handle about what the fallout from that would be.

[greened]

llvm/utils/TableGen/CodeGenInstruction.cpp

291

Actully I think a better approach would be to encode multiple constraints in ConstraintInfo and then have the generator use that to emit the operand info.

[sdesmalen]

llvm/utils/TableGen/CodeGenInstruction.cpp

291

Thanks for looking at this again @greened, I had to swap some pages back in my memory to understand the state of this :)

Looking at this patch with a slightly fresh view, I realised it may not be strictly necessary to add support for more than one constraint per operand, because the constraints can be sufficiently simplified. Some observations when there are operands with >1 constraint:

• EarlyClobber is a more strict variant of not_all_same in that it specifically requires the earlyclobber operand to be allocated a different register from the rest. The not_all_same constraint is then already satisfied by the earlyclobber, making the constraint redundant. That means for a set of constraints, the following rule applies:

{not_all_same(Dst, Op0, Op1), earlyclobber(Dst)} => {earlyclobber(Dst)}

• Tied operands conflict with not_all_same in that two operands cannot be the same if one of them must be different. That means the following rule applies:

{IsTied(Dst, Op0), not_all_same(Dst, Op0, Op1, Op2)} => {IsTied(Dst, Op0), not_all_same(Op1, Op2)}

The register allocator is still free to choose either Op1 or Op2 to be the same as Dst(==Op0), but not both.

• For the case where there would only be one remaining register that needs to be different, the following rule applies:

{IsTied(Dst, Op0), not_all_same(Dst, Op0, Op1)} => {IsTied(Dst, Op0), EarlyClobber(Dst)}

This would satisfy that Op1 must be different from Dst/Op0. According to the LangRef this case is already supported:

It is permitted to tie an input to an “early-clobber” output. In that case, no other input may share the same register as the input tied to the early-clobber (even when the other input has the same value).

The only case that would not be supported is having multiple overlapping not_all_same constraints, but I'm not sure how important it is to support that (as long as TableGen gives an error when that happens).

Adding support for multiple constraints is better if we want to extend TableGen with new constraints in the future, but if my reasoning above is correct, it may not be required to consistently represent not_all_same. I thought it was worth pointing out there is something in between the current patch and major surgery. Curious to hear your thoughts!

[dancgr]

@paulwalker-arm @sdesmalen I will be picking up this work, I will study this patch and see if I have any questions. Thanks!

[dancgr]

llvm/utils/TableGen/CodeGenInstruction.cpp

291

@sdesmalen As far as I understood, you are trying to question whether or not we need to add support for multiple constraints on the same operand, correct?

I agree with your statement. I don't think we need not_all_same and early_clobber at the same time, if early_clobber is statisfied, then not_all_same will also be satisfied. And I agree that there is a conflict between not_all_same and tied operands. Then we are left with the possible need of overlapping not_all_same constraints.

The main example is preventing this:

vz0 = FDIV_ZERO pz1/z, vz2, vz2 => z0 = FDIV_ZERO p1, z0, z0

To support this case we need only:

let Constraints = "not_all_same($Zdn, $_Zdn, $Zm)" in {
  // a[i] = p[i] ? b[i] / c[i] : 0
  defm FDIV_ZERO  : I<(outs z:$Zdn), (ins p:$Pg, z:$_Zdn, z:$Zm)>
  // a[i] = p[i] ? b[i] / c[i] : 0
  defm FDIVR_ZERO : I<(outs z:$Zdn), (ins p:$Pg, z:$_Zdn, z:$Zm)>
}

For that we will have: The single constraint prevents vz0 and vz2 from being assinged the same register.

vz0 = FDIV_ZERO pz1/z, vz2, vz2 => z1 = FDIV_ZERO p1, z0, z0

If that is the case, I think we can change this patch to only add an extra constraint and remove the multiple constraints aspect.

Is there anything that I missed?

[greened]

In D88595#2744776, @dancgr wrote:

@paulwalker-arm @sdesmalen I will be picking up this work, I will study this patch and see if I have any questions. Thanks!

Thank you. I'm sorry about not being present. I had a job change and can't spend time on this right now.

[arsenm]

Could you use hasExtraSrcRegAllocReq/hasExtraDefRegAllocReq?

llvm/include/llvm/MC/MCInstrDesc.h

 //===----------------------------------------------------------------------===//
 
 namespace MCOI {
 /// Operand constraints. These are encoded in 16 bits with one of the
 /// low-order 3 bits specifying that a constraint is present and the
 /// corresponding high-order hex digit specifying the constraint value.
 /// This allows for a maximum of 3 constraints.
 enum OperandConstraint {
-  TIED_TO = 0,  // Must be allocated the same register as specified value.
-  EARLY_CLOBBER // If present, operand is an early clobber register.
+  TIED_TO = 0,   // Must be allocated the same register as specified value.
+  EARLY_CLOBBER, // If present, operand is an early clobber register.
+  NOT_ALL_SAME   // Operands listed cannot all be assigned the same register.
 };
 
 // Define a macro to produce each constraint value.
 #define MCOI_TIED_TO(op) \
   ((1 << MCOI::TIED_TO) | ((op) << (4 + MCOI::TIED_TO * 4)))
 
 #define MCOI_EARLY_CLOBBER \
   (1 << MCOI::EARLY_CLOBBER)
 
+#define MCOI_NOT_ALL_SAME(bitset) \
+  ((bitset << (16 + 4*MCOI::NOT_ALL_SAME)) | (1 << MCOI::NOT_ALL_SAME))
+
 /// These are flags set on operands, but should be considered
 /// private, all access should go through the MCOperandInfo accessors.
 /// See the accessors for a description of what these are.
 enum OperandFlags {
   LookupPtrRegClass = 0,
   Predicate,
   OptionalDef,
   BranchTarget

llvm/test/TableGen/ConstraintChecking.inc

 include "llvm/Target/Target.td"
 
-def TestTarget : Target;
+def TestInstrInfo : InstrInfo;
+
+def TestTarget : Target {
+    let InstructionSet = TestInstrInfo;
+}
 
 class Encoding : Instruction {
   field bits<8> Inst;
 }
 
 class TestReg<string name, bits<1> enc> : Register<name, []> {
     let HWEncoding{15-1} = 0;
     let HWEncoding{0} = enc;
 }
 
 def R0 : TestReg<"R0", 0>;
 def R1 : TestReg<"R1", 1>;
 def Reg : RegisterClass<"TestTarget", [i32], 32, (sequence "R%d", 0, 1)>;
 
 class TestInstructionWithConstraints<string cstr> : Encoding {
+  let Namespace = "Test";
   dag OutOperandList = (outs Reg:$dest1, Reg:$dest2);
-  dag InOperandList = (ins Reg:$src1, Reg:$src2);
-  string AsmString = "mnemonic $dest1, $dest2, $src1, $src2";
+  dag InOperandList = (ins Reg:$src1, Reg:$src2, Reg:$src3);
+  string AsmString = "mnemonic $dest1, $dest2, $src1, $src2, $src3";
   string AsmVariantName = "";
   let Constraints = cstr;
   field bits<1> dest1;
   field bits<1> dest2;
   field bits<1> src1;
   field bits<1> src2;
   let Inst{7-4} = 0b1010;
   let Inst{3} = dest1{0};
   let Inst{2} = dest2{0};
   let Inst{1} = src1{0};
   let Inst{0} = src2{0};
 }

llvm/test/TableGen/NotAllSameConstraintChecking1.td

+// RUN: llvm-tblgen -gen-asm-writer -I %p -I %p/../../include %s 2>&1 | FileCheck %s -DFILE=%s
+
+include "ConstraintChecking.inc"
+
+// CHECK-LABEL: #ifdef GET_INSTRINFO_ENUM
+
+// CHECK: Dest1A {{[[:space]]+}} = [[DEST1A:[0-9]+]]
+// CHECK: Dest1B {{[[:space]]+}} = [[DEST1B:[0-9]+]]
+// CHECK: Dest2A {{[[:space]]+}} = [[DEST2A:[0-9]+]]
+// CHECK: Dest2B {{[[:space]]+}} = [[DEST2B:[0-9]+]]
+// CHECK: Src1A {{[[:space]]+}} = [[SRC1A:[0-9]+]]
+// CHECK: Src1B {{[[:space]]+}} = [[SRC1B:[0-9]+]]
+// CHECK: Src2 {{[[:space]]+}} = [[SRC2:[0-9]+]]
+
+// CHECK-LABEL: #ifdef GET_INSTRINFO_MC_DESC
+
+// CHECK: static const MCOperandInfo [[OPINFODEST1:OperandInfo[0-9]+]][] = { { TestTarget::RegRegClassID, 0, MCOI::OPERAND_REGISTER, 0 }, { TestTarget::RegRegClassID, 0, MCOI::OPERAND_REGISTER, 0 }, { TestTarget::RegRegClassID, 0, MCOI::OPERAND_REGISTER, ((0xF<< 16 + 4*MCOI::NOT_ALL_SAME| (1 << MCOI::NOT_ALL_SAME)) }, { TestTarget::RegRegClassID, 0, MCOI::OPERAND_REGISTER, (1 << MCOI::EARLY_CLOBBER) }, { TestTarget::RegRegClassID, 0, MCOI::OPERAND_REGISTER, 0 }, };
+// CHECK-NEXT: static const MCOperandInfo [[OPINFODEST2:OperandInfo[0-9]+]][] = { { TestTarget::RegRegClassID, 0, MCOI::OPERAND_REGISTER, 0 }, { TestTarget::RegRegClassID, 0, MCOI::OPERAND_REGISTER, ((0xF<< 16 + 4*MCOI::NOT_ALL_SAME| (1 << MCOI::NOT_ALL_SAME)) }, { TestTarget::RegRegClassID, 0, MCOI::OPERAND_REGISTER, ((0 << 16) | (1 << MCOI::TIED_TO)) }, { TestTarget::RegRegClassID, 0, MCOI::OPERAND_REGISTER, (1 << MCOI::EARLY_CLOBBER) }, { TestTarget::RegRegClassID, 0, MCOI::OPERAND_REGISTER, 0 }, };
+// CHECK-NEXT: static const MCOperandInfo [[OPINFOSRC1:OperandInfo[0-9]+]][] = { { TestTarget::RegRegClassID, 0, MCOI::OPERAND_REGISTER, (1 << MCOI::EARLY_CLOBBER) }, { TestTarget::RegRegClassID, 0, MCOI::OPERAND_REGISTER, (1 << MCOI::EARLY_CLOBBER) }, { TestTarget::RegRegClassID, 0, MCOI::OPERAND_REGISTER, ((0xF<< 16 + 4*MCOI::NOT_ALL_SAME| (1 << MCOI::NOT_ALL_SAME)) }, { TestTarget::RegRegClassID, 0, MCOI::OPERAND_REGISTER, ((0 << 16) | (1 << MCOI::TIED_TO)) }, { TestTarget::RegRegClassID, 0, MCOI::OPERAND_REGISTER, 0 }, };
+// CHECK-NEXT: static const MCOperandInfo [[OPINFOSRC2:OperandInfo[0-9]+]][] = { { TestTarget::RegRegClassID, 0, MCOI::OPERAND_REGISTER, 0 }, { TestTarget::RegRegClassID, 0, MCOI::OPERAND_REGISTER, 0 }, { TestTarget::RegRegClassID, 0, MCOI::OPERAND_REGISTER, 0 }, { TestTarget::RegRegClassID, 0, MCOI::OPERAND_REGISTER, ((0xF<< 16 + 4*MCOI::NOT_ALL_SAME| (1 << MCOI::NOT_ALL_SAME)) }, { TestTarget::RegRegClassID, 0, MCOI::OPERAND_REGISTER, 0 }, };
+
+// CHECK-LABEL: extern const MCInstrDesc TestTargetInsts[] = {
+
+// Constraint should go on $src2.
+// CHECK-DAG: { [[SRC2]], {{.*}}, [[OPINFOSRC2]] },  // Inst #[[SRC2]] = Src2
+def Src2 : TestInstructionWithConstraints<"not_all_same($dest1, $dest2, $src1, $src2)">;
+
+// Constraint should go on $dest1.
+// CHECK-DAG: { [[DEST1A]], {{.*}}, [[OPINFODEST1]] },  // Inst #[[DEST1A]] = Dest1A
+def Dest1A : TestInstructionWithConstraints<"@earlyclobber $src2, not_all_same($dest1, $dest2, $src1, $src2)">;
+
+// Constraint should go on $dest1.
+// CHECK-DAG: { [[DEST1B]], {{.*}}, [[OPINFODEST1]] },  // Inst #[[DEST1B]] = Dest1B
+def Dest1B : TestInstructionWithConstraints<"not_all_same($dest1, $dest2, $src1, $src2), @earlyclobber $src2">;
+
+// Constraint should go on $dest2.
+// CHECK-DAG: { [[DEST2A]], {{.*}}, [[OPINFODEST2]] },  // Inst #[[DEST2A]] = Dest2A
+def Dest2A : TestInstructionWithConstraints<"@earlyclobber $src2, $dest1 = $src1, not_all_same($dest1, $dest2, $src1, $src2)">;
+
+// Constraint should go on $dest2.
+// CHECK-DAG: { [[DEST2B]], {{.*}}, [[OPINFODEST2]] },  // Inst #[[DEST2B]] = Dest2B
+def Dest2B : TestInstructionWithConstraints<"not_all_same($dest1, $dest2, $src1, $src2), @earlyclobber $src2, $dest1 = $src1">;
+
+// Constraint should go on $src1.
+// CHECK-DAG: { [[SRC1A]], {{.*}}, [[OPINFOSRC1]] },  // Inst #[[SRC1A]] = Src1A
+def Src1A : TestInstructionWithConstraints<"@earlyclobber $dest1, @earlyclobber $dest2, $dest1 = $src2, not_all_same($dest1, $dest2, $src1, $src2)">;
+
+// Constraint should go on $src1.
+// CHECK-DAG: { [[SRC1B]], {{.*}}, [[OPINFOSRC1]] },  // Inst #[[SRC1B]] = Src1B
+def Src1B : TestInstructionWithConstraints<"not_all_same($dest1, $dest2, $src1, $src2), @earlyclobber $dest1, @earlyclobber $dest2, $dest1 = $src2">;
+

llvm/test/TableGen/NotAllSameConstraintChecking2.td

+// RUN: not llvm-tblgen -gen-instr-info -I %p -I %p/../../include %s 2>&1 | FileCheck %s -DFILE=%s
+
+include "ConstraintChecking.inc"
+
+// CHECK: [[FILE]]:[[@LINE+1]]:1: error: Operand '$dest1' of 'Foo' cannot have multiple operands tied to it!
+def Foo : TestInstructionWithConstraints<"@earlyclobber $dest1, @earlyclobber $dest2, $dest1 = $src1, $dest2 = $src2, not_all_same($dest1, $dest2, $src1, $src2)">;

llvm/test/TableGen/NotAllSameConstraintChecking3.td

+// RUN: not llvm-tblgen -gen-instr-info -I %p -I %p/../../include %s 2>&1 | FileCheck %s -DFILE=%s
+
+include "ConstraintChecking.inc"
+
+// CHECK: [[FILE]]:[[@LINE+1]]:1: error: Operand '$src2' of 'Foo' cannot have multiple constraints!
+def Foo : TestInstructionWithConstraints<"not_all_same($dest1, $dest2, $src1, $src2), @earlyclobber $dest1, @earlyclobber $dest2, $dest1 = $src1, $dest2 = $src2">;

llvm/test/TableGen/NotAllSameConstraintChecking4.td

+// RUN: not llvm-tblgen -gen-asm-writer -I %p -I %p/../../include %s 2>&1 | FileCheck %s -DFILE=%s
+
+include "ConstraintChecking.inc"
+
+// CHECK: [[FILE]]:[[@LINE+1]]:1: error: not_all_same operand '$src3' [Num = 4] out of bounds in 'Foo': 'not_all_same($dest1, $dest2, $src1, $src2, $src3)'
+def Foo : TestInstructionWithConstraints<"not_all_same($dest1, $dest2, $src1, $src2, $src3)">;

llvm/utils/TableGen/CodeGenInstruction.h

 //===- CodeGenInstruction.h - Instruction Class Wrapper ---------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // This file defines a wrapper class for the 'Instruction' TableGen class.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_UTILS_TABLEGEN_CODEGENINSTRUCTION_H
 #define LLVM_UTILS_TABLEGEN_CODEGENINSTRUCTION_H
 
+#include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Support/MachineValueType.h"
 #include "llvm/Support/SMLoc.h"
 #include <cassert>
 #include <string>
 #include <utility>
 #include <vector>
 
 namespace llvm {
 template <typename T> class ArrayRef;
   class Record;
   class DagInit;
   class CodeGenTarget;
 
   class CGIOperandList {
   public:
     class ConstraintInfo {
-      enum { None, EarlyClobber, Tied } Kind = None;
-      unsigned OtherTiedOperand = 0;
+    public:
+      using Operand = unsigned;
+      using OperandList = SmallVector<Operand, 4>;
+
+    private:
+      enum { None, EarlyClobber, Tied, NotAllSame } Kind = None;
+      OperandList Operands;
 
     public:
       ConstraintInfo() = default;
 
       static ConstraintInfo getEarlyClobber() {
         ConstraintInfo I;
         I.Kind = EarlyClobber;
-        I.OtherTiedOperand = 0;
         return I;
       }
 
       static ConstraintInfo getTied(unsigned Op) {
         ConstraintInfo I;
         I.Kind = Tied;
-        I.OtherTiedOperand = Op;
+        I.Operands.push_back(Op);
+        return I;
+      }
+
+      static ConstraintInfo getNotAllSame(const SmallVectorImpl<Operand> &Ops) {
+        ConstraintInfo I;
+        I.Kind = NotAllSame;
+        I.Operands.assign(Ops.begin(), Ops.end());
+        return I;
+      }
+
+      static ConstraintInfo getNotAllSame(SmallVectorImpl<Operand> &&Ops) {
+        ConstraintInfo I;
+        I.Kind = NotAllSame;
+        I.Operands = std::move(Ops);
         return I;
       }
 
       bool isNone() const { return Kind == None; }
       bool isEarlyClobber() const { return Kind == EarlyClobber; }
       bool isTied() const { return Kind == Tied; }
+      bool isNotAllSame() const { return Kind == NotAllSame; }
+
+      OperandList::size_type getNumOperands() const { return Operands.size(); }
+
+      using const_iterator = OperandList::const_iterator;
+      using const_range = iterator_range<const_iterator>;
+
+      const_iterator begin() const { return Operands.begin(); }
+      const_iterator end() const { return Operands.end(); }
+
+      const_range operands() const { return make_range(begin(), end()); }
 
       unsigned getTiedOperand() const {
         assert(isTied());
-        return OtherTiedOperand;
+        return *begin();
       }
 
       bool operator==(const ConstraintInfo &RHS) const {
         if (Kind != RHS.Kind)
           return false;
-        if (Kind == Tied && OtherTiedOperand != RHS.OtherTiedOperand)
+        if ((Kind == Tied || Kind == NotAllSame) && Operands != RHS.Operands)
           return false;
         return true;
       }
       bool operator!=(const ConstraintInfo &RHS) const {
         return !(*this == RHS);
       }
     };
 

llvm/utils/TableGen/CodeGenInstruction.cpp

 //===- CodeGenInstruction.cpp - CodeGen Instruction Class Wrapper ---------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // This file implements the CodeGenInstruction class.
 //
 //===----------------------------------------------------------------------===//
 
 #include "CodeGenInstruction.h"
 #include "CodeGenTarget.h"
+#include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/StringExtras.h"
 #include "llvm/ADT/StringMap.h"
 #include "llvm/TableGen/Error.h"
 #include "llvm/TableGen/Record.h"
 #include <set>
 using namespace llvm;
 
 //===----------------------------------------------------------------------===//
CGIOperandList::ParseOperandName(const std::string &Op, bool AllowWholeOp) {
 
   // Otherwise, didn't find it!
   PrintFatalError(TheDef->getLoc(), TheDef->getName() +
                                         ": unknown suboperand name in '" + Op +
                                         "'");
   return std::make_pair(0U, 0U);
 }
 
+// Represent a single function-style constraint argument.
+struct ConstraintArg {
+  std::string Name;
+  unsigned OpNum;
+  unsigned SubOpNum;
+
+  ConstraintArg(std::string N, unsigned O, unsigned S) :
+      Name(std::move(N)), OpNum(O), SubOpNum(S) {}
+
+  ConstraintArg(std::string N, const std::pair<unsigned, unsigned> &Op) :
+      Name(std::move(N)), OpNum(Op.first), SubOpNum(Op.second) {}
+};
+
+static bool operator<(const ConstraintArg &A, const ConstraintArg &B) {
+  return A.OpNum < B.OpNum || (A.OpNum == B.OpNum && A.SubOpNum < B.SubOpNum);
+}
+
+// Parse a list of constraint parts.  CStr is a string of comma-separated names
+// with leading and trailing whitespace stripped.  Whitespace may still appear
+// after a comma and before the next name.
+static SmallVector<ConstraintArg, 8>
+ParseConstraintOperands(const StringRef ConstraintStr,
+                        CGIOperandList &Ops,
+                        Record *Rec) {
+  SmallVector<ConstraintArg, 8> List;
+
+  SmallVector<StringRef, 8> Args;
+  ConstraintStr.split(Args, ",");
+
+  for (StringRef Arg : Args) {
+    std::string Name(Arg.trim().str());
+    std::pair<unsigned,unsigned> Op = Ops.ParseOperandName(Name, false);
+
+    // Record the name for diagnostic purposes.
+    List.push_back(ConstraintArg(Name, Op.first, Op.second));
+  }
+  return List;
+}
+
+// Try to find an operand on which to place a not-all-same constraint.  Return
+// true on success, false otherwise.
+
+static bool TryToPlaceNotAllSameConstraint(
+    CGIOperandList::ConstraintInfo NewConstraint,
+    CGIOperandList &Ops) {
+  assert(NewConstraint.isNotAllSame() && "Wrong constraint type!");
+
+  // We need to decide where to put this constraint.  It seems that this should
+  // be straightforward but unfortunately we don't know if we might see a
+  // constraint in the future.  The tied constraint will go on the source so we
+  // would prefer not to put it there.  In addition, a destination may have an
+  // early clobber constraint, so we'd prefer to not put this on a destination.
+  // Since we can't know which source might be tied to the destination and we
+  // can't know if the destination might be an early clobber, we just need to
+  // pick an operand and adjust placement later if we see any conflicts.
+  //
+  // Early clobber seems like a much less common constraint, but it also seems
+  // that tied operands are most likely to tie the first source operand to the
+  // destination.  So if we have two or more source operands in our list, put
+  // the constraint on the last source operand.  That way the destination can be
+  // tied and early clobber and we won't have to adjust anything.  If we only
+  // have one source operand and one destination operand, put the constraint on
+  // the destination on the theory that early clobber is less common than tied.
+
+  SmallVector<ConstraintArg, 8> Operands;
+
+  std::transform(NewConstraint.begin(), NewConstraint.end(),
+                 std::back_inserter(Operands),
+                 [&Ops] (unsigned Op) {
+                   return ConstraintArg("", Ops.getSubOperandNumber(Op));
+                 });
+
+  // Sort so that destinations will appear first.
+  std::sort(Operands.begin(), Operands.end());
+
+  int ConstraintOpNum = -1;
+
+  // As a first stab, try to place the constraint on the highest-numbered source
+  // operand first.  This is less likely to conflict with early clobber and tied
+  // constraints.
+  for (int i = Operands.size() - 1; i >= 0; --i) {
+    const ConstraintArg &OpToCheck = Operands[i];
+    if (Ops[OpToCheck.OpNum].Constraints[OpToCheck.SubOpNum].isNone()) {
+      ConstraintOpNum = i;
+      break;
+    }
+  }
+
+  if (ConstraintOpNum > 0 && Operands.size() == 2 &&
+      Operands[0].OpNum < Ops.NumDefs) {
+    // We have two operands, a source and a destination.  Prefer placement on
+    // the destination if possible, because early clobber is less common than
+    // tied.
+    const ConstraintArg &DstArg = Operands[0];
+
+    if (Ops[DstArg.OpNum].Constraints[DstArg.SubOpNum].isNone())
+      ConstraintOpNum = 0;
+  }
+
+  if (ConstraintOpNum < 0)
+    // We have no place to put the constraint.
+    return false;
+
+  const ConstraintArg &OpToConstrain = Operands[ConstraintOpNum];
+
+  Ops[OpToConstrain.OpNum].Constraints[OpToConstrain.SubOpNum] =
+      std::move(NewConstraint);
+
+  return true;
+}
+
+// Attempt to place the given constraint on the given operand.  Move any
+// existing constraints if necessary and possible.  Return true on success,
+// false otherwise.
+static bool
+TryToPlaceConstraint(CGIOperandList::ConstraintInfo NewConstraint,
+                     const std::pair<unsigned, unsigned> &Op,
+                     CGIOperandList &Ops) {
+  if (NewConstraint.isNotAllSame())
+    return TryToPlaceNotAllSameConstraint(NewConstraint, Ops);
+
+  CGIOperandList::ConstraintInfo &ExistingConstraint =
+      Ops[Op.first].Constraints[Op.second];
+
+  if (!ExistingConstraint.isNone() && !ExistingConstraint.isNotAllSame())
+    // We can't move this constraint.
+    return false;
+
+  // Avoid a copy if we don't need it.
+  using OptionalConstraint = Optional<CGIOperandList::ConstraintInfo>;
+
+  OptionalConstraint NotAllSameConstraint(
+      ExistingConstraint.isNotAllSame() ?
+      OptionalConstraint(ExistingConstraint) : OptionalConstraint());
+
+  Ops[Op.first].Constraints[Op.second] = std::move(NewConstraint);
+
+  if (NotAllSameConstraint.hasValue())
+    // Find a new place for the not_all_same constraint that we just removed.
+    if (!TryToPlaceNotAllSameConstraint(*NotAllSameConstraint, Ops))
+      return false;
+
+  return true;
+}
+
+static void ParseFuncLikeConstraint(const std::string &ConstraintStr,
+                                    CGIOperandList &Ops,
+                                    Record *Rec) {
+  std::string::size_type LParen = ConstraintStr.find_first_of("(");
+  if (LParen == std::string::npos) {
+    PrintFatalError(
+        Rec->getLoc(), "Missing opening '(' in '" +
+        Rec->getName() + "': '" + ConstraintStr + "'");
+  }
+
+  const char *Whitespace = " \t";
+  const char *ArgOpener = "( \t";
+
+  std::string Name(ConstraintStr.substr(0, LParen));
+
+  std::string::size_type ArgStart = ConstraintStr.find_first_not_of(ArgOpener, LParen);
+  std::string::size_type RParen = ConstraintStr.find_first_of(")", ArgStart);
+  if (RParen == std::string::npos) {
+    PrintFatalError(
+        Rec->getLoc(), "Missing closing ')' in '" +
+        Rec->getName() + "': '" + ConstraintStr + "'");
+  }
+  std::string::size_type ArgEnd = ConstraintStr.find_last_not_of(Whitespace, RParen);
+
+  std::string Args(ConstraintStr.substr(ArgStart, ArgEnd - ArgStart));
+
+  SmallVector<ConstraintArg, 8> Operands =
+      ParseConstraintOperands(Args, Ops, Rec);
+
+  if (Name == "not_all_same") {
+    // not_all_same(op1, op2, ...)
+    //
+    // Requirement: At least one of the operands must be assigned a register
+    // different from that of some other operand.  There is no need to have an
+    // operand register completely unique from all the others.  It is ok, for
+    // example, to assign a four-operand instruction like this:
+    //
+    // A = op(A, B, B)
+
+    // If we only have a single source or single destination operand listed,
+    // then why are we using this constraint in the first place?
+    if (Operands.size() < 2) {
+      PrintFatalError(
+          Rec->getLoc(), "Single not_all_same operand in '" +
+          Rec->getName() + "': '" + ConstraintStr + "'");
+    }
+
+    SmallVector<CGIOperandList::ConstraintInfo::Operand, 8> ConstraintOps;
+
+    std::transform(Operands.begin(), Operands.end(),
+                   std::back_inserter(ConstraintOps),
+                   [&Ops] (const ConstraintArg &Op) {
+                     return Ops.getFlattenedOperandNumber(std::make_pair(
+                                                              Op.OpNum,
+                                                              Op.SubOpNum));
+                   });
+
+
+    // Due to MC representation limitations, we can only have four operands
+    // participate in this constraint and they must be operands 0-3.  See
+    // MCOperandInfo::Constraints.
+    for (unsigned i = 0; i < ConstraintOps.size(); ++i) {
+      if (ConstraintOps[i] > 3) {
+        PrintFatalError(
+            Rec->getLoc(), "not_all_same operand '" + Operands[i].Name +
+            "' [Num = " + utostr(i) + "] out of bounds in '" +
+            Rec->getName() + "': '" + ConstraintStr + "'");
+      }
+    }
+
+    if (!TryToPlaceNotAllSameConstraint(
+            CGIOperandList::ConstraintInfo::getNotAllSame(ConstraintOps),
+            Ops)) {
+      PrintFatalError(
+          Rec->getLoc(), "Constraint conflict for not_all_same operand in '" +
+          Rec->getName() + "': '" + ConstraintStr + "'");
+    }
+    return;
+  }
+
+  PrintFatalError(
+      Rec->getLoc(), "Unrecognized constraint '" + ConstraintStr +
+      "' in '" + Rec->getName() + "'");
+}
+
 static void ParseConstraint(const std::string &CStr, CGIOperandList &Ops,
                             Record *Rec) {
+  std::string::size_type LParen = CStr.find_first_of("(");
+  if (LParen != std::string::npos) {
+    ParseFuncLikeConstraint(CStr, Ops, Rec);
+    return;
+  }
+
   // EARLY_CLOBBER: @early $reg
   std::string::size_type wpos = CStr.find_first_of(" \t");
   std::string::size_type start = CStr.find_first_not_of(" \t");
   std::string Tok = CStr.substr(start, wpos - start);
   if (Tok == "@earlyclobber") {
     std::string Name = CStr.substr(wpos+1);
     wpos = Name.find_first_not_of(" \t");
     if (wpos == std::string::npos)
       PrintFatalError(
         Rec->getLoc(), "Illegal format for @earlyclobber constraint in '" +
         Rec->getName() + "': '" + CStr + "'");
     Name = Name.substr(wpos);
     std::pair<unsigned,unsigned> Op = Ops.ParseOperandName(Name, false);
 
-    // Build the string for the operand
-    if (!Ops[Op.first].Constraints[Op.second].isNone())
+    if (!TryToPlaceConstraint(CGIOperandList::ConstraintInfo::getEarlyClobber(),
+                              Op, Ops))
       PrintFatalError(
           Rec->getLoc(), "Operand '" + Name + "' of '" + Rec->getName() +
           "' cannot have multiple constraints!");
-    Ops[Op.first].Constraints[Op.second] =
-    CGIOperandList::ConstraintInfo::getEarlyClobber();
+
     return;
   }
 
   // Only other constraint is "TIED_TO" for now.
   std::string::size_type pos = CStr.find_first_of('=');
   if (pos == std::string::npos)
     PrintFatalError(
       Rec->getLoc(), "Unrecognized constraint '" + CStr +
if (DestOp.first >= Ops.NumDefs)
     PrintFatalError(
       Rec->getLoc(), "Input operands '" + LHSOpName + "' and '" + RHSOpName +
       "' of '" + Rec->getName() + "' cannot be tied!");
   if (SrcOp.first < Ops.NumDefs)
     PrintFatalError(
       Rec->getLoc(), "Output operands '" + LHSOpName + "' and '" + RHSOpName +
       "' of '" + Rec->getName() + "' cannot be tied!");
 
-  // The constraint has to go on the operand with higher index, i.e.
-  // the source one. Check there isn't another constraint there
-  // already.
-  if (!Ops[SrcOp.first].Constraints[SrcOp.second].isNone())
-    PrintFatalError(
-      Rec->getLoc(), "Operand '" + SrcOpName + "' of '" + Rec->getName() +
-      "' cannot have multiple constraints!");
-
   unsigned DestFlatOpNo = Ops.getFlattenedOperandNumber(DestOp);
   auto NewConstraint = CGIOperandList::ConstraintInfo::getTied(DestFlatOpNo);
 
   // Check that the earlier operand is not the target of another tie
   // before making it the target of this one.
   for (const CGIOperandList::OperandInfo &Op : Ops) {
     for (unsigned i = 0; i < Op.MINumOperands; i++)
       if (Op.Constraints[i] == NewConstraint)
         PrintFatalError(
           Rec->getLoc(), "Operand '" + DestOpName + "' of '" + Rec->getName() +
           "' cannot have multiple operands tied to it!");
   }
 
-  Ops[SrcOp.first].Constraints[SrcOp.second] = NewConstraint;
+  // The constraint has to go on the operand with higher index, i.e.
+  // the source one. Check there isn't another constraint there
+  // already.
+  if (!TryToPlaceConstraint(NewConstraint, SrcOp, Ops))
+    PrintFatalError(
+      Rec->getLoc(), "Operand '" + SrcOpName + "' of '" + Rec->getName() +
+      "' cannot have multiple constraints!");
 }
 
 static void ParseConstraints(const std::string &CStr, CGIOperandList &Ops,
                              Record *Rec) {
   if (CStr.empty()) return;
 
   const std::string delims(",");
+  const std::string ws(" \t");
   std::string::size_type bidx, eidx;
 
-  bidx = CStr.find_first_not_of(delims);
+  bidx = CStr.find_first_not_of(delims + ws);
   while (bidx != std::string::npos) {
-    eidx = CStr.find_first_of(delims, bidx);
+    std::string::size_type delim_search_start_idx = bidx;
+
+    // Skip paren pairs.  Note that this DOES NOT handle nested parens.
+    std::string::size_type delim = CStr.find_first_of(delims,
+                                                      delim_search_start_idx);
+    std::string::size_type lparen = CStr.find_first_of("(", bidx);
+
+    if (lparen != std::string::npos &&
+        (delim == std::string::npos || lparen < delim)) {
+      // Parenthesis comes first, parse the whole function-like constraint.
+      std::string::size_type rparen = CStr.find_first_of(")", lparen);
+      if (rparen == std::string::npos) {
+        PrintFatalError(
+        Rec->getLoc(), "Missing closing ')' in '" +
+        Rec->getName() + "': '" + CStr + "'");
+      }
+      // Don't look for a delimiter until after the right parenthesis.
+      delim_search_start_idx = rparen;
+    }
+
+    eidx = CStr.find_first_of(delims, delim_search_start_idx);
     if (eidx == std::string::npos)
       eidx = CStr.length();
 
     ParseConstraint(CStr.substr(bidx, eidx - bidx), Ops, Rec);
-    bidx = CStr.find_first_not_of(delims, eidx);
+    bidx = CStr.find_first_not_of(delims + ws, eidx);
   }
 }
 
 void CGIOperandList::ProcessDisableEncoding(std::string DisableEncoding) {
   while (1) {
     std::pair<StringRef, StringRef> P = getToken(DisableEncoding, " ,\t");
     std::string OpName = std::string(P.first);
     DisableEncoding = std::string(P.second);

llvm/utils/TableGen/InstrInfoEmitter.cpp

for (unsigned j = 0, e = OperandList.size(); j != e; ++j) {
       Res += ", ";
 
       const CGIOperandList::ConstraintInfo &Constraint =
         Op.Constraints[j];
       if (Constraint.isNone())
         Res += "0";
       else if (Constraint.isEarlyClobber())
         Res += "MCOI_EARLY_CLOBBER";
-      else {
+      else if (Constraint.isNotAllSame()) {
+        // We have four bits to work with.  Consider the four bits to represent
+        // a set of operands, where a 1 bit means that operand participates in
+        // the constraint.  This means we are limited to representing a total of
+        // four operands.  An instruction could have more than four operands but
+        // only the operands numbered 0-3 can participate in this constraint.
+        unsigned Bitset = 0;
+        for (CGIOperandList::ConstraintInfo::Operand Op : Constraint) {
+          assert(Op < 4 && "Constraint operand overflow");
+          Bitset |= (1 << Op);
+        }
+
+        Res += "MCOI_NOT_ALL_SAME(0x" + utohexstr(Bitset) + ")";
+      } else {
         assert(Constraint.isTied());
         Res += "MCOI_TIED_TO(" + utostr(Constraint.getTiedOperand()) + ")";
       }
 
       Result.push_back(Res);
     }
   }