3810 lines · cpp
1//===- ScopBuilder.cpp ----------------------------------------------------===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8//9// Create a polyhedral description for a static control flow region.10//11// The pass creates a polyhedral description of the Scops detected by the SCoP12// detection derived from their LLVM-IR code.13//14//===----------------------------------------------------------------------===//15 16#include "polly/ScopBuilder.h"17#include "polly/Options.h"18#include "polly/ScopDetection.h"19#include "polly/ScopInfo.h"20#include "polly/Support/GICHelper.h"21#include "polly/Support/ISLTools.h"22#include "polly/Support/SCEVValidator.h"23#include "polly/Support/ScopHelper.h"24#include "polly/Support/VirtualInstruction.h"25#include "llvm/ADT/ArrayRef.h"26#include "llvm/ADT/EquivalenceClasses.h"27#include "llvm/ADT/PostOrderIterator.h"28#include "llvm/ADT/Sequence.h"29#include "llvm/ADT/SmallSet.h"30#include "llvm/ADT/Statistic.h"31#include "llvm/Analysis/AliasAnalysis.h"32#include "llvm/Analysis/AssumptionCache.h"33#include "llvm/Analysis/Delinearization.h"34#include "llvm/Analysis/Loads.h"35#include "llvm/Analysis/LoopInfo.h"36#include "llvm/Analysis/OptimizationRemarkEmitter.h"37#include "llvm/Analysis/RegionInfo.h"38#include "llvm/Analysis/RegionIterator.h"39#include "llvm/Analysis/ScalarEvolution.h"40#include "llvm/Analysis/ScalarEvolutionExpressions.h"41#include "llvm/IR/BasicBlock.h"42#include "llvm/IR/DataLayout.h"43#include "llvm/IR/DebugLoc.h"44#include "llvm/IR/DerivedTypes.h"45#include "llvm/IR/Dominators.h"46#include "llvm/IR/Function.h"47#include "llvm/IR/InstrTypes.h"48#include "llvm/IR/Instruction.h"49#include "llvm/IR/Instructions.h"50#include "llvm/IR/Type.h"51#include "llvm/IR/Use.h"52#include "llvm/IR/Value.h"53#include "llvm/Support/CommandLine.h"54#include "llvm/Support/Compiler.h"55#include "llvm/Support/Debug.h"56#include "llvm/Support/ErrorHandling.h"57#include "llvm/Support/raw_ostream.h"58#include <cassert>59#include <deque>60 61using namespace llvm;62using namespace polly;63 64#include "polly/Support/PollyDebug.h"65#define DEBUG_TYPE "polly-scops"66 67STATISTIC(ScopFound, "Number of valid Scops");68STATISTIC(RichScopFound, "Number of Scops containing a loop");69STATISTIC(InfeasibleScops,70 "Number of SCoPs with statically infeasible context.");71 72bool polly::ModelReadOnlyScalars;73 74// The maximal number of dimensions we allow during invariant load construction.75// More complex access ranges will result in very high compile time and are also76// unlikely to result in good code. This value is very high and should only77// trigger for corner cases (e.g., the "dct_luma" function in h264, SPEC2006).78static unsigned const MaxDimensionsInAccessRange = 9;79 80static cl::opt<bool, true> XModelReadOnlyScalars(81 "polly-analyze-read-only-scalars",82 cl::desc("Model read-only scalar values in the scop description"),83 cl::location(ModelReadOnlyScalars), cl::Hidden, cl::init(true),84 cl::cat(PollyCategory));85 86static cl::opt<int>87 OptComputeOut("polly-analysis-computeout",88 cl::desc("Bound the scop analysis by a maximal amount of "89 "computational steps (0 means no bound)"),90 cl::Hidden, cl::init(800000), cl::cat(PollyCategory));91 92static cl::opt<bool> PollyAllowDereferenceOfAllFunctionParams(93 "polly-allow-dereference-of-all-function-parameters",94 cl::desc(95 "Treat all parameters to functions that are pointers as dereferencible."96 " This is useful for invariant load hoisting, since we can generate"97 " less runtime checks. This is only valid if all pointers to functions"98 " are always initialized, so that Polly can choose to hoist"99 " their loads. "),100 cl::Hidden, cl::init(false), cl::cat(PollyCategory));101 102static cl::opt<bool>103 PollyIgnoreInbounds("polly-ignore-inbounds",104 cl::desc("Do not take inbounds assumptions at all"),105 cl::Hidden, cl::init(false), cl::cat(PollyCategory));106 107static cl::opt<unsigned> RunTimeChecksMaxArraysPerGroup(108 "polly-rtc-max-arrays-per-group",109 cl::desc("The maximal number of arrays to compare in each alias group."),110 cl::Hidden, cl::init(20), cl::cat(PollyCategory));111 112static cl::opt<unsigned> RunTimeChecksMaxAccessDisjuncts(113 "polly-rtc-max-array-disjuncts",114 cl::desc("The maximal number of disjunts allowed in memory accesses to "115 "to build RTCs."),116 cl::Hidden, cl::init(8), cl::cat(PollyCategory));117 118static cl::opt<unsigned> RunTimeChecksMaxParameters(119 "polly-rtc-max-parameters",120 cl::desc("The maximal number of parameters allowed in RTCs."), cl::Hidden,121 cl::init(8), cl::cat(PollyCategory));122 123static cl::opt<bool> UnprofitableScalarAccs(124 "polly-unprofitable-scalar-accs",125 cl::desc("Count statements with scalar accesses as not optimizable"),126 cl::Hidden, cl::init(false), cl::cat(PollyCategory));127 128static cl::opt<std::string> UserContextStr(129 "polly-context", cl::value_desc("isl parameter set"),130 cl::desc("Provide additional constraints on the context parameters"),131 cl::init(""), cl::cat(PollyCategory));132 133static cl::opt<bool> DetectReductions("polly-detect-reductions",134 cl::desc("Detect and exploit reductions"),135 cl::Hidden, cl::init(true),136 cl::cat(PollyCategory));137 138// Multiplicative reductions can be disabled separately as these kind of139// operations can overflow easily. Additive reductions and bit operations140// are in contrast pretty stable.141static cl::opt<bool> DisableMultiplicativeReductions(142 "polly-disable-multiplicative-reductions",143 cl::desc("Disable multiplicative reductions"), cl::Hidden,144 cl::cat(PollyCategory));145 146enum class GranularityChoice { BasicBlocks, ScalarIndependence, Stores };147 148static cl::opt<GranularityChoice> StmtGranularity(149 "polly-stmt-granularity",150 cl::desc(151 "Algorithm to use for splitting basic blocks into multiple statements"),152 cl::values(clEnumValN(GranularityChoice::BasicBlocks, "bb",153 "One statement per basic block"),154 clEnumValN(GranularityChoice::ScalarIndependence, "scalar-indep",155 "Scalar independence heuristic"),156 clEnumValN(GranularityChoice::Stores, "store",157 "Store-level granularity")),158 cl::init(GranularityChoice::ScalarIndependence), cl::cat(PollyCategory));159 160/// Helper to treat non-affine regions and basic blocks the same.161///162///{163 164/// Return the block that is the representing block for @p RN.165static inline BasicBlock *getRegionNodeBasicBlock(RegionNode *RN) {166 return RN->isSubRegion() ? RN->getNodeAs<Region>()->getEntry()167 : RN->getNodeAs<BasicBlock>();168}169 170/// Return the @p idx'th block that is executed after @p RN.171static inline BasicBlock *172getRegionNodeSuccessor(RegionNode *RN, Instruction *TI, unsigned idx) {173 if (RN->isSubRegion()) {174 assert(idx == 0);175 return RN->getNodeAs<Region>()->getExit();176 }177 return TI->getSuccessor(idx);178}179 180static bool containsErrorBlock(RegionNode *RN, const Region &R,181 ScopDetection *SD) {182 if (!RN->isSubRegion())183 return SD->isErrorBlock(*RN->getNodeAs<BasicBlock>(), R);184 for (BasicBlock *BB : RN->getNodeAs<Region>()->blocks())185 if (SD->isErrorBlock(*BB, R))186 return true;187 return false;188}189 190///}191 192/// Create a map to map from a given iteration to a subsequent iteration.193///194/// This map maps from SetSpace -> SetSpace where the dimensions @p Dim195/// is incremented by one and all other dimensions are equal, e.g.,196/// [i0, i1, i2, i3] -> [i0, i1, i2 + 1, i3]197///198/// if @p Dim is 2 and @p SetSpace has 4 dimensions.199static isl::map createNextIterationMap(isl::space SetSpace, unsigned Dim) {200 isl::space MapSpace = SetSpace.map_from_set();201 isl::map NextIterationMap = isl::map::universe(MapSpace);202 for (unsigned u : rangeIslSize(0, NextIterationMap.domain_tuple_dim()))203 if (u != Dim)204 NextIterationMap =205 NextIterationMap.equate(isl::dim::in, u, isl::dim::out, u);206 isl::constraint C =207 isl::constraint::alloc_equality(isl::local_space(MapSpace));208 C = C.set_constant_si(1);209 C = C.set_coefficient_si(isl::dim::in, Dim, 1);210 C = C.set_coefficient_si(isl::dim::out, Dim, -1);211 NextIterationMap = NextIterationMap.add_constraint(C);212 return NextIterationMap;213}214 215/// Add @p BSet to set @p BoundedParts if @p BSet is bounded.216static isl::set collectBoundedParts(isl::set S) {217 isl::set BoundedParts = isl::set::empty(S.get_space());218 for (isl::basic_set BSet : S.get_basic_set_list())219 if (BSet.is_bounded())220 BoundedParts = BoundedParts.unite(isl::set(BSet));221 return BoundedParts;222}223 224/// Compute the (un)bounded parts of @p S wrt. to dimension @p Dim.225///226/// @returns A separation of @p S into first an unbounded then a bounded subset,227/// both with regards to the dimension @p Dim.228static std::pair<isl::set, isl::set> partitionSetParts(isl::set S,229 unsigned Dim) {230 for (unsigned u : rangeIslSize(0, S.tuple_dim()))231 S = S.lower_bound_si(isl::dim::set, u, 0);232 233 unsigned NumDimsS = unsignedFromIslSize(S.tuple_dim());234 isl::set OnlyDimS = S;235 236 // Remove dimensions that are greater than Dim as they are not interesting.237 assert(NumDimsS >= Dim + 1);238 OnlyDimS = OnlyDimS.project_out(isl::dim::set, Dim + 1, NumDimsS - Dim - 1);239 240 // Create artificial parametric upper bounds for dimensions smaller than Dim241 // as we are not interested in them.242 OnlyDimS = OnlyDimS.insert_dims(isl::dim::param, 0, Dim);243 244 for (unsigned u = 0; u < Dim; u++) {245 isl::constraint C = isl::constraint::alloc_inequality(246 isl::local_space(OnlyDimS.get_space()));247 C = C.set_coefficient_si(isl::dim::param, u, 1);248 C = C.set_coefficient_si(isl::dim::set, u, -1);249 OnlyDimS = OnlyDimS.add_constraint(C);250 }251 252 // Collect all bounded parts of OnlyDimS.253 isl::set BoundedParts = collectBoundedParts(OnlyDimS);254 255 // Create the dimensions greater than Dim again.256 BoundedParts =257 BoundedParts.insert_dims(isl::dim::set, Dim + 1, NumDimsS - Dim - 1);258 259 // Remove the artificial upper bound parameters again.260 BoundedParts = BoundedParts.remove_dims(isl::dim::param, 0, Dim);261 262 isl::set UnboundedParts = S.subtract(BoundedParts);263 return std::make_pair(UnboundedParts, BoundedParts);264}265 266/// Create the conditions under which @p L @p Pred @p R is true.267static isl::set buildConditionSet(ICmpInst::Predicate Pred, isl::pw_aff L,268 isl::pw_aff R) {269 switch (Pred) {270 case ICmpInst::ICMP_EQ:271 return L.eq_set(R);272 case ICmpInst::ICMP_NE:273 return L.ne_set(R);274 case ICmpInst::ICMP_SLT:275 return L.lt_set(R);276 case ICmpInst::ICMP_SLE:277 return L.le_set(R);278 case ICmpInst::ICMP_SGT:279 return L.gt_set(R);280 case ICmpInst::ICMP_SGE:281 return L.ge_set(R);282 case ICmpInst::ICMP_ULT:283 return L.lt_set(R);284 case ICmpInst::ICMP_UGT:285 return L.gt_set(R);286 case ICmpInst::ICMP_ULE:287 return L.le_set(R);288 case ICmpInst::ICMP_UGE:289 return L.ge_set(R);290 default:291 llvm_unreachable("Non integer predicate not supported");292 }293}294 295isl::set ScopBuilder::adjustDomainDimensions(isl::set Dom, Loop *OldL,296 Loop *NewL) {297 // If the loops are the same there is nothing to do.298 if (NewL == OldL)299 return Dom;300 301 int OldDepth = scop->getRelativeLoopDepth(OldL);302 int NewDepth = scop->getRelativeLoopDepth(NewL);303 // If both loops are non-affine loops there is nothing to do.304 if (OldDepth == -1 && NewDepth == -1)305 return Dom;306 307 // Distinguish three cases:308 // 1) The depth is the same but the loops are not.309 // => One loop was left one was entered.310 // 2) The depth increased from OldL to NewL.311 // => One loop was entered, none was left.312 // 3) The depth decreased from OldL to NewL.313 // => Loops were left were difference of the depths defines how many.314 if (OldDepth == NewDepth) {315 assert(OldL->getParentLoop() == NewL->getParentLoop());316 Dom = Dom.project_out(isl::dim::set, NewDepth, 1);317 Dom = Dom.add_dims(isl::dim::set, 1);318 } else if (OldDepth < NewDepth) {319 assert(OldDepth + 1 == NewDepth);320 auto &R = scop->getRegion();321 (void)R;322 assert(NewL->getParentLoop() == OldL ||323 ((!OldL || !R.contains(OldL)) && R.contains(NewL)));324 Dom = Dom.add_dims(isl::dim::set, 1);325 } else {326 assert(OldDepth > NewDepth);327 unsigned Diff = OldDepth - NewDepth;328 unsigned NumDim = unsignedFromIslSize(Dom.tuple_dim());329 assert(NumDim >= Diff);330 Dom = Dom.project_out(isl::dim::set, NumDim - Diff, Diff);331 }332 333 return Dom;334}335 336/// Compute the isl representation for the SCEV @p E in this BB.337///338/// @param BB The BB for which isl representation is to be339/// computed.340/// @param InvalidDomainMap A map of BB to their invalid domains.341/// @param E The SCEV that should be translated.342/// @param NonNegative Flag to indicate the @p E has to be non-negative.343///344/// Note that this function will also adjust the invalid context accordingly.345 346__isl_give isl_pw_aff *347ScopBuilder::getPwAff(BasicBlock *BB,348 DenseMap<BasicBlock *, isl::set> &InvalidDomainMap,349 const SCEV *E, bool NonNegative) {350 PWACtx PWAC = scop->getPwAff(E, BB, NonNegative, &RecordedAssumptions);351 InvalidDomainMap[BB] = InvalidDomainMap[BB].unite(PWAC.second);352 return PWAC.first.release();353}354 355/// Build condition sets for unsigned ICmpInst(s).356/// Special handling is required for unsigned operands to ensure that if357/// MSB (aka the Sign bit) is set for an operands in an unsigned ICmpInst358/// it should wrap around.359///360/// @param IsStrictUpperBound holds information on the predicate relation361/// between TestVal and UpperBound, i.e,362/// TestVal < UpperBound OR TestVal <= UpperBound363__isl_give isl_set *ScopBuilder::buildUnsignedConditionSets(364 BasicBlock *BB, Value *Condition, __isl_keep isl_set *Domain,365 const SCEV *SCEV_TestVal, const SCEV *SCEV_UpperBound,366 DenseMap<BasicBlock *, isl::set> &InvalidDomainMap,367 bool IsStrictUpperBound) {368 // Do not take NonNeg assumption on TestVal369 // as it might have MSB (Sign bit) set.370 isl_pw_aff *TestVal = getPwAff(BB, InvalidDomainMap, SCEV_TestVal, false);371 // Take NonNeg assumption on UpperBound.372 isl_pw_aff *UpperBound =373 getPwAff(BB, InvalidDomainMap, SCEV_UpperBound, true);374 375 // 0 <= TestVal376 isl_set *First =377 isl_pw_aff_le_set(isl_pw_aff_zero_on_domain(isl_local_space_from_space(378 isl_pw_aff_get_domain_space(TestVal))),379 isl_pw_aff_copy(TestVal));380 381 isl_set *Second;382 if (IsStrictUpperBound)383 // TestVal < UpperBound384 Second = isl_pw_aff_lt_set(TestVal, UpperBound);385 else386 // TestVal <= UpperBound387 Second = isl_pw_aff_le_set(TestVal, UpperBound);388 389 isl_set *ConsequenceCondSet = isl_set_intersect(First, Second);390 return ConsequenceCondSet;391}392 393bool ScopBuilder::buildConditionSets(394 BasicBlock *BB, SwitchInst *SI, Loop *L, __isl_keep isl_set *Domain,395 DenseMap<BasicBlock *, isl::set> &InvalidDomainMap,396 SmallVectorImpl<__isl_give isl_set *> &ConditionSets) {397 Value *Condition = getConditionFromTerminator(SI);398 assert(Condition && "No condition for switch");399 400 isl_pw_aff *LHS, *RHS;401 LHS = getPwAff(BB, InvalidDomainMap, SE.getSCEVAtScope(Condition, L));402 403 unsigned NumSuccessors = SI->getNumSuccessors();404 ConditionSets.resize(NumSuccessors);405 for (auto &Case : SI->cases()) {406 unsigned Idx = Case.getSuccessorIndex();407 ConstantInt *CaseValue = Case.getCaseValue();408 409 RHS = getPwAff(BB, InvalidDomainMap, SE.getSCEV(CaseValue));410 isl_set *CaseConditionSet =411 buildConditionSet(ICmpInst::ICMP_EQ, isl::manage_copy(LHS),412 isl::manage(RHS))413 .release();414 ConditionSets[Idx] = isl_set_coalesce(415 isl_set_intersect(CaseConditionSet, isl_set_copy(Domain)));416 }417 418 assert(ConditionSets[0] == nullptr && "Default condition set was set");419 isl_set *ConditionSetUnion = isl_set_copy(ConditionSets[1]);420 for (unsigned u = 2; u < NumSuccessors; u++)421 ConditionSetUnion =422 isl_set_union(ConditionSetUnion, isl_set_copy(ConditionSets[u]));423 ConditionSets[0] = isl_set_subtract(isl_set_copy(Domain), ConditionSetUnion);424 425 isl_pw_aff_free(LHS);426 427 return true;428}429 430bool ScopBuilder::buildConditionSets(431 BasicBlock *BB, Value *Condition, Instruction *TI, Loop *L,432 __isl_keep isl_set *Domain,433 DenseMap<BasicBlock *, isl::set> &InvalidDomainMap,434 SmallVectorImpl<__isl_give isl_set *> &ConditionSets) {435 isl_set *ConsequenceCondSet = nullptr;436 437 if (auto Load = dyn_cast<LoadInst>(Condition)) {438 const SCEV *LHSSCEV = SE.getSCEVAtScope(Load, L);439 const SCEV *RHSSCEV = SE.getZero(LHSSCEV->getType());440 bool NonNeg = false;441 isl_pw_aff *LHS = getPwAff(BB, InvalidDomainMap, LHSSCEV, NonNeg);442 isl_pw_aff *RHS = getPwAff(BB, InvalidDomainMap, RHSSCEV, NonNeg);443 ConsequenceCondSet = buildConditionSet(ICmpInst::ICMP_SLE, isl::manage(LHS),444 isl::manage(RHS))445 .release();446 } else if (auto *PHI = dyn_cast<PHINode>(Condition)) {447 auto *Unique = dyn_cast<ConstantInt>(448 getUniqueNonErrorValue(PHI, &scop->getRegion(), &SD));449 assert(Unique &&450 "A PHINode condition should only be accepted by ScopDetection if "451 "getUniqueNonErrorValue returns non-NULL");452 453 if (Unique->isZero())454 ConsequenceCondSet = isl_set_empty(isl_set_get_space(Domain));455 else456 ConsequenceCondSet = isl_set_universe(isl_set_get_space(Domain));457 } else if (auto *CCond = dyn_cast<ConstantInt>(Condition)) {458 if (CCond->isZero())459 ConsequenceCondSet = isl_set_empty(isl_set_get_space(Domain));460 else461 ConsequenceCondSet = isl_set_universe(isl_set_get_space(Domain));462 } else if (BinaryOperator *BinOp = dyn_cast<BinaryOperator>(Condition)) {463 auto Opcode = BinOp->getOpcode();464 assert(Opcode == Instruction::And || Opcode == Instruction::Or);465 466 bool Valid = buildConditionSets(BB, BinOp->getOperand(0), TI, L, Domain,467 InvalidDomainMap, ConditionSets) &&468 buildConditionSets(BB, BinOp->getOperand(1), TI, L, Domain,469 InvalidDomainMap, ConditionSets);470 if (!Valid) {471 while (!ConditionSets.empty())472 isl_set_free(ConditionSets.pop_back_val());473 return false;474 }475 476 isl_set_free(ConditionSets.pop_back_val());477 isl_set *ConsCondPart0 = ConditionSets.pop_back_val();478 isl_set_free(ConditionSets.pop_back_val());479 isl_set *ConsCondPart1 = ConditionSets.pop_back_val();480 481 if (Opcode == Instruction::And)482 ConsequenceCondSet = isl_set_intersect(ConsCondPart0, ConsCondPart1);483 else484 ConsequenceCondSet = isl_set_union(ConsCondPart0, ConsCondPart1);485 } else {486 auto *ICond = dyn_cast<ICmpInst>(Condition);487 assert(ICond &&488 "Condition of exiting branch was neither constant nor ICmp!");489 490 Region &R = scop->getRegion();491 492 isl_pw_aff *LHS, *RHS;493 // For unsigned comparisons we assumed the signed bit of neither operand494 // to be set. The comparison is equal to a signed comparison under this495 // assumption.496 bool NonNeg = ICond->isUnsigned();497 const SCEV *LeftOperand = SE.getSCEVAtScope(ICond->getOperand(0), L),498 *RightOperand = SE.getSCEVAtScope(ICond->getOperand(1), L);499 500 LeftOperand = tryForwardThroughPHI(LeftOperand, R, SE, &SD);501 RightOperand = tryForwardThroughPHI(RightOperand, R, SE, &SD);502 503 switch (ICond->getPredicate()) {504 case ICmpInst::ICMP_ULT:505 ConsequenceCondSet =506 buildUnsignedConditionSets(BB, Condition, Domain, LeftOperand,507 RightOperand, InvalidDomainMap, true);508 break;509 case ICmpInst::ICMP_ULE:510 ConsequenceCondSet =511 buildUnsignedConditionSets(BB, Condition, Domain, LeftOperand,512 RightOperand, InvalidDomainMap, false);513 break;514 case ICmpInst::ICMP_UGT:515 ConsequenceCondSet =516 buildUnsignedConditionSets(BB, Condition, Domain, RightOperand,517 LeftOperand, InvalidDomainMap, true);518 break;519 case ICmpInst::ICMP_UGE:520 ConsequenceCondSet =521 buildUnsignedConditionSets(BB, Condition, Domain, RightOperand,522 LeftOperand, InvalidDomainMap, false);523 break;524 default:525 LHS = getPwAff(BB, InvalidDomainMap, LeftOperand, NonNeg);526 RHS = getPwAff(BB, InvalidDomainMap, RightOperand, NonNeg);527 ConsequenceCondSet = buildConditionSet(ICond->getPredicate(),528 isl::manage(LHS), isl::manage(RHS))529 .release();530 break;531 }532 }533 534 // If no terminator was given we are only looking for parameter constraints535 // under which @p Condition is true/false.536 if (!TI)537 ConsequenceCondSet = isl_set_params(ConsequenceCondSet);538 assert(ConsequenceCondSet);539 ConsequenceCondSet = isl_set_coalesce(540 isl_set_intersect(ConsequenceCondSet, isl_set_copy(Domain)));541 542 isl_set *AlternativeCondSet = nullptr;543 bool TooComplex =544 isl_set_n_basic_set(ConsequenceCondSet) >= (int)MaxDisjunctsInDomain;545 546 if (!TooComplex) {547 AlternativeCondSet = isl_set_subtract(isl_set_copy(Domain),548 isl_set_copy(ConsequenceCondSet));549 TooComplex =550 isl_set_n_basic_set(AlternativeCondSet) >= (int)MaxDisjunctsInDomain;551 }552 553 if (TooComplex) {554 scop->invalidate(COMPLEXITY, TI ? TI->getDebugLoc() : DebugLoc(),555 TI ? TI->getParent() : nullptr /* BasicBlock */);556 isl_set_free(AlternativeCondSet);557 isl_set_free(ConsequenceCondSet);558 return false;559 }560 561 ConditionSets.push_back(ConsequenceCondSet);562 ConditionSets.push_back(isl_set_coalesce(AlternativeCondSet));563 564 return true;565}566 567bool ScopBuilder::buildConditionSets(568 BasicBlock *BB, Instruction *TI, Loop *L, __isl_keep isl_set *Domain,569 DenseMap<BasicBlock *, isl::set> &InvalidDomainMap,570 SmallVectorImpl<__isl_give isl_set *> &ConditionSets) {571 if (SwitchInst *SI = dyn_cast<SwitchInst>(TI))572 return buildConditionSets(BB, SI, L, Domain, InvalidDomainMap,573 ConditionSets);574 575 assert(isa<BranchInst>(TI) && "Terminator was neither branch nor switch.");576 577 if (TI->getNumSuccessors() == 1) {578 ConditionSets.push_back(isl_set_copy(Domain));579 return true;580 }581 582 Value *Condition = getConditionFromTerminator(TI);583 assert(Condition && "No condition for Terminator");584 585 return buildConditionSets(BB, Condition, TI, L, Domain, InvalidDomainMap,586 ConditionSets);587}588 589bool ScopBuilder::propagateDomainConstraints(590 Region *R, DenseMap<BasicBlock *, isl::set> &InvalidDomainMap) {591 // Iterate over the region R and propagate the domain constrains from the592 // predecessors to the current node. In contrast to the593 // buildDomainsWithBranchConstraints function, this one will pull the domain594 // information from the predecessors instead of pushing it to the successors.595 // Additionally, we assume the domains to be already present in the domain596 // map here. However, we iterate again in reverse post order so we know all597 // predecessors have been visited before a block or non-affine subregion is598 // visited.599 600 ReversePostOrderTraversal<Region *> RTraversal(R);601 for (auto *RN : RTraversal) {602 // Recurse for affine subregions but go on for basic blocks and non-affine603 // subregions.604 if (RN->isSubRegion()) {605 Region *SubRegion = RN->getNodeAs<Region>();606 if (!scop->isNonAffineSubRegion(SubRegion)) {607 if (!propagateDomainConstraints(SubRegion, InvalidDomainMap))608 return false;609 continue;610 }611 }612 613 BasicBlock *BB = getRegionNodeBasicBlock(RN);614 isl::set &Domain = scop->getOrInitEmptyDomain(BB);615 assert(!Domain.is_null());616 617 // Under the union of all predecessor conditions we can reach this block.618 isl::set PredDom = getPredecessorDomainConstraints(BB, Domain);619 Domain = Domain.intersect(PredDom).coalesce();620 Domain = Domain.align_params(scop->getParamSpace());621 622 Loop *BBLoop = getRegionNodeLoop(RN, LI);623 if (BBLoop && BBLoop->getHeader() == BB && scop->contains(BBLoop))624 if (!addLoopBoundsToHeaderDomain(BBLoop, InvalidDomainMap))625 return false;626 }627 628 return true;629}630 631void ScopBuilder::propagateDomainConstraintsToRegionExit(632 BasicBlock *BB, Loop *BBLoop,633 SmallPtrSetImpl<BasicBlock *> &FinishedExitBlocks,634 DenseMap<BasicBlock *, isl::set> &InvalidDomainMap) {635 // Check if the block @p BB is the entry of a region. If so we propagate it's636 // domain to the exit block of the region. Otherwise we are done.637 auto *RI = scop->getRegion().getRegionInfo();638 auto *BBReg = RI ? RI->getRegionFor(BB) : nullptr;639 auto *ExitBB = BBReg ? BBReg->getExit() : nullptr;640 if (!BBReg || BBReg->getEntry() != BB || !scop->contains(ExitBB))641 return;642 643 // Do not propagate the domain if there is a loop backedge inside the region644 // that would prevent the exit block from being executed.645 auto *L = BBLoop;646 while (L && scop->contains(L)) {647 SmallVector<BasicBlock *, 4> LatchBBs;648 BBLoop->getLoopLatches(LatchBBs);649 for (auto *LatchBB : LatchBBs)650 if (BB != LatchBB && BBReg->contains(LatchBB))651 return;652 L = L->getParentLoop();653 }654 655 isl::set Domain = scop->getOrInitEmptyDomain(BB);656 assert(!Domain.is_null() && "Cannot propagate a nullptr");657 658 Loop *ExitBBLoop = getFirstNonBoxedLoopFor(ExitBB, LI, scop->getBoxedLoops());659 660 // Since the dimensions of @p BB and @p ExitBB might be different we have to661 // adjust the domain before we can propagate it.662 isl::set AdjustedDomain = adjustDomainDimensions(Domain, BBLoop, ExitBBLoop);663 isl::set &ExitDomain = scop->getOrInitEmptyDomain(ExitBB);664 665 // If the exit domain is not yet created we set it otherwise we "add" the666 // current domain.667 ExitDomain =668 !ExitDomain.is_null() ? AdjustedDomain.unite(ExitDomain) : AdjustedDomain;669 670 // Initialize the invalid domain.671 InvalidDomainMap[ExitBB] = ExitDomain.empty(ExitDomain.get_space());672 673 FinishedExitBlocks.insert(ExitBB);674}675 676isl::set ScopBuilder::getPredecessorDomainConstraints(BasicBlock *BB,677 isl::set Domain) {678 // If @p BB is the ScopEntry we are done679 if (scop->getRegion().getEntry() == BB)680 return isl::set::universe(Domain.get_space());681 682 // The region info of this function.683 auto &RI = *scop->getRegion().getRegionInfo();684 685 Loop *BBLoop = getFirstNonBoxedLoopFor(BB, LI, scop->getBoxedLoops());686 687 // A domain to collect all predecessor domains, thus all conditions under688 // which the block is executed. To this end we start with the empty domain.689 isl::set PredDom = isl::set::empty(Domain.get_space());690 691 // Set of regions of which the entry block domain has been propagated to BB.692 // all predecessors inside any of the regions can be skipped.693 SmallPtrSet<Region *, 8> PropagatedRegions;694 695 for (auto *PredBB : predecessors(BB)) {696 // Skip backedges.697 if (DT.dominates(BB, PredBB))698 continue;699 700 // If the predecessor is in a region we used for propagation we can skip it.701 auto PredBBInRegion = [PredBB](Region *PR) { return PR->contains(PredBB); };702 if (llvm::any_of(PropagatedRegions, PredBBInRegion)) {703 continue;704 }705 706 // Check if there is a valid region we can use for propagation, thus look707 // for a region that contains the predecessor and has @p BB as exit block.708 // FIXME: This was an side-effect-free (and possibly infinite) loop when709 // committed and seems not to be needed.710 auto *PredR = RI.getRegionFor(PredBB);711 while (PredR->getExit() != BB && !PredR->contains(BB))712 PredR = PredR->getParent();713 714 // If a valid region for propagation was found use the entry of that region715 // for propagation, otherwise the PredBB directly.716 if (PredR->getExit() == BB) {717 PredBB = PredR->getEntry();718 PropagatedRegions.insert(PredR);719 }720 721 isl::set PredBBDom = scop->getDomainConditions(PredBB);722 Loop *PredBBLoop =723 getFirstNonBoxedLoopFor(PredBB, LI, scop->getBoxedLoops());724 PredBBDom = adjustDomainDimensions(PredBBDom, PredBBLoop, BBLoop);725 PredDom = PredDom.unite(PredBBDom);726 }727 728 return PredDom;729}730 731bool ScopBuilder::addLoopBoundsToHeaderDomain(732 Loop *L, DenseMap<BasicBlock *, isl::set> &InvalidDomainMap) {733 int LoopDepth = scop->getRelativeLoopDepth(L);734 assert(LoopDepth >= 0 && "Loop in region should have at least depth one");735 736 BasicBlock *HeaderBB = L->getHeader();737 assert(scop->isDomainDefined(HeaderBB));738 isl::set &HeaderBBDom = scop->getOrInitEmptyDomain(HeaderBB);739 740 isl::map NextIterationMap =741 createNextIterationMap(HeaderBBDom.get_space(), LoopDepth);742 743 isl::set UnionBackedgeCondition = HeaderBBDom.empty(HeaderBBDom.get_space());744 745 SmallVector<BasicBlock *, 4> LatchBlocks;746 L->getLoopLatches(LatchBlocks);747 748 for (BasicBlock *LatchBB : LatchBlocks) {749 // If the latch is only reachable via error statements we skip it.750 if (!scop->isDomainDefined(LatchBB))751 continue;752 753 isl::set LatchBBDom = scop->getDomainConditions(LatchBB);754 755 isl::set BackedgeCondition;756 757 Instruction *TI = LatchBB->getTerminator();758 BranchInst *BI = dyn_cast<BranchInst>(TI);759 assert(BI && "Only branch instructions allowed in loop latches");760 761 if (BI->isUnconditional())762 BackedgeCondition = LatchBBDom;763 else {764 SmallVector<isl_set *, 8> ConditionSets;765 int idx = BI->getSuccessor(0) != HeaderBB;766 if (!buildConditionSets(LatchBB, TI, L, LatchBBDom.get(),767 InvalidDomainMap, ConditionSets))768 return false;769 770 // Free the non back edge condition set as we do not need it.771 isl_set_free(ConditionSets[1 - idx]);772 773 BackedgeCondition = isl::manage(ConditionSets[idx]);774 }775 776 int LatchLoopDepth = scop->getRelativeLoopDepth(LI.getLoopFor(LatchBB));777 assert(LatchLoopDepth >= LoopDepth);778 BackedgeCondition = BackedgeCondition.project_out(779 isl::dim::set, LoopDepth + 1, LatchLoopDepth - LoopDepth);780 UnionBackedgeCondition = UnionBackedgeCondition.unite(BackedgeCondition);781 }782 783 isl::map ForwardMap = ForwardMap.lex_le(HeaderBBDom.get_space());784 for (int i = 0; i < LoopDepth; i++)785 ForwardMap = ForwardMap.equate(isl::dim::in, i, isl::dim::out, i);786 787 isl::set UnionBackedgeConditionComplement =788 UnionBackedgeCondition.complement();789 UnionBackedgeConditionComplement =790 UnionBackedgeConditionComplement.lower_bound_si(isl::dim::set, LoopDepth,791 0);792 UnionBackedgeConditionComplement =793 UnionBackedgeConditionComplement.apply(ForwardMap);794 HeaderBBDom = HeaderBBDom.subtract(UnionBackedgeConditionComplement);795 HeaderBBDom = HeaderBBDom.apply(NextIterationMap);796 797 auto Parts = partitionSetParts(HeaderBBDom, LoopDepth);798 HeaderBBDom = Parts.second;799 800 // Check if there is a <nsw> tagged AddRec for this loop and if so do not801 // require a runtime check. The assumption is already implied by the <nsw>802 // tag.803 bool RequiresRTC = !scop->hasNSWAddRecForLoop(L);804 805 isl::set UnboundedCtx = Parts.first.params();806 recordAssumption(&RecordedAssumptions, INFINITELOOP, UnboundedCtx,807 HeaderBB->getTerminator()->getDebugLoc(), AS_RESTRICTION,808 nullptr, RequiresRTC);809 return true;810}811 812void ScopBuilder::buildInvariantEquivalenceClasses() {813 DenseMap<std::pair<const SCEV *, Type *>, LoadInst *> EquivClasses;814 815 const InvariantLoadsSetTy &RIL = scop->getRequiredInvariantLoads();816 for (LoadInst *LInst : RIL) {817 const SCEV *PointerSCEV = SE.getSCEV(LInst->getPointerOperand());818 819 Type *Ty = LInst->getType();820 LoadInst *&ClassRep = EquivClasses[std::make_pair(PointerSCEV, Ty)];821 if (ClassRep) {822 scop->addInvariantLoadMapping(LInst, ClassRep);823 continue;824 }825 826 ClassRep = LInst;827 scop->addInvariantEquivClass(828 InvariantEquivClassTy{PointerSCEV, MemoryAccessList(), {}, Ty});829 }830}831 832bool ScopBuilder::buildDomains(833 Region *R, DenseMap<BasicBlock *, isl::set> &InvalidDomainMap) {834 bool IsOnlyNonAffineRegion = scop->isNonAffineSubRegion(R);835 auto *EntryBB = R->getEntry();836 auto *L = IsOnlyNonAffineRegion ? nullptr : LI.getLoopFor(EntryBB);837 int LD = scop->getRelativeLoopDepth(L);838 auto *S =839 isl_set_universe(isl_space_set_alloc(scop->getIslCtx().get(), 0, LD + 1));840 841 InvalidDomainMap[EntryBB] = isl::manage(isl_set_empty(isl_set_get_space(S)));842 isl::set Domain = isl::manage(S);843 scop->setDomain(EntryBB, Domain);844 845 if (IsOnlyNonAffineRegion)846 return !containsErrorBlock(R->getNode(), *R, &SD);847 848 if (!buildDomainsWithBranchConstraints(R, InvalidDomainMap))849 return false;850 851 if (!propagateDomainConstraints(R, InvalidDomainMap))852 return false;853 854 // Error blocks and blocks dominated by them have been assumed to never be855 // executed. Representing them in the Scop does not add any value. In fact,856 // it is likely to cause issues during construction of the ScopStmts. The857 // contents of error blocks have not been verified to be expressible and858 // will cause problems when building up a ScopStmt for them.859 // Furthermore, basic blocks dominated by error blocks may reference860 // instructions in the error block which, if the error block is not modeled,861 // can themselves not be constructed properly. To this end we will replace862 // the domains of error blocks and those only reachable via error blocks863 // with an empty set. Additionally, we will record for each block under which864 // parameter combination it would be reached via an error block in its865 // InvalidDomain. This information is needed during load hoisting.866 if (!propagateInvalidStmtDomains(R, InvalidDomainMap))867 return false;868 869 return true;870}871 872bool ScopBuilder::buildDomainsWithBranchConstraints(873 Region *R, DenseMap<BasicBlock *, isl::set> &InvalidDomainMap) {874 // To create the domain for each block in R we iterate over all blocks and875 // subregions in R and propagate the conditions under which the current region876 // element is executed. To this end we iterate in reverse post order over R as877 // it ensures that we first visit all predecessors of a region node (either a878 // basic block or a subregion) before we visit the region node itself.879 // Initially, only the domain for the SCoP region entry block is set and from880 // there we propagate the current domain to all successors, however we add the881 // condition that the successor is actually executed next.882 // As we are only interested in non-loop carried constraints here we can883 // simply skip loop back edges.884 885 SmallPtrSet<BasicBlock *, 8> FinishedExitBlocks;886 ReversePostOrderTraversal<Region *> RTraversal(R);887 for (auto *RN : RTraversal) {888 // Recurse for affine subregions but go on for basic blocks and non-affine889 // subregions.890 if (RN->isSubRegion()) {891 Region *SubRegion = RN->getNodeAs<Region>();892 if (!scop->isNonAffineSubRegion(SubRegion)) {893 if (!buildDomainsWithBranchConstraints(SubRegion, InvalidDomainMap))894 return false;895 continue;896 }897 }898 899 if (containsErrorBlock(RN, scop->getRegion(), &SD))900 scop->notifyErrorBlock();901 ;902 903 BasicBlock *BB = getRegionNodeBasicBlock(RN);904 Instruction *TI = BB->getTerminator();905 906 if (isa<UnreachableInst>(TI))907 continue;908 909 if (!scop->isDomainDefined(BB))910 continue;911 isl::set Domain = scop->getDomainConditions(BB);912 913 scop->updateMaxLoopDepth(unsignedFromIslSize(Domain.tuple_dim()));914 915 auto *BBLoop = getRegionNodeLoop(RN, LI);916 // Propagate the domain from BB directly to blocks that have a superset917 // domain, at the moment only region exit nodes of regions that start in BB.918 propagateDomainConstraintsToRegionExit(BB, BBLoop, FinishedExitBlocks,919 InvalidDomainMap);920 921 // If all successors of BB have been set a domain through the propagation922 // above we do not need to build condition sets but can just skip this923 // block. However, it is important to note that this is a local property924 // with regards to the region @p R. To this end FinishedExitBlocks is a925 // local variable.926 auto IsFinishedRegionExit = [&FinishedExitBlocks](BasicBlock *SuccBB) {927 return FinishedExitBlocks.count(SuccBB);928 };929 if (std::all_of(succ_begin(BB), succ_end(BB), IsFinishedRegionExit))930 continue;931 932 // Build the condition sets for the successor nodes of the current region933 // node. If it is a non-affine subregion we will always execute the single934 // exit node, hence the single entry node domain is the condition set. For935 // basic blocks we use the helper function buildConditionSets.936 SmallVector<isl_set *, 8> ConditionSets;937 if (RN->isSubRegion())938 ConditionSets.push_back(Domain.copy());939 else if (!buildConditionSets(BB, TI, BBLoop, Domain.get(), InvalidDomainMap,940 ConditionSets))941 return false;942 943 // Now iterate over the successors and set their initial domain based on944 // their condition set. We skip back edges here and have to be careful when945 // we leave a loop not to keep constraints over a dimension that doesn't946 // exist anymore.947 assert(RN->isSubRegion() || TI->getNumSuccessors() == ConditionSets.size());948 for (unsigned u = 0, e = ConditionSets.size(); u < e; u++) {949 isl::set CondSet = isl::manage(ConditionSets[u]);950 BasicBlock *SuccBB = getRegionNodeSuccessor(RN, TI, u);951 952 // Skip blocks outside the region.953 if (!scop->contains(SuccBB))954 continue;955 956 // If we propagate the domain of some block to "SuccBB" we do not have to957 // adjust the domain.958 if (FinishedExitBlocks.count(SuccBB))959 continue;960 961 // Skip back edges.962 if (DT.dominates(SuccBB, BB))963 continue;964 965 Loop *SuccBBLoop =966 getFirstNonBoxedLoopFor(SuccBB, LI, scop->getBoxedLoops());967 968 CondSet = adjustDomainDimensions(CondSet, BBLoop, SuccBBLoop);969 970 // Set the domain for the successor or merge it with an existing domain in971 // case there are multiple paths (without loop back edges) to the972 // successor block.973 isl::set &SuccDomain = scop->getOrInitEmptyDomain(SuccBB);974 975 if (!SuccDomain.is_null()) {976 SuccDomain = SuccDomain.unite(CondSet).coalesce();977 } else {978 // Initialize the invalid domain.979 InvalidDomainMap[SuccBB] = CondSet.empty(CondSet.get_space());980 SuccDomain = CondSet;981 }982 983 SuccDomain = SuccDomain.detect_equalities();984 985 // Check if the maximal number of domain disjunctions was reached.986 // In case this happens we will clean up and bail.987 if (unsignedFromIslSize(SuccDomain.n_basic_set()) < MaxDisjunctsInDomain)988 continue;989 990 scop->invalidate(COMPLEXITY, DebugLoc());991 while (++u < ConditionSets.size())992 isl_set_free(ConditionSets[u]);993 return false;994 }995 }996 997 return true;998}999 1000bool ScopBuilder::propagateInvalidStmtDomains(1001 Region *R, DenseMap<BasicBlock *, isl::set> &InvalidDomainMap) {1002 ReversePostOrderTraversal<Region *> RTraversal(R);1003 for (auto *RN : RTraversal) {1004 1005 // Recurse for affine subregions but go on for basic blocks and non-affine1006 // subregions.1007 if (RN->isSubRegion()) {1008 Region *SubRegion = RN->getNodeAs<Region>();1009 if (!scop->isNonAffineSubRegion(SubRegion)) {1010 propagateInvalidStmtDomains(SubRegion, InvalidDomainMap);1011 continue;1012 }1013 }1014 1015 bool ContainsErrorBlock = containsErrorBlock(RN, scop->getRegion(), &SD);1016 BasicBlock *BB = getRegionNodeBasicBlock(RN);1017 isl::set &Domain = scop->getOrInitEmptyDomain(BB);1018 assert(!Domain.is_null() && "Cannot propagate a nullptr");1019 1020 isl::set InvalidDomain = InvalidDomainMap[BB];1021 1022 bool IsInvalidBlock = ContainsErrorBlock || Domain.is_subset(InvalidDomain);1023 1024 if (!IsInvalidBlock) {1025 InvalidDomain = InvalidDomain.intersect(Domain);1026 } else {1027 InvalidDomain = Domain;1028 isl::set DomPar = Domain.params();1029 recordAssumption(&RecordedAssumptions, ERRORBLOCK, DomPar,1030 BB->getTerminator()->getDebugLoc(), AS_RESTRICTION);1031 Domain = isl::set::empty(Domain.get_space());1032 }1033 1034 if (InvalidDomain.is_empty()) {1035 InvalidDomainMap[BB] = InvalidDomain;1036 continue;1037 }1038 1039 auto *BBLoop = getRegionNodeLoop(RN, LI);1040 auto *TI = BB->getTerminator();1041 unsigned NumSuccs = RN->isSubRegion() ? 1 : TI->getNumSuccessors();1042 for (unsigned u = 0; u < NumSuccs; u++) {1043 auto *SuccBB = getRegionNodeSuccessor(RN, TI, u);1044 1045 // Skip successors outside the SCoP.1046 if (!scop->contains(SuccBB))1047 continue;1048 1049 // Skip backedges.1050 if (DT.dominates(SuccBB, BB))1051 continue;1052 1053 Loop *SuccBBLoop =1054 getFirstNonBoxedLoopFor(SuccBB, LI, scop->getBoxedLoops());1055 1056 auto AdjustedInvalidDomain =1057 adjustDomainDimensions(InvalidDomain, BBLoop, SuccBBLoop);1058 1059 isl::set SuccInvalidDomain = InvalidDomainMap[SuccBB];1060 SuccInvalidDomain = SuccInvalidDomain.unite(AdjustedInvalidDomain);1061 SuccInvalidDomain = SuccInvalidDomain.coalesce();1062 1063 InvalidDomainMap[SuccBB] = SuccInvalidDomain;1064 1065 // Check if the maximal number of domain disjunctions was reached.1066 // In case this happens we will bail.1067 if (unsignedFromIslSize(SuccInvalidDomain.n_basic_set()) <1068 MaxDisjunctsInDomain)1069 continue;1070 1071 InvalidDomainMap.erase(BB);1072 scop->invalidate(COMPLEXITY, TI->getDebugLoc(), TI->getParent());1073 return false;1074 }1075 1076 InvalidDomainMap[BB] = InvalidDomain;1077 }1078 1079 return true;1080}1081 1082void ScopBuilder::buildPHIAccesses(ScopStmt *PHIStmt, PHINode *PHI,1083 Region *NonAffineSubRegion,1084 bool IsExitBlock) {1085 // PHI nodes that are in the exit block of the region, hence if IsExitBlock is1086 // true, are not modeled as ordinary PHI nodes as they are not part of the1087 // region. However, we model the operands in the predecessor blocks that are1088 // part of the region as regular scalar accesses.1089 1090 // If we can synthesize a PHI we can skip it, however only if it is in1091 // the region. If it is not it can only be in the exit block of the region.1092 // In this case we model the operands but not the PHI itself.1093 auto *Scope = LI.getLoopFor(PHI->getParent());1094 if (!IsExitBlock && canSynthesize(PHI, *scop, &SE, Scope))1095 return;1096 1097 // PHI nodes are modeled as if they had been demoted prior to the SCoP1098 // detection. Hence, the PHI is a load of a new memory location in which the1099 // incoming value was written at the end of the incoming basic block.1100 bool OnlyNonAffineSubRegionOperands = true;1101 for (unsigned u = 0; u < PHI->getNumIncomingValues(); u++) {1102 Value *Op = PHI->getIncomingValue(u);1103 BasicBlock *OpBB = PHI->getIncomingBlock(u);1104 ScopStmt *OpStmt = scop->getIncomingStmtFor(PHI->getOperandUse(u));1105 1106 // Do not build PHI dependences inside a non-affine subregion, but make1107 // sure that the necessary scalar values are still made available.1108 if (NonAffineSubRegion && NonAffineSubRegion->contains(OpBB)) {1109 auto *OpInst = dyn_cast<Instruction>(Op);1110 if (!OpInst || !NonAffineSubRegion->contains(OpInst))1111 ensureValueRead(Op, OpStmt);1112 continue;1113 }1114 1115 OnlyNonAffineSubRegionOperands = false;1116 ensurePHIWrite(PHI, OpStmt, OpBB, Op, IsExitBlock);1117 }1118 1119 if (!OnlyNonAffineSubRegionOperands && !IsExitBlock) {1120 addPHIReadAccess(PHIStmt, PHI);1121 }1122}1123 1124void ScopBuilder::buildScalarDependences(ScopStmt *UserStmt,1125 Instruction *Inst) {1126 assert(!isa<PHINode>(Inst));1127 1128 // Pull-in required operands.1129 for (Use &Op : Inst->operands())1130 ensureValueRead(Op.get(), UserStmt);1131}1132 1133// Create a sequence of two schedules. Either argument may be null and is1134// interpreted as the empty schedule. Can also return null if both schedules are1135// empty.1136static isl::schedule combineInSequence(isl::schedule Prev, isl::schedule Succ) {1137 if (Prev.is_null())1138 return Succ;1139 if (Succ.is_null())1140 return Prev;1141 1142 return Prev.sequence(Succ);1143}1144 1145// Create an isl_multi_union_aff that defines an identity mapping from the1146// elements of USet to their N-th dimension.1147//1148// # Example:1149//1150// Domain: { A[i,j]; B[i,j,k] }1151// N: 11152//1153// Resulting Mapping: { {A[i,j] -> [(j)]; B[i,j,k] -> [(j)] }1154//1155// @param USet A union set describing the elements for which to generate a1156// mapping.1157// @param N The dimension to map to.1158// @returns A mapping from USet to its N-th dimension.1159static isl::multi_union_pw_aff mapToDimension(isl::union_set USet, unsigned N) {1160 assert(!USet.is_null());1161 assert(!USet.is_empty());1162 1163 auto Result = isl::union_pw_multi_aff::empty(USet.get_space());1164 1165 for (isl::set S : USet.get_set_list()) {1166 unsigned Dim = unsignedFromIslSize(S.tuple_dim());1167 assert(Dim >= N);1168 auto PMA = isl::pw_multi_aff::project_out_map(S.get_space(), isl::dim::set,1169 N, Dim - N);1170 if (N > 1)1171 PMA = PMA.drop_dims(isl::dim::out, 0, N - 1);1172 1173 Result = Result.add_pw_multi_aff(PMA);1174 }1175 1176 return isl::multi_union_pw_aff(isl::union_pw_multi_aff(Result));1177}1178 1179void ScopBuilder::buildSchedule() {1180 Loop *L = getLoopSurroundingScop(*scop, LI);1181 LoopStackTy LoopStack({LoopStackElementTy(L, {}, 0)});1182 buildSchedule(scop->getRegion().getNode(), LoopStack);1183 assert(LoopStack.size() == 1 && LoopStack.back().L == L);1184 scop->setScheduleTree(LoopStack[0].Schedule);1185}1186 1187/// To generate a schedule for the elements in a Region we traverse the Region1188/// in reverse-post-order and add the contained RegionNodes in traversal order1189/// to the schedule of the loop that is currently at the top of the LoopStack.1190/// For loop-free codes, this results in a correct sequential ordering.1191///1192/// Example:1193/// bb1(0)1194/// / \.1195/// bb2(1) bb3(2)1196/// \ / \.1197/// bb4(3) bb5(4)1198/// \ /1199/// bb6(5)1200///1201/// Including loops requires additional processing. Whenever a loop header is1202/// encountered, the corresponding loop is added to the @p LoopStack. Starting1203/// from an empty schedule, we first process all RegionNodes that are within1204/// this loop and complete the sequential schedule at this loop-level before1205/// processing about any other nodes. To implement this1206/// loop-nodes-first-processing, the reverse post-order traversal is1207/// insufficient. Hence, we additionally check if the traversal yields1208/// sub-regions or blocks that are outside the last loop on the @p LoopStack.1209/// These region-nodes are then queue and only traverse after the all nodes1210/// within the current loop have been processed.1211void ScopBuilder::buildSchedule(Region *R, LoopStackTy &LoopStack) {1212 Loop *OuterScopLoop = getLoopSurroundingScop(*scop, LI);1213 1214 ReversePostOrderTraversal<Region *> RTraversal(R);1215 std::deque<RegionNode *> WorkList(RTraversal.begin(), RTraversal.end());1216 std::deque<RegionNode *> DelayList;1217 bool LastRNWaiting = false;1218 1219 // Iterate over the region @p R in reverse post-order but queue1220 // sub-regions/blocks iff they are not part of the last encountered but not1221 // completely traversed loop. The variable LastRNWaiting is a flag to indicate1222 // that we queued the last sub-region/block from the reverse post-order1223 // iterator. If it is set we have to explore the next sub-region/block from1224 // the iterator (if any) to guarantee progress. If it is not set we first try1225 // the next queued sub-region/blocks.1226 while (!WorkList.empty() || !DelayList.empty()) {1227 RegionNode *RN;1228 1229 if ((LastRNWaiting && !WorkList.empty()) || DelayList.empty()) {1230 RN = WorkList.front();1231 WorkList.pop_front();1232 LastRNWaiting = false;1233 } else {1234 RN = DelayList.front();1235 DelayList.pop_front();1236 }1237 1238 Loop *L = getRegionNodeLoop(RN, LI);1239 if (!scop->contains(L))1240 L = OuterScopLoop;1241 1242 Loop *LastLoop = LoopStack.back().L;1243 if (LastLoop != L) {1244 if (LastLoop && !LastLoop->contains(L)) {1245 LastRNWaiting = true;1246 DelayList.push_back(RN);1247 continue;1248 }1249 LoopStack.push_back({L, {}, 0});1250 }1251 buildSchedule(RN, LoopStack);1252 }1253}1254 1255void ScopBuilder::buildSchedule(RegionNode *RN, LoopStackTy &LoopStack) {1256 if (RN->isSubRegion()) {1257 auto *LocalRegion = RN->getNodeAs<Region>();1258 if (!scop->isNonAffineSubRegion(LocalRegion)) {1259 buildSchedule(LocalRegion, LoopStack);1260 return;1261 }1262 }1263 1264 assert(LoopStack.rbegin() != LoopStack.rend());1265 auto LoopData = LoopStack.rbegin();1266 LoopData->NumBlocksProcessed += getNumBlocksInRegionNode(RN);1267 1268 for (auto *Stmt : scop->getStmtListFor(RN)) {1269 isl::union_set UDomain{Stmt->getDomain()};1270 auto StmtSchedule = isl::schedule::from_domain(UDomain);1271 LoopData->Schedule = combineInSequence(LoopData->Schedule, StmtSchedule);1272 }1273 1274 // Check if we just processed the last node in this loop. If we did, finalize1275 // the loop by:1276 //1277 // - adding new schedule dimensions1278 // - folding the resulting schedule into the parent loop schedule1279 // - dropping the loop schedule from the LoopStack.1280 //1281 // Then continue to check surrounding loops, which might also have been1282 // completed by this node.1283 size_t Dimension = LoopStack.size();1284 while (LoopData->L &&1285 LoopData->NumBlocksProcessed == getNumBlocksInLoop(LoopData->L)) {1286 isl::schedule Schedule = LoopData->Schedule;1287 auto NumBlocksProcessed = LoopData->NumBlocksProcessed;1288 1289 assert(std::next(LoopData) != LoopStack.rend());1290 Loop *L = LoopData->L;1291 ++LoopData;1292 --Dimension;1293 1294 if (!Schedule.is_null()) {1295 isl::union_set Domain = Schedule.get_domain();1296 isl::multi_union_pw_aff MUPA = mapToDimension(Domain, Dimension);1297 Schedule = Schedule.insert_partial_schedule(MUPA);1298 1299 if (hasDisableAllTransformsHint(L)) {1300 /// If any of the loops has a disable_nonforced heuristic, mark the1301 /// entire SCoP as such. The ISL rescheduler can only reschedule the1302 /// SCoP in its entirety.1303 /// TODO: ScopDetection could avoid including such loops or warp them as1304 /// boxed loop. It still needs to pass-through loop with user-defined1305 /// metadata.1306 scop->markDisableHeuristics();1307 }1308 1309 // It is easier to insert the marks here that do it retroactively.1310 isl::id IslLoopId = createIslLoopAttr(scop->getIslCtx(), L);1311 if (!IslLoopId.is_null())1312 Schedule =1313 Schedule.get_root().child(0).insert_mark(IslLoopId).get_schedule();1314 1315 LoopData->Schedule = combineInSequence(LoopData->Schedule, Schedule);1316 }1317 1318 LoopData->NumBlocksProcessed += NumBlocksProcessed;1319 }1320 // Now pop all loops processed up there from the LoopStack1321 LoopStack.erase(LoopStack.begin() + Dimension, LoopStack.end());1322}1323 1324void ScopBuilder::buildEscapingDependences(Instruction *Inst) {1325 // Check for uses of this instruction outside the scop. Because we do not1326 // iterate over such instructions and therefore did not "ensure" the existence1327 // of a write, we must determine such use here.1328 if (scop->isEscaping(Inst))1329 ensureValueWrite(Inst);1330}1331 1332void ScopBuilder::addRecordedAssumptions() {1333 for (auto &AS : llvm::reverse(RecordedAssumptions)) {1334 1335 if (!AS.BB) {1336 scop->addAssumption(AS.Kind, AS.Set, AS.Loc, AS.Sign,1337 nullptr /* BasicBlock */, AS.RequiresRTC);1338 continue;1339 }1340 1341 // If the domain was deleted the assumptions are void.1342 isl_set *Dom = scop->getDomainConditions(AS.BB).release();1343 if (!Dom)1344 continue;1345 1346 // If a basic block was given use its domain to simplify the assumption.1347 // In case of restrictions we know they only have to hold on the domain,1348 // thus we can intersect them with the domain of the block. However, for1349 // assumptions the domain has to imply them, thus:1350 // _ _____1351 // Dom => S <==> A v B <==> A - B1352 //1353 // To avoid the complement we will register A - B as a restriction not an1354 // assumption.1355 isl_set *S = AS.Set.copy();1356 if (AS.Sign == AS_RESTRICTION)1357 S = isl_set_params(isl_set_intersect(S, Dom));1358 else /* (AS.Sign == AS_ASSUMPTION) */1359 S = isl_set_params(isl_set_subtract(Dom, S));1360 1361 scop->addAssumption(AS.Kind, isl::manage(S), AS.Loc, AS_RESTRICTION, AS.BB,1362 AS.RequiresRTC);1363 }1364}1365 1366void ScopBuilder::addUserAssumptions(1367 AssumptionCache &AC, DenseMap<BasicBlock *, isl::set> &InvalidDomainMap) {1368 for (auto &Assumption : AC.assumptions()) {1369 auto *CI = dyn_cast_or_null<CallInst>(Assumption);1370 if (!CI || CI->arg_size() != 1)1371 continue;1372 1373 bool InScop = scop->contains(CI);1374 if (!InScop && !scop->isDominatedBy(DT, CI->getParent()))1375 continue;1376 1377 auto *L = LI.getLoopFor(CI->getParent());1378 auto *Val = CI->getArgOperand(0);1379 ParameterSetTy DetectedParams;1380 auto &R = scop->getRegion();1381 if (!isAffineConstraint(Val, &R, L, SE, DetectedParams)) {1382 ORE.emit(1383 OptimizationRemarkAnalysis(DEBUG_TYPE, "IgnoreUserAssumption", CI)1384 << "Non-affine user assumption ignored.");1385 continue;1386 }1387 1388 // Collect all newly introduced parameters.1389 ParameterSetTy NewParams;1390 for (auto *Param : DetectedParams) {1391 Param = extractConstantFactor(Param, SE).second;1392 Param = scop->getRepresentingInvariantLoadSCEV(Param);1393 if (scop->isParam(Param))1394 continue;1395 NewParams.insert(Param);1396 }1397 1398 SmallVector<isl_set *, 2> ConditionSets;1399 auto *TI = InScop ? CI->getParent()->getTerminator() : nullptr;1400 BasicBlock *BB = InScop ? CI->getParent() : R.getEntry();1401 auto *Dom = InScop ? isl_set_copy(scop->getDomainConditions(BB).get())1402 : isl_set_copy(scop->getContext().get());1403 assert(Dom && "Cannot propagate a nullptr.");1404 bool Valid = buildConditionSets(BB, Val, TI, L, Dom, InvalidDomainMap,1405 ConditionSets);1406 isl_set_free(Dom);1407 1408 if (!Valid)1409 continue;1410 1411 isl_set *AssumptionCtx = nullptr;1412 if (InScop) {1413 AssumptionCtx = isl_set_complement(isl_set_params(ConditionSets[1]));1414 isl_set_free(ConditionSets[0]);1415 } else {1416 AssumptionCtx = isl_set_complement(ConditionSets[1]);1417 AssumptionCtx = isl_set_intersect(AssumptionCtx, ConditionSets[0]);1418 }1419 1420 // Project out newly introduced parameters as they are not otherwise useful.1421 if (!NewParams.empty()) {1422 for (isl_size u = 0; u < isl_set_n_param(AssumptionCtx); u++) {1423 auto *Id = isl_set_get_dim_id(AssumptionCtx, isl_dim_param, u);1424 auto *Param = static_cast<const SCEV *>(isl_id_get_user(Id));1425 isl_id_free(Id);1426 1427 if (!NewParams.count(Param))1428 continue;1429 1430 AssumptionCtx =1431 isl_set_project_out(AssumptionCtx, isl_dim_param, u--, 1);1432 }1433 }1434 ORE.emit(OptimizationRemarkAnalysis(DEBUG_TYPE, "UserAssumption", CI)1435 << "Use user assumption: "1436 << stringFromIslObj(AssumptionCtx, "null"));1437 isl::set newContext =1438 scop->getContext().intersect(isl::manage(AssumptionCtx));1439 scop->setContext(newContext);1440 }1441}1442 1443bool ScopBuilder::buildAccessMultiDimFixed(MemAccInst Inst, ScopStmt *Stmt) {1444 // Memory builtins are not considered in this function.1445 if (!Inst.isLoad() && !Inst.isStore())1446 return false;1447 1448 Value *Val = Inst.getValueOperand();1449 Type *ElementType = Val->getType();1450 Value *Address = Inst.getPointerOperand();1451 const SCEV *AccessFunction =1452 SE.getSCEVAtScope(Address, LI.getLoopFor(Inst->getParent()));1453 const SCEVUnknown *BasePointer =1454 dyn_cast<SCEVUnknown>(SE.getPointerBase(AccessFunction));1455 enum MemoryAccess::AccessType AccType =1456 isa<LoadInst>(Inst) ? MemoryAccess::READ : MemoryAccess::MUST_WRITE;1457 1458 if (auto *BitCast = dyn_cast<BitCastInst>(Address))1459 Address = BitCast->getOperand(0);1460 1461 auto *GEP = dyn_cast<GetElementPtrInst>(Address);1462 if (!GEP || DL.getTypeAllocSize(GEP->getResultElementType()) !=1463 DL.getTypeAllocSize(ElementType))1464 return false;1465 1466 SmallVector<const SCEV *, 4> Subscripts;1467 SmallVector<int, 4> Sizes;1468 getIndexExpressionsFromGEP(SE, GEP, Subscripts, Sizes);1469 auto *BasePtr = GEP->getOperand(0);1470 1471 if (auto *BasePtrCast = dyn_cast<BitCastInst>(BasePtr))1472 BasePtr = BasePtrCast->getOperand(0);1473 1474 // Check for identical base pointers to ensure that we do not miss index1475 // offsets that have been added before this GEP is applied.1476 if (BasePtr != BasePointer->getValue())1477 return false;1478 1479 std::vector<const SCEV *> SizesSCEV;1480 1481 const InvariantLoadsSetTy &ScopRIL = scop->getRequiredInvariantLoads();1482 1483 Loop *SurroundingLoop = Stmt->getSurroundingLoop();1484 for (auto *Subscript : Subscripts) {1485 InvariantLoadsSetTy AccessILS;1486 if (!isAffineExpr(&scop->getRegion(), SurroundingLoop, Subscript, SE,1487 &AccessILS))1488 return false;1489 1490 for (LoadInst *LInst : AccessILS)1491 if (!ScopRIL.count(LInst))1492 return false;1493 }1494 1495 if (Sizes.empty())1496 return false;1497 1498 SizesSCEV.push_back(nullptr);1499 1500 for (auto V : Sizes)1501 SizesSCEV.push_back(SE.getSCEV(1502 ConstantInt::get(IntegerType::getInt64Ty(BasePtr->getContext()), V)));1503 1504 addArrayAccess(Stmt, Inst, AccType, BasePointer->getValue(), ElementType,1505 true, Subscripts, SizesSCEV, Val);1506 return true;1507}1508 1509bool ScopBuilder::buildAccessMultiDimParam(MemAccInst Inst, ScopStmt *Stmt) {1510 // Memory builtins are not considered by this function.1511 if (!Inst.isLoad() && !Inst.isStore())1512 return false;1513 1514 if (!PollyDelinearize)1515 return false;1516 1517 Value *Address = Inst.getPointerOperand();1518 Value *Val = Inst.getValueOperand();1519 Type *ElementType = Val->getType();1520 unsigned ElementSize = DL.getTypeAllocSize(ElementType);1521 enum MemoryAccess::AccessType AccType =1522 isa<LoadInst>(Inst) ? MemoryAccess::READ : MemoryAccess::MUST_WRITE;1523 1524 const SCEV *AccessFunction =1525 SE.getSCEVAtScope(Address, LI.getLoopFor(Inst->getParent()));1526 const SCEVUnknown *BasePointer =1527 dyn_cast<SCEVUnknown>(SE.getPointerBase(AccessFunction));1528 1529 assert(BasePointer && "Could not find base pointer");1530 1531 auto &InsnToMemAcc = scop->getInsnToMemAccMap();1532 auto AccItr = InsnToMemAcc.find(Inst);1533 if (AccItr == InsnToMemAcc.end())1534 return false;1535 1536 std::vector<const SCEV *> Sizes = {nullptr};1537 1538 Sizes.insert(Sizes.end(), AccItr->second.Shape->DelinearizedSizes.begin(),1539 AccItr->second.Shape->DelinearizedSizes.end());1540 1541 // In case only the element size is contained in the 'Sizes' array, the1542 // access does not access a real multi-dimensional array. Hence, we allow1543 // the normal single-dimensional access construction to handle this.1544 if (Sizes.size() == 1)1545 return false;1546 1547 // Remove the element size. This information is already provided by the1548 // ElementSize parameter. In case the element size of this access and the1549 // element size used for delinearization differs the delinearization is1550 // incorrect. Hence, we invalidate the scop.1551 //1552 // TODO: Handle delinearization with differing element sizes.1553 auto DelinearizedSize =1554 cast<SCEVConstant>(Sizes.back())->getAPInt().getSExtValue();1555 Sizes.pop_back();1556 if (ElementSize != DelinearizedSize)1557 scop->invalidate(DELINEARIZATION, Inst->getDebugLoc(), Inst->getParent());1558 1559 addArrayAccess(Stmt, Inst, AccType, BasePointer->getValue(), ElementType,1560 true, AccItr->second.DelinearizedSubscripts, Sizes, Val);1561 return true;1562}1563 1564bool ScopBuilder::buildAccessMemIntrinsic(MemAccInst Inst, ScopStmt *Stmt) {1565 auto *MemIntr = dyn_cast_or_null<MemIntrinsic>(Inst);1566 1567 if (MemIntr == nullptr)1568 return false;1569 1570 auto *L = LI.getLoopFor(Inst->getParent());1571 const SCEV *LengthVal = SE.getSCEVAtScope(MemIntr->getLength(), L);1572 assert(LengthVal);1573 1574 // Check if the length val is actually affine or if we overapproximate it1575 InvariantLoadsSetTy AccessILS;1576 const InvariantLoadsSetTy &ScopRIL = scop->getRequiredInvariantLoads();1577 1578 Loop *SurroundingLoop = Stmt->getSurroundingLoop();1579 bool LengthIsAffine = isAffineExpr(&scop->getRegion(), SurroundingLoop,1580 LengthVal, SE, &AccessILS);1581 for (LoadInst *LInst : AccessILS)1582 if (!ScopRIL.count(LInst))1583 LengthIsAffine = false;1584 if (!LengthIsAffine)1585 LengthVal = nullptr;1586 1587 auto *DestPtrVal = MemIntr->getDest();1588 assert(DestPtrVal);1589 1590 const SCEV *DestAccFunc = SE.getSCEVAtScope(DestPtrVal, L);1591 assert(DestAccFunc);1592 // Ignore accesses to "NULL".1593 // TODO: We could use this to optimize the region further, e.g., intersect1594 // the context with1595 // isl_set_complement(isl_set_params(getDomain()))1596 // as we know it would be undefined to execute this instruction anyway.1597 if (DestAccFunc->isZero())1598 return true;1599 1600 if (auto *U = dyn_cast<SCEVUnknown>(DestAccFunc)) {1601 if (isa<ConstantPointerNull>(U->getValue()))1602 return true;1603 }1604 1605 auto *DestPtrSCEV = dyn_cast<SCEVUnknown>(SE.getPointerBase(DestAccFunc));1606 assert(DestPtrSCEV);1607 DestAccFunc = SE.getMinusSCEV(DestAccFunc, DestPtrSCEV);1608 addArrayAccess(Stmt, Inst, MemoryAccess::MUST_WRITE, DestPtrSCEV->getValue(),1609 IntegerType::getInt8Ty(DestPtrVal->getContext()),1610 LengthIsAffine, {DestAccFunc, LengthVal}, {nullptr},1611 Inst.getValueOperand());1612 1613 auto *MemTrans = dyn_cast<MemTransferInst>(MemIntr);1614 if (!MemTrans)1615 return true;1616 1617 auto *SrcPtrVal = MemTrans->getSource();1618 assert(SrcPtrVal);1619 1620 const SCEV *SrcAccFunc = SE.getSCEVAtScope(SrcPtrVal, L);1621 assert(SrcAccFunc);1622 // Ignore accesses to "NULL".1623 // TODO: See above TODO1624 if (SrcAccFunc->isZero())1625 return true;1626 1627 auto *SrcPtrSCEV = dyn_cast<SCEVUnknown>(SE.getPointerBase(SrcAccFunc));1628 assert(SrcPtrSCEV);1629 SrcAccFunc = SE.getMinusSCEV(SrcAccFunc, SrcPtrSCEV);1630 addArrayAccess(Stmt, Inst, MemoryAccess::READ, SrcPtrSCEV->getValue(),1631 IntegerType::getInt8Ty(SrcPtrVal->getContext()),1632 LengthIsAffine, {SrcAccFunc, LengthVal}, {nullptr},1633 Inst.getValueOperand());1634 1635 return true;1636}1637 1638bool ScopBuilder::buildAccessCallInst(MemAccInst Inst, ScopStmt *Stmt) {1639 auto *CI = dyn_cast_or_null<CallInst>(Inst);1640 1641 if (CI == nullptr)1642 return false;1643 1644 if (CI->doesNotAccessMemory() || isIgnoredIntrinsic(CI) || isDebugCall(CI))1645 return true;1646 1647 const SCEV *AF = SE.getConstant(IntegerType::getInt64Ty(CI->getContext()), 0);1648 auto *CalledFunction = CI->getCalledFunction();1649 MemoryEffects ME = AA.getMemoryEffects(CalledFunction);1650 if (ME.doesNotAccessMemory())1651 return true;1652 1653 if (ME.onlyAccessesArgPointees()) {1654 ModRefInfo ArgMR = ME.getModRef(IRMemLocation::ArgMem);1655 auto AccType =1656 !isModSet(ArgMR) ? MemoryAccess::READ : MemoryAccess::MAY_WRITE;1657 Loop *L = LI.getLoopFor(Inst->getParent());1658 for (const auto &Arg : CI->args()) {1659 if (!Arg->getType()->isPointerTy())1660 continue;1661 1662 const SCEV *ArgSCEV = SE.getSCEVAtScope(Arg, L);1663 if (ArgSCEV->isZero())1664 continue;1665 1666 if (auto *U = dyn_cast<SCEVUnknown>(ArgSCEV)) {1667 if (isa<ConstantPointerNull>(U->getValue()))1668 return true;1669 }1670 1671 auto *ArgBasePtr = cast<SCEVUnknown>(SE.getPointerBase(ArgSCEV));1672 addArrayAccess(Stmt, Inst, AccType, ArgBasePtr->getValue(),1673 ArgBasePtr->getType(), false, {AF}, {nullptr}, CI);1674 }1675 return true;1676 }1677 1678 if (ME.onlyReadsMemory()) {1679 GlobalReads.emplace_back(Stmt, CI);1680 return true;1681 }1682 return false;1683}1684 1685bool ScopBuilder::buildAccessSingleDim(MemAccInst Inst, ScopStmt *Stmt) {1686 // Memory builtins are not considered by this function.1687 if (!Inst.isLoad() && !Inst.isStore())1688 return false;1689 1690 Value *Address = Inst.getPointerOperand();1691 Value *Val = Inst.getValueOperand();1692 Type *ElementType = Val->getType();1693 enum MemoryAccess::AccessType AccType =1694 isa<LoadInst>(Inst) ? MemoryAccess::READ : MemoryAccess::MUST_WRITE;1695 1696 const SCEV *AccessFunction =1697 SE.getSCEVAtScope(Address, LI.getLoopFor(Inst->getParent()));1698 const SCEVUnknown *BasePointer =1699 dyn_cast<SCEVUnknown>(SE.getPointerBase(AccessFunction));1700 1701 assert(BasePointer && "Could not find base pointer");1702 AccessFunction = SE.getMinusSCEV(AccessFunction, BasePointer);1703 1704 // Check if the access depends on a loop contained in a non-affine subregion.1705 bool isVariantInNonAffineLoop = false;1706 SetVector<const Loop *> Loops;1707 findLoops(AccessFunction, Loops);1708 for (const Loop *L : Loops)1709 if (Stmt->contains(L)) {1710 isVariantInNonAffineLoop = true;1711 break;1712 }1713 1714 InvariantLoadsSetTy AccessILS;1715 1716 Loop *SurroundingLoop = Stmt->getSurroundingLoop();1717 bool IsAffine = !isVariantInNonAffineLoop &&1718 isAffineExpr(&scop->getRegion(), SurroundingLoop,1719 AccessFunction, SE, &AccessILS);1720 1721 const InvariantLoadsSetTy &ScopRIL = scop->getRequiredInvariantLoads();1722 for (LoadInst *LInst : AccessILS)1723 if (!ScopRIL.count(LInst))1724 IsAffine = false;1725 1726 if (!IsAffine && AccType == MemoryAccess::MUST_WRITE)1727 AccType = MemoryAccess::MAY_WRITE;1728 1729 addArrayAccess(Stmt, Inst, AccType, BasePointer->getValue(), ElementType,1730 IsAffine, {AccessFunction}, {nullptr}, Val);1731 return true;1732}1733 1734void ScopBuilder::buildMemoryAccess(MemAccInst Inst, ScopStmt *Stmt) {1735 if (buildAccessMemIntrinsic(Inst, Stmt))1736 return;1737 1738 if (buildAccessCallInst(Inst, Stmt))1739 return;1740 1741 if (buildAccessMultiDimFixed(Inst, Stmt))1742 return;1743 1744 if (buildAccessMultiDimParam(Inst, Stmt))1745 return;1746 1747 if (buildAccessSingleDim(Inst, Stmt))1748 return;1749 1750 llvm_unreachable(1751 "At least one of the buildAccess functions must handled this access, or "1752 "ScopDetection should have rejected this SCoP");1753}1754 1755void ScopBuilder::buildAccessFunctions() {1756 for (auto &Stmt : *scop) {1757 if (Stmt.isBlockStmt()) {1758 buildAccessFunctions(&Stmt, *Stmt.getBasicBlock());1759 continue;1760 }1761 1762 Region *R = Stmt.getRegion();1763 for (BasicBlock *BB : R->blocks())1764 buildAccessFunctions(&Stmt, *BB, R);1765 }1766 1767 // Build write accesses for values that are used after the SCoP.1768 // The instructions defining them might be synthesizable and therefore not1769 // contained in any statement, hence we iterate over the original instructions1770 // to identify all escaping values.1771 for (BasicBlock *BB : scop->getRegion().blocks()) {1772 for (Instruction &Inst : *BB)1773 buildEscapingDependences(&Inst);1774 }1775}1776 1777bool ScopBuilder::shouldModelInst(Instruction *Inst, Loop *L) {1778 return !Inst->isTerminator() && !isIgnoredIntrinsic(Inst) &&1779 !canSynthesize(Inst, *scop, &SE, L);1780}1781 1782/// Generate a name for a statement.1783///1784/// @param BB The basic block the statement will represent.1785/// @param BBIdx The index of the @p BB relative to other BBs/regions.1786/// @param Count The index of the created statement in @p BB.1787/// @param IsMain Whether this is the main of all statement for @p BB. If true,1788/// no suffix will be added.1789/// @param IsLast Uses a special indicator for the last statement of a BB.1790static std::string makeStmtName(BasicBlock *BB, long BBIdx, int Count,1791 bool IsMain, bool IsLast = false) {1792 std::string Suffix;1793 if (!IsMain) {1794 if (UseInstructionNames)1795 Suffix = '_';1796 if (IsLast)1797 Suffix += "last";1798 else if (Count < 26)1799 Suffix += 'a' + Count;1800 else1801 Suffix += std::to_string(Count);1802 }1803 return getIslCompatibleName("Stmt", BB, BBIdx, Suffix, UseInstructionNames);1804}1805 1806/// Generate a name for a statement that represents a non-affine subregion.1807///1808/// @param R The region the statement will represent.1809/// @param RIdx The index of the @p R relative to other BBs/regions.1810static std::string makeStmtName(Region *R, long RIdx) {1811 return getIslCompatibleName("Stmt", R->getNameStr(), RIdx, "",1812 UseInstructionNames);1813}1814 1815void ScopBuilder::buildSequentialBlockStmts(BasicBlock *BB, bool SplitOnStore) {1816 Loop *SurroundingLoop = LI.getLoopFor(BB);1817 1818 int Count = 0;1819 long BBIdx = scop->getNextStmtIdx();1820 std::vector<Instruction *> Instructions;1821 for (Instruction &Inst : *BB) {1822 if (shouldModelInst(&Inst, SurroundingLoop))1823 Instructions.push_back(&Inst);1824 if (Inst.getMetadata("polly_split_after") ||1825 (SplitOnStore && isa<StoreInst>(Inst))) {1826 std::string Name = makeStmtName(BB, BBIdx, Count, Count == 0);1827 scop->addScopStmt(BB, Name, SurroundingLoop, Instructions);1828 Count++;1829 Instructions.clear();1830 }1831 }1832 1833 std::string Name = makeStmtName(BB, BBIdx, Count, Count == 0);1834 scop->addScopStmt(BB, Name, SurroundingLoop, Instructions);1835}1836 1837/// Is @p Inst an ordered instruction?1838///1839/// An unordered instruction is an instruction, such that a sequence of1840/// unordered instructions can be permuted without changing semantics. Any1841/// instruction for which this is not always the case is ordered.1842static bool isOrderedInstruction(Instruction *Inst) {1843 return Inst->mayHaveSideEffects() || Inst->mayReadOrWriteMemory();1844}1845 1846/// Join instructions to the same statement if one uses the scalar result of the1847/// other.1848static void joinOperandTree(EquivalenceClasses<Instruction *> &UnionFind,1849 ArrayRef<Instruction *> ModeledInsts) {1850 for (Instruction *Inst : ModeledInsts) {1851 if (isa<PHINode>(Inst))1852 continue;1853 1854 for (Use &Op : Inst->operands()) {1855 Instruction *OpInst = dyn_cast<Instruction>(Op.get());1856 if (!OpInst)1857 continue;1858 1859 // Check if OpInst is in the BB and is a modeled instruction.1860 if (!UnionFind.contains(OpInst))1861 continue;1862 1863 UnionFind.unionSets(Inst, OpInst);1864 }1865 }1866}1867 1868/// Ensure that the order of ordered instructions does not change.1869///1870/// If we encounter an ordered instruction enclosed in instructions belonging to1871/// a different statement (which might as well contain ordered instructions, but1872/// this is not tested here), join them.1873static void1874joinOrderedInstructions(EquivalenceClasses<Instruction *> &UnionFind,1875 ArrayRef<Instruction *> ModeledInsts) {1876 SetVector<Instruction *> SeenLeaders;1877 for (Instruction *Inst : ModeledInsts) {1878 if (!isOrderedInstruction(Inst))1879 continue;1880 1881 Instruction *Leader = UnionFind.getLeaderValue(Inst);1882 // Since previous iterations might have merged sets, some items in1883 // SeenLeaders are not leaders anymore. However, The new leader of1884 // previously merged instructions must be one of the former leaders of1885 // these merged instructions.1886 bool Inserted = SeenLeaders.insert(Leader);1887 if (Inserted)1888 continue;1889 1890 // Merge statements to close holes. Say, we have already seen statements A1891 // and B, in this order. Then we see an instruction of A again and we would1892 // see the pattern "A B A". This function joins all statements until the1893 // only seen occurrence of A.1894 for (Instruction *Prev : reverse(SeenLeaders)) {1895 // We are backtracking from the last element until we see Inst's leader1896 // in SeenLeaders and merge all into one set. Although leaders of1897 // instructions change during the execution of this loop, it's irrelevant1898 // as we are just searching for the element that we already confirmed is1899 // in the list.1900 if (Prev == Leader)1901 break;1902 UnionFind.unionSets(Prev, Leader);1903 }1904 }1905}1906 1907/// If the BasicBlock has an edge from itself, ensure that the PHI WRITEs for1908/// the incoming values from this block are executed after the PHI READ.1909///1910/// Otherwise it could overwrite the incoming value from before the BB with the1911/// value for the next execution. This can happen if the PHI WRITE is added to1912/// the statement with the instruction that defines the incoming value (instead1913/// of the last statement of the same BB). To ensure that the PHI READ and WRITE1914/// are in order, we put both into the statement. PHI WRITEs are always executed1915/// after PHI READs when they are in the same statement.1916///1917/// TODO: This is an overpessimization. We only have to ensure that the PHI1918/// WRITE is not put into a statement containing the PHI itself. That could also1919/// be done by1920/// - having all (strongly connected) PHIs in a single statement,1921/// - unite only the PHIs in the operand tree of the PHI WRITE (because it only1922/// has a chance of being lifted before a PHI by being in a statement with a1923/// PHI that comes before in the basic block), or1924/// - when uniting statements, ensure that no (relevant) PHIs are overtaken.1925static void joinOrderedPHIs(EquivalenceClasses<Instruction *> &UnionFind,1926 ArrayRef<Instruction *> ModeledInsts) {1927 for (Instruction *Inst : ModeledInsts) {1928 PHINode *PHI = dyn_cast<PHINode>(Inst);1929 if (!PHI)1930 continue;1931 1932 int Idx = PHI->getBasicBlockIndex(PHI->getParent());1933 if (Idx < 0)1934 continue;1935 1936 Instruction *IncomingVal =1937 dyn_cast<Instruction>(PHI->getIncomingValue(Idx));1938 if (!IncomingVal)1939 continue;1940 1941 UnionFind.unionSets(PHI, IncomingVal);1942 }1943}1944 1945void ScopBuilder::buildEqivClassBlockStmts(BasicBlock *BB) {1946 Loop *L = LI.getLoopFor(BB);1947 1948 // Extracting out modeled instructions saves us from checking1949 // shouldModelInst() repeatedly.1950 SmallVector<Instruction *, 32> ModeledInsts;1951 EquivalenceClasses<Instruction *> UnionFind;1952 Instruction *MainInst = nullptr, *MainLeader = nullptr;1953 for (Instruction &Inst : *BB) {1954 if (!shouldModelInst(&Inst, L))1955 continue;1956 ModeledInsts.push_back(&Inst);1957 UnionFind.insert(&Inst);1958 1959 // When a BB is split into multiple statements, the main statement is the1960 // one containing the 'main' instruction. We select the first instruction1961 // that is unlikely to be removed (because it has side-effects) as the main1962 // one. It is used to ensure that at least one statement from the bb has the1963 // same name as with -polly-stmt-granularity=bb.1964 if (!MainInst && (isa<StoreInst>(Inst) ||1965 (isa<CallInst>(Inst) && !isa<IntrinsicInst>(Inst))))1966 MainInst = &Inst;1967 }1968 1969 joinOperandTree(UnionFind, ModeledInsts);1970 joinOrderedInstructions(UnionFind, ModeledInsts);1971 joinOrderedPHIs(UnionFind, ModeledInsts);1972 1973 // The list of instructions for statement (statement represented by the leader1974 // instruction).1975 MapVector<Instruction *, std::vector<Instruction *>> LeaderToInstList;1976 1977 // The order of statements must be preserved w.r.t. their ordered1978 // instructions. Without this explicit scan, we would also use non-ordered1979 // instructions (whose order is arbitrary) to determine statement order.1980 for (Instruction *Inst : ModeledInsts) {1981 if (!isOrderedInstruction(Inst))1982 continue;1983 1984 auto LeaderIt = UnionFind.findLeader(Inst);1985 if (LeaderIt == UnionFind.member_end())1986 continue;1987 1988 // Insert element for the leader instruction.1989 (void)LeaderToInstList[*LeaderIt];1990 }1991 1992 // Collect the instructions of all leaders. UnionFind's member iterator1993 // unfortunately are not in any specific order.1994 for (Instruction *Inst : ModeledInsts) {1995 auto LeaderIt = UnionFind.findLeader(Inst);1996 if (LeaderIt == UnionFind.member_end())1997 continue;1998 1999 if (Inst == MainInst)2000 MainLeader = *LeaderIt;2001 std::vector<Instruction *> &InstList = LeaderToInstList[*LeaderIt];2002 InstList.push_back(Inst);2003 }2004 2005 // Finally build the statements.2006 int Count = 0;2007 long BBIdx = scop->getNextStmtIdx();2008 for (auto &Instructions : LeaderToInstList) {2009 std::vector<Instruction *> &InstList = Instructions.second;2010 2011 // If there is no main instruction, make the first statement the main.2012 bool IsMain = (MainInst ? MainLeader == Instructions.first : Count == 0);2013 2014 std::string Name = makeStmtName(BB, BBIdx, Count, IsMain);2015 scop->addScopStmt(BB, Name, L, std::move(InstList));2016 Count += 1;2017 }2018 2019 // Unconditionally add an epilogue (last statement). It contains no2020 // instructions, but holds the PHI write accesses for successor basic blocks,2021 // if the incoming value is not defined in another statement if the same BB.2022 // The epilogue becomes the main statement only if there is no other2023 // statement that could become main.2024 // The epilogue will be removed if no PHIWrite is added to it.2025 std::string EpilogueName = makeStmtName(BB, BBIdx, Count, Count == 0, true);2026 scop->addScopStmt(BB, EpilogueName, L, {});2027}2028 2029void ScopBuilder::buildStmts(Region &SR) {2030 if (scop->isNonAffineSubRegion(&SR)) {2031 std::vector<Instruction *> Instructions;2032 Loop *SurroundingLoop =2033 getFirstNonBoxedLoopFor(SR.getEntry(), LI, scop->getBoxedLoops());2034 for (Instruction &Inst : *SR.getEntry())2035 if (shouldModelInst(&Inst, SurroundingLoop))2036 Instructions.push_back(&Inst);2037 long RIdx = scop->getNextStmtIdx();2038 std::string Name = makeStmtName(&SR, RIdx);2039 scop->addScopStmt(&SR, Name, SurroundingLoop, Instructions);2040 return;2041 }2042 2043 for (auto I = SR.element_begin(), E = SR.element_end(); I != E; ++I)2044 if (I->isSubRegion())2045 buildStmts(*I->getNodeAs<Region>());2046 else {2047 BasicBlock *BB = I->getNodeAs<BasicBlock>();2048 switch (StmtGranularity) {2049 case GranularityChoice::BasicBlocks:2050 buildSequentialBlockStmts(BB);2051 break;2052 case GranularityChoice::ScalarIndependence:2053 buildEqivClassBlockStmts(BB);2054 break;2055 case GranularityChoice::Stores:2056 buildSequentialBlockStmts(BB, true);2057 break;2058 }2059 }2060}2061 2062void ScopBuilder::buildAccessFunctions(ScopStmt *Stmt, BasicBlock &BB,2063 Region *NonAffineSubRegion) {2064 assert(2065 Stmt &&2066 "The exit BB is the only one that cannot be represented by a statement");2067 assert(Stmt->represents(&BB));2068 2069 // We do not build access functions for error blocks, as they may contain2070 // instructions we can not model.2071 if (SD.isErrorBlock(BB, scop->getRegion()))2072 return;2073 2074 auto BuildAccessesForInst = [this, Stmt,2075 NonAffineSubRegion](Instruction *Inst) {2076 PHINode *PHI = dyn_cast<PHINode>(Inst);2077 if (PHI)2078 buildPHIAccesses(Stmt, PHI, NonAffineSubRegion, false);2079 2080 if (auto MemInst = MemAccInst::dyn_cast(*Inst)) {2081 assert(Stmt && "Cannot build access function in non-existing statement");2082 buildMemoryAccess(MemInst, Stmt);2083 }2084 2085 // PHI nodes have already been modeled above and terminators that are2086 // not part of a non-affine subregion are fully modeled and regenerated2087 // from the polyhedral domains. Hence, they do not need to be modeled as2088 // explicit data dependences.2089 if (!PHI)2090 buildScalarDependences(Stmt, Inst);2091 };2092 2093 const InvariantLoadsSetTy &RIL = scop->getRequiredInvariantLoads();2094 bool IsEntryBlock = (Stmt->getEntryBlock() == &BB);2095 if (IsEntryBlock) {2096 for (Instruction *Inst : Stmt->getInstructions())2097 BuildAccessesForInst(Inst);2098 if (Stmt->isRegionStmt())2099 BuildAccessesForInst(BB.getTerminator());2100 } else {2101 for (Instruction &Inst : BB) {2102 if (isIgnoredIntrinsic(&Inst))2103 continue;2104 2105 // Invariant loads already have been processed.2106 if (isa<LoadInst>(Inst) && RIL.count(cast<LoadInst>(&Inst)))2107 continue;2108 2109 BuildAccessesForInst(&Inst);2110 }2111 }2112}2113 2114MemoryAccess *ScopBuilder::addMemoryAccess(2115 ScopStmt *Stmt, Instruction *Inst, MemoryAccess::AccessType AccType,2116 Value *BaseAddress, Type *ElementType, bool Affine, Value *AccessValue,2117 ArrayRef<const SCEV *> Subscripts, ArrayRef<const SCEV *> Sizes,2118 MemoryKind Kind) {2119 bool isKnownMustAccess = false;2120 2121 // Accesses in single-basic block statements are always executed.2122 if (Stmt->isBlockStmt())2123 isKnownMustAccess = true;2124 2125 if (Stmt->isRegionStmt()) {2126 // Accesses that dominate the exit block of a non-affine region are always2127 // executed. In non-affine regions there may exist MemoryKind::Values that2128 // do not dominate the exit. MemoryKind::Values will always dominate the2129 // exit and MemoryKind::PHIs only if there is at most one PHI_WRITE in the2130 // non-affine region.2131 if (Inst && DT.dominates(Inst->getParent(), Stmt->getRegion()->getExit()))2132 isKnownMustAccess = true;2133 }2134 2135 // Non-affine PHI writes do not "happen" at a particular instruction, but2136 // after exiting the statement. Therefore they are guaranteed to execute and2137 // overwrite the old value.2138 if (Kind == MemoryKind::PHI || Kind == MemoryKind::ExitPHI)2139 isKnownMustAccess = true;2140 2141 if (!isKnownMustAccess && AccType == MemoryAccess::MUST_WRITE)2142 AccType = MemoryAccess::MAY_WRITE;2143 2144 auto *Access = new MemoryAccess(Stmt, Inst, AccType, BaseAddress, ElementType,2145 Affine, Subscripts, Sizes, AccessValue, Kind);2146 2147 scop->addAccessFunction(Access);2148 Stmt->addAccess(Access);2149 return Access;2150}2151 2152void ScopBuilder::addArrayAccess(ScopStmt *Stmt, MemAccInst MemAccInst,2153 MemoryAccess::AccessType AccType,2154 Value *BaseAddress, Type *ElementType,2155 bool IsAffine,2156 ArrayRef<const SCEV *> Subscripts,2157 ArrayRef<const SCEV *> Sizes,2158 Value *AccessValue) {2159 ArrayBasePointers.insert(BaseAddress);2160 addMemoryAccess(Stmt, MemAccInst, AccType, BaseAddress, ElementType, IsAffine,2161 AccessValue, Subscripts, Sizes, MemoryKind::Array);2162}2163 2164/// Check if @p Expr is divisible by @p Size.2165static bool isDivisible(const SCEV *Expr, unsigned Size, ScalarEvolution &SE) {2166 assert(Size != 0);2167 if (Size == 1)2168 return true;2169 2170 // Only one factor needs to be divisible.2171 if (auto *MulExpr = dyn_cast<SCEVMulExpr>(Expr)) {2172 for (const SCEV *FactorExpr : MulExpr->operands())2173 if (isDivisible(FactorExpr, Size, SE))2174 return true;2175 return false;2176 }2177 2178 // For other n-ary expressions (Add, AddRec, Max,...) all operands need2179 // to be divisible.2180 if (auto *NAryExpr = dyn_cast<SCEVNAryExpr>(Expr)) {2181 for (const SCEV *OpExpr : NAryExpr->operands())2182 if (!isDivisible(OpExpr, Size, SE))2183 return false;2184 return true;2185 }2186 2187 const SCEV *SizeSCEV = SE.getConstant(Expr->getType(), Size);2188 const SCEV *UDivSCEV = SE.getUDivExpr(Expr, SizeSCEV);2189 const SCEV *MulSCEV = SE.getMulExpr(UDivSCEV, SizeSCEV);2190 return MulSCEV == Expr;2191}2192 2193void ScopBuilder::foldSizeConstantsToRight() {2194 isl::union_set Accessed = scop->getAccesses().range();2195 2196 for (auto Array : scop->arrays()) {2197 if (Array->getNumberOfDimensions() <= 1)2198 continue;2199 2200 isl::space Space = Array->getSpace();2201 Space = Space.align_params(Accessed.get_space());2202 2203 if (!Accessed.contains(Space))2204 continue;2205 2206 isl::set Elements = Accessed.extract_set(Space);2207 isl::map Transform = isl::map::universe(Array->getSpace().map_from_set());2208 2209 std::vector<int> Int;2210 unsigned Dims = unsignedFromIslSize(Elements.tuple_dim());2211 for (unsigned i = 0; i < Dims; i++) {2212 isl::set DimOnly = isl::set(Elements).project_out(isl::dim::set, 0, i);2213 DimOnly = DimOnly.project_out(isl::dim::set, 1, Dims - i - 1);2214 DimOnly = DimOnly.lower_bound_si(isl::dim::set, 0, 0);2215 2216 isl::basic_set DimHull = DimOnly.affine_hull();2217 2218 if (i == Dims - 1) {2219 Int.push_back(1);2220 Transform = Transform.equate(isl::dim::in, i, isl::dim::out, i);2221 continue;2222 }2223 2224 if (unsignedFromIslSize(DimHull.dim(isl::dim::div)) == 1) {2225 isl::aff Diff = DimHull.get_div(0);2226 isl::val Val = Diff.get_denominator_val();2227 2228 int ValInt = 1;2229 if (Val.is_int()) {2230 auto ValAPInt = APIntFromVal(Val);2231 if (ValAPInt.isSignedIntN(32))2232 ValInt = ValAPInt.getSExtValue();2233 } else {2234 }2235 2236 Int.push_back(ValInt);2237 isl::constraint C = isl::constraint::alloc_equality(2238 isl::local_space(Transform.get_space()));2239 C = C.set_coefficient_si(isl::dim::out, i, ValInt);2240 C = C.set_coefficient_si(isl::dim::in, i, -1);2241 Transform = Transform.add_constraint(C);2242 continue;2243 }2244 2245 isl::basic_set ZeroSet = isl::basic_set(DimHull);2246 ZeroSet = ZeroSet.fix_si(isl::dim::set, 0, 0);2247 2248 int ValInt = 1;2249 if (ZeroSet.is_equal(DimHull)) {2250 ValInt = 0;2251 }2252 2253 Int.push_back(ValInt);2254 Transform = Transform.equate(isl::dim::in, i, isl::dim::out, i);2255 }2256 2257 isl::set MappedElements = isl::map(Transform).domain();2258 if (!Elements.is_subset(MappedElements))2259 continue;2260 2261 bool CanFold = true;2262 if (Int[0] <= 1)2263 CanFold = false;2264 2265 unsigned NumDims = Array->getNumberOfDimensions();2266 for (unsigned i = 1; i < NumDims - 1; i++)2267 if (Int[0] != Int[i] && Int[i])2268 CanFold = false;2269 2270 if (!CanFold)2271 continue;2272 2273 for (auto &Access : scop->access_functions())2274 if (Access->getScopArrayInfo() == Array)2275 Access->setAccessRelation(2276 Access->getAccessRelation().apply_range(Transform));2277 2278 std::vector<const SCEV *> Sizes;2279 for (unsigned i = 0; i < NumDims; i++) {2280 auto Size = Array->getDimensionSize(i);2281 2282 if (i == NumDims - 1)2283 Size = SE.getMulExpr(Size, SE.getConstant(Size->getType(), Int[0]));2284 Sizes.push_back(Size);2285 }2286 2287 Array->updateSizes(Sizes, false /* CheckConsistency */);2288 }2289}2290 2291void ScopBuilder::finalizeAccesses() {2292 updateAccessDimensionality();2293 foldSizeConstantsToRight();2294 foldAccessRelations();2295 assumeNoOutOfBounds();2296}2297 2298void ScopBuilder::updateAccessDimensionality() {2299 // Check all array accesses for each base pointer and find a (virtual) element2300 // size for the base pointer that divides all access functions.2301 for (ScopStmt &Stmt : *scop)2302 for (MemoryAccess *Access : Stmt) {2303 if (!Access->isArrayKind())2304 continue;2305 ScopArrayInfo *Array =2306 const_cast<ScopArrayInfo *>(Access->getScopArrayInfo());2307 2308 if (Array->getNumberOfDimensions() != 1)2309 continue;2310 unsigned DivisibleSize = Array->getElemSizeInBytes();2311 const SCEV *Subscript = Access->getSubscript(0);2312 while (!isDivisible(Subscript, DivisibleSize, SE))2313 DivisibleSize /= 2;2314 auto *Ty = IntegerType::get(SE.getContext(), DivisibleSize * 8);2315 Array->updateElementType(Ty);2316 }2317 2318 for (auto &Stmt : *scop)2319 for (auto &Access : Stmt)2320 Access->updateDimensionality();2321}2322 2323void ScopBuilder::foldAccessRelations() {2324 for (auto &Stmt : *scop)2325 for (auto &Access : Stmt)2326 Access->foldAccessRelation();2327}2328 2329void ScopBuilder::assumeNoOutOfBounds() {2330 if (PollyIgnoreInbounds)2331 return;2332 for (auto &Stmt : *scop)2333 for (auto &Access : Stmt) {2334 isl::set Outside = Access->assumeNoOutOfBound();2335 const auto &Loc = Access->getAccessInstruction()2336 ? Access->getAccessInstruction()->getDebugLoc()2337 : DebugLoc();2338 recordAssumption(&RecordedAssumptions, INBOUNDS, Outside, Loc,2339 AS_ASSUMPTION);2340 }2341}2342 2343void ScopBuilder::ensureValueWrite(Instruction *Inst) {2344 // Find the statement that defines the value of Inst. That statement has to2345 // write the value to make it available to those statements that read it.2346 ScopStmt *Stmt = scop->getStmtFor(Inst);2347 2348 // It is possible that the value is synthesizable within a loop (such that it2349 // is not part of any statement), but not after the loop (where you need the2350 // number of loop round-trips to synthesize it). In LCSSA-form a PHI node will2351 // avoid this. In case the IR has no such PHI, use the last statement (where2352 // the value is synthesizable) to write the value.2353 if (!Stmt)2354 Stmt = scop->getLastStmtFor(Inst->getParent());2355 2356 // Inst not defined within this SCoP.2357 if (!Stmt)2358 return;2359 2360 // Do not process further if the instruction is already written.2361 if (Stmt->lookupValueWriteOf(Inst))2362 return;2363 2364 addMemoryAccess(Stmt, Inst, MemoryAccess::MUST_WRITE, Inst, Inst->getType(),2365 true, Inst, ArrayRef<const SCEV *>(),2366 ArrayRef<const SCEV *>(), MemoryKind::Value);2367}2368 2369void ScopBuilder::ensureValueRead(Value *V, ScopStmt *UserStmt) {2370 // TODO: Make ScopStmt::ensureValueRead(Value*) offer the same functionality2371 // to be able to replace this one. Currently, there is a split responsibility.2372 // In a first step, the MemoryAccess is created, but without the2373 // AccessRelation. In the second step by ScopStmt::buildAccessRelations(), the2374 // AccessRelation is created. At least for scalar accesses, there is no new2375 // information available at ScopStmt::buildAccessRelations(), so we could2376 // create the AccessRelation right away. This is what2377 // ScopStmt::ensureValueRead(Value*) does.2378 2379 auto *Scope = UserStmt->getSurroundingLoop();2380 auto VUse = VirtualUse::create(scop.get(), UserStmt, Scope, V, false);2381 switch (VUse.getKind()) {2382 case VirtualUse::Constant:2383 case VirtualUse::Block:2384 case VirtualUse::Synthesizable:2385 case VirtualUse::Hoisted:2386 case VirtualUse::Intra:2387 // Uses of these kinds do not need a MemoryAccess.2388 break;2389 2390 case VirtualUse::ReadOnly:2391 // Add MemoryAccess for invariant values only if requested.2392 if (!ModelReadOnlyScalars)2393 break;2394 2395 [[fallthrough]];2396 case VirtualUse::Inter:2397 2398 // Do not create another MemoryAccess for reloading the value if one already2399 // exists.2400 if (UserStmt->lookupValueReadOf(V))2401 break;2402 2403 addMemoryAccess(UserStmt, nullptr, MemoryAccess::READ, V, V->getType(),2404 true, V, ArrayRef<const SCEV *>(), ArrayRef<const SCEV *>(),2405 MemoryKind::Value);2406 2407 // Inter-statement uses need to write the value in their defining statement.2408 if (VUse.isInter())2409 ensureValueWrite(cast<Instruction>(V));2410 break;2411 }2412}2413 2414void ScopBuilder::ensurePHIWrite(PHINode *PHI, ScopStmt *IncomingStmt,2415 BasicBlock *IncomingBlock,2416 Value *IncomingValue, bool IsExitBlock) {2417 // As the incoming block might turn out to be an error statement ensure we2418 // will create an exit PHI SAI object. It is needed during code generation2419 // and would be created later anyway.2420 if (IsExitBlock)2421 scop->getOrCreateScopArrayInfo(PHI, PHI->getType(), {},2422 MemoryKind::ExitPHI);2423 2424 // This is possible if PHI is in the SCoP's entry block. The incoming blocks2425 // from outside the SCoP's region have no statement representation.2426 if (!IncomingStmt)2427 return;2428 2429 // Take care for the incoming value being available in the incoming block.2430 // This must be done before the check for multiple PHI writes because multiple2431 // exiting edges from subregion each can be the effective written value of the2432 // subregion. As such, all of them must be made available in the subregion2433 // statement.2434 ensureValueRead(IncomingValue, IncomingStmt);2435 2436 // Do not add more than one MemoryAccess per PHINode and ScopStmt.2437 if (MemoryAccess *Acc = IncomingStmt->lookupPHIWriteOf(PHI)) {2438 assert(Acc->getAccessInstruction() == PHI);2439 Acc->addIncoming(IncomingBlock, IncomingValue);2440 return;2441 }2442 2443 MemoryAccess *Acc = addMemoryAccess(2444 IncomingStmt, PHI, MemoryAccess::MUST_WRITE, PHI, PHI->getType(), true,2445 PHI, ArrayRef<const SCEV *>(), ArrayRef<const SCEV *>(),2446 IsExitBlock ? MemoryKind::ExitPHI : MemoryKind::PHI);2447 assert(Acc);2448 Acc->addIncoming(IncomingBlock, IncomingValue);2449}2450 2451void ScopBuilder::addPHIReadAccess(ScopStmt *PHIStmt, PHINode *PHI) {2452 addMemoryAccess(PHIStmt, PHI, MemoryAccess::READ, PHI, PHI->getType(), true,2453 PHI, ArrayRef<const SCEV *>(), ArrayRef<const SCEV *>(),2454 MemoryKind::PHI);2455}2456 2457void ScopBuilder::buildDomain(ScopStmt &Stmt) {2458 isl::id Id = isl::id::alloc(scop->getIslCtx(), Stmt.getBaseName(), &Stmt);2459 2460 Stmt.Domain = scop->getDomainConditions(&Stmt);2461 Stmt.Domain = Stmt.Domain.set_tuple_id(Id);2462}2463 2464void ScopBuilder::collectSurroundingLoops(ScopStmt &Stmt) {2465 isl::set Domain = Stmt.getDomain();2466 BasicBlock *BB = Stmt.getEntryBlock();2467 2468 Loop *L = LI.getLoopFor(BB);2469 2470 while (L && Stmt.isRegionStmt() && Stmt.getRegion()->contains(L))2471 L = L->getParentLoop();2472 2473 SmallVector<llvm::Loop *, 8> Loops;2474 2475 while (L && Stmt.getParent()->getRegion().contains(L)) {2476 Loops.push_back(L);2477 L = L->getParentLoop();2478 }2479 2480 Stmt.NestLoops.insert(Stmt.NestLoops.begin(), Loops.rbegin(), Loops.rend());2481}2482 2483/// Return the reduction type for a given binary operator.2484static MemoryAccess::ReductionType2485getReductionType(const BinaryOperator *BinOp) {2486 if (!BinOp)2487 return MemoryAccess::RT_NONE;2488 switch (BinOp->getOpcode()) {2489 case Instruction::FAdd:2490 if (!BinOp->isFast())2491 return MemoryAccess::RT_NONE;2492 [[fallthrough]];2493 case Instruction::Add:2494 return MemoryAccess::RT_ADD;2495 case Instruction::Or:2496 return MemoryAccess::RT_BOR;2497 case Instruction::Xor:2498 return MemoryAccess::RT_BXOR;2499 case Instruction::And:2500 return MemoryAccess::RT_BAND;2501 case Instruction::FMul:2502 if (!BinOp->isFast())2503 return MemoryAccess::RT_NONE;2504 [[fallthrough]];2505 case Instruction::Mul:2506 if (DisableMultiplicativeReductions)2507 return MemoryAccess::RT_NONE;2508 return MemoryAccess::RT_MUL;2509 default:2510 return MemoryAccess::RT_NONE;2511 }2512}2513 2514/// @brief Combine two reduction types2515static MemoryAccess::ReductionType2516combineReductionType(MemoryAccess::ReductionType RT0,2517 MemoryAccess::ReductionType RT1) {2518 if (RT0 == MemoryAccess::RT_BOTTOM)2519 return RT1;2520 if (RT0 == RT1)2521 return RT1;2522 return MemoryAccess::RT_NONE;2523}2524 2525/// True if @p AllAccs intersects with @p MemAccs except @p LoadMA and @p2526/// StoreMA2527bool hasIntersectingAccesses(isl::set AllAccs, MemoryAccess *LoadMA,2528 MemoryAccess *StoreMA, isl::set Domain,2529 SmallVector<MemoryAccess *, 8> &MemAccs) {2530 bool HasIntersectingAccs = false;2531 auto AllAccsNoParams = AllAccs.project_out_all_params();2532 2533 for (MemoryAccess *MA : MemAccs) {2534 if (MA == LoadMA || MA == StoreMA)2535 continue;2536 auto AccRel = MA->getAccessRelation().intersect_domain(Domain);2537 auto Accs = AccRel.range();2538 auto AccsNoParams = Accs.project_out_all_params();2539 2540 bool CompatibleSpace = AllAccsNoParams.has_equal_space(AccsNoParams);2541 2542 if (CompatibleSpace) {2543 auto OverlapAccs = Accs.intersect(AllAccs);2544 bool DoesIntersect = !OverlapAccs.is_empty();2545 HasIntersectingAccs |= DoesIntersect;2546 }2547 }2548 return HasIntersectingAccs;2549}2550 2551/// Test if the accesses of @p LoadMA and @p StoreMA can form a reduction2552bool checkCandidatePairAccesses(MemoryAccess *LoadMA, MemoryAccess *StoreMA,2553 isl::set Domain,2554 SmallVector<MemoryAccess *, 8> &MemAccs) {2555 // First check if the base value is the same.2556 isl::map LoadAccs = LoadMA->getAccessRelation();2557 isl::map StoreAccs = StoreMA->getAccessRelation();2558 bool Valid = LoadAccs.has_equal_space(StoreAccs);2559 POLLY_DEBUG(dbgs() << " == The accessed space below is "2560 << (Valid ? "" : "not ") << "equal!\n");2561 POLLY_DEBUG(LoadMA->dump(); StoreMA->dump());2562 2563 if (Valid) {2564 // Then check if they actually access the same memory.2565 isl::map R = isl::manage(LoadAccs.copy())2566 .intersect_domain(isl::manage(Domain.copy()));2567 isl::map W = isl::manage(StoreAccs.copy())2568 .intersect_domain(isl::manage(Domain.copy()));2569 isl::set RS = R.range();2570 isl::set WS = W.range();2571 2572 isl::set InterAccs =2573 isl::manage(RS.copy()).intersect(isl::manage(WS.copy()));2574 Valid = !InterAccs.is_empty();2575 POLLY_DEBUG(dbgs() << " == The accessed memory is " << (Valid ? "" : "not ")2576 << "overlapping!\n");2577 }2578 2579 if (Valid) {2580 // Finally, check if they are no other instructions accessing this memory2581 isl::map AllAccsRel = LoadAccs.unite(StoreAccs);2582 AllAccsRel = AllAccsRel.intersect_domain(Domain);2583 isl::set AllAccs = AllAccsRel.range();2584 Valid = !hasIntersectingAccesses(AllAccs, LoadMA, StoreMA, Domain, MemAccs);2585 POLLY_DEBUG(dbgs() << " == The accessed memory is " << (Valid ? "not " : "")2586 << "accessed by other instructions!\n");2587 }2588 2589 return Valid;2590}2591 2592void ScopBuilder::checkForReductions(ScopStmt &Stmt) {2593 // Perform a data flow analysis on the current scop statement to propagate the2594 // uses of loaded values. Then check and mark the memory accesses which are2595 // part of reduction like chains.2596 // During the data flow analysis we use the State variable to keep track of2597 // the used "load-instructions" for each instruction in the scop statement.2598 // This includes the LLVM-IR of the load and the "number of uses" (or the2599 // number of paths in the operand tree which end in this load).2600 using StatePairTy = std::pair<unsigned, MemoryAccess::ReductionType>;2601 using FlowInSetTy = MapVector<const LoadInst *, StatePairTy>;2602 using StateTy = MapVector<const Instruction *, FlowInSetTy>;2603 StateTy State;2604 2605 // Invalid loads are loads which have uses we can't track properly in the2606 // state map. This includes loads which:2607 // o do not form a reduction when they flow into a memory location:2608 // (e.g., A[i] = B[i] * 3 and A[i] = A[i] * A[i] + A[i])2609 // o are used by a non binary operator or one which is not commutative2610 // and associative (e.g., A[i] = A[i] % 3)2611 // o might change the control flow (e.g., if (A[i]))2612 // o are used in indirect memory accesses (e.g., A[B[i]])2613 // o are used outside the current scop statement2614 SmallPtrSet<const Instruction *, 8> InvalidLoads;2615 SmallVector<BasicBlock *, 8> ScopBlocks;2616 BasicBlock *BB = Stmt.getBasicBlock();2617 if (BB)2618 ScopBlocks.push_back(BB);2619 else2620 for (BasicBlock *Block : Stmt.getRegion()->blocks())2621 ScopBlocks.push_back(Block);2622 // Run the data flow analysis for all values in the scop statement2623 for (BasicBlock *Block : ScopBlocks) {2624 for (Instruction &Inst : *Block) {2625 if ((Stmt.getParent())->getStmtFor(&Inst) != &Stmt)2626 continue;2627 bool UsedOutsideStmt = any_of(Inst.users(), [&Stmt](User *U) {2628 return (Stmt.getParent())->getStmtFor(cast<Instruction>(U)) != &Stmt;2629 });2630 // Treat loads and stores special2631 if (auto *Load = dyn_cast<LoadInst>(&Inst)) {2632 // Invalidate all loads used which feed into the address of this load.2633 if (auto *Ptr = dyn_cast<Instruction>(Load->getPointerOperand())) {2634 const auto &It = State.find(Ptr);2635 if (It != State.end())2636 InvalidLoads.insert_range(llvm::make_first_range(It->second));2637 }2638 2639 // If this load is used outside this stmt, invalidate it.2640 if (UsedOutsideStmt)2641 InvalidLoads.insert(Load);2642 2643 // And indicate that this load uses itself once but without specifying2644 // any reduction operator.2645 State[Load].insert(2646 std::make_pair(Load, std::make_pair(1, MemoryAccess::RT_BOTTOM)));2647 continue;2648 }2649 2650 if (auto *Store = dyn_cast<StoreInst>(&Inst)) {2651 // Invalidate all loads which feed into the address of this store.2652 if (const Instruction *Ptr =2653 dyn_cast<Instruction>(Store->getPointerOperand())) {2654 const auto &It = State.find(Ptr);2655 if (It != State.end())2656 InvalidLoads.insert_range(llvm::make_first_range(It->second));2657 }2658 2659 // Propagate the uses of the value operand to the store2660 if (auto *ValueInst = dyn_cast<Instruction>(Store->getValueOperand()))2661 State.insert(std::make_pair(Store, State[ValueInst]));2662 continue;2663 }2664 2665 // Non load and store instructions are either binary operators or they2666 // will invalidate all used loads.2667 auto *BinOp = dyn_cast<BinaryOperator>(&Inst);2668 MemoryAccess::ReductionType CurRedType = getReductionType(BinOp);2669 POLLY_DEBUG(dbgs() << "CurInst: " << Inst << " RT: " << CurRedType2670 << "\n");2671 2672 // Iterate over all operands and propagate their input loads to2673 // instruction.2674 FlowInSetTy &InstInFlowSet = State[&Inst];2675 for (Use &Op : Inst.operands()) {2676 auto *OpInst = dyn_cast<Instruction>(Op);2677 if (!OpInst)2678 continue;2679 2680 POLLY_DEBUG(dbgs().indent(4) << "Op Inst: " << *OpInst << "\n");2681 const StateTy::iterator &OpInFlowSetIt = State.find(OpInst);2682 if (OpInFlowSetIt == State.end())2683 continue;2684 2685 // Iterate over all the input loads of the operand and combine them2686 // with the input loads of current instruction.2687 FlowInSetTy &OpInFlowSet = OpInFlowSetIt->second;2688 for (auto &OpInFlowPair : OpInFlowSet) {2689 unsigned OpFlowIn = OpInFlowPair.second.first;2690 unsigned InstFlowIn = InstInFlowSet[OpInFlowPair.first].first;2691 2692 MemoryAccess::ReductionType OpRedType = OpInFlowPair.second.second;2693 MemoryAccess::ReductionType InstRedType =2694 InstInFlowSet[OpInFlowPair.first].second;2695 2696 MemoryAccess::ReductionType NewRedType =2697 combineReductionType(OpRedType, CurRedType);2698 if (InstFlowIn)2699 NewRedType = combineReductionType(NewRedType, InstRedType);2700 2701 POLLY_DEBUG(dbgs().indent(8) << "OpRedType: " << OpRedType << "\n");2702 POLLY_DEBUG(dbgs().indent(8) << "NewRedType: " << NewRedType << "\n");2703 InstInFlowSet[OpInFlowPair.first] =2704 std::make_pair(OpFlowIn + InstFlowIn, NewRedType);2705 }2706 }2707 2708 // If this operation is used outside the stmt, invalidate all the loads2709 // which feed into it.2710 if (UsedOutsideStmt)2711 InvalidLoads.insert_range(llvm::make_first_range(InstInFlowSet));2712 }2713 }2714 2715 // All used loads are propagated through the whole basic block; now try to2716 // find valid reduction-like candidate pairs. These load-store pairs fulfill2717 // all reduction like properties with regards to only this load-store chain.2718 // We later have to check if the loaded value was invalidated by an2719 // instruction not in that chain.2720 using MemAccPair = std::pair<MemoryAccess *, MemoryAccess *>;2721 DenseMap<MemAccPair, MemoryAccess::ReductionType> ValidCandidates;2722 2723 // Iterate over all write memory accesses and check the loads flowing into2724 // it for reduction candidate pairs.2725 for (MemoryAccess *WriteMA : Stmt.MemAccs) {2726 if (WriteMA->isRead())2727 continue;2728 StoreInst *St = dyn_cast<StoreInst>(WriteMA->getAccessInstruction());2729 if (!St)2730 continue;2731 assert(!St->isVolatile());2732 2733 FlowInSetTy &MaInFlowSet = State[WriteMA->getAccessInstruction()];2734 for (auto &MaInFlowSetElem : MaInFlowSet) {2735 MemoryAccess *ReadMA = &Stmt.getArrayAccessFor(MaInFlowSetElem.first);2736 assert(ReadMA && "Couldn't find memory access for incoming load!");2737 2738 POLLY_DEBUG(dbgs() << "'" << *ReadMA->getAccessInstruction()2739 << "'\n\tflows into\n'"2740 << *WriteMA->getAccessInstruction() << "'\n\t #"2741 << MaInFlowSetElem.second.first << " times & RT: "2742 << MaInFlowSetElem.second.second << "\n");2743 2744 MemoryAccess::ReductionType RT = MaInFlowSetElem.second.second;2745 unsigned NumAllowableInFlow = 1;2746 2747 // We allow the load to flow in exactly once for binary reductions2748 bool Valid = (MaInFlowSetElem.second.first == NumAllowableInFlow);2749 2750 // Check if we saw a valid chain of binary operators.2751 Valid = Valid && RT != MemoryAccess::RT_BOTTOM;2752 Valid = Valid && RT != MemoryAccess::RT_NONE;2753 2754 // Then check if the memory accesses allow a reduction.2755 Valid = Valid && checkCandidatePairAccesses(2756 ReadMA, WriteMA, Stmt.getDomain(), Stmt.MemAccs);2757 2758 // Finally, mark the pair as a candidate or the load as a invalid one.2759 if (Valid)2760 ValidCandidates[std::make_pair(ReadMA, WriteMA)] = RT;2761 else2762 InvalidLoads.insert(ReadMA->getAccessInstruction());2763 }2764 }2765 2766 // In the last step mark the memory accesses of candidate pairs as reduction2767 // like if the load wasn't marked invalid in the previous step.2768 for (auto &CandidatePair : ValidCandidates) {2769 MemoryAccess *LoadMA = CandidatePair.first.first;2770 if (InvalidLoads.count(LoadMA->getAccessInstruction()))2771 continue;2772 POLLY_DEBUG(2773 dbgs() << " Load :: "2774 << *((CandidatePair.first.first)->getAccessInstruction())2775 << "\n Store :: "2776 << *((CandidatePair.first.second)->getAccessInstruction())2777 << "\n are marked as reduction like\n");2778 MemoryAccess::ReductionType RT = CandidatePair.second;2779 CandidatePair.first.first->markAsReductionLike(RT);2780 CandidatePair.first.second->markAsReductionLike(RT);2781 }2782}2783 2784void ScopBuilder::verifyInvariantLoads() {2785 auto &RIL = scop->getRequiredInvariantLoads();2786 for (LoadInst *LI : RIL) {2787 assert(LI && scop->contains(LI));2788 // If there exists a statement in the scop which has a memory access for2789 // @p LI, then mark this scop as infeasible for optimization.2790 for (ScopStmt &Stmt : *scop)2791 if (Stmt.getArrayAccessOrNULLFor(LI)) {2792 scop->invalidate(INVARIANTLOAD, LI->getDebugLoc(), LI->getParent());2793 return;2794 }2795 }2796}2797 2798void ScopBuilder::hoistInvariantLoads() {2799 if (!PollyInvariantLoadHoisting)2800 return;2801 2802 isl::union_map Writes = scop->getWrites();2803 for (ScopStmt &Stmt : *scop) {2804 InvariantAccessesTy InvariantAccesses;2805 2806 for (MemoryAccess *Access : Stmt) {2807 isl::set NHCtx = getNonHoistableCtx(Access, Writes);2808 if (!NHCtx.is_null())2809 InvariantAccesses.push_back({Access, NHCtx});2810 }2811 2812 // Transfer the memory access from the statement to the SCoP.2813 for (auto InvMA : InvariantAccesses)2814 Stmt.removeMemoryAccess(InvMA.MA);2815 addInvariantLoads(Stmt, InvariantAccesses);2816 }2817}2818 2819/// Check if an access range is too complex.2820///2821/// An access range is too complex, if it contains either many disjuncts or2822/// very complex expressions. As a simple heuristic, we assume if a set to2823/// be too complex if the sum of existentially quantified dimensions and2824/// set dimensions is larger than a threshold. This reliably detects both2825/// sets with many disjuncts as well as sets with many divisions as they2826/// arise in h264.2827///2828/// @param AccessRange The range to check for complexity.2829///2830/// @returns True if the access range is too complex.2831static bool isAccessRangeTooComplex(isl::set AccessRange) {2832 unsigned NumTotalDims = 0;2833 2834 for (isl::basic_set BSet : AccessRange.get_basic_set_list()) {2835 NumTotalDims += unsignedFromIslSize(BSet.dim(isl::dim::div));2836 NumTotalDims += unsignedFromIslSize(BSet.dim(isl::dim::set));2837 }2838 2839 if (NumTotalDims > MaxDimensionsInAccessRange)2840 return true;2841 2842 return false;2843}2844 2845bool ScopBuilder::hasNonHoistableBasePtrInScop(MemoryAccess *MA,2846 isl::union_map Writes) {2847 if (auto *BasePtrMA = scop->lookupBasePtrAccess(MA)) {2848 return getNonHoistableCtx(BasePtrMA, Writes).is_null();2849 }2850 2851 Value *BaseAddr = MA->getOriginalBaseAddr();2852 if (auto *BasePtrInst = dyn_cast<Instruction>(BaseAddr))2853 if (!isa<LoadInst>(BasePtrInst))2854 return scop->contains(BasePtrInst);2855 2856 return false;2857}2858 2859void ScopBuilder::addUserContext() {2860 if (UserContextStr.empty())2861 return;2862 2863 isl::set UserContext = isl::set(scop->getIslCtx(), UserContextStr.c_str());2864 isl::space Space = scop->getParamSpace();2865 isl::size SpaceParams = Space.dim(isl::dim::param);2866 if (unsignedFromIslSize(SpaceParams) !=2867 unsignedFromIslSize(UserContext.dim(isl::dim::param))) {2868 std::string SpaceStr = stringFromIslObj(Space, "null");2869 errs() << "Error: the context provided in -polly-context has not the same "2870 << "number of dimensions than the computed context. Due to this "2871 << "mismatch, the -polly-context option is ignored. Please provide "2872 << "the context in the parameter space: " << SpaceStr << ".\n";2873 return;2874 }2875 2876 for (auto i : rangeIslSize(0, SpaceParams)) {2877 std::string NameContext =2878 scop->getContext().get_dim_name(isl::dim::param, i);2879 std::string NameUserContext = UserContext.get_dim_name(isl::dim::param, i);2880 2881 if (NameContext != NameUserContext) {2882 std::string SpaceStr = stringFromIslObj(Space, "null");2883 errs() << "Error: the name of dimension " << i2884 << " provided in -polly-context "2885 << "is '" << NameUserContext << "', but the name in the computed "2886 << "context is '" << NameContext2887 << "'. Due to this name mismatch, "2888 << "the -polly-context option is ignored. Please provide "2889 << "the context in the parameter space: " << SpaceStr << ".\n";2890 return;2891 }2892 2893 UserContext = UserContext.set_dim_id(isl::dim::param, i,2894 Space.get_dim_id(isl::dim::param, i));2895 }2896 isl::set newContext = scop->getContext().intersect(UserContext);2897 scop->setContext(newContext);2898}2899 2900isl::set ScopBuilder::getNonHoistableCtx(MemoryAccess *Access,2901 isl::union_map Writes) {2902 // TODO: Loads that are not loop carried, hence are in a statement with2903 // zero iterators, are by construction invariant, though we2904 // currently "hoist" them anyway. This is necessary because we allow2905 // them to be treated as parameters (e.g., in conditions) and our code2906 // generation would otherwise use the old value.2907 2908 auto &Stmt = *Access->getStatement();2909 BasicBlock *BB = Stmt.getEntryBlock();2910 2911 if (Access->isScalarKind() || Access->isWrite() || !Access->isAffine() ||2912 Access->isMemoryIntrinsic())2913 return {};2914 2915 // Skip accesses that have an invariant base pointer which is defined but2916 // not loaded inside the SCoP. This can happened e.g., if a readnone call2917 // returns a pointer that is used as a base address. However, as we want2918 // to hoist indirect pointers, we allow the base pointer to be defined in2919 // the region if it is also a memory access. Each ScopArrayInfo object2920 // that has a base pointer origin has a base pointer that is loaded and2921 // that it is invariant, thus it will be hoisted too. However, if there is2922 // no base pointer origin we check that the base pointer is defined2923 // outside the region.2924 auto *LI = cast<LoadInst>(Access->getAccessInstruction());2925 if (hasNonHoistableBasePtrInScop(Access, Writes))2926 return {};2927 2928 isl::map AccessRelation = Access->getAccessRelation();2929 assert(!AccessRelation.is_empty());2930 2931 if (AccessRelation.involves_dims(isl::dim::in, 0, Stmt.getNumIterators()))2932 return {};2933 2934 AccessRelation = AccessRelation.intersect_domain(Stmt.getDomain());2935 isl::set SafeToLoad;2936 2937 auto &DL = scop->getFunction().getDataLayout();2938 if (isSafeToLoadUnconditionally(LI->getPointerOperand(), LI->getType(),2939 LI->getAlign(), DL, nullptr)) {2940 SafeToLoad = isl::set::universe(AccessRelation.get_space().range());2941 } else if (BB != LI->getParent()) {2942 // Skip accesses in non-affine subregions as they might not be executed2943 // under the same condition as the entry of the non-affine subregion.2944 return {};2945 } else {2946 SafeToLoad = AccessRelation.range();2947 }2948 2949 if (isAccessRangeTooComplex(AccessRelation.range()))2950 return {};2951 2952 isl::union_map Written = Writes.intersect_range(SafeToLoad);2953 isl::set WrittenCtx = Written.params();2954 bool IsWritten = !WrittenCtx.is_empty();2955 2956 if (!IsWritten)2957 return WrittenCtx;2958 2959 WrittenCtx = WrittenCtx.remove_divs();2960 bool TooComplex =2961 unsignedFromIslSize(WrittenCtx.n_basic_set()) >= MaxDisjunctsInDomain;2962 if (TooComplex || !isRequiredInvariantLoad(LI))2963 return {};2964 2965 scop->addAssumption(INVARIANTLOAD, WrittenCtx, LI->getDebugLoc(),2966 AS_RESTRICTION, LI->getParent());2967 return WrittenCtx;2968}2969 2970static bool isAParameter(llvm::Value *maybeParam, const Function &F) {2971 for (const llvm::Argument &Arg : F.args())2972 if (&Arg == maybeParam)2973 return true;2974 2975 return false;2976}2977 2978bool ScopBuilder::canAlwaysBeHoisted(MemoryAccess *MA,2979 bool StmtInvalidCtxIsEmpty,2980 bool MAInvalidCtxIsEmpty,2981 bool NonHoistableCtxIsEmpty) {2982 LoadInst *LInst = cast<LoadInst>(MA->getAccessInstruction());2983 const DataLayout &DL = LInst->getDataLayout();2984 if (PollyAllowDereferenceOfAllFunctionParams &&2985 isAParameter(LInst->getPointerOperand(), scop->getFunction()))2986 return true;2987 2988 // TODO: We can provide more information for better but more expensive2989 // results.2990 if (!isDereferenceableAndAlignedPointer(2991 LInst->getPointerOperand(), LInst->getType(), LInst->getAlign(), DL))2992 return false;2993 2994 // If the location might be overwritten we do not hoist it unconditionally.2995 //2996 // TODO: This is probably too conservative.2997 if (!NonHoistableCtxIsEmpty)2998 return false;2999 3000 // If a dereferenceable load is in a statement that is modeled precisely we3001 // can hoist it.3002 if (StmtInvalidCtxIsEmpty && MAInvalidCtxIsEmpty)3003 return true;3004 3005 // Even if the statement is not modeled precisely we can hoist the load if it3006 // does not involve any parameters that might have been specialized by the3007 // statement domain.3008 for (const SCEV *Subscript : MA->subscripts())3009 if (!isa<SCEVConstant>(Subscript))3010 return false;3011 return true;3012}3013 3014void ScopBuilder::addInvariantLoads(ScopStmt &Stmt,3015 InvariantAccessesTy &InvMAs) {3016 if (InvMAs.empty())3017 return;3018 3019 isl::set StmtInvalidCtx = Stmt.getInvalidContext();3020 bool StmtInvalidCtxIsEmpty = StmtInvalidCtx.is_empty();3021 3022 // Get the context under which the statement is executed but remove the error3023 // context under which this statement is reached.3024 isl::set DomainCtx = Stmt.getDomain().params();3025 DomainCtx = DomainCtx.subtract(StmtInvalidCtx);3026 3027 if (unsignedFromIslSize(DomainCtx.n_basic_set()) >= MaxDisjunctsInDomain) {3028 auto *AccInst = InvMAs.front().MA->getAccessInstruction();3029 scop->invalidate(COMPLEXITY, AccInst->getDebugLoc(), AccInst->getParent());3030 return;3031 }3032 3033 // Project out all parameters that relate to loads in the statement. Otherwise3034 // we could have cyclic dependences on the constraints under which the3035 // hoisted loads are executed and we could not determine an order in which to3036 // pre-load them. This happens because not only lower bounds are part of the3037 // domain but also upper bounds.3038 for (auto &InvMA : InvMAs) {3039 auto *MA = InvMA.MA;3040 Instruction *AccInst = MA->getAccessInstruction();3041 if (SE.isSCEVable(AccInst->getType())) {3042 SetVector<Value *> Values;3043 for (const SCEV *Parameter : scop->parameters()) {3044 Values.clear();3045 findValues(Parameter, SE, Values);3046 if (!Values.count(AccInst))3047 continue;3048 3049 isl::id ParamId = scop->getIdForParam(Parameter);3050 if (!ParamId.is_null()) {3051 int Dim = DomainCtx.find_dim_by_id(isl::dim::param, ParamId);3052 if (Dim >= 0)3053 DomainCtx = DomainCtx.eliminate(isl::dim::param, Dim, 1);3054 }3055 }3056 }3057 }3058 3059 for (auto &InvMA : InvMAs) {3060 auto *MA = InvMA.MA;3061 isl::set NHCtx = InvMA.NonHoistableCtx;3062 3063 // Check for another invariant access that accesses the same location as3064 // MA and if found consolidate them. Otherwise create a new equivalence3065 // class at the end of InvariantEquivClasses.3066 LoadInst *LInst = cast<LoadInst>(MA->getAccessInstruction());3067 Type *Ty = LInst->getType();3068 const SCEV *PointerSCEV = SE.getSCEV(LInst->getPointerOperand());3069 3070 isl::set MAInvalidCtx = MA->getInvalidContext();3071 bool NonHoistableCtxIsEmpty = NHCtx.is_empty();3072 bool MAInvalidCtxIsEmpty = MAInvalidCtx.is_empty();3073 3074 isl::set MACtx;3075 // Check if we know that this pointer can be speculatively accessed.3076 if (canAlwaysBeHoisted(MA, StmtInvalidCtxIsEmpty, MAInvalidCtxIsEmpty,3077 NonHoistableCtxIsEmpty)) {3078 MACtx = isl::set::universe(DomainCtx.get_space());3079 } else {3080 MACtx = DomainCtx;3081 MACtx = MACtx.subtract(MAInvalidCtx.unite(NHCtx));3082 MACtx = MACtx.gist_params(scop->getContext());3083 }3084 3085 bool Consolidated = false;3086 for (auto &IAClass : scop->invariantEquivClasses()) {3087 if (PointerSCEV != IAClass.IdentifyingPointer || Ty != IAClass.AccessType)3088 continue;3089 3090 // If the pointer and the type is equal check if the access function wrt.3091 // to the domain is equal too. It can happen that the domain fixes3092 // parameter values and these can be different for distinct part of the3093 // SCoP. If this happens we cannot consolidate the loads but need to3094 // create a new invariant load equivalence class.3095 auto &MAs = IAClass.InvariantAccesses;3096 if (!MAs.empty()) {3097 auto *LastMA = MAs.front();3098 3099 isl::set AR = MA->getAccessRelation().range();3100 isl::set LastAR = LastMA->getAccessRelation().range();3101 bool SameAR = AR.is_equal(LastAR);3102 3103 if (!SameAR)3104 continue;3105 }3106 3107 // Add MA to the list of accesses that are in this class.3108 MAs.push_front(MA);3109 3110 Consolidated = true;3111 3112 // Unify the execution context of the class and this statement.3113 isl::set IAClassDomainCtx = IAClass.ExecutionContext;3114 if (!IAClassDomainCtx.is_null())3115 IAClassDomainCtx = IAClassDomainCtx.unite(MACtx).coalesce();3116 else3117 IAClassDomainCtx = MACtx;3118 IAClass.ExecutionContext = IAClassDomainCtx;3119 break;3120 }3121 3122 if (Consolidated)3123 continue;3124 3125 MACtx = MACtx.coalesce();3126 3127 // If we did not consolidate MA, thus did not find an equivalence class3128 // for it, we create a new one.3129 scop->addInvariantEquivClass(3130 InvariantEquivClassTy{PointerSCEV, MemoryAccessList{MA}, MACtx, Ty});3131 }3132}3133 3134/// Find the canonical scop array info object for a set of invariant load3135/// hoisted loads. The canonical array is the one that corresponds to the3136/// first load in the list of accesses which is used as base pointer of a3137/// scop array.3138static const ScopArrayInfo *findCanonicalArray(Scop &S,3139 MemoryAccessList &Accesses) {3140 for (MemoryAccess *Access : Accesses) {3141 const ScopArrayInfo *CanonicalArray = S.getScopArrayInfoOrNull(3142 Access->getAccessInstruction(), MemoryKind::Array);3143 if (CanonicalArray)3144 return CanonicalArray;3145 }3146 return nullptr;3147}3148 3149/// Check if @p Array severs as base array in an invariant load.3150static bool isUsedForIndirectHoistedLoad(Scop &S, const ScopArrayInfo *Array) {3151 for (InvariantEquivClassTy &EqClass2 : S.getInvariantAccesses())3152 for (MemoryAccess *Access2 : EqClass2.InvariantAccesses)3153 if (Access2->getScopArrayInfo() == Array)3154 return true;3155 return false;3156}3157 3158/// Replace the base pointer arrays in all memory accesses referencing @p Old,3159/// with a reference to @p New.3160static void replaceBasePtrArrays(Scop &S, const ScopArrayInfo *Old,3161 const ScopArrayInfo *New) {3162 for (ScopStmt &Stmt : S)3163 for (MemoryAccess *Access : Stmt) {3164 if (Access->getLatestScopArrayInfo() != Old)3165 continue;3166 3167 isl::id Id = New->getBasePtrId();3168 isl::map Map = Access->getAccessRelation();3169 Map = Map.set_tuple_id(isl::dim::out, Id);3170 Access->setAccessRelation(Map);3171 }3172}3173 3174void ScopBuilder::canonicalizeDynamicBasePtrs() {3175 for (InvariantEquivClassTy &EqClass : scop->InvariantEquivClasses) {3176 MemoryAccessList &BasePtrAccesses = EqClass.InvariantAccesses;3177 3178 const ScopArrayInfo *CanonicalBasePtrSAI =3179 findCanonicalArray(*scop, BasePtrAccesses);3180 3181 if (!CanonicalBasePtrSAI)3182 continue;3183 3184 for (MemoryAccess *BasePtrAccess : BasePtrAccesses) {3185 const ScopArrayInfo *BasePtrSAI = scop->getScopArrayInfoOrNull(3186 BasePtrAccess->getAccessInstruction(), MemoryKind::Array);3187 if (!BasePtrSAI || BasePtrSAI == CanonicalBasePtrSAI ||3188 !BasePtrSAI->isCompatibleWith(CanonicalBasePtrSAI))3189 continue;3190 3191 // we currently do not canonicalize arrays where some accesses are3192 // hoisted as invariant loads. If we would, we need to update the access3193 // function of the invariant loads as well. However, as this is not a3194 // very common situation, we leave this for now to avoid further3195 // complexity increases.3196 if (isUsedForIndirectHoistedLoad(*scop, BasePtrSAI))3197 continue;3198 3199 replaceBasePtrArrays(*scop, BasePtrSAI, CanonicalBasePtrSAI);3200 }3201 }3202}3203 3204void ScopBuilder::buildAccessRelations(ScopStmt &Stmt) {3205 for (MemoryAccess *Access : Stmt.MemAccs) {3206 Type *ElementType = Access->getElementType();3207 3208 MemoryKind Ty;3209 if (Access->isPHIKind())3210 Ty = MemoryKind::PHI;3211 else if (Access->isExitPHIKind())3212 Ty = MemoryKind::ExitPHI;3213 else if (Access->isValueKind())3214 Ty = MemoryKind::Value;3215 else3216 Ty = MemoryKind::Array;3217 3218 // Create isl::pw_aff for SCEVs which describe sizes. Collect all3219 // assumptions which are taken. isl::pw_aff objects are cached internally3220 // and they are used later by scop.3221 for (const SCEV *Size : Access->Sizes) {3222 if (!Size)3223 continue;3224 scop->getPwAff(Size, nullptr, false, &RecordedAssumptions);3225 }3226 auto *SAI = scop->getOrCreateScopArrayInfo(Access->getOriginalBaseAddr(),3227 ElementType, Access->Sizes, Ty);3228 3229 // Create isl::pw_aff for SCEVs which describe subscripts. Collect all3230 // assumptions which are taken. isl::pw_aff objects are cached internally3231 // and they are used later by scop.3232 for (const SCEV *Subscript : Access->subscripts()) {3233 if (!Access->isAffine() || !Subscript)3234 continue;3235 scop->getPwAff(Subscript, Stmt.getEntryBlock(), false,3236 &RecordedAssumptions);3237 }3238 Access->buildAccessRelation(SAI);3239 scop->addAccessData(Access);3240 }3241}3242 3243/// Add the minimal/maximal access in @p Set to @p User.3244///3245/// @return True if more accesses should be added, false if we reached the3246/// maximal number of run-time checks to be generated.3247static bool buildMinMaxAccess(isl::set Set,3248 Scop::MinMaxVectorTy &MinMaxAccesses, Scop &S) {3249 isl::pw_multi_aff MinPMA, MaxPMA;3250 isl::pw_aff LastDimAff;3251 isl::aff OneAff;3252 unsigned Pos;3253 3254 Set = Set.remove_divs();3255 polly::simplify(Set);3256 3257 if (unsignedFromIslSize(Set.n_basic_set()) > RunTimeChecksMaxAccessDisjuncts)3258 Set = Set.simple_hull();3259 3260 // Restrict the number of parameters involved in the access as the lexmin/3261 // lexmax computation will take too long if this number is high.3262 //3263 // Experiments with a simple test case using an i7 4800MQ:3264 //3265 // #Parameters involved | Time (in sec)3266 // 6 | 0.013267 // 7 | 0.043268 // 8 | 0.123269 // 9 | 0.403270 // 10 | 1.543271 // 11 | 6.783272 // 12 | 30.383273 //3274 if (isl_set_n_param(Set.get()) >3275 static_cast<isl_size>(RunTimeChecksMaxParameters)) {3276 unsigned InvolvedParams = 0;3277 for (unsigned u = 0, e = isl_set_n_param(Set.get()); u < e; u++)3278 if (Set.involves_dims(isl::dim::param, u, 1))3279 InvolvedParams++;3280 3281 if (InvolvedParams > RunTimeChecksMaxParameters)3282 return false;3283 }3284 3285 MinPMA = Set.lexmin_pw_multi_aff();3286 MaxPMA = Set.lexmax_pw_multi_aff();3287 3288 MinPMA = MinPMA.coalesce();3289 MaxPMA = MaxPMA.coalesce();3290 3291 if (MaxPMA.is_null())3292 return false;3293 3294 unsigned MaxOutputSize = unsignedFromIslSize(MaxPMA.dim(isl::dim::out));3295 3296 // Adjust the last dimension of the maximal access by one as we want to3297 // enclose the accessed memory region by MinPMA and MaxPMA. The pointer3298 // we test during code generation might now point after the end of the3299 // allocated array but we will never dereference it anyway.3300 assert(MaxOutputSize >= 1 && "Assumed at least one output dimension");3301 3302 Pos = MaxOutputSize - 1;3303 LastDimAff = MaxPMA.at(Pos);3304 OneAff = isl::aff(isl::local_space(LastDimAff.get_domain_space()));3305 OneAff = OneAff.add_constant_si(1);3306 LastDimAff = LastDimAff.add(OneAff);3307 MaxPMA = MaxPMA.set_pw_aff(Pos, LastDimAff);3308 3309 if (MinPMA.is_null() || MaxPMA.is_null())3310 return false;3311 3312 MinMaxAccesses.push_back(std::make_pair(MinPMA, MaxPMA));3313 3314 return true;3315}3316 3317/// Wrapper function to calculate minimal/maximal accesses to each array.3318bool ScopBuilder::calculateMinMaxAccess(AliasGroupTy AliasGroup,3319 Scop::MinMaxVectorTy &MinMaxAccesses) {3320 MinMaxAccesses.reserve(AliasGroup.size());3321 3322 isl::union_set Domains = scop->getDomains();3323 isl::union_map Accesses = isl::union_map::empty(scop->getIslCtx());3324 3325 for (MemoryAccess *MA : AliasGroup)3326 Accesses = Accesses.unite(MA->getAccessRelation());3327 3328 Accesses = Accesses.intersect_domain(Domains);3329 isl::union_set Locations = Accesses.range();3330 3331 bool LimitReached = false;3332 for (isl::set Set : Locations.get_set_list()) {3333 LimitReached |= !buildMinMaxAccess(Set, MinMaxAccesses, *scop);3334 if (LimitReached)3335 break;3336 }3337 3338 return !LimitReached;3339}3340 3341static isl::set getAccessDomain(MemoryAccess *MA) {3342 isl::set Domain = MA->getStatement()->getDomain();3343 Domain = Domain.project_out(isl::dim::set, 0,3344 unsignedFromIslSize(Domain.tuple_dim()));3345 return Domain.reset_tuple_id();3346}3347 3348bool ScopBuilder::buildAliasChecks() {3349 if (!PollyUseRuntimeAliasChecks)3350 return true;3351 3352 if (buildAliasGroups()) {3353 // Aliasing assumptions do not go through addAssumption but we still want to3354 // collect statistics so we do it here explicitly.3355 if (scop->getAliasGroups().size())3356 Scop::incrementNumberOfAliasingAssumptions(1);3357 return true;3358 }3359 3360 // If a problem occurs while building the alias groups we need to delete3361 // this SCoP and pretend it wasn't valid in the first place. To this end3362 // we make the assumed context infeasible.3363 scop->invalidate(ALIASING, DebugLoc());3364 3365 POLLY_DEBUG(dbgs() << "\n\nNOTE: Run time checks for " << scop->getNameStr()3366 << " could not be created. This SCoP has been dismissed.");3367 return false;3368}3369 3370std::tuple<ScopBuilder::AliasGroupVectorTy, DenseSet<const ScopArrayInfo *>>3371ScopBuilder::buildAliasGroupsForAccesses() {3372 BatchAAResults BAA(AA);3373 AliasSetTracker AST(BAA);3374 3375 DenseMap<Value *, MemoryAccess *> PtrToAcc;3376 DenseSet<const ScopArrayInfo *> HasWriteAccess;3377 for (ScopStmt &Stmt : *scop) {3378 3379 isl::set StmtDomain = Stmt.getDomain();3380 bool StmtDomainEmpty = StmtDomain.is_empty();3381 3382 // Statements with an empty domain will never be executed.3383 if (StmtDomainEmpty)3384 continue;3385 3386 for (MemoryAccess *MA : Stmt) {3387 if (MA->isScalarKind())3388 continue;3389 if (!MA->isRead())3390 HasWriteAccess.insert(MA->getScopArrayInfo());3391 MemAccInst Acc(MA->getAccessInstruction());3392 if (MA->isRead() && isa<MemTransferInst>(Acc))3393 PtrToAcc[cast<MemTransferInst>(Acc)->getRawSource()] = MA;3394 else3395 PtrToAcc[Acc.getPointerOperand()] = MA;3396 AST.add(Acc);3397 }3398 }3399 3400 AliasGroupVectorTy AliasGroups;3401 for (AliasSet &AS : AST) {3402 if (AS.isMustAlias() || AS.isForwardingAliasSet())3403 continue;3404 AliasGroupTy AG;3405 for (const Value *Ptr : AS.getPointers())3406 AG.push_back(PtrToAcc[const_cast<Value *>(Ptr)]);3407 if (AG.size() < 2)3408 continue;3409 AliasGroups.push_back(std::move(AG));3410 }3411 3412 return std::make_tuple(AliasGroups, HasWriteAccess);3413}3414 3415bool ScopBuilder::buildAliasGroups() {3416 // To create sound alias checks we perform the following steps:3417 // o) We partition each group into read only and non read only accesses.3418 // o) For each group with more than one base pointer we then compute minimal3419 // and maximal accesses to each array of a group in read only and non3420 // read only partitions separately.3421 AliasGroupVectorTy AliasGroups;3422 DenseSet<const ScopArrayInfo *> HasWriteAccess;3423 3424 std::tie(AliasGroups, HasWriteAccess) = buildAliasGroupsForAccesses();3425 3426 splitAliasGroupsByDomain(AliasGroups);3427 3428 for (AliasGroupTy &AG : AliasGroups) {3429 if (!scop->hasFeasibleRuntimeContext())3430 return false;3431 3432 {3433 IslMaxOperationsGuard MaxOpGuard(scop->getIslCtx().get(), OptComputeOut);3434 bool Valid = buildAliasGroup(AG, HasWriteAccess);3435 if (!Valid)3436 return false;3437 }3438 if (isl_ctx_last_error(scop->getIslCtx().get()) == isl_error_quota) {3439 scop->invalidate(COMPLEXITY, DebugLoc());3440 return false;3441 }3442 }3443 3444 return true;3445}3446 3447bool ScopBuilder::buildAliasGroup(3448 AliasGroupTy &AliasGroup, DenseSet<const ScopArrayInfo *> HasWriteAccess) {3449 AliasGroupTy ReadOnlyAccesses;3450 AliasGroupTy ReadWriteAccesses;3451 SmallPtrSet<const ScopArrayInfo *, 4> ReadWriteArrays;3452 SmallPtrSet<const ScopArrayInfo *, 4> ReadOnlyArrays;3453 3454 if (AliasGroup.size() < 2)3455 return true;3456 3457 for (MemoryAccess *Access : AliasGroup) {3458 ORE.emit(OptimizationRemarkAnalysis(DEBUG_TYPE, "PossibleAlias",3459 Access->getAccessInstruction())3460 << "Possibly aliasing pointer, use restrict keyword.");3461 const ScopArrayInfo *Array = Access->getScopArrayInfo();3462 if (HasWriteAccess.count(Array)) {3463 ReadWriteArrays.insert(Array);3464 ReadWriteAccesses.push_back(Access);3465 } else {3466 ReadOnlyArrays.insert(Array);3467 ReadOnlyAccesses.push_back(Access);3468 }3469 }3470 3471 // If there are no read-only pointers, and less than two read-write pointers,3472 // no alias check is needed.3473 if (ReadOnlyAccesses.empty() && ReadWriteArrays.size() <= 1)3474 return true;3475 3476 // If there is no read-write pointer, no alias check is needed.3477 if (ReadWriteArrays.empty())3478 return true;3479 3480 // For non-affine accesses, no alias check can be generated as we cannot3481 // compute a sufficiently tight lower and upper bound: bail out.3482 for (MemoryAccess *MA : AliasGroup) {3483 if (!MA->isAffine()) {3484 scop->invalidate(ALIASING, MA->getAccessInstruction()->getDebugLoc(),3485 MA->getAccessInstruction()->getParent());3486 return false;3487 }3488 }3489 3490 // Ensure that for all memory accesses for which we generate alias checks,3491 // their base pointers are available.3492 for (MemoryAccess *MA : AliasGroup) {3493 if (MemoryAccess *BasePtrMA = scop->lookupBasePtrAccess(MA))3494 scop->addRequiredInvariantLoad(3495 cast<LoadInst>(BasePtrMA->getAccessInstruction()));3496 }3497 3498 // scop->getAliasGroups().emplace_back();3499 // Scop::MinMaxVectorPairTy &pair = scop->getAliasGroups().back();3500 Scop::MinMaxVectorTy MinMaxAccessesReadWrite;3501 Scop::MinMaxVectorTy MinMaxAccessesReadOnly;3502 3503 bool Valid;3504 3505 Valid = calculateMinMaxAccess(ReadWriteAccesses, MinMaxAccessesReadWrite);3506 3507 if (!Valid)3508 return false;3509 3510 // Bail out if the number of values we need to compare is too large.3511 // This is important as the number of comparisons grows quadratically with3512 // the number of values we need to compare.3513 if (MinMaxAccessesReadWrite.size() + ReadOnlyArrays.size() >3514 RunTimeChecksMaxArraysPerGroup)3515 return false;3516 3517 Valid = calculateMinMaxAccess(ReadOnlyAccesses, MinMaxAccessesReadOnly);3518 3519 scop->addAliasGroup(MinMaxAccessesReadWrite, MinMaxAccessesReadOnly);3520 if (!Valid)3521 return false;3522 3523 return true;3524}3525 3526void ScopBuilder::splitAliasGroupsByDomain(AliasGroupVectorTy &AliasGroups) {3527 for (unsigned u = 0; u < AliasGroups.size(); u++) {3528 AliasGroupTy NewAG;3529 AliasGroupTy &AG = AliasGroups[u];3530 AliasGroupTy::iterator AGI = AG.begin();3531 isl::set AGDomain = getAccessDomain(*AGI);3532 while (AGI != AG.end()) {3533 MemoryAccess *MA = *AGI;3534 isl::set MADomain = getAccessDomain(MA);3535 if (AGDomain.is_disjoint(MADomain)) {3536 NewAG.push_back(MA);3537 AGI = AG.erase(AGI);3538 } else {3539 AGDomain = AGDomain.unite(MADomain);3540 AGI++;3541 }3542 }3543 if (NewAG.size() > 1)3544 AliasGroups.push_back(std::move(NewAG));3545 }3546}3547 3548#ifndef NDEBUG3549static void verifyUse(Scop *S, Use &Op, LoopInfo &LI) {3550 auto PhysUse = VirtualUse::create(S, Op, &LI, false);3551 auto VirtUse = VirtualUse::create(S, Op, &LI, true);3552 assert(PhysUse.getKind() == VirtUse.getKind());3553}3554 3555/// Check the consistency of every statement's MemoryAccesses.3556///3557/// The check is carried out by expecting the "physical" kind of use (derived3558/// from the BasicBlocks instructions resides in) to be same as the "virtual"3559/// kind of use (derived from a statement's MemoryAccess).3560///3561/// The "physical" uses are taken by ensureValueRead to determine whether to3562/// create MemoryAccesses. When done, the kind of scalar access should be the3563/// same no matter which way it was derived.3564///3565/// The MemoryAccesses might be changed by later SCoP-modifying passes and hence3566/// can intentionally influence on the kind of uses (not corresponding to the3567/// "physical" anymore, hence called "virtual"). The CodeGenerator therefore has3568/// to pick up the virtual uses. But here in the code generator, this has not3569/// happened yet, such that virtual and physical uses are equivalent.3570static void verifyUses(Scop *S, LoopInfo &LI, DominatorTree &DT) {3571 for (auto *BB : S->getRegion().blocks()) {3572 for (auto &Inst : *BB) {3573 auto *Stmt = S->getStmtFor(&Inst);3574 if (!Stmt)3575 continue;3576 3577 if (isIgnoredIntrinsic(&Inst))3578 continue;3579 3580 // Branch conditions are encoded in the statement domains.3581 if (Inst.isTerminator() && Stmt->isBlockStmt())3582 continue;3583 3584 // Verify all uses.3585 for (auto &Op : Inst.operands())3586 verifyUse(S, Op, LI);3587 3588 // Stores do not produce values used by other statements.3589 if (isa<StoreInst>(Inst))3590 continue;3591 3592 // For every value defined in the block, also check that a use of that3593 // value in the same statement would not be an inter-statement use. It can3594 // still be synthesizable or load-hoisted, but these kind of instructions3595 // are not directly copied in code-generation.3596 auto VirtDef =3597 VirtualUse::create(S, Stmt, Stmt->getSurroundingLoop(), &Inst, true);3598 assert(VirtDef.getKind() == VirtualUse::Synthesizable ||3599 VirtDef.getKind() == VirtualUse::Intra ||3600 VirtDef.getKind() == VirtualUse::Hoisted);3601 }3602 }3603 3604 if (S->hasSingleExitEdge())3605 return;3606 3607 // PHINodes in the SCoP region's exit block are also uses to be checked.3608 if (!S->getRegion().isTopLevelRegion()) {3609 for (auto &Inst : *S->getRegion().getExit()) {3610 if (!isa<PHINode>(Inst))3611 break;3612 3613 for (auto &Op : Inst.operands())3614 verifyUse(S, Op, LI);3615 }3616 }3617}3618#endif3619 3620void ScopBuilder::buildScop(Region &R, AssumptionCache &AC) {3621 scop.reset(new Scop(R, SE, LI, DT, *SD.getDetectionContext(&R), ORE,3622 SD.getNextID()));3623 3624 buildStmts(R);3625 3626 // Create all invariant load instructions first. These are categorized as3627 // 'synthesizable', therefore are not part of any ScopStmt but need to be3628 // created somewhere.3629 const InvariantLoadsSetTy &RIL = scop->getRequiredInvariantLoads();3630 for (BasicBlock *BB : scop->getRegion().blocks()) {3631 if (SD.isErrorBlock(*BB, scop->getRegion()))3632 continue;3633 3634 for (Instruction &Inst : *BB) {3635 LoadInst *Load = dyn_cast<LoadInst>(&Inst);3636 if (!Load)3637 continue;3638 3639 if (!RIL.count(Load))3640 continue;3641 3642 // Invariant loads require a MemoryAccess to be created in some statement.3643 // It is not important to which statement the MemoryAccess is added3644 // because it will later be removed from the ScopStmt again. We chose the3645 // first statement of the basic block the LoadInst is in.3646 ArrayRef<ScopStmt *> List = scop->getStmtListFor(BB);3647 assert(!List.empty());3648 ScopStmt *RILStmt = List.front();3649 buildMemoryAccess(Load, RILStmt);3650 }3651 }3652 buildAccessFunctions();3653 3654 // In case the region does not have an exiting block we will later (during3655 // code generation) split the exit block. This will move potential PHI nodes3656 // from the current exit block into the new region exiting block. Hence, PHI3657 // nodes that are at this point not part of the region will be.3658 // To handle these PHI nodes later we will now model their operands as scalar3659 // accesses. Note that we do not model anything in the exit block if we have3660 // an exiting block in the region, as there will not be any splitting later.3661 if (!R.isTopLevelRegion() && !scop->hasSingleExitEdge()) {3662 for (Instruction &Inst : *R.getExit()) {3663 PHINode *PHI = dyn_cast<PHINode>(&Inst);3664 if (!PHI)3665 break;3666 3667 buildPHIAccesses(nullptr, PHI, nullptr, true);3668 }3669 }3670 3671 // Create memory accesses for global reads since all arrays are now known.3672 const SCEV *AF = SE.getConstant(IntegerType::getInt64Ty(SE.getContext()), 0);3673 for (auto GlobalReadPair : GlobalReads) {3674 ScopStmt *GlobalReadStmt = GlobalReadPair.first;3675 Instruction *GlobalRead = GlobalReadPair.second;3676 for (auto *BP : ArrayBasePointers)3677 addArrayAccess(GlobalReadStmt, MemAccInst(GlobalRead), MemoryAccess::READ,3678 BP, BP->getType(), false, {AF}, {nullptr}, GlobalRead);3679 }3680 3681 buildInvariantEquivalenceClasses();3682 3683 /// A map from basic blocks to their invalid domains.3684 DenseMap<BasicBlock *, isl::set> InvalidDomainMap;3685 3686 if (!buildDomains(&R, InvalidDomainMap)) {3687 POLLY_DEBUG(3688 dbgs() << "Bailing-out because buildDomains encountered problems\n");3689 return;3690 }3691 3692 addUserAssumptions(AC, InvalidDomainMap);3693 3694 // Initialize the invalid domain.3695 for (ScopStmt &Stmt : scop->Stmts)3696 if (Stmt.isBlockStmt())3697 Stmt.setInvalidDomain(InvalidDomainMap[Stmt.getEntryBlock()]);3698 else3699 Stmt.setInvalidDomain(InvalidDomainMap[getRegionNodeBasicBlock(3700 Stmt.getRegion()->getNode())]);3701 3702 // Remove empty statements.3703 // Exit early in case there are no executable statements left in this scop.3704 scop->removeStmtNotInDomainMap();3705 scop->simplifySCoP(false);3706 if (scop->isEmpty()) {3707 POLLY_DEBUG(dbgs() << "Bailing-out because SCoP is empty\n");3708 return;3709 }3710 3711 // The ScopStmts now have enough information to initialize themselves.3712 for (ScopStmt &Stmt : *scop) {3713 collectSurroundingLoops(Stmt);3714 3715 buildDomain(Stmt);3716 buildAccessRelations(Stmt);3717 3718 if (DetectReductions)3719 checkForReductions(Stmt);3720 }3721 3722 // Check early for a feasible runtime context.3723 if (!scop->hasFeasibleRuntimeContext()) {3724 POLLY_DEBUG(3725 dbgs() << "Bailing-out because of unfeasible context (early)\n");3726 return;3727 }3728 3729 // Check early for profitability. Afterwards it cannot change anymore,3730 // only the runtime context could become infeasible.3731 if (!scop->isProfitable(UnprofitableScalarAccs)) {3732 scop->invalidate(PROFITABLE, DebugLoc());3733 POLLY_DEBUG(3734 dbgs() << "Bailing-out because SCoP is not considered profitable\n");3735 return;3736 }3737 3738 buildSchedule();3739 3740 finalizeAccesses();3741 3742 scop->realignParams();3743 addUserContext();3744 3745 // After the context was fully constructed, thus all our knowledge about3746 // the parameters is in there, we add all recorded assumptions to the3747 // assumed/invalid context.3748 addRecordedAssumptions();3749 3750 scop->simplifyContexts();3751 if (!buildAliasChecks()) {3752 POLLY_DEBUG(dbgs() << "Bailing-out because could not build alias checks\n");3753 return;3754 }3755 3756 hoistInvariantLoads();3757 canonicalizeDynamicBasePtrs();3758 verifyInvariantLoads();3759 scop->simplifySCoP(true);3760 3761 // Check late for a feasible runtime context because profitability did not3762 // change.3763 if (!scop->hasFeasibleRuntimeContext()) {3764 POLLY_DEBUG(dbgs() << "Bailing-out because of unfeasible context (late)\n");3765 return;3766 }3767 3768#ifndef NDEBUG3769 verifyUses(scop.get(), LI, DT);3770#endif3771}3772 3773ScopBuilder::ScopBuilder(Region *R, AssumptionCache &AC, AAResults &AA,3774 const DataLayout &DL, DominatorTree &DT, LoopInfo &LI,3775 ScopDetection &SD, ScalarEvolution &SE,3776 OptimizationRemarkEmitter &ORE)3777 : AA(AA), DL(DL), DT(DT), LI(LI), SD(SD), SE(SE), ORE(ORE) {3778 DebugLoc Beg, End;3779 auto P = getBBPairForRegion(R);3780 getDebugLocations(P, Beg, End);3781 3782 std::string Msg = "SCoP begins here.";3783 ORE.emit(OptimizationRemarkAnalysis(DEBUG_TYPE, "ScopEntry", Beg, P.first)3784 << Msg);3785 3786 buildScop(*R, AC);3787 3788 POLLY_DEBUG(dbgs() << *scop);3789 3790 if (!scop->hasFeasibleRuntimeContext()) {3791 InfeasibleScops++;3792 Msg = "SCoP ends here but was dismissed.";3793 POLLY_DEBUG(dbgs() << "SCoP detected but dismissed\n");3794 RecordedAssumptions.clear();3795 scop.reset();3796 } else {3797 Msg = "SCoP ends here.";3798 ++ScopFound;3799 if (scop->getMaxLoopDepth() > 0)3800 ++RichScopFound;3801 }3802 3803 if (R->isTopLevelRegion())3804 ORE.emit(OptimizationRemarkAnalysis(DEBUG_TYPE, "ScopEnd", End, P.first)3805 << Msg);3806 else3807 ORE.emit(OptimizationRemarkAnalysis(DEBUG_TYPE, "ScopEnd", End, P.second)3808 << Msg);3809}3810