[GVN] Don't use the eliminated load as an available value in phi construction

[john.brawn]

Summary

In ConstructSSAForLoadSet if an available value is actually the load that we're doing SSA construction to eliminate, then we can omit it as SSAUpdate will add in the value for the phi that will be replacing it anyway. This can result in simpler IR which can allow further optimisation.

[mkazantsev]

To me it looks fine, but please wait for Daniel or Eli to take a look.

[• dberlin]

So this looks like a really weird optimization to avoid AA being broken.
As you say, the code it inserts will be fixed up later (and you are taking an O(1) function and making it O(N).
We should just fix AA.

It should see no difference between the two.
If we really can't fix AA, i'd like to understand why before we go this route.
Because we shouldnt' be working around these problems this way.

[• dberlin]

In particular, i feel this way because GVN should already get your case
without this.
The fact that it doesn't is an issue with AA.
Working around it like this only fixes GVN's ability to optimize this.
There will be plenty of cases something *else* could eliminate code like
that will not be able to
Fixing AA fixes it for everyone (and doesn't require pass-specific
workarounds).

So i'd like to understand what is going wrong in AA before we start trying
to hack around it in GVN.

[john.brawn]

Alias analysis uses GetUnderlyingObject from ValueTracking to figure out the 'real' value of the phi and that uses SimplifyInstruction, so I think there's where we should do this. SimplifyPHINode already handles the simple case of a single phi node, and extending it to work on a chain of phi nodes (which is what we need here) looks doable though a bit fiddly to get right in all cases.

[john.brawn]

I've posted by attempt to fix this in alias anlysis in D44564, but the problem is that it's actually InstSimplify that's the underlying thing being used to figure out the value of the PHI, and that's used all over the place and causes knock-on changes that require work to be done elsewhere.

[• dberlin]

FWIW: It's also possible to just fix AA without InstSimplify just by
replacing what it uses with something more powerful.
That would avoid disturbing the other users.

[reames]

lib/Transforms/Scalar/GVN.cpp

786

Maybe I'm missing something, but couldn't we get the same effect you're looking for by adding the check for LI as our AV into this loop? This would have the effect of telling the SSAUpdator about only one def in your example which should avoid the need for any phi creation.

Then there's no concern about change in O() since this loop is already O(ValuesPerBloc).

To be clear, I don't really care about the side effect of "fixing" AA, but reducing redundant IR always seems like a win since it's likely to let the rest of the GVN run be more effective.

[john.brawn]

lib/Transforms/Scalar/GVN.cpp

786

I hadn't realised that SSAUpdater would work if you did that, but from some testing it looks like that does work. I'll update this patch to do that. It doesn't solve the problem entirely in more complicated cases though, which will need better alias analysis (which I'll continue working on).

[john.brawn]

Go with the approach of not adding the eliminated load to SSAUpdate.

[john.brawn]

Ping.

[john.brawn]

Adjusted to require that the load must be available in the block the load is in, as in some cases not having that causes things to go wrong (test for this also added).

[john.brawn]

Ping.

[john.brawn]

Ping.

[reames]

Sorry, thought I'd reviewed this. I apparently didn't hit submit.

lib/Transforms/Scalar/GVN.cpp

787

Don't you need to add the original LI to the SSA updater at least once? Starting at the original block?

[john.brawn]

lib/Transforms/Scalar/GVN.cpp

787

There's no inherent need to do that, I'm pretty sure. Adding LI to the SSA updater really means adding the value that LI will be replaced with, which is exactly what the SSA updater is itself deciding. So adding LI as available value in the block it's in is like saying "the value in this block is the value that's going to be in this block", and the SSA updater already knows that.

[john.brawn]

Ping.

[john.brawn]

Ping.

[reames]

LGTM

lib/Transforms/Scalar/GVN.cpp

787

You are correct. I was confusing myself by thinking the following two (wrong) things:

1. That we still had to reason about potentially unavailable blocks at this point.
2. That there might be store somewhere in the block. (Can't because otherwise we'd not have circled all the way around.)

