[TableGen] AsmMatcher: fix OpIdx computation when HasOptionalOperands is true

[alexandru.guduleasa]

Summary

Consider the following instruction: "inst.eq $dst, $src" where ".eq" is an optional flag operand.
The $src and $dst operands are registers.
If we parse the instruction "inst r0, r1", the flag is not present and it will be marked in the "OptionalOperandsMask" variable.
After the matching is complete we call the "convertToMCInst" method.

The current implementation works only if the optional operands are at the end of the array.
The "Operands" array looks like [token:"inst", reg:r0, reg:r1].
The first operand that must be added to the MCInst is the destination, the r0 register.
The "OpIdx" (in the Operands array) for this register is 2.
However, since the flag is not present in the Operands, the actual index for r0 should be 1.
The flag is not present since we rely on the default value.

This patch removes the "NumDefaults" variable and replaces it with an array (DefaultsOffset).
This array contains an index for each operand (excluding the mnemonic).
At each index, the array contains the number of optional operands that should be subtracted.
For the previous example, this array looks like this: [0, 1, 1].
When we need to access the r0 register, we compute its index as 2 - DefaultsOffset[1] = 1.

[niravd]

Can you add a test case?

[alexandru.guduleasa]

Unfortunately, the only in-tree target that uses IsOptional attribute is AMDGPU.

As far as I can tell, all these optional operands are placed at the end of the asm string.
e.g.

class MIMG_NoSampler_Helper <bits<7> op, string asm,
                             RegisterClass dst_rc,
                             RegisterClass addr_rc,
                             string dns=""> : MIMG_Helper <
  (outs dst_rc:$vdata),
  (ins addr_rc:$vaddr, SReg_256:$srsrc,
       dmask:$dmask, unorm:$unorm, GLC:$glc, slc:$slc,
       r128:$r128, tfe:$tfe, lwe:$lwe, da:$da),
  asm#" $vdata, $vaddr, $srsrc$dmask$unorm$glc$slc$r128$tfe$lwe$da",
  dns>, MIMGe<op> {
  let ssamp = 0;
}

where $dmask $unorm $glc $slc $r128 $tfe $lwe and $da are all optional.

Therefore, I don't think I can add a test for this.

[niravd]

utils/TableGen/AsmMatcherEmitter.cpp

2001 ↗

