Skip to content

Commit 189abad

Browse files
committedJun 12, 2019
[ScopBuilder] Move addInvariantLoads to ScopBuilder. NFC.
Moved addInvariantLoads and functions listed below to ScopBuilder: isAParameter canAlwaysBeHoisted These functions were referenced only by getNonHoistableCtx. Moved CLI parameter PollyAllowDereferenceOfAllFunctionParams to ScopBuilder. Added iterator range through InvariantEquivClasses. Patch by Dominik Adamski <adamski.dominik@gmail.com> Differential Revision: https://reviews.llvm.org/D63172 llvm-svn: 363216
1 parent 41e0b9f commit 189abad

File tree

4 files changed

+188
-180
lines changed

4 files changed

+188
-180
lines changed
 

‎polly/include/polly/ScopBuilder.h

+8
Original file line numberDiff line numberDiff line change
@@ -394,6 +394,14 @@ class ScopBuilder {
394394
/// Required inv. loads: LB[0], LB[1], (V, if it may alias with A or LB)
395395
void hoistInvariantLoads();
396396

397+
/// Add invariant loads listed in @p InvMAs with the domain of @p Stmt.
398+
void addInvariantLoads(ScopStmt &Stmt, InvariantAccessesTy &InvMAs);
399+
400+
/// Check if @p MA can always be hoisted without execution context.
401+
bool canAlwaysBeHoisted(MemoryAccess *MA, bool StmtInvalidCtxIsEmpty,
402+
bool MAInvalidCtxIsEmpty,
403+
bool NonHoistableCtxIsEmpty);
404+
397405
/// Return true if and only if @p LI is a required invariant load.
398406
bool isRequiredInvariantLoad(LoadInst *LI) const {
399407
return scop->getRequiredInvariantLoads().count(LI);

‎polly/include/polly/ScopInfo.h

+6-8
Original file line numberDiff line numberDiff line change
@@ -2033,11 +2033,6 @@ class Scop {
20332033
/// Return the access for the base ptr of @p MA if any.
20342034
MemoryAccess *lookupBasePtrAccess(MemoryAccess *MA);
20352035

2036-
/// Check if @p MA can always be hoisted without execution context.
2037-
bool canAlwaysBeHoisted(MemoryAccess *MA, bool StmtInvalidCtxIsEmpty,
2038-
bool MAInvalidCtxIsEmpty,
2039-
bool NonHoistableCtxIsEmpty);
2040-
20412036
/// Create an id for @p Param and store it in the ParameterIds map.
20422037
void createParameterId(const SCEV *Param);
20432038

@@ -2312,9 +2307,6 @@ class Scop {
23122307
InvEquivClassVMap[LoadInst] = ClassRep;
23132308
}
23142309

2315-
/// Add invariant loads listed in @p InvMAs with the domain of @p Stmt.
2316-
void addInvariantLoads(ScopStmt &Stmt, InvariantAccessesTy &InvMAs);
2317-
23182310
/// Remove the metadata stored for @p Access.
23192311
void removeAccessData(MemoryAccess *Access);
23202312

@@ -2340,6 +2332,12 @@ class Scop {
23402332
return make_range(Parameters.begin(), Parameters.end());
23412333
}
23422334

2335+
/// Return an iterator range containing invariant accesses.
2336+
iterator_range<InvariantEquivClassesTy::iterator> invariantEquivClasses() {
2337+
return make_range(InvariantEquivClasses.begin(),
2338+
InvariantEquivClasses.end());
2339+
}
2340+
23432341
/// Return whether this scop is empty, i.e. contains no statements that
23442342
/// could be executed.
23452343
bool isEmpty() const { return Stmts.empty(); }

‎polly/lib/Analysis/ScopBuilder.cpp

+174-1
Original file line numberDiff line numberDiff line change
@@ -76,6 +76,16 @@ static cl::opt<bool, true> XModelReadOnlyScalars(
7676
cl::location(ModelReadOnlyScalars), cl::Hidden, cl::ZeroOrMore,
7777
cl::init(true), cl::cat(PollyCategory));
7878

79+
static cl::opt<bool> PollyAllowDereferenceOfAllFunctionParams(
80+
"polly-allow-dereference-of-all-function-parameters",
81+
cl::desc(
82+
"Treat all parameters to functions that are pointers as dereferencible."
83+
" This is useful for invariant load hoisting, since we can generate"
84+
" less runtime checks. This is only valid if all pointers to functions"
85+
" are always initialized, so that Polly can choose to hoist"
86+
" their loads. "),
87+
cl::Hidden, cl::init(false), cl::cat(PollyCategory));
88+
7989
static cl::opt<bool> UnprofitableScalarAccs(
8090
"polly-unprofitable-scalar-accs",
8191
cl::desc("Count statements with scalar accesses as not optimizable"),
@@ -1343,7 +1353,7 @@ void ScopBuilder::hoistInvariantLoads() {
13431353
// Transfer the memory access from the statement to the SCoP.
13441354
for (auto InvMA : InvariantAccesses)
13451355
Stmt.removeMemoryAccess(InvMA.MA);
1346-
scop->addInvariantLoads(Stmt, InvariantAccesses);
1356+
addInvariantLoads(Stmt, InvariantAccesses);
13471357
}
13481358
}
13491359

@@ -1456,6 +1466,169 @@ isl::set ScopBuilder::getNonHoistableCtx(MemoryAccess *Access,
14561466
return WrittenCtx;
14571467
}
14581468

1469+
static bool isAParameter(llvm::Value *maybeParam, const Function &F) {
1470+
for (const llvm::Argument &Arg : F.args())
1471+
if (&Arg == maybeParam)
1472+
return true;
1473+
1474+
return false;
1475+
}
1476+
1477+
bool ScopBuilder::canAlwaysBeHoisted(MemoryAccess *MA,
1478+
bool StmtInvalidCtxIsEmpty,
1479+
bool MAInvalidCtxIsEmpty,
1480+
bool NonHoistableCtxIsEmpty) {
1481+
LoadInst *LInst = cast<LoadInst>(MA->getAccessInstruction());
1482+
const DataLayout &DL = LInst->getParent()->getModule()->getDataLayout();
1483+
if (PollyAllowDereferenceOfAllFunctionParams &&
1484+
isAParameter(LInst->getPointerOperand(), scop->getFunction()))
1485+
return true;
1486+
1487+
// TODO: We can provide more information for better but more expensive
1488+
// results.
1489+
if (!isDereferenceableAndAlignedPointer(LInst->getPointerOperand(),
1490+
LInst->getAlignment(), DL))
1491+
return false;
1492+
1493+
// If the location might be overwritten we do not hoist it unconditionally.
1494+
//
1495+
// TODO: This is probably too conservative.
1496+
if (!NonHoistableCtxIsEmpty)
1497+
return false;
1498+
1499+
// If a dereferenceable load is in a statement that is modeled precisely we
1500+
// can hoist it.
1501+
if (StmtInvalidCtxIsEmpty && MAInvalidCtxIsEmpty)
1502+
return true;
1503+
1504+
// Even if the statement is not modeled precisely we can hoist the load if it
1505+
// does not involve any parameters that might have been specialized by the
1506+
// statement domain.
1507+
for (unsigned u = 0, e = MA->getNumSubscripts(); u < e; u++)
1508+
if (!isa<SCEVConstant>(MA->getSubscript(u)))
1509+
return false;
1510+
return true;
1511+
}
1512+
1513+
void ScopBuilder::addInvariantLoads(ScopStmt &Stmt,
1514+
InvariantAccessesTy &InvMAs) {
1515+
if (InvMAs.empty())
1516+
return;
1517+
1518+
isl::set StmtInvalidCtx = Stmt.getInvalidContext();
1519+
bool StmtInvalidCtxIsEmpty = StmtInvalidCtx.is_empty();
1520+
1521+
// Get the context under which the statement is executed but remove the error
1522+
// context under which this statement is reached.
1523+
isl::set DomainCtx = Stmt.getDomain().params();
1524+
DomainCtx = DomainCtx.subtract(StmtInvalidCtx);
1525+
1526+
if (DomainCtx.n_basic_set() >= MaxDisjunctsInDomain) {
1527+
auto *AccInst = InvMAs.front().MA->getAccessInstruction();
1528+
scop->invalidate(COMPLEXITY, AccInst->getDebugLoc(), AccInst->getParent());
1529+
return;
1530+
}
1531+
1532+
// Project out all parameters that relate to loads in the statement. Otherwise
1533+
// we could have cyclic dependences on the constraints under which the
1534+
// hoisted loads are executed and we could not determine an order in which to
1535+
// pre-load them. This happens because not only lower bounds are part of the
1536+
// domain but also upper bounds.
1537+
for (auto &InvMA : InvMAs) {
1538+
auto *MA = InvMA.MA;
1539+
Instruction *AccInst = MA->getAccessInstruction();
1540+
if (SE.isSCEVable(AccInst->getType())) {
1541+
SetVector<Value *> Values;
1542+
for (const SCEV *Parameter : scop->parameters()) {
1543+
Values.clear();
1544+
findValues(Parameter, SE, Values);
1545+
if (!Values.count(AccInst))
1546+
continue;
1547+
1548+
if (isl::id ParamId = scop->getIdForParam(Parameter)) {
1549+
int Dim = DomainCtx.find_dim_by_id(isl::dim::param, ParamId);
1550+
if (Dim >= 0)
1551+
DomainCtx = DomainCtx.eliminate(isl::dim::param, Dim, 1);
1552+
}
1553+
}
1554+
}
1555+
}
1556+
1557+
for (auto &InvMA : InvMAs) {
1558+
auto *MA = InvMA.MA;
1559+
isl::set NHCtx = InvMA.NonHoistableCtx;
1560+
1561+
// Check for another invariant access that accesses the same location as
1562+
// MA and if found consolidate them. Otherwise create a new equivalence
1563+
// class at the end of InvariantEquivClasses.
1564+
LoadInst *LInst = cast<LoadInst>(MA->getAccessInstruction());
1565+
Type *Ty = LInst->getType();
1566+
const SCEV *PointerSCEV = SE.getSCEV(LInst->getPointerOperand());
1567+
1568+
isl::set MAInvalidCtx = MA->getInvalidContext();
1569+
bool NonHoistableCtxIsEmpty = NHCtx.is_empty();
1570+
bool MAInvalidCtxIsEmpty = MAInvalidCtx.is_empty();
1571+
1572+
isl::set MACtx;
1573+
// Check if we know that this pointer can be speculatively accessed.
1574+
if (canAlwaysBeHoisted(MA, StmtInvalidCtxIsEmpty, MAInvalidCtxIsEmpty,
1575+
NonHoistableCtxIsEmpty)) {
1576+
MACtx = isl::set::universe(DomainCtx.get_space());
1577+
} else {
1578+
MACtx = DomainCtx;
1579+
MACtx = MACtx.subtract(MAInvalidCtx.unite(NHCtx));
1580+
MACtx = MACtx.gist_params(scop->getContext());
1581+
}
1582+
1583+
bool Consolidated = false;
1584+
for (auto &IAClass : scop->invariantEquivClasses()) {
1585+
if (PointerSCEV != IAClass.IdentifyingPointer || Ty != IAClass.AccessType)
1586+
continue;
1587+
1588+
// If the pointer and the type is equal check if the access function wrt.
1589+
// to the domain is equal too. It can happen that the domain fixes
1590+
// parameter values and these can be different for distinct part of the
1591+
// SCoP. If this happens we cannot consolidate the loads but need to
1592+
// create a new invariant load equivalence class.
1593+
auto &MAs = IAClass.InvariantAccesses;
1594+
if (!MAs.empty()) {
1595+
auto *LastMA = MAs.front();
1596+
1597+
isl::set AR = MA->getAccessRelation().range();
1598+
isl::set LastAR = LastMA->getAccessRelation().range();
1599+
bool SameAR = AR.is_equal(LastAR);
1600+
1601+
if (!SameAR)
1602+
continue;
1603+
}
1604+
1605+
// Add MA to the list of accesses that are in this class.
1606+
MAs.push_front(MA);
1607+
1608+
Consolidated = true;
1609+
1610+
// Unify the execution context of the class and this statement.
1611+
isl::set IAClassDomainCtx = IAClass.ExecutionContext;
1612+
if (IAClassDomainCtx)
1613+
IAClassDomainCtx = IAClassDomainCtx.unite(MACtx).coalesce();
1614+
else
1615+
IAClassDomainCtx = MACtx;
1616+
IAClass.ExecutionContext = IAClassDomainCtx;
1617+
break;
1618+
}
1619+
1620+
if (Consolidated)
1621+
continue;
1622+
1623+
MACtx = MACtx.coalesce();
1624+
1625+
// If we did not consolidate MA, thus did not find an equivalence class
1626+
// for it, we create a new one.
1627+
scop->addInvariantEquivClass(
1628+
InvariantEquivClassTy{PointerSCEV, MemoryAccessList{MA}, MACtx, Ty});
1629+
}
1630+
}
1631+
14591632
void ScopBuilder::collectCandidateReductionLoads(
14601633
MemoryAccess *StoreMA, SmallVectorImpl<MemoryAccess *> &Loads) {
14611634
ScopStmt *Stmt = StoreMA->getStatement();

0 commit comments

Comments
 (0)
Please sign in to comment.