summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp
Commit message (Collapse)AuthorAgeFilesLines
* [Modules] Fix potential ODR violations by sinking the DEBUG_TYPEChandler Carruth2014-04-221-1/+2
| | | | | | | | | | | | | | | | | definition below all of the header #include lines, lib/Transforms/... edition. This one is tricky for two reasons. We again have a couple of passes that define something else before the includes as well. I've sunk their name macros with the DEBUG_TYPE. Also, InstCombine contains headers that need DEBUG_TYPE, so now those headers #define and #undef DEBUG_TYPE around their code, leaving them well formed modular headers. Fixing these headers was a large motivation for all of these changes, as "leaky" macros of this form are hard on the modules implementation. llvm-svn: 206844
* remove a bunch of unused private methodsNuno Lopes2014-03-231-8/+0
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | found with a smarter version of -Wunused-member-function that I'm playwing with. Appologies in advance if I removed someone's WIP code. include/llvm/CodeGen/MachineSSAUpdater.h | 1 include/llvm/IR/DebugInfo.h | 3 lib/CodeGen/MachineSSAUpdater.cpp | 10 -- lib/CodeGen/PostRASchedulerList.cpp | 1 lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp | 10 -- lib/IR/DebugInfo.cpp | 12 -- lib/MC/MCAsmStreamer.cpp | 2 lib/Support/YAMLParser.cpp | 39 --------- lib/TableGen/TGParser.cpp | 16 --- lib/TableGen/TGParser.h | 1 lib/Target/AArch64/AArch64TargetTransformInfo.cpp | 9 -- lib/Target/ARM/ARMCodeEmitter.cpp | 12 -- lib/Target/ARM/ARMFastISel.cpp | 84 -------------------- lib/Target/Mips/MipsCodeEmitter.cpp | 11 -- lib/Target/Mips/MipsConstantIslandPass.cpp | 12 -- lib/Target/NVPTX/NVPTXISelDAGToDAG.cpp | 21 ----- lib/Target/NVPTX/NVPTXISelDAGToDAG.h | 2 lib/Target/PowerPC/PPCFastISel.cpp | 1 lib/Transforms/Instrumentation/AddressSanitizer.cpp | 2 lib/Transforms/Instrumentation/BoundsChecking.cpp | 2 lib/Transforms/Instrumentation/MemorySanitizer.cpp | 1 lib/Transforms/Scalar/LoopIdiomRecognize.cpp | 8 - lib/Transforms/Scalar/SCCP.cpp | 1 utils/TableGen/CodeEmitterGen.cpp | 2 24 files changed, 2 insertions(+), 261 deletions(-) llvm-svn: 204560
* [C++11] Add range based accessors for the Use-Def chain of a Value.Chandler Carruth2014-03-091-8/+5
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This requires a number of steps. 1) Move value_use_iterator into the Value class as an implementation detail 2) Change it to actually be a *Use* iterator rather than a *User* iterator. 3) Add an adaptor which is a User iterator that always looks through the Use to the User. 4) Wrap these in Value::use_iterator and Value::user_iterator typedefs. 5) Add the range adaptors as Value::uses() and Value::users(). 6) Update *all* of the callers to correctly distinguish between whether they wanted a use_iterator (and to explicitly dig out the User when needed), or a user_iterator which makes the Use itself totally opaque. Because #6 requires churning essentially everything that walked the Use-Def chains, I went ahead and added all of the range adaptors and switched them to range-based loops where appropriate. Also because the renaming requires at least churning every line of code, it didn't make any sense to split these up into multiple commits -- all of which would touch all of the same lies of code. The result is still not quite optimal. The Value::use_iterator is a nice regular iterator, but Value::user_iterator is an iterator over User*s rather than over the User objects themselves. As a consequence, it fits a bit awkwardly into the range-based world and it has the weird extra-dereferencing 'operator->' that so many of our iterators have. I think this could be fixed by providing something which transforms a range of T&s into a range of T*s, but that *can* be separated into another patch, and it isn't yet 100% clear whether this is the right move. However, this change gets us most of the benefit and cleans up a substantial amount of code around Use and User. =] llvm-svn: 203364
* [C++11] Add 'override' keyword to virtual methods that override their base ↵Craig Topper2014-03-051-2/+2
| | | | | | class. llvm-svn: 202953
* Make DataLayout a plain object, not a pass.Rafael Espindola2014-02-251-1/+5
| | | | | | | Instead, have a DataLayoutPass that holds one. This will allow parts of LLVM don't don't handle passes to also use DataLayout. llvm-svn: 202168
* Rename many DataLayout variables from TD to DL.Rafael Espindola2014-02-211-10/+10
| | | | | | | | | I am really sorry for the noise, but the current state where some parts of the code use TD (from the old name: TargetData) and other parts use DL makes it hard to write a patch that changes where those variables come from and how they are passed along. llvm-svn: 201827
* Disable most IR-level transform passes on functions marked 'optnone'.Paul Robinson2014-02-061-0/+3
| | | | | | | | | Ideally only those transform passes that run at -O0 remain enabled, in reality we get as close as we reasonably can. Passes are responsible for disabling themselves, it's not the job of the pass manager to do it for them. llvm-svn: 200892
* Fix known typosAlp Toker2014-01-241-3/+3
| | | | | | | Sweep the codebase for common typos. Includes some changes to visible function names that were misspelt. llvm-svn: 200018
* [PM] Split DominatorTree into a concrete analysis result object whichChandler Carruth2014-01-131-4/+5
| | | | | | | | | | | | | | | | | | | | | | | 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
* [cleanup] Move the Dominators.h and Verifier.h headers into the IRChandler Carruth2014-01-131-1/+1
| | | | | | | | | | | | | | | | | | 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
* 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
* Even more spelling fixes for "instruction".Robert Wilhelm2013-09-281-1/+1
| | | | llvm-svn: 191611
* Teach loop-idiom about address space pointer sizesMatt Arsenault2013-09-111-12/+21
| | | | llvm-svn: 190491
* Add bracesMatt Arsenault2013-09-111-6/+9
| | | | llvm-svn: 190490
* Fix spelling and grammarMatt Arsenault2013-07-221-12/+12
| | | | llvm-svn: 186858
* 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
OpenPOWER on IntegriCloud