summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp
Commit message (Collapse)AuthorAgeFilesLines
* PR14904: Segmentation fault running pass 'Recognize loop idioms'Shuxin Yang2013-01-101-1/+1
| | | | | | | | The root cause is mistakenly taking for granted that "dyn_cast<Instruction>(a-Value)" return a non-NULL instruction. llvm-svn: 172145
* Switch LoopIdiom pass to directly require target transform information.Chandler Carruth2013-01-071-3/+3
| | | | | | | | I'm sorry for duplicating bad style here, but I wanted to keep consistency. I've pinged the code review thread where this style was reviewed and changes were requested. llvm-svn: 171714
* Make the popcnt support enums and methods have more clear names andChandler Carruth2013-01-071-1/+1
| | | | | | | follow the conding conventions regarding enumerating a set of "kinds" of things. llvm-svn: 171687
* Move TargetTransformInfo to live under the Analysis library. This noChandler Carruth2013-01-071-1/+1
| | | | | | | longer would violate any dependency layering and it is in fact an analysis. =] llvm-svn: 171686
* Switch LoopIdiomRecognize to directly use the TargetTransformInfoChandler Carruth2013-01-051-11/+9
| | | | | | interface rather than the ScalarTargetTransformInterface. llvm-svn: 171616
* - Add comment to two functions which might be considered as dead code. Shuxin Yang2013-01-021-2/+4
| | | | | | - Fix a typo llvm-svn: 171399
* Move all of the header files which are involved in modelling the LLVM IRChandler Carruth2013-01-021-4/+4
| | | | | | | | | | | | | | | | | | | | | 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
* - Re-enable population count loop idiom recognization Shuxin Yang2012-12-091-19/+516
| | | | | | | - fix a bug which cause sigfault. - add two testing cases which was causing crash llvm-svn: 169687
* Revert the patches adding a popcount loop idiom recognition pass.Chandler Carruth2012-12-081-513/+19
| | | | | | | | | | | | | | There are still bugs in this pass, as well as other issues that are being worked on, but the bugs are crashers that occur pretty easily in the wild. Test cases have been sent to the original commit's review thread. This reverts the commits: r169671: Fix a logic error. r169604: Move the popcnt tests to an X86 subdirectory. r168931: Initial commit adding the pass. llvm-svn: 169683
* Fix an inadvertent typo error.Shuxin Yang2012-12-081-1/+1
| | | | llvm-svn: 169671
* Use the new script to sort the includes of every file under lib.Chandler Carruth2012-12-031-4/+4
| | | | | | | | | | | | | | | | | 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
* rdar://12100355 (part 1)Shuxin Yang2012-11-291-19/+513
| | | | | | | | | | | | | | This revision attempts to recognize following population-count pattern: while(a) { c++; ... ; a &= a - 1; ... }, where <c> and <a>could be used multiple times in the loop body. TODO: On X8664 and ARM, __buildin_ctpop() are not expanded to a efficent instruction sequence, which need to be improved in the following commits. Reviewed by Nadav, really appreciate! llvm-svn: 168931
* Revert the switch of loop-idiom to use the new dependence analysis.Chandler Carruth2012-11-021-69/+88
| | | | | | | | | | | | | | | | | | | | | | | | | | | | The new analysis is not yet ready for prime time. It has a *critical* flawed assumption, and some troubling shortages of testing. Until it's been hammered into better shape, let's stick with the working code. This should be easy to revert itself when the analysis is ready. Fixes PR14241, a miscompile of any memcpy-able loop which uses a pointer as the induction mechanism. If you have been seeing miscompiles in this revision range, you really want to test with this backed out. The results of this miscompile are a bit subtle as they can lead to downstream passes concluding things are impossible which are in fact possible. Thanks to David Blaikie for the majority of the reduction of this miscompile. I'll be checking in the test case in a non-revert commit. Revesions reverted here: r167045: LoopIdiom: Fix a serious missed optimization: we only turned top-level loops into memmove. r166877: LoopIdiom: Add checks to avoid turning memmove into an infinite loop. r166875: LoopIdiom: Recognize memmove loops. r166874: LoopIdiom: Replace custom dependence analysis with DependenceAnalysis. llvm-svn: 167286
* Revert the series of commits starting with r166578 which introduced theChandler Carruth2012-11-011-6/+5
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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
* LoopIdiom: Fix a serious missed optimization: we only turned top-level loops ↵Benjamin Kramer2012-10-301-4/+5
| | | | | | | | into memmove. Thanks to Preston Briggs for catching this! llvm-svn: 167045
* LoopIdiom: Add checks to avoid turning memmove into an infinite loop.Benjamin Kramer2012-10-271-2/+2
| | | | | | I don't think this is possible with the current implementation but that may change eventually. llvm-svn: 166877
* LoopIdiom: Recognize memmove loops.Benjamin Kramer2012-10-271-10/+24
| | | | | | | | | | | This turns loops like for (unsigned i = 0; i != n; ++i) p[i] = p[i+1]; into memmove, which has a highly optimized implementation in most libcs. This was really easy with the new DependenceAnalysis :) llvm-svn: 166875
* LoopIdiom: Replace custom dependence analysis with DependenceAnalysis.Benjamin Kramer2012-10-271-80/+45
| | | | | | | | | | | Requires a lot less code and complexity on loop-idiom's side and the more precise analysis can catch more cases, like the one I included as a test case. This also fixes the edge-case miscompilation from PR9481. Compile time performance seems to be slightly worse, but this is mostly due to an extra LCSSA run scheduled by the PassManager and should be fixed there. llvm-svn: 166874
* Add in support for getIntPtrType to get the pointer type based on the ↵Micah Villmow2012-10-241-3/+5
| | | | | | | | | address space. This checkin also adds in some tests that utilize these paths and updates some of the clients. llvm-svn: 166578
* Revert r166390 "LoopIdiom: Replace custom dependence analysis with ↵Benjamin Kramer2012-10-211-26/+74
| | | | | | | | | | | | | LoopDependenceAnalysis." It passes all tests, produces better results than the old code but uses the wrong pass, LoopDependenceAnalysis, which is old and unmaintained. "Why is it still in tree?", you might ask. The answer is obviously: "To confuse developers." Just swapping in the new dependency pass sends the pass manager into an infinte loop, I'll try to figure out why tomorrow. llvm-svn: 166399
* LoopIdiom: Replace custom dependence analysis with LoopDependenceAnalysis.Benjamin Kramer2012-10-211-74/+26
| | | | | | | | | | Requires a lot less code and complexity on loop-idiom's side and the more precise analysis can catch more cases, like the one I included as a test case. This also fixes the edge-case miscompilation from PR9481. I'm not entirely sure that all cases are handled that the old checks handled but LDA will certainly become smarter in the future. llvm-svn: 166390
* Move TargetData to DataLayout.Micah Villmow2012-10-081-4/+4
| | | | llvm-svn: 165402
* LoopIdiom: Give up when the loop is not in canonical form.Benjamin Kramer2012-09-211-0/+5
| | | | | | | | | We rely on it when doing the transforms. This can happen when there is an indirectbr in the loop. Fixes PR13892. llvm-svn: 164383
* Make MemoryBuiltins aware of TargetLibraryInfo.Benjamin Kramer2012-08-291-11/+13
| | | | | | | | | | | | | | | | This disables malloc-specific optimization when -fno-builtin (or -ffreestanding) is specified. This has been a problem for a long time but became more severe with the recent memory builtin improvements. Since the memory builtin functions are used everywhere, this required passing TLI in many places. This means that functions that now have an optional TLI argument, like RecursivelyDeleteTriviallyDeadFunctions, won't remove dead mallocs anymore if the TLI argument is missing. I've updated most passes to do the right thing. Fixes PR13694 and probably others. llvm-svn: 162841
* Clean whitespaces.Nadav Rotem2012-07-241-1/+1
| | | | llvm-svn: 160668
* Move llvm/Support/IRBuilder.h -> llvm/IRBuilder.hChandler Carruth2012-06-291-5/+5
| | | | | | | | | | | | | | | | | This was always part of the VMCore library out of necessity -- it deals entirely in the IR. The .cpp file in fact was already part of the VMCore library. This is just a mechanical move. I've tried to go through and re-apply the coding standard's preferred header sort, but at 40-ish files, I may have gotten some wrong. Please let me know if so. I'll be committing the corresponding updates to Clang and Polly, and Duncan has DragonEgg. Thanks to Bill and Eric for giving the green light for this bit of cleanup. llvm-svn: 159421
* Correct grammar.Eli Friedman2011-09-131-1/+1
| | | | llvm-svn: 139565
* Change a bunch of isVolatile() checks to check for atomic load/store as well.Eli Friedman2011-09-121-2/+2
| | | | | | | | No tests; these changes aren't really interesting in the sense that the logic is the same for volatile and atomic. I believe this completes all of the changes necessary for the optimizer to handle loads and stores correctly. I'm going to try and come up with some additional testing, though. llvm-svn: 139533
* land David Blaikie's patch to de-constify Type, with a few tweaks.Chris Lattner2011-07-181-2/+2
| | | | llvm-svn: 135375
* Disable loop idiom recognition of memset/memcpy if the function being compiledChad Rosier2011-07-151-0/+5
| | | | | | | | | is named after a common idiom (i.e., memset/memcpy). Otherwise, we can run into infinite recursion. Ideally, the user should use the correct -fno-builtin flag, but in case they don't we should play nicely. rdar://9763412 llvm-svn: 135286
* SCEVExpander: give new insts a name that identifies the reponsible pass.Andrew Trick2011-06-281-2/+2
| | | | llvm-svn: 133992
* whitespaceAndrew Trick2011-06-281-8/+8
| | | | llvm-svn: 133991
* Fix PR9815: I was trying to get out of "generating code and thenChris Lattner2011-05-221-44/+66
| | | | | | | | failing to form a memset, then having to delete it" but my approximation isn't safe for self recurrent loops. Instead of doign a hack, just do it the right way. llvm-svn: 131858
* preserve line number info.Devang Patel2011-05-041-2/+3
| | | | llvm-svn: 130869
* Added SCEV::NoWrapFlags to manage unsigned, signed, and self wrapAndrew Trick2011-03-141-4/+4
| | | | | | | | | properties. Added the self-wrap flag for SCEV::AddRecExpr. A slew of temporary FIXMEs indicate the intention of the no-self-wrap flag without changing behavior in this revision. llvm-svn: 127590
* whitespaceAndrew Trick2011-03-141-66/+66
| | | | llvm-svn: 127589
* Preserve line no. info.Devang Patel2011-03-071-2/+2
| | | | | | Radar 9097659 llvm-svn: 127182
* fix a crasher in disabled code (on variable stride loops)Chris Lattner2011-02-211-1/+1
| | | | llvm-svn: 126125
* Add some (disabled code) to print out negative strides.Chris Lattner2011-02-211-3/+15
| | | | llvm-svn: 126102
* rewrite the memset_pattern pattern generation stuff to accept any 2/4/8/16-byteChris Lattner2011-02-191-32/+12
| | | | | | | | | | | | | | | | | | constant, including globals. This makes us generate much more "pretty" pattern globals as well because it doesn't break it down to an array of bytes all the time. This enables us to handle stores of relocatable globals. This kicks in about 48 times in 254.gap, giving us stuff like this: @.memset_pattern40 = internal constant [2 x %struct.TypHeader* (%struct.TypHeader*, %struct.TypHeader*)*] [%struct.TypHeader* (%struct.TypHeader*, %struct .TypHeader*)* @IsFalse, %struct.TypHeader* (%struct.TypHeader*, %struct.TypHeader*)* @IsFalse], align 16 ... call void @memset_pattern16(i8* %scevgep5859, i8* bitcast ([2 x %struct.TypHeader* (%struct.TypHeader*, %struct.TypHeader*)*]* @.memset_pattern40 to i8* ), i64 %tmp75) nounwind llvm-svn: 126044
* Implement rdar://9009151, transforming strided loop stores ofChris Lattner2011-02-191-32/+125
| | | | | | | | | | | unsplatable values into memset_pattern16 when it is available (recent darwins). This transforms lots of strided loop stores of ints for example, like 5 in vpr: Formed memset: call void @memset_pattern16(i8* %4, i8* getelementptr inbounds ([16 x i8]* @.memset_pattern9, i32 0, i32 0), i64 %tmp25) from store to: {%3,+,4}<%11> at: store i32 3, i32* %scevgep, align 4, !tbaa !4 llvm-svn: 126040
* Make loop-idiom use TargetLibraryInfo to determine whether it is allowedChris Lattner2011-02-181-1/+18
| | | | | | to hack on memset, memcpy etc. llvm-svn: 125974
* Spelling fix: consequtive -> consecutive.Duncan Sands2011-02-151-1/+1
| | | | llvm-svn: 125563
* Teach loop-idiom to turn a loop containing a memset into a larger memsetChris Lattner2011-01-041-18/+69
| | | | | | | | | | | | | | | | when safe. The testcase is basically this nested loop: void foo(char *X) { for (int i = 0; i != 100; ++i) for (int j = 0; j != 100; ++j) X[j+i*100] = 0; } which gets turned into a single memset now. clang -O3 doesn't optimize this yet though due to a phase ordering issue I haven't analyzed yet. llvm-svn: 122806
* restructure this a bit. Initialize the WeakVH with "I", theChris Lattner2011-01-041-11/+14
| | | | | | | | instruction *after* the store. The store will always be deleted if the transformation kicks in, so we'd do an N^2 scan of every loop block. Whoops. llvm-svn: 122805
* use the very-handy getTruncateOrZeroExtend helper function, andChris Lattner2011-01-041-14/+6
| | | | | | | stop setting NSW: signed overflow is possible. Thanks to Dan for pointing these out. llvm-svn: 122790
* Fix comment.Owen Anderson2011-01-031-1/+1
| | | | llvm-svn: 122788
* reduce redundancy in the hashing code and other misc cleanups.Chris Lattner2011-01-031-1/+1
| | | | llvm-svn: 122720
* add DEBUG and -stats output to earlycse.Chris Lattner2011-01-021-3/+4
| | | | | | Teach it to CSE the rest of the non-side-effecting instructions. llvm-svn: 122716
* fix a miscompilation of tramp3d-v4: when forming a memcpy, we have to makeChris Lattner2011-01-021-12/+23
| | | | | | | | sure that the loop we're promoting into a memcpy doesn't mutate the input of the memcpy. Before we were just checking that the dest of the memcpy wasn't mod/ref'd by the loop. llvm-svn: 122712
OpenPOWER on IntegriCloud