Page MenuHomePhabricator

[IndVars] Use more precise context when eliminating narrowing
ClosedPublic

Authored by mkazantsev on Oct 30 2020, 4:57 AM.

Details

Summary

When deciding to widen narrow use, we may need to prove some facts
about it. For proof, the context is used. Currently we take the instruction
being widened as the context.

However, we may be more precise here if we take as context the point that
dominates all users of instruction being widened.

Diff Detail

Event Timeline

mkazantsev created this revision.Oct 30 2020, 4:57 AM
Herald added a project: Restricted Project. · View Herald TranscriptOct 30 2020, 4:57 AM
mkazantsev edited the summary of this revision. (Show Details)
mkazantsev added reviewers: skatkov, fhahn, anna, lebedev.ri.
anna added inline comments.Nov 17 2020, 8:48 AM
llvm/lib/Transforms/Utils/SimplifyIndVar.cpp
1564

dominates is a more expensive check than comesBefore. We can special case for uses in the same basic block, i.e. :

if (User->getParent() == Context->getParent() && User->comesBefore(Context))
    Context = User
skatkov added inline comments.Nov 17 2020, 11:01 PM
llvm/lib/Transforms/Utils/SimplifyIndVar.cpp
1564

comesBefore is used in DT->dominates...

1569

What do you think about introducing the method in DT which finds nearestCommonDominator for an array of values?
Here, just to collect all users and trigger the utility method?

Alternatively, introduce findNearestCommonDominator which accepts Instructions or values in DomTree?
And use just it instead of this dispatching.

1573

If all users are NarrowDef, should we mark it as dead?

mkazantsev added inline comments.Nov 18 2020, 12:35 AM
llvm/lib/Transforms/Utils/SimplifyIndVar.cpp
1569

It's a good idea.

1573

NarrowDef will be deleted in the end in any case.

anna added inline comments.Nov 18 2020, 8:38 AM
llvm/lib/Transforms/Utils/SimplifyIndVar.cpp
1564

yes I know :), but there are a bunch of other checks in DT-dominates() which are first checked that are not needed for the same basic block case. Maybe it doesn't make a difference...

mkazantsev added inline comments.Nov 18 2020, 8:13 PM
llvm/lib/Transforms/Utils/SimplifyIndVar.cpp
1564

But why do you think that the users will be in the same block? In either case, DT checks cost is nothing compared to SCEV creation cost.

Rebased, with dom tree logic factored out into separate patch (added dependency).

skatkov added inline comments.Nov 19 2020, 12:51 AM
llvm/lib/Transforms/Utils/SimplifyIndVar.cpp
1546

Can you land this code movement as NFC in a separate patch and update this one?

skatkov accepted this revision.Nov 19 2020, 1:47 AM
This revision is now accepted and ready to land.Nov 19 2020, 1:47 AM

Roll back to older code concept (without generatization into DomTree). It seems unreasonably difficult to check in code there.

skatkov accepted this revision.Nov 23 2020, 10:27 PM

It is pity that we did not introduce an useful utility function.

Still lgtm.