#include "llvm/Analysis/LoopAccessAnalysis.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/ScalarEvolutionExpander.h"
+#include "llvm/Analysis/TargetLibraryInfo.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/DiagnosticInfo.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/IRBuilder.h"
#include "llvm/Support/Debug.h"
+#include "llvm/Support/raw_ostream.h"
#include "llvm/Transforms/Utils/VectorUtils.h"
using namespace llvm;
AliasSetId.push_back(ASId);
}
-bool LoopAccessInfo::RuntimePointerCheck::needsChecking(unsigned I,
- unsigned J) const {
+bool LoopAccessInfo::RuntimePointerCheck::needsChecking(
+ unsigned I, unsigned J, const SmallVectorImpl<int> *PtrPartition) const {
// No need to check if two readonly pointers intersect.
if (!IsWritePtr[I] && !IsWritePtr[J])
return false;
if (AliasSetId[I] != AliasSetId[J])
return false;
+ // If PtrPartition is set omit checks between pointers of the same partition.
+ // Partition number -1 means that the pointer is used in multiple partitions.
+ // In this case we can't omit the check.
+ if (PtrPartition && (*PtrPartition)[I] != -1 &&
+ (*PtrPartition)[I] == (*PtrPartition)[J])
+ return false;
+
return true;
}
-void LoopAccessInfo::RuntimePointerCheck::print(raw_ostream &OS,
- unsigned Depth) const {
+void LoopAccessInfo::RuntimePointerCheck::print(
+ raw_ostream &OS, unsigned Depth,
+ const SmallVectorImpl<int> *PtrPartition) const {
unsigned NumPointers = Pointers.size();
if (NumPointers == 0)
return;
unsigned N = 0;
for (unsigned I = 0; I < NumPointers; ++I)
for (unsigned J = I + 1; J < NumPointers; ++J)
- if (needsChecking(I, J)) {
+ if (needsChecking(I, J, PtrPartition)) {
OS.indent(Depth) << N++ << ":\n";
- OS.indent(Depth + 2) << *Pointers[I] << "\n";
- OS.indent(Depth + 2) << *Pointers[J] << "\n";
+ OS.indent(Depth + 2) << *Pointers[I];
+ if (PtrPartition)
+ OS << " (Partition: " << (*PtrPartition)[I] << ")";
+ OS << "\n";
+ OS.indent(Depth + 2) << *Pointers[J];
+ if (PtrPartition)
+ OS << " (Partition: " << (*PtrPartition)[J] << ")";
+ OS << "\n";
}
}
+bool LoopAccessInfo::RuntimePointerCheck::needsAnyChecking(
+ const SmallVectorImpl<int> *PtrPartition) const {
+ unsigned NumPointers = Pointers.size();
+
+ for (unsigned I = 0; I < NumPointers; ++I)
+ for (unsigned J = I + 1; J < NumPointers; ++J)
+ if (needsChecking(I, J, PtrPartition))
+ return true;
+ return false;
+}
+
namespace {
/// \brief Analyses memory accesses in a loop.
///
case BackwardVectorizableButPreventsForwarding:
return false;
}
+ llvm_unreachable("unexpected DepType!");
}
bool MemoryDepChecker::Dependence::isInterestingDependence(DepType Type) {
case BackwardVectorizableButPreventsForwarding:
return true;
}
+ llvm_unreachable("unexpected DepType!");
}
bool MemoryDepChecker::Dependence::isPossiblyBackward() const {
case BackwardVectorizableButPreventsForwarding:
return true;
}
+ llvm_unreachable("unexpected DepType!");
}
bool MemoryDepChecker::couldPreventStoreLoadForward(unsigned Distance,
return SafeForVectorization;
}
+SmallVector<Instruction *, 4>
+MemoryDepChecker::getInstructionsForAccess(Value *Ptr, bool isWrite) const {
+ MemAccessInfo Access(Ptr, isWrite);
+ auto &IndexVector = Accesses.find(Access)->second;
+
+ SmallVector<Instruction *, 4> Insts;
+ std::transform(IndexVector.begin(), IndexVector.end(),
+ std::back_inserter(Insts),
+ [&](unsigned Idx) { return this->InstMap[Idx]; });
+ return Insts;
+}
+
const char *MemoryDepChecker::Dependence::DepName[] = {
"NoDep", "Unknown", "Forward", "ForwardButPreventsForwarding", "Backward",
"BackwardVectorizable", "BackwardVectorizableButPreventsForwarding"};
if (Call && getIntrinsicIDForCall(Call, TLI))
continue;
+ // If the function has an explicit vectorized counterpart, we can safely
+ // assume that it can be vectorized.
+ if (Call && !Call->isNoBuiltin() && Call->getCalledFunction() &&
+ TLI->isFunctionVectorizable(Call->getCalledFunction()->getName()))
+ continue;
+
LoadInst *Ld = dyn_cast<LoadInst>(it);
if (!Ld || (!Ld->isSimple() && !IsAnnotatedParallel)) {
emitAnalysis(LoopAccessReport(Ld)
for (I = Stores.begin(), IE = Stores.end(); I != IE; ++I) {
StoreInst *ST = cast<StoreInst>(*I);
Value* Ptr = ST->getPointerOperand();
-
- if (isUniform(Ptr)) {
- emitAnalysis(
- LoopAccessReport(ST)
- << "write to a loop invariant address could not be vectorized");
- DEBUG(dbgs() << "LAA: We don't allow storing to uniform addresses\n");
- CanVecMem = false;
- return;
- }
-
+ // Check for store to loop invariant address.
+ StoreToLoopInvariantAddress |= isUniform(Ptr);
// If we did *not* see this pointer before, insert it to the read-write
// list. At this phase it is only a 'write' list.
if (Seen.insert(Ptr).second) {
if (NumComparisons == 0 && NeedRTCheck)
NeedRTCheck = false;
- // Check that we did not find an unsizeable pointer.
+ // Check that we found the bounds for the pointer.
if (CanDoRT)
DEBUG(dbgs() << "LAA: We can perform a memory runtime check if needed.\n");
else if (NeedRTCheck) {
CanDoRT = Accesses.canCheckPtrAtRT(PtrRtCheck, NumComparisons, SE,
TheLoop, Strides, true);
- // Check that we didn't find an unsizeable pointer.
+ // Check that we found the bounds for the pointer.
if (!CanDoRT && NumComparisons > 0) {
emitAnalysis(LoopAccessReport()
<< "cannot check memory dependencies at runtime");
}
}
- if (!CanVecMem)
+ if (CanVecMem)
+ DEBUG(dbgs() << "LAA: No unsafe dependent memory operations in loop. We"
+ << (NeedRTCheck ? "" : " don't")
+ << " need a runtime memory check.\n");
+ else {
emitAnalysis(LoopAccessReport() <<
"unsafe dependent memory operations in loop");
-
- DEBUG(dbgs() << "LAA: We" << (NeedRTCheck ? "" : " don't") <<
- " need a runtime memory check.\n");
+ DEBUG(dbgs() << "LAA: unsafe dependent memory operations in loop\n");
+ }
}
bool LoopAccessInfo::blockNeedsPredication(BasicBlock *BB, Loop *TheLoop,
return nullptr;
}
-std::pair<Instruction *, Instruction *>
-LoopAccessInfo::addRuntimeCheck(Instruction *Loc) const {
- Instruction *tnullptr = nullptr;
+std::pair<Instruction *, Instruction *> LoopAccessInfo::addRuntimeCheck(
+ Instruction *Loc, const SmallVectorImpl<int> *PtrPartition) const {
if (!PtrRtCheck.Need)
- return std::pair<Instruction *, Instruction *>(tnullptr, tnullptr);
+ return std::make_pair(nullptr, nullptr);
unsigned NumPointers = PtrRtCheck.Pointers.size();
SmallVector<TrackingVH<Value> , 2> Starts;
Value *MemoryRuntimeCheck = nullptr;
for (unsigned i = 0; i < NumPointers; ++i) {
for (unsigned j = i+1; j < NumPointers; ++j) {
- if (!PtrRtCheck.needsChecking(i, j))
+ if (!PtrRtCheck.needsChecking(i, j, PtrPartition))
continue;
unsigned AS0 = Starts[i]->getType()->getPointerAddressSpace();
}
}
+ if (!MemoryRuntimeCheck)
+ return std::make_pair(nullptr, nullptr);
+
// We have to do this trickery because the IRBuilder might fold the check to a
// constant expression in which case there is no Instruction anchored in a
// the block.
const ValueToValueMap &Strides)
: DepChecker(SE, L), NumComparisons(0), TheLoop(L), SE(SE), DL(DL),
TLI(TLI), AA(AA), DT(DT), NumLoads(0), NumStores(0),
- MaxSafeDepDistBytes(-1U), CanVecMem(false) {
+ MaxSafeDepDistBytes(-1U), CanVecMem(false),
+ StoreToLoopInvariantAddress(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
+ if (PtrRtCheck.Need)
OS.indent(Depth) << "Memory dependences are safe with run-time checks\n";
+ else
+ OS.indent(Depth) << "Memory dependences are safe\n";
}
+ OS.indent(Depth) << "Store to invariant address was "
+ << (StoreToLoopInvariantAddress ? "" : "not ")
+ << "found in loop.\n";
+
if (Report)
OS.indent(Depth) << "Report: " << Report->str() << "\n";
projects / oota-llvm.git / blobdiff