[tblgen] Allow FixedLenDecoderEmitter to use APInt-like objects as InsnType

[dsanders]

Summary

Some targets have very long encodings and uint64_t isn't sufficient. uint128_t
isn't portable so such targets need to use an object instead.

There is one catch with this at the moment, no string of bits extracted
from the encoding may exceeed 64-bits. Fields are still permitted to
exceed 64-bits so long as they aren't one contiguous string of bits. If
this proves to be a problem then we can modify the generation of
fieldFromInstruction() calls to account for it but for now I've added an
assertion for this.

InsnType must either be integral or an APInt-like object that must:

• Have a static const max_size_in_bits equal to the number of bits in the encoding.
• be default-constructible and copy-constructible
• be constructible from a uint64_t (this is the key area the interface deviates from APInt since this constructor does not take the bit width)
• be constructible from an APInt (this can be private)
• be convertible to uint64_t
• Support the ~, &,, ==, !=, and |= operators with other objects of the same type
• Support shift (<<, >>) with signed and unsigned integers on the RHS
• Support put (<<) to raw_ostream&

[dsanders]

Correct a silly mistake in fieldFromInstruction(). The bit of code that
actually built the mask in the APInt-like case was missing.

[dsanders]

Add requirement for == and !=.
Add requirement for conversion to uint64_t. I'd like to remove this one again but it's currently necessary for field extraction
Remove conversion to bool. This proved to be very dangerous as it happily casts to any integral type via bool, silently truncating data.

[dsanders]

ping

[dsanders]

ping

[dsanders]

ping

[nhaehnle]

utils/TableGen/FixedLenDecoderEmitter.cpp

2118–2122

This assertion seems to defeat the point of the change?

[dsanders]

utils/TableGen/FixedLenDecoderEmitter.cpp

2118–2122

This assertion is what I was referring to in the summary with 'There is one catch with this at the moment, no string of bits extracted from the encoding may exceed 64-bits'. The assertion is there to catch the case where the generated matcher table falls foul of some remaining implicit casts to uint64_t that I haven't managed to eliminate yet but probably don't need to because it's very rare that ISA's that needed the space afforded by large encodings will hit it.

Suppose you have an ISA with a single instruction:

def A : Instruction { let Inst{0-127} = 0; }

That will currently fail to work, because the generated matcher will extract 128 bits in a single command:

if Inst[0-127] == 0: # We don't support this extraction
  Instruction is A

This will also fail for the same reason:

def A : Instruction { let Inst{0-127} = 0; }
def B : Instruction { let Inst{0-62} = 0; let Inst{63} = 1; let Inst{64-127} = 0; }

because it's still a 128-bit literal being checked:

if Inst[0-127] == 0: # We don't support this extraction
  Instruction is A
if Inst[0-127] == 0b000....010.....000: # We don't support this extraction
  Instruction is B

However, this ISA:

def A : Instruction { let Inst{0-127} = 0; }
def B : Instruction {
  bits<32> Imm;
  let Inst{0-62} = Imm;
  let Inst{63} = 1;
  let Inst{64-127} = 0;
}

will succeed since the generated matcher will only generate extractions of 64-bits or less:

if Inst[63] == 0:
  if Inst[0-62] == 0 and Inst[64-127] == 0:
    Instruction is A
else:
  if Inst[64-127] == 0:
    Instruction is B
    Imm is Inst[0-63]

To summarize, targets should only hit this assertion if they haven't implemented enough of their ISA to justify the length of the encodings. In the case of the out of tree target I'm working on, it was only a problem when nop's were the only thing implemented. As soon as I implemented an add instruction the matcher was complicated enough to not hit this corner case.

[nhaehnle]

Apart from the issue with the assertion, this change looks good to me.

utils/TableGen/FixedLenDecoderEmitter.cpp

2118–2122

Extracting Inst[64-127] will use startBit == 64, numBits == 64, right? So that will fail the assertion.

[dsanders]

