[SCEV] Fully invalidate SCEVUnknown on RAUW

[nikic]

Summary

When a SCEVUnknown gets RAUWd, we currently drop it from the folding set, but don't forget memoized values. I believe we should be treating RAUW the same way as deletion here and invalidate all caches and dependent expressions.

I don't have any specific cases where this causes issues right now. This patch is inspired by the FIXME in https://reviews.llvm.org/D119488.

[reames]

I don't think is quite right. We can have SCEV forget all of it's memoized results, but we can't disallow a client hanging onto an expression containing a SCEVUnknown over a RAUW. Given that, I think we need to explicitly forget, but keep the bit about changing the value pointer to the new value.

[nikic]

In D120033#3329890, @reames wrote:

I don't think is quite right. We can have SCEV forget all of it's memoized results, but we can't disallow a client hanging onto an expression containing a SCEVUnknown over a RAUW. Given that, I think we need to explicitly forget, but keep the bit about changing the value pointer to the new value.

This is making the behavior the same as for erasing the value, so clients already need to deal with SCEVUnknown holding onto a nullptr (if they both cache it and inspect it that deeply).

Though I don't mind keeping the setValPtr(New), that seems harmless.

[nikic]

Don't replace value pointer with nullptr.

[mkazantsev]

When something is already erased from uniqueSCEVs, but is still in use, I'm pretty sure verify() should break somewhere on this situation. Is this something that is happening in reality?

I think we've been too permissive to holding various kinds of dangling pointers, and this caused us *very* nasty bugs. If we can avoid this situation, I think we must.

[nikic]

In D120033#3344649, @mkazantsev wrote:

When something is already erased from uniqueSCEVs, but is still in use, I'm pretty sure verify() should break somewhere on this situation. Is this something that is happening in reality?

I just checked that this patch does fix eliminate-max.ll with D119488, so clearly this does happen, and we do need to invalidate here. I think the reason why this is not more problematic in practice is that SCEVCallbackVH will perform a use-def walk on RAUW and remove values from the value map, so we end up mostly doing the invalidation through that mechanism. But of course, this is not quite the same, as the SCEV may be part of structures other than the value map etc.

[reames]

LGTM

llvm/lib/Analysis/ScalarEvolution.cpp

void SCEVUnknown::deleted() {
   // Remove this SCEVUnknown from the uniquing map.
   SE->UniqueSCEVs.RemoveNode(this);
 
   // Release the value.
   setValPtr(nullptr);
 }
 
 void SCEVUnknown::allUsesReplacedWith(Value *New) {
+  // Clear this SCEVUnknown from various maps.
+  SE->forgetMemoizedResults(this);
+
   // Remove this SCEVUnknown from the uniquing map.
   SE->UniqueSCEVs.RemoveNode(this);
 
-  // Update this SCEVUnknown to point to the new value. This is needed
-  // because there may still be outstanding SCEVs which still point to
-  // this SCEVUnknown.
+  // Replace the value pointer in case someone is still using this SCEVUnknown.
   setValPtr(New);
 }
 
 bool SCEVUnknown::isSizeOf(Type *&AllocTy) const {
   if (ConstantExpr *VCE = dyn_cast<ConstantExpr>(getValue()))
     if (VCE->getOpcode() == Instruction::PtrToInt)
       if (ConstantExpr *CE = dyn_cast<ConstantExpr>(VCE->getOperand(0)))
         if (CE->getOpcode() == Instruction::GetElementPtr &&