summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis/ScalarEvolution.cpp
Commit message (Collapse)AuthorAgeFilesLines
...
* Move all of the header files which are involved in modelling the LLVM IRChandler Carruth2013-01-021-8/+8
| | | | | | | | | | | | | | | | | | | | | into their new header subdirectory: include/llvm/IR. This matches the directory structure of lib, and begins to correct a long standing point of file layout clutter in LLVM. There are still more header files to move here, but I wanted to handle them in separate commits to make tracking what files make sense at each layer easier. The only really questionable files here are the target intrinsic tablegen files. But that's a battle I'd rather not fight today. I've updated both CMake and Makefile build systems (I think, and my tests think, but I may have missed something). I've also re-sorted the includes throughout the project. I'll be committing updates to Clang, DragonEgg, and Polly momentarily. llvm-svn: 171366
* Use the new script to sort the includes of every file under lib.Chandler Carruth2012-12-031-12/+13
| | | | | | | | | | | | | | | | | 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
* 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
* 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
* Revert the series of commits starting with r166578 which introduced theChandler Carruth2012-11-011-7/+8
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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
* SCEV validator: Ignore CouldNotCompute/undef on both sides. This is mostly ↵Benjamin Kramer2012-10-271-3/+6
| | | | | | noise and blocks finding more severe bugs. llvm-svn: 166873
* SCEV validator: Add workarounds for some common false positives due to the ↵Benjamin Kramer2012-10-271-0/+18
| | | | | | way it handles strings. llvm-svn: 166872
* Add a basic verifier for SCEV's backedge taken counts.Benjamin Kramer2012-10-261-0/+68
| | | | | | | | | | | Enabled with -verify-scev. This could be extended significantly but hopefully catches the common cases now. Note that it's not enabled by default in any configuration because the way it tries to distinguish SCEVs is still fragile and may produce false positives. Also the test-suite isn't clean yet, one example is that it fails if a pass drops an NSW bit but it's still present in SCEV's cached. Cleaning up all those cases will take some time. llvm-svn: 166786
* getSmallConstantTripMultiple should never return zero.Hal Finkel2012-10-241-2/+5
| | | | | | | | | When the trip count is -1, getSmallConstantTripMultiple could return zero, and this would cause runtime loop unrolling to assert. Instead of returning zero, one is now returned (consistent with the existing overflow cases). Fixes PR14167. llvm-svn: 166612
* Add in support for getIntPtrType to get the pointer type based on the ↵Micah Villmow2012-10-241-8/+7
| | | | | | | | | address space. This checkin also adds in some tests that utilize these paths and updates some of the clients. llvm-svn: 166578
* Move TargetData to DataLayout.Micah Villmow2012-10-081-8/+8
| | | | llvm-svn: 165402
* Revert 'Fix a typo 'iff' => 'if''. iff is an abreviation of if and only if. ↵Sylvestre Ledru2012-09-271-2/+2
| | | | | | See: http://en.wikipedia.org/wiki/If_and_only_if Commit 164767 llvm-svn: 164768
* Fix a typo 'iff' => 'if'Sylvestre Ledru2012-09-271-2/+2
| | | | llvm-svn: 164767
* Release build: guard dump functions withManman Ren2012-09-121-1/+1
| | | | | | | | "#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)" No functional change. Update r163344. llvm-svn: 163679
* Release build: guard dump functions with "ifndef NDEBUG"Manman Ren2012-09-061-0/+2
| | | | | | No functional change. llvm-svn: 163344
* Stay rational; don't assert trying to take the square root of a negative value.Nick Lewycky2012-08-011-0/+6
| | | | | | If it's negative, the loop is already proven to be infinite. Fixes PR13489! llvm-svn: 161107
* Factor SCEV traversal code so I can use it elsewhere. No functionality.Andrew Trick2012-07-131-51/+19
| | | | llvm-svn: 160203
* Delete code for folding undefs in ScalarEvolution. It's invalid inDan Gohman2012-07-091-14/+0
| | | | | | obscure ways, and it isn't actually important in the real world. llvm-svn: 159969
* Reduce use list thrashing by using DenseMap's find_as for maps with ↵Benjamin Kramer2012-06-301-6/+8
| | | | | | | | ValueHandle keys. No functionality change. llvm-svn: 159497
* If the step value is a constant zero, the loop isn't going to terminate. FixesNick Lewycky2012-06-281-1/+1
| | | | | | the assert reported in PR13228! llvm-svn: 159393
* Fix typos found by http://github.com/lyda/misspell-checkBenjamin Kramer2012-06-021-1/+1
| | | | llvm-svn: 157885
* Make sure that we're dealing with a binary SCEVExpr when simplifying.Benjamin Kramer2012-05-301-1/+2
| | | | llvm-svn: 157704
* Teach SCEV's icmp simplification logic that a-b == 0 is equivalent to a == b.Benjamin Kramer2012-05-301-1/+20
| | | | | | | | | | | | | | | This also required making recursive simplifications until nothing changes or a hard limit (currently 3) is hit. With the simplification in place indvars can canonicalize loops of the form for (unsigned i = 0; i < a-b; ++i) into for (unsigned i = 0; i != a-b; ++i) which used to fail because SCEV created a weird umax expr for the backedge taken count. llvm-svn: 157701
* SCEV: Handle a corner case reducing AddRecExpr * AddRecExprAndrew Trick2012-05-301-1/+4
| | | | | | | | | If integer overflow causes one of the terms to reach zero, that can force the entire expression to zero. Fixes PR12929: cast<Ty>() argument of incompatible type llvm-svn: 157673
* Reformat the loop that does AddRecExpr * AddRecExpr reduction.Andrew Trick2012-05-301-55/+56
| | | | | | No functionality. llvm-svn: 157672
* SCEV: Add MarkPendingLoopPredicates to avoid recursive isImpliedCond.Andrew Trick2012-05-191-0/+24
| | | | | | | | | | getUDivExpr attempts to simplify by checking for overflow. isLoopEntryGuardedByCond then evaluates the loop predicate which may lead to the same getUDivExpr causing endless recursion. Fixes PR12868: clang 3.2 segmentation fault. llvm-svn: 157092
* reuse the result of some expensive computations in getSignExtendExpr() and ↵Nuno Lopes2012-05-151-18/+20
| | | | | | | | getZeroExtendExpr() this gives a speedup of > 80 in a debug build in the test case of PR12825 (php_sha512_crypt_r) llvm-svn: 156849
* minor simplification to code: Ty is already a SCEV type; don't need to run ↵Nuno Lopes2012-05-151-6/+3
| | | | | | getEffectiveSCEVType() twice llvm-svn: 156823
* Rewrite ScalarEvolution::hasOperand to use an explicit worklist insteadDan Gohman2012-05-101-35/+50
| | | | | | of recursion, to avoid excessive stack usage on deep expressions. llvm-svn: 156554
* Revert "SCEV: When expanding a GEP the final addition to the base pointer ↵Benjamin Kramer2012-04-171-1/+1
| | | | | | | | has NUW but not NSW." This isn't right either, reverting for now. llvm-svn: 154910
* SCEV: When expanding a GEP the final addition to the base pointer has NUW ↵Benjamin Kramer2012-04-071-1/+1
| | | | | | | | but not NSW. Found by inspection. llvm-svn: 154262
* Always compute all the bits in ComputeMaskedBits.Rafael Espindola2012-04-041-6/+3
| | | | | | | | This allows us to keep passing reduced masks to SimplifyDemandedBits, but know about all the bits if SimplifyDemandedBits fails. This allows instcombine to simplify cases like the one in the included testcase. llvm-svn: 154011
* SCEV fix: Handle loop invariant loads.Andrew Trick2012-03-261-1/+5
| | | | | | Fixes PR11882: NULL dereference in ComputeLoadConstantCompareExitLimit. llvm-svn: 153480
* switch SCEV to use the new ConstantFoldLoadThroughGEPIndices functionChris Lattner2012-01-241-35/+3
| | | | | | | | instead of its own hard coded thing, allowing it to handle ConstantDataSequential and fixing some obscure bugs (e.g. it would previously crash on a CAZ of vector type). llvm-svn: 148788
* More dead code removal (using -Wunreachable-code)David Blaikie2012-01-201-22/+8
| | | | llvm-svn: 148578
* Remove obviously invalid early exit that prevented analyzing ↵Benjamin Kramer2012-01-201-1/+0
| | | | | | | | ConstantAggregateZeros. Found by the clang static analyzer. llvm-svn: 148540
* Clarified the SCEV getSmallConstantTripCount interface with in-your-face ↵Andrew Trick2012-01-111-9/+18
| | | | | | | | comments. This interface is misleading and dangerous, but it is actually what we need for unrolling. llvm-svn: 147926
* Expose isNonConstantNegative to users of ScalarEvolution.Andrew Trick2012-01-071-0/+14
| | | | llvm-svn: 147700
* Fix a few more places where TargetData/TargetLibraryInfo is not being passed.Chad Rosier2011-12-021-6/+7
| | | | | | Add FIXMEs to places that are non-trivial to fix. llvm-svn: 145661
* Last bit of TargetLibraryInfo propagation. Also fixed a case for TargetDataChad Rosier2011-12-011-9/+12
| | | | | | | where it appeared beneficial to pass. More of rdar://10500969 llvm-svn: 145630
* Propagate TargetLibraryInfo throughout ConstantFolding.cpp and Chad Rosier2011-12-011-1/+5
| | | | | | | InstructionSimplify.cpp. Other fixups as needed. Part of rdar://10500969 llvm-svn: 145559
* SCEV fix. In general, Add/Mul expressions should not inherit NSW/NUW.Andrew Trick2011-11-291-8/+8
| | | | | | | This reverts r139450, fixes r139453, and adds much needed comments and a unit test. llvm-svn: 145367
* Make SCEV print <nsw><nuw> for Add/MulExpr.Andrew Trick2011-11-291-0/+8
| | | | llvm-svn: 145364
* SCEV: Actually set overflow flags on add expressions.Benjamin Kramer2011-11-201-2/+2
| | | | | | setFlags doesn't modify its arguments. llvm-svn: 145007
* Fix SCEV overly optimistic back edge taken count for multi-exit loops.Andrew Trick2011-11-161-9/+22
| | | | | | Fixes PR11375: Different results for 'clang++ huh.cpp'... llvm-svn: 144746
* Don't try to loop on iterators that are potentially invalidated inside the ↵Nick Lewycky2011-11-121-0/+18
| | | | | | loop. Fixes PR11361! llvm-svn: 144454
* Don't forget to check FlagNW when determining whether an AddRecExpr will wrapNick Lewycky2011-11-091-2/+3
| | | | | | or not. Patch by Brendon Cahoon! llvm-svn: 144173
* Restore commits 142790 and 142843 - they weren't breaking the buildDuncan Sands2011-10-251-26/+46
| | | | | | | | | | | | | | | | | | | | | | | | | | bots. Original commit messages: - Reapply r142781 with fix. Original message: Enhance SCEV's brute force loop analysis to handle multiple PHI nodes in the loop header when computing the trip count. With this, we now constant evaluate: struct ListNode { const struct ListNode *next; int i; }; static const struct ListNode node1 = {0, 1}; static const struct ListNode node2 = {&node1, 2}; static const struct ListNode node3 = {&node2, 3}; int test() { int sum = 0; for (const struct ListNode *n = &node3; n != 0; n = n->next) sum += n->i; return sum; } - Now that we look at all the header PHIs, we need to consider all the header PHIs when deciding that the loop has stopped evolving. Fixes miscompile in the gcc torture testsuite! llvm-svn: 142919
* Speculatively revert commits 142790 and 142843 to see if it fixesDuncan Sands2011-10-251-46/+26
| | | | | | | | | | | | | | | | | | | | | | | | | | | the dragonegg and llvm-gcc self-host buildbots. Original commit messages: - Reapply r142781 with fix. Original message: Enhance SCEV's brute force loop analysis to handle multiple PHI nodes in the loop header when computing the trip count. With this, we now constant evaluate: struct ListNode { const struct ListNode *next; int i; }; static const struct ListNode node1 = {0, 1}; static const struct ListNode node2 = {&node1, 2}; static const struct ListNode node3 = {&node2, 3}; int test() { int sum = 0; for (const struct ListNode *n = &node3; n != 0; n = n->next) sum += n->i; return sum; } - Now that we look at all the header PHIs, we need to consider all the header PHIs when deciding that the loop has stopped evolving. Fixes miscompile in the gcc torture testsuite! llvm-svn: 142916
OpenPOWER on IntegriCloud