[InstCombine] Simplify (x >> y) <= x
This commit extends the patterns recognised by InstSimplify to also handle (x >> y) <= x in the same way as (x /u y) <= x.
The missing optimisation was found investigating why LLVM did not optimise away bound checks in a binary search: https://github.com/rust-lang/rust/pull/30917
Patch by Andrea Canciani!
Differential Revision: http://reviews.llvm.org/D16402
llvm-svn: 258422
diff --git a/llvm/lib/Analysis/InstructionSimplify.cpp b/llvm/lib/Analysis/InstructionSimplify.cpp
index 2b577f0..1300ec9 100644
--- a/llvm/lib/Analysis/InstructionSimplify.cpp
+++ b/llvm/lib/Analysis/InstructionSimplify.cpp
@@ -2727,9 +2727,11 @@
}
}
+ // x >> y <=u x
// x udiv y <=u x.
- if (LBO && match(LBO, m_UDiv(m_Specific(RHS), m_Value()))) {
- // icmp pred (X /u Y), X
+ if (LBO && (match(LBO, m_LShr(m_Specific(RHS), m_Value())) ||
+ match(LBO, m_UDiv(m_Specific(RHS), m_Value())))) {
+ // icmp pred (X op Y), X
if (Pred == ICmpInst::ICMP_UGT)
return getFalse(ITy);
if (Pred == ICmpInst::ICMP_ULE)