summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis
Commit message (Collapse)AuthorAgeFilesLines
* Revert "Revert "Add Constant Hoisting Pass" (r200034)"Juergen Ributzka2014-01-251-1/+21
| | | | | | | This reverts commit r200058 and adds the using directive for ARMTargetTransformInfo to silence two g++ overload warnings. llvm-svn: 200062
* Revert "Add Constant Hoisting Pass" (r200034)Hans Wennborg2014-01-251-21/+1
| | | | | | | | | | | | | | | This commit caused -Woverloaded-virtual warnings. The two new TargetTransformInfo::getIntImmCost functions were only added to the superclass, and to the X86 subclass. The other targets were not updated, and the warning highlighted this by pointing out that e.g. ARMTTI::getIntImmCost was hiding the two new getIntImmCost variants. We could pacify the warning by adding "using TargetTransformInfo::getIntImmCost" to the various subclasses, or turning it off, but I suspect that it's wrong to leave the functions unimplemnted in those targets. The default implementations return TCC_Free, which I don't think is right e.g. for ARM. llvm-svn: 200058
* Add Constant Hoisting PassJuergen Ributzka2014-01-241-1/+21
| | | | | | | | Retry commit r200022 with a fix for the build bot errors. Constant expressions have (unlike instructions) module scope use lists and therefore may have users in different functions. The fix is to simply ignore these out-of-function uses. llvm-svn: 200034
* Revert "Add Constant Hoisting Pass"Juergen Ributzka2014-01-241-21/+1
| | | | | | This reverts commit r200022 to unbreak the build bots. llvm-svn: 200024
* Add Constant Hoisting PassJuergen Ributzka2014-01-241-1/+21
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This pass identifies expensive constants to hoist and coalesces them to better prepare it for SelectionDAG-based code generation. This works around the limitations of the basic-block-at-a-time approach. First it scans all instructions for integer constants and calculates its cost. If the constant can be folded into the instruction (the cost is TCC_Free) or the cost is just a simple operation (TCC_BASIC), then we don't consider it expensive and leave it alone. This is the default behavior and the default implementation of getIntImmCost will always return TCC_Free. If the cost is more than TCC_BASIC, then the integer constant can't be folded into the instruction and it might be beneficial to hoist the constant. Similar constants are coalesced to reduce register pressure and materialization code. When a constant is hoisted, it is also hidden behind a bitcast to force it to be live-out of the basic block. Otherwise the constant would be just duplicated and each basic block would have its own copy in the SelectionDAG. The SelectionDAG recognizes such constants as opaque and doesn't perform certain transformations on them, which would create a new expensive constant. This optimization is only applied to integer constants in instructions and simple (this means not nested) constant cast experessions. For example: %0 = load i64* inttoptr (i64 big_constant to i64*) Reviewed by Eric llvm-svn: 200022
* Add final and owerride keywords to TargetTransformInfo's subclasses.Juergen Ributzka2014-01-241-45/+53
| | | | llvm-svn: 200021
* Fix known typosAlp Toker2014-01-243-6/+6
| | | | | | | Sweep the codebase for common typos. Includes some changes to visible function names that were misspelt. llvm-svn: 200018
* InstSimplify: Make shift, select and GEP simplifications vector-aware.Benjamin Kramer2014-01-241-18/+41
| | | | llvm-svn: 200016
* Get right cost for addrspacecast in cost modelMatt Arsenault2014-01-221-1/+2
| | | | llvm-svn: 199833
* [PM] Make the verifier work independently of any pass manager.Chandler Carruth2014-01-191-6/+19
| | | | | | | | | | | | | | | | | | | | | | | This makes the 'verifyFunction' and 'verifyModule' functions totally independent operations on the LLVM IR. It also cleans up their API a bit by lifting the abort behavior into their clients and just using an optional raw_ostream parameter to control printing. The implementation of the verifier is now just an InstVisitor with no multiple inheritance. It also is significantly more const-correct, and hides the const violations internally. The two layers that force us to break const correctness are building a DomTree and dispatching through the InstVisitor. A new VerifierPass is used to implement the legacy pass manager interface in terms of the other pieces. The error messages produced may be slightly different now, and we may have slightly different short circuiting behavior with different usage models of the verifier, but generally everything works equivalently and this unblocks wiring the verifier up to the new pass manager. llvm-svn: 199569
* BasicAA: We need to check both access sizes when comparing a gep and anArnold Schwaighofer2014-01-161-1/+9
| | | | | | | | underlying object of unknown size. Fixes PR18460. llvm-svn: 199351
* Fix PR18449: SCEV needs more precise max BECount for multi-exit loop.Andrew Trick2014-01-151-14/+30
| | | | llvm-svn: 199299
* Make nocapture analysis work with addrspacecastMatt Arsenault2014-01-141-0/+1
| | | | llvm-svn: 199246
* [PM] Split DominatorTree into a concrete analysis result object whichChandler Carruth2014-01-139-30/+56
| | | | | | | | | | | | | | | | | | | | | | | can be used by both the new pass manager and the old. This removes it from any of the virtual mess of the pass interfaces and lets it derive cleanly from the DominatorTreeBase<> template. In turn, tons of boilerplate interface can be nuked and it turns into a very straightforward extension of the base DominatorTree interface. The old analysis pass is now a simple wrapper. The names and style of this split should match the split between CallGraph and CallGraphWrapperPass. All of the users of DominatorTree have been updated to match using many of the same tricks as with CallGraph. The goal is that the common type remains the resulting DominatorTree rather than the pass. This will make subsequent work toward the new pass manager significantly easier. Also in numerous places things became cleaner because I switched from re-running the pass (!!! mid way through some other passes run!!!) to directly recomputing the domtree. llvm-svn: 199104
* [PM] Pull the generic graph algorithms and data structures for dominatorChandler Carruth2014-01-131-1/+1
| | | | | | | | | | | | | | | | | | | | | | | | | trees into the Support library. These are all expressed in terms of the generic GraphTraits and CFG, with no reliance on any concrete IR types. Putting them in support clarifies that and makes the fact that the static analyzer in Clang uses them much more sane. When moving the Dominators.h file into the IR library I claimed that this was the right home for it but not something I planned to work on. Oops. So why am I doing this? It happens to be one step toward breaking the requirement that IR verification can only be performed from inside of a pass context, which completely blocks the implementation of verification for the new pass manager infrastructure. Fixing it will also allow removing the concept of the "preverify" step (WTF???) and allow the verifier to cleanly flag functions which fail verification in a way that precludes even computing dominance information. Currently, that results in a fatal error even when you ask the verifier to not fatally error. It's awesome like that. The yak shaving will continue... llvm-svn: 199095
* [cleanup] Move the Dominators.h and Verifier.h headers into the IRChandler Carruth2014-01-1314-14/+14
| | | | | | | | | | | | | | | | | | directory. These passes are already defined in the IR library, and it doesn't make any sense to have the headers in Analysis. Long term, I think there is going to be a much better way to divide these matters. The dominators code should be fully separated into the abstract graph algorithm and have that put in Support where it becomes obvious that evn Clang's CFGBlock's can use it. Then the verifier can manually construct dominance information from the Support-driven interface while the Analysis library can provide a pass which both caches, reconstructs, and supports a nice update API. But those are very long term, and so I don't want to leave the really confusing structure until that day arrives. llvm-svn: 199082
* [PM] Rename the IR printing pass header to a more generic and correctChandler Carruth2014-01-121-1/+1
| | | | | | | | name to match the source file which I got earlier. Update the include sites. Also modernize the comments in the header to use the more recommended doxygen style. llvm-svn: 199041
* Fixed old typo in ScalarEvolution, that caused wrong SCEVs zext operation.Stepan Dyatkovskiy2014-01-091-1/+1
| | | | | | | | | Detailed description is here: http://llvm.org/bugs/show_bug.cgi?id=18000#c16 For participation in bugfix process special thanks to David Wiberg. llvm-svn: 198863
* Put the functionality for printing a value to a raw_ostream as anChandler Carruth2014-01-0914-40/+26
| | | | | | | | | | | | operand into the Value interface just like the core print method is. That gives a more conistent organization to the IR printing interfaces -- they are all attached to the IR objects themselves. Also, update all the users. This removes the 'Writer.h' header which contained only a single function declaration. llvm-svn: 198836
* Move the LLVM IR asm writer header files into the IR directory, as theyChandler Carruth2014-01-0715-15/+15
| | | | | | | | | | | | | | | | | are part of the core IR library in order to support dumping and other basic functionality. Rename the 'Assembly' include directory to 'AsmParser' to match the library name and the only functionality left their -- printing has been in the core IR library for quite some time. Update all of the #includes to match. All of this started because I wanted to have the layering in good shape before I started adding support for printing LLVM IR using the new pass infrastructure, and commandline support for the new pass infrastructure. llvm-svn: 198688
* Re-sort all of the includes with ./utils/sort_includes.py so thatChandler Carruth2014-01-0710-15/+14
| | | | | | | | | | subsequent changes are easier to review. About to fix some layering issues, and wanted to separate out the necessary churn. Also comment and sink the include of "Windows.h" in three .inc files to match the usage in Memory.inc. llvm-svn: 198685
* Fix comment of findGCD.Mingjie Xing2014-01-071-2/+2
| | | | llvm-svn: 198660
* [PM] Add a definition for the static PassID in the CallGraphAnalysis.Chandler Carruth2014-01-051-0/+6
| | | | | | | Missed this when adding the skeleton analysis. Caught by a build break in the next patch I'm working on when trying to use the analysis. llvm-svn: 198556
* BasicAA: Use reachabilty instead of dominance for checking value equality in phiArnold Schwaighofer2014-01-031-28/+35
| | | | | | | | | | | | | | | | | | | | | cycles This allows the value equality check to work even if we don't have a dominator tree. Also add some more comments. I was worried about compile time impacts and did not implement reachability but used the dominance check in the initial patch. The trade-off was that the dominator tree was required. The llvm utility function isPotentiallyReachable cuts off the recursive search after 32 visits. Testing did not show any compile time regressions showing my worries unjustfied. No compile time or performance regressions at O3 -flto -mavx on test-suite + externals. Addresses review comments from r198290. llvm-svn: 198400
* BasicAA: Fix value equality and phi cyclesArnold Schwaighofer2014-01-021-37/+112
| | | | | | | | | | | | | | | | | | | | | | | | | When there are cycles in the value graph we have to be careful interpreting "Value*" identity as "value" equivalence. We interpret the value of a phi node as the value of its operands. When we check for value equivalence now we make sure that the "Value*" dominates all cycles (phis). %0 = phi [%noaliasval, %addr2] %l = load %ptr %addr1 = gep @a, 0, %l %addr2 = gep @a, 0, (%l + 1) store %ptr ... Before this patch we would return NoAlias for (%0, %addr1) which is wrong because the value of the load is from different iterations of the loop. Tested on x86_64 -mavx at O3 and O3 -flto with no performance or compile time regressions. PR18068 radar://15653794 llvm-svn: 198290
* BlockFrequencyInfo: Readded getEntryFreq.Yuchen Wu2013-12-201-0/+4
| | | | llvm-svn: 197839
* [block-freq] Teach branch probability how to return the edge weight in ↵Michael Gottesman2013-12-141-0/+10
| | | | | | | | | | between a BasicBlock and one of its successors. IMHO At some point BasicBlock should be refactored along the lines of MachineBasicBlock so that successors/weights are actually embedded within the block. Now is not that time though. llvm-svn: 197303
* Teach MemoryBuiltins about address spacesMatt Arsenault2013-12-141-5/+11
| | | | llvm-svn: 197292
* [block-freq] Update BlockFrequencyInfo/MachineBlockFrequencyInfo to use the ↵Michael Gottesman2013-12-141-1/+1
| | | | | | new print methods. llvm-svn: 197289
* [block-freq] Add the equivalent methods to MachineBlockFrequencyInfo and ↵Michael Gottesman2013-12-141-0/+11
| | | | | | BlockFrequencyInfo that were added to BlockFrequencyImpl in r197285 and r197284. llvm-svn: 197287
* [inliner] Fix PR18206 by preventing inlining functions that call setjmpChandler Carruth2013-12-131-1/+1
| | | | | | | | | | | | | through an invoke instruction. The original patch for this was written by Mark Seaborn, but I've reworked his test case into the existing returns_twice test case and implemented the fix by the prior refactoring to actually run the cost analysis over invoke instructions, and then here fixing our detection of the returns_twice attribute to work for both calls and invokes. We never noticed because we never saw an invoke. =[ llvm-svn: 197216
* [inliner] Completely change (and fix) how the inline cost analysisChandler Carruth2013-12-131-37/+76
| | | | | | | | | | | | | | | | | | | | | | | | | | | | handles terminator instructions. The inline cost analysis inheritted some pretty rough handling of terminator insts from the original cost analysis, and then made it much, much worse by factoring all of the important analyses into a separate instruction visitor. That instruction visitor never visited the terminator. This works fine for things like conditional branches, but for many other things we simply computed The Wrong Value. First example are unconditional branches, which should be free but were counted as full cost. This is most significant for conditional branches where the condition simplifies and folds during inlining. We paid a 1 instruction tax on every branch in a straight line specialized path. =[ Oh, we also claimed that the unreachable instruction had cost. But it gets worse. Let's consider invoke. We never applied the call penalty. We never accounted for the cost of the arguments. Nope. Worse still, we didn't handle the *correctness* constraints of not inlining recursive invokes, or exception throwing returns_twice functions. Oops. See PR18206. Sadly, PR18206 requires yet another fix, but this refactoring is at least a huge step in that direction. llvm-svn: 197215
* [cleanup] Remove trailing whitespace before I start changing this file.Chandler Carruth2013-12-121-1/+1
| | | | llvm-svn: 197149
* Don't #include heavy Dominators.h file in LoopInfo.h. This change reducesJakub Staszak2013-12-071-0/+1
| | | | | | overall time of LLVM compilation by ~1%. llvm-svn: 196667
* Correct word hyphenationsAlp Toker2013-12-052-2/+2
| | | | | | | This patch tries to avoid unrelated changes other than fixing a few hyphen-related ambiguities and contractions in nearby lines. llvm-svn: 196471
* Fix typo.Eric Christopher2013-12-041-1/+1
| | | | llvm-svn: 196434
* [PM] Split the CallGraph out from the ModulePass which creates theChandler Carruth2013-11-265-81/+116
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | CallGraph. This makes the CallGraph a totally generic analysis object that is the container for the graph data structure and the primary interface for querying and manipulating it. The pass logic is separated into its own class. For compatibility reasons, the pass provides wrapper methods for most of the methods on CallGraph -- they all just forward. This will allow the new pass manager infrastructure to provide its own analysis pass that constructs the same CallGraph object and makes it available. The idea is that in the new pass manager, the analysis pass's 'run' method returns a concrete analysis 'result'. Here, that result is a 'CallGraph'. The 'run' method will typically do only minimal work, deferring much of the work into the implementation of the result object in order to be lazy about computing things, but when (like DomTree) there is *some* up-front computation, the analysis does it prior to handing the result back to the querying pass. I know some of this is fairly ugly. I'm happy to change it around if folks can suggest a cleaner interim state, but there is going to be some amount of unavoidable ugliness during the transition period. The good thing is that this is very limited and will naturally go away when the old pass infrastructure goes away. It won't hang around to bother us later. Next up is the initial new-PM-style call graph analysis. =] llvm-svn: 195722
* [PM] Reformat some code with clang-format as I'm going to be editting asChandler Carruth2013-11-261-21/+12
| | | | | | | part of generalizing the call graph infrastructure for the new pass manager. llvm-svn: 195718
* [PM] Rename the 'Mod' member to the more idiomatic 'M'. No functionalityChandler Carruth2013-11-261-3/+3
| | | | | | changed. llvm-svn: 195701
* Don't speculate loads under ThreadSanitizerKostya Serebryany2013-11-211-1/+3
| | | | | | | | | | | | | | | | | Summary: Don't speculate loads under ThreadSanitizer. This fixes https://code.google.com/p/thread-sanitizer/issues/detail?id=40 Also discussed here: http://lists.cs.uiuc.edu/pipermail/llvmdev/2013-November/067929.html Reviewers: chandlerc Reviewed By: chandlerc CC: llvm-commits, dvyukov Differential Revision: http://llvm-reviews.chandlerc.com/D2227 llvm-svn: 195324
* The 'optnone' attribute means don't inline anything into this functionPaul Robinson2013-11-181-0/+4
| | | | | | | | | | (except functions marked always_inline). Functions with 'optnone' must also have 'noinline' so they don't get inlined into any other function. Based on work by Andrea Di Biagio. llvm-svn: 195046
* Annotate APInt methods where it's not clear whether they are in place with ↵Benjamin Kramer2013-11-161-6/+6
| | | | | | | | warn_unused_result. Fix ScalarEvolution bugs uncovered by this. llvm-svn: 194928
* Use correct size for address space in BasicAA.Matt Arsenault2013-11-161-2/+3
| | | | | | | | | | | | The tests just hit this with a different sized address space since I haven't figured out how to use this to break it. I thought I committed this a long time ago, and I'm not sure why missing this hasn't caused any problems. llvm-svn: 194903
* Add addrspacecast instruction.Matt Arsenault2013-11-151-5/+7
| | | | | | Patch by Michele Scandale! llvm-svn: 194760
* Added BlockFrequencyInfo::view for displaying the block frequency ↵Michael Gottesman2013-11-141-0/+103
| | | | | | | | | | propagation graph via graphviz. This is useful for debugging issues in the BlockFrequency implementation since one can easily visualize where probability mass and other errors occur in the propagation. llvm-svn: 194654
* Fixing a heisenbug where the memory dependence analysis behaves differentlyYunzhong Gao2013-11-141-5/+6
| | | | | | | | | | | | with and without -g. Adding a test case to make sure that the threshold used in the memory dependence analysis is respected. The test case also checks that debug intrinsics are not counted towards this threshold. Differential Revision: http://llvm-reviews.chandlerc.com/D2141 llvm-svn: 194646
* Fixed 80+ violations.Michael Gottesman2013-11-141-5/+5
| | | | llvm-svn: 194634
* add more comments around the delinearization of arraysSebastian Pop2013-11-133-17/+88
| | | | llvm-svn: 194612
* Simplify code. No functionality change.Jakub Staszak2013-11-131-8/+8
| | | | llvm-svn: 194602
* Move Delinearization pass into an anonymous namespace.Benjamin Kramer2013-11-131-0/+4
| | | | llvm-svn: 194582
OpenPOWER on IntegriCloud