Index: include/llvm/Transforms/Scalar/GVN.h =================================================================== --- include/llvm/Transforms/Scalar/GVN.h +++ include/llvm/Transforms/Scalar/GVN.h @@ -18,7 +18,6 @@ #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/MapVector.h" -#include "llvm/ADT/PostOrderIterator.h" #include "llvm/ADT/SetVector.h" #include "llvm/ADT/SmallVector.h" #include "llvm/Analysis/AliasAnalysis.h" @@ -28,7 +27,6 @@ #include "llvm/IR/PassManager.h" #include "llvm/Support/Allocator.h" #include "llvm/Support/Compiler.h" -#include "llvm/Transforms/Utils/OrderedInstructions.h" #include #include #include @@ -158,11 +156,7 @@ AssumptionCache *AC; SetVector DeadBlocks; OptimizationRemarkEmitter *ORE; - // Maps a block to the topmost instruction with implicit control flow in it. - DenseMap - FirstImplicitControlFlowInsts; - OrderedInstructions *OI; ValueTable VN; /// A mapping from value numbers to lists of Value*'s that @@ -274,7 +268,6 @@ BasicBlock *Curr, unsigned int ValNo); Value *findLeader(const BasicBlock *BB, uint32_t num); void cleanupGlobalSets(); - void fillImplicitControlFlowInfo(ReversePostOrderTraversal &RPOT); 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 @@ -38,7 +38,6 @@ #include "llvm/Analysis/OptimizationRemarkEmitter.h" #include "llvm/Analysis/PHITransAddr.h" #include "llvm/Analysis/TargetLibraryInfo.h" -#include "llvm/Analysis/ValueTracking.h" #include "llvm/IR/Attributes.h" #include "llvm/IR/BasicBlock.h" #include "llvm/IR/CallSite.h" @@ -1049,32 +1048,7 @@ // backwards through predecessors if needed. BasicBlock *LoadBB = LI->getParent(); BasicBlock *TmpBB = LoadBB; - bool IsSafeToSpeculativelyExecute = isSafeToSpeculativelyExecute(LI); - // Check that there is no implicit control flow instructions above our load in - // its block. If there is an instruction that doesn't always pass the - // execution to the following instruction, then moving through it may become - // invalid. For example: - // - // int arr[LEN]; - // int index = ???; - // ... - // guard(0 <= index && index < LEN); - // use(arr[index]); - // - // It is illegal to move the array access to any point above the guard, - // because if the index is out of bounds we should deoptimize rather than - // access the array. - // Check that there is no guard in this block above our intruction. - if (!IsSafeToSpeculativelyExecute) { - auto It = FirstImplicitControlFlowInsts.find(TmpBB); - if (It != FirstImplicitControlFlowInsts.end()) { - assert(It->second->getParent() == TmpBB && - "Implicit control flow map broken?"); - if (OI->dominates(It->second, LI)) - return false; - } - } while (TmpBB->getSinglePredecessor()) { TmpBB = TmpBB->getSinglePredecessor(); if (TmpBB == LoadBB) // Infinite (unreachable) loop. @@ -1089,11 +1063,6 @@ // which it was not previously executed. if (TmpBB->getTerminator()->getNumSuccessors() != 1) return false; - - // Check that there is no implicit control flow in a block above. - if (!IsSafeToSpeculativelyExecute && - FirstImplicitControlFlowInsts.count(TmpBB)) - return false; } assert(TmpBB); @@ -2014,8 +1983,6 @@ TLI = &RunTLI; VN.setAliasAnalysis(&RunAA); MD = RunMD; - OrderedInstructions OrderedInstrs(DT); - OI = &OrderedInstrs; VN.setMemDep(MD); ORE = RunORE; @@ -2105,9 +2072,6 @@ DEBUG(verifyRemoved(*I)); (*I)->eraseFromParent(); } - - if (!InstrsToErase.empty()) - OI->invalidateBlock(BB); InstrsToErase.clear(); if (AtStart) @@ -2303,7 +2267,6 @@ MD->removeInstruction(CurInst); DEBUG(verifyRemoved(CurInst)); CurInst->eraseFromParent(); - OI->invalidateBlock(CurrentBlock); ++NumGVNInstr; return true; @@ -2370,7 +2333,6 @@ // RPOT walks the graph in its constructor and will not be invalidated during // processBlock. ReversePostOrderTraversal RPOT(&F); - fillImplicitControlFlowInfo(RPOT); for (BasicBlock *BB : RPOT) Changed |= processBlock(BB); @@ -2382,45 +2344,6 @@ LeaderTable.clear(); BlockRPONumber.clear(); TableAllocator.Reset(); - FirstImplicitControlFlowInsts.clear(); -} - -void -GVN::fillImplicitControlFlowInfo(ReversePostOrderTraversal &RPOT) { - 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 (isa(I)) { - assert(cast(I)->isVolatile() && - "Non-volatile load should transfer execution to successor!"); - return false; - } - if (isa(I)) { - assert(cast(I)->isVolatile() && - "Non-volatile store should transfer execution to successor!"); - return false; - } - return true; - }; - - 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 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 @@ -0,0 +1,31 @@ +; 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 } Index: test/Transforms/GVN/PRE/pre-load-guards.ll =================================================================== --- test/Transforms/GVN/PRE/pre-load-guards.ll +++ /dev/null @@ -1,146 +0,0 @@ -; RUN: opt < %s -basicaa -gvn -enable-load-pre -S | FileCheck %s -target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64" - -declare void @llvm.experimental.guard(i1, ...) - -; This is a motivating example on why we prohibit hoisting through guards. -; In the bottom block, we check that the index is within bounds and only access -; the element in this case and deoptimize otherwise. If we hoist the load to a -; place above the guard, it will may lead to out-of-bound array access. -define i32 @test_motivation(i32* %p, i32* %q, i1 %C, i32 %index, i32 %len) { -; CHECK-LABEL: @test_motivation( -block1: - %el1 = getelementptr inbounds i32, i32* %q, i32 %index - %el2 = getelementptr inbounds i32, i32* %p, i32 %index - br i1 %C, label %block2, label %block3 - -block2: - -; CHECK: block2: -; CHECK-NEXT: br -; CHECK-NOT: load -; CHECK-NOT: sge -; CHECK-NOT: slt -; CHECK-NOT: and - br label %block4 - -block3: - store i32 0, i32* %el1 - br label %block4 - -block4: - -; CHECK: block4: -; CHECK: %cond1 = icmp sge i32 %index, 0 -; CHECK-NEXT: %cond2 = icmp slt i32 %index, %len -; CHECK-NEXT: %in.bounds = and i1 %cond1, %cond2 -; CHECK: call void (i1, ...) @llvm.experimental.guard(i1 %in.bounds) -; CHECK-NEXT: %PRE = load i32, i32* %P2 -; CHECK: ret i32 %PRE - - %P2 = phi i32* [%el2, %block3], [%el1, %block2] - %cond1 = icmp sge i32 %index, 0 - %cond2 = icmp slt i32 %index, %len - %in.bounds = and i1 %cond1, %cond2 - call void (i1, ...) @llvm.experimental.guard(i1 %in.bounds) [ "deopt"() ] - %PRE = load i32, i32* %P2 - ret i32 %PRE -} - -; Guard in load's block that is above the load should prohibit the PRE. -define i32 @test_guard_01(i32* %p, i32* %q, i1 %C, i1 %G) { -; CHECK-LABEL: @test_guard_01( -block1: - br i1 %C, label %block2, label %block3 - -block2: - -; CHECK: block2: -; CHECK-NEXT: br -; CHECK-NOT: load - - br label %block4 - -block3: - store i32 0, i32* %p - br label %block4 - -block4: - -; CHECK: block4: -; CHECK: call void (i1, ...) @llvm.experimental.guard(i1 %G) -; CHECK-NEXT: load -; CHECK: ret i32 - - %P2 = phi i32* [%p, %block3], [%q, %block2] - call void (i1, ...) @llvm.experimental.guard(i1 %G) [ "deopt"() ] - %PRE = load i32, i32* %P2 - ret i32 %PRE -} - -; Guard in load's block that is below the load should not prohibit the PRE. -define i32 @test_guard_02(i32* %p, i32* %q, i1 %C, i1 %G) { -; CHECK-LABEL: @test_guard_02( -block1: - br i1 %C, label %block2, label %block3 - -block2: - -; CHECK: block2: -; CHECK-NEXT: load i32, i32* %q - - br label %block4 - -block3: - store i32 0, i32* %p - br label %block4 - -block4: - -; CHECK: block4: -; CHECK-NEXT: phi i32 [ -; CHECK-NEXT: phi i32* [ -; CHECK-NEXT: call void (i1, ...) @llvm.experimental.guard(i1 %G) -; CHECK-NOT: load -; CHECK: ret i32 - - %P2 = phi i32* [%p, %block3], [%q, %block2] - %PRE = load i32, i32* %P2 - call void (i1, ...) @llvm.experimental.guard(i1 %G) [ "deopt"() ] - ret i32 %PRE -} - -; Guard above the load's block should prevent PRE from hoisting through it. -define i32 @test_guard_03(i32* %p, i32* %q, i1 %C, i1 %G) { -; CHECK-LABEL: @test_guard_03( -block1: - br i1 %C, label %block2, label %block3 - -block2: - -; CHECK: block2: -; CHECK-NEXT: br -; CHECK-NOT: load - - br label %block4 - -block3: - store i32 0, i32* %p - br label %block4 - -block4: - -; CHECK: block4: -; CHECK-NEXT: phi i32* -; CHECK-NEXT: call void (i1, ...) @llvm.experimental.guard(i1 %G) -; CHECK-NEXT: load -; CHECK-NEXT: ret i32 - - %P2 = phi i32* [%p, %block3], [%q, %block2] - call void (i1, ...) @llvm.experimental.guard(i1 %G) [ "deopt"() ] - br label %block5 - -block5: - %PRE = load i32, i32* %P2 - ret i32 %PRE -} Index: test/Transforms/GVN/PRE/pre-load.ll =================================================================== --- test/Transforms/GVN/PRE/pre-load.ll +++ test/Transforms/GVN/PRE/pre-load.ll @@ -430,31 +430,3 @@ call void @g(i32 %NOTPRE) cleanupret from %c2 unwind to caller } - -; Don't PRE load across calls. - -define i32 @test13(i32* noalias nocapture readonly %x, i32* noalias nocapture %r, i32 %a) { -; CHECK-LABEL: @test13( -; CHECK: entry: -; CHECK-NEXT: icmp eq -; CHECK-NEXT: br i1 -entry: - %tobool = icmp eq i32 %a, 0 - br i1 %tobool, label %if.end, label %if.then - -; CHECK: if.then: -; CHECK-NEXT: load i32 -; CHECK-NEXT: store i32 -if.then: - %uu = load i32, i32* %x, align 4 - store i32 %uu, i32* %r, align 4 - br label %if.end - -; CHECK: if.end: -; CHECK-NEXT: call void @f() -; CHECK-NEXT: load i32 -if.end: - call void @f() - %vv = load i32, i32* %x, align 4 - ret i32 %vv -}