This is an archive of the discontinued LLVM Phabricator instance.

[ValueLattice] Add singlecrfromundef lattice value.
ClosedPublic

Authored by fhahn on Mar 9 2020, 6:11 AM.

Details

Summary

This patch adds a new singlecrfromundef lattice value, indicating a
single element constant range which was merge with undef at some point.
Merging it with another constant range results in overdefined, as we
won't be able to replace all users with a single value.

This patch uses a ConstantRange instead of a Constant*, because regular
integer constants are represented as single element constant ranges as
well and this allows the existing code working without additional
changes.

Diff Detail

Event Timeline

fhahn created this revision.Mar 9 2020, 6:11 AM
Herald added a project: Restricted Project. · View Herald TranscriptMar 9 2020, 6:11 AM
Herald added a subscriber: hiraditya. · View Herald Transcript
nikic added a comment.Mar 9 2020, 1:44 PM

Same comment as on D75055: For LVI we don't guarantee that all uses of the value will be replaced, so this does not seem like a completely fix. I'm generally not really clear on how this differs from the variant implemented in D75055 (is it is just a matter of style, i.e. making this explicit, or is there a functional difference here?)

fhahn added a comment.Mar 9 2020, 3:24 PM

Same comment as on D75055: For LVI we don't guarantee that all uses of the value will be replaced, so this does not seem like a completely fix.

Yes that is an additional issue that needs to be addressed in LVI and/or its clients. This patch (and the preceding one) are a first step towards fixing the underlying issue in ValueLattice. Once those are addressed, we can fix the code in LVI.

I'm generally not really clear on how this differs from the variant implemented in D75120 (is it is just a matter of style, i.e. making this explicit, or is there a functional difference here?)

Sorry for the confusion. This patch and D75120 complement each other and both are needed. D75120 introduces a state for actual undef values and separates the notion of value we know nothing about yet and values we know are undef. This patch introduces a state for constants that started out as undef values or were merged with undef values. Such constants cannot safely be merged with other constant ranges.

efriedma accepted this revision.Mar 11 2020, 10:22 AM

LGTM, with some updates to the comments.

llvm/include/llvm/Analysis/ValueLattice.h
31–37

I think it would make sense to list out the possible state transitions for each state here.

71

I would prefer to say something like "This Value contains a single element constant range that was merged with an Undef value".

This revision is now accepted and ready to land.Mar 11 2020, 10:22 AM
efriedma added inline comments.Mar 11 2020, 10:29 AM
llvm/include/llvm/Analysis/ValueLattice.h
61

Sort of a side-question while I'm here, but how are we inferring notconstant? Is the inference safe in the presence of undef?

fhahn updated this revision to Diff 249724.Mar 11 2020, 12:23 PM

Thank you very much for taking a look!

Update wording around singlecrfromundef as suggested, document allowed follow-on states.

fhahn marked 2 inline comments as done.Mar 11 2020, 12:25 PM
fhahn added inline comments.
llvm/include/llvm/Analysis/ValueLattice.h
31–37

Done! Is the format along the lines you imagined? It does not list explicitly that we can stay in the existing state, if nothing changes.

fhahn marked an inline comment as done.Mar 11 2020, 12:26 PM
fhahn added inline comments.
llvm/include/llvm/Analysis/ValueLattice.h
61

I've responded in D75120

efriedma added inline comments.Mar 11 2020, 12:58 PM
llvm/include/llvm/Analysis/ValueLattice.h
31–37

Yes, this format looks fine.

For unknown specifically, probably you could just say "transition allowed to any state".

44

Is there actually a transition from undef -> constant?

61

I guess my concern is really, does "notconstant" imply that we've proven the value isn't undef? It would probably be worth stating that explicitly.

fhahn updated this revision to Diff 250365.Mar 14 2020, 9:47 AM

Rebase after recent changes landed.

fhahn marked 4 inline comments as done.Mar 15 2020, 4:35 AM
fhahn added inline comments.
llvm/include/llvm/Analysis/ValueLattice.h
44

Yes it is allowed in mergeIn(), which also ensures going to overdefined if we merge a constant with a different constant.

61

Right, notconstant (undef) is not allowed. I'll state that explicitly.

This revision was automatically updated to reflect the committed changes.
fhahn marked an inline comment as done.
efriedma added inline comments.Mar 16 2020, 12:03 PM
llvm/include/llvm/Analysis/ValueLattice.h
44

Oh, I see. It's probably worth calling out in the documentation for constant: it might actually come from an undef/constant merge, like singlecrfromundef. (I don't think it has any practical impact at the moment, but it could matter in the future.)

fhahn marked an inline comment as done.Mar 17 2020, 7:33 AM
fhahn added inline comments.
llvm/include/llvm/Analysis/ValueLattice.h
44

Should be added in 873ab73db477