summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/Scalar/EarlyCSE.cpp
Commit message (Collapse)AuthorAgeFilesLines
* [EarlyCSE] Fix hashing of self-comparesJoseph Tremoulet2019-06-171-2/+7
| | | | | | | | | | | | | | | | | | | | | | | Summary: Update compare normalization in SimpleValue hashing to break ties (when the same value is being compared to itself) by switching to the swapped predicate if it has a lower numerical value. This brings the hashing in line with isEqual, which already recognizes the self-compares with swapped predicates as equal. Fixes PR 42280. Reviewers: spatel, efriedma, nikic, fhahn, uabelho Reviewed By: nikic Subscribers: hiraditya, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D63349 llvm-svn: 363598
* [EarlyCSE] Ensure equal keys have the same hash valueJoseph Tremoulet2019-06-131-64/+110
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: The logic in EarlyCSE that looks through 'not' operations in the predicate recognizes e.g. that `select (not (cmp sgt X, Y)), X, Y` is equivalent to `select (cmp sgt X, Y), Y, X`. Without this change, however, only the latter is recognized as a form of `smin X, Y`, so the two expressions receive different hash codes. This leads to missed optimization opportunities when the quadratic probing for the two hashes doesn't happen to collide, and assertion failures when probing doesn't collide on insertion but does collide on a subsequent table grow operation. This change inverts the order of some of the pattern matching, checking first for the optional `not` and then for the min/max/abs patterns, so that e.g. both expressions above are recognized as a form of `smin X, Y`. It also adds an assertion to isEqual verifying that it implies equal hash codes; this fires when there's a collision during insertion, not just grow, and so will make it easier to notice if these functions fall out of sync again. A new flag --earlycse-debug-hash is added which can be used when changing the hash function; it forces hash collisions so that any pair of values inserted which compare as equal but hash differently will be caught by the isEqual assertion. Reviewers: spatel, nikic Reviewed By: spatel, nikic Subscribers: lebedev.ri, arsenm, craig.topper, efriedma, hiraditya, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D62644 llvm-svn: 363274
* [EarlyCSE] detect equivalence of selects with inverse conditions and ↵Sanjay Patel2019-04-161-2/+59
| | | | | | | | | | | | | | | | | | commuted operands (PR41101) This is 1 of the problems discussed in the post-commit thread for: rL355741 / http://lists.llvm.org/pipermail/llvm-commits/Week-of-Mon-20190311/635516.html and filed as: https://bugs.llvm.org/show_bug.cgi?id=41101 Instcombine tries to canonicalize some of these cases (and there's room for improvement there independently of this patch), but it can't always do that because of extra uses. So we need to recognize these commuted operand patterns here in EarlyCSE. This is similar to how we detect commuted compares and commuted min/max/abs. Differential Revision: https://reviews.llvm.org/D60723 llvm-svn: 358523
* Very minor typo. NFCKristina Brooks2019-03-121-1/+1
| | | | | | | | | | Typo `we we're` => `we were` in the pass EarlyCSE Patch by liangdzou (Liang ZOU) Differential Revision: https://reviews.llvm.org/D59241 llvm-svn: 355895
* [EarlyCSE] Cleanup deadcode. [NFCI]Alina Sbirlea2019-02-211-5/+1
| | | | | | | | | | | | | | Summary: Cleanup nop assignments. Reviewers: george.burgess.iv, davide Subscribers: sanjoy, jlebar, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D58308 llvm-svn: 354612
* [EarlyCSE & MSSA] Cap the clobbering calls in EarlyCSE.Alina Sbirlea2019-02-151-2/+13
| | | | | | | | | | | | | | | | | | | Summary: Unlimitted number of calls to getClobberingAccess can lead to high compile times in pathological cases. Limitting getClobberingAccess to a fairly high number. Can be adjusted based on users/need. Note: this is the only user of MemorySSA currently enabled by default. The same handling exists in LICM (disabled atm). As MemorySSA gains more users, this logic of capping will need to move inside MemorySSA. Reviewers: george.burgess.iv Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D58248 llvm-svn: 354182
* [EarlyCSE & MSSA] Cleanup special handling for removing MemoryAccesses.Alina Sbirlea2019-01-311-30/+5
| | | | | | | | | | | | Summary: Moving special handling to MemorySSAUpdater in D57199. Reviewers: gberry, george.burgess.iv Subscribers: sanjoy, jlebar, Prazek, llvm-commits Differential Revision: https://reviews.llvm.org/D57200 llvm-svn: 352794
* 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
* [EarlyCSE] If DI can't be salvaged, mark it as unavailable.Davide Italiano2018-12-171-1/+2
| | | | | | Fixes PR39874. llvm-svn: 349323
* [EarlyCSEwMemorySSA] Add MSSA verification and tests to make EarlyCSE ↵Alina Sbirlea2018-09-171-0/+2
| | | | | | | | | | | | | | | | | failures easier to track. Summary: EarlyCSE can make IR changes that will leave MemorySSA with accesses claiming to be optimized, but for which a subsequent MemorySSA run will yield a different optimized result. Due to relying on AA queries, we can't fix this in general, unless we recompute MemorySSA. Adding some tests to track this and a basic verify for future potential failures. Reviewers: george.burgess.iv, gberry Subscribers: sanjoy, jlebar, Prazek, llvm-commits Differential Revision: https://reviews.llvm.org/D51960 llvm-svn: 342422
* Re-enable "[NFC] Unify guards detection"Max Kazantsev2018-08-301-1/+3
| | | | | | | | | | 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-2/+1
| | | | | | | | | | | | | | | | | | 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-1/+2
| | | | | | | | | | | 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
* Remove trailing spaceFangrui Song2018-07-301-3/+3
| | | | | | sed -Ei 's/[[:space:]]+$//' include/**/*.{def,h,td} lib/**/*.{cpp,h} llvm-svn: 338293
* [EarlyCSE] Fix MSVC build. NFCI.Simon Pilgrim2018-06-141-9/+5
| | | | | | MSVC doesn't let you assign different lambdas through a ternary operator. llvm-svn: 334715
* [EarlyCSE] Propagate conditions of AND and OR instructionsMax Kazantsev2018-06-141-14/+43
| | | | | | | | | | | This patches teaches EarlyCSE to figure out that if `and i1 %x, %y` is true then both `%x` and `%y` are true in the taken branch, and if `or i1 %x, %y` is false then both `%x` and `%y` are false in non-taken branch. Fix for PR37635. Differential Revision: https://reviews.llvm.org/D47574 Reviewed By: reames llvm-svn: 334707
* [NFC] fix trivial typos in commentsHiroshi Inoue2018-06-141-2/+2
| | | | llvm-svn: 334687
* Move Analysis/Utils/Local.h back to TransformsDavid Blaikie2018-06-041-1/+1
| | | | | | | | | | Review feedback from r328165. Split out just the one function from the file that's used by Analysis. (As chandlerc pointed out, the original change only moved the header and not the implementation anyway - which was fine for the one function that was used (since it's a template/inlined in the header) but not in general) llvm-svn: 333954
* [NFC] Factor out a method for further extensionMax Kazantsev2018-05-311-20/+32
| | | | llvm-svn: 333633
* [EarlyCSE] Improve EarlyCSE of some absolute value cases.Craig Topper2018-05-211-4/+12
| | | | | | | | | | Change matchSelectPattern to return X and -X for ABS/NABS in a well defined order. Adjust EarlyCSE to account for this. Ensure the SPF result is some kind of min/max and not abs/nabs in one place in InstCombine that made me nervous. Prevously we returned the two operands of the compare part of the abs pattern. The RHS is always going to be a 0i, 1 or -1 constant. This isn't a very meaningful thing to return for any one. There's also some freedom in the abs pattern as to what happens when the value is equal to 0. This freedom led to early cse failing to match when different constants were used in otherwise equivalent operations. By returning the input and its negation in a defined order we can ensure an exact match. This also makes sure both patterns use the exact same subtract instruction for the negation. I believe CSE should evebntually make this happen and properly merge the nsw/nuw flags. But I'm not familiar with CSE and what order it does things in so it seemed like it might be good to really enforce that they were the same. Differential Revision: https://reviews.llvm.org/D47037 llvm-svn: 332865
* Rename DEBUG macro to LLVM_DEBUG.Nicola Zaghen2018-05-141-25/+29
| | | | | | | | | | | | | | | | 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
* Remove \brief commands from doxygen comments.Adrian Prantl2018-05-011-9/+9
| | | | | | | | | | | | | | | | 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
* [EarlyCSE] Add debug counter for debugging mis-optimizations. NFC.Geoff Berry2018-04-061-24/+60
| | | | | | | | | | Reviewers: reames, spatel, davide, dberlin Subscribers: mcrosier, llvm-commits Differential Revision: https://reviews.llvm.org/D45162 llvm-svn: 329443
* Fix a couple of layering violations in TransformsDavid Blaikie2018-03-211-1/+1
| | | | | | | | | | | | | Remove #include of Transforms/Scalar.h from Transform/Utils to fix layering. Transforms depends on Transforms/Utils, not the other way around. So remove the header and the "createStripGCRelocatesPass" function declaration (& definition) that is unused and motivated this dependency. Move Transforms/Utils/Local.h into Analysis because it's used by Analysis/MemoryBuiltins.cpp. llvm-svn: 328165
* [EarlyCSE] Don't hide earler invariant.scopesPhilip Reames2018-03-151-3/+8
| | | | | | | | If we've already established an invariant scope with an earlier generation, we don't want to hide it in the scoped hash table with one with a later generation. I noticed this when working on the invariant-load handling, but it also applies to the invariant.start case as well. Without this change, my previous patch for invariant-load regresses some cases, so I'm pushing this without waiting for review. This is why you don't make last minute tweaks to patches to catch "obvious cases" after it's already been reviewed. Bad Philip! llvm-svn: 327655
* [EarlyCSE] Reuse invariant scopes for invariant loadPhilip Reames2018-03-151-10/+13
| | | | | | | | | | This is a follow up to https://reviews.llvm.org/D43716 which rewrites the invariant load handling using the new infrastructure. It's slightly more powerful, but only in somewhat minor ways for the moment. It's not clear that DSE of stores to invariant locations is actually interesting since why would your IR have such a construct to start with? Note: The submitted version is slightly different than the reviewed one. I realized the scope could start for an invariant load which was proven redundant and removed. Added a test case to illustrate that as well. Differential Revision: https://reviews.llvm.org/D44497 llvm-svn: 327646
* [EarlyCSE] Exploit open ended invariant.start scopesPhilip Reames2018-03-141-19/+75
| | | | | | | | | | | | If we have an invariant.start with no corresponding invariant.end, then the memory location becomes invariant indefinitely after the invariant.start. As a result, anything dominated by the start is guaranteed to see the value the memory location had when the invariant.start executed. This patch adds an AvailableInvariants table which tracks the generation a particular memory location became invariant and then uses that information to allow value forwarding that would otherwise be disallowed by potentially aliasing stores. (Reminder: In EarlyCSE everything clobbers everything by default.) This should be compatible with the MemorySSA variant, but design is generational. We can and should add first class support for invariant.start within MemorySSA at a later time. I took a quick look at doing so, but probably need some input from a MemorySSA expert. Differential Revision: https://reviews.llvm.org/D43716 llvm-svn: 327577
* [NFC] Consolidate six getPointerOperand() utility functions into one placeRenato Golin2018-03-091-6/+1
| | | | | | | | | | | | | | | | | There are six separate instances of getPointerOperand() utility. LoopVectorize.cpp has one of them, and I don't want to create a 7th one while I'm trying to move LoopVectorizationLegality into a separate file (eventual objective is to move it to Analysis tree). See http://lists.llvm.org/pipermail/llvm-dev/2018-February/120999.html for llvm-dev discussions Closes D43323. Patch by Hideki Saito <hideki.saito@intel.com>. llvm-svn: 327173
* [EarlyCSE] Salvage debug info during DCEPetar Jovanovic2018-01-091-0/+1
| | | | | | | | | | | EarlyCSE did not try to salvage debug info during erasing of instructions. This change fixes it. Patch by Djordje Todorovic. Differential Revision: https://reviews.llvm.org/D41496 llvm-svn: 322083
* [EarlyCSE] recognize swapped variants of abs/nabs as equivalentSanjay Patel2017-12-131-9/+12
| | | | | | | | Extends https://reviews.llvm.org/rL320640 Differential Revision: https://reviews.llvm.org/D41136 llvm-svn: 320653
* [EarlyCSE] recognize commuted and swapped variants of min/max as equivalent ↵Sanjay Patel2017-12-131-0/+27
| | | | | | | | | | | | | (PR35642) As shown in: https://bugs.llvm.org/show_bug.cgi?id=35642 ...we can have different forms of min/max, so we should recognize those here in EarlyCSE similar to how we already handle binops and compares that can commute. Differential Revision: https://reviews.llvm.org/D41136 llvm-svn: 320640
* Add an @llvm.sideeffect intrinsicDan Gohman2017-11-081-0/+6
| | | | | | | | | | | | | | | | | | | | | | | | | | This patch implements Chandler's idea [0] for supporting languages that require support for infinite loops with side effects, such as Rust, providing part of a solution to bug 965 [1]. Specifically, it adds an `llvm.sideeffect()` intrinsic, which has no actual effect, but which appears to optimization passes to have obscure side effects, such that they don't optimize away loops containing it. It also teaches several optimization passes to ignore this intrinsic, so that it doesn't significantly impact optimization in most cases. As discussed on llvm-dev [2], this patch is the first of two major parts. The second part, to change LLVM's semantics to have defined behavior on infinite loops by default, with a function attribute for opting into potential-undefined-behavior, will be implemented and posted for review in a separate patch. [0] http://lists.llvm.org/pipermail/llvm-dev/2015-July/088103.html [1] https://bugs.llvm.org/show_bug.cgi?id=965 [2] http://lists.llvm.org/pipermail/llvm-dev/2017-October/118632.html Differential Revision: https://reviews.llvm.org/D38336 llvm-svn: 317729
* [Transforms] Fix some Clang-tidy modernize and Include What You Use ↵Eugene Zelenko2017-10-131-42/+90
| | | | | | warnings; other minor fixes (NFC). llvm-svn: 315760
* [EarlyCSE] Handle calls with no MemorySSA info.Geoff Berry2017-07-141-1/+15
| | | | | | | | | | | | | | | | | | Summary: When checking for memory dependencies between calls using MemorySSA, handle cases where the calls have no MemoryAccess associated with them because the AA analysis being used has determined that the call does not read/write memory. Fixes PR33756 Reviewers: dberlin, davide Subscribers: mcrosier, llvm-commits, Prazek Differential Revision: https://reviews.llvm.org/D35317 llvm-svn: 308051
* [Constants] If we already have a ConstantInt*, prefer to use ↵Craig Topper2017-07-061-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
* [EarlyCSE] Make PhiToCheck in removeMSSA() a set.Davide Italiano2017-06-141-2/+3
| | | | | | | | | | | This way we end up not looking at PHI args already removed. MemSSA now goes through the updater so we can prune it to avoid having redundant MemoryPHI arguments, but that doesn't quite work for the general case. Discussed with Daniel Berlin, fixes PR33406. llvm-svn: 305409
* [Statistics] Use Statistic::operator+= instead of adding and assigning ↵Craig Topper2017-05-171-1/+1
| | | | | | | | separately. I believe this technically fixes a multithreaded race condition in this code. But my primary concern was as part of looking at removing the ability to treat Statistics like a plain unsigned. There are many weird operations on Statistics in the codebase. llvm-svn: 303314
* Kill off the old SimplifyInstruction API by converting remaining users.Daniel Berlin2017-04-281-8/+8
| | | | llvm-svn: 301673
* [EarlyCSE] Mark the condition of assume intrinsic as trueMax Kazantsev2017-04-281-3/+9
| | | | | | | | | | | | | | EarlyCSE should not just ignore assumes. It should use the fact that its condition is true for all dominated instructions. Reviewers: sanjoy, reames, apilipenko, anna, skatkov Reviewed By: reames, sanjoy Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D32482 llvm-svn: 301625
* [EarlyCSE] Remove guards with conditions known to be trueMax Kazantsev2017-04-281-3/+18
| | | | | | | | | | | | | | | | | If a condition is calculated only once, and there are multiple guards on this condition, we should be able to remove all guards dominated by the first of them. This patch allows EarlyCSE to try to find the condition of a guard among the known values, and if it is true, remove the guard. Otherwise we keep the guard and mark its condition as 'true' for future consideration. Reviewers: sanjoy, reames, apilipenko, skatkov, anna, dberlin Reviewed By: reames, sanjoy Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D32476 llvm-svn: 301623
* MemorySSA: Move to Analysis, from Transforms/Utils. It's used asDaniel Berlin2017-04-111-2/+2
| | | | | | | | Analysis, it has Analysis passes, and once NewGVN is made an Analysis, this removes the cross dependency from Analysis to Transform/Utils. NFC. llvm-svn: 299980
* TTI: Split IsSimple in MemIntrinsicInfoMatt Arsenault2017-03-241-13/+9
| | | | | | All this did before was assert in EarlyCSE. llvm-svn: 298724
* [EarlyCSE] reduce indent; NFCISanjay Patel2017-03-151-21/+22
| | | | llvm-svn: 297886
* Move updating functions to MemorySSAUpdater.Daniel Berlin2017-02-221-2/+6
| | | | | | | | | | | | | | | Add updater to passes that now need it. Move around code in MemorySSA to expose needed functions. Summary: Mostly cleanup Reviewers: george.burgess.iv Subscribers: llvm-commits, Prazek Differential Revision: https://reviews.llvm.org/D30221 llvm-svn: 295887
* [EarlyCSE] Don't DSE across readnone functions that may throwSanjoy Das2017-01-171-6/+7
| | | | | | | | | | | | Summary: Depends on D28740 Reviewers: dberlin, chandlerc, hfinkel, majnemer Subscribers: mcrosier, llvm-commits Differential Revision: https://reviews.llvm.org/D28741 llvm-svn: 292249
* [PM] Introduce an analysis set used to preserve all analyses overChandler Carruth2017-01-151-3/+1
| | | | | | | | | | | | | | | 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
* [EarlyCSE] less else, more auto; NFCSanjay Patel2017-01-031-2/+2
| | | | llvm-svn: 290848
* Revert @llvm.assume with operator bundles (r289755-r289757)Daniel Jasper2016-12-191-5/+12
| | | | | | | This creates non-linear behavior in the inliner (see more details in r289755's commit thread). llvm-svn: 290086
* Remove the AssumptionCacheHal Finkel2016-12-151-12/+5
| | | | | | | | | After r289755, the AssumptionCache is no longer needed. Variables affected by assumptions are now found by using the new operand-bundle-based scheme. This new scheme is more computationally efficient, and also we need much less code... llvm-svn: 289756
* [EarlyCSE] Make MemorySSA memory dependency check more aggressive.Geoff Berry2016-10-251-16/+6
| | | | | | | | | | Now that MemorySSA keeps track of whether MemoryUses are optimized, use getClobberingMemoryAccess() to check MemoryUse memory dependencies since it should no longer be so expensive. This is a follow-up change to https://reviews.llvm.org/D25881 llvm-svn: 285080
OpenPOWER on IntegriCloud