[GVN] Handle removal of first implicit CF instruction correctly

[mkazantsev]

Summary

When erasing an instruction, we can erase the one which is the first implicit
control flow instruction in the block. This will invalidate the respective map.
This patch ensures that we re-calculate the FirstImplicitControlFlowInsts for
a block every time we remove the first implicit CF instruction.

It is the fix for bug introduced in https://reviews.llvm.org/D37460; these two
patches should be merged together and are only separated for convenience
of review.

[mkazantsev]

Factor out common code.

[• dberlin]

lib/Transforms/Scalar/GVN.cpp

1202–1204

Please don't do this.
Just mark them all for deletion, unless there is a very good reason not to.

2103–2112

If you are going to try to abstract the deletion, you should do all the updating this wants (IE MD->removeInstrruction, etc)

Please don't call it eraseFromPaernt, that's meaningless. Please call it deleteInstruction or something

2318–2320

Ditto

[• dberlin]

lib/Transforms/Scalar/GVN.cpp

1202–1204

On the bug it sounded like you think not erasing immediately causes further problems.
Could you expand a bit?
It's hard to see how that could cause failures with this one since we would erase them after processing the current instruction.

The one in performScalarPRE, it looks like instructions marked to be erased are not erased after performing scalar PRE because it's done after GVN.

2318–2320

