Index: polly/trunk/include/polly/ScopInfo.h =================================================================== --- polly/trunk/include/polly/ScopInfo.h +++ polly/trunk/include/polly/ScopInfo.h @@ -1710,6 +1710,12 @@ /// List of invariant accesses. InvariantEquivClassesTy InvariantEquivClasses; + /// The smallest array index not yet assigned. + long ArrayIdx = 0; + + /// The smallest statement index not yet assigned. + long StmtIdx = 0; + /// Scop constructor; invoked from ScopBuilder::buildScop. Scop(Region &R, ScalarEvolution &SE, LoopInfo &LI, ScopDetection::DetectionContext &DC); @@ -2620,6 +2626,18 @@ /// When true, also removes statements without /// side-effects. void simplifySCoP(bool AfterHoisting); + + /// Get the next free array index. + /// + /// This function returns a unique index which can be used to identify an + /// array. + long getNextArrayIdx() { return ArrayIdx++; } + + /// Get the next free statement index. + /// + /// This function returns a unique index which can be used to identify a + /// statement. + long getNextStmtIdx() { return StmtIdx++; } }; /// Print Scop scop to raw_ostream O. Index: polly/trunk/include/polly/Support/GICHelper.h =================================================================== --- polly/trunk/include/polly/Support/GICHelper.h +++ polly/trunk/include/polly/Support/GICHelper.h @@ -235,10 +235,43 @@ return OS; } -/// Return @p Prefix + @p Val->getName() + @p Suffix but Isl compatible. +/// Combine Prefix, Val (or Number) and Suffix to an isl-compatible name. +/// +/// In case @p UseInstructionNames is set, this function returns: +/// +/// @p Prefix + "_" + @p Val->getName() + @p Suffix +/// +/// otherwise +/// +/// @p Prefix + to_string(Number) + @p Suffix +/// +/// We ignore the value names by default, as they may change between release +/// and debug mode and can consequently not be used when aiming for reproducible +/// builds. However, for debugging named statements are often helpful, hence +/// we allow their optional use. std::string getIslCompatibleName(const std::string &Prefix, - const llvm::Value *Val, - const std::string &Suffix); + const llvm::Value *Val, long Number, + const std::string &Suffix, + bool UseInstructionNames); + +/// Combine Prefix, Name (or Number) and Suffix to an isl-compatible name. +/// +/// In case @p UseInstructionNames is set, this function returns: +/// +/// @p Prefix + "_" + Name + @p Suffix +/// +/// otherwise +/// +/// @p Prefix + to_string(Number) + @p Suffix +/// +/// We ignore @p Name by default, as they may change between release +/// and debug mode and can consequently not be used when aiming for reproducible +/// builds. However, for debugging named statements are often helpful, hence +/// we allow their optional use. +std::string getIslCompatibleName(const std::string &Prefix, + const std::string &Middle, long Number, + const std::string &Suffix, + bool UseInstructionNames); std::string getIslCompatibleName(const std::string &Prefix, const std::string &Middle, Index: polly/trunk/lib/Analysis/ScopInfo.cpp =================================================================== --- polly/trunk/lib/Analysis/ScopInfo.cpp +++ polly/trunk/lib/Analysis/ScopInfo.cpp @@ -158,6 +158,12 @@ cl::desc("Fold memory accesses to model more possible delinearizations " "(does not scale well)"), cl::Hidden, cl::init(false), cl::cat(PollyCategory)); + +static cl::opt UseInstructionNames( + "polly-use-llvm-names", + cl::desc("Use LLVM-IR names when deriving statement names"), cl::Hidden, + cl::init(false), cl::ZeroOrMore, cl::cat(PollyCategory)); + //===----------------------------------------------------------------------===// // Create a sequence of two schedules. Either argument may be null and is @@ -240,8 +246,9 @@ : BasePtr(BasePtr), ElementType(ElementType), Kind(Kind), DL(DL), S(*S) { std::string BasePtrName = BaseName ? BaseName - : getIslCompatibleName("MemRef_", BasePtr, - Kind == MemoryKind::PHI ? "__phi" : ""); + : getIslCompatibleName("MemRef", BasePtr, S->getNextArrayIdx(), + Kind == MemoryKind::PHI ? "__phi" : "", + UseInstructionNames); Id = isl_id_alloc(Ctx, BasePtrName.c_str(), this); updateSizes(Sizes); @@ -1574,14 +1581,16 @@ : Parent(parent), InvalidDomain(nullptr), Domain(nullptr), BB(nullptr), R(&R), Build(nullptr), SurroundingLoop(SurroundingLoop) { - BaseName = getIslCompatibleName("Stmt_", R.getNameStr(), ""); + BaseName = getIslCompatibleName( + "Stmt", R.getNameStr(), parent.getNextStmtIdx(), "", UseInstructionNames); } ScopStmt::ScopStmt(Scop &parent, BasicBlock &bb, Loop *SurroundingLoop) : Parent(parent), InvalidDomain(nullptr), Domain(nullptr), BB(&bb), R(nullptr), Build(nullptr), SurroundingLoop(SurroundingLoop) { - BaseName = getIslCompatibleName("Stmt_", &bb, ""); + BaseName = getIslCompatibleName("Stmt", &bb, parent.getNextStmtIdx(), "", + UseInstructionNames); } ScopStmt::ScopStmt(Scop &parent, __isl_take isl_map *SourceRel, @@ -1891,25 +1900,27 @@ std::string ParameterName = "p_" + std::to_string(getNumParams() - 1); - if (const SCEVUnknown *ValueParameter = dyn_cast(Parameter)) { - Value *Val = ValueParameter->getValue(); - - // If this parameter references a specific Value and this value has a name - // we use this name as it is likely to be unique and more useful than just - // a number. - if (Val->hasName()) - ParameterName = Val->getName(); - else if (LoadInst *LI = dyn_cast(Val)) { - auto *LoadOrigin = LI->getPointerOperand()->stripInBoundsOffsets(); - if (LoadOrigin->hasName()) { - ParameterName += "_loaded_from_"; - ParameterName += - LI->getPointerOperand()->stripInBoundsOffsets()->getName(); + if (UseInstructionNames) { + if (const SCEVUnknown *ValueParameter = dyn_cast(Parameter)) { + Value *Val = ValueParameter->getValue(); + + // If this parameter references a specific Value and this value has a name + // we use this name as it is likely to be unique and more useful than just + // a number. + if (Val->hasName()) + ParameterName = Val->getName(); + else if (LoadInst *LI = dyn_cast(Val)) { + auto *LoadOrigin = LI->getPointerOperand()->stripInBoundsOffsets(); + if (LoadOrigin->hasName()) { + ParameterName += "_loaded_from_"; + ParameterName += + LI->getPointerOperand()->stripInBoundsOffsets()->getName(); + } } } - } - ParameterName = getIslCompatibleName("", ParameterName, ""); + ParameterName = getIslCompatibleName("", ParameterName, ""); + } auto *Id = isl_id_alloc(getIslCtx(), ParameterName.c_str(), const_cast((const void *)Parameter)); Index: polly/trunk/lib/Support/GICHelper.cpp =================================================================== --- polly/trunk/lib/Support/GICHelper.cpp +++ polly/trunk/lib/Support/GICHelper.cpp @@ -193,13 +193,32 @@ } std::string polly::getIslCompatibleName(const std::string &Prefix, - const Value *Val, - const std::string &Suffix) { + const std::string &Name, long Number, + const std::string &Suffix, + bool UseInstructionNames) { + std::string S = Prefix; + + if (UseInstructionNames) + S += std::string("_") + Name; + else + S += std::to_string(Number); + + S += Suffix; + + makeIslCompatible(S); + return S; +} + +std::string polly::getIslCompatibleName(const std::string &Prefix, + const Value *Val, long Number, + const std::string &Suffix, + bool UseInstructionNames) { std::string ValStr; - raw_string_ostream OS(ValStr); - Val->printAsOperand(OS, false); - ValStr = OS.str(); - // Remove the leading % - ValStr.erase(0, 1); + + if (UseInstructionNames && Val->hasName()) + ValStr = std::string("_") + std::string(Val->getName()); + else + ValStr = std::to_string(Number); + return getIslCompatibleName(Prefix, ValStr, Suffix); } Index: polly/trunk/test/ScopInfo/unnamed_nonaffine.ll =================================================================== --- polly/trunk/test/ScopInfo/unnamed_nonaffine.ll +++ polly/trunk/test/ScopInfo/unnamed_nonaffine.ll @@ -0,0 +1,150 @@ +; RUN: opt %loadPolly -polly-allow-nonaffine -polly-scops -analyze < %s \ +; RUN: -polly-use-llvm-names=true | FileCheck %s +; +; RUN: opt %loadPolly -polly-allow-nonaffine -polly-scops -analyze < %s \ +; RUN: -polly-use-llvm-names=false | FileCheck %s -check-prefix=UNNAMED +; +; void f(int *A, int b) { +; int x; +; for (int i = 0; i < 1024; i++) { +; if (b > i) +; x = 0; +; else if (b < 2 * i) +; x = 3; +; else +; x = b; +; +; if (A[x]) +; A[x] = 0; +; } +; } +; +; CHECK: Statements { +; CHECK-NEXT: Stmt_bb3 +; CHECK-NEXT: Domain := +; CHECK-NEXT: [b] -> { Stmt_bb3[i0] : 0 <= i0 <= 1023 and i0 < b }; +; CHECK-NEXT: Schedule := +; CHECK-NEXT: [b] -> { Stmt_bb3[i0] -> [i0, 2] }; +; CHECK-NEXT: MustWriteAccess := [Reduction Type: NONE] [Scalar: 1] +; CHECK-NEXT: [b] -> { Stmt_bb3[i0] -> MemRef_x_1__phi[] }; +; CHECK-NEXT: Stmt_bb7 +; CHECK-NEXT: Domain := +; CHECK-NEXT: [b] -> { Stmt_bb7[i0] : i0 >= b and 0 <= i0 <= 1023 and 2i0 > b }; +; CHECK-NEXT: Schedule := +; CHECK-NEXT: [b] -> { Stmt_bb7[i0] -> [i0, 1] }; +; CHECK-NEXT: MustWriteAccess := [Reduction Type: NONE] [Scalar: 1] +; CHECK-NEXT: [b] -> { Stmt_bb7[i0] -> MemRef_x_1__phi[] }; +; CHECK-NEXT: Stmt_bb8 +; CHECK-NEXT: Domain := +; CHECK-NEXT: [b] -> { Stmt_bb8[0] : b = 0 }; +; CHECK-NEXT: Schedule := +; CHECK-NEXT: [b] -> { Stmt_bb8[i0] -> [0, 0] }; +; CHECK-NEXT: MustWriteAccess := [Reduction Type: NONE] [Scalar: 1] +; CHECK-NEXT: [b] -> { Stmt_bb8[i0] -> MemRef_x_1__phi[] }; +; CHECK-NEXT: Stmt_bb10__TO__bb18 +; CHECK-NEXT: Domain := +; CHECK-NEXT: [b] -> { Stmt_bb10__TO__bb18[i0] : 0 <= i0 <= 1023 }; +; CHECK-NEXT: Schedule := +; CHECK-NEXT: [b] -> { Stmt_bb10__TO__bb18[i0] -> [i0, 3] } +; CHECK-NEXT: ReadAccess := [Reduction Type: NONE] [Scalar: 1] +; CHECK-NEXT: [b] -> { Stmt_bb10__TO__bb18[i0] -> MemRef_x_1__phi[] }; +; CHECK-NEXT: ReadAccess := [Reduction Type: NONE] [Scalar: 0] +; CHECK-NEXT: [b] -> { Stmt_bb10__TO__bb18[i0] -> MemRef_A[o0] }; +; CHECK-NEXT: MayWriteAccess := [Reduction Type: NONE] [Scalar: 0] +; CHECK-NEXT: [b] -> { Stmt_bb10__TO__bb18[i0] -> MemRef_A[o0] }; +; CHECK-NEXT: } + +; UNNAMED: Arrays { +; UNNAMED-NEXT: i32 MemRef0__phi; // Element size 4 +; UNNAMED-NEXT: i32 MemRef1[*]; // Element size 4 +; UNNAMED-NEXT: } + +; UNNAMED: Statements { +; UNNAMED-NEXT: Stmt2 +; UNNAMED-NEXT: Domain := +; UNNAMED-NEXT: [p_0] -> { Stmt2[i0] : 0 <= i0 <= 1023 and i0 < p_0 }; +; UNNAMED-NEXT: Schedule := +; UNNAMED-NEXT: [p_0] -> { Stmt2[i0] -> [i0, 2] }; +; UNNAMED-NEXT: MustWriteAccess := [Reduction Type: NONE] [Scalar: 1] +; UNNAMED-NEXT: [p_0] -> { Stmt2[i0] -> MemRef0__phi[] }; +; UNNAMED-NEXT: Stmt4 +; UNNAMED-NEXT: Domain := +; UNNAMED-NEXT: [p_0] -> { Stmt4[i0] : i0 >= p_0 and 0 <= i0 <= 1023 and 2i0 > p_0 }; +; UNNAMED-NEXT: Schedule := +; UNNAMED-NEXT: [p_0] -> { Stmt4[i0] -> [i0, 1] }; +; UNNAMED-NEXT: MustWriteAccess := [Reduction Type: NONE] [Scalar: 1] +; UNNAMED-NEXT: [p_0] -> { Stmt4[i0] -> MemRef0__phi[] }; +; UNNAMED-NEXT: Stmt5 +; UNNAMED-NEXT: Domain := +; UNNAMED-NEXT: [p_0] -> { Stmt5[0] : p_0 = 0 }; +; UNNAMED-NEXT: Schedule := +; UNNAMED-NEXT: [p_0] -> { Stmt5[i0] -> [0, 0] }; +; UNNAMED-NEXT: MustWriteAccess := [Reduction Type: NONE] [Scalar: 1] +; UNNAMED-NEXT: [p_0] -> { Stmt5[i0] -> MemRef0__phi[] }; +; UNNAMED-NEXT: Stmt6 +; UNNAMED-NEXT: Domain := +; UNNAMED-NEXT: [p_0] -> { Stmt6[i0] : 0 <= i0 <= 1023 }; +; UNNAMED-NEXT: Schedule := +; UNNAMED-NEXT: [p_0] -> { Stmt6[i0] -> [i0, 3] }; +; UNNAMED-NEXT: ReadAccess := [Reduction Type: NONE] [Scalar: 1] +; UNNAMED-NEXT: [p_0] -> { Stmt6[i0] -> MemRef0__phi[] }; +; UNNAMED-NEXT: ReadAccess := [Reduction Type: NONE] [Scalar: 0] +; UNNAMED-NEXT: [p_0] -> { Stmt6[i0] -> MemRef1[o0] }; +; UNNAMED-NEXT: MayWriteAccess := [Reduction Type: NONE] [Scalar: 0] +; UNNAMED-NEXT: [p_0] -> { Stmt6[i0] -> MemRef1[o0] }; +; UNNAMED-NEXT: } + + +target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" + +define void @f(i32* %A, i32 %b) { +bb: + br label %bb1 + +bb1: ; preds = %bb19, %bb + %i.0 = phi i32 [ 0, %bb ], [ %tmp20, %bb19 ] + %exitcond = icmp ne i32 %i.0, 1024 + br i1 %exitcond, label %bb2, label %bb21 + +bb2: ; preds = %bb1 + %tmp = icmp slt i32 %i.0, %b + br i1 %tmp, label %bb3, label %bb4 + +bb3: ; preds = %bb2 + br label %bb10 + +bb4: ; preds = %bb2 + %tmp5 = mul nsw i32 %i.0, 2 + %tmp6 = icmp sgt i32 %tmp5, %b + br i1 %tmp6, label %bb7, label %bb8 + +bb7: ; preds = %bb4 + br label %bb10 + +bb8: ; preds = %bb4 + br label %bb10 + +bb10: ; preds = %bb9, %bb3 + %x.1 = phi i32 [ 0, %bb3 ], [ 3, %bb7 ], [ %b, %bb8 ] + %tmp11 = sext i32 %x.1 to i64 + %tmp12 = getelementptr inbounds i32, i32* %A, i64 %tmp11 + %tmp13 = load i32, i32* %tmp12, align 4 + %tmp14 = icmp eq i32 %tmp13, 0 + br i1 %tmp14, label %bb18, label %bb15 + +bb15: ; preds = %bb10 + %tmp16 = sext i32 %x.1 to i64 + %tmp17 = getelementptr inbounds i32, i32* %A, i64 %tmp16 + store i32 0, i32* %tmp17, align 4 + br label %bb18 + +bb18: ; preds = %bb10, %bb15 + br label %bb19 + +bb19: ; preds = %bb18 + %tmp20 = add nuw nsw i32 %i.0, 1 + br label %bb1 + +bb21: ; preds = %bb1 + ret void +} Index: polly/trunk/test/ScopInfo/unnamed_stmts.ll =================================================================== --- polly/trunk/test/ScopInfo/unnamed_stmts.ll +++ polly/trunk/test/ScopInfo/unnamed_stmts.ll @@ -0,0 +1,148 @@ +; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s + +; This test case verifies that we generate numbered statement names in case +; no LLVM-IR names are used in the test case. We also verify, that we +; distinguish statements named with a number and unnamed statements that happen +; to have an index identical to a number used in a statement name. + +; CHECK: Arrays { +; CHECK-NEXT: float MemRef0[*][%n]; // Element size 4 +; CHECK-NEXT: float MemRef1[*][%n]; // Element size 4 +; CHECK-NEXT: } +; CHECK-NEXT: Arrays (Bounds as pw_affs) { +; CHECK-NEXT: float MemRef0[*][ [n] -> { [] -> [(n)] } ]; // Element size 4 +; CHECK-NEXT: float MemRef1[*][ [n] -> { [] -> [(n)] } ]; // Element size 4 +; CHECK-NEXT: } + +; CHECK: Statements { +; CHECK-NEXT: Stmt2 +; CHECK-NEXT: Domain := +; CHECK-NEXT: [n] -> { Stmt2[i0, i1] : 0 <= i0 < n and 0 <= i1 < n }; +; CHECK-NEXT: Schedule := +; CHECK-NEXT: [n] -> { Stmt2[i0, i1] -> [0, i0, i1, 0] }; +; CHECK-NEXT: ReadAccess := [Reduction Type: NONE] [Scalar: 0] +; CHECK-NEXT: [n] -> { Stmt2[i0, i1] -> MemRef0[i0, i1] }; +; CHECK-NEXT: ReadAccess := [Reduction Type: NONE] [Scalar: 0] +; CHECK-NEXT: [n] -> { Stmt2[i0, i1] -> MemRef1[i0, i1] }; +; CHECK-NEXT: MustWriteAccess := [Reduction Type: NONE] [Scalar: 0] +; CHECK-NEXT: [n] -> { Stmt2[i0, i1] -> MemRef1[i0, i1] }; +; CHECK-NEXT: Stmt10 +; CHECK-NEXT: Domain := +; CHECK-NEXT: [n] -> { Stmt10[i0, i1] : 0 <= i0 < n and 0 <= i1 < n }; +; CHECK-NEXT: Schedule := +; CHECK-NEXT: [n] -> { Stmt10[i0, i1] -> [1, i0, i1, 0] }; +; CHECK-NEXT: ReadAccess := [Reduction Type: NONE] [Scalar: 0] +; CHECK-NEXT: [n] -> { Stmt10[i0, i1] -> MemRef1[i0, i1] }; +; CHECK-NEXT: ReadAccess := [Reduction Type: NONE] [Scalar: 0] +; CHECK-NEXT: [n] -> { Stmt10[i0, i1] -> MemRef0[i0, i1] }; +; CHECK-NEXT: MustWriteAccess := [Reduction Type: NONE] [Scalar: 0] +; CHECK-NEXT: [n] -> { Stmt10[i0, i1] -> MemRef0[i0, i1] }; +; CHECK-NEXT: Stmt_2 +; CHECK-NEXT: Domain := +; CHECK-NEXT: [n] -> { Stmt_2[i0, i1] : 0 <= i0 < n and 0 <= i1 < n }; +; CHECK-NEXT: Schedule := +; CHECK-NEXT: [n] -> { Stmt_2[i0, i1] -> [1, i0, i1, 1] }; +; CHECK-NEXT: MustWriteAccess := [Reduction Type: NONE] [Scalar: 0] +; CHECK-NEXT: [n] -> { Stmt_2[i0, i1] -> MemRef0[i0, i1] + +target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" + +; Function Attrs: nounwind uwtable +define void @vec3(i64 %n, float*, float*) #0 { + br label %.split + +.split: ; preds = %0 + br label %.preheader2.lr.ph + +.preheader2.lr.ph: ; preds = %.split + br label %.preheader2 + +.preheader2: ; preds = %.preheader2.lr.ph, %15 + %i.010 = phi i64 [ 0, %.preheader2.lr.ph ], [ %16, %15 ] + br label %.lr.ph8 + +.lr.ph8: ; preds = %.preheader2 + br label %4 + +..preheader1_crit_edge: ; preds = %15 + br label %.preheader1 + +.preheader1: ; preds = %..preheader1_crit_edge, %.split + %3 = icmp sgt i64 %n, 0 + br i1 %3, label %.preheader.lr.ph, label %"name" + +.preheader.lr.ph: ; preds = %.preheader1 + br label %.preheader + +;