This is an archive of the discontinued LLVM Phabricator instance.

[CodeMoverUtils] Use dominator tree level to decide the direction of code motion
ClosedPublic

Authored by RithikSharma on May 17 2020, 7:26 AM.

Details

Summary

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.

Diff Detail

Event Timeline

RithikSharma created this revision.May 17 2020, 7:26 AM
Whitney added inline comments.May 17 2020, 10:09 AM
llvm/include/llvm/Analysis/OrderedInstructions.h
48

Please add description of this new function.

fhahn added a subscriber: fhahn.May 17 2020, 1:05 PM

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

nikic added inline comments.May 19 2020, 1:07 PM
llvm/lib/Transforms/Utils/CodeMoverUtils.cpp
319–330

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.

RithikSharma added a reviewer: fhahn.

Added function description to bfsLevelBefore and made some optimization changes in the dominance checks.

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

It makes sense to me, surely I will move these OrderedInstructions to CodeMoverUtils in the next patch.

RithikSharma marked an inline comment as done.

This update changes bfsLevelBefore to domTreeLevelBefore, the new name adds more details about the function and makes it more descriptive.

Whitney added inline comments.May 26 2020, 11:11 AM
llvm/include/llvm/Analysis/OrderedInstructions.h
52

nit: sentence end with a period.

llvm/lib/Analysis/OrderedInstructions.cpp
48

clang-format?

This update changes OrderedInstructions.cpp to Clang-format and fixes errors in function description of domTreeLevelBefore.

Whitney accepted this revision.May 27 2020, 5:13 AM

Knowing that you will move OrderedInstructions to CodeMoverUtils in the next patch. LGTM.

This revision is now accepted and ready to land.May 27 2020, 5:13 AM
This revision was automatically updated to reflect the committed changes.
nikic added inline comments.May 28 2020, 10:59 AM
llvm/lib/Transforms/Utils/CodeMoverUtils.cpp
337

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.

Whitney added inline comments.May 28 2020, 12:06 PM
llvm/lib/Transforms/Utils/CodeMoverUtils.cpp
337

If there is a control flow split, then isControlFlowEquivalent check on line 317 will exit.