This is an archive of the discontinued LLVM Phabricator instance.

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

Authored by ankur29.garg on Sep 29 2014, 3:55 AM.

Details

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

Diff Detail

Event Timeline

ankur29.garg retitled this revision from to Added InstCombine transformation for combining two instructions icmp slt/sle/ult/ule/sge/sgt/uge/ugt (ashr/lshr (Const2) %A), (Const1).
ankur29.garg updated this object.
ankur29.garg edited the test plan for this revision. (Show Details)
ankur29.garg set the repository for this revision to rL LLVM.
ankur29.garg added a subscriber: Unknown Object (MLST).
majnemer edited edge metadata.Sep 29 2014, 10:09 AM

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.

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.

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

ankur29.garg edited edge metadata.

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 retitled this revision from Added InstCombine transformation for combining two instructions icmp slt/sle/ult/ule/sge/sgt/uge/ugt (ashr/lshr (Const2) %A), (Const1) to Added InstCombine transformation for combining two instructions icmp ult/ule/uge/ugt (ashr/lshr (Const2) %A), (Const1).
ankur29.garg updated this object.

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 added a subscriber: silvas.Nov 7 2014, 8:02 PM

Could you verify this with a theorem prover?

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.

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 ?

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)

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 added inline comments.Nov 28 2014, 11:13 AM
lib/Transforms/InstCombine/InstCombineCompares.cpp
1146

This should be handled by InstSimplify.

1157

As should this.

1180

And this.

2874–2883

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

2874–2885

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

2875

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

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.

Gentle Ping ! Please help in reviewing the changes.

dexonsmith resigned from this revision.Oct 6 2020, 3:35 PM
silvas removed a subscriber: silvas.Oct 8 2020, 7:17 PM