Page MenuHomePhabricator

[LVI] Introduce an intersect operation on lattice values

Authored by reames on Nov 6 2015, 7:32 PM.



LVI has several separate sources of facts - edge local conditions, recursive queries, assumes, and control independent value facts - which all apply to the same value at the same location. The existing implementation was very conservative about exploiting all of these facts at once.

This change introduces an "intersect" function specifically to abstract the action of picking a good set of facts from all of the separate facts given. At the moment, this function is relatively simple (i.e. mostly just reuses the bits which were already there), but even the minor additions reveal the inherent power. For example, JumpThreading is now capable of doing an inductive proof that a particular value is always positive and removing a half range check.

I'm currently only using the new intersect function in one place. If folks are happy with the direction of the work, I plan on making a series of small changes without review to replace mergeIn with intersect at all the appropriate places.

Diff Detail


Event Timeline

reames updated this revision to Diff 39625.Nov 6 2015, 7:32 PM
reames retitled this revision from to [LVI] Introduce an intersect operation on lattice values.
reames updated this object.
reames added reviewers: hfinkel, sanjoy, nlewycky.
reames added a subscriber: llvm-commits.
sanjoy edited edge metadata.Nov 9 2015, 11:25 AM

Two nitpicky comments inline.

1019 ↗(On Diff #39625)

Why not return A.isConstantRange() ? A : B?

1041 ↗(On Diff #39625)

This looks a little misleading. If the return value of getEdgeValueLocal truly does not matter, I'd prefer the more idiomatic (void)getEdgeValueLocal(...)

reames added inline comments.Nov 10 2015, 9:47 AM
1019 ↗(On Diff #39625)

Unless I'm misreading something, your replacement would be incorrect. Specifically, I'm returning here if either A or B is NOT a constant range.

1041 ↗(On Diff #39625)

I was planning on fixing this in a follow on NFC change by making the function return void. Happy to tweak as suggested though.

reames updated this revision to Diff 39819.Nov 10 2015, 10:03 AM
reames edited edge metadata.

Fix Sanjoy's comment.

sanjoy added inline comments.Nov 10 2015, 10:31 AM
1019 ↗(On Diff #39819)

I was suggesting putting the return inside the if -- the rule I was suggesting was that if one of the values is not a ConstantRange and the other one isn't then return the one that is a constantrange. However, after re-reading the code it looks like you'll enter the if only with either two nonconstant s or one nonconstant and one constantrange. With that in mind, I'm not sure if my suggestion is actually useful -- both a constantrange and nonconstant are equally "good" I think.

1041 ↗(On Diff #39819)

Fixing as a follow on change is fine.

nlewycky added inline comments.Nov 10 2015, 2:02 PM
351 ↗(On Diff #39819)

Remove extra space after 'dbgs'

991–995 ↗(On Diff #39819)

Optional: You could return a single definition of the constant 'undef'?

997–1007 ↗(On Diff #39819)

I think that if it's undefined, that means that "there exists no definition for this value", and that's stronger than all other possibilities. I think if it's proven to be undefined by any means, you should return undefined.

1009–1010 ↗(On Diff #39819)

Optional: Well, you can still rank constants. ConstantExpr is worse than ConstantInt is worse than Undef.

(Actually, there's something even more interesting here which is that constant A must equal constant B, which might be something nobody else has figured out yet. GVN would like to know.)

1052 ↗(On Diff #39819)

One dot or three, never two.

reames added inline comments.Nov 16 2015, 2:43 PM
991–995 ↗(On Diff #39819)

I'm really trying to avoid changing fundamentals of the lattice with this change. If you think this is a valuable enhancement given discussion below, let me know and I'll consider a future patch.

997–1007 ↗(On Diff #39819)

I think the interpretation you're giving is a reasonable one, but it's not clear to me that's what is currently implemented in LVI. I can't find a counter example, so I'm willing to do this, but would you mind if I submitted this change as is, then followed with a separate change to invert the handling for undefined and clarify the comments? I'd like to isolate any breakage into an easy to revert patch. I also think the diff will be fairly large without adding much value in understandability to the current patch.

1009–1010 ↗(On Diff #39819)

While interesting, this would be a fundamental change to the nature of the lattice. We'd effectively be increasing it's height by the number of constant types. Without a clear motivating example, I'd rather not go here.

1052 ↗(On Diff #39819)

Will fix.

reames updated this revision to Diff 46586.Feb 1 2016, 4:10 PM

Updated patch w/Nick's comments -- the key point I was confused about is that the previous code implicitly treated the result on the edge as overdefined without ever explicitly making it so. Adding that explicit step and then updating the intersect logic makes things far more clear.

nlewycky added inline comments.Feb 1 2016, 5:02 PM
357 ↗(On Diff #46586)

Please fix the extra space after 'dbgs'

1055–1058 ↗(On Diff #46586)

Optional: I'd reorder this test first on the grounds that it should be much more likely.

1090 ↗(On Diff #46586)

A period at the end please.

1105–1107 ↗(On Diff #46586)

If using Undefined here doesn't work today, please file a PR and link to that PR from here. It has to be a bug, right?

2–3 ↗(On Diff #46586)

Can you check anything positive about the results, that we did or didn't fold away branches or comparisons maybe?

2 ↗(On Diff #46586)

Extra newline.

13 ↗(On Diff #46586)

Could you add a CHECK line which shows that this happened? The presence of a branch to the backedge isn't entirely clear.

reames updated this revision to Diff 46600.Feb 1 2016, 5:23 PM

Update per Nick's comments.

nlewycky accepted this revision.Feb 1 2016, 7:14 PM
nlewycky edited edge metadata.


This revision is now accepted and ready to land.Feb 1 2016, 7:14 PM
This revision was automatically updated to reflect the committed changes.