[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

480

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

480

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

480

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

480

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

581

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
+}
+
+; An initializer may reference the variable it's initializing via bitcast /
+; GEP. Check that it doesn't cause an infinite loop.
+
+%struct.mutex = type { %struct.list_head }
+%struct.list_head = type { %struct.list_head*, %struct.list_head* }
+
+@vmx_l1d_flush_mutex = internal global %struct.mutex { %struct.list_head { %struct.list_head* bitcast (i8* getelementptr (i8, i8* bitcast (%struct.mutex* @vmx_l1d_flush_mutex to i8*), i64 16) to %struct.list_head*), %struct.list_head* bitcast (i8* getelementptr (i8, i8* bitcast (%struct.mutex* @vmx_l1d_flush_mutex to i8*), i64 16) to %struct.list_head*) } }, align 8
+
+define internal i32 @qux() {
+  call void undef(%struct.mutex* @vmx_l1d_flush_mutex)
+  ret i32 undef
+}

llvm/tools/llvm-diff/DifferenceEngine.cpp

T remove_min() {
     return tmp;
   }
 };
 
 /// A function-scope difference engine.
 class FunctionDifferenceEngine {
   DifferenceEngine &Engine;
 
+  // Some initializers may reference the variable we're currently checking. This
+  // can cause an infinite loop. The Saved[LR]HS ivars can be checked to prevent
+  // recursing.
+  const Value *SavedLHS;
+  const Value *SavedRHS;
+
   /// The current mapping from old local values to new local values.
   DenseMap<const Value *, const Value *> Values;
 
   /// The current mapping from old blocks to new blocks.
   DenseMap<const BasicBlock *, const BasicBlock *> Blocks;
 
   DenseSet<std::pair<const Value *, const Value *>> TentativeValues;
 

 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;
-    
     // Ask the engine about global values.
     if (isa<GlobalValue>(L))
       return Engine.equivalentAsOperands(cast<GlobalValue>(L),
                                          cast<GlobalValue>(R));
 
     // Compare constant expressions structurally.
     if (isa<ConstantExpr>(L))
       return equivalentAsOperands(cast<ConstantExpr>(L),
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;
+
+      for (unsigned I = 0; I < LTy->getNumElements(); I++) {
+        const Value *LAgg = CSL->getAggregateElement(I);
+        const Value *RAgg = CSR->getAggregateElement(I);
+
+        if (!equivalentAsOperands(LAgg, RAgg)) {
+          return false;
+        }
+      }
+
+      return true;
+    }
+
     return false;
   }
 
   bool equivalentAsOperands(const ConstantExpr *L, const ConstantExpr *R) {
     if (L == R)
       return true;
+
     if (L->getOpcode() != R->getOpcode())
       return false;
 
     switch (L->getOpcode()) {
     case Instruction::ICmp:
     case Instruction::FCmp:
       if (L->getPredicate() != R->getPredicate())
         return false;
       break;
 
     case Instruction::GetElementPtr:
       // FIXME: inbounds?
       break;
 
     default:
       break;
     }
 
     if (L->getNumOperands() != R->getNumOperands())
       return false;
 
-    for (unsigned I = 0, E = L->getNumOperands(); I != E; ++I)
-      if (!equivalentAsOperands(L->getOperand(I), R->getOperand(I)))
+    for (unsigned I = 0, E = L->getNumOperands(); I != E; ++I) {
+      const auto *LOp = L->getOperand(I);
+      const auto *ROp = R->getOperand(I);
+
+      if (LOp == SavedLHS || ROp == SavedRHS) {
+        if (LOp != SavedLHS || ROp != SavedRHS)
+          // If the left and right operands aren't both re-analyzing the
+          // variable, then the initialiers don't match, so report "false".
+          // Otherwise, we skip these operands..
           return false;
 
+        continue;
+      }
+
+      if (!equivalentAsOperands(LOp, ROp))
+        return false;
+    }
+
     return true;
   }
 
   bool equivalentAsOperands(const Value *L, const Value *R) {
     // Fall out if the values have different kind.
     // This possibly shouldn't take priority over oracles.
     if (L->getValueID() != R->getValueID())
       return false;
bool equivalentAsOperands(const Value *L, const Value *R) {
     // Pretend everything else is identical.
     return true;
   }
 
   // Avoid a gcc warning about accessing 'this' in an initializer.
   FunctionDifferenceEngine *this_() { return this; }
 
 public:
-  FunctionDifferenceEngine(DifferenceEngine &Engine) :
-    Engine(Engine), Queue(QueueSorter(*this_())) {}
+  FunctionDifferenceEngine(DifferenceEngine &Engine,
+                           const Value *SavedLHS = nullptr,
+                           const Value *SavedRHS = nullptr)
+      : Engine(Engine), SavedLHS(SavedLHS), SavedRHS(SavedRHS),
+        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();
bool DifferenceEngine::equivalentAsOperands(const GlobalValue *L,
                                             const GlobalValue *R) {
   if (globalValueOracle) return (*globalValueOracle)(L, R);
 
   if (isa<GlobalVariable>(L) && isa<GlobalVariable>(R)) {
     const GlobalVariable *GVL = cast<GlobalVariable>(L);
     const GlobalVariable *GVR = cast<GlobalVariable>(R);
     if (GVL->hasLocalLinkage() && GVL->hasUniqueInitializer() &&
         GVR->hasLocalLinkage() && GVR->hasUniqueInitializer())
-      return FunctionDifferenceEngine(*this).equivalentAsOperands(
-          GVL->getInitializer(), GVR->getInitializer());
+      return FunctionDifferenceEngine(*this, GVL, GVR)
+          .equivalentAsOperands(GVL->getInitializer(), GVR->getInitializer());
   }
 
   return L->getName() == R->getName();
 }