Page MenuHomePhabricator

Add more opportunities for constant folding in ScalarEvolution.
AcceptedPublic

Authored by timmurray on Dec 2 2014, 3:11 PM.

Details

Reviewers
nlewycky
Summary

More constant multiplies will be folded. This prevents SCEVs from
being generated with mismatches such as

{((4 * ((-1 * %x1) + %X.unr)) + %1),+,32}<%Loop>

vs

{((4 * %X.unr) + (-4 * %x1) + %1),+,32}

Diff Detail

Event Timeline

timmurray updated this revision to Diff 16832.Dec 2 2014, 3:11 PM
timmurray retitled this revision from to Add more opportunities for constant folding in ScalarEvolution..
timmurray updated this object.
timmurray edited the test plan for this revision. (Show Details)
srhines added a subscriber: srhines.Dec 2 2014, 3:14 PM
timmurray added a subscriber: Unknown Object (MLST).Dec 2 2014, 3:16 PM
timmurray updated this revision to Diff 16836.Dec 2 2014, 3:26 PM

fix change description

majnemer added inline comments.
lib/Analysis/ScalarEvolution.cpp
2212

Please give this function a name that starts with a lower case letter. Also, pointers bind to the variable name.

2216

It's more natural in LLVM to write:

const auto *Target = dyn_cast<SCEVNAryExpr>(Expr);
2220–2221

This would probably read easier as:

for (const SCEV *Operand : Target->operands())
2220–2227

I think this would look a little more natural:

for (const SCEV *Operand : Target->operands()) {
  if (isa<SCEVConstant>(*Operand))
    return true;
  if (isa<SCEVAddExpr>(*Operand) || isa<SCEVMulExpr>(*Operand))
    if (containsConstantSomewhere(*Operand))
      return true;
}
2222

These extra parens look strange.

nlewycky added inline comments.
lib/Analysis/ScalarEvolution.cpp
2210

I forget; are expr's guaranteed to be "GroupByComplexity"'d? If so, ContainsConstantSomewhere can be optimized greatly. If there's any constant, it's guaranteed to be in a group at the end. You only recurse on Add and Mul, so if you've gone past those (to umax, smax, unknown or could-not-compute, you can stop).

Also, please iterate with a worklist instead of recursing. Create a SmallVector<SCEV*>, push your starting element into it, use pop_back_val to grab the latest one off the top of the list. If you're worried about revisiting the same thing multiple times, add a SmallSet<SCEV*> and test whether inserting the new element succeeds -- if it doesn't, it's already in the set.

2269–2270

Capitalize 'If', remove extra space before 'then'.

timmurray updated this revision to Diff 16839.Dec 2 2014, 4:53 PM

Switch to worklist-based constant search instead of recursion. Clean up style.

nlewycky added inline comments.Dec 2 2014, 4:57 PM
lib/Analysis/ScalarEvolution.cpp
2212

"SCEV* StartExpr" should be "SCEV *StartExpr".

2221

This cast is guaranteed to succeed because of the if isa's above. Use cast<> instead of dyn_cast<>.

timmurray updated this revision to Diff 16902.Dec 3 2014, 5:01 PM

Update style and cast.

nlewycky accepted this revision.Dec 3 2014, 5:03 PM
nlewycky added a reviewer: nlewycky.

LGTM

This revision is now accepted and ready to land.Dec 3 2014, 5:03 PM
nlewycky requested changes to this revision.Dec 3 2014, 5:03 PM
nlewycky edited edge metadata.

Er, wait. Needs a test.

This revision now requires changes to proceed.Dec 3 2014, 5:03 PM
timmurray updated this revision to Diff 16992.Dec 5 2014, 12:23 PM
timmurray edited edge metadata.

Add test for additional fold opportunity.

nlewycky accepted this revision.Dec 5 2014, 2:13 PM
nlewycky edited edge metadata.

LGTM with comment.

test/Analysis/ScalarEvolution/scev-mul-expr-fold.ll
53–62

I think you can safely drop all the metadata from this test?

This revision is now accepted and ready to land.Dec 5 2014, 2:13 PM

Looks like patch was not committed.

It looks like I LGTM'd it with comments that aren't resolved. If you don't have commit access, please upload a version which I can commit for you with no changes. Usually I LGTM+comments with the expectation that you can resolve the comments and commit without going through another round of review.