Index: include/polly/ScopInfo.h =================================================================== --- include/polly/ScopInfo.h +++ include/polly/ScopInfo.h @@ -1112,6 +1112,9 @@ ScopStmt(const ScopStmt &) = delete; const ScopStmt &operator=(const ScopStmt &) = delete; + /// Create the ScopStmt from another ScopStmt. + ScopStmt(ScopStmt *Original, int CopyNo); + /// Create the ScopStmt from a BasicBlock. ScopStmt(Scop &parent, BasicBlock &bb, Loop *SurroundingLoop); @@ -2085,6 +2088,9 @@ /// @return The count of copy statements added to this Scop. unsigned getCopyStmtsNum() { return CopyStmtsNum; } + /// Create a new SCoP statement for @p ScopStmt. + void copyScopStmt(ScopStmt *NewStmt, int CopyNo); + /// Create a new copy statement. /// /// A new statement will be created and added to the statement vector. Index: lib/Analysis/ScopInfo.cpp =================================================================== --- lib/Analysis/ScopInfo.cpp +++ lib/Analysis/ScopInfo.cpp @@ -1573,6 +1573,21 @@ } } +ScopStmt::ScopStmt(ScopStmt *Original, int CopyNo) + : Parent(*(Original->getParent())), InvalidDomain(nullptr), Domain(nullptr), + BB(Original->getBasicBlock()), R(Original->getRegion()), Build(nullptr), + SurroundingLoop(Original->getSurroundingLoop()) { + BaseName = getIslCompatibleName(Original->getBaseName(), "_copy_no_", + std::to_string(CopyNo)); + Domain = Original->getDomain(); + Domain = isl_set_set_tuple_name(Domain, BaseName.c_str()); + isl_id *Id = isl_id_alloc(getIslCtx(), getBaseName(), this); + Domain = isl_set_set_tuple_id(Domain, Id); + for (MemoryAccess *Access : Original->MemAccs) { + addAccess(Access); + } +} + ScopStmt::ScopStmt(Scop &parent, Region &R, Loop *SurroundingLoop) : Parent(parent), InvalidDomain(nullptr), Domain(nullptr), BB(nullptr), R(&R), Build(nullptr), SurroundingLoop(SurroundingLoop) { @@ -4441,6 +4456,11 @@ return isl_multi_union_pw_aff_from_union_pw_multi_aff(Data.Res); } +void Scop::copyScopStmt(ScopStmt *NewStmt, int CopyNo) { + assert(NewStmt && "Unexpected nullptr!"); + Stmts.emplace_back(NewStmt, CopyNo); +} + void Scop::addScopStmt(BasicBlock *BB, Loop *SurroundingLoop) { assert(BB && "Unexpected nullptr!"); Stmts.emplace_back(*this, *BB, SurroundingLoop); Index: lib/Exchange/JSONExporter.cpp =================================================================== --- lib/Exchange/JSONExporter.cpp +++ lib/Exchange/JSONExporter.cpp @@ -16,6 +16,7 @@ #include "polly/Options.h" #include "polly/ScopInfo.h" #include "polly/ScopPass.h" +#include "polly/Support/GICHelper.h" #include "polly/Support/ScopLocation.h" #include "llvm/ADT/Statistic.h" #include "llvm/Analysis/RegionInfo.h" @@ -29,6 +30,7 @@ #include "isl/printer.h" #include "isl/set.h" #include "isl/union_map.h" +#include "isl/union_set.h" #include "json/reader.h" #include "json/writer.h" #include @@ -287,6 +289,126 @@ return true; } +// Struct containing the info required for the copying of the statements in the +// scop and the schedule. +struct copy_info { + isl_union_map *NewSchedule; + Scop *S; +}; + +// finds the ScopStmt corresponding to Map. +ScopStmt *findStmtFromMap(Scop *S, isl_map *Map) { + isl_map *Universe; + isl_set *StmtDomain, *MapDomain; + ScopStmt *CurrentStmt; + + Universe = isl_map_universe(isl_map_get_space(Map)); + MapDomain = isl_map_domain(Universe); + + for (ScopStmt &Stmt : *S) { + StmtDomain = isl_map_domain(Stmt.getSchedule()); + if (isl_set_is_equal(StmtDomain, MapDomain)) { + CurrentStmt = &Stmt; + isl_set_free(StmtDomain); + break; + } + isl_set_free(StmtDomain); + } + + isl_set_free(MapDomain); + isl_map_free(Map); + + return CurrentStmt; +} + +// Transforms the schedule of the scopstmt, adds it to newSchedule and adds the +// required ScopStmts to S. +static isl_stat makeStmtSingleValued(__isl_take isl_map *MapToAdd, void *User) { + struct copy_info *Data = (copy_info *)User; + isl_union_map *NewSchedule = Data->NewSchedule; + Scop *S = Data->S; + + isl_map *LexMin; + ScopStmt *CurrentStmt; + std::string name; + int i = 0; + + CurrentStmt = findStmtFromMap(S, isl_map_copy(MapToAdd)); + + while (!isl_map_is_empty(MapToAdd)) { + assert(i < 11 && "More than 10 copies required!"); + + assert((LexMin = isl_map_lexmin(isl_map_copy(MapToAdd))) && + "Map is not lower-bounded!"); + MapToAdd = isl_map_subtract(MapToAdd, isl_map_copy(LexMin)); + + if (i != 0) { + name = getIslCompatibleName( + (std::string)isl_map_get_tuple_name(LexMin, isl_dim_in), "_copy_no_", + std::to_string(i)); + LexMin = isl_map_set_tuple_name(LexMin, isl_dim_in, name.c_str()); + S->copyScopStmt(CurrentStmt, i); + } + assert((NewSchedule = isl_union_map_add_map(NewSchedule, LexMin)) && + "Adding to schedule failed!"); + + i++; + } + isl_map_free(MapToAdd); + + return isl_stat_ok; +} + +/// Makes a single-valued schedule and adds the required ScopStmts to the +/// Scop. +/// +/// @param OldSchedule The non-single-valued schedule to be made single-valued. +/// +/// @param S The Scop where the new ScopStmts need to be added. +/// +/// @returns isl_union_map the new single valued schedule. +isl_union_map *makeScheduleSingleValued(isl_union_map *OldSchedule, Scop &S) { + isl_union_map *NewSchedule = + isl_union_map_empty(isl_union_map_get_space(OldSchedule)); + struct copy_info CopyData = {NewSchedule, &S}; + + assert(isl_union_map_foreach_map(OldSchedule, &makeStmtSingleValued, + &CopyData) >= 0 && + "error during fixing schedule!"); + + DEBUG(dbgs() << "\nNew Map:\n" << CopyData.NewSchedule << "\n\n"); + + isl_union_map_free(OldSchedule); + return CopyData.NewSchedule; +} + +static isl_stat basicMapIsBounded(__isl_take isl_basic_map *Map, void *User) { + if (isl_basic_map_image_is_bounded(Map)) { + isl_basic_map_free(Map); + return isl_stat_ok; + } + isl_basic_map_free(Map); + return isl_stat_error; +} + +static isl_stat mapIsBounded(__isl_take isl_map *Map, void *User) { + if (isl_map_foreach_basic_map(Map, basicMapIsBounded, NULL) == isl_stat_ok) { + isl_map_free(Map); + DEBUG(dbgs() << "\nbounded map found!\n"); + return isl_stat_ok; + } + isl_map_free(Map); + DEBUG(dbgs() << "\nnon-bounded map found!\n"); + return isl_stat_error; +} + +bool unionMapIsBounded(isl_union_map *Map) { + if (isl_union_map_foreach_map(Map, &mapIsBounded, NULL) == isl_stat_ok) { + return true; + } + return false; +} + bool JSONImporter::importSchedule(Scop &S, Json::Value &JScop, const Dependences &D) { StatementToIslMapTy NewSchedule; @@ -328,6 +450,23 @@ ScheduleMap = isl_union_map_add_map(ScheduleMap, Stmt.getSchedule()); } + // Check if the map is single valued. + if (!isl_union_map_is_single_valued(ScheduleMap)) { + DEBUG( + dbgs() << "JScop file contains a schedule that is not single valued\n"); + + // Not Yet Finished, when ScheduleMap can be fixed by + // makeScheduleSingleValued, the new ScheduleMap will be passed. + if (!unionMapIsBounded(ScheduleMap)) { + DEBUG(dbgs() << "JScop file contains a schedule that is not bounded\n"); + isl_union_map_free(ScheduleMap); + return false; + } + ScheduleMap = makeScheduleSingleValued(ScheduleMap, S); + isl_union_map_free(ScheduleMap); + return false; + } + S.setSchedule(ScheduleMap); return true; Index: test/ScopDetect/double_convolution___%for.cond1.preheader---%for.end37.jscop.notbound =================================================================== --- test/ScopDetect/double_convolution___%for.cond1.preheader---%for.end37.jscop.notbound +++ test/ScopDetect/double_convolution___%for.cond1.preheader---%for.end37.jscop.notbound @@ -0,0 +1,139 @@ +{ + "arrays" : [ + { + "name" : "MemRef_k1_idata", + "sizes" : [ "*" ], + "type" : "i32" + }, + { + "name" : "MemRef_l1_ucdata", + "sizes" : [ "*" ], + "type" : "i8" + }, + { + "name" : "MemRef_l2_ucdata", + "sizes" : [ "*" ], + "type" : "i8" + }, + { + "name" : "MemRef_k2_idata", + "sizes" : [ "*" ], + "type" : "i32" + }, + { + "name" : "MemRef_l3_ucdata", + "sizes" : [ "*" ], + "type" : "i8" + } + ], + "context" : "{ : }", + "name" : "%for.cond1.preheader---%for.end37", + "statements" : [ + { + "accesses" : [ + { + "kind" : "write", + "relation" : "{ Stmt_for_cond1_preheader[i0] -> MemRef_output1_04__phi[] }" + } + ], + "domain" : "{ Stmt_for_cond1_preheader[i0] : 0 <= i0 <= 95 }", + "name" : "Stmt_for_cond1_preheader", + "schedule" : "{ Stmt_for_cond1_preheader[i0] -> [t0, 0, i0, 0, 0] : 0 <= t0 <= i0 <= t0 + 2 <= 95}" + }, + { + "accesses" : [ + { + "kind" : "write", + "relation" : "{ Stmt_for_inc[i0, i1] -> MemRef_output1_04__phi[] }" + }, + { + "kind" : "read", + "relation" : "{ Stmt_for_inc[i0, i1] -> MemRef_output1_04__phi[] }" + }, + { + "kind" : "read", + "relation" : "{ Stmt_for_inc[i0, i1] -> MemRef_k1_idata[i1] }" + }, + { + "kind" : "read", + "relation" : "{ Stmt_for_inc[i0, i1] -> MemRef_l1_ucdata[i0 + i1] }" + }, + { + "kind" : "write", + "relation" : "{ Stmt_for_inc[i0, i1] -> MemRef_add6_lcssa__phi[] }" + } + ], + "domain" : "{ Stmt_for_inc[i0, i1] : 0 <= i0 <= 95 and 0 <= i1 <= 4 }", + "name" : "Stmt_for_inc", + "schedule" : "{ Stmt_for_inc[i0, i1] -> [t0, 0, i0, 1, i1] : 0 <= t0 <= i0 <= t0 + 2 <= 95}" + }, + { + "accesses" : [ + { + "kind" : "read", + "relation" : "{ Stmt_for_end[i0] -> MemRef_add6_lcssa__phi[] }" + }, + { + "kind" : "write", + "relation" : "{ Stmt_for_end[i0] -> MemRef_l2_ucdata[i0] }" + } + ], + "domain" : "{ Stmt_for_end[i0] : 0 <= i0 <= 95 }", + "name" : "Stmt_for_end", + "schedule" : "{ Stmt_for_end[i0] -> [t0, 0, i0, 2, 0] : 0 <= t0 <= i0 <= t0 + 2 <= 95}" + }, + { + "accesses" : [ + { + "kind" : "write", + "relation" : "{ Stmt_for_cond17_preheader[i0] -> MemRef_output2_01__phi[] }" + } + ], + "domain" : "{ Stmt_for_cond17_preheader[i0] : 0 <= i0 <= 93 }", + "name" : "Stmt_for_cond17_preheader", + "schedule" : "{ Stmt_for_cond17_preheader[i0] -> [i0, 1, t0, 0, 0] : 0 <= t0}" + }, + { + "accesses" : [ + { + "kind" : "write", + "relation" : "{ Stmt_for_inc29[i0, i1] -> MemRef_output2_01__phi[] }" + }, + { + "kind" : "read", + "relation" : "{ Stmt_for_inc29[i0, i1] -> MemRef_output2_01__phi[] }" + }, + { + "kind" : "read", + "relation" : "{ Stmt_for_inc29[i0, i1] -> MemRef_k2_idata[i1] }" + }, + { + "kind" : "read", + "relation" : "{ Stmt_for_inc29[i0, i1] -> MemRef_l2_ucdata[i0 + i1] }" + }, + { + "kind" : "write", + "relation" : "{ Stmt_for_inc29[i0, i1] -> MemRef_add28_lcssa__phi[] }" + } + ], + "domain" : "{ Stmt_for_inc29[i0, i1] : 0 <= i0 <= 93 and 0 <= i1 <= 2 }", + "name" : "Stmt_for_inc29", + "schedule" : "{ Stmt_for_inc29[i0, i1] -> [i0, 1, t0, 1, i1] : 0 <= t0}" + }, + { + "accesses" : [ + { + "kind" : "read", + "relation" : "{ Stmt_for_end31[i0] -> MemRef_add28_lcssa__phi[] }" + }, + { + "kind" : "write", + "relation" : "{ Stmt_for_end31[i0] -> MemRef_l3_ucdata[i0] }" + } + ], + "domain" : "{ Stmt_for_end31[i0] : 0 <= i0 <= 93 }", + "name" : "Stmt_for_end31", + "schedule" : "{ Stmt_for_end31[i0] -> [i0, 1, t0, 2, 0] : 0 <= t0}" + } + ] +} Index: test/ScopDetect/double_convolution___%for.cond1.preheader---%for.end37.jscop.recompute =================================================================== --- test/ScopDetect/double_convolution___%for.cond1.preheader---%for.end37.jscop.recompute +++ test/ScopDetect/double_convolution___%for.cond1.preheader---%for.end37.jscop.recompute @@ -0,0 +1,139 @@ +{ + "arrays" : [ + { + "name" : "MemRef_k1_idata", + "sizes" : [ "*" ], + "type" : "i32" + }, + { + "name" : "MemRef_l1_ucdata", + "sizes" : [ "*" ], + "type" : "i8" + }, + { + "name" : "MemRef_l2_ucdata", + "sizes" : [ "*" ], + "type" : "i8" + }, + { + "name" : "MemRef_k2_idata", + "sizes" : [ "*" ], + "type" : "i32" + }, + { + "name" : "MemRef_l3_ucdata", + "sizes" : [ "*" ], + "type" : "i8" + } + ], + "context" : "{ : }", + "name" : "%for.cond1.preheader---%for.end37", + "statements" : [ + { + "accesses" : [ + { + "kind" : "write", + "relation" : "{ Stmt_for_cond1_preheader[i0] -> MemRef_output1_04__phi[] }" + } + ], + "domain" : "{ Stmt_for_cond1_preheader[i0] : 0 <= i0 <= 95 }", + "name" : "Stmt_for_cond1_preheader", + "schedule" : "{ Stmt_for_cond1_preheader[i0] -> [t0, 0, i0, 0, 0] : 0 <= t0 <= i0 <= t0 + 2 <= 95}" + }, + { + "accesses" : [ + { + "kind" : "write", + "relation" : "{ Stmt_for_inc[i0, i1] -> MemRef_output1_04__phi[] }" + }, + { + "kind" : "read", + "relation" : "{ Stmt_for_inc[i0, i1] -> MemRef_output1_04__phi[] }" + }, + { + "kind" : "read", + "relation" : "{ Stmt_for_inc[i0, i1] -> MemRef_k1_idata[i1] }" + }, + { + "kind" : "read", + "relation" : "{ Stmt_for_inc[i0, i1] -> MemRef_l1_ucdata[i0 + i1] }" + }, + { + "kind" : "write", + "relation" : "{ Stmt_for_inc[i0, i1] -> MemRef_add6_lcssa__phi[] }" + } + ], + "domain" : "{ Stmt_for_inc[i0, i1] : 0 <= i0 <= 95 and 0 <= i1 <= 4 }", + "name" : "Stmt_for_inc", + "schedule" : "{ Stmt_for_inc[i0, i1] -> [t0, 0, i0, 1, i1] : 0 <= t0 <= i0 <= t0 + 2 <= 95}" + }, + { + "accesses" : [ + { + "kind" : "read", + "relation" : "{ Stmt_for_end[i0] -> MemRef_add6_lcssa__phi[] }" + }, + { + "kind" : "write", + "relation" : "{ Stmt_for_end[i0] -> MemRef_l2_ucdata[i0] }" + } + ], + "domain" : "{ Stmt_for_end[i0] : 0 <= i0 <= 95 }", + "name" : "Stmt_for_end", + "schedule" : "{ Stmt_for_end[i0] -> [t0, 0, i0, 2, 0] : 0 <= t0 <= i0 <= t0 + 2 <= 95}" + }, + { + "accesses" : [ + { + "kind" : "write", + "relation" : "{ Stmt_for_cond17_preheader[i0] -> MemRef_output2_01__phi[] }" + } + ], + "domain" : "{ Stmt_for_cond17_preheader[i0] : 0 <= i0 <= 93 }", + "name" : "Stmt_for_cond17_preheader", + "schedule" : "{ Stmt_for_cond17_preheader[i0] -> [i0, 1, 0, 0, 0] }" + }, + { + "accesses" : [ + { + "kind" : "write", + "relation" : "{ Stmt_for_inc29[i0, i1] -> MemRef_output2_01__phi[] }" + }, + { + "kind" : "read", + "relation" : "{ Stmt_for_inc29[i0, i1] -> MemRef_output2_01__phi[] }" + }, + { + "kind" : "read", + "relation" : "{ Stmt_for_inc29[i0, i1] -> MemRef_k2_idata[i1] }" + }, + { + "kind" : "read", + "relation" : "{ Stmt_for_inc29[i0, i1] -> MemRef_l2_ucdata[i0 + i1] }" + }, + { + "kind" : "write", + "relation" : "{ Stmt_for_inc29[i0, i1] -> MemRef_add28_lcssa__phi[] }" + } + ], + "domain" : "{ Stmt_for_inc29[i0, i1] : 0 <= i0 <= 93 and 0 <= i1 <= 2 }", + "name" : "Stmt_for_inc29", + "schedule" : "{ Stmt_for_inc29[i0, i1] -> [i0, 1, 0, 1, i1] }" + }, + { + "accesses" : [ + { + "kind" : "read", + "relation" : "{ Stmt_for_end31[i0] -> MemRef_add28_lcssa__phi[] }" + }, + { + "kind" : "write", + "relation" : "{ Stmt_for_end31[i0] -> MemRef_l3_ucdata[i0] }" + } + ], + "domain" : "{ Stmt_for_end31[i0] : 0 <= i0 <= 93 }", + "name" : "Stmt_for_end31", + "schedule" : "{ Stmt_for_end31[i0] -> [i0, 1, 0, 2, 0] }" + } + ] +} Index: test/ScopDetect/recomputation.ll =================================================================== --- test/ScopDetect/recomputation.ll +++ test/ScopDetect/recomputation.ll @@ -0,0 +1,120 @@ +; RUN: opt -basicaa -polly-import-jscop -polly-import-jscop-dir=%S -polly-import-jscop-postfix=recompute -polly-ast -analyze -disable-polly-legality -debug < %s 2>&1 | FileCheck %s + +; void double_convolution(unsigned char* restrict l1_ucdata, int* restrict k1_idata, unsigned char* restrict l2_ucdata, +; int* restrict k2_idata, unsigned char* restrict l3_ucdata) { +; +; for (int m1 = 0; m1 < 96; m1++){ +; int output1=0; +; for(int k1 = 0; k1 < 5; k1++){ +; output1 += ((int) l1_ucdata[ m1 + k1 ]) * k1_idata[k1]; +; } +; l2_ucdata[m1]= output1; +; } +; +; for (int m2 = 0; m2 < 94; m2++){ +; int output2=0; +; for(int k2 = 0; k2 < 3; k2++){ +; output2 += ((int) l2_ucdata[ m2 + k2 ]) * k2_idata[k2]; +; } +; l3_ucdata[m2]= output2; +; } +;} + +target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" + +define void @double_convolution(i8* noalias %l1_ucdata, i32* noalias %k1_idata, i8* noalias %l2_ucdata, i32* noalias %k2_idata, i8* noalias %l3_ucdata) #0 { +entry: + br label %entry.split + +entry.split: ; preds = %entry + br label %for.cond1.preheader + +for.cond1.preheader: ; preds = %entry.split, %for.end + %indvars.iv15 = phi i64 [ 0, %entry.split ], [ %indvars.iv.next16, %for.end ] + br label %for.inc + +for.cond13.preheader: ; preds = %for.end + br label %for.cond17.preheader + +for.inc: ; preds = %for.cond1.preheader, %for.inc + %indvars.iv11 = phi i64 [ 0, %for.cond1.preheader ], [ %indvars.iv.next12, %for.inc ] + %output1.04 = phi i32 [ 0, %for.cond1.preheader ], [ %add6, %for.inc ] + %arrayidx5 = getelementptr inbounds i32, i32* %k1_idata, i64 %indvars.iv11 + %0 = load i32, i32* %arrayidx5, align 4 + %1 = add nuw nsw i64 %indvars.iv11, %indvars.iv15 + %arrayidx = getelementptr inbounds i8, i8* %l1_ucdata, i64 %1 + %2 = load i8, i8* %arrayidx, align 1 + %conv = zext i8 %2 to i32 + %mul = mul nsw i32 %0, %conv + %add6 = add nsw i32 %mul, %output1.04 + %indvars.iv.next12 = add nuw nsw i64 %indvars.iv11, 1 + %exitcond14 = icmp ne i64 %indvars.iv.next12, 5 + br i1 %exitcond14, label %for.inc, label %for.end + +for.end: ; preds = %for.inc + %add6.lcssa = phi i32 [ %add6, %for.inc ] + %conv7 = trunc i32 %add6.lcssa to i8 + %arrayidx9 = getelementptr inbounds i8, i8* %l2_ucdata, i64 %indvars.iv15 + store i8 %conv7, i8* %arrayidx9, align 1 + %indvars.iv.next16 = add nuw nsw i64 %indvars.iv15, 1 + %exitcond17 = icmp ne i64 %indvars.iv.next16, 96 + br i1 %exitcond17, label %for.cond1.preheader, label %for.cond13.preheader + +for.cond17.preheader: ; preds = %for.cond13.preheader, %for.end31 + %indvars.iv8 = phi i64 [ 0, %for.cond13.preheader ], [ %indvars.iv.next9, %for.end31 ] + br label %for.inc29 + +for.inc29: ; preds = %for.cond17.preheader, %for.inc29 + %indvars.iv = phi i64 [ 0, %for.cond17.preheader ], [ %indvars.iv.next, %for.inc29 ] + %output2.01 = phi i32 [ 0, %for.cond17.preheader ], [ %add28, %for.inc29 ] + %arrayidx26 = getelementptr inbounds i32, i32* %k2_idata, i64 %indvars.iv + %3 = load i32, i32* %arrayidx26, align 4 + %4 = add nuw nsw i64 %indvars.iv, %indvars.iv8 + %arrayidx23 = getelementptr inbounds i8, i8* %l2_ucdata, i64 %4 + %5 = load i8, i8* %arrayidx23, align 1 + %conv24 = zext i8 %5 to i32 + %mul27 = mul nsw i32 %3, %conv24 + %add28 = add nsw i32 %mul27, %output2.01 + %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1 + %exitcond = icmp ne i64 %indvars.iv.next, 3 + br i1 %exitcond, label %for.inc29, label %for.end31 + +for.end31: ; preds = %for.inc29 + %add28.lcssa = phi i32 [ %add28, %for.inc29 ] + %conv32 = trunc i32 %add28.lcssa to i8 + %arrayidx34 = getelementptr inbounds i8, i8* %l3_ucdata, i64 %indvars.iv8 + store i8 %conv32, i8* %arrayidx34, align 1 + %indvars.iv.next9 = add nuw nsw i64 %indvars.iv8, 1 + %exitcond10 = icmp ne i64 %indvars.iv.next9, 94 + br i1 %exitcond10, label %for.cond17.preheader, label %for.end37 + +for.end37: ; preds = %for.end31 + ret void +} + + +; CHECK: JScop file contains a schedule that is not single valued +; CHECK-NOT: JScop file contains a schedule that is not bounded +; CHECK: { Stmt_for_cond1_preheader_copy_no_1[i0] -> [t0 = -1 + i0, 0, i0, 0, 0] : 2 <= i0 <= 94; +; CHECK-SAME: Stmt_for_cond1_preheader_copy_no_1[i0 = 1] -> [t0 = 1, 0, 1, 0, 0]; +; CHECK-SAME: Stmt_for_inc29[i0, i1] -> [i0, 1, 0, 1, i1]; +; CHECK-SAME: Stmt_for_cond17_preheader[i0] -> [i0, 1, 0, 0, 0]; +; CHECK-SAME: Stmt_for_cond1_preheader_copy_no_2[i0] -> [t0 = i0, 0, i0, 0, 0] : 2 <= i0 <= 93; +; CHECK-SAME: Stmt_for_inc[i0, i1] -> [t0 = 0, 0, i0, 1, i1] : 0 <= i0 <= 1; +; CHECK-SAME: Stmt_for_inc[i0, i1] -> [t0 = -2 + i0, 0, i0, 1, i1] : 2 <= i0 <= 95; +; CHECK-SAME: Stmt_for_inc_copy_no_1[i0, i1] -> [t0 = -1 + i0, 0, i0, 1, i1] : 2 <= i0 <= 94; +; CHECK-SAME: Stmt_for_inc_copy_no_1[i0 = 1, i1] -> [t0 = 1, 0, 1, 1, i1]; +; CHECK-SAME: Stmt_for_end31[i0] -> [i0, 1, 0, 2, 0]; +; CHECK-SAME: Stmt_for_end_copy_no_1[i0] -> [t0 = -1 + i0, 0, i0, 2, 0] : 2 <= i0 <= 94; +; CHECK-SAME: Stmt_for_end_copy_no_1[i0 = 1] -> [t0 = 1, 0, 1, 2, 0]; +; CHECK-SAME: Stmt_for_inc_copy_no_2[i0, i1] -> [t0 = i0, 0, i0, 1, i1] : 2 <= i0 <= 93; +; CHECK-SAME: Stmt_for_end[i0] -> [t0 = 0, 0, i0, 2, 0] : 0 <= i0 <= 1; +; CHECK-SAME: Stmt_for_end[i0] -> [t0 = -2 + i0, 0, i0, 2, 0] : 2 <= i0 <= 95; +; CHECK-SAME: Stmt_for_cond1_preheader[i0] -> [t0 = 0, 0, i0, 0, 0] : 0 <= i0 <= 1; +; CHECK-SAME: Stmt_for_cond1_preheader[i0] -> [t0 = -2 + i0, 0, i0, 0, 0] : 2 <= i0 <= 95; +; CHECK-SAME: Stmt_for_end_copy_no_2[i0] -> [t0 = i0, 0, i0, 2, 0] : 2 <= i0 <= 93 } +; CHECK: Function: double_convolution +; CHECK-NOT: Stmt_for_inc29_copy_no_1 +; CHECK: Stmt_for_inc_copy_no_1 +; CHECK: Stmt_for_inc_copy_no_2 +; CHECK-NOT: Stmt_for_inc29_copy_no_1 Index: test/ScopDetect/recomputation_unbound.ll =================================================================== --- test/ScopDetect/recomputation_unbound.ll +++ test/ScopDetect/recomputation_unbound.ll @@ -0,0 +1,99 @@ +; RUN: opt -basicaa -polly-import-jscop -polly-import-jscop-dir=%S -polly-import-jscop-postfix=notbound -polly-ast -analyze -disable-polly-legality -debug < %s 2>&1 | FileCheck %s + +; void double_convolution(unsigned char* restrict l1_ucdata, int* restrict k1_idata, unsigned char* restrict l2_ucdata, +; int* restrict k2_idata, unsigned char* restrict l3_ucdata) { +; +; for (int m1 = 0; m1 < 96; m1++){ +; int output1=0; +; for(int k1 = 0; k1 < 5; k1++){ +; output1 += ((int) l1_ucdata[ m1 + k1 ]) * k1_idata[k1]; +; } +; l2_ucdata[m1]= output1; +; } +; +; for (int m2 = 0; m2 < 94; m2++){ +; int output2=0; +; for(int k2 = 0; k2 < 3; k2++){ +; output2 += ((int) l2_ucdata[ m2 + k2 ]) * k2_idata[k2]; +; } +; l3_ucdata[m2]= output2; +; } +;} + +target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" + +define void @double_convolution(i8* noalias %l1_ucdata, i32* noalias %k1_idata, i8* noalias %l2_ucdata, i32* noalias %k2_idata, i8* noalias %l3_ucdata) #0 { +entry: + br label %entry.split + +entry.split: ; preds = %entry + br label %for.cond1.preheader + +for.cond1.preheader: ; preds = %entry.split, %for.end + %indvars.iv15 = phi i64 [ 0, %entry.split ], [ %indvars.iv.next16, %for.end ] + br label %for.inc + +for.cond13.preheader: ; preds = %for.end + br label %for.cond17.preheader + +for.inc: ; preds = %for.cond1.preheader, %for.inc + %indvars.iv11 = phi i64 [ 0, %for.cond1.preheader ], [ %indvars.iv.next12, %for.inc ] + %output1.04 = phi i32 [ 0, %for.cond1.preheader ], [ %add6, %for.inc ] + %arrayidx5 = getelementptr inbounds i32, i32* %k1_idata, i64 %indvars.iv11 + %0 = load i32, i32* %arrayidx5, align 4 + %1 = add nuw nsw i64 %indvars.iv11, %indvars.iv15 + %arrayidx = getelementptr inbounds i8, i8* %l1_ucdata, i64 %1 + %2 = load i8, i8* %arrayidx, align 1 + %conv = zext i8 %2 to i32 + %mul = mul nsw i32 %0, %conv + %add6 = add nsw i32 %mul, %output1.04 + %indvars.iv.next12 = add nuw nsw i64 %indvars.iv11, 1 + %exitcond14 = icmp ne i64 %indvars.iv.next12, 5 + br i1 %exitcond14, label %for.inc, label %for.end + +for.end: ; preds = %for.inc + %add6.lcssa = phi i32 [ %add6, %for.inc ] + %conv7 = trunc i32 %add6.lcssa to i8 + %arrayidx9 = getelementptr inbounds i8, i8* %l2_ucdata, i64 %indvars.iv15 + store i8 %conv7, i8* %arrayidx9, align 1 + %indvars.iv.next16 = add nuw nsw i64 %indvars.iv15, 1 + %exitcond17 = icmp ne i64 %indvars.iv.next16, 96 + br i1 %exitcond17, label %for.cond1.preheader, label %for.cond13.preheader + +for.cond17.preheader: ; preds = %for.cond13.preheader, %for.end31 + %indvars.iv8 = phi i64 [ 0, %for.cond13.preheader ], [ %indvars.iv.next9, %for.end31 ] + br label %for.inc29 + +for.inc29: ; preds = %for.cond17.preheader, %for.inc29 + %indvars.iv = phi i64 [ 0, %for.cond17.preheader ], [ %indvars.iv.next, %for.inc29 ] + %output2.01 = phi i32 [ 0, %for.cond17.preheader ], [ %add28, %for.inc29 ] + %arrayidx26 = getelementptr inbounds i32, i32* %k2_idata, i64 %indvars.iv + %3 = load i32, i32* %arrayidx26, align 4 + %4 = add nuw nsw i64 %indvars.iv, %indvars.iv8 + %arrayidx23 = getelementptr inbounds i8, i8* %l2_ucdata, i64 %4 + %5 = load i8, i8* %arrayidx23, align 1 + %conv24 = zext i8 %5 to i32 + %mul27 = mul nsw i32 %3, %conv24 + %add28 = add nsw i32 %mul27, %output2.01 + %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1 + %exitcond = icmp ne i64 %indvars.iv.next, 3 + br i1 %exitcond, label %for.inc29, label %for.end31 + +for.end31: ; preds = %for.inc29 + %add28.lcssa = phi i32 [ %add28, %for.inc29 ] + %conv32 = trunc i32 %add28.lcssa to i8 + %arrayidx34 = getelementptr inbounds i8, i8* %l3_ucdata, i64 %indvars.iv8 + store i8 %conv32, i8* %arrayidx34, align 1 + %indvars.iv.next9 = add nuw nsw i64 %indvars.iv8, 1 + %exitcond10 = icmp ne i64 %indvars.iv.next9, 94 + br i1 %exitcond10, label %for.cond17.preheader, label %for.end37 + +for.end37: ; preds = %for.end31 + ret void +} + + +; CHECK: JScop file contains a schedule that is not single valued +; CHECK: JScop file contains a schedule that is not bounded +; CHECK-NOT: Stmt_for_inc29_copy_no_1 +; CHECK-NOT: Stmt_for_inc_copy_no_1