Added InstCombine transformation for combining two instructions icmp ult/ule/uge/ugt (ashr/lshr (Const2) %A), (Const1)

[ankur29.garg]

Summary

Hi,
I have added function to transform the two instructions of the type:
icmp slt/sle/ult/ule/sge/sgt/uge/ugt (ashr/lshr (Const2) %A), (Const1)

The patch for operators eq/ne has already been added in: http://reviews.llvm.org/D4068
This handles it for rest of the operators.

Please help in reviewing it.

Edit:
This patch now implements the optimization for only unsigned operators (ult/ule/ugt/uge). I've split it into two to make it easier to review. Earlier, the size of the diff was quite large.

Thanks.
Regards,
Ankur Garg

[majnemer]

You have a lot of logic in here that could easily live in InstSimplify, please move appropriate code into the InstructionSimplify analysis code in a separate differential.

[ankur29.garg]

Hi David,
Thanks for the comments. Some of the logic that i have written here is already present in InstSimplify. Those cases never reach here. I just added them for better understanding of the code flow as done for previous patch for EQ/NE. Should I remove the logic which is not being used in this function ? or Should I keep it for better understanding of the logical flow ?

Thanks.

[majnemer]

Untestable code makes this harder to understand, I'd simply assert that those states are unreachable.

[ankur29.garg]

Hi David,
All of the logic movable to InstSimplify was already present there. I have removed most of such logic from this function.
Remaining logic is quite specific to certain cases and I have left it as it is, just to avoid confusion in understanding the other cases. Though, it is already being handled in InstSimplify.

Please help in reviewing the updated revision.
Thanks.

[ankur29.garg]

Gentle Ping !

[ankur29.garg]

Gentle Ping !

[ankur29.garg]

Hi everyone,
It seems like this patch which I had submitted earlier for review was quite big and it would've taken a lot of effort for some one to review it.
So, I have split it into 2 parts.
This updated revision contains the optimization for unsigned operators (ult/ule/ugt/uge). Once this is reviewed, I will submit another patch with only signed operators so, that it becomes easier to review.

Also, Based on another patch i submitted for 'shl' instruction, I have made some changes based on the reviews I received for that patch.

This is a reduced size patch. Please help in reviewing it.

Thanks.

[silvas]

Could you verify this with a theorem prover?

[ankur29.garg]

Hi Silvas,
Can you please suggest some theorem prover which would be useful for llvm optimizations ?
The only theorem prover that I've used is http://rise4fun.com/Z3/. But, in this, we'll have to declare all the functions being used inside the logic for example, getBitWidth(), countLeadingZeros(), etc. Also, I am not sure if I can return instructions using this.

Thanks.

[ankur29.garg]

Hi silvas,
I checked the optimization using ALIVe. I found out a couple of cases, which although never reached this code, were being handled wrong. I have made the appropriate changes to exclude those cases from being handled here as they are already being handled in InstSimplify.

Since there are 4 number of operators (uge/ugt/ule/ult) and two right shifts (ashr/lshr), the total number of cases are really huge. This makes the output of alive really large. (Total 56 separate cases). Should I paste it here ?

[ankur29.garg]

Here is the ALIVe input I used to test the optimization:

Name: 1
Pre: C1 == C2 && C1 < 0 && C2 != -1
 %shr = ashr i8 C2, %a
 %cmp = icmp ule i8 %shr, C1
=>
 %cmp = icmp eq i8 %a, 0

Name: 2
Pre: C1 == C2 && C1 < 0 && C2 != -1
 %shr = ashr i8 C2, %a
 %cmp = icmp ugt i8 %shr, C1
=>
 %cmp = icmp ne i8 %a, 0

Name: 3
Pre: C1 == C2 && C1 < 0 && C2 != -1
 %shr = ashr i8 C2, %a
 %cmp = icmp ult i8 %shr, C1
=>
 %cmp = i1 false

Name: 4
Pre: C1 == C2 && C1 < 0 && C2 != -1
 %shr = ashr i8 C2, %a
 %cmp = icmp uge i8 %shr, C1
=>
 %cmp = i1 true
 
Name: 5
Pre: C1 == C2 && C2 != -1 && C2 != 0
 %shr = lshr i8 C2, %a
 %cmp = icmp ult i8 %shr, C1
=>
 %cmp = icmp ugt i8 %a, 0

Name: 6
Pre: C1 == C2 && C2 != -1 && C2 != 0
 %shr = lshr i8 C2, %a
 %cmp = icmp uge i8 %shr, C1
=>
 %cmp = icmp eq i8 %a, 0

Name: 7
Pre: C1 == C2 && C2 != -1 && C2 != 0
 %shr = lshr i8 C2, %a
 %cmp = icmp ule i8 %shr, C1
=>
 %cmp = i1 true

Name: 8
Pre: C1 == C2 && C2 != -1 && C2 != 0
 %shr = lshr i8 C2, %a
 %cmp = icmp ugt i8 %shr, C1
=>
 %cmp = i1 false

Name: 9
Pre: C1 == C2 && C1 > 0
 %shr = ashr i8 C2, %a
 %cmp = icmp ult i8 %shr, C1
=>
 %cmp = icmp ugt i8 %a, 0

Name: 10
Pre: C1 == C2 && C1 > 0
 %shr = ashr i8 C2, %a
 %cmp = icmp ule i8 %shr, C1
=>
 %cmp = i1 true

