30#include "llvm/ADT/APInt.h"
31#include "llvm/ADT/ArrayRef.h"
32#include "llvm/ADT/PostOrderIterator.h"
33#include "llvm/ADT/Sequence.h"
34#include "llvm/ADT/SmallPtrSet.h"
35#include "llvm/ADT/SmallSet.h"
36#include "llvm/ADT/Statistic.h"
37#include "llvm/ADT/StringExtras.h"
38#include "llvm/Analysis/AliasAnalysis.h"
39#include "llvm/Analysis/AssumptionCache.h"
40#include "llvm/Analysis/Loads.h"
41#include "llvm/Analysis/LoopInfo.h"
42#include "llvm/Analysis/OptimizationRemarkEmitter.h"
43#include "llvm/Analysis/RegionInfo.h"
44#include "llvm/Analysis/RegionIterator.h"
45#include "llvm/Analysis/ScalarEvolution.h"
46#include "llvm/Analysis/ScalarEvolutionExpressions.h"
47#include "llvm/IR/BasicBlock.h"
48#include "llvm/IR/ConstantRange.h"
49#include "llvm/IR/DataLayout.h"
50#include "llvm/IR/DebugLoc.h"
51#include "llvm/IR/Dominators.h"
52#include "llvm/IR/Function.h"
53#include "llvm/IR/InstrTypes.h"
54#include "llvm/IR/Instruction.h"
55#include "llvm/IR/Instructions.h"
56#include "llvm/IR/Module.h"
57#include "llvm/IR/PassManager.h"
58#include "llvm/IR/Type.h"
59#include "llvm/IR/Value.h"
60#include "llvm/InitializePasses.h"
61#include "llvm/Support/Compiler.h"
62#include "llvm/Support/Debug.h"
63#include "llvm/Support/ErrorHandling.h"
64#include "llvm/Support/raw_ostream.h"
77#define DEBUG_TYPE "polly-scops"
79STATISTIC(AssumptionsAliasing,
"Number of aliasing assumptions taken.");
80STATISTIC(AssumptionsInbounds,
"Number of inbounds assumptions taken.");
81STATISTIC(AssumptionsWrapping,
"Number of wrapping assumptions taken.");
82STATISTIC(AssumptionsUnsigned,
"Number of unsigned assumptions taken.");
83STATISTIC(AssumptionsComplexity,
"Number of too complex SCoPs.");
84STATISTIC(AssumptionsUnprofitable,
"Number of unprofitable SCoPs.");
85STATISTIC(AssumptionsErrorBlock,
"Number of error block assumptions taken.");
86STATISTIC(AssumptionsInfiniteLoop,
"Number of bounded loop assumptions taken.");
88 "Number of invariant loads assumptions taken.");
90 "Number of delinearization assumptions taken.");
92STATISTIC(NumScops,
"Number of feasible SCoPs after ScopInfo");
93STATISTIC(NumLoopsInScop,
"Number of loops in scops");
94STATISTIC(NumBoxedLoops,
"Number of boxed loops in SCoPs after ScopInfo");
95STATISTIC(NumAffineLoops,
"Number of affine loops in SCoPs after ScopInfo");
97STATISTIC(NumScopsDepthZero,
"Number of scops with maximal loop depth 0");
98STATISTIC(NumScopsDepthOne,
"Number of scops with maximal loop depth 1");
99STATISTIC(NumScopsDepthTwo,
"Number of scops with maximal loop depth 2");
100STATISTIC(NumScopsDepthThree,
"Number of scops with maximal loop depth 3");
101STATISTIC(NumScopsDepthFour,
"Number of scops with maximal loop depth 4");
102STATISTIC(NumScopsDepthFive,
"Number of scops with maximal loop depth 5");
104 "Number of scops with maximal loop depth 6 and larger");
105STATISTIC(MaxNumLoopsInScop,
"Maximal number of loops in scops");
107STATISTIC(NumValueWrites,
"Number of scalar value writes after ScopInfo");
109 NumValueWritesInLoops,
110 "Number of scalar value writes nested in affine loops after ScopInfo");
111STATISTIC(NumPHIWrites,
"Number of scalar phi writes after ScopInfo");
113 "Number of scalar phi writes nested in affine loops after ScopInfo");
114STATISTIC(NumSingletonWrites,
"Number of singleton writes after ScopInfo");
116 "Number of singleton writes nested in affine loops after ScopInfo");
130 "polly-remarks-minimal",
131 cl::desc(
"Do not emit remarks about assumptions that are known"),
136 cl::desc(
"Abort if an isl error is encountered"),
140 "polly-precise-inbounds",
141 cl::desc(
"Take more precise inbounds assumptions (do not scale well)"),
145 "polly-ignore-parameter-bounds",
147 "Do not add parameter bounds and do no gist simplify sets accordingly"),
151 "polly-precise-fold-accesses",
152 cl::desc(
"Fold memory accesses to model more possible delinearizations "
153 "(does not scale well)"),
159 "polly-use-llvm-names",
160 cl::desc(
"Use LLVM-IR names when deriving statement names"),
164 "polly-print-instructions", cl::desc(
"Output instructions per ScopStmt"),
165 cl::Hidden, cl::Optional, cl::init(
false), cl::cat(
PollyCategory));
167static cl::list<std::string>
IslArgs(
"polly-isl-arg",
168 cl::value_desc(
"argument"),
169 cl::desc(
"Option passed to ISL"),
183 S =
S.lower_bound_val(
type, dim, V);
185 S =
S.upper_bound_val(
type, dim, V);
187 if (
Range.isFullSet())
195 if (
Range.isSignWrappedSet()) {
209 LoadInst *BasePtrLI = dyn_cast<LoadInst>(BasePtr);
213 if (!
S->contains(BasePtrLI))
216 ScalarEvolution &SE = *
S->getSE();
218 const SCEV *OriginBaseSCEV =
219 SE.getPointerBase(SE.getSCEV(BasePtrLI->getPointerOperand()));
223 auto *OriginBaseSCEVUnknown = dyn_cast<SCEVUnknown>(OriginBaseSCEV);
224 if (!OriginBaseSCEVUnknown)
227 return S->getScopArrayInfo(OriginBaseSCEVUnknown->getValue(),
234 const char *BaseName)
236 std::string BasePtrName =
289 auto OldElementSize =
DL.getTypeAllocSizeInBits(
ElementType);
290 auto NewElementSize =
DL.getTypeAllocSizeInBits(NewElementType);
292 if (NewElementSize == OldElementSize || NewElementSize == 0)
295 if (NewElementSize % OldElementSize == 0 && NewElementSize < OldElementSize) {
298 auto GCD = std::gcd((uint64_t)NewElementSize, (uint64_t)OldElementSize);
304 bool CheckConsistency) {
305 int SharedDims = std::min(NewSizes.size(),
DimensionSizes.size());
306 int ExtraDimsNew = NewSizes.size() - SharedDims;
309 if (CheckConsistency) {
310 for (
int i = 0; i < SharedDims; i++) {
311 auto *NewSize = NewSizes[i + ExtraDimsNew];
313 if (NewSize && KnownSize && NewSize != KnownSize)
344#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
361 OS <<
" " << Size <<
" ";
380 assert(!
Id.is_null() &&
"Output dimension didn't have an ID");
385 void *User =
Id.get_user();
394 unsigned DimsArray = SAI->getNumberOfDimensions();
401 for (
int i = DimsArray - 1; i > 0; i--) {
402 auto *DimSize = SAI->getDimensionSize(i);
403 auto *DimSizeCst = dyn_cast<SCEVConstant>(DimSize);
410 if (DimSize->isZero())
422 Modulo = Modulo.
pullback(DivModAff);
426 Divide = Divide.
floor();
427 Divide = Divide.
add(PrevVar);
428 Divide = Divide.
pullback(DivModAff);
431 DivModAff = DivModAff.
set_aff(i, Modulo);
432 DivModAff = DivModAff.
set_aff(i - 1, Divide);
450 assert(DimsArray >= DimsAccess);
451 unsigned DimsMissing = DimsArray - DimsAccess;
454 auto &DL = BB->getModule()->getDataLayout();
455 unsigned ArrayElemSize = SAI->getElemSizeInBytes();
461 for (
auto i : seq<unsigned>(0, DimsMissing))
464 for (
auto i : seq<unsigned>(DimsMissing, DimsArray))
479 if (DimsAccess == 1) {
500 if (ElemBytes > ArrayElemSize) {
501 assert(ElemBytes % ArrayElemSize == 0 &&
502 "Loaded element size should be multiple of canonical element size");
506 for (
auto i : seq<unsigned>(0, DimsArray - 1))
534 llvm_unreachable(
"Requested a reduction operator string for a memory "
535 "access which isn't a reduction");
537 llvm_unreachable(
"Requested a reduction operator string for a internal "
550 llvm_unreachable(
"Unknown reduction type");
662 Outside = Outside.
unite(DimOutside);
667 Outside = Outside.
params();
700 LengthMap = LengthMap.
sum(SubscriptMap);
706 ScalarEvolution *SE =
Statement->getParent()->getSE();
709 if (isa<MemIntrinsic>(MAI))
712 Value *Ptr = MAI.getPointerOperand();
713 if (!Ptr || !SE->isSCEVable(Ptr->getType()))
716 const SCEV *PtrSCEV = SE->getSCEV(Ptr);
717 if (isa<SCEVCouldNotCompute>(PtrSCEV))
720 const SCEV *BasePtrSCEV = SE->getPointerBase(PtrSCEV);
721 if (BasePtrSCEV && !isa<SCEVCouldNotCompute>(BasePtrSCEV))
722 PtrSCEV = SE->getMinusSCEV(PtrSCEV, BasePtrSCEV);
724 const ConstantRange &
Range = SE->getSignedRange(PtrSCEV);
725 if (
Range.isFullSet())
728 if (
Range.isUpperWrapped() ||
Range.isSignWrappedSet())
731 bool isWrapping =
Range.isSignWrappedSet();
733 unsigned BW =
Range.getBitWidth();
734 const auto One = APInt(BW, 1);
735 const auto LB = isWrapping ?
Range.getLower() :
Range.getSignedMin();
736 const auto UB = isWrapping ? (
Range.getUpper() - One) :
Range.getSignedMax();
738 auto Min = LB.sdiv(APInt(BW, ElementSize));
739 auto Max = UB.sdiv(APInt(BW, ElementSize)) + One;
741 assert(Min.sle(Max) &&
"Minimum expected to be less or equal than max");
751 if (
Sizes.size() < 2 || isa<SCEVConstant>(
Sizes[1]))
758 for (
int i = Size - 2; i >= 0; --i) {
773 for (
int j = 0; j < Size; ++j)
778 for (
int j = 0; j < Size; ++j)
779 if (j < i || j > i + 1)
785 C =
C.set_constant_si(-1);
796 MapOne = MapOne.
unite(MapTwo);
849 for (
int i = 0, Size =
Subscripts.size(); i < Size; ++i) {
875 static const std::string TypeStrings[] = {
"",
"_Read",
"_Write",
"_MayWrite"};
876 const std::string Access = TypeStrings[
AccType] + utostr(Stmt->
size());
887 Sizes.push_back(
nullptr);
888 for (
unsigned i = 1; i < SAI->getNumberOfDimensions(); i++)
889 Sizes.push_back(SAI->getDimensionSize(i));
892 static const std::string TypeStrings[] = {
"",
"_Read",
"_Write",
"_MayWrite"};
893 const std::string Access = TypeStrings[
AccType] + utostr(Stmt->
size());
936 OS.indent(12) <<
"ReadAccess :=\t";
939 OS.indent(12) <<
"MustWriteAccess :=\t";
942 OS.indent(12) <<
"MayWriteAccess :=\t";
954#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
960 PWACtx PWAC = Stmt->getParent()->getPwAff(E, Stmt->getEntryBlock());
989 for (
unsigned i = 0; i < lastDimension; ++i)
1005 Schedule = Schedule.
reverse();
1006 NextScatt = NextScatt.
lexmin();
1024 for (
auto i : seq<int>(0, Size - 1))
1064 "Partial READ accesses not supported");
1069 "Must specify the array that is accessed");
1072 assert(SAI &&
"Must set a ScopArrayInfo");
1074 if (SAI->isArrayKind() && SAI->getBasePtrOriginSAI()) {
1079 "Access functions to indirect arrays must have an invariant and "
1080 "hoisted base pointer");
1085 unsigned Dims = SAI->getNumberOfDimensions();
1087 assert(SpaceSize == Dims &&
"Access dims must match array dims");
1109 if (Schedule.is_null())
1112 if (Schedule.is_empty())
1123 "New domain is not a subset of old domain!");
1132 MAL.emplace_front(Access);
1134 Instruction *AccessVal = cast<Instruction>(Access->
getAccessValue());
1182 std::vector<Instruction *> EntryBlockInstructions)
1244 OS <<
"Instructions {\n";
1247 OS.indent(16) << *Inst <<
"\n";
1249 OS.indent(12) <<
"}\n";
1254 OS.indent(12) <<
"Domain :=\n";
1259 OS.indent(16) <<
"n/a\n";
1261 OS.indent(12) <<
"Schedule :=\n";
1266 OS.indent(16) <<
"n/a\n";
1271 if (PrintInstructions)
1275#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1283 assert(Found &&
"Expected access data not found");
1288 assert(Found &&
"Expected access data not found");
1293 assert(Found &&
"Expected access data not found");
1298 assert(Found &&
"Expected access data not found");
1313 if (Predicate(MA)) {
1315 Parent.removeAccessData(MA);
1318 llvm::erase_if(
MemAccs, Predicate);
1323 if (AfterHoisting) {
1329 Parent.removeAccessData(MA);
1334 It->second.remove(MA);
1335 if (It->second.empty())
1349 Parent.addAccessFunction(Access);
1352 Parent.addAccessData(Access);
1371class SCEVSensitiveParameterRewriter final
1372 :
public SCEVRewriteVisitor<SCEVSensitiveParameterRewriter> {
1373 const ValueToValueMap &VMap;
1376 SCEVSensitiveParameterRewriter(
const ValueToValueMap &VMap,
1377 ScalarEvolution &SE)
1378 : SCEVRewriteVisitor(SE), VMap(VMap) {}
1380 static const SCEV *rewrite(
const SCEV *E, ScalarEvolution &SE,
1381 const ValueToValueMap &VMap) {
1382 SCEVSensitiveParameterRewriter SSPR(VMap, SE);
1383 return SSPR.visit(E);
1386 const SCEV *visitAddRecExpr(
const SCEVAddRecExpr *E) {
1387 const SCEV *Start = visit(E->getStart());
1388 const SCEV *AddRec = SE.getAddRecExpr(SE.getConstant(E->getType(), 0),
1389 visit(E->getStepRecurrence(SE)),
1390 E->getLoop(), SCEV::FlagAnyWrap);
1391 return SE.getAddExpr(Start, AddRec);
1394 const SCEV *visitUnknown(
const SCEVUnknown *E) {
1395 if (
auto *NewValue = VMap.lookup(E->getValue()))
1396 return SE.getUnknown(NewValue);
1402class SCEVFindInsideScop :
public SCEVTraversal<SCEVFindInsideScop> {
1403 const ValueToValueMap &VMap;
1404 bool FoundInside =
false;
1408 SCEVFindInsideScop(
const ValueToValueMap &VMap, ScalarEvolution &SE,
1410 : SCEVTraversal(*this), VMap(VMap),
S(
S) {}
1412 static bool hasVariant(
const SCEV *E, ScalarEvolution &SE,
1413 const ValueToValueMap &VMap,
const Scop *
S) {
1414 SCEVFindInsideScop SFIS(VMap, SE,
S);
1416 return SFIS.FoundInside;
1419 bool follow(
const SCEV *E) {
1420 if (
auto *AddRec = dyn_cast<SCEVAddRecExpr>(E)) {
1421 FoundInside |=
S->getRegion().contains(AddRec->getLoop());
1422 }
else if (
auto *Unknown = dyn_cast<SCEVUnknown>(E)) {
1423 if (Instruction *I = dyn_cast<Instruction>(Unknown->getValue()))
1424 FoundInside |=
S->getRegion().contains(I) && !VMap.count(I);
1426 return !FoundInside;
1429 bool isDone() {
return FoundInside; }
1448 std::string ParameterName =
"p_" + std::to_string(
getNumParams() - 1);
1450 if (
const SCEVUnknown *ValueParameter = dyn_cast<SCEVUnknown>(Parameter)) {
1451 Value *Val = ValueParameter->getValue();
1458 ParameterName = Val->getName().str();
1459 else if (LoadInst *LI = dyn_cast<LoadInst>(Val)) {
1460 auto *LoadOrigin = LI->getPointerOperand()->stripInBoundsOffsets();
1461 if (LoadOrigin->hasName()) {
1462 ParameterName +=
"_loaded_from_";
1464 LI->getPointerOperand()->stripInBoundsOffsets()->getName();
1473 const_cast<void *
>((
const void *)Parameter));
1478 for (
const SCEV *Parameter : NewParameters) {
1509 ConstantRange SRange =
SE->getSignedRange(Parameter);
1548 if (!
S.hasErrorBlock()) {
1549 auto DomainParameters =
S.getDomains().params();
1550 AssumptionContext = AssumptionContext.
gist_params(DomainParameters);
1553 AssumptionContext = AssumptionContext.
gist_params(
S.getContext());
1554 return AssumptionContext;
1599 return DIt->getSecond();
1601 auto &RI = *
R.getRegionInfo();
1602 auto *BBR = RI.getRegionFor(BB);
1603 while (BBR->getEntry() == BB)
1604 BBR = BBR->getParent();
1610 OptimizationRemarkEmitter &
ORE,
int ID)
1618 SmallVector<char *, 8> IslArgv;
1619 IslArgv.reserve(1 +
IslArgs.size());
1622 IslArgv.push_back(
const_cast<char *
>(
"-polly-isl-arg"));
1624 for (std::string &Arg :
IslArgs)
1625 IslArgv.push_back(
const_cast<char *
>(Arg.c_str()));
1647 for (BasicBlock *BB : Stmt.
getRegion()->blocks()) {
1653 for (Instruction &Inst : *BB)
1658 if (StmtMapIt !=
StmtMap.end())
1659 llvm::erase(StmtMapIt->second, &Stmt);
1666 bool AfterHoisting) {
1667 for (
auto StmtIt =
Stmts.begin(), StmtEnd =
Stmts.end(); StmtIt != StmtEnd;) {
1668 if (!ShouldDelete(*StmtIt)) {
1676 SmallVector<MemoryAccess *, 16> MAList(StmtIt->begin(), StmtIt->end());
1678 StmtIt->removeSingleMemoryAccess(MA, AfterHoisting);
1681 StmtIt =
Stmts.erase(StmtIt);
1690 return Domain.is_empty();
1696 [AfterHoisting](
ScopStmt &Stmt) ->
bool {
1701 bool RemoveStmt = Stmt.
isEmpty();
1704 if (!RemoveStmt && AfterHoisting) {
1705 bool OnlyRead =
true;
1714 RemoveStmt = OnlyRead;
1722 LoadInst *LInst = dyn_cast<LoadInst>(Val);
1727 LInst = cast<LoadInst>(Rep);
1729 Type *Ty = LInst->getType();
1730 const SCEV *PointerSCEV =
SE->getSCEV(LInst->getPointerOperand());
1732 if (PointerSCEV != IAClass.IdentifyingPointer || Ty != IAClass.AccessType)
1735 auto &MAs = IAClass.InvariantAccesses;
1736 for (
auto *MA : MAs)
1737 if (MA->getAccessInstruction() == Val)
1745 ArrayRef<const SCEV *> Sizes,
1747 const char *BaseName) {
1748 assert((BasePtr || BaseName) &&
1749 "BasePtr and BaseName can not be nullptr at the same time.");
1750 assert(!(BasePtr && BaseName) &&
"BaseName is redundant.");
1754 auto &DL =
getFunction().getParent()->getDataLayout();
1756 DL,
this, BaseName));
1759 SAI->updateElementType(ElementType);
1762 if (!SAI->updateSizes(Sizes))
1769 const std::string &BaseName,
1770 const std::vector<unsigned> &Sizes) {
1772 std::vector<const SCEV *> SCEVSizes;
1774 for (
auto size : Sizes)
1778 SCEVSizes.push_back(
nullptr);
1792 assert(SAI &&
"No ScopArrayInfo available for this base pointer");
1810 std::string ExitName, EntryName;
1812 return EntryName +
"---" + ExitName;
1816 std::string ExitName, EntryName;
1817 raw_string_ostream ExitStr(ExitName);
1818 raw_string_ostream EntryStr(EntryName);
1820 R.getEntry()->printAsOperand(EntryStr,
false);
1823 R.getExit()->printAsOperand(ExitStr,
false);
1825 ExitName =
"FunctionExit";
1827 return std::make_pair(EntryName, ExitName);
1859 unsigned OptimizableStmtsOrLoops = 0;
1860 for (
auto &Stmt : *
this) {
1861 if (Stmt.getNumIterators() == 0)
1864 bool ContainsArrayAccs =
false;
1865 bool ContainsScalarAccs =
false;
1866 for (
auto *MA : Stmt) {
1869 ContainsArrayAccs |= MA->isLatestArrayKind();
1870 ContainsScalarAccs |= MA->isLatestScalarKind();
1873 if (!ScalarsAreUnprofitable || (ContainsArrayAccs && !ContainsScalarAccs))
1874 OptimizableStmtsOrLoops += Stmt.getNumIterators();
1877 return OptimizableStmtsOrLoops > 1;
1895 auto *PointerBaseInst = dyn_cast<Instruction>(PointerBase);
1896 if (!PointerBaseInst)
1899 auto *BasePtrStmt =
getStmtFor(PointerBaseInst);
1903 return BasePtrStmt->getArrayAccessOrNULLFor(PointerBaseInst);
1909 return "No-aliasing";
1913 return "No-overflows";
1915 return "Signed-unsigned";
1917 return "Low complexity";
1919 return "Profitable";
1923 return "Finite loop";
1925 return "Invariant load";
1927 return "Delinearization";
1929 llvm_unreachable(
"Unknown AssumptionKind!");
1969 AssumptionsAliasing++;
1972 AssumptionsInbounds++;
1975 AssumptionsWrapping++;
1978 AssumptionsUnsigned++;
1981 AssumptionsComplexity++;
1984 AssumptionsUnprofitable++;
1987 AssumptionsErrorBlock++;
1990 AssumptionsInfiniteLoop++;
1993 AssumptionsInvariantLoad++;
1996 AssumptionsDelinearization++;
2000 auto Suffix = Sign ==
AS_ASSUMPTION ?
" assumption:\t" :
" restriction:\t";
2001 std::string Msg =
toString(
Kind) + Suffix + stringFromIslObj(Set);
2003 ORE.emit(OptimizationRemarkAnalysis(
DEBUG_TYPE,
"AssumpRestrict", Loc, BB)
2006 ORE.emit(OptimizationRemarkAnalysis(
DEBUG_TYPE,
"AssumpRestrict", Loc,
2052 POLLY_DEBUG(dbgs() <<
"Invalidate SCoP because of reason " <<
Kind <<
"\n");
2060 OS.indent(4) <<
Context <<
"\n";
2062 OS.indent(4) <<
"Assumed Context:\n";
2065 OS.indent(4) <<
"Invalid Context:\n";
2068 OS.indent(4) <<
"Defined Behavior Context:\n";
2072 OS.indent(4) <<
"<unavailable>\n";
2076 OS.indent(4) <<
"p" << Dim++ <<
": " << *Parameter <<
"\n";
2082 if (
Pair.second.size() == 0)
2085 noOfGroups +=
Pair.second.size();
2088 OS.indent(4) <<
"Alias Groups (" << noOfGroups <<
"):\n";
2090 OS.indent(8) <<
"n/a\n";
2097 if (
Pair.second.empty()) {
2098 OS.indent(8) <<
"[[";
2100 OS <<
" <" << MMANonReadOnly.first <<
", " << MMANonReadOnly.second
2107 OS.indent(8) <<
"[[";
2108 OS <<
" <" << MMAReadOnly.first <<
", " << MMAReadOnly.second <<
">";
2110 OS <<
" <" << MMANonReadOnly.first <<
", " << MMANonReadOnly.second
2119 OS <<
"Statements {\n";
2121 for (
const ScopStmt &Stmt : *
this) {
2123 Stmt.
print(OS, PrintInstructions);
2126 OS.indent(4) <<
"}\n";
2135 OS.indent(4) <<
"}\n";
2137 OS.indent(4) <<
"Arrays (Bounds as pw_affs) {\n";
2140 Array->print(OS,
true);
2142 OS.indent(4) <<
"}\n";
2146 OS.indent(4) <<
"Function: " <<
getFunction().getName() <<
"\n";
2147 OS.indent(4) <<
"Region: " <<
getNameStr() <<
"\n";
2149 OS.indent(4) <<
"Invariant Accesses: {\n";
2151 const auto &MAs = IAClass.InvariantAccesses;
2153 OS.indent(12) <<
"Class Pointer: " << *IAClass.IdentifyingPointer <<
"\n";
2155 MAs.front()->print(OS);
2156 OS.indent(12) <<
"Execution Context: " << IAClass.ExecutionContext
2160 OS.indent(4) <<
"}\n";
2167#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
2181 auto PWAC =
Affinator.getPwAff(E, BB, RecordedAssumptions);
2182 if (!PWAC.first.is_null()) {
2189 Affinator.takeNonNegativeAssumption(PWAC, RecordedAssumptions);
2193 auto DL = BB ? BB->getTerminator()->getDebugLoc() : DebugLoc();
2195 return Affinator.getPwAff(
SE->getZero(E->getType()), BB, RecordedAssumptions);
2220 if (!Predicate(*MA))
2224 isl::map AccessDomain = MA->getAccessRelation();
2226 Accesses = Accesses.
unite(AccessDomain);
2260 return Tree.get_map();
2280 bool Changed =
false;
2285 if (StmtDomain.
is_subset(NewStmtDomain))
2290 NewStmtDomain = NewStmtDomain.
coalesce();
2303 std::vector<Instruction *> Instructions) {
2304 assert(BB &&
"Unexpected nullptr!");
2305 Stmts.emplace_back(*
this, *BB, Name, SurroundingLoop, Instructions);
2306 auto *Stmt = &
Stmts.back();
2308 for (Instruction *Inst : Instructions) {
2310 "Unexpected statement corresponding to the instruction.");
2316 std::vector<Instruction *> Instructions) {
2317 assert(
R &&
"Unexpected nullptr!");
2318 Stmts.emplace_back(*
this, *
R, Name, SurroundingLoop, Instructions);
2319 auto *Stmt = &
Stmts.back();
2321 for (Instruction *Inst : Instructions) {
2323 "Unexpected statement corresponding to the instruction.");
2327 for (BasicBlock *BB :
R->blocks()) {
2329 if (BB ==
R->getEntry())
2331 for (Instruction &Inst : *BB) {
2333 "Unexpected statement corresponding to the instruction.");
2345 "Target access not defined for complete statement domain");
2347 "Source access not defined for complete statement domain");
2349 Stmts.emplace_back(*
this, SourceRel, TargetRel,
Domain);
2351 return &(
Stmts.back());
2355 auto StmtMapIt =
StmtMap.find(BB);
2356 if (StmtMapIt ==
StmtMap.end())
2358 return StmtMapIt->second;
2362 auto *
PHI = cast<PHINode>(U.getUser());
2363 BasicBlock *IncomingBB =
PHI->getIncomingBlock(U);
2367 if (
auto *IncomingInst = dyn_cast<Instruction>(U.get())) {
2368 if (IncomingInst->getParent() == IncomingBB) {
2370 return IncomingStmt;
2380 if (!StmtList.empty())
2381 return StmtList.back();
2386 if (RN->isSubRegion())
2396 if (!L || !
R.contains(L))
2399 if (
R.isTopLevelRegion()) {
2401 return L->getLoopDepth() - 1;
2403 Loop *OuterLoop =
R.outermostLoopInRegion(
const_cast<Loop *
>(L));
2405 return L->getLoopDepth() - OuterLoop->getLoopDepth();
2410 for (
auto &SAI :
arrays()) {
2411 if (SAI->getName() == BaseName)
2419 assert(SAI &&
"can only use after access relations have been constructed");
2432 llvm::erase(Uses, Access);
2438 llvm::erase(Incomings, Access);
2445 Instruction *Val = dyn_cast<Instruction>(SAI->
getBasePtr());
2479 assert(
contains(Inst) &&
"The concept of escaping makes only sense for "
2480 "values defined inside the SCoP");
2482 for (Use &Use : Inst->uses()) {
2491 isExit(cast<PHINode>(Use.getUser())->getParent()))
2498 AssumptionsAliasing += step;
2503#if !defined(NDEBUG) || defined(LLVM_ENABLE_STATS)
2506 int NumTotalLoops = LoopStat.NumLoops;
2510 for (
const ScopStmt &Stmt : *
this) {
2517 if (MA->isLatestValueKind()) {
2523 if (MA->isLatestAnyPHIKind()) {
2530 MA->getAccessRelation().intersect_domain(
Domain).range();
2549 AU.addRequired<LoopInfoWrapperPass>();
2550 AU.addRequired<RegionInfoPass>();
2551 AU.addRequired<DominatorTreeWrapperPass>();
2552 AU.addRequiredTransitive<ScalarEvolutionWrapperPass>();
2554 AU.addRequired<AAResultsWrapperPass>();
2555 AU.addRequired<AssumptionCacheTracker>();
2556 AU.addRequired<OptimizationRemarkEmitterWrapperPass>();
2557 AU.setPreservesAll();
2567 std::max(MaxNumLoopsInScop.getValue(), (uint64_t)Stats.
NumLoops);
2570 NumScopsDepthZero++;
2576 NumScopsDepthThree++;
2578 NumScopsDepthFour++;
2580 NumScopsDepthFive++;
2582 NumScopsDepthLarger++;
2596 auto &SD = getAnalysis<ScopDetectionWrapperPass>().getSD();
2598 if (!SD.isMaxRegionInScop(*R))
2601 Function *F = R->getEntry()->getParent();
2602 auto &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();
2603 auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
2604 auto &AA = getAnalysis<AAResultsWrapperPass>().getAAResults();
2605 auto const &DL = F->getParent()->getDataLayout();
2606 auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
2607 auto &AC = getAnalysis<AssumptionCacheTracker>().getAssumptionCache(*F);
2608 auto &ORE = getAnalysis<OptimizationRemarkEmitterWrapperPass>().getORE();
2610 ScopBuilder SB(R, AC, AA, DL, DT, LI, SD, SE, ORE);
2613#if !defined(NDEBUG) || defined(LLVM_ENABLE_STATS)
2628 OS <<
"Invalid Scop!\n";
2636 "Polly - Create polyhedral description of Scops",
false,
2646 "Polly - Create polyhedral description of Scops",
false,
2654class ScopInfoPrinterLegacyRegionPass final :
public RegionPass {
2658 ScopInfoPrinterLegacyRegionPass() : ScopInfoPrinterLegacyRegionPass(outs()) {}
2660 explicit ScopInfoPrinterLegacyRegionPass(llvm::raw_ostream &OS)
2663 bool runOnRegion(Region *R, RGPassManager &RGM)
override {
2666 OS <<
"Printing analysis '" << P.getPassName() <<
"' for region: '"
2667 << R->getNameStr() <<
"' in function '"
2668 << R->getEntry()->getParent()->getName() <<
"':\n";
2674 void getAnalysisUsage(AnalysisUsage &AU)
const override {
2675 RegionPass::getAnalysisUsage(AU);
2677 AU.setPreservesAll();
2681 llvm::raw_ostream &OS;
2684char ScopInfoPrinterLegacyRegionPass::ID = 0;
2688 return new ScopInfoPrinterLegacyRegionPass(OS);
2692 "Polly - Print polyhedral description of Scops",
false,
2696 "Polly - Print polyhedral description of Scops",
false,
2702 LoopInfo &LI, AliasAnalysis &AA, DominatorTree &DT,
2703 AssumptionCache &AC, OptimizationRemarkEmitter &ORE)
2704 : DL(DL), SD(SD), SE(SE), LI(LI), AA(AA), DT(DT), AC(AC), ORE(ORE) {
2712 for (
auto &It :
SD) {
2713 Region *R =
const_cast<Region *
>(It);
2714 if (!
SD.isMaxRegionInScop(*R))
2718 std::unique_ptr<Scop>
S = SB.
getScop();
2721#if !defined(NDEBUG) || defined(LLVM_ENABLE_STATS)
2727 assert(Inserted &&
"Building Scop for the same region twice!");
2733 FunctionAnalysisManager::Invalidator &Inv) {
2737 return !(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>()) ||
2739 Inv.invalidate<ScalarEvolutionAnalysis>(F, PA) ||
2740 Inv.invalidate<LoopAnalysis>(F, PA) ||
2741 Inv.invalidate<AAManager>(F, PA) ||
2742 Inv.invalidate<DominatorTreeAnalysis>(F, PA) ||
2743 Inv.invalidate<AssumptionAnalysis>(F, PA);
2749 FunctionAnalysisManager &FAM) {
2751 auto &SE = FAM.getResult<ScalarEvolutionAnalysis>(F);
2752 auto &LI = FAM.getResult<LoopAnalysis>(F);
2753 auto &AA = FAM.getResult<AAManager>(F);
2754 auto &DT = FAM.getResult<DominatorTreeAnalysis>(F);
2755 auto &AC = FAM.getResult<AssumptionAnalysis>(F);
2756 auto &DL = F.getParent()->getDataLayout();
2757 auto &ORE = FAM.getResult<OptimizationRemarkEmitterAnalysis>(F);
2758 return {DL, SD, SE, LI, AA, DT, AC, ORE};
2762 FunctionAnalysisManager &FAM) {
2766 for (
auto &It : reverse(SI)) {
2770 Stream <<
"Invalid Scop!\n";
2772 return PreservedAnalyses::all();
2776 AU.addRequired<LoopInfoWrapperPass>();
2777 AU.addRequired<RegionInfoPass>();
2778 AU.addRequired<DominatorTreeWrapperPass>();
2779 AU.addRequiredTransitive<ScalarEvolutionWrapperPass>();
2781 AU.addRequired<AAResultsWrapperPass>();
2782 AU.addRequired<AssumptionCacheTracker>();
2783 AU.addRequired<OptimizationRemarkEmitterWrapperPass>();
2784 AU.setPreservesAll();
2788 auto &SD = getAnalysis<ScopDetectionWrapperPass>().getSD();
2789 auto &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();
2790 auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
2791 auto &AA = getAnalysis<AAResultsWrapperPass>().getAAResults();
2792 auto const &DL = F.getParent()->getDataLayout();
2793 auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
2794 auto &AC = getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
2795 auto &ORE = getAnalysis<OptimizationRemarkEmitterWrapperPass>().getORE();
2802 for (
auto &It : *
Result) {
2806 OS <<
"Invalid Scop!\n";
2818 "Polly - Create polyhedral description of all Scops of a function",
false,
2829 "Polly - Create polyhedral description of all Scops of a function",
false,
2836class ScopInfoPrinterLegacyFunctionPass final :
public FunctionPass {
2840 ScopInfoPrinterLegacyFunctionPass()
2841 : ScopInfoPrinterLegacyFunctionPass(outs()) {}
2842 explicit ScopInfoPrinterLegacyFunctionPass(llvm::raw_ostream &OS)
2845 bool runOnFunction(
Function &F)
override {
2848 OS <<
"Printing analysis '" << P.getPassName() <<
"' for function '"
2849 << F.getName() <<
"':\n";
2855 void getAnalysisUsage(AnalysisUsage &AU)
const override {
2856 FunctionPass::getAnalysisUsage(AU);
2858 AU.setPreservesAll();
2862 llvm::raw_ostream &OS;
2865char ScopInfoPrinterLegacyFunctionPass::ID = 0;
2869 return new ScopInfoPrinterLegacyFunctionPass(OS);
2873 ScopInfoPrinterLegacyFunctionPass,
"polly-print-function-scops",
2874 "Polly - Print polyhedral description of all Scops of a function",
false,
2878 ScopInfoPrinterLegacyFunctionPass,
"polly-print-function-scops",
2879 "Polly - Print polyhedral description of all Scops of a function",
false,
INITIALIZE_PASS_BEGIN(DependenceInfo, "polly-dependences", "Polly - Calculate dependences", false, false)
INITIALIZE_PASS_END(DependenceInfo, "polly-dependences", "Polly - Calculate dependences", false, false) namespace
INITIALIZE_PASS_DEPENDENCY(ScopInfoRegionPass)
polly dump Polly Dump Function
polly dump Polly Dump Module
llvm::cl::OptionCategory PollyCategory
static void updateLoopCountStatistic(ScopDetection::LoopStats Stats, bool OnlyProfitable)
static RegisterPass< ScopPrinterWrapperPass > M("dot-scops", "Polly - Print Scops of function")
static isl::set simplifyAssumptionContext(isl::set AssumptionContext, const Scop &S)
static isl::set addRangeBoundsToSet(isl::set S, const ConstantRange &Range, int dim, isl::dim type)
static cl::opt< bool > PollyPrintInstructions("polly-print-instructions", cl::desc("Output instructions per ScopStmt"), cl::Hidden, cl::Optional, 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 isl::map getEqualAndLarger(isl::space SetDomain)
static cl::opt< bool > PollyRemarksMinimal("polly-remarks-minimal", cl::desc("Do not emit remarks about assumptions that are known"), cl::Hidden, cl::cat(PollyCategory))
static std::string toString(AssumptionKind Kind)
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::cat(PollyCategory))
static int const MaxDisjunctsInContext
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::list< std::string > IslArgs("polly-isl-arg", cl::value_desc("argument"), cl::desc("Option passed to ISL"), 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))
STATISTIC(AssumptionsAliasing, "Number of aliasing assumptions taken.")
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))
static int const MaxDisjunktsInDefinedBehaviourContext
static const ScopArrayInfo * identifyBasePtrOriginSAI(Scop *S, Value *BasePtr)
polly scop functions based on how much of the function is a scop
isl::aff pullback(isl::multi_aff ma) const
isl::aff mod(isl::val mod) const
isl::aff div(isl::aff aff2) const
static isl::aff var_on_domain(isl::local_space ls, isl::dim type, unsigned int pos)
isl::aff add(isl::aff aff2) const
static isl::basic_map from_domain_and_range(isl::basic_set domain, isl::basic_set range)
static isl::basic_set universe(isl::space space)
static isl::constraint alloc_inequality(isl::local_space ls)
static isl::constraint alloc_equality(isl::local_space ls)
static isl::id alloc(isl::ctx ctx, const std::string &name, void *user)
isl::map add_constraint(isl::constraint constraint) const
isl::map align_params(isl::space model) const
isl::map detect_equalities() const
isl::map equate(isl::dim type1, int pos1, isl::dim type2, int pos2) const
static isl::map universe(isl::space space)
class size domain_tuple_dim() const
isl::map gist_domain(isl::set context) const
isl::map upper_bound_si(isl::dim type, unsigned int pos, int value) const
isl::map set_tuple_id(isl::dim type, isl::id id) const
isl::map fix_si(isl::dim type, unsigned int pos, int value) const
static isl::map from_domain_and_range(isl::set domain, isl::set range)
isl::map sum(isl::map map2) const
isl::map intersect_range(isl::set set) const
isl::map apply_range(isl::map map2) const
isl::map unite(isl::map map2) const
static isl::map from_union_map(isl::union_map umap)
static isl::map from_multi_aff(isl::multi_aff maff)
static isl::map lex_gt(isl::space set_space)
isl::map apply_domain(isl::map map2) const
isl::space get_space() const
isl::map gist_params(isl::set context) const
static isl::map from_aff(isl::aff aff)
isl::map lower_bound_si(isl::dim type, unsigned int pos, int value) const
isl::map intersect_domain(isl::set set) const
static isl::map from_pw_aff(isl::pw_aff pwaff)
isl::map order_lt(isl::dim type1, int pos1, isl::dim type2, int pos2) const
isl::multi_aff identity() const
isl::multi_aff set_aff(int pos, isl::aff el) const
static isl::multi_union_pw_aff from_union_map(isl::union_map umap)
isl::set lt_set(isl::pw_aff pwaff2) const
static isl::pw_aff var_on_domain(isl::local_space ls, isl::dim type, unsigned int pos)
isl::space get_space() const
isl::set le_set(isl::pw_aff pwaff2) const
isl::pw_aff set_tuple_id(isl::dim type, isl::id id) const
isl::pw_aff add_dims(isl::dim type, unsigned int n) const
isl::id get_tuple_id(isl::dim type) const
static isl::pw_multi_aff from_map(isl::map map)
static isl::schedule from_domain(isl::union_set domain)
isl::set intersect(isl::set set2) const
static isl::set universe(isl::space space)
isl::set fix_si(isl::dim type, unsigned int pos, int value) const
isl::set complement() const
isl::set gist_params(isl::set context) const
boolean is_subset(const isl::set &set2) const
isl::set intersect_params(isl::set params) const
static isl::set empty(isl::space space)
isl::set align_params(isl::space model) const
class size tuple_dim() const
isl::space get_space() const
isl::set apply(isl::map map) const
__isl_give isl_set * release()
isl::set reset_tuple_id() const
boolean is_disjoint(const isl::set &set2) const
isl::set unite(isl::set set2) const
boolean is_equal(const isl::set &set2) const
isl::set remove_divs() const
boolean is_singleton() const
isl::space set_dim_id(isl::dim type, unsigned int pos, isl::id id) const
int find_dim_by_id(isl::dim type, const isl::id &id) const
isl::space map_from_domain_and_range(isl::space range) const
boolean has_tuple_id(isl::dim type) const
static isl::space params_alloc(isl::ctx ctx, unsigned int nparam)
isl::space domain() const
class size dim(isl::dim type) const
isl::id get_dim_id(isl::dim type, unsigned int pos) const
isl::id get_tuple_id(isl::dim type) const
isl::space map_from_set() const
isl::space align_params(isl::space space2) const
boolean has_equal_tuples(const isl::space &space2) const
isl::union_map unite(isl::union_map umap2) const
isl::union_map coalesce() const
static isl::union_map empty(isl::ctx ctx)
isl::union_map intersect_domain(isl::space space) const
boolean is_subset(const isl::union_set &uset2) const
isl::union_set coalesce() const
isl::union_set intersect(isl::union_set uset2) const
isl::set extract_set(isl::space space) const
isl::val sub(isl::val v2) const
Utility proxy to wrap the common members of LoadInst and StoreInst.
Represent memory accesses in statements.
const ScopArrayInfo * getLatestScopArrayInfo() const
Get the ScopArrayInfo object for the base address, or the one set by setNewAccessRelation().
std::string getAccessRelationStr() const
Get an isl string representing the latest access relation.
isl::map getNewAccessRelation() const
Get the new access function imported or set by a pass.
void dump() const
Print the MemoryAccess to stderr.
isl::set assumeNoOutOfBound()
isl::id getArrayId() const
Old name of getOriginalArrayId().
SmallVector< const SCEV *, 4 > Sizes
Size of each dimension of the accessed array.
void foldAccessRelation()
Fold the memory access to consider parametric offsets.
AssertingVH< Value > AccessValue
The value associated with this memory access.
bool isOriginalValueKind() const
Was this MemoryAccess detected as a scalar dependences?
isl::space getOriginalAccessRelationSpace() const
Return the space in which the access relation lives in.
bool isAnyPHIKind() const
Old name of isOriginalAnyPHIKind().
AccessType
The access type of a memory access.
ReductionType
Reduction access type.
@ RT_BOTTOM
Pseudo type for the data flow analysis.
@ RT_NONE
Indicate no reduction at all.
isl::basic_map createBasicAccessMap(ScopStmt *Statement)
SubscriptsTy Subscripts
Subscript expression for each dimension.
isl::map getLatestAccessRelation() const
Return the newest access relation of this access.
isl::id getOriginalArrayId() const
Get the detection-time base array isl::id for this access.
isl::pw_aff getPwAff(const SCEV *E)
Compute the isl representation for the SCEV E wrt.
Instruction * AccessInstruction
The access instruction of this memory access.
void computeBoundsOnAccessRelation(unsigned ElementSize)
Compute bounds on an over approximated access relation.
bool isValueKind() const
Old name of isOriginalValueKind().
bool hasNewAccessRelation() const
Check if a new access relation was imported or set by a pass.
isl::id Id
A unique identifier for this memory access.
bool isWrite() const
Is this a write memory access?
bool IsAffine
Are all the subscripts affine expression?
ReductionType getReductionType() const
Get the reduction type of this access.
const ScopArrayInfo * getOriginalScopArrayInfo() const
Get the detection-time ScopArrayInfo object for the base address.
AssertingVH< Value > BaseAddr
The base address (e.g., A for A[i+j]).
bool isOriginalAnyPHIKind() const
Was this access detected as one of the two PHI types?
void updateDimensionality()
Update the dimensionality of the memory access.
Instruction * getAccessInstruction() const
Return the access instruction of this memory access.
bool isStrideZero(isl::map Schedule) const
Is always the same memory accessed for a given statement instance set?
bool isLatestPartialAccess() const
Return whether the MemoryyAccess is a partial access.
std::string getOriginalAccessRelationStr() const
Get an isl string representing the access function read from IR.
isl::set InvalidDomain
The domain under which this access is not modeled precisely.
bool isRead() const
Is this a read memory access?
void buildAccessRelation(const ScopArrayInfo *SAI)
Assemble the access relation from all available information.
isl::id getId() const
Get identifier for the memory access.
isl::map NewAccessRelation
Updated access relation read from JSCOP file.
isl::map getAddressFunction() const
Get an isl map describing the memory address accessed.
void setAccessRelation(isl::map AccessRelation)
Update the original access relation.
bool isMustWrite() const
Is this a must-write memory access?
bool isScalarKind() const
Old name of isOriginalScalarKind.
isl::map AccessRelation
Relation from statement instances to the accessed array elements.
void realignParams()
Align the parameters in the access relation to the scop context.
Type * getElementType() const
Return the element type of the accessed array wrt. this access.
bool isOriginalPHIKind() const
Was this MemoryAccess detected as a special PHI node access?
void print(raw_ostream &OS) const
Print the MemoryAccess.
const ScopArrayInfo * getScopArrayInfo() const
Legacy name of getOriginalScopArrayInfo().
void wrapConstantDimensions()
Carry index overflows of dimensions with constant size to the next higher dimension.
ScopStmt * Statement
Parent ScopStmt of this access.
bool isStrideX(isl::map Schedule, int StrideWidth) const
Is the stride of the access equal to a certain width?
bool isStrideOne(isl::map Schedule) const
Is consecutive memory accessed for a given statement instance set?
Type * ElementType
Type a single array element wrt. this access.
enum AccessType AccType
Whether it a reading or writing access, and if writing, whether it is conditional (MAY_WRITE).
std::string getNewAccessRelationStr() const
Get an isl string representing a new access function, if available.
void buildMemIntrinsicAccessRelation()
Create the access relation for the underlying memory intrinsic.
Value * getOriginalBaseAddr() const
Get the original base address of this access (e.g.
ScopStmt * getStatement() const
Get the statement that contains this memory access.
bool isAffine() const
Is the memory access affine?
isl::set getStride(isl::map Schedule) const
Get the stride of this memory access in the specified Schedule.
bool isMayWrite() const
Is this a may-write memory access?
isl::id getLatestArrayId() const
Get the base array isl::id for this access, modifiable through setNewAccessRelation().
MemoryKind Kind
What is modeled by this MemoryAccess.
isl::pw_multi_aff applyScheduleToAccessRelation(isl::union_map Schedule) const
Return the access relation after the schedule was applied.
MemoryAccess(ScopStmt *Stmt, Instruction *AccessInst, AccessType AccType, Value *BaseAddress, Type *ElemType, bool Affine, ArrayRef< const SCEV * > Subscripts, ArrayRef< const SCEV * > Sizes, Value *AccessValue, MemoryKind Kind)
Create a new MemoryAccess.
std::string getReductionOperatorStr() const
Return a string representation of the access's reduction type.
isl::map getAccessRelation() const
Old name of getLatestAccessRelation().
Value * getAccessValue() const
Return the access value of this memory access.
isl::map getOriginalAccessRelation() const
Get the original access function as read from IR.
void setNewAccessRelation(isl::map NewAccessRelation)
Set the updated access relation read from JSCOP file.
bool isArrayKind() const
Old name of isOriginalArrayKind.
bool isMemoryIntrinsic() const
Is this a memory intrinsic access (memcpy, memset, memmove)?
A class to store information about arrays in the SCoP.
const SCEV * getDimensionSize(unsigned Dim) const
Return the size of dimension dim as SCEV*.
Type * ElementType
The canonical element type of this array.
isl::space getSpace() const
Get the space of this array access.
isl::id Id
The isl id for the base pointer.
SmallVector< isl::pw_aff, 4 > DimensionSizesPw
The sizes of each dimension as isl::pw_aff.
bool isExitPHIKind() const
Is this array info modeling an MemoryKind::ExitPHI?
bool isReadOnly()
If the array is read only.
bool updateSizes(ArrayRef< const SCEV * > Sizes, bool CheckConsistency=true)
Update the sizes of the ScopArrayInfo object.
~ScopArrayInfo()
Destructor to free the isl id of the base pointer.
bool isValueKind() const
Is this array info modeling an llvm::Value?
ScopArrayInfo(Value *BasePtr, Type *ElementType, isl::ctx IslCtx, ArrayRef< const SCEV * > DimensionSizes, MemoryKind Kind, const DataLayout &DL, Scop *S, const char *BaseName=nullptr)
Construct a ScopArrayInfo object.
static const ScopArrayInfo * getFromId(isl::id Id)
Access the ScopArrayInfo associated with an isl Id.
std::string getName() const
Get the name of this memory reference.
bool isPHIKind() const
Is this array info modeling special PHI node memory?
Value * getBasePtr() const
Return the base pointer.
int getElemSizeInBytes() const
Get element size in bytes.
isl::pw_aff getDimensionSizePw(unsigned Dim) const
Return the size of dimension dim as isl::pw_aff.
AssertingVH< Value > BasePtr
The base pointer.
bool isCompatibleWith(const ScopArrayInfo *Array) const
Verify that Array is compatible to this ScopArrayInfo.
void addDerivedSAI(ScopArrayInfo *DerivedSAI)
void updateElementType(Type *NewElementType)
Update the element type of the ScopArrayInfo object.
const ScopArrayInfo * BasePtrOriginSAI
For indirect accesses this is the SAI of the BP origin.
const DataLayout & DL
The data layout of the module.
isl::id getBasePtrId() const
Return the isl id for the base pointer.
Scop & S
The scop this SAI object belongs to.
static const ScopArrayInfo * getFromAccessFunction(isl::pw_multi_aff PMA)
Access the ScopArrayInfo associated with an access function.
unsigned getNumberOfDimensions() const
Return the number of dimensions.
void print(raw_ostream &OS, bool SizeAsPwAff=false) const
Print a readable representation to OS.
Type * getElementType() const
Get the canonical element type of this array.
SmallVector< const SCEV *, 4 > DimensionSizes
The sizes of each dimension as SCEV*.
MemoryKind Kind
The type of this scop array info object.
void dump() const
Dump a readable representation to stderr.
Build the Polly IR (Scop and ScopStmt) on a Region.
std::unique_ptr< Scop > getScop()
Try to build the Polly IR of static control part on the current SESE-Region.
Pass to detect the maximal static control parts (Scops) of a function.
static ScopDetection::LoopStats countBeneficialLoops(Region *R, ScalarEvolution &SE, LoopInfo &LI, unsigned MinProfitableTrips)
Count the number of loops and the maximal loop depth in R.
The legacy pass manager's analysis pass to compute scop information for a region.
std::unique_ptr< Scop > S
The Scop pointer which is used to construct a Scop.
void print(raw_ostream &O, const Module *M=nullptr) const override
void getAnalysisUsage(AnalysisUsage &AU) const override
bool runOnRegion(Region *R, RGPassManager &RGM) override
Calculate the polyhedral scop information for a given Region.
The legacy pass manager's analysis pass to compute scop information for the whole function.
void getAnalysisUsage(AnalysisUsage &AU) const override
void print(raw_ostream &O, const Module *M=nullptr) const override
bool runOnFunction(Function &F) override
Calculate all the polyhedral scops for a given function.
std::unique_ptr< ScopInfo > Result
bool invalidate(Function &F, const PreservedAnalyses &PA, FunctionAnalysisManager::Invalidator &Inv)
Handle invalidation explicitly.
void recompute()
Recompute the Scop-Information for a function.
OptimizationRemarkEmitter & ORE
RegionToScopMapTy RegionToScopMap
A map of Region to its Scop object containing Polly IR of static control part.
BasicBlock * getEntryBlock() const
Return a BasicBlock from this statement.
void dump() const
Print the ScopStmt to stderr.
bool isEmpty() const
Return true if this statement does not contain any accesses.
std::vector< Instruction * > Instructions
Vector for Instructions in this statement.
void print(raw_ostream &OS, bool PrintInstructions) const
Print the ScopStmt.
Region * R
The region represented by this statement (in the non-affine case).
DenseMap< PHINode *, MemoryAccess * > PHIWrites
Map from PHI nodes to its incoming value when coming from this statement.
isl::set Domain
The iteration domain describes the set of iterations for which this statement is executed.
const std::vector< Instruction * > & getInstructions() const
bool isBlockStmt() const
Return true if this statement represents a single basic block.
void removeSingleMemoryAccess(MemoryAccess *MA, bool AfterHoisting=true)
Remove MA from this statement.
MemoryAccess * ensureValueRead(Value *V)
Check whether there is a value read access for V in this statement, and if not, create one.
Loop * SurroundingLoop
The closest loop that contains this statement.
ScopStmt(Scop &parent, BasicBlock &bb, StringRef Name, Loop *SurroundingLoop, std::vector< Instruction * > Instructions)
Create the ScopStmt from a BasicBlock.
MemoryAccess * lookupInputAccessOf(Value *Val) const
Return the input access of the value, or null if no such MemoryAccess exists.
std::string getScheduleStr() const
Get an isl string representing this schedule.
std::string getDomainStr() const
Get an isl string representing this domain.
void realignParams()
Align the parameters in the statement to the scop context.
void removeAccessData(MemoryAccess *MA)
Remove MA from dictionaries pointing to them.
isl::map getSchedule() const
Get the schedule function of this ScopStmt.
isl::set getInvalidDomain() const
Get the invalid domain for this statement.
SmallVector< Loop *, 4 > NestLoops
DenseMap< const Instruction *, MemoryAccessList > InstructionToAccess
Mapping from instructions to (scalar) memory accesses.
Scop & Parent
Polyhedral description.
void restrictDomain(isl::set NewDomain)
Restrict the domain of the statement.
isl::ctx getIslCtx() const
Get an isl_ctx pointer.
Region * getRegion() const
Get the region represented by this ScopStmt (if any).
DenseMap< Instruction *, MemoryAccess * > ValueWrites
The set of values defined in this ScopStmt that are required elsewhere, mapped to their MemoryKind::V...
BasicBlock * getBasicBlock() const
Get the BasicBlock represented by this ScopStmt (if any).
void removeMemoryAccess(MemoryAccess *MA)
Remove a MemoryAccess from this statement.
MemoryAccessVec MemAccs
The memory accesses of this statement.
const char * getBaseName() const
DenseMap< Value *, MemoryAccess * > ValueReads
The set of values defined elsewhere required in this ScopStmt and their MemoryKind::Value READ Memory...
isl::set InvalidDomain
The domain under which this statement is not modeled precisely.
DenseMap< PHINode *, MemoryAccess * > PHIReads
Map from PHI nodes to its read access in this statement.
isl::id getDomainId() const
Get the id of the iteration domain space.
void addAccess(MemoryAccess *Access, bool Prepend=false)
Add Access to this statement's list of accesses.
bool isRegionStmt() const
Return true if this statement represents a whole region.
void setInvalidDomain(isl::set ID)
Set the invalid context for this statement to ID.
unsigned getNumIterators() const
Loop * getLoopForDimension(unsigned Dimension) const
Get the loop for a dimension.
isl::set getDomain() const
Get the iteration domain of this ScopStmt.
BasicBlock * BB
A SCoP statement represents either a basic block (affine/precise case) or a whole region (non-affine ...
isl::space getDomainSpace() const
Get the space of the iteration domain.
void printInstructions(raw_ostream &OS) const
Print the instructions in ScopStmt.
InvariantEquivClassTy * lookupInvariantEquivClass(Value *Val)
Return the invariant equivalence class for Val if any.
isl::schedule getScheduleTree() const
Get a schedule tree describing the schedule of all statements.
isl::set InvalidContext
The restrictions under which this SCoP was built.
void intersectDefinedBehavior(isl::set Set, AssumptionSign Sign)
Add the conditions from Set (or subtract them if Sign is AS_RESTRICTION) to the defined behaviour con...
isl::space getFullParamSpace() const
Return the full space of parameters.
ArrayRef< MemoryAccess * > getValueUses(const ScopArrayInfo *SAI) const
Return all MemoryAccesses that us an llvm::Value, represented by a ScopArrayInfo.
DenseMap< const ScopArrayInfo *, SmallVector< MemoryAccess *, 4 > > ValueUseAccs
List of all uses (i.e.
isl::union_map getMayWrites()
Get a union map of all may-writes performed in the SCoP.
void printContext(raw_ostream &OS) const
isl::set getInvalidContext() const
Get the invalid context for this Scop.
void dump() const
Print the ScopStmt to stderr.
isl::union_map getSchedule() const
Get the schedule of all the statements in the SCoP.
void invalidate(AssumptionKind Kind, DebugLoc Loc, BasicBlock *BB=nullptr)
Mark the scop as invalid.
MemoryAccess * getValueDef(const ScopArrayInfo *SAI) const
Return the MemoryAccess that writes an llvm::Value, represented by a ScopArrayInfo.
ScalarEvolution * getSE() const
Return the scalar evolution.
unsigned getMaxLoopDepth() const
Get the maximum depth of the loop.
void printAliasAssumptions(raw_ostream &OS) const
ArrayRef< MemoryAccess * > getPHIIncomings(const ScopArrayInfo *SAI) const
Return all MemoryAccesses for all incoming statements of a PHINode, represented by a ScopArrayInfo.
ScopStmt * getStmtFor(Instruction *Inst) const
Return the ScopStmt an instruction belongs to, or nullptr if it does not belong to any statement in t...
ScopArrayInfo * getScopArrayInfo(Value *BasePtr, MemoryKind Kind)
Return the cached ScopArrayInfo object for BasePtr.
ParameterSetTy Parameters
Parameters of this Scop.
ArrayInfoSetTy ScopArrayInfoSet
A set to remember ScopArrayInfo objects.
ValueToValueMap InvEquivClassVMap
Mapping from invariant loads to the representing invariant load of their equivalence class.
isl::union_map getReads()
Get a union map of all reads performed in the SCoP.
unsigned getCopyStmtsNum()
Get the count of copy statements added to this Scop.
unsigned CopyStmtsNum
Number of copy statements.
DenseMap< BasicBlock *, std::vector< ScopStmt * > > StmtMap
A map from basic blocks to vector of SCoP statements.
void addParams(const ParameterSetTy &NewParameters)
Take a list of parameters and add the new ones to the scop.
isl::set getAssumedContext() const
Get the assumed context for this Scop.
void addScopStmt(BasicBlock *BB, StringRef Name, Loop *SurroundingLoop, std::vector< Instruction * > Instructions)
Create a new SCoP statement for BB.
SCEVAffinator Affinator
The affinator used to translate SCEVs to isl expressions.
ScopArrayInfo * getOrCreateScopArrayInfo(Value *BasePtr, Type *ElementType, ArrayRef< const SCEV * > Sizes, MemoryKind Kind, const char *BaseName=nullptr)
Return the (possibly new) ScopArrayInfo object for Access.
void addAccessFunction(MemoryAccess *Access)
Add the access function to all MemoryAccess objects of the Scop created in this pass.
isl::schedule Schedule
The schedule of the SCoP.
isl::set getBestKnownDefinedBehaviorContext() const
Return the define behavior context, or if not available, its approximation from all other contexts.
isl::set Context
Constraints on parameters.
isl::union_set getDomains() const
Get a union set containing the iteration domains of all statements.
const BoxedLoopsSetTy & getBoxedLoops() const
Return the set of boxed (thus overapproximated) loops.
std::shared_ptr< isl_ctx > IslCtx
Isl context.
std::string getAssumedContextStr() const
Get an isl string representing the assumed context.
bool isProfitable(bool ScalarsAreUnprofitable) const
Return true if this SCoP can be profitably optimized.
bool isDominatedBy(const DominatorTree &DT, BasicBlock *BB) const
Return true if and only if BB dominates the SCoP.
ScopArrayInfo * getArrayInfoByName(const std::string BaseName)
Find the ScopArrayInfo associated with an isl Id that has name Name.
void addAccessData(MemoryAccess *Access)
Add metadata for Access.
isl::set getDomainConditions(const ScopStmt *Stmt) const
Return the domain of Stmt.
PWACtx getPwAff(const SCEV *E, BasicBlock *BB=nullptr, bool NonNegative=false, RecordedAssumptionsTy *RecordedAssumptions=nullptr)
Compute the isl representation for the SCEV E.
DenseMap< Value *, MemoryAccess * > ValueDefAccs
Map of values to the MemoryAccess that writes its definition.
isl::union_map getMustWrites()
Get a union map of all must-writes performed in the SCoP.
std::pair< std::string, std::string > getEntryExitStr() const
Get the name of the entry and exit blocks of this Scop.
isl::pw_aff getPwAffOnly(const SCEV *E, BasicBlock *BB=nullptr, RecordedAssumptionsTy *RecordedAssumptions=nullptr)
Compute the isl representation for the SCEV E.
ScopStatistics getStatistics() const
Collect statistic about this SCoP.
std::string getContextStr() const
Get an isl string representing the context.
std::pair< MinMaxVectorTy, MinMaxVectorTy > MinMaxVectorPairTy
Pair of minimal/maximal access vectors representing read write and read only accesses.
DenseMap< BasicBlock *, isl::set > DomainMap
A map from basic blocks to their domains.
isl::union_map getAccessesOfType(std::function< bool(MemoryAccess &)> Predicate)
Collect all memory access relations of a given type.
void removeStmts(function_ref< bool(ScopStmt &)> ShouldDelete, bool AfterHoisting=true)
Remove statements from the list of scop statements.
void buildContext()
Build the Context of the Scop.
int getRelativeLoopDepth(const Loop *L) const
Get the depth of a loop relative to the outermost loop in the Scop.
isl::ctx getIslCtx() const
Get the isl context of this static control part.
LoopInfo * getLI() const
Return the LoopInfo used for this Scop.
std::string getInvalidContextStr() const
Get an isl string representing the invalid context.
bool HasSingleExitEdge
True if the underlying region has a single exiting block.
DenseMap< Instruction *, ScopStmt * > InstStmtMap
A map from instructions to SCoP statements.
bool isEscaping(Instruction *Inst)
Return whether Inst has a use outside of this SCoP.
void removeStmtNotInDomainMap()
Removes all statements where the entry block of the statement does not have a corresponding domain in...
ScopDetection::DetectionContext & DC
The context of the SCoP created during SCoP detection.
void print(raw_ostream &OS, bool PrintInstructions) const
Print the static control part.
void printStatements(raw_ostream &OS, bool PrintInstructions) const
isl::union_map getWrites()
Get a union map of all writes performed in the SCoP.
void setSchedule(isl::union_map NewSchedule)
Update the current schedule.
void setContext(isl::set NewContext)
Set new isl context.
bool hasFeasibleRuntimeContext() const
Return true if the optimized SCoP can be executed.
DenseMap< const SCEV *, isl::id > ParameterIds
Mapping from parameters to their ids.
isl::space getParamSpace() const
Return space of isl context parameters.
bool isExit(BasicBlock *BB) const
Return true if BB is the exit block of the SCoP.
std::string getNameStr() const
Get the name of this Scop.
DenseMap< PHINode *, MemoryAccess * > PHIReadAccs
Map of values to the MemoryAccess that reads a PHI.
static void incrementNumberOfAliasingAssumptions(unsigned Step)
Increment actual number of aliasing assumptions taken.
std::pair< isl::pw_multi_aff, isl::pw_multi_aff > MinMaxAccessTy
Type to represent a pair of minimal/maximal access to an array.
std::optional< std::string > name
The name of the SCoP (identical to the regions name)
void createParameterId(const SCEV *Param)
Create an id for Param and store it in the ParameterIds map.
ArrayNameMapTy ScopArrayNameMap
A map to remember ScopArrayInfo objects for all names of memory references.
isl::set DefinedBehaviorContext
The context under which the SCoP must have defined behavior.
bool isEmpty() const
Return whether this scop is empty, i.e.
DenseMap< const ScopArrayInfo *, SmallVector< MemoryAccess *, 4 > > PHIIncomingAccs
List of all incoming values (write MemoryAccess) of a MemoryKind::PHI or MemoryKind::ExitPHI scalar.
isl::id getIdForParam(const SCEV *Parameter) const
Return the isl_id that represents a certain parameter.
InvariantEquivClassesTy InvariantEquivClasses
List of invariant accesses.
BasicBlock * getExitingBlock() const
Return the unique exiting block of the SCoP if any.
Region & R
The underlying Region.
OptimizationRemarkEmitter & ORE
OptimizationRemarkEmitter object for displaying diagnostic remarks.
bool ScheduleModified
Whether the schedule has been modified after derived from the CFG by ScopBuilder.
size_t getNumParams() const
Get the count of parameters used in this Scop.
void addParameterBounds()
Add the bounds of the parameters to the context.
bool restrictDomains(isl::union_set Domain)
Intersects the domains of all statements in the SCoP.
isl::union_map getAccesses()
Get a union map of all memory accesses performed in the SCoP.
ScopArrayInfo * createScopArrayInfo(Type *ElementType, const std::string &BaseName, const std::vector< unsigned > &Sizes)
Create an array and return the corresponding ScopArrayInfo object.
StmtSet Stmts
The statements in this Scop.
void removeAccessData(MemoryAccess *Access)
Remove the metadata stored for Access.
ArrayRef< ScopStmt * > getStmtListFor(BasicBlock *BB) const
Return the list of ScopStmts that represent the given BB.
MemoryAccess * getPHIRead(const ScopArrayInfo *SAI) const
Return the MemoryAccess that represents an llvm::PHINode.
bool contains(const Loop *L) const
Check if L is contained in the SCoP.
void realignParams()
Align the parameters in the statement to the scop context.
Function & getFunction() const
Return the function this SCoP is in.
ArrayInfoMapTy ScopArrayInfoMap
A map to remember ScopArrayInfo objects for all base pointers.
void printArrayInfo(raw_ostream &OS) const
Scop(Region &R, ScalarEvolution &SE, LoopInfo &LI, DominatorTree &DT, ScopDetection::DetectionContext &DC, OptimizationRemarkEmitter &ORE, int ID)
Scop constructor; invoked from ScopBuilder::buildScop.
const SCEV * getRepresentingInvariantLoadSCEV(const SCEV *S) const
Get the representing SCEV for S if applicable, otherwise S.
void simplifyContexts()
Simplify the assumed and invalid context.
bool hasSingleExitEdge() const
Return true if the underlying region has a single exiting block.
ScopArrayInfo * getScopArrayInfoOrNull(Value *BasePtr, MemoryKind Kind)
Return the cached ScopArrayInfo object for BasePtr.
MemoryAccess * lookupBasePtrAccess(MemoryAccess *MA)
Return the access for the base ptr of MA if any.
isl::set AssumedContext
The assumptions under which this scop was built.
void addAssumption(AssumptionKind Kind, isl::set Set, DebugLoc Loc, AssumptionSign Sign, BasicBlock *BB, bool RTC=true)
Add assumptions to assumed context.
MinMaxVectorPairVectorTy MinMaxAliasGroups
The set of minimal/maximal accesses for each alias group.
bool isEffectiveAssumption(isl::set Set, AssumptionSign Sign)
Check if the assumption in Set is trivial or not.
void simplifySCoP(bool AfterHoisting)
Simplify the SCoP representation.
ScopStmt * getIncomingStmtFor(const Use &U) const
Get the statement to put a PHI WRITE into.
bool trackAssumption(AssumptionKind Kind, isl::set Set, DebugLoc Loc, AssumptionSign Sign, BasicBlock *BB)
Track and report an assumption.
isl::set getContext() const
Get the constraint on parameter of this Scop.
void setScheduleTree(isl::schedule NewSchedule)
Update the current schedule.
BasicBlock * getEntry() const
Return the unique entry block of the SCoP.
const int ID
A number that uniquely represents a Scop within its function.
ScopStmt * getLastStmtFor(BasicBlock *BB) const
Return the last statement representing BB.
void removeFromStmtMap(ScopStmt &Stmt)
Removes Stmt from the StmtMap.
isl_ctx * isl_ctx_alloc(void)
int isl_ctx_parse_options(isl_ctx *ctx, int argc, char **argv, unsigned flags)
void isl_ctx_free(isl_ctx *ctx)
boolean manage(isl_bool val)
This file contains the declaration of the PolyhedralInfo class, which will provide an interface to ex...
std::forward_list< MemoryAccess * > MemoryAccessList
Ordered list type to hold accesses.
std::pair< isl::pw_aff, isl::set > PWACtx
The result type of the SCEVAffinator.
unsigned const MaxDisjunctsInDomain
std::string getIslCompatibleName(const std::string &Prefix, const llvm::Value *Val, long Number, const std::string &Suffix, bool UseInstructionNames)
Combine Prefix, Val (or Number) and Suffix to an isl-compatible name.
llvm::SetVector< const llvm::SCEV * > ParameterSetTy
Set type for parameters.
AssumptionSign
Enum to distinguish between assumptions and restrictions.
MemoryKind
The different memory kinds used in Polly.
@ Array
MemoryKind::Array: Models a one or multi-dimensional array.
@ Value
MemoryKind::Value: Models an llvm::Value.
@ PHI
MemoryKind::PHI: Models PHI nodes within the SCoP.
raw_ostream & operator<<(raw_ostream &OS, MemoryAccess::ReductionType RT)
llvm::Pass * createScopInfoWrapperPassPass()
llvm::Pass * createScopInfoPrinterLegacyRegionPass(llvm::raw_ostream &OS)
isl::val getConstant(isl::pw_aff PwAff, bool Max, bool Min)
If PwAff maps to a constant, return said constant.
bool hasDebugCall(ScopStmt *Stmt)
Does the statement contain a call to a debug function?
llvm::BasicBlock * getUseBlock(const llvm::Use &U)
Return the block in which a value is used.
isl::val valFromAPInt(isl_ctx *Ctx, const llvm::APInt Int, bool IsSigned)
Translate an llvm::APInt to an isl::val.
bool PollyProcessUnprofitable
std::pair< const llvm::SCEVConstant *, const llvm::SCEV * > extractConstantFactor(const llvm::SCEV *M, llvm::ScalarEvolution &SE)
Extract the constant factors from the multiplication M.
llvm::Pass * createScopInfoPrinterLegacyFunctionPass(llvm::raw_ostream &OS)
llvm::Pass * createScopInfoRegionPassPass()
llvm::SmallVector< Assumption, 8 > RecordedAssumptionsTy
AssumptionKind
Enumeration of assumptions Polly can take.
isl_stat isl_options_set_on_error(isl_ctx *ctx, int val)
#define ISL_ON_ERROR_ABORT
isl_stat isl_options_set_schedule_serialize_sccs(isl_ctx *ctx, int val)
__isl_give isl_space * isl_space_params_alloc(isl_ctx *ctx, unsigned nparam)
Type for equivalent invariant accesses and their domain context.
Context variables for SCoP detection.
Helper data structure to collect statistics about loop counts.
Result run(Function &, FunctionAnalysisManager &)
PreservedAnalyses run(Function &, FunctionAnalysisManager &)
int NumValueWritesInLoops
int NumSingletonWritesInLoops
static TupleKindPtr Domain("Domain")
static TupleKindPtr Range("Range")
__isl_give isl_union_set * isl_union_set_add_set(__isl_take isl_union_set *uset, __isl_take isl_set *set)
__isl_give isl_union_set * isl_union_set_empty(__isl_take isl_space *space)