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

Does this pattern exist somewhere else in llvm?

[dmikulin]

llvm/lib/IR/Value.cpp

469

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

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

458

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

458

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

12

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

17

You can probably remove the argument list and return void.

21

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/lib/IR/Value.cpp

for (; UI != E;) {
     auto *Usr = dyn_cast<Instruction>(U.getUser());
     if (Usr && Usr->getParent() == BB)
       continue;
     U.set(New);
   }
 }
 
 void Value::replaceUsesExceptBlockAddr(Value *New) {
-  use_iterator UI = use_begin(), E = use_end();
-  for (; UI != E;) {
-    Use &U = *UI;
-    ++UI;
+  SmallVector<std::pair<Use*, Value*>, 8> BA;
+  while (!use_empty()) {
+    Use &U = *UseList;
 
-    if (isa<BlockAddress>(U.getUser()))
+    // Don't process blockaddress uses. Remove them from UseList
+    // temporarily and place onto a separate list. We can't use
+    // UseList iterator here as the list is changing inside the loop.
+    // That's why we need to remove skiped uses from the list.
+    if (isa<BlockAddress>(U.getUser())) {
+      Value *V = U.get();
+      BA.push_back(std::make_pair(&U, V));
+      U.set(nullptr);
       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);
         continue;
       }
     }
 
     U.set(New);
   }
+
+  // Go over the saved block address uses and add them back to UseList.
+  while (!BA.empty()) {
+    std::pair<Use*, Value*> P = BA.pop_back_val();
+    Use *U = P.first;
+    Value *V = P.second;
+    U->set(V);
+  }
 }
 
 namespace {
 // Various metrics for how much to strip off of pointers.
 enum PointerStripKind {
   PSK_ZeroIndices,
   PSK_ZeroIndicesAndAliases,
   PSK_ZeroIndicesAndAliasesAndBarriers,

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

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