Currently isSafeToMoveBefore uses DFS numbering for determining the relative position of instruction and insert point which is not always correct. This PR proposes the use of Dominator Tree depth for the same. If a node is at a higher level than the insert point then it is safe to say that we want to move in the forward direction.
Details
Diff Detail
Event Timeline
llvm/include/llvm/Analysis/OrderedInstructions.h | ||
---|---|---|
48 | Please add description of this new function. |
It looks like the only user of OrderedInstructions.h is CodeMoverUtils now. At this point I think it would be good to remove OrderedInstructions and move the new code directly to CodeMoverUtils
llvm/lib/Transforms/Utils/CodeMoverUtils.cpp | ||
---|---|---|
323–337 | I'd feel a lot better about this code if this code were just if (!DT.dominates(&InsertPoint, &I)) for (const Use &U : I.uses()) if (auto *UserInst = dyn_cast<Instruction>(U.getUser())) if (UserInst != &InsertPoint && !DT.dominates(&InsertPoint, U)) return false; if (!DT.dominates(&I, &InsertPoint)) for (const Value *Op : I.operands()) if (auto *OpInst = dyn_cast<Instruction>(Op)) if (&InsertPoint == OpInst || !DT.dominates(OpInst, &InsertPoint)) return false; which is more "obviously correct". The outer dominance checks here are just an optimization to handle obvious cases, but for (const Use &U : I.uses()) if (auto *UserInst = dyn_cast<Instruction>(U.getUser())) if (UserInst != &InsertPoint && !DT.dominates(&InsertPoint, U)) return false; for (const Value *Op : I.operands()) if (auto *OpInst = dyn_cast<Instruction>(Op)) if (&InsertPoint == OpInst || !DT.dominates(OpInst, &InsertPoint)) return false; would work as well. In this case the MoveForward variable would only be needed for the collectInstructionsInBetween() check below. |
Added function description to bfsLevelBefore and made some optimization changes in the dominance checks.
It makes sense to me, surely I will move these OrderedInstructions to CodeMoverUtils in the next patch.
This update changes bfsLevelBefore to domTreeLevelBefore, the new name adds more details about the function and makes it more descriptive.
This update changes OrderedInstructions.cpp to Clang-format and fixes errors in function description of domTreeLevelBefore.
Knowing that you will move OrderedInstructions to CodeMoverUtils in the next patch. LGTM.
llvm/lib/Transforms/Utils/CodeMoverUtils.cpp | ||
---|---|---|
342 | Side note: collectInstructionsInBetween() seems to collect much more instructions than it actually needs. If there is a control flow split and the end instruction is on one side, it will still visit the other one, and everything that is reachable from it. |
llvm/lib/Transforms/Utils/CodeMoverUtils.cpp | ||
---|---|---|
342 | If there is a control flow split, then isControlFlowEquivalent check on line 317 will exit. |
Please add description of this new function.