Index: include/polly/ScopInfo.h =================================================================== --- include/polly/ScopInfo.h +++ include/polly/ScopInfo.h @@ -429,9 +429,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; @@ -449,7 +461,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(); @@ -489,14 +511,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: @@ -532,11 +559,24 @@ /// @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 Return true if this statement represents a single basic block. + bool isBlockStmt() const { return BB != nullptr; } + + /// @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; } + + /// @brief Return true if this statement represents a whole region. + bool isRegionStmt() const { return R != nullptr; } + const MemoryAccess &getAccessFor(const Instruction *Inst) const { MemoryAccess *A = lookupAccessFor(Inst); assert(A && "Cannot get memory access because it does not exist!"); @@ -549,7 +589,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; @@ -697,7 +742,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. /// @@ -719,12 +765,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/ScopInfo.cpp =================================================================== --- lib/Analysis/ScopInfo.cpp +++ lib/Analysis/ScopInfo.cpp @@ -798,15 +798,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 (isApproximated && Access.isWrite()) + Access.setMayWrite(); + MemAccs.push_back(new MemoryAccess(Access, AccessInst, this, SAI)); // We do not track locations for scalar memory accesses at the moment. @@ -895,7 +903,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()) { @@ -979,16 +987,39 @@ 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(); + for (BasicBlock *Block : R.blocks()) { + buildAccesses(tempScop, Block, Block != EntryBB); + 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]; @@ -997,20 +1028,23 @@ 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 /// -/// Check if the stored value for @p StoreMA is a binary operator with one or -/// two loads as operands. If the binary operand is commutative & associative, +/// Check if the stored value for @p StoreMA is a binary operator with one +/// or +/// two loads as operands. If the binary operand is commutative & +/// associative, /// used only once (by @p StoreMA) and its load operands are also used only /// once, we have found a possible reduction chain. It starts at an operand /// load and includes the binary operator and @p StoreMA. /// -/// Note: We allow only one use to ensure the load and binary operator cannot +/// Note: We allow only one use to ensure the load and binary operator +/// cannot /// escape this block or into any other store except @p StoreMA. void ScopStmt::collectCandiateReductionLoads( MemoryAccess *StoreMA, SmallVectorImpl &Loads) { @@ -1027,7 +1061,8 @@ if (BinOp->getNumUses() != 1) return; - // Skip if the opcode of the binary operator is not commutative/associative + // Skip if the opcode of the binary operator is not + // commutative/associative if (!BinOp->isCommutative() || !BinOp->isAssociative()) return; @@ -1058,11 +1093,16 @@ /// @brief Check for reductions in this ScopStmt /// -/// Iterate over all store memory accesses and check for valid binary reduction -/// like chains. For all candidates we check if they have the same base address -/// and there are no other accesses which overlap with them. The base address -/// check rules out impossible reductions candidates early. The overlap check, -/// together with the "only one user" check in collectCandiateReductionLoads, +/// Iterate over all store memory accesses and check for valid binary +/// reduction +/// like chains. For all candidates we check if they have the same base +/// address +/// and there are no other accesses which overlap with them. The base +/// address +/// check rules out impossible reductions candidates early. The overlap +/// check, +/// together with the "only one user" check in +/// collectCandiateReductionLoads, /// guarantees that none of the intermediate results will escape during /// execution of the loop nest. We basically check here that no other memory /// access can access the same memory as the potential reduction. @@ -1070,7 +1110,8 @@ SmallVector Loads; SmallVector, 4> Candidates; - // First collect candidate load-store reduction chains by iterating over all + // First collect candidate load-store reduction chains by iterating over + // all // stores and collecting possible reduction loads. for (MemoryAccess *StoreMA : MemAccs) { if (StoreMA->isRead()) @@ -1283,10 +1324,13 @@ // WARNING: This only holds if the assumptions we have taken do not reduce // the set of statement instances that are executed. Otherwise we // may run into a case where the iteration domains suggest that - // for a certain set of parameter constraints no code is executed, + // for a certain set of parameter constraints no code is + // executed, // but in the original program some computation would have been - // performed. In such a case, modifying the run-time conditions and - // possibly influencing the run-time check may cause certain scops + // performed. In such a case, modifying the run-time conditions + // and + // possibly influencing the run-time check may cause certain + // scops // to not be executed. // // Example: @@ -1298,7 +1342,8 @@ // A[i+p][j] = 1.0; // // we assume that the condition m <= 0 or (m >= 1 and p >= 0) holds as - // otherwise we would access out of bound data. Now, knowing that code is + // otherwise we would access out of bound data. Now, knowing that code + // is // only executed for the case m >= 0, it is sufficient to assume p >= 0. AssumedContext = isl_set_gist_params(AssumedContext, isl_union_set_params(getDomains())); @@ -1375,18 +1420,22 @@ bool Scop::buildAliasGroups(AliasAnalysis &AA) { // To create sound alias checks we perform the following steps: - // o) Use the alias analysis and an alias set tracker to build alias sets + // o) Use the alias analysis and an alias set tracker to build alias + // sets // for all memory accesses inside the SCoP. // o) For each alias set we then map the aliasing pointers back to the - // memory accesses we know, thus obtain groups of memory accesses which + // memory accesses we know, thus obtain groups of memory accesses + // which // might alias. // o) We divide each group based on the domains of the minimal/maximal - // accesses. That means two minimal/maximal accesses are only in a group + // accesses. That means two minimal/maximal accesses are only in a + // group // if their access domains intersect, otherwise they are in different // ones. // o) We split groups such that they contain at most one read only base // address. - // o) For each group with more than one base pointer we then compute minimal + // o) For each group with more than one base pointer we then compute + // minimal // and maximal accesses to each array in this group. using AliasGroupTy = SmallVector; @@ -1486,7 +1535,8 @@ } // If we have both read only and non read only base pointers we combine - // the non read only ones with exactly one read only one at a time into a + // the non read only ones with exactly one read only one at a time into + // a // new alias group and clear the old alias group in the end. for (const auto &ReadOnlyPair : ReadOnlyPairs) { AliasGroupTy AGNonReadOnly = AG; @@ -1583,10 +1633,11 @@ } 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)) { IslCtx = Context; + buildContext(); SmallVector NestLoops; @@ -1596,7 +1647,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(); @@ -1867,9 +1918,39 @@ 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) { + if (SD.isNonAffineSubRegion(&CurRegion, &getRegion())) + return addScopStmt(nullptr, const_cast(&CurRegion), tempScop, + CurRegion, NestLoops, Scatter); + Loop *L = castToLoop(CurRegion, LI); if (L) @@ -1881,24 +1962,15 @@ 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()) { + buildScop(tempScop, *I->getNodeAs(), 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) @@ -1932,6 +2004,7 @@ AU.addRequired(); AU.addRequired(); AU.addRequired(); + AU.addRequired(); AU.addRequired(); AU.addRequired(); AU.setPreservesAll(); @@ -1960,6 +2033,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); @@ -1970,7 +2044,7 @@ return false; } - scop = new Scop(*tempScop, LI, SE, ctx); + scop = new Scop(*tempScop, LI, SE, SD, ctx); if (!PollyUseRuntimeAliasChecks) { // Statistics. @@ -2006,10 +2080,12 @@ DEBUG(dbgs() << "\n\nNOTE: Run time checks for " << scop->getNameStr() - << " could not be created as the number of parameters involved is too " + << " could not be created as the number of parameters involved is " + "too " "high. The SCoP will be " "dismissed.\nUse:\n\t--polly-rtc-max-parameters=X\nto adjust the " - "maximal number of parameters but be advised that the compile time " + "maximal number of parameters but be advised that the compile " + "time " "might increase exponentially.\n\n"); delete scop; @@ -2028,6 +2104,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,24 @@ if (Br->isUnconditional()) continue; + DominatorBrBlocks.push_back(BBNode->getBlock()); + } + + RegionInfo *RI = R.getRegionInfo(); + // Iterate in reverse order over the dominating blocks. Until a non-affine + // branch was encountered add all conditions collected. 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->isNonAffineSubRegion(RI->getRegionFor(BBNode), &R)) + break; + BasicBlock *TrueBB = Br->getSuccessor(0), *FalseBB = Br->getSuccessor(1); // Is BB on the ELSE side of the branch? @@ -365,7 +385,7 @@ for (const auto &BB : R.blocks()) { buildAccessFunctions(R, *BB); - buildCondition(BB, R.getEntry()); + buildCondition(BB, R); } return TScop; Index: test/ScopInfo/NonAffine/non_affine_conditional_nested.ll =================================================================== --- /dev/null +++ test/ScopInfo/NonAffine/non_affine_conditional_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/NonAffine/non_affine_float_compare.ll =================================================================== --- /dev/null +++ test/ScopInfo/NonAffine/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 +}