Index: llvm/trunk/include/llvm/Transforms/Utils/MemorySSA.h =================================================================== --- llvm/trunk/include/llvm/Transforms/Utils/MemorySSA.h +++ llvm/trunk/include/llvm/Transforms/Utils/MemorySSA.h @@ -974,6 +974,10 @@ inline upward_defs_iterator upward_defs_end() { return upward_defs_iterator(); } +bool instructionClobbersQuery(MemoryDef *MD, + const MemoryLocation &UseLoc, + const Instruction *UseInst, + AliasAnalysis &AA); } // end namespace llvm #endif // LLVM_TRANSFORMS_UTILS_MEMORYSSA_H Index: llvm/trunk/lib/Transforms/Scalar/GVNHoist.cpp =================================================================== --- llvm/trunk/lib/Transforms/Scalar/GVNHoist.cpp +++ llvm/trunk/lib/Transforms/Scalar/GVNHoist.cpp @@ -329,31 +329,36 @@ return I1DFS < I2DFS; } - // Return true when there are users of Def in BB. - bool hasMemoryUseOnPath(MemoryAccess *Def, const BasicBlock *BB, - const Instruction *OldPt) { - const BasicBlock *DefBB = Def->getBlock(); - const BasicBlock *OldBB = OldPt->getParent(); + // Return true when there are memory uses of Def in BB. + bool hasMemoryUse(const Instruction *NewPt, MemoryDef *Def, + const BasicBlock *BB) { + const MemorySSA::AccessList *Acc = MSSA->getBlockAccesses(BB); + if (!Acc) + return false; - for (User *U : Def->users()) - if (auto *MU = dyn_cast(U)) { - // FIXME: MU->getBlock() does not get updated when we move the instruction. - BasicBlock *UBB = MU->getMemoryInst()->getParent(); - // Only analyze uses in BB. - if (BB != UBB) - continue; + Instruction *OldPt = Def->getMemoryInst(); + const BasicBlock *OldBB = OldPt->getParent(); + const BasicBlock *NewBB = NewPt->getParent(); + bool ReachedNewPt = false; - // A use in the same block as the Def is on the path. - if (UBB == DefBB) { - assert(MSSA->locallyDominates(Def, MU) && "def not dominating use"); - return true; - } + for (const MemoryAccess &MA : *Acc) + if (const MemoryUse *MU = dyn_cast(&MA)) { + Instruction *Insn = MU->getMemoryInst(); - if (UBB != OldBB) - return true; + // Do not check whether MU aliases Def when MU occurs after OldPt. + if (BB == OldBB && firstInBB(OldPt, Insn)) + break; - // It is only harmful to hoist when the use is before OldPt. - if (firstInBB(MU->getMemoryInst(), OldPt)) + // Do not check whether MU aliases Def when MU occurs before NewPt. + if (BB == NewBB) { + if (!ReachedNewPt) { + if (firstInBB(Insn, NewPt)) + continue; + ReachedNewPt = true; + } + } + if (instructionClobbersQuery(Def, MemoryLocation::get(Insn), Insn, + *AA)) return true; } @@ -361,17 +366,18 @@ } // Return true when there are exception handling or loads of memory Def - // between OldPt and NewPt. + // between Def and NewPt. This function is only called for stores: Def is + // the MemoryDef of the store to be hoisted. // Decrement by 1 NBBsOnAllPaths for each block between HoistPt and BB, and // return true when the counter NBBsOnAllPaths reaces 0, except when it is // initialized to -1 which is unlimited. - bool hasEHOrLoadsOnPath(const Instruction *NewPt, const Instruction *OldPt, - MemoryAccess *Def, int &NBBsOnAllPaths) { + bool hasEHOrLoadsOnPath(const Instruction *NewPt, MemoryDef *Def, + int &NBBsOnAllPaths) { const BasicBlock *NewBB = NewPt->getParent(); - const BasicBlock *OldBB = OldPt->getParent(); + const BasicBlock *OldBB = Def->getBlock(); assert(DT->dominates(NewBB, OldBB) && "invalid path"); - assert(DT->dominates(Def->getBlock(), NewBB) && + assert(DT->dominates(Def->getDefiningAccess()->getBlock(), NewBB) && "def does not dominate new hoisting point"); // Walk all basic blocks reachable in depth-first iteration on the inverse @@ -390,7 +396,7 @@ return true; // Check that we do not move a store past loads. - if (hasMemoryUseOnPath(Def, *I, OldPt)) + if (hasMemoryUse(NewPt, Def, *I)) return true; // Stop walk once the limit is reached. @@ -473,7 +479,7 @@ // Check for unsafe hoistings due to side effects. if (K == InsKind::Store) { - if (hasEHOrLoadsOnPath(NewPt, OldPt, D, NBBsOnAllPaths)) + if (hasEHOrLoadsOnPath(NewPt, dyn_cast(U), NBBsOnAllPaths)) return false; } else if (hasEHOnPath(NewBB, OldBB, NBBsOnAllPaths)) return false; Index: llvm/trunk/lib/Transforms/Utils/MemorySSA.cpp =================================================================== --- llvm/trunk/lib/Transforms/Utils/MemorySSA.cpp +++ llvm/trunk/lib/Transforms/Utils/MemorySSA.cpp @@ -169,44 +169,6 @@ return LHS == RHS; } }; -} - -namespace { -struct UpwardsMemoryQuery { - // True if our original query started off as a call - bool IsCall; - // The pointer location we started the query with. This will be empty if - // IsCall is true. - MemoryLocation StartingLoc; - // This is the instruction we were querying about. - const Instruction *Inst; - // The MemoryAccess we actually got called with, used to test local domination - const MemoryAccess *OriginalAccess; - - UpwardsMemoryQuery() - : IsCall(false), Inst(nullptr), OriginalAccess(nullptr) {} - - UpwardsMemoryQuery(const Instruction *Inst, const MemoryAccess *Access) - : IsCall(ImmutableCallSite(Inst)), Inst(Inst), OriginalAccess(Access) { - if (!IsCall) - StartingLoc = MemoryLocation::get(Inst); - } -}; - -static bool lifetimeEndsAt(MemoryDef *MD, const MemoryLocation &Loc, - AliasAnalysis &AA) { - Instruction *Inst = MD->getMemoryInst(); - if (IntrinsicInst *II = dyn_cast(Inst)) { - switch (II->getIntrinsicID()) { - case Intrinsic::lifetime_start: - case Intrinsic::lifetime_end: - return AA.isMustAlias(MemoryLocation(II->getArgOperand(1)), Loc); - default: - return false; - } - } - return false; -} enum class Reorderability { Always, IfNoAlias, Never }; @@ -248,21 +210,10 @@ return Result; } -static bool isUseTriviallyOptimizableToLiveOnEntry(AliasAnalysis &AA, - const Instruction *I) { - // If the memory can't be changed, then loads of the memory can't be - // clobbered. - // - // FIXME: We should handle invariant groups, as well. It's a bit harder, - // because we need to pay close attention to invariant group barriers. - return isa(I) && (I->getMetadata(LLVMContext::MD_invariant_load) || - AA.pointsToConstantMemory(I)); -} - -static bool instructionClobbersQuery(MemoryDef *MD, - const MemoryLocation &UseLoc, - const Instruction *UseInst, - AliasAnalysis &AA) { +bool instructionClobbersQuery(MemoryDef *MD, + const MemoryLocation &UseLoc, + const Instruction *UseInst, + AliasAnalysis &AA) { Instruction *DefInst = MD->getMemoryInst(); assert(DefInst && "Defining instruction not actually an instruction"); @@ -303,6 +254,56 @@ return AA.getModRefInfo(DefInst, UseLoc) & MRI_Mod; } +} + +namespace { +struct UpwardsMemoryQuery { + // True if our original query started off as a call + bool IsCall; + // The pointer location we started the query with. This will be empty if + // IsCall is true. + MemoryLocation StartingLoc; + // This is the instruction we were querying about. + const Instruction *Inst; + // The MemoryAccess we actually got called with, used to test local domination + const MemoryAccess *OriginalAccess; + + UpwardsMemoryQuery() + : IsCall(false), Inst(nullptr), OriginalAccess(nullptr) {} + + UpwardsMemoryQuery(const Instruction *Inst, const MemoryAccess *Access) + : IsCall(ImmutableCallSite(Inst)), Inst(Inst), OriginalAccess(Access) { + if (!IsCall) + StartingLoc = MemoryLocation::get(Inst); + } +}; + +static bool lifetimeEndsAt(MemoryDef *MD, const MemoryLocation &Loc, + AliasAnalysis &AA) { + Instruction *Inst = MD->getMemoryInst(); + if (IntrinsicInst *II = dyn_cast(Inst)) { + switch (II->getIntrinsicID()) { + case Intrinsic::lifetime_start: + case Intrinsic::lifetime_end: + return AA.isMustAlias(MemoryLocation(II->getArgOperand(1)), Loc); + default: + return false; + } + } + return false; +} + +static bool isUseTriviallyOptimizableToLiveOnEntry(AliasAnalysis &AA, + const Instruction *I) { + // If the memory can't be changed, then loads of the memory can't be + // clobbered. + // + // FIXME: We should handle invariant groups, as well. It's a bit harder, + // because we need to pay close attention to invariant group barriers. + return isa(I) && (I->getMetadata(LLVMContext::MD_invariant_load) || + AA.pointsToConstantMemory(I)); +} + static bool instructionClobbersQuery(MemoryDef *MD, MemoryUse *MU, const MemoryLocOrCall &UseMLOC, AliasAnalysis &AA) { Index: llvm/trunk/test/Transforms/GVNHoist/pr30216.ll =================================================================== --- llvm/trunk/test/Transforms/GVNHoist/pr30216.ll +++ llvm/trunk/test/Transforms/GVNHoist/pr30216.ll @@ -0,0 +1,52 @@ +; RUN: opt -S -gvn-hoist < %s | FileCheck %s + +; Make sure the two stores @B do not get hoisted past the load @B. + +; CHECK-LABEL: define i8* @Foo +; CHECK: store +; CHECK: store +; CHECK: load +; CHECK: store + +@A = external global i8 +@B = external global i8* + +define i8* @Foo() { + store i8 0, i8* @A + br i1 undef, label %if.then, label %if.else + +if.then: + store i8* null, i8** @B + ret i8* null + +if.else: + %1 = load i8*, i8** @B + store i8* null, i8** @B + ret i8* %1 +} + +; Make sure the two stores @B do not get hoisted past the store @GlobalVar. + +; CHECK-LABEL: define i8* @Fun +; CHECK: store +; CHECK: store +; CHECK: store +; CHECK: store +; CHECK: load + +@GlobalVar = internal global i8 0 + +define i8* @Fun() { + store i8 0, i8* @A + br i1 undef, label %if.then, label %if.else + +if.then: + store i8* null, i8** @B + ret i8* null + +if.else: + store i8 0, i8* @GlobalVar + store i8* null, i8** @B + %1 = load i8*, i8** @B + ret i8* %1 +} Index: llvm/trunk/test/Transforms/GVNHoist/pr30499.ll =================================================================== --- llvm/trunk/test/Transforms/GVNHoist/pr30499.ll +++ llvm/trunk/test/Transforms/GVNHoist/pr30499.ll @@ -0,0 +1,30 @@ +; RUN: opt -S -gvn-hoist < %s + +define void @_Z3fn2v() #0 { +entry: + %a = alloca i8*, align 8 + %b = alloca i32, align 4 + %0 = load i8*, i8** %a, align 8 + store i8 0, i8* %0, align 1 + %1 = load i32, i32* %b, align 4 + %tobool = icmp ne i32 %1, 0 + br i1 %tobool, label %if.then, label %if.end + +if.then: ; preds = %entry + %call = call i64 @_Z3fn1v() #2 + %conv = trunc i64 %call to i32 + store i32 %conv, i32* %b, align 4 + br label %if.end + +if.end: ; preds = %if.then, %entry + %2 = load i8*, i8** %a, align 8 + store i8 0, i8* %2, align 1 + ret void +} + +; Function Attrs: nounwind readonly +declare i64 @_Z3fn1v() #1 + +attributes #0 = { nounwind "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "less-precise-fpmad"="false" "no-frame-pointer-elim"="false" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+fxsr,+mmx,+sse,+sse2,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" } +attributes #1 = { nounwind readonly "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "less-precise-fpmad"="false" "no-frame-pointer-elim"="false" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+fxsr,+mmx,+sse,+sse2,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" } +attributes #2 = { nounwind readonly }