Fix mergefunc infinite loop

[• jrkoenig]

Summary

Self-referential constants containing references to a merged function
no longer cause the MergeFunctions pass to infinite loop. Also adds a
reproduction IR which would otherwise fail, which was isolated from a similar
issue in Chromium.

[nlewycky]

lib/Transforms/IPO/MergeFunctions.cpp

1517–1520 ↗

(On Diff #29738)

Just FYI as an optional alternative. You could use a single SetVector for both, call insert() to insert into it, track your position with an increasing integer, and never remove from it.

The way you've written it here is more common in llvm, I think.

1520 ↗

(On Diff #29738)

"Variable names should be nouns (as they represent state). The name should be camel case, and start with an upper case letter (e.g. Leader or Boats)." - http://llvm.org/docs/CodingStandards.html#name-types-functions-variables-and-enumerators-properly

[• jrkoenig]

Fix variable name case

[jfb]

lgtm, assuming @nlewycky is OK with the fix not using SetVector.

[nlewycky]

No need to use SetVector.

llvm/trunk/lib/Transforms/IPO/MergeFunctions.cpp

void MergeFunctions::remove(Function *F) {
   }
 }
 
 // For each instruction used by the value, remove() the function that contains
 // the instruction. This should happen right before a call to RAUW.
 void MergeFunctions::removeUsers(Value *V) {
   std::vector<Value *> Worklist;
   Worklist.push_back(V);
+  SmallSet<Value*, 8> Visited;
+  Visited.insert(V);
   while (!Worklist.empty()) {
     Value *V = Worklist.back();
     Worklist.pop_back();
 
     for (User *U : V->users()) {
       if (Instruction *I = dyn_cast<Instruction>(U)) {
         remove(I->getParent()->getParent());
       } else if (isa<GlobalValue>(U)) {
         // do nothing
       } else if (Constant *C = dyn_cast<Constant>(U)) {
-        for (User *UU : C->users())
+        for (User *UU : C->users()) {
+          if (!Visited.insert(UU).second)
             Worklist.push_back(UU);
         }
       }
     }
   }
+}

llvm/trunk/test/Transforms/MergeFunc/self-referential-global.ll

+; RUN: opt -mergefunc -disable-output < %s
+
+; A linked list type and simple payload
+%LL = type { %S, %LL* }
+%S = type { void (%S*, i32)* }
+
+; Table refers to itself via GEP
+@Table = internal global [3 x %LL] [%LL { %S { void (%S*, i32)* @B }, %LL* getelementptr inbounds ([3 x %LL], [3 x %LL]* @Table, i32 0, i32 0) }, %LL { %S { void (%S*, i32)* @A }, %LL* getelementptr inbounds ([3 x %LL], [3 x %LL]* @Table, i32 0, i32 0) }, %LL { %S { void (%S*, i32)* @A }, %LL* getelementptr inbounds ([3 x %LL], [3 x %LL]* @Table, i32 0, i32 0) }], align 16
+
+; The body of this is irrelevant; it is long so that mergefunc doesn't skip it as a small function.
+define internal void @A(%S* %self, i32 %a) {
+  %1 = add i32 %a, 32
+  %2 = add i32 %1, 32
+  %3 = add i32 %2, 32
+  %4 = add i32 %3, 32
+  %5 = add i32 %4, 32
+  %6 = add i32 %5, 32
+  %7 = add i32 %6, 32
+  %8 = add i32 %7, 32
+  %9 = add i32 %8, 32
+  %10 = add i32 %9, 32
+  %11 = add i32 %10, 32
+  ret void
+}
+
+define internal void @B(%S* %self, i32 %a) {
+  %1 = add i32 %a, 32
+  %2 = add i32 %1, 32
+  %3 = add i32 %2, 32
+  %4 = add i32 %3, 32
+  %5 = add i32 %4, 32
+  %6 = add i32 %5, 32
+  %7 = add i32 %6, 32
+  %8 = add i32 %7, 32
+  %9 = add i32 %8, 32
+  %10 = add i32 %9, 32
+  %11 = add i32 %10, 32
+  ret void
+}
+