Page MenuHomePhabricator

[ValueLattice] Add new state for undef constants.
ClosedPublic

Authored by fhahn on Feb 25 2020, 8:00 AM.

Details

Summary

This patch adds a new undef lattice state, which is used to represent
UndefValue constants or instructions producing undef.

The main difference to the unknown state is that merging undef values
with constants (or single element constant ranges) produces the
constant/constant range, assuming all uses of the merge result will be
replaced by the found constant.

Contrary, merging non-single element ranges with undef needs to go to
overdefined. Using unknown for UndefValues currently causes mis-compiles
in CVP/LVI (PR44949) and will become problematic once we use
ValueLatticeElement for SCCP.

Diff Detail

Event Timeline

fhahn created this revision.Feb 25 2020, 8:00 AM
Herald added a project: Restricted Project. · View Herald TranscriptFeb 25 2020, 8:00 AM
Herald added a subscriber: hiraditya. · View Herald Transcript

I'm not quite sure the merge function here is right. I think constant_merged_with_undef has to be a different state from constant. It's basically the same as constant, except that merging it with a different constant or constantrange produces overdefined.

llvm/lib/Transforms/Scalar/SCCP.cpp
439

Not sure about this change; do we not need to markUndef?

fhahn added a comment.Feb 26 2020, 9:32 AM

I'm not quite sure the merge function here is right. I think constant_merged_with_undef has to be a different state from constant. It's basically the same as constant, except that merging it with a different constant or constantrange produces overdefined.

Yes it still misses that case. I see it as the first step of the transition. To address the undef -> constant -> constant range merge issue there are a few options I think:

  1. let caller deal with it, e.g. by passing in whether one of the merge operands is undefined.
  2. Differentiate between constants that started out as undefined in ValueLattice, e.g. by adding another state like constant_from_undef (that would be a bit like forcedconstant, with the difference being that it cannot be marked as a different constant - which would go to overdefined for forced constant) or by using undefined + Constant pointer set.

Maybe there are other options? What would your preference be?

fhahn marked an inline comment as done.Feb 26 2020, 9:48 AM
fhahn added inline comments.
llvm/lib/Transforms/Scalar/SCCP.cpp
439

markConstant used to be a no-op for UndefValue constants. I've updated it to use markUndefined for UndefValue constants, it might be clearer to do it explicitly here though?

If you don't have all the relevant states represented in the ValueLattice, where are you storing the "possibly undef" bit? I think having all the states in the ValueLattice is simpler, at least conceptually.

llvm/lib/Transforms/Scalar/SCCP.cpp
439

Oh, right, that makes sense.

And yes, I guess the new lattice state is very similar to the old forcedconstant. We could even port the various tricks involving arithmetic on undef from the old ResolveUndefsIn.

wmi added a subscriber: wmi.Fri, Feb 28, 10:32 AM
fhahn added a comment.Wed, Mar 4, 2:32 PM

If you don't have all the relevant states represented in the ValueLattice, where are you storing the "possibly undef" bit? I think having all the states in the ValueLattice is simpler, at least conceptually.

Thanks Eli (and sorry for the late response, I somehow missed your response).

I *think* the callers of the mergeIn functions should the information, but I agree it would be much better to model it explicitly. I'll put up a patch soon.

fhahn updated this revision to Diff 249074.Mon, Mar 9, 6:12 AM

Rebased with additional tests, fix formatting.

fhahn added a comment.Mon, Mar 9, 6:20 AM

If you don't have all the relevant states represented in the ValueLattice, where are you storing the "possibly undef" bit? I think having all the states in the ValueLattice is simpler, at least conceptually.

I've put up a patch that adds a new lattice state for single element constant ranges that started out/merged with undef: D75845. I hope that's along the lines you suggested.

I worked on an SCCP test case for that, but the way we currently handle PHIs means we merge all incoming values in the existing state for a PHI, which means that if the result is a constant range and any operands is undef, we will merge CR & undef, going to overdefined.

With an additional patch skipping some unnecessary updates (D75846), I managed to get a SCCP test case (llvm/test/Transforms/SCCP/range-and-ip.ll) in D75845. There's also a test case that shows the issue with CorrelatedValuePropagation.

