summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis/DemandedBits.cpp
Commit message (Collapse)AuthorAgeFilesLines
* Sink all InitializePasses.h includesReid Kleckner2019-11-131-0/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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
* [DemandedBits] Remove some redundancy in the work listFangrui Song2019-03-031-8/+9
| | | | | | | | | InputIsKnownDead check is shared by all operands. Compute it once. For non-integer instructions, use Visited.insert(I).second to replace a find() and an insert(). llvm-svn: 355290
* [DemandedBits] Optimize a find()+insert pattern with try_emplace and ↵Fangrui Song2019-03-031-8/+3
| | | | | | APInt::operator|= llvm-svn: 355284
* 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
* Reapply "[DemandedBits] Use SetVector for Worklist"Nikita Popov2019-01-121-7/+6
| | | | | | | | | | | | | | | | DemandedBits currently uses a simple vector for the worklist, which means that instructions may be inserted multiple times into it. Especially in combination with the deep lattice, this may cause instructions too be recomputed very often. To avoid this, switch to a SetVector. Reapplying with a smaller number of inline elements in the SmallSetVector, to avoid running into the SmallDenseMap issue described in D56455. Differential Revision: https://reviews.llvm.org/D56362 llvm-svn: 350997
* Revert "[DemandedBits] Use SetVector for Worklist"Nikita Popov2019-01-071-6/+7
| | | | | | | | This reverts commit r350547. Seeing assertion failures on clang tests. llvm-svn: 350549
* [DemandedBits] Use SetVector for WorklistNikita Popov2019-01-071-7/+6
| | | | | | | | | | | | DemandedBits currently uses a simple vector for the worklist, which means that instructions may be inserted multiple times into it. Especially in combination with the deep lattice, this may cause instructions too be recomputed very often. To avoid this, switch to a SetVector. Differential Revision: https://reviews.llvm.org/D56362 llvm-svn: 350547
* [BDCE] Remove dead uses of argumentsNikita Popov2019-01-041-41/+47
| | | | | | | | | | | | | | | | | In addition to finding dead uses of instructions, also find dead uses of function arguments, and replace them with zero as well. I'm changing the way the known bits are computed here to remove the coupling between the transfer function and the algorithm. It previously relied on the first op being visited first and computing known bits -- unless the first op is not an instruction, in which case they're computed on the second op. I could have adjusted this to check for "instruction or argument", but I think it's better to avoid the repeated calculation with an explicit flag. Differential Revision: https://reviews.llvm.org/D56247 llvm-svn: 350435
* Reapply "[BDCE][DemandedBits] Detect dead uses of undead instructions"Nikita Popov2019-01-011-2/+36
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This (mostly) fixes https://bugs.llvm.org/show_bug.cgi?id=39771. BDCE currently detects instructions that don't have any demanded bits and replaces their uses with zero. However, if an instruction has multiple uses, then some of the uses may be dead (have no demanded bits) even though the instruction itself is still live. This patch extends DemandedBits/BDCE to detect such uses and replace them with zero. While this will not immediately render any instructions dead, it may lead to simplifications (in the motivating case, by converting a rotate into a simple shift), break dependencies, etc. The implementation tries to strike a balance between analysis power and complexity/memory usage. Originally I wanted to track demanded bits on a per-use level, but ultimately we're only really interested in whether a use is entirely dead or not. I'm using an extra set to track which uses are dead. However, as initially all uses are dead, I'm not storing uses those user is also dead. This case is checked separately instead. The previous attempt to land this lead to miscompiles, because cases where uses were initially dead but were later found to be live during further analysis were not always correctly removed from the DeadUses set. This is fixed now and the added test case demanstrates such an instance. Differential Revision: https://reviews.llvm.org/D55563 llvm-svn: 350188
* Revert "[BDCE][DemandedBits] Detect dead uses of undead instructions"Nikita Popov2018-12-191-41/+6
| | | | | | | This reverts commit r349674. It causes a failure in test-suite enc-3des.execution_time. llvm-svn: 349684
* [BDCE][DemandedBits] Detect dead uses of undead instructionsNikita Popov2018-12-191-6/+41
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This (mostly) fixes https://bugs.llvm.org/show_bug.cgi?id=39771. BDCE currently detects instructions that don't have any demanded bits and replaces their uses with zero. However, if an instruction has multiple uses, then some of the uses may be dead (have no demanded bits) even though the instruction itself is still live. This patch extends DemandedBits/BDCE to detect such uses and replace them with zero. While this will not immediately render any instructions dead, it may lead to simplifications (in the motivating case, by converting a rotate into a simple shift), break dependencies, etc. The implementation tries to strike a balance between analysis power and complexity/memory usage. Originally I wanted to track demanded bits on a per-use level, but ultimately we're only really interested in whether a use is entirely dead or not. I'm using an extra set to track which uses are dead. However, as initially all uses are dead, I'm not storing uses those user is also dead. This case is checked separately instead. The test case has a couple of cases that are not simplified yet. In particular, we're only looking at uses of instructions right now. I think it would make sense to also extend this to arguments. Furthermore DemandedBits doesn't yet know some of the tricks that InstCombine does for the demanded bits or bitwise or/and/xor in combination with known bits information. Differential Revision: https://reviews.llvm.org/D55563 llvm-svn: 349674
* Reapply "[DemandedBits][BDCE] Support vectors of integers"Nikita Popov2018-12-071-21/+44
| | | | | | | | | | | | | | | | | | | | | | DemandedBits and BDCE currently only support scalar integers. This patch extends them to also handle vector integer operations. In this case bits are not tracked for individual vector elements, instead a bit is demanded if it is demanded for any of the elements. This matches the behavior of computeKnownBits in ValueTracking and SimplifyDemandedBits in InstCombine. Unlike the previous iteration of this patch, getDemandedBits() can now again be called on arbirary (sized) instructions, even if they don't have integer or vector of integer type. (For vector types the size of the returned mask will now be the scalar size in bits though.) The added LoopVectorize test case shows a case which triggered an assertion failure with the previous attempt, because getDemandedBits() was called on a pointer-typed instruction. Differential Revision: https://reviews.llvm.org/D55297 llvm-svn: 348602
* Revert "[DemandedBits][BDCE] Support vectors of integers"Nikita Popov2018-12-071-44/+22
| | | | | | | This reverts commit r348549. Causing assertion failures during clang build. llvm-svn: 348558
* [DemandedBits][BDCE] Support vectors of integersNikita Popov2018-12-061-22/+44
| | | | | | | | | | | | | | | | | | | DemandedBits and BDCE currently only support scalar integers. This patch extends them to also handle vector integer operations. In this case bits are not tracked for individual vector elements, instead a bit is demanded if it is demanded for any of the elements. This matches the behavior of computeKnownBits in ValueTracking and SimplifyDemandedBits in InstCombine. The getDemandedBits() method can now only be called on instructions that have integer or vector of integer type. Previously it could be called on any sized instruction (even if it was not particularly useful). The size of the return value is now always the scalar size in bits (while previously it was the type size in bits). Differential Revision: https://reviews.llvm.org/D55297 llvm-svn: 348549
* [DemandedBits] Add support for funnel shiftsNikita Popov2018-11-261-0/+21
| | | | | | | | | | | | | | Add support for funnel shifts to the DemandedBits analysis. The demanded bits of the first two operands can be determined if the shift amount is constant. The demanded bits of the third operand (shift amount) can be determined if the bitwidth is a power of two. This is basically the same functionality as implemented in D54869 and D54478, but for DemandedBits rather than InstCombine. Differential Revision: https://reviews.llvm.org/D54876 llvm-svn: 347561
* [IR] Replace `isa<TerminatorInst>` with `isTerminator()`.Chandler Carruth2018-08-261-2/+2
| | | | | | | | | | | | This is a bit awkward in a handful of places where we didn't even have an instruction and now we have to see if we can build one. But on the whole, this seems like a win and at worst a reasonable cost for removing `TerminatorInst`. All of this is part of the removal of `TerminatorInst` from the `Instruction` type hierarchy. llvm-svn: 340701
* Remove trailing spaceFangrui Song2018-07-301-2/+2
| | | | | | sed -Ei 's/[[:space:]]+$//' include/**/*.{def,h,td} lib/**/*.{cpp,h} llvm-svn: 338293
* Rename DEBUG macro to LLVM_DEBUG.Nicola Zaghen2018-05-141-4/+4
| | | | | | | | | | | | | | | | 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
* Avoid int to string conversion in Twine or raw_ostream contexts.Benjamin Kramer2017-12-281-2/+2
| | | | | | Some output changes from uppercase hex to lowercase hex, no other functionality change intended. llvm-svn: 321526
* [DemandedBits] simplify call; NFCSanjay Patel2017-08-161-1/+1
| | | | llvm-svn: 311009
* [Analysis] Fix some Clang-tidy modernize and Include What You Use warnings; ↵Eugene Zelenko2017-07-211-4/+15
| | | | | | other minor fixes (NFC). llvm-svn: 308787
* [DemandedBits] fix formatting; NFCSanjay Patel2017-07-071-9/+6
| | | | llvm-svn: 307403
* [BDCE] Add comments. NFCXin Tong2017-06-191-0/+2
| | | | llvm-svn: 305739
* [ValueTracking] Remove const_casts on several calls to computeKnownBits and ↵Craig Topper2017-05-131-4/+2
| | | | | | ComputeSignBit. NFC llvm-svn: 302991
* [KnownBits] Add bit counting methods to KnownBits struct and use them where ↵Craig Topper2017-05-121-2/+2
| | | | | | | | | | | | possible This patch adds min/max population count, leading/trailing zero/one bit counting methods. The min methods return answers based on bits that are known without considering unknown bits. The max methods give answers taking into account the largest count that unknown bits could give. Differential Revision: https://reviews.llvm.org/D32931 llvm-svn: 302925
* [APInt] Add clearSignBit method. Use it and setSignBit in a few places. NFCICraig Topper2017-04-281-2/+2
| | | | llvm-svn: 301656
* [ValueTracking] Introduce a KnownBits struct to wrap the two APInts for ↵Craig Topper2017-04-261-17/+14
| | | | | | | | | | | | | | | | 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
* [Analysis] Support bitreverse in -demanded-bits passBrian Gesiak2017-04-131-0/+3
| | | | | | | | | | | | | | | | | | | | Summary: * Add a bitreverse case in the demanded bits analysis pass. * Add tests for the bitreverse (and bswap) intrinsic in the demanded bits pass. * Add a test case to the BDCE tests: that manipulations to high-order bits are eliminated once the bits are reversed and then right-shifted. Reviewers: mkuper, jmolloy, hfinkel, trentxintong Reviewed By: jmolloy Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D31857 llvm-svn: 300215
* Revert @llvm.assume with operator bundles (r289755-r289757)Daniel Jasper2016-12-191-4/+9
| | | | | | | 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-9/+4
| | | | | | | | | 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
* [PM] Change the static object whose address is used to uniquely identifyChandler Carruth2016-11-231-1/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | analyses to have a common type which is enforced rather than using a char object and a `void *` type when used as an identifier. This has a number of advantages. First, it at least helps some of the confusion raised in Justin Lebar's code review of why `void *` was being used everywhere by having a stronger type that connects to documentation about this. However, perhaps more importantly, it addresses a serious issue where the alignment of these pointer-like identifiers was unknown. This made it hard to use them in pointer-like data structures. We were already dodging this in dangerous ways to create the "all analyses" entry. In a subsequent patch I attempted to use these with TinyPtrVector and things fell apart in a very bad way. And it isn't just a compile time or type system issue. Worse than that, the actual alignment of these pointer-like opaque identifiers wasn't guaranteed to be a useful alignment as they were just characters. This change introduces a type to use as the "key" object whose address forms the opaque identifier. This both forces the objects to have proper alignment, and provides type checking that we get it right everywhere. It also makes the types somewhat less mysterious than `void *`. We could go one step further and introduce a truly opaque pointer-like type to return from the `ID()` static function rather than returning `AnalysisKey *`, but that didn't seem to be a clear win so this is just the initial change to get to a reliably typed and aligned object serving is a key for all the analyses. Thanks to Richard Smith and Justin Lebar for helping pick plausible names and avoid making this refactoring many times. =] And thanks to Sean for the super fast review! While here, I've tried to move away from the "PassID" nomenclature entirely as it wasn't really helping and is overloaded with old pass manager constructs. Now we have IDs for analyses, and key objects whose address can be used as IDs. Where possible and clear I've shortened this to just "ID". In a few places I kept "AnalysisID" to make it clear what was being identified. Differential Revision: https://reviews.llvm.org/D27031 llvm-svn: 287783
* 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
* [DemandedBits] Reduce number of duplicated DenseMap lookups.Benjamin Kramer2016-07-211-5/+4
| | | | | | No functionality change intended. llvm-svn: 276278
* Port DemandedBits to the new pass manager.Michael Kuperstein2016-04-181-22/+42
| | | | | | Differential Revision: http://reviews.llvm.org/D18679 llvm-svn: 266699
* [NFC] Header cleanupMehdi Amini2016-04-181-1/+0
| | | | | | | | | | | | | | Removed some unused headers, replaced some headers with forward class declarations. Found using simple scripts like this one: clear && ack --cpp -l '#include "llvm/ADT/IndexedMap.h"' | xargs grep -L 'IndexedMap[<]' | xargs grep -n --color=auto 'IndexedMap' Patch by Eugene Kosov <claprix@yandex.ru> Differential Revision: http://reviews.llvm.org/D19219 From: Mehdi Amini <mehdi.amini@apple.com> llvm-svn: 266595
* [DemandedBits] Revert r249687 due to PR26071James Molloy2016-02-031-7/+0
| | | | | | | | | | | | | | This regresses a test in LoopVectorize, so I'll need to go away and think about how to solve this in a way that isn't broken. From the writeup in PR26071: What's happening is that ComputeKnownZeroes is telling us that all bits except the LSB are zero. We're then deciding that only the LSB needs to be demanded from the icmp's inputs. This is where we're wrong - we're assuming that after simplification the bits that were known zero will continue to be known zero. But they're not - during trivialization the upper bits get changed (because an XOR isn't shrunk), so the icmp fails. The fault is in demandedbits - its contract does clearly state that a non-demanded bit may either be zero or one. llvm-svn: 259649
* Make some headers self-contained, remove unused includes that violate layering.Benjamin Kramer2016-01-271-1/+0
| | | | llvm-svn: 258937
* [DemandedBits] Fix computation of demanded bits for ICmpsJames Molloy2016-01-251-1/+1
| | | | | | | | | | The computation of ICmp demanded bits is independent of the individual operand being evaluated. We simply return a mask consisting of the minimum leading zeroes of both operands. We were incorrectly passing "I" to ComputeKnownBits - this should be "UserI->getOperand(0)". In cases where we were evaluating the 1th operand, we were taking the minimum leading zeroes of it and itself. This should fix PR26266. llvm-svn: 258690
* Compute demanded bits for icmp instructionsJames Molloy2015-10-081-0/+7
| | | | | | | | | Instead of bailing out when we see an icmp, we can instead at least say that if the upper bits of both operands are known zero, they are not demanded. This doesn't help with signed comparisons, but it's at least better than bailing out. llvm-svn: 249687
* Treat Mul just like Add and SubtractJames Molloy2015-10-081-0/+12
| | | | | | | | | | Like adds and subtracts, muls ripple only to the left so we can use the same logic. While we're here, add a print method to DemandedBits so it can be used with -analyze, which we'll use in the testcase. llvm-svn: 249686
* Make demanded bits lazyJames Molloy2015-10-081-7/+19
| | | | | | | | | | The algorithm itself is still eager, but it doesn't get run until a query function is called. This greatly reduces the compile-time impact of requiring DemandedBits when at runtime it is not often used. NFCI. llvm-svn: 249685
* Untabify.NAKAMURA Takumi2015-09-221-7/+5
| | | | llvm-svn: 248264
* Reformat comment lines.NAKAMURA Takumi2015-09-221-2/+2
| | | | llvm-svn: 248262
* Reformat.NAKAMURA Takumi2015-09-221-2/+1
| | | | llvm-svn: 248261
* Separate out BDCE's analysis into a separate DemandedBits analysis.James Molloy2015-08-141-0/+364
This allows other areas of the compiler to use BDCE's bit-tracking. NFCI. llvm-svn: 245039
OpenPOWER on IntegriCloud