summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis
Commit message (Collapse)AuthorAgeFilesLines
...
* [LCG] Add a unittest for the LazyCallGraph. I had a weak moment andChandler Carruth2014-04-231-0/+2
| | | | | | | | | | | | | | | | | | | | | | | | resisted this for too long. Just with the basic testing here I was able to exercise the analysis in more detail and sift out both type signature bugs in the API and a bug in the DFS numbering. All of these are fixed here as well. The unittests will be much more important for the mutation support where it is necessary to craft minimal mutations and then inspect the state of the graph. There is just no way to do that with a standard FileCheck test. However, unittesting these kinds of analyses is really quite easy, especially as they're designed with the new pass manager where there is essentially no infrastructure required to rig up the core logic and exercise it at an API level. As a minor aside about the DFS numbering bug, the DFS numbering used in LCG is a bit unusual. Rather than numbering from 0, we number from 1, and use 0 as the sentinel "unvisited" state. Other implementations often use '-1' for this, but I find it easier to deal with 0 and it shouldn't make any real difference provided someone doesn't write silly bugs like forgetting to actually initialize the DFS numbering. Oops. ;] llvm-svn: 206954
* [LCG] Hoist the logic for forming a new SCC from the top of the DFSStackChandler Carruth2014-04-231-41/+47
| | | | | | | into a helper function. I plan to re-use it for doing incremental DFS-based updates to the SCCs when we mutate the call graph. llvm-svn: 206948
* [LCG] Switch the Callee sets to be DenseMaps pointing to the index intoChandler Carruth2014-04-231-7/+8
| | | | | | | | | the Callee list. This is going to be quite important to prevent removal from going quadratic. No functionality changed at this point, this is one of the refactoring patches I've broken out of my initial work toward mutation updates of the call graph. llvm-svn: 206938
* blockfreq: Skip irreducible backedges inside functionsDuncan P. N. Exon Smith2014-04-221-1/+1
| | | | | | | | | | | | The branch that skips irreducible backedges was only active when propagating mass at the top-level. In particular, when propagating mass through a loop recognized by `LoopInfo` with irreducible control flow inside, irreducible backedges would not be skipped. Not sure where that idea came from, but the result was that mass was lost until after loop exit. Added a testcase that covers this case. llvm-svn: 206860
* blockfreq: Rename PackagedLoops => LoopsDuncan P. N. Exon Smith2014-04-221-1/+1
| | | | llvm-svn: 206859
* blockfreq: Use a pointer for ContainingLoop tooDuncan P. N. Exon Smith2014-04-221-9/+9
| | | | llvm-svn: 206858
* blockfreq: Use pointers to loops instead of an indexDuncan P. N. Exon Smith2014-04-221-4/+5
| | | | | | | | | | | | | Store pointers directly to loops inside the nodes. This could have been done without changing the type stored in `std::vector<>`. However, rather than computing the number of loops before constructing them (which `LoopInfo` doesn't provide directly), I've switched to a `vector<unique_ptr<LoopData>>`. This adds some heap overhead, but the number of loops is typically small. llvm-svn: 206857
* blockfreq: Implement clear() explicitlyDuncan P. N. Exon Smith2014-04-221-1/+5
| | | | | | | | | This was implicitly with copy assignment before, which fails to actually clear `std::vector<>`'s heap storage. Move assignment would work, but since MSVC can't imply those anyway, explicitly `clear()`-ing members makes more sense. llvm-svn: 206856
* blockfreq: Rename PackagedLoopData => LoopDataDuncan P. N. Exon Smith2014-04-221-7/+7
| | | | | | No functionality change. llvm-svn: 206855
* [Modules] Fix potential ODR violations by sinking the DEBUG_TYPEChandler Carruth2014-04-2221-25/+44
| | | | | | | | | | definition below all the header #include lines, lib/Analysis/... edition. This one has a bit extra as there were *other* #define's before #include lines in addition to DEBUG_TYPE. I've sunk all of them as a block. llvm-svn: 206843
* [Modules] Remove potential ODR violations by sinking the DEBUG_TYPEChandler Carruth2014-04-221-1/+2
| | | | | | | | | | | | define below all header includes in the lib/CodeGen/... tree. While the current modules implementation doesn't check for this kind of ODR violation yet, it is likely to grow support for it in the future. It also removes one layer of macro pollution across all the included headers. Other sub-trees will follow. llvm-svn: 206837
* [Modules] Make Support/Debug.h modular. This requires it to not changeChandler Carruth2014-04-211-0/+2
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | behavior based on other files defining DEBUG_TYPE, which means it cannot define DEBUG_TYPE at all. This is actually better IMO as it forces folks to define relevant DEBUG_TYPEs for their files. However, it requires all files that currently use DEBUG(...) to define a DEBUG_TYPE if they don't already. I've updated all such files in LLVM and will do the same for other upstream projects. This still leaves one important change in how LLVM uses the DEBUG_TYPE macro going forward: we need to only define the macro *after* header files have been #include-ed. Previously, this wasn't possible because Debug.h required the macro to be pre-defined. This commit removes that. By defining DEBUG_TYPE after the includes two things are fixed: - Header files that need to provide a DEBUG_TYPE for some inline code can do so by defining the macro before their inline code and undef-ing it afterward so the macro does not escape. - We no longer have rampant ODR violations due to including headers with different DEBUG_TYPE definitions. This may be mostly an academic violation today, but with modules these types of violations are easy to check for and potentially very relevant. Where necessary to suppor headers with DEBUG_TYPE, I have moved the definitions below the includes in this commit. I plan to move the rest of the DEBUG_TYPE macros in LLVM in subsequent commits; this one is big enough. The comments in Debug.h, which were hilariously out of date already, have been updated to reflect the recommended practice going forward. llvm-svn: 206822
* blockfreq: Some cleanup of UnsignedFloatDuncan P. N. Exon Smith2014-04-211-22/+19
| | | | | | | Change `PositiveFloat` to `UnsignedFloat`, and fix some of the comments to indicate that it's disappearing eventually. llvm-svn: 206771
* Reapply "blockfreq: Rewrite BlockFrequencyInfoImpl"Duncan P. N. Exon Smith2014-04-213-2/+939
| | | | | | | | | This reverts commit r206707, reapplying r206704. The preceding commit to CalcSpillWeights should have sorted out the failing buildbots. <rdar://problem/14292693> llvm-svn: 206766
* [PM] Add a new-PM-style CGSCC pass manager using the newly addedChandler Carruth2014-04-212-0/+168
| | | | | | | | | | | | | | | | | | | | | | | LazyCallGraph analysis framework. Wire it up all the way through the opt driver and add some very basic testing that we can build pass pipelines including these components. Still a lot more to do in terms of testing that all of this works, but the basic pieces are here. There is a *lot* of boiler plate here. It's something I'm going to actively look at reducing, but I don't have any immediate ideas that don't end up making the code terribly complex in order to fold away the boilerplate. Until I figure out something to minimize the boilerplate, almost all of this is based on the code for the existing pass managers, copied and heavily adjusted to suit the needs of the CGSCC pass management layer. The actual CG management still has a bunch of FIXMEs in it. Notably, we don't do *any* updating of the CG as it is potentially invalidated. I wanted to get this in place to motivate the new analysis, and add update APIs to the analysis and the pass management layers in concert to make sure that the *right* APIs are present. llvm-svn: 206745
* [LCG] Add some basic debug output to the LCG pass.Chandler Carruth2014-04-211-2/+17
| | | | llvm-svn: 206730
* Revert "blockfreq: Rewrite BlockFrequencyInfoImpl"Duncan P. N. Exon Smith2014-04-193-939/+2
| | | | | | This reverts commit r206704, as expected. llvm-svn: 206707
* Reapply "blockfreq: Rewrite BlockFrequencyInfoImpl"Duncan P. N. Exon Smith2014-04-193-2/+939
| | | | | | | | | | | | | | | | | | | | | This reverts commit r206677, reapplying my BlockFrequencyInfo rewrite. I've done a careful audit, added some asserts, and fixed a couple of bugs (unfortunately, they were in unlikely code paths). There's a small chance that this will appease the failing bots [1][2]. (If so, great!) If not, I have a follow-up commit ready that will temporarily add -debug-only=block-freq to the two failing tests, allowing me to compare the code path between what the failing bots and what my machines (and the rest of the bots) are doing. Once I've triggered those builds, I'll revert both commits so the bots go green again. [1]: http://bb.pgr.jp/builders/ninja-x64-msvc-RA-centos6/builds/1816 [2]: http://llvm-amd64.freebsd.your.org/b/builders/clang-i386-freebsd/builds/18445 <rdar://problem/14292693> llvm-svn: 206704
* Revert "blockfreq: Rewrite BlockFrequencyInfoImpl" (#2)Duncan P. N. Exon Smith2014-04-193-940/+2
| | | | | | | | | | | This reverts commit r206666, as planned. Still stumped on why the bots are failing. Sanitizer bots haven't turned anything up. If anyone can help me debug either of the failures (referenced in r206666) I'll owe them a beer. (In the meantime, I'll be auditing my patch for undefined behaviour.) llvm-svn: 206677
* Reapply "blockfreq: Rewrite BlockFrequencyInfoImpl" (#2)Duncan P. N. Exon Smith2014-04-183-2/+940
| | | | | | | | | | | | | | | | | | | This reverts commit r206628, reapplying r206622 (and r206626). Two tests are failing only on buildbots [1][2]: i.e., I can't reproduce on Darwin, and Chandler can't reproduce on Linux. Asan and valgrind don't tell us anything, but we're hoping the msan bot will catch it. So, I'm applying this again to get more feedback from the bots. I'll leave it in long enough to trigger builds in at least the sanitizer buildbots (it was failing for reasons unrelated to my commit last time it was in), and hopefully a few others.... and then I expect to revert a third time. [1]: http://bb.pgr.jp/builders/ninja-x64-msvc-RA-centos6/builds/1816 [2]: http://llvm-amd64.freebsd.your.org/b/builders/clang-i386-freebsd/builds/18445 llvm-svn: 206666
* [LCG] Fix the bugs that Ben pointed out in code review (and the MSan botChandler Carruth2014-04-181-3/+7
| | | | | | | caught). Sad that we don't have warnings for these things, but bleh, no idea how to fix that. llvm-svn: 206646
* Remove a couple of redundant copies of SmallVector::operator==.Benjamin Kramer2014-04-182-29/+3
| | | | | | No functionality change. llvm-svn: 206635
* Revert "blockfreq: Rewrite BlockFrequencyInfoImpl" (#2)Duncan P. N. Exon Smith2014-04-183-940/+2
| | | | | | | | | This reverts commit r206622 and the MSVC fixup in r206626. Apparently the remotely failing tests are still failing, despite my attempt to fix the nondeterminism in r206621. llvm-svn: 206628
* Fixing MSVC after r206622?Duncan P. N. Exon Smith2014-04-181-0/+2
| | | | llvm-svn: 206626
* Reapply "blockfreq: Rewrite BlockFrequencyInfoImpl"Duncan P. N. Exon Smith2014-04-183-2/+938
| | | | | | | | | | | | | | This reverts commit r206556, effectively reapplying commit r206548 and its fixups in r206549 and r206550. In an intervening commit I've added target triples to the tests that were failing remotely [1] (but passing locally). I'm hoping the mystery is solved? I'll revert this again if the tests are still failing remotely. [1]: http://bb.pgr.jp/builders/ninja-x64-msvc-RA-centos6/builds/1816 llvm-svn: 206622
* [LCG] Remove all of the complexity stemming from supporting copying.Chandler Carruth2014-04-181-42/+21
| | | | | | | | | | | | | | Reality is that we're never going to copy one of these. Supporting this was becoming a nightmare because nothing even causes it to compile most of the time. Lots of subtle errors built up that wouldn't have been caught by any "normal" testing. Also, make the move assignment actually work rather than the bogus swap implementation that would just infloop if used. As part of that, factor out the graph pointer updates into a helper to share between move construction and move assignment. llvm-svn: 206583
* [LCG] Add support for building persistent and connected SCCs to theChandler Carruth2014-04-181-4/+118
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | LazyCallGraph. This is the start of the whole point of this different abstraction, but it is just the initial bits. Here is a run-down of what's going on here. I'm planning to incorporate some (or all) of this into comments going forward, hopefully with better editing and wording. =] The crux of the problem with the traditional way of building SCCs is that they are ephemeral. The new pass manager however really needs the ability to associate analysis passes and results of analysis passes with SCCs in order to expose these analysis passes to the SCC passes. Making this work is kind-of the whole point of the new pass manager. =] So, when we're building SCCs for the call graph, we actually want to build persistent nodes that stick around and can be reasoned about later. We'd also like the ability to walk the SCC graph in more complex ways than just the traditional postorder traversal of the current CGSCC walk. That means that in addition to being persistent, the SCCs need to be connected into a useful graph structure. However, we still want the SCCs to be formed lazily where possible. These constraints are quite hard to satisfy with the SCC iterator. Also, using that would bypass our ability to actually add data to the nodes of the call graph to facilite implementing the Tarjan walk. So I've re-implemented things in a more direct and embedded way. This immediately makes it easy to get the persistence and connectivity correct, and it also allows leveraging the existing nodes to simplify the algorithm. I've worked somewhat to make this implementation more closely follow the traditional paper's nomenclature and strategy, although it is still a bit obtuse because it isn't recursive, using an explicit stack and a tail call instead, and it is interruptable, resuming each time we need another SCC. The other tricky bit here, and what actually took almost all the time and trials and errors I spent building this, is exactly *what* graph structure to build for the SCCs. The naive thing to build is the call graph in its newly acyclic form. I wrote about 4 versions of this which did precisely this. Inevitably, when I experimented with them across various use cases, they became incredibly awkward. It was all implementable, but it felt like a complete wrong fit. Square peg, round hole. There were two overriding aspects that pushed me in a different direction: 1) We want to discover the SCC graph in a postorder fashion. That means the root node will be the *last* node we find. Using the call-SCC DAG as the graph structure of the SCCs results in an orphaned graph until we discover a root. 2) We will eventually want to walk the SCC graph in parallel, exploring distinct sub-graphs independently, and synchronizing at merge points. This again is not helped by the call-SCC DAG structure. The structure which, quite surprisingly, ended up being completely natural to use is the *inverse* of the call-SCC DAG. We add the leaf SCCs to the graph as "roots", and have edges to the caller SCCs. Once I switched to building this structure, everything just fell into place elegantly. Aside from general cleanups (there are FIXMEs and too few comments overall) that are still needed, the other missing piece of this is support for iterating across levels of the SCC graph. These will become useful for implementing #2, but they aren't an immediate priority. Once SCCs are in good shape, I'll be working on adding mutation support for incremental updates and adding the pass manager that this analysis enables. llvm-svn: 206581
* Revert "blockfreq: Rewrite BlockFrequencyInfoImpl"Duncan P. N. Exon Smith2014-04-183-938/+2
| | | | | | | | | | | This reverts commits r206548, r206549 and r206549. There are some unit tests failing that aren't failing locally [1], so reverting until I have time to investigate. [1]: http://bb.pgr.jp/builders/ninja-x64-msvc-RA-centos6/builds/1816 llvm-svn: 206556
* blockfreq: Really fix r206548 (and r206549)Duncan P. N. Exon Smith2014-04-181-32/+0
| | | | | | Turns out this code is dead. llvm-svn: 206554
* blockfreq: Fixing MSVC after r206548?Duncan P. N. Exon Smith2014-04-181-2/+2
| | | | llvm-svn: 206549
* blockfreq: Rewrite BlockFrequencyInfoImplDuncan P. N. Exon Smith2014-04-183-2/+970
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Rewrite the shared implementation of BlockFrequencyInfo and MachineBlockFrequencyInfo entirely. The old implementation had a fundamental flaw: precision losses from nested loops (or very wide branches) compounded past loop exits (and convergence points). The @nested_loops testcase at the end of test/Analysis/BlockFrequencyAnalysis/basic.ll is motivating. This function has three nested loops, with branch weights in the loop headers of 1:4000 (exit:continue). The old analysis gives non-sensical results: Printing analysis 'Block Frequency Analysis' for function 'nested_loops': ---- Block Freqs ---- entry = 1.0 for.cond1.preheader = 1.00103 for.cond4.preheader = 5.5222 for.body6 = 18095.19995 for.inc8 = 4.52264 for.inc11 = 0.00109 for.end13 = 0.0 The new analysis gives correct results: Printing analysis 'Block Frequency Analysis' for function 'nested_loops': block-frequency-info: nested_loops - entry: float = 1.0, int = 8 - for.cond1.preheader: float = 4001.0, int = 32007 - for.cond4.preheader: float = 16008001.0, int = 128064007 - for.body6: float = 64048012001.0, int = 512384096007 - for.inc8: float = 16008001.0, int = 128064007 - for.inc11: float = 4001.0, int = 32007 - for.end13: float = 1.0, int = 8 Most importantly, the frequency leaving each loop matches the frequency entering it. The new algorithm leverages BlockMass and PositiveFloat to maintain precision, separates "probability mass distribution" from "loop scaling", and uses dithering to eliminate probability mass loss. I have unit tests for these types out of tree, but it was decided in the review to make the classes private to BlockFrequencyInfoImpl, and try to shrink them (or remove them entirely) in follow-up commits. The new algorithm should generally have a complexity advantage over the old. The previous algorithm was quadratic in the worst case. The new algorithm is still worst-case quadratic in the presence of irreducible control flow, but it's linear without it. The key difference between the old algorithm and the new is that control flow within a loop is evaluated separately from control flow outside, limiting propagation of precision problems and allowing loop scale to be calculated independently of mass distribution. Loops are visited bottom-up, their loop scales are calculated, and they are replaced by pseudo-nodes. Mass is then distributed through the function, which is now a DAG. Finally, loops are revisited top-down to multiply through the loop scales and the masses distributed to pseudo nodes. There are some remaining flaws. - Irreducible control flow isn't modelled correctly. LoopInfo and MachineLoopInfo ignore irreducible edges, so this algorithm will fail to scale accordingly. There's a note in the class documentation about how to get closer. See also the comments in test/Analysis/BlockFrequencyInfo/irreducible.ll. - Loop scale is limited to 4096 per loop (2^12) to avoid exhausting the 64-bit integer precision used downstream. - The "bias" calculation proposed on llvmdev is *not* incorporated here. This will be added in a follow-up commit, once comments from this review have been handled. llvm-svn: 206548
* remove some dead codeNuno Lopes2014-04-173-20/+0
| | | | | | | | | | | | | | | lib/Analysis/IPA/InlineCost.cpp | 18 ------------------ lib/Analysis/RegionPass.cpp | 1 - lib/Analysis/TypeBasedAliasAnalysis.cpp | 1 - lib/Transforms/Scalar/LoopUnswitch.cpp | 21 --------------------- lib/Transforms/Utils/LCSSA.cpp | 2 -- lib/Transforms/Utils/LoopSimplify.cpp | 6 ------ utils/TableGen/AsmWriterEmitter.cpp | 13 ------------- utils/TableGen/DFAPacketizerEmitter.cpp | 7 ------- utils/TableGen/IntrinsicEmitter.cpp | 2 -- 9 files changed, 71 deletions(-) llvm-svn: 206506
* Reverse 206485.Gerolf Hoflehner2014-04-171-8/+2
| | | | | | | | | After some discussions the preferred semantics of the always_inline attribute is inline always when the compiler can determine that it it safe to do so. llvm-svn: 206487
* [LCG] Just move the allocator (now that we can) when moving a callChandler Carruth2014-04-171-28/+14
| | | | | | | | | graph. This simplifies the custom move constructor operation to one of walking the graph and updating the 'up' pointers to point to the new location of the graph. Switch the nodes from a reference to a pointer for the 'up' edge to facilitate this. llvm-svn: 206450
* [LCG] Remove the Module reference member which we weren't using forChandler Carruth2014-04-171-3/+3
| | | | | | anything and doesn't make sense if assigning. llvm-svn: 206449
* Inline a function when the always_inline attributeGerolf Hoflehner2014-04-171-2/+8
| | | | | | | | | | is set even when it contains a indirect branch. The attribute overrules correctness concerns like the escape of a local block address. This is for rdar://16501761 llvm-svn: 206429
* RegionInfo: Do not access a value that was just moved awayTobias Grosser2014-04-151-1/+1
| | | | | | This fixes a regression introduced in r206310. llvm-svn: 206328
* Use unique_ptr to manage ownership of child Regions within llvm::RegionDavid Blaikie2014-04-153-31/+35
| | | | llvm-svn: 206310
* [C++11] More 'nullptr' conversion. In some cases just using a boolean check ↵Craig Topper2014-04-1539-505/+512
| | | | | | instead of comparing to nullptr. llvm-svn: 206243
* Fix a bug in which BranchProbabilityInfo wasn't setting branch weights of ↵Akira Hatanaka2014-04-141-0/+3
| | | | | | | | | | | | basic blocks inside loops correctly. Previously, BranchProbabilityInfo::calcLoopBranchHeuristics would determine the weights of basic blocks inside loops even when it didn't have enough information to estimate the branch probabilities correctly. This patch fixes the function to exit early if it doesn't see any exit edges or back edges and let the later heuristics determine the weights. This fixes PR18705 and <rdar://problem/15991090>. Differential Revision: http://reviews.llvm.org/D3363 llvm-svn: 206194
* blockfreq: Rename BlockFrequencyImpl to BlockFrequencyInfoImplDuncan P. N. Exon Smith2014-04-111-2/+2
| | | | | | | | | | | | This is a shared implementation class for BlockFrequencyInfo and MachineBlockFrequencyInfo, not for BlockFrequency, a related (but distinct) class. No functionality change. <rdar://problem/14292693> llvm-svn: 206083
* blockfreq: Use getSuccessorIndex()Duncan P. N. Exon Smith2014-04-111-5/+3
| | | | | | | | No functionality change. <rdar://problem/14292693> llvm-svn: 206082
* Delinearize: Extend informationin -analyze outputTobias Grosser2014-04-091-0/+4
| | | | llvm-svn: 205838
* divide by the result of the gcdSebastian Pop2014-04-081-1/+1
| | | | | | used to fail with 'Step should divide Start with no remainder.' llvm-svn: 205802
* handle special cases when findGCD returns 1Sebastian Pop2014-04-081-1/+6
| | | | | | used to fail with 'Step should divide Start with no remainder.' llvm-svn: 205801
* in findGCD of multiply expr return the gcdSebastian Pop2014-04-081-2/+4
| | | | | | we used to return 1 instead of the gcd llvm-svn: 205800
* Handle vlas during inline cost computation if they'll be turnedEric Christopher2014-04-071-1/+10
| | | | | | | | | | | into a constant size alloca by inlining. Ran a run over the testsuite, no results out of the noise, fixes the testcase in the PR. PR19115. llvm-svn: 205710
* Use TopTTI->getGEPCost from within getUserCostHal Finkel2014-04-011-4/+4
| | | | | | | | | | | The implementation of getUserCost had duplicated (and hard-coded) the default logic in getGEPCost. Instead, it is better to use getGEPCost directly, which limits the default logic to the implementation of one function, and allows targets to override the behavior. No functionality change intended. llvm-svn: 205346
* PR15967 Fix in basicaa for faulty returning no alias.Arnold Schwaighofer2014-03-261-11/+38
| | | | | | | | | | | | | | This commit consist of two parts. The first part fix the PR15967. The wrong conclusion was made when the MaxLookup limit was reached. The fix introduce a out parameter (MaxLookupReached) to DecomposeGEPExpression that the function aliasGEP can act upon. The second part is introducing the constant MaxLookupSearchDepth to make sure that DecomposeGEPExpression and GetUnderlyingObject use the same search depth. This is a small cleanup to clarify the original algorithm. Patch by Karl-Johan Karlsson! llvm-svn: 204859
* blockfreq: Implement Pass::releaseMemory()Duncan P. N. Exon Smith2014-03-251-9/+10
| | | | | | | | | | Implement Pass::releaseMemory() in BlockFrequencyInfo and MachineBlockFrequencyInfo. Just delete the private implementation when not in use. Switch to a std::unique_ptr to make the logic more clear. <rdar://problem/14292693> llvm-svn: 204741
OpenPOWER on IntegriCloud