summaryrefslogtreecommitdiffstats
path: root/llvm/test/Transforms/InstSimplify/compare.ll
Commit message (Collapse)AuthorAgeFilesLines
* [InstSimplify] add nuw %x, C2 must be at least C2David Majnemer2015-08-201-0/+8
| | | | | | | Use the fact that add nuw always creates a larger bit pattern when trying to simplify comparisons. llvm-svn: 245638
* Add a bunch of CHECK missing colons in tests. NFC.Ahmed Bougacha2015-03-141-1/+1
| | | | | | Some wouldn't pass; fixed most, the rest will be fixed separately. llvm-svn: 232239
* [opaque pointer type] Add textual IR support for explicit type parameter to ↵David Blaikie2015-02-271-3/+3
| | | | | | | | | | | | | | | | | | | | | | | | load instruction Essentially the same as the GEP change in r230786. A similar migration script can be used to update test cases, though a few more test case improvements/changes were required this time around: (r229269-r229278) import fileinput import sys import re pat = re.compile(r"((?:=|:|^)\s*load (?:atomic )?(?:volatile )?(.*?))(| addrspace\(\d+\) *)\*($| *(?:%|@|null|undef|blockaddress|getelementptr|addrspacecast|bitcast|inttoptr|\[\[[a-zA-Z]|\{\{).*$)") for line in sys.stdin: sys.stdout.write(re.sub(pat, r"\1, \2\3*\4", line)) Reviewers: rafael, dexonsmith, grosser Differential Revision: http://reviews.llvm.org/D7649 llvm-svn: 230794
* [opaque pointer type] Add textual IR support for explicit type parameter to ↵David Blaikie2015-02-271-46/+46
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | getelementptr instruction One of several parallel first steps to remove the target type of pointers, replacing them with a single opaque pointer type. This adds an explicit type parameter to the gep instruction so that when the first parameter becomes an opaque pointer type, the type to gep through is still available to the instructions. * This doesn't modify gep operators, only instructions (operators will be handled separately) * Textual IR changes only. Bitcode (including upgrade) and changing the in-memory representation will be in separate changes. * geps of vectors are transformed as: getelementptr <4 x float*> %x, ... ->getelementptr float, <4 x float*> %x, ... Then, once the opaque pointer type is introduced, this will ultimately look like: getelementptr float, <4 x ptr> %x with the unambiguous interpretation that it is a vector of pointers to float. * address spaces remain on the pointer, not the type: getelementptr float addrspace(1)* %x ->getelementptr float, float addrspace(1)* %x Then, eventually: getelementptr float, ptr addrspace(1) %x Importantly, the massive amount of test case churn has been automated by same crappy python code. I had to manually update a few test cases that wouldn't fit the script's model (r228970,r229196,r229197,r229198). The python script just massages stdin and writes the result to stdout, I then wrapped that in a shell script to handle replacing files, then using the usual find+xargs to migrate all the files. update.py: import fileinput import sys import re ibrep = re.compile(r"(^.*?[^%\w]getelementptr inbounds )(((?:<\d* x )?)(.*?)(| addrspace\(\d\)) *\*(|>)(?:$| *(?:%|@|null|undef|blockaddress|getelementptr|addrspacecast|bitcast|inttoptr|\[\[[a-zA-Z]|\{\{).*$))") normrep = re.compile( r"(^.*?[^%\w]getelementptr )(((?:<\d* x )?)(.*?)(| addrspace\(\d\)) *\*(|>)(?:$| *(?:%|@|null|undef|blockaddress|getelementptr|addrspacecast|bitcast|inttoptr|\[\[[a-zA-Z]|\{\{).*$))") def conv(match, line): if not match: return line line = match.groups()[0] if len(match.groups()[5]) == 0: line += match.groups()[2] line += match.groups()[3] line += ", " line += match.groups()[1] line += "\n" return line for line in sys.stdin: if line.find("getelementptr ") == line.find("getelementptr inbounds"): if line.find("getelementptr inbounds") != line.find("getelementptr inbounds ("): line = conv(re.match(ibrep, line), line) elif line.find("getelementptr ") != line.find("getelementptr ("): line = conv(re.match(normrep, line), line) sys.stdout.write(line) apply.sh: for name in "$@" do python3 `dirname "$0"`/update.py < "$name" > "$name.tmp" && mv "$name.tmp" "$name" rm -f "$name.tmp" done The actual commands: From llvm/src: find test/ -name *.ll | xargs ./apply.sh From llvm/src/tools/clang: find test/ -name *.mm -o -name *.m -o -name *.cpp -o -name *.c | xargs -I '{}' ../../apply.sh "{}" From llvm/src/tools/polly: find test/ -name *.ll | xargs ./apply.sh After that, check-all (with llvm, clang, clang-tools-extra, lld, compiler-rt, and polly all checked out). The extra 'rm' in the apply.sh script is due to a few files in clang's test suite using interesting unicode stuff that my python script was throwing exceptions on. None of those files needed to be migrated, so it seemed sufficient to ignore those cases. Reviewers: rafael, dexonsmith, grosser Differential Revision: http://reviews.llvm.org/D7636 llvm-svn: 230786
* InstSimplify: Handle some simple tautological comparisonsDavid Majnemer2014-11-251-0/+64
| | | | | | | | This handles cases where we are comparing a masked value against itself. The analysis could be further improved by making it recursive but such expense is not currently justified. llvm-svn: 222716
* Introduce a 'nonnull' metadata on Load instructions.Philip Reames2014-10-201-0/+23
| | | | | | | | | The newly introduced 'nonnull' metadata is analogous to existing 'nonnull' attributes, but applies to load instructions rather than call arguments or returns. Long term, it would be nice to combine these into a single construct. The value of the load is allowed to vary between successive loads, but null is not a valid value to be loaded by any load marked nonnull. Reviewed by: Hal Finkel Differential Revision: http://reviews.llvm.org/D5220 llvm-svn: 220240
* InstSimplify: Move a transform from InstCombine to InstSimplifyDavid Majnemer2014-08-281-2/+70
| | | | | | | | Several combines involving icmp (shl C2, %X) C1 can be simplified without introducing any new instructions. Move them to InstSimplify; while we are at it, make them more powerful. llvm-svn: 216642
* InstSimplify: Compute comparison ranges for left shift instructionsDavid Majnemer2014-08-271-0/+27
| | | | | | | | 'shl nuw CI, x' produces [CI, CI << CLZ(CI)] 'shl nsw CI, x' produces [CI << CLO(CI)-1, CI] if CI is negative 'shl nsw CI, x' produces [CI, CI << CLZ(CI)-1] if CI is non-negative llvm-svn: 216570
* ValueTracking: Figure out more bits when looking at add/subDavid Majnemer2014-08-221-0/+13
| | | | | | | | | Given something like X01XX + X01XX, we know that the result must look like X1XXX. Adapted from a patch by Richard Smith, test-case written by me. llvm-svn: 216250
* Add a dereferenceable attributeHal Finkel2014-07-181-0/+34
| | | | | | | | | This attribute indicates that the parameter or return pointer is dereferenceable. Practically speaking, loads from such a pointer within the associated byte range are safe to speculatively execute. Such pointer parameters are common in source languages (C++ references, for example). llvm-svn: 213385
* Fix a test broken in r212981David Majnemer2014-07-141-1/+1
| | | | | | | @icmp_sdiv_neg1 should have referred to %a instead of %call, it was renamed at the last second. llvm-svn: 212983
* InstSimplify: Correct sdiv x / -1David Majnemer2014-07-141-0/+11
| | | | | | | | | | | Determining the bounds of x/ -1 would start off with us dividing it by INT_MIN. Suffice to say, this would not work very well. Instead, handle it upfront by checking for -1 and mapping it to the range: [INT_MIN + 1, INT_MAX. This means that the result of our division can be any value other than INT_MIN. llvm-svn: 212981
* InstSimplify: The upper bound of X / C was missing a rounding stepDavid Majnemer2014-07-141-0/+11
| | | | | | | | | | | | | | | | | | Summary: When calculating the upper bound of X / -8589934592, we would perform the following calculation: Floor[INT_MAX / 8589934592] However, flooring the result would make us wrongly come to the conclusion that 1073741824 was not in the set of possible values. Instead, use the ceiling of the result. Reviewers: nicholas Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D4502 llvm-svn: 212976
* InstSimplify: Fix a bug when INT_MIN is in a sdivDavid Majnemer2014-07-041-0/+11
| | | | | | | | | | | | | When INT_MIN is the numerator in a sdiv, we would not properly handle overflow when calculating the bounds of possible values; abs(INT_MIN) is not a meaningful number. Instead, check and handle INT_MIN by reasoning that the largest value is INT_MIN/-2 and the smallest value is INT_MIN. This fixes PR20199. llvm-svn: 212307
* Make instsimplify's analysis of icmp eq/ne use computeKnownBits to determine ↵Nick Lewycky2014-06-191-0/+19
| | | | | | whether the icmp is always true or false. Patch by Suyog Sarda! llvm-svn: 211251
* Teach isKnownNonNull that a nonnull return is not null. Add a test for this ↵Nick Lewycky2014-05-201-0/+17
| | | | | | case as well as the case of a nonnull attribute (already handled but not tested). llvm-svn: 209193
* InstSimplify: Improve handling of ashr/lshrDavid Majnemer2014-05-161-0/+40
| | | | | | | | | | | | | | Summary: Analyze the range of values produced by ashr/lshr cst, %V when it is being used in an icmp. Reviewers: nicholas Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D3774 llvm-svn: 209000
* InstSimplify: Optimize using dividend in sdivDavid Majnemer2014-05-161-0/+9
| | | | | | | | | | | | | | | Summary: The dividend in an sdiv tells us the largest and smallest possible results. Use this fact to optimize comparisons against an sdiv with a constant dividend. Reviewers: nicholas Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D3795 llvm-svn: 208999
* InstSimplify: Optimize signed icmp of -(zext V)David Majnemer2014-05-141-0/+60
| | | | | | | | | | | | | | | | Summary: We know that -(zext V) will always be <= zero, simplify signed icmps that have these. Uncovered using http://www.cs.utah.edu/~regehr/souper/ Reviewers: nicholas Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D3754 llvm-svn: 208809
* InstSimplify: Make shift, select and GEP simplifications vector-aware.Benjamin Kramer2014-01-241-0/+18
| | | | llvm-svn: 200016
* Add a test that large offsets on GEPs on 32 bits targets are handled correctly.Benjamin Kramer2013-09-281-0/+10
| | | | llvm-svn: 191628
* Expand test case a bit.Benjamin Kramer2013-09-231-2/+5
| | | | llvm-svn: 191205
* InstSimplify: Fold equality comparisons between non-inbounds GEPs.Benjamin Kramer2013-09-231-0/+9
| | | | | | | | | Overflow doesn't affect the correctness of equalities. Computing this is cheap, we just reuse the computation for the inbounds case and try to peel of more non-inbounds GEPs. This pattern is unlikely to ever appear in code generated by Clang, but SCEV occasionally produces it. llvm-svn: 191200
* Update Transforms tests to use CHECK-LABEL for easier debugging. No ↵Stephen Lin2013-07-141-69/+69
| | | | | | | | | | | | | | | | | | | | | | functionality change. This update was done with the following bash script: find test/Transforms -name "*.ll" | \ while read NAME; do echo "$NAME" if ! grep -q "^; *RUN: *llc" $NAME; then TEMP=`mktemp -t temp` cp $NAME $TEMP sed -n "s/^define [^@]*@\([A-Za-z0-9_]*\)(.*$/\1/p" < $NAME | \ while read FUNC; do sed -i '' "s/;\(.*\)\([A-Za-z0-9_]*\):\( *\)@$FUNC\([( ]*\)\$/;\1\2-LABEL:\3@$FUNC(/g" $TEMP done mv $TEMP $NAME fi done llvm-svn: 186268
* Fix logic error optimizing "icmp pred (urem X, Y), Y" where pred is signed.Nick Lewycky2013-07-121-1/+9
| | | | | | Fixes PR16605. llvm-svn: 186229
* InstSimplify: X >> X -> 0David Majnemer2013-07-091-0/+16
| | | | llvm-svn: 185973
* Check whether a pointer is non-null (isKnownNonNull) in isKnownNonZero.Manman Ren2013-03-181-0/+11
| | | | | | | | This handles the case where we have an inbounds GEP with alloca as the pointer. This fixes the regression in PR12750 and rdar://13286434. Note that we can also fix this by handling some GEP cases in isKnownNonNull. llvm-svn: 177321
* Rewrite instsimplify's handling if icmp on pointer values to remove theDan Gohman2013-02-011-0/+22
| | | | | | | | | | | | remaining use of AliasAnalysis concepts such as isIdentifiedObject to prove pointer inequality. @external_compare in test/Transforms/InstSimplify/compare.ll shows a simple case where a noalias argument can be equal to a global variable address, and while AliasAnalysis can get away with saying that these pointers don't alias, instsimplify cannot say that they are not equal. llvm-svn: 174122
* An alloca can be equal to an argument. It can't *alias* an alloca, but it couldDan Gohman2013-01-311-0/+13
| | | | | | | be equal, since there's nothing preventing a caller from correctly predicting the stack location of an alloca. llvm-svn: 174119
* Add support to ValueTracking for determining that a pointer is non-nullChandler Carruth2012-12-071-0/+40
| | | | | | | | | | | | | | | | | | | | | | | by virtue of inbounds GEPs that preclude a null pointer. This is a very common pattern in the code generated by std::vector and other standard library routines which use allocators that test for null pervasively. This is one step closer to teaching Clang+LLVM to be able to produce an empty function for: void f() { std::vector<int> v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); } Which is related to getting them to completely fold SmallVector push_back sequences into constants when inlining and other optimizations make that a possibility. llvm-svn: 169573
* InstructionSimplify should be able to simplify A+B==B+A to 'true'Duncan Sands2012-11-161-0/+9
| | | | | | but wasn't due to the same logic bug that caused PR14361. llvm-svn: 168186
* Teach instsimplify how to simplify comparisons of pointers which areChandler Carruth2012-03-251-0/+62
| | | | | | | constant-offsets of a common base using the generic GEP-walking logic I added for computing pointer differences in the same situation. llvm-svn: 153419
* Reinstate the optimization from r151449 with a fix to not turn 'gep %x' intoNick Lewycky2012-02-261-0/+63
| | | | | | 'gep null' when the icmp predicate is unsigned (or is signed without inbounds). llvm-svn: 151467
* Roll these back to r151448 until I figure out how they're breakingNick Lewycky2012-02-251-54/+0
| | | | | | MultiSource/Applications/lua. llvm-svn: 151463
* An argument and a local identified object (eg. a noalias call) could turn outNick Lewycky2012-02-251-14/+24
| | | | | | | equal if both are null. In the test, scope type %t and global @y by adding a 'gep' prefix to them. llvm-svn: 151452
* Teach instsimplify to be more aggressive when analyzing comparisons of pointersNick Lewycky2012-02-251-0/+44
| | | | | | | by using llvm::isIdentifiedObject. Also teach it to handle GEPs that have the same base pointer and constant operands. Fixes PR11238! llvm-svn: 151449
* fix PR12075, a regression in a recent transform I added. In unreachable ↵Chris Lattner2012-02-241-0/+10
| | | | | | code, gep chains can be infinite. Just like "stripPointerCasts", use a set to keep track of visited instructions so we don't recurse infinitely. llvm-svn: 151383
* fold comparisons of gep'd alloca points with null to false,Chris Lattner2012-02-201-1/+12
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | implementing PR12013. We now compile the testcase to: __Z4testv: ## @_Z4testv ## BB#0: ## %_ZN4llvm15SmallVectorImplIiE9push_backERKi.exit pushq %rbx subq $64, %rsp leaq 32(%rsp), %rbx movq %rbx, (%rsp) leaq 64(%rsp), %rax movq %rax, 16(%rsp) movl $1, 32(%rsp) leaq 36(%rsp), %rax movq %rax, 8(%rsp) leaq (%rsp), %rdi callq __Z1gRN4llvm11SmallVectorIiLj8EEE movq (%rsp), %rdi cmpq %rbx, %rdi je LBB0_2 ## BB#1: callq _free LBB0_2: ## %_ZN4llvm11SmallVectorIiLj8EED1Ev.exit addq $64, %rsp popq %rbx ret instead of: __Z4testv: ## @_Z4testv ## BB#0: pushq %rbx subq $64, %rsp xorl %eax, %eax leaq (%rsp), %rbx addq $32, %rbx movq %rbx, (%rsp) movq %rbx, 8(%rsp) leaq 64(%rsp), %rcx movq %rcx, 16(%rsp) je LBB0_2 ## BB#1: movl $1, 32(%rsp) movq %rbx, %rax LBB0_2: ## %_ZN4llvm15SmallVectorImplIiE9push_backERKi.exit addq $4, %rax movq %rax, 8(%rsp) leaq (%rsp), %rdi callq __Z1gRN4llvm11SmallVectorIiLj8EEE movq (%rsp), %rdi cmpq %rbx, %rdi je LBB0_4 ## BB#3: callq _free LBB0_4: ## %_ZN4llvm11SmallVectorIiLj8EED1Ev.exit addq $64, %rsp popq %rbx ret This doesn't shrink clang noticably though. llvm-svn: 150944
* Fix a rather nasty regression from r150690: LHS != RHS does not imply ↵Eli Friedman2012-02-181-0/+10
| | | | | | LHS->stripPointerCasts() != RHS->stripPointerCasts(). llvm-svn: 150863
* InstSimplify: Ignore pointer casts when constant folding compares between ↵Benjamin Kramer2012-02-161-0/+20
| | | | | | pointers. llvm-svn: 150690
* Fix PR11948: the result type of an icmp may be a vector of boolean -Duncan Sands2012-02-101-0/+7
| | | | | | don't assume it is a boolean. llvm-svn: 150247
* Revert commit 149912 (lattner) and add a testcase that shows the problem (whichDuncan Sands2012-02-101-0/+9
| | | | | | | | | | is that patterns no longer match for vectors of booleans, because you only get ConstantDataVector when the vector element type is i8, i16, etc, not when it is i1). Original commit message: Remove some dead code and tidy things up now that vectors use ConstantDataVector instead of always using ConstantVector. llvm-svn: 150246
* Fix code to match comment. Fixes PR11340, a regression from r143209.Eli Friedman2011-11-081-0/+10
| | | | llvm-svn: 144121
* Reapply commit 143214 with a fix: m_ICmp doesn't match conditionsDuncan Sands2011-10-301-0/+18
| | | | | | | | | | | | with the given predicate, it matches any condition and returns the predicate - d'oh! Original commit message: The expression icmp eq (select (icmp eq x, 0), 1, x), 0 folds to false. Spotted by my super-optimizer in 186.crafty and 450.soplex. We really need a proper infrastructure for handling generalizations of this kind of thing (which occur a lot), however this case is so simple that I decided to go ahead and implement it directly. llvm-svn: 143318
* Revert r143214; it's breaking a bunch of stuff.Eli Friedman2011-10-291-9/+0
| | | | llvm-svn: 143265
* The expression icmp eq (select (icmp eq x, 0), 1, x), 0 folds to false.Duncan Sands2011-10-281-0/+9
| | | | | | | | | Spotted by my super-optimizer in 186.crafty and 450.soplex. We really need a proper infrastructure for handling generalizations of this kind of thing (which occur a lot), however this case is so simple that I decided to go ahead and implement it directly. llvm-svn: 143214
* Fold icmp ugt (udiv X, Y), X to false. Spotted by my super-optimizerDuncan Sands2011-10-281-0/+24
| | | | | | in 186.crafty. llvm-svn: 143209
* Reapply commit 143028 with a fix: the problem was casting a ConstantExpr MulDuncan Sands2011-10-271-0/+31
| | | | | | | | | | | using BinaryOperator (which only works for instructions) when it should have been a cast to OverflowingBinaryOperator (which also works for constants). While there, correct a few other dubious looking uses of BinaryOperator. Thanks to Chad Rosier for the testcase. Original commit message: My super-optimizer noticed that we weren't folding this expression to true: (x *nsw x) sgt 0, where x = (y | 1). This occurs in 464.h264ref. llvm-svn: 143125
* Revert Duncan's r143028 expression folding which appears to be the culpritBob Wilson2011-10-271-31/+0
| | | | | | behind a compile failure on 483.xalancbmk. llvm-svn: 143102
* My super-optimizer noticed that we weren't folding this expression toDuncan Sands2011-10-261-0/+31
| | | | | | true: (x *nsw x) sgt 0, where x = (y | 1). This occurs in 464.h264ref. llvm-svn: 143028
OpenPOWER on IntegriCloud