Page MenuHomePhabricator

[mlgo][inline] Improve global state tracking
ClosedPublic

Authored by mtrofin on Dec 15 2021, 10:07 PM.

Details

Summary

The global state refers to the number of the nodes currently in the module, and the number of direct calls between nodes, across the module.

Node counts are not a problem; edge counts are because we want strictly the kind of edges that affect inlining (direct calls), and that is not easily obtainable without iteration over the whole module.

This patch avoids relying on analysis invalidation because it turned out to be too aggressive in some cases. It leverages the fact that Node objects are stable - they do not get deleted while cgscc passes are run over the module; and cgscc pass manager invariants.

Diff Detail

Event Timeline

mtrofin created this revision.Dec 15 2021, 10:07 PM
mtrofin requested review of this revision.Dec 15 2021, 10:07 PM
Herald added a project: Restricted Project. · View Herald TranscriptDec 15 2021, 10:07 PM
mtrofin updated this revision to Diff 395060.Dec 17 2021, 12:07 AM

an alternative that is more robust and arguably easier to understand, as it makes no assumption about scc contents after we leave the inliner: any function could change, and we would capture that. The case of node addition, however, is handled the same way.

This looks reasonable although I'm not familiar with this part of the codebase so I'd like for @aeubanks to take a look as well.

llvm/include/llvm/Analysis/MLInlineAdvisor.h
79
llvm/lib/Analysis/MLInlineAdvisor.cpp
171
llvm/test/Transforms/Inline/ML/state-tracking.ll
25

Can you add a newline here?

mtrofin updated this revision to Diff 397617.Jan 5 2022, 9:32 AM
mtrofin marked 2 inline comments as done.

feedback

mtrofin marked an inline comment as done.Jan 5 2022, 9:32 AM

This patch avoids relying on analysis invalidation because it turned out to be too aggressive in some cases.

Can you explain this a bit more?

We shouldn't need to completely recalculate everything when adding a new function. Any new functions have to be children of the current SCC, so we should be able to find them by iterating through the outgoing edges from the current SCC and seeing if we encounter any nodes we haven't seen before.

llvm/include/llvm/Analysis/InlineAdvisor.h
12

do you need this? this is the legacy PM one

llvm/lib/Analysis/MLInlineAdvisor.cpp
146

if ShuttingDown is ever true, that we means the object has already been destructed and calling any method on it is bad.
In general having things done at a distance in the destructor of an analysis seems iffy. Keeping everything in the pass's run method should be doable here, we just need to keep track of the nodes in the most recently visited SCC.

417

newline?

llvm/test/Transforms/Inline/ML/state-tracking-coro.ll
2

I'm not sure I'd want to depend on exact coroutine semantics for these tests especially since it seems like they keep changing
but if we don't do that then I don't think there's any other way to test new functions being added to the call graph
maybe it's ok if these tests aren't run normally and you're fine with keeping these up to date if coroutine semantics/pipelines change

mtrofin marked an inline comment as done.Jan 7 2022, 3:12 PM

I think there are 2 questions, is that correct? If so:

This patch avoids relying on analysis invalidation because it turned out to be too aggressive in some cases.

Can you explain this a bit more?

This refers to the behavior before. Invalidation of the whole analysis (the MLInlineAdvisor one) was still happening too frequently.

We shouldn't need to completely recalculate everything when adding a new function. Any new functions have to be children of the current SCC, so we should be able to find them by iterating through the outgoing edges from the current SCC and seeing if we encounter any nodes we haven't seen before.

I think you're referring here to the behavior in the patch, correct (i.e. not to the quoted sentence in the patch description)?

I would prefer not assuming that SCC passes adding functions relate them to the SCC they are currently processing. I realize that's currently the case, but this assumption made me uncomfortable: I am not sure why this is something that a pass would necessarily respect in the future.

I think there is a partial update approach that is only dependent on the fact that Nodes are only added for the duration of a module-wide cgscc traversal: we remember a "watermark" of the last node and iterate from that watermark up next time we re-enter the inliner. That's a change that can be done incrementally though, from the current change.

llvm/lib/Analysis/MLInlineAdvisor.cpp
146

See the dtor - this just avoids spending time doing inserts due to the abandon-ing of the NotifyOnChangeFunctionAnalysis in the ~MLInlineAdvisor. The object isn't destructed just yet.

mtrofin updated this revision to Diff 398250.Jan 7 2022, 3:19 PM
mtrofin marked 4 inline comments as done.

feedback

llvm/test/Transforms/Inline/ML/state-tracking-coro.ll
2