Rebase. I think the incorrect assertion is a missing patch from my original patch series. The tip of my local repo only has that assertion in the integral case

[dsanders]

Fold in a correction that ended up in a downstream-specific patch. The 64-bit assertion should only be in the path for integer types

[dsanders]

Thanks

utils/TableGen/FixedLenDecoderEmitter.cpp

2118–2122

You're absolutely right. It turns out I missed the patch where I moved it to the integer only case as it ended up part of a patch that isn't upstreamable.

[Sonicadvance1]

This commit breaks my 128bit instruction target.
I'm currently using a workaround locally for enabling APInt based encodings when your instruction encoding is >64bit.
The main issue with this approach is that getBinaryCodeForInstr completely falls apart.

I have this reverted on my local target, I recommend the same upstream until this is fully baked.

[dsanders]

In D52100#1277769, @Sonicadvance1 wrote:

This commit breaks my 128bit instruction target.
I'm currently using a workaround locally for enabling APInt based encodings when your instruction encoding is >64bit.
The main issue with this approach is that getBinaryCodeForInstr completely falls apart.

Could you elaborate on this? getBinaryCodeForInstr() is for encoding instructions whereas FixedLenDecoderEmitter generates a decoder so I'm surprised that you're seeing a connection between getBinaryCodeForInstr() and this patch. Our out-of-tree target didn't use the FixedLenDecoderEmitter until after this patch made it possible but we've been using getBinaryCodeForInstr() for a very long time so I think there's unlikely to be a connection between the two. Additionally, not affecting encoding was a requirement for us as we're also working around the lack of >64-bit support in getBinaryCodeForInstr()

[Sonicadvance1]

In D52100#1277817, @dsanders wrote:

In D52100#1277769, @Sonicadvance1 wrote:

This commit breaks my 128bit instruction target.
I'm currently using a workaround locally for enabling APInt based encodings when your instruction encoding is >64bit.
The main issue with this approach is that getBinaryCodeForInstr completely falls apart.

Could you elaborate on this? getBinaryCodeForInstr() is for encoding instructions whereas FixedLenDecoderEmitter generates a decoder so I'm surprised that you're seeing a connection between getBinaryCodeForInstr() and this patch. Our out-of-tree target didn't use the FixedLenDecoderEmitter until after this patch made it possible but we've been using getBinaryCodeForInstr() for a very long time so I think there's unlikely to be a connection between the two. Additionally, not affecting encoding was a requirement for us as we're also working around the lack of >64-bit support in getBinaryCodeForInstr()

I can only assume you aren't using a disassembler in your backend currently? That also breaks immediately.
Any form of reasonably mature backend is going to hit issues due to this being half baked at the moment.
I was using the getBinaryCodeForInstr function as an example of missing features that this misses but there are definitely more than what I've stated.
Sadly my backend is out of tree so I can't complain too much.

[dsanders]

In D52100#1277915, @Sonicadvance1 wrote:

In D52100#1277817, @dsanders wrote:

In D52100#1277769, @Sonicadvance1 wrote:

This commit breaks my 128bit instruction target.
I'm currently using a workaround locally for enabling APInt based encodings when your instruction encoding is >64bit.
The main issue with this approach is that getBinaryCodeForInstr completely falls apart.

Could you elaborate on this? getBinaryCodeForInstr() is for encoding instructions whereas FixedLenDecoderEmitter generates a decoder so I'm surprised that you're seeing a connection between getBinaryCodeForInstr() and this patch. Our out-of-tree target didn't use the FixedLenDecoderEmitter until after this patch made it possible but we've been using getBinaryCodeForInstr() for a very long time so I think there's unlikely to be a connection between the two. Additionally, not affecting encoding was a requirement for us as we're also working around the lack of >64-bit support in getBinaryCodeForInstr()

I can only assume you aren't using a disassembler in your backend currently? That also breaks immediately.

