|
Revision tags: llvmorg-20.1.0, llvmorg-20.1.0-rc3, llvmorg-20.1.0-rc2, llvmorg-20.1.0-rc1, llvmorg-21-init, llvmorg-19.1.7, llvmorg-19.1.6, llvmorg-19.1.5, llvmorg-19.1.4, llvmorg-19.1.3, llvmorg-19.1.2, llvmorg-19.1.1, llvmorg-19.1.0, llvmorg-19.1.0-rc4, llvmorg-19.1.0-rc3, llvmorg-19.1.0-rc2, llvmorg-19.1.0-rc1, llvmorg-20-init, llvmorg-18.1.8, llvmorg-18.1.7, llvmorg-18.1.6, llvmorg-18.1.5, llvmorg-18.1.4, llvmorg-18.1.3, llvmorg-18.1.2, llvmorg-18.1.1, llvmorg-18.1.0, llvmorg-18.1.0-rc4, llvmorg-18.1.0-rc3, llvmorg-18.1.0-rc2, llvmorg-18.1.0-rc1, llvmorg-19-init, llvmorg-17.0.6, llvmorg-17.0.5, llvmorg-17.0.4, llvmorg-17.0.3, llvmorg-17.0.2, llvmorg-17.0.1, llvmorg-17.0.0, llvmorg-17.0.0-rc4, llvmorg-17.0.0-rc3, llvmorg-17.0.0-rc2, llvmorg-17.0.0-rc1, llvmorg-18-init, llvmorg-16.0.6, llvmorg-16.0.5, llvmorg-16.0.4, llvmorg-16.0.3, llvmorg-16.0.2, llvmorg-16.0.1, llvmorg-16.0.0, llvmorg-16.0.0-rc4, llvmorg-16.0.0-rc3, llvmorg-16.0.0-rc2, llvmorg-16.0.0-rc1, llvmorg-17-init, llvmorg-15.0.7, llvmorg-15.0.6, llvmorg-15.0.5, llvmorg-15.0.4, llvmorg-15.0.3, llvmorg-15.0.2, llvmorg-15.0.1, llvmorg-15.0.0, llvmorg-15.0.0-rc3, llvmorg-15.0.0-rc2, llvmorg-15.0.0-rc1, llvmorg-16-init, llvmorg-14.0.6, llvmorg-14.0.5, llvmorg-14.0.4, llvmorg-14.0.3, llvmorg-14.0.2, llvmorg-14.0.1, llvmorg-14.0.0, llvmorg-14.0.0-rc4, llvmorg-14.0.0-rc3, llvmorg-14.0.0-rc2, llvmorg-14.0.0-rc1, llvmorg-15-init, llvmorg-13.0.1, llvmorg-13.0.1-rc3, llvmorg-13.0.1-rc2, llvmorg-13.0.1-rc1 |
|
| #
029f1a53 |
| 20-Oct-2021 |
Arthur Eubanks <[email protected]> |
[LazyCallGraph] Skip blockaddresses
blockaddresses do not participate in the call graph since the only instructions that use them must all return to someplace within the current function. And passes
[LazyCallGraph] Skip blockaddresses
blockaddresses do not participate in the call graph since the only instructions that use them must all return to someplace within the current function. And passes cannot retrieve a function address from a blockaddress.
This was suggested by efriedma in D58260.
Fixes PR50881.
Reviewed By: nickdesaulniers
Differential Revision: https://reviews.llvm.org/D112178
show more ...
|
|
Revision tags: llvmorg-13.0.0, llvmorg-13.0.0-rc4, llvmorg-13.0.0-rc3, llvmorg-13.0.0-rc2, llvmorg-13.0.0-rc1, llvmorg-14-init, llvmorg-12.0.1, llvmorg-12.0.1-rc4, llvmorg-12.0.1-rc3, llvmorg-12.0.1-rc2, llvmorg-12.0.1-rc1, llvmorg-12.0.0, llvmorg-12.0.0-rc5, llvmorg-12.0.0-rc4, llvmorg-12.0.0-rc3, llvmorg-12.0.0-rc2, llvmorg-11.1.0, llvmorg-11.1.0-rc3, llvmorg-12.0.0-rc1, llvmorg-13-init, llvmorg-11.1.0-rc2, llvmorg-11.1.0-rc1 |
|
| #
7fea561e |
| 26-Dec-2020 |
Arthur Eubanks <[email protected]> |
[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 ...
|
|
Revision tags: llvmorg-11.0.1, llvmorg-11.0.1-rc2, llvmorg-11.0.1-rc1 |
|
| #
491dd271 |
| 02-Nov-2020 |
Fangrui Song <[email protected]> |
[LazyCallGraph] Build SCCs of the reference graph in order
``` // The legacy PM CGPassManager discovers SCCs this way: for function in the source order tarjanSCC(function)
// While the new PM CGS
[LazyCallGraph] Build SCCs of the reference graph in order
``` // The legacy PM CGPassManager discovers SCCs this way: for function in the source order tarjanSCC(function)
// While the new PM CGSCCPassManager does: for function in the reversed source order [1] discover a reference graph SCC build call graph SCCs inside the reference graph SCC ```
In the common cases, reference graph ~= call graph, the new PM order is undesired because for `a | b | c` (3 independent functions), the new PM will process them in the reversed order: c, b, a. If `a <-> b <-> c`, we can see that `-print-after-all` will report the sole SCC as `scc: (c, b, a)`.
This patch corrects the iteration order. The discovered SCC order will match the legacy PM in the common cases.
For some tests (`Transforms/Inline/cgscc-*.ll` and `unittests/Analysis/CGSCCPassManagerTest.cpp`), the behaviors are dependent on the SCC discovery order and there are too many check lines for the particular order. This patch simply reverses the function order to avoid changing too many check lines.
Differential Revision: https://reviews.llvm.org/D90566
show more ...
|
|
Revision tags: llvmorg-11.0.0, llvmorg-11.0.0-rc6, llvmorg-11.0.0-rc5, llvmorg-11.0.0-rc4, llvmorg-11.0.0-rc3 |
|
| #
6b1ce83a |
| 16-Sep-2020 |
Arthur Eubanks <[email protected]> |
[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 ...
|
|
Revision tags: llvmorg-11.0.0-rc2, llvmorg-11.0.0-rc1, llvmorg-12-init, llvmorg-10.0.1, llvmorg-10.0.1-rc4, llvmorg-10.0.1-rc3, llvmorg-10.0.1-rc2 |
|
| #
06fd973c |
| 05-Jun-2020 |
Simon Pilgrim <[email protected]> |
TargetLibraryInfo.h - reduce Triple.h include to forward declaration. NFC.
Move implicit include dependencies down to source files.
|
|
Revision tags: llvmorg-10.0.1-rc1, llvmorg-10.0.0, llvmorg-10.0.0-rc6, llvmorg-10.0.0-rc5, llvmorg-10.0.0-rc4, llvmorg-10.0.0-rc3 |
|
| #
0deef2e1 |
| 17-Feb-2020 |
Brian Gesiak <[email protected]> |
Re-land "Add LazyCallGraph API to add function to RefSCC"
This re-commits https://reviews.llvm.org/D70927, which I reverted in https://reviews.llvm.org/rG28213680b2a7d1fdeea16aa3f3a368879472c72a due
Re-land "Add LazyCallGraph API to add function to RefSCC"
This re-commits https://reviews.llvm.org/D70927, which I reverted in https://reviews.llvm.org/rG28213680b2a7d1fdeea16aa3f3a368879472c72a due to a buildbot error: http://lab.llvm.org:8011/builders/clang-cmake-x86_64-avx2-linux/builds/13251
I no longer include a test case that appears to crash when built with the buildbot's compiler, GCC 5.4.0.
show more ...
|
| #
28213680 |
| 17-Feb-2020 |
Brian Gesiak <[email protected]> |
Revert "Add LazyCallGraph API to add function to RefSCC"
This reverts commit https://reviews.llvm.org/rG449a13509190b1c57e5fcf5cd7e8f0f647f564b4, due to buildbot failures such as http://lab.llvm.org
Revert "Add LazyCallGraph API to add function to RefSCC"
This reverts commit https://reviews.llvm.org/rG449a13509190b1c57e5fcf5cd7e8f0f647f564b4, due to buildbot failures such as http://lab.llvm.org:8011/builders/clang-cmake-x86_64-avx2-linux/builds/13251.
show more ...
|
|
Revision tags: llvmorg-10.0.0-rc2 |
|
| #
449a1350 |
| 04-Feb-2020 |
Brian Gesiak <[email protected]> |
Add LazyCallGraph API to add function to RefSCC
Summary: Depends on https://reviews.llvm.org/D70927.
`LazyCallGraph::addNewFunctionIntoSCC` allows users to insert a new function node into a call gr
Add LazyCallGraph API to add function to RefSCC
Summary: Depends on https://reviews.llvm.org/D70927.
`LazyCallGraph::addNewFunctionIntoSCC` allows users to insert a new function node into a call graph, into a specific, existing SCC.
Extend this interface such that functions can be added even when they do not belong in any existing SCC, but instead in a new SCC within an existing RefSCC.
The ability to insert new functions as part of a RefSCC is necessary for outlined functions that do not form a strongly connected cycle with the function they are outlined from. An example of such a function would be the coroutine funclets 'f.resume', etc., which are outlined from a coroutine 'f'. Coroutine 'f' only references the funclets' addresses, it does not call them directly.
Reviewers: jdoerfert, chandlerc, wenlei, hfinkel
Reviewed By: jdoerfert
Subscribers: hfinkel, JonChesterfield, mehdi_amini, hiraditya, llvm-commits
Tags: #llvm
Differential Revision: https://reviews.llvm.org/D72226
show more ...
|
| #
c057d1d3 |
| 09-Feb-2020 |
Johannes Doerfert <[email protected]> |
[FIX] Fix warning in LazyCallGraphTest caused by D70927
|
|
Revision tags: llvmorg-10.0.0-rc1, llvmorg-11-init, llvmorg-9.0.1, llvmorg-9.0.1-rc3, llvmorg-9.0.1-rc2 |
|
| #
72277ecd |
| 29-Nov-2019 |
Johannes Doerfert <[email protected]> |
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 ...
|
| #
adcd0268 |
| 28-Jan-2020 |
Benjamin Kramer <[email protected]> |
Make llvm::StringRef to std::string conversions explicit.
This is how it should've been and brings it more in line with std::string_view. There should be no functional change here.
This is mostly m
Make llvm::StringRef to std::string conversions explicit.
This is how it should've been and brings it more in line with std::string_view. There should be no functional change here.
This is mostly mechanical from a custom clang-tidy check, with a lot of manual fixups. It uncovers a lot of minor inefficiencies.
This doesn't actually modify StringRef yet, I'll do that in a follow-up.
show more ...
|
|
Revision tags: llvmorg-9.0.1-rc1, llvmorg-9.0.0, llvmorg-9.0.0-rc6, llvmorg-9.0.0-rc5, llvmorg-9.0.0-rc4 |
|
| #
9c27b59c |
| 07-Sep-2019 |
Teresa Johnson <[email protected]> |
Change TargetLibraryInfo analysis passes to always require Function
Summary: This is the first change to enable the TLI to be built per-function so that -fno-builtin* handling can be migrated to use
Change TargetLibraryInfo analysis passes to always require Function
Summary: This is the first change to enable the TLI to be built per-function so that -fno-builtin* handling can be migrated to use function attributes. See discussion on D61634 for background. This is an enabler for fixing handling of these options for LTO, for example.
This change should not affect behavior, as the provided function is not yet used to build a specifically per-function TLI, but rather enables that migration.
Most of the changes were very mechanical, e.g. passing a Function to the legacy analysis pass's getTLI interface, or in Module level cases, adding a callback. This is similar to the way the per-function TTI analysis works.
There was one place where we were looking for builtins but not in the context of a specific function. See FindCXAAtExit in lib/Transforms/IPO/GlobalOpt.cpp. I'm somewhat concerned my workaround could provide the wrong behavior in some corner cases. Suggestions welcome.
Reviewers: chandlerc, hfinkel
Subscribers: arsenm, dschuff, jvesely, nhaehnle, mehdi_amini, javed.absar, sbc100, jgravelle-google, eraman, aheejin, steven_wu, george.burgess.iv, dexonsmith, jfb, asbirlea, gchatelet, llvm-commits
Tags: #llvm
Differential Revision: https://reviews.llvm.org/D66428
llvm-svn: 371284
show more ...
|
|
Revision tags: llvmorg-9.0.0-rc3, llvmorg-9.0.0-rc2, llvmorg-9.0.0-rc1, llvmorg-10-init, llvmorg-8.0.1, llvmorg-8.0.1-rc4, llvmorg-8.0.1-rc3, llvmorg-8.0.1-rc2 |
|
| #
639b29b1 |
| 20-May-2019 |
Nick Desaulniers <[email protected]> |
[INLINER] allow inlining of blockaddresses if sole uses are callbrs
Summary: It was supposed that Ref LazyCallGraph::Edge's were being inserted by inlining, but that doesn't seem to be the case. In
[INLINER] allow inlining of blockaddresses if sole uses are callbrs
Summary: It was supposed that Ref LazyCallGraph::Edge's were being inserted by inlining, but that doesn't seem to be the case. Instead, it seems that there was no test for a blockaddress Constant in an instruction that referenced the function that contained the instruction. Ex:
``` define void @f() { %1 = alloca i8*, align 8 2: store i8* blockaddress(@f, %2), i8** %1, align 8 ret void } ```
When iterating blockaddresses, do not add the function they refer to back to the worklist if the blockaddress is referring to the contained function (as opposed to an external function).
Because blockaddress has sligtly different semantics than GNU C's address of labels, there are 3 cases that can occur with blockaddress, where only 1 can happen in GNU C due to C's scoping rules: * blockaddress is within the function it refers to (possible in GNU C). * blockaddress is within a different function than the one it refers to (not possible in GNU C). * blockaddress is used in to declare a global (not possible in GNU C).
The second case is tested in:
``` $ ./llvm/build/unittests/Analysis/AnalysisTests \ --gtest_filter=LazyCallGraphTest.HandleBlockAddress ```
This patch adjusts the iteration of blockaddresses in LazyCallGraph::visitReferences to not revisit the blockaddresses function in the first case.
The Linux kernel contains code that's not semantically valid at -O0; specifically code passed to asm goto. It requires that asm goto be inline-able. This patch conservatively does not attempt to handle the more general case of inlining blockaddresses that have non-callbr users (pr/39560).
https://bugs.llvm.org/show_bug.cgi?id=39560 https://bugs.llvm.org/show_bug.cgi?id=40722 https://github.com/ClangBuiltLinux/linux/issues/6 https://reviews.llvm.org/rL212077
Reviewers: jyknight, eli.friedman, chandlerc
Reviewed By: chandlerc
Subscribers: george.burgess.iv, nathanchance, mgorny, craig.topper, mengxu.gatech, void, mehdi_amini, E5ten, chandlerc, efriedma, eraman, hiraditya, haicheng, pirama, llvm-commits, srhines
Tags: #llvm
Differential Revision: https://reviews.llvm.org/D58260
llvm-svn: 361173
show more ...
|
|
Revision tags: llvmorg-8.0.1-rc1, llvmorg-8.0.0, llvmorg-8.0.0-rc5, llvmorg-8.0.0-rc4, llvmorg-8.0.0-rc3, llvmorg-7.1.0, llvmorg-7.1.0-rc1, llvmorg-8.0.0-rc2, llvmorg-8.0.0-rc1 |
|
| #
2946cd70 |
| 19-Jan-2019 |
Chandler Carruth <[email protected]> |
Update the file headers across all of the LLVM projects in the monorepo to reflect the new license.
We understand that people may be surprised that we're moving the header entirely to discuss the ne
Update the file headers across all of the LLVM projects in the monorepo to reflect the new license.
We understand that people may be surprised that we're moving the header entirely to discuss the new license. We checked this carefully with the Foundation's lawyer and we believe this is the correct approach.
Essentially, all code in the project is now made available by the LLVM project under our new license, so you will see that the license headers include that license only. Some of our contributors have contributed code under our old license, and accordingly, we have retained a copy of our old license notice in the top-level files in each project and repository.
llvm-svn: 351636
show more ...
|
|
Revision tags: llvmorg-7.0.1, llvmorg-7.0.1-rc3, llvmorg-7.0.1-rc2, llvmorg-7.0.1-rc1 |
|
| #
0cac726a |
| 27-Sep-2018 |
Fangrui Song <[email protected]> |
llvm::sort(C.begin(), C.end(), ...) -> llvm::sort(C, ...)
Summary: The convenience wrapper in STLExtras is available since rL342102.
Reviewers: dblaikie, javed.absar, JDevlieghere, andreadb
Subscr
llvm::sort(C.begin(), C.end(), ...) -> llvm::sort(C, ...)
Summary: The convenience wrapper in STLExtras is available since rL342102.
Reviewers: dblaikie, javed.absar, JDevlieghere, andreadb
Subscribers: MatzeB, sanjoy, arsenm, dschuff, mehdi_amini, sdardis, nemanjai, jvesely, nhaehnle, sbc100, jgravelle-google, eraman, aheejin, kbarton, JDevlieghere, javed.absar, gbedwell, jrtc27, mgrang, atanasyan, steven_wu, george.burgess.iv, dexonsmith, kristina, jsji, llvm-commits
Differential Revision: https://reviews.llvm.org/D52573
llvm-svn: 343163
show more ...
|
|
Revision tags: llvmorg-7.0.0, llvmorg-7.0.0-rc3, llvmorg-7.0.0-rc2, llvmorg-7.0.0-rc1, llvmorg-6.0.1, llvmorg-6.0.1-rc3, llvmorg-6.0.1-rc2, llvmorg-6.0.1-rc1 |
|
| #
13e70cb1 |
| 07-Apr-2018 |
Mandeep Singh Grang <[email protected]> |
[unittests] Change std::sort to llvm::sort in response to r327219
r327219 added wrappers to std::sort which randomly shuffle the container before sorting. This will help in uncovering non-determini
[unittests] Change std::sort to llvm::sort in response to r327219
r327219 added wrappers to std::sort which randomly shuffle the container before sorting. This will help in uncovering non-determinism caused due to undefined sorting order of objects having the same key.
To make use of that infrastructure we need to invoke llvm::sort instead of std::sort.
Note: This patch is one of a series of patches to replace *all* std::sort to llvm::sort. Refer the comments section in D44363 for a list of all the required patches.
llvm-svn: 329475
show more ...
|
|
Revision tags: llvmorg-5.0.2, llvmorg-5.0.2-rc2, llvmorg-5.0.2-rc1, llvmorg-6.0.0, llvmorg-6.0.0-rc3, llvmorg-6.0.0-rc2, llvmorg-6.0.0-rc1, llvmorg-5.0.1, llvmorg-5.0.1-rc3, llvmorg-5.0.1-rc2, llvmorg-5.0.1-rc1, llvmorg-5.0.0, llvmorg-5.0.0-rc5, llvmorg-5.0.0-rc4, llvmorg-5.0.0-rc3, llvmorg-5.0.0-rc2 |
|
| #
23c2f44c |
| 09-Aug-2017 |
Chandler Carruth <[email protected]> |
[LCG] Switch one of the update methods for the LazyCallGraph to support limited batch updates.
Specifically, allow removing multiple reference edges starting from a common source node. There are a f
[LCG] Switch one of the update methods for the LazyCallGraph to support limited batch updates.
Specifically, allow removing multiple reference edges starting from a common source node. There are a few constraints that play into supporting this form of batching:
1) The way updates occur during the CGSCC walk, about the most we can functionally batch together are those with a common source node. This also makes the batching simpler to implement, so it seems a worthwhile restriction. 2) The far and away hottest function for large C++ files I measured (generated code for protocol buffers) showed a huge amount of time was spent removing ref edges specifically, so it seems worth focusing there. 3) The algorithm for removing ref edges is very amenable to this restricted batching. There are just both API and implementation special casing for the non-batch case that gets in the way. Once removed, supporting batches is nearly trivial.
This does modify the API in an interesting way -- now, we only preserve the target RefSCC when the RefSCC structure is unchanged. In the face of any splits, we create brand new RefSCC objects. However, all of the users were OK with it that I could find. Only the unittest needed interesting updates here.
How much does batching these updates help? I instrumented the compiler when run over a very large generated source file for a protocol buffer and found that the majority of updates are intrinsically updating one function at a time. However, nearly 40% of the total ref edges removed are removed as part of a batch of removals greater than one, so these are the cases batching can help with.
When compiling the IR for this file with 'opt' and 'O3', this patch reduces the total time by 8-9%.
Differential Revision: https://reviews.llvm.org/D36352
llvm-svn: 310450
show more ...
|
|
Revision tags: llvmorg-5.0.0-rc1 |
|
| #
f59a8387 |
| 15-Jul-2017 |
Chandler Carruth <[email protected]> |
[PM/LCG] Teach the LazyCallGraph to maintain reference edges from every function to every defined function known to LLVM as a library function.
LLVM can introduce calls to these functions either by
[PM/LCG] Teach the LazyCallGraph to maintain reference edges from every function to every defined function known to LLVM as a library function.
LLVM can introduce calls to these functions either by replacing other library calls or by recognizing patterns (such as memset_pattern or vector math patterns) and replacing those with calls. When these library functions are actually defined in the module, we need to have reference edges to them initially so that we visit them during the CGSCC walk in the right order and can effectively rebuild the call graph afterward.
This was discovered when building code with Fortify enabled as that is a common case of both inline definitions of library calls and simplifications of code into calling them.
This can in extreme cases of LTO-ing with libc introduce *many* more reference edges. I discussed a bunch of different options with folks but all of them are unsatisfying. They either make the graph operations substantially more complex even when there are *no* defined libfuncs, or they introduce some other complexity into the callgraph. So this patch goes with the simplest possible solution of actual synthetic reference edges. If this proves to be a memory problem, I'm happy to implement one of the clever techniques to save memory here.
llvm-svn: 308088
show more ...
|
| #
c213c67d |
| 09-Jul-2017 |
Chandler Carruth <[email protected]> |
[PM] Fix a nasty bug in the new PM where we failed to properly invalidation of analyses when merging SCCs.
While I've added a bunch of testing of this, it takes something much more like the inliner
[PM] Fix a nasty bug in the new PM where we failed to properly invalidation of analyses when merging SCCs.
While I've added a bunch of testing of this, it takes something much more like the inliner to really trigger this as you need to have partially-analyzed SCCs with updates at just the right time. So I've added a direct test for this using the inliner and verifying the domtree. Without the changes here, this test ends up finding a stale dominator tree.
However, to handle this properly, we need to invalidate analyses *before* merging the SCCs. After talking to Philip and Sanjoy about this they convinced me this was the right approach. To do this, we need a callback mechanism when merging SCCs so we can observe the cycle that will be merged before the merge happens. This API update ended up being surprisingly easy.
With this commit, the new PM passes the test-suite again. It hadn't since MemorySSA was enabled for EarlyCSE as that also will find this bug very quickly.
llvm-svn: 307498
show more ...
|
|
Revision tags: llvmorg-4.0.1, llvmorg-4.0.1-rc3 |
|
| #
9a67b073 |
| 06-Jun-2017 |
Chandler Carruth <[email protected]> |
Re-sort #include lines for unittests. This uses a slightly modified clang-format (https://reviews.llvm.org/D33932) to keep primary headers at the top and handle new utility headers like 'gmock' consi
Re-sort #include lines for unittests. This uses a slightly modified clang-format (https://reviews.llvm.org/D33932) to keep primary headers at the top and handle new utility headers like 'gmock' consistently with other utility headers.
No other change was made. I did no manual edits, all of this is clang-format.
This should allow other changes to have more clear and focused diffs, and is especially motivated by moving some headers into more focused libraries.
llvm-svn: 304786
show more ...
|
|
Revision tags: llvmorg-4.0.1-rc2, llvmorg-4.0.1-rc1 |
|
| #
bd83f83b |
| 11-Mar-2017 |
Simon Pilgrim <[email protected]> |
Fix signed/unsigned comparison warnings
llvm-svn: 297561
|
|
Revision tags: llvmorg-4.0.0, llvmorg-4.0.0-rc4, llvmorg-4.0.0-rc3 |
|
| #
1f8fcfea |
| 09-Feb-2017 |
Chandler Carruth <[email protected]> |
[PM/LCG] Teach LCG to support spurious reference edges.
Somewhat amazingly, this only requires teaching it to clean them up when deleting a dead function from the graph. And we already have exactly
[PM/LCG] Teach LCG to support spurious reference edges.
Somewhat amazingly, this only requires teaching it to clean them up when deleting a dead function from the graph. And we already have exactly the necessary data structures to do that in the parent RefSCCs.
This allows ArgPromote to work in a much simpler way be merely letting reference edges linger in the graph after the causing IR is deleted. We will clean up these edges when we run any function pass over the IR, but don't remove them eagerly.
This avoids all of the quadratic update issues both in the current pass manager and in my previous attempt with the new pass manager.
Differential Revision: https://reviews.llvm.org/D29579
llvm-svn: 294663
show more ...
|
| #
aaad9f84 |
| 09-Feb-2017 |
Chandler Carruth <[email protected]> |
[PM/LCG] Teach the LazyCallGraph how to replace a function without disturbing the graph or having to update edges.
This is motivated by porting argument promotion to the new pass manager. Because of
[PM/LCG] Teach the LazyCallGraph how to replace a function without disturbing the graph or having to update edges.
This is motivated by porting argument promotion to the new pass manager. Because of how LLVM IR Function objects work, in order to change their signature a new object needs to be created. This is efficient and straight forward in the IR but previously was very hard to implement in LCG. We could easily replace the function a node in the graph represents. The challenging part is how to handle updating the edges in the graph.
LCG previously used an edge to a raw function to represent a node that had not yet been scanned for calls and references. This was the core of its laziness. However, that model causes this kind of update to be very hard: 1) The keys to lookup an edge need to be `Function*`s that would all need to be updated when we update the node. 2) There will be some unknown number of edges that haven't transitioned from `Function*` edges to `Node*` edges.
All of this complexity isn't necessary. Instead, we can always build a node around any function, always pointing edges at it and always using it as the key to lookup an edge. To maintain the laziness, we need to sink the *edges* of a node into a secondary object and explicitly model transitioning a node from empty to populated by scanning the function. This design seems much cleaner in a number of ways, but importantly there is now exactly *one* place where the `Function*` has to be updated!
Some other cleanups that fall out of this include having something to model the *entry* edges more accurately. Rather than hand rolling parts of the node in the graph itself, we have an explicit `EdgeSequence` object that gives us exactly the functionality needed. We also have a consistent place to define the edge iterators and can use them for both the entry edges and the internal edges of the graph.
The API used to model the separation between a node and its edges is intentionally very thin as most clients are expected to deal with nodes that have populated edges. We model this exactly as an optional does with an additional method to populate the edges when that is a reasonable thing for a client to do. This is based on API design suggestions from Richard Smith and David Blaikie, credit goes to them for helping pick how to model this without it being either too explicit or too implicit.
The patch is somewhat noisy due to shifting around iterator types and new syntax for walking the edges of a node, but most of the functionality change is in the `Edge`, `EdgeSequence`, and `Node` types.
Differential Revision: https://reviews.llvm.org/D29577
llvm-svn: 294653
show more ...
|
|
Revision tags: llvmorg-4.0.0-rc2 |
|
| #
2e0fe3e6 |
| 06-Feb-2017 |
Chandler Carruth <[email protected]> |
[PM/LCG] Remove the lazy RefSCC formation from the LazyCallGraph during iteration.
The lazy formation of RefSCCs isn't really the most important part of the laziness here -- that has to do with walk
[PM/LCG] Remove the lazy RefSCC formation from the LazyCallGraph during iteration.
The lazy formation of RefSCCs isn't really the most important part of the laziness here -- that has to do with walking the functions themselves -- and isn't essential to maintain. Originally, there were incremental update algorithms that relied on updates happening predominantly near the most recent RefSCC formed, but those have been replaced with ones that have much tighter general case bounds at this point. We do still perform asserts that only scale well due to this incrementality, but those are easy to place behind EXPENSIVE_CHECKS.
Removing this simplifies the entire analysis by having a single up-front step that builds all of the RefSCCs in a direct Tarjan walk. We can even easily replace this with other or better algorithms at will and with much less confusion now that there is no iterator-based incremental logic involved. This removes a lot of complexity from LCG.
Another advantage of moving in this direction is that it simplifies testing the system substantially as we no longer have to worry about observing and mutating the graph half-way through the RefSCC formation.
We still need a somewhat special iterator for RefSCCs because we want the iterator to remain stable in the face of graph updates. However, this now merely involves relative indexing to the current RefSCC's position in the sequence which isn't too hard.
Differential Revision: https://reviews.llvm.org/D29381
llvm-svn: 294227
show more ...
|
|
Revision tags: llvmorg-4.0.0-rc1 |
|
| #
443e57e0 |
| 28-Dec-2016 |
Chandler Carruth <[email protected]> |
[PM] Teach the CGSCC's CG update utility to more carefully invalidate analyses when we're about to break apart an SCC.
We can't wait until after breaking apart the SCC to invalidate things: 1) Which
[PM] Teach the CGSCC's CG update utility to more carefully invalidate analyses when we're about to break apart an SCC.
We can't wait until after breaking apart the SCC to invalidate things: 1) Which SCC do we then invalidate? All of them? 2) Even if we invalidate all of them, a newly created SCC may not have a proxy that will convey the invalidation to functions!
Previously we only invalidated one of the SCCs and too late. This led to stale analyses remaining in the cache. And because the caching strategy actually works, they would get used and chaos would ensue.
Doing invalidation early is somewhat pessimizing though if we *know* that the SCC structure won't change. So it turns out that the design to make the mutation API force the caller to know the *kind* of mutation in advance was indeed 100% correct and we didn't do enough of it. So this change also splits two cases of switching a call edge to a ref edge into two separate APIs so that callers can clearly test for this and take the easy path without invalidating when appropriate. This is particularly important in this case as we expect most inlines to be between functions in separate SCCs and so the common case is that we don't have to so aggressively invalidate analyses.
The LCG API change in turn needed some basic cleanups and better testing in its unittest. No interesting functionality changed there other than more coverage of the returned sequence of SCCs.
While this seems like an obvious improvement over the current state, I'd like to revisit the core concept of invalidating within the CG-update layer at all. I'm wondering if we would be better served forcing the callers to handle the invalidation beforehand in the cases that they can handle it. An interesting example is when we want to teach the inliner to *update and preserve* analyses. But we can cross that bridge when we get there.
With this patch, the new pass manager an build all of the LLVM test suite at -O3 and everything passes. =D I haven't bootstrapped yet and I'm sure there are still plenty of bugs, but this gives a nice baseline so I'm going to increasingly focus on fleshing out the missing functionality, especially the bits that are just turned off right now in order to let us establish this baseline.
llvm-svn: 290664
show more ...
|