ack - this is just taking a dep on the coro pass generating a few fcts, I'm hoping that won't change, but if it does and it becomes burdensome, we can cross that bridge then, I think?

aeubanks accepted this revision.Jan 10 2022, 11:20 AM

I think there are 2 questions, is that correct? If so:

This patch avoids relying on analysis invalidation because it turned out to be too aggressive in some cases.

Can you explain this a bit more?

This refers to the behavior before. Invalidation of the whole analysis (the MLInlineAdvisor one) was still happening too frequently.

Oh I thought this was in reference to FunctionPropertiesAnalysis being invalidated too much.

We shouldn't need to completely recalculate everything when adding a new function. Any new functions have to be children of the current SCC, so we should be able to find them by iterating through the outgoing edges from the current SCC and seeing if we encounter any nodes we haven't seen before.

I think you're referring here to the behavior in the patch, correct (i.e. not to the quoted sentence in the patch description)?

I would prefer not assuming that SCC passes adding functions relate them to the SCC they are currently processing. I realize that's currently the case, but this assumption made me uncomfortable: I am not sure why this is something that a pass would necessarily respect in the future.

An SCC pass should not be adding functions that don't relate to some function in the current SCC. That wouldn't fit the CGSCC pass model and would break LCG. So I think looking around all the nodes in the current SCC to discover new functions is fine.

I think there is a partial update approach that is only dependent on the fact that Nodes are only added for the duration of a module-wide cgscc traversal: we remember a "watermark" of the last node and iterate from that watermark up next time we re-enter the inliner. That's a change that can be done incrementally though, from the current change.

later changes sgtm.

llvm/lib/Analysis/MLInlineAdvisor.cpp
146

ah I missed that

llvm/test/Transforms/Inline/ML/state-tracking-scc-splits.ll
5

not related to this patch but you could add this as a lit.local.cfg in the ML directory so you don't have to put it on every test

This revision is now accepted and ready to land.Jan 10 2022, 11:20 AM

I think there are 2 questions, is that correct? If so:

This patch avoids relying on analysis invalidation because it turned out to be too aggressive in some cases.

Can you explain this a bit more?

This refers to the behavior before. Invalidation of the whole analysis (the MLInlineAdvisor one) was still happening too frequently.

We shouldn't need to completely recalculate everything when adding a new function. Any new functions have to be children of the current SCC, so we should be able to find them by iterating through the outgoing edges from the current SCC and seeing if we encounter any nodes we haven't seen before.

I think you're referring here to the behavior in the patch, correct (i.e. not to the quoted sentence in the patch description)?

I would prefer not assuming that SCC passes adding functions relate them to the SCC they are currently processing. I realize that's currently the case, but this assumption made me uncomfortable: I am not sure why this is something that a pass would necessarily respect in the future.

I think there is a partial update approach that is only dependent on the fact that Nodes are only added for the duration of a module-wide cgscc traversal: we remember a "watermark" of the last node and iterate from that watermark up next time we re-enter the inliner. That's a change that can be done incrementally though, from the current change.

I think there are 2 questions, is that correct? If so:

This patch avoids relying on analysis invalidation because it turned out to be too aggressive in some cases.

Can you explain this a bit more?

This refers to the behavior before. Invalidation of the whole analysis (the MLInlineAdvisor one) was still happening too frequently.

Oh I thought this was in reference to FunctionPropertiesAnalysis being invalidated too much.

We shouldn't need to completely recalculate everything when adding a new function. Any new functions have to be children of the current SCC, so we should be able to find them by iterating through the outgoing edges from the current SCC and seeing if we encounter any nodes we haven't seen before.

I think you're referring here to the behavior in the patch, correct (i.e. not to the quoted sentence in the patch description)?

I would prefer not assuming that SCC passes adding functions relate them to the SCC they are currently processing. I realize that's currently the case, but this assumption made me uncomfortable: I am not sure why this is something that a pass would necessarily respect in the future.

An SCC pass should not be adding functions that don't relate to some function in the current SCC. That wouldn't fit the CGSCC pass model and would break LCG. So I think looking around all the nodes in the current SCC to discover new functions is fine.

Ah, ok, so should such a pass try to get introduced, some test(s) would fail, I assume. OK. Let me try and make sure I understand how this check would work:

  • I keep track of the set of Nodes I've seen last, and the total set of Nodes
  • when onPassEntry is called again, I check that the set of Nodes adjacent (through what? Ref or Call edges? I guess both) to the Nodes in the set above are in the total set of Nodes, otherwise I found new nodes

