aboutsummaryrefslogtreecommitdiff
path: root/llvm/unittests/IR/ConstantRangeTest.cpp
AgeCommit message (Collapse)AuthorFilesLines
2021-09-09[APInt] Normalize naming on keep constructors / predicate methods.Chris Lattner1-13/+9
This renames the primary methods for creating a zero value to `getZero` instead of `getNullValue` and renames predicates like `isAllOnesValue` to simply `isAllOnes`. This achieves two things: 1) This starts standardizing predicates across the LLVM codebase, following (in this case) ConstantInt. The word "Value" doesn't convey anything of merit, and is missing in some of the other things. 2) Calling an integer "null" doesn't make any sense. The original sin here is mine and I've regretted it for years. This moves us to calling it "zero" instead, which is correct! APInt is widely used and I don't think anyone is keen to take massive source breakage on anything so core, at least not all in one go. As such, this doesn't actually delete any entrypoints, it "soft deprecates" them with a comment. Included in this patch are changes to a bunch of the codebase, but there are more. We should normalize SelectionDAG and other APIs as well, which would make the API change more mechanical. Differential Revision: https://reviews.llvm.org/D109483
2021-07-21[llvm] Add enum iteration to SequenceGuillaume Chatelet1-3/+3
This patch allows iterating typed enum via the ADT/Sequence utility. It also changes the original design to better separate concerns: - `StrongInt` only deals with safe `intmax_t` operations, - `SafeIntIterator` presents the iterator and reverse iterator interface but only deals with safe `StrongInt` internally. - `iota_range` only deals with `SafeIntIterator` internally. This design ensures that operations are always valid. In particular, "Out of bounds" assertions fire when: - the `value_type` is not representable as an `intmax_t` - iterator operations make internal computation underflow/overflow - the internal representation cannot be converted back to `value_type` Differential Revision: https://reviews.llvm.org/D106279
2021-07-13Revert "[llvm] Add enum iteration to Sequence"Guillaume Chatelet1-3/+3
This reverts commit a006af5d6ec6280034ae4249f6d2266d726ccef4.
2021-07-13[llvm] Add enum iteration to SequenceGuillaume Chatelet1-3/+3
This patch allows iterating typed enum via the ADT/Sequence utility. Differential Revision: https://reviews.llvm.org/D103900
2021-04-10[NFC][ConstantRange] Add 'icmp' helper methodRoman Lebedev1-1/+48
"Does the predicate hold between two ranges?" Not very surprisingly, some places were already doing this check, without explicitly naming the algorithm, cleanup them all.
2021-04-10Revert "[NFC][ConstantRange] Add 'icmp' helper method"Roman Lebedev1-48/+1
This reverts commit 17cf2c94230bc107e7294ef84fad3b47f4cd1b73.
2021-04-10[NFC][ConstantRange] Add 'icmp' helper methodRoman Lebedev1-1/+48
"Does the predicate hold between two ranges?" Not very surprisingly, some places were already doing this check, without explicitly naming the algorithm, cleanup them all.
2021-02-20[ConstantRange] Handle wrapping ranges in min/max (PR48643)Nikita Popov1-6/+39
When one of the inputs is a wrapping range, intersect with the union of the two inputs. The union of the two inputs corresponds to the result we would get if we treated the min/max as a simple select. This fixes PR48643.
2021-02-20[ConstantRange] Handle wrapping range in binaryNot()Nikita Popov1-5/+3
We don't need any special handling for wrapping ranges (or empty ranges for that matter). The sub() call will already compute a correct and precise range. We only need to adjust the test expectation: We're now computing an optimal result, rather than an unsigned envelope.
2021-02-20[ConstantRangeTest] Print detailed information on failure (NFC)Nikita Popov1-14/+27
When the optimality check fails, print the inputs, the computed range and the better range that was found. This makes it much simpler to identify the cause of the failure. Make sure that full ranges (which, unlikely all the other cases, have multiple ways to construct them that all result in the same range) only print one message by handling them separately.
2021-02-20[ConstantRangeTest] Make exhaustive testing more principled (NFC)Nikita Popov1-230/+209
The current infrastructure for exhaustive ConstantRange testing is somewhat confusing in what exactly it tests and currently cannot even be used for operations that produce smallest-size results, rather than signed/unsigned envelopes. This patch makes the testing more principled by collecting the exact set of results of an operation into a bit set and then comparing it against the range approximation by: * Checking conservative correctness: All elements in the set must be in the range. * Checking optimality under a given preference function: None of the (slack-free) ranges that can be constructed from the set are preferred over the computed range. Implemented preference functions are: * PreferSmallest: Smallest range regardless of signed/unsigned wrapping behavior. Probably what we would call "optimal" without further qualification. * PreferSmallestUnsigned/Signed: Smallest range that has no unsigned/signed wrapping. We use this if our calculation is precise only up to signed/unsigned envelope. * PreferSmallestNonFullUnsigned/Signed: Smallest range that has no unsigned/signed wrapping -- but preferring a smaller wrapping range over a (non-wrapping) full range. We use this if we have a fully precise calculation but apply a sign preference to the result (union/intersection). Even with a sign preference, returning a wrapping range is still "strictly better" than returning a full one. This also addresses PR49273 by replacing the fragile manual range construction logic in testBinarySetOperationExhaustive() with generic code that isn't specialized to the particular form of ranges that set operations can produces. Differential Revision: https://reviews.llvm.org/D88356
2020-11-04Fix gcc braces warning. NFCI.Simon Pilgrim1-1/+2
gcc warns that the EXPECT_TRUE macro isn't surrounded by if() {} - we already do this in other cases in the file.
2020-09-24Revert "[NFCI][IR] ConstantRangeTest: add basic scaffolding for next-gen ↵Reid Kleckner1-88/+2
precision/correctness testing" This reverts commit 9bcf7b1c7a139a455400df109d81c638b9e75150. Breaks build with MSVC.
2020-09-25[NFCI][IR] ConstantRangeTest: add basic scaffolding for next-gen ↵Roman Lebedev1-2/+88
precision/correctness testing I have long complained that while we have exhaustive tests for ConstantRange, they are, uh, not good. The approach of groking our own constant range via exhaustive enumeration is, mysterious. It neither tells us without doubt that the result is conservatively correct, nor the precise match to the ConstantRange result tells us that the result is precise. But yeah, it's fast, i give it that. In short, there are three things that we need to check: 1. That ConstantRange result is conservatively correct 2. That ConstantRange range is reasonable 3. That ConstantRange result is reasonably precise So let's not just check the middle one, but all three. This provides precision test coverage for D88178.
2020-09-25[NFCI][IR] ConstantRangeTest: refactor operation range gatherersRoman Lebedev1-140/+137
We do the same dance to acquire the "exact" range of an op via an exhaustive approach in many places. Let's not invent the wheel each time.
2020-09-22[ConstantRange] Introduce getMinSignedBits() methodRoman Lebedev1-0/+26
Similar to the ConstantRange::getActiveBits(), and to similarly-named methods in APInt, returns the bitwidth needed to represent the given signed constant range
2020-09-22[ConstantRange] Introduce getActiveBits() methodRoman Lebedev1-0/+27
Much like APInt::getActiveBits(), computes how many bits are needed to be able to represent every value in this constant range, treating the values as unsigned.
2020-09-22[ConstantRange] binaryXor(): special-case binary complement case - the ↵Roman Lebedev1-0/+18
result is precise Use the fact that `~X` is equivalent to `-1 - X`, which gives us fully-precise answer, and we only need to special-handle the wrapped case. This fires ~16k times for vanilla llvm test-suite + RawSpeed.
2020-07-30[ConstantRange] Support abs with poison flagNikita Popov1-23/+39
This just adds the ConstantRange support, including exhaustive testing. It's not wired up to the IR intrinsic flag yet.
2020-03-24[ConstantRange] Add initial support for binaryXor.Florian Hahn1-0/+16
The initial implementation just delegates to APInt's implementation of XOR for single element ranges and conservatively returns the full set otherwise. Reviewers: nikic, spatel, lebedev.ri Reviewed By: nikic Differential Revision: https://reviews.llvm.org/D76453
2019-12-27[ConstantRange] Respect destination bitwidth for cast results.Florian Hahn1-0/+22
We returning a full set, we should use ResultBitWidth. Otherwise we might it assertions when the resulting constant ranges are used later on. Reviewers: nikic, spatel, reames Reviewed By: nikic Differential Revision: https://reviews.llvm.org/D71937
2019-11-08[ConstantRange] Add umul_sat()/smul_sat() methodsRoman Lebedev1-0/+16
Summary: To be used in `ConstantRange::mulWithNoOverflow()`, may in future be useful for when saturating shift/mul ops are added. These are precise as far as i can tell. I initially though i will need `APInt::[us]mul_sat()` for these, but it turned out much simpler to do what `ConstantRange::multiply()` does - perform multiplication in twice the bitwidth, and then truncate. Though here we want saturating signed truncation. Reviewers: nikic, reames, spatel Reviewed By: nikic Subscribers: hiraditya, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D69994
2019-11-08[ConstantRange] Add `ushl_sat()`/`sshl_sat()` methods.Roman Lebedev1-0/+16
Summary: To be used in `ConstantRange::shlWithNoOverflow()`, may in future be useful for when saturating shift/mul ops are added. Unlike `ConstantRange::shl()`, these are precise. Reviewers: nikic, spatel, reames Reviewed By: nikic Subscribers: hiraditya, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D69960
2019-11-07[ConstantRange] Add `subWithNoWrap()` methodRoman Lebedev1-0/+28
Summary: Much like D67339, adds ConstantRange handling for when we know no-wrap behavior of the `sub`. Unlike addWithNoWrap(), we only get lucky re returning empty set for signed wrap. For unsigned, we must perform overflow check manually. A patch that makes use of this in LVI (CVP) to be posted later. Reviewers: nikic, shchenz, efriedma Reviewed By: nikic Subscribers: hiraditya, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D69918
2019-11-07[ConstantRange] TestAddWithNo*WrapExhaustive: check that all overflow means ↵Roman Lebedev1-0/+13
empty set As disscussed in https://reviews.llvm.org/D69918 / https://reviews.llvm.org/D67339 that is an implied postcondition, but it's not really fully tested.
2019-10-20[ConstantRange] makeGuaranteedNoWrapRegion(): `shl` supportRoman Lebedev1-0/+78
Summary: If all the shifts amount are already poison-producing, then we can add more poison-producing flags ontop: https://rise4fun.com/Alive/Ocwi Otherwise, we should only consider the possible range of shift amts that don't result in poison. For unsigned range not not overflow, we must not shift out any set bits, and the actual limit for `x` can be computed by backtransforming the maximal value we could ever get out of the `shl` - `-1` through `lshr`. If the `x` is any larger than that then it will overflow. Likewise for signed range, but just in signed domain.. This is based on the general idea outlined by @nikic in https://reviews.llvm.org/D68672#1714990 Reviewers: nikic, sanjoy Reviewed By: nikic Subscribers: hiraditya, llvm-commits, nikic Tags: #llvm Differential Revision: https://reviews.llvm.org/D69217 llvm-svn: 375370
2019-10-20[ConstantRange] Optimize nowrap region test, remove redundant tests; NFCNikita Popov1-103/+23
Enumerate one less constant range in TestNoWrapRegionExhaustive, which was unnecessary. This allows us to bump the bit count from 3 to 5 while keeping reasonable timing. Drop four tests for multiply nowrap regions, as these cover subsets of the exhaustive test. They do use a wider bitwidth, but I don't think it's worthwhile to have them additionally now. llvm-svn: 375369
2019-10-08[ConstantRange] [NFC] replace addWithNoSignedWrap with addWithNoWrap.Chen Zheng1-26/+0
llvm-svn: 374016
2019-09-30[ConstantRange] add helper function addWithNoWrap().Chen Zheng1-0/+256
Differential Revision: https://reviews.llvm.org/D67339 llvm-svn: 373205
2019-06-03[ConstantRange] Add sdiv() supportNikita Popov1-0/+58
The implementation is conceptually simple: We separate the LHS and RHS into positive and negative components and then also compute the positive and negative components of the result, taking into account that e.g. only pos/pos and neg/neg will give a positive result. However, there's one significant complication: SignedMin / -1 is UB for sdiv, and we can't just ignore it, because the APInt result of SignedMin would break the sign segregation. Instead we drop SignedMin or -1 from the corresponding ranges, taking into account some edge cases with wrapped ranges. Because of the sign segregation, the implementation ends up being nearly fully precise even for wrapped ranges (the remaining imprecision is due to ranges that are both signed and unsigned wrapping and are divided by a trivial divisor like 1). This means that the testing cannot just check the signed envelope as we usually do. Instead we collect all possible results in a bitvector and construct a better sign wrapped range (than the full envelope). Differential Revision: https://reviews.llvm.org/D61238 llvm-svn: 362430
2019-05-28[ValueTracking][ConstantRange] Distinguish low/high always overflowNikita Popov1-22/+43
In order to fold an always overflowing signed saturating add/sub, we need to know in which direction the always overflow occurs. This patch splits up AlwaysOverflows into AlwaysOverflowsLow and AlwaysOverflowsHigh to pass through this information (but it is not used yet). Differential Revision: https://reviews.llvm.org/D62463 llvm-svn: 361858
2019-05-06[ConstantRange] Add srem() supportNikita Popov1-8/+91
Add support for srem() to ConstantRange so we can use it in LVI. For srem the sign of the result matches the sign of the LHS. For the RHS only the absolute value is important. Apart from that the logic is like urem. Just like for urem this is only an approximate implementation. The tests check a few specific cases and run an exhaustive test for conservative correctness (but not exactness). Differential Revision: https://reviews.llvm.org/D61207 llvm-svn: 360055
2019-05-06Fix compilation warnings when compiling with GCC 7.3Alexandre Ganea1-0/+1
Differential Revision: https://reviews.llvm.org/D61046 llvm-svn: 360044
2019-04-28[ConstantRange] Add makeExactNoWrapRegion()Nikita Popov1-2/+10
I got confused on the terminology, and the change in D60598 was not correct. I was thinking of "exact" in terms of the result being non-approximate. However, the relevant distinction here is whether the result is * Largest range such that: Forall Y in Other: Forall X in Result: X BinOp Y does not wrap. (makeGuaranteedNoWrapRegion) * Smallest range such that: Forall Y in Other: Forall X not in Result: X BinOp Y wraps. (A hypothetical makeAllowedNoWrapRegion) * Both. (makeExactNoWrapRegion) I'm adding a separate makeExactNoWrapRegion method accepting a single APInt (same as makeExactICmpRegion) and using it in the places where the guarantee is relevant. Differential Revision: https://reviews.llvm.org/D60960 llvm-svn: 359402
2019-04-26[ConstantRange] Add abs() supportNikita Popov1-0/+26
Add support for abs() to ConstantRange. This will allow to handle SPF_ABS select flavor in LVI and will also come in handy as a primitive for the srem implementation. The implementation is slightly tricky, because a) abs of signed min is signed min and b) sign-wrapped ranges may have an abs() that is smaller than a full range, so we need to explicitly handle them. Differential Revision: https://reviews.llvm.org/D61084 llvm-svn: 359321
2019-04-25[ConstantRange] [a, b) udiv a full range is [0, umax(b)).Florian Hahn1-0/+10
Reviewers: nikic, spatel, efriedma Reviewed By: nikic Differential Revision: https://reviews.llvm.org/D60536 llvm-svn: 359180
2019-04-23[ConstantRange] Add urem supportNikita Popov1-8/+54
Add urem support to ConstantRange, so we can handle in in LVI. This is an approximate implementation that tries to capture the most useful conditions: If the LHS is always strictly smaller than the RHS, then the urem is a no-op and the result is the same as the LHS range. Otherwise the lower bound is zero and the upper bound is min(LHSMax, RHSMax - 1). Differential Revision: https://reviews.llvm.org/D60952 llvm-svn: 359019
2019-04-23[ConstantRangeTest] Move helper methods; NFCNikita Popov1-54/+54
Move Test(Unsigned|Signed)BinOpExhaustive() towards the top of the file, so they're easier to reuse. llvm-svn: 359018
2019-04-22Revert "[ConstantRange] Rename make{Guaranteed -> Exact}NoWrapRegion() NFC"Nikita Popov1-40/+40
This reverts commit 7bf4d7c07f2fac862ef34c82ad0fef6513452445. After thinking about this more, this isn't right, the range is not exact in the same sense as makeExactICmpRegion(). This needs a separate function. llvm-svn: 358876
2019-04-22[ConstantRange] Rename make{Guaranteed -> Exact}NoWrapRegion() NFCNikita Popov1-40/+40
Following D60632 makeGuaranteedNoWrapRegion() always returns an exact nowrap region. Rename the function accordingly. This is in line with the naming of makeExactICmpRegion(). llvm-svn: 358875
2019-04-21[ConstantRange] Add saturating add/sub methodsNikita Popov1-0/+94
Add support for uadd_sat and friends to ConstantRange, so we can handle uadd.sat and friends in LVI. The implementation is forwarding to the corresponding APInt methods with appropriate bounds. One thing worth pointing out here is that the handling of wrapping ranges is not maximally accurate. A simple example is that adding 0 to a wrapped range will return a full range, rather than the original wrapped range. The tests also only check that the non-wrapping envelope is correct and minimal. Differential Revision: https://reviews.llvm.org/D60946 llvm-svn: 358855
2019-04-14[ConstantRange] Simplify unittests after getSetSize was removedFangrui Song1-28/+9
Reviewers: lebedev.ri, nikic Reviewed By: nikic Subscribers: llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D60662 llvm-svn: 358354
2019-04-14[ConstantRange] Fix unittest after rL358347Fangrui Song1-63/+60
llvm-svn: 358348
2019-04-13[ConstantRange] Disallow NUW | NSW in makeGuaranteedNoWrapRegion()Nikita Popov1-106/+0
As motivated in D60598, this drops support for specifying both NUW and NSW in makeGuaranteedNoWrapRegion(). None of the users of this function currently make use of this. When both NUW and NSW are specified, the exact nowrap region has two disjoint parts and makeGNWR() returns one of them. This result doesn't seem to be useful for anything, but makes the semantics of the function fuzzier. Differential Revision: https://reviews.llvm.org/D60632 llvm-svn: 358340
2019-04-12[ConstantRange] Clarify makeGuaranteedNoWrapRegion() guarantees; NFCNikita Popov1-0/+70
makeGuaranteedNoWrapRegion() is actually makeExactNoWrapRegion() as long as only one of NUW or NSW is specified. This is not obvious from the current documentation, and some code seems to think that it is only exact for single-element ranges. Clarify docs and add tests to be more confident this really holds. There are currently no users of makeGuaranteedNoWrapRegion() that pass both NUW and NSW. I think it would be best to drop support for this entirely and then rename the function to makeExactNoWrapRegion(). Knowing that the no-wrap region is exact is useful, because we can backwards-constrain values. What I have in mind in particular is that LVI should be able to constrain values on edges where the with.overflow overflow flag is false. Differential Revision: https://reviews.llvm.org/D60598 llvm-svn: 358305
2019-04-11[ConstantRange] Add unsignedMulMayOverflow()Nikita Popov1-0/+12
Same as the other ConstantRange overflow checking methods, but for unsigned mul. In this case there is no cheap overflow criterion, so using umul_ov for the implementation. Differential Revision: https://reviews.llvm.org/D60574 llvm-svn: 358228
2019-04-11[ConstantRangeTest] Fix typos in test names; NFCNikita Popov1-4/+4
llvm-svn: 358227
2019-04-07[ConstantRange] Add signed/unsigned unionWith()Nikita Popov1-0/+11
This extends D59959 to unionWith(), allowing to specify that a non-wrapping unsigned/signed range is preferred. This is somewhat less useful than the intersect case, because union operations are rarer. An example use would the the phi union computed in SCEV. The implementation is mostly a straightforward use of getPreferredRange(), but I also had to adjust some <=/< checks to make sure that no ranges with lower==upper get constructed before they're passed to getPreferredRange(), as these have additional constraints. Differential Revision: https://reviews.llvm.org/D60377 llvm-svn: 357876
2019-04-07[ConstantRangeTest] Generalize intersection testing code; NFCNikita Popov1-8/+17
Extract the exhaustive intersection tests into a separate function, so that it may be reused for unions as well. llvm-svn: 357874
2019-04-07[ConstantRange] Add unsigned and signed intersection typesNikita Popov1-8/+47
The intersection of two ConstantRanges may consist of two disjoint ranges. As we can only return one range as the result, we need to return one of the two possible ranges that cover both. Currently the result is picked based on set size. However, this is not always optimal: If we're in an unsigned context, we'd prefer to get a large unsigned range over a small signed range -- the latter effectively becomes a full set in the unsigned domain. This revision adds a PreferredRangeType, which can be either Smallest, Unsigned or Signed. Smallest is the current behavior and Unsigned and Signed are new variants that prefer not to wrap the unsigned/signed domain. The new type isn't used anywhere yet (but SCEV will be a good first user, see D60035). I've also added some comments to illustrate the various cases in intersectWith(), which should hopefully make it more obvious what is going on. Differential Revision: https://reviews.llvm.org/D59959 llvm-svn: 357873
generated by cgit v1.1 at 2025-09-29 21:08:54 +0000