summaryrefslogtreecommitdiffstats
path: root/contrib/llvm/lib/Analysis/LoopAccessAnalysis.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'contrib/llvm/lib/Analysis/LoopAccessAnalysis.cpp')
-rw-r--r--contrib/llvm/lib/Analysis/LoopAccessAnalysis.cpp216
1 files changed, 132 insertions, 84 deletions
diff --git a/contrib/llvm/lib/Analysis/LoopAccessAnalysis.cpp b/contrib/llvm/lib/Analysis/LoopAccessAnalysis.cpp
index 5214eb7..bf80072 100644
--- a/contrib/llvm/lib/Analysis/LoopAccessAnalysis.cpp
+++ b/contrib/llvm/lib/Analysis/LoopAccessAnalysis.cpp
@@ -13,18 +13,60 @@
//===----------------------------------------------------------------------===//
#include "llvm/Analysis/LoopAccessAnalysis.h"
+#include "llvm/ADT/APInt.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/DepthFirstIterator.h"
+#include "llvm/ADT/EquivalenceClasses.h"
+#include "llvm/ADT/PointerIntPair.h"
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/SetVector.h"
+#include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/ADT/SmallSet.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/ADT/iterator_range.h"
+#include "llvm/Analysis/AliasAnalysis.h"
+#include "llvm/Analysis/AliasSetTracker.h"
+#include "llvm/Analysis/LoopAnalysisManager.h"
#include "llvm/Analysis/LoopInfo.h"
-#include "llvm/Analysis/LoopPassManager.h"
+#include "llvm/Analysis/MemoryLocation.h"
+#include "llvm/Analysis/OptimizationDiagnosticInfo.h"
+#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Analysis/ScalarEvolutionExpander.h"
+#include "llvm/Analysis/ScalarEvolutionExpressions.h"
#include "llvm/Analysis/TargetLibraryInfo.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/Analysis/VectorUtils.h"
+#include "llvm/IR/BasicBlock.h"
+#include "llvm/IR/Constants.h"
+#include "llvm/IR/DataLayout.h"
+#include "llvm/IR/DebugLoc.h"
+#include "llvm/IR/DerivedTypes.h"
#include "llvm/IR/DiagnosticInfo.h"
#include "llvm/IR/Dominators.h"
+#include "llvm/IR/Function.h"
#include "llvm/IR/IRBuilder.h"
+#include "llvm/IR/InstrTypes.h"
+#include "llvm/IR/Instruction.h"
+#include "llvm/IR/Instructions.h"
+#include "llvm/IR/Operator.h"
#include "llvm/IR/PassManager.h"
+#include "llvm/IR/Type.h"
+#include "llvm/IR/Value.h"
+#include "llvm/IR/ValueHandle.h"
+#include "llvm/Pass.h"
+#include "llvm/Support/Casting.h"
+#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
+#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/raw_ostream.h"
+#include <algorithm>
+#include <cassert>
+#include <cstdint>
+#include <cstdlib>
+#include <iterator>
+#include <utility>
+#include <vector>
+
using namespace llvm;
#define DEBUG_TYPE "loop-accesses"
@@ -94,14 +136,18 @@ bool VectorizerParams::isInterleaveForced() {
}
void LoopAccessReport::emitAnalysis(const LoopAccessReport &Message,
- const Function *TheFunction,
- const Loop *TheLoop,
- const char *PassName) {
+ const Loop *TheLoop, const char *PassName,
+ OptimizationRemarkEmitter &ORE) {
DebugLoc DL = TheLoop->getStartLoc();
- if (const Instruction *I = Message.getInstr())
- DL = I->getDebugLoc();
- emitOptimizationRemarkAnalysis(TheFunction->getContext(), PassName,
- *TheFunction, DL, Message.str());
+ const Value *V = TheLoop->getHeader();
+ if (const Instruction *I = Message.getInstr()) {
+ // If there is no debug location attached to the instruction, revert back to
+ // using the loop's.
+ if (I->getDebugLoc())
+ DL = I->getDebugLoc();
+ V = I->getParent();
+ }
+ ORE.emitOptimizationRemarkAnalysis(PassName, DL, V, Message.str());
}
Value *llvm::stripIntegerCast(Value *V) {
@@ -463,6 +509,7 @@ void RuntimePointerChecking::print(raw_ostream &OS, unsigned Depth) const {
}
namespace {
+
/// \brief Analyses memory accesses in a loop.
///
/// Checks whether run time pointer checks are needed and builds sets for data
@@ -886,7 +933,7 @@ static bool isNoWrapAddRec(Value *Ptr, const SCEVAddRecExpr *AR,
/// \brief Check whether the access through \p Ptr has a constant stride.
int64_t llvm::getPtrStride(PredicatedScalarEvolution &PSE, Value *Ptr,
const Loop *Lp, const ValueToValueMap &StridesMap,
- bool Assume) {
+ bool Assume, bool ShouldCheckWrap) {
Type *Ty = Ptr->getType();
assert(Ty->isPointerTy() && "Unexpected non-ptr");
@@ -925,9 +972,9 @@ int64_t llvm::getPtrStride(PredicatedScalarEvolution &PSE, Value *Ptr,
// to access the pointer value "0" which is undefined behavior in address
// space 0, therefore we can also vectorize this case.
bool IsInBoundsGEP = isInBoundsGep(Ptr);
- bool IsNoWrapAddRec =
- PSE.hasNoOverflow(Ptr, SCEVWrapPredicate::IncrementNUSW) ||
- isNoWrapAddRec(Ptr, AR, PSE, Lp);
+ bool IsNoWrapAddRec = !ShouldCheckWrap ||
+ PSE.hasNoOverflow(Ptr, SCEVWrapPredicate::IncrementNUSW) ||
+ isNoWrapAddRec(Ptr, AR, PSE, Lp);
bool IsInAddressSpaceZero = PtrTy->getAddressSpace() == 0;
if (!IsNoWrapAddRec && !IsInBoundsGEP && !IsInAddressSpaceZero) {
if (Assume) {
@@ -1028,8 +1075,8 @@ bool llvm::isConsecutiveAccess(Value *A, Value *B, const DataLayout &DL,
return false;
// Make sure that A and B have the same type if required.
- if(CheckType && PtrA->getType() != PtrB->getType())
- return false;
+ if (CheckType && PtrA->getType() != PtrB->getType())
+ return false;
unsigned PtrBitWidth = DL.getPointerSizeInBits(ASA);
Type *Ty = cast<PointerType>(PtrA->getType())->getElementType();
@@ -1451,7 +1498,7 @@ MemoryDepChecker::getInstructionsForAccess(Value *Ptr, bool isWrite) const {
auto &IndexVector = Accesses.find(Access)->second;
SmallVector<Instruction *, 4> Insts;
- std::transform(IndexVector.begin(), IndexVector.end(),
+ transform(IndexVector,
std::back_inserter(Insts),
[&](unsigned Idx) { return this->InstMap[Idx]; });
return Insts;
@@ -1478,25 +1525,23 @@ bool LoopAccessInfo::canAnalyzeLoop() {
// We can only analyze innermost loops.
if (!TheLoop->empty()) {
DEBUG(dbgs() << "LAA: loop is not the innermost loop\n");
- emitAnalysis(LoopAccessReport() << "loop is not the innermost loop");
+ recordAnalysis("NotInnerMostLoop") << "loop is not the innermost loop";
return false;
}
// We must have a single backedge.
if (TheLoop->getNumBackEdges() != 1) {
DEBUG(dbgs() << "LAA: loop control flow is not understood by analyzer\n");
- emitAnalysis(
- LoopAccessReport() <<
- "loop control flow is not understood by analyzer");
+ recordAnalysis("CFGNotUnderstood")
+ << "loop control flow is not understood by analyzer";
return false;
}
// We must have a single exiting block.
if (!TheLoop->getExitingBlock()) {
DEBUG(dbgs() << "LAA: loop control flow is not understood by analyzer\n");
- emitAnalysis(
- LoopAccessReport() <<
- "loop control flow is not understood by analyzer");
+ recordAnalysis("CFGNotUnderstood")
+ << "loop control flow is not understood by analyzer";
return false;
}
@@ -1505,17 +1550,16 @@ bool LoopAccessInfo::canAnalyzeLoop() {
// instructions in the loop are executed the same number of times.
if (TheLoop->getExitingBlock() != TheLoop->getLoopLatch()) {
DEBUG(dbgs() << "LAA: loop control flow is not understood by analyzer\n");
- emitAnalysis(
- LoopAccessReport() <<
- "loop control flow is not understood by analyzer");
+ recordAnalysis("CFGNotUnderstood")
+ << "loop control flow is not understood by analyzer";
return false;
}
// ScalarEvolution needs to be able to find the exit count.
const SCEV *ExitCount = PSE->getBackedgeTakenCount();
if (ExitCount == PSE->getSE()->getCouldNotCompute()) {
- emitAnalysis(LoopAccessReport()
- << "could not determine number of loop iterations");
+ recordAnalysis("CantComputeNumberOfIterations")
+ << "could not determine number of loop iterations";
DEBUG(dbgs() << "LAA: SCEV could not compute the loop exit count.\n");
return false;
}
@@ -1564,8 +1608,8 @@ void LoopAccessInfo::analyzeLoop(AliasAnalysis *AA, LoopInfo *LI,
auto *Ld = dyn_cast<LoadInst>(&I);
if (!Ld || (!Ld->isSimple() && !IsAnnotatedParallel)) {
- emitAnalysis(LoopAccessReport(Ld)
- << "read with atomic ordering or volatile read");
+ recordAnalysis("NonSimpleLoad", Ld)
+ << "read with atomic ordering or volatile read";
DEBUG(dbgs() << "LAA: Found a non-simple load.\n");
CanVecMem = false;
return;
@@ -1582,14 +1626,14 @@ void LoopAccessInfo::analyzeLoop(AliasAnalysis *AA, LoopInfo *LI,
if (I.mayWriteToMemory()) {
auto *St = dyn_cast<StoreInst>(&I);
if (!St) {
- emitAnalysis(LoopAccessReport(St)
- << "instruction cannot be vectorized");
+ recordAnalysis("CantVectorizeInstruction", St)
+ << "instruction cannot be vectorized";
CanVecMem = false;
return;
}
if (!St->isSimple() && !IsAnnotatedParallel) {
- emitAnalysis(LoopAccessReport(St)
- << "write with atomic ordering or volatile write");
+ recordAnalysis("NonSimpleStore", St)
+ << "write with atomic ordering or volatile write";
DEBUG(dbgs() << "LAA: Found a non-simple store.\n");
CanVecMem = false;
return;
@@ -1697,7 +1741,7 @@ void LoopAccessInfo::analyzeLoop(AliasAnalysis *AA, LoopInfo *LI,
bool CanDoRTIfNeeded = Accesses.canCheckPtrAtRT(*PtrRtChecking, PSE->getSE(),
TheLoop, SymbolicStrides);
if (!CanDoRTIfNeeded) {
- emitAnalysis(LoopAccessReport() << "cannot identify array bounds");
+ recordAnalysis("CantIdentifyArrayBounds") << "cannot identify array bounds";
DEBUG(dbgs() << "LAA: We can't vectorize because we can't find "
<< "the array bounds.\n");
CanVecMem = false;
@@ -1728,8 +1772,8 @@ void LoopAccessInfo::analyzeLoop(AliasAnalysis *AA, LoopInfo *LI,
// Check that we found the bounds for the pointer.
if (!CanDoRTIfNeeded) {
- emitAnalysis(LoopAccessReport()
- << "cannot check memory dependencies at runtime");
+ recordAnalysis("CantCheckMemDepsAtRunTime")
+ << "cannot check memory dependencies at runtime";
DEBUG(dbgs() << "LAA: Can't vectorize with memory checks\n");
CanVecMem = false;
return;
@@ -1744,12 +1788,11 @@ void LoopAccessInfo::analyzeLoop(AliasAnalysis *AA, LoopInfo *LI,
<< (PtrRtChecking->Need ? "" : " don't")
<< " need runtime memory checks.\n");
else {
- emitAnalysis(
- LoopAccessReport()
+ recordAnalysis("UnsafeMemDep")
<< "unsafe dependent memory operations in loop. Use "
"#pragma loop distribute(enable) to allow loop distribution "
"to attempt to isolate the offending operations into a separate "
- "loop");
+ "loop";
DEBUG(dbgs() << "LAA: unsafe dependent memory operations in loop\n");
}
}
@@ -1763,13 +1806,35 @@ bool LoopAccessInfo::blockNeedsPredication(BasicBlock *BB, Loop *TheLoop,
return !DT->dominates(BB, Latch);
}
-void LoopAccessInfo::emitAnalysis(LoopAccessReport &Message) {
+OptimizationRemarkAnalysis &LoopAccessInfo::recordAnalysis(StringRef RemarkName,
+ Instruction *I) {
assert(!Report && "Multiple reports generated");
- Report = Message;
+
+ Value *CodeRegion = TheLoop->getHeader();
+ DebugLoc DL = TheLoop->getStartLoc();
+
+ if (I) {
+ CodeRegion = I->getParent();
+ // If there is no debug location attached to the instruction, revert back to
+ // using the loop's.
+ if (I->getDebugLoc())
+ DL = I->getDebugLoc();
+ }
+
+ Report = make_unique<OptimizationRemarkAnalysis>(DEBUG_TYPE, RemarkName, DL,
+ CodeRegion);
+ return *Report;
}
bool LoopAccessInfo::isUniform(Value *V) const {
- return (PSE->getSE()->isLoopInvariant(PSE->getSE()->getSCEV(V), TheLoop));
+ auto *SE = PSE->getSE();
+ // Since we rely on SCEV for uniformity, if the type is not SCEVable, it is
+ // never considered uniform.
+ // TODO: Is this really what we want? Even without FP SCEV, we may want some
+ // trivially loop-invariant FP values to be considered uniform.
+ if (!SE->isSCEVable(V->getType()))
+ return false;
+ return (SE->isLoopInvariant(SE->getSCEV(V), TheLoop));
}
// FIXME: this function is currently a duplicate of the one in
@@ -1784,6 +1849,7 @@ static Instruction *getFirstInst(Instruction *FirstInst, Value *V,
}
namespace {
+
/// \brief IR Values for the lower and upper bounds of a pointer evolution. We
/// need to use value-handles because SCEV expansion can invalidate previously
/// expanded values. Thus expansion of a pointer can invalidate the bounds for
@@ -1792,6 +1858,7 @@ struct PointerBounds {
TrackingVH<Value> Start;
TrackingVH<Value> End;
};
+
} // end anonymous namespace
/// \brief Expand code for the lower and upper bound of the pointer group \p CG
@@ -1803,18 +1870,24 @@ expandBounds(const RuntimePointerChecking::CheckingPtrGroup *CG, Loop *TheLoop,
Value *Ptr = PtrRtChecking.Pointers[CG->Members[0]].PointerValue;
const SCEV *Sc = SE->getSCEV(Ptr);
+ unsigned AS = Ptr->getType()->getPointerAddressSpace();
+ LLVMContext &Ctx = Loc->getContext();
+
+ // Use this type for pointer arithmetic.
+ Type *PtrArithTy = Type::getInt8PtrTy(Ctx, AS);
+
if (SE->isLoopInvariant(Sc, TheLoop)) {
DEBUG(dbgs() << "LAA: Adding RT check for a loop invariant ptr:" << *Ptr
<< "\n");
- return {Ptr, Ptr};
+ // Ptr could be in the loop body. If so, expand a new one at the correct
+ // location.
+ Instruction *Inst = dyn_cast<Instruction>(Ptr);
+ Value *NewPtr = (Inst && TheLoop->contains(Inst))
+ ? Exp.expandCodeFor(Sc, PtrArithTy, Loc)
+ : Ptr;
+ return {NewPtr, NewPtr};
} else {
- unsigned AS = Ptr->getType()->getPointerAddressSpace();
- LLVMContext &Ctx = Loc->getContext();
-
- // Use this type for pointer arithmetic.
- Type *PtrArithTy = Type::getInt8PtrTy(Ctx, AS);
Value *Start = nullptr, *End = nullptr;
-
DEBUG(dbgs() << "LAA: Adding RT check for range:\n");
Start = Exp.expandCodeFor(CG->Low, PtrArithTy, Loc);
End = Exp.expandCodeFor(CG->High, PtrArithTy, Loc);
@@ -1833,9 +1906,8 @@ static SmallVector<std::pair<PointerBounds, PointerBounds>, 4> expandBounds(
// Here we're relying on the SCEV Expander's cache to only emit code for the
// same bounds once.
- std::transform(
- PointerChecks.begin(), PointerChecks.end(),
- std::back_inserter(ChecksWithBounds),
+ transform(
+ PointerChecks, std::back_inserter(ChecksWithBounds),
[&](const RuntimePointerChecking::PointerCheck &Check) {
PointerBounds
First = expandBounds(Check.first, L, Loc, Exp, SE, PtrRtChecking),
@@ -1967,7 +2039,7 @@ void LoopAccessInfo::print(raw_ostream &OS, unsigned Depth) const {
}
if (Report)
- OS.indent(Depth) << "Report: " << Report->str() << "\n";
+ OS.indent(Depth) << "Report: " << Report->getMsg() << "\n";
if (auto *Dependences = DepChecker->getDependences()) {
OS.indent(Depth) << "Dependences:\n";
@@ -2046,41 +2118,17 @@ INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
INITIALIZE_PASS_END(LoopAccessLegacyAnalysis, LAA_NAME, laa_name, false, true)
-char LoopAccessAnalysis::PassID;
-
-LoopAccessInfo LoopAccessAnalysis::run(Loop &L, AnalysisManager<Loop> &AM) {
- const AnalysisManager<Function> &FAM =
- AM.getResult<FunctionAnalysisManagerLoopProxy>(L).getManager();
- Function &F = *L.getHeader()->getParent();
- auto *SE = FAM.getCachedResult<ScalarEvolutionAnalysis>(F);
- auto *TLI = FAM.getCachedResult<TargetLibraryAnalysis>(F);
- auto *AA = FAM.getCachedResult<AAManager>(F);
- auto *DT = FAM.getCachedResult<DominatorTreeAnalysis>(F);
- auto *LI = FAM.getCachedResult<LoopAnalysis>(F);
- if (!SE)
- report_fatal_error(
- "ScalarEvolution must have been cached at a higher level");
- if (!AA)
- report_fatal_error("AliasAnalysis must have been cached at a higher level");
- if (!DT)
- report_fatal_error("DominatorTree must have been cached at a higher level");
- if (!LI)
- report_fatal_error("LoopInfo must have been cached at a higher level");
- return LoopAccessInfo(&L, SE, TLI, AA, DT, LI);
-}
+AnalysisKey LoopAccessAnalysis::Key;
-PreservedAnalyses LoopAccessInfoPrinterPass::run(Loop &L,
- AnalysisManager<Loop> &AM) {
- Function &F = *L.getHeader()->getParent();
- auto &LAI = AM.getResult<LoopAccessAnalysis>(L);
- OS << "Loop access info in function '" << F.getName() << "':\n";
- OS.indent(2) << L.getHeader()->getName() << ":\n";
- LAI.print(OS, 4);
- return PreservedAnalyses::all();
+LoopAccessInfo LoopAccessAnalysis::run(Loop &L, LoopAnalysisManager &AM,
+ LoopStandardAnalysisResults &AR) {
+ return LoopAccessInfo(&L, &AR.SE, &AR.TLI, &AR.AA, &AR.DT, &AR.LI);
}
namespace llvm {
+
Pass *createLAAPass() {
return new LoopAccessLegacyAnalysis();
}
-}
+
+} // end namespace llvm
OpenPOWER on IntegriCloud