... (kind of obvious what follows)

Is this correct? (thanks!)

I think there is a partial update approach that is only dependent on the fact that Nodes are only added for the duration of a module-wide cgscc traversal: we remember a "watermark" of the last node and iterate from that watermark up next time we re-enter the inliner. That's a change that can be done incrementally though, from the current change.

later changes sgtm.

mtrofin marked 2 inline comments as done.Jan 10 2022, 11:34 AM
mtrofin added inline comments.
llvm/test/Transforms/Inline/ML/state-tracking-scc-splits.ll
5

some tests have REQUIRES: have_tf_api, some have_tf_aot, and some both. ('api' is for training, 'aot' is for deployment compiler, i.e. where we embed a pre-trained model as a .o)

I think there are 2 questions, is that correct? If so:

This patch avoids relying on analysis invalidation because it turned out to be too aggressive in some cases.

Can you explain this a bit more?

This refers to the behavior before. Invalidation of the whole analysis (the MLInlineAdvisor one) was still happening too frequently.

We shouldn't need to completely recalculate everything when adding a new function. Any new functions have to be children of the current SCC, so we should be able to find them by iterating through the outgoing edges from the current SCC and seeing if we encounter any nodes we haven't seen before.

I think you're referring here to the behavior in the patch, correct (i.e. not to the quoted sentence in the patch description)?

I would prefer not assuming that SCC passes adding functions relate them to the SCC they are currently processing. I realize that's currently the case, but this assumption made me uncomfortable: I am not sure why this is something that a pass would necessarily respect in the future.

I think there is a partial update approach that is only dependent on the fact that Nodes are only added for the duration of a module-wide cgscc traversal: we remember a "watermark" of the last node and iterate from that watermark up next time we re-enter the inliner. That's a change that can be done incrementally though, from the current change.

I think there are 2 questions, is that correct? If so:

This patch avoids relying on analysis invalidation because it turned out to be too aggressive in some cases.

Can you explain this a bit more?

This refers to the behavior before. Invalidation of the whole analysis (the MLInlineAdvisor one) was still happening too frequently.

Oh I thought this was in reference to FunctionPropertiesAnalysis being invalidated too much.

We shouldn't need to completely recalculate everything when adding a new function. Any new functions have to be children of the current SCC, so we should be able to find them by iterating through the outgoing edges from the current SCC and seeing if we encounter any nodes we haven't seen before.

I think you're referring here to the behavior in the patch, correct (i.e. not to the quoted sentence in the patch description)?

I would prefer not assuming that SCC passes adding functions relate them to the SCC they are currently processing. I realize that's currently the case, but this assumption made me uncomfortable: I am not sure why this is something that a pass would necessarily respect in the future.

An SCC pass should not be adding functions that don't relate to some function in the current SCC. That wouldn't fit the CGSCC pass model and would break LCG. So I think looking around all the nodes in the current SCC to discover new functions is fine.

Ah, ok, so should such a pass try to get introduced, some test(s) would fail, I assume. OK. Let me try and make sure I understand how this check would work:

  • I keep track of the set of Nodes I've seen last, and the total set of Nodes
  • when onPassEntry is called again, I check that the set of Nodes adjacent (through what? Ref or Call edges? I guess both) to the Nodes in the set above are in the total set of Nodes, otherwise I found new nodes

