[InstCombine] fold icmp sgt/slt (add nsw X, C2), C --> icmp sgt/slt X, (C - C2)
ClosedPublic

Authored by spatel on Feb 9 2017, 10:48 AM.

Details

Summary

I found one special case of this transform for 'slt 0', so I removed that and added the general transform.

Here are Alive programs that try to verify the correctness of the logic:
http://rise4fun.com/Alive/GH

(is there a better way to write the no-overflow constraints?)

Name: slt_no_overflow
Pre: ((C1 < 0) && (C2 < 0)) || ((C1 >= 0) && (C2 >= 0)) || (((C2 - C1) < 0) && (C2 < 0)) || (((C2 - C1) >= 0) && (C2 >= 0))
%a = add nsw i8 %x, C1
%b = icmp slt %a, C2

=>

%b = icmp slt %x, C2 - C1

Name: sgt_no_overflow
Pre: ((C1 < 0) && (C2 < 0)) || ((C1 >= 0) && (C2 >= 0)) || (((C2 - C1) < 0) && (C2 < 0)) || (((C2 - C1) >= 0) && (C2 >= 0))
%a = add nsw i8 %x, C1
%b = icmp sgt %a, C2

=>

%b = icmp sgt %x, C2 - C1

And here are the cases where the subtraction does overflow:
http://rise4fun.com/Alive/ao

Name: slt_overflow_false
Pre: C2 < 0 && C1 >= 0 && (C2 - C1) >= 0
%a = add nsw i8 %x, C1
%b = icmp slt %a, C2

=>

%b = false

Name: slt_overflow_true
Pre: C2 >= 0 && C1 < 0 && (C2 - C1) < 0
%a = add nsw i8 %x, C1
%b = icmp slt %a, C2

=>

%b = true

Name: sgt_overflow_true
Pre: C2 < 0 && C1 >= 0 && (C2 - C1) >= 0
%a = add nsw i8 %x, C1
%b = icmp sgt %a, C2

=>

%b = true

Name: sgt_overflow_false
Pre: C2 >= 0 && C1 < 0 && (C2 - C1) < 0
%a = add nsw i8 %x, C1
%b = icmp sgt %a, C2

=>

%b = false

Diff Detail

Repository
rL LLVM
spatel created this revision.Feb 9 2017, 10:48 AM

LGTM.
The easy way to check for overflow in Alive: http://rise4fun.com/Alive/MH

Regarding the instsimplify ones you mention, I didn't check what's implemented, but they need a precondition stronger than just that C1-C2 overflows: http://rise4fun.com/Alive/TRL

LGTM.
The easy way to check for overflow in Alive: http://rise4fun.com/Alive/MH

Thanks! I should read some docs now. :)
It looks like I should start with the papers and presentations from previous LLVM dev confs...is there also a reference doc for the online tool?

Regarding the instsimplify ones you mention, I didn't check what's implemented, but they need a precondition stronger than just that C1-C2 overflows: http://rise4fun.com/Alive/TRL

We know that those will simplify to true/false in all cases, but we don't know if the result is true or false unless we check the sign of C2:
http://rise4fun.com/Alive/2S

This revision was automatically updated to reflect the committed changes.

LGTM.
The easy way to check for overflow in Alive: http://rise4fun.com/Alive/MH

Thanks! I should read some docs now. :)
It looks like I should start with the papers and presentations from previous LLVM dev confs...is there also a reference doc for the online tool?

There isn't much available, sorry. I need to write down some documentation.
You can see the list of predicates/functions here (the syntax highlighting code): https://github.com/nunoplopes/alive/blob/newsema/rise4fun/language

Anyway, if there's some feature you are missing let me know ;)