[GVN] Properly invalidate ICF cache when we simplify a value

[aeubanks]

Summary

This fixes a "Cached first special instruction is wrong!" assert.

The assert fires because replacing a value with another can cause an
instruction to no longer be "special" to ICF. In this case,
devirtualization happened, turning an indirect call to a
call to a willreturn function which is no longer special.

[aeubanks]

actually make the test do something

[lebedev.ri]

Does this cause ICF to be recomputed afterwards?
Can it be updated instead?

[nikic]

llvm/lib/Transforms/Scalar/GVN.cpp

2177

It would be better to extend the IPT interface to allow more fine grained invalidation here. At least to only invalidate the blocks where the user is the current special instruction.

[aeubanks]

selectively invalidate

[nikic]

LGTM

[rnk]

llvm/lib/Transforms/Scalar/GVN.cpp

2177

That seems reasonable, so something like: IPT::clearUsersOf(Instruction*I)? The intention is that this should be called before any RAUW operation, it will iterate the users, and if any of them are the cached special instruction, those blocks will be invalidated.

llvm/test/Transforms/GVN/simplify-icf-cache-invalidation.ll

36

Please make this test case a bit more human readable. I'm guessing what happens here is that GVN somehow forwards the earlier invariant.group store to the invariant.group load, and simplifying the load instruction has the side effect of making the following indirect call "willreturn". There should be a way to test that without loads from null pointers and branches on undef, which make the test fragile to future GVN changes.

[aeubanks]

simplify test more
move cache invalidation into ICF method

[rnk]

lgtm

llvm/include/llvm/Analysis/InstructionPrecedenceTracking.h

83

s/remove/replace/, should be "... going to replace all uses of..."

[aeubanks]

address comment

llvm/include/llvm/Analysis/InstructionPrecedenceTracking.h

public:
   /// Inst to the basic block \p BB. It makes all necessary updates to internal
   /// caches to keep them consistent.
   void insertInstructionTo(const Instruction *Inst, const BasicBlock *BB);
 
   /// Notifies this tracking that we are going to remove the instruction \p Inst
   /// It makes all necessary updates to internal caches to keep them consistent.
   void removeInstruction(const Instruction *Inst);
 
+  /// Notifies this tracking that we are going to remove all uses of \p Inst.
+  /// It makes all necessary updates to internal caches to keep them consistent.
+  /// Should typically be called before a RAUW.
+  void removeUsersOf(const Instruction *Inst);
+
   /// Invalidates all information from this tracking.
   void clear();
 };
 
 /// This class allows to keep track on instructions with implicit control flow.
 /// These are instructions that may not pass execution to their successors. For
 /// example, throwing calls and guards do not always do this. If we need to know
 /// for sure that some instruction is guaranteed to execute if the given block

llvm/lib/Analysis/InstructionPrecedenceTracking.cpp

if (isSpecialInstruction(Inst))
     FirstSpecialInsts.erase(BB);
 }
 
 void InstructionPrecedenceTracking::removeInstruction(const Instruction *Inst) {
   if (isSpecialInstruction(Inst))
     FirstSpecialInsts.erase(Inst->getParent());
 }
 
+void InstructionPrecedenceTracking::removeUsersOf(const Instruction *Inst) {
+  for (auto *U : Inst->users()) {
+    if (auto *UI = dyn_cast<Instruction>(U))
+      removeInstruction(UI);
+  }
+}
+
 void InstructionPrecedenceTracking::clear() {
   FirstSpecialInsts.clear();
 #ifndef NDEBUG
   // The map should be valid after clearing (at least empty).
   validateAll();
 #endif
 }
 

llvm/lib/Transforms/Scalar/GVN.cpp

