This is an archive of the discontinued LLVM Phabricator instance.

[SCEV][NFC] Smarter implementation of isAvailableAtLoopEntry
ClosedPublic

Authored by mkazantsev on Mar 1 2018, 11:09 PM.

Details

Summary

isAvailableAtLoopEntry duplicates logic of properlyDominates after checking invariance.
This patch replaces this logic with invocation of this method which is more profitable
because it supports caching.

Diff Detail

Event Timeline

mkazantsev created this revision.Mar 1 2018, 11:09 PM
sanjoy requested changes to this revision.Mar 12 2018, 10:57 AM
sanjoy added inline comments.
lib/Analysis/ScalarEvolution.cpp
2237

Looks like properlyDominates is not transitive when this used to be transitive?

(It could be that properlyDominates is incorrect itself and needs to be transitive too - if yes, let's make that change first.)

This revision now requires changes to proceed.Mar 12 2018, 10:57 AM
mkazantsev added inline comments.Mar 12 2018, 9:31 PM
lib/Analysis/ScalarEvolution.cpp
2237

I didn't get what do you mean under "transitive" in this context. The only significant difference I see is that getBlockDisposition is implemented via recursion with global caching and this is via SCEV traversal with local caching. Global caching is more profitable in this case since we can end up checking the same SCEVs again and again. I don't think there are any functional differences.

sanjoy accepted this revision.Mar 12 2018, 10:34 PM
sanjoy added inline comments.
lib/Analysis/ScalarEvolution.cpp
2237

Yes, you're right, I missed the recursion in ScalarEvolution::computeBlockDisposition.

Do you mind, as a later change, rewriting ScalarEvolution::computeBlockDisposition to use SCEVTraversal? That's more idiomatic and reduces (although only by a little bit :) ) the possibility of stack overflow.

This revision is now accepted and ready to land.Mar 12 2018, 10:34 PM
mkazantsev added inline comments.Mar 12 2018, 10:50 PM
lib/Analysis/ScalarEvolution.cpp
2237

I think we could do it, yes. But in this case we cache the same data in both local and global cache. I think we can replace it with a global traversal or something. :)

This revision was automatically updated to reflect the committed changes.
fhahn added a subscriber: fhahn.Mar 13 2018, 3:12 AM