Page MenuHomePhabricator

[SCEV] Avoid redundant computations when doing AddRec merge
ClosedPublic

Authored by mkazantsev on Oct 12 2018, 4:38 AM.

Details

Summary

When we calculate a product of 2 AddRecs, we end up making quite massive
computations to deduce the operands of resulting AddRec. This process can
be optimized by computing all args of intermediate sum and then calling
getAddExpr once rather than calling getAddExpr with intermediate
result every time a new argument is computed.

Diff Detail

Repository
rL LLVM

Event Timeline

mkazantsev created this revision.Oct 12 2018, 4:38 AM

Rebased: the patch slightly alters simplification, but in this test the expression is still within reasonable bounds.

rtereshin accepted this revision.Oct 31 2018, 12:52 PM

Do you think it's better to remove the NFC tag from the patch? It doesn't look like it's completely NFC, though, I've tested this out for a major (though, out of tree) GPU target on a very large suite of shaders and found no difference.

What's the compile time impact roughly?

I also think that giving the wrapping flags a thought here (in a sense of preserving / re-deriving them a bit better) is valuable, but I don't have any concrete suggestions unfortunately.

Regardless, LGTM, thanks for doing this.

This revision is now accepted and ready to land.Oct 31 2018, 12:52 PM
mkazantsev retitled this revision from [SCEV][NFC] Avoid redundant computations when doing AddRec merge to [SCEV] Avoid redundant computations when doing AddRec merge.Oct 31 2018, 9:48 PM

I expect compile time impact to be zero for majority of cases. It should only affect corner cases at which we reach limit depth during simplifications. For them, depending on simplifications complexity, we save O(N) time simplifying. I don't think it will really be observable on anything other than corner-cases.

This revision was automatically updated to reflect the committed changes.