[llvm-diff] Explicitly check ConstantStructs for differences

[void]

Summary

A ConstantStruct is renamed when the LLVM context sees a new one. This
makes global variable initializers appear different when they aren't.
Instead, check the ConstantStruct for equivalence.

[rjmccall]

llvm/tools/llvm-diff/DifferenceEngine.cpp

477

Hmm. I don't think it's okay to just compare the number of elements: if the types might be different, they might have different layouts.

[void]

llvm/tools/llvm-diff/DifferenceEngine.cpp

477

The individual elements are checked in the loop below. I made it recursive because I couldn't count on the types to be uniqued, because of the naming differences.

[rjmccall]

llvm/tools/llvm-diff/DifferenceEngine.cpp

477

Sure, I see that, but you could have different struct types with different layouts but compatible elements. Because one is packed and the other isn't, or so on.

[void]

Check for packed structures to ensure they have the same data layout.

[void]

llvm/tools/llvm-diff/DifferenceEngine.cpp

477

Ah! I see what you mean. There's a method called isLayoutIdentical, but it checks each element's pointer value. The only other thing it checks is the Packed attribute. I added that.

[rjmccall]

That should work, thanks. What's going on with StructStack?

[void]

In D104734#2834999, @rjmccall wrote:

That should work, thanks. What's going on with StructStack?

Structures are the only types which can reference themselves. If I don't stop processing already seen types then it's possible they could infinitely recurse. The stack / std::find code is very hackish. I'm open to suggestions on making it non-gross. :-)

[rjmccall]

In D104734#2835045, @void wrote:

In D104734#2834999, @rjmccall wrote:

That should work, thanks. What's going on with StructStack?

Structures are the only types which can reference themselves. If I don't stop processing already seen types then it's possible they could infinitely recurse. The stack / std::find code is very hackish. I'm open to suggestions on making it non-gross. :-)

Well, they can't reference themselves as sub-aggregates; you'll never see another field of this exact type.

[void]

Check to ensure we don't analyze the global variable we're currently analyzing. This causes an infinite loop.

[void]

In D104734#2836575, @rjmccall wrote:

In D104734#2835045, @void wrote:

In D104734#2834999, @rjmccall wrote:

That should work, thanks. What's going on with StructStack?

Structures are the only types which can reference themselves. If I don't stop processing already seen types then it's possible they could infinitely recurse. The stack / std::find code is very hackish. I'm open to suggestions on making it non-gross. :-)

Well, they can't reference themselves as sub-aggregates; you'll never see another field of this exact type.

Doh! Of course. I found the actual problem. A global variable may occur in its own initializer as part of a GEP or bitcast. I added a more sane check. PTAL

[rjmccall]

Oh, yeah, if we recurse into initializers in equivalentAsOperands then we'll have that problem for sure. I don't think you can just check at the top level of a struct initializer, though — you need to be able to do this check in recursive positions, like if the element initializer is a bitcast. I would suggest doing the check specifically in the case where you've found global variables.

Also, you should record both GVL and GVR in the difference engine you construct, and then do something like if (GVL == SavedGVL) return GVR == SavedGVR;. If you see a self-reference in the LHS but the RHS is like a null pointer or some other global, that's a difference, not something we should skip! This will make it a sort of maximal fixed point.

I would suggest just setting SavedGVL and SavedGVR on the temporary difference engine instead of passing them in to all uses of equivalentOnOperands.

[void]

Improve the check of the global variable initializers. Both LHS and RHS need to
match the global variable at the same time when recursing or they don't match.

[rjmccall]

llvm/tools/llvm-diff/DifferenceEngine.cpp

572

The other constructors doesn't initialize these. Might be best to just = nullptr them and then override them, either here or separately after construction.

[void]

Initialize Saved[LR]HS to nullptr.

[rjmccall]

Thanks for bearing with all the comments. :) LGTM.

[void]

In D104734#2837430, @rjmccall wrote:

Thanks for bearing with all the comments. :) LGTM.

Not at all! Thanks for the review. :-) You made it better than it was.

