summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis/MustExecute.cpp
Commit message (Collapse)AuthorAgeFilesLines
* Sink all InitializePasses.h includesReid Kleckner2019-11-131-1/+2
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This file lists every pass in LLVM, and is included by Pass.h, which is very popular. Every time we add, remove, or rename a pass in LLVM, it caused lots of recompilation. I found this fact by looking at this table, which is sorted by the number of times a file was changed over the last 100,000 git commits multiplied by the number of object files that depend on it in the current checkout: recompiles touches affected_files header 342380 95 3604 llvm/include/llvm/ADT/STLExtras.h 314730 234 1345 llvm/include/llvm/InitializePasses.h 307036 118 2602 llvm/include/llvm/ADT/APInt.h 213049 59 3611 llvm/include/llvm/Support/MathExtras.h 170422 47 3626 llvm/include/llvm/Support/Compiler.h 162225 45 3605 llvm/include/llvm/ADT/Optional.h 158319 63 2513 llvm/include/llvm/ADT/Triple.h 140322 39 3598 llvm/include/llvm/ADT/StringRef.h 137647 59 2333 llvm/include/llvm/Support/Error.h 131619 73 1803 llvm/include/llvm/Support/FileSystem.h Before this change, touching InitializePasses.h would cause 1345 files to recompile. After this change, touching it only causes 550 compiles in an incremental rebuild. Reviewers: bkramer, asbirlea, bollu, jdoerfert Differential Revision: https://reviews.llvm.org/D70211
* [FIX] Make LSan happy by *not* leaking memoryJohannes Doerfert2019-10-311-4/+13
| | | | | | | I left a memory leak in a printer pass which made LSan sad so I remove the memory leak now to make LSan happy. Reported and tested by vlad.tsyrklevich.
* [MustExecute] Silence clang warning about unused captured 'this'Mikael Holmen2019-10-311-2/+2
| | | | | | | | | | | | New code introduced in fe799c97fa caused clang to complain with ../lib/Analysis/MustExecute.cpp:360:34: error: lambda capture 'this' is not used [-Werror,-Wunused-lambda-capture] GetterTy<LoopInfo> LIGetter = [this](const Function &F) { ^~~~ ../lib/Analysis/MustExecute.cpp:365:44: error: lambda capture 'this' is not used [-Werror,-Wunused-lambda-capture] GetterTy<PostDominatorTree> PDTGetter = [this](const Function &F) { ^~~~ 2 errors generated.
* [MustExecute] Forward iterate over conditional branchesJohannes Doerfert2019-10-311-1/+187
| | | | | | | | | | | | | | | | | | | Summary: If a conditional branch is encountered we can try to find a join block where the execution is known to continue. This means finding a suitable block, e.g., the immediate post dominator of the conditional branch, and proofing control will always reach that block. This patch implements different techniques that work with and without provided analysis. Reviewers: uenoku, sstefan1, hfinkel Subscribers: hiraditya, bollu, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D68933
* [MustExec] Add a generic "must-be-executed-context" explorerJohannes Doerfert2019-08-231-0/+118
| | | | | | | | | | | | | | | | Given an instruction I, the MustBeExecutedContextExplorer allows to easily traverse instructions that are guaranteed to be executed whenever I is. For now, these instruction have to be statically "after" I, in the same or different basic blocks. This patch also adds a pass which prints the must-be-executed-context for each instruction in a module. It is used to test the MustBeExecutedContextExplorer, for now on the examples given in the class comment of the MustBeExecutedIterator. Differential Revision: https://reviews.llvm.org/D65186 llvm-svn: 369765
* [MustExecute] Improve MustExecute to correctly handle loop nestXing Xue2019-05-271-1/+8
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: for.outer: br for.inner for.inner: LI <loop invariant load instruction> for.inner.latch: br for.inner, for.outer.latch for.outer.latch: br for.outer, for.outer.exit LI is a loop invariant load instruction that post dominate for.outer, so LI should be able to move out of the loop nest. However, there is a bug in allLoopPathsLeadToBlock(). Current algorithm of allLoopPathsLeadToBlock() 1. get all the transitive predecessors of the basic block LI belongs to (for.inner) ==> for.outer, for.inner.latch 2. if any successors of any of the predecessors are not for.inner or for.inner's predecessors, then return false 3. return true Although for.inner.latch is for.inner's predecessor, but for.inner dominates for.inner.latch, which means if for.inner.latch is ever executed, for.inner should be as well. It should not return false for cases like this. Author: Whitney (committed by xingxue) Reviewers: kbarton, jdoerfert, Meinersbur, hfinkel, fhahn Reviewed By: jdoerfert Subscribers: hiraditya, jsji, llvm-commits, etiotto, bmahjour Tags: #LLVM Differential Revision: https://reviews.llvm.org/D62418 llvm-svn: 361762
* Update the file headers across all of the LLVM projects in the monorepoChandler Carruth2019-01-191-4/+3
| | | | | | | | | | | | | | | | | to reflect the new license. We understand that people may be surprised that we're moving the header entirely to discuss the new license. We checked this carefully with the Foundation's lawyer and we believe this is the correct approach. Essentially, all code in the project is now made available by the LLVM project under our new license, so you will see that the license headers include that license only. Some of our contributors have contributed code under our old license, and accordingly, we have retained a copy of our old license notice in the top-level files in each project and repository. llvm-svn: 351636
* [IPT] Drop cache less eagerly in GVN and LoopSafetyInfoMax Kazantsev2019-01-091-7/+6
| | | | | | | | | | | | | | | | | | | | Current strategy of dropping `InstructionPrecedenceTracking` cache is to invalidate the entire basic block whenever we change its contents. In fact, `InstructionPrecedenceTracking` has 2 internal strictures: `OrderedInstructions` that is needed to be invalidated whenever the contents changes, and the map with first special instructions in block. This second map does not need an update if we add/remove a non-special instuction because it cannot affect the contents of this map. This patch changes API of `InstructionPrecedenceTracking` so that it now accounts for reasons under which we invalidate blocks. This should lead to much less recalculations of the map and should save us some compile time because in practice we don't typically add/remove special instructions. Differential Revision: https://reviews.llvm.org/D54462 Reviewed By: efriedma llvm-svn: 350694
* [LICM] Hoist guards from non-header blocksMax Kazantsev2018-11-121-0/+31
| | | | | | | | | | | This patch relaxes overconservative checks on whether or not we could write memory before we execute an instruction. This allows us to hoist guards out of loops even if they are not in the header block. Differential Revision: https://reviews.llvm.org/D50891 Reviewed By: fedor.sergeev llvm-svn: 346643
* [NFC] Turn collectTransitivePredecessors into a static functionMax Kazantsev2018-11-061-2/+5
| | | | llvm-svn: 346217
* [NFC] Specialize public API of ICFLoopSafetyInfo for insertions and removalsMax Kazantsev2018-11-011-1/+7
| | | | llvm-svn: 345822
* [NFC] Introduce ICFLoopSafetyInfoMax Kazantsev2018-10-161-0/+31
| | | | | | | | | | | | | | | | This is an alternative implementation of LoopSafetyInfo that uses the implicit control flow tracking to give precise answers on queries "whether or not this block contains throwing instructions". This rules out false-positive answers on LoopSafetyInfo's queries. This patch only introduces the new implementation. It is not currently used in any pass. The enabling patches will go separately, through review. The plan is to completely replace all uses of LoopSafetyInfo with ICFLoopSafetyInfo in the future, but to avoid introducing functional problems, we will do it pass by pass. llvm-svn: 344601
* [NFC] Remove obsolete method headerMayThrowMax Kazantsev2018-10-161-13/+2
| | | | llvm-svn: 344596
* [NFC] Make LoopSafetyInfo abstract to allow alternative implementationsMax Kazantsev2018-10-161-8/+8
| | | | llvm-svn: 344592
* [NFC] Encapsulate work with BlockColors in LoopSafetyInfoMax Kazantsev2018-10-161-1/+16
| | | | llvm-svn: 344590
* [NFC] Move block throw check inside allLoopPathsLeadToBlockMax Kazantsev2018-10-161-6/+10
| | | | llvm-svn: 344588
* [NFC] Turn isGuaranteedToExecute into a methodMax Kazantsev2018-10-161-8/+8
| | | | llvm-svn: 344587
* [NFC] Factor out predecessors collection into a separate methodMax Kazantsev2018-08-211-11/+20
| | | | | | | | | It may be reused in a different piece of logic. Differential Revision: https://reviews.llvm.org/D50890 Reviewed By: reames llvm-svn: 340250
* [MustExecute] Fix algorithmic bug in isGuaranteedToExecute. PR38514Max Kazantsev2018-08-171-33/+70
| | | | | | | | | | | | | | | | | | | | | The description of `isGuaranteedToExecute` does not correspond to its implementation. According to description, it should return `true` if an instruction is executed under the assumption that its loop is *entered*. However there is a sophisticated alrogithm inside that tries to prove that the instruction is executed if the loop is *exited*, which is not the same thing for infinite loops. There is an attempt to protect from dealing with infinite loops by prohibiting loops without exit blocks, however an infinite loop can have exit blocks. As result of that, MustExecute can falsely consider some blocks that are never entered as mustexec, and LICM can hoist dangerous instructions out of them basing on this fact. This may introduce UB to programs which did not contain it initially. This patch removes the problematic algorithm and replaced it with a one which tries to prove what is required in description. Differential Revision: https://reviews.llvm.org/D50558 Reviewed By: reames llvm-svn: 339984
* [NFC] Add missing const modifierMax Kazantsev2018-08-161-1/+1
| | | | llvm-svn: 339844
* [NFC] Refactoring of LoopSafetyInfo, step 1Max Kazantsev2018-08-151-18/+17
| | | | | | | | | Turn structure into class, encapsulate methods, add clarifying comments. Differential Revision: https://reviews.llvm.org/D50693 Reviewed By: reames llvm-svn: 339752
* Remove trailing spaceFangrui Song2018-07-301-3/+3
| | | | | | sed -Ei 's/[[:space:]]+$//' include/**/*.{def,h,td} lib/**/*.{cpp,h} llvm-svn: 338293
* [Analysis] Fix typo in assert. NFCShoaib Meenai2018-07-191-1/+1
| | | | | | Test commit to see if my mailing list woes have been resolved. llvm-svn: 337485
* [MustExecute] Fix a debug invariant issue in isGuaranteedToExecute()David Stenberg2018-05-251-1/+1
| | | | | | | | | | | | | | | | | | | | | | | | | Summary: Look past debug intrinsics when querying whether an instruction is the first instruction in the header block. The commit includes a reproducer for a case where LICM would not hoist an instruction, due to the presence of the intrinsic. A caveat with this commit is that the check will not work properly if the instruction at hand is a debug intrinsic. I assume that no one depends on isGuaranteedToExecute() to return true for debug intrinsics for these cases (and that this might be an indication of another debug invariant issue), so I thought that it was not worth adding that extra bit of complexity. Reviewers: reames, anna Reviewed By: anna Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D47197 llvm-svn: 333274
* [LICM] Extend the MustExecute scopeSerguei Katkov2018-05-181-0/+4
| | | | | | | | | | | | CanProveNotTakenFirstIteration utility does not handle the case when condition of the branch is a constant. Add its handling. Reviewers: reames, anna, mkazantsev Reviewed By: reames Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D46996 llvm-svn: 332695
* [WebAssembly] Add Wasm personality and isScopedEHPersonality()Heejin Ahn2018-05-171-1/+1
| | | | | | | | | | | | | | | | | | | | | Summary: - Add wasm personality function - Re-categorize the existing `isFuncletEHPersonality()` function into two different functions: `isFuncletEHPersonality()` and `isScopedEHPersonality(). This becomes necessary as wasm EH uses scoped EH instructions (catchswitch, catchpad/ret, and cleanuppad/ret) but not outlined funclets. - Changed some callsites of `isFuncletEHPersonality()` to `isScopedEHPersonality()` if they are related to scoped EH IR-level stuff. Reviewers: majnemer, dschuff, rnk Subscribers: jfb, sbc100, jgravelle-google, eraman, JDevlieghere, sunfish, llvm-commits Differential Revision: https://reviews.llvm.org/D45559 llvm-svn: 332667
* Remove \brief commands from doxygen comments.Adrian Prantl2018-05-011-1/+1
| | | | | | | | | | | | | | | | We've been running doxygen with the autobrief option for a couple of years now. This makes the \brief markers into our comments redundant. Since they are a visual distraction and we don't want to encourage more \brief markers in new code either, this patch removes them all. Patch produced by for i in $(git grep -l '\\brief'); do perl -pi -e 's/\\brief //g' $i & done Differential Revision: https://reviews.llvm.org/D46290 llvm-svn: 331272
* [MustExecute/LICM] Special case first instruction in throwing headerPhilip Reames2018-04-271-2/+5
| | | | | | | | | | | We currently have a hard to solve analysis problem around the order of instructions within a potentially throwing block. We can't cheaply determine whether a given instruction is before the first potential throw in the block. While we're working on that in the background, special case the first instruction within the header. why this particular special case? Well, headers are guaranteed to execute if the loop does, and it turns out we tend to produce this form in practice. In a follow on patch, I tend to extend LICM with an alternate approach which works for any instruction in the header before the first throw, but this is the best I can come up with other users of the analysis (such as store promotion.) Note: I can't show the difference in the analysis result since we're ORing in the expensive instruction walk used by SCEV. Using the full walk is not suitable for a general solution. llvm-svn: 331079
* Make helpers static. NFC.Benjamin Kramer2018-04-041-1/+3
| | | | llvm-svn: 329170
* Fix an accidental circular dependencePhilip Reames2018-03-291-1/+1
| | | | llvm-svn: 328816
* [MustExecute] Shwo the effect of using full loop info variantPhilip Reames2018-03-201-5/+7
| | | | | | | | Most basic possible test for the logic used by LICM. Also contains a speculative build fix for compiles which complain about a definition of a stuct K; followed by a declaration as class K; llvm-svn: 328058
* [MustExecute] Move isGuaranteedToExecute and related rourtines to AnalysisPhilip Reames2018-03-201-0/+135
| | | | | | Next step is to actually merge the implementations and get both implementations tested through the new printer. llvm-svn: 328055
* [MustExecute] Use the annotation style printerPhilip Reames2018-03-201-33/+54
| | | | | | | As suggested in the original review (https://reviews.llvm.org/D44524), use an annotation style printer instead. Note: The switch from -analyze to -disable-output in tests was driven by the fact that seems to be the idiomatic style used in annoation passes. I tried to keep both working, but the old style pass API for printers really doesn't make this easy. It invokes (runOnFunction, print(Module)) repeatedly. I decided the extra state wasn't worth it given the old pass manager is going away soonish anyway. llvm-svn: 328015
* Add an analysis printer for must execute reasoningPhilip Reames2018-03-201-0/+102
Many of our loop passes make use of so called "must execute" or "guaranteed to execute" facts to prove the legality of code motion. The basic notion is that we know (by assumption) an instruction didn't fault at it's original location, so if the location we move it to is strictly post dominated by the original, then we can't have introduced a new fault. At the moment, the testing for this logic is somewhat adhoc and done mostly through LICM. Since I'm working on that code, I want to improve the testing. This patch is the first step in that direction. It doesn't actually test the variant used by the loop passes - I need to move that to the Analysis library first - but instead exercises an alternate implementation used by SCEV. (I plan on merging both implementations.) Note: I'll be replacing the printing logic within this with an annotation based version in the near future. Anna suggested this in review, and it seems like a strictly better format. Differential Revision: https://reviews.llvm.org/D44524 llvm-svn: 328004
OpenPOWER on IntegriCloud