Page MenuHomePhabricator

[CodeMoverUtils] Added an API to check if an instruction can be safely moved before another instruction.
ClosedPublic

Authored by Whitney on Nov 9 2019, 8:45 PM.

Details

Summary

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.

Diff Detail

Event Timeline

Whitney created this revision.Nov 9 2019, 8:45 PM
jdoerfert added inline comments.Nov 11 2019, 11:49 AM
llvm/lib/Transforms/Utils/CodeMoverUtils.cpp
85

Why PDT. domainates? Operands need to dominate the use:
DT.dominates(OpInst, InsertPoint)

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?
E.g., would this allow me to move I to IP in the example below:

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:
No need for inline (let the compiler figure it out).
If you reorder, forward declarations not necessary (= easier to maintain).

Meinersbur added inline comments.Nov 11 2019, 3:51 PM
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.

Whitney updated this revision to Diff 228796.Nov 11 2019, 7:03 PM
Whitney marked 4 inline comments as done.
Whitney added inline comments.
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?

Meinersbur added inline comments.Nov 11 2019, 8:25 PM
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.

Whitney updated this revision to Diff 228806.Nov 11 2019, 8:52 PM
Whitney marked 3 inline comments as done.
Whitney added inline comments.
llvm/include/llvm/Transforms/Utils/CodeMoverUtils.h
30–32

Good to know! I thought there is a different convention for different kind of functions.

bmahjour added inline comments.Nov 12 2019, 10:03 AM
llvm/lib/Transforms/Utils/CodeMoverUtils.cpp
144

Does dependence info track dependences between side-effects (e.g., global write) and potentially throwing instructions

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.

jdoerfert added inline comments.Nov 12 2019, 5:51 PM
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.

Whitney updated this revision to Diff 229388.Nov 14 2019, 1:41 PM
Whitney edited the summary of this revision. (Show Details)

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?

Whitney marked 3 inline comments as done.Nov 14 2019, 1:41 PM
bmahjour added inline comments.Nov 14 2019, 2:37 PM
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.

Whitney updated this revision to Diff 229422.Nov 14 2019, 3:49 PM

Addressed all comments from Bardia.

Whitney marked 3 inline comments as done.Nov 14 2019, 3:49 PM

I'm fine with this @bmahjour @Meinersbur please accept if you are satisfied.

This revision is now accepted and ready to land.Nov 21 2019, 10:00 AM
Whitney closed this revision.Nov 22 2019, 2:21 PM

Landed.

vitalybuka added inline comments.
llvm/unittests/Transforms/Utils/CodeMoverUtilsTest.cpp
145

https://github.com/llvm/llvm-project/commit/ad58d1a9d117d46916bfff77aad0c369cee91cea.diff
to fix

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 

********************
Whitney marked 2 inline comments as done.Nov 26 2019, 7:19 PM
Whitney added inline comments.
llvm/unittests/Transforms/Utils/CodeMoverUtilsTest.cpp
145

Thanks for putting in the fix.