summaryrefslogtreecommitdiff
path: root/lib/Analysis
Commit message (Collapse)AuthorAge
* [LCG] Add the really, *really* boring edge insertion case: adding anChandler Carruth2014-04-30
| | | | | | | | | | edge entirely within an existing SCC. Shockingly, making the connected component more connected is ... a total snooze fest. =] Anyways, its wired up, and I even added a test case to make sure it pretty much sorta works. =D git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@207631 91177308-0d34-0410-b5e6-96231b3b80d8
* [LCG] Actually test the *basic* edge removal bits (IE, the non-SCCChandler Carruth2014-04-30
| | | | | | | | | | | | | | | | | | | | | | | | | | bits), and discover that it's totally broken. Yay tests. Boo bug. Fix the basic edge removal so that it works by nulling out the removed edges rather than actually removing them. This leaves the indices valid in the map from callee to index, and preserves some of the locality for iterating over edges. The iterator is made bidirectional to reflect that it now has to skip over null entries, and the skipping logic is layered onto it. As future work, I would like to track essentially the "load factor" of the edge list, and when it falls below a threshold do a compaction. An alternative I considered (and continue to consider) is storing the callees in a doubly linked list where each element of the list is in a set (which is essentially the classical linked-hash-table datastructure). The problem with that approach is that either you need to heap allocate the linked list nodes and use pointers to them, or use a bucket hash table (with even *more* linked list pointer overhead!), etc. It's pretty easy to get 5x overhead for values that are just pointers. So far, I think punching holes in the vector, and periodic compaction is likely to be much more efficient overall in the space/time tradeoff. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@207619 91177308-0d34-0410-b5e6-96231b3b80d8
* raw_ostream: Forward declare OpenFlags and include FileSystem.h only where ↵Benjamin Kramer2014-04-29
| | | | | | necessary. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@207593 91177308-0d34-0410-b5e6-96231b3b80d8
* blockfreq: Defer to BranchProbability::scale()Duncan P. N. Exon Smith2014-04-29
| | | | | | `BlockMass` can now defer to `BranchProbability::scale()`. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@207547 91177308-0d34-0410-b5e6-96231b3b80d8
* blockfreq: Remove more extra typenames from r207438Duncan P. N. Exon Smith2014-04-28
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@207440 91177308-0d34-0410-b5e6-96231b3b80d8
* Reapply "blockfreq: Approximate irreducible control flow"Duncan P. N. Exon Smith2014-04-28
| | | | | | | | | | This reverts commit r207287, reapplying r207286. I'm hoping that declaring an explicit struct and instantiating `addBlockEdges()` directly works around the GCC crash from r207286. This is a lot more boilerplate, though. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@207438 91177308-0d34-0410-b5e6-96231b3b80d8
* [LCG] Add the most basic of edge insertion to the lazy call graph. ThisChandler Carruth2014-04-28
| | | | | | | just handles the pre-DFS case. Also add some test cases for this case to make sure it works. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@207411 91177308-0d34-0410-b5e6-96231b3b80d8
* [LCG] Make the return of the IntraSCC removal method actually match itsChandler Carruth2014-04-28
| | | | | | | | contract (and be much more useful). It now provides exactly the post-order traversal a caller might need to perform on newly formed SCCs. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@207410 91177308-0d34-0410-b5e6-96231b3b80d8
* [inliner] Significantly improve the compile time in cases like PR19499Chandler Carruth2014-04-28
| | | | | | | | | | | | | | | by avoiding inlining massive switches merely because they have no instructions in them. These switches still show up where we fail to form lookup tables, and in those cases they are actually going to cause a very significant code size hit anyways, so inlining them is not the right call. The right way to fix any performance regressions stemming from this is to enhance the switch-to-lookup-table logic to fire in more places. This makes PR19499 about 5x less bad. It uncovers a second compile time problem in that test case that is unrelated (surprisingly!). git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@207403 91177308-0d34-0410-b5e6-96231b3b80d8
* [C++] Use 'nullptr'.Craig Topper2014-04-28
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@207394 91177308-0d34-0410-b5e6-96231b3b80d8
* [LCG] Re-organize the methods for mutating a call graph to make theirChandler Carruth2014-04-27
| | | | | | | | | | | | | | | | | | | | | | | | | | | | API requirements much more obvious. The key here is that there are two totally different use cases for mutating the graph. Prior to doing any SCC formation, it is very easy to mutate the graph. There may be users that want to do small tweaks here, and then use the already-built graph for their SCC-based operations. This method remains on the graph itself and is documented carefully as being cheap but unavailable once SCCs are formed. Once SCCs are formed, and there is some in-flight DFS building them, we have to be much more careful in how we mutate the graph. These mutation operations are sunk onto the SCCs themselves, which both simplifies things (the code was already there!) and helps make it obvious that these interfaces are only applicable within that context. The other primary constraint is that the edge being mutated is actually related to the SCC on which we call the method. This helps make it obvious that you cannot arbitrarily mutate some other SCC. I've tried to write much more complete documentation for the interesting mutation API -- intra-SCC edge removal. Currently one aspect of this documentation is a lie (the result list of SCCs) but we also don't even have tests for that API. =[ I'm going to add tests and fix it to match the documentation next. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@207339 91177308-0d34-0410-b5e6-96231b3b80d8
* [LCG] Rather than removing nodes from the SCC entry set when we processChandler Carruth2014-04-26
| | | | | | | | | | them, just skip over any DFS-numbered nodes when finding the next root of a DFS. This allows the entry set to just be a vector as we populate it from a uniqued source. It also removes the possibility for a linear scan of the entry set to actually do the removal which can make things go quadratic if we get unlucky. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@207312 91177308-0d34-0410-b5e6-96231b3b80d8
* [LCG] Rotate the full SCC finding algorithm to avoid round-trips throughChandler Carruth2014-04-26
| | | | | | | | | | | | | | | the DFS stack for leaves in the call graph. As mentioned in my previous commit, this is particularly interesting for graphs which have high fan out but low connectivity resulting in many leaves. For such graphs, this can remove a large % of the DFS stack traffic even though it doesn't make the stack much smaller. It's a bit easier to formulate this for the full algorithm because that one stops completely for each SCC. For example, I was able to directly eliminate the "Recurse" boolean used to continue an outer loop from the inner loop. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@207311 91177308-0d34-0410-b5e6-96231b3b80d8
* [LCG] Hoist the main DFS loop out of the edge removal function. ThisChandler Carruth2014-04-26
| | | | | | | | | makes working through the worklist much cleaner, and makes it possible to avoid the 'bool-to-continue-the-outer-loop' hack. Not a huge difference, but I think this is approaching as polished as I can make it. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@207310 91177308-0d34-0410-b5e6-96231b3b80d8
* [LCG] In the incremental SCC re-formation, lift the node currently beingChandler Carruth2014-04-26
| | | | | | | | | | | | | | | | | | | processed in the DFS out of the stack completely. Keep it exclusively in a variable. Re-shuffle some code structure to make this easier. This can have a very dramatic effect in some cases because call graphs tend to look like a high fan-out spanning tree. As a consequence, there are a large number of leaf nodes in the graph, and this technique causes leaf nodes to never even go into the stack. While this only reduces the max depth by 1, it may cause the total number of round trips through the stack to drop by a lot. Now, most of this isn't really relevant for the incremental version. =] But I wanted to prototype it first here as this variant is in ways more complex. As long as I can get the code factored well here, I'll next make the primary walk look the same. There are several refactorings this exposes I think. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@207306 91177308-0d34-0410-b5e6-96231b3b80d8
* [LCG] Special case the removal of self edges. These don't impact the SCCChandler Carruth2014-04-26
| | | | | | | | graph in any way because we don't track edges in the SCC graph, just nodes. This also lets us add a nice assert about the invariant that we're working on at least a certain number of nodes within the SCC. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@207305 91177308-0d34-0410-b5e6-96231b3b80d8
* [LCG] Refactor the duplicated code I added in my last commit here intoChandler Carruth2014-04-26
| | | | | | | a helper function. Also factor the other two places where we did the same thing into the helper function. =] Much cleaner this way. NFC. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@207300 91177308-0d34-0410-b5e6-96231b3b80d8
* Revert "blockfreq: Approximate irreducible control flow"Duncan P. N. Exon Smith2014-04-25
| | | | | | | | | | | | This reverts commit r207286. It causes an ICE on the cmake-llvm-x86_64-linux buildbot [1]: llvm/lib/Analysis/BlockFrequencyInfo.cpp: In lambda function: llvm/lib/Analysis/BlockFrequencyInfo.cpp:182:1: internal compiler error: in get_expr_operands, at tree-ssa-operands.c:1035 [1]: http://bb.pgr.jp/builders/cmake-llvm-x86_64-linux/builds/12093/steps/build_llvm/logs/stdio git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@207287 91177308-0d34-0410-b5e6-96231b3b80d8
* blockfreq: Approximate irreducible control flowDuncan P. N. Exon Smith2014-04-25
| | | | | | | | | | | | | | | | | | | | | | Previously, irreducible backedges were ignored. With this commit, irreducible SCCs are discovered on the fly, and modelled as loops with multiple headers. This approximation specifies the headers of irreducible sub-SCCs as its entry blocks and all nodes that are targets of a backedge within it (excluding backedges within true sub-loops). Block frequency calculations act as if we insert a new block that intercepts all the edges to the headers. All backedges and entries to the irreducible SCC point to this imaginary block. This imaginary block has an edge (with even probability) to each header block. The result is now reasonable enough that I've added a number of testcases for irreducible control flow. I've outlined in `BlockFrequencyInfoImpl.h` ways to improve the approximation. <rdar://problem/14292693> git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@207286 91177308-0d34-0410-b5e6-96231b3b80d8
* blockfreq: Further shift logic to LoopDataDuncan P. N. Exon Smith2014-04-25
| | | | | | | | | Move a lot of the loop-related logic that was sprinkled around the code into `LoopData`. <rdar://problem/14292693> git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@207258 91177308-0d34-0410-b5e6-96231b3b80d8
* SCC: Change clients to use const, NFCDuncan P. N. Exon Smith2014-04-25
| | | | | | | | | | It's fishy to be changing the `std::vector<>` owned by the iterator, and no one actual does it, so I'm going to remove the ability in a subsequent commit. First, update the users. <rdar://problem/14292693> git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@207252 91177308-0d34-0410-b5e6-96231b3b80d8
* [LCG] During the incremental update of an SCC, switch to using theChandler Carruth2014-04-25
| | | | | | | | | | | | | | | | | | SCCMap to test for nodes that have been re-added to the root SCC rather than a set vector. We already have done the SCCMap lookup, we juts need to test it in two different ways. In turn, do most of the processing of these nodes as they go into the root SCC rather than lazily. This simplifies the final loop to just stitch the root SCC into its children's parent sets. No functionlatiy changed. However, this makes a few things painfully obvious, which was my intent. =] There is tons of repeated code introduced here and elsewhere. I'm splitting the refactoring of that code into helpers from this change so its clear that this is the change which switches the datastructures used around, and the other is a pure factoring & deduplication of code change. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@207217 91177308-0d34-0410-b5e6-96231b3b80d8
* [LCG] During the incremental re-build of an SCC after removing an edge,Chandler Carruth2014-04-25
| | | | | | | | | | | | | | | | | | remove the nodes in the SCC from the SCC map entirely prior to the DFS walk. This allows the SCC map to represent both the state of not-yet-re-added-to-an-SCC and added-back-to-this-SCC independently. The first is being missing from the SCC map, the second is mapping back to 'this'. In a subsequent commit, I'm going to use this property to simplify the new node list for this SCC. In theory, I think this also makes the contract for orphaning a node from the graph slightly less confusing. Now it is also orphaned from the SCC graph. Still, this isn't quite right either, and so I'm not adding test cases here. I'll add test cases for the behavior of orphaning nodes when the code *actually* supports it. The change here is mostly incidental, my goal is simplifying the algorithm. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@207213 91177308-0d34-0410-b5e6-96231b3b80d8
* [LCG] Rather than doing a linear time SmallSetVector removal of eachChandler Carruth2014-04-25
| | | | | | | | | child from the worklist, wait until we actually need to pop another element off of the worklist and skip over any that were already visited by the DFS. This also enables swapping the nodes of the SCC into the worklist. No functionality changed. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@207212 91177308-0d34-0410-b5e6-96231b3b80d8
* [LCG] Remove a completely unnecessary loop. It wasn't even doing anyChandler Carruth2014-04-25
| | | | | | | | | thing, just mucking up the code. I feel bad that I even wrote this loop. Very sorry. The diff is huge because of the indent change, but I promise all this is doing is realizing that the outer two loops were actually the exact same loops, and we didn't need two of them. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@207202 91177308-0d34-0410-b5e6-96231b3b80d8
* [LCG] Now that the loop structure of the core SCC finding routine isChandler Carruth2014-04-25
| | | | | | | | | factored into a more reasonable form, replace the tail call with a simple outer-loop continuation. It's sad that C++ makes this so awkward to write, but it seems more direct and clear than the tail call at this point. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@207201 91177308-0d34-0410-b5e6-96231b3b80d8
* blockfreq: Only one mass distribution per nodeDuncan P. N. Exon Smith2014-04-25
| | | | | | | | | | Remove the concepts of "forward" and "general" mass distributions, which was wrong. The split might have made sense in an early version of the algorithm, but it's definitely wrong now. <rdar://problem/14292693> git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@207195 91177308-0d34-0410-b5e6-96231b3b80d8
* blockfreq: Document assertionDuncan P. N. Exon Smith2014-04-25
| | | | | | <rdar://problem/14292693> git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@207194 91177308-0d34-0410-b5e6-96231b3b80d8
* blockfreq: Document high-level functionsDuncan P. N. Exon Smith2014-04-25
| | | | | | <rdar://problem/14292693> git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@207191 91177308-0d34-0410-b5e6-96231b3b80d8
* blockfreq: Scale LoopData::Scale on the way downDuncan P. N. Exon Smith2014-04-25
| | | | | | | | | | | Rather than scaling loop headers and then scaling all the loop members by the header frequency, scale `LoopData::Scale` itself, and scale the loop members by it. It's much more obvious what's going on this way, and doesn't cost any extra multiplies. <rdar://problem/14292693> git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@207189 91177308-0d34-0410-b5e6-96231b3b80d8
* blockfreq: unwrapLoopPackage() => unwrapLoop()Duncan P. N. Exon Smith2014-04-25
| | | | | | <rdar://problem/14292693> git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@207188 91177308-0d34-0410-b5e6-96231b3b80d8
* blockfreq: Pass the Loop directly into unwrapLoopPackage()Duncan P. N. Exon Smith2014-04-25
| | | | | | <rdar://problem/14292693> git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@207187 91177308-0d34-0410-b5e6-96231b3b80d8
* blockfreq: Unwrap from LoopsDuncan P. N. Exon Smith2014-04-25
| | | | | | | | When unwrapping loops, just visit the loops rather than all nodes. <rdar://problem/14292693> git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@207186 91177308-0d34-0410-b5e6-96231b3b80d8
* blockfreq: Separate unwrapLoops() from finalizeMetrics()Duncan P. N. Exon Smith2014-04-25
| | | | | | <rdar://problem/14292693> git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@207185 91177308-0d34-0410-b5e6-96231b3b80d8
* blockfreq: Expose getPackagedNode()Duncan P. N. Exon Smith2014-04-25
| | | | | | | | | Make `getPackagedNode()` a member function of `BlockFrequencyInfoImplBase` so that it's available for templated code. <rdar://problem/14292693> git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@207183 91177308-0d34-0410-b5e6-96231b3b80d8
* blockfreq: Store the header with the membersDuncan P. N. Exon Smith2014-04-25
| | | | | | <rdar://problem/14292693> git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@207182 91177308-0d34-0410-b5e6-96231b3b80d8
* blockfreq: Encapsulate LoopData::HeaderDuncan P. N. Exon Smith2014-04-25
| | | | | | <rdar://problem/14292693> git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@207181 91177308-0d34-0410-b5e6-96231b3b80d8
* blockfreq: Use LoopData directlyDuncan P. N. Exon Smith2014-04-25
| | | | | | | | Instead of passing around loop headers, pass around `LoopData` directly. <rdar://problem/14292693> git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@207179 91177308-0d34-0410-b5e6-96231b3b80d8
* blockfreq: Use a std::list for LoopsDuncan P. N. Exon Smith2014-04-25
| | | | | | | | | | | | As pointed out by David Blaikie in code review, a `std::list<T>` is simpler than a `std::vector<std::unique_ptr<T>>`. Another option is a `std::deque<T>` (which allocates in chunks), but I'd like to leave open the option of inserting in the middle of the sequence for handling irreducible control flow on the fly. <rdar://problem/14292693> git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@207177 91177308-0d34-0410-b5e6-96231b3b80d8
* [LCG] Switch a weird do/while loop that actually couldn't fail itsChandler Carruth2014-04-24
| | | | | | | condition into an obviously infinite loop with an assert about the degenerate condition. No functionality changed. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@207147 91177308-0d34-0410-b5e6-96231b3b80d8
* [LCG] Incorporate the core trick of improvements on the naive Tarjan'sChandler Carruth2014-04-24
| | | | | | | | | | | | | | | | | | | | | | | | | | | algorithm here: http://dl.acm.org/citation.cfm?id=177301. The idea of isolating the roots has even more relevance when using the stack not just to implement the DFS but also to implement the recursive step. Because we use it for the recursive step, to isolate the roots we need to maintain two stacks: one for our recursive DFS walk, and another of the nodes that have been walked. The nice thing is that the latter will be half the size. It also fixes a complete hack where we scanned backwards over the stack to find the next potential-root to continue processing. Now that is always the top of the DFS stack. While this is a really nice improvement already (IMO) it further opens the door for two important simplifications: 1) De-duplicating some of the code across the two different walks. I've actually made the duplication a bit worse in some senses with this patch because the two are starting to converge. 2) Dramatically simplifying the loop structures of both walks. I wanted to do those separately as they'll be essentially *just* CFG restructuring. This patch on the other hand actually uses different datastructures to implement the algorithm itself. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@207098 91177308-0d34-0410-b5e6-96231b3b80d8
* [LCG] Rotate logic applied to the top of the DFSStack to instead beChandler Carruth2014-04-24
| | | | | | | | | | | | | applied prior to pushing a node onto the DFSStack. This is the first step toward avoiding the stack entirely for leaf nodes. It also simplifies things a bit and I think is pointing the way toward factoring some more of the shared logic out of the two implementations. It is also making it more obvious how to restructure the loops themselves to be a bit easier to read (although no different in terms of functionality). git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@207095 91177308-0d34-0410-b5e6-96231b3b80d8
* [LCG] Switch the parent SCC tracking from a SmallSetVector toChandler Carruth2014-04-24
| | | | | | | | | | | | | | | | a SmallPtrSet. Currently, there is no need for stable iteration in this dimension, and I now thing there won't need to be going forward. If this is ever re-introduced in any form, it needs to not be a SetVector based solution because removal cannot be linear. There will be many SCCs with large numbers of parents. When encountering these, the incremental SCC update for intra-SCC edge removal was quadratic due to linear removal (kind of). I'm really hoping we can avoid having an ordering property here at all though... git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@207091 91177308-0d34-0410-b5e6-96231b3b80d8
* [LCG] We don't actually need a set in each SCC to track the nodes. WeChandler Carruth2014-04-24
| | | | | | | can use the node -> SCC mapping in the top-level graph to test this on the rare occasions we need it. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@207090 91177308-0d34-0410-b5e6-96231b3b80d8
* [C++] Use 'nullptr'.Craig Topper2014-04-24
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@207083 91177308-0d34-0410-b5e6-96231b3b80d8
* [LCG] Normalize the post-order SCC iterator to just iterate over the SCCChandler Carruth2014-04-23
| | | | | | values rather than having pointers in weird places. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@207053 91177308-0d34-0410-b5e6-96231b3b80d8
* [LCG] Switch the primary node iterator to be a *much* more normal C++Chandler Carruth2014-04-23
| | | | | | iterator, returning a Node by reference on dereference. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@207048 91177308-0d34-0410-b5e6-96231b3b80d8
* [LCG] Make the insertion and query paths into the LCG which cannot failChandler Carruth2014-04-23
| | | | | | | | return references to better model this property. No functionality changed. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@207047 91177308-0d34-0410-b5e6-96231b3b80d8
* [LCG] Switch the SCC lookup to be in terms of call graph nodes ratherChandler Carruth2014-04-23
| | | | | | | | | | than functions. So far, this access pattern is *much* more common. It seems likely that any user of this interface is going to have nodes at the point that they are querying the SCCs. No functionality changed. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@207045 91177308-0d34-0410-b5e6-96231b3b80d8
* [LCG] Switch the primary SCC building code to use the negative low-linkChandler Carruth2014-04-23
| | | | | | | | | | | | | | | values rather than an expensive dense map query to test whether children have already been popped into an SCC. This matches the incremental SCC building code. I've also included the assert that I put there but updated both of their text. No functionality changed here. I still don't have any great ideas for sharing the code between the two implementations, but I may try a brute-force approach to factoring it at some point. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@207042 91177308-0d34-0410-b5e6-96231b3b80d8
generated by cgit v1.2.3 (git 2.25.1) at 2024-05-18 15:18:25 +0000