This is an archive of the discontinued LLVM Phabricator instance.

Improve the determinism of MergeFunctions
ClosedPublic

Authored by jrkoenig on Aug 19 2015, 2:59 PM.

Details

Summary

Merge functions previously relied on unsigned comparisons of pointer values to
order functions. This caused observable non-determinism in the compiler for
large bitcode programs. Basically, opt -mergefuncs program.bc | md5sum produces
different hashes when run repeatedly on the same machine. Differing output was
observed on three large bitcodes, but it was less frequent on the smallest file.
It is possible that this only manifests on the large inputs, hence remaining
undetected until now.

This patch fixes this by removing (almost, see below) all places where
comparisons between pointers are used to order functions. Most of these changes
are local, but the comparison of global values requires assigning an identifier
to each local in the order it is visited. This is very similar to the way the
comparison function identifies Value*'s defined within a function. Because the
order of visiting the functions and their subparts is deterministic, the
identifiers assigned to the globals will be as well, and the order of functions
will be deterministic.

With these changes, there is no more observed non-determinism. There is also
only minor slowdowns (negligible to 4%) compared to the baseline, which is
likely a result of the fact that global comparisons involve hash lookups and not
just pointer comparisons.

The one caveat so far is that programs containing BlockAddress constants can
still be non-deterministic. It is not clear what the right solution is here. In
particular, even if the global numbers are used to order by function, we still
need a way to order the BasicBlock*'s. Unfortunately, we cannot just bail out
and fail to order the functions or consider them equal, because we require a
total order over functions. Note that programs with BlockAddress constants are
relatively rare, so the impact of leaving this in is minor as long as this pass
is opt-in.

Diff Detail

Repository
rL LLVM

Event Timeline

jrkoenig retitled this revision from to Improve the determinism of MergeFunctions.
jrkoenig updated this object.
jrkoenig added reviewers: jfb, dschuff, nlewycky.
jrkoenig added subscribers: chapuni, llvm-commits.
jfb added inline comments.Aug 20 2015, 1:40 PM
lib/Transforms/IPO/MergeFunctions.cpp
159 ↗(On Diff #32622)

Use std::tie here, it'll make the code easier to read since you can name first and second: I had to look up insert's API to figure this out :-)

460 ↗(On Diff #32622)

?

484 ↗(On Diff #32622)

existant?

489 ↗(On Diff #32622)

Why not also compare min/max exponent here? It seems like you could add bool operator==(const fltSemantics&, const fltSemantics&) and use that?

616 ↗(On Diff #32622)

I think it would be worth renaming cmpStrings to cmpMem because that's what StringRef does: it ignores null-termination and does memcmp based on the declared size.

Could you also add a mergefuncs test that makes sure this is the case: two functions with ConstantDataArray (or vector) which have the same length, same prefix, a null byte, and then different tail. They shouldn't get merged with the current implementation.

690 ↗(On Diff #32622)

Can you cmpBasicBlocks?

695 ↗(On Diff #32622)

I think some MSVC versions are sad if you don't have a return here. It should be conservative, so not 0.

729 ↗(On Diff #32622)

Is TyR also known to be IntegerType here? I don't think it is.

731 ↗(On Diff #32622)

Same here.

998 ↗(On Diff #32622)

No comparison of getType and getFunctionType?

999 ↗(On Diff #32622)

Same on final return for MSVC.

jrkoenig marked 5 inline comments as done.

Addressed @jfb's comments.

lib/Transforms/IPO/MergeFunctions.cpp
460 ↗(On Diff #32622)

GlobalNumbers is not in scope. Moved this assertion to MergeFunctions, where it is in scope

484 ↗(On Diff #32622)

Extant is technically correct, but I changed it to existing :)

489 ↗(On Diff #32622)

I'll add APFloat::semanticsMaxExponent/MinExponent and use them here in another patch, as that will touch another file.

690 ↗(On Diff #32622)

No, cmpBasicBlocks will only verify that the instructions are the same, not that the two Block Addresses point to semantically identical code (because we also need to account for successor blocks). A full solution would do something like compare the functions, and if they are the same, compare the index of each basic block within the function in depth first proposal order.

729 ↗(On Diff #32622)

From right above the switch, TyL->getTypeID() == TyR->getTypeID(), otherwise the comparison would have have returned.

998 ↗(On Diff #32622)

Oh, I pulled in all the fields from llvm::InlineAsmKeyType, but the type is also used in the uniquing. Fixed.

jfb accepted this revision.Aug 21 2015, 2:05 PM
jfb edited edge metadata.

lgtm besides two nits.

test/Transforms/MergeFunc/constant-entire-value.ll
2 ↗(On Diff #32862)

Add a description of what this is doing (the 0 check isn't obvious).

22 ↗(On Diff #32862)

CHECK-NOT like this is usually done with a different RUN: opt ... line, which checks the entire file.

This revision is now accepted and ready to land.Aug 21 2015, 2:05 PM
jrkoenig edited edge metadata.

Made test more robust; added comment

dschuff accepted this revision.Aug 21 2015, 2:52 PM
dschuff edited edge metadata.
This revision was automatically updated to reflect the committed changes.