This is an archive of the discontinued LLVM Phabricator instance.

[IPSCCP] Do not zap return if the return value is overdefined at any call site.
AbandonedPublic

Authored by fhahn on Jul 16 2018, 9:47 AM.

Details

Summary

We cannot zap a return if the return value at any of the function's call
sites is overdefined. This can happen, for example, when the return
value is used as a condition on for a branch and the return value is
still unknown when the branch is visited during ResolvedUndefsIn(). Then
the return value of the call site will be force to false.

Alternatively, we could mark functions as 'do not zap' if we go to
overdefined when handling call instructions, but the current approach
seems more direct.

In general, it is unfortunate that we fail to do the optimal thing
here. I guess we could force the return value to the known constant
after solving to at least replace the uses, but this seems like a slight
hack without much benefit.

Diff Detail

Event Timeline

fhahn created this revision.Jul 16 2018, 9:47 AM

Stuff like this really makes me want to kill off ResolveUndefsIn. But this works for now.

lib/Transforms/Scalar/SCCP.cpp
2021

I think cast<Instruction>(U) will fail if there's a BlockAddress user of F.

fhahn added a comment.Jul 16 2018, 3:01 PM

Stuff like this really makes me want to kill off ResolveUndefsIn. But this works for now.

Yeah I guess if we continue to make SCCP more powerful, we hit more cases like this. For example, the problem was exposed by rL336098. I am not sure what a good alternative to ResolvedUndefsIn() would be. Just marking undef conditions as overdefined after a round of Solve()? I am not sure how big the ResolvedUndefsIn contributes to the overall precision.

Thought about it a bit more, came up with an alternative fix: https://reviews.llvm.org/D49408. It's a bit more aggressive, and avoids the weirdness of calling markForcedConstant on an arbitrary value.

Just marking undef conditions as overdefined after a round of Solve()?

I'm not completely sure.

The academic algorithm for SCCP has three lattice states. The first state, there's no viable path to execute the instruction producing the value ("undef"). The second state, all viable paths produce the same value ("constant"). The third state, there are multiple possible values ("overdefined").

The LLVM version essentially tries to incorporate a fourth state: the instruction executes, but the result is the LLVM value "undef", so we can choose a constant to replace it later. But the implementation is awkward because the lattice doesn't represent the difference between this state and the "undef" state, and we try to fix it up later in ResolveUndefsIn. I think we should fix the lattice to represent this explicitly: "undef" should be split into "dead" and "indeterminate". (This would probably allow SCCP to find more constants, because we wouldn't need to ResolvedUndefsIn on dead instructions.) If we do that, though, I guess we have to continue using something like ResolvedUndefsIn; but at least it would be more clear why it's necessary.

FWIW, my take is that we should kill ResolvedUndefsIn (as already pointed by Eli, and probably me, and others in the past).
My take is that the benefit of having a forth lattice state is really little compared to the amount of effort we had to put to fix bugs.
If somebody is willing to take the time to do the work I'd rather zap away undef from the lattice and see how many constant we lose (and what's the runtime cost). But I understand this is a fair amount of work. That said, I think I like Eli's proof of concept a little better than this, so I'm happy if you want to pursue that path, Florian.

fhahn added a comment.Jul 17 2018, 7:11 AM

Thought about it a bit more, came up with an alternative fix: https://reviews.llvm.org/D49408. It's a bit more aggressive, and avoids the weirdness of calling markForcedConstant on an arbitrary value.

Great, I think back-propagating false to the condition is the biggest troublemaker, responsible for this bug and also D48327, so getting rid of it is great. And D49408 solves both problems.

fhahn abandoned this revision.Jul 19 2018, 1:55 AM

Abandoned in favor of D49408