[CallGraphUpdater] Remove some legacy pass manager support (#98362)

We don't have any legacy pass manager CGSCC passes that modify the call
graph (we only use it in the codegen pipeline to run func

[CallGraphUpdater] Remove some legacy pass manager support (#98362)

We don't have any legacy pass manager CGSCC passes that modify the call
graph (we only use it in the codegen pipeline to run function passes in
call graph order). This is the beginning of removing CallGraphUpdater
and making all the relevant CGSCC passes directly use the new pass
manager APIs.

show more ...

[CGSCC] Remove CGSCCUpdateResult::InvalidatedRefSCCs (#98213)

The RefSCC that a function marked dead is in may still contain valid
SCCs that we want to visit. We rely on InvalidatedSCCs to skip SCC

[CGSCC] Remove CGSCCUpdateResult::InvalidatedRefSCCs (#98213)

The RefSCC that a function marked dead is in may still contain valid
SCCs that we want to visit. We rely on InvalidatedSCCs to skip SCCs
containing dead functions.

The addition of RefSCCs in CallGraphUpdater to InvalidatedRefSCCs was
causing asserts as reported in #94815. Fix some more CallGraphUpdater
function deletion methods as well.

show more ...

[CGSCC] Fix compile time blowup with large RefSCCs (#94815)

In some modules, e.g. Kotlin-generated IR, we end up with a huge RefSCC
and the call graph updates done as a result of the inliner take a

[CGSCC] Fix compile time blowup with large RefSCCs (#94815)

In some modules, e.g. Kotlin-generated IR, we end up with a huge RefSCC
and the call graph updates done as a result of the inliner take a long
time. This is due to RefSCC::removeInternalRefEdges() getting called
many times, each time removing one function from the RefSCC, but each
call to removeInternalRefEdges() is proportional to the size of the
RefSCC.

There are two places that call removeInternalRefEdges(), in
updateCGAndAnalysisManagerForPass() and
LazyCallGraph::removeDeadFunction().

1) Since LazyCallGraph can deal with spurious (edges that exist in the
graph but not in the IR) ref edges, we can simply not call
removeInternalRefEdges() in updateCGAndAnalysisManagerForPass().

2) LazyCallGraph::removeDeadFunction() still ends up taking the brunt of
compile time with the above change for the original reason. So instead
we batch all the dead function removals so we can call
removeInternalRefEdges() just once. This requires some changes to
callers of removeDeadFunction() to not actually erase the function from
the module, but defer it to when we batch delete dead functions at the
end of the CGSCC run, leaving the function body as "unreachable" in the
meantime. We still need to ensure that call edges are accurate. I had
also tried deleting dead functions after visiting a RefSCC, but deleting
them all at once at the end was simpler.

Many test changes are due to not performing unnecessary revisits of an
SCC (the CGSCC infrastructure deems ref edge refinements as unimportant
when it comes to revisiting SCCs, although that seems to not be
consistently true given these changes) because we don't remove some ref
edges. Specifically for devirt-invalidated.ll this seems to expose an
inlining order issue with the inliner. Probably unimportant for this
type of intentionally weird call graph.

Compile time:
https://llvm-compile-time-tracker.com/compare.php?from=6f2c61071c274a1b5e212e6ad4114641ec7c7fc3&to=b08c90d05e290dd065755ea776ceaf1420680224&stat=instructions:u

show more ...

[Attributor][FIX] Ensure the function manager cache is updated

When a function is removed we need to clear cached analysis from the
function manager cache.

Use PoisonValue instead of UndefValue when RAUWing unreachable code [NFC]

Replacing the following instances of UndefValue with PoisonValue, where the UndefValue is used as an arbitrary value:

- llv

Use PoisonValue instead of UndefValue when RAUWing unreachable code [NFC]

Replacing the following instances of UndefValue with PoisonValue, where the UndefValue is used as an arbitrary value:

- llvm/lib/CodeGen/WinEHPrepare.cpp
`demotePHIsOnFunclets`: RAUW arbitrary value for lingering uses of removed PHI nodes

- llvm/lib/Transforms/Utils/BasicBlockUtils.cpp
`FoldSingleEntryPHINodes`: Removes a self-referential single entry phi node.

- llvm/lib/Transforms/Utils/CallGraphUpdater.cpp
`finalize`: Remove all references to removed functions.

- llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp
`cleanup`: the result is not used then the inserted instructions are removed.

- llvm/tools/bugpoint/CrashDebugger.cpp
`TestInts`: the program is cloned and instructions are removed to narrow down source of crash.

Differential Revision: https://reviews.llvm.org/D133640

show more ...

Cleanup includes: TransformsUtils

Estimation on the impact on preprocessor output:
before: 1065307662
after: 1064800684

Discourse thread: https://discourse.llvm.org/t/include-what-you-use-include-

Cleanup includes: TransformsUtils

Estimation on the impact on preprocessor output:
before: 1065307662
after: 1064800684

Discourse thread: https://discourse.llvm.org/t/include-what-you-use-include-cleanup
Differential Revision: https://reviews.llvm.org/D120741

show more ...

[NFC] Remove unnecessary "#include"s from header files

[ModuleUtils] Remove dead arg from filterDeadComdatFunctions() (NFC)

The module argument is no longer used.

[CGSCC][Coroutine][NewPM] Properly support function splitting/outlining

Previously when trying to support CoroSplit's function splitting, we
added in a hack that simply added the new function's node

[CGSCC][Coroutine][NewPM] Properly support function splitting/outlining

Previously when trying to support CoroSplit's function splitting, we
added in a hack that simply added the new function's node into the
original function's SCC (https://reviews.llvm.org/D87798). This is
incorrect since it might be in its own SCC.

Now, more similar to the previous design, we have callers explicitly
notify the LazyCallGraph that a function has been split out from another
one.

In order to properly support CoroSplit, there are two ways functions can
be split out.

One is the normal expected "outlining" of one function into a new one.
The new function may only contain references to other functions that the
original did. The original function must reference the new function. The
new function may reference the original function, which can result in
the new function being in the same SCC as the original function. The
weird case is when the original function indirectly references the new
function, but the new function directly calls the original function,
resulting in the new SCC being a parent of the original function's SCC.
This form of function splitting works with CoroSplit's Switch ABI.

The second way of splitting is more specific to CoroSplit. CoroSplit's
Retcon and Async ABIs split the original function into multiple
functions that all reference each other and are referenced by the
original function. In order to keep the LazyCallGraph in a valid state,
all new functions must be processed together, else some nodes won't be
populated. To keep things simple, this only supports the case where all
new edges are ref edges, and every new function references every other
new function. There can be a reference back from any new function to the
original function, putting all functions in the same RefSCC.

This also adds asserts that all nodes in a (Ref)SCC can reach all other
nodes to prevent future incorrect hacks.

The original hacks in https://reviews.llvm.org/D87798 are no longer
necessary since all new functions should have been registered before
calling updateCGAndAnalysisManagerForPass.

This fixes all coroutine tests when opt's -enable-new-pm is true by
default. This also fixes PR48190, which was likely due to the previous
hack breaking SCC invariants.

Reviewed By: rnk

Differential Revision: https://reviews.llvm.org/D93828

show more ...

[NewPM][CGSCC] Handle newly added functions in updateCGAndAnalysisManagerForPass

This seems to fit the CGSCC updates model better than calling
addNewFunctionInto{Ref,}SCC() on newly created/outlined

[NewPM][CGSCC] Handle newly added functions in updateCGAndAnalysisManagerForPass

This seems to fit the CGSCC updates model better than calling
addNewFunctionInto{Ref,}SCC() on newly created/outlined functions.
Now addNewFunctionInto{Ref,}SCC() are no longer necessary.

However, this doesn't work on newly outlined functions that aren't
referenced by the original function. e.g. if a() was outlined into b()
and c(), but c() is only referenced by b() and not by a(), this will
trigger an assert.

This also fixes an issue I was seeing with newly created functions not
having passes run on them.

Ran check-llvm with expensive checks.

Reviewed By: asbirlea

Differential Revision: https://reviews.llvm.org/D87798

show more ...

[CallGraph] Add support for callback call sites

Summary:
This patch changes call graph analysis to recognize callback call sites
and add an artificial 'reference' call record from the broker functio

[CallGraph] Add support for callback call sites

Summary:
This patch changes call graph analysis to recognize callback call sites
and add an artificial 'reference' call record from the broker function
caller to the callback function in the call graph. A presence of such
reference enforces bottom-up traversal order for callback functions in
CG SCC pass manager because callback function logically becomes a callee
of the broker function caller.

Reviewers: jdoerfert, hfinkel, sstefan1, baziotis

Reviewed By: jdoerfert

Subscribers: hiraditya, kuter, sstefan1, llvm-commits

Tags: #llvm

Differential Revision: https://reviews.llvm.org/D82572

show more ...

[NewPassManager] Add assertions when getting statefull cached analysis.

Summary:
Analyses that are statefull should not be retrieved through a proxy from
an outer IR unit, as these analyses are only

[NewPassManager] Add assertions when getting statefull cached analysis.

Summary:
Analyses that are statefull should not be retrieved through a proxy from
an outer IR unit, as these analyses are only invalidated at the end of
the inner IR unit manager.
This patch disallows getting the outer manager and provides an API to
get a cached analysis through the proxy. If the analysis is not
stateless, the call to getCachedResult will assert.

Reviewers: chandlerc

Subscribers: mehdi_amini, eraman, hiraditya, zzheng, llvm-commits

Tags: #llvm

Differential Revision: https://reviews.llvm.org/D72893

show more ...

[CallGraphUpdater] Removed references to calles when deleting function

Summary: Otherwise we can get unaccounted references to call graph nodes.

Reviewers: jdoerfert, sstefan1

Reviewed By: jdoerfe

[CallGraphUpdater] Removed references to calles when deleting function

Summary: Otherwise we can get unaccounted references to call graph nodes.

Reviewers: jdoerfert, sstefan1

Reviewed By: jdoerfert

Subscribers: hiraditya, llvm-commits

Tags: #llvm

Differential Revision: https://reviews.llvm.org/D79382

show more ...

[CallGraphUpdater][NFC] Minor updates to D77855

I uploaded the old version accidentally instead of the one with these
minor adjustments requested by the reviewers.

Differential Revision: https://re

[CallGraphUpdater][NFC] Minor updates to D77855

I uploaded the old version accidentally instead of the one with these
minor adjustments requested by the reviewers.

Differential Revision: https://reviews.llvm.org/D77855

show more ...

[CallGraphUpdater] Remove nodes from their SCC (old PM)

Summary:
We can and should remove deleted nodes from their respective SCCs. We
did not do this before and this was a potential problem even th

[CallGraphUpdater] Remove nodes from their SCC (old PM)

Summary:
We can and should remove deleted nodes from their respective SCCs. We
did not do this before and this was a potential problem even though I
couldn't locally trigger an issue. Since the `DeleteNode` would assert
if the node was not in the SCC, we know we only remove nodes from their
SCC and only once (when run on all the Attributor tests).

Reviewers: lebedev.ri, hfinkel, fhahn, probinson, wristow, loladiro, sstefan1, uenoku

Subscribers: hiraditya, bollu, uenoku, llvm-commits

Tags: #llvm

Differential Revision: https://reviews.llvm.org/D77855

show more ...

[CallGraphUpdater] Update the ExternalCallingNode for node replacements

Summary:
While it is uncommon that the ExternalCallingNode needs to be updated,
it can happen. It is uncommon because most fun

[CallGraphUpdater] Update the ExternalCallingNode for node replacements

Summary:
While it is uncommon that the ExternalCallingNode needs to be updated,
it can happen. It is uncommon because most functions listed as callees
have external linkage, modifying them is usually not allowed. That said,
there are also internal functions that have, or better had, their
"address taken" at construction time. We conservatively assume various
uses cause the address "to be taken". Furthermore, the user might have
become dead at some point. As a consequence, transformations, e.g., the
Attributor, might be able to replace a function that is listed
as callee of the ExternalCallingNode.

Since there is no function corresponding to the ExternalCallingNode, we
did just remove the node from the callee list if we replaced it (so
far). Now it would be preferable to replace it if needed and remove it
otherwise. However, removing the node has implications on the CGSCC
iteration. Locally, that caused some other nodes to be never visited
but it is for sure possible other (bad) side effects can occur. As it
seems conservatively safe to keep the new node in the callee list we
will do that for now.

Reviewers: lebedev.ri, hfinkel, fhahn, probinson, wristow, loladiro, sstefan1, uenoku

Subscribers: hiraditya, bollu, uenoku, llvm-commits

Tags: #llvm

Differential Revision: https://reviews.llvm.org/D77854

show more ...

[CallGraphUpdater] Properly remove strongly connected components (oldPM)

Summary:
The old code did eliminate references from and to functions that were
about to be deleted only just before we delete

[CallGraphUpdater] Properly remove strongly connected components (oldPM)

Summary:
The old code did eliminate references from and to functions that were
about to be deleted only just before we deleted them. This can cause
references from other functions that are supposed to be deleted to still
exist, depending on the order. If the functions form a strongly
connected component the problem manifests regardless of the order in
which we try to actually delete the functions.

This patch introduces a two step deletion. First we remove all
references and then we delete the function. Note that this only affects
the old call graph. There should not be any functional changes if no old
style call graph was given.

To test this we delete two strongly connected functions instead of one
in an existing test.

Reviewers: hfinkel

Subscribers: hiraditya, bollu, llvm-commits

Tags: #llvm

Differential Revision: https://reviews.llvm.org/D77975

show more ...

[CallGraphUpdater] Remove dead constants before replacing a function

Dead constants might be left when a function is replaced, we can
gracefully handle this case and avoid complexity for the users w

[CallGraphUpdater] Remove dead constants before replacing a function

Dead constants might be left when a function is replaced, we can
gracefully handle this case and avoid complexity for the users who would
see an assertion otherwise.

show more ...

[Attributor] Derive memory location attributes (argmemonly, ...)

In addition to memory behavior attributes (readonly/writeonly) we now
derive memory location attributes (argmemonly/inaccessiblememon

[Attributor] Derive memory location attributes (argmemonly, ...)

In addition to memory behavior attributes (readonly/writeonly) we now
derive memory location attributes (argmemonly/inaccessiblememonly/...).
The former is part of AAMemoryBehavior and the latter part of
AAMemoryLocation. While they are similar in nature it got messy when
they were put in a single AA. Location attributes for arguments and
floating values will follow later.

Note that both memory attributes kinds can derive readnone. If there are
no accesses AAMemoryBehavior will derive readnone. If there are accesses
but only to stack (=local) locations AAMemoryLocation will derive
readnone.

Reviewed By: uenoku

Differential Revision: https://reviews.llvm.org/D73426

show more ...

Introduce a CallGraph updater helper class

The CallGraphUpdater is a helper that simplifies the process of updating
the call graph, both old and new style, while running an CGSCC pass.

The uses are

Introduce a CallGraph updater helper class

The CallGraphUpdater is a helper that simplifies the process of updating
the call graph, both old and new style, while running an CGSCC pass.

The uses are contained in different commits, e.g. D70767.

More functionality is added as we need it.

Reviewed By: modocache, hfinkel

Differential Revision: https://reviews.llvm.org/D70927

show more ...