This is an archive of the discontinued LLVM Phabricator instance.

[BasicAA] Fix zext & sext handling
ClosedPublic

Authored by njw45 on Dec 16 2014, 9:27 AM.

Details

Summary

There are several unhandled edge cases in BasicAA's GetLinearExpression method. This changes fixes outstanding issues, including zext / sext of a constant with the sign bit set, and the refusal to decompose zexts or sexts of wrapping arithmetic.

Diff Detail

Event Timeline

njw45 updated this revision to Diff 17339.Dec 16 2014, 9:27 AM
njw45 retitled this revision from to wip.
njw45 updated this object.
njw45 edited the test plan for this revision. (Show Details)
njw45 retitled this revision from wip to [BasicAA] Fix zext & sext handling.Dec 22 2014, 3:54 PM
njw45 updated this object.
njw45 edited the test plan for this revision. (Show Details)

I think this is moving in the right direction.

lib/Analysis/BasicAliasAnalysis.cpp
219

nsw -> NSW, nuw -> NUW as per the coding convention.

335

And, generally speaking, you should clang-format the patch.

1189

Can you move this into a separate function?

njw45 added a subscriber: Unknown Object (MLST).Dec 30 2014, 5:41 AM

Hi @hfinkel - I've made the fixes you suggested and have added a couple more comments. Thanks -

Nick

hfinkel added inline comments.Jan 9 2015, 6:15 AM
lib/Analysis/BasicAliasAnalysis.cpp
233

Why do we always zero-extend here? Why not sign extend? There should at least be a comment explaining this.

243

You might want to add "see below" or some other hint to where this happens.

335

this -> This

338

we -> We

njw45 added a comment.Jan 16 2015, 9:25 AM

Thanks for the review, @hfinkel - I've updated the commit.

hfinkel accepted this revision.Feb 8 2015, 10:14 AM
hfinkel added a reviewer: hfinkel.

LGTM, thanks!

This revision is now accepted and ready to land.Feb 8 2015, 10:14 AM
njw45 added a comment.Apr 5 2015, 4:34 PM

Sorry I dropped the ball on this - could you commit it for me as I still
don't have commit access? Thanks -

Nick

sanjoy added a subscriber: sanjoy.Apr 5 2015, 7:15 PM

Some drop-by-comments inline in case you find them useful. I see this patch has been LGTM'ed so feel free to ignore. :)

lib/Analysis/BasicAliasAnalysis.cpp
335

I'm not sure I understand the comment -- this clause looks like it is implementing sext(sext(X,a),b) == sext(X, a + b).

340

Why is the .zextOrSelf(OldWidth) or the .trunc(SmallWidth) needed? Isn't OldWidth always equal to SmallWidth?

1000

Do you mean i3? Additions in i8 are modulo 256.

1004

Minor: APIntOps::umin may be clearer here.

Some drop-by-comments inline in case you find them useful. I see this patch has been LGTM'ed so feel free to ignore. :)

No, that's not how things work. All comments need to be addressed. Pre- or post-commit.

In any case, this patch needs to be rebased because it no longer applies cleanly to trunk.

njw45 updated this revision to Diff 24546.Apr 28 2015, 6:25 AM
njw45 edited edge metadata.

[BasicAA] Fix zext & sext handling

There are several unhandled edge cases in BasicAA's GetLinearExpression method. This changes fixes outstanding issues, including zext / sext of a constant with the sign bit set, and the refusal to decompose zexts or sexts of wrapping arithmetic.

njw45 added a comment.Apr 28 2015, 6:36 AM

@sanjoy - thanks for the review; bugs in this class are rather hard to track down as they only really manifest themselves in later optimisations, so more eyes are definitely appreciated :). I've replied to all your comments in-line - let me know if anything's not clear.

Nick

lib/Analysis/BasicAliasAnalysis.cpp
335

My latest commit adds more comments to make this clearer - does that explain it well enough?

340

This method can call itself recursively, and so the operator width reduces as we look through zexts + sexts, but the offset always stays at the initial width.

1000

You're right - and I've added several unit tests prefixed "constantOffsetHeuristic_" to q.bad.ll to explore this behaviour (and to verify that I'm picking the right scales to multiply by in the heuristic).

1004

Thanks - code reviews are one of the best ways to discover new utility functions in the codebase :)

njw45 updated this revision to Diff 24549.Apr 28 2015, 7:16 AM

Remove dead code left from testing

njw45 added a comment.May 5 2015, 8:43 AM

Hi Sanjoy - have you had a chance to look at this yet? Thanks -

Nick

sanjoy accepted this revision.May 6 2015, 7:15 PM
sanjoy added a reviewer: sanjoy.
sanjoy added inline comments.
lib/Analysis/BasicAliasAnalysis.cpp
284

Note that currently in the LangRef, shl nsw X, Y is not the same as mul nsw X (1 << Y), the LangRef has a bug in this regard. David has an out of tree patch to fix this http://reviews.llvm.org/D8890 but meanwhile you might want to not propagate nuw and nsw for shifts.

337

Very minor, but I think it will be clearer if you just add an annotation to each branch of the if statement:

if (is<SEXtInst>(V) && ZExtBits == 0) {
  // sext(sext(A)) == sext(A)

etc. instead of a comprehensive meta comment.

njw45 updated this revision to Diff 25231.May 7 2015, 1:55 PM
njw45 edited edge metadata.

Address review comments

njw45 added a comment.May 7 2015, 1:57 PM

Hi @sanjoy - I've revised the patch to incorporate your suggestions. Is it OK now? Thanks -

Nick

lib/Analysis/BasicAliasAnalysis.cpp
284

That's interesting - I've added an early escape for the Shl that sets NSW & NUW to false in the latest version of this patch so they won't be propagated.

337

I've changed this in my latest revision of this patch.

sanjoy added a comment.May 7 2015, 2:01 PM

LGTM, please check in.

njw45 added a comment.May 8 2015, 11:18 AM

Thanks @sanjoy - however I don't have commit rights to the repo so could you (or @hfinkel) commit it for me? Thanks -

Nick

I'll take care of it.

This revision was automatically updated to reflect the committed changes.