This is an archive of the discontinued LLVM Phabricator instance.

Differential D25476

GVN-hoist: fix store past load dependence analysis (PR30216, PR30499)
ClosedPublic

Authored by sebpop on Oct 11 2016, 8:30 AM.

Details

Reviewers
• dberlin
Commits
rGab12fb62ee04: GVN-hoist: fix store past load dependence analysis (PR30216, PR30499)
rL283965: GVN-hoist: fix store past load dependence analysis (PR30216, PR30499)
Summary

This is a refreshed version of a patch that was reverted: it fixes
the problems reported in both PR30216 and PR30499, and
contains all the test-cases from both bugs.

To hoist stores past loads, we used to search for potential
conflicting loads on the hoisting path by following a MemorySSA
def-def link from the store to be hoisted to the previous
defining memory access, and from there we followed the def-use
chains to all the uses that occur on the hoisting path. The
problem is that the def-def link may point to a store that does
not alias with the store to be hoisted, and so the loads that are
walked may not alias with the store to be hoisted, and even as in
the testcase of PR30216, the loads that may alias with the store
to be hoisted are not visited.

The current patch visits all loads on the path from the store to
be hoisted to the hoisting position and uses the alias analysis
to ask whether the store may alias the load. I was not able to
use the MemorySSA functionality to ask for whether load and
store are clobbered: I'm not sure which function to call, so I
used a call to AA->isNoAlias().

Store past store is still working as before using a MemorySSA
query: I added an extra test to pr30216.ll to make sure store
past store does not regress.

Tested on x86_64-linux with check and a test-suite run.

Diff Detail

Repository
rL LLVM

Event Timeline

sebpop updated this revision to Diff 74255.Oct 11 2016, 8:30 AM
sebpop retitled this revision from to GVN-hoist: fix store past load dependence analysis (PR30216, PR30499).
sebpop updated this object.
sebpop added a reviewer: • dberlin.
sebpop added subscribers: george.burgess.iv, llvm-commits.
sebpop updated this revision to Diff 74281.Oct 11 2016, 11:52 AM

Updated to use MemorySSA.cpp:instructionClobbersQuery().
Thanks Danny for insisting on properly fixing this.

sebpop added a comment.Oct 11 2016, 11:59 AM

The way diff and phabricator displays the MemorySSA.cpp change is strange:
all I did is move getLoadReorderability() and instructionClobbersQuery() up in the llvm namespace, all the rest remains in place.
As the amount of text remaining in place is less than what moves, diff decided to display the complement.

• dberlin accepted this revision.Oct 11 2016, 6:23 PM
• dberlin edited edge metadata.
• dberlin added inline comments.
llvm/include/llvm/Transforms/Utils/MemorySSA.h
977 ↗(On Diff #74281)

I would really rather not expose this version.
We should keep the interface as "memorydefs and memoryuses" as much as possible.

It also shouldn't be named instructionClobbersQuery.

So i would expect this to be something like

bool defClobbersUseOrDef(MemoryDef *MD, MemoryUseOrDef *MU, AliasAnalysis &AA);

Internally, it obviously will just call a version of instructionClobbersQuery, but that should be an API implementation detail.
I'm fine fixing this in a followup though.

This revision is now accepted and ready to land.Oct 11 2016, 6:23 PM
sebpop added inline comments.Oct 11 2016, 8:19 PM
llvm/include/llvm/Transforms/Utils/MemorySSA.h
977 ↗(On Diff #74281)

Committed the patch as r283965.
Committed the followup cleanup separately as r283967.

Closed by commit rL283965: GVN-hoist: fix store past load dependence analysis (PR30216, PR30499) (authored by spop). · Explain WhyOct 12 2016, 12:57 AM
This revision was automatically updated to reflect the committed changes.

Revision Contents

PathSize
llvm/
trunk/
include/
llvm/
Transforms/
Utils/
4 lines
lib/
Transforms/
Scalar/
62 lines
Utils/
107 lines
test/
Transforms/
GVNHoist/
52 lines
30 lines

Diff 74337

llvm/trunk/include/llvm/Transforms/Utils/MemorySSA.h

Show First 20 Lines • Show All 968 Lines • ▼ Show 20 Lines
}; };
inline upward_defs_iterator upward_defs_begin(const MemoryAccessPair &Pair) { inline upward_defs_iterator upward_defs_begin(const MemoryAccessPair &Pair) {
return upward_defs_iterator(Pair); return upward_defs_iterator(Pair);
} }
inline upward_defs_iterator upward_defs_end() { return upward_defs_iterator(); } 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 } // end namespace llvm
#endif // LLVM_TRANSFORMS_UTILS_MEMORYSSA_H #endif // LLVM_TRANSFORMS_UTILS_MEMORYSSA_H

