This is an archive of the discontinued LLVM Phabricator instance.

[MLIR] Add a switch operation to the standard dialect
ClosedPublic

Authored by GMNGeoffrey on Apr 5 2021, 10:34 PM.

Details

Summary

This is similar to the definition of llvm.switch, providing
unstructured branch-based control flow. It differs from the LLVM
operation in that it accepts any signless integer (not only an i32),
takes no branch weights (the same as the Branch and CondBranch ops),
and has a slightly different syntax for the default case that includes
it in the list of cases with an explicit default keyword.

Also included are several canonicalizers.

See https://llvm.discourse.group/t/rfc-add-std-switch-and-scf-switch/3090

Diff Detail

Event Timeline

GMNGeoffrey created this revision.Apr 5 2021, 10:34 PM
GMNGeoffrey requested review of this revision.Apr 5 2021, 10:34 PM

Remove leftover debugging stuff

  • Remove extraneous include
rriddle added inline comments.Apr 5 2021, 10:48 PM
mlir/include/mlir/Dialect/StandardOps/IR/Ops.td
2044

typo siwtch

2060

Not sure I understand the justification for choosing i32 here.

mlir/lib/Dialect/StandardOps/IR/Ops.cpp
2315

Avoid computing the size during the loop.

2316

Drop trivial braces here and on the for.

Harbormaster completed remote builds in B97231: Diff 335403.
bondhugula requested changes to this revision.Apr 6 2021, 12:22 AM
bondhugula added a subscriber: bondhugula.

Looks great - some minor comments.

mlir/include/mlir/Dialect/StandardOps/IR/Ops.td
2053

Do you want to instead just:

switch %flag [
  default: ^bb1(%a : i32)
  42: ^bb1(%b : i32),
  43: ^bb3(%c : i32)
]
2060

Use i64 instead? You could have a case for a large value 2^64-1 and then default for everything.

mlir/lib/Dialect/StandardOps/IR/Ops.cpp
2174

unsigned?

2255

Nit: ' '

This revision now requires changes to proceed.Apr 6 2021, 12:22 AM
ftynse added a subscriber: ftynse.Apr 6 2021, 2:19 AM
ftynse added inline comments.
mlir/include/mlir/Dialect/StandardOps/IR/Ops.td
2060

Can't it be just any integer? Same for case values, which can become IntElementsAttr. Just have a verifier check that the types match.

GMNGeoffrey added inline comments.Apr 6 2021, 9:30 AM
mlir/include/mlir/Dialect/StandardOps/IR/Ops.td
2060

Per the RFC, I modeled this directly off of llvm.switch. This could indeed be any Integer, or really any type at all. How much do we want to expand it?

ftynse added inline comments.Apr 6 2021, 9:35 AM
mlir/include/mlir/Dialect/StandardOps/IR/Ops.td
2060

Sorry, I didn't see the RFC before. I would have asked why do we need a carbon copy of the LLVM dialect operation in the Standard dialect if we can mix dialects instead (LLVM no longer needs special types...) I am fine with any integer because I don't see how to make the verification work for an arbitrary type.

Are these clang-tidy naming errors legit? I think the names match the ones used

Also terrifying that my test for passthrough isn't failing given that I apparently forgot to add the passthrough pattern.... It would be really nice to be able to limit canonicalization to only patterns on certain ops or something

GMNGeoffrey marked an inline comment as not done.Apr 6 2021, 9:41 AM
GMNGeoffrey added inline comments.
mlir/include/mlir/Dialect/StandardOps/IR/Ops.td
2060

Seems like arbitrary type should be verifiable in just the same way? Check that the type of the ElementsAttr elements are the same as the type of value. The fact that ElementsAttr is limited to tensor or vector places some restrictions on the type, although we could even expand this to be an Array instead (there was discussion of having something that general in scf). That "feels" too high level for standard to me (switch on my custom proto type!), but I'm not sure I have a good argument for why.

ftynse added a comment.Apr 6 2021, 9:44 AM

Are these clang-tidy naming errors legit? I think the names match the ones used

MLIR uses (lower) camelBack for function names.

