summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/IPO/FunctionAttrs.cpp
Commit message (Collapse)AuthorAgeFilesLines
* Sink all InitializePasses.h includesReid Kleckner2019-11-131-0/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This file lists every pass in LLVM, and is included by Pass.h, which is very popular. Every time we add, remove, or rename a pass in LLVM, it caused lots of recompilation. I found this fact by looking at this table, which is sorted by the number of times a file was changed over the last 100,000 git commits multiplied by the number of object files that depend on it in the current checkout: recompiles touches affected_files header 342380 95 3604 llvm/include/llvm/ADT/STLExtras.h 314730 234 1345 llvm/include/llvm/InitializePasses.h 307036 118 2602 llvm/include/llvm/ADT/APInt.h 213049 59 3611 llvm/include/llvm/Support/MathExtras.h 170422 47 3626 llvm/include/llvm/Support/Compiler.h 162225 45 3605 llvm/include/llvm/ADT/Optional.h 158319 63 2513 llvm/include/llvm/ADT/Triple.h 140322 39 3598 llvm/include/llvm/ADT/StringRef.h 137647 59 2333 llvm/include/llvm/Support/Error.h 131619 73 1803 llvm/include/llvm/Support/FileSystem.h Before this change, touching InitializePasses.h would cause 1345 files to recompile. After this change, touching it only causes 550 compiles in an incremental rebuild. Reviewers: bkramer, asbirlea, bollu, jdoerfert Differential Revision: https://reviews.llvm.org/D70211
* [FunctionAttrs] Enable nonnull arg propagationDavid Bolvansky2019-09-231-4/+1
| | | | | | Enable flag introduced in rL294998. Security concerns are no longer valid, since function signatures for mentioned libc functions has no nonnull attribute (Clang does not generate them? I see no nonnull attr in LLVM IR for these functions) and since rL372091 we carefully annotate the callsites where we know that size is static, non zero. So let's enable this flag again.. llvm-svn: 372573
* LLVM: Optimization Pass: Remove conflicting attribute, if any, beforeWhitney Tsang2019-09-111-11/+22
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | adding new read attribute to an argument Summary: Update optimization pass to prevent adding read-attribute to an argument without removing its conflicting attribute. A read attribute, based on the result of the attribute deduction process, might be added to an argument. The attribute might be in conflict with other read/write attribute currently associated with the argument. To ensure the compatibility of attributes, conflicting attribute, if any, must be removed before a new one is added. The following snippet shows the current behavior of the compiler, where the compilation process is aborted due to incompatible attributes. $ cat x.ll ; ModuleID = 'x.bc' %_type_of_d-ccc = type <{ i8*, i8, i8, i8, i8 }> @d-ccc = internal global %_type_of_d-ccc <{ i8* null, i8 1, i8 13, i8 0, i8 -127 }>, align 8 define void @foo(i32* writeonly %.aaa) { foo_entry: %_param_.aaa = alloca i32*, align 8 store i32* %.aaa, i32** %_param_.aaa, align 8 store i8 0, i8* getelementptr inbounds (%_type_of_d-ccc, %_type_of_d-ccc* @d-ccc, i32 0, i32 3) ret void } $ opt -O3 x.ll Attributes 'readnone and writeonly' are incompatible! void (i32*)* @foo in function foo LLVM ERROR: Broken function found, compilation aborted! The purpose of this changeset is to fix the above error. This fix is based on a suggestion from Johannes @jdoerfert (many thanks!!!) Authored By: anhtuyen Reviewer: nicholas, rnk, chandlerc, jdoerfert Reviewed By: rnk Subscribers: hiraditya, jdoerfert, llvm-commits, anhtuyen, LLVM Tag: LLVM Differential Revision: https://reviews.llvm.org/D58694 llvm-svn: 371622
* [FunctionAttrs] Remove readonly and writeonly assertionJohannes Doerfert2019-07-151-2/+5
| | | | | | | | | | | | | There are scenarios where mutually recursive functions may cause the SCC to contain both read only and write only functions. This removes an assertion when adding read attributes which caused a crash with a the provided test case, and instead just doesn't add the attributes. Patch by Luke Lau <luke.lau@intel.com> Differential Revision: https://reviews.llvm.org/D60761 llvm-svn: 366090
* Add, and infer, a nofree function attributeBrian Homerding2019-07-081-5/+0
| | | | | | | | | | Removing dead code leftover from refactor. Reviewers: jdoerfert Differential Revision: https://reviews.llvm.org/D49165 llvm-svn: 365345
* Add, and infer, a nofree function attributeBrian Homerding2019-07-081-1/+55
| | | | | | | | | | | | This patch adds a function attribute, nofree, to indicate that a function does not, directly or indirectly, call a memory-deallocation function (e.g., free, C++'s operator delete). Reviewers: jdoerfert Differential Revision: https://reviews.llvm.org/D49165 llvm-svn: 365336
* Do not derive no-recurse attribute if function does not have exact definition.Vivek Pandya2019-06-101-1/+1
| | | | | | | | | | | This is fix for https://bugs.llvm.org/show_bug.cgi?id=41336 Reviewers: jdoerfert Reviewed by: jdoerfert Differential Revision: https://reviews.llvm.org/D63045 llvm-svn: 362918
* [IR] Refactor attribute methods in Function class (NFC)Evandro Menezes2019-04-041-2/+2
| | | | | | | | Rename the functions that query the optimization kind attributes. Differential revision: https://reviews.llvm.org/D60287 llvm-svn: 357731
* [IR] Create new method in `Function` class (NFC)Evandro Menezes2019-04-031-4/+2
| | | | | | | | | Create method `optForNone()` testing for the function level equivalent of `-O0` and refactor appropriately. Differential revision: https://reviews.llvm.org/D59852 llvm-svn: 357638
* Update the file headers across all of the LLVM projects in the monorepoChandler Carruth2019-01-191-4/+3
| | | | | | | | | | | | | | | | | 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
* [CallSite removal] Migrate all Alias Analysis APIs to use the newlyChandler Carruth2019-01-071-6/+5
| | | | | | | | | | | | | | | | | | | | | | | | | | minted `CallBase` class instead of the `CallSite` wrapper. This moves the largest interwoven collection of APIs that traffic in `CallSite`s. While a handful of these could have been migrated with a minorly more shallow migration by converting from a `CallSite` to a `CallBase`, it hardly seemed worth it. Most of the APIs needed to migrate together because of the complex interplay of AA APIs and the fact that converting from a `CallBase` to a `CallSite` isn't free in its current implementation. Out of tree users of these APIs can fairly reliably migrate with some combination of `.getInstruction()` on the `CallSite` instance and casting the resulting pointer. The most generic form will look like `CS` -> `cast_or_null<CallBase>(CS.getInstruction())` but in most cases there is a more elegant migration. Hopefully, this migrates enough APIs for users to fully move from `CallSite` to the base class. All of the in-tree users were easily migrated in that fashion. Thanks for the review from Saleem! Differential Revision: https://reviews.llvm.org/D55641 llvm-svn: 350503
* Allow norecurse attribute on functions that have debug infos.Christian Bruel2018-12-051-7/+9
| | | | | | | | | | | | | | Summary: debug intrinsics might be marked norecurse to enable the caller function to be norecurse and optimized if needed. This avoids code gen optimisation differences when -g is used, as in globalOpt.cpp:processInternalGlobal checks. Reviewers: chandlerc, jmolloy, aprantl Reviewed By: aprantl Subscribers: aprantl, llvm-commits Differential Revision: https://reviews.llvm.org/D55187 llvm-svn: 348381
* Replace most users of UnknownSize with LocationSize::unknown(); NFCGeorge Burgess IV2018-10-101-1/+1
| | | | | | | | | | | | Moving away from UnknownSize is part of the effort to migrate us to LocationSizes (e.g. the cleanup promised in D44748). This doesn't entirely remove all of the uses of UnknownSize; some uses require tweaks to assume that UnknownSize isn't just some kind of int. This patch is intended to just be a trivial replacement for all places where LocationSize::unknown() will Just Work. llvm-svn: 344186
* [FuncAttrs] Remove "access range attributes" for read-none functionsJohannes Doerfert2018-09-111-0/+7
| | | | | | | | | | The presence of readnone and an access range attribute (argmemonly, inaccessiblememonly, inaccessiblemem_or_argmemonly) is considered an error by the verifier. This seems strict but also not wrong. This patch makes sure function attribute detection will remove all access range attributes for readnone functions. llvm-svn: 341927
* [FunctionAttrs] Infer WriteOnly Function AttributeBrian Homerding2018-08-231-10/+38
| | | | | | | | | | | | These changes expand the FunctionAttr logic in order to mark functions as WriteOnly when appropriate. This is done through an additional bool variable and extended logic. Reviewers: hfinkel, jdoerfert Differential Revision: https://reviews.llvm.org/D48387 llvm-svn: 340537
* [NFC][FunctionAttrs] Remove duplication in old/new PM pipelineJohannes Doerfert2018-08-011-33/+29
| | | | | | | | This patch just extract code into a separate function to remove some duplication between the old and new pass manager pipeline. Due to the different CGSCC iterators used, not all code duplication was eliminated. llvm-svn: 338585
* Remove trailing spaceFangrui Song2018-07-301-1/+1
| | | | | | sed -Ei 's/[[:space:]]+$//' include/**/*.{def,h,td} lib/**/*.{cpp,h} llvm-svn: 338293
* Use SmallPtrSet explicitly for SmallSets with pointer types (NFC).Florian Hahn2018-06-121-2/+1
| | | | | | | | | | | | | | Currently SmallSet<PointerTy> inherits from SmallPtrSet<PointerTy>. This patch replaces such types with SmallPtrSet, because IMO it is slightly clearer and allows us to get rid of unnecessarily including SmallSet.h Reviewers: dblaikie, craig.topper Reviewed By: dblaikie Differential Revision: https://reviews.llvm.org/D47836 llvm-svn: 334492
* Rename DEBUG macro to LLVM_DEBUG.Nicola Zaghen2018-05-141-5/+7
| | | | | | | | | | | | | | | | The DEBUG() macro is very generic so it might clash with other projects. The renaming was done as follows: - git grep -l 'DEBUG' | xargs sed -i 's/\bDEBUG\s\?(/LLVM_DEBUG(/g' - git diff -U0 master | ../clang/tools/clang-format/clang-format-diff.py -i -p1 -style LLVM - Manual change to APInt - Manually chage DOCS as regex doesn't match it. In the transition period the DEBUG() macro is still present and aliased to the LLVM_DEBUG() one. Differential Revision: https://reviews.llvm.org/D43624 llvm-svn: 332240
* [PM][FunctionAttrs] add NoUnwind attribute inference to ↵Fedor Sergeev2018-03-231-32/+201
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | PostOrderFunctionAttrs pass Summary: This was motivated by absence of PrunEH functionality in new PM. It was decided that a proper way to do PruneEH is to add NoUnwind inference into PostOrderFunctionAttrs and then perform normal SimplifyCFG on top. This change generalizes attribute handling implemented for (a removal of) Convergent attribute, by introducing a generic builder-like class AttributeInferer It registers all the attribute inference requests, storing per-attribute predicates into a vector, and then goes through an SCC Node, scanning all the instructions for not breaking attribute assumptions. The main idea is that as soon all the instructions from all the functions of SCC Node conform to attribute assumptions then we are free to infer the attribute as set for all the functions of SCC Node. It handles two distinct cases of attributes: - those that might break due to derefinement of the function code for these attributes we are allowed to apply inference only if all the functions are "exact definitions". Example - NoUnwind. - those that do not care about derefinement for these attributes we are allowed to apply inference as soon as we see any function definition. Example - removal of Convergent attribute. Also in this commit: * Converted all the FunctionAttrs tests to use FileCheck and added new-PM invocations to them * FunctionAttrs/convergent.ll test demonstrates a difference in behavior between new and old PM implementations. Marked with FIXME. * PruneEH tests were converted to new-PM as well, using function-attrs+simplify-cfg combo as intended * some of "other" tests were updated since function-attrs now infers 'nounwind' even for old PM pipeline * -disable-nounwind-inference hidden option added as a possible workaround for a supposedly rare case when nounwind being inferred by default presents a problem Reviewers: chandlerc, jlebar Reviewed By: jlebar Subscribers: eraman, llvm-commits Differential Revision: https://reviews.llvm.org/D44415 llvm-svn: 328377
* [FunctionAttrs][ArgumentPromotion][GlobalOpt] Disable some optimisations ↵Luke Cheeseman2018-02-221-2/+4
| | | | | | | | | | | | | | passes for naked functions - Fix for bug 36078. - Prevent the functionattrs, function-attrs, globalopt and argpromotion passes from changing naked functions. - These passes can perform some alterations to the functions that should not be applied. An example is removing parameters that are seemingly not used because they are only referenced in the inline assembly. Another example is marking the function as fastcc. llvm-svn: 325788
* Modify ModRefInfo values using static inline method abstractions [NFC].Alina Sbirlea2017-12-051-5/+6
| | | | | | | | | | | | | | | | | Summary: The aim is to make ModRefInfo checks and changes more intuitive and less error prone using inline methods that abstract the bit operations. Ideally ModRefInfo would become an enum class, but that change will require a wider set of changes into FunctionModRefBehavior. Reviewers: sanjoy, george.burgess.iv, dberlin, hfinkel Subscribers: nlopes, llvm-commits Differential Revision: https://reviews.llvm.org/D40749 llvm-svn: 319821
* [Transforms] Fix some Clang-tidy modernize and Include What You Use ↵Eugene Zelenko2017-10-191-27/+73
| | | | | | warnings; other minor fixes (NFC). llvm-svn: 316187
* Merge isKnownNonNull into isKnownNonZeroNuno Lopes2017-09-091-1/+3
| | | | | | | | | It now knows the tricks of both functions. Also, fix a bug that considered allocas of non-zero address space to be always non null Differential Revision: https://reviews.llvm.org/D37628 llvm-svn: 312869
* Sort the remaining #include lines in include/... and lib/....Chandler Carruth2017-06-061-2/+1
| | | | | | | | | | | | | | | | | | | | | | | | | I did this a long time ago with a janky python script, but now clang-format has built-in support for this. I fed clang-format every line with a #include and let it re-sort things according to the precise LLVM rules for include ordering baked into clang-format these days. I've reverted a number of files where the results of sorting includes isn't healthy. Either places where we have legacy code relying on particular include ordering (where possible, I'll fix these separately) or where we have particular formatting around #include lines that I didn't want to disturb in this patch. This patch is *entirely* mechanical. If you get merge conflicts or anything, just ignore the changes in this patch and run clang-format over your #include lines in the files. Sorry for any noise here, but it is important to keep these things stable. I was seeing an increasing number of patches with irrelevant re-ordering of #include lines because clang-format was used. This patch at least isolates that churn, makes it easy to skip when resolving conflicts, and gets us to a clean baseline (again). llvm-svn: 304787
* FunctionAttrs: Skip it if the effective SCC (ignoring optnone functions) is ↵David Blaikie2017-06-021-0/+4
| | | | | | | | | empty Minor optimization but mostly simplifies my debugging so I'm not dealing with empty SCCNodeSets while investigating issues in this optimization. llvm-svn: 304597
* [IR] Abstract away ArgNo+1 attribute indexing as much as possibleReid Kleckner2017-05-031-3/+3
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: Do three things to help with that: - Add AttributeList::FirstArgIndex, which is an enumerator currently set to 1. It allows us to change the indexing scheme with fewer changes. - Add addParamAttr/removeParamAttr. This just shortens addAttribute call sites that would otherwise need to spell out FirstArgIndex. - Remove some attribute-specific getters and setters from Function that take attribute list indices. Most of these were only used from BuildLibCalls, and doesNotAlias was only used to test or set if the return value is malloc-like. I'm happy to split the patch, but I think they are probably easier to review when taken together. This patch should be NFC, but it sets the stage to change the indexing scheme to this, which is more convenient when indexing into an array: 0: func attrs 1: retattrs 2...: arg attrs Reviewers: chandlerc, pete, javed.absar Subscribers: david2050, llvm-commits Differential Revision: https://reviews.llvm.org/D32811 llvm-svn: 302060
* Use Argument::hasAttribute and AttributeList::ReturnIndex moreReid Kleckner2017-04-281-2/+3
| | | | | | | | | | | This eliminates many extra 'Idx' induction variables in loops over arguments in CodeGen/ and Target/. It also reduces the number of places where we assume that ReturnIndex is 0 and that we should add one to argument numbers to get the corresponding attribute list index. NFC llvm-svn: 301666
* Prefer addAttr(Attribute::AttrKind) over the AttributeList overloadReid Kleckner2017-04-191-28/+12
| | | | | | | | This should simplify the call sites, which typically want to tweak one attribute at a time. It should also avoid creating ephemeral AttributeLists that live forever. llvm-svn: 300718
* [IR] Make paramHasAttr to use arg indices instead of attr indicesReid Kleckner2017-04-141-1/+1
| | | | | | | | | This avoids the confusing 'CS.paramHasAttr(ArgNo + 1, Foo)' pattern. Previously we were testing return value attributes with index 0, so I introduced hasReturnAttr() for that use case. llvm-svn: 300367
* Rename AttributeSet to AttributeListReid Kleckner2017-03-211-15/+16
| | | | | | | | | | | | | | | | | | | | | | | | | Summary: This class is a list of AttributeSetNodes corresponding the function prototype of a call or function declaration. This class used to be called ParamAttrListPtr, then AttrListPtr, then AttributeSet. It is typically accessed by parameter and return value index, so "AttributeList" seems like a more intuitive name. Rename AttributeSetImpl to AttributeListImpl to follow suit. It's useful to rename this class so that we can rename AttributeSetNode to AttributeSet later. AttributeSet is the set of attributes that apply to a single function, argument, or return value. Reviewers: sanjoy, javed.absar, chandlerc, pete Reviewed By: pete Subscribers: pete, jholewinski, arsenm, dschuff, mehdi_amini, jfb, nhaehnle, sbc100, void, llvm-commits Differential Revision: https://reviews.llvm.org/D31102 llvm-svn: 298393
* FunctionAttrs: Factor out a function for querying memory access of a ↵Peter Collingbourne2017-02-141-16/+21
| | | | | | | | | | | specific copy of a function. NFC. This will later be used by ThinLTOBitcodeWriter to add copies of readnone functions to the regular LTO module. Differential Revision: https://reviews.llvm.org/D29695 llvm-svn: 295008
* [FunctionAttrs] try to extend nonnull-ness of arguments from a callsite back ↵Sanjay Patel2017-02-131-0/+53
| | | | | | | | | | | | | | | | | | | to its parent function As discussed here: http://lists.llvm.org/pipermail/llvm-dev/2016-December/108182.html ...we should be able to propagate 'nonnull' info from a callsite back to its parent. The original motivation for this patch is our botched optimization of "dyn_cast" (PR28430), but this won't solve that problem. The transform is currently disabled by default while we wait for clang to work-around potential security problems: http://lists.llvm.org/pipermail/cfe-dev/2017-January/052066.html Differential Revision: https://reviews.llvm.org/D27855 llvm-svn: 294998
* De-duplicate some code for creating an AARGetter suitable for the legacy PM.Peter Collingbourne2017-02-091-14/+2
| | | | | | | | I'm about to use this in a couple more places. Differential Revision: https://reviews.llvm.org/D29793 llvm-svn: 294648
* [PH] Replace uses of AssertingVH from members of analysis results withChandler Carruth2017-01-241-9/+2
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | a lazy-asserting PoisoningVH. AssertVH is fundamentally incompatible with cache-invalidation of analysis results. The invaliadtion happens after the AssertingVH has already fired. Instead, use a PoisoningVH that will assert if the dangling handle is ever used rather than merely be assigned or destroyed. This patch also removes all of the (numerous) doomed attempts to work around this fundamental incompatibility. It is a pretty significant simplification IMO. The most interesting change is in the Inliner where we still do some clearing because we don't want to rely on the coarse grained invalidation strategy of the containing pass manager. However, I prefer the approach that contains this logic to the cleanup phase of the Inliner, and I think we could enhance the CGSCC analysis management layer to make this even better in the future if desired. The rest is straight cleanup. I've also added a test for one of the harder cases to work around: when a *module analysis* contains many AssertingVHes pointing at functions. Differential Revision: https://reviews.llvm.org/D29006 llvm-svn: 292928
* Revert @llvm.assume with operator bundles (r289755-r289757)Daniel Jasper2016-12-191-0/+3
| | | | | | | This creates non-linear behavior in the inliner (see more details in r289755's commit thread). llvm-svn: 290086
* Remove the AssumptionCacheHal Finkel2016-12-151-3/+0
| | | | | | | | | After r289755, the AssumptionCache is no longer needed. Variables affected by assumptions are now found by using the new operand-bundle-based scheme. This new scheme is more computationally efficient, and also we need much less code... llvm-svn: 289756
* Fix 80-column violations. NFC.Chad Rosier2016-11-071-3/+7
| | | | llvm-svn: 286117
* [FunctionAttrs] Don't try to infer returned if it is already on an argumentDavid Majnemer2016-09-121-0/+5
| | | | | | | | | | | Trying to infer the 'returned' attribute if an argument is already 'returned' can lead to verification failure: inference might determine that a different argument is passed through which would result in two different arguments marked as 'returned'. This fixes PR30350. llvm-svn: 281221
* s/static inline/static/ for headers I have changed in r279475. NFC.Tim Shen2016-08-311-5/+3
| | | | llvm-svn: 280257
* [PM] Introduce basic update capabilities to the new PM's CGSCC passChandler Carruth2016-08-241-2/+4
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | manager, including both plumbing and logic to handle function pass updates. There are three fundamentally tied changes here: 1) Plumbing *some* mechanism for updating the CGSCC pass manager as the CG changes while passes are running. 2) Changing the CGSCC pass manager infrastructure to have support for the underlying graph to mutate mid-pass run. 3) Actually updating the CG after function passes run. I can separate them if necessary, but I think its really useful to have them together as the needs of #3 drove #2, and that in turn drove #1. The plumbing technique is to extend the "run" method signature with extra arguments. We provide the call graph that intrinsically is available as it is the basis of the pass manager's IR units, and an output parameter that records the results of updating the call graph during an SCC passes's run. Note that "...UpdateResult" isn't a *great* name here... suggestions very welcome. I tried a pretty frustrating number of different data structures and such for the innards of the update result. Every other one failed for one reason or another. Sometimes I just couldn't keep the layers of complexity right in my head. The thing that really worked was to just directly provide access to the underlying structures used to walk the call graph so that their updates could be informed by the *particular* nature of the change to the graph. The technique for how to make the pass management infrastructure cope with mutating graphs was also something that took a really, really large number of iterations to get to a place where I was happy. Here are some of the considerations that drove the design: - We operate at three levels within the infrastructure: RefSCC, SCC, and Node. In each case, we are working bottom up and so we want to continue to iterate on the "lowest" node as the graph changes. Look at how we iterate over nodes in an SCC running function passes as those function passes mutate the CG. We continue to iterate on the "lowest" SCC, which is the one that continues to contain the function just processed. - The call graph structure re-uses SCCs (and RefSCCs) during mutation events for the *highest* entry in the resulting new subgraph, not the lowest. This means that it is necessary to continually update the current SCC or RefSCC as it shifts. This is really surprising and subtle, and took a long time for me to work out. I actually tried changing the call graph to provide the opposite behavior, and it breaks *EVERYTHING*. The graph update algorithms are really deeply tied to this particualr pattern. - When SCCs or RefSCCs are split apart and refined and we continually re-pin our processing to the bottom one in the subgraph, we need to enqueue the newly formed SCCs and RefSCCs for subsequent processing. Queuing them presents a few challenges: 1) SCCs and RefSCCs use wildly different iteration strategies at a high level. We end up needing to converge them on worklist approaches that can be extended in order to be able to handle the mutations. 2) The order of the enqueuing need to remain bottom-up post-order so that we don't get surprising order of visitation for things like the inliner. 3) We need the worklists to have set semantics so we don't duplicate things endlessly. We don't need a *persistent* set though because we always keep processing the bottom node!!!! This is super, super surprising to me and took a long time to convince myself this is correct, but I'm pretty sure it is... Once we sink down to the bottom node, we can't re-split out the same node in any way, and the postorder of the current queue is fixed and unchanging. 4) We need to make sure that the "current" SCC or RefSCC actually gets enqueued here such that we re-visit it because we continue processing a *new*, *bottom* SCC/RefSCC. - We also need the ability to *skip* SCCs and RefSCCs that get merged into a larger component. We even need the ability to skip *nodes* from an SCC that are no longer part of that SCC. This led to the design you see in the patch which uses SetVector-based worklists. The RefSCC worklist is always empty until an update occurs and is just used to handle those RefSCCs created by updates as the others don't even exist yet and are formed on-demand during the bottom-up walk. The SCC worklist is pre-populated from the RefSCC, and we push new SCCs onto it and blacklist existing SCCs on it to get the desired processing. We then *directly* update these when updating the call graph as I was never able to find a satisfactory abstraction around the update strategy. Finally, we need to compute the updates for function passes. This is mostly used as an initial customer of all the update mechanisms to drive their design to at least cover some real set of use cases. There are a bunch of interesting things that came out of doing this: - It is really nice to do this a function at a time because that function is likely hot in the cache. This means we want even the function pass adaptor to support online updates to the call graph! - To update the call graph after arbitrary function pass mutations is quite hard. We have to build a fairly comprehensive set of data structures and then process them. Fortunately, some of this code is related to the code for building the cal graph in the first place. Unfortunately, very little of it makes any sense to share because the nature of what we're doing is so very different. I've factored out the one part that made sense at least. - We need to transfer these updates into the various structures for the CGSCC pass manager. Once those were more sanely worked out, this became relatively easier. But some of those needs necessitated changes to the LazyCallGraph interface to make it significantly easier to extract the changed SCCs from an update operation. - We also need to update the CGSCC analysis manager as the shape of the graph changes. When an SCC is merged away we need to clear analyses associated with it from the analysis manager which we didn't have support for in the analysis manager infrsatructure. New SCCs are easy! But then we have the case that the original SCC has its shape changed but remains in the call graph. There we need to *invalidate* the analyses associated with it. - We also need to invalidate analyses after we *finish* processing an SCC. But the analyses we need to invalidate here are *only those for the newly updated SCC*!!! Because we only continue processing the bottom SCC, if we split SCCs apart the original one gets invalidated once when its shape changes and is not processed farther so its analyses will be correct. It is the bottom SCC which continues being processed and needs to have the "normal" invalidation done based on the preserved analyses set. All of this is mostly background and context for the changes here. Many thanks to all the reviewers who helped here. Especially Sanjoy who caught several interesting bugs in the graph algorithms, David, Sean, and others who all helped with feedback. Differential Revision: http://reviews.llvm.org/D21464 llvm-svn: 279618
* [GraphTraits] Replace all NodeType usage with NodeRefTim Shen2016-08-221-9/+4
| | | | | | | | This should finish the GraphTraits migration. Differential Revision: http://reviews.llvm.org/D23730 llvm-svn: 279475
* Replace a few more "fall through" comments with LLVM_FALLTHROUGHJustin Bogner2016-08-171-1/+2
| | | | | | Follow up to r278902. I had missed "fall through", with a space. llvm-svn: 278970
* IPO: Swap || operands to avoid dereferencing end()Duncan P. N. Exon Smith2016-08-171-2/+2
| | | | | | | | IsOperandBundleUse conveniently indicates whether std::next(F->arg_begin(),UseIndex) will get to (or past) end(). Check it first to avoid dereferencing end(). llvm-svn: 278884
* Consistently use ModuleAnalysisManagerSean Silva2016-08-091-1/+1
| | | | | | | | | | | Besides a general consistently benefit, the extra layer of indirection allows the mechanical part of https://reviews.llvm.org/D23256 that requires touching every transformation and analysis to be factored out cleanly. Thanks to David for the suggestion. llvm-svn: 278078
* Add some comments linking back to PR28400.Sean Silva2016-08-081-0/+2
| | | | | | Thanks to Mehdi for the suggestion! llvm-svn: 277984
* [PM] Invalidate CallGraphAnalysis because it holds AssertingVHSean Silva2016-08-081-0/+5
| | | | | | | This is essentially PR28400. The fix here is similar to that implemented in r274656. llvm-svn: 277980
* [ADT] NFC: Generalize GraphTraits requirement of "NodeType *" in interfaces ↵Tim Shen2016-08-011-0/+1
| | | | | | | | | | | | | | to "NodeRef", and migrate SCCIterator.h to use NodeRef Summary: By generalize the interface, users are able to inject more flexible Node token into the algorithm, for example, a pair of vector<Node>* and index integer. Currently I only migrated SCCIterator to use NodeRef, but more is coming. It's a NFC. Reviewers: dblaikie, chandlerc Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D22937 llvm-svn: 277399
* [FunctionAttrs] Correct the safety analysis for inference of 'returned'David Majnemer2016-07-191-0/+51
| | | | | | | | | | | | We skipped over ReturnInsts which didn't return an argument which would lead us to incorrectly conclude that an argument returned by another ReturnInst was 'returned'. This reverts commit r275756. This fixes PR28610. llvm-svn: 276008
* Revert r275678, "Revert "Revert r275027 - Let FuncAttrs infer the 'returned' ↵NAKAMURA Takumi2016-07-181-50/+0
| | | | | | | | | | argument attribute"" This reverts also r275029, "Update Clang tests after adding inference for the returned argument attribute" It broke LTO build. Seems miscompilation. llvm-svn: 275756
OpenPOWER on IntegriCloud