Add optimization for 'icmp slt (or A, B), A' and some related idioms based on knowled...
authorNick Lewycky <nicholas@mxc.ca>
Thu, 21 Apr 2016 00:53:14 +0000 (00:53 +0000)
committerNick Lewycky <nicholas@mxc.ca>
Thu, 21 Apr 2016 00:53:14 +0000 (00:53 +0000)
commit762f8a8549c86014d0f1d73518c1133829202c1c
tree3fd53937d82cd0ad9914ef6303d3045fb96e75b5
parent410ae489b4989667f34621037ef84114375aa7e7
Add optimization for 'icmp slt (or A, B), A' and some related idioms based on knowledge of the sign bit for A and B.

No matter what value you OR in to A, the result of (or A, B) is going to be UGE A. When A and B are positive, it's SGE too. If A is negative, OR'ing a value into it can't make it positive, but can increase its value closer to -1, therefore (or A, B) is SGE A. Working through all possible combinations produces this truth table:

```
A is
+, -, +/-
F  F   F   +    B is
T  F   ?   -
?  F   ?   +/-
```

The related optimizations are flipping the 'slt' for 'sge' which always NOTs the result (if the result is known), and swapping the LHS and RHS while swapping the comparison predicate.

There are more idioms left to implement (aren't there always!) but I've stopped here because any more would risk becoming unreasonable for reviewers.

llvm-svn: 266939
llvm/include/llvm/Analysis/ValueTracking.h
llvm/include/llvm/IR/PatternMatch.h
llvm/lib/Analysis/InstructionSimplify.cpp
llvm/lib/Analysis/ValueTracking.cpp
llvm/test/Transforms/InstSimplify/compare.ll