This is an archive of the discontinued LLVM Phabricator instance.

[SCCP] Mark CFG as preserved.
ClosedPublic

Authored by fhahn on May 21 2018, 9:44 AM.

Details

Summary

SCCP does not change the CFG, so we can mark it as preserved.

Diff Detail

Repository
rL LLVM

Event Timeline

davide requested changes to this revision.May 21 2018, 9:57 AM

If I recall correctly the sparse constant propagation implementation in LLVM (interproceturally, at least), calls changeToUnreachable which modifies the CFG.
(this is, quite unfortunate, as it's declared in Local.h). So, I'm afraid the patch as is is not correct. That said, it's been a while since I last worked on this area so I might recall incorrectly :)

This revision now requires changes to proceed.May 21 2018, 9:57 AM

This is, AFAIK, right but your assumption is wrong.

In particular, DT is preserved, but the CFG is definitely changed by SCCP.
See changeToUnreachable and what it does under the covers.

(this has confused people before :P).

Davide beat me to it.

DT is still preserved.

Right, IPSCCP does use changeToUnreachable, but it can be told to update the DT. The thing that confused me is that we use removeAllNonTerminatorInstruction... in runSCCP with a comment that we should not change the CFG. Is there a reason we use changeToUnreachable in IPSCCP but removeAllNonTerminatorInstruction... in SCCP?

Florian, I won't be opposed if you decide to preserve the dominator tree as part of changeToUnreachable, but, as we discussed with Dan in the past, do we really need to? I mean, we could just change changeToUnreachable (no pun intended) to do something sane and not modify the CFG (if the block is really unreachable, it's very likely that the next round of DCE is going to remove it anyway) [and in case it doesn't I'm really not worried about running DCE again because it's really basically free].

Right, IPSCCP does use changeToUnreachable, but it can be told to update the DT. The thing that confused me is that we use removeAllNonTerminatorInstruction... in runSCCP with a comment that we should not change the CFG. Is there a reason we use changeToUnreachable in IPSCCP but removeAllNonTerminatorInstruction... in SCCP?

I don't think there's a good one, FWIW.

fhahn added a comment.May 21 2018, 1:38 PM

Thanks Davide. It should be fairly straight forward to preserve the DT on top of D45330, which requires dominators anyways for IPSCCP. If we could get away not modifying that would be great, I just want to avoid pessimizing passes close to IPSCCP.

fhahn updated this revision to Diff 148029.May 22 2018, 9:43 AM

Removed DT preservation for IPSCCP, which uses changeToUnreachable. SCCP uses removeAllNonTerminatorInstruction... and should not change the CFG.

efriedma requested changes to this revision.Jun 25 2018, 11:17 AM

Err, actually, thinking about it a big more, can you use setPreservesCFG() instead, if we're not modifying the CFG at all?

This revision now requires changes to proceed.Jun 25 2018, 11:17 AM
fhahn added a comment.Jun 26 2018, 8:21 AM

Yep I think we could preserve all CFG analysis. But wouldn't that potentially lead to worse results, if a preserved analysis could benefit from the propagated constants?

setPreservesCFG preserves passes which *only* depend on the CFG, like domtree/loopinfo/etc.

fhahn updated this revision to Diff 153093.Jun 27 2018, 8:09 AM
fhahn retitled this revision from [SCCP] Mark DominatorTreeAnalysis as preserved. to [SCCP] Mark CFG as preserved..
fhahn edited the summary of this revision. (Show Details)

Updated to mark CFG as preserved. I also added a test case.

davide accepted this revision.Jun 27 2018, 8:18 AM

LGTM.

This revision was not accepted when it landed; it landed in state Needs Review.Jun 28 2018, 2:58 AM
Closed by commit rL335820: [SCCP] Mark CFG as preserved. (authored by fhahn). · Explain Why
This revision was automatically updated to reflect the committed changes.