Index: include/polly/ScopDetection.h =================================================================== --- include/polly/ScopDetection.h +++ include/polly/ScopDetection.h @@ -136,6 +136,11 @@ AliasAnalysis *AA; //@} + /// @brief Set to remeber non-affine branches in regions. + using NonAffineBranchSetTy = + DenseSet>; + NonAffineBranchSetTy NonAffineBranchSet; + /// @brief Context variables for SCoP detection. struct DetectionContext { Region &CurRegion; // The region to check. @@ -162,6 +167,9 @@ /// @brief The region has at least one store instruction. bool hasStores; + /// @brief Set to remeber non-affine branches in regions. + NonAffineBranchSetTy NonAffineBranchSet; + DetectionContext(Region &R, AliasAnalysis &AA, bool Verify) : CurRegion(R), AST(AA), Verifying(Verify), Log(&R), hasLoads(false), hasStores(false) {} @@ -300,6 +308,9 @@ /// @return Return true if R is the maximum Region in a Scop, false otherwise. bool isMaxRegionInScop(const Region &R, bool Verify = true) const; + /// @brief Return true if @p BB has a non-affine branch in @p R. + bool hasNonAffineBranch(const Region *R, const BasicBlock *BB) const; + /// @brief Get a message why a region is invalid /// /// @param R The region for which we get the error message Index: include/polly/ScopInfo.h =================================================================== --- include/polly/ScopInfo.h +++ include/polly/ScopInfo.h @@ -424,9 +424,21 @@ //@} - /// The BasicBlock represented by this statement. + /// @brief A SCoP statement represents either a basic block (affine/precise + /// case) or a whole region (non-affine case). Only one of the + /// following two members will therefore be set and indicate which + /// kind of statement this is. + /// + ///{ + + /// @brief The BasicBlock represented by this statement (in the affine case). BasicBlock *BB; + /// @brief The region represented by this statement (in the non-affine case). + Region *R; + + ///} + /// @brief The isl AST build for the new generated AST. isl_ast_build *Build; @@ -444,7 +456,17 @@ TempScop &tempScop); __isl_give isl_set *buildDomain(TempScop &tempScop, const Region &CurRegion); void buildScattering(SmallVectorImpl &Scatter); - void buildAccesses(TempScop &tempScop); + + /// @brief Create the accesses for instructions in @p Block. + /// + /// @param tempScop The template SCoP. + /// @param Block The basic block for which accesses should be + /// created. + /// @param isApproximated Flag to indicate blocks that might not be executed, + /// hence for which write accesses need to be modelt as + /// may-write accesses. + void buildAccesses(TempScop &tempScop, BasicBlock *Block, + bool isApproximated = false); /// @brief Detect and mark reductions in the ScopStmt void checkForReductions(); @@ -484,14 +506,19 @@ /// or non-optimal run-time checks. void deriveAssumptionsFromGEP(GetElementPtrInst *Inst); - /// @brief Scan the scop and derive assumptions about parameter values. - void deriveAssumptions(); + /// @brief Scan @p Block and derive assumptions about parameter values. + void deriveAssumptions(BasicBlock *Block); /// Create the ScopStmt from a BasicBlock. ScopStmt(Scop &parent, TempScop &tempScop, const Region &CurRegion, BasicBlock &bb, SmallVectorImpl &NestLoops, SmallVectorImpl &Scatter); + /// Create an overapproximating ScopStmt for the region @p R. + ScopStmt(Scop &parent, TempScop &tempScop, const Region &CurRegion, Region &R, + SmallVectorImpl &NestLoops, + SmallVectorImpl &Scatter); + friend class Scop; public: @@ -527,11 +554,18 @@ /// @brief Get an isl string representing this scattering. std::string getScatteringStr() const; - /// @brief Get the BasicBlock represented by this ScopStmt. + /// @brief Get the BasicBlock represented by this ScopStmt (if any). /// - /// @return The BasicBlock represented by this ScopStmt. + /// @return The BasicBlock represented by this ScopStmt, or null if the + /// statement represents a region. BasicBlock *getBasicBlock() const { return BB; } + /// @brief Get the region represented by this ScopStmt (if any). + /// + /// @return The region represented by this ScopStmt, or null if the statement + /// represents a basic block. + Region *getRegion() const { return R; } + const MemoryAccess &getAccessFor(const Instruction *Inst) const { MemoryAccess *A = lookupAccessFor(Inst); assert(A && "Cannot get memory access because it does not exist!"); @@ -544,7 +578,12 @@ return at == InstructionToAccess.end() ? NULL : at->second; } - void setBasicBlock(BasicBlock *Block) { BB = Block; } + void setBasicBlock(BasicBlock *Block) { + // TODO: Handle the case where the statement is a region statement, thus + // the entry block was split and needs to be changed in the region R. + assert(BB && "Cannot set a block for a region statement"); + BB = Block; + } typedef MemoryAccessVec::iterator iterator; typedef MemoryAccessVec::const_iterator const_iterator; @@ -692,7 +731,8 @@ /// Create the static control part with a region, max loop depth of this /// region and parameters used in this region. - Scop(TempScop &TempScop, LoopInfo &LI, ScalarEvolution &SE, isl_ctx *ctx); + Scop(TempScop &TempScop, LoopInfo &LI, ScalarEvolution &SE, ScopDetection &SD, + isl_ctx *ctx); /// @brief Check if a basic block is trivial. /// @@ -714,12 +754,28 @@ /// @brief Simplify the assumed context. void simplifyAssumedContext(); + /// @brief Create a new SCoP statement for either @p BB or @p R. + /// + /// Either @p BB or @p R should be non-null. A new statement for the non-null + /// argument will be created and added to the statement vector and map. + /// + /// @param BB The basic block we build the statement for (or null) + /// @param R The region we build the statement for (or null). + /// @param tempScop The temp SCoP we use as model. + /// @param CurRegion The SCoP region. + /// @param NestLoops A vector of all surrounding loops. + /// @param Scatter The position of the new statement as scattering. + void addScopStmt(BasicBlock *BB, Region *R, TempScop &tempScop, + const Region &CurRegion, SmallVectorImpl &NestLoops, + SmallVectorImpl &Scatter); + /// Build the Scop and Statement with precalculated scop information. void buildScop(TempScop &TempScop, const Region &CurRegion, // Loops in Scop containing CurRegion SmallVectorImpl &NestLoops, // The scattering numbers - SmallVectorImpl &Scatter, LoopInfo &LI); + SmallVectorImpl &Scatter, LoopInfo &LI, + ScopDetection &SD); /// @name Helper function for printing the Scop. /// Index: include/polly/TempScopInfo.h =================================================================== --- include/polly/TempScopInfo.h +++ include/polly/TempScopInfo.h @@ -80,6 +80,8 @@ bool isWrite() const { return Type == MUST_WRITE; } + void setMayWrite() { Type = MAY_WRITE; } + bool isMayWrite() const { return Type == MAY_WRITE; } bool isScalar() const { return Subscripts.size() == 0; } @@ -136,7 +138,7 @@ const BBCondMapType &BBConds; // Access function of bbs. - const AccFuncMapType &AccFuncMap; + AccFuncMapType &AccFuncMap; friend class TempScopInfo; @@ -169,8 +171,8 @@ /// /// @return All access functions in BB /// - const AccFuncSetType *getAccessFunctions(const BasicBlock *BB) const { - AccFuncMapType::const_iterator at = AccFuncMap.find(BB); + AccFuncSetType *getAccessFunctions(const BasicBlock *BB) { + AccFuncMapType::iterator at = AccFuncMap.find(BB); return at != AccFuncMap.end() ? &(at->second) : 0; } //@} @@ -239,10 +241,9 @@ /// @brief Build condition constrains to BBs in a valid Scop. /// - /// @param BB The BasicBlock to build condition constrains - /// @param RegionEntry The entry block of the Smallest Region that containing - /// BB - void buildCondition(BasicBlock *BB, BasicBlock *RegionEntry); + /// @param BB The BasicBlock to build condition constrains + /// @param R The region for the current TempScop. + void buildCondition(BasicBlock *BB, Region &R); // Build the affine function of the given condition void buildAffineCondition(Value &V, bool inverted, Comparison **Comp) const; Index: lib/Analysis/ScopDetection.cpp =================================================================== --- lib/Analysis/ScopDetection.cpp +++ lib/Analysis/ScopDetection.cpp @@ -126,6 +126,12 @@ cl::Hidden, cl::init(false), cl::ZeroOrMore, cl::cat(PollyCategory)); +static cl::opt + AllowNonAffineBranches("polly-allow-nonaffine-branches", + cl::desc("Allow non affine conditions for branches"), + cl::Hidden, cl::init(false), cl::ZeroOrMore, + cl::cat(PollyCategory)); + static cl::opt AllowUnsigned("polly-allow-unsigned", cl::desc("Allow unsigned expressions"), cl::Hidden, cl::init(false), cl::ZeroOrMore, @@ -300,8 +306,12 @@ return invalid(Context, /*Assert=*/true, Br, &BB); // Only Constant and ICmpInst are allowed as condition. - if (!(isa(Condition) || isa(Condition))) - return invalid(Context, /*Assert=*/true, Br, &BB); + if (!(isa(Condition) || isa(Condition))) { + if (AllowNonAffineBranches) + Context.NonAffineBranchSet.insert(std::make_pair(&RefRegion, &BB)); + else + return invalid(Context, /*Assert=*/true, Br, &BB); + } // Allow perfectly nested conditions. assert(Br->getNumSuccessors() == 2 && "Unexpected number of successors"); @@ -325,9 +335,13 @@ const SCEV *RHS = SE->getSCEVAtScope(ICmp->getOperand(1), L); if (!isAffineExpr(&Context.CurRegion, LHS, *SE) || - !isAffineExpr(&Context.CurRegion, RHS, *SE)) - return invalid(Context, /*Assert=*/true, &BB, LHS, - RHS, ICmp); + !isAffineExpr(&Context.CurRegion, RHS, *SE)) { + if (AllowNonAffineBranches) + Context.NonAffineBranchSet.insert(std::make_pair(&RefRegion, &BB)); + else + return invalid(Context, /*Assert=*/true, &BB, LHS, + RHS, ICmp); + } } // Allow loop exit conditions. @@ -643,8 +657,13 @@ bool ScopDetection::isValidLoop(Loop *L, DetectionContext &Context) const { // Is the loop count affine? const SCEV *LoopCount = SE->getBackedgeTakenCount(L); - if (!isAffineExpr(&Context.CurRegion, LoopCount, *SE)) - return invalid(Context, /*Assert=*/true, L, LoopCount); + if (!isAffineExpr(&Context.CurRegion, LoopCount, *SE)) { + if (AllowNonAffineBranches) + Context.NonAffineBranchSet.insert( + std::make_pair(&Context.CurRegion, L->getHeader())); + else + return invalid(Context, /*Assert=*/true, L, LoopCount); + } return true; } @@ -680,6 +699,10 @@ // far). LastValidRegion = ExpandedRegion; + // Remember the non-affine branches in this region. + NonAffineBranchSet.insert(Context.NonAffineBranchSet.begin(), + Context.NonAffineBranchSet.end()); + // Create and test the next greater region (if any) ExpandedRegion = ExpandedRegion->getExpandedRegion(); @@ -743,6 +766,10 @@ if (!HasErrors) { ++ValidRegion; ValidRegions.insert(&R); + + // Remember the non-affine branches in this region. + NonAffineBranchSet.insert(Context.NonAffineBranchSet.begin(), + Context.NonAffineBranchSet.end()); return; } @@ -960,6 +987,11 @@ return false; } +bool ScopDetection::hasNonAffineBranch(const Region *R, + const BasicBlock *BB) const { + return NonAffineBranchSet.count(std::make_pair(R, BB)); +} + void polly::ScopDetection::verifyRegion(const Region &R) const { assert(isMaxRegionInScop(R) && "Expect R is a valid region."); DetectionContext Context(const_cast(R), *AA, true /*verifying*/); @@ -995,6 +1027,7 @@ void ScopDetection::releaseMemory() { ValidRegions.clear(); RejectLogs.clear(); + NonAffineBranchSet.clear(); // Do not clear the invalid function set. } Index: lib/Analysis/ScopInfo.cpp =================================================================== --- lib/Analysis/ScopInfo.cpp +++ lib/Analysis/ScopInfo.cpp @@ -745,15 +745,23 @@ Scattering = isl_map_align_params(Scattering, Parent.getParamSpace()); } -void ScopStmt::buildAccesses(TempScop &tempScop) { - for (const auto &AccessPair : *tempScop.getAccessFunctions(BB)) { - const IRAccess &Access = AccessPair.first; +void ScopStmt::buildAccesses(TempScop &tempScop, BasicBlock *Block, + bool isApproximated) { + AccFuncSetType *AFS = tempScop.getAccessFunctions(Block); + if (!AFS) + return; + + for (auto &AccessPair : *AFS) { + IRAccess &Access = AccessPair.first; Instruction *AccessInst = AccessPair.second; Type *AccessType = getAccessInstType(AccessInst)->getPointerTo(); const ScopArrayInfo *SAI = getParent()->getOrCreateScopArrayInfo( Access.getBase(), AccessType, Access.Sizes); + if (Access.isWrite() && isApproximated) + Access.setMayWrite(); + MemAccs.push_back(new MemoryAccess(Access, AccessInst, this, SAI)); // We do not track locations for scalar memory accesses at the moment. @@ -842,7 +850,7 @@ const Region &CurRegion) { const Region *TopRegion = tempScop.getMaxRegion().getParent(), *CurrentRegion = &CurRegion; - const BasicBlock *BranchingBB = BB; + const BasicBlock *BranchingBB = BB ? BB : R->getEntry(); do { if (BranchingBB != CurrentRegion->getEntry()) { @@ -926,16 +934,40 @@ isl_local_space_free(LSpace); } -void ScopStmt::deriveAssumptions() { - for (Instruction &Inst : *BB) +void ScopStmt::deriveAssumptions(BasicBlock *Block) { + for (Instruction &Inst : *Block) if (auto *GEP = dyn_cast(&Inst)) deriveAssumptionsFromGEP(GEP); } ScopStmt::ScopStmt(Scop &parent, TempScop &tempScop, const Region &CurRegion, + Region &R, SmallVectorImpl &Nest, + SmallVectorImpl &Scatter) + : Parent(parent), BB(nullptr), R(&R), Build(nullptr), + NestLoops(Nest.size()) { + // Setup the induction variables. + for (unsigned i = 0, e = Nest.size(); i < e; ++i) + NestLoops[i] = Nest[i]; + + BaseName = getIslCompatibleName("Stmt_(", R.getNameStr(), ")"); + + Domain = buildDomain(tempScop, CurRegion); + buildScattering(Scatter); + + BasicBlock *EntryBB = R.getEntry(); + BasicBlock *ExitBB = R.getExit(); + for (BasicBlock *Block : R.blocks()) { + buildAccesses(tempScop, Block, Block != EntryBB && Block != ExitBB); + deriveAssumptions(Block); + } + checkForReductions(); +} + +ScopStmt::ScopStmt(Scop &parent, TempScop &tempScop, const Region &CurRegion, BasicBlock &bb, SmallVectorImpl &Nest, SmallVectorImpl &Scatter) - : Parent(parent), BB(&bb), Build(nullptr), NestLoops(Nest.size()) { + : Parent(parent), BB(&bb), R(nullptr), Build(nullptr), + NestLoops(Nest.size()) { // Setup the induction variables. for (unsigned i = 0, e = Nest.size(); i < e; ++i) NestLoops[i] = Nest[i]; @@ -944,9 +976,9 @@ Domain = buildDomain(tempScop, CurRegion); buildScattering(Scatter); - buildAccesses(tempScop); + buildAccesses(tempScop, BB); + deriveAssumptions(BB); checkForReductions(); - deriveAssumptions(); } /// @brief Collect loads which might form a reduction chain with @p StoreMA @@ -1086,9 +1118,7 @@ unsigned ScopStmt::getNumParams() const { return Parent.getNumParams(); } -unsigned ScopStmt::getNumIterators() const { - return NestLoops.size(); -} +unsigned ScopStmt::getNumIterators() const { return NestLoops.size(); } unsigned ScopStmt::getNumScattering() const { return isl_map_dim(Scattering, isl_dim_out); @@ -1491,7 +1521,8 @@ return Valid; } -static unsigned getMaxLoopDepthInRegion(const Region &R, LoopInfo &LI) { +static unsigned getMaxLoopDepthInRegion(const Region &R, LoopInfo &LI, + ScopDetection &SD) { unsigned MinLD = INT_MAX, MaxLD = 0; for (BasicBlock *BB : R.blocks()) { if (Loop *L = LI.getLoopFor(BB)) { @@ -1548,9 +1579,9 @@ } Scop::Scop(TempScop &tempScop, LoopInfo &LI, ScalarEvolution &ScalarEvolution, - isl_ctx *Context) + ScopDetection &SD, isl_ctx *Context) : SE(&ScalarEvolution), R(tempScop.getMaxRegion()), IsOptimized(false), - MaxLoopDepth(getMaxLoopDepthInRegion(tempScop.getMaxRegion(), LI)) { + MaxLoopDepth(getMaxLoopDepthInRegion(tempScop.getMaxRegion(), LI, SD)) { IslCtx = Context; buildContext(); @@ -1561,7 +1592,7 @@ // Build the iteration domain, access functions and scattering functions // traversing the region tree. - buildScop(tempScop, getRegion(), NestLoops, Scatter, LI); + buildScop(tempScop, getRegion(), NestLoops, Scatter, LI, SD); realignParams(); addParameterBounds(); @@ -1832,9 +1863,35 @@ return true; } +void Scop::addScopStmt(BasicBlock *BB, Region *R, TempScop &tempScop, + const Region &CurRegion, + SmallVectorImpl &NestLoops, + SmallVectorImpl &Scatter) { + ScopStmt *Stmt; + + if (BB) { + Stmt = new ScopStmt(*this, tempScop, CurRegion, *BB, NestLoops, Scatter); + StmtMap[BB] = Stmt; + } else { + assert(R && "Either a basic block or a region is needed to " + "create a new SCoP stmt."); + Stmt = new ScopStmt(*this, tempScop, CurRegion, *R, NestLoops, Scatter); + for (BasicBlock *BB : R->blocks()) + StmtMap[BB] = Stmt; + } + + // Insert all statements into the statement map and the statement vector. + Stmts.push_back(Stmt); + + // Increasing the Scattering function is OK for the moment, because + // we are using a depth first iterator and the program is well structured. + ++Scatter[NestLoops.size()]; +} + void Scop::buildScop(TempScop &tempScop, const Region &CurRegion, SmallVectorImpl &NestLoops, - SmallVectorImpl &Scatter, LoopInfo &LI) { + SmallVectorImpl &Scatter, LoopInfo &LI, + ScopDetection &SD) { Loop *L = castToLoop(CurRegion, LI); if (L) @@ -1846,24 +1903,20 @@ for (Region::const_element_iterator I = CurRegion.element_begin(), E = CurRegion.element_end(); I != E; ++I) - if (I->isSubRegion()) - buildScop(tempScop, *(I->getNodeAs()), NestLoops, Scatter, LI); - else { + if (I->isSubRegion()) { + Region *SubRegion = I->getNodeAs(); + if (SD.hasNonAffineBranch(&CurRegion, SubRegion->getEntry())) + addScopStmt(nullptr, SubRegion, tempScop, CurRegion, NestLoops, + Scatter); + else + buildScop(tempScop, *SubRegion, NestLoops, Scatter, LI, SD); + } else { BasicBlock *BB = I->getNodeAs(); if (isTrivialBB(BB, tempScop)) continue; - ScopStmt *Stmt = - new ScopStmt(*this, tempScop, CurRegion, *BB, NestLoops, Scatter); - - // Insert all statements into the statement map and the statement vector. - StmtMap[BB] = Stmt; - Stmts.push_back(Stmt); - - // Increasing the Scattering function is OK for the moment, because - // we are using a depth first iterator and the program is well structured. - ++Scatter[loopDepth]; + addScopStmt(BB, nullptr, tempScop, CurRegion, NestLoops, Scatter); } if (!L) @@ -1897,6 +1950,7 @@ AU.addRequired(); AU.addRequired(); AU.addRequired(); + AU.addRequired(); AU.addRequired(); AU.addRequired(); AU.setPreservesAll(); @@ -1925,6 +1979,7 @@ bool ScopInfo::runOnRegion(Region *R, RGPassManager &RGM) { LoopInfo &LI = getAnalysis().getLoopInfo(); AliasAnalysis &AA = getAnalysis(); + ScopDetection &SD = getAnalysis(); ScalarEvolution &SE = getAnalysis(); TempScop *tempScop = getAnalysis().getTempScop(R); @@ -1935,7 +1990,7 @@ return false; } - scop = new Scop(*tempScop, LI, SE, ctx); + scop = new Scop(*tempScop, LI, SE, SD, ctx); if (!PollyUseRuntimeAliasChecks) { // Statistics. @@ -1993,6 +2048,7 @@ INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass); INITIALIZE_PASS_DEPENDENCY(RegionInfoPass); INITIALIZE_PASS_DEPENDENCY(ScalarEvolution); +INITIALIZE_PASS_DEPENDENCY(ScopDetection); INITIALIZE_PASS_DEPENDENCY(TempScopInfo); INITIALIZE_PASS_END(ScopInfo, "polly-scops", "Polly - Create polyhedral description of Scops", false, Index: lib/Analysis/TempScopInfo.cpp =================================================================== --- lib/Analysis/TempScopInfo.cpp +++ lib/Analysis/TempScopInfo.cpp @@ -310,15 +310,17 @@ *Comp = new Comparison(LHS, RHS, Pred); } -void TempScopInfo::buildCondition(BasicBlock *BB, BasicBlock *RegionEntry) { +void TempScopInfo::buildCondition(BasicBlock *BB, Region &R) { + BasicBlock *RegionEntry = R.getEntry(); BBCond Cond; DomTreeNode *BBNode = DT->getNode(BB), *EntryNode = DT->getNode(RegionEntry); assert(BBNode && EntryNode && "Get null node while building condition!"); - // Walk up the dominance tree until reaching the entry node. Add all - // conditions on the path to BB except if BB postdominates the block + // Walk up the dominance tree until reaching the entry node. Collect all + // branching blocks on the path to BB except if BB postdominates the block // containing the condition. + SmallVector DominatorBrBlocks; while (BBNode != EntryNode) { BasicBlock *CurBB = BBNode->getBlock(); BBNode = BBNode->getIDom(); @@ -333,6 +335,23 @@ if (Br->isUnconditional()) continue; + DominatorBrBlocks.push_back(BBNode->getBlock()); + } + + // Until a non-affine branch was encountered add all conditions collected + // before. If a non-affine branch was encountered, stop as we overapproximate + // from here on anyway. + for (auto BIt = DominatorBrBlocks.rbegin(), BEnd = DominatorBrBlocks.rend(); + BIt != BEnd; BIt++) { + + BasicBlock *BBNode = *BIt; + BranchInst *Br = dyn_cast(BBNode->getTerminator()); + assert(Br && "A Valid Scop should only contain branch instruction"); + assert(Br->isConditional() && "Assumed a conditional branch"); + + if (SD->hasNonAffineBranch(&R, BBNode)) + break; + BasicBlock *TrueBB = Br->getSuccessor(0), *FalseBB = Br->getSuccessor(1); // Is BB on the ELSE side of the branch? @@ -365,7 +384,7 @@ for (const auto &BB : R.blocks()) { buildAccessFunctions(R, *BB); - buildCondition(BB, R.getEntry()); + buildCondition(BB, R); } return TScop; Index: test/ScopDetect/non-affine-conditional.ll =================================================================== --- /dev/null +++ test/ScopDetect/non-affine-conditional.ll @@ -0,0 +1,42 @@ +; RUN: opt %loadPolly -polly-allow-nonaffine-branches -polly-detect -analyze < %s | FileCheck %s +; +; void f(int *A) { +; for (int i = 0; i < 1024; i++) +; if (A[i]) +; A[i] = 0; +; } +; +; CHECK: Valid Region for Scop: bb1 => bb9 +; +target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" + +define void @f(i32* %A) { +bb: + br label %bb1 + +bb1: ; preds = %bb8, %bb + %indvars.iv = phi i64 [ %indvars.iv.next, %bb8 ], [ 0, %bb ] + %exitcond = icmp ne i64 %indvars.iv, 1024 + br i1 %exitcond, label %bb2, label %bb9 + +bb2: ; preds = %bb1 + %tmp = getelementptr inbounds i32* %A, i64 %indvars.iv + %tmp3 = load i32* %tmp, align 4 + %tmp4 = icmp eq i32 %tmp3, 0 + br i1 %tmp4, label %bb7, label %bb5 + +bb5: ; preds = %bb2 + %tmp6 = getelementptr inbounds i32* %A, i64 %indvars.iv + store i32 0, i32* %tmp6, align 4 + br label %bb7 + +bb7: ; preds = %bb2, %bb5 + br label %bb8 + +bb8: ; preds = %bb7 + %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1 + br label %bb1 + +bb9: ; preds = %bb1 + ret void +} Index: test/ScopDetect/non-affine-loop-condition-dependent-access.ll =================================================================== --- /dev/null +++ test/ScopDetect/non-affine-loop-condition-dependent-access.ll @@ -0,0 +1,53 @@ +; RUN: opt %loadPolly -polly-detect -polly-allow-nonaffine-branches -analyze < %s | FileCheck %s +; +; Here we have a non affine branch but also a non-affine access which should +; be rejected as long as -polly-allow-nonaffine isn't given. +; +; CHECK-NOT: Valid +; +; void f(int *A, int *C) { +; int j; +; for (int i = 0; i < 1024; i++) { +; while ((j = C[i])) +; A[j]++; +; } +; } +; +target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" + +define void @f(i32* %A, i32* %C) { +bb: + br label %bb1 + +bb1: ; preds = %bb12, %bb + %indvars.iv = phi i64 [ %indvars.iv.next, %bb12 ], [ 0, %bb ] + %exitcond = icmp ne i64 %indvars.iv, 1024 + br i1 %exitcond, label %bb2, label %bb13 + +bb2: ; preds = %bb1 + br label %bb3 + +bb3: ; preds = %bb6, %bb2 + %tmp = getelementptr inbounds i32* %C, i64 %indvars.iv + %tmp4 = load i32* %tmp, align 4 + %tmp5 = icmp eq i32 %tmp4, 0 + br i1 %tmp5, label %bb11, label %bb6 + +bb6: ; preds = %bb3 + %tmp7 = sext i32 %tmp4 to i64 + %tmp8 = getelementptr inbounds i32* %A, i64 %tmp7 + %tmp9 = load i32* %tmp8, align 4 + %tmp10 = add nsw i32 %tmp9, 1 + store i32 %tmp10, i32* %tmp8, align 4 + br label %bb3 + +bb11: ; preds = %bb3 + br label %bb12 + +bb12: ; preds = %bb11 + %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1 + br label %bb1 + +bb13: ; preds = %bb1 + ret void +} Index: test/ScopInfo/non-affine-conditionals-nested.ll =================================================================== --- /dev/null +++ test/ScopInfo/non-affine-conditionals-nested.ll @@ -0,0 +1,72 @@ +; RUN: opt %loadPolly -polly-scops -polly-allow-nonaffine-branches -analyze < %s | FileCheck %s +; +; void f(int *A) { +; for (int i = 0; i < 1024; i++) +; if (A[i]) +; if (A[i - 1]) +; A[i] = A[i - 2]; +; } +; +; CHECK: Region: %bb1---%bb18 +; CHECK: Max Loop Depth: 1 +; CHECK: Statements { +; CHECK: Stmt_(bb2 => bb16) +; CHECK: Domain := +; CHECK: { Stmt_(bb2 => bb16)[i0] : i0 >= 0 and i0 <= 1023 }; +; CHECK: Scattering := +; CHECK: { Stmt_(bb2 => bb16)[i0] -> [i0] }; +; CHECK: ReadAccess := [Reduction Type: NONE] [Scalar: 0] +; CHECK: { Stmt_(bb2 => bb16)[i0] -> MemRef_A[i0] }; +; CHECK: ReadAccess := [Reduction Type: NONE] [Scalar: 0] +; CHECK: { Stmt_(bb2 => bb16)[i0] -> MemRef_A[-1 + i0] }; +; CHECK: ReadAccess := [Reduction Type: NONE] [Scalar: 0] +; CHECK: { Stmt_(bb2 => bb16)[i0] -> MemRef_A[-2 + i0] }; +; CHECK: MayWriteAccess := [Reduction Type: NONE] [Scalar: 0] +; CHECK: { Stmt_(bb2 => bb16)[i0] -> MemRef_A[i0] }; +; CHECK: } + +target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" + +define void @f(i32* %A) { +bb: + br label %bb1 + +bb1: ; preds = %bb17, %bb + %indvars.iv = phi i64 [ %indvars.iv.next, %bb17 ], [ 0, %bb ] + %exitcond = icmp ne i64 %indvars.iv, 1024 + br i1 %exitcond, label %bb2, label %bb18 + +bb2: ; preds = %bb1 + %tmp = getelementptr inbounds i32* %A, i64 %indvars.iv + %tmp3 = load i32* %tmp, align 4 + %tmp4 = icmp eq i32 %tmp3, 0 + br i1 %tmp4, label %bb16, label %bb5 + +bb5: ; preds = %bb2 + %tmp6 = add nsw i64 %indvars.iv, -1 + %tmp7 = getelementptr inbounds i32* %A, i64 %tmp6 + %tmp8 = load i32* %tmp7, align 4 + %tmp9 = icmp eq i32 %tmp8, 0 + br i1 %tmp9, label %bb15, label %bb10 + +bb10: ; preds = %bb5 + %tmp11 = add nsw i64 %indvars.iv, -2 + %tmp12 = getelementptr inbounds i32* %A, i64 %tmp11 + %tmp13 = load i32* %tmp12, align 4 + %tmp14 = getelementptr inbounds i32* %A, i64 %indvars.iv + store i32 %tmp13, i32* %tmp14, align 4 + br label %bb15 + +bb15: ; preds = %bb5, %bb10 + br label %bb16 + +bb16: ; preds = %bb2, %bb15 + br label %bb17 + +bb17: ; preds = %bb16 + %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1 + br label %bb1 + +bb18: ; preds = %bb1 + ret void +} Index: test/ScopInfo/non-affine-float-compare.ll =================================================================== --- /dev/null +++ test/ScopInfo/non-affine-float-compare.ll @@ -0,0 +1,63 @@ +; RUN: opt %loadPolly -polly-scops -polly-allow-nonaffine-branches -analyze < %s | FileCheck %s +; +; void f(float *A) { +; for (int i = 0; i < 1024; i++) +; if (A[i] == A[i - 1]) +; A[i]++; +; } +; +; CHECK: Function: f +; CHECK: Region: %bb1---%bb14 +; CHECK: Max Loop Depth: 1 +; CHECK: Statements { +; CHECK: Stmt_(bb2 => bb12) +; CHECK: Domain := +; CHECK: { Stmt_(bb2 => bb12)[i0] : i0 >= 0 and i0 <= 1023 }; +; CHECK: Scattering := +; CHECK: { Stmt_(bb2 => bb12)[i0] -> [i0] }; +; CHECK: ReadAccess := [Reduction Type: NONE] [Scalar: 0] +; CHECK: { Stmt_(bb2 => bb12)[i0] -> MemRef_A[i0] }; +; CHECK: ReadAccess := [Reduction Type: NONE] [Scalar: 0] +; CHECK: { Stmt_(bb2 => bb12)[i0] -> MemRef_A[-1 + i0] }; +; CHECK: ReadAccess := [Reduction Type: NONE] [Scalar: 0] +; CHECK: { Stmt_(bb2 => bb12)[i0] -> MemRef_A[i0] }; +; CHECK: MayWriteAccess := [Reduction Type: NONE] [Scalar: 0] +; CHECK: { Stmt_(bb2 => bb12)[i0] -> MemRef_A[i0] }; +; CHECK: } +target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" + +define void @f(float* %A) { +bb: + br label %bb1 + +bb1: ; preds = %bb13, %bb + %indvars.iv = phi i64 [ %indvars.iv.next, %bb13 ], [ 0, %bb ] + %exitcond = icmp ne i64 %indvars.iv, 1024 + br i1 %exitcond, label %bb2, label %bb14 + +bb2: ; preds = %bb1 + %tmp = getelementptr inbounds float* %A, i64 %indvars.iv + %tmp3 = load float* %tmp, align 4 + %tmp4 = add nsw i64 %indvars.iv, -1 + %tmp5 = getelementptr inbounds float* %A, i64 %tmp4 + %tmp6 = load float* %tmp5, align 4 + %tmp7 = fcmp oeq float %tmp3, %tmp6 + br i1 %tmp7, label %bb8, label %bb12 + +bb8: ; preds = %bb2 + %tmp9 = getelementptr inbounds float* %A, i64 %indvars.iv + %tmp10 = load float* %tmp9, align 4 + %tmp11 = fadd float %tmp10, 1.000000e+00 + store float %tmp11, float* %tmp9, align 4 + br label %bb12 + +bb12: ; preds = %bb8, %bb2 + br label %bb13 + +bb13: ; preds = %bb12 + %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1 + br label %bb1 + +bb14: ; preds = %bb1 + ret void +} Index: test/ScopInfo/non-affine-loop-condition.ll =================================================================== --- /dev/null +++ test/ScopInfo/non-affine-loop-condition.ll @@ -0,0 +1,67 @@ +; RUN: opt %loadPolly -polly-scops -polly-allow-nonaffine-branches -analyze < %s | FileCheck %s +; +; void f(int *A, int *C) { +; for (int i = 0; i < 1024; i++) { +; while (C[i]) +; A[i]++; +; } +; } +; +; CHECK: Function: f +; CHECK: Region: %bb1---%bb12 +; TODO: It would be nice to state max loop depth : 1 but it is hard to +; implement that in the current scheme and not imporant at all. However, +; in case the SCoP creation is changed we should keep this in mind. +; CHECK: Max Loop Depth: 2 +; CHECK-NOT: Max Loop Depth: 1 +; CHECK: Statements { +; CHECK: Stmt_(bb3 => bb10) +; CHECK: Domain := +; CHECK: { Stmt_(bb3 => bb10)[i0] : i0 >= 0 and i0 <= 1023 }; +; CHECK: Scattering := +; CHECK: { Stmt_(bb3 => bb10)[i0] -> [i0, 0] }; +; CHECK: ReadAccess := [Reduction Type: NONE] [Scalar: 0] +; CHECK: { Stmt_(bb3 => bb10)[i0] -> MemRef_C[i0] }; +; CHECK: ReadAccess := [Reduction Type: +] [Scalar: 0] +; CHECK: { Stmt_(bb3 => bb10)[i0] -> MemRef_A[i0] }; +; CHECK: MayWriteAccess := [Reduction Type: +] [Scalar: 0] +; CHECK: { Stmt_(bb3 => bb10)[i0] -> MemRef_A[i0] }; +; CHECK: } + +target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" + +define void @f(i32* %A, i32* %C) { +bb: + br label %bb1 + +bb1: ; preds = %bb11, %bb + %indvars.iv = phi i64 [ %indvars.iv.next, %bb11 ], [ 0, %bb ] + %exitcond = icmp ne i64 %indvars.iv, 1024 + br i1 %exitcond, label %bb2, label %bb12 + +bb2: ; preds = %bb1 + br label %bb3 + +bb3: ; preds = %bb6, %bb2 + %tmp = getelementptr inbounds i32* %C, i64 %indvars.iv + %tmp4 = load i32* %tmp, align 4 + %tmp5 = icmp eq i32 %tmp4, 0 + br i1 %tmp5, label %bb10, label %bb6 + +bb6: ; preds = %bb3 + %tmp7 = getelementptr inbounds i32* %A, i64 %indvars.iv + %tmp8 = load i32* %tmp7, align 4 + %tmp9 = add nsw i32 %tmp8, 1 + store i32 %tmp9, i32* %tmp7, align 4 + br label %bb3 + +bb10: ; preds = %bb3 + br label %bb11 + +bb11: ; preds = %bb10 + %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1 + br label %bb1 + +bb12: ; preds = %bb1 + ret void +}