Name: 11
Pre: C1 == C2 && C1 > 0
 %shr = ashr i8 C2, %a
 %cmp = icmp ugt i8 %shr, C1
=>
 %cmp = i1 false

Name: 12
Pre: C1 == C2 && C1 > 0
 %shr = ashr i8 C2, %a
 %cmp = icmp uge i8 %shr, C1
=>
 %cmp = icmp eq i8 %a, 0

Name: 13
Pre: C1 != C2 && C1 < 0 && C2 < C1 && C2 >> (log2(~C2) - log2(~C1)) == C1
 %shr = ashr i8 C2, %a
 %cmp = icmp uge i8 %shr, C1
=>
 %cmp = icmp uge i8 %a, log2(~C2) - log2(~C1)

Name: 14
Pre: C1 != C2 && C1 < 0 && C2 < C1 && C2 >> (log2(~C2) - log2(~C1)) == C1
 %shr = ashr i8 C2, %a
 %cmp = icmp ugt i8 %shr, C1
=>
 %cmp = icmp ugt i8 %a, log2(~C2) - log2(~C1)
 
Name: 15
Pre: C1 != C2 && C1 < 0 && C2 < C1 && C2 >> (log2(~C2) - log2(~C1)) == C1
 %shr = ashr i8 C2, %a
 %cmp = icmp ule i8 %shr, C1
=>
 %cmp = icmp ule i8 %a, log2(~C2) - log2(~C1)

Name: 16
Pre: C1 != C2 && C1 < 0 && C2 < C1 && C2 >> (log2(~C2) - log2(~C1)) == C1
 %shr = ashr i8 C2, %a
 %cmp = icmp ult i8 %shr, C1
=>
 %cmp = icmp ult i8 %a, log2(~C2) - log2(~C1)


Name: 17
Pre: C1 != C2 && C1 < 0 && C2 < C1 && (C2 >> (log2(~C2) - log2(~C1))) u> (C1)
 %shr = ashr i8 C2, %a
 %cmp = icmp uge i8 %shr, C1
=>
 %cmp = icmp ugt i8 %a, log2(~C2) - log2(~C1) - 1

Name: 18
Pre: C1 != C2 && C1 < 0 && C2 < C1 && (C2 >> (log2(~C2) - log2(~C1))) u> (C1)
 %shr = ashr i8 C2, %a
 %cmp = icmp ugt i8 %shr, C1
=>
 %cmp = icmp ugt i8 %a, log2(~C2) - log2(~C1) - 1

Name: 19
Pre: C1 != C2 && C1 < 0 && C2 < C1 && (C2 >> (log2(~C2) - log2(~C1))) u> (C1)
 %shr = ashr i8 C2, %a
 %cmp = icmp ult i8 %shr, C1
=>
 %cmp = icmp ult i8 %a, log2(~C2) - log2(~C1)

Name: 20
Pre: C1 != C2 && C1 < 0 && C2 < C1 && (C2 >> (log2(~C2) - log2(~C1))) u> (C1)
 %shr = ashr i8 C2, %a
 %cmp = icmp ule i8 %shr, C1
=>
 %cmp = icmp ult i8 %a, log2(~C2) - log2(~C1)

Name: 21
Pre: C1 != C2 && C1 < -1 && C2 < C1 && (C2 >> (log2(~C2) - log2(~C1))) u< (C1)
 %shr = ashr i8 C2, %a
 %cmp = icmp uge i8 %shr, C1
=>
 %cmp = icmp ugt i8 %a, log2(~C2) - log2(~C1)

Name: 22
Pre: C1 != C2 && C1 < -1 && C2 < C1 && (C2 >> (log2(~C2) - log2(~C1))) u< (C1)
 %shr = ashr i8 C2, %a
 %cmp = icmp ugt i8 %shr, C1
=>
 %cmp = icmp ugt i8 %a, log2(~C2) - log2(~C1)

Name: 23
Pre: C1 != C2 && C1 < -1 && C2 < C1 && (C2 >> (log2(~C2) - log2(~C1))) u< (C1)
 %shr = ashr i8 C2, %a
 %cmp = icmp ult i8 %shr, C1
=>
 %cmp = icmp ult i8 %a, log2(~C2) - log2(~C1) + 1

Name: 24
Pre: C1 != C2 && C1 < -1 && C2 < C1 && (C2 >> (log2(~C2) - log2(~C1))) u< (C1)
 %shr = ashr i8 C2, %a
 %cmp = icmp ule i8 %shr, C1
=>
 %cmp = icmp ult i8 %a, log2(~C2) - log2(~C1) + 1
 
Name: 25
Pre: C1 != C2 && C1 > 0 && C1 u> C2
 %shr = ashr i8 C2, %a
 %cmp = icmp uge i8 %shr, C1
=>
 %cmp = i1 false

Name: 26
Pre: C1 != C2 && C1 > 0 && C1 u> C2
 %shr = ashr i8 C2, %a
 %cmp = icmp ugt i8 %shr, C1
=>
 %cmp = i1 false

Name: 27
Pre: C1 != C2 && C1 > 0 && C1 u> C2
 %shr = ashr i8 C2, %a
 %cmp = icmp ule i8 %shr, C1
=>
 %cmp = i1 true

Name: 28
Pre: C1 != C2 && C1 > 0 && C1 u> C2
 %shr = ashr i8 C2, %a
 %cmp = icmp ult i8 %shr, C1
=>
 %cmp = i1 true

