Simplify `x >=u x >> y` and `x >=u x udiv y`
Summary:
Extends InstSimplify to handle both `x >=u x >> y` and `x >=u x udiv y`.
This is a folloup of rL258422 and
https://github.com/rust-lang/rust/pull/30917 where llvm failed to
optimize away the bounds checking in a binary search.
Patch by Arthur Silva!
Reviewers: sanjoy
Subscribers: llvm-commits
Differential Revision: https://reviews.llvm.org/D25941
llvm-svn: 285228
diff --git a/llvm/lib/Analysis/InstructionSimplify.cpp b/llvm/lib/Analysis/InstructionSimplify.cpp
index 1679d3a..398ac52 100644
--- a/llvm/lib/Analysis/InstructionSimplify.cpp
+++ b/llvm/lib/Analysis/InstructionSimplify.cpp
@@ -2857,6 +2857,17 @@
return getTrue(ITy);
}
+ // x >=u x >> y
+ // x >=u x udiv y.
+ if (RBO && (match(RBO, m_LShr(m_Specific(LHS), m_Value())) ||
+ match(RBO, m_UDiv(m_Specific(LHS), m_Value())))) {
+ // icmp pred X, (X op Y)
+ if (Pred == ICmpInst::ICMP_ULT)
+ return getFalse(ITy);
+ if (Pred == ICmpInst::ICMP_UGE)
+ return getTrue(ITy);
+ }
+
// handle:
// CI2 << X == CI
// CI2 << X != CI