Fix bug 25440: GVN assertion after coercing loads

[weimingz]

Summary

when coercing loads, it inserts some instructions, which have no GV assigned.

https://llvm.org/bugs/show_bug.cgi?id=25440

[• dberlin]

This patch doesn't make sense.

Either you need to have it assign the GV and fix the leader tables so that
the lookup at this point succeeds (which is ideal), or VN.lookup(op) ==
null, it should set success=false and break.

The former is *greatly* preferable to the latter.

What you've done here makes no sense, because findLeader(anything, <new
value number>) will always return nothing, since addLeaderToTable has not
been called on the new value number.
All you are doing in that case is wasting time calling findLeader.

[weimingz]

This patch is just for review purpose. It only handles the cases in GetLoadValueForLoad().
If the fix is right, I can apply it to other routines like CoerceAvailableValueToLoadType

[• dberlin]

lib/Transforms/Scalar/GVN.cpp

646

Close, but if you are adding only the new instructions, I believe this should be unconditional.

Think of the leader table as "the list of things in the program that have a given value number".

Even if the value number existed, if this is a new instruction, it's still a new thing that has that value number, and should still end up in the leader table.

(I'd also probably name it addNewInstruction or something)

1231

These definitely look right

[weimingz]

lib/Transforms/Scalar/GVN.cpp

646

Is it possible that the new instruction has some existing GVN ? I was thinking calling processInstruction, but concerned that it may have side effect.

[• dberlin]

lib/Transforms/Scalar/GVN.cpp

646

It is possible the new instruction has an existing VN.

Imagine instruction is the lshr you have below, of a constant and a value.

Imagine we coerce a bunch of loads.

We are highly likely to insert the lshr a bunch of times, and it will be the same each time.
So t's entirely possible that lshr instruction already exists in the program, and vn_lookup_or_add will then find a value number for this instruction.

It happens that the current VN is not great, and so it won't find stuff unless they are pretty much completely identical. processInstruction does a lot of forward propagation to try to make things look the same to account for this.

You also can't call processInstruction here because it may mess with or delete things or change the CFG or ...

(One of the other nice things new gvn does is split analysis and elimination, so that would never happen. It would be hard to fix this in existing GVN)

So i think what you are doing here is pretty much the best you can do in this situation, it should probably just be unconditional, as i mentioned.

[weimingz]

lib/Transforms/Scalar/GVN.cpp

646

Cool. Thanks for the detailed explanation.

[weimingz]

This patch set VNs for newly created instructions.

[• dberlin]

LGTM

It would be super nice to have testcases for all of these, but i suspect that would be pretty hard to test by hand.

I wonder if it doesn't make sense to have, at the end of GVN:

#ifdef DEBUG

for each instruction

assert that VN.lookup returns a non-null value

#endif
to make sure we catch all the cases this can happen in.

Because i suspect it happens in loadpre as well, when phitranslate inserts instructions, etc.

lib/Transforms/Scalar/GVN.cpp

public:
     void markInstructionForDeletion(Instruction *I) {
       VN.erase(I);
       InstrsToErase.push_back(I);
     }
 
     DominatorTree &getDominatorTree() const { return *DT; }
     AliasAnalysis *getAliasAnalysis() const { return VN.getAliasAnalysis(); }
     MemoryDependenceAnalysis &getMemDep() const { return *MD; }
+
+    // Assign VNs for instructions newly created during GVN optimization.
+    void addNewInstruction(Value *Val) {
+      if (Instruction *I = dyn_cast<Instruction>(Val)) {
+        unsigned Num = VN.lookup_or_add(I);
+        addToLeaderTable(Num, I, I->getParent());
+      }
+    }
+
   private:
     /// Push a new Value to the LeaderTable onto the list for its value number.
     void addToLeaderTable(uint32_t N, Value *V, const BasicBlock *BB) {
       LeaderTableEntry &Curr = LeaderTable[N];
       if (!Curr.Val) {
         Curr.Val = V;
         Curr.BB = BB;
         return;

 
 /// This function is called when we have a
 /// memdep query of a load that ends up being a clobbering store.  This means
 /// that the store provides bits used by the load but we the pointers don't
 /// mustalias.  Check this case to see if there is anything more we can do
 /// before we give up.
 static Value *GetStoreValueForLoad(Value *SrcVal, unsigned Offset,
                                    Type *LoadTy,
-                                   Instruction *InsertPt, const DataLayout &DL){
+                                   Instruction *InsertPt, const DataLayout &DL,
+                                   GVN &gvn){
   LLVMContext &Ctx = SrcVal->getType()->getContext();
 
   uint64_t StoreSize = (DL.getTypeSizeInBits(SrcVal->getType()) + 7) / 8;
   uint64_t LoadSize = (DL.getTypeSizeInBits(LoadTy) + 7) / 8;
 
   IRBuilder<> Builder(InsertPt);
 
   // Compute which bits of the stored value are being used by the load.  Convert
   // to an integer type to start with.
-  if (SrcVal->getType()->getScalarType()->isPointerTy())
+  if (SrcVal->getType()->getScalarType()->isPointerTy()) {
     SrcVal = Builder.CreatePtrToInt(SrcVal,
         DL.getIntPtrType(SrcVal->getType()));
-  if (!SrcVal->getType()->isIntegerTy())
+    gvn.addNewInstruction(SrcVal);
+  }
+  if (!SrcVal->getType()->isIntegerTy()) {
     SrcVal = Builder.CreateBitCast(SrcVal, IntegerType::get(Ctx, StoreSize*8));
+    gvn.addNewInstruction(SrcVal);
+  }
 
   // Shift the bits to the least significant depending on endianness.
   unsigned ShiftAmt;
   if (DL.isLittleEndian())
     ShiftAmt = Offset*8;
   else
     ShiftAmt = (StoreSize-LoadSize-Offset)*8;
 
-  if (ShiftAmt)
+  if (ShiftAmt) {
     SrcVal = Builder.CreateLShr(SrcVal, ShiftAmt);
+    gvn.addNewInstruction(SrcVal);
+  }
 
-  if (LoadSize != StoreSize)
+  if (LoadSize != StoreSize) {
     SrcVal = Builder.CreateTrunc(SrcVal, IntegerType::get(Ctx, LoadSize*8));
+    gvn.addNewInstruction(SrcVal);
+  }
 
   return CoerceAvailableValueToLoadType(SrcVal, LoadTy, Builder, DL);
 }
 
 /// This function is called when we have a
 /// memdep query of a load that ends up being a clobbering load.  This means
 /// that the load *may* provide bits used by the load but we can't be sure
 /// because the pointers don't mustalias.  Check this case to see if there is
if (Offset+LoadSize > SrcValSize) {
     // load completely because it is already in the value numbering table.
     IRBuilder<> Builder(SrcVal->getParent(), ++BasicBlock::iterator(SrcVal));
     Type *DestPTy =
       IntegerType::get(LoadTy->getContext(), NewLoadSize*8);
     DestPTy = PointerType::get(DestPTy,
                                PtrVal->getType()->getPointerAddressSpace());
     Builder.SetCurrentDebugLocation(SrcVal->getDebugLoc());
     PtrVal = Builder.CreateBitCast(PtrVal, DestPTy);
+    gvn.addNewInstruction(PtrVal);
     LoadInst *NewLoad = Builder.CreateLoad(PtrVal);
     NewLoad->takeName(SrcVal);
     NewLoad->setAlignment(SrcVal->getAlignment());
 
     DEBUG(dbgs() << "GVN WIDENED LOAD: " << *SrcVal << "\n");
     DEBUG(dbgs() << "TO: " << *NewLoad << "\n");
 
     // Replace uses of the original load with the wider load.  On a big endian
     // system, we need to shift down to get the relevant bits.
     Value *RV = NewLoad;
-    if (DL.isBigEndian())
+    if (DL.isBigEndian()) {
       RV = Builder.CreateLShr(RV,
                     NewLoadSize*8-SrcVal->getType()->getPrimitiveSizeInBits());
+      gvn.addNewInstruction(RV);
+    }
     RV = Builder.CreateTrunc(RV, SrcVal->getType());
+    gvn.addNewInstruction(RV);
     SrcVal->replaceAllUsesWith(RV);
 
     // We would like to use gvn.markInstructionForDeletion here, but we can't
     // because the load is already memoized into the leader map table that GVN
     // tracks.  It is potentially possible to remove the load from the table,
     // but then there all of the operations based on it would need to be
     // rehashed.  Just leave the dead load around.
     gvn.getMemDep().removeInstruction(SrcVal);
     SrcVal = NewLoad;
   }
 
-  return GetStoreValueForLoad(SrcVal, Offset, LoadTy, InsertPt, DL);
+  return GetStoreValueForLoad(SrcVal, Offset, LoadTy, InsertPt, DL, gvn);
 }
 
 
 /// This function is called when we have a
 /// memdep query of a load that ends up being a clobbering mem intrinsic.
 static Value *GetMemInstValueForLoad(MemIntrinsic *SrcInst, unsigned Offset,
                                      Type *LoadTy, Instruction *InsertPt,
-                                     const DataLayout &DL){
+                                     const DataLayout &DL, GVN &gvn){
   LLVMContext &Ctx = LoadTy->getContext();
   uint64_t LoadSize = DL.getTypeSizeInBits(LoadTy)/8;
 
   IRBuilder<> Builder(InsertPt);
 
   // We know that this method is only called when the mem transfer fully
   // provides the bits for the load.
   if (MemSetInst *MSI = dyn_cast<MemSetInst>(SrcInst)) {
     // memset(P, 'x', 1234) -> splat('x'), even if x is a variable, and
     // independently of what the offset is.
     Value *Val = MSI->getValue();
-    if (LoadSize != 1)
+    if (LoadSize != 1) {
       Val = Builder.CreateZExt(Val, IntegerType::get(Ctx, LoadSize*8));
+      gvn.addNewInstruction(Val);
+    }
 
     Value *OneElt = Val;
 
     // Splat the value out to the right number of bits.
     for (unsigned NumBytesSet = 1; NumBytesSet != LoadSize; ) {
       // If we can double the number of bytes set, do it.
       if (NumBytesSet*2 <= LoadSize) {
         Value *ShVal = Builder.CreateShl(Val, NumBytesSet*8);
+        gvn.addNewInstruction(ShVal);
         Val = Builder.CreateOr(Val, ShVal);
+        gvn.addNewInstruction(Val);
         NumBytesSet <<= 1;
         continue;
       }
 
       // Otherwise insert one byte at a time.
       Value *ShVal = Builder.CreateShl(Val, 1*8);
+      gvn.addNewInstruction(ShVal);
       Val = Builder.CreateOr(OneElt, ShVal);
+      gvn.addNewInstruction(Val);
       ++NumBytesSet;
     }
 
     return CoerceAvailableValueToLoadType(Val, LoadTy, Builder, DL);
   }
 
   // Otherwise, this is a memcpy/memmove from a constant global.
   MemTransferInst *MTI = cast<MemTransferInst>(SrcInst);

 Value *AvailableValueInBlock::MaterializeAdjustedValue(LoadInst *LI,
                                                        GVN &gvn) const {
   Value *Res;
   Type *LoadTy = LI->getType();
   const DataLayout &DL = LI->getModule()->getDataLayout();
   if (isSimpleValue()) {
     Res = getSimpleValue();
     if (Res->getType() != LoadTy) {
-      Res = GetStoreValueForLoad(Res, Offset, LoadTy, BB->getTerminator(), DL);
+      Res = GetStoreValueForLoad(Res, Offset, LoadTy, BB->getTerminator(), DL, gvn);
 
       DEBUG(dbgs() << "GVN COERCED NONLOCAL VAL:\nOffset: " << Offset << "  "
                    << *getSimpleValue() << '\n'
                    << *Res << '\n' << "\n\n\n");
     }
   } else if (isCoercedLoadValue()) {
     LoadInst *Load = getCoercedLoadValue();
     if (Load->getType() == LoadTy && Offset == 0) {
       Res = Load;
     } else {
       Res = GetLoadValueForLoad(Load, Offset, LoadTy, BB->getTerminator(),
                                 gvn);
   
       DEBUG(dbgs() << "GVN COERCED NONLOCAL LOAD:\nOffset: " << Offset << "  "
                    << *getCoercedLoadValue() << '\n'
                    << *Res << '\n' << "\n\n\n");
     }
   } else if (isMemIntrinValue()) {
     Res = GetMemInstValueForLoad(getMemIntrinValue(), Offset, LoadTy,
-                                 BB->getTerminator(), DL);
+                                 BB->getTerminator(), DL, gvn);
     DEBUG(dbgs() << "GVN COERCED NONLOCAL MEM INTRIN:\nOffset: " << Offset
                  << "  " << *getMemIntrinValue() << '\n'
                  << *Res << '\n' << "\n\n\n");
   } else {
     assert(isUndefValue() && "Should be UndefVal");
     DEBUG(dbgs() << "GVN COERCED NONLOCAL Undef:\n";);
     return UndefValue::get(LoadTy);
   }
if (Dep.isClobber()) {
     // completely covers this load.  This sort of thing can happen in bitfield
     // access code.
     Value *AvailVal = nullptr;
     if (StoreInst *DepSI = dyn_cast<StoreInst>(Dep.getInst())) {
       int Offset = AnalyzeLoadFromClobberingStore(
           L->getType(), L->getPointerOperand(), DepSI);
       if (Offset != -1)
         AvailVal = GetStoreValueForLoad(DepSI->getValueOperand(), Offset,
-                                        L->getType(), L, DL);
+                                        L->getType(), L, DL, *this);
     }
 
     // Check to see if we have something like this:
     //    load i32* P
     //    load i8* (P+1)
     // if we have this, replace the later with an extraction from the former.
     if (LoadInst *DepLI = dyn_cast<LoadInst>(Dep.getInst())) {
       // If this is a clobber and L is the first instruction in its block, then
       // we have the first instruction in the entry block.
       if (DepLI == L)
         return false;
 
       int Offset = AnalyzeLoadFromClobberingLoad(
           L->getType(), L->getPointerOperand(), DepLI, DL);
       if (Offset != -1)
         AvailVal = GetLoadValueForLoad(DepLI, Offset, L->getType(), L, *this);
     }
 
     // If the clobbering value is a memset/memcpy/memmove, see if we can forward
     // a value on from it.
     if (MemIntrinsic *DepMI = dyn_cast<MemIntrinsic>(Dep.getInst())) {
       int Offset = AnalyzeLoadFromClobberingMemInst(
           L->getType(), L->getPointerOperand(), DepMI, DL);
       if (Offset != -1)
-        AvailVal = GetMemInstValueForLoad(DepMI, Offset, L->getType(), L, DL);
+        AvailVal = GetMemInstValueForLoad(DepMI, Offset, L->getType(), L, DL, *this);
     }
 
     if (AvailVal) {
       DEBUG(dbgs() << "GVN COERCED INST:\n" << *Dep.getInst() << '\n'
             << *AvailVal << '\n' << *L << "\n\n\n");
 
       // Replace the load!
       L->replaceAllUsesWith(AvailVal);

test/Transforms/GVN/pr25440.ll

+;RUN: opt -gvn -S < %s | FileCheck %s
+
+target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-a:0:32-n8:16:32-S64"
+target triple = "thumbv7--linux-gnueabi"
+
+%struct.a = type { i16, i16, [1 x %union.a] }
+%union.a = type { i32 }
+
+@length = external global [0 x i32], align 4
+
+; Function Attrs: nounwind
+define fastcc void @foo(%struct.a* nocapture readonly %x) {
+;CHECK-LABEL: foo
+entry:
+  br label %bb0
+
+bb0:                                      ; preds = %land.lhs.true, %entry
+;CHECK: bb0:
+  %x.tr = phi %struct.a* [ %x, %entry ], [ null, %land.lhs.true ]
+  %code1 = getelementptr inbounds %struct.a, %struct.a* %x.tr, i32 0, i32 0
+  %0 = load i16, i16* %code1, align 4
+; CHECK: load i32, i32*
+  %conv = zext i16 %0 to i32
+  switch i32 %conv, label %if.end.50 [
+    i32 43, label %cleanup
+    i32 52, label %if.then.5
+  ]
+
+if.then.5:                                        ; preds = %bb0
+  br i1 undef, label %land.lhs.true, label %if.then.26
+
+land.lhs.true:                                    ; preds = %if.then.5
+  br i1 undef, label %cleanup, label %bb0
+
+if.then.26:                                       ; preds = %if.then.5
+  %x.tr.lcssa163 = phi %struct.a* [ %x.tr, %if.then.5 ]
+  br i1 undef, label %cond.end, label %cond.false
+
+cond.false:                                       ; preds = %if.then.26
+; CHECK: cond.false:
+; CHECK-NOT: load
+  %mode = getelementptr inbounds %struct.a, %struct.a* %x.tr.lcssa163, i32 0, i32 1
+  %bf.load = load i16, i16* %mode, align 2
+  %bf.shl = shl i16 %bf.load, 8
+  br label %cond.end
+
+cond.end:                                         ; preds = %cond.false, %if.then.26
+  br i1 undef, label %if.then.44, label %cleanup
+
+if.then.44:                                       ; preds = %cond.end
+  unreachable
+
+if.end.50:                                        ; preds = %bb0
+;%CHECK: if.end.50:
+  %conv.lcssa = phi i32 [ %conv, %bb0 ]
+  %arrayidx52 = getelementptr inbounds [0 x i32], [0 x i32]* @length, i32 0, i32 %conv.lcssa
+  %1 = load i32, i32* %arrayidx52, align 4
+  br i1 undef, label %for.body.57, label %cleanup
+
+for.body.57:                                      ; preds = %if.end.50
+  %i.2157 = add nsw i32 %1, -1
+  unreachable
+
+cleanup:                                          ; preds = %if.end.50, %cond.end, %land.lhs.true, %bb0
+  ret void
+}