Name: 29
Pre: C1 != C2 && C1 > 0 && C2 > 0 && (C1 u< C2) && C1 == lshr(C2, countLeadingZeros(C1) - countLeadingZeros(C2))
 %shr = ashr i8 C2, %a
 %cmp = icmp ult i8 %shr, C1
=>
 %cmp = icmp ugt i8 %a, countLeadingZeros(C1) - countLeadingZeros(C2)

Name: 30
Pre: C1 != C2 && C1 > 0 && C2 > 0 && (C1 u< C2) && C1 == lshr(C2, countLeadingZeros(C1) - countLeadingZeros(C2))
 %shr = ashr i8 C2, %a
 %cmp = icmp ule i8 %shr, C1
=>
 %cmp = icmp uge i8 %a, countLeadingZeros(C1) - countLeadingZeros(C2)

Name: 31
Pre: C1 != C2 && C1 > 0 && C2 > 0 && (C1 u< C2) && C1 == lshr(C2, countLeadingZeros(C1) - countLeadingZeros(C2))
 %shr = ashr i8 C2, %a
 %cmp = icmp ugt i8 %shr, C1
=>
 %cmp = icmp ult i8 %a, countLeadingZeros(C1) - countLeadingZeros(C2)

Name: 32
Pre: C1 != C2 && C1 > 0 && C2 > 0 && (C1 u< C2) && C1 == lshr(C2, countLeadingZeros(C1) - countLeadingZeros(C2))
 %shr = ashr i8 C2, %a
 %cmp = icmp uge i8 %shr, C1
=>
 %cmp = icmp ule i8 %a, countLeadingZeros(C1) - countLeadingZeros(C2)
 
Name: 33
Pre: C1 != C2 && C1 > 0 && C2 > 0 && C1 u< C2 && C1 u> lshr(C2, countLeadingZeros(C1) - countLeadingZeros(C2))
 %shr = ashr i8 C2, %a
 %cmp = icmp ult i8 %shr, C1
=>
 %cmp = icmp ugt i8 %a, countLeadingZeros(C1) - countLeadingZeros(C2) - 1

Name: 34
Pre: C1 != C2 && C1 > 0 && C2 > 0 && C1 u< C2 && C1 u> lshr(C2, countLeadingZeros(C1) - countLeadingZeros(C2))
 %shr = ashr i8 C2, %a
 %cmp = icmp ule i8 %shr, C1
=>
 %cmp = icmp ugt i8 %a, countLeadingZeros(C1) - countLeadingZeros(C2) - 1

Name: 35
Pre: C1 != C2 && C1 > 0 && C2 > 0 && C1 u< C2 && C1 u> lshr(C2, countLeadingZeros(C1) - countLeadingZeros(C2))
 %shr = ashr i8 C2, %a
 %cmp = icmp ugt i8 %shr, C1
=>
 %cmp = icmp ule i8 %a, countLeadingZeros(C1) - countLeadingZeros(C2) - 1

Name: 36
Pre: C1 != C2 && C1 > 0 && C2 > 0 && C1 u< C2 && C1 u> lshr(C2, countLeadingZeros(C1) - countLeadingZeros(C2))
 %shr = ashr i8 C2, %a
 %cmp = icmp uge i8 %shr, C1
=>
 %cmp = icmp ule i8 %a, countLeadingZeros(C1) - countLeadingZeros(C2) - 1


Name: 37
Pre: C1 != C2 && C1 > 0 && C2 > 0 && C1 u< C2 && C1 u< lshr(C2, countLeadingZeros(C1) - countLeadingZeros(C2))
 %shr = ashr i8 C2, %a
 %cmp = icmp ult i8 %shr, C1
=>
 %cmp = icmp ugt i8 %a, countLeadingZeros(C1) - countLeadingZeros(C2)

Name: 38
Pre: C1 != C2 && C1 > 0 && C2 > 0 && C1 u< C2 && C1 u< lshr(C2, countLeadingZeros(C1) - countLeadingZeros(C2))
 %shr = ashr i8 C2, %a
 %cmp = icmp ule i8 %shr, C1
=>
 %cmp = icmp ugt i8 %a, countLeadingZeros(C1) - countLeadingZeros(C2)

Name: 39
Pre: C1 != C2 && C1 > 0 && C2 > 0 && C1 u< C2 && C1 u< lshr(C2, countLeadingZeros(C1) - countLeadingZeros(C2))
 %shr = ashr i8 C2, %a
 %cmp = icmp ugt i8 %shr, C1
=>
 %cmp = icmp ule i8 %a, countLeadingZeros(C1) - countLeadingZeros(C2)

Name: 40
Pre: C1 != C2 && C1 > 0 && C2 > 0 && C1 u< C2 && C1 u< lshr(C2, countLeadingZeros(C1) - countLeadingZeros(C2))
 %shr = ashr i8 C2, %a
 %cmp = icmp uge i8 %shr, C1
=>
 %cmp = icmp ule i8 %a, countLeadingZeros(C1) - countLeadingZeros(C2)
 
Name: 41
Pre: C1 != C2 && C1 u> C2
 %shr = lshr i8 C2, %a
 %cmp = icmp uge i8 %shr, C1
=>
 %cmp = i1 false

Name: 42
Pre: C1 != C2 && C1 u> C2
 %shr = lshr i8 C2, %a
 %cmp = icmp ugt i8 %shr, C1
=>
 %cmp = i1 false

Name: 43
Pre: C1 != C2 && C1 u> C2
 %shr = lshr i8 C2, %a
 %cmp = icmp ule i8 %shr, C1
