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 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.
Created attachment 3915 [details] edge order passes proof of concept I disagree that we should store the use-list orderings in the .bc and .ll files. I do agree that there is a distinct need to have access to this data for testcases and whatnot. I also think that we should be able to write passes that are idempotent across changes to the order of the use-list, like we write passes which work the same regardless of the memory addresses. 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. [1]: http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20140728/228763.html r213824 = 5667cf2fef6816bb384c36464938608051a1b7c9 r213836 = 117dff7bd2574e5a0b2571a78fd8159ec4d92650 r213866 = 6d469808a046185a46ec8790f3a104c47ffa6c66 r213945 = cb9adb363fad8d9e82dbd323470b91852d299cf5 r213946 = d8d3b4dc61004dd1d5f6d868c54b02a65c7b08e5 r213947 = deb8e3091302f7f62fadc939575f561c7d44f9d0 r213953 = 17cb4cb5a37dddf858629ea0181179acaf8c695f r213957 = 2602b66b91ee31362fac5e9dce31b22b9596dab8 r214121 = 31e6dbfd54acec83afffb12798eb389fc1c96a58 r214122 = beb0ac53644cdddd95e819440c83d7d6eaff27c7 r214123 = 0aed6e729d9d200e26391594cc7e3b07cff8836f r214125 = bd24fe8c7e8038fe53accad67c480875f87df2a8 r214128 = 8a4d11e412f44716a828905ed3454e9188d24d70 r214135 = f575ec435eba0a92d4ef748e4b4e8a71aa9a05c4 r214144 = a784589f579de6f8a34e6bbfcf48ebba6b01c719 r214155 = 2c9dac0c3aa60fc8700803ce933808d0c4722ecf r214156 = 15f92a3a7d2a94ceb527d6592a81951f1e3df538 r214157 = 994af148ca788984dff71afcdfca99e388325973 r214184 = 34fa69757f152e8a4e3b774d0118f4cd21ec5f75 r214187 = 52f23be0802aa01569c0e6870774ac4b5b9c23f8 r214212 = 49d1690338625db91d2c7f717e5e41500c23a3d3 r214213 = bcb3a4189116b038940031d69356439e64bbf20c r214224 = f80532597ccf7ee435abbf7f4c14684d6b37cf41 r214241 = abf3c77acb51c5dac5f349fa9893da7b144906f7 r214242 = 9b9c19509fc7eb63f023915aaad063ebe1953d15 r214243 = 04bcdf16a90678249d10cd517eed8a966af5508c r214249 = 70fec687442b2cbd56baeec31fd504020723377d r214260 = 56a165cc96fb213d635beb86917f714516365a4e r214264 = f8b862d87c14217d3038cb053917987730f9efcc r214270 = c128f3b34ceac52bd3b0e2473dbb2b27a0091fbf r214271 = cd29d802047b018f77ebbd0cdadfa41911036cdf r214313 = e188fa672bc2d8ab999971826c4d9f3b11bd8c8e r214317 = 4a9efdaf9fc21a810e9bd9b85f92bf964ff46df7 r214318 = 89c4197256acd0fa340aa9657f167152f8c3f7be r214320 = 8dc3e30075926ac2ed921ba1acb2b38e7ef88102 r214321 = 43b54db2a4db4648441f2887f4fb02412b815981 r214365 = d321cdfc1cb4a4380ba4a1c5e14f8481eb2d6bcc r214368 = e5ae09b08fdcbfd2440d527e64d805c915f4ee41 r214417 = 9d65d3717c184449f4417bc5639e5f7513017c0e r214419 = 94f7c7aeaa1821c657c57926c67ee691c007fe43 r214556 = 2e9b60aea8c9a6a46cc35bf4c3b82d875ef2c750 r214558 = fc15e8a60f93f3e2a2075324c238e65754c5c6e7 r214559 = cf8b959e8d938d39c0899365d98426cdbd96ed93 r214563 = 865919d60d0cd05f97f5762b505b0c3b92aeedf7 r214570 = 147851ef9d11173c012217511be257ebefe695c4 r214581 = 15262784434ada50aeb5f8474b880ce5d672fb0e r214584 = 7df1db57b3ae35afcc1df648f1446b7c7b60993b r214587 = 236c1ac873be983ccde36bc8af049e48ce40b50c r214592 = b2b0ad4c75ce683da6f92de378c1c3422fc938a9 r214594 = 99a43c2c4251ca4f67058695a165353588131791 r214595 = 4277019a753ac6efbd1c4d5c9908f10f9404f697 r214596 = 1d3169155bcdf072f007edf6d909f476d95ca7da
LTO bitcode from tablegen (7.2MB) passes verify-uselistorder (with the global ctors patch [1] applied). [1]: http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20140728/228763.html
I turned this on by default in r234510, then reversed course [1] with r234919, r234920 (clang), and r234921. Also cleaned up the output of `verify-uselistorder` in r234929. Now it's on by default for `clang -save-temps`, `clang -emit-llvm`, and for all the LLVM tools I found that output bitcode. [1]: http://lists.cs.uiuc.edu/pipermail/llvmdev/2015-April/084468.html