[SCEV][NFC] Smarter implementation of isAvailableAtLoopEntry

[mkazantsev]

Summary

isAvailableAtLoopEntry duplicates logic of properlyDominates after checking invariance.
This patch replaces this logic with invocation of this method which is more profitable
because it supports caching.

[mkazantsev]

Ping

[sanjoy]

lib/Analysis/ScalarEvolution.cpp

2237 ↗

(On Diff #136681)

Looks like properlyDominates is not transitive when this used to be transitive?

(It could be that properlyDominates is incorrect itself and needs to be transitive too - if yes, let's make that change first.)

[mkazantsev]

lib/Analysis/ScalarEvolution.cpp

2237 ↗

(On Diff #136681)

I didn't get what do you mean under "transitive" in this context. The only significant difference I see is that getBlockDisposition is implemented via recursion with global caching and this is via SCEV traversal with local caching. Global caching is more profitable in this case since we can end up checking the same SCEVs again and again. I don't think there are any functional differences.

[sanjoy]

lib/Analysis/ScalarEvolution.cpp

2237 ↗

(On Diff #136681)

Yes, you're right, I missed the recursion in ScalarEvolution::computeBlockDisposition.

Do you mind, as a later change, rewriting ScalarEvolution::computeBlockDisposition to use SCEVTraversal? That's more idiomatic and reduces (although only by a little bit :) ) the possibility of stack overflow.

[mkazantsev]

lib/Analysis/ScalarEvolution.cpp

2237 ↗

(On Diff #136681)

I think we could do it, yes. But in this case we cache the same data in both local and global cache. I think we can replace it with a global traversal or something. :)

llvm/trunk/lib/Analysis/ScalarEvolution.cpp

if (!(SignOrUnsignWrap & SCEV::FlagNUW)) {
         Flags = ScalarEvolution::setFlags(Flags, SCEV::FlagNUW);
     }
   }
 
   return Flags;
 }
 
 bool ScalarEvolution::isAvailableAtLoopEntry(const SCEV *S, const Loop *L) {
-  if (!isLoopInvariant(S, L))
-    return false;
-  // If a value depends on a SCEVUnknown which is defined after the loop, we
-  // conservatively assume that we cannot calculate it at the loop's entry.
-  struct FindDominatedSCEVUnknown {
-    bool Found = false;
-    const Loop *L;
-    DominatorTree &DT;
-    LoopInfo &LI;
-
-    FindDominatedSCEVUnknown(const Loop *L, DominatorTree &DT, LoopInfo &LI)
-        : L(L), DT(DT), LI(LI) {}
-
-    bool checkSCEVUnknown(const SCEVUnknown *SU) {
-      if (auto *I = dyn_cast<Instruction>(SU->getValue())) {
-        if (DT.dominates(L->getHeader(), I->getParent()))
-          Found = true;
-        else
-          assert(DT.dominates(I->getParent(), L->getHeader()) &&
-                 "No dominance relationship between SCEV and loop?");
-      }
-      return false;
-    }
-
-    bool follow(const SCEV *S) {
-      switch (static_cast<SCEVTypes>(S->getSCEVType())) {
-      case scConstant:
-        return false;
-      case scAddRecExpr:
-      case scTruncate:
-      case scZeroExtend:
-      case scSignExtend:
-      case scAddExpr:
-      case scMulExpr:
-      case scUMaxExpr:
-      case scSMaxExpr:
-      case scUDivExpr:
-        return true;
-      case scUnknown:
-        return checkSCEVUnknown(cast<SCEVUnknown>(S));
-      case scCouldNotCompute:
-        llvm_unreachable("Attempt to use a SCEVCouldNotCompute object!");
-      }
-      return false;
-    }
-
-    bool isDone() { return Found; }
-  };
-
-  FindDominatedSCEVUnknown FSU(L, DT, LI);
-  SCEVTraversal<FindDominatedSCEVUnknown> ST(FSU);
-  ST.visitAll(S);
-  return !FSU.Found;
+  return isLoopInvariant(S, L) && properlyDominates(S, L->getHeader());
 }
 
 /// Get a canonical add expression, or something simpler if possible.
 const SCEV *ScalarEvolution::getAddExpr(SmallVectorImpl<const SCEV *> &Ops,
                                         SCEV::NoWrapFlags Flags,
                                         unsigned Depth) {
   assert(!(Flags & ~(SCEV::FlagNUW | SCEV::FlagNSW)) &&
          "only nuw or nsw allowed");