summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis
Commit message (Collapse)AuthorAgeFilesLines
...
* Fix a stunning oversight in the inline cost analysis. It was neverChandler Carruth2012-12-281-4/+16
| | | | | | | | | | | | | | | | | | | | | | | | | | | propagating one of the values it simplified to a constant across a myriad of instructions. Notably, ptrtoint instructions when we had a constant pointer (say, 0) didn't propagate that, blocking a massive number of down-stream optimizations. This was uncovered when investigating why we fail to inline and delete the boilerplate in: void f() { std::vector<int> v; v.push_back(1); } It turns out most of the efforts I've made thus far to improve the analysis weren't making it far purely because of this. After this is fixed, the store-to-load forwarding patch enables LLVM to optimize the above to an empty function. We still can't nuke a second push_back, but for different reasons. There is a very real chance this will cause somewhat noticable changes in inlining behavior, so please let me know if you see regressions (or improvements!) because of this patch. llvm-svn: 171196
* Teach the inline cost analysis about calls that can be simplified andChandler Carruth2012-12-281-11/+87
| | | | | | | | | | | | | | | | | | | | | how to propagate constants through insert and extract value instructions. With the recent improvements to instsimplify, this allows inline cost analysis to constant fold through intrinsic functions, including notably the with.overflow intrinsic math routines which often show up inside of STL abstractions. This is yet another piece in the puzzle of breaking down the code for: void f() { std::vector<int> v; v.push_back(1); } But it still isn't enough. There are a pile of bugs in inline cost still blocking this. llvm-svn: 171195
* Teach instsimplify to use the constant folder where appropriate forChandler Carruth2012-12-281-8/+29
| | | | | | | | constant folding calls. Add the initial tests for this which show that now instsimplify can simplify blindingly obvious code patterns expressed with both intrinsics and library calls. llvm-svn: 171194
* Add entry points to instsimplify for simplifying calls. The entry pointsChandler Carruth2012-12-281-5/+30
| | | | | | | | | | are nice and decomposed so that we can simplify synthesized calls as easily as actually call instructions. The internal utility still has the same behavior, it just now operates on a more generic interface so that I can extend the set of call simplifications that instsimplify knows about. llvm-svn: 171189
* Add LLVMContext::emitWarning methods and use them. <rdar://problem/12867368>Bob Wilson2012-12-242-10/+11
| | | | | | | | | When the backend is used from clang, it should produce proper diagnostics instead of just printing messages to errs(). Other clients may also want to register their own error handlers with the LLVMContext, and the same handler should work for warnings in the same way as the existing emitError methods. llvm-svn: 171041
* Update the docs of the cost model.Nadav Rotem2012-12-241-3/+6
| | | | llvm-svn: 171016
* Remove trailing whitespace.Craig Topper2012-12-221-94/+94
| | | | llvm-svn: 170991
* Add a new attribute, 'noduplicate'. If a function contains a noduplicate ↵James Molloy2012-12-203-7/+40
| | | | | | | | call, the call cannot be duplicated - Jump threading, loop unrolling, loop unswitching, and loop rotation are inhibited if they would duplicate the call. Similarly inlining of the function is inhibited, if that would duplicate the call (in particular inlining is still allowed when there is only one callsite and the function has internal linkage). llvm-svn: 170704
* Fix a bug that was found by building clang with -fsanitize.Nadav Rotem2012-12-191-1/+6
| | | | | | | | | I introduced it in r166785. PR14291. If TD is unavailable use getScalarSizeInBits, but don't optimize pointers or vectors of pointers. llvm-svn: 170586
* Rename the 'Attributes' class to 'Attribute'. It's going to represent a ↵Bill Wendling2012-12-195-8/+8
| | | | | | single attribute in the future. llvm-svn: 170502
* Fix a crash in ValueTracking on vectors of pointers. Nadav Rotem2012-12-141-1/+1
| | | | llvm-svn: 170240
* Rename isPowerOfTwo to isKnownToBeAPowerOfTwo.Rafael Espindola2012-12-132-13/+13
| | | | | | | | In a previous thread it was pointed out that isPowerOfTwo is not a very precise name since it can return false for powers of two if it is unable to show that they are powers of two. llvm-svn: 170093
* The TargetData is not used for the isPowerOfTwo determination. It has neverRafael Espindola2012-12-122-13/+12
| | | | | | | | | | been used in the first place. It simply was passed to the function and to the recursive invocations. Simply drop the parameter and update the callers for the new signature. Patch by Saleem Abdulrasool! llvm-svn: 169988
* Have SimplifyBinOp call the new FAdd/FSub/FMul helpers, with fast-math flags offMichael Ilseman2012-12-121-0/+8
| | | | llvm-svn: 169943
* Added a slew of SimplifyInstruction floating-point optimizations, many of ↵Michael Ilseman2012-12-121-10/+109
| | | | | | | | | | | | | | | | which take advantage of fast-math flags. Test cases included. fsub X, +0 ==> X fsub X, -0 ==> X, when we know X is not -0 fsub +/-0.0, (fsub -0.0, X) ==> X fsub nsz +/-0.0, (fsub +/-0.0, X) ==> X fsub nnan ninf X, X ==> 0.0 fadd nsz X, 0 ==> X fadd [nnan ninf] X, (fsub [nnan ninf] 0, X) ==> 0 where nnan and ninf have to occur at least once somewhere in this expression fmul X, 1.0 ==> X llvm-svn: 169940
* Holding my nose and moving the accumulation routine to GEPOperatorChandler Carruth2012-12-111-34/+1
| | | | | | | | | | | | | | | | | instead of the instruction. I've left a forwarding wrapper for the instruction so users with the instruction don't need to create a GEPOperator themselves. This lets us remove the copy of this code in instsimplify. I've looked at most of the other copies of similar code, and this is the only one I've found that is actually exactly the same. The one in InlineCost is very close, but it requires re-mapping non-constant indices through the cost analysis value simplification map. I could add direct support for this to the generic routine, but it seems overly specific. llvm-svn: 169853
* Hoist the GEP constant address offset computation to a common home onChandler Carruth2012-12-111-23/+1
| | | | | | | | | | | the GEP instruction class. This is part of the continued refactoring and cleaning of the infrastructure used by SROA. This particular operation is also done in a few other places which I'll try to refactor to share this implementation. llvm-svn: 169852
* Optimistically analyse Phi cyclesArnold Schwaighofer2012-12-101-41/+13
| | | | | | | | | | Analyse Phis under the starting assumption that they are NoAlias. Recursively look at their inputs. If they MayAlias/MustAlias there must be an input that makes them so. Addresses bug 14351. llvm-svn: 169788
* Add a new visitor for walking the uses of a pointer value.Chandler Carruth2012-12-102-0/+59
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This visitor provides infrastructure for recursively traversing the use-graph of a pointer-producing instruction like an alloca or a malloc. It maintains a worklist of uses to visit, so it can handle very deep recursions. It automatically looks through instructions which simply translate one pointer to another (bitcasts and GEPs). It tracks the offset relative to the original pointer as long as that offset remains constant and exposes it during the visit as an APInt offset. Finally, it performs conservative escape analysis. However, currently it has some limitations that should be addressed going forward: 1) It doesn't handle vectors of pointers. 2) It doesn't provide a cheaper visitor when the constant offset tracking isn't needed. 3) It doesn't support non-instruction pointer values. The current functionality is exactly what is required to implement the SROA pointer-use visitors in terms of this one, rather than in terms of their own ad-hoc base visitor, which was always very poorly specified. SROA has been converted to use this, and the code there deleted which this utility now provides. Technically speaking, using this new visitor allows SROA to handle a few more cases than it previously did. It is now more aggressive in ignoring chains of instructions which look like they would defeat SROA, but in fact do not because they never result in a read or write of memory. While this is "neat", it shouldn't be interesting for real programs as any such chains should have been removed by others passes long before we get to SROA. As a consequence, I've not added any tests for these features -- it shouldn't be part of SROA's contract to perform such heroics. The goal is to extend the functionality of this visitor going forward, and re-use it from passes like ASan that can benefit from doing a detailed walk of the uses of a pointer. Thanks to Ben Kramer for the code review rounds and lots of help reviewing and debugging this patch. llvm-svn: 169728
* Reorganize FastMathFlags to be a wrapper around unsigned, and streamline ↵Michael Ilseman2012-12-091-2/+2
| | | | | | some interfaces. llvm-svn: 169712
* Add support to ValueTracking for determining that a pointer is non-nullChandler Carruth2012-12-071-0/+73
| | | | | | | | | | | | | | | | | | | | | | | by virtue of inbounds GEPs that preclude a null pointer. This is a very common pattern in the code generated by std::vector and other standard library routines which use allocators that test for null pervasively. This is one step closer to teaching Clang+LLVM to be able to produce an empty function for: void f() { std::vector<int> v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); } Which is related to getting them to completely fold SmallVector push_back sequences into constants when inlining and other optimizations make that a possibility. llvm-svn: 169573
* Have CannotBeNegativeZero() be aware of the nsz fast-math flagMichael Ilseman2012-12-061-1/+6
| | | | llvm-svn: 169452
* constify the cost APINadav Rotem2012-12-031-7/+7
| | | | llvm-svn: 169172
* Use the new script to sort the includes of every file under lib.Chandler Carruth2012-12-0353-205/+202
| | | | | | | | | | | | | | | | | Sooooo many of these had incorrect or strange main module includes. I have manually inspected all of these, and fixed the main module include to be the nearest plausible thing I could find. If you own or care about any of these source files, I encourage you to take some time and check that these edits were sensible. I can't have broken anything (I strictly added headers, and reordered them, never removed), but they may not be the headers you'd really like to identify as containing the API being implemented. Many forward declarations and missing includes were added to a header files to allow them to parse cleanly when included first. The main module rule does in fact have its merits. =] llvm-svn: 169131
* Move the InstVisitor utility into VMCore where it belongs. It heavilyChandler Carruth2012-11-303-3/+3
| | | | | | | | | | | | depends on the IR infrastructure, there is no sense in it being off in Support land. This is in preparation to start working to expand InstVisitor into more special-purpose visitors that are still generic and can be re-used across different passes. The expansion will go into the Analylis tree though as nothing in VMCore needs it. llvm-svn: 168972
* Modified dump() to provide a littlePreston Briggs2012-11-301-32/+30
| | | | | | | | | more information for dependences between instructions that don't share a common loop. Updated the test results appropriately. llvm-svn: 168965
* Follow up to 168711: It's safe to base this analysis on the found compare, ↵Benjamin Kramer2012-11-291-4/+3
| | | | | | | | just return the value for the right predicate. Thanks to Andy for catching this. llvm-svn: 168921
* Improve isImpliedCond comment a bit.Andrew Trick2012-11-291-2/+2
| | | | llvm-svn: 168914
* Cleaned up a couple of comments.Preston Briggs2012-11-291-4/+4
| | | | llvm-svn: 168854
* Modified depends() to recognize that when all levels are "=" andPreston Briggs2012-11-271-1/+16
| | | | | | | | | there's no possible loo-independent dependence, then there's no dependence. Updated all test result appropriately. llvm-svn: 168719
* SCEV: Even if the latch terminator is foldable we can't deduce the result of ↵Benjamin Kramer2012-11-271-3/+4
| | | | | | | | an unrelated condition with it. Fixes PR14432. llvm-svn: 168711
* Modify depends(Src, Dst, PossiblyLoopIndependent).Preston Briggs2012-11-271-0/+3
| | | | | | | | | | If the Src and Dst are the same instruction, no loop-independent dependence is possible, so we force the PossiblyLoopIndependent flag to false. The test case results are updated appropriately. llvm-svn: 168678
* Fast-math optimization: fold multiply by zeroMichael Ilseman2012-11-271-0/+39
| | | | | | Added in first optimization using fast-math flags to serve as an example for following optimizations. SimplifyInstruction will now try to optimize an fmul observing its FastMathFlags to see if it can fold multiply by zero when 'nnan' and 'nsz' flags are set. llvm-svn: 168648
* Corrects a problem where we reply exclusively of GEPs to drivePreston Briggs2012-11-211-69/+108
| | | | | | | | | | | | analysis. Better is to look for cases with useful GEPs and use them when possible. When a pair of useful GEPs is not available, use the raw SCEVs directly. This approach supports better analysis of pointer dereferencing. In parallel, all the test cases are updated appropriately. Cases where we have a store to *B++ can now be analyzed! llvm-svn: 168474
* removes a few "const" qualifiersSebastian Pop2012-11-201-13/+13
| | | | | | | | | so that I can (someday) call SE->getSCEV without complaint. No semantic change intended. Patch from Preston Briggs <preston.briggs@gmail.com>. llvm-svn: 168391
* Clean up handling of always-inline functions in the inliner.Bob Wilson2012-11-191-71/+105
| | | | | | | | | This patch moves the isInlineViable function from the InlineAlways pass into the InlineCostAnalyzer and then changes the InlineCost computation to use that simple check for always-inline functions. All the special-case checks for AlwaysInline in the CallAnalyzer can then go away. llvm-svn: 168300
* Some comment fixes.Bob Wilson2012-11-191-1/+1
| | | | llvm-svn: 168299
* Phi speculation improvement for BasicAAHal Finkel2012-11-171-3/+12
| | | | | | | | | | | | This is a partial solution to PR14351. It removes some of the special significance of the first incoming phi value in the phi aliasing checking logic in BasicAA. In the context of a loop, the old logic assumes that the first incoming value is the interesting one (meaning that it is the one that comes from outside the loop), but this is often not the case. With this change, we now test first the incoming value that comes from a block other than the parent of the phi being tested. llvm-svn: 168245
* Make this easier to understand, as suggested by Chandler.Duncan Sands2012-11-161-1/+6
| | | | llvm-svn: 168196
* InstructionSimplify should be able to simplify A+B==B+A to 'true'Duncan Sands2012-11-161-2/+14
| | | | | | but wasn't due to the same logic bug that caused PR14361. llvm-svn: 168186
* Add doInitialization and doFinalization methods to ModulePass's, to allow ↵Owen Anderson2012-11-151-0/+3
| | | | | | | | them to be re-initialized and reused on multiple Module's. Patch by Pedro Artigas. llvm-svn: 168008
* DependenceAnalysis: Print all dependency pairs when dumping. Update all ↵Benjamin Kramer2012-11-131-8/+5
| | | | | | | | testcases. Part of a patch by Preston Briggs. llvm-svn: 167827
* llvm/ConstantFolding.cpp: Make ReadDataFromGlobal() and ↵NAKAMURA Takumi2012-11-081-9/+19
| | | | | | FoldReinterpretLoadFromConstPtr() Big-endian-aware. llvm-svn: 167595
* Don't infer whether a value is captured in the current function from theRichard Osborne2012-11-051-5/+5
| | | | | | | | | | 'nocapture' attribute. The nocapture attribute only specifies that no copies are made that outlive the function. This isn't the same as there being no copies at all. This fixes PR14045. llvm-svn: 167381
* ConstantFolding.cpp: Whitespace.NAKAMURA Takumi2012-11-051-100/+100
| | | | llvm-svn: 167377
* Apply the patch from PR14160. I failed to construct a testcase for this, butDuncan Sands2012-11-041-0/+3
| | | | | | I'm applying it anyway since it seems to be obviously correct. llvm-svn: 167370
* CostModel: add support for Vector Insert and Extract.Nadav Rotem2012-11-021-0/+18
| | | | llvm-svn: 167329
* Add a cost model analysis that allows us to estimate the cost of IR-level ↵Nadav Rotem2012-11-023-0/+177
| | | | | | instructions. llvm-svn: 167324
* Revert the majority of the next patch in the address space series:Chandler Carruth2012-11-016-37/+20
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | r165941: Resubmit the changes to llvm core to update the functions to support different pointer sizes on a per address space basis. Despite this commit log, this change primarily changed stuff outside of VMCore, and those changes do not carry any tests for correctness (or even plausibility), and we have consistently found questionable or flat out incorrect cases in these changes. Most of them are probably correct, but we need to devise a system that makes it more clear when we have handled the address space concerns correctly, and ideally each pass that gets updated would receive an accompanying test case that exercises that pass specificaly w.r.t. alternate address spaces. However, from this commit, I have retained the new C API entry points. Those were an orthogonal change that probably should have been split apart, but they seem entirely good. In several places the changes were very obvious cleanups with no actual multiple address space code added; these I have not reverted when I spotted them. In a few other places there were merge conflicts due to a cleaner solution being implemented later, often not using address spaces at all. In those cases, I've preserved the new code which isn't address space dependent. This is part of my ongoing effort to clean out the partial address space code which carries high risk and low test coverage, and not likely to be finished before the 3.2 release looms closer. Duncan and I would both like to see the above issues addressed before we return to these changes. llvm-svn: 167222
* Revert the series of commits starting with r166578 which introduced theChandler Carruth2012-11-017-146/+140
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | getIntPtrType support for multiple address spaces via a pointer type, and also introduced a crasher bug in the constant folder reported in PR14233. These commits also contained several problems that should really be addressed before they are re-committed. I have avoided reverting various cleanups to the DataLayout APIs that are reasonable to have moving forward in order to reduce the amount of churn, and minimize the number of commits that were reverted. I've also manually updated merge conflicts and manually arranged for the getIntPtrType function to stay in DataLayout and to be defined in a plausible way after this revert. Thanks to Duncan for working through this exact strategy with me, and Nick Lewycky for tracking down the really annoying crasher this triggered. (Test case to follow in its own commit.) After discussing with Duncan extensively, and based on a note from Micah, I'm going to continue to back out some more of the more problematic patches in this series in order to ensure we go into the LLVM 3.2 branch with a reasonable story here. I'll send a note to llvmdev explaining what's going on and why. Summary of reverted revisions: r166634: Fix a compiler warning with an unused variable. r166607: Add some cleanup to the DataLayout changes requested by Chandler. r166596: Revert "Back out r166591, not sure why this made it through since I cancelled the command. Bleh, sorry about this! r166591: Delete a directory that wasn't supposed to be checked in yet. r166578: Add in support for getIntPtrType to get the pointer type based on the address space. llvm-svn: 167221
OpenPOWER on IntegriCloud