[LLVMdev] [RFC] Setting preserve-bc-use-list-order=true by default

[Duncan P. N. Exon Smith]

A while back I finished up some work [1] that Chad started to preserve
use-list-order in bitcode [2], hidden behind an "experimental" option
called `-preserve-bc-use-list-order`.  I then added a similar
`-preserve-ll-use-list-order` option for LLVM assembly [3].

[1]: http://lists.cs.uiuc.edu/pipermail/llvmdev/2014-July/074604.html
[2]: https://llvm.org/bugs/show_bug.cgi?id=5680
[3]: https://llvm.org/bugs/show_bug.cgi?id=20515

I'd like to move both of these options out of "experimental" mode, and
turn `-preserve-bc-use-list-order` on by default.  I've attached a patch
that does this.

Why?
====

Use-list order affects the output of some LLVM passes.  A typical
example is a pass that walks through basic block predecessors.  The
use-list order is deterministic, but not preserved when serializing the
LLVM IR to bitcode or assembly.

In rare (but frustrating) cases, this makes it difficult to reproduce a
crash or miscompile from an intermediate result.

For example, consider running an LTO build and serializing between the
LTO optimization pipeline and the LTO codegen pipeline.  On SPEC,
serializing to/from bitcode will change the output executable in 33
benchmarks.  If you use `-preserve-bc-use-list-order`, all executables
match.

How?
====

Have a look at `BitcodeReader::ParseUseLists()` and
`predictUseListOrder()` in `lib/Bitcode/Writer/ValueEnumerator.cpp`.

Does it degrade smoothly if IR changes?
=======================================

Yes.  If a `Value`'s use-list has changed in size (e.g., because of
bitcode upgrades), its use-list order record is ignored.

What does it cost?
==================

Manman collected a bunch of numbers, with `-preserve-bc-use-list-order`
and `-preserve-ll-use-list-order` both turned on:

  - Time increase on LTO build time: negligible.
  - Filesize increase in bitcode files output by `clang -flto`:
      - clang: 6.8556% (sum when from 310412640 to 331693296 bytes).
  - Filesize increase in merged bitcode files (output of
    `ld -save-temps` when using `clang -flto` on Darwin).
      — SPEC: 5.24% to 23.4% increase in file size.
      — clang and related tools: 0.83% to 9.19% (details in
        filesize_clang.txt, attached).
  - Time increase of running `llvm-dis` on merged bitcode files:
      — 6.4% to 15% on SPEC benchmarks with running time >= 1 second.
      — 7.9% to 14.5% on clang with running time >= 1 second (details in
        dis_clang.txt, attached).
  - Time increase of running `llvm-as` on merged bitcode files:
      — 3.5% to 39% on SPEC benchmarks with running time >= 1 second.
      — 14.7% to 24.5% with running time >= 1 second (details in
        as_clang.txt, attached).

Does it work?
=============

Manman also ran `verify-uselistorder` (a use-list fuzzer that shuffles
use-lists, serializes IR, compares use-lists, rinses, repeats), on the
merged bitcode files above.  After I fixed a bug in assembly
serialization in r232200, they all come up clean.

Why leave -preserve-ll-use-list-order=false by default?
=======================================================

Firstly, our practise is to error on mismatches in LLVM assembly (unlike
bitcode where we upgrade or drop old formats).  Printing use-list
directives by default would make it almost impossible to update an
assembly file by hand without stripping out the directives.

Secondly, use-list order is encoded as a "shuffle", which isn't
human-friendly.  I'm not convinced this adds value to textual IR except
in rare cases where a developer actually wants to see the order, or
wants to try to make a change without perturbing the use-lists.

Nevertheless, the option works.  An LLVM developer can turn it on and
hack at the IR, and `llvm-as` will complain if the developer makes the
`uselistorder` directives inconsistent.  The developer can choose
whether to delete the mismatched directives or to update them.


-------------- next part --------------
A non-text attachment was scrubbed...
Name: use-list-order.patch
Type: application/octet-stream
Size: 818 bytes
Desc: not available
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150331/a84886c5/attachment.obj>
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: filesize_clang.txt
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150331/a84886c5/attachment.txt>
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: dis_clang.txt
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150331/a84886c5/attachment-0001.txt>
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: as_clang.txt
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150331/a84886c5/attachment-0002.txt>