[SCEV] Don't invalidate past dependency-breaking instructions

[nikic]

Summary

When invalidating a value, we walk all users of that value and invalidate them as well. This can be very expensive for large use graphs.

However, we only need to invalidate a user U of instruction I if SCEV(U) can depend on SCEV(I). This is not the case if U is an instruction that always produces a SCEVUnknown, such as a load. If the load pointer operand is invalidated, there is no need to invalidate the load result, which is completely unrelated from a SCEV perspective.

This is a decent compile-time improvement in some cases: http://llvm-compile-time-tracker.com/compare.php?from=da4fcb0c0b281746067f92d8804c18dbce4269bd&to=3d7d37d4cc0118af994c70037753358868f25147&stat=instructions:u

[mkazantsev]

Consider example:

%sum = add i32 %x, %y
%load_p= gep ptr %p, i32 %sum
%load1 = load %i32 load_p

if (%load_1 == %sum) {
  %load_2 = load %i32 load_p
  %sum_2 = add i32 %load_2, 2
}

Here we can theoretically prove that SCEV for %load_2 is %x + %y (same as %sum) and %sum2 = %x + %y + 1.

Now, imagine that we invalidate %x. With your patch, if I understand it correctly, %sum_2 won't be invalidated.

[nikic]

In D149323#4304636, @mkazantsev wrote:

Consider example:

%sum = add i32 %x, %y
%load_p= gep ptr %p, i32 %sum
%load1 = load %i32 load_p

if (%load_1 == %sum) {
  %load_2 = load %i32 load_p
  %sum_2 = add i32 %load_2, 2
}

Here we can theoretically prove that SCEV for %load_2 is %x + %y (same as %sum) and %sum2 = %x + %y + 1.

Now, imagine that we invalidate %x. With your patch, if I understand it correctly, %sum_2 won't be invalidated.

Not sure I get the example. %load1 and %load_2 will both always be SCEVUnknown (loads always are, if they are SCEVable at all). The %x + %y is part of the load address, but it doesn't impact the SCEV of the load itself. It's part of %load_p, but that one will continue to be invalidated normally.

[mkazantsev]

If we prove that two values are the same, their SCEVs can also be proven the same (and not necessarity SCEVUnknown). If a load is equal to some non-load. then load's SCEV can be non-SCEVUnknown.

[nikic]

In D149323#4304765, @mkazantsev wrote:

If we prove that two values are the same, their SCEVs can also be proven the same (and not necessarity SCEVUnknown). If a load is equal to some non-load. then load's SCEV can be non-SCEVUnknown.

I think your example is a bit confusing because it uses %sum both in the load address and the comparison. Let's consider this variant where %v and %load1 are only related by the comparison:

%load1 = load i32, ptr %p
if (%load1 == %v) {
   %load2 = load i32, ptr %p
}

If we determined that getSCEV(%load2) = getSCEV(%v) based on the comparison and memory dependence reasoning here, then invalidating %v would not invalidate %load2 even with the current implementation, because there is no use-def relationship between them. We would have to invalidate based on potential memory dependences, which is not feasible in practice.

While SCEV could in theory do something like this, it doesn't do this currently, and it's very unlikely that it will do so in the future. If it does do so in the future, we can change this code to reflect the new reality...

[nikic]

Add assertion to make sure the assumption about SCEVUnknown is correct.

[mkazantsev]

Ok thanks, at least we'll know if it breaks.

llvm/lib/Analysis/ScalarEvolution.cpp

void ScalarEvolution::insertValueToMap(Value *V, const SCEV *S) {
   // inferred nowrap flags.
   auto It = ValueExprMap.find_as(V);
   if (It == ValueExprMap.end()) {
     ValueExprMap.insert({SCEVCallbackVH(V, this), S});
     ExprValueMap[S].insert(V);
   }
 }
 
+/// Determine whether this instruction is either not SCEVable or will always
+/// produce a SCEVUnknown. We do not have to walk past such instructions when
+/// invalidating.
+static bool isAlwaysUnknown(const Instruction *I) {
+  switch (I->getOpcode()) {
+  case Instruction::Load:
+    return true;
+  default:
+    return false;
+  }
+}
+
 /// Return an existing SCEV if it exists, otherwise analyze the expression and
 /// create a new one.
 const SCEV *ScalarEvolution::getSCEV(Value *V) {
   assert(isSCEVable(V->getType()) && "Value is not SCEVable!");
 
   if (const SCEV *S = getExistingSCEV(V))
     return S;
-  return createSCEVIter(V);
+  const SCEV *S = createSCEVIter(V);
+  assert((!isa<Instruction>(V) || !isAlwaysUnknown(cast<Instruction>(V)) ||
+          isa<SCEVUnknown>(S)) &&
+         "isAlwaysUnknown() instruction is not SCEVUnknown");
+  return S;
 }
 
 const SCEV *ScalarEvolution::getExistingSCEV(Value *V) {
   assert(isSCEVable(V->getType()) && "Value is not SCEVable!");
 
   ValueExprMapType::iterator I = ValueExprMap.find_as(V);
   if (I != ValueExprMap.end()) {
     const SCEV *S = I->second;

 
 /// Push users of the given Instruction onto the given Worklist.
 static void PushDefUseChildren(Instruction *I,
                                SmallVectorImpl<Instruction *> &Worklist,
                                SmallPtrSetImpl<Instruction *> &Visited) {
   // Push the def-use children onto the Worklist stack.
   for (User *U : I->users()) {
     auto *UserInsn = cast<Instruction>(U);
+    if (isAlwaysUnknown(UserInsn))
+      continue;
     if (Visited.insert(UserInsn).second)
       Worklist.push_back(UserInsn);
   }
 }
 
 namespace {
 
 /// Takes SCEV S and Loop L. For each AddRec sub-expression, use its start