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)

1209

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:
     DominatorTree &getDominatorTree() const { return *DT; }
     AliasAnalysis *getAliasAnalysis() const { return VN.getAliasAnalysis(); }
     MemoryDependenceAnalysis &getMemDep() const { return *MD; }
   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;
       }
 
       LeaderTableEntry *Node = TableAllocator.Allocate<LeaderTableEntry>();
       Node->Val = V;
       Node->BB = BB;
       Node->Next = Curr.Next;
if (Offset+LoadSize > SrcValSize) {
 
     // 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())
       RV = Builder.CreateLShr(RV,
                     NewLoadSize*8-SrcVal->getType()->getPrimitiveSizeInBits());
     RV = Builder.CreateTrunc(RV, SrcVal->getType());
     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;
bool GVN::performScalarPREInsertion(Instruction *Instr, BasicBlock *Pred,
   // that weren't originally present will have been instantiated earlier
   // in this loop.
   bool success = true;
   for (unsigned i = 0, e = Instr->getNumOperands(); i != e; ++i) {
     Value *Op = Instr->getOperand(i);
     if (isa<Argument>(Op) || isa<Constant>(Op) || isa<GlobalValue>(Op))
       continue;
 
-    if (Value *V = findLeader(Pred, VN.lookup(Op))) {
+    if (Value *V = findLeader(Pred, VN.lookup_or_add(Op))) {
       Instr->setOperand(i, V);
     } else {
       success = false;
       break;
     }
   }
 
   // Fail out if we encounter an operand that is not available in