This is an archive of the discontinued LLVM Phabricator instance.

[MLIR][ANALYSIS] Add liveness analysis utility
ClosedPublic

Authored by srishti-pm on Jun 26 2023, 8:25 AM.

Details

Summary

This commit adds a utility to implement liveness analysis using the
sparse backward data-flow analysis framework. Theoretically, liveness
analysis assigns liveness to each (value, program point) pair in the
program and it is thus a dense analysis. However, since values are
immutable in MLIR, a sparse analysis, which will assign liveness to
each value in the program, suffices here.

Liveness analysis has many applications. It can be used to avoid the
computation of extraneous operations that have no effect on the memory
or the final output of a program. It can also be used to optimize
register allocation. Both of these applications help achieve one very
important goal: reducing runtime.

A value is considered "live" iff it:

(1) has memory effects OR
(2) is returned by a public function OR
(3) is used to compute a value of type (1) or (2).

It is also to be noted that a value could be of multiple types (1/2/3) at
the same time.

A value "has memory effects" iff it:

(1.a) is an operand of an op with memory effects OR
(1.b) is a non-forwarded branch operand and a block where its op could
take the control has an op with memory effects.

A value A is said to be "used to compute" value B iff B cannot be
computed in the absence of A. Thus, in this implementation, we say that
value A is used to compute value B iff:

(3.a) `B` is a result of an op with operand `A` OR
(3.b) `A` is used to compute some value `C` and `C` is used to compute
`B`.

It is important to note that there already exists an MLIR liveness
utility here: llvm-project/mlir/include/mlir/Analysis/Liveness.h. So,
what is the need for this new liveness analysis utility being added by
this commit? That need is explained as follows:-

The similarities between these two utilities is that both use the
fixpoint iteration method to converge to the final result of liveness.
And, both have the same theoretical understanding of liveness as well.

However, the main difference between (a) the existing utility and (b)
the added utility is the "scope of the analysis". (a) is restricted to
analysing each block independently while (b) analyses blocks together,
i.e., it looks at how the control flows from one block to the other,
how a caller calls a callee, etc. The restriction in the former implies
that some potentially non-live values could be marked live and thus the
full potential of liveness analysis will not be realised.

This can be understood using the example below:

1 func.func private @private() -> (i32, i32) {
2   %0 = arith.constant 0 : i32
3   %1 = arith.addi %0, %0 : i32
4   return %0, %1 : i32, i32
5 }
6 func.func @public() -> (i32) {
7   %0:2 = func.call @private() : () -> (i32, i32)
8   return %0#0 : i32
9 }

Here, if we just restrict our analysis to a per-block basis like (a), we
will say that the %1 on line 3 is live because it is computed and then
returned outside its block by the function. But, if we perform a
backward data-flow analysis like (b) does, we will say that %0#1 of line
7 is not live because it isn't returned by the public function and thus,
%1 of line 3 is also not live. So, while (a) will be unable to suggest
any IR optimizations, (b) can enable this IR to convert to:-

1 func.func private @private() -> i32 {
2   %0 = arith.constant 0 : i32
3   return %0 : i32
4 }
5 func.func @public() -> i32 {
6   %0 = call @private() : () -> i32
7   return %0 : i32
8 }

One operation was removed and one unnecessary return value of the
function was removed and the function signature was modified. This is an
optimization that (b) can enable but (a) cannot. Such optimizations can
help remove a lot of extraneous computations that are currently being
done.

Signed-off-by: Srishti Srivastava <srishtisrivastava.ai@gmail.com>

Diff Detail

Event Timeline

srishti-pm created this revision.Jun 26 2023, 8:25 AM
Herald added a project: Restricted Project. · View Herald TranscriptJun 26 2023, 8:25 AM
srishti-pm edited the summary of this revision. (Show Details)Jun 26 2023, 8:27 AM

Fix typo in commit message.

Make the analysis less rigid by checking memory effects instead of
comparing with the memref.store op.

srishti-pm edited the summary of this revision. (Show Details)Jun 26 2023, 2:25 PM

Fix typo in documentation.

srishti-pm edited the summary of this revision. (Show Details)Jun 27 2023, 11:24 AM

Finish the todo marked earlier in the code to match the theoretical
definition of "live" with its implementation here.

srishti-pm edited the summary of this revision. (Show Details)Jun 30 2023, 12:23 PM
srishti-pm added reviewers: aartbik, jpienaar, phisiart.
srishti-pm published this revision for review.Jun 30 2023, 12:31 PM