=>
 %cmp = i1 true

Name: 44
Pre: C1 != C2 && C1 u> C2
 %shr = lshr i8 C2, %a
 %cmp = icmp ult i8 %shr, C1
=>
 %cmp = i1 true

Name: 45
Pre: C1 != 0 && C2 != 0 && C1 != C2 && C1 u< C2 && C1 == lshr(C2, countLeadingZeros(C1) - countLeadingZeros(C2))
 %shr = lshr i8 C2, %a
 %cmp = icmp ult i8 %shr, C1
=>
 %cmp = icmp ugt i8 %a, countLeadingZeros(C1) - countLeadingZeros(C2)

Name: 46
Pre: C1 != 0 && C2 != 0 && C1 != C2 && C1 u< C2 && C1 == lshr(C2, countLeadingZeros(C1) - countLeadingZeros(C2))
 %shr = lshr i8 C2, %a
 %cmp = icmp ule i8 %shr, C1
=>
 %cmp = icmp uge i8 %a, countLeadingZeros(C1) - countLeadingZeros(C2)

Name: 47
Pre: C1 != 0 && C2 != 0 && C1 != C2 && C1 u< C2 && C1 == lshr(C2, countLeadingZeros(C1) - countLeadingZeros(C2))
 %shr = lshr i8 C2, %a
 %cmp = icmp ugt i8 %shr, C1
=>
 %cmp = icmp ult i8 %a, countLeadingZeros(C1) - countLeadingZeros(C2)

Name: 48
Pre: C1 != 0 && C2 != 0 && C1 != C2 && C1 u< C2 && C1 == lshr(C2, countLeadingZeros(C1) - countLeadingZeros(C2))
 %shr = lshr i8 C2, %a
 %cmp = icmp uge i8 %shr, C1
=>
 %cmp = icmp ule i8 %a, countLeadingZeros(C1) - countLeadingZeros(C2)
 
Name: 49
Pre: C1 != 0 && C2 != 0 && C1 != C2 && C1 u< C2 && C1 u> lshr(C2, countLeadingZeros(C1) - countLeadingZeros(C2))
 %shr = lshr i8 C2, %a
 %cmp = icmp ult i8 %shr, C1
=>
 %cmp = icmp ugt i8 %a, countLeadingZeros(C1) - countLeadingZeros(C2) - 1

Name: 50
Pre: C1 != 0 && C2 != 0 && C1 != C2 && C1 u< C2 && C1 u> lshr(C2, countLeadingZeros(C1) - countLeadingZeros(C2))
 %shr = lshr i8 C2, %a
 %cmp = icmp ule i8 %shr, C1
=>
 %cmp = icmp ugt i8 %a, countLeadingZeros(C1) - countLeadingZeros(C2) - 1

Name: 51
Pre: C1 != 0 && C2 != 0 && C1 != C2 && C1 u< C2 && C1 u> lshr(C2, countLeadingZeros(C1) - countLeadingZeros(C2))
 %shr = lshr i8 C2, %a
 %cmp = icmp ugt i8 %shr, C1
=>
 %cmp = icmp ule i8 %a, countLeadingZeros(C1) - countLeadingZeros(C2) - 1

Name: 52
Pre: C1 != 0 && C2 != 0 && C1 != C2 && C1 u< C2 && C1 u> lshr(C2, countLeadingZeros(C1) - countLeadingZeros(C2))
 %shr = lshr i8 C2, %a
 %cmp = icmp uge i8 %shr, C1
=>
 %cmp = icmp ule i8 %a, countLeadingZeros(C1) - countLeadingZeros(C2) - 1

Name: 53
Pre: C1 != 0 && C2 != 0 && C1 != C2 && C1 u< C2 && C1 u< lshr(C2, countLeadingZeros(C1) - countLeadingZeros(C2))
 %shr = lshr i8 C2, %a
 %cmp = icmp ult i8 %shr, C1
=>
 %cmp = icmp ugt i8 %a, countLeadingZeros(C1) - countLeadingZeros(C2)

Name: 54
Pre: C1 != 0 && C2 != 0 && C1 != C2 && C1 u< C2 && C1 u< lshr(C2, countLeadingZeros(C1) - countLeadingZeros(C2))
 %shr = lshr i8 C2, %a
 %cmp = icmp ule i8 %shr, C1
=>
 %cmp = icmp ugt i8 %a, countLeadingZeros(C1) - countLeadingZeros(C2)

Name: 55
Pre: C1 != 0 && C2 != 0 && C1 != C2 && C1 u< C2 && C1 u< lshr(C2, countLeadingZeros(C1) - countLeadingZeros(C2))
 %shr = lshr i8 C2, %a
 %cmp = icmp ugt i8 %shr, C1
=>
 %cmp = icmp ule i8 %a, countLeadingZeros(C1) - countLeadingZeros(C2)

Name: 56
Pre: C1 != 0 && C2 != 0 && C1 != C2 && C1 u< C2 && C1 u< lshr(C2, countLeadingZeros(C1) - countLeadingZeros(C2))
 %shr = lshr i8 C2, %a
 %cmp = icmp uge i8 %shr, C1
=>
 %cmp = icmp ule i8 %a, countLeadingZeros(C1) - countLeadingZeros(C2)

[ankur29.garg]

Gentle Ping !

[ankur29.garg]

Gentle Ping !

[ankur29.garg]

Gentle Ping!

[ankur29.garg]

