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.
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.)
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  of the first
value, that operand is considered high cost due to :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 :// 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?
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