This is an archive of the discontinued LLVM Phabricator instance.

[unroll] Use value domain for symbolic execution based cost model
ClosedPublic

Authored by reames on May 21 2021, 10:20 AM.

Details

Summary

The current full unroll cost model does a symbolic evaluation of the loop up to a fixed limit. That symbolic evaluation currently simplifies to constants, but we can generalize to arbitrary Values using the InstructionSimplify infrastructure at very low cost.

By itself, this enables some simplifications, but it's mainly useful when combined with the branch simplification over in D102928.

(FYI, current tests are a bit lacking. Planning to pre-commit some tests and rebase in the near future.)

Diff Detail

Event Timeline

reames created this revision.May 21 2021, 10:20 AM
reames requested review of this revision.May 21 2021, 10:20 AM
Herald added a project: Restricted Project. · View Herald TranscriptMay 21 2021, 10:20 AM
reames updated this revision to Diff 347083.May 21 2021, 11:01 AM

Rebase over landed tests

nikic added a comment.May 21 2021, 3:20 PM

I think it would be good to split this into two parts: One that changes the infrastructure to map to Value rather than Constant, making use of the existing SimplifyBinOp fold. And another that replaces constant folding with InstSimplify calls in the places it's not used yet.

llvm/lib/Analysis/LoopUnrollAnalyzer.cpp
203

With the added SimplifyCmpInst, I'd expect that we no longer need this ConstantExpr::getCompare() block.

nikic added inline comments.May 21 2021, 3:26 PM
llvm/test/Transforms/LoopUnroll/unroll-cost-symbolic-execute.ll
23

Side note: Looks like we currently don't simplify peeled blocks at all.

I think it would be good to split this into two parts: One that changes the infrastructure to map to Value rather than Constant, making use of the existing SimplifyBinOp fold. And another that replaces constant folding with InstSimplify calls in the places it's not used yet.

If you're happy with the direction, do you mind if I land them without separate review? i.e. Can I interpret this as an LGTM for the split patches?

I'd mildly prefer not splitting the patches, but I'll do whatever will minimize the review back-and-forth. :)

nikic accepted this revision.May 25 2021, 9:35 AM

If you're happy with the direction, do you mind if I land them without separate review? i.e. Can I interpret this as an LGTM for the split patches?

I'd mildly prefer not splitting the patches, but I'll do whatever will minimize the review back-and-forth. :)

Okay, I don't feel particularly strongly about this, so let's say this LGTM modulo the note about ConstantExpr::getCompare().

This revision is now accepted and ready to land.May 25 2021, 9:35 AM
This revision was landed with ongoing or failed builds.May 26 2021, 8:41 AM
This revision was automatically updated to reflect the committed changes.