Page MenuHomePhabricator

[InstSimplify] Fold simple known implications to true
ClosedPublic

Authored by reames on Sep 22 2015, 3:13 PM.

Details

Summary

This was split off of http://reviews.llvm.org/D13040 to make it easier to test the correctness of the implication logic. For the moment, this only handles a single easy case which shows up when eliminating and combining range checks. In the (near) future, I plan to extend this for other cases which show up in range checks, but I wanted to make those changes incrementally once the framework was in place.

At the moment, the implication logic will be used by two places. One in InstSimplify (this review) and two in SimplifyCFG (http://reviews.llvm.org/D13040 & http://reviews.llvm.org/D13070). Can anyone think of other locations this style of reasoning would make sense?

Diff Detail

Repository
rL LLVM

Event Timeline

reames updated this revision to Diff 35423.Sep 22 2015, 3:13 PM
reames retitled this revision from to [InstSimplify] Fold simple known implications to true.
reames updated this object.
reames added reviewers: majnemer, sanjoy.
reames added a subscriber: llvm-commits.
sanjoy added inline comments.Sep 22 2015, 8:49 PM
lib/Analysis/InstructionSimplify.cpp
2140 ↗(On Diff #35423)

Same comment here as in D13040: "Why not use matchers from PatternMatch.h here? I think that will make the logic a lot more obvious."

2210 ↗(On Diff #35423)

You could also match >=s here.

reames updated this revision to Diff 35544.Sep 23 2015, 1:13 PM

Match via pattern matchers not raw inspection; in the process fix a bug - I was accepting any binary operator, not just add.

Handle one more case while I'm at it.

reames marked an inline comment as done.Sep 23 2015, 1:15 PM
reames added inline comments.
lib/Analysis/InstructionSimplify.cpp
2216 ↗(On Diff #35544)

Pretty sure I can't use signed compares. I believe "1" is interpreted as "-1" in a signed compare. This generates a different truth table.

hfinkel added inline comments.
lib/Analysis/InstructionSimplify.cpp
2216 ↗(On Diff #35544)

FWIW, yes, i1 signed values are interpreted as 0 and -1.

sanjoy added inline comments.Sep 23 2015, 1:43 PM
lib/Analysis/InstructionSimplify.cpp
2216 ↗(On Diff #35544)

I was taking about matching LHS >=s RHS as LHS implies RHS. I
think the truth table is

LHS | RHS | LHS >=s RHS   | LHS implies RHS
 0  |  0  |  1 (0 >= 0)   |  1
 0  |  1  |  1 (0 >= -1)  |  1
 1  |  0  |  0 (-1 >= 0)  |  0
 1  |  1  |  1 (-1 >= -1) |  1
reames added inline comments.Sep 23 2015, 5:22 PM
lib/Analysis/InstructionSimplify.cpp
2216 ↗(On Diff #35544)

Hm, interesting. You appear to be right. Assume I've added this, anything else?

sanjoy edited edge metadata.Sep 23 2015, 5:32 PM

This looks good to me (both with or without the sle change, as you see fit), but given that I haven't worked on instsimplify, I'd wait for @hfinkel to take a final look.

I don't know if instcombine transforms Not(A) | B to A ULE B. If it does not, adding that seems like a logical thing to do (in a later change) -- I think that's a more idiomatic way to represent implication.

reames added a subscriber: reames.Sep 25 2015, 9:56 AM

Ping. Hal? David?

hfinkel accepted this revision.Sep 25 2015, 4:47 PM
hfinkel edited edge metadata.

LGTM too.

This revision is now accepted and ready to land.Sep 25 2015, 4:47 PM
This revision was automatically updated to reflect the committed changes.