Added an API to check if an instruction can be safely moved before another instruction. In future PRs, we will like to add support of moving instructions between blocks that are not control flow equivalent, and add other APIs to enhance usability, e.g. moving basic blocks, moving list of instructions...
Loop Fusion will be its first user. When there is intervening code in between two loops, fusion is currently unable to fuse them. Loop Fusion can use this utility to check if the intervening code can be safely moved before or after the two loops, and move them, then it can successfully fuse them.
Details
Diff Detail
- Repository
- rG LLVM Github Monorepo
Event Timeline
llvm/lib/Transforms/Utils/CodeMoverUtils.cpp | ||
---|---|---|
85 | Why PDT. domainates? Operands need to dominate the use: Below, dominance is allowing the move but post-dominance would prevent it. a = add ... if (abc) { IP = ... [..] I = add a, ... } | |
144 | High-level question: Does dependence info track dependences between side-effects (e.g., global write) and potentially throwing instructions? IP = ... call void @unknown() readnone store ... // <- I Thinking about it, if you move a (generic) side-effect you need to check nounwind and willreturn for all instructions you move it over. Nits: |
llvm/include/llvm/Transforms/Utils/CodeMoverUtils.h | ||
---|---|---|
30–32 | [style] Start function names with lower case letters. | |
llvm/lib/Analysis/PostDominators.cpp | ||
59 | [serious] Should ensure that not both of the instructions are PHIs. These do not (post-)dominate each other even if one follows the other. See https://llvm.org/PR26718. | |
llvm/lib/Transforms/Utils/CodeMoverUtils.cpp | ||
50 | [suggestion] Could just return false in this case. Even if this is a wrong use of the interface, callers should not do anything. |
llvm/include/llvm/Transforms/Utils/CodeMoverUtils.h | ||
---|---|---|
30–32 | Actually I intensionally start with upper case for this function, as I see global functions in other files also start with upper case (e.g. CloneFunction.cpp). Do you know which way is the recommenced style? |
llvm/include/llvm/Transforms/Utils/CodeMoverUtils.h | ||
---|---|---|
30–32 | Functions with starting capital letter is an older style. It's just that nobody put in the work to do the style conversion yet. Recently, the community was even discussing applying lower camelCase to variables as well and apply it wholesale with a conversion script. In any case, PascalCase style for functions is deprecated and I see no reason why no going to the current coding convention. |
llvm/include/llvm/Transforms/Utils/CodeMoverUtils.h | ||
---|---|---|
30–32 | Good to know! I thought there is a different convention for different kind of functions. |
llvm/lib/Transforms/Utils/CodeMoverUtils.cpp | ||
---|---|---|
144 |
Dependence analysis knows nothing about function calls, so it makes worst case assumption and assumes there is confused dependency between calls and other memory accesses (even if the call takes no arguments and is readnone). This should be safe for now but is obviously too pessimistic. I think dependence analysis could be improved to take some obvious cases of function calls into account, but I don't think exception handling would be something it can be taught about. It also raises the question, to what extend do we need to be worried about exceptions and side-effects at higher optimization levels? For instance one could go as far as saying any store cannot be moved past any other store (even if the memories accessed are disjoint) because for example the first store could cause a segfault before the second store has had a chance to execute. |
llvm/lib/Transforms/Utils/CodeMoverUtils.cpp | ||
---|---|---|
144 | It's not as bad fortunately. A segfault (or similar) caused by a memory access is undefined behavior (UB). What we need to make sure is that we do not move a store (or similar) across something that: might synchronize (but nothing else, incl. readnone) might throw (same as above) might never return = endless loop (only not move it before and only if the pointer is not known dereferenceable and never return call/loop is side effect and synchronization free). We probably want tests for these. |
With this change, no instructions are considered safe to move across instructions that may throw, or call instructions that may not return or may synchronize, which is straighter than @jdoerfert suggestion. We can generalize it when needed. @jdoerfert What do you think?
llvm/lib/Transforms/Utils/CodeMoverUtils.cpp | ||
---|---|---|
135 | None of these checks are required for simple instructions (such as add and icmp which are used in the test bellow). I think we should only check for throw/sync/noreturn if isSafeToSpeculativelyExecute(I) returns false. | |
158 | remove the dump or guard it. | |
llvm/unittests/Transforms/Utils/CodeMoverUtilsTest.cpp | ||
72 | Please see my comment above. I think we should use an instruction with potential side-effect to really test what moves across safecalls and what doesn't move across unsafe calls. We should also test that instructions without side-effect can be moved across function calls as long as def-use dependency is preserved. |
llvm/unittests/Transforms/Utils/CodeMoverUtilsTest.cpp | ||
---|---|---|
145 | https://github.com/llvm/llvm-project/commit/ad58d1a9d117d46916bfff77aad0c369cee91cea.diff Note: Google Test filter = CodeMoverUtils.BasicTest [==========] Running 1 test from 1 test case. [----------] Global test environment set-up. [----------] 1 test from CodeMoverUtils [ RUN ] CodeMoverUtils.BasicTest /b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm-project/llvm/unittests/Transforms/Utils/CodeMoverUtilsTest.cpp:145:9: runtime error: reference binding to null pointer of type 'llvm::Instruction' #0 0x45d68e in operator() /b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm-project/llvm/unittests/Transforms/Utils/CodeMoverUtilsTest.cpp:145:9 #1 0x45d68e in void llvm::function_ref<void (llvm::Function&, llvm::DominatorTree&, llvm::PostDominatorTree&, llvm::DependenceInfo&)>::callback_fn<CodeMoverUtils_BasicTest_Test::TestBody()::$_0>(long, llvm::Function&, llvm::DominatorTree&, llvm::PostDominatorTree&, llvm::DependenceInfo&) /b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm-project/llvm/include/llvm/ADT/STLExtras.h:108:12 #2 0x45be28 in run /b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm-project/llvm/unittests/Transforms/Utils/CodeMoverUtilsTest.cpp:45:3 #3 0x45be28 in CodeMoverUtils_BasicTest_Test::TestBody() /b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm-project/llvm/unittests/Transforms/Utils/CodeMoverUtilsTest.cpp:102:3 #4 0x94138b in testing::Test::Run() /b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm-project/llvm/utils/unittest/googletest/src/gtest.cc:2474:5 #5 0x94207a in testing::TestInfo::Run() /b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm-project/llvm/utils/unittest/googletest/src/gtest.cc:2656:11 #6 0x942a42 in testing::TestCase::Run() /b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm-project/llvm/utils/unittest/googletest/src/gtest.cc:2774:28 #7 0x94a042 in testing::internal::UnitTestImpl::RunAllTests() /b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm-project/llvm/utils/unittest/googletest/src/gtest.cc:4649:43 #8 0x949ab5 in testing::UnitTest::Run() /b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm-project/llvm/utils/unittest/googletest/src/gtest.cc:4257:10 #9 0x939d23 in RUN_ALL_TESTS /b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm-project/llvm/utils/unittest/googletest/include/gtest/gtest.h:2233:46 #10 0x939d23 in main /b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm-project/llvm/utils/unittest/UnitTestMain/TestMain.cpp:50:10 #11 0x7f1b4d6402e0 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x202e0) #12 0x412ad9 in _start (/b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm_build_ubsan/unittests/Transforms/Utils/UtilsTests+0x412ad9) SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior /b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm-project/llvm/unittests/Transforms/Utils/CodeMoverUtilsTest.cpp:145:9 in ******************** |
llvm/unittests/Transforms/Utils/CodeMoverUtilsTest.cpp | ||
---|---|---|
145 | Thanks for putting in the fix. |
[style] Start function names with lower case letters.