#include "llvm/Transforms/Utils/VectorUtils.h"
using namespace llvm;
-#define DEBUG_TYPE "loop-vectorize"
+#define DEBUG_TYPE "loop-accesses"
static cl::opt<unsigned, true>
VectorizationFactor("force-vector-width", cl::Hidden,
return ::VectorizationInterleave.getNumOccurrences() > 0;
}
-void VectorizationReport::emitAnalysis(VectorizationReport &Message,
- const Function *TheFunction,
- const Loop *TheLoop) {
+void LoopAccessReport::emitAnalysis(const LoopAccessReport &Message,
+ const Function *TheFunction,
+ const Loop *TheLoop,
+ const char *PassName) {
DebugLoc DL = TheLoop->getStartLoc();
- if (Instruction *I = Message.getInstr())
+ if (const Instruction *I = Message.getInstr())
DL = I->getDebugLoc();
- emitOptimizationRemarkAnalysis(TheFunction->getContext(), DEBUG_TYPE,
+ emitOptimizationRemarkAnalysis(TheFunction->getContext(), PassName,
*TheFunction, DL, Message.str());
}
const SCEV *ByOne =
SCEVParameterRewriter::rewrite(OrigSCEV, *SE, RewriteMap, true);
- DEBUG(dbgs() << "LV: Replacing SCEV: " << *OrigSCEV << " by: " << *ByOne
+ DEBUG(dbgs() << "LAA: Replacing SCEV: " << *OrigSCEV << " by: " << *ByOne
<< "\n");
return ByOne;
}
return true;
}
+void LoopAccessInfo::RuntimePointerCheck::print(raw_ostream &OS,
+ unsigned Depth) const {
+ unsigned NumPointers = Pointers.size();
+ if (NumPointers == 0)
+ return;
+
+ OS.indent(Depth) << "Run-time memory checks:\n";
+ unsigned N = 0;
+ for (unsigned I = 0; I < NumPointers; ++I)
+ for (unsigned J = I + 1; J < NumPointers; ++J)
+ if (needsChecking(I, J)) {
+ OS.indent(Depth) << N++ << ":\n";
+ OS.indent(Depth + 2) << *Pointers[I] << "\n";
+ OS.indent(Depth + 2) << *Pointers[J] << "\n";
+ }
+}
+
namespace {
/// \brief Analyses memory accesses in a loop.
///
RtCheck.insert(SE, TheLoop, Ptr, IsWrite, DepId, ASId, StridesMap);
- DEBUG(dbgs() << "LV: Found a runtime check ptr:" << *Ptr << '\n');
+ DEBUG(dbgs() << "LAA: Found a runtime check ptr:" << *Ptr << '\n');
} else {
CanDoRT = false;
}
unsigned ASi = PtrI->getType()->getPointerAddressSpace();
unsigned ASj = PtrJ->getType()->getPointerAddressSpace();
if (ASi != ASj) {
- DEBUG(dbgs() << "LV: Runtime check would require comparison between"
+ DEBUG(dbgs() << "LAA: Runtime check would require comparison between"
" different address spaces\n");
return false;
}
// process read-only pointers. This allows us to skip dependence tests for
// read-only pointers.
- DEBUG(dbgs() << "LV: Processing memory accesses...\n");
+ DEBUG(dbgs() << "LAA: Processing memory accesses...\n");
DEBUG(dbgs() << " AST: "; AST.dump());
- DEBUG(dbgs() << "LV: Accesses:\n");
+ DEBUG(dbgs() << "LAA: Accesses:\n");
DEBUG({
for (auto A : Accesses)
dbgs() << "\t" << *A.getPointer() << " (" <<
// Make sure that the pointer does not point to aggregate types.
const PointerType *PtrTy = cast<PointerType>(Ty);
if (PtrTy->getElementType()->isAggregateType()) {
- DEBUG(dbgs() << "LV: Bad stride - Not a pointer to a scalar type" << *Ptr <<
- "\n");
+ DEBUG(dbgs() << "LAA: Bad stride - Not a pointer to a scalar type"
+ << *Ptr << "\n");
return 0;
}
const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(PtrScev);
if (!AR) {
- DEBUG(dbgs() << "LV: Bad stride - Not an AddRecExpr pointer "
+ DEBUG(dbgs() << "LAA: Bad stride - Not an AddRecExpr pointer "
<< *Ptr << " SCEV: " << *PtrScev << "\n");
return 0;
}
// The accesss function must stride over the innermost loop.
if (Lp != AR->getLoop()) {
- DEBUG(dbgs() << "LV: Bad stride - Not striding over innermost loop " <<
+ DEBUG(dbgs() << "LAA: Bad stride - Not striding over innermost loop " <<
*Ptr << " SCEV: " << *PtrScev << "\n");
}
bool IsNoWrapAddRec = AR->getNoWrapFlags(SCEV::NoWrapMask);
bool IsInAddressSpaceZero = PtrTy->getAddressSpace() == 0;
if (!IsNoWrapAddRec && !IsInBoundsGEP && !IsInAddressSpaceZero) {
- DEBUG(dbgs() << "LV: Bad stride - Pointer may wrap in the address space "
+ DEBUG(dbgs() << "LAA: Bad stride - Pointer may wrap in the address space "
<< *Ptr << " SCEV: " << *PtrScev << "\n");
return 0;
}
// Calculate the pointer stride and check if it is consecutive.
const SCEVConstant *C = dyn_cast<SCEVConstant>(Step);
if (!C) {
- DEBUG(dbgs() << "LV: Bad stride - Not a constant strided " << *Ptr <<
+ DEBUG(dbgs() << "LAA: Bad stride - Not a constant strided " << *Ptr <<
" SCEV: " << *PtrScev << "\n");
return 0;
}
}
if (MaxVFWithoutSLForwardIssues< 2*TypeByteSize) {
- DEBUG(dbgs() << "LV: Distance " << Distance <<
+ DEBUG(dbgs() << "LAA: Distance " << Distance <<
" that could cause a store-load forwarding conflict\n");
return true;
}
const SCEV *Dist = SE->getMinusSCEV(Sink, Src);
- DEBUG(dbgs() << "LV: Src Scev: " << *Src << "Sink Scev: " << *Sink
+ DEBUG(dbgs() << "LAA: Src Scev: " << *Src << "Sink Scev: " << *Sink
<< "(Induction step: " << StrideAPtr << ")\n");
- DEBUG(dbgs() << "LV: Distance for " << *InstMap[AIdx] << " to "
+ DEBUG(dbgs() << "LAA: Distance for " << *InstMap[AIdx] << " to "
<< *InstMap[BIdx] << ": " << *Dist << "\n");
// Need consecutive accesses. We don't want to vectorize
const SCEVConstant *C = dyn_cast<SCEVConstant>(Dist);
if (!C) {
- DEBUG(dbgs() << "LV: Dependence because of non-constant distance\n");
+ DEBUG(dbgs() << "LAA: Dependence because of non-constant distance\n");
ShouldRetryWithRuntimeCheck = true;
return true;
}
ATy != BTy))
return true;
- DEBUG(dbgs() << "LV: Dependence is negative: NoDep\n");
+ DEBUG(dbgs() << "LAA: Dependence is negative: NoDep\n");
return false;
}
if (Val == 0) {
if (ATy == BTy)
return false;
- DEBUG(dbgs() << "LV: Zero dependence difference but different types\n");
+ DEBUG(dbgs() << "LAA: Zero dependence difference but different types\n");
return true;
}
// Positive distance bigger than max vectorization factor.
if (ATy != BTy) {
DEBUG(dbgs() <<
- "LV: ReadWrite-Write positive dependency with different types\n");
+ "LAA: ReadWrite-Write positive dependency with different types\n");
return false;
}
if (Distance < 2*TypeByteSize ||
2*TypeByteSize > MaxSafeDepDistBytes ||
Distance < TypeByteSize * ForcedUnroll * ForcedFactor) {
- DEBUG(dbgs() << "LV: Failure because of Positive distance "
+ DEBUG(dbgs() << "LAA: Failure because of Positive distance "
<< Val.getSExtValue() << '\n');
return true;
}
couldPreventStoreLoadForward(Distance, TypeByteSize))
return true;
- DEBUG(dbgs() << "LV: Positive distance " << Val.getSExtValue() <<
+ DEBUG(dbgs() << "LAA: Positive distance " << Val.getSExtValue() <<
" with max VF = " << MaxSafeDepDistBytes / TypeByteSize << '\n');
return false;
return true;
}
+bool LoopAccessInfo::canAnalyzeLoop() {
+ // We can only analyze innermost loops.
+ if (!TheLoop->empty()) {
+ emitAnalysis(LoopAccessReport() << "loop is not the innermost loop");
+ return false;
+ }
+
+ // We must have a single backedge.
+ if (TheLoop->getNumBackEdges() != 1) {
+ emitAnalysis(
+ LoopAccessReport() <<
+ "loop control flow is not understood by analyzer");
+ return false;
+ }
+
+ // We must have a single exiting block.
+ if (!TheLoop->getExitingBlock()) {
+ emitAnalysis(
+ LoopAccessReport() <<
+ "loop control flow is not understood by analyzer");
+ return false;
+ }
+
+ // We only handle bottom-tested loops, i.e. loop in which the condition is
+ // checked at the end of each iteration. With that we can assume that all
+ // instructions in the loop are executed the same number of times.
+ if (TheLoop->getExitingBlock() != TheLoop->getLoopLatch()) {
+ emitAnalysis(
+ LoopAccessReport() <<
+ "loop control flow is not understood by analyzer");
+ return false;
+ }
+
+ // We need to have a loop header.
+ DEBUG(dbgs() << "LAA: Found a loop: " <<
+ TheLoop->getHeader()->getName() << '\n');
+
+ // ScalarEvolution needs to be able to find the exit count.
+ const SCEV *ExitCount = SE->getBackedgeTakenCount(TheLoop);
+ if (ExitCount == SE->getCouldNotCompute()) {
+ emitAnalysis(LoopAccessReport() <<
+ "could not determine number of loop iterations");
+ DEBUG(dbgs() << "LAA: SCEV could not compute the loop exit count.\n");
+ return false;
+ }
+
+ return true;
+}
+
void LoopAccessInfo::analyzeLoop(ValueToValueMap &Strides) {
typedef SmallVector<Value*, 16> ValueVector;
LoadInst *Ld = dyn_cast<LoadInst>(it);
if (!Ld || (!Ld->isSimple() && !IsAnnotatedParallel)) {
- emitAnalysis(VectorizationReport(Ld)
+ emitAnalysis(LoopAccessReport(Ld)
<< "read with atomic ordering or volatile read");
- DEBUG(dbgs() << "LV: Found a non-simple load.\n");
+ DEBUG(dbgs() << "LAA: Found a non-simple load.\n");
CanVecMem = false;
return;
}
if (it->mayWriteToMemory()) {
StoreInst *St = dyn_cast<StoreInst>(it);
if (!St) {
- emitAnalysis(VectorizationReport(it) <<
+ emitAnalysis(LoopAccessReport(it) <<
"instruction cannot be vectorized");
CanVecMem = false;
return;
}
if (!St->isSimple() && !IsAnnotatedParallel) {
- emitAnalysis(VectorizationReport(St)
+ emitAnalysis(LoopAccessReport(St)
<< "write with atomic ordering or volatile write");
- DEBUG(dbgs() << "LV: Found a non-simple store.\n");
+ DEBUG(dbgs() << "LAA: Found a non-simple store.\n");
CanVecMem = false;
return;
}
// Check if we see any stores. If there are no stores, then we don't
// care if the pointers are *restrict*.
if (!Stores.size()) {
- DEBUG(dbgs() << "LV: Found a read-only loop!\n");
+ DEBUG(dbgs() << "LAA: Found a read-only loop!\n");
CanVecMem = true;
return;
}
if (isUniform(Ptr)) {
emitAnalysis(
- VectorizationReport(ST)
+ LoopAccessReport(ST)
<< "write to a loop invariant address could not be vectorized");
- DEBUG(dbgs() << "LV: We don't allow storing to uniform addresses\n");
+ DEBUG(dbgs() << "LAA: We don't allow storing to uniform addresses\n");
CanVecMem = false;
return;
}
if (IsAnnotatedParallel) {
DEBUG(dbgs()
- << "LV: A loop annotated parallel, ignore memory dependency "
+ << "LAA: A loop annotated parallel, ignore memory dependency "
<< "checks.\n");
CanVecMem = true;
return;
// If we write (or read-write) to a single destination and there are no
// other reads in this loop then is it safe to vectorize.
if (NumReadWrites == 1 && NumReads == 0) {
- DEBUG(dbgs() << "LV: Found a write-only loop!\n");
+ DEBUG(dbgs() << "LAA: Found a write-only loop!\n");
CanVecMem = true;
return;
}
CanDoRT = Accesses.canCheckPtrAtRT(PtrRtCheck, NumComparisons, SE, TheLoop,
Strides);
- DEBUG(dbgs() << "LV: We need to do " << NumComparisons <<
+ DEBUG(dbgs() << "LAA: We need to do " << NumComparisons <<
" pointer comparisons.\n");
// If we only have one set of dependences to check pointers among we don't
}
if (CanDoRT) {
- DEBUG(dbgs() << "LV: We can perform a memory runtime check if needed.\n");
+ DEBUG(dbgs() << "LAA: We can perform a memory runtime check if needed.\n");
}
if (NeedRTCheck && !CanDoRT) {
- emitAnalysis(VectorizationReport() << "cannot identify array bounds");
- DEBUG(dbgs() << "LV: We can't vectorize because we can't find " <<
+ emitAnalysis(LoopAccessReport() << "cannot identify array bounds");
+ DEBUG(dbgs() << "LAA: We can't vectorize because we can't find " <<
"the array bounds.\n");
PtrRtCheck.reset();
CanVecMem = false;
CanVecMem = true;
if (Accesses.isDependencyCheckNeeded()) {
- DEBUG(dbgs() << "LV: Checking memory dependencies\n");
+ DEBUG(dbgs() << "LAA: Checking memory dependencies\n");
CanVecMem = DepChecker.areDepsSafe(
DependentAccesses, Accesses.getDependenciesToCheck(), Strides);
MaxSafeDepDistBytes = DepChecker.getMaxSafeDepDistBytes();
if (!CanVecMem && DepChecker.shouldRetryWithRuntimeCheck()) {
- DEBUG(dbgs() << "LV: Retrying with memory checks\n");
+ DEBUG(dbgs() << "LAA: Retrying with memory checks\n");
NeedRTCheck = true;
// Clear the dependency checks. We assume they are not needed.
if (!CanDoRT ||
NumComparisons > VectorizerParams::RuntimeMemoryCheckThreshold) {
if (!CanDoRT && NumComparisons > 0)
- emitAnalysis(VectorizationReport()
+ emitAnalysis(LoopAccessReport()
<< "cannot check memory dependencies at runtime");
else
- emitAnalysis(VectorizationReport()
+ emitAnalysis(LoopAccessReport()
<< NumComparisons << " exceeds limit of "
<< VectorizerParams::RuntimeMemoryCheckThreshold
<< " dependent memory operations checked at runtime");
- DEBUG(dbgs() << "LV: Can't vectorize with memory checks\n");
+ DEBUG(dbgs() << "LAA: Can't vectorize with memory checks\n");
PtrRtCheck.reset();
CanVecMem = false;
return;
}
if (!CanVecMem)
- emitAnalysis(VectorizationReport() <<
+ emitAnalysis(LoopAccessReport() <<
"unsafe dependent memory operations in loop");
- DEBUG(dbgs() << "LV: We" << (NeedRTCheck ? "" : " don't") <<
+ DEBUG(dbgs() << "LAA: We" << (NeedRTCheck ? "" : " don't") <<
" need a runtime memory check.\n");
}
return !DT->dominates(BB, Latch);
}
-void LoopAccessInfo::emitAnalysis(VectorizationReport &Message) {
+void LoopAccessInfo::emitAnalysis(LoopAccessReport &Message) {
assert(!Report && "Multiple reports generated");
Report = Message;
}
const SCEV *Sc = SE->getSCEV(Ptr);
if (SE->isLoopInvariant(Sc, TheLoop)) {
- DEBUG(dbgs() << "LV: Adding RT check for a loop invariant ptr:" <<
+ DEBUG(dbgs() << "LAA: Adding RT check for a loop invariant ptr:" <<
*Ptr <<"\n");
Starts.push_back(Ptr);
Ends.push_back(Ptr);
} else {
- DEBUG(dbgs() << "LV: Adding RT check for range:" << *Ptr << '\n');
+ DEBUG(dbgs() << "LAA: Adding RT check for range:" << *Ptr << '\n');
unsigned AS = Ptr->getType()->getPointerAddressSpace();
// Use this type for pointer arithmetic.
FirstInst = getFirstInst(FirstInst, Check, Loc);
return std::make_pair(FirstInst, Check);
}
+
+LoopAccessInfo::LoopAccessInfo(Loop *L, ScalarEvolution *SE,
+ const DataLayout *DL,
+ const TargetLibraryInfo *TLI, AliasAnalysis *AA,
+ DominatorTree *DT, ValueToValueMap &Strides)
+ : TheLoop(L), SE(SE), DL(DL), TLI(TLI), AA(AA), DT(DT), NumLoads(0),
+ NumStores(0), MaxSafeDepDistBytes(-1U), CanVecMem(false) {
+ if (canAnalyzeLoop())
+ analyzeLoop(Strides);
+}
+
+void LoopAccessInfo::print(raw_ostream &OS, unsigned Depth) const {
+ if (CanVecMem) {
+ if (PtrRtCheck.empty())
+ OS.indent(Depth) << "Memory dependences are safe\n";
+ else
+ OS.indent(Depth) << "Memory dependences are safe with run-time checks\n";
+ }
+
+ if (Report)
+ OS.indent(Depth) << "Report: " << Report->str() << "\n";
+
+ // FIXME: Print unsafe dependences
+
+ // List the pair of accesses need run-time checks to prove independence.
+ PtrRtCheck.print(OS, Depth);
+ OS << "\n";
+}
+
+LoopAccessInfo &LoopAccessAnalysis::getInfo(Loop *L, ValueToValueMap &Strides) {
+ auto &LAI = LoopAccessInfoMap[L];
+
+#ifndef NDEBUG
+ assert((!LAI || LAI->NumSymbolicStrides == Strides.size()) &&
+ "Symbolic strides changed for loop");
+#endif
+
+ if (!LAI) {
+ LAI = llvm::make_unique<LoopAccessInfo>(L, SE, DL, TLI, AA, DT, Strides);
+#ifndef NDEBUG
+ LAI->NumSymbolicStrides = Strides.size();
+#endif
+ }
+ return *LAI.get();
+}
+
+void LoopAccessAnalysis::print(raw_ostream &OS, const Module *M) const {
+ LoopAccessAnalysis &LAA = *const_cast<LoopAccessAnalysis *>(this);
+
+ LoopInfo *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
+ ValueToValueMap NoSymbolicStrides;
+
+ for (Loop *TopLevelLoop : *LI)
+ for (Loop *L : depth_first(TopLevelLoop)) {
+ OS.indent(2) << L->getHeader()->getName() << ":\n";
+ auto &LAI = LAA.getInfo(L, NoSymbolicStrides);
+ LAI.print(OS, 4);
+ }
+}
+
+bool LoopAccessAnalysis::runOnFunction(Function &F) {
+ SE = &getAnalysis<ScalarEvolution>();
+ DL = F.getParent()->getDataLayout();
+ auto *TLIP = getAnalysisIfAvailable<TargetLibraryInfoWrapperPass>();
+ TLI = TLIP ? &TLIP->getTLI() : nullptr;
+ AA = &getAnalysis<AliasAnalysis>();
+ DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
+
+ return false;
+}
+
+void LoopAccessAnalysis::getAnalysisUsage(AnalysisUsage &AU) const {
+ AU.addRequired<ScalarEvolution>();
+ AU.addRequired<AliasAnalysis>();
+ AU.addRequired<DominatorTreeWrapperPass>();
+ AU.addRequired<LoopInfoWrapperPass>();
+
+ AU.setPreservesAll();
+}
+
+char LoopAccessAnalysis::ID = 0;
+static const char laa_name[] = "Loop Access Analysis";
+#define LAA_NAME "loop-accesses"
+
+INITIALIZE_PASS_BEGIN(LoopAccessAnalysis, LAA_NAME, laa_name, false, true)
+INITIALIZE_AG_DEPENDENCY(AliasAnalysis)
+INITIALIZE_PASS_DEPENDENCY(ScalarEvolution)
+INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
+INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
+INITIALIZE_PASS_END(LoopAccessAnalysis, LAA_NAME, laa_name, false, true)
+
+namespace llvm {
+ Pass *createLAAPass() {
+ return new LoopAccessAnalysis();
+ }
+}
projects / oota-llvm.git / blobdiff