Hi David,
Can you please help in reviewing this patch. I have added the ALIVe output for proving the correctness of the transformation.

Thanks.

[majnemer]

lib/Transforms/InstCombine/InstCombineCompares.cpp

1125

This should be handled by InstSimplify.

1136

As should this.

1159

And this.

2682–2702

This code would be more general if you use m_APInt instead of m_ConstantInt.

2689

Can you just make this if, I think it makes the control flow a little simpler.

2690–2697

Why is this else if now? It should be fine as if.

[ankur29.garg]

Hi David,
Thanks for reviewing the patch. I have made the changes as per your comments.

About the change from ConstantInt to APInt:
There are two ConstantInt variables 'CI' and 'CI2'. The variable 'CI' is being used elsewhere too. Should I make this change ? And CI2 is being used in 2 other functions. Both these functions right now, expect ConstantInt. Should I change it for all the functions ?

Thanks.

[ankur29.garg]

Gentle Ping !

[ankur29.garg]

Gentle Ping ! Please help in reviewing the changes.

[ankur29.garg]

Gentle Ping

lib/Transforms/InstCombine/InstCombine.h

public:
   Instruction *visitICmpInstWithInstAndIntCst(ICmpInst &ICI, Instruction *LHS,
                                               ConstantInt *RHS);
   Instruction *FoldICmpDivCst(ICmpInst &ICI, BinaryOperator *DivI,
                               ConstantInt *DivRHS);
   Instruction *FoldICmpShrCst(ICmpInst &ICI, BinaryOperator *DivI,
                               ConstantInt *DivRHS);
   Instruction *FoldICmpCstShrCst(ICmpInst &I, Value *Op, Value *A,
                                  ConstantInt *CI1, ConstantInt *CI2);
+  Instruction *FoldUICmpCstShrCst(ICmpInst &I, Value *Op, Value *A,
+                                  ConstantInt *CI1, ConstantInt *CI2);
   Instruction *FoldICmpCstShlCst(ICmpInst &I, Value *Op, Value *A,
                                  ConstantInt *CI1, ConstantInt *CI2);
   Instruction *FoldICmpAddOpCst(Instruction &ICI, Value *X, ConstantInt *CI,
                                 ICmpInst::Predicate Pred);
   Instruction *FoldGEPICmp(GEPOperator *GEPLHS, Value *RHS,
                            ICmpInst::Predicate Cond, Instruction &I);
   Instruction *FoldShiftByConstant(Value *Op0, Constant *Op1,
                                    BinaryOperator &I);

lib/Transforms/InstCombine/InstCombineCompares.cpp

if (AP2 == 0)
     return nullptr;
 
   unsigned AP2TrailingZeros = AP2.countTrailingZeros();
 
   if (!AP1 && AP2TrailingZeros != 0)
     return getICmp(I.ICMP_UGE, A,
                    ConstantInt::get(A->getType(), AP2.getBitWidth() - AP2TrailingZeros));
 
   if (AP1 == AP2)
     return getICmp(I.ICMP_EQ, A, ConstantInt::getNullValue(A->getType()));
 
   // Get the distance between the lowest bits that are set.
   int Shift = AP1.countTrailingZeros() - AP2TrailingZeros;
 
   if (Shift > 0 && AP2.shl(Shift) == AP1)
     return getICmp(I.ICMP_EQ, A, ConstantInt::get(A->getType(), Shift));
 
   // Shifting const2 will never be equal to const1.
   return getConstant(false);
 }
 