Rebased to main.

srishti-pm edited the summary of this revision. (Show Details)Jun 30 2023, 1:12 PM
srishti-pm edited the summary of this revision. (Show Details)

Add more background in the commit description.

jcai19 added a subscriber: jcai19.Jun 30 2023, 1:56 PM
jcai19 added inline comments.
mlir/lib/Analysis/DataFlow/LivenessAnalysis.cpp
39

Can you please copy the comments that explain what are (a) (b) (c) and (d) in LivenessAnalysis.h here as well?

Address comments.

srishti-pm marked an inline comment as done.Jun 30 2023, 2:04 PM
srishti-pm added inline comments.
mlir/lib/Analysis/DataFlow/LivenessAnalysis.cpp
39

Done

Can LivenessAnalysis be used as a standard analysis?

LivenessAnalysis &otherAnalysis = am.getAnalysis<LivenessAnalysis>();
if (otherAnalysis.isLive(aValue) {
}
mlir/test/lib/Analysis/DataFlow/TestLivenessAnalysis.cpp
45

You don't test LivenessAnalysis in isolation, but with dead code analysis and sparse constant propagation?

srishti-pm marked 2 inline comments as done.Jul 1 2023, 2:12 PM
srishti-pm added inline comments.
mlir/test/lib/Analysis/DataFlow/TestLivenessAnalysis.cpp
45

You don't test LivenessAnalysis in isolation, but with dead code analysis and sparse constant propagation?

No, liveness analysis is being tested in isolation (i.e., only "isLive" values are printed for different SSA values in the tests).

But the reason that DeadCodeAnalysis and SparseConstantPropagation are loaded is the presence of a bug in the sparse backward data-flow analysis framework.

As mentioned in the commit, liveness analysis uses this framework to execute. This framework allows a lot of things to be taken care of in the backend so that any analysis, like liveness analysis doesn't have to implement much on its own. An analysis just needs to define how and what values propagate and what the dependencies between values are. And the framework takes care of the rest. The bug in the framework is that it (wrongly) depends on DeadCodeAnalysis and SparseConstantPropagation to correctly work.

I think there is ongoing work/discussion to fix this bug and that fixing should happen in a way that the implementation of liveness analysis here would not change. The only change that should happen is that we will then (correctly) no longer load the DeadCodeAnalysis and SparseConstantPropagation to be able to test liveness analysis.

This is my understanding of the situation. @matthiaskramm, requesting you to kindly let me know if anything I mentioned here is incorrect and also please share your views on the matter!

srishti-pm updated this revision to Diff 537534.Jul 5 2023, 3:54 PM
srishti-pm marked an inline comment as done.

Rebased to main.

jpienaar added inline comments.Jul 7 2023, 3:43 PM
mlir/include/mlir/Analysis/DataFlow/LivenessAnalysis.h
2

You'll need -*- C++ -*- for header files to be able to differentiate between C and C++ headers.

28

Feel free to use C++17's namespace mlir::dataflow form

42

Could we keep this closer to include/mlir/Analysis/DataFlow/DeadCodeAnalysis.h in naming below?

mlir/lib/Analysis/DataFlow/LivenessAnalysis.cpp
26

Is this-> needed?

66

So this is conservative in marking live?

mlir/test/Analysis/DataFlow/test-liveness-analysis.mlir
1

Is there an example/test here that shows difference between this and Analysis/Liveness.h ?

srishti-pm updated this revision to Diff 538468.Jul 9 2023, 5:00 PM
srishti-pm marked 3 inline comments as done.

Address review comments.

srishti-pm added inline comments.Jul 9 2023, 5:02 PM
mlir/include/mlir/Analysis/DataFlow/LivenessAnalysis.h
2

Done.

28

Done.

42

Do you mean that I could replace the name "Liveness" with "Executable"?

mlir/lib/Analysis/DataFlow/LivenessAnalysis.cpp
26

No, it wasn't! Removed it, thanks!

66

That is correct. It is conservative in marking live.

Being conservative in marking live is not safe. It could lead to the removal of operations that are actually live but were marked non-live because of the conservatism.

The safe thing to do in liveness analysis is being conservative in marking non-live.

If we do not want an unsafe analysis to go into the codebase, we could do two things here:-
(1) For region-based control flow ops, mark their non-forwarded operands as live always.
OR
(2) Do what is mentioned in the TODO.

Both (1) and (2) are conservative in marking non-live. Thus, both are safe. (1) is more conservative in marking non-live than (2). Thus, (2) can enable more optimizations than (1).

I'll thus finish the TODO in this patch itself so we do not add an unsafe analysis into the codebase.

Does that seem okay?

srishti-pm added a comment.EditedJul 9 2023, 5:25 PM

Can LivenessAnalysis be used as a standard analysis?

LivenessAnalysis &otherAnalysis = am.getAnalysis<LivenessAnalysis>();
if (otherAnalysis.isLive(aValue) {
}

I'm not sure. I didn't know about analysis and thus I read about it now. It appears as though we can only possibly add dependencies between parent and child operations (thus between any ancestor and any successor). But liveness analysis also requires us to add other dependencies, for example, a dependency between a caller and a callee (for example, in functions). Will there be a provision to add such a dependency in analysis? Based on what I read so far, there doesn't appear to be such a provision but I could be wrong.

I believe you could add a wrapper pass:

class LivenessAnalysis {
public:
  LivenessAnalysis(mlir::ModuleOp *module) {
    // run Dataflowsolver with liveness
  }

  bool isLive(mlir::Value *val) {
  }
private:
  // store result from data flow run
};

Complete the TODO

srishti-pm edited the summary of this revision. (Show Details)Jul 13 2023, 8:30 AM
srishti-pm edited the summary of this revision. (Show Details)
srishti-pm marked an inline comment as done.

Add a unit test that shows the difference of this added utility from the
existing liveness utility at llvm-project/mlir/include/mlir/Analysis/Liveness.h

srishti-pm marked an inline comment as done.Jul 13 2023, 9:03 AM
srishti-pm added inline comments.
mlir/lib/Analysis/DataFlow/LivenessAnalysis.cpp
66

This is done. It is no longer conservative in marking live. I have tried to cover all cases of liveness I could think of.

mlir/test/Analysis/DataFlow/test-liveness-analysis.mlir
1

Yes, just added: @test_9_negative().

srishti-pm marked an inline comment as done.

Make liveness analysis a standard analysis.

I believe you could add a wrapper pass:

class LivenessAnalysis {
public:
  LivenessAnalysis(mlir::ModuleOp *module) {
    // run Dataflowsolver with liveness
  }

  bool isLive(mlir::Value *val) {
  }
private:
  // store result from data flow run
};

Done! :)

srishti-pm edited the summary of this revision. (Show Details)Jul 13 2023, 12:06 PM

Nit changes

srishti-pm added a comment.EditedJul 13 2023, 12:14 PM

All comments on this revision are addressed and/or answered @tschuett @jcai19 @jpienaar

CC: @matthiaskramm

matthiaskramm accepted this revision.Jul 13 2023, 12:52 PM
This revision is now accepted and ready to land.Jul 13 2023, 12:52 PM

The build was successful. Can this be landed? @matthiaskramm @tschuett @jcai19 @jpienaar

A gentle reminder to @tschuett @jcai19 @jpienaar to kindly let me know if this can be landed or if there are any more comments to be given here :)
CC: @matthiaskramm

jcai19 accepted this revision.Jul 17 2023, 1:29 PM

We are planning on landing this in the next 24 hours @tschuett @jpienaar. Kindly let me know if you have any follow up comments after I had addressed your comments here, or even new comments. I'm thinking that if we don't get comments in the next 24 hours, we'll land this. It's accepted by @matthiaskramm and @jcai19.

Fixed 2 errors I caught while reviewing the implementation again
and doing more testing.

Error 1: All operands of a branching operation were being marked
live if at least one result was live. This was obviously incorrect
and not our intention at all. Fixed it.

Error 2: The non-forwarded branch operand of ops of interface
RegionBranchTerminatorOpInterface were being marked "not live"
even when they were live because they were incorrectly only relying
this op's results instead of also relying on the op's parent's
results. Fixed it as well.

Rebased to main.

This revision was automatically updated to reflect the committed changes.

Thanks for providing extended documentation in the commit description, and more importantly propagating this useful information as code comments! Nice work.

Thanks for providing extended documentation in the commit description, and more importantly propagating this useful information as code comments! Nice work.

Thanks for the appreciation. Means a lot :)

srishti-pm edited the summary of this revision. (Show Details)Aug 17 2023, 8:41 PM