bool GVN::processInstruction(Instruction *I) {
   // If the instruction can be easily simplified then do so now in preference
   // to value numbering it.  Value numbering often exposes redundancies, for
   // example if it determines that %y is equal to %x then the instruction
   // "%z = and i32 %x, %y" becomes "%z = and i32 %x, %x" which we now simplify.
   const DataLayout &DL = I->getModule()->getDataLayout();
   if (Value *V = SimplifyInstruction(I, {DL, TLI, DT, AC})) {
     bool Changed = false;
     if (!I->use_empty()) {
+      // Simplification can cause a special instruction to become not special.
+      // For example, devirtualization to a willreturn function.
+      ICF->removeUsersOf(I);
       I->replaceAllUsesWith(V);
       Changed = true;
     }
     if (isInstructionTriviallyDead(I, TLI)) {
       markInstructionForDeletion(I);
       Changed = true;
     }
     if (Changed) {
       if (MD && V->getType()->isPtrOrPtrVectorTy())
         MD->invalidateCachedPointerInfo(V);
       ++NumGVNSimpl;
       return true;

llvm/test/Transforms/GVN/simplify-icf-cache-invalidation.ll

+; RUN: opt -passes=gvn -S < %s | FileCheck %s
+
+; CHECK: define {{.*}}@eggs
+
+%struct.zot = type { i32 (...)** }
+%struct.wombat = type { i8* }
+%struct.baz = type { i8, i8* }
+
+@global = hidden unnamed_addr constant i8* bitcast (void (%struct.zot*, i1)* @quux to i8*)
+
+declare i8* @f()
+
+define hidden void @eggs(%struct.zot* %arg, i1 %arg2, i32* %arg3, i32 %arg4, %struct.baz** %arg5) unnamed_addr align 2 {
+bb:
+  %tmp = alloca %struct.wombat, align 8
+  %tmp1 = getelementptr %struct.zot, %struct.zot* %arg, i64 0, i32 0
+  store i32 (...)** bitcast (i8** @global to i32 (...)**), i32 (...)*** %tmp1, align 8, !invariant.group !0
+  br i1 %arg2, label %bb4, label %bb2
+
+bb2:                                              ; preds = %bb
+  %tmp3 = atomicrmw sub i32* %arg3, i32 %arg4 acq_rel, align 4
+  br label %bb4
+
+bb4:                                              ; preds = %bb2, %bb
+  %tmp5 = load %struct.baz*, %struct.baz** %arg5, align 8
+  %tmp6 = getelementptr inbounds %struct.baz, %struct.baz* %tmp5, i64 0, i32 1
+  br i1 %arg2, label %bb9, label %bb7
+
+bb7:                                              ; preds = %bb4
+  %tmp8 = tail call i8* @f()
+  br label %bb9
+
+bb9:                                              ; preds = %bb7, %bb4
+  %tmp10 = load %struct.baz*, %struct.baz** %arg5, align 8
+  %tmp11 = getelementptr inbounds %struct.baz, %struct.baz* %tmp10, i64 0, i32 0
+  %tmp12 = bitcast %struct.zot* %arg to void (%struct.zot*, i1)***
+  %tmp13 = load void (%struct.zot*, i1)**, void (%struct.zot*, i1)*** %tmp12, align 8, !invariant.group !0
+  %tmp14 = getelementptr inbounds void (%struct.zot*, i1)*, void (%struct.zot*, i1)** %tmp13, i64 0
+  %tmp15 = load void (%struct.zot*, i1)*, void (%struct.zot*, i1)** %tmp14, align 8
+  tail call void %tmp15(%struct.zot* %arg, i1 %arg2)
+  %tmp16 = getelementptr inbounds %struct.wombat, %struct.wombat* %tmp, i64 0, i32 0
+  %tmp17 = load i8*, i8** %tmp16, align 8
+  %tmp18 = icmp eq i8* %tmp17, null
+  ret void
+}
+
+; Function Attrs: nounwind willreturn
+declare hidden void @quux(%struct.zot*, i1) unnamed_addr #0 align 2
+
+attributes #0 = { nounwind willreturn }
+
+!0 = !{}