summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/Scalar/GuardWidening.cpp
Commit message (Collapse)AuthorAgeFilesLines
* Broaden the definition of a "widenable branch"Philip Reames2019-11-211-5/+6
| | | | | | | | | | | | As a reminder, a "widenable branch" is the pattern "br i1 (and i1 X, WC()), label %taken, label %untaken" where "WC" is the widenable condition intrinsics. The semantics of such a branch (derived from the semantics of WC) is that a new condition can be added into the condition arbitrarily without violating legality. Broaden the definition in two ways: Allow swapped operands to the br (and X, WC()) form Allow widenable branch w/trivial condition (i.e. true) which takes form of br i1 WC() The former is just general robustness (e.g. for X = non-instruction this is what instcombine produces). The later is specifically important as partial unswitching of a widenable range check produces exactly this form above the loop. Differential Revision: https://reviews.llvm.org/D70502
* [GuardWidening] Remove WidenFrequentBranches transformPhilip Reames2019-11-191-68/+6
| | | | This code has never been enabled. While it is tested, it's complicating some refactoring. If we decide to re-implement this, doing it in SimplifyCFG would probably make more sense anyways.
* [NFC] Factor out utilities for manipulating widenable branchesPhilip Reames2019-11-191-5/+2
| | | | | | With the widenable condition construct, we have the ability to reason about branches which can be 'widened' (i.e. made to fail more often). We've got a couple o transforms which leverage this. This patch just cleans up the API a bit. This is prep work for generalizing our definition of a widenable branch slightly. At the moment "br i1 (and A, wc()), ..." is considered widenable, but oddly, neither "br i1 (and wc(), B), ..." or "br i1 wc(), ..." is. That clearly needs addressed, so first, let's centralize the code in one place.
* Add missing includes needed to prune LLVMContext.h include, NFCReid Kleckner2019-11-141-0/+1
| | | | | These are a pre-requisite to removing #include "llvm/Support/Options.h" from LLVMContext.h: https://reviews.llvm.org/D70280
* 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
* [WC] Fix a subtle bug in our definition of widenable branchPhilip Reames2019-11-061-6/+7
| | | | | | | | | | | | We had a subtle, but nasty bug in our definition of a widenable branch, and thus in the transforms which used that utility. Specifically, we returned true for any branch which included a widenable condition within it's condition, regardless of whether that widenable condition also had other uses. The problem is that the result of the WC() call is defined to be one particular value. As such, all users must agree as to what that value is. If we widen a branch without also updating *all other users* of the WC in the same way, we have broken the required semantics. Most of the textual diff is updating existing transforms not to leave dead uses hanging around. They're largely NFC as the dead instructions would be immediately deleted by other passes. The reason to make these changes is so that the transforms preserve the widenable branch form. In practice, we don't get bitten by this only because it isn't profitable to CSE WC() calls and the lowering pass from guards uses distinct WC calls per branch. Differential Revision: https://reviews.llvm.org/D69916
* GuardWidening - silence static analyzer null dereference warning with ↵Simon Pilgrim2019-10-211-1/+1
| | | | | | assertion. NFCI. llvm-svn: 375428
* [GuardWidening] Wire up a NPM version of the LoopGuardWidening passPhilip Reames2019-04-181-0/+25
| | | | llvm-svn: 358704
* [NFC] Add const qualifiers where possibleMax Kazantsev2019-02-131-28/+29
| | | | llvm-svn: 353941
* [GuardWidening] Support widening of explicitly expressed guardsMax Kazantsev2019-02-131-3/+30
| | | | | | | | | | This patch adds support of guards expressed in explicit form via `widenable_condition` in Guard Widening pass. Differential Revision: https://reviews.llvm.org/D56075 Reviewed By: reames llvm-svn: 353932
* [NFC] Simplify check in guard wideningMax Kazantsev2019-02-061-9/+3
| | | | llvm-svn: 353290
* [NFC] Make a check in GuardWidening more obviousMax Kazantsev2019-02-041-1/+1
| | | | llvm-svn: 353038
* [NFC] Rename variables to reflect the actual status of GuardWideningMax Kazantsev2019-02-041-35/+34
| | | | llvm-svn: 353036
* [NFC] Remove redundant parameters for better readabilityMax Kazantsev2019-02-041-12/+8
| | | | llvm-svn: 353034
* [NFC] Replace equivalent condition for better readabilityMax Kazantsev2019-02-041-1/+2
| | | | llvm-svn: 353032
* 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
* [NFC] Reuse variables instead of re-calling getParentMax Kazantsev2018-12-251-2/+1
| | | | llvm-svn: 350062
* 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
OpenPOWER on IntegriCloud