I can see how this may cause assertion failures (though it's silly that we do it this way), so you may have to leave this as a direct deleteInstruction call

[mkazantsev]

lib/Transforms/Scalar/GVN.cpp

1202–1204

No matter when we erase, we should update the implicit CF map after we do it. When we used OrderedInstructions we assumed that the invariant "first instruction with implicit CF" preserves, no matter what happens. But it appeared that it doesn't (for example, if there are two calls into readnone function with the same args in different blocks; then the dominated call can be eliminated).

Even if we mark for deletion, we should update the map immediately to be able to hoist across the marked instruction. Marking alone does not solve the problem, it will still need the same code that also updates the map. If marking is only needed for uniformity of GVN code, this can be done separately from fixing the actual bug.

[mkazantsev]

lib/Transforms/Scalar/GVN.cpp

1202–1204

Ok, it seems impossible here. NewInsts cannot contain such instructions since they were just created. I will assert on that.

[mkazantsev]

Followed Daniel's advices.

[• dberlin]

Both of the deletions are in PRE, after it has been successful. If either the inserted or the deleted instructions were implicit control flow, PRE should have been unsafe. It's probably worth noting this in a comment

[• dberlin]

"Even if we mark for deletion, we should update the map immediately to be able to hoist across the marked instruction. Marking alone does not solve the problem, it will still need the same code that also updates the map. If marking is only needed for uniformity of GVN code, this can be done separately from fixing the actual bug."
The instructions will be deleted and the map updated as soon as we return from this function up the call stack.
It will not prevent further anything, because

1. the hoisting has already happened (and all the functions in this stack are going to return and then the next thing that will happen is we will delete the dead instructions)
2. The marked instruction could not have blocked hoisting anyway, or else it would not have been safe to PRE.

[mkazantsev]

Yes, I agree. In the current version of the patch these facts are enforced by asserts. Thanks for clarification!

[reames]

lib/Transforms/Scalar/GVN.cpp

1202

This assertion doesn't look correct. Your message says the instruction doesn't have implicit control flow, the actual assert says it's not the first in the basic block. One or the other needs fixed.

1204

This looks highly suspicious. Why remove from MD, but not erase? I think you want to either a) remove the MD->removeInstruction (because it's handled on actual deletion), or b) leave a good comment here.

Also, if replacing eraseInstruction with markForDeletion really is NFC, it should be a standalone patch which this is rebased on.

2104

The switch to a range iteration, and addition of the assertion is a separable change. Please commit that as a change of it's own and rebase the patch to reduce the diff for review.

2109

This can be written as:
InvalidateImplicitCF |= new_condition;

2313

Hm, optional larger code organization suggestion. Could we introduce two operations: one which invalidates and one which rebuilds? This would make the invariants of the FillICFI function more clear and would make this code a bit more readable.

If we could arrange to have the ICFI lazily rebuild on access to the block, that might be an overall cleaner scheme.

Again, both parts are optional.

2408

This assert doesn't look like it belongs in the lamda. Lift out to containing function.

[• dberlin]

lib/Transforms/Scalar/GVN.cpp

2109

|= wouldn't short circuit however, since it's bitwise and not logical
So it would have to be InvalidateImplicitCF = x || y

[reames]

lib/Transforms/Scalar/GVN.cpp

2109

If we're actually worried about reducing the evaluation time of the RHS - not sure we are - we can manually LICM the expression "FirstICFI.lookup(I->getParent())" since this is all the same BB.

I'm not sure the minor time savings of the short circuit is worth the code complexity honestly. I'd also expect a decent compiler to recognize that this is actually boolean. If we don't get that case, dang we really should.

[mkazantsev]

Given that https://reviews.llvm.org/D37460 and this one should only go together, it makes more sense to merge them into one. I am abandoning this one; the fixed changes from here will be merged into https://reviews.llvm.org/D37460. Abandoning this one.

lib/Transforms/Scalar/GVN.cpp

1202

The intention here is to make sure that we don't need to take actions updating this map here. Actually this assertion doesn't bring in anything new because all map-related stuff is handled within markInstructionForDeletion.

1204

Thanks for pointing out. Submitted as separate change: https://reviews.llvm.org/D39369

2104

Commited as separate NFC: https://reviews.llvm.org/rL316748

2109

Reworked this piece to avoid both redundan execution and dangling pointers.

2313

I will consider ractoring out ICF-related stuff into a separate structure in follow-up patches.

2408

I wasn't certain that InstrsToErase always contains instructions from one block at this point, but it seems it does. Hoisted the assert out.

include/llvm/Transforms/Scalar/GVN.h

private:
   void dump(DenseMap<uint32_t, Value *> &d) const;
   bool iterateOnFunction(Function &F);
   bool performPRE(Function &F);
   bool performScalarPRE(Instruction *I);
   bool performScalarPREInsertion(Instruction *Instr, BasicBlock *Pred,
                                  BasicBlock *Curr, unsigned int ValNo);
   Value *findLeader(const BasicBlock *BB, uint32_t num);
   void cleanupGlobalSets();
-  void fillImplicitControlFlowInfo(ReversePostOrderTraversal<Function *> &RPOT);
+  void fillImplicitControlFlowInfo(BasicBlock *BB);
   void verifyRemoved(const Instruction *I) const;
   bool splitCriticalEdges();
   BasicBlock *splitCriticalEdges(BasicBlock *Pred, BasicBlock *Succ);
   bool replaceOperandsWithConsts(Instruction *I) const;
   bool propagateEquality(Value *LHS, Value *RHS, const BasicBlockEdge &Root,
                          bool DominatesByEdge);
   bool processFoldableCondBr(BranchInst *BI);
   void addDeadBlock(BasicBlock *BB);

lib/Transforms/Scalar/GVN.cpp

for (auto &PredLoad : PredLoads) {
 
     PredLoad.second = LoadPtr;
   }
 
   if (!CanDoPRE) {
     while (!NewInsts.empty()) {
       Instruction *I = NewInsts.pop_back_val();
       if (MD) MD->removeInstruction(I);
-      I->eraseFromParent();
+      assert(FirstImplicitControlFlowInsts.lookup(I->getParent()) != I &&
+             "Newly created instruction has implicit control flow?");
+      markInstructionForDeletion(I);
     }
     // HINT: Don't revert the edge-splitting as following transformation may
     // also need to split these critical edges.
     return !CriticalEdgePred.empty();
   }
 
   // Okay, we can eliminate this load by inserting a reload in the predecessor
   // and using PHI construction to get the value in the other predecessors, do
for (BasicBlock::iterator BI = BB->begin(), BE = BB->end();
     // If we need some instructions deleted, do it now.
     NumGVNInstr += InstrsToErase.size();
 
     // Avoid iterator invalidation.
     bool AtStart = BI == BB->begin();
     if (!AtStart)
       --BI;
 
-    for (SmallVectorImpl<Instruction *>::iterator I = InstrsToErase.begin(),
-         E = InstrsToErase.end(); I != E; ++I) {
-      DEBUG(dbgs() << "GVN removed: " << **I << '\n');
-      if (MD) MD->removeInstruction(*I);
-      DEBUG(verifyRemoved(*I));
-      (*I)->eraseFromParent();
+    bool InvalidateImplicitCF = false;
+    for (auto *I : InstrsToErase) {
+      assert(I->getParent() == BB && "Erasing instruction from wrong block?");
+      DEBUG(dbgs() << "GVN removed: " << *I << '\n');
+      if (MD) MD->removeInstruction(I);
+      DEBUG(verifyRemoved(I));
+      if (!InvalidateImplicitCF &&
+          FirstImplicitControlFlowInsts.lookup(I->getParent()) == I)
+        InvalidateImplicitCF = true;
+      I->eraseFromParent();
     }
 
     if (!InstrsToErase.empty())
       OI->invalidateBlock(BB);
+    if (InvalidateImplicitCF)
+      fillImplicitControlFlowInfo(BB);
     InstrsToErase.clear();
 
     if (AtStart)
       BI = BB->begin();
     else
       ++BI;
   }
 
if (MD && Phi->getType()->isPtrOrPtrVectorTy())
     MD->invalidateCachedPointerInfo(Phi);
   VN.erase(CurInst);
   removeFromLeaderTable(ValNo, CurInst, CurrentBlock);
 
   DEBUG(dbgs() << "GVN PRE removed: " << *CurInst << '\n');
   if (MD)
     MD->removeInstruction(CurInst);
   DEBUG(verifyRemoved(CurInst));
+  bool InvalidateImplicitCF =
+      FirstImplicitControlFlowInsts.lookup(CurInst->getParent()) == CurInst;
+  // FIXME: Intended to be markInstructionForDeletion(CurInst), but it causes
+  // some assertion failures.
   CurInst->eraseFromParent();
   OI->invalidateBlock(CurrentBlock);
+  if (InvalidateImplicitCF)
+    fillImplicitControlFlowInfo(CurrentBlock);
   ++NumGVNInstr;
 
   return true;
 }
 
 /// Perform a purely local form of PRE that looks for diamond
 /// control flow patterns and attempts to perform simple PRE at the join point.
 bool GVN::performPRE(Function &F) {
bool GVN::iterateOnFunction(Function &F) {
   cleanupGlobalSets();
 
   // Top-down walk of the dominator tree
   bool Changed = false;
   // Needed for value numbering with phi construction to work.
   // RPOT walks the graph in its constructor and will not be invalidated during
   // processBlock.
   ReversePostOrderTraversal<Function *> RPOT(&F);
-  fillImplicitControlFlowInfo(RPOT);
+
+  for (BasicBlock *BB : RPOT)
+    fillImplicitControlFlowInfo(BB);
   for (BasicBlock *BB : RPOT)
     Changed |= processBlock(BB);
 
   return Changed;
 }
 
 void GVN::cleanupGlobalSets() {
   VN.clear();
   LeaderTable.clear();
   BlockRPONumber.clear();
   TableAllocator.Reset();
   FirstImplicitControlFlowInsts.clear();
 }
 
 void
-GVN::fillImplicitControlFlowInfo(ReversePostOrderTraversal<Function *> &RPOT) {
+GVN::fillImplicitControlFlowInfo(BasicBlock *BB) {
   auto MayNotTransferExecutionToSuccessor = [&](const Instruction *I) {
+    // Make sure that the instruction is not marked for further removal.
+    assert(std::find(InstrsToErase.begin(), InstrsToErase.end(), I) ==
+           InstrsToErase.end() && "Filling before removed all marked insns?");
     // If a block's instruction doesn't always pass the control to its successor
     // instruction, mark the block as having implicit control flow. We use them
     // to avoid wrong assumptions of sort "if A is executed and B post-dominates
     // A, then B is also executed". This is not true is there is an implicit
     // control flow instruction (e.g. a guard) between them.
     //
     // TODO: Currently, isGuaranteedToTransferExecutionToSuccessor returns false
     // for volatile stores and loads because they can trap. The discussion on
auto MayNotTransferExecutionToSuccessor = [&](const Instruction *I) {
     }
     if (isa<StoreInst>(I)) {
       assert(cast<StoreInst>(I)->isVolatile() &&
              "Non-volatile store should transfer execution to successor!");
       return false;
     }
     return true;
   };
+  FirstImplicitControlFlowInsts.erase(BB);
 
-  for (BasicBlock *BB : RPOT)
-    for (auto &I : *BB)
-      if (MayNotTransferExecutionToSuccessor(&I)) {
-        FirstImplicitControlFlowInsts[BB] = &I;
-        break;
-      }
 }
 
 /// Verify that the specified instruction does not occur in our
 /// internal data structures.
 void GVN::verifyRemoved(const Instruction *Inst) const {
   VN.verifyRemoved(Inst);
 
   // Walk through the value number scope to make sure the instruction isn't

test/Transforms/GVN/PRE/2017-10-16-LoadPRECrash.ll

 declare i64* @getaddr_i64(i64 addrspace(100)*) #0
 
 ; Make sure that the test compiles without a crash.
 ; Bug https://bugs.llvm.org/show_bug.cgi?id=34937
 
 define hidden void @wrapon_fn173() {
 
 ; CHECK-LABEL: @wrapon_fn173
+; CHECK:       entry:
+; CHECK-NEXT:    call %ArrayImpl* @getaddr_ArrayImpl(%ArrayImpl addrspace(100)* undef)
+; CHECK-NEXT:    %.pre = load i64 addrspace(100)*, i64 addrspace(100)** null, align 8
+; CHECK-NEXT:    br label %loop
+; CHECK:       loop:
+; CHECK-NEXT:    call i64* @getaddr_i64(i64 addrspace(100)* %.pre)
+; CHECK-NEXT:    br label %loop
 
 entry:
   %0 = call %ArrayImpl* @getaddr_ArrayImpl(%ArrayImpl addrspace(100)* undef)
   br label %loop
 
 loop:
   %1 = call %ArrayImpl* @getaddr_ArrayImpl(%ArrayImpl addrspace(100)* undef)
   %2 = load i64 addrspace(100)*, i64 addrspace(100)** null, align 8
   %3 = call i64* @getaddr_i64(i64 addrspace(100)* %2)
   br label %loop
 }
 
 attributes #0 = { readnone }

test/Transforms/GVN/PRE/pre-load-implicit-cf-updates.ll

+; RUN: opt -S -gvn -enable-load-pre < %s | FileCheck %s
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+; These tests exercise situations when instructions that were first instructions
+; with implicit control flow get removed. We make sure that after that we don't
+; face crashes and are still able to perform PRE correctly.
+
+declare i32 @foo(i32 %arg) #0
+
+define hidden void @test_01(i32 %x, i32 %y) {
+
+; c2 only throws if c1 throws, so it can be safely removed and then PRE can
+; hoist the load out of loop.
+
+; CHECK-LABEL: @test_01
+; CHECK:       entry:
+; CHECK-NEXT:    %c1 = call i32 @foo(i32 %x)
+; CHECK-NEXT:    %val.pre = load i32, i32* null, align 8
+; CHECK-NEXT:    br label %loop
+; CHECK:       loop:
+; CHECK-NEXT:    %c3 = call i32 @foo(i32 %val.pre)
+; CHECK-NEXT:    br label %loop
+
+entry:
+  %c1 = call i32 @foo(i32 %x)
+  br label %loop
+
+loop:
+  %c2 = call i32 @foo(i32 %x)
+  %val = load i32, i32* null, align 8
+  %c3 = call i32 @foo(i32 %val)
+  br label %loop
+}
+
+define hidden void @test_02(i32 %x, i32 %y) {
+
+; PRE is not allowed because c2 may throw.
+
+; CHECK-LABEL: @test_02
+; CHECK:       entry:
+; CHECK-NEXT:    %c1 = call i32 @foo(i32 %x)
+; CHECK-NEXT:    br label %loop
+; CHECK:       loop:
+; CHECK-NEXT:    %c2 = call i32 @foo(i32 %y)
+; CHECK-NEXT:    %val = load i32, i32* null, align 8
+; CHECK-NEXT:    %c3 = call i32 @foo(i32 %val)
+; CHECK-NEXT:    br label %loop
+
+entry:
+  %c1 = call i32 @foo(i32 %x)
+  br label %loop
+
+loop:
+  %c2 = call i32 @foo(i32 %y)
+  %val = load i32, i32* null, align 8
+  %c3 = call i32 @foo(i32 %val)
+  br label %loop
+}
+
+define hidden void @test_03(i32 %x, i32 %y) {
+
+; PRE of load is allowed because c2 only throws if c1 throws. c3 should
+; not be eliminated. c4 is eliminated because it only throws if c3 throws.
+
+; CHECK-LABEL: @test_03
+; CHECK:       entry:
+; CHECK-NEXT:    %c1 = call i32 @foo(i32 %x)
+; CHECK-NEXT:    %val.pre = load i32, i32* null, align 8
+; CHECK-NEXT:    br label %loop
+; CHECK:       loop:
+; CHECK-NEXT:    %c3 = call i32 @foo(i32 %y)
+; CHECK-NEXT:    %c5 = call i32 @foo(i32 %val.pre)
+; CHECK-NEXT:    br label %loop
+
+entry:
+  %c1 = call i32 @foo(i32 %x)
+  br label %loop
+
+loop:
+  %c2 = call i32 @foo(i32 %x)
+  %val = load i32, i32* null, align 8
+  %c3 = call i32 @foo(i32 %y)
+  %val2 = load i32, i32* null, align 8
+  %c4 = call i32 @foo(i32 %y)
+  %c5 = call i32 @foo(i32 %val)
+  br label %loop
+}
+
+define hidden void @test_04(i32 %x, i32 %y) {
+
+; PRE is not allowed even after we remove c2 because now c3 prevents us from it.
+
+; CHECK-LABEL: @test_04
+; CHECK:       entry:
+; CHECK-NEXT:    %c1 = call i32 @foo(i32 %x)
+; CHECK-NEXT:    br label %loop
+; CHECK:       loop:
+; CHECK-NEXT:    %c3 = call i32 @foo(i32 %y)
+; CHECK-NEXT:    %val = load i32, i32* null, align 8
+; CHECK-NEXT:    %c5 = call i32 @foo(i32 %val)
+; CHECK-NEXT:    br label %loop
+
+entry:
+  %c1 = call i32 @foo(i32 %x)
+  br label %loop
+
+loop:
+  %c2 = call i32 @foo(i32 %x)
+  %c3 = call i32 @foo(i32 %y)
+  %val = load i32, i32* null, align 8
+  %c4 = call i32 @foo(i32 %y)
+  %c5 = call i32 @foo(i32 %val)
+  br label %loop
+}
+
+attributes #0 = { readnone }