[AArch64] Fix problems in handling generic MSR/MRS instructions

[petpav01]

Summary

Decoding to MSRpstate should occur only if <op1><op2> represents a valid <pstatefield>, else the instruction should be decoded to a generic MSR.

[petpav01]

Any feedback on this patch? I realize it is an ugly one but I would appreciate any hints how it could be done in a cleaner way.

Thanks,
Petr Pavlu

[rengolin]

Adding Tim and James to review the patch.

lib/Target/AArch64/Disassembler/AArch64Disassembler.cpp

1506 ↗

(On Diff #18747)

This seems like a gross exaggeration. Is it possible that the name would come invalid for any other reason?

[petpav01]

Thank you Renato for having a look at this patch.

lib/Target/AArch64/Disassembler/AArch64Disassembler.cpp

1506 ↗

(On Diff #18747)

I am not sure if I am really answering your question but DecodeSystemPStateInstruction() is called only for MSRpstate and this instruction aliases with an extended MSR format (introduced in r218753). All cases not allowed by MSRpstate are valid MSR cases.

Some more background on this code:

MC instruction MSRpstate is defined to have:

Inst{31-19} = 0b1101010100000;
Inst{18-16} = pstatefield{5-3};
Inst{15-12} = 0b0100;
Inst{11-8} = imm;
Inst{7-5} = pstatefield{2-0};
Inst{4-0} = 0b11111

A problem here is that there does not seem to be a good way how to specify that only a subset of pstatefield is allowed.

Disassembling a bitpattern that should be handled as an extended MSR (but which aliases MSRpstate):

$ echo "0x1f 0x40 0x00 0xd5" | ./llvm-mc -triple=aarch64 -show-inst -show-encoding -disassemble -debug
Args: ./llvm-mc -triple=aarch64 -show-inst -show-encoding -disassemble -debug 
        .text
0: OPC_ExtractField(26, 3): 5
3: OPC_FilterValue(2, 1110): FAIL: continuing at 1117
1117: OPC_FilterValue(3, 28396): FAIL: continuing at 29517
29517: OPC_FilterValue(4, 447): FAIL: continuing at 29968
29968: OPC_FilterValue(5, 474): PASS: continuing at 29972
29972: OPC_ExtractField(29, 3): 6
29975: OPC_FilterValue(0, 4): FAIL: continuing at 29983
29983: OPC_FilterValue(1, 39): FAIL: continuing at 30026
30026: OPC_FilterValue(2, 17): FAIL: continuing at 30047
30047: OPC_FilterValue(4, 4): FAIL: continuing at 30055
30055: OPC_FilterValue(5, 39): FAIL: continuing at 30098
30098: OPC_FilterValue(6, 10539): PASS: continuing at 30102
30102: OPC_ExtractField(21, 5): 8
30105: OPC_FilterValue(0, 30): FAIL: continuing at 30139
30139: OPC_FilterValue(1, 10): FAIL: continuing at 30153
30153: OPC_FilterValue(2, 11): FAIL: continuing at 30168
30168: OPC_FilterValue(5, 30): FAIL: continuing at 30202
30202: OPC_FilterValue(8, 122): PASS: continuing at 30206
30206: OPC_ExtractField(0, 8): 31
30209: OPC_FilterValue(95, 11): FAIL: continuing at 30224
30224: OPC_FilterValue(159, 11): FAIL: continuing at 30240
30240: OPC_FilterValue(191, 11): FAIL: continuing at 30256
30256: OPC_FilterValue(223, 11): FAIL: continuing at 30272
30272: OPC_ExtractField(0, 5): 31
30275: OPC_FilterValue(31, 33): PASS: continuing at 30279
30279: OPC_ExtractField(12, 4): 4
30282: OPC_FilterValue(2, 11): FAIL: continuing at 30297
30297: OPC_FilterValue(4, 11): PASS: continuing at 30301
30301: OPC_CheckField(19, 1, 0, 5): FieldValue = 0, ExpectedValue = 0: PASS
30307: OPC_Decode: opcode 1124, using decoder 216
----- DECODE SUCCESSFUL -----
<stdin>:1:1: warning: invalid instruction encoding
0x1f 0x40 0x00 0xd5
^

My understanding of the generated disassembler is that it works in two phases. In the first phase (before "DECODE SUCCESSFUL") the disassembler matches all constant bits and determines an MC opcode. In the second phase it calls a decode method specific to the determined opcode. In this case it calls explicit decode method DecodeSystemPStateInstruction(), it sees that pstatefield is not one of SPSel, DAIFSet, DAIFClr and rejects the instruction. No programmatic limitation on field values (without changing the resulting opcode) in the first phase, or a jump from the second phase back to the first one to handle the instruction as an extended MSR (after it is rejected as MSRpstate) seems possible.

I also considered an option to instantiate only the allowed MSR (immed) instructions (e.g. to have MSRpstateSPSel, MSRpstateDAIFSet, MSRpstateDAIFClr) but that does not look right because it creates a new MC opcode for each allowed pstatefield value.

A similar problem exists in the ARM backend where the preload hints fit into holes in the encodings of the LDRH/STRH instructions. It seems to be handled similarly in the instruction decode method.

[rengolin]

@t.p.northover, @jmolloy, please have a look. I'm probably being overzealous, but I'd rather be safe than sorry.

lib/Target/AArch64/Disassembler/AArch64Disassembler.cpp

1506 ↗

(On Diff #18747)

I understand why it's safe to do that in your case, but I worry that there would be other cases where an invalid name won't match in your pattern. What I'm saying is that I'd like to see a way of that function return Invalid for all the cases where it IS invalid, even with your extension.

I don't know all the variations that function can cope with, but I'd be surprised if all validation on all fields was made before entering this function. You may get it right on your examples, but that doesn't mean there are other examples where that would get it wrong.

Basically, you need an active selection to make a conscious choice of acceptance and reject the unknown, instead of blindly convert whatever comes into an MSR, even if it was an MSR to begin with, it could have wrong operand values, etc.

Tim and James may have a better idea of how to do that.

[petpav01]

Updated patch adds a check that the instruction coming in DecodeSystemPStateInstruction() is really MSR (immediate) (MSRpstate in LLVM), which means it can be interpreted as the extended MSR if pstatefield is not allocated. I think it would be a logical error if the method was called for non-MSR (immediate) instructions so the code asserts this condition (instead of returning Fail).

The patch also simplifies adding of the general register operand, it is always XZR.

[jmolloy]

lib/Target/AArch64/Disassembler/AArch64Disassembler.cpp

1506 ↗

(On Diff #18747)

Hi Petr,

Renato, thanks for pointing me at this. Sorry it took so long.

I think this approach is fundamentally flawed, and isn't good enough as a workaround for tablegen. It assumes that this is the last operand to be decoded (implicit decoding order which the FixedLenDecoderEmitter doesn't provide), and it mutates already-decoded parts under the disassembler's feet. It's a hack, pure and simple.

I think the only reasonable way to do this is to enhance TableGen with your feature. I don't think it'll be horrendously hard, but it's something that needs to be done to avoid hacks in a nice clean backend.

Sorry.

James

[petpav01]

Hi James,

Thank you for the review. The rewrite happens in a DecoderMethod of the MSRpstate instrution, not in a DecoderMethod of an operand, so there should be no assumption it is the last operand to be decoded.

However, thanks for confirming there is currently not a good way how to implement this cleanly without modifying TableGen parts. I will have a look what could be done to support this case but it will probably take me some time to get to it.

Petr

[petpav01]

Improve decoding options for non-orthogonal instructions

When FixedLenDecoder matches an input bitpattern of form [01]+ with an
instruction bitpattern of form [01?]+ (where 0/1 are static bits and ? are
mixed/variable bits) it passes the input bitpattern to a specific instruction
decoder method which then makes a final decision whether the bitpattern is a
valid instruction or not. This means the decoder must handle all possible
values of the variable bits which sometimes leads to opcode rewrites in the
decoder method when the instructions are not fully orthogonal.

The patch provides a way for the decoder method to say that when it returns
Fail it does not necessarily mean the bitpattern is invalid, but rather that
the bitpattern is definitely not an instruction that is recognized by the
decoder method. The decoder can then try to match the input bitpattern with
other possible instruction bitpatterns.

This allows to solve a situation on AArch64 where the MSR (immediate)
instruction has form:
1101 0101 0000 0??? 0100 ???? ???1 1111
but not all values of the ? bits are allowed. The rejected values should be
handled by the extended MSR (register) instruction:
1101 0101 000? ???? ???? ???? ???? ????

The decoder will first try to decode an input bitpattern that matches both
bitpatterns as MSR (immediate) but currently this puts the decoder method of
MSR (immediate) into a situation when it must be able to decode all possible
values of the ? bits, i.e. it would need to rewrite the instruction to `MSR
(register) when it is not MSR (immediate)`.

The patch allows to specify that the decoder method cannot determine if the
instruction is valid for all variable values. The decoder method can simply
return Fail when it knows it is definitely not MSR (immediate). The decoder
will then backtrack the decoding and find that it can match the input
bitpattern with the more generic MSR (register) bitpattern too.

This behaviour could be enabled for all instruction decoders but new TryDecode
opcode is larger by 2B than the Decode opcode. Using TryDecode for all
instruction on AArch64 increased size of the decoder table from 44kB to
49kB. The expectation is that most encodings are orthogonal so this should be
enabled only in exceptional cases to prevent any slowdown with additional
matching+decoding and size bloat.

[jmolloy]

Hi Petr,

This generally looks good to me. Apart from the nits in the comments below, generally:

• The tablegen+tests changes need to be split from the ARM changes and applied in two separate patches.
• The spelling correction needs to be split out and committed as its own (trivial, needs no code review) patch.

Cheers,

James

utils/TableGen/FixedLenDecoderEmitter.cpp

1084 ↗

(On Diff #29065)

Merge lines 1084 and 1085 together.

1899 ↗

(On Diff #29065)

You can use dyn_cast_or_null here:

BitInit *BI = dyn_cast_or_null<BitInit>(TypeRecord->getValue("hasCompleteDecoder")); 
bool HasCompleteDecoder = BI ? BI->getValue() : true;

1976 ↗

(On Diff #29065)

Same comment as in line 1899.

2179 ↗

(On Diff #29065)

Why change SUCCESSFUL to COMPLETE here?

[petpav01]

Hi James,

Thank you for the review. I will split the changes into three separate patches as you suggested before committing (typo fix, TableGen, AArch64 part).
Other comments are inlined.

Thanks,
Petr

utils/TableGen/FixedLenDecoderEmitter.cpp

1899 ↗

(On Diff #29065)

This would need

BitInit *BI = dyn_cast_or_null<BitInit>(TypeRecord->getValue("hasCompleteDecoder")->getValue());

but TypeRecord->getValue("hasCompleteDecoder") can be nullptr so that cannot be used.

2179 ↗

(On Diff #29065)

I believe the original intention of this message was to give information that the "filter decoding" part in FixedLenDecoder was successful. This is ok but the bitpattern then gets passed by FixedLenDecoder to a specific decoder method, it can reject the bitpattern and so the decoding as a whole fails.

This created a bit confusing output from llvm-mc -disassemble -debug when the input bitpattern was invalid. It would contain 'DECODE SUCCESSFUL' followed by 'invalid instruction encoding':

$ echo "0x1f 0x40 0x00 0xd5" | llvm-mc -triple=aarch64 -show-inst -show-encoding -disassemble -debug
[...]
31211: OPC_CheckField(19, 1, 0, 5): FieldValue = 0, ExpectedValue = 0: PASS
31217: OPC_Decode: opcode 1283, using decoder 220
----- DECODE SUCCESSFUL -----
<stdin>:1:1: warning: invalid instruction encoding
0x1f 0x40 0x00 0xd5
^

The patch changed this to printing 'DECODE COMPLETE' when FixedLenDecoder fully finished the decoding (including running any decoding methods).

However, it might be better to simply remove this message because it does not provide much information (OPC_Decode implies end of decoding similarly to OPC_Fail) and additionally extend the OPC_Decode debug message with a result returned from the decoding method. I will update the patch.

[petpav01]

Updated patch fixes formatting problems and corrects the debugging output.

[jmolloy]

I think this is reasonable. Please go ahead and commit.

llvm/trunk/include/llvm/MC/MCFixedLenDisassembler.h

 // Disassembler state machine opcodes.
 enum DecoderOps {
   OPC_ExtractField = 1, // OPC_ExtractField(uint8_t Start, uint8_t Len)
   OPC_FilterValue,      // OPC_FilterValue(uleb128 Val, uint16_t NumToSkip)
   OPC_CheckField,       // OPC_CheckField(uint8_t Start, uint8_t Len,
                         //                uleb128 Val, uint16_t NumToSkip)
   OPC_CheckPredicate,   // OPC_CheckPredicate(uleb128 PIdx, uint16_t NumToSkip)
   OPC_Decode,           // OPC_Decode(uleb128 Opcode, uleb128 DIdx)
+  OPC_TryDecode,        // OPC_TryDecode(uleb128 Opcode, uleb128 DIdx,
+                        //               uint16_t NumToSkip)
   OPC_SoftFail,         // OPC_SoftFail(uleb128 PMask, uleb128 NMask)
   OPC_Fail              // OPC_Fail()
 };
 
 } // namespace MCDecode
 } // namespace llvm
 
 #endif

llvm/trunk/include/llvm/Target/Target.td

class Instruction {
 
   /// DisableEncoding - List of operand names (e.g. "$op1,$op2") that should not
   /// be encoded into the output machineinstr.
   string DisableEncoding = "";
 
   string PostEncoderMethod = "";
   string DecoderMethod = "";
 
+  // Is the instruction decoder method able to completely determine if the
+  // given instruction is valid or not. If the TableGen definition of the
+  // instruction specifies bitpattern A??B where A and B are static bits, the
+  // hasCompleteDecoder flag says whether the decoder method fully handles the
+  // ?? space, i.e. if it is a final arbiter for the instruction validity.
+  // If not then the decoder attempts to continue decoding when the decoder
+  // method fails.
+  //
+  // This allows to handle situations where the encoding is not fully
+  // orthogonal. Example:
+  // * InstA with bitpattern 0b0000????,
+  // * InstB with bitpattern 0b000000?? but the associated decoder method
+  //   DecodeInstB() returns Fail when ?? is 0b00 or 0b11.
+  //
+  // The decoder tries to decode a bitpattern that matches both InstA and
+  // InstB bitpatterns first as InstB (because it is the most specific
+  // encoding). In the default case (hasCompleteDecoder = 1), when
+  // DecodeInstB() returns Fail the bitpattern gets rejected. By setting
+  // hasCompleteDecoder = 0 in InstB, the decoder is informed that
+  // DecodeInstB() is not able to determine if all possible values of ?? are
+  // valid or not. If DecodeInstB() returns Fail the decoder will attempt to
+  // decode the bitpattern as InstA too.
+  bit hasCompleteDecoder = 1;
+
   /// Target-specific flags. This becomes the TSFlags field in TargetInstrDesc.
   bits<64> TSFlags = 0;
 
   ///@name Assembler Parser Support
   ///@{
 
   string AsmMatchConverter = "";
 

 /// Operand Types - These provide the built-in operand types that may be used
 /// by a target.  Targets can optionally provide their own operand types as
 /// needed, though this should not be needed for RISC targets.
 class Operand<ValueType ty> : DAGOperand {
   ValueType Type = ty;
   string PrintMethod = "printOperand";
   string EncoderMethod = "";
   string DecoderMethod = "";
+  bit hasCompleteDecoder = 1;
   string OperandType = "OPERAND_UNKNOWN";
   dag MIOperandInfo = (ops);
 
   // MCOperandPredicate - Optionally, a code fragment operating on
   // const MCOperand &MCOp, and returning a bool, to indicate if
   // the value of MCOp is valid for the specific subclass of Operand
   code MCOperandPredicate;
 

llvm/trunk/test/TableGen/trydecode-emission.td

+// RUN: llvm-tblgen -gen-disassembler -I %p/../../include %s | FileCheck %s
+
+// Check that if decoding of an instruction fails and the instruction does not
+// have a complete decoder method that can determine if the bitpattern is valid
+// or not then the decoder tries to find a more general instruction that
+// matches the bitpattern too.
+
+include "llvm/Target/Target.td"
+
+def archInstrInfo : InstrInfo { }
+
+def arch : Target {
+  let InstructionSet = archInstrInfo;
+}
+
+class TestInstruction : Instruction {
+  let Size = 1;
+  let OutOperandList = (outs);
+  let InOperandList = (ins);
+  field bits<8> Inst;
+  field bits<8> SoftFail = 0;
+}
+
+def InstA : TestInstruction {
+  let Inst = {0,0,0,0,?,?,?,?};
+  let AsmString = "InstA";
+}
+
+def InstB : TestInstruction {
+  let Inst = {0,0,0,0,0,0,?,?};
+  let AsmString = "InstB";
+  let DecoderMethod = "DecodeInstB";
+  let hasCompleteDecoder = 0;
+}
+
+// CHECK:      /* 0 */       MCD::OPC_ExtractField, 4, 4,  // Inst{7-4} ...
+// CHECK-NEXT: /* 3 */       MCD::OPC_FilterValue, 0, 14, 0, // Skip to: 21
+// CHECK-NEXT: /* 7 */       MCD::OPC_CheckField, 2, 2, 0, 5, 0, // Skip to: 18
+// CHECK-NEXT: /* 13 */      MCD::OPC_TryDecode, 24, 0, 0, 0, // Opcode: InstB, skip to: 18
+// CHECK-NEXT: /* 18 */      MCD::OPC_Decode, 23, 1, // Opcode: InstA
+// CHECK-NEXT: /* 21 */      MCD::OPC_Fail,
+
+// CHECK: if (DecodeInstB(MI, insn, Address, Decoder) == MCDisassembler::Fail) { DecodeComplete = false; return MCDisassembler::Fail; }

llvm/trunk/test/TableGen/trydecode-emission2.td

+// RUN: llvm-tblgen -gen-disassembler -I %p/../../include %s | FileCheck %s
+
+include "llvm/Target/Target.td"
+
+def archInstrInfo : InstrInfo { }
+
+def arch : Target {
+  let InstructionSet = archInstrInfo;
+}
+
+class TestInstruction : Instruction {
+  let Size = 1;
+  let OutOperandList = (outs);
+  let InOperandList = (ins);
+  field bits<8> Inst;
+  field bits<8> SoftFail = 0;
+}
+
+def InstA : TestInstruction {
+  let Inst = {0,0,0,0,0,0,?,?};
+  let AsmString = "InstA";
+  let DecoderMethod = "DecodeInstA";
+  let hasCompleteDecoder = 0;
+}
+
+def InstB : TestInstruction {
+  let Inst = {0,0,0,?,?,0,1,1};
+  let AsmString = "InstB";
+  let DecoderMethod = "DecodeInstB";
+  let hasCompleteDecoder = 0;
+}
+
+// CHECK:      /* 0 */       MCD::OPC_ExtractField, 2, 1,  // Inst{2} ...
+// CHECK-NEXT: /* 3 */       MCD::OPC_FilterValue, 0, 29, 0, // Skip to: 36
+// CHECK-NEXT: /* 7 */       MCD::OPC_ExtractField, 5, 3,  // Inst{7-5} ...
+// CHECK-NEXT: /* 10 */      MCD::OPC_FilterValue, 0, 22, 0, // Skip to: 36
+// CHECK-NEXT: /* 14 */      MCD::OPC_CheckField, 0, 2, 3, 5, 0, // Skip to: 25
+// CHECK-NEXT: /* 20 */      MCD::OPC_TryDecode, 24, 0, 0, 0, // Opcode: InstB, skip to: 25
+// CHECK-NEXT: /* 25 */      MCD::OPC_CheckField, 3, 2, 0, 5, 0, // Skip to: 36
+// CHECK-NEXT: /* 31 */      MCD::OPC_TryDecode, 23, 1, 0, 0, // Opcode: InstA, skip to: 36
+// CHECK-NEXT: /* 36 */      MCD::OPC_Fail,
+
+// CHECK: if (DecodeInstB(MI, insn, Address, Decoder) == MCDisassembler::Fail) { DecodeComplete = false; return MCDisassembler::Fail; }
+// CHECK: if (DecodeInstA(MI, insn, Address, Decoder) == MCDisassembler::Fail) { DecodeComplete = false; return MCDisassembler::Fail; }

llvm/trunk/test/TableGen/trydecode-emission3.td

+// RUN: llvm-tblgen -gen-disassembler -I %p/../../include %s | FileCheck %s
+
+include "llvm/Target/Target.td"
+
+def archInstrInfo : InstrInfo { }
+
+def arch : Target {
+  let InstructionSet = archInstrInfo;
+}
+
+class TestInstruction : Instruction {
+  let Size = 1;
+  let OutOperandList = (outs);
+  let InOperandList = (ins);
+  field bits<8> Inst;
+  field bits<8> SoftFail = 0;
+}
+
+def InstA : TestInstruction {
+  let Inst = {0,0,0,0,?,?,?,?};
+  let AsmString = "InstA";
+}
+
+def InstBOp : Operand<i32> {
+  let DecoderMethod = "DecodeInstBOp";
+  let hasCompleteDecoder = 0;
+}
+
+def InstB : TestInstruction {
+  bits<2> op;
+  let Inst{7-2} = {0,0,0,0,0,0};
+  let Inst{1-0} = op;
+  let OutOperandList = (outs InstBOp:$op);
+  let AsmString = "InstB";
+}
+
+// CHECK:      /* 0 */       MCD::OPC_ExtractField, 4, 4,  // Inst{7-4} ...
+// CHECK-NEXT: /* 3 */       MCD::OPC_FilterValue, 0, 14, 0, // Skip to: 21
+// CHECK-NEXT: /* 7 */       MCD::OPC_CheckField, 2, 2, 0, 5, 0, // Skip to: 18
+// CHECK-NEXT: /* 13 */      MCD::OPC_TryDecode, 24, 0, 0, 0, // Opcode: InstB, skip to: 18
+// CHECK-NEXT: /* 18 */      MCD::OPC_Decode, 23, 1, // Opcode: InstA
+// CHECK-NEXT: /* 21 */      MCD::OPC_Fail,
+
+// CHECK: if (DecodeInstBOp(MI, tmp, Address, Decoder) == MCDisassembler::Fail) { DecodeComplete = false; return MCDisassembler::Fail; }

llvm/trunk/utils/TableGen/DisassemblerEmitter.cpp

void EmitDisassembler(RecordKeeper &Records, raw_ostream &OS) {
   // ARM and Thumb have a CHECK() macro to deal with DecodeStatuses.
   if (Target.getName() == "ARM" || Target.getName() == "Thumb" ||
       Target.getName() == "AArch64" || Target.getName() == "ARM64") {
     std::string PredicateNamespace = Target.getName();
     if (PredicateNamespace == "Thumb")
       PredicateNamespace = "ARM";
 
     EmitFixedLenDecoder(Records, OS, PredicateNamespace,
-                        "if (!Check(S, ", ")) return MCDisassembler::Fail;",
+                        "if (!Check(S, ", "))",
                         "S", "MCDisassembler::Fail",
                         "  MCDisassembler::DecodeStatus S = "
                           "MCDisassembler::Success;\n(void)S;");
     return;
   }
 
   EmitFixedLenDecoder(Records, OS, Target.getName(),
-                      "if (", " == MCDisassembler::Fail)"
-                       " return MCDisassembler::Fail;",
+                      "if (", " == MCDisassembler::Fail)",
                       "MCDisassembler::Success", "MCDisassembler::Fail", "");
 }
 
 } // End llvm namespace

llvm/trunk/utils/TableGen/FixedLenDecoderEmitter.cpp

struct EncodingField {
   unsigned Base, Width, Offset;
   EncodingField(unsigned B, unsigned W, unsigned O)
     : Base(B), Width(W), Offset(O) { }
 };
 
 struct OperandInfo {
   std::vector<EncodingField> Fields;
   std::string Decoder;
+  bool HasCompleteDecoder;
 
-  OperandInfo(std::string D)
-    : Decoder(D) { }
+  OperandInfo(std::string D, bool HCD)
+    : Decoder(D), HasCompleteDecoder(HCD) { }
 
   void addField(unsigned Base, unsigned Width, unsigned Offset) {
     Fields.push_back(EncodingField(Base, Width, Offset));
   }
 
   unsigned numFields() const { return Fields.size(); }
 
   typedef std::vector<EncodingField>::const_iterator const_iterator;
class FixedLenDecoderEmitter {
   const std::vector<const CodeGenInstruction*> *NumberedInstructions;
 public:
 
   // Defaults preserved here for documentation, even though they aren't
   // strictly necessary given the way that this is currently being called.
   FixedLenDecoderEmitter(RecordKeeper &R,
                          std::string PredicateNamespace,
                          std::string GPrefix  = "if (",
-                         std::string GPostfix = " == MCDisassembler::Fail)"
-                         " return MCDisassembler::Fail;",
+                         std::string GPostfix = " == MCDisassembler::Fail)",
                          std::string ROK      = "MCDisassembler::Success",
                          std::string RFail    = "MCDisassembler::Fail",
                          std::string L        = "") :
     Target(R),
     PredicateNamespace(PredicateNamespace),
     GuardPrefix(GPrefix), GuardPostfix(GPostfix),
     ReturnOK(ROK), ReturnFail(RFail), Locals(L) {}
 
protected:
   void emitSingletonTableEntry(DecoderTableInfo &TableInfo,
                                unsigned Opc) const;
 
   // Emits code to decode the singleton, and then to decode the rest.
   void emitSingletonTableEntry(DecoderTableInfo &TableInfo,
                                const Filter &Best) const;
 
   void emitBinaryParser(raw_ostream &o, unsigned &Indentation,
-                        const OperandInfo &OpInfo) const;
+                        const OperandInfo &OpInfo,
+                        bool &OpHasCompleteDecoder) const;
 
-  void emitDecoder(raw_ostream &OS, unsigned Indentation, unsigned Opc) const;
-  unsigned getDecoderIndex(DecoderSet &Decoders, unsigned Opc) const;
+  void emitDecoder(raw_ostream &OS, unsigned Indentation, unsigned Opc,
+                   bool &HasCompleteDecoder) const;
+  unsigned getDecoderIndex(DecoderSet &Decoders, unsigned Opc,
+                           bool &HasCompleteDecoder) const;
 
   // Assign a single filter and run with it.
   void runSingleFilter(unsigned startBit, unsigned numBit, bool mixed);
 
   // reportRegion is a helper function for filterProcessor to mark a region as
   // eligible for use as a filter region.
   void reportRegion(bitAttr_t RA, unsigned StartBit, unsigned BitIndex,
                     bool AllowMixed);
case MCD::OPC_CheckPredicate: {
       uint32_t NumToSkip = Byte;
       OS << utostr(Byte) << ", ";
       Byte = *I++;
       OS << utostr(Byte) << ", ";
       NumToSkip |= Byte << 8;
       OS << "// Skip to: " << ((I - Table.begin()) + NumToSkip) << "\n";
       break;
     }
-    case MCD::OPC_Decode: {
+    case MCD::OPC_Decode:
+    case MCD::OPC_TryDecode: {
+      bool IsTry = *I == MCD::OPC_TryDecode;
       ++I;
       // Extract the ULEB128 encoded Opcode to a buffer.
       uint8_t Buffer[8], *p = Buffer;
       while ((*p++ = *I++) >= 128)
         assert((p - Buffer) <= (ptrdiff_t)sizeof(Buffer)
                && "ULEB128 value too large!");
       // Decode the Opcode value.
       unsigned Opc = decodeULEB128(Buffer);
-      OS.indent(Indentation) << "MCD::OPC_Decode, ";
+      OS.indent(Indentation) << "MCD::OPC_" << (IsTry ? "Try" : "")
+        << "Decode, ";
       for (p = Buffer; *p >= 128; ++p)
         OS << utostr(*p) << ", ";
       OS << utostr(*p) << ", ";
 
       // Decoder index.
       for (; *I >= 128; ++I)
         OS << utostr(*I) << ", ";
       OS << utostr(*I++) << ", ";
 
+      if (!IsTry) {
         OS << "// Opcode: "
            << NumberedInstructions->at(Opc)->TheDef->getName() << "\n";
         break;
       }
+
+      // Fallthrough for OPC_TryDecode.
+
+      // 16-bit numtoskip value.
+      uint8_t Byte = *I++;
+      uint32_t NumToSkip = Byte;
+      OS << utostr(Byte) << ", ";
+      Byte = *I++;
+      OS << utostr(Byte) << ", ";
+      NumToSkip |= Byte << 8;
+
+      OS << "// Opcode: "
+         << NumberedInstructions->at(Opc)->TheDef->getName()
+         << ", skip to: " << ((I - Table.begin()) + NumToSkip) << "\n";
+      break;
+    }
     case MCD::OPC_SoftFail: {
       ++I;
       OS.indent(Indentation) << "MCD::OPC_SoftFail";
       // Positive mask
       uint64_t Value = 0;
       unsigned Shift = 0;
       do {
         OS << ", " << utostr(*I);

 emitDecoderFunction(formatted_raw_ostream &OS, DecoderSet &Decoders,
                     unsigned Indentation) const {
   // The decoder function is just a big switch statement based on the
   // input decoder index.
   OS.indent(Indentation) << "template<typename InsnType>\n";
   OS.indent(Indentation) << "static DecodeStatus decodeToMCInst(DecodeStatus S,"
     << " unsigned Idx, InsnType insn, MCInst &MI,\n";
   OS.indent(Indentation) << "                                   uint64_t "
-    << "Address, const void *Decoder) {\n";
+    << "Address, const void *Decoder, bool &DecodeComplete) {\n";
   Indentation += 2;
+  OS.indent(Indentation) << "DecodeComplete = true;\n";
   OS.indent(Indentation) << "InsnType tmp;\n";
   OS.indent(Indentation) << "switch (Idx) {\n";
   OS.indent(Indentation) << "default: llvm_unreachable(\"Invalid index!\");\n";
   unsigned Index = 0;
   for (const auto &Decoder : Decoders) {
     OS.indent(Indentation) << "case " << Index++ << ":\n";
     OS << Decoder;
     OS.indent(Indentation+2) << "return S;\n";
unsigned FilterChooser::getIslands(std::vector<unsigned> &StartBits,
   }
 
   assert(StartBits.size() == Num && EndBits.size() == Num &&
          FieldVals.size() == Num);
   return Num;
 }
 
 void FilterChooser::emitBinaryParser(raw_ostream &o, unsigned &Indentation,
-                                     const OperandInfo &OpInfo) const {
+                                     const OperandInfo &OpInfo,
+                                     bool &OpHasCompleteDecoder) const {
   const std::string &Decoder = OpInfo.Decoder;
 
   if (OpInfo.numFields() != 1)
     o.indent(Indentation) << "tmp = 0;\n";
 
   for (const EncodingField &EF : OpInfo) {
     o.indent(Indentation) << "tmp ";
     if (OpInfo.numFields() != 1) o << '|';
     o << "= fieldFromInstruction"
       << "(insn, " << EF.Base << ", " << EF.Width << ')';
     if (OpInfo.numFields() != 1 || EF.Offset != 0)
       o << " << " << EF.Offset;
     o << ";\n";
   }
 
-  if (Decoder != "")
+  if (Decoder != "") {
+    OpHasCompleteDecoder = OpInfo.HasCompleteDecoder;
     o.indent(Indentation) << Emitter->GuardPrefix << Decoder
-                          << "(MI, tmp, Address, Decoder)"
-                          << Emitter->GuardPostfix << "\n";
-  else
+      << Emitter->GuardPostfix
+      << " { " << (OpHasCompleteDecoder ? "" : "DecodeComplete = false; ")
+      << "return MCDisassembler::Fail; }\n";
+  } else {
+    OpHasCompleteDecoder = true;
     o.indent(Indentation) << "MI.addOperand(MCOperand::createImm(tmp));\n";
-
+  }
 }
 
 void FilterChooser::emitDecoder(raw_ostream &OS, unsigned Indentation,
-                                unsigned Opc) const {
+                                unsigned Opc, bool &HasCompleteDecoder) const {
+  HasCompleteDecoder = true;
+
   for (const auto &Op : Operands.find(Opc)->second) {
     // If a custom instruction decoder was specified, use that.
     if (Op.numFields() == 0 && Op.Decoder.size()) {
+      HasCompleteDecoder = Op.HasCompleteDecoder;
       OS.indent(Indentation) << Emitter->GuardPrefix << Op.Decoder
         << "(MI, insn, Address, Decoder)"
-        << Emitter->GuardPostfix << "\n";
+        << Emitter->GuardPostfix
+        << " { " << (HasCompleteDecoder ? "" : "DecodeComplete = false; ")
+        << "return MCDisassembler::Fail; }\n";
       break;
     }
 
-    emitBinaryParser(OS, Indentation, Op);
+    bool OpHasCompleteDecoder;
+    emitBinaryParser(OS, Indentation, Op, OpHasCompleteDecoder);
+    if (!OpHasCompleteDecoder)
+      HasCompleteDecoder = false;
   }
 }
 
 unsigned FilterChooser::getDecoderIndex(DecoderSet &Decoders,
-                                        unsigned Opc) const {
+                                        unsigned Opc,
+                                        bool &HasCompleteDecoder) const {
   // Build up the predicate string.
   SmallString<256> Decoder;
   // FIXME: emitDecoder() function can take a buffer directly rather than
   // a stream.
   raw_svector_ostream S(Decoder);
   unsigned I = 4;
-  emitDecoder(S, I, Opc);
+  emitDecoder(S, I, Opc, HasCompleteDecoder);
   S.flush();
 
   // Using the full decoder string as the key value here is a bit
   // heavyweight, but is effective. If the string comparisons become a
   // performance concern, we can implement a mangling of the predicate
   // data easilly enough with a map back to the actual string. That's
   // overkill for now, though.
 
for (unsigned I = Size; I != 0; --I) {
     // before we fully resolve the real value here.
     TableInfo.Table.push_back(0);
     TableInfo.Table.push_back(0);
   }
 
   // Check for soft failure of the match.
   emitSoftFailTableEntry(TableInfo, Opc);
 
-  TableInfo.Table.push_back(MCD::OPC_Decode);
+  bool HasCompleteDecoder;
+  unsigned DIdx = getDecoderIndex(TableInfo.Decoders, Opc, HasCompleteDecoder);
+
+  // Produce OPC_Decode or OPC_TryDecode opcode based on the information
+  // whether the instruction decoder is complete or not. If it is complete
+  // then it handles all possible values of remaining variable/unfiltered bits
+  // and for any value can determine if the bitpattern is a valid instruction
+  // or not. This means OPC_Decode will be the final step in the decoding
+  // process. If it is not complete, then the Fail return code from the
+  // decoder method indicates that additional processing should be done to see
+  // if there is any other instruction that also matches the bitpattern and
+  // can decode it.
+  TableInfo.Table.push_back(HasCompleteDecoder ? MCD::OPC_Decode :
+      MCD::OPC_TryDecode);
   uint8_t Buffer[8], *p;
   encodeULEB128(Opc, Buffer);
   for (p = Buffer; *p >= 128 ; ++p)
     TableInfo.Table.push_back(*p);
   TableInfo.Table.push_back(*p);
 
-  unsigned DIdx = getDecoderIndex(TableInfo.Decoders, Opc);
   SmallString<16> Bytes;
   raw_svector_ostream S(Bytes);
   encodeULEB128(DIdx, S);
   S.flush();
 
   // Decoder index
   for (unsigned i = 0, e = Bytes.size(); i != e; ++i)
     TableInfo.Table.push_back(Bytes[i]);
+
+  if (!HasCompleteDecoder) {
+    // Push location for NumToSkip backpatching.
+    TableInfo.FixupStack.back().push_back(TableInfo.Table.size());
+    // Allocate the space for the fixup.
+    TableInfo.Table.push_back(0);
+    TableInfo.Table.push_back(0);
+  }
 }
 
 // Emits table entries to decode the singleton, and then to decode the rest.
 void FilterChooser::emitSingletonTableEntry(DecoderTableInfo &TableInfo,
                                             const Filter &Best) const {
   unsigned Opc = Best.getSingletonOpc();
 
   // complex singletons need predicate checks from the first singleton
static bool populateInstruction(CodeGenTarget &Target,
   if (Bits.allInComplete()) return false;
 
   std::vector<OperandInfo> InsnOperands;
 
   // If the instruction has specified a custom decoding hook, use that instead
   // of trying to auto-generate the decoder.
   std::string InstDecoder = Def.getValueAsString("DecoderMethod");
   if (InstDecoder != "") {
-    InsnOperands.push_back(OperandInfo(InstDecoder));
+    bool HasCompleteInstDecoder = Def.getValueAsBit("hasCompleteDecoder");
+    InsnOperands.push_back(OperandInfo(InstDecoder, HasCompleteInstDecoder));
     Operands[Opc] = InsnOperands;
     return true;
   }
 
   // Generate a description of the operand of the instruction that we know
   // how to decode automatically.
   // FIXME: We'll need to have a way to manually override this as needed.
 
for (unsigned i = 0, e = Vals.size(); i != e; ++i) {
       }
 
       DecoderString = TypeRecord->getValue("DecoderMethod");
       String = DecoderString ?
         dyn_cast<StringInit>(DecoderString->getValue()) : nullptr;
       if (!isReg && String && String->getValue() != "")
         Decoder = String->getValue();
 
-      OperandInfo OpInfo(Decoder);
+      RecordVal *HasCompleteDecoderVal =
+        TypeRecord->getValue("hasCompleteDecoder");
+      BitInit *HasCompleteDecoderBit = HasCompleteDecoderVal ?
+        dyn_cast<BitInit>(HasCompleteDecoderVal->getValue()) : nullptr;
+      bool HasCompleteDecoder = HasCompleteDecoderBit ?
+        HasCompleteDecoderBit->getValue() : true;
+
+      OperandInfo OpInfo(Decoder, HasCompleteDecoder);
       OpInfo.addField(bitStart, bitWidth, 0);
 
       NumberedInsnOperands[Name].push_back(OpInfo);
 
       // FIXME: For complex operands with custom decoders we can't handle tied
       // sub-operands automatically. Skip those here and assume that this is
       // fixed up elsewhere.
       if (CGI.Operands[SO.first].MIOperandInfo &&
for (const auto &Op : InOutOperands) {
     }
 
     RecordVal *DecoderString = TypeRecord->getValue("DecoderMethod");
     StringInit *String = DecoderString ?
       dyn_cast<StringInit>(DecoderString->getValue()) : nullptr;
     if (!isReg && String && String->getValue() != "")
       Decoder = String->getValue();
 
-    OperandInfo OpInfo(Decoder);
+    RecordVal *HasCompleteDecoderVal =
+      TypeRecord->getValue("hasCompleteDecoder");
+    BitInit *HasCompleteDecoderBit = HasCompleteDecoderVal ?
+      dyn_cast<BitInit>(HasCompleteDecoderVal->getValue()) : nullptr;
+    bool HasCompleteDecoder = HasCompleteDecoderBit ?
+      HasCompleteDecoderBit->getValue() : true;
+
+    OperandInfo OpInfo(Decoder, HasCompleteDecoder);
     unsigned Base = ~0U;
     unsigned Width = 0;
     unsigned Offset = 0;
 
     for (unsigned bi = 0; bi < Bits.getNumBits(); ++bi) {
       VarInit *Var = nullptr;
       VarBitInit *BI = dyn_cast<VarBitInit>(Bits.getBit(bi));
       if (BI)
OS << "template<typename InsnType>\n"
      << "    }\n"
      << "    case MCD::OPC_Decode: {\n"
      << "      unsigned Len;\n"
      << "      // Decode the Opcode value.\n"
      << "      unsigned Opc = decodeULEB128(++Ptr, &Len);\n"
      << "      Ptr += Len;\n"
      << "      unsigned DecodeIdx = decodeULEB128(Ptr, &Len);\n"
      << "      Ptr += Len;\n"
-     << "      DEBUG(dbgs() << Loc << \": OPC_Decode: opcode \" << Opc\n"
-     << "                   << \", using decoder \" << DecodeIdx << \"\\n\" );\n"
-     << "      DEBUG(dbgs() << \"----- DECODE SUCCESSFUL -----\\n\");\n"
      << "\n"
      << "      MI.setOpcode(Opc);\n"
-     << "      return decodeToMCInst(S, DecodeIdx, insn, MI, Address, DisAsm);\n"
+     << "      bool DecodeComplete;\n"
+     << "      S = decodeToMCInst(S, DecodeIdx, insn, MI, Address, DisAsm, DecodeComplete);\n"
+     << "      assert(DecodeComplete);\n"
+     << "\n"
+     << "      DEBUG(dbgs() << Loc << \": OPC_Decode: opcode \" << Opc\n"
+     << "                   << \", using decoder \" << DecodeIdx << \": \"\n"
+     << "                   << (S != MCDisassembler::Fail ? \"PASS\" : \"FAIL\") << \"\\n\");\n"
+     << "      return S;\n"
+     << "    }\n"
+     << "    case MCD::OPC_TryDecode: {\n"
+     << "      unsigned Len;\n"
+     << "      // Decode the Opcode value.\n"
+     << "      unsigned Opc = decodeULEB128(++Ptr, &Len);\n"
+     << "      Ptr += Len;\n"
+     << "      unsigned DecodeIdx = decodeULEB128(Ptr, &Len);\n"
+     << "      Ptr += Len;\n"
+     << "      // NumToSkip is a plain 16-bit integer.\n"
+     << "      unsigned NumToSkip = *Ptr++;\n"
+     << "      NumToSkip |= (*Ptr++) << 8;\n"
+     << "\n"
+     << "      // Perform the decode operation.\n"
+     << "      MCInst TmpMI;\n"
+     << "      TmpMI.setOpcode(Opc);\n"
+     << "      bool DecodeComplete;\n"
+     << "      S = decodeToMCInst(S, DecodeIdx, insn, TmpMI, Address, DisAsm, DecodeComplete);\n"
+     << "      DEBUG(dbgs() << Loc << \": OPC_TryDecode: opcode \" << Opc\n"
+     << "                   << \", using decoder \" << DecodeIdx << \": \");\n"
+     << "\n"
+     << "      if (DecodeComplete) {\n"
+     << "        // Decoding complete.\n"
+     << "        DEBUG(dbgs() << (S != MCDisassembler::Fail ? \"PASS\" : \"FAIL\") << \"\\n\");\n"
+     << "        MI = TmpMI;\n"
+     << "        return S;\n"
+     << "      } else {\n"
+     << "        assert(S == MCDisassembler::Fail);\n"
+     << "        // If the decoding was incomplete, skip.\n"
+     << "        Ptr += NumToSkip;\n"
+     << "        DEBUG(dbgs() << \"FAIL: continuing at \" << (Ptr - DecodeTable) << \"\\n\");\n"
+     << "        // Reset decode status. This also drops a SoftFail status that could be\n"
+     << "        // set before the decode attempt.\n"
+     << "        S = MCDisassembler::Success;\n"
+     << "      }\n"
+     << "      break;\n"
      << "    }\n"
      << "    case MCD::OPC_SoftFail: {\n"
      << "      // Decode the mask values.\n"
      << "      unsigned Len;\n"
      << "      InsnType PositiveMask = decodeULEB128(++Ptr, &Len);\n"
      << "      Ptr += Len;\n"
      << "      InsnType NegativeMask = decodeULEB128(Ptr, &Len);\n"
      << "      Ptr += Len;\n"