Page MenuHomePhabricator

[SCEV] Use wrap flags in InsertBinop
ClosedPublic

Authored by samparker on May 15 2019, 1:49 AM.

Diff Detail

Repository
rL LLVM

Event Timeline

samparker created this revision.May 15 2019, 1:49 AM
jdoerfert added inline comments.
lib/Analysis/ScalarEvolutionExpander.cpp
753 ↗(On Diff #199563)

Why is this happening only at the end? A SCEVAdd <nsw>(a+b+c) should have two <nsw> additions, right? Should we have the following code as a helper routine that is called after a new Sum was created?

I just realized, maybe my interpretation of SCEVAdd <nsw>(a+b+c) is wrong. Does it mean there is no intermediate overflow? In that case, the above might be what we want. If that is not the case, what does it mean?

754 ↗(On Diff #199563)

This makes implicit assumptions about the hierarchy. Could you (also) check isa<Instruction>?

nikic added a subscriber: nikic.Sun, Jun 2, 3:11 PM

It's not entirely obvious to me that this will be correct if an existing add instruction gets reused.

I think it might make more sense to pass nowrap flags to InsertBinop and integrate more tightly there, in particular see the TODO on canGeneratePoison. That is pick an existing instruction with right nowrap flags or insert a new one, but don't reuse an instruction while assigning different flags.

samparker updated this revision to Diff 202685.Mon, Jun 3, 3:40 AM
samparker retitled this revision from [SCEV] Add wrap flags while expanding Add to [SCEV] Use wrap flags in InsertBinop.

Thanks both, I've moved the logic into InsertBinop.

nikic added inline comments.Tue, Jun 4, 12:05 PM
lib/Analysis/ScalarEvolutionExpander.cpp
193 ↗(On Diff #202685)

I'd move the comment down to the corresponding branch.

865 ↗(On Diff #202685)

Should be FlagAnyWrap?

samparker marked an inline comment as done.Wed, Jun 5, 1:30 AM
samparker added inline comments.
lib/Analysis/ScalarEvolutionExpander.cpp
865 ↗(On Diff #202685)

Neither lshr or udiv wrap, they only support 'exact'.

samparker updated this revision to Diff 203103.Wed, Jun 5, 1:34 AM

Updated comments.

nikic added inline comments.Wed, Jun 5, 1:37 AM
lib/Analysis/ScalarEvolutionExpander.cpp
865 ↗(On Diff #202685)

Right, that's why you want to pass no flags here, which is what AnyWrap (=0) does. FlagNW is a different kind of nowrap flag that doesn't apply to udiv and has no IR representation anyway.

samparker marked an inline comment as done.Wed, Jun 5, 1:50 AM
samparker added inline comments.
lib/Analysis/ScalarEvolutionExpander.cpp
865 ↗(On Diff #202685)

Ah, okay, thanks!

samparker updated this revision to Diff 203104.Wed, Jun 5, 1:56 AM

Using FlagAnyWrap for lshr and udiv.

nikic added inline comments.Wed, Jun 5, 1:39 PM
test/Transforms/LoopIdiom/basic.ll
49 ↗(On Diff #203104)

This nuw flag seems dubious. Or maybe the whole transform is dubious. It's not immediately clear to me why it would be illegal to have a loop that clears a whole address space using say i16s and size half the address space. In that case this memset formation will go from clearing the address space to setting zero bytes. With the additional nuw flag it will be UB instead. But I don't think it's UB to pass a large size to this function in the first place. Am I wrong about that?

nikic accepted this revision.Wed, Jun 5, 1:56 PM

LGTM. The question regarding the memset transform still stands, but it's really an unrelated issue.

This revision is now accepted and ready to land.Wed, Jun 5, 1:56 PM
Closed by commit rL362687: [SCEV] Use wrap flags in InsertBinop (authored by sam_parker, committed by ). · Explain WhyThu, Jun 6, 1:53 AM
This revision was automatically updated to reflect the committed changes.
Herald added a project: Restricted Project. · View Herald TranscriptThu, Jun 6, 1:53 AM
samparker marked an inline comment as done.Thu, Jun 6, 2:08 AM
samparker added inline comments.
test/Transforms/LoopIdiom/basic.ll
49 ↗(On Diff #203104)

I agree, it looks wrong to me. I can't see how it's safe to double 'Size'.

samparker marked an inline comment as done.Thu, Jun 6, 5:29 AM
samparker added inline comments.
test/Transforms/LoopIdiom/basic.ll
49 ↗(On Diff #203104)

@echristo Looks like your test, so are you able to shed some light on this please?

reames added a subscriber: reames.Thu, Jun 6, 10:32 AM

Flags on SCEVs are valid for the current set of users that exist in the loop. If you add *new* users then those flags may no longer be valid. We recently ran into this in LFTR, and this patch seems likely to have the same risk. I have not audited the patch or its output to be sure, just throwing out a possibility.

Thanks Philip. This has been reverted, so something is wrong. I'm finding it difficult to wrap, pun intended, my head around how adding users affects the semantics of a given expression. Are they any reviews/threads that you could point me to?

nikic added a comment.Mon, Jun 10, 2:02 AM

Thanks Philip. This has been reverted, so something is wrong. I'm finding it difficult to wrap, pun intended, my head around how adding users affects the semantics of a given expression. Are they any reviews/threads that you could point me to?

It would be nice to find out what went wrong here. The issue Philip refers to is discussed in D60935, but I don't think it applies in this context. I would expect that the nowrap flags in SCEV are just wrong ... somewhere.

A suggestion on how to make progress here. Introduce the wrap flags to the API, but have *all* callers pass AnyWrap. That must be NFC.

Then land each API usage one by one. (Without separate review is fine, but let them sit for a day or two between commits.) Whichever one breaks is the problematic one, and you'll then know where to spend your debugging cycles.

llvm/trunk/lib/Analysis/ScalarEvolutionExpander.cpp
747

This particular pair of lines looks really suspicious. The flags which are correct on an add are very different from those valid on a subtract.

Consider:
add nsw i32 %a, -1
sub nsw nuw i32 %a, 1
OR
add nsw nuw i8 %a, 127 ;; %a must be zero
sub i32 %a, 128

Thanks @reames - this is the approach I will take and I'll pay particular attention to the add/sub case. I'll link the commits back to this review as I go.