This is an archive of the discontinued LLVM Phabricator instance.

[ValueLattice] Merging a constant range with undefined is overdefined.
AbandonedPublic

Authored by fhahn on Feb 24 2020, 8:15 AM.

Details

Summary

When merging a non-singleton constant range with undefined, we have to
go to overdefined. For constant ranges, we cannot guarantee that we will
be able to replace all uses of the underlying value which could lead to
contradictions with other transforms/analysis.

Note that we still cannot go to overdefined when merging undefined and a
constant range, because we initially create all elements as undefined.
But that should be fine, because that should only happen when setting
the initial concrete value.

Fixes PR44949.

Even though this might slightly pessimizes the analysis, if the
undefined value is truly not reachable, but the impact in practice seems
relatively low. I've built MultiSource, SPEC2000, SPEC2006 with -O3 +
LTO and collected the number of times CVP fired using

cat result.json | grep correlated | cut -d" " -f 10 | cut -d',' -f 1 | awk '{s+=$1} END {print s}'

Without this patch: 158985
With this patch: 158957

Alternatively we could force undef constants to overdefined (as
suggested by @efriedma in D61314) or replace the undefs in the IR with
other constants.

Diff Detail

Event Timeline

fhahn created this revision.Feb 24 2020, 8:15 AM
Herald added a project: Restricted Project. · View Herald TranscriptFeb 24 2020, 8:15 AM
Herald added a subscriber: dexonsmith. · View Herald Transcript
nikic added inline comments.Feb 24 2020, 9:40 AM
llvm/include/llvm/Analysis/ValueLattice.h
261

I don't think this reasoning holds up for LVI. While we *could* replace all uses, nothing actually forces consumers of LVI to do so. And in practice, I don't believe that either JumpThreading or CVP will replace all constant lattice values. JT only looks at br/switch and CVP mostly does range-based simplifications.

llvm/test/Transforms/CorrelatedValuePropagation/merge-range-and-undef.ll
2

Can you please pre-commit, so diffs are visible here?

wmi added a subscriber: wmi.Feb 24 2020, 11:29 AM
fhahn planned changes to this revision.Feb 24 2020, 11:52 AM
fhahn marked an inline comment as done.
fhahn added inline comments.
llvm/include/llvm/Analysis/ValueLattice.h
261

Ah right, we might have to convey if folding will happen or not.

uenoku added a subscriber: uenoku.Feb 25 2020, 7:52 AM
fhahn abandoned this revision.Mar 9 2020, 3:14 PM

This is superseded by D75120 (and the linked follow-up patch), which is a more complete approach.