Fix for CFI type tests lowering assert.

[dmikulin]

Summary

My attempt to fix https://bugs.llvm.org/show_bug.cgi?id=35252.

The problem is that current implementation of Value::replaceUsesExceptBlockAddr() uses UseList iterator to walk the list which keeps changing inside the loop. doRAUW() gets around it by checking if the list is empty to terminate. When we skip blockaddress uses, the list is never empty if there are any blockaddress uses. This change removes blockaddress uses from the UseList, places them in a temporary list and adds them back after all uses are processed.

I don't particularly like this fix, but couldn't find a better way. I have another version where the loop terminating condition checks if the only remaining uses are blockaddresses and skips leading blockaddresses on loop entry, but it requires repeated scans of UseList, so I liked it even less. If anyone has suggestions I'll be happy to explore.

[filcab]

Seems ok assuming that construct is safe.

llvm/lib/IR/Value.cpp

469 ↗

(On Diff #122309)

Does this pattern exist somewhere else in llvm?

[dmikulin]

llvm/lib/IR/Value.cpp

469 ↗

(On Diff #122309)

You mean U.set(nullptr);? It's used in a few places as a way to remove a value from UseList without replacing it with anything else. There's no direct access to UseList add/remove methods. As as side effect of set(nullptr), the value ptr gets nuked, so I need to save it to restore later.

[dmikulin]

Nag... Can you guys please review this?

[pcc]

llvm/lib/IR/Value.cpp

477 ↗

(On Diff #122309)

I think the only way that you can end up replacing multiple users during an iteration of this loop is if this function gets called. So could you instead collect a set of constants that you need to call handleOperandChange on and take care of them separately after the loop?

[dmikulin]

Changed the fix to save unique Constant users and process them separately outside of the UseList iterator.

[davide]

llvm/lib/IR/Value.cpp

459 ↗

(On Diff #123234)

SmallSetVector to make sure this is deterministic, maybe?

[davide]

(unless you don't care about the order at all, in which case you might consider adding a comment).

[dmikulin]

llvm/lib/IR/Value.cpp

459 ↗

(On Diff #123234)

Not sure about the order, so changed it to SmallSetVector.

[pcc]

Assuming that you've made the obvious change to the set type locally, this LGTM.

llvm/test/Transforms/LowerTypeTests/blockaddress-2.ll

11 ↗

(On Diff #123234)

If this line isn't necessary to reproduce the bug, please remove it.

16 ↗

(On Diff #123234)

You can probably remove the argument list and return void.

20 ↗

(On Diff #123234)

Same here.

[davide]

LGTM with Peter comment's addressed (and please don't forget to switch this to a SmallSetVector ;)

[dmikulin]

And the set type is changed to SmallSetVector.

llvm/trunk/lib/IR/Value.cpp

 // This file implements the Value, ValueHandle, and User classes.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/IR/Value.h"
 #include "LLVMContextImpl.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/SmallString.h"
+#include "llvm/ADT/SetVector.h"
 #include "llvm/IR/CallSite.h"
 #include "llvm/IR/Constant.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/DerivedTypes.h"
 #include "llvm/IR/DerivedUser.h"
 #include "llvm/IR/GetElementPtrTypeIterator.h"
 #include "llvm/IR/InstrTypes.h"
for (; UI != E;) {
     auto *Usr = dyn_cast<Instruction>(U.getUser());
     if (Usr && Usr->getParent() == BB)
       continue;
     U.set(New);
   }
 }
 
 void Value::replaceUsesExceptBlockAddr(Value *New) {
+  SmallSetVector<Constant *, 4> Constants;
   use_iterator UI = use_begin(), E = use_end();
   for (; UI != E;) {
     Use &U = *UI;
     ++UI;
 
     if (isa<BlockAddress>(U.getUser()))
       continue;
 
     // Must handle Constants specially, we cannot call replaceUsesOfWith on a
     // constant because they are uniqued.
     if (auto *C = dyn_cast<Constant>(U.getUser())) {
       if (!isa<GlobalValue>(C)) {
-        C->handleOperandChange(this, New);
+        // Save unique users to avoid processing operand replacement
+        // more than once.
+        Constants.insert(C);
         continue;
       }
     }
 
     U.set(New);
   }
+
+  // Process operand replacement of saved constants.
+  for (auto *C : Constants)
+    C->handleOperandChange(this, New);
 }
 
 namespace {
 // Various metrics for how much to strip off of pointers.
 enum PointerStripKind {
   PSK_ZeroIndices,
   PSK_ZeroIndicesAndAliases,
   PSK_ZeroIndicesAndAliasesAndBarriers,

llvm/trunk/test/Transforms/LowerTypeTests/blockaddress-2.ll

+; RUN: opt -S %s -lowertypetests | FileCheck %s
+
+; CHECK: @badfileops = internal global %struct.f { void ()* @bad_f, void ()* @bad_f }
+; CHECK: @bad_f = internal alias void (), void ()* @.cfi.jumptable
+; CHECK: define internal void @bad_f.cfi() !type !0 {
+; CHECK-NEXT:  ret void
+
+target triple = "x86_64-unknown-linux"
+
+%struct.f = type { void ()*, void ()* }
+@badfileops = internal global %struct.f { void ()* @bad_f, void ()* @bad_f }, align 8
+
+declare i1 @llvm.type.test(i8*, metadata)
+
+define internal void @bad_f() !type !1 {
+  ret void
+}
+
+define internal fastcc void @do_f() unnamed_addr !type !2 {
+  %1 = tail call i1 @llvm.type.test(i8* undef, metadata !"_ZTSFiP4fileP3uioP5ucrediP6threadE"), !nosanitize !3
+  ret void
+}
+
+!1 = !{i64 0, !"_ZTSFiP4fileP3uioP5ucrediP6threadE"}
+!2 = !{i64 0, !"_ZTSFiP6threadiP4fileP3uioliE"}
+!3 = !{}