summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/Scalar/GuardWidening.cpp
Commit message (Collapse)AuthorAgeFilesLines
* llvm::sort(C.begin(), C.end(), ...) -> llvm::sort(C, ...)Fangrui Song2018-09-271-3/+2
| | | | | | | | | | | | Summary: The convenience wrapper in STLExtras is available since rL342102. Reviewers: dblaikie, javed.absar, JDevlieghere, andreadb Subscribers: MatzeB, sanjoy, arsenm, dschuff, mehdi_amini, sdardis, nemanjai, jvesely, nhaehnle, sbc100, jgravelle-google, eraman, aheejin, kbarton, JDevlieghere, javed.absar, gbedwell, jrtc27, mgrang, atanasyan, steven_wu, george.burgess.iv, dexonsmith, kristina, jsji, llvm-commits Differential Revision: https://reviews.llvm.org/D52573 llvm-svn: 343163
* Re-enable "[NFC] Unify guards detection"Max Kazantsev2018-08-301-6/+1
| | | | | | | | | | rL340921 has been reverted by rL340923 due to linkage dependency from Transform/Utils to Analysis which is not allowed. In this patch this has been fixed, a new utility function moved to Analysis. Differential Revision: https://reviews.llvm.org/D51152 llvm-svn: 341014
* Revert r340921 "[NFC] Unify guards detection"Hans Wennborg2018-08-291-1/+6
| | | | | | | | | | | | | | | | | | This broke the build, see e.g. http://lab.llvm.org:8011/builders/clang-cmake-armv8-lnt/builds/4626/ http://lab.llvm.org:8011/builders/clang-ppc64be-linux-lnt/builds/18647/ http://lab.llvm.org:8011/builders/clang-cmake-x86_64-avx2-linux/builds/5856/ http://lab.llvm.org:8011/builders/lld-x86_64-freebsd/builds/22800/ > We have multiple places in code where we try to identify whether or not > some instruction is a guard. This patch factors out this logic into a separate > utility function which works uniformly in all places. > > Differential Revision: https://reviews.llvm.org/D51152 > Reviewed By: fedor.sergeev llvm-svn: 340923
* [NFC] Unify guards detectionMax Kazantsev2018-08-291-6/+1
| | | | | | | | | | | We have multiple places in code where we try to identify whether or not some instruction is a guard. This patch factors out this logic into a separate utility function which works uniformly in all places. Differential Revision: https://reviews.llvm.org/D51152 Reviewed By: fedor.sergeev llvm-svn: 340921
* [GuardWidening] Ignore guards with trivial conditionsMax Kazantsev2018-08-221-0/+6
| | | | | | | | | | | | Guard widening should not spend efforts on dealing with guards with trivial true/false conditions. Such guards can easily be eliminated by any further cleanup pass like instcombine. However we should not unconditionally delete them because it may be profitable to widen other conditions into such guards. Differential Revision: https://reviews.llvm.org/D50247 Reviewed By: fedor.sergeev llvm-svn: 340381
* [GuardWidening] Widen very likely non-taken br instructionsMax Kazantsev2018-08-131-24/+47
| | | | | | | | | | This is a second part of D49974 that handles widening of conditional branches that have very likely `false` branch. Differential Revision: https://reviews.llvm.org/D50040 Reviewed By: reames llvm-svn: 339537
* Try to fix buildbotMax Kazantsev2018-08-061-1/+1
| | | | llvm-svn: 338991
* [GuardWidening] Widen guards with conditions of frequently taken dominated ↵Max Kazantsev2018-08-061-34/+98
| | | | | | | | | | | | | | | | | | | | | | | | | | branches If there is a frequently taken branch dominated by a guard, and its condition is available at the point of the guard, we can widen guard with condition of this branch and convert the branch into unconditional: guard(cond1) if (cond2) { // taken in 99.9% cases // do something } else { // do something else } Converts to guard(cond1 && cond2) // do something Differential Revision: https://reviews.llvm.org/D49974 Reviewed By: reames llvm-svn: 338988
* [NFC] Add missing commentMax Kazantsev2018-08-031-0/+1
| | | | llvm-svn: 338848
* [NFC] Move some methods into static functionsMax Kazantsev2018-08-031-37/+27
| | | | llvm-svn: 338843
* [NFC] Collect statistics in GuardWideningMax Kazantsev2018-07-311-0/+4
| | | | llvm-svn: 338348
* Remove trailing spaceFangrui Song2018-07-301-2/+2
| | | | | | sed -Ei 's/[[:space:]]+$//' include/**/*.{def,h,td} lib/**/*.{cpp,h} llvm-svn: 338293
* [NFC] Prepare GuardWidening for widening of cond branchesMax Kazantsev2018-07-301-27/+61
| | | | llvm-svn: 338229
* Rename DEBUG macro to LLVM_DEBUG.Nicola Zaghen2018-05-141-6/+7
| | | | | | | | | | | | | | | | The DEBUG() macro is very generic so it might clash with other projects. The renaming was done as follows: - git grep -l 'DEBUG' | xargs sed -i 's/\bDEBUG\s\?(/LLVM_DEBUG(/g' - git diff -U0 master | ../clang/tools/clang-format/clang-format-diff.py -i -p1 -style LLVM - Manual change to APInt - Manually chage DOCS as regex doesn't match it. In the transition period the DEBUG() macro is still present and aliased to the LLVM_DEBUG() one. Differential Revision: https://reviews.llvm.org/D43624 llvm-svn: 332240
* [LoopGuardWidening] Make PostDomTree optionalPhilip Reames2018-04-271-10/+28
| | | | | | | | The effect of doing so is not disrupting the LoopPassManager when mixing this pass with other loop passes. This should help locality of access substaintially and avoids the cost of computing PostDom. The assumption here is that the full GuardWidening (which does use PostDom) is run as a canonicalization before loop opts and that this version is just catching cases exposed by other loop passes. (i.e. LoopPredication, IndVarSimplify, LoopUnswitch, etc..) llvm-svn: 331094
* [GuardWidening] Add some clarifying comments about heuristics [NFC]Philip Reames2018-04-271-0/+8
| | | | llvm-svn: 331061
* [LoopGuardWidening] Split out a loop pass version of GuardWideningPhilip Reames2018-04-271-9/+74
| | | | | | | | The idea is to have a pass which performs the same transformation as GuardWidening, but can be run within a loop pass manager without disrupting the pass manager structure. As demonstrated by the test case, this doesn't quite get there because of issues with post dom, but it gives a good step in the right direction. the motivation is purely to reduce compile time since we can now preserve locality during the loop walk. This patch only includes a legacy pass. A follow up will add a new style pass as well. llvm-svn: 331060
* [Transforms] Change std::sort to llvm::sort in response to r327219Mandeep Singh Grang2018-04-131-3/+3
| | | | | | | | | | | | | | | | | | | | | | Summary: r327219 added wrappers to std::sort which randomly shuffle the container before sorting. This will help in uncovering non-determinism caused due to undefined sorting order of objects having the same key. To make use of that infrastructure we need to invoke llvm::sort instead of std::sort. Note: This patch is one of a series of patches to replace *all* std::sort to llvm::sort. Refer the comments section in D44363 for a list of all the required patches. Reviewers: kcc, pcc, danielcdh, jmolloy, sanjoy, dberlin, ruiu Reviewed By: ruiu Subscribers: ruiu, llvm-commits Differential Revision: https://reviews.llvm.org/D45142 llvm-svn: 330059
* [GuardWidening] Group code by class [NFC]Philip Reames2018-03-231-39/+40
| | | | llvm-svn: 328387
* Guard print() functions only used by dump() functions.Florian Hahn2017-07-311-0/+2
| | | | | | | | | | | | | | | | | | | Summary: Since r293359, most dump() function are only defined when `!defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)` holds. print() functions only used by dump() functions are now unused in release builds, generating lots of warnings. This patch only defines some print() functions if they are used. Reviewers: MatzeB Reviewed By: MatzeB Subscribers: arsenm, mzolotukhin, nhaehnle, llvm-commits Differential Revision: https://reviews.llvm.org/D35949 llvm-svn: 309553
* Sort the remaining #include lines in include/... and lib/....Chandler Carruth2017-06-061-1/+1
| | | | | | | | | | | | | | | | | | | | | | | | | I did this a long time ago with a janky python script, but now clang-format has built-in support for this. I fed clang-format every line with a #include and let it re-sort things according to the precise LLVM rules for include ordering baked into clang-format these days. I've reverted a number of files where the results of sorting includes isn't healthy. Either places where we have legacy code relying on particular include ordering (where possible, I'll fix these separately) or where we have particular formatting around #include lines that I didn't want to disturb in this patch. This patch is *entirely* mechanical. If you get merge conflicts or anything, just ignore the changes in this patch and run clang-format over your #include lines in the files. Sorry for any noise here, but it is important to keep these things stable. I was seeing an increasing number of patches with irrelevant re-ordering of #include lines because clang-format was used. This patch at least isolates that churn, makes it easy to skip when resolving conflicts, and gets us to a clean baseline (again). llvm-svn: 304787
* [ValueTracking] Convert most of the calls to computeKnownBits to use the ↵Craig Topper2017-05-241-3/+1
| | | | | | | | | | version that returns the KnownBits object. This continues the changes started when computeSignBit was replaced with this new version of computeKnowBits. Differential Revision: https://reviews.llvm.org/D33431 llvm-svn: 303773
* Fix typos in commentSanjoy Das2017-05-031-4/+4
| | | | llvm-svn: 302063
* [ValueTracking] Introduce a KnownBits struct to wrap the two APInts for ↵Craig Topper2017-04-261-3/+4
| | | | | | | | | | | | | | | | computeKnownBits This patch introduces a new KnownBits struct that wraps the two APInt used by computeKnownBits. This allows us to treat them as more of a unit. Initially I've just altered the signatures of computeKnownBits and InstCombine's simplifyDemandedBits to pass a KnownBits reference instead of two separate APInt references. I'll do similar to the SelectionDAG version of computeKnownBits/simplifyDemandedBits as a separate patch. I've added a constructor that allows initializing both APInts to the same bit width with a starting value of 0. This reduces the repeated pattern of initializing both APInts. Once place default constructed the APInts so I added a default constructor for those cases. Going forward I would like to add more methods that will work on the pairs. For example trunc, zext, and sext occur on both APInts together in several places. We should probably add a clear method that can be used to clear both pieces. Maybe a method to check for conflicting information. A method to return (Zero|One) so we don't write it out everywhere. Maybe a method for (Zero|One).isAllOnesValue() to determine if all bits are known. I'm sure there are many other methods we can come up with. Differential Revision: https://reviews.llvm.org/D32376 llvm-svn: 301432
* Add a wrapper around copy_if in STLExtras; NFCSanjoy Das2017-02-211-2/+1
| | | | | | I will add one more use for this in a later change. llvm-svn: 295685
* [PM] Introduce an analysis set used to preserve all analyses overChandler Carruth2017-01-151-2/+6
| | | | | | | | | | | | | | | 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
* Analysis: Move llvm::getConstantRangeFromMetadata to IR library.Peter Collingbourne2016-10-211-0/+1
| | | | | | | | We're about to start using it there. Differential Revision: https://reviews.llvm.org/D25877 llvm-svn: 284865
* Consistently use FunctionAnalysisManagerSean Silva2016-08-091-1/+1
| | | | | | | | | | | 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
* fix formatting, typo; NFCSanjay Patel2016-06-191-1/+1
| | | | llvm-svn: 273118
* Avoid copies of std::strings and APInt/APFloats where we only read from itBenjamin Kramer2016-06-081-1/+1
| | | | | | | | As suggested by clang-tidy's performance-unnecessary-copy-initialization. This can easily hit lifetime issues, so I audited every change and ran the tests under asan, which came back clean. llvm-svn: 272126
* [GuardWidening] Tighten the interface of the RangeCheck struct; NFCSanjoy Das2016-05-241-32/+37
| | | | | | Make `GuardWideningImpl::RangeCheck` into a class and add accessors. llvm-svn: 270611
* [GuardWidening] Fix incorrect use of remove_ifSanjoy Das2016-05-211-25/+29
| | | | | | | | | | | I had used `std::remove_if` under the assumption that it moves the predicate matching elements to the end, but actaully the elements remaining towards the end (after the iterator returned by `std::remove_if`) are indeterminate. Fix the bug (and make the code more straightforward) by using a temporary SmallVector, and add a test case demonstrating the issue. llvm-svn: 270306
* Add const qualifiers to appease bots; NFCSanjoy Das2016-05-191-3/+3
| | | | llvm-svn: 270155
* [GuardWidening] Introduce range check mergingSanjoy Das2016-05-191-0/+244
| | | | | | | | | | | | | | | | | | | | | | Sequences of range checks expressed using guards, like guard((I - 2) u< L) guard((I - 1) u< L) guard((I + 0) u< L) guard((I + 1) u< L) guard((I + 2) u< L) can sometimes be combined into a smaller sequence: guard((I - 2) u< L AND (I + 2) u< L) if we can prove that (I - 2) u< L AND (I + 2) u< L implies all of checks expressed in the previous sequence. This change teaches GuardWidening to do this kind of merging when feasible. llvm-svn: 270151
* [GuardWidening] Use getEquivalentICmp to fold constant comparesSanjoy Das2016-05-191-13/+23
| | | | | | | `ConstantRange::getEquivalentICmp` is more general, and better factored. llvm-svn: 270019
* New pass: guard wideningSanjoy Das2016-05-181-0/+428
Summary: Implement guard widening in LLVM. Description from GuardWidening.cpp: The semantics of the `@llvm.experimental.guard` intrinsic lets LLVM transform it so that it fails more often that it did before the transform. This optimization is called "widening" and can be used hoist and common runtime checks in situations like these: ``` %cmp0 = 7 u< Length call @llvm.experimental.guard(i1 %cmp0) [ "deopt"(...) ] call @unknown_side_effects() %cmp1 = 9 u< Length call @llvm.experimental.guard(i1 %cmp1) [ "deopt"(...) ] ... ``` to ``` %cmp0 = 9 u< Length call @llvm.experimental.guard(i1 %cmp0) [ "deopt"(...) ] call @unknown_side_effects() ... ``` If `%cmp0` is false, `@llvm.experimental.guard` will "deoptimize" back to a generic implementation of the same function, which will have the correct semantics from that point onward. It is always _legal_ to deoptimize (so replacing `%cmp0` with false is "correct"), though it may not always be profitable to do so. NB! This pass is a work in progress. It hasn't been tuned to be "production ready" yet. It is known to have quadriatic running time and will not scale to large numbers of guards Reviewers: reames, atrick, bogner, apilipenko, nlewycky Subscribers: mcrosier, llvm-commits Differential Revision: http://reviews.llvm.org/D20143 llvm-svn: 269997
OpenPOWER on IntegriCloud