lib/Transforms/Scalar/GVN.cpp

 }
 
 /// Given a set of loads specified by ValuesPerBlock,
 /// construct SSA form, allowing us to eliminate LI.  This returns the value
 /// that should be used at LI's definition site.
 static Value *ConstructSSAForLoadSet(LoadInst *LI,
                          SmallVectorImpl<AvailableValueInBlock> &ValuesPerBlock,
                                      GVN &gvn) {
-  // Check for the fully redundant, dominating load case.  In this case, we can
-  // just use the dominating value directly.
-  if (ValuesPerBlock.size() == 1 &&
-      gvn.getDominatorTree().properlyDominates(ValuesPerBlock[0].BB,
+  // Check if we have a fully redundant load by checking if we have only one
+  // available value, not counting the load we're going to be eliminating.
+  const AvailableValueInBlock *SingleValue = nullptr;
+  for (const AvailableValueInBlock &AV : ValuesPerBlock) {
+    // Discount this available value if it's the load we're eliminating.
+    if ((AV.AV.isSimpleValue() && AV.AV.getSimpleValue() == LI) ||
+        (AV.AV.isCoercedLoadValue() && AV.AV.getCoercedLoadValue() == LI)) {
+      continue;
+    }
+    // If we've already seen a value then we have more than one, so we don't
+    // have a single value.
+    if (SingleValue) {
+      SingleValue = nullptr;
+      break;
+    }
+    // We haven't seen any available values before this, so if we have a single
+    // value this is it.
+    SingleValue = &AV;
+  }
+  // If we have a fully redundant load check if it dominates LI, as in that case
+  // we can just use the dominating value directly.
+  if (SingleValue &&
+      gvn.getDominatorTree().properlyDominates(SingleValue->BB,
                                                LI->getParent())) {
-    assert(!ValuesPerBlock[0].AV.isUndefValue() &&
+    assert(!SingleValue->AV.isUndefValue() &&
            "Dead BB dominate this block");
-    return ValuesPerBlock[0].MaterializeAdjustedValue(LI, gvn);
+    return SingleValue->MaterializeAdjustedValue(LI, gvn);
   }
 
   // Otherwise, we have to construct SSA form.
   SmallVector<PHINode*, 8> NewPHIs;
   SSAUpdater SSAUpdate(&NewPHIs);
   SSAUpdate.Initialize(LI->getType(), LI->getName());
 
   for (const AvailableValueInBlock &AV : ValuesPerBlock) {
     BasicBlock *BB = AV.BB;
 
     if (SSAUpdate.HasValueForBlock(BB))
       continue;
 
     SSAUpdate.AddAvailableValue(BB, AV.MaterializeAdjustedValue(LI, gvn));
   }
 
   // Perform PHI construction.
   return SSAUpdate.GetValueInMiddleOfBlock(LI->getParent());
 }
 
 Value *AvailableValue::MaterializeAdjustedValue(LoadInst *LI,
                                                 Instruction *InsertPt,

test/Transforms/GVN/pre-after-rle.ll

+; RUN: opt -gvn -S < %s | FileCheck %s
+
+declare noalias i8* @malloc(i64)
+
+; Detecting that %s is fully redundant should let us detect that %w is partially
+; redundant.
+define void @fn(i32** noalias %start, i32* %width, i32 %h) {
+entry:
+  %call = tail call noalias i8* @malloc(i64 1024)
+  %call.cast = bitcast i8* %call to i32*
+  store i32* %call.cast, i32** %start, align 8
+  br label %preheader
+
+preheader:
+  %cmp = icmp slt i32 1, %h
+  br i1 %cmp, label %body, label %exit
+
+; CHECK-LABEL: preheader.body_crit_edge:
+; CHECK: load i32, i32* %width, align 8
+
+; CHECK-LABEL: body:
+; CHECK-NOT: load i32*, i32** %start, align 8
+; CHECK-NOT: load i32, i32* %width, align 8
+body:
+  %j = phi i32 [ 0, %preheader ], [ %j.next, %body ]
+  %s = load i32*, i32** %start, align 8
+  %idx = getelementptr inbounds i32, i32* %s, i64 0
+  store i32 0, i32* %idx, align 4
+  %j.next = add nuw nsw i32 %j, 1
+  %w = load i32, i32* %width, align 8
+  %cmp3 = icmp slt i32 %j.next, %w
+  br i1 %cmp3, label %body, label %preheader
+
+exit:
+  ret void
+}