[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

1204–1206

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

2108–2110

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

2314

Ditto

[• dberlin]

lib/Transforms/Scalar/GVN.cpp

1204–1206

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.

2314

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

1204–1206

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

1204–1206

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

1204–1206

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.

1206

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.

2109

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.

2114

This can be written as:
InvalidateImplicitCF |= new_condition;

2309

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.

2402

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

[• dberlin]

lib/Transforms/Scalar/GVN.cpp

2114

|= 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

2114

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

1204–1206

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.

1206

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

2109

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

2114

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

2309

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

2402

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);
+  bool isFirstImplicitControlFlowInstruction(Instruction *I);
   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);
+      BasicBlock *IBB = I->getParent();
+      bool IsFirstImplicitCF = isFirstImplicitControlFlowInstruction(I);
       I->eraseFromParent();
+      if (IsFirstImplicitCF)
+        fillImplicitControlFlowInfo(IBB);
     }
     // 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 (!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));
+      BasicBlock *IBB = (*I)->getParent();
+      bool IsFirstImplicitCF = isFirstImplicitControlFlowInstruction(*I);
       (*I)->eraseFromParent();
+      if (IsFirstImplicitCF)
+        fillImplicitControlFlowInfo(IBB);
     }
 
     if (!InstrsToErase.empty())
       OI->invalidateBlock(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 IsFirstImplicitCF = isFirstImplicitControlFlowInstruction(CurInst);
   CurInst->eraseFromParent();
+  if (IsFirstImplicitCF)
+    fillImplicitControlFlowInfo(CurrentBlock);
   OI->invalidateBlock(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) {
     // 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
     // whether or not it is correct is still ongoing. We might want to get rid
     // of this logic in the future. Anyways, trapping instructions shouldn't
     // introduce implicit control flow, so we explicitly allow them here. This
     // must be removed once isGuaranteedToTransferExecutionToSuccessor is fixed.
     if (isGuaranteedToTransferExecutionToSuccessor(I))
       return false;
     if (auto *LI = dyn_cast<LoadInst>(I)) {
       assert(LI->isVolatile() && "Non-volatile load should transfer execution"
                                  " to successor!");
       return false;
     }
     if (auto *SI = dyn_cast<StoreInst>(I)) {
       assert(SI->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;
-      }
 }
 
+bool GVN::isFirstImplicitControlFlowInstruction(Instruction *I) {
+  assert(I->getParent() && "Instruction already erased?");
+  auto It = FirstImplicitControlFlowInsts.find(I->getParent());
+  if (It == FirstImplicitControlFlowInsts.end())
+    return false;
+  return It->second == I;
+}
+
 /// 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
   // ferreted away in it.
   for (DenseMap<uint32_t, LeaderTableEntry>::const_iterator

test/Transforms/GVN/PRE/2017-10-16-LoadPRECrash.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"
+
+%ArrayImpl = type { i64, i64 addrspace(100)*, [1 x i64], [1 x i64], [1 x i64], i64, i64, double addrspace(100)*, double addrspace(100)*, i8, i64 }
+
+; Function Attrs: readnone
+declare %ArrayImpl* @getaddr_ArrayImpl(%ArrayImpl addrspace(100)*) #0
+
+; Function Attrs: readnone
+declare i64* @getaddr_i64(i64 addrspace(100)*) #0
+
+; Make sure that the test compiles without a crash.
+
+define hidden void @wrapon_fn173() {
+
+; CHECK-LABEL: @wrapon_fn173
+
+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 }