[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

2180

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

2180

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 ↗

(On Diff #336196)

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

[aeubanks]

address comment

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.
+      for (auto *U : I->users()) {
+        if (auto *UI = dyn_cast<Instruction>(U))
+          ICF->removeInstruction(UI);
+      }
       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 { [4 x i8*] } { [4 x i8*] [i8* null, i8* null, i8* undef, i8* bitcast (void (%struct.zot*, i1)* @quux to i8*)] }, align 8
+
+define hidden void @eggs(%struct.zot* %arg) 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** getelementptr inbounds ({ [4 x i8*] }, { [4 x i8*] }* @global, i64 0, inrange i32 0, i64 2) to i32 (...)**), i32 (...)*** %tmp1, align 8, !invariant.group !0
+  br i1 undef, label %bb4, label %bb2
+
+bb2:                                              ; preds = %bb
+  %tmp3 = atomicrmw sub i32* undef, i32 undef acq_rel, align 4
+  br label %bb4
+
+bb4:                                              ; preds = %bb2, %bb
+  %tmp5 = load %struct.baz*, %struct.baz** null, align 8
+  %tmp6 = getelementptr inbounds %struct.baz, %struct.baz* %tmp5, i64 0, i32 1
+  br i1 undef, label %bb9, label %bb7
+
+bb7:                                              ; preds = %bb4
+  %tmp8 = tail call i8* undef()
+  br label %bb9
+
+bb9:                                              ; preds = %bb7, %bb4
+  %tmp10 = load %struct.baz*, %struct.baz** null, 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 1
+  %tmp15 = load void (%struct.zot*, i1)*, void (%struct.zot*, i1)** %tmp14, align 8
+  tail call void %tmp15(%struct.zot* %arg, i1 undef)
+  %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 = !{}