Page MenuHomePhabricator

[GVN] Do PHI translations across all edges between the load and the unavailable pred.

Authored by fhahn on Jul 19 2019, 2:39 PM.



Currently we do not properly translate addresses with PHIs if LoadBB !=
LI->getParent(), because PHITranslateAddr expects a direct predecessor as argument,
because it considers all instructions outside of the current block to
not requiring translation.

The amount of cases that trigger this should be very low, as most single
predecessor blocks should be folded into their predecessor by GVN before
we actually start with value numbering. It is still not guaranteed to
happen, so we should do PHI translation along all edges between the
loads' block and the predecessor where we have to place a load.

There are a few test cases showing current limits of the PHI translation, which
could be improved later.

Diff Detail

Event Timeline

fhahn created this revision.Jul 19 2019, 2:39 PM
Herald added a project: Restricted Project. · View Herald TranscriptJul 19 2019, 2:39 PM
Herald added a subscriber: hiraditya. · View Herald Transcript

Given that each block only has a single predecessor, there aren't any PHI nodes involved. In that case, what does PHITranslateWithInsertion actually do?


I don't see any explanation for this change?

fhahn marked an inline comment as done.Aug 15 2019, 6:11 AM

Given that each block only has a single predecessor, there aren't any PHI nodes involved. In that case, what does PHITranslateWithInsertion actually do?

I think this is related to how PHITranslateAddr does the translation: it only translates along CFG edges. When called with (%input, %BB, %PredBB), it tries to generate a value that represents %input in %PredBB. If %input (or any of its operands) are not defined in %BB, there is nothing to translate for this edge (they must also be available in the predecessor) and it will return the untranslated version of the input. This is the problem we hit in phi_trans6, if we would just call it with (%gep.1, %header, %latch).


markInstructionForDeletion asserts that the removed instructions are defined in the current basic block.

But PHI translation may insert instructions in any of the basic blocks traversed during translation. If that happens and translation fails, we have to remove instructions from different basic blocks than the current one. I thought it is best to directly remove them (no other parts of GVN have seen them yet and they are not numbered yet).

I can update the comment to make that clearer.

efriedma added inline comments.Aug 15 2019, 12:27 PM

That makes sense. Please update the comment to at least mention the cross-BB issue.

fhahn updated this revision to Diff 215466.Aug 15 2019, 1:56 PM

Update comment about deleting instructions directly. also run clang-format-diff.

fhahn marked 2 inline comments as done.Aug 15 2019, 1:57 PM
fhahn added inline comments.

Thanks, I've updated the comment. I hope it is clearer now.

fhahn marked an inline comment as done.Wed, Aug 21, 9:49 AM

ping. Eli, are you happy with the latest version, with the updated comment?

This revision is now accepted and ready to land.Wed, Aug 21, 11:41 AM
This revision was automatically updated to reflect the committed changes.