This is an archive of the discontinued LLVM Phabricator instance.

[PM] Introduce an analysis set used to preserve all analyses over a function's CFG when that CFG is unchanged.
ClosedPublic

Authored by chandlerc on Jan 12 2017, 3:21 PM.

Details

Summary

This allows transformation passes to simply claim they preserve the CFG
and analysis passes to check for the CFG being preserved to remove the
fanout of all analyses being listed in all passes.

I've gone through and removed or cleaned up as many of the comments
reminding us to do this as I could.

The name for this set is ... *TERRIBLE* though. And so is the name for the
static helper function that builds one of these. I'd really lik suggestions on
better names here as I drew a complete blank. Especially if they'll be
consistent and pattern nicely with the other examples we have. These are
especially easy for me to rename.

Diff Detail

Repository
rL LLVM

Event Timeline

chandlerc updated this revision to Diff 84182.Jan 12 2017, 3:21 PM
chandlerc retitled this revision from to [PM] Introduce an analysis set used to preserve all analyses over a function's CFG when that CFG is unchanged..
chandlerc updated this object.
chandlerc added a subscriber: llvm-commits.
davide edited edge metadata.Jan 12 2017, 3:55 PM

I'm so glad to see this happening =)
First round of comments.

lib/Transforms/InstCombine/InstructionCombining.cpp
3180–3181 ↗(On Diff #84182)

The fact that we preserve now GlobalsAA and AAManager is an unrelated change, I guess? (can be committed separately).

lib/Transforms/Scalar/DCE.cpp
127–128 ↗(On Diff #84182)

this comment is too trivial to be useful.

lib/Transforms/Scalar/IndVarSimplify.cpp
2497 ↗(On Diff #84182)

Why std::move() here?

lib/Transforms/Scalar/LoopRotation.cpp
637 ↗(On Diff #84182)

Unrelated?

lib/Transforms/Scalar/LoopSimplifyCFG.cpp
72 ↗(On Diff #84182)

Unrelated?

lib/Transforms/Scalar/LoopUnrollPass.cpp
1133 ↗(On Diff #84182)

Unrelated?

lib/Transforms/Scalar/NaryReassociate.cpp
168–169 ↗(On Diff #84182)

Remove the FIXME.

davide added inline comments.Jan 12 2017, 4:34 PM
lib/Transforms/Scalar/GuardWidening.cpp
662–663 ↗(On Diff #84182)

hmm, this doesn't seem to have a FIXME but it's supposed to preserve the CFG analyses, so good that you caught it (here and elsewhere).

davide added inline comments.Jan 12 2017, 9:56 PM
lib/Analysis/BlockFrequencyInfo.cpp
135–143 ↗(On Diff #84182)

The class of invalidate functions share a decent amount of code, maybe we can factor it out somehow?

jlebar added inline comments.Jan 13 2017, 9:03 AM
include/llvm/IR/PassManager.h
98 ↗(On Diff #84182)

This analysis set doesn't really "represent the CFG of a function". It's like AllAnalysesOn above; it "represents analyses that only look at functions' control flow graphs (and therefore are preserved if the CFG is unchanged)".

105 ↗(On Diff #84182)

Can you clarify what you mean by "mutating a basic block"? I would think that adding (say) an add instruction to a BB does not affect the CFG, but does "mutate" the BB.

106 ↗(On Diff #84182)

You could call it CFGAnalyses? If at some point we wanted to preserve the CFG plus call graph in every function in a module, we could call that "GlobalCFGAnalyses" and I don't think that would be particularly strange.

I don't think we need to keep with the AllAnalysesOnFoo idiom. It makes sense for AllAnalysesOn<IRUnitT> (although if you wanted to drop the "All" I'd be ok with that), but that's mainly because of the position of the template parameter.

170 ↗(On Diff #84182)

I actually think we should get rid of these two helpers and make the code more verbose, on the theory that there should be One Way to Do It. Otherwise every time we add a new analysis set, we have to ask whether it belongs as a static function in here, and in any case our code is going to be inconsistent, with half using the one way and half using the other... Also seeing the helper makes me ask the question, "is this different somehow than the trivial implementation I expected?"

lib/Analysis/BlockFrequencyInfo.cpp
135–143 ↗(On Diff #84182)

The way I think of it, this here is how we list the things that preserve BlockFrequencyInfo. "Factoring out" the code somehow would mean we changed the invalidator API somehow.

When I did an earlier review, I suggested not even calling invalidate() if we know a priori that the pass is preserved (I guess that would correspond to PAC.preserved() || PAC.preservedSet<AllAnalysesOn<IRUnitT>>())). Chandler explained at the time why this wouldn't work. I don't quite remember, but IIRC the problem isn't with analyses but with transformation passes, which want to do work inside invalidate(). I think it's a decent simplification if we keep the analysis and transformation invalidate functions close together, even if it means we have to write a bit more boilerplate.

davide added inline comments.Jan 13 2017, 10:37 AM
lib/Analysis/BlockFrequencyInfo.cpp
135–143 ↗(On Diff #84182)

Fair enough.

chandlerc updated this revision to Diff 84470.Jan 14 2017, 6:11 PM
chandlerc marked 11 inline comments as done.
chandlerc edited edge metadata.

Update based on review comments including moving to the newly suggested name.

davide accepted this revision.Jan 14 2017, 6:15 PM
davide edited edge metadata.

There are still a bunch of unrelated newline/whitespace changes in Loop passes. Revert them, and this looks good to me. Thanks for your patience!

This revision is now accepted and ready to land.Jan 14 2017, 6:15 PM
chandlerc updated this revision to Diff 84471.Jan 14 2017, 6:19 PM
chandlerc marked 3 inline comments as done.
chandlerc edited edge metadata.

One more comment update that I missed.

Thanks for all of the great review comments! Patch is updated, see responses below.

include/llvm/IR/PassManager.h
98 ↗(On Diff #84182)

Tried to reword, lemme know if you like.

105 ↗(On Diff #84182)

Sorry, I meant mutating the *set* of BBs. IE, adding or removing BBs. I also made the branch mutation comment much more accurate and precise (I hope).

106 ↗(On Diff #84182)

Done, and thanks!

lib/Analysis/BlockFrequencyInfo.cpp
135–143 ↗(On Diff #84182)

The reason just not calling these functions doesn't work is that we need to call these functions to handle dependencies between analyses.

I agree however that this is essentially the listing of dependencies and sets. If there is a more concise and simple way of writing the code however, I'm all for it.

I tried several variations to get a single method call on PreservedAnalyses, but they weren't actually easier to read.

lib/Transforms/InstCombine/InstructionCombining.cpp
3180–3181 ↗(On Diff #84182)

Yeah, I just noticed when reading the code. I'll pull this into a separate commit as there is also a FIXME above that would be good to resolve at the same time.

lib/Transforms/Scalar/GuardWidening.cpp
662–663 ↗(On Diff #84182)

I tried to audit all passes which have a setPreservesCFG for the legacy PM and a run function definition for the new PM, and add this to them.

lib/Transforms/Scalar/IndVarSimplify.cpp
2497 ↗(On Diff #84182)

Because i didn't remove it before mailing. Gone now.

lib/Transforms/Scalar/LoopRotation.cpp
637 ↗(On Diff #84182)

I was just making all of these look the same. I'm happy to split it into a separate patch if you want, but didn't seem worthwhile..

lib/Transforms/Scalar/LoopSimplifyCFG.cpp
72 ↗(On Diff #84182)

See above. Will follow whatever pattern you want.

lib/Transforms/Scalar/LoopUnrollPass.cpp
1133 ↗(On Diff #84182)

See above.

Sorry, phab was slow and I didn't get your last mail. I think it's not worth splitting the newline changes separately, now that I understand your intention. LGTM, again.

jlebar accepted this revision.Jan 14 2017, 6:52 PM
jlebar edited edge metadata.

I like it!

include/llvm/IR/PassManager.h
105 ↗(On Diff #84182)

Yes, this comment is much better now.

silvas edited edge metadata.Jan 14 2017, 8:03 PM

I couldn't come up with a good name for this either. I described a design in my log here: https://docs.google.com/document/d/1-nrq2y_hTiZhrsJDmH8TzFjFEeApfccs6wwGyaXjSkg/edit#heading=h.ut7bc0x07mmh

There the naming in my sketch there was super crazy verbose. E.g. the analysis key object for each "set" would be called AnalysesThatOnlyDependOnTheCFG and I guess what I was thinking was to have a convention of accessing the raw keys through simple wrapper functions called invalidateMeIfIAmAnAnalysisThat... (which allowed for sets to easily "inherit" from each other; I didn't record any really compelling use case for this so I'm not sure what the value is).

It would be good to build up some verification machinery here at some point in the future.

lib/Transforms/InstCombine/InstructionCombining.cpp
3180 ↗(On Diff #84471)

Is this actually true? I've seen InstCombine rewrite a switch. I know we *want* it to be true, but I'm not sure if it is right now.

I also imagined using very verbose / explicit names. But I'm happy (enough) with Justin's nice, short name. I don't think it'll ever become really ambiguous and it needs to be short given how much it gets used.

lib/Transforms/InstCombine/InstructionCombining.cpp
3180 ↗(On Diff #84471)

The question is whether it preserves the edge relationships and the set of BBs.

It can fold constants into branch conditions and otherwise restructure the *values* in a switch all it wants.

But more importantly perhaps, this matches exactly what the legacy PM does. So if there are bugs here, they exactly match existing bugs. =] I don't want the new PM to diverge here.

(FYI, going ahead and landing this as both Justin and Davide are happy. I'm more than happy to continue discussing any concerns around instcombine though)

This revision was automatically updated to reflect the committed changes.