summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp
Commit message (Collapse)AuthorAgeFilesLines
* 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
* [LoopIdiomRecognize] Add CTTZ supportCraig Topper2018-12-261-64/+85
| | | | | | | | | | | | | | | | | | | | | Summary: Existing LIR recognizes CTLZ where shifting input variable right until it is zero. (Shift-Until-Zero idiom) This commit: 1. Augments Shift-Until-Zero idiom to recognize CTTZ where input variable is shifted left. 2. Prepare for BitScan idiom recognition. Patch by Yuanfang Chen (tabloid.adroit) Reviewers: craig.topper, evstupac Reviewed By: craig.topper Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D55876 llvm-svn: 350074
* [LoopIdioms] More LocationSize::precise annotations; NFCGeorge Burgess IV2018-12-241-2/+3
| | | | | | | | | Both of these places reference memset-like loops. Memset is precise. Trying to keep these patches super small so they're easily post-commit verifiable, as requested in D44748. llvm-svn: 350044
* [InstCombine] Cleanup libfunc attribute inferringDavid Bolvansky2018-10-161-2/+3
| | | | | | | | | | | | Reviewers: efriedma Reviewed By: efriedma Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D53338 llvm-svn: 344645
* [NFC] Make LoopSafetyInfo abstract to allow alternative implementationsMax Kazantsev2018-10-161-1/+1
| | | | llvm-svn: 344592
* [InstCombine] Fixed crash with aliased functionsDavid Bolvansky2018-10-131-1/+1
| | | | | | | | | | | | | | Summary: Fixes PR39177 Reviewers: spatel, jbuening Reviewed By: jbuening Subscribers: jbuening, llvm-commits Differential Revision: https://reviews.llvm.org/D53129 llvm-svn: 344454
* Merge clang's isRepeatedBytePattern with LLVM's isBytewiseValueJF Bastien2018-09-211-0/+7
| | | | | | | | | | | | | Summary: his code was in CGDecl.cpp and really belongs in LLVM's isBytewiseValue. Teach isBytewiseValue the tricks clang's isRepeatedBytePattern had, including merging undef properly, and recursing on more types. clang part of this patch: D51752 Subscribers: dexonsmith, llvm-commits Differential Revision: https://reviews.llvm.org/D51751 llvm-svn: 342709
* NFC: remove magic bool in LoopIdiomRecognizeJF Bastien2018-09-071-9/+9
| | | | | | Use an enum class instead. llvm-svn: 341684
* [NFC] Refactoring of LoopSafetyInfo, step 1Max Kazantsev2018-08-151-2/+2
| | | | | | | | | 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-1/+1
| | | | | | sed -Ei 's/[[:space:]]+$//' include/**/*.{def,h,td} lib/**/*.{cpp,h} llvm-svn: 338293
* [LoopIdiomRecognize] Don't convert a do while loop to ctlz.Craig Topper2018-07-111-10/+15
| | | | | | | | | | | | | | | | | | | This commit suppresses turning loops like this into "(bitwidth - ctlz(input))". unsigned foo(unsigned input) { unsigned num = 0; do { ++num; input >>= 1; } while (input != 0); return num; } The loop version returns a value of 1 for both an input of 0 and an input of 1. Converting to a naive ctlz does not preserve that. Theoretically we could do better if we checked isKnownNonZero or we could insert a select to handle the divergence. But until we have motivating cases for that, this is the easiest solution. llvm-svn: 336864
* [LoopIdiomRecognize] Support for converting loops that use LSHR to CTLZ.Craig Topper2018-07-081-13/+21
| | | | | | | | | | | | | | | | | | | | | In the 'detectCTLZIdiom' function support for loops that use LSHR instruction instead of ASHR has been added. This supports creating ctlz from the following code. int lzcnt(int x) { int count = 0; while (x > 0) { count++; x = x >> 1; } return count; } Patch by Olga Moldovanova Differential Revision: https://reviews.llvm.org/D48354 llvm-svn: 336509
* [LoopIdiomRecognize] Fix a couple places where it appears we were ↵Craig Topper2018-06-251-6/+5
| | | | | | unintenionally making copies of DebugLoc. llvm-svn: 335521
* [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
* [LoopIdiomRecognize] Only convert loops to ctlz if we can prove that the ↵Craig Topper2018-05-311-0/+8
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | input is non-negative. Summary: Loop idiom recognize tries to convert loops like ``` int foo(int x) { int cnt = 0; while (x) { x >>= 1; ++cnt; } return cnt; } ``` into calls to ctlz, but if x is initially negative this loop should be infinite. It happens that the cases that motivated this change have an absolute value of x before the loop. So this patch restricts the transform to cases where we know x is positive. Note: We are relying on the absolute value of INT_MIN to be undefined so we can assume that the result is always positive. Fixes PR37479 Reviewers: spatel, hfinkel, efriedma, javed.absar Reviewed By: efriedma Subscribers: dmgreen, llvm-commits Differential Revision: https://reviews.llvm.org/D47348 llvm-svn: 333702
* Rename DEBUG macro to LLVM_DEBUG.Nicola Zaghen2018-05-141-11/+13
| | | | | | | | | | | | | | | | 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
* [LoopIdiomRecognize] Don't create an IRBuilder just to call getTrue/getFalse.Craig Topper2018-05-041-2/+2
| | | | | | We can call the methods in ConstantInt directly. We just need a context. llvm-svn: 331542
* [LoopIdiomRecognize] Replace more unchecked dyn_casts with cast.Craig Topper2018-05-041-4/+4
| | | | | | Two of these are immediately dereferenced on the next line. The other two are passed immediately to the IRBuilder constructor which can't handle a nullptr. llvm-svn: 331500
* [LoopIdiomRecognize] Use a regular array instead of a SmallVector and ↵Craig Topper2018-05-041-2/+1
| | | | | | explicit ArrayRef. llvm-svn: 331499
* [LoopIdiomRecognize] Turn two uncheck dyn_casts into regular casts.Craig Topper2018-05-041-2/+2
| | | | | | These are casts on users of a PHINode to Instruction. I think since PHINode is an Instruction any users would also be Instructions. At least a cast will give us an assertion if its wrong. llvm-svn: 331498
* [LoopIdiomRecognize] When looking for 'x & (x -1)' for popcnt, make sure the ↵Craig Topper2018-05-031-1/+1
| | | | | | left hand side of the 'and' matches the left hand side of the 'subtract' llvm-svn: 331437
* [LoopIdiomRecognize] Remove unnecessary cast from BinaryOperator to ↵Craig Topper2018-05-031-4/+3
| | | | | | | | Instruction. NFC BinaryOperator is a sub class of Instruction. We don't need an explicit cast back to Instruction. llvm-svn: 331432
* [LIR] Reorder header. NFCXin Tong2018-04-081-1/+1
| | | | llvm-svn: 329530
* 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
* [LoopIdiom] Be more aggressive when setting alignment in memcpyDaniel Neilson2018-02-081-4/+5
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: This change is part of step five in the series of changes to remove alignment argument from memcpy/memmove/memset in favour of alignment attributes. In particular, this changes the LoopIdiom pass to cease using the old IRBuilder CreateMemCpy single-alignment APIs in favour of the new API that allows setting source and destination alignments independently. This allows us to be slightly more aggressive in setting the alignment of memcpy calls that loop idiom creates. Steps: Step 1) Remove alignment parameter and create alignment parameter attributes for memcpy/memmove/memset. ( rL322965, rC322964, rL322963 ) Step 2) Expand the IRBuilder API to allow creation of memcpy/memmove with differing source and dest alignments. ( rL323597 ) Step 3) Update Clang to use the new IRBuilder API. ( rC323617 ) Step 4) Update Polly to use the new IRBuilder API. ( rL323618 ) Step 5) Update LLVM passes that create memcpy/memmove calls to use the new IRBuilder API, and those that use use MemIntrinsicInst::[get|set]Alignment() to use [get|set]DestAlignment() and [get|set]SourceAlignment() instead. ( rL323886, rL323891, rL324148, rL324273, rL324278, rL324384, rL324395, rL324402 ) Step 6) Remove the single-alignment IRBuilder API for memcpy/memmove, and the MemIntrinsicInst::[get|set]Alignment() methods. Reference http://lists.llvm.org/pipermail/llvm-dev/2015-August/089384.html http://lists.llvm.org/pipermail/llvm-commits/Week-of-Mon-20151109/312083.html llvm-svn: 324626
* [NFC] fix trivial typos in comments and documentsHiroshi Inoue2018-01-291-1/+1
| | | | | | "to to" -> "to" llvm-svn: 323628
* [ModRefInfo] Make enum ModRefInfo an enum class [NFC].Alina Sbirlea2017-12-071-5/+5
| | | | | | | | | | | | | | | Summary: Make enum ModRefInfo an enum class. Changes to ModRefInfo values should be done using inline wrappers. This should prevent future bit-wise opearations from being added, which can be more error-prone. Reviewers: sanjoy, dberlin, hfinkel, george.burgess.iv Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D40933 llvm-svn: 320107
* [ModRefInfo] Do not use ModRefInfo result in if conditions as this makesAlina Sbirlea2017-12-061-1/+2
| | | | | | | assumptions about the values in the enum. Replace with wrapper returning bool [NFC]. llvm-svn: 319949
* Modify ModRefInfo values using static inline method abstractions [NFC].Alina Sbirlea2017-12-051-1/+1
| | | | | | | | | | | | | | | | | Summary: The aim is to make ModRefInfo checks and changes more intuitive and less error prone using inline methods that abstract the bit operations. Ideally ModRefInfo would become an enum class, but that change will require a wider set of changes into FunctionModRefBehavior. Reviewers: sanjoy, george.burgess.iv, dberlin, hfinkel Subscribers: nlopes, llvm-commits Differential Revision: https://reviews.llvm.org/D40749 llvm-svn: 319821
* Use getStoreSize() in various places instead of 'BitSize >> 3'.Jonas Paulsson2017-11-281-11/+4
| | | | | | | | | | | | | | | | | | This is needed for cases when the memory access is not as big as the width of the data type. For instance, storing i1 (1 bit) would be done in a byte (8 bits). Using 'BitSize >> 3' (or '/ 8') would e.g. give the memory access of an i1 a size of 0, which for instance makes alias analysis return NoAlias even when it shouldn't. There are no tests as this was done as a follow-up to the bugfix for the case where this was discovered (r318824). This handles more similar cases. Review: Björn Petterson https://reviews.llvm.org/D40339 llvm-svn: 319173
* Expand IRBuilder interface for atomic memcpy to require pointer alignments. ↵Daniel Neilson2017-11-101-9/+5
| | | | | | | | | | | | | | | (NFC) Summary: The specification of the @llvm.memcpy.element.unordered.atomic intrinsic requires that the pointer arguments have alignments of at least the element size. The existing IRBuilder interface to create a call to this intrinsic does not allow for providing the alignment of these pointer args. Having an interface that makes it easy to construct invalid intrinsic calls doesn't seem sensible, so this patch simply adds the requirement that one provide the argument alignments when using IRBuilder to create atomic memcpy calls. llvm-svn: 317918
* The patch fixes PR35131Evgeny Stupachenko2017-11-031-3/+3
| | | | | | | | | | | | | Summary: Fix a misprint which led to false CTLZ recognition. Reviewers: craig.topper Differential Revision: https://reviews.llvm.org/D39585 From: Evgeny Stupachenko <evstupac@gmail.com> llvm-svn: 317348
* [Transforms] Fix some Clang-tidy modernize and Include What You Use ↵Eugene Zelenko2017-10-161-15/+49
| | | | | | warnings; other minor fixes (NFC). llvm-svn: 315940
* [LIR] Teach LIR to avoid extending the BE count prior to adding one toChandler Carruth2017-07-251-18/+37
| | | | | | | | | | | | | | | | | | | | | | | | | | it when safe. Very often the BE count is the trip count minus one, and the plus one here should fold with that minus one. But because the BE count might in theory be UINT_MAX or some such, adding one before we extend could in some cases wrap to zero and break when we scale things. This patch checks to see if it would be safe to add one because the specific case that would cause this is guarded for prior to entering the preheader. This should handle essentially all of the common loop idioms coming out of C/C++ code once canonicalized by LLVM. Before this patch, both forms of loop in the added test cases ended up subtracting one from the size, extending it, scaling it up by 8 and then adding 8 back onto it. This is really silly, and it turns out made it all the way into generated code very often, so this is a surprisingly important cleanup to do. Many thanks to Sanjoy for showing me how to do this with SCEV. Differential Revision: https://reviews.llvm.org/D35758 llvm-svn: 308968
* [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
* [Atomics] Rename and change prototype for atomic memcpy intrinsicDaniel Neilson2017-06-161-13/+11
| | | | | | | | | | | | | | | | | | Summary: Background: http://lists.llvm.org/pipermail/llvm-dev/2017-May/112779.html This change is to alter the prototype for the atomic memcpy intrinsic. The prototype itself is being changed to more closely resemble the semantics and parameters of the llvm.memcpy intrinsic -- to ease later combination of the llvm.memcpy and atomic memcpy intrinsics. Furthermore, the name of the atomic memcpy intrinsic is being changed to make it clear that it is not a generic atomic memcpy, but specifically a memcpy is unordered atomic. Reviewers: reames, sanjoy, efriedma Reviewed By: reames Subscribers: mzolotukhin, anna, llvm-commits, skatkov Differential Revision: https://reviews.llvm.org/D33240 llvm-svn: 305558
* [Atomics][LoopIdiom] Recognize unordered atomic memcpyAnna Thomas2017-06-061-15/+62
| | | | | | | | | | | | | | | | | | | | | | Summary: Expanding the loop idiom test for memcpy to also recognize unordered atomic memcpy. The only difference for recognizing an unordered atomic memcpy and instead of a normal memcpy is that the loads and/or stores involved are unordered atomic operations. Background: http://lists.llvm.org/pipermail/llvm-dev/2017-May/112779.html Patch by Daniel Neilson! Reviewers: reames, anna, skatkov Reviewed By: reames, anna Subscribers: llvm-commits, mzolotukhin Differential Revision: https://reviews.llvm.org/D33243 llvm-svn: 304806
* Revert "[Atomics][LoopIdiom] Recognize unordered atomic memcpy"Anna Thomas2017-05-311-65/+15
| | | | | | | | | | This reverts commit r304310. It caused build failures in polly and mingw due to undefined reference to llvm::RTLIB::getMEMCPY_ELEMENT_ATOMIC. llvm-svn: 304315
* [Atomics][LoopIdiom] Recognize unordered atomic memcpyAnna Thomas2017-05-311-15/+65
| | | | | | | | | | | | | | | | | | | | | Summary: Expanding the loop idiom test for memcpy to also recognize unordered atomic memcpy. The only difference for recognizing an unordered atomic memcpy and instead of a normal memcpy is that the loads and/or stores involved are unordered atomic operations. Background: http://lists.llvm.org/pipermail/llvm-dev/2017-May/112779.html Patch by Daniel Neilson! Reviewers: reames, anna, skatkov Reviewed By: reames Subscribers: llvm-commits, mzolotukhin Differential Revision: https://reviews.llvm.org/D33243 llvm-svn: 304310
* [LIR] Use the newly `getRecurrenceVar()` helper. NFCI.Davide Italiano2017-05-231-4/+4
| | | | llvm-svn: 303704
* [LIR] Strengthen the check for recurrence variable in popcnt/CTLZ.Davide Italiano2017-05-231-9/+16
| | | | | | | Fixes PR33114. Differential Revision: https://reviews.llvm.org/D33420 llvm-svn: 303700
* [NFC][loopIdiom] Clang format change rL303434Anna Thomas2017-05-191-3/+5
| | | | llvm-svn: 303439
* [LoopIdiom] Refactor return value of isLegalStore [NFC]Anna Thomas2017-05-191-31/+38
| | | | | | | | | | | | | | | | | | | | | | | Summary: This NFC simply refactors the return value of LoopIdiomRecognize::isLegalStore() from bool to an enumeration, and removes the return-through-parameter mechanism that the function was using. This function is constructed such that it will only ever recognize a single store idiom (memset, memset_pattern, or memcpy), and never a combination of these. As such it makes much more sense for the return value to be the single idiom that the store matches, rather than having a separate argument-return for each idiom -- it's cleaner, and makes it clearer that only a single idiom can be matched. Patch by Daniel Neilson! Reviewers: anna, sanjoy, davide, haicheng Reviewed By: anna, haicheng Subscribers: haicheng, mzolotukhin, llvm-commits Differential Revision: https://reviews.llvm.org/D33359 llvm-svn: 303434
* The patch exclude a case from zero check skip inEvgeny Stupachenko2017-05-161-7/+9
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | CTLZ idiom recognition (r303102). Summary: The following case: i = 1; if(n) while (n >>= 1) i++; use(i); Was converted to: i = 1; if(n) i += builtin_ctlz(n >> 1, false); use(i); Which is not correct. The patch make it: i = 1; if(n) i += builtin_ctlz(n >> 1, true); use(i); From: Evgeny Stupachenko <evstupac@gmail.com> llvm-svn: 303212
* The patch adds CTLZ idiom recognition.Evgeny Stupachenko2017-05-151-1/+294
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: The following loops should be recognized: i = 0; while (n) { n = n >> 1; i++; body(); } use(i); And replaced with builtin_ctlz(n) if body() is empty or for CPUs that have CTLZ instruction converted to countable: for (j = 0; j < builtin_ctlz(n); j++) { n = n >> 1; i++; body(); } use(builtin_ctlz(n)); Reviewers: rengolin, joerg Differential Revision: http://reviews.llvm.org/D32605 From: Evgeny Stupachenko <evstupac@gmail.com> llvm-svn: 303102
* [LoopIdiom] check for safety while expandingAditya Kumar2017-05-051-0/+10
| | | | | | | | | Loop Idiom recognition was generating memset in a case that would result generating a division operation to an unsafe location. Differential Revision: https://reviews.llvm.org/D32674 llvm-svn: 302238
* Empty Space. NFCXin Tong2017-05-011-1/+1
| | | | llvm-svn: 301878
* Rename WeakVH to WeakTrackingVH; NFCSanjoy Das2017-05-011-1/+1
| | | | | | This relands r301424. llvm-svn: 301812
* Reverts commit r301424, r301425 and r301426Sanjoy Das2017-04-261-1/+1
| | | | | | | | | | | | Commits were: "Use WeakVH instead of WeakTrackingVH in AliasSetTracker's UnkownInsts" "Add a new WeakVH value handle; NFC" "Rename WeakVH to WeakTrackingVH; NFC" The changes assumed pointers are 8 byte aligned on all architectures. llvm-svn: 301429
OpenPOWER on IntegriCloud