(On Diff #108648)

It looks like you're only using the final DefaultOffset value in OpIdx calculation and NumDefault isn't used elsewhere so it seems like we don't need the array at all.

Does replacing the ++NumDefaults line with

if (OptionalOperandsMask[i]) ++NumDefaults;

work?

[alexandru.guduleasa]

utils/TableGen/AsmMatcherEmitter.cpp

2001 ↗

(On Diff #108648)

The array is used because the order in which the operands are added in the MCInst is provided by the "ConversionTable".

For the following instruction, I've added the entry from the "ConversionTable"

Instruction asm str:

"inst$flg1$flg2 rd, rs, Imm"

ConversionTable:
 // Convert__Reg1_2__Flg1_0__Flg2_1__Reg1_3__s32Imm1_4
{ CVT_95_Reg, 3,
  CVT_95_addFlagOperands_LT_CplOperand_COLON__COLON_k_95_Flg1, 1,
  CVT_95_addFlagOperands_LT_CplOperand_COLON__COLON_k_95_Flg2, 2,
  CVT_95_Reg, 4,
  CVT_95_addImmOperands,5, CVT_Done
}

The first operand that is added is a register (rd, at position 3 in the Operands vector) since the destination must come first.

The array is computed before we analyze the operands and it provides us with the "correction offset".
We could technically remove the array, but then we would need to recompute the offset before each operand (because they are out of order).

[niravd]

utils/TableGen/AsmMatcherEmitter.cpp

2001 ↗

(On Diff #108648)

Ah. So the reason ++NumDefaults worked before is that it only handled at the end.

Okay. I don't think there's much else we can do here beyond precomputing all DefaultOffsets per instruction at compile time and adding it to the table which doesn't seem worthwhile.

Can you add a comment with a little explanation here. and otherwise LGTM.

[alexandru.guduleasa]

Added requested comment.

[niravd]

Great. It looks like you don't have commit access. Would you like me to commit this patch for you?

[alexandru.guduleasa]

Yes, thank you.

[niravd]

I just did a sanity check on this patch upstream before committing and it crashes on a number of AMDGPU tests. Can you take a quick look at what's wrong?

[alexandru.guduleasa]

Can you please tell which tests? And how did you ran them?

We ran the tests on a linux x64 machine, with the patch applied after commit:

commit b779d345975e7346ce783d7d843e09706539c49e
Author: Strahinja Petrovic <[e-mail]>
Date:   Fri Jul 28 12:54:57 2017 +0000

    [ARM] Add the option to directly access TLS pointer

The result were:

Testing Time: 600.54s
  Expected Passes    : 20952
  Expected Failures  : 136
  Unsupported Tests  : 437
[100%] Built target check-llvm

Cmake was ran with just the source directory (i.e. with all targets)

cmake ../llvm

Maybe we are missing something.

[niravd]

I'm seeing it after this:

commit 343f60c4b20e14528fc519c83b7bbd9e2a48423b
Author: Ayal Zaks <[e-mail]>
Date: Mon Jul 31 13:21:42 2017 +0000

[LV] Avoid redundant operations manipulating masks

with the following failing tests:

LLVM :: MC/AMDGPU/gfx7_asm_all.s
LLVM :: MC/AMDGPU/gfx8_asm_all.s
LLVM :: MC/AMDGPU/gfx9_asm_all.s
LLVM :: MC/AMDGPU/sopk.s
LLVM :: MC/AMDGPU/vintrp.s
LLVM :: MC/AMDGPU/vop1-gfx9.s
LLVM :: MC/AMDGPU/vop2.s
LLVM :: MC/AMDGPU/vop3-convert.s

[alexandru.guduleasa]

Thank you for your reply.

We applied the patch after the commit that you mentioned:

git log -n2 --oneline
db8a65e AsmMatcher: fix OpIdx computation when HasOptionalOperands is true
343f60c [LV] Avoid redundant operations manipulating masks

We confirmed that the generated code contains our modification:

cat AMDGPUGenAsmMatcher.inc | grep -e "DefaultsOffset"
  unsigned DefaultsOffset[12];
    DefaultsOffset[i] = NumDefaults;
    OpIdx = *(p + 1) - DefaultsOffset[*(p + 1) - 1];

After this, we explicitly ran the mentioned tests:

./bin/llvm-lit ../llvm/test/MC/AMDGPU/gfx7_asm_all.s ../llvm/test/MC/AMDGPU/gfx8_asm_all.s ../llvm/test/MC/AMDGPU/gfx9_asm_all.s ../llvm/test/MC/AMDGPU/sopk.s ../llvm/test/MC/AMDGPU/vintrp.s ../llvm/test/MC/AMDGPU/vop1-gfx9.s ../llvm/test/MC/AMDGPU/vop2.s ../llvm/test/MC/AMDGPU/vop3-convert.s
-- Testing: 8 tests, 4 threads --
PASS: LLVM :: MC/AMDGPU/sopk.s (1 of 8)
PASS: LLVM :: MC/AMDGPU/vintrp.s (2 of 8)
PASS: LLVM :: MC/AMDGPU/vop1-gfx9.s (3 of 8)
PASS: LLVM :: MC/AMDGPU/vop2.s (4 of 8)
PASS: LLVM :: MC/AMDGPU/vop3-convert.s (5 of 8)
PASS: LLVM :: MC/AMDGPU/gfx7_asm_all.s (6 of 8)
PASS: LLVM :: MC/AMDGPU/gfx9_asm_all.s (7 of 8)
PASS: LLVM :: MC/AMDGPU/gfx8_asm_all.s (8 of 8)
Testing Time: 4.76s
  Expected Passes    : 8

Any suggestions?

[niravd]

I suspect that the issue is variation in our cmake configurations. I just rebuilt from a clean build and got the same issues.

Try it with CMAKE_BUILD_TYPE=Debug and LLVM_ENABLE_ASSERETIONS=ON.

In D35998#828678, @alexandru.guduleasa wrote:

Thank you for your reply.

We applied the patch after the commit that you mentioned:

git log -n2 --oneline
db8a65e AsmMatcher: fix OpIdx computation when HasOptionalOperands is true
343f60c [LV] Avoid redundant operations manipulating masks

We confirmed that the generated code contains our modification:

cat AMDGPUGenAsmMatcher.inc | grep -e "DefaultsOffset"
  unsigned DefaultsOffset[12];
    DefaultsOffset[i] = NumDefaults;
    OpIdx = *(p + 1) - DefaultsOffset[*(p + 1) - 1];

After this, we explicitly ran the mentioned tests:

./bin/llvm-lit ../llvm/test/MC/AMDGPU/gfx7_asm_all.s ../llvm/test/MC/AMDGPU/gfx8_asm_all.s ../llvm/test/MC/AMDGPU/gfx9_asm_all.s ../llvm/test/MC/AMDGPU/sopk.s ../llvm/test/MC/AMDGPU/vintrp.s ../llvm/test/MC/AMDGPU/vop1-gfx9.s ../llvm/test/MC/AMDGPU/vop2.s ../llvm/test/MC/AMDGPU/vop3-convert.s
-- Testing: 8 tests, 4 threads --
PASS: LLVM :: MC/AMDGPU/sopk.s (1 of 8)
PASS: LLVM :: MC/AMDGPU/vintrp.s (2 of 8)
PASS: LLVM :: MC/AMDGPU/vop1-gfx9.s (3 of 8)
PASS: LLVM :: MC/AMDGPU/vop2.s (4 of 8)
PASS: LLVM :: MC/AMDGPU/vop3-convert.s (5 of 8)
PASS: LLVM :: MC/AMDGPU/gfx7_asm_all.s (6 of 8)
PASS: LLVM :: MC/AMDGPU/gfx9_asm_all.s (7 of 8)
PASS: LLVM :: MC/AMDGPU/gfx8_asm_all.s (8 of 8)
Testing Time: 4.76s
  Expected Passes    : 8

Any suggestions?

[alexandru.guduleasa]

We managed to reproduce this using Visual Studio; thank you for your patience.
The issue was that for Tied operand, the OpIdx is an index in Inst, not in the Operands vector.
Since we subtracted 1 for the mnemonic, we had an underflow access in the array.
For Tied Operands, we don't need the array at all since the index is in the Inst, not the Operands.

[niravd]

Looks Good. I'll just recheck it again and land it.

[vitalybuka]

reverted in r310008
http://lab.llvm.org:8011/builders/sanitizer-x86_64-linux-fast/builds/6924/steps/check-llvm%20ubsan/logs/stdio

[niravd]

Based on the UB Error, it seems like the CVT_tied check should be removed and the values of DefaultOffsets shifted over one.

CvtOS << "  for (unsigned i = 0, NumDefaults = 0; i < " << (MaxNumOperands-1) << "; ++i) {\n";
CvtOS << "    DefaultsOffset[i] = NumDefaults;\n";
CvtOS << "    NumDefaults += (OptionalOperandsMask[i+1] ? 1 : 0);\n";
CvtOS << "  }\n";

and

CvtOS << "    OpIdx = *(p + 1) - DefaultsOffset[*(p + 1) ];\n" ;

[alexandru.guduleasa]

I agree with the sift by one proposal and I apologize that we didn't catch this error on our end.
Apparently, there are some immediate operands that have the same value (e.g. 0).
For these, the OpIdx is not used, but it was computed anyway (and caused the out of bounds error).

I've increased the size of the array by one and I'm accessing the same index as the Operands vector.
All the operands that have 0 as the index (Tied_To, and those always-zero immediate) will no longer cause an error.

[niravd]

LGTM. I'll run it locally myself and land it. Thanks.

[MikeStump]

This version is buggy and doesn't work. The version of the fix in https://reviews.llvm.org/D32461 is better in my port and works even in the trivial cases. So the question is, is there any case not fixed by it?

llvm/trunk/utils/TableGen/AsmMatcherEmitter.cpp

if (HasOptionalOperands) {
     CvtOS << "void " << Target.getName() << ClassName << "::\n"
           << "convertToMCInst(unsigned Kind, MCInst &Inst, "
           << "unsigned Opcode,\n"
           << "                const OperandVector &Operands) {\n";
   }
   CvtOS << "  assert(Kind < CVT_NUM_SIGNATURES && \"Invalid signature!\");\n";
   CvtOS << "  const uint8_t *Converter = ConversionTable[Kind];\n";
   if (HasOptionalOperands) {
-    CvtOS << "  unsigned NumDefaults = 0;\n";
+    size_t MaxNumOperands = 0;
+    for (const auto &MI : Infos) {
+      MaxNumOperands = std::max(MaxNumOperands, MI->AsmOperands.size());
+    }
+    CvtOS << "  unsigned DefaultsOffset[" << (MaxNumOperands + 1)
+          << "] = { 0 };\n";
+    CvtOS << "  assert(OptionalOperandsMask.size() == " << (MaxNumOperands)
+          << ");\n";
+    CvtOS << "  for (unsigned i = 0, NumDefaults = 0; i < " << (MaxNumOperands)
+          << "; ++i) {\n";
+    CvtOS << "    DefaultsOffset[i + 1] = NumDefaults;\n";
+    CvtOS << "    NumDefaults += (OptionalOperandsMask[i] ? 1 : 0);\n";
+    CvtOS << "  }\n";
   }
   CvtOS << "  unsigned OpIdx;\n";
   CvtOS << "  Inst.setOpcode(Opcode);\n";
   CvtOS << "  for (const uint8_t *p = Converter; *p; p+= 2) {\n";
   if (HasOptionalOperands) {
-    CvtOS << "    OpIdx = *(p + 1) - NumDefaults;\n";
+    CvtOS << "    OpIdx = *(p + 1) - DefaultsOffset[*(p + 1)];\n";
   } else {
     CvtOS << "    OpIdx = *(p + 1);\n";
   }
   CvtOS << "    switch (*p) {\n";
   CvtOS << "    default: llvm_unreachable(\"invalid conversion entry!\");\n";
   CvtOS << "    case CVT_Reg:\n";
   CvtOS << "      static_cast<" << TargetOperandClass
         << "&>(*Operands[OpIdx]).addRegOperands(Inst, 1);\n";
for (unsigned i = 0, e = II->ResOperands.size(); i != e; ++i) {
         if (Op.Class->IsOptional) {
           // If optional operand is not present in actual instruction then we
           // should call its DefaultMethod before RenderMethod
           assert(HasOptionalOperands);
           CvtOS << "      if (OptionalOperandsMask[*(p + 1) - 1]) {\n"
                 << "        " << Op.Class->DefaultMethod << "()"
                 << "->" << Op.Class->RenderMethod << "(Inst, "
                 << OpInfo.MINumOperands << ");\n"
-                << "        ++NumDefaults;\n"
                 << "      } else {\n"
                 << "        static_cast<" << TargetOperandClass
                 << "&>(*Operands[OpIdx])." << Op.Class->RenderMethod
                 << "(Inst, " << OpInfo.MINumOperands << ");\n"
                 << "      }\n";
         } else {
           CvtOS << "      static_cast<" << TargetOperandClass
                 << "&>(*Operands[OpIdx])." << Op.Class->RenderMethod