//===- ScopBuilder.cpp ----------------------------------------------------===// // // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. // See https://llvm.org/LICENSE.txt for license information. // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception // //===----------------------------------------------------------------------===// // // Create a polyhedral description for a static control flow region. // // The pass creates a polyhedral description of the Scops detected by the SCoP // detection derived from their LLVM-IR code. // //===----------------------------------------------------------------------===// #include "polly/ScopBuilder.h" #include "polly/Options.h" #include "polly/ScopDetection.h" #include "polly/ScopInfo.h" #include "polly/Support/GICHelper.h" #include "polly/Support/ISLTools.h" #include "polly/Support/SCEVValidator.h" #include "polly/Support/ScopHelper.h" #include "polly/Support/VirtualInstruction.h" #include "llvm/ADT/ArrayRef.h" #include "llvm/ADT/EquivalenceClasses.h" #include "llvm/ADT/PostOrderIterator.h" #include "llvm/ADT/Sequence.h" #include "llvm/ADT/SmallSet.h" #include "llvm/ADT/Statistic.h" #include "llvm/Analysis/AliasAnalysis.h" #include "llvm/Analysis/AssumptionCache.h" #include "llvm/Analysis/Delinearization.h" #include "llvm/Analysis/Loads.h" #include "llvm/Analysis/LoopInfo.h" #include "llvm/Analysis/OptimizationRemarkEmitter.h" #include "llvm/Analysis/RegionInfo.h" #include "llvm/Analysis/RegionIterator.h" #include "llvm/Analysis/ScalarEvolution.h" #include "llvm/Analysis/ScalarEvolutionExpressions.h" #include "llvm/IR/BasicBlock.h" #include "llvm/IR/DataLayout.h" #include "llvm/IR/DebugLoc.h" #include "llvm/IR/DerivedTypes.h" #include "llvm/IR/Dominators.h" #include "llvm/IR/Function.h" #include "llvm/IR/InstrTypes.h" #include "llvm/IR/Instruction.h" #include "llvm/IR/Instructions.h" #include "llvm/IR/Type.h" #include "llvm/IR/Use.h" #include "llvm/IR/Value.h" #include "llvm/Support/CommandLine.h" #include "llvm/Support/Compiler.h" #include "llvm/Support/Debug.h" #include "llvm/Support/ErrorHandling.h" #include "llvm/Support/raw_ostream.h" #include <cassert> usingnamespacellvm; usingnamespacepolly; #include "polly/Support/PollyDebug.h" #define DEBUG_TYPE … STATISTIC(ScopFound, "Number of valid Scops"); STATISTIC(RichScopFound, "Number of Scops containing a loop"); STATISTIC(InfeasibleScops, "Number of SCoPs with statically infeasible context."); bool polly::ModelReadOnlyScalars; // The maximal number of dimensions we allow during invariant load construction. // More complex access ranges will result in very high compile time and are also // unlikely to result in good code. This value is very high and should only // trigger for corner cases (e.g., the "dct_luma" function in h264, SPEC2006). static unsigned const MaxDimensionsInAccessRange = …; static cl::opt<bool, true> XModelReadOnlyScalars( "polly-analyze-read-only-scalars", cl::desc("Model read-only scalar values in the scop description"), cl::location(ModelReadOnlyScalars), cl::Hidden, cl::init(true), cl::cat(PollyCategory)); static cl::opt<int> OptComputeOut("polly-analysis-computeout", cl::desc("Bound the scop analysis by a maximal amount of " "computational steps (0 means no bound)"), cl::Hidden, cl::init(800000), cl::cat(PollyCategory)); static cl::opt<bool> PollyAllowDereferenceOfAllFunctionParams( "polly-allow-dereference-of-all-function-parameters", cl::desc( "Treat all parameters to functions that are pointers as dereferencible." " This is useful for invariant load hoisting, since we can generate" " less runtime checks. This is only valid if all pointers to functions" " are always initialized, so that Polly can choose to hoist" " their loads. "), cl::Hidden, cl::init(false), cl::cat(PollyCategory)); static cl::opt<bool> PollyIgnoreInbounds("polly-ignore-inbounds", cl::desc("Do not take inbounds assumptions at all"), cl::Hidden, cl::init(false), cl::cat(PollyCategory)); static cl::opt<unsigned> RunTimeChecksMaxArraysPerGroup( "polly-rtc-max-arrays-per-group", cl::desc("The maximal number of arrays to compare in each alias group."), cl::Hidden, cl::init(20), cl::cat(PollyCategory)); static cl::opt<unsigned> RunTimeChecksMaxAccessDisjuncts( "polly-rtc-max-array-disjuncts", cl::desc("The maximal number of disjunts allowed in memory accesses to " "to build RTCs."), cl::Hidden, cl::init(8), cl::cat(PollyCategory)); static cl::opt<unsigned> RunTimeChecksMaxParameters( "polly-rtc-max-parameters", cl::desc("The maximal number of parameters allowed in RTCs."), cl::Hidden, cl::init(8), cl::cat(PollyCategory)); static cl::opt<bool> UnprofitableScalarAccs( "polly-unprofitable-scalar-accs", cl::desc("Count statements with scalar accesses as not optimizable"), cl::Hidden, cl::init(false), cl::cat(PollyCategory)); static cl::opt<std::string> UserContextStr( "polly-context", cl::value_desc("isl parameter set"), cl::desc("Provide additional constraints on the context parameters"), cl::init(""), cl::cat(PollyCategory)); static cl::opt<bool> DetectReductions("polly-detect-reductions", cl::desc("Detect and exploit reductions"), cl::Hidden, cl::init(true), cl::cat(PollyCategory)); // Multiplicative reductions can be disabled separately as these kind of // operations can overflow easily. Additive reductions and bit operations // are in contrast pretty stable. static cl::opt<bool> DisableMultiplicativeReductions( "polly-disable-multiplicative-reductions", cl::desc("Disable multiplicative reductions"), cl::Hidden, cl::cat(PollyCategory)); enum class GranularityChoice { … }; static cl::opt<GranularityChoice> StmtGranularity( "polly-stmt-granularity", cl::desc( "Algorithm to use for splitting basic blocks into multiple statements"), cl::values(clEnumValN(GranularityChoice::BasicBlocks, "bb", "One statement per basic block"), clEnumValN(GranularityChoice::ScalarIndependence, "scalar-indep", "Scalar independence heuristic"), clEnumValN(GranularityChoice::Stores, "store", "Store-level granularity")), cl::init(GranularityChoice::ScalarIndependence), cl::cat(PollyCategory)); /// Helper to treat non-affine regions and basic blocks the same. /// ///{ /// Return the block that is the representing block for @p RN. static inline BasicBlock *getRegionNodeBasicBlock(RegionNode *RN) { … } /// Return the @p idx'th block that is executed after @p RN. static inline BasicBlock * getRegionNodeSuccessor(RegionNode *RN, Instruction *TI, unsigned idx) { … } static bool containsErrorBlock(RegionNode *RN, const Region &R, ScopDetection *SD) { … } ///} /// Create a map to map from a given iteration to a subsequent iteration. /// /// This map maps from SetSpace -> SetSpace where the dimensions @p Dim /// is incremented by one and all other dimensions are equal, e.g., /// [i0, i1, i2, i3] -> [i0, i1, i2 + 1, i3] /// /// if @p Dim is 2 and @p SetSpace has 4 dimensions. static isl::map createNextIterationMap(isl::space SetSpace, unsigned Dim) { … } /// Add @p BSet to set @p BoundedParts if @p BSet is bounded. static isl::set collectBoundedParts(isl::set S) { … } /// Compute the (un)bounded parts of @p S wrt. to dimension @p Dim. /// /// @returns A separation of @p S into first an unbounded then a bounded subset, /// both with regards to the dimension @p Dim. static std::pair<isl::set, isl::set> partitionSetParts(isl::set S, unsigned Dim) { … } /// Create the conditions under which @p L @p Pred @p R is true. static isl::set buildConditionSet(ICmpInst::Predicate Pred, isl::pw_aff L, isl::pw_aff R) { … } isl::set ScopBuilder::adjustDomainDimensions(isl::set Dom, Loop *OldL, Loop *NewL) { … } /// Compute the isl representation for the SCEV @p E in this BB. /// /// @param BB The BB for which isl representation is to be /// computed. /// @param InvalidDomainMap A map of BB to their invalid domains. /// @param E The SCEV that should be translated. /// @param NonNegative Flag to indicate the @p E has to be non-negative. /// /// Note that this function will also adjust the invalid context accordingly. __isl_give isl_pw_aff * ScopBuilder::getPwAff(BasicBlock *BB, DenseMap<BasicBlock *, isl::set> &InvalidDomainMap, const SCEV *E, bool NonNegative) { … } /// Build condition sets for unsigned ICmpInst(s). /// Special handling is required for unsigned operands to ensure that if /// MSB (aka the Sign bit) is set for an operands in an unsigned ICmpInst /// it should wrap around. /// /// @param IsStrictUpperBound holds information on the predicate relation /// between TestVal and UpperBound, i.e, /// TestVal < UpperBound OR TestVal <= UpperBound __isl_give isl_set *ScopBuilder::buildUnsignedConditionSets( BasicBlock *BB, Value *Condition, __isl_keep isl_set *Domain, const SCEV *SCEV_TestVal, const SCEV *SCEV_UpperBound, DenseMap<BasicBlock *, isl::set> &InvalidDomainMap, bool IsStrictUpperBound) { … } bool ScopBuilder::buildConditionSets( BasicBlock *BB, SwitchInst *SI, Loop *L, __isl_keep isl_set *Domain, DenseMap<BasicBlock *, isl::set> &InvalidDomainMap, SmallVectorImpl<__isl_give isl_set *> &ConditionSets) { … } bool ScopBuilder::buildConditionSets( BasicBlock *BB, Value *Condition, Instruction *TI, Loop *L, __isl_keep isl_set *Domain, DenseMap<BasicBlock *, isl::set> &InvalidDomainMap, SmallVectorImpl<__isl_give isl_set *> &ConditionSets) { … } bool ScopBuilder::buildConditionSets( BasicBlock *BB, Instruction *TI, Loop *L, __isl_keep isl_set *Domain, DenseMap<BasicBlock *, isl::set> &InvalidDomainMap, SmallVectorImpl<__isl_give isl_set *> &ConditionSets) { … } bool ScopBuilder::propagateDomainConstraints( Region *R, DenseMap<BasicBlock *, isl::set> &InvalidDomainMap) { … } void ScopBuilder::propagateDomainConstraintsToRegionExit( BasicBlock *BB, Loop *BBLoop, SmallPtrSetImpl<BasicBlock *> &FinishedExitBlocks, DenseMap<BasicBlock *, isl::set> &InvalidDomainMap) { … } isl::set ScopBuilder::getPredecessorDomainConstraints(BasicBlock *BB, isl::set Domain) { … } bool ScopBuilder::addLoopBoundsToHeaderDomain( Loop *L, DenseMap<BasicBlock *, isl::set> &InvalidDomainMap) { … } void ScopBuilder::buildInvariantEquivalenceClasses() { … } bool ScopBuilder::buildDomains( Region *R, DenseMap<BasicBlock *, isl::set> &InvalidDomainMap) { … } bool ScopBuilder::buildDomainsWithBranchConstraints( Region *R, DenseMap<BasicBlock *, isl::set> &InvalidDomainMap) { … } bool ScopBuilder::propagateInvalidStmtDomains( Region *R, DenseMap<BasicBlock *, isl::set> &InvalidDomainMap) { … } void ScopBuilder::buildPHIAccesses(ScopStmt *PHIStmt, PHINode *PHI, Region *NonAffineSubRegion, bool IsExitBlock) { … } void ScopBuilder::buildScalarDependences(ScopStmt *UserStmt, Instruction *Inst) { … } // Create a sequence of two schedules. Either argument may be null and is // interpreted as the empty schedule. Can also return null if both schedules are // empty. static isl::schedule combineInSequence(isl::schedule Prev, isl::schedule Succ) { … } // Create an isl_multi_union_aff that defines an identity mapping from the // elements of USet to their N-th dimension. // // # Example: // // Domain: { A[i,j]; B[i,j,k] } // N: 1 // // Resulting Mapping: { {A[i,j] -> [(j)]; B[i,j,k] -> [(j)] } // // @param USet A union set describing the elements for which to generate a // mapping. // @param N The dimension to map to. // @returns A mapping from USet to its N-th dimension. static isl::multi_union_pw_aff mapToDimension(isl::union_set USet, unsigned N) { … } void ScopBuilder::buildSchedule() { … } /// To generate a schedule for the elements in a Region we traverse the Region /// in reverse-post-order and add the contained RegionNodes in traversal order /// to the schedule of the loop that is currently at the top of the LoopStack. /// For loop-free codes, this results in a correct sequential ordering. /// /// Example: /// bb1(0) /// / \. /// bb2(1) bb3(2) /// \ / \. /// bb4(3) bb5(4) /// \ / /// bb6(5) /// /// Including loops requires additional processing. Whenever a loop header is /// encountered, the corresponding loop is added to the @p LoopStack. Starting /// from an empty schedule, we first process all RegionNodes that are within /// this loop and complete the sequential schedule at this loop-level before /// processing about any other nodes. To implement this /// loop-nodes-first-processing, the reverse post-order traversal is /// insufficient. Hence, we additionally check if the traversal yields /// sub-regions or blocks that are outside the last loop on the @p LoopStack. /// These region-nodes are then queue and only traverse after the all nodes /// within the current loop have been processed. void ScopBuilder::buildSchedule(Region *R, LoopStackTy &LoopStack) { … } void ScopBuilder::buildSchedule(RegionNode *RN, LoopStackTy &LoopStack) { … } void ScopBuilder::buildEscapingDependences(Instruction *Inst) { … } void ScopBuilder::addRecordedAssumptions() { … } void ScopBuilder::addUserAssumptions( AssumptionCache &AC, DenseMap<BasicBlock *, isl::set> &InvalidDomainMap) { … } bool ScopBuilder::buildAccessMultiDimFixed(MemAccInst Inst, ScopStmt *Stmt) { … } bool ScopBuilder::buildAccessMultiDimParam(MemAccInst Inst, ScopStmt *Stmt) { … } bool ScopBuilder::buildAccessMemIntrinsic(MemAccInst Inst, ScopStmt *Stmt) { … } bool ScopBuilder::buildAccessCallInst(MemAccInst Inst, ScopStmt *Stmt) { … } bool ScopBuilder::buildAccessSingleDim(MemAccInst Inst, ScopStmt *Stmt) { … } void ScopBuilder::buildMemoryAccess(MemAccInst Inst, ScopStmt *Stmt) { … } void ScopBuilder::buildAccessFunctions() { … } bool ScopBuilder::shouldModelInst(Instruction *Inst, Loop *L) { … } /// Generate a name for a statement. /// /// @param BB The basic block the statement will represent. /// @param BBIdx The index of the @p BB relative to other BBs/regions. /// @param Count The index of the created statement in @p BB. /// @param IsMain Whether this is the main of all statement for @p BB. If true, /// no suffix will be added. /// @param IsLast Uses a special indicator for the last statement of a BB. static std::string makeStmtName(BasicBlock *BB, long BBIdx, int Count, bool IsMain, bool IsLast = false) { … } /// Generate a name for a statement that represents a non-affine subregion. /// /// @param R The region the statement will represent. /// @param RIdx The index of the @p R relative to other BBs/regions. static std::string makeStmtName(Region *R, long RIdx) { … } void ScopBuilder::buildSequentialBlockStmts(BasicBlock *BB, bool SplitOnStore) { … } /// Is @p Inst an ordered instruction? /// /// An unordered instruction is an instruction, such that a sequence of /// unordered instructions can be permuted without changing semantics. Any /// instruction for which this is not always the case is ordered. static bool isOrderedInstruction(Instruction *Inst) { … } /// Join instructions to the same statement if one uses the scalar result of the /// other. static void joinOperandTree(EquivalenceClasses<Instruction *> &UnionFind, ArrayRef<Instruction *> ModeledInsts) { … } /// Ensure that the order of ordered instructions does not change. /// /// If we encounter an ordered instruction enclosed in instructions belonging to /// a different statement (which might as well contain ordered instructions, but /// this is not tested here), join them. static void joinOrderedInstructions(EquivalenceClasses<Instruction *> &UnionFind, ArrayRef<Instruction *> ModeledInsts) { … } /// If the BasicBlock has an edge from itself, ensure that the PHI WRITEs for /// the incoming values from this block are executed after the PHI READ. /// /// Otherwise it could overwrite the incoming value from before the BB with the /// value for the next execution. This can happen if the PHI WRITE is added to /// the statement with the instruction that defines the incoming value (instead /// of the last statement of the same BB). To ensure that the PHI READ and WRITE /// are in order, we put both into the statement. PHI WRITEs are always executed /// after PHI READs when they are in the same statement. /// /// TODO: This is an overpessimization. We only have to ensure that the PHI /// WRITE is not put into a statement containing the PHI itself. That could also /// be done by /// - having all (strongly connected) PHIs in a single statement, /// - unite only the PHIs in the operand tree of the PHI WRITE (because it only /// has a chance of being lifted before a PHI by being in a statement with a /// PHI that comes before in the basic block), or /// - when uniting statements, ensure that no (relevant) PHIs are overtaken. static void joinOrderedPHIs(EquivalenceClasses<Instruction *> &UnionFind, ArrayRef<Instruction *> ModeledInsts) { … } void ScopBuilder::buildEqivClassBlockStmts(BasicBlock *BB) { … } void ScopBuilder::buildStmts(Region &SR) { … } void ScopBuilder::buildAccessFunctions(ScopStmt *Stmt, BasicBlock &BB, Region *NonAffineSubRegion) { … } MemoryAccess *ScopBuilder::addMemoryAccess( ScopStmt *Stmt, Instruction *Inst, MemoryAccess::AccessType AccType, Value *BaseAddress, Type *ElementType, bool Affine, Value *AccessValue, ArrayRef<const SCEV *> Subscripts, ArrayRef<const SCEV *> Sizes, MemoryKind Kind) { … } void ScopBuilder::addArrayAccess(ScopStmt *Stmt, MemAccInst MemAccInst, MemoryAccess::AccessType AccType, Value *BaseAddress, Type *ElementType, bool IsAffine, ArrayRef<const SCEV *> Subscripts, ArrayRef<const SCEV *> Sizes, Value *AccessValue) { … } /// Check if @p Expr is divisible by @p Size. static bool isDivisible(const SCEV *Expr, unsigned Size, ScalarEvolution &SE) { … } void ScopBuilder::foldSizeConstantsToRight() { … } void ScopBuilder::finalizeAccesses() { … } void ScopBuilder::updateAccessDimensionality() { … } void ScopBuilder::foldAccessRelations() { … } void ScopBuilder::assumeNoOutOfBounds() { … } void ScopBuilder::ensureValueWrite(Instruction *Inst) { … } void ScopBuilder::ensureValueRead(Value *V, ScopStmt *UserStmt) { … } void ScopBuilder::ensurePHIWrite(PHINode *PHI, ScopStmt *IncomingStmt, BasicBlock *IncomingBlock, Value *IncomingValue, bool IsExitBlock) { … } void ScopBuilder::addPHIReadAccess(ScopStmt *PHIStmt, PHINode *PHI) { … } void ScopBuilder::buildDomain(ScopStmt &Stmt) { … } void ScopBuilder::collectSurroundingLoops(ScopStmt &Stmt) { … } /// Return the reduction type for a given binary operator. static MemoryAccess::ReductionType getReductionType(const BinaryOperator *BinOp) { … } /// @brief Combine two reduction types static MemoryAccess::ReductionType combineReductionType(MemoryAccess::ReductionType RT0, MemoryAccess::ReductionType RT1) { … } /// True if @p AllAccs intersects with @p MemAccs execpt @p LoadMA and @p /// StoreMA bool hasIntersectingAccesses(isl::set AllAccs, MemoryAccess *LoadMA, MemoryAccess *StoreMA, isl::set Domain, SmallVector<MemoryAccess *, 8> &MemAccs) { … } /// Test if the accesses of @p LoadMA and @p StoreMA can form a reduction bool checkCandidatePairAccesses(MemoryAccess *LoadMA, MemoryAccess *StoreMA, isl::set Domain, SmallVector<MemoryAccess *, 8> &MemAccs) { … } void ScopBuilder::checkForReductions(ScopStmt &Stmt) { … } void ScopBuilder::verifyInvariantLoads() { … } void ScopBuilder::hoistInvariantLoads() { … } /// Check if an access range is too complex. /// /// An access range is too complex, if it contains either many disjuncts or /// very complex expressions. As a simple heuristic, we assume if a set to /// be too complex if the sum of existentially quantified dimensions and /// set dimensions is larger than a threshold. This reliably detects both /// sets with many disjuncts as well as sets with many divisions as they /// arise in h264. /// /// @param AccessRange The range to check for complexity. /// /// @returns True if the access range is too complex. static bool isAccessRangeTooComplex(isl::set AccessRange) { … } bool ScopBuilder::hasNonHoistableBasePtrInScop(MemoryAccess *MA, isl::union_map Writes) { … } void ScopBuilder::addUserContext() { … } isl::set ScopBuilder::getNonHoistableCtx(MemoryAccess *Access, isl::union_map Writes) { … } static bool isAParameter(llvm::Value *maybeParam, const Function &F) { … } bool ScopBuilder::canAlwaysBeHoisted(MemoryAccess *MA, bool StmtInvalidCtxIsEmpty, bool MAInvalidCtxIsEmpty, bool NonHoistableCtxIsEmpty) { … } void ScopBuilder::addInvariantLoads(ScopStmt &Stmt, InvariantAccessesTy &InvMAs) { … } /// Find the canonical scop array info object for a set of invariant load /// hoisted loads. The canonical array is the one that corresponds to the /// first load in the list of accesses which is used as base pointer of a /// scop array. static const ScopArrayInfo *findCanonicalArray(Scop &S, MemoryAccessList &Accesses) { … } /// Check if @p Array severs as base array in an invariant load. static bool isUsedForIndirectHoistedLoad(Scop &S, const ScopArrayInfo *Array) { … } /// Replace the base pointer arrays in all memory accesses referencing @p Old, /// with a reference to @p New. static void replaceBasePtrArrays(Scop &S, const ScopArrayInfo *Old, const ScopArrayInfo *New) { … } void ScopBuilder::canonicalizeDynamicBasePtrs() { … } void ScopBuilder::buildAccessRelations(ScopStmt &Stmt) { … } /// Add the minimal/maximal access in @p Set to @p User. /// /// @return True if more accesses should be added, false if we reached the /// maximal number of run-time checks to be generated. static bool buildMinMaxAccess(isl::set Set, Scop::MinMaxVectorTy &MinMaxAccesses, Scop &S) { … } /// Wrapper function to calculate minimal/maximal accesses to each array. bool ScopBuilder::calculateMinMaxAccess(AliasGroupTy AliasGroup, Scop::MinMaxVectorTy &MinMaxAccesses) { … } static isl::set getAccessDomain(MemoryAccess *MA) { … } bool ScopBuilder::buildAliasChecks() { … } std::tuple<ScopBuilder::AliasGroupVectorTy, DenseSet<const ScopArrayInfo *>> ScopBuilder::buildAliasGroupsForAccesses() { … } bool ScopBuilder::buildAliasGroups() { … } bool ScopBuilder::buildAliasGroup( AliasGroupTy &AliasGroup, DenseSet<const ScopArrayInfo *> HasWriteAccess) { … } void ScopBuilder::splitAliasGroupsByDomain(AliasGroupVectorTy &AliasGroups) { … } #ifndef NDEBUG static void verifyUse(Scop *S, Use &Op, LoopInfo &LI) { auto PhysUse = VirtualUse::create(S, Op, &LI, false); auto VirtUse = VirtualUse::create(S, Op, &LI, true); assert(PhysUse.getKind() == VirtUse.getKind()); } /// Check the consistency of every statement's MemoryAccesses. /// /// The check is carried out by expecting the "physical" kind of use (derived /// from the BasicBlocks instructions resides in) to be same as the "virtual" /// kind of use (derived from a statement's MemoryAccess). /// /// The "physical" uses are taken by ensureValueRead to determine whether to /// create MemoryAccesses. When done, the kind of scalar access should be the /// same no matter which way it was derived. /// /// The MemoryAccesses might be changed by later SCoP-modifying passes and hence /// can intentionally influence on the kind of uses (not corresponding to the /// "physical" anymore, hence called "virtual"). The CodeGenerator therefore has /// to pick up the virtual uses. But here in the code generator, this has not /// happened yet, such that virtual and physical uses are equivalent. static void verifyUses(Scop *S, LoopInfo &LI, DominatorTree &DT) { for (auto *BB : S->getRegion().blocks()) { for (auto &Inst : *BB) { auto *Stmt = S->getStmtFor(&Inst); if (!Stmt) continue; if (isIgnoredIntrinsic(&Inst)) continue; // Branch conditions are encoded in the statement domains. if (Inst.isTerminator() && Stmt->isBlockStmt()) continue; // Verify all uses. for (auto &Op : Inst.operands()) verifyUse(S, Op, LI); // Stores do not produce values used by other statements. if (isa<StoreInst>(Inst)) continue; // For every value defined in the block, also check that a use of that // value in the same statement would not be an inter-statement use. It can // still be synthesizable or load-hoisted, but these kind of instructions // are not directly copied in code-generation. auto VirtDef = VirtualUse::create(S, Stmt, Stmt->getSurroundingLoop(), &Inst, true); assert(VirtDef.getKind() == VirtualUse::Synthesizable || VirtDef.getKind() == VirtualUse::Intra || VirtDef.getKind() == VirtualUse::Hoisted); } } if (S->hasSingleExitEdge()) return; // PHINodes in the SCoP region's exit block are also uses to be checked. if (!S->getRegion().isTopLevelRegion()) { for (auto &Inst : *S->getRegion().getExit()) { if (!isa<PHINode>(Inst)) break; for (auto &Op : Inst.operands()) verifyUse(S, Op, LI); } } } #endif void ScopBuilder::buildScop(Region &R, AssumptionCache &AC) { … } ScopBuilder::ScopBuilder(Region *R, AssumptionCache &AC, AAResults &AA, const DataLayout &DL, DominatorTree &DT, LoopInfo &LI, ScopDetection &SD, ScalarEvolution &SE, OptimizationRemarkEmitter &ORE) : … { … }
Codebase Browser
llvm