llvm/test/tools/llvm-diff/initializers.ll

 ; RUN: llvm-diff %s %s
 
 ; An initializer that has a GEP instruction in it won't match itself in
 ; llvm-diff unless the a deep comparison is done on the initializer.
 
 @gv1 = external dso_local global [28 x i16], align 16
 @gv2 = private unnamed_addr constant [2 x i16*] [i16* getelementptr inbounds ([28 x i16], [28 x i16]* @gv1, i32 0, i32 0), i16* poison], align 16
 
 define void @foo() {
   %1 = getelementptr [2 x i16*], [2 x i16*]* @gv2, i64 0, i64 undef
   ret void
 }
+
+; A named structure may be renamed when the right module is read. This is due
+; to the LLParser being different between the left and right modules, and the
+; context renaming one.
+
+%struct.ty1 = type { i16, i16 }
+
+@gv3 = internal global [1 x %struct.ty1] [%struct.ty1 { i16 928, i16 0 }], align 16
+
+define void @bar() {
+  %1 = getelementptr [1 x %struct.ty1], [1 x %struct.ty1]* @gv3, i64 0, i64 undef
+  ret void
+}

llvm/tools/llvm-diff/DifferenceEngine.cpp

for (unsigned I = 0, E = L->getNumOperands(); I != E; ++I) {
         if (Complain) Engine.logf("operands %l and %r differ") << LO << RO;
         return true;
       }
     }
 
     return false;
   }
 
+private:
+  std::vector<StringRef> StructStack;
+
 public:
   bool equivalentAsOperands(const Constant *L, const Constant *R) {
     // Use equality as a preliminary filter.
     if (L == R)
       return true;
 
     if (L->getValueID() != R->getValueID())
       return false;
if (isa<ConstantArray>(L)) {
         if (!equivalentAsOperands(CAL->getAggregateElement(I),
                                   CAR->getAggregateElement(I)))
           return false;
       }
 
       return true;
     }
 
+    // If L and R are ConstantStructs, compare each field and type.
+    if (isa<ConstantStruct>(L)) {
+      const ConstantStruct *CSL = cast<ConstantStruct>(L);
+      const ConstantStruct *CSR = cast<ConstantStruct>(R);
+
+      const StructType *LTy = cast<StructType>(CSL->getType());
+      const StructType *RTy = cast<StructType>(CSR->getType());
+
+      // The StructTypes should have the same attributes. Don't use
+      // isLayoutIdentical(), because that just checks the element pointers,
+      // which may not work here.
+      if (LTy->getNumElements() != RTy->getNumElements() ||
+          LTy->isPacked() != RTy->isPacked())
+        return false;
+
+      StructStack.push_back(CSL->getName());
+
+      for (unsigned I = 0; I < LTy->getNumElements(); I++) {
+        const Value *LAgg = CSL->getAggregateElement(I);
+        const Value *RAgg = CSR->getAggregateElement(I);
+
+        if (std::find(StructStack.begin(), StructStack.end(),
+                      LAgg->getName()) != StructStack.end())
+          continue;
+
+        if (!equivalentAsOperands(LAgg, RAgg)) {
+          StructStack.pop_back();
+          return false;
+        }
+      }
+
+      StructStack.pop_back();
+      return true;
+    }
+
     return false;
   }
 
   bool equivalentAsOperands(const ConstantExpr *L, const ConstantExpr *R) {
     if (L == R)
       return true;
     if (L->getOpcode() != R->getOpcode())
       return false;
public:
 
   // Avoid a gcc warning about accessing 'this' in an initializer.
   FunctionDifferenceEngine *this_() { return this; }
 
 public:
   FunctionDifferenceEngine(DifferenceEngine &Engine) :
     Engine(Engine), Queue(QueueSorter(*this_())) {}
 
   void diff(const Function *L, const Function *R) {
     if (L->arg_size() != R->arg_size())
       Engine.log("different argument counts");
 
     // Map the arguments.
     for (Function::const_arg_iterator LI = L->arg_begin(), LE = L->arg_end(),
                                       RI = R->arg_begin(), RE = R->arg_end();
          LI != LE && RI != RE; ++LI, ++RI)
       Values[&*LI] = &*RI;