Page MenuHomePhabricator

Extended Liveness analysis to support nested regions.

Authored by dfki-mako on Apr 8 2020, 1:45 AM.



The current Liveness analysis does not support operations with nested regions. This causes issues when querying liveness information about blocks nested within operations. Furthermore, the live-in and live-out sets are not computed properly in these cases.

Diff Detail

Event Timeline

dfki-mako created this revision.Apr 8 2020, 1:45 AM
Herald added a project: Restricted Project. · View Herald TranscriptApr 8 2020, 1:45 AM
dfki-mako updated this revision to Diff 255951.Apr 8 2020, 3:39 AM

Addressed formatting issues introduced by clang-format-6.

herhut added a comment.Apr 8 2020, 6:02 AM

This still does not handle the case where values flow through operations (and that is fine, we lack the interface). A good example might be a loop.for with iter_args

I am OK with this to land with the two comments addressed but wait for @rriddle to comment and approve.


What does it mean if there is no ownerBlock. Can this ever happen? It would mean that the use was in a block that does not have the current operation as parent. Values cannot escape regions, though. Maybe rather assert than hiding this case.


Is this a spurious reformat?


Use valueIds here?


I think this would be easier to read if the function arguments were already named %argX in the input. Also, please make the value names unique, either by using the counter or you could use an instruction position trace, using block numbers and trace back via parent ops.

i1@b0@i5 for the second instruction in block zero of the fifth instruction. These are easier to map back to the actual code than global numbers.

In any case, something to make the printout non-ambiguous.

dfki-mako updated this revision to Diff 256233.Apr 9 2020, 3:24 AM
dfki-mako marked 5 inline comments as done.

Applied comments and adapted test cases.

dfki-mako added inline comments.Apr 15 2020, 4:20 AM

Was wrongly formatted.

rriddle requested changes to this revision.Apr 15 2020, 10:49 AM

Thanks for tackling this! Left a few comments.


nit: Use getUsers if you are only accessing the use owners.


Can you just add a utility Region::findAncestorOpInRegion(Operation *op) method that finds the ancestor of an operation within a given region? It's effectively similar to the block variant.


nit: Same here, can you change this to getUsers?


Are you trying to find an ancestor of useOperation that exists within block? Seems like block->findAncestorOpInBlock(useOperation) is intended for this use case.

This revision now requires changes to proceed.Apr 15 2020, 10:49 AM
dfki-mako updated this revision to Diff 258022.Apr 16 2020, 5:17 AM
dfki-mako marked 4 inline comments as done.

Applied comments and refactored findInCurrent functionality.

We have introduced a new utility function

Block *Region::findAncestorBlockInRegion(Block &block)

in order to remove the findInCurrent implementation.

dfki-mako added a project: Restricted Project.Apr 21 2020, 1:58 AM
herhut accepted this revision.Apr 21 2020, 2:18 AM

Thanks for adding this!

rriddle accepted this revision.Apr 21 2020, 2:46 AM
rriddle added inline comments.

nit: ancestor block -> ancestor

(There are a lot of 'block's in that sentence)


Can you reflow these comments to wrap at 80 characters.

This revision is now accepted and ready to land.Apr 21 2020, 2:46 AM
dfki-mako updated this revision to Diff 258956.Apr 21 2020, 3:31 AM
dfki-mako marked 2 inline comments as done.

Reformatted and upated comments.

This revision was automatically updated to reflect the committed changes.