bitcode files do not preserve order of use lists #6052
Comments
|
assigned to @dexonsmith |
|
The critical edge splitting in PHIElimination should be independent of block ordering, except for the numbering of the new blocks. The numbering is used as a third-level sorting key by the copy coalescer, so you could get different results there. I have experimented with removing edge splitting completely from CodeGenPrepare. It mostly works, except for a few test cases whose performance suffer. But it is probably difficult to be completely order independent, so your suggestions are good. |
|
edge order passes proof of concept I've written a patch which creates lib/Transforms/IPO/EdgeOrder.cpp that provides three passes. The first is -scramble-edges which runs std::random_shuffle over the ordering of the use-list for every value. Every pass (and .bc and .ll output) should behave the same when -scramble-edges is inserted. The other two passes load and save use list ordering information to disk. They do this with a modified ValueEnumerator that assigns the same numbers to all reachable Values, even across .bc boundaries. You can run 'opt -edge-order-outfile=filename -save-edge-order' to produce a use-list information file and 'opt -edge-order-infile=filename -load-edge-order' to load it back in. Now please understand, this patch is ONLY a proof of concept. It's ugly, it violates LLVM style, it's not factored properly, its file format is stupid, etc. Please PLEASE please understand ALL of the XXX comments in EdgeOrder.cpp before trying to use it. One final thing: in an average Module there are users which don't exist in the .bc file. The bitcode reader may create ConstantExpr's (that use GlobalValues) which don't end up in the final Module. This means that you can't preserve them in a .bc file, at least not without doing something more drastic. See the comments about GV->removeDeadConstantUsers() in the patch. |
|
Dependence on use list order is very pervasive throughout the compiler, for example, the order of pred_iterator depends on it. It is deterministic and not a problem, except that it doesn't get serialized out. |
|
I'm actively investigating this now, and just posted a summary of my current understanding (and plan) to llvmdev: http://lists.cs.uiuc.edu/pipermail/llvmdev/2014-July/074966.html |
|
The bitcode side of this is in tree and working (commits to date at the end of this comment), save for one patch that's under review 1. Need to do some profiling, but otherwise this looks done. r213824 = 5667cf2fef6816bb384c36464938608051a1b7c9 |
|
LTO bitcode from tablegen (7.2MB) passes verify-uselistorder (with the global ctors patch 1 applied). |
|
I turned this on by default in r234510, then reversed course 1 with r234919, r234920 (clang), and r234921. Also cleaned up the output of |
…e1b2b4ecf4cd658019d867 [lldb] Re-enable xmm/ymm/zmm tests with the system debugserver
Extended Description
The order of entries in use lists is deterministic but that order is not preserved in bitcode files. Serializing/deserializing the IR to a bitcode file in between passes may change the behavior of those passes if they depend on the order of use lists. This is a problem for bugpoint and for manual debugging as well.
I ran into this while trying to track down a performance problem in llvm-gcc. Writing a bitcode file and running llc produced slightly different results that prevented me from reproducing the performance issues. I tracked this down to CodeGenPrepare splitting critical edges by iterating over the basic block predecessor list and selecting the first suitable edge to split. The order of predecessors was different in llc than in llvm-gcc, which caused a different edge to be split. The problem applies to all use lists, not just basic block predecessors.
It would be good to add information to the bitcode files to preserve the use list order, at least as an option for debugging.
It would also be good to have a way to keep that same information in llvm assembly files so that disassembling a bitcode file preserves the information.
The text was updated successfully, but these errors were encountered: