This is an archive of the discontinued LLVM Phabricator instance.

Preserve use-list orders in mlir bytecode
ClosedPublic

Authored by mfrancio on May 3 2023, 8:56 AM.

Details

Summary

This patch implements a mechanism to read/write use-list orders from/to the mlir bytecode format. When producing bytecode, use-list orders are appended to each value of the IR. When reading bytecode, use-lists orders are loaded in memory and used at the end of parsing to sort the existing use-list chains.

Diff Detail

Event Timeline

mfrancio created this revision.May 3 2023, 8:56 AM
Herald added a project: Restricted Project. · View Herald TranscriptMay 3 2023, 8:56 AM
mfrancio requested review of this revision.May 3 2023, 8:56 AM

You need to update the Bytecode documentation still I think.

mlir/include/mlir/Bytecode/BytecodeWriter.h
37 ↗(On Diff #519093)

Please keep the default to true: I'd really want the default to always be the "safe" way. We already got it wrong in other places and it's impossible to fix later.

Also what about a fluent API like we do for other config? (OpPrintingFlags for example)

mlir/include/mlir/IR/AsmState.h
463 ↗(On Diff #519093)

I don't quite get why we need this? I would just honor what's in the bytecode without config here.

mlir/lib/Bytecode/Writer/BytecodeWriter.cpp
793

How do you manager the order of two uses by the same operation?

mlir/lib/IR/Value.cpp
103

Seems like you could just zip order with the uses here instead of enumerate?

107

Does C++17 allows for (const auto &[use, newUse] : llvm::zip(getUses(), newUseList)) {?
Structured bindings might look nicer than the std::get

rriddle added inline comments.May 3 2023, 9:46 PM
mlir/include/mlir/Bytecode/BytecodeWriter.h
37 ↗(On Diff #519093)

+1. Let's focus on making the default correct and efficient.

mlir/include/mlir/IR/AsmState.h
463 ↗(On Diff #519093)

Yeah, I don't see an initial need for this functionality. Let's start simple, this can always be added if we really really need it later.

mlir/include/mlir/IR/Value.h
192

The formatting here looks off.

mlir/lib/Bytecode/Reader/BytecodeReader.cpp
1286–1287

Can you turn the value of this into a struct? It's not obvious what the bool means.

1348

Please document the struct.

1353

// -> /// for each of these.

1835–1838
mfrancio updated this revision to Diff 520217.May 7 2023, 4:45 PM

The patch contains the following updates:

  1. removes the command line arguments to optionally print/read use-lists to bytecode, which are now printed and parsed by default;
  2. extends the use-lists orders info to block arguments and increases the bytecode version to 2 (this was a breaking change);
  3. implements a testing pass to do somewhat of a rigorous functional check (essentially, the pass takes any module, applies a random shuffle to the use-list of every value/blockarg, does a roundtrip to bytecode and verifies that the use-list order is preserved).
  4. Fixes few functionality issues of the initial implementation:
    • the use-list was not shuffled correctly, the implementation is now updated and tested rigorously within the testing pass;
    • the case with multiple uses in the same operand was not handled correctly - now I introduced a new enumeration that takes into account the operand number of the use;
    • I found few corner cases where the op enumeration I was doing was not consistent with what I needed (pre-order walk). Now this is done separately before the recursive enumeration of regions

I experimented a little bit with the testing pass and run it through the whole set of mlir file check tests that exist in the repo, and saw no failures.

I hope you will find this work interesting. Looking forward for further feedback.

mfrancio marked 11 inline comments as done.May 7 2023, 4:53 PM
mfrancio added inline comments.
mlir/include/mlir/Bytecode/BytecodeWriter.h
37 ↗(On Diff #519093)

Ok, I removed this. We could add this later if needed.

mlir/include/mlir/IR/AsmState.h
463 ↗(On Diff #519093)

Removed. Thanks.

mlir/include/mlir/IR/Value.h
192

Should be fixed now.

mlir/lib/Bytecode/Reader/BytecodeReader.cpp
1286–1287

I simplified the implementation a little bit and added a struct with documentation.

mlir/lib/Bytecode/Writer/BytecodeWriter.cpp
793

It was indeed not done correctly - I updated the implementation and now this is done by sorting with keys that contain operand number and operation number.

mlir/lib/IR/Value.cpp
107

Apologies, but this wasn't done correctly - I thought I could be able to change pointee without changing pointers, but the API wasn't really doing that. I added a couple of helpers to shuffle the uselist explicitly.

mfrancio updated this revision to Diff 521408.May 11 2023, 12:24 PM
mfrancio marked 6 inline comments as done.
mfrancio edited the summary of this revision. (Show Details)

Adds a test case that exercises preserving use-lists on IR without dominance.

mehdi_amini accepted this revision.May 19 2023, 9:51 PM

LG, with a nit.

mlir/test/lib/IR/TestUseListOrders.cpp
200

I'm concerned that we'll have reproducibility issues here. Can we explicitly initialize the engine with a seed that would be a pass option?
Even if you run the test with a random seed, we'll at least see it in the invocation and have reproducibility.

This revision is now accepted and ready to land.May 19 2023, 9:51 PM
mehdi_amini added inline comments.May 19 2023, 9:51 PM
mlir/docs/BytecodeFormat.md
458

(newline)

mfrancio updated this revision to Diff 524069.May 20 2023, 5:10 PM
  • Adds random number generator seed as pass input to allow test reproducibility
  • Removes the do{}while(is_sorted) from permutation testing - essentially, this allows to verify that sorted uselists remain sorted after a bytecode roundtrip
  • Improves comments of few helper functions
mfrancio marked 2 inline comments as done.May 20 2023, 5:11 PM
mfrancio added inline comments.
mlir/test/lib/IR/TestUseListOrders.cpp
200

Agreed, added!

Can you rebase? The version was just bumped.

mehdi_amini added inline comments.May 20 2023, 8:33 PM
mlir/docs/BytecodeFormat.md
407

Nit: seems like you have spaces at the end of every line here

456

Nit: space at the end of line here as well

mfrancio updated this revision to Diff 524137.May 21 2023, 4:14 PM
mfrancio marked an inline comment as done.

Removed trailing whitespaces and rebased.

mfrancio marked 2 inline comments as done.May 21 2023, 4:17 PM
This revision was automatically updated to reflect the committed changes.

Thanks for the report, seems like a leak in the test, I'll have a fix shortly (building/testing locally)

f6fb639c76ce may be enough to fix it, this bot seems really slow though: any reason ccache isn't enabled?

It's enabled. but it spends most of the time in "check" steps.
Also splitting it into 3 bots, 1 per sanitizer, could be useful.

There is something fishy, this is the build-time:

real	8m51.140s
user	228m58.976s
sys	16m24.143s

That seems far too much for just this patch alone: either the ccache cache is too small, or it isn't setup correctly (maybe wiped between builds?).

From which build/step is this from?

From which build/step is this from?

Found that: asan build from https://lab.llvm.org/buildbot/#/builders/5/builds/33857

From which build/step is this from?

Found that: asan build from https://lab.llvm.org/buildbot/#/builders/5/builds/33857

You can find ccach stat in Info of the bot, hit rate is quite high.
The step is 8 min, usually, it's less, one before is 4. Failed step is "asan check" and it's 30m.

E.g. here ccache was whipped (settings changed) https://lab.llvm.org/buildbot/#/builders/5/builds/33859 and the build is 39m.