Also terrifying that my test for passthrough isn't failing given that I apparently forgot to add the passthrough pattern.... It would be really nice to be able to limit canonicalization to only patterns on certain ops or something

I think br has a canonicalizer itself that removes useless branches.

ftynse added inline comments.Apr 6 2021, 9:46 AM
mlir/include/mlir/Dialect/StandardOps/IR/Ops.td
2060

Standard ops (mostly) work on built-in types only, so I'd stick to that for consistency.

Are these clang-tidy naming errors legit? I think the names match the ones used

MLIR uses (lower) camelBack for function names.

Oh right because the other canonicalizers are structs and these are just free functions.

rriddle requested changes to this revision.Apr 6 2021, 10:12 AM
rriddle added inline comments.
mlir/include/mlir/Dialect/StandardOps/IR/Ops.td
2060

I'd stick to just builtin integers for now.

mlir/lib/Dialect/StandardOps/IR/Ops.cpp
2213

Can you use succeeded/failed for these optional parse functions?

2216–2217

This would mean that no error message is emitted when the integer isn't there, but should be. Can you split these two cases and give a proper error message?

2224

Can you use succeeded/failed for these optional parse functions?

2268

Can you cache case_values() and caseDestinations()?

2352

Same comment on recomputing size here and below.

2360

Please avoid going through IntegerAttr, use APInt instead (assuming the cases can be any integer).

2549

Drop the llvm:: here.

GMNGeoffrey added inline comments.Apr 6 2021, 10:19 AM
mlir/include/mlir/Dialect/StandardOps/IR/Ops.td
2053

Do others have thoughts on the assembly format here? I was again using the same format as llvm.switch, but I do think that perhaps this way with a keyword is clearer.

mlir/lib/Dialect/StandardOps/IR/Ops.cpp
2213

Will clean up the print/parse functions. I just copied them from llvm :-D

2268

Are these accessors expensive? I had assumed they're just giving references to existing vectors.

2315

Is size computation expensive for these? Again I assumed this would be a constant access to some offset.

rriddle added inline comments.Apr 6 2021, 10:25 AM
mlir/lib/Dialect/StandardOps/IR/Ops.cpp
2268

The below applies to operations in general:

They can be, because the locations of the operands have to be computed. It isn't just a index into a field of Operation, it is also an address calculation for the trailing array. That also isn't factoring in when multiple operand groups of the operation are variadic, it has to compute the range of this operand group (which may involve accessing attributes from the operation).

2315

In this case, size() is likely "free" (case_values is not). In the broader LLVM style, we take the approach of never recomputing the size unless necessary for the algorithm being performed.

https://llvm.org/docs/CodingStandards.html#don-t-evaluate-end-every-time-through-a-loop

GMNGeoffrey added inline comments.Apr 6 2021, 10:29 AM
mlir/lib/Dialect/StandardOps/IR/Ops.cpp
2268

Got it. Thanks for explaining :-)

2315

Got it, thanks for the pointer!

GMNGeoffrey added inline comments.Apr 6 2021, 11:49 AM
mlir/lib/Dialect/StandardOps/IR/Ops.cpp
2174

The function being called here is getI32VectorAttr(ArrayRef<int32_t> values);, so I think int32_t is the correct type

2213

How do we feel about optional trailing commas when parsing? In general, I'm pro, but it means there are non-whitespace differences between different correct ways to write this, which I'm not sure yet exists in MLIR

mehdi_amini added inline comments.Apr 6 2021, 12:26 PM
mlir/lib/Dialect/StandardOps/IR/Ops.cpp
2213

I'm pro in programming language and other things like JSON (which does not have them and I hate it for this!).
I'm not sure it makes sense for an IR format though?

