Google Git
Sign in
cobalt / cobalt / e83fce97d7405b0b5e569d961aa431b1112ac6ac / . / src / third_party / llvm-project / polly / lib / Analysis / ScopInfo.cpp
blob: 489a60b6754b139367b9be7e706eb92d6b8382f3 [file] [log] [blame]
//===- ScopInfo.cpp -------------------------------------------------------===//
//
// The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// Create a polyhedral description for a static control flow region.
//
// The pass creates a polyhedral description of the Scops detected by the Scop
// detection derived from their LLVM-IR code.
//
// This representation is shared among several tools in the polyhedral
// community, which are e.g. Cloog, Pluto, Loopo, Graphite.
//
//===----------------------------------------------------------------------===//
#include "polly/ScopInfo.h"
#include "polly/LinkAllPasses.h"
#include "polly/Options.h"
#include "polly/ScopBuilder.h"
#include "polly/ScopDetection.h"
#include "polly/Support/GICHelper.h"
#include "polly/Support/ISLOStream.h"
#include "polly/Support/ISLTools.h"
#include "polly/Support/SCEVAffinator.h"
#include "polly/Support/SCEVValidator.h"
#include "polly/Support/ScopHelper.h"
#include "llvm/ADT/APInt.h"
#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/DenseSet.h"
#include "llvm/ADT/PostOrderIterator.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/Statistic.h"
#include "llvm/ADT/StringExtras.h"
#include "llvm/ADT/StringMap.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/AliasSetTracker.h"
#include "llvm/Analysis/AssumptionCache.h"
#include "llvm/Analysis/Loads.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/OptimizationRemarkEmitter.h"
#include "llvm/Analysis/RegionInfo.h"
#include "llvm/Analysis/RegionIterator.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Analysis/ScalarEvolutionExpressions.h"
#include "llvm/IR/Argument.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/CFG.h"
#include "llvm/IR/ConstantRange.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/InstrTypes.h"
#include "llvm/IR/Instruction.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/PassManager.h"
#include "llvm/IR/Type.h"
#include "llvm/IR/Use.h"
#include "llvm/IR/User.h"
#include "llvm/IR/Value.h"
#include "llvm/Pass.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/MathExtras.h"
#include "llvm/Support/raw_ostream.h"
#include "isl/aff.h"
#include "isl/constraint.h"
#include "isl/local_space.h"
#include "isl/map.h"
#include "isl/options.h"
#include "isl/printer.h"
#include "isl/schedule.h"
#include "isl/schedule_node.h"
#include "isl/set.h"
#include "isl/union_map.h"
#include "isl/union_set.h"
#include "isl/val.h"
#include <algorithm>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <iterator>
#include <memory>
#include <string>
#include <tuple>
#include <utility>
#include <vector>
using namespace llvm;
using namespace polly;
#define DEBUG_TYPE "polly-scops"
STATISTIC(AssumptionsAliasing, "Number of aliasing assumptions taken.");
STATISTIC(AssumptionsInbounds, "Number of inbounds assumptions taken.");
STATISTIC(AssumptionsWrapping, "Number of wrapping assumptions taken.");
STATISTIC(AssumptionsUnsigned, "Number of unsigned assumptions taken.");
STATISTIC(AssumptionsComplexity, "Number of too complex SCoPs.");
STATISTIC(AssumptionsUnprofitable, "Number of unprofitable SCoPs.");
STATISTIC(AssumptionsErrorBlock, "Number of error block assumptions taken.");
STATISTIC(AssumptionsInfiniteLoop, "Number of bounded loop assumptions taken.");
STATISTIC(AssumptionsInvariantLoad,
"Number of invariant loads assumptions taken.");
STATISTIC(AssumptionsDelinearization,
"Number of delinearization assumptions taken.");
STATISTIC(NumScops, "Number of feasible SCoPs after ScopInfo");
STATISTIC(NumLoopsInScop, "Number of loops in scops");
STATISTIC(NumBoxedLoops, "Number of boxed loops in SCoPs after ScopInfo");
STATISTIC(NumAffineLoops, "Number of affine loops in SCoPs after ScopInfo");
STATISTIC(NumScopsDepthZero, "Number of scops with maximal loop depth 0");
STATISTIC(NumScopsDepthOne, "Number of scops with maximal loop depth 1");
STATISTIC(NumScopsDepthTwo, "Number of scops with maximal loop depth 2");
STATISTIC(NumScopsDepthThree, "Number of scops with maximal loop depth 3");
STATISTIC(NumScopsDepthFour, "Number of scops with maximal loop depth 4");
STATISTIC(NumScopsDepthFive, "Number of scops with maximal loop depth 5");
STATISTIC(NumScopsDepthLarger,
"Number of scops with maximal loop depth 6 and larger");
STATISTIC(MaxNumLoopsInScop, "Maximal number of loops in scops");
STATISTIC(NumValueWrites, "Number of scalar value writes after ScopInfo");
STATISTIC(
NumValueWritesInLoops,
"Number of scalar value writes nested in affine loops after ScopInfo");
STATISTIC(NumPHIWrites, "Number of scalar phi writes after ScopInfo");
STATISTIC(NumPHIWritesInLoops,
"Number of scalar phi writes nested in affine loops after ScopInfo");
STATISTIC(NumSingletonWrites, "Number of singleton writes after ScopInfo");
STATISTIC(NumSingletonWritesInLoops,
"Number of singleton writes nested in affine loops after ScopInfo");
// The maximal number of basic sets we allow during domain construction to
// be created. More complex scops will result in very high compile time and
// are also unlikely to result in good code
static int const MaxDisjunctsInDomain = 20;
// The number of disjunct in the context after which we stop to add more
// disjuncts. This parameter is there to avoid exponential growth in the
// number of disjunct when adding non-convex sets to the context.
static int const MaxDisjunctsInContext = 4;
// The maximal number of dimensions we allow during invariant load construction.
// More complex access ranges will result in very high compile time and are also
// unlikely to result in good code. This value is very high and should only
// trigger for corner cases (e.g., the "dct_luma" function in h264, SPEC2006).
static int const MaxDimensionsInAccessRange = 9;
static cl::opt<int>
OptComputeOut("polly-analysis-computeout",
cl::desc("Bound the scop analysis by a maximal amount of "
"computational steps (0 means no bound)"),
cl::Hidden, cl::init(800000), cl::ZeroOrMore,
cl::cat(PollyCategory));
static cl::opt<bool> PollyRemarksMinimal(
"polly-remarks-minimal",
cl::desc("Do not emit remarks about assumptions that are known"),
cl::Hidden, cl::ZeroOrMore, cl::init(false), cl::cat(PollyCategory));
static cl::opt<int> RunTimeChecksMaxAccessDisjuncts(
"polly-rtc-max-array-disjuncts",
cl::desc("The maximal number of disjunts allowed in memory accesses to "
"to build RTCs."),
cl::Hidden, cl::ZeroOrMore, cl::init(8), cl::cat(PollyCategory));
static cl::opt<unsigned> RunTimeChecksMaxParameters(
"polly-rtc-max-parameters",
cl::desc("The maximal number of parameters allowed in RTCs."), cl::Hidden,
cl::ZeroOrMore, cl::init(8), cl::cat(PollyCategory));
static cl::opt<unsigned> RunTimeChecksMaxArraysPerGroup(
"polly-rtc-max-arrays-per-group",
cl::desc("The maximal number of arrays to compare in each alias group."),
cl::Hidden, cl::ZeroOrMore, cl::init(20), cl::cat(PollyCategory));
static cl::opt<std::string> UserContextStr(
"polly-context", cl::value_desc("isl parameter set"),
cl::desc("Provide additional constraints on the context parameters"),
cl::init(""), cl::cat(PollyCategory));
static cl::opt<bool>
IslOnErrorAbort("polly-on-isl-error-abort",
cl::desc("Abort if an isl error is encountered"),
cl::init(true), cl::cat(PollyCategory));
static cl::opt<bool> PollyPreciseInbounds(
"polly-precise-inbounds",
cl::desc("Take more precise inbounds assumptions (do not scale well)"),
cl::Hidden, cl::init(false), cl::cat(PollyCategory));
static cl::opt<bool>
PollyIgnoreInbounds("polly-ignore-inbounds",
cl::desc("Do not take inbounds assumptions at all"),
cl::Hidden, cl::init(false), cl::cat(PollyCategory));
static cl::opt<bool> PollyIgnoreParamBounds(
"polly-ignore-parameter-bounds",
cl::desc(
"Do not add parameter bounds and do no gist simplify sets accordingly"),
cl::Hidden, cl::init(false), cl::cat(PollyCategory));
static cl::opt<bool> PollyAllowDereferenceOfAllFunctionParams(
"polly-allow-dereference-of-all-function-parameters",
cl::desc(
"Treat all parameters to functions that are pointers as dereferencible."
" This is useful for invariant load hoisting, since we can generate"
" less runtime checks. This is only valid if all pointers to functions"
" are always initialized, so that Polly can choose to hoist"
" their loads. "),
cl::Hidden, cl::init(false), cl::cat(PollyCategory));
static cl::opt<bool> PollyPreciseFoldAccesses(
"polly-precise-fold-accesses",
cl::desc("Fold memory accesses to model more possible delinearizations "
"(does not scale well)"),
cl::Hidden, cl::init(false), cl::cat(PollyCategory));
bool polly::UseInstructionNames;
static cl::opt<bool, true> XUseInstructionNames(
"polly-use-llvm-names",
cl::desc("Use LLVM-IR names when deriving statement names"),
cl::location(UseInstructionNames), cl::Hidden, cl::init(false),
cl::ZeroOrMore, cl::cat(PollyCategory));
static cl::opt<bool> PollyPrintInstructions(
"polly-print-instructions", cl::desc("Output instructions per ScopStmt"),
cl::Hidden, cl::Optional, cl::init(false), cl::cat(PollyCategory));
//===----------------------------------------------------------------------===//
// Create a sequence of two schedules. Either argument may be null and is
// interpreted as the empty schedule. Can also return null if both schedules are
// empty.
static isl::schedule combineInSequence(isl::schedule Prev, isl::schedule Succ) {
if (!Prev)
return Succ;
if (!Succ)
return Prev;
return Prev.sequence(Succ);
}
static isl::set addRangeBoundsToSet(isl::set S, const ConstantRange &Range,
int dim, isl::dim type) {
isl::val V;
isl::ctx Ctx = S.get_ctx();
// The upper and lower bound for a parameter value is derived either from
// the data type of the parameter or from the - possibly more restrictive -
// range metadata.
V = valFromAPInt(Ctx.get(), Range.getSignedMin(), true);
S = S.lower_bound_val(type, dim, V);
V = valFromAPInt(Ctx.get(), Range.getSignedMax(), true);
S = S.upper_bound_val(type, dim, V);
if (Range.isFullSet())
return S;
if (S.n_basic_set() > MaxDisjunctsInContext)
return S;
// In case of signed wrapping, we can refine the set of valid values by
// excluding the part not covered by the wrapping range.
if (Range.isSignWrappedSet()) {
V = valFromAPInt(Ctx.get(), Range.getLower(), true);
isl::set SLB = S.lower_bound_val(type, dim, V);
V = valFromAPInt(Ctx.get(), Range.getUpper(), true);
V = V.sub_ui(1);
isl::set SUB = S.upper_bound_val(type, dim, V);
S = SLB.unite(SUB);
}
return S;
}
static const ScopArrayInfo *identifyBasePtrOriginSAI(Scop *S, Value *BasePtr) {
LoadInst *BasePtrLI = dyn_cast<LoadInst>(BasePtr);
if (!BasePtrLI)
return nullptr;
if (!S->contains(BasePtrLI))
return nullptr;
ScalarEvolution &SE = *S->getSE();
auto *OriginBaseSCEV =
SE.getPointerBase(SE.getSCEV(BasePtrLI->getPointerOperand()));
if (!OriginBaseSCEV)
return nullptr;
auto *OriginBaseSCEVUnknown = dyn_cast<SCEVUnknown>(OriginBaseSCEV);
if (!OriginBaseSCEVUnknown)
return nullptr;
return S->getScopArrayInfo(OriginBaseSCEVUnknown->getValue(),
MemoryKind::Array);
}
ScopArrayInfo::ScopArrayInfo(Value *BasePtr, Type *ElementType, isl::ctx Ctx,
ArrayRef<const SCEV *> Sizes, MemoryKind Kind,
const DataLayout &DL, Scop *S,
const char *BaseName)
: BasePtr(BasePtr), ElementType(ElementType), Kind(Kind), DL(DL), S(*S) {
std::string BasePtrName =
BaseName ? BaseName
: getIslCompatibleName("MemRef", BasePtr, S->getNextArrayIdx(),
Kind == MemoryKind::PHI ? "__phi" : "",
UseInstructionNames);
Id = isl::id::alloc(Ctx, BasePtrName, this);
updateSizes(Sizes);
if (!BasePtr || Kind != MemoryKind::Array) {
BasePtrOriginSAI = nullptr;
return;
}
BasePtrOriginSAI = identifyBasePtrOriginSAI(S, BasePtr);
if (BasePtrOriginSAI)
const_cast<ScopArrayInfo *>(BasePtrOriginSAI)->addDerivedSAI(this);
}
ScopArrayInfo::~ScopArrayInfo() = default;
isl::space ScopArrayInfo::getSpace() const {
auto Space = isl::space(Id.get_ctx(), 0, getNumberOfDimensions());
Space = Space.set_tuple_id(isl::dim::set, Id);
return Space;
}
bool ScopArrayInfo::isReadOnly() {
isl::union_set WriteSet = S.getWrites().range();
isl::space Space = getSpace();
WriteSet = WriteSet.extract_set(Space);
return bool(WriteSet.is_empty());
}
bool ScopArrayInfo::isCompatibleWith(const ScopArrayInfo *Array) const {
if (Array->getElementType() != getElementType())
return false;
if (Array->getNumberOfDimensions() != getNumberOfDimensions())
return false;
for (unsigned i = 0; i < getNumberOfDimensions(); i++)
if (Array->getDimensionSize(i) != getDimensionSize(i))
return false;
return true;
}
void ScopArrayInfo::updateElementType(Type *NewElementType) {
if (NewElementType == ElementType)
return;
auto OldElementSize = DL.getTypeAllocSizeInBits(ElementType);
auto NewElementSize = DL.getTypeAllocSizeInBits(NewElementType);
if (NewElementSize == OldElementSize || NewElementSize == 0)
return;
if (NewElementSize % OldElementSize == 0 && NewElementSize < OldElementSize) {
ElementType = NewElementType;
} else {
auto GCD = GreatestCommonDivisor64(NewElementSize, OldElementSize);
ElementType = IntegerType::get(ElementType->getContext(), GCD);
}
}
/// Make the ScopArrayInfo model a Fortran Array
void ScopArrayInfo::applyAndSetFAD(Value *FAD) {
assert(FAD && "got invalid Fortran array descriptor");
if (this->FAD) {
assert(this->FAD == FAD &&
"receiving different array descriptors for same array");
return;
}
assert(DimensionSizesPw.size() > 0 && !DimensionSizesPw[0]);
assert(!this->FAD);
this->FAD = FAD;
isl::space Space(S.getIslCtx(), 1, 0);
std::string param_name = getName();
param_name += "_fortranarr_size";
isl::id IdPwAff = isl::id::alloc(S.getIslCtx(), param_name, this);
Space = Space.set_dim_id(isl::dim::param, 0, IdPwAff);
isl::pw_aff PwAff =
isl::aff::var_on_domain(isl::local_space(Space), isl::dim::param, 0);
DimensionSizesPw[0] = PwAff;
}
bool ScopArrayInfo::updateSizes(ArrayRef<const SCEV *> NewSizes,
bool CheckConsistency) {
int SharedDims = std::min(NewSizes.size(), DimensionSizes.size());
int ExtraDimsNew = NewSizes.size() - SharedDims;
int ExtraDimsOld = DimensionSizes.size() - SharedDims;
if (CheckConsistency) {
for (int i = 0; i < SharedDims; i++) {
auto *NewSize = NewSizes[i + ExtraDimsNew];
auto *KnownSize = DimensionSizes[i + ExtraDimsOld];
if (NewSize && KnownSize && NewSize != KnownSize)
return false;
}
if (DimensionSizes.size() >= NewSizes.size())
return true;
}
DimensionSizes.clear();
DimensionSizes.insert(DimensionSizes.begin(), NewSizes.begin(),
NewSizes.end());
DimensionSizesPw.clear();
for (const SCEV *Expr : DimensionSizes) {
if (!Expr) {
DimensionSizesPw.push_back(nullptr);
continue;
}
isl::pw_aff Size = S.getPwAffOnly(Expr);
DimensionSizesPw.push_back(Size);
}
return true;
}
std::string ScopArrayInfo::getName() const { return Id.get_name(); }
int ScopArrayInfo::getElemSizeInBytes() const {
return DL.getTypeAllocSize(ElementType);
}
isl::id ScopArrayInfo::getBasePtrId() const { return Id; }
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
LLVM_DUMP_METHOD void ScopArrayInfo::dump() const { print(errs()); }
#endif
void ScopArrayInfo::print(raw_ostream &OS, bool SizeAsPwAff) const {
OS.indent(8) << *getElementType() << " " << getName();
unsigned u = 0;
// If this is a Fortran array, then we can print the outermost dimension
// as a isl_pw_aff even though there is no SCEV information.
bool IsOutermostSizeKnown = SizeAsPwAff && FAD;
if (!IsOutermostSizeKnown && getNumberOfDimensions() > 0 &&
!getDimensionSize(0)) {
OS << "[*]";
u++;
}
for (; u < getNumberOfDimensions(); u++) {
OS << "[";
if (SizeAsPwAff) {
isl::pw_aff Size = getDimensionSizePw(u);
OS << " " << Size << " ";
} else {
OS << *getDimensionSize(u);
}
OS << "]";
}
OS << ";";
if (BasePtrOriginSAI)
OS << " [BasePtrOrigin: " << BasePtrOriginSAI->getName() << "]";
OS << " // Element size " << getElemSizeInBytes() << "\n";
}
const ScopArrayInfo *
ScopArrayInfo::getFromAccessFunction(isl::pw_multi_aff PMA) {
isl::id Id = PMA.get_tuple_id(isl::dim::out);
assert(!Id.is_null() && "Output dimension didn't have an ID");
return getFromId(Id);
}
const ScopArrayInfo *ScopArrayInfo::getFromId(isl::id Id) {
void *User = Id.get_user();
const ScopArrayInfo *SAI = static_cast<ScopArrayInfo *>(User);
return SAI;
}
void MemoryAccess::wrapConstantDimensions() {
auto *SAI = getScopArrayInfo();
isl::space ArraySpace = SAI->getSpace();
isl::ctx Ctx = ArraySpace.get_ctx();
unsigned DimsArray = SAI->getNumberOfDimensions();
isl::multi_aff DivModAff = isl::multi_aff::identity(
ArraySpace.map_from_domain_and_range(ArraySpace));
isl::local_space LArraySpace = isl::local_space(ArraySpace);
// Begin with last dimension, to iteratively carry into higher dimensions.
for (int i = DimsArray - 1; i > 0; i--) {
auto *DimSize = SAI->getDimensionSize(i);
auto *DimSizeCst = dyn_cast<SCEVConstant>(DimSize);
// This transformation is not applicable to dimensions with dynamic size.
if (!DimSizeCst)
continue;
// This transformation is not applicable to dimensions of size zero.
if (DimSize->isZero())
continue;
isl::val DimSizeVal =
valFromAPInt(Ctx.get(), DimSizeCst->getAPInt(), false);
isl::aff Var = isl::aff::var_on_domain(LArraySpace, isl::dim::set, i);
isl::aff PrevVar =
isl::aff::var_on_domain(LArraySpace, isl::dim::set, i - 1);
// Compute: index % size
// Modulo must apply in the divide of the previous iteration, if any.
isl::aff Modulo = Var.mod(DimSizeVal);
Modulo = Modulo.pullback(DivModAff);
// Compute: floor(index / size)
isl::aff Divide = Var.div(isl::aff(LArraySpace, DimSizeVal));
Divide = Divide.floor();
Divide = Divide.add(PrevVar);
Divide = Divide.pullback(DivModAff);
// Apply Modulo and Divide.
DivModAff = DivModAff.set_aff(i, Modulo);
DivModAff = DivModAff.set_aff(i - 1, Divide);
}
// Apply all modulo/divides on the accesses.
isl::map Relation = AccessRelation;
Relation = Relation.apply_range(isl::map::from_multi_aff(DivModAff));
Relation = Relation.detect_equalities();
AccessRelation = Relation;
}
void MemoryAccess::updateDimensionality() {
auto *SAI = getScopArrayInfo();
isl::space ArraySpace = SAI->getSpace();
isl::space AccessSpace = AccessRelation.get_space().range();
isl::ctx Ctx = ArraySpace.get_ctx();
auto DimsArray = ArraySpace.dim(isl::dim::set);
auto DimsAccess = AccessSpace.dim(isl::dim::set);
auto DimsMissing = DimsArray - DimsAccess;
auto *BB = getStatement()->getEntryBlock();
auto &DL = BB->getModule()->getDataLayout();
unsigned ArrayElemSize = SAI->getElemSizeInBytes();
unsigned ElemBytes = DL.getTypeAllocSize(getElementType());
isl::map Map = isl::map::from_domain_and_range(
isl::set::universe(AccessSpace), isl::set::universe(ArraySpace));
for (unsigned i = 0; i < DimsMissing; i++)
Map = Map.fix_si(isl::dim::out, i, 0);
for (unsigned i = DimsMissing; i < DimsArray; i++)
Map = Map.equate(isl::dim::in, i - DimsMissing, isl::dim::out, i);
AccessRelation = AccessRelation.apply_range(Map);
// For the non delinearized arrays, divide the access function of the last
// subscript by the size of the elements in the array.
//
// A stride one array access in C expressed as A[i] is expressed in
// LLVM-IR as something like A[i * elementsize]. This hides the fact that
// two subsequent values of 'i' index two values that are stored next to
// each other in memory. By this division we make this characteristic
// obvious again. If the base pointer was accessed with offsets not divisible
// by the accesses element size, we will have chosen a smaller ArrayElemSize
// that divides the offsets of all accesses to this base pointer.
if (DimsAccess == 1) {
isl::val V = isl::val(Ctx, ArrayElemSize);
AccessRelation = AccessRelation.floordiv_val(V);
}
// We currently do this only if we added at least one dimension, which means
// some dimension's indices have not been specified, an indicator that some
// index values have been added together.
// TODO: Investigate general usefulness; Effect on unit tests is to make index
// expressions more complicated.
if (DimsMissing)
wrapConstantDimensions();
if (!isAffine())
computeBoundsOnAccessRelation(ArrayElemSize);
// Introduce multi-element accesses in case the type loaded by this memory
// access is larger than the canonical element type of the array.
//
// An access ((float *)A)[i] to an array char *A is modeled as
// {[i] -> A[o] : 4 i <= o <= 4 i + 3
if (ElemBytes > ArrayElemSize) {
assert(ElemBytes % ArrayElemSize == 0 &&
"Loaded element size should be multiple of canonical element size");
isl::map Map = isl::map::from_domain_and_range(
isl::set::universe(ArraySpace), isl::set::universe(ArraySpace));
for (unsigned i = 0; i < DimsArray - 1; i++)
Map = Map.equate(isl::dim::in, i, isl::dim::out, i);
isl::constraint C;
isl::local_space LS;
LS = isl::local_space(Map.get_space());
int Num = ElemBytes / getScopArrayInfo()->getElemSizeInBytes();
C = isl::constraint::alloc_inequality(LS);
C = C.set_constant_val(isl::val(Ctx, Num - 1));
C = C.set_coefficient_si(isl::dim::in, DimsArray - 1, 1);
C = C.set_coefficient_si(isl::dim::out, DimsArray - 1, -1);
Map = Map.add_constraint(C);
C = isl::constraint::alloc_inequality(LS);
C = C.set_coefficient_si(isl::dim::in, DimsArray - 1, -1);
C = C.set_coefficient_si(isl::dim::out, DimsArray - 1, 1);
C = C.set_constant_val(isl::val(Ctx, 0));
Map = Map.add_constraint(C);
AccessRelation = AccessRelation.apply_range(Map);
}
}
const std::string
MemoryAccess::getReductionOperatorStr(MemoryAccess::ReductionType RT) {
switch (RT) {
case MemoryAccess::RT_NONE:
llvm_unreachable("Requested a reduction operator string for a memory "
"access which isn't a reduction");
case MemoryAccess::RT_ADD:
return "+";
case MemoryAccess::RT_MUL:
return "*";
case MemoryAccess::RT_BOR:
return "|";
case MemoryAccess::RT_BXOR:
return "^";
case MemoryAccess::RT_BAND:
return "&";
}
llvm_unreachable("Unknown reduction type");
}
const ScopArrayInfo *MemoryAccess::getOriginalScopArrayInfo() const {
isl::id ArrayId = getArrayId();
void *User = ArrayId.get_user();
const ScopArrayInfo *SAI = static_cast<ScopArrayInfo *>(User);
return SAI;
}
const ScopArrayInfo *MemoryAccess::getLatestScopArrayInfo() const {
isl::id ArrayId = getLatestArrayId();
void *User = ArrayId.get_user();
const ScopArrayInfo *SAI = static_cast<ScopArrayInfo *>(User);
return SAI;
}
isl::id MemoryAccess::getOriginalArrayId() const {
return AccessRelation.get_tuple_id(isl::dim::out);
}
isl::id MemoryAccess::getLatestArrayId() const {
if (!hasNewAccessRelation())
return getOriginalArrayId();
return NewAccessRelation.get_tuple_id(isl::dim::out);
}
isl::map MemoryAccess::getAddressFunction() const {
return getAccessRelation().lexmin();
}
isl::pw_multi_aff
MemoryAccess::applyScheduleToAccessRelation(isl::union_map USchedule) const {
isl::map Schedule, ScheduledAccRel;
isl::union_set UDomain;
UDomain = getStatement()->getDomain();
USchedule = USchedule.intersect_domain(UDomain);
Schedule = isl::map::from_union_map(USchedule);
ScheduledAccRel = getAddressFunction().apply_domain(Schedule);
return isl::pw_multi_aff::from_map(ScheduledAccRel);
}
isl::map MemoryAccess::getOriginalAccessRelation() const {
return AccessRelation;
}
std::string MemoryAccess::getOriginalAccessRelationStr() const {
return AccessRelation.to_str();
}
isl::space MemoryAccess::getOriginalAccessRelationSpace() const {
return AccessRelation.get_space();
}
isl::map MemoryAccess::getNewAccessRelation() const {
return NewAccessRelation;
}
std::string MemoryAccess::getNewAccessRelationStr() const {
return NewAccessRelation.to_str();
}
std::string MemoryAccess::getAccessRelationStr() const {
return getAccessRelation().to_str();
}
isl::basic_map MemoryAccess::createBasicAccessMap(ScopStmt *Statement) {
isl::space Space = isl::space(Statement->getIslCtx(), 0, 1);
Space = Space.align_params(Statement->getDomainSpace());
return isl::basic_map::from_domain_and_range(
isl::basic_set::universe(Statement->getDomainSpace()),
isl::basic_set::universe(Space));
}
// Formalize no out-of-bound access assumption
//
// When delinearizing array accesses we optimistically assume that the
// delinearized accesses do not access out of bound locations (the subscript
// expression of each array evaluates for each statement instance that is
// executed to a value that is larger than zero and strictly smaller than the
// size of the corresponding dimension). The only exception is the outermost
// dimension for which we do not need to assume any upper bound. At this point
// we formalize this assumption to ensure that at code generation time the
// relevant run-time checks can be generated.
//
// To find the set of constraints necessary to avoid out of bound accesses, we
// first build the set of data locations that are not within array bounds. We
// then apply the reverse access relation to obtain the set of iterations that
// may contain invalid accesses and reduce this set of iterations to the ones
// that are actually executed by intersecting them with the domain of the
// statement. If we now project out all loop dimensions, we obtain a set of
// parameters that may cause statement instances to be executed that may
// possibly yield out of bound memory accesses. The complement of these
// constraints is the set of constraints that needs to be assumed to ensure such
// statement instances are never executed.
void MemoryAccess::assumeNoOutOfBound() {
if (PollyIgnoreInbounds)
return;
auto *SAI = getScopArrayInfo();
isl::space Space = getOriginalAccessRelationSpace().range();
isl::set Outside = isl::set::empty(Space);
for (int i = 1, Size = Space.dim(isl::dim::set); i < Size; ++i) {
isl::local_space LS(Space);
isl::pw_aff Var = isl::pw_aff::var_on_domain(LS, isl::dim::set, i);
isl::pw_aff Zero = isl::pw_aff(LS);
isl::set DimOutside = Var.lt_set(Zero);
isl::pw_aff SizeE = SAI->getDimensionSizePw(i);
SizeE = SizeE.add_dims(isl::dim::in, Space.dim(isl::dim::set));
SizeE = SizeE.set_tuple_id(isl::dim::in, Space.get_tuple_id(isl::dim::set));
DimOutside = DimOutside.unite(SizeE.le_set(Var));
Outside = Outside.unite(DimOutside);
}
Outside = Outside.apply(getAccessRelation().reverse());
Outside = Outside.intersect(Statement->getDomain());
Outside = Outside.params();
// Remove divs to avoid the construction of overly complicated assumptions.
// Doing so increases the set of parameter combinations that are assumed to
// not appear. This is always save, but may make the resulting run-time check
// bail out more often than strictly necessary.
Outside = Outside.remove_divs();
Outside = Outside.complement();
const auto &Loc = getAccessInstruction()
? getAccessInstruction()->getDebugLoc()
: DebugLoc();
if (!PollyPreciseInbounds)
Outside = Outside.gist_params(Statement->getDomain().params());
Statement->getParent()->recordAssumption(INBOUNDS, Outside, Loc,
AS_ASSUMPTION);
}
void MemoryAccess::buildMemIntrinsicAccessRelation() {
assert(isMemoryIntrinsic());
assert(Subscripts.size() == 2 && Sizes.size() == 1);
isl::pw_aff SubscriptPWA = getPwAff(Subscripts[0]);
isl::map SubscriptMap = isl::map::from_pw_aff(SubscriptPWA);
isl::map LengthMap;
if (Subscripts[1] == nullptr) {
LengthMap = isl::map::universe(SubscriptMap.get_space());
} else {
isl::pw_aff LengthPWA = getPwAff(Subscripts[1]);
LengthMap = isl::map::from_pw_aff(LengthPWA);
isl::space RangeSpace = LengthMap.get_space().range();
LengthMap = LengthMap.apply_range(isl::map::lex_gt(RangeSpace));
}
LengthMap = LengthMap.lower_bound_si(isl::dim::out, 0, 0);
LengthMap = LengthMap.align_params(SubscriptMap.get_space());
SubscriptMap = SubscriptMap.align_params(LengthMap.get_space());
LengthMap = LengthMap.sum(SubscriptMap);
AccessRelation =
LengthMap.set_tuple_id(isl::dim::in, getStatement()->getDomainId());
}
void MemoryAccess::computeBoundsOnAccessRelation(unsigned ElementSize) {
ScalarEvolution *SE = Statement->getParent()->getSE();
auto MAI = MemAccInst(getAccessInstruction());
if (isa<MemIntrinsic>(MAI))
return;
Value *Ptr = MAI.getPointerOperand();
if (!Ptr || !SE->isSCEVable(Ptr->getType()))
return;
auto *PtrSCEV = SE->getSCEV(Ptr);
if (isa<SCEVCouldNotCompute>(PtrSCEV))
return;
auto *BasePtrSCEV = SE->getPointerBase(PtrSCEV);
if (BasePtrSCEV && !isa<SCEVCouldNotCompute>(BasePtrSCEV))
PtrSCEV = SE->getMinusSCEV(PtrSCEV, BasePtrSCEV);
const ConstantRange &Range = SE->getSignedRange(PtrSCEV);
if (Range.isFullSet())
return;
if (Range.isWrappedSet() || Range.isSignWrappedSet())
return;
bool isWrapping = Range.isSignWrappedSet();
unsigned BW = Range.getBitWidth();
const auto One = APInt(BW, 1);
const auto LB = isWrapping ? Range.getLower() : Range.getSignedMin();
const auto UB = isWrapping ? (Range.getUpper() - One) : Range.getSignedMax();
auto Min = LB.sdiv(APInt(BW, ElementSize));
auto Max = UB.sdiv(APInt(BW, ElementSize)) + One;
assert(Min.sle(Max) && "Minimum expected to be less or equal than max");
isl::map Relation = AccessRelation;
isl::set AccessRange = Relation.range();
AccessRange = addRangeBoundsToSet(AccessRange, ConstantRange(Min, Max), 0,
isl::dim::set);
AccessRelation = Relation.intersect_range(AccessRange);
}
void MemoryAccess::foldAccessRelation() {
if (Sizes.size() < 2 || isa<SCEVConstant>(Sizes[1]))
return;
int Size = Subscripts.size();
isl::map NewAccessRelation = AccessRelation;
for (int i = Size - 2; i >= 0; --i) {
isl::space Space;
isl::map MapOne, MapTwo;
isl::pw_aff DimSize = getPwAff(Sizes[i + 1]);
isl::space SpaceSize = DimSize.get_space();
isl::id ParamId = SpaceSize.get_dim_id(isl::dim::param, 0);
Space = AccessRelation.get_space();
Space = Space.range().map_from_set();
Space = Space.align_params(SpaceSize);
int ParamLocation = Space.find_dim_by_id(isl::dim::param, ParamId);
MapOne = isl::map::universe(Space);
for (int j = 0; j < Size; ++j)
MapOne = MapOne.equate(isl::dim::in, j, isl::dim::out, j);
MapOne = MapOne.lower_bound_si(isl::dim::in, i + 1, 0);
MapTwo = isl::map::universe(Space);
for (int j = 0; j < Size; ++j)
if (j < i || j > i + 1)
MapTwo = MapTwo.equate(isl::dim::in, j, isl::dim::out, j);
isl::local_space LS(Space);
isl::constraint C;
C = isl::constraint::alloc_equality(LS);
C = C.set_constant_si(-1);
C = C.set_coefficient_si(isl::dim::in, i, 1);
C = C.set_coefficient_si(isl::dim::out, i, -1);
MapTwo = MapTwo.add_constraint(C);
C = isl::constraint::alloc_equality(LS);
C = C.set_coefficient_si(isl::dim::in, i + 1, 1);
C = C.set_coefficient_si(isl::dim::out, i + 1, -1);
C = C.set_coefficient_si(isl::dim::param, ParamLocation, 1);
MapTwo = MapTwo.add_constraint(C);
MapTwo = MapTwo.upper_bound_si(isl::dim::in, i + 1, -1);
MapOne = MapOne.unite(MapTwo);
NewAccessRelation = NewAccessRelation.apply_range(MapOne);
}
isl::id BaseAddrId = getScopArrayInfo()->getBasePtrId();
isl::space Space = Statement->getDomainSpace();
NewAccessRelation = NewAccessRelation.set_tuple_id(
isl::dim::in, Space.get_tuple_id(isl::dim::set));
NewAccessRelation = NewAccessRelation.set_tuple_id(isl::dim::out, BaseAddrId);
NewAccessRelation = NewAccessRelation.gist_domain(Statement->getDomain());
// Access dimension folding might in certain cases increase the number of
// disjuncts in the memory access, which can possibly complicate the generated
// run-time checks and can lead to costly compilation.
if (!PollyPreciseFoldAccesses &&
NewAccessRelation.n_basic_map() > AccessRelation.n_basic_map()) {
} else {
AccessRelation = NewAccessRelation;
}
}
/// Check if @p Expr is divisible by @p Size.
static bool isDivisible(const SCEV *Expr, unsigned Size, ScalarEvolution &SE) {
assert(Size != 0);
if (Size == 1)
return true;
// Only one factor needs to be divisible.
if (auto *MulExpr = dyn_cast<SCEVMulExpr>(Expr)) {
for (auto *FactorExpr : MulExpr->operands())
if (isDivisible(FactorExpr, Size, SE))
return true;
return false;
}
// For other n-ary expressions (Add, AddRec, Max,...) all operands need
// to be divisible.
if (auto *NAryExpr = dyn_cast<SCEVNAryExpr>(Expr)) {
for (auto *OpExpr : NAryExpr->operands())
if (!isDivisible(OpExpr, Size, SE))
return false;
return true;
}
auto *SizeSCEV = SE.getConstant(Expr->getType(), Size);
auto *UDivSCEV = SE.getUDivExpr(Expr, SizeSCEV);
auto *MulSCEV = SE.getMulExpr(UDivSCEV, SizeSCEV);
return MulSCEV == Expr;
}
void MemoryAccess::buildAccessRelation(const ScopArrayInfo *SAI) {
assert(AccessRelation.is_null() && "AccessRelation already built");
// Initialize the invalid domain which describes all iterations for which the
// access relation is not modeled correctly.
isl::set StmtInvalidDomain = getStatement()->getInvalidDomain();
InvalidDomain = isl::set::empty(StmtInvalidDomain.get_space());
isl::ctx Ctx = Id.get_ctx();
isl::id BaseAddrId = SAI->getBasePtrId();
if (getAccessInstruction() && isa<MemIntrinsic>(getAccessInstruction())) {
buildMemIntrinsicAccessRelation();
AccessRelation = AccessRelation.set_tuple_id(isl::dim::out, BaseAddrId);
return;
}
if (!isAffine()) {
// We overapproximate non-affine accesses with a possible access to the
// whole array. For read accesses it does not make a difference, if an
// access must or may happen. However, for write accesses it is important to
// differentiate between writes that must happen and writes that may happen.
if (AccessRelation.is_null())
AccessRelation = createBasicAccessMap(Statement);
AccessRelation = AccessRelation.set_tuple_id(isl::dim::out, BaseAddrId);
return;
}
isl::space Space = isl::space(Ctx, 0, Statement->getNumIterators(), 0);
AccessRelation = isl::map::universe(Space);
for (int i = 0, Size = Subscripts.size(); i < Size; ++i) {
isl::pw_aff Affine = getPwAff(Subscripts[i]);
isl::map SubscriptMap = isl::map::from_pw_aff(Affine);
AccessRelation = AccessRelation.flat_range_product(SubscriptMap);
}
Space = Statement->getDomainSpace();
AccessRelation = AccessRelation.set_tuple_id(
isl::dim::in, Space.get_tuple_id(isl::dim::set));
AccessRelation = AccessRelation.set_tuple_id(isl::dim::out, BaseAddrId);
AccessRelation = AccessRelation.gist_domain(Statement->getDomain());
}
MemoryAccess::MemoryAccess(ScopStmt *Stmt, Instruction *AccessInst,
AccessType AccType, Value *BaseAddress,
Type *ElementType, bool Affine,
ArrayRef<const SCEV *> Subscripts,
ArrayRef<const SCEV *> Sizes, Value *AccessValue,
MemoryKind Kind)
: Kind(Kind), AccType(AccType), Statement(Stmt), InvalidDomain(nullptr),
BaseAddr(BaseAddress), ElementType(ElementType),
Sizes(Sizes.begin(), Sizes.end()), AccessInstruction(AccessInst),
AccessValue(AccessValue), IsAffine(Affine),
Subscripts(Subscripts.begin(), Subscripts.end()), AccessRelation(nullptr),
NewAccessRelation(nullptr), FAD(nullptr) {
static const std::string TypeStrings[] = {"", "_Read", "_Write", "_MayWrite"};
const std::string Access = TypeStrings[AccType] + utostr(Stmt->size());
std::string IdName = Stmt->getBaseName() + Access;
Id = isl::id::alloc(Stmt->getParent()->getIslCtx(), IdName, this);
}
MemoryAccess::MemoryAccess(ScopStmt *Stmt, AccessType AccType, isl::map AccRel)
: Kind(MemoryKind::Array), AccType(AccType), Statement(Stmt),
InvalidDomain(nullptr), AccessRelation(nullptr),
NewAccessRelation(AccRel), FAD(nullptr) {
isl::id ArrayInfoId = NewAccessRelation.get_tuple_id(isl::dim::out);
auto *SAI = ScopArrayInfo::getFromId(ArrayInfoId);
Sizes.push_back(nullptr);
for (unsigned i = 1; i < SAI->getNumberOfDimensions(); i++)
Sizes.push_back(SAI->getDimensionSize(i));
ElementType = SAI->getElementType();
BaseAddr = SAI->getBasePtr();
static const std::string TypeStrings[] = {"", "_Read", "_Write", "_MayWrite"};
const std::string Access = TypeStrings[AccType] + utostr(Stmt->size());
std::string IdName = Stmt->getBaseName() + Access;
Id = isl::id::alloc(Stmt->getParent()->getIslCtx(), IdName, this);
}
MemoryAccess::~MemoryAccess() = default;
void MemoryAccess::realignParams() {
isl::set Ctx = Statement->getParent()->getContext();
InvalidDomain = InvalidDomain.gist_params(Ctx);
AccessRelation = AccessRelation.gist_params(Ctx);
}
const std::string MemoryAccess::getReductionOperatorStr() const {
return MemoryAccess::getReductionOperatorStr(getReductionType());
}
isl::id MemoryAccess::getId() const { return Id; }
raw_ostream &polly::operator<<(raw_ostream &OS,
MemoryAccess::ReductionType RT) {
if (RT == MemoryAccess::RT_NONE)
OS << "NONE";
else
OS << MemoryAccess::getReductionOperatorStr(RT);
return OS;
}
void MemoryAccess::setFortranArrayDescriptor(Value *FAD) { this->FAD = FAD; }
void MemoryAccess::print(raw_ostream &OS) const {
switch (AccType) {
case READ:
OS.indent(12) << "ReadAccess :=\t";
break;
case MUST_WRITE:
OS.indent(12) << "MustWriteAccess :=\t";
break;
case MAY_WRITE:
OS.indent(12) << "MayWriteAccess :=\t";
break;
}
OS << "[Reduction Type: " << getReductionType() << "] ";
if (FAD) {
OS << "[Fortran array descriptor: " << FAD->getName();
OS << "] ";
};
OS << "[Scalar: " << isScalarKind() << "]\n";
OS.indent(16) << getOriginalAccessRelationStr() << ";\n";
if (hasNewAccessRelation())
OS.indent(11) << "new: " << getNewAccessRelationStr() << ";\n";
}
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
LLVM_DUMP_METHOD void MemoryAccess::dump() const { print(errs()); }
#endif
isl::pw_aff MemoryAccess::getPwAff(const SCEV *E) {
auto *Stmt = getStatement();
PWACtx PWAC = Stmt->getParent()->getPwAff(E, Stmt->getEntryBlock());
isl::set StmtDom = getStatement()->getDomain();
StmtDom = StmtDom.reset_tuple_id();
isl::set NewInvalidDom = StmtDom.intersect(PWAC.second);
InvalidDomain = InvalidDomain.unite(NewInvalidDom);
return PWAC.first;
}
// Create a map in the size of the provided set domain, that maps from the
// one element of the provided set domain to another element of the provided
// set domain.
// The mapping is limited to all points that are equal in all but the last
// dimension and for which the last dimension of the input is strict smaller
// than the last dimension of the output.
//
// getEqualAndLarger(set[i0, i1, ..., iX]):
//
// set[i0, i1, ..., iX] -> set[o0, o1, ..., oX]
// : i0 = o0, i1 = o1, ..., i(X-1) = o(X-1), iX < oX
//
static isl::map getEqualAndLarger(isl::space SetDomain) {
isl::space Space = SetDomain.map_from_set();
isl::map Map = isl::map::universe(Space);
unsigned lastDimension = Map.dim(isl::dim::in) - 1;
// Set all but the last dimension to be equal for the input and output
//
// input[i0, i1, ..., iX] -> output[o0, o1, ..., oX]
// : i0 = o0, i1 = o1, ..., i(X-1) = o(X-1)
for (unsigned i = 0; i < lastDimension; ++i)
Map = Map.equate(isl::dim::in, i, isl::dim::out, i);
// Set the last dimension of the input to be strict smaller than the
// last dimension of the output.
//
// input[?,?,?,...,iX] -> output[?,?,?,...,oX] : iX < oX
Map = Map.order_lt(isl::dim::in, lastDimension, isl::dim::out, lastDimension);
return Map;
}
isl::set MemoryAccess::getStride(isl::map Schedule) const {
isl::map AccessRelation = getAccessRelation();
isl::space Space = Schedule.get_space().range();
isl::map NextScatt = getEqualAndLarger(Space);
Schedule = Schedule.reverse();
NextScatt = NextScatt.lexmin();
NextScatt = NextScatt.apply_range(Schedule);
NextScatt = NextScatt.apply_range(AccessRelation);
NextScatt = NextScatt.apply_domain(Schedule);
NextScatt = NextScatt.apply_domain(AccessRelation);
isl::set Deltas = NextScatt.deltas();
return Deltas;
}
bool MemoryAccess::isStrideX(isl::map Schedule, int StrideWidth) const {
isl::set Stride, StrideX;
bool IsStrideX;
Stride = getStride(Schedule);
StrideX = isl::set::universe(Stride.get_space());
for (unsigned i = 0; i < StrideX.dim(isl::dim::set) - 1; i++)
StrideX = StrideX.fix_si(isl::dim::set, i, 0);
StrideX = StrideX.fix_si(isl::dim::set, StrideX.dim(isl::dim::set) - 1,
StrideWidth);
IsStrideX = Stride.is_subset(StrideX);
return IsStrideX;
}
bool MemoryAccess::isStrideZero(isl::map Schedule) const {
return isStrideX(Schedule, 0);
}
bool MemoryAccess::isStrideOne(isl::map Schedule) const {
return isStrideX(Schedule, 1);
}
void MemoryAccess::setAccessRelation(isl::map NewAccess) {
AccessRelation = NewAccess;
}
void MemoryAccess::setNewAccessRelation(isl::map NewAccess) {
assert(NewAccess);
#ifndef NDEBUG
// Check domain space compatibility.
isl::space NewSpace = NewAccess.get_space();
isl::space NewDomainSpace = NewSpace.domain();
isl::space OriginalDomainSpace = getStatement()->getDomainSpace();
assert(OriginalDomainSpace.has_equal_tuples(NewDomainSpace));
// Reads must be executed unconditionally. Writes might be executed in a
// subdomain only.
if (isRead()) {
// Check whether there is an access for every statement instance.
isl::set StmtDomain = getStatement()->getDomain();
StmtDomain =
StmtDomain.intersect_params(getStatement()->getParent()->getContext());
isl::set NewDomain = NewAccess.domain();
assert(StmtDomain.is_subset(NewDomain) &&
"Partial READ accesses not supported");
}
isl::space NewAccessSpace = NewAccess.get_space();
assert(NewAccessSpace.has_tuple_id(isl::dim::set) &&
"Must specify the array that is accessed");
isl::id NewArrayId = NewAccessSpace.get_tuple_id(isl::dim::set);
auto *SAI = static_cast<ScopArrayInfo *>(NewArrayId.get_user());
assert(SAI && "Must set a ScopArrayInfo");
if (SAI->isArrayKind() && SAI->getBasePtrOriginSAI()) {
InvariantEquivClassTy *EqClass =
getStatement()->getParent()->lookupInvariantEquivClass(
SAI->getBasePtr());
assert(EqClass &&
"Access functions to indirect arrays must have an invariant and "
"hoisted base pointer");
}
// Check whether access dimensions correspond to number of dimensions of the
// accesses array.
auto Dims = SAI->getNumberOfDimensions();
assert(NewAccessSpace.dim(isl::dim::set) == Dims &&
"Access dims must match array dims");
#endif
NewAccess = NewAccess.gist_domain(getStatement()->getDomain());
NewAccessRelation = NewAccess;
}
bool MemoryAccess::isLatestPartialAccess() const {
isl::set StmtDom = getStatement()->getDomain();
isl::set AccDom = getLatestAccessRelation().domain();
return !StmtDom.is_subset(AccDom);
}
//===----------------------------------------------------------------------===//
isl::map ScopStmt::getSchedule() const {
isl::set Domain = getDomain();
if (Domain.is_empty())
return isl::map::from_aff(isl::aff(isl::local_space(getDomainSpace())));
auto Schedule = getParent()->getSchedule();
if (!Schedule)
return nullptr;
Schedule = Schedule.intersect_domain(isl::union_set(Domain));
if (Schedule.is_empty())
return isl::map::from_aff(isl::aff(isl::local_space(getDomainSpace())));
isl::map M = M.from_union_map(Schedule);
M = M.coalesce();
M = M.gist_domain(Domain);
M = M.coalesce();
return M;
}
void ScopStmt::restrictDomain(isl::set NewDomain) {
assert(NewDomain.is_subset(Domain) &&
"New domain is not a subset of old domain!");
Domain = NewDomain;
}
void ScopStmt::addAccess(MemoryAccess *Access, bool Prepend) {
Instruction *AccessInst = Access->getAccessInstruction();
if (Access->isArrayKind()) {
MemoryAccessList &MAL = InstructionToAccess[AccessInst];
MAL.emplace_front(Access);
} else if (Access->isValueKind() && Access->isWrite()) {
Instruction *AccessVal = cast<Instruction>(Access->getAccessValue());
assert(!ValueWrites.lookup(AccessVal));
ValueWrites[AccessVal] = Access;
} else if (Access->isValueKind() && Access->isRead()) {
Value *AccessVal = Access->getAccessValue();
assert(!ValueReads.lookup(AccessVal));
ValueReads[AccessVal] = Access;
} else if (Access->isAnyPHIKind() && Access->isWrite()) {
PHINode *PHI = cast<PHINode>(Access->getAccessValue());
assert(!PHIWrites.lookup(PHI));
PHIWrites[PHI] = Access;
} else if (Access->isAnyPHIKind() && Access->isRead()) {
PHINode *PHI = cast<PHINode>(Access->getAccessValue());
assert(!PHIReads.lookup(PHI));
PHIReads[PHI] = Access;
}
if (Prepend) {
MemAccs.insert(MemAccs.begin(), Access);
return;
}
MemAccs.push_back(Access);
}
void ScopStmt::realignParams() {
for (MemoryAccess *MA : *this)
MA->realignParams();
isl::set Ctx = Parent.getContext();
InvalidDomain = InvalidDomain.gist_params(Ctx);
Domain = Domain.gist_params(Ctx);
}
/// Add @p BSet to set @p BoundedParts if @p BSet is bounded.
static isl::set collectBoundedParts(isl::set S) {
isl::set BoundedParts = isl::set::empty(S.get_space());
for (isl::basic_set BSet : S.get_basic_set_list())
if (BSet.is_bounded())
BoundedParts = BoundedParts.unite(isl::set(BSet));
return BoundedParts;
}
/// Compute the (un)bounded parts of @p S wrt. to dimension @p Dim.
///
/// @returns A separation of @p S into first an unbounded then a bounded subset,
/// both with regards to the dimension @p Dim.
static std::pair<isl::set, isl::set> partitionSetParts(isl::set S,
unsigned Dim) {
for (unsigned u = 0, e = S.n_dim(); u < e; u++)
S = S.lower_bound_si(isl::dim::set, u, 0);
unsigned NumDimsS = S.n_dim();
isl::set OnlyDimS = S;
// Remove dimensions that are greater than Dim as they are not interesting.
assert(NumDimsS >= Dim + 1);
OnlyDimS = OnlyDimS.project_out(isl::dim::set, Dim + 1, NumDimsS - Dim - 1);
// Create artificial parametric upper bounds for dimensions smaller than Dim
// as we are not interested in them.
OnlyDimS = OnlyDimS.insert_dims(isl::dim::param, 0, Dim);
for (unsigned u = 0; u < Dim; u++) {
isl::constraint C = isl::constraint::alloc_inequality(
isl::local_space(OnlyDimS.get_space()));
C = C.set_coefficient_si(isl::dim::param, u, 1);
C = C.set_coefficient_si(isl::dim::set, u, -1);
OnlyDimS = OnlyDimS.add_constraint(C);
}
// Collect all bounded parts of OnlyDimS.
isl::set BoundedParts = collectBoundedParts(OnlyDimS);
// Create the dimensions greater than Dim again.
BoundedParts =
BoundedParts.insert_dims(isl::dim::set, Dim + 1, NumDimsS - Dim - 1);
// Remove the artificial upper bound parameters again.
BoundedParts = BoundedParts.remove_dims(isl::dim::param, 0, Dim);
isl::set UnboundedParts = S.subtract(BoundedParts);
return std::make_pair(UnboundedParts, BoundedParts);
}
/// Create the conditions under which @p L @p Pred @p R is true.
static isl::set buildConditionSet(ICmpInst::Predicate Pred, isl::pw_aff L,
isl::pw_aff R) {
switch (Pred) {
case ICmpInst::ICMP_EQ:
return L.eq_set(R);
case ICmpInst::ICMP_NE:
return L.ne_set(R);
case ICmpInst::ICMP_SLT:
return L.lt_set(R);
case ICmpInst::ICMP_SLE:
return L.le_set(R);
case ICmpInst::ICMP_SGT:
return L.gt_set(R);
case ICmpInst::ICMP_SGE:
return L.ge_set(R);
case ICmpInst::ICMP_ULT:
return L.lt_set(R);
case ICmpInst::ICMP_UGT:
return L.gt_set(R);
case ICmpInst::ICMP_ULE:
return L.le_set(R);
case ICmpInst::ICMP_UGE:
return L.ge_set(R);
default:
llvm_unreachable("Non integer predicate not supported");
}
}
/// Compute the isl representation for the SCEV @p E in this BB.
///
/// @param S The Scop in which @p BB resides in.
/// @param BB The BB for which isl representation is to be
/// computed.
/// @param InvalidDomainMap A map of BB to their invalid domains.
/// @param E The SCEV that should be translated.
/// @param NonNegative Flag to indicate the @p E has to be non-negative.
///
/// Note that this function will also adjust the invalid context accordingly.
__isl_give isl_pw_aff *
getPwAff(Scop &S, BasicBlock *BB,
DenseMap<BasicBlock *, isl::set> &InvalidDomainMap, const SCEV *E,
bool NonNegative = false) {
PWACtx PWAC = S.getPwAff(E, BB, NonNegative);
InvalidDomainMap[BB] = InvalidDomainMap[BB].unite(PWAC.second);
return PWAC.first.release();
}
/// Build the conditions sets for the switch @p SI in the @p Domain.
///
/// This will fill @p ConditionSets with the conditions under which control
/// will be moved from @p SI to its successors. Hence, @p ConditionSets will
/// have as many elements as @p SI has successors.
bool buildConditionSets(Scop &S, BasicBlock *BB, SwitchInst *SI, Loop *L,
__isl_keep isl_set *Domain,
DenseMap<BasicBlock *, isl::set> &InvalidDomainMap,
SmallVectorImpl<__isl_give isl_set *> &ConditionSets) {
Value *Condition = getConditionFromTerminator(SI);
assert(Condition && "No condition for switch");
ScalarEvolution &SE = *S.getSE();
isl_pw_aff *LHS, *RHS;
LHS = getPwAff(S, BB, InvalidDomainMap, SE.getSCEVAtScope(Condition, L));
unsigned NumSuccessors = SI->getNumSuccessors();
ConditionSets.resize(NumSuccessors);
for (auto &Case : SI->cases()) {
unsigned Idx = Case.getSuccessorIndex();
ConstantInt *CaseValue = Case.getCaseValue();
RHS = getPwAff(S, BB, InvalidDomainMap, SE.getSCEV(CaseValue));
isl_set *CaseConditionSet =
buildConditionSet(ICmpInst::ICMP_EQ, isl::manage_copy(LHS),
isl::manage(RHS))
.release();
ConditionSets[Idx] = isl_set_coalesce(
isl_set_intersect(CaseConditionSet, isl_set_copy(Domain)));
}
assert(ConditionSets[0] == nullptr && "Default condition set was set");
isl_set *ConditionSetUnion = isl_set_copy(ConditionSets[1]);
for (unsigned u = 2; u < NumSuccessors; u++)
ConditionSetUnion =
isl_set_union(ConditionSetUnion, isl_set_copy(ConditionSets[u]));
ConditionSets[0] = isl_set_subtract(isl_set_copy(Domain), ConditionSetUnion);
isl_pw_aff_free(LHS);
return true;
}
/// Build condition sets for unsigned ICmpInst(s).
/// Special handling is required for unsigned operands to ensure that if
/// MSB (aka the Sign bit) is set for an operands in an unsigned ICmpInst
/// it should wrap around.
///
/// @param IsStrictUpperBound holds information on the predicate relation
/// between TestVal and UpperBound, i.e,
/// TestVal < UpperBound OR TestVal <= UpperBound
__isl_give isl_set *
buildUnsignedConditionSets(Scop &S, BasicBlock *BB, Value *Condition,
__isl_keep isl_set *Domain, const SCEV *SCEV_TestVal,
const SCEV *SCEV_UpperBound,
DenseMap<BasicBlock *, isl::set> &InvalidDomainMap,
bool IsStrictUpperBound) {
// Do not take NonNeg assumption on TestVal
// as it might have MSB (Sign bit) set.
isl_pw_aff *TestVal = getPwAff(S, BB, InvalidDomainMap, SCEV_TestVal, false);
// Take NonNeg assumption on UpperBound.
isl_pw_aff *UpperBound =
getPwAff(S, BB, InvalidDomainMap, SCEV_UpperBound, true);
// 0 <= TestVal
isl_set *First =
isl_pw_aff_le_set(isl_pw_aff_zero_on_domain(isl_local_space_from_space(
isl_pw_aff_get_domain_space(TestVal))),
isl_pw_aff_copy(TestVal));
isl_set *Second;
if (IsStrictUpperBound)
// TestVal < UpperBound
Second = isl_pw_aff_lt_set(TestVal, UpperBound);
else
// TestVal <= UpperBound
Second = isl_pw_aff_le_set(TestVal, UpperBound);
isl_set *ConsequenceCondSet = isl_set_intersect(First, Second);
return ConsequenceCondSet;
}
/// Build the conditions sets for the branch condition @p Condition in
/// the @p Domain.
///
/// This will fill @p ConditionSets with the conditions under which control
/// will be moved from @p TI to its successors. Hence, @p ConditionSets will
/// have as many elements as @p TI has successors. If @p TI is nullptr the
/// context under which @p Condition is true/false will be returned as the
/// new elements of @p ConditionSets.
bool buildConditionSets(Scop &S, BasicBlock *BB, Value *Condition,
TerminatorInst *TI, Loop *L, __isl_keep isl_set *Domain,
DenseMap<BasicBlock *, isl::set> &InvalidDomainMap,
SmallVectorImpl<__isl_give isl_set *> &ConditionSets) {
ScalarEvolution &SE = *S.getSE();
isl_set *ConsequenceCondSet = nullptr;
if (auto Load = dyn_cast<LoadInst>(Condition)) {
const SCEV *LHSSCEV = SE.getSCEVAtScope(Load, L);
const SCEV *RHSSCEV = SE.getZero(LHSSCEV->getType());
bool NonNeg = false;
isl_pw_aff *LHS = getPwAff(S, BB, InvalidDomainMap, LHSSCEV, NonNeg);
isl_pw_aff *RHS = getPwAff(S, BB, InvalidDomainMap, RHSSCEV, NonNeg);
ConsequenceCondSet = buildConditionSet(ICmpInst::ICMP_SLE, isl::manage(LHS),
isl::manage(RHS))
.release();
} else if (auto *PHI = dyn_cast<PHINode>(Condition)) {
auto *Unique = dyn_cast<ConstantInt>(
getUniqueNonErrorValue(PHI, &S.getRegion(), *S.getLI(), *S.getDT()));
if (Unique->isZero())
ConsequenceCondSet = isl_set_empty(isl_set_get_space(Domain));
else
ConsequenceCondSet = isl_set_universe(isl_set_get_space(Domain));
} else if (auto *CCond = dyn_cast<ConstantInt>(Condition)) {
if (CCond->isZero())
ConsequenceCondSet = isl_set_empty(isl_set_get_space(Domain));
else
ConsequenceCondSet = isl_set_universe(isl_set_get_space(Domain));
} else if (BinaryOperator *BinOp = dyn_cast<BinaryOperator>(Condition)) {
auto Opcode = BinOp->getOpcode();
assert(Opcode == Instruction::And || Opcode == Instruction::Or);
bool Valid = buildConditionSets(S, BB, BinOp->getOperand(0), TI, L, Domain,
InvalidDomainMap, ConditionSets) &&
buildConditionSets(S, BB, BinOp->getOperand(1), TI, L, Domain,
InvalidDomainMap, ConditionSets);
if (!Valid) {
while (!ConditionSets.empty())
isl_set_free(ConditionSets.pop_back_val());
return false;
}
isl_set_free(ConditionSets.pop_back_val());
isl_set *ConsCondPart0 = ConditionSets.pop_back_val();
isl_set_free(ConditionSets.pop_back_val());
isl_set *ConsCondPart1 = ConditionSets.pop_back_val();
if (Opcode == Instruction::And)
ConsequenceCondSet = isl_set_intersect(ConsCondPart0, ConsCondPart1);
else
ConsequenceCondSet = isl_set_union(ConsCondPart0, ConsCondPart1);
} else {
auto *ICond = dyn_cast<ICmpInst>(Condition);
assert(ICond &&
"Condition of exiting branch was neither constant nor ICmp!");
LoopInfo &LI = *S.getLI();
DominatorTree &DT = *S.getDT();
Region &R = S.getRegion();
isl_pw_aff *LHS, *RHS;
// For unsigned comparisons we assumed the signed bit of neither operand
// to be set. The comparison is equal to a signed comparison under this
// assumption.
bool NonNeg = ICond->isUnsigned();
const SCEV *LeftOperand = SE.getSCEVAtScope(ICond->getOperand(0), L),
*RightOperand = SE.getSCEVAtScope(ICond->getOperand(1), L);
LeftOperand = tryForwardThroughPHI(LeftOperand, R, SE, LI, DT);
RightOperand = tryForwardThroughPHI(RightOperand, R, SE, LI, DT);
switch (ICond->getPredicate()) {
case ICmpInst::ICMP_ULT:
ConsequenceCondSet =
buildUnsignedConditionSets(S, BB, Condition, Domain, LeftOperand,
RightOperand, InvalidDomainMap, true);
break;
case ICmpInst::ICMP_ULE:
ConsequenceCondSet =
buildUnsignedConditionSets(S, BB, Condition, Domain, LeftOperand,
RightOperand, InvalidDomainMap, false);
break;
case ICmpInst::ICMP_UGT:
ConsequenceCondSet =
buildUnsignedConditionSets(S, BB, Condition, Domain, RightOperand,
LeftOperand, InvalidDomainMap, true);
break;
case ICmpInst::ICMP_UGE:
ConsequenceCondSet =
buildUnsignedConditionSets(S, BB, Condition, Domain, RightOperand,
LeftOperand, InvalidDomainMap, false);
break;
default:
LHS = getPwAff(S, BB, InvalidDomainMap, LeftOperand, NonNeg);
RHS = getPwAff(S, BB, InvalidDomainMap, RightOperand, NonNeg);
ConsequenceCondSet = buildConditionSet(ICond->getPredicate(),
isl::manage(LHS), isl::manage(RHS))
.release();
break;
}
}
// If no terminator was given we are only looking for parameter constraints
// under which @p Condition is true/false.
if (!TI)
ConsequenceCondSet = isl_set_params(ConsequenceCondSet);
assert(ConsequenceCondSet);
ConsequenceCondSet = isl_set_coalesce(
isl_set_intersect(ConsequenceCondSet, isl_set_copy(Domain)));
isl_set *AlternativeCondSet = nullptr;
bool TooComplex =
isl_set_n_basic_set(ConsequenceCondSet) >= MaxDisjunctsInDomain;
if (!TooComplex) {
AlternativeCondSet = isl_set_subtract(isl_set_copy(Domain),
isl_set_copy(ConsequenceCondSet));
TooComplex =
isl_set_n_basic_set(AlternativeCondSet) >= MaxDisjunctsInDomain;
}
if (TooComplex) {
S.invalidate(COMPLEXITY, TI ? TI->getDebugLoc() : DebugLoc(),
TI ? TI->getParent() : nullptr /* BasicBlock */);
isl_set_free(AlternativeCondSet);
isl_set_free(ConsequenceCondSet);
return false;
}
ConditionSets.push_back(ConsequenceCondSet);
ConditionSets.push_back(isl_set_coalesce(AlternativeCondSet));
return true;
}
/// Build the conditions sets for the terminator @p TI in the @p Domain.
///
/// This will fill @p ConditionSets with the conditions under which control
/// will be moved from @p TI to its successors. Hence, @p ConditionSets will
/// have as many elements as @p TI has successors.
bool buildConditionSets(Scop &S, BasicBlock *BB, TerminatorInst *TI, Loop *L,
__isl_keep isl_set *Domain,
DenseMap<BasicBlock *, isl::set> &InvalidDomainMap,
SmallVectorImpl<__isl_give isl_set *> &ConditionSets) {
if (SwitchInst *SI = dyn_cast<SwitchInst>(TI))
return buildConditionSets(S, BB, SI, L, Domain, InvalidDomainMap,
ConditionSets);
assert(isa<BranchInst>(TI) && "Terminator was neither branch nor switch.");
if (TI->getNumSuccessors() == 1) {
ConditionSets.push_back(isl_set_copy(Domain));
return true;
}
Value *Condition = getConditionFromTerminator(TI);
assert(Condition && "No condition for Terminator");
return buildConditionSets(S, BB, Condition, TI, L, Domain, InvalidDomainMap,
ConditionSets);
}
ScopStmt::ScopStmt(Scop &parent, Region &R, StringRef Name,
Loop *SurroundingLoop,
std::vector<Instruction *> EntryBlockInstructions)
: Parent(parent), InvalidDomain(nullptr), Domain(nullptr), R(&R),
Build(nullptr), BaseName(Name), SurroundingLoop(SurroundingLoop),
Instructions(EntryBlockInstructions) {}
ScopStmt::ScopStmt(Scop &parent, BasicBlock &bb, StringRef Name,
Loop *SurroundingLoop,
std::vector<Instruction *> Instructions)
: Parent(parent), InvalidDomain(nullptr), Domain(nullptr), BB(&bb),
Build(nullptr), BaseName(Name), SurroundingLoop(SurroundingLoop),
Instructions(Instructions) {}
ScopStmt::ScopStmt(Scop &parent, isl::map SourceRel, isl::map TargetRel,
isl::set NewDomain)
: Parent(parent), InvalidDomain(nullptr), Domain(NewDomain),
Build(nullptr) {
BaseName = getIslCompatibleName("CopyStmt_", "",
std::to_string(parent.getCopyStmtsNum()));
isl::id Id = isl::id::alloc(getIslCtx(), getBaseName(), this);
Domain = Domain.set_tuple_id(Id);
TargetRel = TargetRel.set_tuple_id(isl::dim::in, Id);
auto *Access =
new MemoryAccess(this, MemoryAccess::AccessType::MUST_WRITE, TargetRel);
parent.addAccessFunction(Access);
addAccess(Access);
SourceRel = SourceRel.set_tuple_id(isl::dim::in, Id);
Access = new MemoryAccess(this, MemoryAccess::AccessType::READ, SourceRel);
parent.addAccessFunction(Access);
addAccess(Access);
}
ScopStmt::~ScopStmt() = default;
std::string ScopStmt::getDomainStr() const { return Domain.to_str(); }
std::string ScopStmt::getScheduleStr() const {
auto *S = getSchedule().release();
if (!S)
return {};
auto Str = stringFromIslObj(S);
isl_map_free(S);
return Str;
}
void ScopStmt::setInvalidDomain(isl::set ID) { InvalidDomain = ID; }
BasicBlock *ScopStmt::getEntryBlock() const {
if (isBlockStmt())
return getBasicBlock();
return getRegion()->getEntry();
}
unsigned ScopStmt::getNumIterators() const { return NestLoops.size(); }
const char *ScopStmt::getBaseName() const { return BaseName.c_str(); }
Loop *ScopStmt::getLoopForDimension(unsigned Dimension) const {
return NestLoops[Dimension];
}
isl::ctx ScopStmt::getIslCtx() const { return Parent.getIslCtx(); }
isl::set ScopStmt::getDomain() const { return Domain; }
isl::space ScopStmt::getDomainSpace() const { return Domain.get_space(); }
isl::id ScopStmt::getDomainId() const { return Domain.get_tuple_id(); }
void ScopStmt::printInstructions(raw_ostream &OS) const {
OS << "Instructions {\n";
for (Instruction *Inst : Instructions)
OS.indent(16) << *Inst << "\n";
OS.indent(12) << "}\n";
}
void ScopStmt::print(raw_ostream &OS, bool PrintInstructions) const {
OS << "\t" << getBaseName() << "\n";
OS.indent(12) << "Domain :=\n";
if (Domain) {
OS.indent(16) << getDomainStr() << ";\n";
} else
OS.indent(16) << "n/a\n";
OS.indent(12) << "Schedule :=\n";
if (Domain) {
OS.indent(16) << getScheduleStr() << ";\n";
} else
OS.indent(16) << "n/a\n";
for (MemoryAccess *Access : MemAccs)
Access->print(OS);
if (PrintInstructions)
printInstructions(OS.indent(12));
}
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
LLVM_DUMP_METHOD void ScopStmt::dump() const { print(dbgs(), true); }
#endif
void ScopStmt::removeAccessData(MemoryAccess *MA) {
if (MA->isRead() && MA->isOriginalValueKind()) {
bool Found = ValueReads.erase(MA->getAccessValue());
(void)Found;
assert(Found && "Expected access data not found");
}
if (MA->isWrite() && MA->isOriginalValueKind()) {
bool Found = ValueWrites.erase(cast<Instruction>(MA->getAccessValue()));
(void)Found;
assert(Found && "Expected access data not found");
}
if (MA->isWrite() && MA->isOriginalAnyPHIKind()) {
bool Found = PHIWrites.erase(cast<PHINode>(MA->getAccessInstruction()));
(void)Found;
assert(Found && "Expected access data not found");
}
if (MA->isRead() && MA->isOriginalAnyPHIKind()) {
bool Found = PHIReads.erase(cast<PHINode>(MA->getAccessInstruction()));
(void)Found;
assert(Found && "Expected access data not found");
}
}
void ScopStmt::removeMemoryAccess(MemoryAccess *MA) {
// Remove the memory accesses from this statement together with all scalar
// accesses that were caused by it. MemoryKind::Value READs have no access
// instruction, hence would not be removed by this function. However, it is
// only used for invariant LoadInst accesses, its arguments are always affine,
// hence synthesizable, and therefore there are no MemoryKind::Value READ
// accesses to be removed.
auto Predicate = [&](MemoryAccess *Acc) {
return Acc->getAccessInstruction() == MA->getAccessInstruction();
};
for (auto *MA : MemAccs) {
if (Predicate(MA)) {
removeAccessData(MA);
Parent.removeAccessData(MA);
}
}
MemAccs.erase(std::remove_if(MemAccs.begin(), MemAccs.end(), Predicate),
MemAccs.end());
InstructionToAccess.erase(MA->getAccessInstruction());
}
void ScopStmt::removeSingleMemoryAccess(MemoryAccess *MA, bool AfterHoisting) {
if (AfterHoisting) {
auto MAIt = std::find(MemAccs.begin(), MemAccs.end(), MA);
assert(MAIt != MemAccs.end());
MemAccs.erase(MAIt);
removeAccessData(MA);
Parent.removeAccessData(MA);
}
auto It = InstructionToAccess.find(MA->getAccessInstruction());
if (It != InstructionToAccess.end()) {
It->second.remove(MA);
if (It->second.empty())
InstructionToAccess.erase(MA->getAccessInstruction());
}
}
MemoryAccess *ScopStmt::ensureValueRead(Value *V) {
MemoryAccess *Access = lookupInputAccessOf(V);
if (Access)
return Access;
ScopArrayInfo *SAI =
Parent.getOrCreateScopArrayInfo(V, V->getType(), {}, MemoryKind::Value);
Access = new MemoryAccess(this, nullptr, MemoryAccess::READ, V, V->getType(),
true, {}, {}, V, MemoryKind::Value);
Parent.addAccessFunction(Access);
Access->buildAccessRelation(SAI);
addAccess(Access);
Parent.addAccessData(Access);
return Access;
}
raw_ostream &polly::operator<<(raw_ostream &OS, const ScopStmt &S) {
S.print(OS, PollyPrintInstructions);
return OS;
}
//===----------------------------------------------------------------------===//
/// Scop class implement
void Scop::setContext(isl::set NewContext) {
Context = NewContext.align_params(Context.get_space());
}
namespace {
/// Remap parameter values but keep AddRecs valid wrt. invariant loads.
struct SCEVSensitiveParameterRewriter
: public SCEVRewriteVisitor<SCEVSensitiveParameterRewriter> {
const ValueToValueMap &VMap;
public:
SCEVSensitiveParameterRewriter(const ValueToValueMap &VMap,
ScalarEvolution &SE)
: SCEVRewriteVisitor(SE), VMap(VMap) {}
static const SCEV *rewrite(const SCEV *E, ScalarEvolution &SE,
const ValueToValueMap &VMap) {
SCEVSensitiveParameterRewriter SSPR(VMap, SE);
return SSPR.visit(E);
}
const SCEV *visitAddRecExpr(const SCEVAddRecExpr *E) {
auto *Start = visit(E->getStart());
auto *AddRec = SE.getAddRecExpr(SE.getConstant(E->getType(), 0),
visit(E->getStepRecurrence(SE)),
E->getLoop(), SCEV::FlagAnyWrap);
return SE.getAddExpr(Start, AddRec);
}
const SCEV *visitUnknown(const SCEVUnknown *E) {
if (auto *NewValue = VMap.lookup(E->getValue()))
return SE.getUnknown(NewValue);
return E;
}
};
/// Check whether we should remap a SCEV expression.
struct SCEVFindInsideScop : public SCEVTraversal<SCEVFindInsideScop> {
const ValueToValueMap &VMap;
bool FoundInside = false;
const Scop *S;
public:
SCEVFindInsideScop(const ValueToValueMap &VMap, ScalarEvolution &SE,
const Scop *S)
: SCEVTraversal(*this), VMap(VMap), S(S) {}
static bool hasVariant(const SCEV *E, ScalarEvolution &SE,
const ValueToValueMap &VMap, const Scop *S) {
SCEVFindInsideScop SFIS(VMap, SE, S);
SFIS.visitAll(E);
return SFIS.FoundInside;
}
bool follow(const SCEV *E) {
if (auto *AddRec = dyn_cast<SCEVAddRecExpr>(E)) {
FoundInside |= S->getRegion().contains(AddRec->getLoop());
} else if (auto *Unknown = dyn_cast<SCEVUnknown>(E)) {
if (Instruction *I = dyn_cast<Instruction>(Unknown->getValue()))
FoundInside |= S->getRegion().contains(I) && !VMap.count(I);
}
return !FoundInside;
}
bool isDone() { return FoundInside; }
};
} // end anonymous namespace
const SCEV *Scop::getRepresentingInvariantLoadSCEV(const SCEV *E) const {
// Check whether it makes sense to rewrite the SCEV. (ScalarEvolution
// doesn't like addition between an AddRec and an expression that
// doesn't have a dominance relationship with it.)
if (SCEVFindInsideScop::hasVariant(E, *SE, InvEquivClassVMap, this))
return E;
// Rewrite SCEV.
return SCEVSensitiveParameterRewriter::rewrite(E, *SE, InvEquivClassVMap);
}
// This table of function names is used to translate parameter names in more
// human-readable names. This makes it easier to interpret Polly analysis
// results.
StringMap<std::string> KnownNames = {
{"_Z13get_global_idj", "global_id"},
{"_Z12get_local_idj", "local_id"},
{"_Z15get_global_sizej", "global_size"},
{"_Z14get_local_sizej", "local_size"},
{"_Z12get_work_dimv", "work_dim"},
{"_Z17get_global_offsetj", "global_offset"},
{"_Z12get_group_idj", "group_id"},
{"_Z14get_num_groupsj", "num_groups"},
};
static std::string getCallParamName(CallInst *Call) {
std::string Result;
raw_string_ostream OS(Result);
std::string Name = Call->getCalledFunction()->getName();
auto Iterator = KnownNames.find(Name);
if (Iterator != KnownNames.end())
Name = "__" + Iterator->getValue();
OS << Name;
for (auto &Operand : Call->arg_operands()) {
ConstantInt *Op = cast<ConstantInt>(&Operand);
OS << "_" << Op->getValue();
}
OS.flush();
return Result;
}
void Scop::createParameterId(const SCEV *Parameter) {
assert(Parameters.count(Parameter));
assert(!ParameterIds.count(Parameter));
std::string ParameterName = "p_" + std::to_string(getNumParams() - 1);
if (const SCEVUnknown *ValueParameter = dyn_cast<SCEVUnknown>(Parameter)) {
Value *Val = ValueParameter->getValue();
CallInst *Call = dyn_cast<CallInst>(Val);
if (Call && isConstCall(Call)) {
ParameterName = getCallParamName(Call);
} else if (UseInstructionNames) {
// If this parameter references a specific Value and this value has a name
// we use this name as it is likely to be unique and more useful than just
// a number.
if (Val->hasName())
ParameterName = Val->getName();
else if (LoadInst *LI = dyn_cast<LoadInst>(Val)) {
auto *LoadOrigin = LI->getPointerOperand()->stripInBoundsOffsets();
if (LoadOrigin->hasName()) {
ParameterName += "_loaded_from_";
ParameterName +=
LI->getPointerOperand()->stripInBoundsOffsets()->getName();
}
}
}
ParameterName = getIslCompatibleName("", ParameterName, "");
}
isl::id Id = isl::id::alloc(getIslCtx(), ParameterName,
const_cast<void *>((const void *)Parameter));
ParameterIds[Parameter] = Id;
}
void Scop::addParams(const ParameterSetTy &NewParameters) {
for (const SCEV *Parameter : NewParameters) {
// Normalize the SCEV to get the representing element for an invariant load.
Parameter = extractConstantFactor(Parameter, *SE).second;
Parameter = getRepresentingInvariantLoadSCEV(Parameter);
if (Parameters.insert(Parameter))
createParameterId(Parameter);
}
}
isl::id Scop::getIdForParam(const SCEV *Parameter) const {
// Normalize the SCEV to get the representing element for an invariant load.
Parameter = getRepresentingInvariantLoadSCEV(Parameter);
return ParameterIds.lookup(Parameter);
}
isl::set Scop::addNonEmptyDomainConstraints(isl::set C) const {
isl::set DomainContext = getDomains().params();
return C.intersect_params(DomainContext);
}
bool Scop::isDominatedBy(const DominatorTree &DT, BasicBlock *BB) const {
return DT.dominates(BB, getEntry());
}
void Scop::addUserAssumptions(
AssumptionCache &AC, DominatorTree &DT, LoopInfo &LI,
DenseMap<BasicBlock *, isl::set> &InvalidDomainMap) {
for (auto &Assumption : AC.assumptions()) {
auto *CI = dyn_cast_or_null<CallInst>(Assumption);
if (!CI || CI->getNumArgOperands() != 1)
continue;
bool InScop = contains(CI);
if (!InScop && !isDominatedBy(DT, CI->getParent()))
continue;
auto *L = LI.getLoopFor(CI->getParent());
auto *Val = CI->getArgOperand(0);
ParameterSetTy DetectedParams;
if (!isAffineConstraint(Val, &R, L, *SE, DetectedParams)) {
ORE.emit(
OptimizationRemarkAnalysis(DEBUG_TYPE, "IgnoreUserAssumption", CI)
<< "Non-affine user assumption ignored.");
continue;
}
// Collect all newly introduced parameters.
ParameterSetTy NewParams;
for (auto *Param : DetectedParams) {
Param = extractConstantFactor(Param, *SE).second;
Param = getRepresentingInvariantLoadSCEV(Param);
if (Parameters.count(Param))
continue;
NewParams.insert(Param);
}
SmallVector<isl_set *, 2> ConditionSets;
auto *TI = InScop ? CI->getParent()->getTerminator() : nullptr;
BasicBlock *BB = InScop ? CI->getParent() : getRegion().getEntry();
auto *Dom = InScop ? DomainMap[BB].copy() : Context.copy();
assert(Dom && "Cannot propagate a nullptr.");
bool Valid = buildConditionSets(*this, BB, Val, TI, L, Dom,
InvalidDomainMap, ConditionSets);
isl_set_free(Dom);
if (!Valid)
continue;
isl_set *AssumptionCtx = nullptr;
if (InScop) {
AssumptionCtx = isl_set_complement(isl_set_params(ConditionSets[1]));
isl_set_free(ConditionSets[0]);
} else {
AssumptionCtx = isl_set_complement(ConditionSets[1]);
AssumptionCtx = isl_set_intersect(AssumptionCtx, ConditionSets[0]);
}
// Project out newly introduced parameters as they are not otherwise useful.
if (!NewParams.empty()) {
for (unsigned u = 0; u < isl_set_n_param(AssumptionCtx); u++) {
auto *Id = isl_set_get_dim_id(AssumptionCtx, isl_dim_param, u);
auto *Param = static_cast<const SCEV *>(isl_id_get_user(Id));
isl_id_free(Id);
if (!NewParams.count(Param))
continue;
AssumptionCtx =
isl_set_project_out(AssumptionCtx, isl_dim_param, u--, 1);
}
}
ORE.emit(OptimizationRemarkAnalysis(DEBUG_TYPE, "UserAssumption", CI)
<< "Use user assumption: " << stringFromIslObj(AssumptionCtx));
Context = Context.intersect(isl::manage(AssumptionCtx));
}
}
void Scop::addUserContext() {
if (UserContextStr.empty())
return;
isl::set UserContext = isl::set(getIslCtx(), UserContextStr.c_str());
isl::space Space = getParamSpace();
if (Space.dim(isl::dim::param) != UserContext.dim(isl::dim::param)) {
std::string SpaceStr = Space.to_str();
errs() << "Error: the context provided in -polly-context has not the same "
<< "number of dimensions than the computed context. Due to this "
<< "mismatch, the -polly-context option is ignored. Please provide "
<< "the context in the parameter space: " << SpaceStr << ".\n";
return;
}
for (unsigned i = 0; i < Space.dim(isl::dim::param); i++) {
std::string NameContext = Context.get_dim_name(isl::dim::param, i);
std::string NameUserContext = UserContext.get_dim_name(isl::dim::param, i);
if (NameContext != NameUserContext) {
std::string SpaceStr = Space.to_str();
errs() << "Error: the name of dimension " << i
<< " provided in -polly-context "
<< "is '" << NameUserContext << "', but the name in the computed "
<< "context is '" << NameContext
<< "'. Due to this name mismatch, "
<< "the -polly-context option is ignored. Please provide "
<< "the context in the parameter space: " << SpaceStr << ".\n";
return;
}
UserContext = UserContext.set_dim_id(isl::dim::param, i,
Space.get_dim_id(isl::dim::param, i));
}
Context = Context.intersect(UserContext);
}
void Scop::buildInvariantEquivalenceClasses() {
DenseMap<std::pair<const SCEV *, Type *>, LoadInst *> EquivClasses;
const InvariantLoadsSetTy &RIL = getRequiredInvariantLoads();
for (LoadInst *LInst : RIL) {
const SCEV *PointerSCEV = SE->getSCEV(LInst->getPointerOperand());
Type *Ty = LInst->getType();
LoadInst *&ClassRep = EquivClasses[std::make_pair(PointerSCEV, Ty)];
if (ClassRep) {
InvEquivClassVMap[LInst] = ClassRep;
continue;
}
ClassRep = LInst;
InvariantEquivClasses.emplace_back(
InvariantEquivClassTy{PointerSCEV, MemoryAccessList(), nullptr, Ty});
}
}
void Scop::buildContext() {
isl::space Space = isl::space::params_alloc(getIslCtx(), 0);
Context = isl::set::universe(Space);
InvalidContext = isl::set::empty(Space);
AssumedContext = isl::set::universe(Space);
}
void Scop::addParameterBounds() {
unsigned PDim = 0;
for (auto *Parameter : Parameters) {
ConstantRange SRange = SE->getSignedRange(Parameter);
Context = addRangeBoundsToSet(Context, SRange, PDim++, isl::dim::param);
}
}
static std::vector<isl::id> getFortranArrayIds(Scop::array_range Arrays) {
std::vector<isl::id> OutermostSizeIds;
for (auto Array : Arrays) {
// To check if an array is a Fortran array, we check if it has a isl_pw_aff
// for its outermost dimension. Fortran arrays will have this since the
// outermost dimension size can be picked up from their runtime description.
// TODO: actually need to check if it has a FAD, but for now this works.
if (Array->getNumberOfDimensions() > 0) {
isl::pw_aff PwAff = Array->getDimensionSizePw(0);
if (!PwAff)
continue;
isl::id Id = PwAff.get_dim_id(isl::dim::param, 0);
assert(!Id.is_null() &&
"Invalid Id for PwAff expression in Fortran array");
OutermostSizeIds.push_back(Id);
}
}
return OutermostSizeIds;
}
// The FORTRAN array size parameters are known to be non-negative.
static isl::set boundFortranArrayParams(isl::set Context,
Scop::array_range Arrays) {
std::vector<isl::id> OutermostSizeIds;
OutermostSizeIds = getFortranArrayIds(Arrays);
for (isl::id Id : OutermostSizeIds) {
int dim = Context.find_dim_by_id(isl::dim::param, Id);
Context = Context.lower_bound_si(isl::dim::param, dim, 0);
}
return Context;
}
void Scop::realignParams() {
if (PollyIgnoreParamBounds)
return;
// Add all parameters into a common model.
isl::space Space = getFullParamSpace();
// Align the parameters of all data structures to the model.
Context = Context.align_params(Space);
// Bound the size of the fortran array dimensions.
Context = boundFortranArrayParams(Context, arrays());
// As all parameters are known add bounds to them.
addParameterBounds();
for (ScopStmt &Stmt : *this)
Stmt.realignParams();
// Simplify the schedule according to the context too.
Schedule = Schedule.gist_domain_params(getContext());
}
static isl::set simplifyAssumptionContext(isl::set AssumptionContext,
const Scop &S) {
// If we have modeled all blocks in the SCoP that have side effects we can
// simplify the context with the constraints that are needed for anything to
// be executed at all. However, if we have error blocks in the SCoP we already
// assumed some parameter combinations cannot occur and removed them from the
// domains, thus we cannot use the remaining domain to simplify the
// assumptions.
if (!S.hasErrorBlock()) {
auto DomainParameters = S.getDomains().params();
AssumptionContext = AssumptionContext.gist_params(DomainParameters);
}
AssumptionContext = AssumptionContext.gist_params(S.getContext());
return AssumptionContext;
}
void Scop::simplifyContexts() {
// The parameter constraints of the iteration domains give us a set of
// constraints that need to hold for all cases where at least a single
// statement iteration is executed in the whole scop. We now simplify the
// assumed context under the assumption that such constraints hold and at
// least a single statement iteration is executed. For cases where no
// statement instances are executed, the assumptions we have taken about
// the executed code do not matter and can be changed.
//
// WARNING: This only holds if the assumptions we have taken do not reduce
// the set of statement instances that are executed. Otherwise we
// may run into a case where the iteration domains suggest that
// for a certain set of parameter constraints no code is executed,
// but in the original program some computation would have been
// performed. In such a case, modifying the run-time conditions and
// possibly influencing the run-time check may cause certain scops
// to not be executed.
//
// Example:
//
// When delinearizing the following code:
//
// for (long i = 0; i < 100; i++)
// for (long j = 0; j < m; j++)
// A[i+p][j] = 1.0;
//
// we assume that the condition m <= 0 or (m >= 1 and p >= 0) holds as
// otherwise we would access out of bound data. Now, knowing that code is
// only executed for the case m >= 0, it is sufficient to assume p >= 0.
AssumedContext = simplifyAssumptionContext(AssumedContext, *this);
InvalidContext = InvalidContext.align_params(getParamSpace());
}
/// Add the minimal/maximal access in @p Set to @p User.
///
/// @return True if more accesses should be added, false if we reached the
/// maximal number of run-time checks to be generated.
static bool buildMinMaxAccess(isl::set Set,
Scop::MinMaxVectorTy &MinMaxAccesses, Scop &S) {
isl::pw_multi_aff MinPMA, MaxPMA;
isl::pw_aff LastDimAff;
isl::aff OneAff;
unsigned Pos;
Set = Set.remove_divs();
polly::simplify(Set);
if (Set.n_basic_set() > RunTimeChecksMaxAccessDisjuncts)
Set = Set.simple_hull();
// Restrict the number of parameters involved in the access as the lexmin/
// lexmax computation will take too long if this number is high.
//
// Experiments with a simple test case using an i7 4800MQ:
//
// #Parameters involved | Time (in sec)
// 6 | 0.01
// 7 | 0.04
// 8 | 0.12
// 9 | 0.40
// 10 | 1.54
// 11 | 6.78
// 12 | 30.38
//
if (isl_set_n_param(Set.get()) > RunTimeChecksMaxParameters) {
unsigned InvolvedParams = 0;
for (unsigned u = 0, e = isl_set_n_param(Set.get()); u < e; u++)
if (Set.involves_dims(isl::dim::param, u, 1))
InvolvedParams++;
if (InvolvedParams > RunTimeChecksMaxParameters)
return false;
}
MinPMA = Set.lexmin_pw_multi_aff();
MaxPMA = Set.lexmax_pw_multi_aff();
MinPMA = MinPMA.coalesce();
MaxPMA = MaxPMA.coalesce();
// Adjust the last dimension of the maximal access by one as we want to
// enclose the accessed memory region by MinPMA and MaxPMA. The pointer
// we test during code generation might now point after the end of the
// allocated array but we will never dereference it anyway.
assert((!MaxPMA || MaxPMA.dim(isl::dim::out)) &&
"Assumed at least one output dimension");
Pos = MaxPMA.dim(isl::dim::out) - 1;
LastDimAff = MaxPMA.get_pw_aff(Pos);
OneAff = isl::aff(isl::local_space(LastDimAff.get_domain_space()));
OneAff = OneAff.add_constant_si(1);
LastDimAff = LastDimAff.add(OneAff);
MaxPMA = MaxPMA.set_pw_aff(Pos, LastDimAff);
if (!MinPMA || !MaxPMA)
return false;
MinMaxAccesses.push_back(std::make_pair(MinPMA, MaxPMA));
return true;
}
static isl::set getAccessDomain(MemoryAccess *MA) {
isl::set Domain = MA->getStatement()->getDomain();
Domain = Domain.project_out(isl::dim::set, 0, Domain.n_dim());
return Domain.reset_tuple_id();
}
/// Wrapper function to calculate minimal/maximal accesses to each array.
static bool calculateMinMaxAccess(Scop::AliasGroupTy AliasGroup, Scop &S,
Scop::MinMaxVectorTy &MinMaxAccesses) {
MinMaxAccesses.reserve(AliasGroup.size());
isl::union_set Domains = S.getDomains();
isl::union_map Accesses = isl::union_map::empty(S.getParamSpace());
for (MemoryAccess *MA : AliasGroup)
Accesses = Accesses.add_map(MA->getAccessRelation());
Accesses = Accesses.intersect_domain(Domains);
isl::union_set Locations = Accesses.range();
bool LimitReached = false;
for (isl::set Set : Locations.get_set_list()) {
LimitReached |= !buildMinMaxAccess(Set, MinMaxAccesses, S);
if (LimitReached)
break;
}
return !LimitReached;
}
/// Helper to treat non-affine regions and basic blocks the same.
///
///{
/// Return the block that is the representing block for @p RN.
static inline BasicBlock *getRegionNodeBasicBlock(RegionNode *RN) {
return RN->isSubRegion() ? RN->getNodeAs<Region>()->getEntry()
: RN->getNodeAs<BasicBlock>();
}
/// Return the @p idx'th block that is executed after @p RN.
static inline BasicBlock *
getRegionNodeSuccessor(RegionNode *RN, TerminatorInst *TI, unsigned idx) {
if (RN->isSubRegion()) {
assert(idx == 0);
return RN->getNodeAs<Region>()->getExit();
}
return TI->getSuccessor(idx);
}
/// Return the smallest loop surrounding @p RN.
static inline Loop *getRegionNodeLoop(RegionNode *RN, LoopInfo &LI) {
if (!RN->isSubRegion()) {
BasicBlock *BB = RN->getNodeAs<BasicBlock>();
Loop *L = LI.getLoopFor(BB);
// Unreachable statements are not considered to belong to a LLVM loop, as
// they are not part of an actual loop in the control flow graph.
// Nevertheless, we handle certain unreachable statements that are common
// when modeling run-time bounds checks as being part of the loop to be
// able to model them and to later eliminate the run-time bounds checks.
//
// Specifically, for basic blocks that terminate in an unreachable and
// where the immediate predecessor is part of a loop, we assume these
// basic blocks belong to the loop the predecessor belongs to. This
// allows us to model the following code.
//
// for (i = 0; i < N; i++) {
// if (i > 1024)
// abort(); <- this abort might be translated to an
// unreachable
//
// A[i] = ...
// }
if (!L && isa<UnreachableInst>(BB->getTerminator()) && BB->getPrevNode())
L = LI.getLoopFor(BB->getPrevNode());
return L;
}
Region *NonAffineSubRegion = RN->getNodeAs<Region>();
Loop *L = LI.getLoopFor(NonAffineSubRegion->getEntry());
while (L && NonAffineSubRegion->contains(L))
L = L->getParentLoop();
return L;
}
/// Get the number of blocks in @p L.
///
/// The number of blocks in a loop are the number of basic blocks actually
/// belonging to the loop, as well as all single basic blocks that the loop
/// exits to and which terminate in an unreachable instruction. We do not
/// allow such basic blocks in the exit of a scop, hence they belong to the
/// scop and represent run-time conditions which we want to model and
/// subsequently speculate away.
///
/// @see getRegionNodeLoop for additional details.
unsigned getNumBlocksInLoop(Loop *L) {
unsigned NumBlocks = L->getNumBlocks();
SmallVector<BasicBlock *, 4> ExitBlocks;
L->getExitBlocks(ExitBlocks);
for (auto ExitBlock : ExitBlocks) {
if (isa<UnreachableInst>(ExitBlock->getTerminator()))
NumBlocks++;
}
return NumBlocks;
}
static inline unsigned getNumBlocksInRegionNode(RegionNode *RN) {
if (!RN->isSubRegion())
return 1;
Region *R = RN->getNodeAs<Region>();
return std::distance(R->block_begin(), R->block_end());
}
static bool containsErrorBlock(RegionNode *RN, const Region &R, LoopInfo &LI,
const DominatorTree &DT) {
if (!RN->isSubRegion())
return isErrorBlock(*RN->getNodeAs<BasicBlock>(), R, LI, DT);
for (BasicBlock *BB : RN->getNodeAs<Region>()->blocks())
if (isErrorBlock(*BB, R, LI, DT))
return true;
return false;
}
///}
isl::set Scop::getDomainConditions(const ScopStmt *Stmt) const {
return getDomainConditions(Stmt->getEntryBlock());
}
isl::set Scop::getDomainConditions(BasicBlock *BB) const {
auto DIt = DomainMap.find(BB);
if (DIt != DomainMap.end())
return DIt->getSecond();
auto &RI = *R.getRegionInfo();
auto *BBR = RI.getRegionFor(BB);
while (BBR->getEntry() == BB)
BBR = BBR->getParent();
return getDomainConditions(BBR->getEntry());
}
bool Scop::buildDomains(Region *R, DominatorTree &DT, LoopInfo &LI,
DenseMap<BasicBlock *, isl::set> &InvalidDomainMap) {
bool IsOnlyNonAffineRegion = isNonAffineSubRegion(R);
auto *EntryBB = R->getEntry();
auto *L = IsOnlyNonAffineRegion ? nullptr : LI.getLoopFor(EntryBB);
int LD = getRelativeLoopDepth(L);
auto *S = isl_set_universe(isl_space_set_alloc(getIslCtx().get(), 0, LD + 1));
while (LD-- >= 0) {
L = L->getParentLoop();
}
InvalidDomainMap[EntryBB] = isl::manage(isl_set_empty(isl_set_get_space(S)));
DomainMap[EntryBB] = isl::manage(S);
if (IsOnlyNonAffineRegion)
return !containsErrorBlock(R->getNode(), *R, LI, DT);
if (!buildDomainsWithBranchConstraints(R, DT, LI, InvalidDomainMap))
return false;
if (!propagateDomainConstraints(R, DT, LI, InvalidDomainMap))
return false;
// Error blocks and blocks dominated by them have been assumed to never be
// executed. Representing them in the Scop does not add any value. In fact,
// it is likely to cause issues during construction of the ScopStmts. The
// contents of error blocks have not been verified to be expressible and
// will cause problems when building up a ScopStmt for them.
// Furthermore, basic blocks dominated by error blocks may reference
// instructions in the error block which, if the error block is not modeled,
// can themselves not be constructed properly. To this end we will replace
// the domains of error blocks and those only reachable via error blocks
// with an empty set. Additionally, we will record for each block under which
// parameter combination it would be reached via an error block in its
// InvalidDomain. This information is needed during load hoisting.
if (!propagateInvalidStmtDomains(R, DT, LI, InvalidDomainMap))
return false;
return true;
}
/// Adjust the dimensions of @p Dom that was constructed for @p OldL
/// to be compatible to domains constructed for loop @p NewL.
///
/// This function assumes @p NewL and @p OldL are equal or there is a CFG
/// edge from @p OldL to @p NewL.
static isl::set adjustDomainDimensions(Scop &S, isl::set Dom, Loop *OldL,
Loop *NewL) {
// If the loops are the same there is nothing to do.
if (NewL == OldL)
return Dom;
int OldDepth = S.getRelativeLoopDepth(OldL);
int NewDepth = S.getRelativeLoopDepth(NewL);
// If both loops are non-affine loops there is nothing to do.
if (OldDepth == -1 && NewDepth == -1)
return Dom;
// Distinguish three cases:
// 1) The depth is the same but the loops are not.
// => One loop was left one was entered.
// 2) The depth increased from OldL to NewL.
// => One loop was entered, none was left.
// 3) The depth decreased from OldL to NewL.
// => Loops were left were difference of the depths defines how many.
if (OldDepth == NewDepth) {
assert(OldL->getParentLoop() == NewL->getParentLoop());
Dom = Dom.project_out(isl::dim::set, NewDepth, 1);
Dom = Dom.add_dims(isl::dim::set, 1);
} else if (OldDepth < NewDepth) {
assert(OldDepth + 1 == NewDepth);
auto &R = S.getRegion();
(void)R;
assert(NewL->getParentLoop() == OldL ||
((!OldL || !R.contains(OldL)) && R.contains(NewL)));
Dom = Dom.add_dims(isl::dim::set, 1);
} else {
assert(OldDepth > NewDepth);
int Diff = OldDepth - NewDepth;
int NumDim = Dom.n_dim();
assert(NumDim >= Diff);
Dom = Dom.project_out(isl::dim::set, NumDim - Diff, Diff);
}
return Dom;
}
bool Scop::propagateInvalidStmtDomains(
Region *R, DominatorTree &DT, LoopInfo &LI,
DenseMap<BasicBlock *, isl::set> &InvalidDomainMap) {
ReversePostOrderTraversal<Region *> RTraversal(R);
for (auto *RN : RTraversal) {
// Recurse for affine subregions but go on for basic blocks and non-affine
// subregions.
if (RN->isSubRegion()) {
Region *SubRegion = RN->getNodeAs<Region>();
if (!isNonAffineSubRegion(SubRegion)) {
propagateInvalidStmtDomains(SubRegion, DT, LI, InvalidDomainMap);
continue;
}
}
bool ContainsErrorBlock = containsErrorBlock(RN, getRegion(), LI, DT);
BasicBlock *BB = getRegionNodeBasicBlock(RN);
isl::set &Domain = DomainMap[BB];
assert(Domain && "Cannot propagate a nullptr");
isl::set InvalidDomain = InvalidDomainMap[BB];
bool IsInvalidBlock = ContainsErrorBlock || Domain.is_subset(InvalidDomain);
if (!IsInvalidBlock) {
InvalidDomain = InvalidDomain.intersect(Domain);
} else {
InvalidDomain = Domain;
isl::set DomPar = Domain.params();
recordAssumption(ERRORBLOCK, DomPar, BB->getTerminator()->getDebugLoc(),
AS_RESTRICTION);
Domain = nullptr;