yeah it could be a ref or a call edge, and theoretically we could add functions that are only referenced from another added function (e.g. A becomes A'->A1->A2), although LCG doesn't currently support that

... (kind of obvious what follows)

Is this correct? (thanks!)

yup sounds right to me

I think there is a partial update approach that is only dependent on the fact that Nodes are only added for the duration of a module-wide cgscc traversal: we remember a "watermark" of the last node and iterate from that watermark up next time we re-enter the inliner. That's a change that can be done incrementally though, from the current change.

later changes sgtm.

mtrofin marked an inline comment as done.Jan 10 2022, 11:41 AM

I think there are 2 questions, is that correct? If so:

This patch avoids relying on analysis invalidation because it turned out to be too aggressive in some cases.

Can you explain this a bit more?

This refers to the behavior before. Invalidation of the whole analysis (the MLInlineAdvisor one) was still happening too frequently.

We shouldn't need to completely recalculate everything when adding a new function. Any new functions have to be children of the current SCC, so we should be able to find them by iterating through the outgoing edges from the current SCC and seeing if we encounter any nodes we haven't seen before.

I think you're referring here to the behavior in the patch, correct (i.e. not to the quoted sentence in the patch description)?

I would prefer not assuming that SCC passes adding functions relate them to the SCC they are currently processing. I realize that's currently the case, but this assumption made me uncomfortable: I am not sure why this is something that a pass would necessarily respect in the future.

I think there is a partial update approach that is only dependent on the fact that Nodes are only added for the duration of a module-wide cgscc traversal: we remember a "watermark" of the last node and iterate from that watermark up next time we re-enter the inliner. That's a change that can be done incrementally though, from the current change.

I think there are 2 questions, is that correct? If so:

This patch avoids relying on analysis invalidation because it turned out to be too aggressive in some cases.

Can you explain this a bit more?

This refers to the behavior before. Invalidation of the whole analysis (the MLInlineAdvisor one) was still happening too frequently.

Oh I thought this was in reference to FunctionPropertiesAnalysis being invalidated too much.

We shouldn't need to completely recalculate everything when adding a new function. Any new functions have to be children of the current SCC, so we should be able to find them by iterating through the outgoing edges from the current SCC and seeing if we encounter any nodes we haven't seen before.

I think you're referring here to the behavior in the patch, correct (i.e. not to the quoted sentence in the patch description)?

I would prefer not assuming that SCC passes adding functions relate them to the SCC they are currently processing. I realize that's currently the case, but this assumption made me uncomfortable: I am not sure why this is something that a pass would necessarily respect in the future.

An SCC pass should not be adding functions that don't relate to some function in the current SCC. That wouldn't fit the CGSCC pass model and would break LCG. So I think looking around all the nodes in the current SCC to discover new functions is fine.

Ah, ok, so should such a pass try to get introduced, some test(s) would fail, I assume. OK. Let me try and make sure I understand how this check would work:

  • I keep track of the set of Nodes I've seen last, and the total set of Nodes
  • when onPassEntry is called again, I check that the set of Nodes adjacent (through what? Ref or Call edges? I guess both) to the Nodes in the set above are in the total set of Nodes, otherwise I found new nodes

yeah it could be a ref or a call edge, and theoretically we could add functions that are only referenced from another added function (e.g. A becomes A'->A1->A2), although LCG doesn't currently support that

... (kind of obvious what follows)

Is this correct? (thanks!)

yup sounds right to me

Oh OK - then I can go back to the first version of this patch, where I didn't need the function pass part (but need this Node accounting)

I think there is a partial update approach that is only dependent on the fact that Nodes are only added for the duration of a module-wide cgscc traversal: we remember a "watermark" of the last node and iterate from that watermark up next time we re-enter the inliner. That's a change that can be done incrementally though, from the current change.

later changes sgtm.

mtrofin updated this revision to Diff 399741.Jan 13 2022, 11:30 AM

Improved handing of "new nodes" - also went back to the first variant of this patch.

mtrofin edited the summary of this revision. (Show Details)Jan 13 2022, 12:55 PM
mtrofin edited the summary of this revision. (Show Details)
aeubanks added inline comments.Jan 13 2022, 1:46 PM
llvm/include/llvm/Analysis/MLInlineAdvisor.h
12

not used?

llvm/lib/Analysis/MLInlineAdvisor.cpp
147

then the pipeline is restarted on the merged SCC

153

or adjacent to other new nodes. no existing passes do this, but it's possible
this isn't properly handled below, but maybe a TODO is good enough for now?

158

does this come up? the CGSCC infra only visits function definitions

164

ditto

mtrofin updated this revision to Diff 399864.Jan 13 2022, 6:29 PM
mtrofin marked 5 inline comments as done.
mtrofin edited the summary of this revision. (Show Details)

feedback

llvm/lib/Analysis/MLInlineAdvisor.cpp
153

fixed.

158

N->isDead could happen if the function for N died since. The second part - not sure, I could imagine a pass converting an implementation to an intrinsic?

164

here I think you're right, this should be an assert.

aeubanks accepted this revision.Jan 18 2022, 9:23 AM

looks good except for the one comment

llvm/lib/Analysis/MLInlineAdvisor.cpp
158

a pass wouldn't replace the node with an intrinsic, every node is required to have a function definition
so I'd remove the check for a function declaration

mtrofin updated this revision to Diff 400885.Jan 18 2022, 9:45 AM
mtrofin marked an inline comment as done.

feedback

llvm/lib/Analysis/MLInlineAdvisor.cpp
158

made into an assert.

This revision was landed with ongoing or failed builds.Jan 18 2022, 9:47 AM
This revision was automatically updated to reflect the committed changes.