[SCEV] Skip instrs with non-scevable types in forget[Loop,Value].

[fhahn]

Summary

No SCEVs are formed for instructions with non-scevable types, so no
other SCEV expressions can depend on them. Skip those instructions and
their users when invalidating SCEV expressions.

To catch potential missed cases, the full def-use chains are traversed
after the cleanup to assert no entries in ValueExprMap remain.

Depends on D144847.

[nikic]

llvm/lib/Analysis/ScalarEvolution.cpp

8411

Hm, isn't the verification supposed to omit this check?

[mkazantsev]

This comment has been deleted.

llvm/include/llvm/Analysis/ScalarEvolution.h

2049 ↗

(On Diff #500689)

typo: Worlist -> Worklist

llvm/lib/Analysis/ScalarEvolution.cpp

8411

I guess we can skip it. We can't have them in ValueExprMap anyways.

[mkazantsev]

Should this be under VerifySCEV ?

[mkazantsev]

llvm/lib/Analysis/ScalarEvolution.cpp

8411

Maybe even assert on that.

[fhahn]

Adjust condition to skip instructions in verifyAllUsersClearedFromMap.

[fhahn]

In D144848#4154876, @mkazantsev wrote:

Should this be under VerifySCEV ?

The main reason I didn't use VerifySCEV is that this would require a check of the VerifySCEV variable on each verifyAllUsersClearedFromMap, whereas with the current setup it is free for builds without assertions.

llvm/lib/Analysis/ScalarEvolution.cpp

8411

The issue is that non-SCEVable instructions can be operands for SCEVable instructions (e.g. a floating point instruction used by an fcmp). I think in all those cases, the SCEV-able instruction needs to be a SCEVUnknown and the SCEV def-use chain is broken and we should be able to stop invalidation for this instruction.

I updated the condition to more explicitly check for this.

[fhahn]

Also fix typo

[fhahn]

llvm/include/llvm/Analysis/ScalarEvolution.h

2049 ↗

(On Diff #500689)

Fixed, thanks!

[mkazantsev]

LG, thanks!

[nikic]

llvm/lib/Analysis/ScalarEvolution.cpp

8411

I think the general change here is right, but I'm not sure this verification is actually verifying anything useful. We aren't going to invalidate the same set of values (by design), so there doesn't really seem anything to verify.

My understanding of this change is that we only want to visit users for which the value may contribute towards the user's SCEV expression. Non-scevable types are one case that can never contribute. The other are instructions that always produce SCEVUnknown, e.g. it doesn't really make sense to follow the use chain across a load regardless of which types it works on (this is probably more common than non-scevable types).

The caveat here is that while they cannot contribute towards SCEVs, it's still theoretically possible to contribute towards cached analysis results, e.g. a SCEVUnknown could be caching no longer valid ValueTracking results.

[fhahn]

llvm/lib/Analysis/ScalarEvolution.cpp

8411

The current verification here is not super useful for the change here itself, the main use case where it would become more useful should be D144849. I can also just remove it from the current patch.

[nikic]

llvm/lib/Analysis/ScalarEvolution.cpp

8411

In that case I'd drop it from this patch.

[fhahn]

Strip off verification. I'll update the description and I am planning on committing this soon.

llvm/lib/Analysis/ScalarEvolution.cpp

void ScalarEvolution::forgetAllLoops() {
   FoldCacheUser.clear();
 }
 void ScalarEvolution::visitAndClearUsers(
     SmallVectorImpl<Instruction *> &Worklist,
     SmallPtrSetImpl<Instruction *> &Visited,
     SmallVectorImpl<const SCEV *> &ToForget) {
   while (!Worklist.empty()) {
     Instruction *I = Worklist.pop_back_val();
+    if (!isSCEVable(I->getType()))
+      continue;
 
     ValueExprMapType::iterator It =
         ValueExprMap.find_as(static_cast<Value *>(I));
     if (It != ValueExprMap.end()) {
       eraseValueFromMap(It->first);
       ToForget.push_back(It->second);
       if (PHINode *PN = dyn_cast<PHINode>(I))
         ConstantEvolutionLoopExitValue.erase(PN);
     }
 
     PushDefUseChildren(I, Worklist, Visited);
   }
 }
 
 void ScalarEvolution::forgetLoop(const Loop *L) {
   SmallVector<const Loop *, 16> LoopWorklist(1, L);
   SmallVector<Instruction *, 32> Worklist;
   SmallPtrSet<Instruction *, 16> Visited;
   SmallVector<const SCEV *, 16> ToForget;
 
   // Iterate over all the loops and sub-loops to drop SCEV information.
   while (!LoopWorklist.empty()) {
     auto *CurrL = LoopWorklist.pop_back_val();
 
     // Drop any stored trip count value.
     forgetBackedgeTakenCounts(CurrL, /* Predicated */ false);
     forgetBackedgeTakenCounts(CurrL, /* Predicated */ true);
 
     // Drop information about predicated SCEV rewrites for this loop.
     for (auto I = PredicatedSCEVRewrites.begin();