This is an archive of the discontinued LLVM Phabricator instance.

[MLIR][Liveness] Add `currentlyLiveValues`, a way to get a set of values that are live as of a given operation.
ClosedPublic

Authored by bzcheeseman on Jul 10 2022, 8:28 AM.

Details

Summary

This change allows the user of LivenessBlockInfo to specify an op within the block and get a set of all values that are live as of that op. Semantically it relies on having a dominance-based region that has ordered operations. For DFG regions, computing liveness statically this way doesn't really make sense, it likely needs to be done at runtime.

Diff Detail

Event Timeline

bzcheeseman created this revision.Jul 10 2022, 8:28 AM
Herald added a project: Restricted Project. · View Herald TranscriptJul 10 2022, 8:28 AM
bzcheeseman requested review of this revision.Jul 10 2022, 8:28 AM

I had also considered a version of this patch that iterated the block with a set of refcounts for each value - that also works but this version felt a little closer to the way that the rest of the analysis is performed. I'm totally fine either way, happy to update the patch to use the other method.

rriddle added inline comments.Jul 12 2022, 3:22 AM
mlir/include/mlir/Analysis/Liveness.h
154

This is building a map from every operation to every value that is live over that operation? This feels extremely expensive. I'm not really sure this scales beyond simple cases.

mlir/lib/Analysis/Liveness.cpp
396

This is returning a copy of the set? I would have expected a reference, a copy is going to be expensive.

bzcheeseman added inline comments.Jul 12 2022, 8:24 AM
mlir/include/mlir/Analysis/Liveness.h
154

Yep, it is pretty expensive. The other option I can think of is to keep a simpler data structure and make the query operation do some of the computation which I'm not a huge fan of because you'd pay the cost of walking the block repeatedly - both options are bad in extreme cases I think?

mlir/lib/Analysis/Liveness.cpp
396

Good point, should be a const reference. I'll fix it.

bzcheeseman added inline comments.Jul 12 2022, 5:28 PM
mlir/lib/Analysis/Liveness.cpp
396

Actually, with the changes making this do the analysis on-demand, we no longer can keep a reference to this so we have to return it by value.

rriddle added inline comments.Jul 12 2022, 5:34 PM
mlir/lib/Analysis/Liveness.cpp
398

Why do we need this here? Can't we just have ValueSetT variable and ignore the cases we don't care about (i.e. any other op)?

407–413

Can you rework to have control flow like this? Having the assignments so close together for me mitigates the need for an assert.

439

nit: Can you spell out auto on each of these?

450

nit: op? o isn't really used to refer to operation variables anywhere else.

bzcheeseman added inline comments.Jul 12 2022, 6:01 PM
mlir/lib/Analysis/Liveness.cpp
398

That's a good point! I'll fix this.

407–413

works for me!

439

sure thing :)

450

op is the argument to the function so I needed a different name. I can switch to something like walkOp?

rriddle added inline comments.Jul 13 2022, 10:29 AM
mlir/lib/Analysis/Liveness.cpp
436–437

Do you need to check live outs? Wouldn't those already be covered by checking live-ins+ops within the block?

441

walk is recursive, but for the sake of this computation you don't want that right?

442–443

If you are already tracking live ins, do you need to check the operands of each op? I would expect that checking live-ins+results of operations in the block would give you what you need.

bzcheeseman added inline comments.Jul 13 2022, 10:34 AM
mlir/lib/Analysis/Liveness.cpp
436–437

You're right, an old implementation did need it but this one does not. I think at one point I had a bad version of the live range checking and improving that has made this unnecessary.

441

Actually I do want that - the scf.for example is one where I want to know the values that are live *within* the loop as well.

442–443

same as above - at one point I improved the live range thing and didn't realize I didn't need this :)

rriddle added inline comments.Jul 13 2022, 11:03 AM
mlir/lib/Analysis/Liveness.cpp
441

For nested operations though, we would handle them differently that operations in the current block, right?

bzcheeseman added inline comments.Jul 13 2022, 11:57 AM
mlir/lib/Analysis/Liveness.cpp
441

I mean for a concrete example, in the scf.for loop below it's useful to have a list of values that are live even only for the body of the loop. That's the main reason for it - that's the semantic that I needed in the past. That said, for the current use case I have in mind, the operation that I want this analysis for doesn't have nested ops so I'm semi-okay with changing the semantics, we just gotta agree that's the way to move forward.

rriddle accepted this revision.Jul 15 2022, 6:38 PM
This revision is now accepted and ready to land.Jul 15 2022, 6:38 PM

clang-format isn't happy, please look into that.

clang-format isn't happy, please look into that.

Done, thanks :)