aboutsummaryrefslogtreecommitdiff
path: root/llvm/lib/Analysis/LoopInfo.cpp
AgeCommit message (Collapse)AuthorFilesLines
2017-12-01IR printing improvement for loop passes - handle -print-module-scopeFedor Sergeev1-0/+12
Summary: Adding support for -print-module-scope similar to how it is being done for function passes. This option causes loop-pass printer to emit a whole-module IR instead of just a loop itself. Reviewers: sanjoy, silvas, weimingz Reviewed By: sanjoy Subscribers: apilipenko, skatkov, llvm-commits Differential Revision: https://reviews.llvm.org/D40247 llvm-svn: 319566
2017-12-01Mark all library options as hidden.Zachary Turner1-1/+1
These command line options are not intended for public use, and often don't even make sense in the context of a particular tool anyway. About 90% of them are already hidden, but when people add new options they forget to hide them, so if you were to make a brand new tool today, link against one of LLVM's libraries, and run tool -help you would get a bunch of junk that doesn't make sense for the tool you're writing. This patch hides these options. The real solution is to not have libraries defining command line options, but that's a much larger effort and not something I'm prepared to take on. Differential Revision: https://reviews.llvm.org/D40674 llvm-svn: 319505
2017-11-22IR printing improvement for loop passesFedor Sergeev1-0/+19
Summary: Loop-pass printing is somewhat deficient since it does not provide the context around the loop (e.g. preheader). This context information becomes pretty essential when analyzing transformations that move stuff out of the loop. Extending printLoop to cover preheader and exit blocks (if any). Reviewers: sanjoy, silvas, weimingz Reviewed By: sanjoy Subscribers: apilipenko, skatkov, llvm-commits Differential Revision: https://reviews.llvm.org/D40246 llvm-svn: 318878
2017-10-15Reverting r315590; it did not include changes for llvm-tblgen, which is ↵Aaron Ballman1-1/+1
causing link errors for several people. Error LNK2019 unresolved external symbol "public: void __cdecl `anonymous namespace'::MatchableInfo::dump(void)const " (?dump@MatchableInfo@?A0xf4f1c304@@QEBAXXZ) referenced in function "public: void __cdecl `anonymous namespace'::AsmMatcherEmitter::run(class llvm::raw_ostream &)" (?run@AsmMatcherEmitter@?A0xf4f1c304@@QEAAXAEAVraw_ostream@llvm@@@Z) llvm-tblgen D:\llvm\2017\utils\TableGen\AsmMatcherEmitter.obj 1 llvm-svn: 315854
2017-10-15[LoopInfo][Refactor] Make SetLoopAlreadyUnrolled a member function of the ↵Hongbin Zheng1-0/+33
Loop Pass, NFC. This avoid code duplication and allow us to add the disable unroll metadata elsewhere. Differential Revision: https://reviews.llvm.org/D38928 llvm-svn: 315850
2017-10-12[dump] Remove NDEBUG from test to enable dump methods [NFC]Don Hinton1-1/+1
Summary: Add LLVM_FORCE_ENABLE_DUMP cmake option, and use it along with LLVM_ENABLE_ASSERTIONS to set LLVM_ENABLE_DUMP. Remove NDEBUG and only use LLVM_ENABLE_DUMP to enable dump methods. Move definition of LLVM_ENABLE_DUMP from config.h to llvm-config.h so it'll be picked up by public headers. Differential Revision: https://reviews.llvm.org/D38406 llvm-svn: 315590
2017-09-28Use a BumpPtrAllocator for Loop objectsSanjoy Das1-3/+1
Summary: And now that we no longer have to explicitly free() the Loop instances, we can (with more ease) use the destructor of LoopBase to do what LoopBase::clear() was doing. Reviewers: chandlerc Subscribers: mehdi_amini, mcrosier, llvm-commits Differential Revision: https://reviews.llvm.org/D38201 llvm-svn: 314375
2017-09-22Rename markAsErased to erase, as pointed out in a previous review; NFCSanjoy Das1-1/+1
llvm-svn: 313951
2017-09-20Tighten the invariants around LoopBase::invalidateSanjoy Das1-1/+4
Summary: With this change: - Methods in LoopBase trip an assert if the receiver has been invalidated - LoopBase::clear frees up the memory held the LoopBase instance This change also shuffles things around as necessary to work with this stricter invariant. Reviewers: chandlerc Subscribers: mehdi_amini, mcrosier, llvm-commits Differential Revision: https://reviews.llvm.org/D38055 llvm-svn: 313708
2017-09-20Clang-format few files to make later diffs leaner; NFCSanjoy Das1-36/+33
llvm-svn: 313705
2017-09-19[LoopInfo] Make LoopBase and Loop destructors non-publicSanjoy Das1-2/+2
Summary: See comment for why I think this is a good idea. This change also: - Removes an SCEV test case. The SCEV test was not testing anything useful (most of it was `#if 0` ed out) and it would need to be updated to deal with a private ~Loop::Loop. - Updates the loop pass manager test case to deal with a private ~Loop::Loop. - Renames markAsRemoved to markAsErased to contrast with removeLoop, via the usual remove vs. erase idiom we already have for instructions and basic blocks. Reviewers: chandlerc Subscribers: mehdi_amini, mcrosier, llvm-commits Differential Revision: https://reviews.llvm.org/D37996 llvm-svn: 313695
2017-07-14[Dominators] Make IsPostDominator a template parameterJakub Kuderski1-1/+1
Summary: DominatorTreeBase used to have IsPostDominators (bool) member to indicate if the tree is a dominator or a postdominator tree. This made it possible to switch between the two 'modes' at runtime, but it isn't used in practice anywhere. This patch makes IsPostDominator a template argument. This way, it is easier to switch between different algorithms at compile-time based on this argument and design external utilities around it. It also makes it impossible to incidentally assign a postdominator tree to a dominator tree (and vice versa), and to further simplify template code in GenericDominatorTreeConstruction. Reviewers: dberlin, sanjoy, davide, grosser Reviewed By: dberlin Subscribers: mzolotukhin, llvm-commits Differential Revision: https://reviews.llvm.org/D35315 llvm-svn: 308040
2017-07-09fix trivial typos; NFCHiroshi Inoue1-1/+1
sucessor -> successor llvm-svn: 307488
2017-07-06[Constants] Replace calls to ConstantInt::equalsInt(0)/equalsInt(1) with ↵Craig Topper1-1/+1
isZero and isOne. NFCI llvm-svn: 307293
2017-07-06[Constants] If we already have a ConstantInt*, prefer to use ↵Craig Topper1-1/+1
isZero/isOne/isMinusOne instead of isNullValue/isOneValue/isAllOnesValue inherited from Constant. NFCI Going through the Constant methods requires redetermining that the Constant is a ConstantInt and then calling isZero/isOne/isMinusOne. llvm-svn: 307292
2017-01-24Make VerifyDomInfo and VerifyLoopInfo global variablesSerge Pavlov1-2/+2
Verifications of dominator tree and loop info are expensive operations so they are disabled by default. They can be enabled by command line options -verify-dom-info and -verify-loop-info. These options however enable checks only in files Dominators.cpp and LoopInfo.cpp. If some transformation changes dominaror tree and/or loop info, it would be convenient to place similar checks to the files implementing the transformation. This change makes corresponding flags global, so they can be used in any file to optionally turn verification on. llvm-svn: 292889
2017-01-15Use getLoopLatch in place of isLoopSimplifyFormXin Tong1-4/+7
Summary: Use getLoopLatch in place of isLoopSimplifyForm. we do not need to know whether the loop has a preheader nor dedicated exits. Reviewers: hfinkel, sanjoy, atrick, mkuper Subscribers: mzolotukhin, llvm-commits Differential Revision: https://reviews.llvm.org/D28724 llvm-svn: 292078
2017-01-15Reverted: Track validity of pass resultsSerge Pavlov1-4/+2
Commits r291882 and related r291887. llvm-svn: 292062
2017-01-15[PM] Introduce an analysis set used to preserve all analyses overChandler Carruth1-0/+9
a function's CFG when that CFG is unchanged. This allows transformation passes to simply claim they preserve the CFG and analysis passes to check for the CFG being preserved to remove the fanout of all analyses being listed in all passes. I've gone through and removed or cleaned up as many of the comments reminding us to do this as I could. Differential Revision: https://reviews.llvm.org/D28627 llvm-svn: 292054
2017-01-13Track validity of pass resultsSerge Pavlov1-2/+4
Running tests with expensive checks enabled exhibits some problems with verification of pass results. First, the pass verification may require results of analysis that are not available. For instance, verification of loop info requires results of dominator tree analysis. A pass may be marked as conserving loop info but does not need to be dependent on DominatorTreePass. When a pass manager tries to verify that loop info is valid, it needs dominator tree, but corresponding analysis may be already destroyed as no user of it remained. Another case is a pass that is skipped. For instance, entities with linkage available_externally do not need code generation and such passes are skipped for them. In this case result verification must also be skipped. To solve these problems this change introduces a special flag to the Pass structure to mark passes that have valid results. If this flag is reset, verifications dependent on the pass result are skipped. Differential Revision: https://reviews.llvm.org/D27190 llvm-svn: 291882
2017-01-11[PM] Rewrite the loop pass manager to use a worklist and augmented runChandler Carruth1-6/+1
arguments much like the CGSCC pass manager. This is a major redesign following the pattern establish for the CGSCC layer to support updates to the set of loops during the traversal of the loop nest and to support invalidation of analyses. An additional significant burden in the loop PM is that so many passes require access to a large number of function analyses. Manually ensuring these are cached, available, and preserved has been a long-standing burden in LLVM even with the help of the automatic scheduling in the old pass manager. And it made the new pass manager extremely unweildy. With this design, we can package the common analyses up while in a function pass and make them immediately available to all the loop passes. While in some cases this is unnecessary, I think the simplicity afforded is worth it. This does not (yet) address loop simplified form or LCSSA form, but those are the next things on my radar and I have a clear plan for them. While the patch is very large, most of it is either mechanically updating loop passes to the new API or the new testing for the loop PM. The code for it is reasonably compact. I have not yet updated all of the loop passes to correctly leverage the update mechanisms demonstrated in the unittests. I'll do that in follow-up patches along with improved FileCheck tests for those passes that ensure things work in more realistic scenarios. In many cases, there isn't much we can do with these until the loop simplified form and LCSSA form are in place. Differential Revision: https://reviews.llvm.org/D28292 llvm-svn: 291651
2017-01-08[LCSSA] Fix some typos. NFCI.Davide Italiano1-3/+3
llvm-svn: 291404
2016-11-23[PM] Change the static object whose address is used to uniquely identifyChandler Carruth1-1/+1
analyses to have a common type which is enforced rather than using a char object and a `void *` type when used as an identifier. This has a number of advantages. First, it at least helps some of the confusion raised in Justin Lebar's code review of why `void *` was being used everywhere by having a stronger type that connects to documentation about this. However, perhaps more importantly, it addresses a serious issue where the alignment of these pointer-like identifiers was unknown. This made it hard to use them in pointer-like data structures. We were already dodging this in dangerous ways to create the "all analyses" entry. In a subsequent patch I attempted to use these with TinyPtrVector and things fell apart in a very bad way. And it isn't just a compile time or type system issue. Worse than that, the actual alignment of these pointer-like opaque identifiers wasn't guaranteed to be a useful alignment as they were just characters. This change introduces a type to use as the "key" object whose address forms the opaque identifier. This both forces the objects to have proper alignment, and provides type checking that we get it right everywhere. It also makes the types somewhat less mysterious than `void *`. We could go one step further and introduce a truly opaque pointer-like type to return from the `ID()` static function rather than returning `AnalysisKey *`, but that didn't seem to be a clear win so this is just the initial change to get to a reliably typed and aligned object serving is a key for all the analyses. Thanks to Richard Smith and Justin Lebar for helping pick plausible names and avoid making this refactoring many times. =] And thanks to Sean for the super fast review! While here, I've tried to move away from the "PassID" nomenclature entirely as it wasn't really helping and is overloaded with old pass manager constructs. Now we have IDs for analyses, and key objects whose address can be used as IDs. Where possible and clear I've shortened this to just "ID". In a few places I kept "AnalysisID" to make it clear what was being identified. Differential Revision: https://reviews.llvm.org/D27031 llvm-svn: 287783
2016-11-08Adds the loop end location to the loop metadata.Amara Emerson1-7/+24
This additional information can be used to improve the locations when generating remarks for loops. Patch by Florian Hahn. Differential Revision: https://reviews.llvm.org/D25763 llvm-svn: 286227
2016-10-11[LCSSA] Implement linear algorithm for the isRecursivelyLCSSAFormIgor Laevsky1-30/+36
For each block check that it doesn't have any uses outside of it's innermost loop. Differential Revision: https://reviews.llvm.org/D25364 llvm-svn: 283877
2016-08-31[LoopInfo] Add verification by recomputation.Michael Zolotukhin1-3/+6
Summary: Current implementation of LI verifier isn't ideal and fails to detect some cases when LI is incorrect. For instance, it checks that all recorded loops are in a correct form, but it has no way to check if there are no more other (unrecorded in LI) loops in the function. This patch adds a way to detect such bugs. Reviewers: chandlerc, sanjoy, hfinkel Subscribers: llvm-commits, silvas, mzolotukhin Differential Revision: https://reviews.llvm.org/D23437 llvm-svn: 280280
2016-08-11Use range algorithms instead of unpacking begin/endDavid Majnemer1-7/+4
No functionality change is intended. llvm-svn: 278417
2016-08-09Consistently use FunctionAnalysisManagerSean Silva1-3/+3
Besides a general consistently benefit, the extra layer of indirection allows the mechanical part of https://reviews.llvm.org/D23256 that requires touching every transformation and analysis to be factored out cleanly. Thanks to David for the suggestion. llvm-svn: 278077
2016-07-27add a verbose mode to Loop->print() to print all the basic blocks of a loopSebastian Pop1-0/+4
Differential Revision: https://reviews.llvm.org/D22817 llvm-svn: 276838
2016-07-19[PM] Port LoopUnroll.Sean Silva1-0/+7
We just set PreserveLCSSA to always true since we don't have an analogous method `mustPreserveAnalysisID(LCSSA)`. Also port LoopInfo verifier pass to test LoopUnrollPass. llvm-svn: 276063
2016-06-26Apply clang-tidy's modernize-loop-convert to lib/Analysis.Benjamin Kramer1-5/+4
Only minor manual fixes. No functionality change intended. llvm-svn: 273816
2016-06-17[PM] Remove support for omitting the AnalysisManager argument to newChandler Carruth1-1/+1
pass manager passes' `run` methods. This removes a bunch of SFINAE goop from the pass manager and just requires pass authors to accept `AnalysisManager<IRUnitT> &` as a dead argument. This is a small price to pay for the simplicity of the system as a whole, despite the noise that changing it causes at this stage. This will also helpfull allow us to make the signature of the run methods much more flexible for different kinds af passes to support things like intelligently updating the pass's progression over IR units. While this touches many, many, files, the changes are really boring. Mostly made with the help of my trusty perl one liners. Thanks to Sean and Hal for bouncing ideas for this with me in IRC. llvm-svn: 272978
2016-05-25Look for a loop's starting location in the llvm.loop metadataHal Finkel1-0/+21
Getting accurate locations for loops is important, because those locations are used by the frontend to generate optimization remarks. Currently, optimization remarks for loops often appear on the wrong line, often the first line of the loop body instead of the loop itself. This is confusing because that line might itself be another loop, or might be somewhere else completely if the body was inlined function call. This happens because of the way we find the loop's starting location. First, we look for a preheader, and if we find one, and its terminator has a debug location, then we use that. Otherwise, we look for a location on an instruction in the loop header. The fallback heuristic is not bad, but will almost always find the beginning of the body, and not the loop statement itself. The preheader location search often fails because there's often not a preheader, and even when there is a preheader, depending on how it was formed, it sometimes carries the location of some preceeding code. I don't see any good theoretical way to fix this problem. On the other hand, this seems like a straightforward solution: Put the debug location in the loop's llvm.loop metadata. A companion Clang patch will cause Clang to insert llvm.loop metadata with appropriate locations when generating debugging information. With these changes, our loop remarks have much more accurate locations. Differential Revision: http://reviews.llvm.org/D19738 llvm-svn: 270771
2016-05-13[scan-build] fix warnings emiited on LLVM Analysis code baseSilviu Baranga1-24/+24
Fix "Logic error" warnings of the type "Called C++ object pointer is null" reported by Clang Static Analyzer on the following files: lib/Analysis/ScalarEvolution.cpp, lib/Analysis/LoopInfo.cpp. Patch by Apelete Seketeli! llvm-svn: 269424
2016-05-03[LoopUnroll] Unroll loops which have exit blocks to EH padsDavid Majnemer1-16/+3
We were overly cautious in our analysis of loops which have invokes which unwind to EH pads. The loop unroll transform is safe because it only clones blocks in the loop body, it does not try to split critical edges involving EH pads. Instead, move the necessary safety check to LoopUnswitch. N.B. The safety check for loop unswitch is covered by an existing test which fails without it. llvm-svn: 268357
2016-04-29Unify XDEBUG and EXPENSIVE_CHECKS (into the latter), and add an option to ↵Filipe Cabecinhas1-1/+1
the cmake build to enable them. Summary: Historically, we had a switch in the Makefiles for turning on "expensive checks". This has never been ported to the cmake build, but the (dead-ish) code is still around. This will also make it easier to turn it on in buildbots. Reviewers: chandlerc Subscribers: jyknight, mzolotukhin, RKSimon, gberry, llvm-commits Differential Revision: http://reviews.llvm.org/D19723 llvm-svn: 268050
2016-03-25IR: Reserve an MDKind for !llvm.loop; NFCDuncan P. N. Exon Smith1-7/+4
This reserves an MDKind for !llvm.loop, which allows callers to avoid a string-based lookup. I'm not sure why it was missing. There should be no functionality change here, just a small compile-time speedup. llvm-svn: 264371
2016-03-11[PM] Make the AnalysisManager parameter to run methods a reference.Chandler Carruth1-4/+4
This was originally a pointer to support pass managers which didn't use AnalysisManagers. However, that doesn't realistically come up much and the complexity of supporting it doesn't really make sense. In fact, *many* parts of the pass manager were just assuming the pointer was never null already. This at least makes it much more explicit and clear. llvm-svn: 263219
2016-03-11[PM] Implement the final conclusion as to how the analysis IDs shouldChandler Carruth1-1/+1
work in the face of the limitations of DLLs and templated static variables. This requires passes that use the AnalysisBase mixin provide a static variable themselves. So as to keep their APIs clean, I've made these private and befriended the CRTP base class (which is the common practice). I've added documentation to AnalysisBase for why this is necessary and at what point we can go back to the much simpler system. This is clearly a better pattern than the extern template as it caught *numerous* places where the template magic hadn't been applied and things were "just working" but would eventually have broken mysteriously. llvm-svn: 263216
2016-02-28[PM] Appease mingw32's auto-import DLL build with minimal tweaks, with fix ↵NAKAMURA Takumi1-0/+2
for clang. char AnalysisBase::ID should be declared as extern and defined in one module. llvm-svn: 262188
2016-02-28Revert r262185, "[PM] Appease mingw32's auto-import DLL build with minimal ↵NAKAMURA Takumi1-2/+0
tweaks." I'll rework soon. llvm-svn: 262186
2016-02-28[PM] Appease mingw32's auto-import DLL build with minimal tweaks.NAKAMURA Takumi1-0/+2
char AnalysisBase::ID should be declared as extern and defined in one module. llvm-svn: 262185
2016-02-26[PM] Introduce CRTP mixin base classes to help define passes andChandler Carruth1-2/+0
analyses in the new pass manager. These just handle really basic stuff: turning a type name into a string statically that is nice to print in logs, and getting a static unique ID for each analysis. Sadly, the format of passes in anonymous namespaces makes using their names in tests really annoying so I've customized the names of the no-op passes to keep tests sane to read. This is the first of a few simplifying refactorings for the new pass manager that should reduce boilerplate and confusion. llvm-svn: 262004
2016-01-29Annotate dump() methods with LLVM_DUMP_METHOD, addressing Richard Smith ↵Yaron Keren1-1/+1
r259192 post commit comment. clang part in r259232, this is the LLVM part of the patch. llvm-svn: 259240
2016-01-17fix variable names; NFCSanjay Patel1-16/+16
llvm-svn: 258027
2016-01-15rangify; NFCISanjay Patel1-49/+40
llvm-svn: 257845
2016-01-14remove duplicate documentation comments (already in the header file) ; NFCSanjay Patel1-54/+8
llvm-svn: 257835
2016-01-08LoopInfo: Simplify ownership of Loop objectsJustin Bogner1-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
2015-12-18[WinEH] Update LCSSA to handle catchswitch with handlers inside and outside ↵Andrew Kaylor1-1/+8
a loop Differential Revision: http://reviews.llvm.org/D15630 llvm-svn: 256005
2015-12-16Fix typo in r255720Justin Bogner1-1/+1
llvm-svn: 255724
generated by cgit v1.1 at 2025-10-18 10:02:54 +0000