Page MenuHomePhabricator

[SCEV] Memoize visitMulExpr results in SCEVRewriteVisitor. Fix PR18606
ClosedPublic

Authored by lihuang on Oct 19 2016, 5:56 PM.

Details

Summary

[SCEV] Memoize visitMulExpr results in SCEVRewriteVisitor. Fix PR18606

When SCEVRewriteVisitor traverses the SCEV DAG, it may visit the same SCEV multiple times if this SCEV is referenced by multiple other SCEVs. This has exponential time complexity in the worst case. Memoizing the results will avoid re-visiting the same SCEV.

It's legal to memoize the rewrite results because SCEVRewriteVisitor is state-less, i.e., it should return the same rewrite result each time for the same input SCEV. Currently only memoize results of visitMulExpr because other functions are much cheaper in the worst case.

This patch depends on D25794, and they together fix PR18606.

Diff Detail

Repository
rL LLVM

Event Timeline

lihuang updated this revision to Diff 75262.Oct 19 2016, 5:56 PM
lihuang retitled this revision from to [SCEV] Memoize visitMulExpr results in SCEVRewriteVisitor. Fix PR18606.
lihuang updated this object.
lihuang added a subscriber: llvm-commits.
sanjoy requested changes to this revision.Oct 20 2016, 1:12 AM
sanjoy edited edge metadata.
sanjoy added inline comments.
include/llvm/Analysis/ScalarEvolutionExpressions.h
552 ↗(On Diff #75262)

Design-wise I'm not too happy to do see this happen only for multiplications -- have you considered over-riding the visit function and implementing the general logic there?

585 ↗(On Diff #75262)

s/it/It/

592 ↗(On Diff #75262)

I'd use .insert.

This revision now requires changes to proceed.Oct 20 2016, 1:12 AM
lihuang updated this revision to Diff 75373.Oct 20 2016, 5:20 PM
lihuang edited edge metadata.
lihuang marked 2 inline comments as done.Oct 20 2016, 5:37 PM
lihuang added inline comments.
include/llvm/Analysis/ScalarEvolutionExpressions.h
552 ↗(On Diff #75262)

Override the visit function in SCEVRewriteVisitor class. This function checks the map first, then forward the input to SCEVVisitor::visit.

sanjoy accepted this revision.Oct 20 2016, 11:48 PM
sanjoy edited edge metadata.

lgtm with nits

include/llvm/Analysis/ScalarEvolutionExpressions.h
540 ↗(On Diff #75373)

Please document the fact that this only implements "pure" transforms.

560 ↗(On Diff #75373)

Just to be pedantic, I'd assert here that you did in fact insert a new entry.

test/Analysis/ScalarEvolution/pr18606.ll
3 ↗(On Diff #75373)

Please add a basic output sanity check.

This revision is now accepted and ready to land.Oct 20 2016, 11:48 PM
lihuang added inline comments.Oct 21 2016, 11:19 AM
include/llvm/Analysis/ScalarEvolutionExpressions.h
540 ↗(On Diff #75373)

Sorry, but by "pure" transform do you mean identity transform? So what about:

/// Recursively visits a SCEV expression and re-writes an identical SCEV.

560 ↗(On Diff #75373)

what about:

assert(RewriteResults.insert({S, Result}).second && "Should insert a new entry");

test/Analysis/ScalarEvolution/pr18606.ll
3 ↗(On Diff #75373)

Okay.

sanjoy added inline comments.Oct 21 2016, 11:29 AM
include/llvm/Analysis/ScalarEvolutionExpressions.h
540 ↗(On Diff #75373)

I meant a transform that maps equal inputs to equal outputs. For instance, I cannot use this framework to implement a transform that maps all SCEVConstant s to getConstant(Counter++) since then the caching scheme won't work.

560 ↗(On Diff #75373)

sgtm

lihuang added inline comments.Oct 21 2016, 11:56 AM
include/llvm/Analysis/ScalarEvolutionExpressions.h
540 ↗(On Diff #75373)

I see, thanks. What about:

/// This visitor recursively visits a SCEV expression and re-writes it. The result from each visit is cached, so it will return the same SCEV for the same input.

sanjoy added inline comments.Oct 21 2016, 11:56 AM
include/llvm/Analysis/ScalarEvolutionExpressions.h
540 ↗(On Diff #75373)

sgtm

This revision was automatically updated to reflect the committed changes.