This is an archive of the discontinued LLVM Phabricator instance.

[gvn] Precisely propagate equalities to phi operands
ClosedPublic

Authored by reames on Mar 5 2021, 3:17 PM.

Details

Summary

The code used for propagating equalities (e.g. assume facts) was conservative in two ways - one of which this patch fixes. Specifically, it shifts the code reasoning about whether a use is dominated by the end of the assume block to consider phi uses to exist on the predecessor edge. This matches the dominator tree handling for dominates(X, Use), and simply extends it to properlyDominates.

Note that the decision to use the end of the block is itself a conservative choice. The more precise option would be to use the later of the assume and the value, and replace all uses after that. GVN handles that case separately (with the replace operand mechanism) because it used to be expensive to ask dominator questions within blocks. With the new instruction ordering support, we should probably rewrite this code at some point to simplify.

Diff Detail

Event Timeline

reames created this revision.Mar 5 2021, 3:17 PM
reames requested review of this revision.Mar 5 2021, 3:17 PM
Herald added a project: Restricted Project. · View Herald TranscriptMar 5 2021, 3:17 PM
reames updated this revision to Diff 328665.Mar 5 2021, 3:24 PM

Rebase over landed tests.

I don't understand how second commit message paragraph in this context but the logic seems fine. Second pair of eyes won't hurt though.

nikic added inline comments.Mar 6 2021, 12:56 AM
llvm/lib/Transforms/Utils/Local.cpp
2698

I'd suggest to write it like this:

Instruction *UserInst = cast<Instruction>(U.getUser());
if (auto *PN = dyn_cast<PHINode>(UserInst))
  return DT.dominates(BB, PN->getIncomingBlock());
else
  return DT.properlyDominates(BB, UserInst->getParent());

Though ideally this should be an API on DominatorTree. We currently have dominates(BasicBlockEdge, Use), but we're missing the dominates(BasicBlock, Use) variant.

reames updated this revision to Diff 328800.Mar 6 2021, 12:01 PM

address review comments + rebase over landed change which causes a further test diff

nikic accepted this revision.Mar 6 2021, 12:08 PM

LGTM

This revision is now accepted and ready to land.Mar 6 2021, 12:08 PM
This revision was landed with ongoing or failed builds.Mar 8 2021, 8:59 AM
This revision was automatically updated to reflect the committed changes.