Before this patch, there was no means to have a disassembler that used FixedLenDecoderEmitter to support >64-bit instructions. With this patch, we've been able to bring up a working and tested disassembler very quickly. We're still a long way from supporting 100% of our ISA but we're making progress very quickly and our experience is far from "breaks immediately". Our biggest problem is conflicting encodings in our tablegen definitions and we find instructions usually work once those decoder conflicts are resolved. The next biggest is that disassemblers with a lot of variety can be a bit slow to compile due to the number of allocas the APInt objects create (part of this is DCE being >=quadratic on number of allocas and exit blocks). To be clear, I fully expect that a mature target trying to make use of a new feature may hit issues that our target hasn't. That's unfortunately par for the course for targets making use of new features, especially when the target concerned is out of tree like both of ours.

Going back to the issue you're encountering: What do you mean by "breaks immediately"? I'd like to help you resolve the problem you're encountering but I need more than "it's broken" to go on. Does it crash? Pick the wrong opcode? Produce the wrong MCInst operands? or something else?

Any form of reasonably mature backend is going to hit issues due to this being half baked at the moment.
I was using the getBinaryCodeForInstr function as an example of missing features

getBinaryCodeForInstr() is a conscious omission as I'm trying to get >64-bit instructions working for the MCDisassembler layer and getBinaryCodeForInstr() is not part of that layer (it's in the MC layer). We generally develop things incrementally in LLVM rather than try to deliver everything at once in one large patch. Among other reasons (which can be found at https://llvm.org/docs/DeveloperPolicy.html#incremental-development), this makes code review easier and also allows the community more opportunity to shape the overall direction and consider the viewpoints of the relevant targets to produce a better feature than would otherwise be possible.

In this case, the high-level increments are:

1. Make it possible to support >64-bit in the MCDisassembler layer
2. (out-of-tree) Use that support to implement a disassembler that requires it
3. Make it possible to support >64-bit in the MCCodeEmitter and related layers
4. (out-of-tree) Replace our various hacks with a proper implementation based on that support

Our target doesn't have an urgent need to do 3 and 4 yet (because we have out-of-tree workarounds) but we do want to resolve that too as soon as we can as it would improve the quality and reduce the maintenance requirements of our compiler.

that this misses but there are definitely more than what I've stated.

If you are aware of any affecting the MCDisassembler layer (aside from the known issue of >64-bit fields) then I'd appreciate more information on this. It's entirely possible that there are things I haven't thought about or encountered yet

Sadly my backend is out of tree so I can't complain too much.

I understand the difficulty here as our backend is also out-of-tree and we too occasionally have issues with upstream changes and find it difficult to share details when we need upstreams help to resolve it. We usually end up reproducing the issue using toy examples and an in-tree target to enable us to discuss it.

[dsanders]

I've been thinking about this over the weekend and I think I may be able to hazard a guess: Are you trying to use APInt directly? Or use APInt-like object that meets all the requirements in the emitted comment? (see emitFieldFromInstruction)

The reason I ask is that while the expected interface generally a subset of APInt, there's a few requirements that APInt itself doesn't meet. Specifically:

1. Have a static const max_size_in_bits equal to the number of bits in the encoding.
2. be constructible from a uint64_t
3. be convertible to uint64_t

From that list 1. is to support the sanity checking asserts that ensure we don't extract more bits than we have. 2. is primarily to support the 'tmp = 0' in the generated which could be fixed if we require targets to declare their need for the APInt-like up front so we can change the code emitted for that (it's necessary for the integral case). 3. was primarily to pass it in MCOperand::CreateImm() but looking at it again, there's probably a bug lurking there as one of the messages in the flood of CreateImm-related errors involves the SoftFail checks which use decodeULEB128 which return uint64_t.

[Sonicadvance1]

I'm using APInt directly yes.
Which is then handling a fixed length size of 128bit instructions

