Page MenuHomePhabricator

[IndVarSimplify][LoopUtils] Track rewrite cost per unique BB (PR45835)
AbandonedPublic

Authored by dmajor on Mon, May 11, 9:14 AM.

Details

Summary

If a PHI node has multiple (identical) values for a given block, rewriteLoopExitValues must either rewrite all of them or none of them. Therefore, instead of tracking the cost for the individual values, track the cost per unique BB.

See PR45835

Diff Detail

Event Timeline

dmajor created this revision.Mon, May 11, 9:14 AM

Note: the test case does not currently fail on trunk before this change (although it does fail on the 10.0 release branch, where I would eventually like to get this merged) because after D73744 it is no longer blanket assumed that SCEVMinMaxExpr is high cost. Any pointers on how I could modify the test to get around that? (I'm not familiar with why this IR is considered to have a SCEVMinMaxExpr or what it would take to make it high cost.)

lebedev.ri retitled this revision from [IndVarSimplify][LoopUtils] Track rewrite cost per unique BB to [IndVarSimplify][LoopUtils] Track rewrite cost per unique BB (PR45835).Mon, May 11, 9:32 AM
lebedev.ri edited the summary of this revision. (Show Details)

Thank you for looking into it!

(In reply to dmajor from https://bugs.llvm.org/show_bug.cgi?id=45835#c3)

For anyone curious where the different values of HighCost come from...

When we're recursively looking at the second NAry operand [0] of the first
value, that operand is considered high cost due to [1]:

if (isa<SCEVMinMaxExpr>(S))
  return true;

When we're looking at the second NAry operand of the second value, it is
considered low cost due to [2]:

// If we can find an existing value for this scev available at the point "At"
// then consider the expression cheap.
if (At && getRelatedExistingExpansion(S, At, L))
  return false;

Yes, but it is still not obvious to me as to why that happens?
It's the same PHI node, we are asking about the same value, for the same basic block.
Why do we not find expansion first time but do find it second time?
Did we perform some expansion inbetween?

[0]
https://github.com/llvm/llvm-project/blob/release/10.x/llvm/lib/Analysis/
ScalarEvolutionExpander.cpp#L2198-L2205
[1]
https://github.com/llvm/llvm-project/blob/release/10.x/llvm/lib/Analysis/
ScalarEvolutionExpander.cpp#L2193-L2196
[2]
https://github.com/llvm/llvm-project/blob/release/10.x/llvm/lib/Analysis/
ScalarEvolutionExpander.cpp#L2135-L2138

Yes, but it is still not obvious to me as to why that happens?
It's the same PHI node, we are asking about the same value, for the same basic block.
Why do we not find expansion first time but do find it second time?
Did we perform some expansion inbetween?

If I'm understanding my recording correctly -- the reason the expansion was found the second time was that we expanded the value the first time, immediately after computing isHighCostExpansion: https://github.com/llvm/llvm-project/blob/release/10.x/llvm/lib/Transforms/Scalar/IndVarSimplify.cpp#L675

lebedev.ri added a comment.EditedMon, May 11, 12:01 PM

Yes, but it is still not obvious to me as to why that happens?
It's the same PHI node, we are asking about the same value, for the same basic block.
Why do we not find expansion first time but do find it second time?
Did we perform some expansion inbetween?

If I'm understanding my recording correctly -- the reason the expansion was found the second time was that we expanded the value the first time, immediately after computing isHighCostExpansion: https://github.com/llvm/llvm-project/blob/release/10.x/llvm/lib/Transforms/Scalar/IndVarSimplify.cpp#L675

But that doesn't make sense to me.
How/why could have we expanded it if we've decided that it is high cost?
Did we expand it just because, and then not actually used the expansion?

As discussed in IRC, there is a much more fundamental problem that needs to be solved.
I'll take a look.

lebedev.ri requested changes to this revision.Tue, May 12, 7:23 AM
This revision now requires changes to proceed.Tue, May 12, 7:23 AM
dmajor abandoned this revision.Tue, May 12, 7:34 AM

Abandoning in favor of D79787. Thanks!