Index: include/llvm/Transforms/Scalar/GVN.h =================================================================== --- include/llvm/Transforms/Scalar/GVN.h +++ include/llvm/Transforms/Scalar/GVN.h @@ -274,7 +274,7 @@ BasicBlock *Curr, unsigned int ValNo); Value *findLeader(const BasicBlock *BB, uint32_t num); void cleanupGlobalSets(); - void fillImplicitControlFlowInfo(ReversePostOrderTraversal &RPOT); + void fillImplicitControlFlowInfo(BasicBlock *BB); void verifyRemoved(const Instruction *I) const; bool splitCriticalEdges(); BasicBlock *splitCriticalEdges(BasicBlock *Pred, BasicBlock *Succ); Index: lib/Transforms/Scalar/GVN.cpp =================================================================== --- lib/Transforms/Scalar/GVN.cpp +++ lib/Transforms/Scalar/GVN.cpp @@ -1199,7 +1199,9 @@ 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. @@ -2098,16 +2100,22 @@ if (!AtStart) --BI; - for (SmallVectorImpl::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) @@ -2302,8 +2310,14 @@ 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; @@ -2370,7 +2384,9 @@ // RPOT walks the graph in its constructor and will not be invalidated during // processBlock. ReversePostOrderTraversal RPOT(&F); - fillImplicitControlFlowInfo(RPOT); + + for (BasicBlock *BB : RPOT) + fillImplicitControlFlowInfo(BB); for (BasicBlock *BB : RPOT) Changed |= processBlock(BB); @@ -2386,8 +2402,11 @@ } void -GVN::fillImplicitControlFlowInfo(ReversePostOrderTraversal &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 @@ -2414,13 +2433,13 @@ } return true; }; + FirstImplicitControlFlowInsts.erase(BB); - for (BasicBlock *BB : RPOT) - for (auto &I : *BB) - if (MayNotTransferExecutionToSuccessor(&I)) { - FirstImplicitControlFlowInsts[BB] = &I; - break; - } + for (auto &I : *BB) + if (MayNotTransferExecutionToSuccessor(&I)) { + FirstImplicitControlFlowInsts[BB] = &I; + break; + } } /// Verify that the specified instruction does not occur in our Index: test/Transforms/GVN/PRE/2017-10-16-LoadPRECrash.ll =================================================================== --- test/Transforms/GVN/PRE/2017-10-16-LoadPRECrash.ll +++ test/Transforms/GVN/PRE/2017-10-16-LoadPRECrash.ll @@ -17,6 +17,13 @@ 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) Index: test/Transforms/GVN/PRE/pre-load-implicit-cf-updates.ll =================================================================== --- /dev/null +++ test/Transforms/GVN/PRE/pre-load-implicit-cf-updates.ll @@ -0,0 +1,118 @@ +; 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 }