+Instruction *InstCombiner::FoldUICmpCstShrCst(ICmpInst &I, Value *Op, Value *A,
+                                              ConstantInt *CI1,
+                                              ConstantInt *CI2) {
+
+  Instruction *Result = nullptr;
+
+  APInt AP1 = CI1->getValue();
+  APInt AP2 = CI2->getValue();
+
+  bool IsAShr = isa<AShrOperator>(Op);
+
+  // Both AP1, AP2 are non-zero
+  if (!AP1 || !AP2) {
+    return Result;
+  }
+
+  if (AP1 == AP2) {
+    if (AP1.isNegative() && IsAShr) {
+      if (!AP1.isAllOnesValue()) {
+        if (I.getPredicate() == I.ICMP_ULE) {
+          Result = new ICmpInst(I.ICMP_EQ, A,
+                                ConstantInt::getNullValue(A->getType()));
+        } else if (I.getPredicate() == I.ICMP_UGT) {
+          Result = new ICmpInst(I.ICMP_NE, A,
+                                ConstantInt::getNullValue(A->getType()));
+        }
+      }
+    } else if (I.getPredicate() == I.ICMP_ULT) {
+      Result =
+          new ICmpInst(I.ICMP_UGT, A, ConstantInt::getNullValue(A->getType()));
+    } else if (I.getPredicate() == I.ICMP_UGE) {
+      Result =
+          new ICmpInst(I.ICMP_EQ, A, ConstantInt::getNullValue(A->getType()));
+    }
+  } else if (IsAShr && AP1.isNegative()) {
+    if (AP2.slt(AP1) && !AP1.isAllOnesValue()) {
+      int Shift = (~AP2).logBase2() - (~AP1).logBase2();
+
+      if (AP2.ashr(Shift) == AP1) {
+        Result = new ICmpInst(I.getPredicate(), A,
+                              ConstantInt::get(A->getType(), Shift));
+      } else {
+        if (AP2.ashr(Shift).ugt(AP1))
+          Shift--;
+        if (I.getPredicate() == I.ICMP_ULT || I.getPredicate() == I.ICMP_ULE) {
+          Result = new ICmpInst(I.ICMP_ULT, A,
+                                ConstantInt::get(A->getType(), Shift + 1));
+        } else {
+          Result = new ICmpInst(I.ICMP_UGT, A,
+                                ConstantInt::get(A->getType(), Shift));
+        }
+      }
+    }
+  } else if (!IsAShr || !AP1.isNegative()) {
+    if (AP1.ule(AP2)) {
+      int Shift = AP1.countLeadingZeros() - AP2.countLeadingZeros();
+      if (AP1 == AP2.lshr(Shift)) {
+        if (I.getPredicate() == I.ICMP_ULT) {
+          Result = new ICmpInst(I.ICMP_UGT, A,
+                                ConstantInt::get(A->getType(), Shift));
+        } else if (I.getPredicate() == I.ICMP_ULE) {
+          Result = new ICmpInst(I.ICMP_UGE, A,
+                                ConstantInt::get(A->getType(), Shift));
+        } else if (I.getPredicate() == I.ICMP_UGT) {
+          Result = new ICmpInst(I.ICMP_ULT, A,
+                                ConstantInt::get(A->getType(), Shift));
+        } else {
+          Result = new ICmpInst(I.ICMP_ULE, A,
+                                ConstantInt::get(A->getType(), Shift));
+        }
+      } else {
+        if (AP1.ugt(AP2.lshr(Shift))) {
+          Shift--;
+        }
+        if (I.getPredicate() == I.ICMP_ULT || I.getPredicate() == I.ICMP_ULE) {
+          Result = new ICmpInst(I.ICMP_UGT, A,
+                                ConstantInt::get(A->getType(), Shift));
+        } else {
+          Result = new ICmpInst(I.ICMP_ULE, A,
+                                ConstantInt::get(A->getType(), Shift));
+        }
+      }
+    }
+  }
+
+  return Result;
+}
+
 /// visitICmpInstWithInstAndIntCst - Handle "icmp (instr, intcst)".
 ///
 Instruction *InstCombiner::visitICmpInstWithInstAndIntCst(ICmpInst &ICI,
                                                           Instruction *LHSI,
                                                           ConstantInt *RHS) {
   const APInt &RHSV = RHS->getValue();
 
   switch (LHSI->getOpcode()) {
if (LHSI->hasOneUse() && isa<ConstantInt>(LHSI->getOperand(1)) &&
           // are correct using an SMT solver.
           if (!ICI.isSigned())
             CanFold = true;
           else {
             ConstantInt *ShiftedAndCst =
               cast<ConstantInt>(ConstantExpr::getShl(AndCst, ShAmt));
             ConstantInt *ShiftedRHSCst =
               cast<ConstantInt>(ConstantExpr::getShl(RHS, ShAmt));
-            
             if (!ShiftedAndCst->isNegative() && !ShiftedRHSCst->isNegative())
               CanFold = true;
           }
         }
 
         if (CanFold) {
           Constant *NewCst;
           if (ShiftOpcode == Instruction::Shl)
case ICmpInst::ICMP_UGE:
       return new ICmpInst(ICmpInst::ICMP_UGT, Op0,
                           Builder->getInt(CI->getValue()-1));
     case ICmpInst::ICMP_SGE:
       assert(!CI->isMinValue(true));                  // A >=s MIN -> TRUE
       return new ICmpInst(ICmpInst::ICMP_SGT, Op0,
                           Builder->getInt(CI->getValue()-1));
     }
 
-    if (I.isEquality()) {
-      ConstantInt *CI2;
-      if (match(Op0, m_AShr(m_ConstantInt(CI2), m_Value(A))) ||
-          match(Op0, m_LShr(m_ConstantInt(CI2), m_Value(A)))) {
+      if (I.isEquality()) {
         // (icmp eq/ne (ashr/lshr const2, A), const1)
         if (Instruction *Inst = FoldICmpCstShrCst(I, Op0, A, CI, CI2))
           return Inst;
       }
-      if (match(Op0, m_Shl(m_ConstantInt(CI2), m_Value(A)))) {
+      if (I.isUnsigned()) {
+        // (icmp ugt/uge/ult/ule (ashr/lshr const2, A), const1)
+        if (Instruction *Inst = FoldUICmpCstShrCst(I, Op0, A, CI, CI2))
+          return Inst;
+      }
+    }
+      if (I.isEquality()) {
         // (icmp eq/ne (shl const2, A), const1)
         if (Instruction *Inst = FoldICmpCstShlCst(I, Op0, A, CI, CI2))
           return Inst;
       }
     }
 
     // If this comparison is a normal comparison, it demands all
     // bits, if it is a sign bit comparison, it only demands the sign bit.
     bool UnusedBit;
     isSignBit = isSignBitCheck(I.getPredicate(), CI, UnusedBit);
   }
 
   // See if we can fold the comparison based on range information we can get

test/Transforms/InstCombine/icmp-shr.ll

 
 ; CHECK-LABEL: @PR21222
 ; CHECK: icmp eq i32 %B, 6
 define i1 @PR21222(i32 %B) {
   %shr = ashr i32 -93, %B
   %cmp = icmp eq i32 %shr, -2
   ret i1 %cmp
 }
+
+define i1 @ashr_ult_ap1_equal_ap2(i8 %a) {
+; CHECK-LABEL: @ashr_ult_ap1_equal_ap2(
+; CHECK-NEXT: %cmp = icmp ne i8 %a, 0
+; CHECK-NEXT: ret i1 %cmp
+  %shr = ashr i8 13, %a
+  %cmp = icmp ult i8 %shr, 13
+  ret i1 %cmp
+}
+
+define i1 @ashr_uge_ap1_equal_ap2(i8 %a) {
+; CHECK-LABEL: @ashr_uge_ap1_equal_ap2(
+; CHECK-NEXT: %cmp = icmp eq i8 %a, 0
+; CHECK-NEXT: ret i1 %cmp
+  %shr = ashr i8 13, %a
+  %cmp = icmp uge i8 %shr, 13
+  ret i1 %cmp
+}
+
+define i1 @lshr_ult_ap1_equal_ap2(i8 %a) {
+; CHECK-LABEL: @lshr_ult_ap1_equal_ap2(
+; CHECK-NEXT: %cmp = icmp ne i8 %a, 0
+; CHECK-NEXT: ret i1 %cmp
+  %shr = lshr i8 13, %a
+  %cmp = icmp ult i8 %shr, 13
+  ret i1 %cmp
+}
+
+define i1 @lshr_uge_ap1_equal_ap2(i8 %a) {
+; CHECK-LABEL: @lshr_uge_ap1_equal_ap2(
+; CHECK-NEXT: %cmp = icmp eq i8 %a, 0
+; CHECK-NEXT: ret i1 %cmp
+  %shr = lshr i8 13, %a
+  %cmp = icmp uge i8 %shr, 13
+  ret i1 %cmp
+}
+
+define i1 @ashr_ugt_ap1_equal_ap2_negative(i8 %a) {
+; CHECK-LABEL: @ashr_ugt_ap1_equal_ap2_negative(
+; CHECK-NEXT: %cmp = icmp ne i8 %a, 0
+; CHECK-NEXT: ret i1 %cmp
+  %shr = ashr i8 -13, %a
+  %cmp = icmp ugt i8 %shr, -13
+  ret i1 %cmp
+}
+
+define i1 @ashr_ule_ap1_equal_ap2_negative(i8 %a) {
+; CHECK-LABEL: @ashr_ule_ap1_equal_ap2_negative(
+; CHECK-NEXT: %cmp = icmp eq i8 %a, 0
+; CHECK-NEXT: ret i1 %cmp
+  %shr = ashr i8 -13, %a
+  %cmp = icmp ule i8 %shr, -13
+  ret i1 %cmp
+}
+
+define i1 @lshr_uge_ap1_equal_ap2_negative(i8 %a) {
+; CHECK-LABEL: @lshr_uge_ap1_equal_ap2_negative(
+; CHECK-NEXT: %cmp = icmp eq i8 %a, 0
+; CHECK-NEXT: ret i1 %cmp
+  %shr = lshr i8 -13, %a
+  %cmp = icmp uge i8 %shr, -13
+  ret i1 %cmp
+}
+
+define i1 @lshr_ult_ap1_equal_ap2_negative(i8 %a) {
+; CHECK-LABEL: @lshr_ult_ap1_equal_ap2_negative(
+; CHECK-NEXT: %cmp = icmp ne i8 %a, 0
+; CHECK-NEXT: ret i1 %cmp
+  %shr = lshr i8 -13, %a
+  %cmp = icmp ult i8 %shr, -13
+  ret i1 %cmp
+}
+
+define i1 @ashr_ugt_ap1_negative_ap2_negative_ap1(i32 %a) {
+; CHECK-LABEL: @ashr_ugt_ap1_negative_ap2_negative_ap1(
+; CHECK-NEXT: %cmp = icmp ne i32 %a, 0
+; CHECK-NEXT: ret i1 %cmp
+  %shr = ashr i32 -22, %a
+  %cmp = icmp ugt i32 %shr, -14
+  ret i1 %cmp
+}
+
+define i1 @ashr_ult_ap1_negative_ap2_negative_ap1(i32 %a) {
+; CHECK-LABEL: @ashr_ult_ap1_negative_ap2_negative_ap1(
+; CHECK-NEXT: %cmp = icmp eq i32 %a, 0
+; CHECK-NEXT: ret i1 %cmp
+  %shr = ashr i32 -22, %a
+  %cmp = icmp ult i32 %shr, -14
+  ret i1 %cmp
+}
+
+define i1 @ashr_uge_ap1_negative_ap2_negative_ap1(i32 %a) {
+; CHECK-LABEL: @ashr_uge_ap1_negative_ap2_negative_ap1(
+; CHECK-NEXT: %cmp = icmp ne i32 %a, 0
+; CHECK-NEXT: ret i1 %cmp
+  %shr = ashr i32 -22, %a
+  %cmp = icmp uge i32 %shr, -14
+  ret i1 %cmp
+}
+
+define i1 @ashr_ule_ap1_negative_ap2_negative_ap1(i32 %a) {
+; CHECK-LABEL: @ashr_ule_ap1_negative_ap2_negative_ap1(
+; CHECK-NEXT: %cmp = icmp eq i32 %a, 0
+; CHECK-NEXT: ret i1 %cmp
+  %shr = ashr i32 -22, %a
+  %cmp = icmp ule i32 %shr, -14
+  ret i1 %cmp
+}
+
+define i1 @lshr_ugt_ap1_negative_ap2_negative_ap2(i32 %a) {
+; CHECK-LABEL: @lshr_ugt_ap1_negative_ap2_negative_ap2(
+; CHECK-NEXT: %cmp = icmp eq i32 %a, 0
+; CHECK-NEXT: ret i1 %cmp
+  %shr = lshr i32 -14, %a
+  %cmp = icmp ugt i32 %shr, -22
+  ret i1 %cmp
+}
+
+define i1 @lshr_ult_ap1_negative_ap2_negative_ap2(i32 %a) {
+; CHECK-LABEL: @lshr_ult_ap1_negative_ap2_negative_ap2(
+; CHECK-NEXT: %cmp = icmp ne i32 %a, 0
+; CHECK-NEXT: ret i1 %cmp
+  %shr = lshr i32 -14, %a
+  %cmp = icmp ult i32 %shr, -22
+  ret i1 %cmp 
+}
+
+define i1 @lshr_uge_ap1_negative_ap2_negative_ap2(i32 %a) {
+; CHECK-LABEL: @lshr_uge_ap1_negative_ap2_negative_ap2(
+; CHECK-NEXT: %cmp = icmp eq i32 %a, 0
+; CHECK-NEXT: ret i1 %cmp
+  %shr = lshr i32 -14, %a
+  %cmp = icmp uge i32 %shr, -22
+  ret i1 %cmp
+}
+
+define i1 @lshr_ule_ap1_negative_ap2_negative_ap2(i32 %a) {
+; CHECK-LABEL: @lshr_ule_ap1_negative_ap2_negative_ap2(
+; CHECK-NEXT: %cmp = icmp ne i32 %a, 0
+; CHECK-NEXT: ret i1 %cmp
+  %shr = lshr i32 -14, %a
+  %cmp = icmp ule i32 %shr, -22
+  ret i1 %cmp
+}
+
+define i1 @lshr_ugt_ap1_positive_ap2_positive_ap2(i32 %a) {
+; CHECK-LABEL: @lshr_ugt_ap1_positive_ap2_positive_ap2(
+; CHECK-NEXT: %cmp = icmp eq i32 %a, 0
+; CHECK-NEXT: ret i1 %cmp
+  %shr = lshr i32 14, %a
+  %cmp = icmp ugt i32 %shr, 7
+  ret i1 %cmp
+}
+
+define i1 @lshr_ult_ap1_positive_ap2_positive_ap2(i32 %a) {
+; CHECK-LABEL: @lshr_ult_ap1_positive_ap2_positive_ap2(
+; CHECK-NEXT: %cmp = icmp ugt i32 %a, 1
+; CHECK-NEXT: ret i1 %cmp
+  %shr = lshr i32 14, %a
+  %cmp = icmp ult i32 %shr, 7
+  ret i1 %cmp 
+}
+
+define i1 @lshr_uge_ap1_positive_ap2_positive_ap2(i32 %a) {
+; CHECK-LABEL: @lshr_uge_ap1_positive_ap2_positive_ap2(
+; CHECK-NEXT: %cmp = icmp ult i32 %a, 2
+; CHECK-NEXT: ret i1 %cmp
+  %shr = lshr i32 14, %a
+  %cmp = icmp uge i32 %shr, 7
+  ret i1 %cmp
+}
+
+define i1 @lshr_ule_ap1_positive_ap2_positive_ap2(i32 %a) {
+; CHECK-LABEL: @lshr_ule_ap1_positive_ap2_positive_ap2(
+; CHECK-NEXT: %cmp = icmp ne i32 %a, 0
+; CHECK-NEXT: ret i1 %cmp
+  %shr = lshr i32 14, %a
+  %cmp = icmp ule i32 %shr, 7
+  ret i1 %cmp
+}
+
+define i1 @lshr_ugt_ap1_positive_ap2_negative(i32 %a) {
+; CHECK-LABEL: @lshr_ugt_ap1_positive_ap2_negative(
+; CHECK-NEXT: %cmp = icmp ult i32 %a, 29
+; CHECK-NEXT: ret i1 %cmp
+  %shr = lshr i32 -14, %a
+  %cmp = icmp ugt i32 %shr, 7
+  ret i1 %cmp
+}
+
+define i1 @lshr_ult_ap1_positive_ap2_negative(i32 %a) {
+; CHECK-LABEL: @lshr_ult_ap1_positive_ap2_negative(
+; CHECK-NEXT: %cmp = icmp ugt i32 %a, 29
+; CHECK-NEXT: ret i1 %cmp
+  %shr = lshr i32 -14, %a
+  %cmp = icmp ult i32 %shr, 7
+  ret i1 %cmp 
+}
+
+define i1 @lshr_uge_ap1_positive_ap2_negative(i32 %a) {
+; CHECK-LABEL: @lshr_uge_ap1_positive_ap2_negative(
+; CHECK-NEXT: %cmp = icmp ult i32 %a, 30
+; CHECK-NEXT: ret i1 %cmp
+  %shr = lshr i32 -14, %a
+  %cmp = icmp uge i32 %shr, 7
+  ret i1 %cmp
+}
+
+define i1 @lshr_ule_ap1_positive_ap2_negative(i32 %a) {
+; CHECK-LABEL: @lshr_ule_ap1_positive_ap2_negative(
+; CHECK-NEXT: %cmp = icmp ugt i32 %a, 28
+; CHECK-NEXT: ret i1 %cmp
+  %shr = lshr i32 -14, %a
+  %cmp = icmp ule i32 %shr, 7
+  ret i1 %cmp
+}