(I'm sure many custom parser are already accepting non-whitespace difference though, I think I wrote such code myself on occasions)

GMNGeoffrey marked an inline comment as not done.Apr 6 2021, 12:45 PM
GMNGeoffrey added inline comments.
mlir/lib/Dialect/StandardOps/IR/Ops.cpp
2213

Yes that's how I feel as well. I write mlir enough that it feels like a programming language sometimes :-D One of the reasons I ask is that it can make the parser potentially simpler if I'm looking for the right square bracket to end the loop rather than it being dependent on commas:

c++
  while(failed(parser.parseOptionalRSquare())) {
    if (failed(parser.parseInteger(value)))
      return failure();
    values.push_back(value);

    Block *destination;
    SmallVector<OpAsmParser::OperandType> operands;
    if (failed(parser.parseColon()) ||
        failed(parser.parseSuccessor(destination)))
      return failure();
    if (succeeded(parser.parseOptionalLParen())) {
      if (failed(parser.parseRegionArgumentList(operands)) ||
          failed(parser.parseColonTypeList(caseOperandTypes)) ||
          failed(parser.parseRParen()))
        return failure();
    }
    caseDestinations.push_back(destination);
    caseOperands.append(operands.begin(), operands.end());
    offsets.push_back(offset);
    offset += operands.size();
    if (failed(parser.parseOptionalComma())) {
      if(failed(parser.parseRSquare()))
        return failure();
      break;
    }
  }

Maybe makes sense to see how people feel about Uday's suggestion to move the default case within the brackets as well. One other wrinkle with the format is that if we allow any integer I think we have to include the type. Something like this is now what I'm thinking:

mlir
switch %flag, [
  default: ^bb1(%a : f32),
  42: ^bb2(%b : f32)
] : i32

Or maybe it's better to leave the type by the flag:

mlir
switch %flag : i32, [
  default: ^bb1(%a : f32),
  42: ^bb2(%b : f32)
]
GMNGeoffrey marked 11 inline comments as done.

Respond to review comments

GMNGeoffrey added inline comments.Apr 6 2021, 8:49 PM
mlir/include/mlir/Dialect/StandardOps/IR/Ops.td
2053

I switched to this format. I like it better.

mlir/lib/Dialect/StandardOps/IR/Ops.cpp
2255

Sorry I don't understand. This is printing two spaces, so can't be a char, if that's what you mean. Let me know if this comment still applies to the updated printer.

2316

Done. Though I still hate this :-D

Fix function naming

bondhugula accepted this revision.Apr 7 2021, 10:30 AM
bondhugula added inline comments.
mlir/include/mlir/Dialect/StandardOps/IR/Ops.td
2053

Looks great (the syntax I found in the test case). This snippet needs to be updated.

mlir/test/Dialect/Standard/parser.mlir
41

The syntax in the op doc hasn't been updated to reflect this I think.

GMNGeoffrey marked an inline comment as done.
  • Add unknown op predecessor to tests to block other canonicalizations
  • Fix passthrough canonicalization
  • Clean up test cases
mlir/test/Dialect/Standard/parser.mlir
41

Thanks for catching :-)

rriddle accepted this revision.Apr 9 2021, 5:46 PM

LGTM in general.

mlir/include/mlir/Dialect/StandardOps/IR/Ops.td
2044

The description here is out-of-date.

2092–2094
mlir/lib/Dialect/StandardOps/IR/Ops.cpp
2344–2345

nit: Can you spell out auto here?

2345

Hoist this to the top of the function to avoid calling case_values twice?

2349

This assumes that the values are int64_t, I think will assert if not.

2549

nit: Spell out auto here.

2608

nit: Drop trivial braces here.

This revision is now accepted and ready to land.Apr 9 2021, 5:46 PM
GMNGeoffrey marked 5 inline comments as done.

Address review comments

GMNGeoffrey added inline comments.Apr 12 2021, 5:03 PM
mlir/include/mlir/Dialect/StandardOps/IR/Ops.td
2044

Thanks for catching. Fixed.

mlir/lib/Dialect/StandardOps/IR/Ops.cpp
2349

Yikes! Thanks for catching. What's the right way to test this? It doesn't seem right that every op (especially those outside of core dialects) should be tested as part of the sccp pass test.

GMNGeoffrey retitled this revision from Add a switch operation to the standard dialect to [MLIR] Add a switch operation to the standard dialect.Apr 12 2021, 6:45 PM
GMNGeoffrey edited the summary of this revision. (Show Details)
This revision was automatically updated to reflect the committed changes.