llvm/trunk/lib/Transforms/Scalar/GVNHoist.cpp

Show First 20 Lines • Show All 323 Lines • ▼ Show 20 Linesprivate:
bool firstInBB(const Instruction *I1, const Instruction *I2) { bool firstInBB(const Instruction *I1, const Instruction *I2) {
assert (I1->getParent() == I2->getParent()); assert (I1->getParent() == I2->getParent());
unsigned I1DFS = DFSNumber.lookup(I1); unsigned I1DFS = DFSNumber.lookup(I1);
unsigned I2DFS = DFSNumber.lookup(I2); unsigned I2DFS = DFSNumber.lookup(I2);
assert (I1DFS && I2DFS); assert (I1DFS && I2DFS);
return I1DFS < I2DFS; return I1DFS < I2DFS;
} }
// Return true when there are users of Def in BB. // Return true when there are memory uses of Def in BB.
bool hasMemoryUseOnPath(MemoryAccess *Def, const BasicBlock *BB, bool hasMemoryUse(const Instruction *NewPt, MemoryDef *Def,
const Instruction *OldPt) { const BasicBlock *BB) {
const BasicBlock *DefBB = Def->getBlock(); const MemorySSA::AccessList *Acc = MSSA->getBlockAccesses(BB);
const BasicBlock *OldBB = OldPt->getParent(); if (!Acc)
return false;
for (User *U : Def->users()) Instruction *OldPt = Def->getMemoryInst();
if (auto *MU = dyn_cast<MemoryUse>(U)) { const BasicBlock *OldBB = OldPt->getParent();
// FIXME: MU->getBlock() does not get updated when we move the instruction. const BasicBlock *NewBB = NewPt->getParent();
BasicBlock *UBB = MU->getMemoryInst()->getParent(); bool ReachedNewPt = false;
// Only analyze uses in BB.
if (BB != UBB)
continue;
// A use in the same block as the Def is on the path. for (const MemoryAccess &MA : *Acc)
if (UBB == DefBB) { if (const MemoryUse *MU = dyn_cast<MemoryUse>(&MA)) {
assert(MSSA->locallyDominates(Def, MU) && "def not dominating use"); Instruction *Insn = MU->getMemoryInst();
return true;
}
if (UBB != OldBB) // Do not check whether MU aliases Def when MU occurs after OldPt.
return true; if (BB == OldBB && firstInBB(OldPt, Insn))
break;
// It is only harmful to hoist when the use is before OldPt. // Do not check whether MU aliases Def when MU occurs before NewPt.
if (firstInBB(MU->getMemoryInst(), OldPt)) if (BB == NewBB) {
if (!ReachedNewPt) {
if (firstInBB(Insn, NewPt))
continue;
ReachedNewPt = true;
}
}
if (instructionClobbersQuery(Def, MemoryLocation::get(Insn), Insn,
*AA))
return true; return true;
} }
return false; return false;
} }
// Return true when there are exception handling or loads of memory Def // 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 // Decrement by 1 NBBsOnAllPaths for each block between HoistPt and BB, and
// return true when the counter NBBsOnAllPaths reaces 0, except when it is // return true when the counter NBBsOnAllPaths reaces 0, except when it is
// initialized to -1 which is unlimited. // initialized to -1 which is unlimited.
bool hasEHOrLoadsOnPath(const Instruction *NewPt, const Instruction *OldPt, bool hasEHOrLoadsOnPath(const Instruction *NewPt, MemoryDef *Def,
MemoryAccess *Def, int &NBBsOnAllPaths) { int &NBBsOnAllPaths) {
const BasicBlock *NewBB = NewPt->getParent(); 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(NewBB, OldBB) && "invalid path");
assert(DT->dominates(Def->getBlock(), NewBB) && assert(DT->dominates(Def->getDefiningAccess()->getBlock(), NewBB) &&
"def does not dominate new hoisting point"); "def does not dominate new hoisting point");
// Walk all basic blocks reachable in depth-first iteration on the inverse // Walk all basic blocks reachable in depth-first iteration on the inverse
// CFG from OldBB to NewBB. These blocks are all the blocks that may be // CFG from OldBB to NewBB. These blocks are all the blocks that may be
// executed between the execution of NewBB and OldBB. Hoisting an expression // executed between the execution of NewBB and OldBB. Hoisting an expression
// from OldBB into NewBB has to be safe on all execution paths. // from OldBB into NewBB has to be safe on all execution paths.
for (auto I = idf_begin(OldBB), E = idf_end(OldBB); I != E;) { for (auto I = idf_begin(OldBB), E = idf_end(OldBB); I != E;) {
if (*I == NewBB) { if (*I == NewBB) {
// Stop traversal when reaching HoistPt. // Stop traversal when reaching HoistPt.
I.skipChildren(); I.skipChildren();
continue; continue;
} }
// Impossible to hoist with exceptions on the path. // Impossible to hoist with exceptions on the path.
if (hasEH(*I)) if (hasEH(*I))
return true; return true;
// Check that we do not move a store past loads. // Check that we do not move a store past loads.
if (hasMemoryUseOnPath(Def, *I, OldPt)) if (hasMemoryUse(NewPt, Def, *I))
return true; return true;
// Stop walk once the limit is reached. // Stop walk once the limit is reached.
if (NBBsOnAllPaths == 0) if (NBBsOnAllPaths == 0)
return true; return true;
// -1 is unlimited number of blocks on all paths. // -1 is unlimited number of blocks on all paths.
if (NBBsOnAllPaths != -1) if (NBBsOnAllPaths != -1)
▲ Show 20 Lines • Show All 66 Lines • ▼ Show 20 Lines bool safeToHoistLdSt(const Instruction *NewPt, const Instruction *OldPt,
if (NewBB == DBB && !MSSA->isLiveOnEntryDef(D)) if (NewBB == DBB && !MSSA->isLiveOnEntryDef(D))
if (auto *UD = dyn_cast<MemoryUseOrDef>(D)) if (auto *UD = dyn_cast<MemoryUseOrDef>(D))
if (firstInBB(NewPt, UD->getMemoryInst())) if (firstInBB(NewPt, UD->getMemoryInst()))
// Cannot move the load or store to NewPt above its definition in D. // Cannot move the load or store to NewPt above its definition in D.
return false; return false;
// Check for unsafe hoistings due to side effects. // Check for unsafe hoistings due to side effects.
if (K == InsKind::Store) { if (K == InsKind::Store) {
if (hasEHOrLoadsOnPath(NewPt, OldPt, D, NBBsOnAllPaths)) if (hasEHOrLoadsOnPath(NewPt, dyn_cast<MemoryDef>(U), NBBsOnAllPaths))
return false; return false;
} else if (hasEHOnPath(NewBB, OldBB, NBBsOnAllPaths)) } else if (hasEHOnPath(NewBB, OldBB, NBBsOnAllPaths))
return false; return false;
if (UBB == NewBB) { if (UBB == NewBB) {
if (DT->properlyDominates(DBB, NewBB)) if (DT->properlyDominates(DBB, NewBB))
return true; return true;
assert(UBB == DBB); assert(UBB == DBB);
▲ Show 20 Lines • Show All 513 Lines • Show Last 20 Lines

llvm/trunk/lib/Transforms/Utils/MemorySSA.cpp

Show First 20 Lines • Show All 163 Lines • ▼ Show 20 Lines if (MLOC.IsCall)
MLOC.getCS().getCalledValue())); MLOC.getCS().getCalledValue()));
return hash_combine( return hash_combine(
MLOC.IsCall, DenseMapInfo<MemoryLocation>::getHashValue(MLOC.getLoc())); MLOC.IsCall, DenseMapInfo<MemoryLocation>::getHashValue(MLOC.getLoc()));
} }
static bool isEqual(const MemoryLocOrCall &LHS, const MemoryLocOrCall &RHS) { static bool isEqual(const MemoryLocOrCall &LHS, const MemoryLocOrCall &RHS) {
return LHS == RHS; 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<IntrinsicInst>(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 }; enum class Reorderability { Always, IfNoAlias, Never };
/// This does one-way checks to see if Use could theoretically be hoisted above /// This does one-way checks to see if Use could theoretically be hoisted above
/// MayClobber. This will not check the other way around. /// MayClobber. This will not check the other way around.
/// ///
/// This assumes that, for the purposes of MemorySSA, Use comes directly after /// This assumes that, for the purposes of MemorySSA, Use comes directly after
/// MayClobber, with no potentially clobbering operations in between them. /// MayClobber, with no potentially clobbering operations in between them.
Show All 25 Linesstatic Reorderability getLoadReorderability(const LoadInst *Use,
bool SeqCstUse = Use->getOrdering() == AtomicOrdering::SequentiallyConsistent; bool SeqCstUse = Use->getOrdering() == AtomicOrdering::SequentiallyConsistent;
bool MayClobberIsAcquire = isAtLeastOrStrongerThan(MayClobber->getOrdering(), bool MayClobberIsAcquire = isAtLeastOrStrongerThan(MayClobber->getOrdering(),
AtomicOrdering::Acquire); AtomicOrdering::Acquire);
if (SeqCstUse || MayClobberIsAcquire) if (SeqCstUse || MayClobberIsAcquire)
return Reorderability::Never; return Reorderability::Never;
return Result; return Result;
} }
static bool isUseTriviallyOptimizableToLiveOnEntry(AliasAnalysis &AA, bool instructionClobbersQuery(MemoryDef *MD,
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<LoadInst>(I) && (I->getMetadata(LLVMContext::MD_invariant_load) ||
AA.pointsToConstantMemory(I));
}
static bool instructionClobbersQuery(MemoryDef *MD,
const MemoryLocation &UseLoc, const MemoryLocation &UseLoc,
const Instruction *UseInst, const Instruction *UseInst,
AliasAnalysis &AA) { AliasAnalysis &AA) {
Instruction *DefInst = MD->getMemoryInst(); Instruction *DefInst = MD->getMemoryInst();
assert(DefInst && "Defining instruction not actually an instruction"); assert(DefInst && "Defining instruction not actually an instruction");
if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(DefInst)) { if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(DefInst)) {
// These intrinsics will show up as affecting memory, but they are just // These intrinsics will show up as affecting memory, but they are just
// markers. // markers.
switch (II->getIntrinsicID()) { switch (II->getIntrinsicID()) {
case Intrinsic::lifetime_start: case Intrinsic::lifetime_start:
Show All 24 Lines if (auto *UseLoad = dyn_cast<LoadInst>(UseInst)) {
return !AA.isNoAlias(UseLoc, MemoryLocation::get(DefLoad)); return !AA.isNoAlias(UseLoc, MemoryLocation::get(DefLoad));
} }
} }
} }
return AA.getModRefInfo(DefInst, UseLoc) & MRI_Mod; 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<IntrinsicInst>(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<LoadInst>(I) && (I->getMetadata(LLVMContext::MD_invariant_load) ||
AA.pointsToConstantMemory(I));
}
static bool instructionClobbersQuery(MemoryDef *MD, MemoryUse *MU, static bool instructionClobbersQuery(MemoryDef *MD, MemoryUse *MU,
const MemoryLocOrCall &UseMLOC, const MemoryLocOrCall &UseMLOC,
AliasAnalysis &AA) { AliasAnalysis &AA) {
// FIXME: This is a temporary hack to allow a single instructionClobbersQuery // FIXME: This is a temporary hack to allow a single instructionClobbersQuery
// to exist while MemoryLocOrCall is pushed through places. // to exist while MemoryLocOrCall is pushed through places.
if (UseMLOC.IsCall) if (UseMLOC.IsCall)
return instructionClobbersQuery(MD, MemoryLocation(), MU->getMemoryInst(), return instructionClobbersQuery(MD, MemoryLocation(), MU->getMemoryInst(),
AA); AA);
▲ Show 20 Lines • Show All 1,922 Lines • Show Last 20 Lines

llvm/trunk/test/Transforms/GVNHoist/pr30216.ll

; 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
}

llvm/trunk/test/Transforms/GVNHoist/pr30499.ll

; 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 }