This is an archive of the discontinued LLVM Phabricator instance.

[SCEV] Compute symbolic exit count for 'and' conditions
ClosedPublic

Authored by mkazantsev on Dec 6 2022, 1:28 AM.

Details

Summary

If loop exits by condition like A < B && X < Y, and at least one of symbolic max
exit counts for these conditions is known, it can be used as estimate of symbolic
max exit count for whole branch. If both are known, then we can use their umin
as the estimate.

Diff Detail

Event Timeline

mkazantsev created this revision.Dec 6 2022, 1:28 AM
Herald added a project: Restricted Project. · View Herald TranscriptDec 6 2022, 1:28 AM
Herald added a subscriber: hiraditya. · View Herald Transcript
mkazantsev requested review of this revision.Dec 6 2022, 1:28 AM
Herald added a project: Restricted Project. · View Herald TranscriptDec 6 2022, 1:28 AM
mkazantsev added inline comments.
llvm/lib/Analysis/ScalarEvolution.cpp
9003

This looks fishy to me, but one of tests is failing without this. It looks like we can make an improvement somewhere else to get rid of two checks above, but I haven't figured how it happens.

nikic added inline comments.Dec 6 2022, 2:10 AM
llvm/lib/Analysis/ScalarEvolution.cpp
8718

Why the new condition here?

llvm/test/Analysis/ScalarEvolution/widenable-condition.ll
27 ↗(On Diff #480380)

I don't really get why this patch introduces these changes (i.e. why this wasn't the result previously). Aren't we already assigning the constant max to the symbol max if there is no exact?

nikic added inline comments.Dec 6 2022, 2:15 AM
llvm/test/Analysis/ScalarEvolution/symbolic_max_exit_count.ll
227

I'm missing a test for the case where we actually produce a umin_seq.

mkazantsev added inline comments.Dec 7 2022, 12:59 AM
llvm/lib/Analysis/ScalarEvolution.cpp
8718

The old logic was: put to ExitCounts whenever an exact count is known. Then, when we request loop's exact exit count, we traverse through them and take umin.

Now in the test symbolic_max_exit_count.ll exact is not known. But we still want to put it into this vector to be able to request symbolic exit count.

That's why now we put it if either exact or symbolic is known. I think we can relax it to just symbolic (exact always implies it).

llvm/test/Analysis/ScalarEvolution/symbolic_max_exit_count.ll
227

In fact we have it in test/Analysis/ScalarEvolution/exit-count-select-safe.ll. This patch preserves current behavior, however if I remove /*IsSequential*/ true, it changes. Is it enough or you want a new one specifically for this?

llvm/test/Analysis/ScalarEvolution/widenable-condition.ll
27 ↗(On Diff #480380)

This is indeed strange. I will investigate.

mkazantsev planned changes to this revision.Dec 7 2022, 1:06 AM

Planned separation into 2 pieces.

llvm/test/Analysis/ScalarEvolution/widenable-condition.ll
27 ↗(On Diff #480380)

Funny thing, it happened exactly because I've added this

if (EL.ExactNotTaken != getCouldNotCompute() ||
    EL.SymbolicMaxNotTaken != getCouldNotCompute())

The story is simple: symbolic exit count was exaluated as constant, but then ExitCount simply wasn't added to the array because Exact was missing.

I will split it off into a separate fix.

mkazantsev updated this revision to Diff 480811.Dec 7 2022, 1:27 AM

Now this is duing purely what it claims to do.

nikic added inline comments.Dec 7 2022, 2:11 AM
llvm/test/Analysis/ScalarEvolution/symbolic_max_exit_count.ll
227

If I understand correctly, the tests in exit-count-select-safe.ll cover the case where we have an exact (but umin_seq) exit count. I think it still makes sense to have a test for the case where we don't have an exact count, but do have a symbolic umin_seq count.

We probably also want to use umin or umin_seq depending on isa<BinaryOperator>(ExitCond), same as is done for the ExactNotTaken case a few lines before the new code.

mkazantsev added inline comments.Dec 7 2022, 2:33 AM
llvm/test/Analysis/ScalarEvolution/symbolic_max_exit_count.ll
227

Good point, I'll try to wright such a test.

mkazantsev updated this revision to Diff 480863.Dec 7 2022, 5:11 AM

I've added a test which I think should end up with umin_seq, but it's umin. I don't know why, maybe a bug?

nikic added a comment.Dec 7 2022, 6:44 AM

I've added a test which I think should end up with umin_seq, but it's umin. I don't know why, maybe a bug?

Indeed, we were missing a umin_seq when computing the symbolic max BE count. Fixed in https://github.com/llvm/llvm-project/commit/4d97a914d7aef6c95cd95669f99e5d32899e165a.

However, this indicates that this test is still not covering the right code path: I think what you need is a nested (A1 and A2) and (B1 and B2) structure where we get symbolic counts C1 and C2 from the inner ands and then those get combined. That will give you the umin from the new code path.

I've added a test which I think should end up with umin_seq, but it's umin. I don't know why, maybe a bug?

Indeed, we were missing a umin_seq when computing the symbolic max BE count. Fixed in https://github.com/llvm/llvm-project/commit/4d97a914d7aef6c95cd95669f99e5d32899e165a.

However, this indicates that this test is still not covering the right code path: I think what you need is a nested (A1 and A2) and (B1 and B2) structure where we get symbolic counts C1 and C2 from the inner ands and then those get combined. That will give you the umin from the new code path.

Will do, but I don't quite get why. In my example, if %start_1 is 0, we will bail on 1st exit and never use %start_2. So there is no UB if start_1 = 0 and start_2 = poison. As far as I understood what umin_seq is, it's trying to address exactly this case.

Rebased on top of more tests with combined arith and logical AND conditions.

As far as I understand the topic, it should be umin in test_two_phis_arithmetic_and and umin_seq in test_two_phis_logical_and. In practice it's umin_seq in the former case and nothing in the later.

Do we really want to block the patch on this? Looks like umin_seq requires a lot of work to apply where it's really needed.

nikic added inline comments.Dec 7 2022, 11:43 PM
llvm/lib/Analysis/ScalarEvolution.cpp
8984

This should pass !isa<BinaryOperator>(ExitCond) as in the ExactNotTaken case above.

llvm/test/Analysis/ScalarEvolution/symbolic_max_exit_count.ll
394

This should be select i1 %c1, i1 %c2, i1 false. You made this an or rather than an and.

mkazantsev added inline comments.Dec 8 2022, 12:22 AM
llvm/test/Analysis/ScalarEvolution/symbolic_max_exit_count.ll
394

You're right, what I've done is OR... /facepalm

Let me fix that.

mkazantsev added inline comments.Dec 8 2022, 12:39 AM
llvm/lib/Analysis/ScalarEvolution.cpp
8984

I missed that one, thanks for reminding!

Fixed umin(seq)

mkazantsev marked 4 inline comments as done.Dec 8 2022, 12:44 AM
nikic accepted this revision.Dec 8 2022, 12:57 AM

LGTM

This revision is now accepted and ready to land.Dec 8 2022, 12:57 AM
This revision was landed with ongoing or failed builds.Dec 8 2022, 1:05 AM
This revision was automatically updated to reflect the committed changes.