fhahn retitled this revision from [ValueLattice] Add new state for undef constants. (WIP) to [ValueLattice] Add new state for undef constants..
efriedma added inline comments.Wed, Mar 11, 10:33 AM
llvm/include/llvm/Analysis/ValueLattice.h
136

I'm not sure I understand how getNot(undef) is supposed to work.

293

We already checked RHS.isUnknown() earlier?

fhahn updated this revision to Diff 249702.Wed, Mar 11, 11:24 AM

Remove unnecessary RHS.isUnknown() check.

fhahn updated this revision to Diff 249718.Wed, Mar 11, 12:03 PM
fhahn marked 2 inline comments as done.

Add test case where LVI uses getNot(undef). Add comment it should be fine to assume undef from x != undef. Alive seems to agree (I would post a link, but rise4fun.com is terrible slow to respond)

fhahn marked an inline comment as done.Wed, Mar 11, 12:05 PM
fhahn added inline comments.
llvm/include/llvm/Analysis/ValueLattice.h
136

I think it should be fine to assume x != undef => undef. Alive seems to agree. Granted, it is probably not very useful. I tried to replace it with an assert ruling out undef here, but we hit this case in practice in LVI via JumpThreading.

293

Done, thanks! I've added an assertion to guard against accidentally breaking the assumption by changes.

nikic added inline comments.Wed, Mar 11, 12:41 PM
llvm/include/llvm/Analysis/ValueLattice.h
195

Nit: Should be markUndef() for consistency.

efriedma added inline comments.Wed, Mar 11, 12:56 PM
llvm/include/llvm/Analysis/ValueLattice.h
136

If you prove x != undef, x can't be any specific value... including undef, I think. So actually you could just treat it as unknown, I think?

fhahn updated this revision to Diff 249756.Wed, Mar 11, 2:20 PM

Rename markUndefined -> markUndef as suggested.

fhahn marked 2 inline comments as done.Wed, Mar 11, 3:38 PM
fhahn added inline comments.
llvm/include/llvm/Analysis/ValueLattice.h
136

Looking at the uses in LVI, it seems like it is used for information coming from things like %x = icmp ne %a, CONST; %y = select %x, %a, 10 and LVI would use getNot(CONST) and use that to mark %y as != CONST if 10 != Const . (https://github.com/llvm-mirror/llvm/blob/master/lib/Analysis/LazyValueInfo.cpp#L953)

I'm not sure if that allows saying that %a cannot be any specific value including undef, if CONST is undef. Couldn't the use in %a be any value, by choosing something like %a+1 for undef in the icmp?

Because IIUC we can only chose a single concrete value for the undef in the icmp per execution.

Another way to think about it might be a constant range with a single value missing. The missing value can be arbitrarily chosen per use/execution. I think what's allowed and dis-allowed would heavily depend on how it is used exactly. Maybe it would be best to start out with overdefined in this patch and refine it if required later on?

efriedma added inline comments.Wed, Mar 11, 5:00 PM
llvm/include/llvm/Analysis/ValueLattice.h
136

Oh, I see, code being analyzed is not actually assuming it like an llvm.assume; it's just using it in the condition of a select.

I guess that a == undef ? 0 : undef+1 is in fact undef... but I don't think that generalizes in any useful way to other places we might use getNot(). I'd prefer to explicitly bail out in LVI, as opposed to handling it here.

fhahn updated this revision to Diff 249957.Thu, Mar 12, 9:23 AM

Assert on getNot(undef), avoid in LVI.

fhahn marked an inline comment as done.Thu, Mar 12, 10:41 AM
fhahn added inline comments.
llvm/include/llvm/Analysis/ValueLattice.h
136

Sounds good! I've updated LVI to not use getNot for undef constants and added an assertion to getNot().

This revision is now accepted and ready to land.Thu, Mar 12, 12:45 PM
fhahn updated this revision to Diff 250363.Sat, Mar 14, 9:45 AM

Rebased after recent changes landed.

This revision was automatically updated to reflect the committed changes.