summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis/LoopInfo.cpp
Commit message (Collapse)AuthorAgeFilesLines
...
* LoopInfo: Simplify ownership of Loop objectsJustin Bogner2016-01-081-2/+4
| | | | | | | | | | | It's strange that LoopInfo mostly owns the Loop objects, but that it defers deleting them to the loop pass manager. Instead, change the oddly named "updateUnloop" to "markAsRemoved" and have it queue the Loop object for deletion. We can't delete the Loop immediately when we remove it, since we need its pointer identity still, so we'll mark the object as "invalid" so that clients can see what's going on. llvm-svn: 257191
* [WinEH] Update LCSSA to handle catchswitch with handlers inside and outside ↵Andrew Kaylor2015-12-181-1/+8
| | | | | | | | a loop Differential Revision: http://reviews.llvm.org/D15630 llvm-svn: 256005
* Fix typo in r255720Justin Bogner2015-12-161-1/+1
| | | | llvm-svn: 255724
* LPM: Simplify how passes mark loops for deletion. NFCJustin Bogner2015-12-161-7/+1
| | | | | | | | | | | | | | | | | | | | When a pass removes a loop it currently has to reach up into the LPPassManager's internals to update the state of the iteration over loops. This reverse dependency results in a pretty awkward interplay of the LPPassManager and its Passes. Here, we change this to instead keep track of when a loop has become "unlooped" in the Loop objects themselves, then the LPPassManager can check this and manipulate its own state directly. This opens the door to allow most of the loop passes to work without a backreference to the LPPassManager. I've kept passes calling the LPPassManager::deleteLoopFromQueue API now so I could put an assert in to prove that this is NFC, but a later pass will update passes just to preserve the LoopInfo directly and stop referencing the LPPassManager completely. llvm-svn: 255720
* [IR] Reformulate LLVM's EH funclet IRDavid Majnemer2015-12-121-1/+7
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | While we have successfully implemented a funclet-oriented EH scheme on top of LLVM IR, our scheme has some notable deficiencies: - catchendpad and cleanupendpad are necessary in the current design but they are difficult to explain to others, even to seasoned LLVM experts. - catchendpad and cleanupendpad are optimization barriers. They cannot be split and force all potentially throwing call-sites to be invokes. This has a noticable effect on the quality of our code generation. - catchpad, while similar in some aspects to invoke, is fairly awkward. It is unsplittable, starts a funclet, and has control flow to other funclets. - The nesting relationship between funclets is currently a property of control flow edges. Because of this, we are forced to carefully analyze the flow graph to see if there might potentially exist illegal nesting among funclets. While we have logic to clone funclets when they are illegally nested, it would be nicer if we had a representation which forbade them upfront. Let's clean this up a bit by doing the following: - Instead, make catchpad more like cleanuppad and landingpad: no control flow, just a bunch of simple operands; catchpad would be splittable. - Introduce catchswitch, a control flow instruction designed to model the constraints of funclet oriented EH. - Make funclet scoping explicit by having funclet instructions consume the token produced by the funclet which contains them. - Remove catchendpad and cleanupendpad. Their presence can be inferred implicitly using coloring information. N.B. The state numbering code for the CLR has been updated but the veracity of it's output cannot be spoken for. An expert should take a look to make sure the results are reasonable. Reviewers: rnk, JosephTremoulet, andrew.w.kaylor Differential Revision: http://reviews.llvm.org/D15139 llvm-svn: 255422
* [IndVars] Have getInsertPointForUses preserve LCSSASanjoy Das2015-12-081-0/+9
| | | | | | | | | | | | | | | Summary: Also add a stricter post-condition for IndVarSimplify. Fixes PR25578. Test case by Michael Zolotukhin. Reviewers: hfinkel, atrick, mzolotukhin Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D15059 llvm-svn: 254977
* Revert "Revert "Strip metadata when speculatively hoisting instructions ↵Igor Laevsky2015-11-181-0/+7
| | | | | | | | (r252604)" Failing clang test is now fixed by the r253458. llvm-svn: 253459
* Revert "Strip metadata when speculatively hoisting instructions"Renato Golin2015-11-101-7/+0
| | | | | | | This reverts commit r252604, as it broke all ARM and AArch64 buildbots, as well as some x86, et al. llvm-svn: 252623
* Strip metadata when speculatively hoisting instructionsIgor Laevsky2015-11-101-0/+7
| | | | | | | | | | | | | | | | This is fix for PR24059. When we are hoisting instruction above some condition it may turn out that metadata on this instruction was control dependant on the condition. This metadata becomes invalid and we need to drop it. This patch should cover most obvious places of speculative execution (which I have found by greping isSafeToSpeculativelyExecute). I think there are more cases but at least this change covers the severe ones. Differential Revision: http://reviews.llvm.org/D14398 llvm-svn: 252604
* PM: Rephrase PrintLoopPass as a wrapper around a new-style pass. NFCJustin Bogner2015-11-041-0/+14
| | | | | | | Splits PrintLoopPass into a new-style pass and a PrintLoopPassWrapper, much like we already do for PrintFunctionPass and PrintModulePass. llvm-svn: 252085
* [IR] Add token typesDavid Majnemer2015-08-141-0/+2
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This introduces the basic functionality to support "token types". The motivation stems from the need to perform operations on a Value whose provenance cannot be obscured. There are several applications for such a type but my immediate motivation stems from WinEH. Our personality routine enforces a single-entry - single-exit regime for cleanups. After several rounds of optimizations, we may be left with a terminator whose "cleanup-entry block" is not entirely clear because control flow has merged two cleanups together. We have experimented with using labels as operands inside of instructions which are not terminators to indicate where we came from but found that LLVM does not expect such exotic uses of BasicBlocks. Instead, we can use this new type to clearly associate the "entry point" and "exit point" of our cleanup. This is done by having the cleanuppad yield a Token and consuming it at the cleanupret. The token type makes it impossible to obscure or otherwise hide the Value, making it trivial to track the relationship between the two points. What is the burden to the optimizer? Well, it turns out we have already paid down this cost by accepting that there are certain calls that we are not permitted to duplicate, optimizations have to watch out for such instructions anyway. There are additional places in the optimizer that we will probably have to update but early examination has given me the impression that this will not be heroic. Differential Revision: http://reviews.llvm.org/D11861 llvm-svn: 245029
* New EH representation for MSVC compatibilityDavid Majnemer2015-07-311-2/+2
| | | | | | | | | | This introduces new instructions neccessary to implement MSVC-compatible exception handling support. Most of the middle-end and none of the back-end haven't been audited or updated to take them into account. Differential Revision: http://reviews.llvm.org/D11097 llvm-svn: 243766
* Add new constructors for LoopInfo/DominatorTree/BFI/BPICong Hou2015-07-161-0/+4
| | | | | | | | | | | | | | | | | Those new constructors make it more natural to construct an object for a function. For example, previously to build a LoopInfo for a function, we need four statements: DominatorTree DT; LoopInfo LI; DT.recalculate(F); LI.analyze(DT); Now we only need one statement: LoopInfo LI(DominatorTree(F)); http://reviews.llvm.org/D11274 llvm-svn: 242486
* Rename LoopInfo::Analyze() to LoopInfo::analyze() and turn its parameter ↵Cong Hou2015-07-161-2/+2
| | | | | | | | | | type to const&. The benefit of turning the parameter of LoopInfo::analyze() to const& is that it now can accept a rvalue. http://reviews.llvm.org/D11250 llvm-svn: 242426
* Add llvm::all_of which wraps std::all_of.Pete Cooper2015-05-131-5/+1
| | | | | | | | | | This version doesn't need begin/end but can instead just take a type which has begin/end methods. Use this to replace an eligible foreach loop in LoopInfo found by David Blaikie in r237224. Reviewed by David Blaikie. llvm-svn: 237301
* Change a loop in LoopInfo to foreach. NFCPete Cooper2015-05-131-2/+2
| | | | llvm-svn: 237224
* Constify arguments to methods in LoopInfo. NFCPete Cooper2015-05-131-3/+3
| | | | llvm-svn: 237223
* Fix -Wpessimizing-move warnings by removing std::move calls.Richard Trieu2015-04-301-1/+1
| | | | llvm-svn: 236278
* Re-sort includes with sort-includes.py and insert raw_ostream.h where it's used.Benjamin Kramer2015-03-231-0/+1
| | | | llvm-svn: 232998
* [PM] Port LoopInfo to the new pass manager, adding both a LoopAnalysisChandler Carruth2015-01-201-0/+21
| | | | | | | | | | | | | | pass and a LoopPrinterPass with the expected associated wiring. I've added a RUN line to the only test case (!!!) we have that actually prints loops. Everything seems to be working. This is somewhat exciting as this is the first analysis using another analysis to go in for the new pass manager. =D I also believe it is the last analysis necessary for porting instcombine, but of course I may yet discover more. llvm-svn: 226560
* [PM] Now that LoopInfo isn't in the Pass type hierarchy, it is muchChandler Carruth2015-01-181-26/+11
| | | | | | | | | | | | cleaner to derive from the generic base. Thise removes a ton of boiler plate code and somewhat strange and pointless indirections. It also remove a bunch of the previously needed friend declarations. To fully remove these, I also lifted the verify logic into the generic LoopInfoBase, which seems good anyways -- it is generic and useful logic even for the machine side. llvm-svn: 226385
* [PM] Cleanup more warnings my refactoring exposed where now we haveChandler Carruth2015-01-171-0/+2
| | | | | | | | | unused variables in a no-asserts build. I've fixed this by putting the entire loop behind an #ifndef as it contains nothing other than asserts. llvm-svn: 226377
* [PM] Split the LoopInfo object apart from the legacy pass, creatingChandler Carruth2015-01-171-27/+31
| | | | | | | | | | a LoopInfoWrapperPass to wire the object up to the legacy pass manager. This switches all the clients of LoopInfo over and paves the way to port LoopInfo to the new pass manager. No functionality change is intended with this iteration. llvm-svn: 226373
* Revert "IR: MDNode => Value"Duncan P. N. Exon Smith2014-11-111-3/+3
| | | | | | | | | | | | | | | | | Instead, we're going to separate metadata from the Value hierarchy. See PR21532. This reverts commit r221375. This reverts commit r221373. This reverts commit r221359. This reverts commit r221167. This reverts commit r221027. This reverts commit r221024. This reverts commit r221023. This reverts commit r220995. This reverts commit r220994. llvm-svn: 221711
* IR: MDNode => Value: Instruction::getMetadata()Duncan P. N. Exon Smith2014-11-011-3/+3
| | | | | | | | | | Change `Instruction::getMetadata()` to return `Value` as part of PR21433. Update most callers to use `Instruction::getMDNode()`, which wraps the result in a `cast_or_null<MDNode>`. llvm-svn: 221024
* Introduce enum values for previously defined metadata types. (NFC)Philip Reames2014-10-211-1/+3
| | | | | | | | | | | Our metadata scheme lazily assigns IDs to string metadata, but we have a mechanism to preassign them as well. Using a preassigned ID is helpful since we get compile time type checking, and avoid some (minimal) string construction and comparison. This change adds enum value for three existing metadata types: + MD_nontemporal = 9, // "nontemporal" + MD_mem_parallel_loop_access = 10, // "llvm.mem.parallel_loop_access" + MD_nonnull = 11 // "nonnull" I went through an updated various uses as well. I made no attempt to get all uses; I focused on the ones which were easily grepable and easily to translate. For example, there were several items in LoopInfo.cpp I chose not to update. llvm-svn: 220248
* Revert "[C++11] Add predecessors(BasicBlock *) / successors(BasicBlock *) ↵Duncan P. N. Exon Smith2014-07-211-9/+10
| | | | | | | | | iterator ranges." This reverts commit r213474 (and r213475), which causes a miscompile on a stage2 LTO build. I'll reply on the list in a moment. llvm-svn: 213562
* [C++11] Add predecessors(BasicBlock *) / successors(BasicBlock *) iterator ↵Manuel Jacob2014-07-201-10/+9
| | | | | | | | | | | | | | | | | | ranges. Summary: This patch introduces two new iterator ranges and updates existing code to use it. No functional change intended. Test Plan: All tests (make check-all) still pass. Reviewers: dblaikie Reviewed By: dblaikie Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D4481 llvm-svn: 213474
* [C++11] More 'nullptr' conversion. In some cases just using a boolean check ↵Craig Topper2014-04-151-15/+15
| | | | | | instead of comparing to nullptr. llvm-svn: 206243
* Consistent use of the noduplicate attribute.Eli Bendersky2014-03-171-2/+2
| | | | | | | | | The "noduplicate" attribute of call instructions is sometimes queried directly and sometimes through the cannotDuplicate() predicate. This patch streamlines all queries to use the cannotDuplicate() predicate. It also adds this predicate to InvokeInst, to mirror what CallInst has. llvm-svn: 204049
* [C++11] Add range based accessors for the Use-Def chain of a Value.Chandler Carruth2014-03-091-6/+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
* [Modules] Move CFG.h to the IR library as it defines graph traits overChandler Carruth2014-03-041-1/+1
| | | | | | IR types. llvm-svn: 202827
* [C++11] Replace llvm::next and llvm::prior with std::next and std::prev.Benjamin Kramer2014-03-021-3/+3
| | | | | | Remove the old functions. llvm-svn: 202636
* [PM] Split DominatorTree into a concrete analysis result object whichChandler Carruth2014-01-131-3/+3
| | | | | | | | | | | | | | | | | | | | | | | 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
* Put the functionality for printing a value to a raw_ostream as anChandler Carruth2014-01-091-1/+0
| | | | | | | | | | | | operand into the Value interface just like the core print method is. That gives a more conistent organization to the IR printing interfaces -- they are all attached to the IR objects themselves. Also, update all the users. This removes the 'Writer.h' header which contained only a single function declaration. llvm-svn: 198836
* Move the LLVM IR asm writer header files into the IR directory, as theyChandler Carruth2014-01-071-1/+1
| | | | | | | | | | | | | | | | | are part of the core IR library in order to support dumping and other basic functionality. Rename the 'Assembly' include directory to 'AsmParser' to match the library name and the only functionality left their -- printing has been in the core IR library for quite some time. Update all of the #includes to match. All of this started because I wanted to have the layering in good shape before I started adding support for printing LLVM IR using the new pass infrastructure, and commandline support for the new pass infrastructure. llvm-svn: 198688
* Simplify code. No functionality change.Jakub Staszak2013-11-131-8/+8
| | | | llvm-svn: 194602
* Quick look-up for block in loop.Wan Xiaofei2013-10-261-15/+3
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This patch implements quick look-up for block in loop by maintaining a hash set for blocks. It improves the efficiency of loop analysis a lot, the biggest improvement could be 5-6%(458.sjeng). Below are the compilation time for our benchmark in llc before & after the patch. Benchmark llc - trunk llc - patched 401.bzip2 0.339081 100.00% 0.329657 102.86% 403.gcc 19.853966 100.00% 19.605466 101.27% 429.mcf 0.049823 100.00% 0.048451 102.83% 433.milc 0.514898 100.00% 0.510217 100.92% 444.namd 1.109328 100.00% 1.103481 100.53% 445.gobmk 4.988028 100.00% 4.929114 101.20% 456.hmmer 0.843871 100.00% 0.825865 102.18% 458.sjeng 0.754238 100.00% 0.714095 105.62% 464.h264ref 2.9668 100.00% 2.90612 102.09% 471.omnetpp 4.556533 100.00% 4.511886 100.99% bitmnp01 0.038168 100.00% 0.0357 106.91% idctrn01 0.037745 100.00% 0.037332 101.11% libquake2 3.78689 100.00% 3.76209 100.66% libquake_ 2.251525 100.00% 2.234104 100.78% linpack 0.033159 100.00% 0.032788 101.13% matrix01 0.045319 100.00% 0.043497 104.19% nbench 0.333161 100.00% 0.329799 101.02% tblook01 0.017863 100.00% 0.017666 101.12% ttsprk01 0.054337 100.00% 0.053057 102.41% Reviewer : Andrew Trick <atrick@apple.com>, Hal Finkel <hfinkel@anl.gov> Approver : Andrew Trick <atrick@apple.com> Test : Pass make check-all & llvm test-suite llvm-svn: 193460
* Add 'const' qualifiers to static const char* variables.Craig Topper2013-07-161-1/+1
| | | | llvm-svn: 186371
* Add support for llvm.vectorizer metadataPaul Redmond2013-05-281-6/+57
| | | | | | | | | | | | | | | | | | | - llvm.loop.parallel metadata has been renamed to llvm.loop to be more generic by making the root of additional loop metadata. - Loop::isAnnotatedParallel now looks for llvm.loop and associated llvm.mem.parallel_loop_access - document llvm.loop and update llvm.mem.parallel_loop_access - add support for llvm.vectorizer.width and llvm.vectorizer.unroll - document llvm.vectorizer.* metadata - add utility class LoopVectorizerHints for getting/setting loop metadata - use llvm.vectorizer.width=1 to indicate already vectorized instead of already_vectorized - update existing tests that used llvm.loop.parallel and llvm.vectorizer.already_vectorized Reviewed by: Nadav Rotem llvm-svn: 182802
* Metadata for annotating loops as parallel. The first consumer for this Pekka Jaaskelainen2013-02-131-0/+50
| | | | | | | | metadata is the loop vectorizer. See the documentation update for more info. llvm-svn: 175060
* Move all of the header files which are involved in modelling the LLVM IRChandler Carruth2013-01-021-2/+2
| | | | | | | | | | | | | | | | | | | | | 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
* Add a new attribute, 'noduplicate'. If a function contains a noduplicate ↵James Molloy2012-12-201-2/+14
| | | | | | | | 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
* 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
* 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
* Reduce duplicated hash map lookups.Benjamin Kramer2012-08-221-5/+4
| | | | llvm-svn: 162362
* Enable the new LoopInfo algorithm by default.Andrew Trick2012-06-261-8/+1
| | | | | | | | | | | | | | | | | | | | | | | | The primary advantage is that loop optimizations will be applied in a stable order. This helps debugging and unit test creation. It is also a better overall implementation without pathologically bad performance on deep functions. On large functions (llvm-stress --size=200000 | opt -loops) Before: 0.1263s After: 0.0225s On deep functions (after tweaking llvm-stress, thanks Nadav): Before: 0.2281s After: 0.0227s See r158790 for more comments. The loop tree is now consistently generated in forward order, but loop passes are applied in reverse order over the program. If we have a loop optimization that prefers forward order, that can easily be achieved by adding a different type of LoopPassManager. llvm-svn: 159183
* Remove unnecessary FIXMEAndrew Trick2012-06-261-3/+0
| | | | llvm-svn: 159182
OpenPOWER on IntegriCloud