utils/TableGen/FixedLenDecoderEmitter.cpp

 }
 
 // emitFieldFromInstruction - Emit the templated helper function
 // fieldFromInstruction().
 // On Windows we make sure that this function is not inlined when
 // using the VS compiler. It has a bug which causes the function
 // to be optimized out in some circustances. See llvm.org/pr38292
 static void emitFieldFromInstruction(formatted_raw_ostream &OS) {
-  OS << "// Helper function for extracting fields from encoded instructions.\n"
+  OS << "// Helper functions for extracting fields from encoded instructions.\n"
+     << "// InsnType must either be integral or an APInt-like object that "
+        "must:\n"
+     << "// * Have a static const max_size_in_bits equal to the number of bits "
+        "in the\n"
+     << "//   encoding.\n"
+     << "// * be default-constructible and copy-constructible\n"
+     << "// * be constructible from a uint64_t\n"
+     << "// * be constructible from an APInt (this can be private)\n"
+     << "// * Support getBitsSet(loBit, hiBit)\n"
+     << "// * be convertible to bool\n"
+     << "// * Support the ~, &, and |= operators with other objects of the "
+        "same type\n"
+     << "// * Support shift (<<, >>) with signed and unsigned integers on the "
+        "RHS\n"
+     << "// * Support put (<<) to raw_ostream&\n"
      << "template<typename InsnType>\n"
      << "#if defined(_MSC_VER) && !defined(__clang__)\n"
      << "__declspec(noinline)\n"
      << "#endif\n"
      << "static InsnType fieldFromInstruction(InsnType insn, unsigned startBit,\n"
-     << "                                     unsigned numBits) {\n"
-     << "    assert(startBit + numBits <= (sizeof(InsnType)*8) &&\n"
-     << "           \"Instruction field out of bounds!\");\n"
-     << "    InsnType fieldMask;\n"
-     << "    if (numBits == sizeof(InsnType)*8)\n"
-     << "      fieldMask = (InsnType)(-1LL);\n"
-     << "    else\n"
-     << "      fieldMask = (((InsnType)1 << numBits) - 1) << startBit;\n"
-     << "    return (insn & fieldMask) >> startBit;\n"
+     << "                                     unsigned numBits, "
+        "std::true_type) {\n"
+     << "  assert(startBit + numBits <= (sizeof(InsnType) * 8) &&\n"
+     << "         \"Instruction field out of bounds!\");\n"
+     << "  InsnType fieldMask;\n"
+     << "  if (numBits == sizeof(InsnType) * 8)\n"
+     << "    fieldMask = (InsnType)(-1LL);\n"
+     << "  else\n"
+     << "    fieldMask = (((InsnType)1 << numBits) - 1) << startBit;\n"
+     << "  return (insn & fieldMask) >> startBit;\n"
+     << "}\n"
+     << "\n"
+     << "template<typename InsnType>\n"
+     << "static InsnType fieldFromInstruction(InsnType insn, unsigned "
+        "startBit,\n"
+     << "                                     unsigned numBits, "
+        "std::false_type) {\n"
+     << "  assert(startBit + numBits <= InsnType::max_size_in_bits && "
+        "\"Instruction field out of bounds!\");\n"
+     << "  InsnType fieldMask = InsnType::getBitsSet(0, numBits);\n"
+     << "  return (insn >> startBit) & fieldMask;\n"
+     << "}\n"
+     << "\n"
+     << "template<typename InsnType>\n"
+     << "static InsnType fieldFromInstruction(InsnType insn, unsigned "
+        "startBit,\n"
+     << "                                     unsigned numBits) {\n"
+     << "  assert(startBit + numBits <= 64 && \"Cannot support >64-bit "
+        "extractions!\");\n"
+     << "  return fieldFromInstruction(insn, startBit, numBits, "
+        "std::is_integral<InsnType>());\n"
      << "}\n\n";
 }
 
 // emitDecodeInstruction - Emit the templated helper function
 // decodeInstruction().
 static void emitDecodeInstruction(formatted_raw_ostream &OS) {
   OS << "template<typename InsnType>\n"
      << "static DecodeStatus decodeInstruction(const uint8_t DecodeTable[], "
         "MCInst &MI,\n"