aboutsummaryrefslogtreecommitdiff
path: root/lib/Transforms/Scalar/LoopIdiomRecognize.cpp
AgeCommit message (Collapse)Author
2013-01-10PR14904: Segmentation fault running pass 'Recognize loop idioms'Shuxin Yang
The root cause is mistakenly taking for granted that "dyn_cast<Instruction>(a-Value)" return a non-NULL instruction. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@172145 91177308-0d34-0410-b5e6-96231b3b80d8
2013-01-07Switch LoopIdiom pass to directly require target transform information.Chandler Carruth
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@171714 91177308-0d34-0410-b5e6-96231b3b80d8
2013-01-07Make the popcnt support enums and methods have more clear names andChandler Carruth
follow the conding conventions regarding enumerating a set of "kinds" of things. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@171687 91177308-0d34-0410-b5e6-96231b3b80d8
2013-01-07Move TargetTransformInfo to live under the Analysis library. This noChandler Carruth
longer would violate any dependency layering and it is in fact an analysis. =] git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@171686 91177308-0d34-0410-b5e6-96231b3b80d8
2013-01-05Switch LoopIdiomRecognize to directly use the TargetTransformInfoChandler Carruth
interface rather than the ScalarTargetTransformInterface. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@171616 91177308-0d34-0410-b5e6-96231b3b80d8
2013-01-02- Add comment to two functions which might be considered as dead code. Shuxin Yang
- Fix a typo git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@171399 91177308-0d34-0410-b5e6-96231b3b80d8
2013-01-02Move all of the header files which are involved in modelling the LLVM IRChandler Carruth
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@171366 91177308-0d34-0410-b5e6-96231b3b80d8
2012-12-09- Re-enable population count loop idiom recognization Shuxin Yang
- fix a bug which cause sigfault. - add two testing cases which was causing crash git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@169687 91177308-0d34-0410-b5e6-96231b3b80d8
2012-12-08Revert the patches adding a popcount loop idiom recognition pass.Chandler Carruth
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@169683 91177308-0d34-0410-b5e6-96231b3b80d8
2012-12-08Fix an inadvertent typo error.Shuxin Yang
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@169671 91177308-0d34-0410-b5e6-96231b3b80d8
2012-12-03Use the new script to sort the includes of every file under lib.Chandler Carruth
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. =] git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@169131 91177308-0d34-0410-b5e6-96231b3b80d8
2012-11-29rdar://12100355 (part 1)Shuxin Yang
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! git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@168931 91177308-0d34-0410-b5e6-96231b3b80d8
2012-11-02Revert the switch of loop-idiom to use the new dependence analysis.Chandler Carruth
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@167286 91177308-0d34-0410-b5e6-96231b3b80d8
2012-11-01Revert the series of commits starting with r166578 which introduced theChandler Carruth
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@167221 91177308-0d34-0410-b5e6-96231b3b80d8
2012-10-30LoopIdiom: Fix a serious missed optimization: we only turned top-level loops ↵Benjamin Kramer
into memmove. Thanks to Preston Briggs for catching this! git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@167045 91177308-0d34-0410-b5e6-96231b3b80d8
2012-10-27LoopIdiom: Add checks to avoid turning memmove into an infinite loop.Benjamin Kramer
I don't think this is possible with the current implementation but that may change eventually. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@166877 91177308-0d34-0410-b5e6-96231b3b80d8
2012-10-27LoopIdiom: Recognize memmove loops.Benjamin Kramer
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 :) git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@166875 91177308-0d34-0410-b5e6-96231b3b80d8
2012-10-27LoopIdiom: Replace custom dependence analysis with DependenceAnalysis.Benjamin Kramer
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@166874 91177308-0d34-0410-b5e6-96231b3b80d8
2012-10-24Add in support for getIntPtrType to get the pointer type based on the ↵Micah Villmow
address space. This checkin also adds in some tests that utilize these paths and updates some of the clients. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@166578 91177308-0d34-0410-b5e6-96231b3b80d8
2012-10-21Revert r166390 "LoopIdiom: Replace custom dependence analysis with ↵Benjamin Kramer
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@166399 91177308-0d34-0410-b5e6-96231b3b80d8
2012-10-21LoopIdiom: Replace custom dependence analysis with LoopDependenceAnalysis.Benjamin Kramer
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@166390 91177308-0d34-0410-b5e6-96231b3b80d8
2012-10-08Move TargetData to DataLayout.Micah Villmow
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@165402 91177308-0d34-0410-b5e6-96231b3b80d8
2012-09-21LoopIdiom: Give up when the loop is not in canonical form.Benjamin Kramer
We rely on it when doing the transforms. This can happen when there is an indirectbr in the loop. Fixes PR13892. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@164383 91177308-0d34-0410-b5e6-96231b3b80d8
2012-08-29Make MemoryBuiltins aware of TargetLibraryInfo.Benjamin Kramer
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@162841 91177308-0d34-0410-b5e6-96231b3b80d8
2012-07-24Clean whitespaces.Nadav Rotem
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@160668 91177308-0d34-0410-b5e6-96231b3b80d8
2012-06-29Move llvm/Support/IRBuilder.h -> llvm/IRBuilder.hChandler Carruth
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@159421 91177308-0d34-0410-b5e6-96231b3b80d8
2011-09-13Correct grammar.Eli Friedman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@139565 91177308-0d34-0410-b5e6-96231b3b80d8
2011-09-12Change a bunch of isVolatile() checks to check for atomic load/store as well.Eli Friedman
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@139533 91177308-0d34-0410-b5e6-96231b3b80d8
2011-07-18land David Blaikie's patch to de-constify Type, with a few tweaks.Chris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@135375 91177308-0d34-0410-b5e6-96231b3b80d8
2011-07-15Disable loop idiom recognition of memset/memcpy if the function being compiledChad Rosier
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 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@135286 91177308-0d34-0410-b5e6-96231b3b80d8
2011-06-28SCEVExpander: give new insts a name that identifies the reponsible pass.Andrew Trick
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@133992 91177308-0d34-0410-b5e6-96231b3b80d8
2011-06-28whitespaceAndrew Trick
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@133991 91177308-0d34-0410-b5e6-96231b3b80d8
2011-05-22Fix PR9815: I was trying to get out of "generating code and thenChris Lattner
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@131858 91177308-0d34-0410-b5e6-96231b3b80d8
2011-05-04preserve line number info.Devang Patel
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@130869 91177308-0d34-0410-b5e6-96231b3b80d8
2011-03-14Added SCEV::NoWrapFlags to manage unsigned, signed, and self wrapAndrew Trick
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@127590 91177308-0d34-0410-b5e6-96231b3b80d8
2011-03-14whitespaceAndrew Trick
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@127589 91177308-0d34-0410-b5e6-96231b3b80d8
2011-03-07Preserve line no. info.Devang Patel
Radar 9097659 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@127182 91177308-0d34-0410-b5e6-96231b3b80d8
2011-02-21fix a crasher in disabled code (on variable stride loops)Chris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@126125 91177308-0d34-0410-b5e6-96231b3b80d8
2011-02-21Add some (disabled code) to print out negative strides.Chris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@126102 91177308-0d34-0410-b5e6-96231b3b80d8
2011-02-19rewrite the memset_pattern pattern generation stuff to accept any 2/4/8/16-byteChris Lattner
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 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@126044 91177308-0d34-0410-b5e6-96231b3b80d8
2011-02-19Implement rdar://9009151, transforming strided loop stores ofChris Lattner
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 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@126040 91177308-0d34-0410-b5e6-96231b3b80d8
2011-02-18Make loop-idiom use TargetLibraryInfo to determine whether it is allowedChris Lattner
to hack on memset, memcpy etc. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@125974 91177308-0d34-0410-b5e6-96231b3b80d8
2011-02-15Spelling fix: consequtive -> consecutive.Duncan Sands
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@125563 91177308-0d34-0410-b5e6-96231b3b80d8
2011-01-04Teach loop-idiom to turn a loop containing a memset into a larger memsetChris Lattner
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122806 91177308-0d34-0410-b5e6-96231b3b80d8
2011-01-04restructure this a bit. Initialize the WeakVH with "I", theChris Lattner
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122805 91177308-0d34-0410-b5e6-96231b3b80d8
2011-01-04use the very-handy getTruncateOrZeroExtend helper function, andChris Lattner
stop setting NSW: signed overflow is possible. Thanks to Dan for pointing these out. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122790 91177308-0d34-0410-b5e6-96231b3b80d8
2011-01-03Fix comment.Owen Anderson
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122788 91177308-0d34-0410-b5e6-96231b3b80d8
2011-01-03reduce redundancy in the hashing code and other misc cleanups.Chris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122720 91177308-0d34-0410-b5e6-96231b3b80d8
2011-01-02add DEBUG and -stats output to earlycse.Chris Lattner
Teach it to CSE the rest of the non-side-effecting instructions. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122716 91177308-0d34-0410-b5e6-96231b3b80d8
2011-01-02fix a miscompilation of tramp3d-v4: when forming a memcpy, we have to makeChris Lattner
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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122712 91177308-0d34-0410-b5e6-96231b3b80d8
generated by cgit v1.2.3-18-g5258 (git 2.32.0) at 2025-08-21 03:03:28 +0000