Index: polly/trunk/include/polly/ScopInfo.h =================================================================== --- polly/trunk/include/polly/ScopInfo.h +++ polly/trunk/include/polly/ScopInfo.h @@ -333,11 +333,6 @@ /// Value *AccessValue; - /// @brief Accessed element relative to the base pointer (in bytes). - /// - /// Currently only used by printIR. - const SCEV *Offset; - /// @brief Are all the subscripts affine expression? bool IsAffine; @@ -358,8 +353,6 @@ /// @brief Is this MemoryAccess modeling special PHI node accesses? bool isPHI() const { return IsPHI; } - void printIR(raw_ostream &OS) const; - void setStatement(ScopStmt *Stmt) { this->Statement = Stmt; } __isl_give isl_basic_map *createBasicAccessMap(ScopStmt *Statement); @@ -426,7 +419,6 @@ /// @param Id Identifier that is guranteed to be unique within the /// same ScopStmt. /// @param BaseAddr The accessed array's address. - /// @param Offset Accessed memoray location relative to @p BaseAddr. /// @param ElemBytes Number of accessed bytes. /// @param AccType Whether read or write access. /// @param IsAffine Whether the subscripts are affine expressions. @@ -435,10 +427,9 @@ /// @param Sizes Dimension lengths of the accessed array. /// @param BaseName Name of the acessed array. MemoryAccess(Instruction *AccessInst, __isl_take isl_id *Id, AccessType Type, - Value *BaseAddress, const SCEV *Offset, unsigned ElemBytes, - bool Affine, ArrayRef Subscripts, - ArrayRef Sizes, Value *AccessValue, bool IsPHI, - StringRef BaseName); + Value *BaseAddress, unsigned ElemBytes, bool Affine, + ArrayRef Subscripts, ArrayRef Sizes, + Value *AccessValue, bool IsPHI, StringRef BaseName); ~MemoryAccess(); /// @brief Get the type of a memory access. @@ -1120,22 +1111,6 @@ } //@} - /// @brief Print data access information. - /// - /// @param OS The output stream the access functions is printed to. - /// @param SE The ScalarEvolution to help printing more details. - /// @param LI The LoopInfo that help printing the access functions. - void printIRAccesses(raw_ostream &OS, ScalarEvolution *SE, - LoopInfo *LI) const; - - /// @brief Print the access functions and loop bounds in this Scop. - /// - /// @param OS The output stream the access functions is printed to. - /// @param SE The ScalarEvolution that help printing the access functions. - /// @param LI The LoopInfo that help printing the access functions. - void printIRAccessesDetail(raw_ostream &OS, ScalarEvolution *SE, LoopInfo *LI, - const Region *Reg, unsigned ind) const; - ScalarEvolution *getSE() const; /// @brief Get the count of parameters used in this Scop. @@ -1503,7 +1478,6 @@ /// inside @p BB. /// @param Type The kind of access. /// @param BaseAddress The accessed array's base address. - /// @param Offset Accessed location relative to @p BaseAddress. /// @param ElemBytes Size of accessed array element. /// @param Affine Whether all subscripts are affine expressions. /// @param AccessValue Value read or written. @@ -1512,26 +1486,25 @@ /// @param IsPHI Whether this is an emulated PHI node. void addMemoryAccess(BasicBlock *BB, Instruction *Inst, MemoryAccess::AccessType Type, Value *BaseAddress, - const SCEV *Offset, unsigned ElemBytes, bool Affine, - Value *AccessValue, ArrayRef Subscripts, + unsigned ElemBytes, bool Affine, Value *AccessValue, + ArrayRef Subscripts, ArrayRef Sizes, bool IsPHI); void addMemoryAccess(BasicBlock *BB, Instruction *Inst, MemoryAccess::AccessType Type, Value *BaseAddress, - const SCEV *Offset, unsigned ElemBytes, bool Affine, - Value *AccessValue, bool IsPHI = false) { - addMemoryAccess(BB, Inst, Type, BaseAddress, Offset, ElemBytes, Affine, - AccessValue, ArrayRef(), - ArrayRef(), IsPHI); + unsigned ElemBytes, bool Affine, Value *AccessValue, + bool IsPHI = false) { + addMemoryAccess(BB, Inst, Type, BaseAddress, ElemBytes, Affine, AccessValue, + ArrayRef(), ArrayRef(), IsPHI); } void addMemoryAccess(BasicBlock *BB, Instruction *Inst, MemoryAccess::AccessType Type, Value *BaseAddress, - const SCEV *Offset, unsigned ElemBytes, bool Affine, + unsigned ElemBytes, bool Affine, ArrayRef Subscripts, ArrayRef Sizes, Value *AccessValue) { - addMemoryAccess(BB, Inst, Type, BaseAddress, Offset, ElemBytes, Affine, - AccessValue, Subscripts, Sizes, false); + addMemoryAccess(BB, Inst, Type, BaseAddress, ElemBytes, Affine, AccessValue, + Subscripts, Sizes, false); } public: Index: polly/trunk/lib/Analysis/ScopInfo.cpp =================================================================== --- polly/trunk/lib/Analysis/ScopInfo.cpp +++ polly/trunk/lib/Analysis/ScopInfo.cpp @@ -227,17 +227,6 @@ return SAI; } -void MemoryAccess::printIR(raw_ostream &OS) const { - if (isRead()) - OS << "Read "; - else { - if (isMayWrite()) - OS << "May"; - OS << "Write "; - } - OS << BaseAddr->getName() << '[' << *Offset << "]\n"; -} - const std::string MemoryAccess::getReductionOperatorStr(MemoryAccess::ReductionType RT) { switch (RT) { @@ -614,14 +603,14 @@ MemoryAccess::MemoryAccess(Instruction *AccessInst, __isl_take isl_id *Id, AccessType Type, Value *BaseAddress, - const SCEV *Offset, unsigned ElemBytes, bool Affine, + unsigned ElemBytes, bool Affine, ArrayRef Subscripts, ArrayRef Sizes, Value *AccessValue, bool IsPHI, StringRef BaseName) : Id(Id), IsPHI(IsPHI), AccType(Type), RedType(RT_NONE), Statement(nullptr), BaseAddr(BaseAddress), BaseName(BaseName), ElemBytes(ElemBytes), Sizes(Sizes.begin(), Sizes.end()), AccessInstruction(AccessInst), - AccessValue(AccessValue), Offset(Offset), IsAffine(Affine), + AccessValue(AccessValue), IsAffine(Affine), Subscripts(Subscripts.begin(), Subscripts.end()), AccessRelation(nullptr), NewAccessRelation(nullptr) {} @@ -2668,34 +2657,6 @@ return StmtMapIt->second; } -void Scop::printIRAccesses(raw_ostream &OS, ScalarEvolution *SE, - LoopInfo *LI) const { - OS << "Scop: " << R.getNameStr() << "\n"; - - printIRAccessesDetail(OS, SE, LI, &R, 0); -} - -void Scop::printIRAccessesDetail(raw_ostream &OS, ScalarEvolution *SE, - LoopInfo *LI, const Region *CurR, - unsigned ind) const { - // FIXME: Print other details rather than memory accesses. - for (const auto &CurBlock : CurR->blocks()) { - AccFuncMapType::const_iterator AccSetIt = AccFuncMap.find(CurBlock); - - // Ignore trivial blocks that do not contain any memory access. - if (AccSetIt == AccFuncMap.end()) - continue; - - OS.indent(ind) << "BB: " << CurBlock->getName() << '\n'; - typedef AccFuncSetType::const_iterator access_iterator; - const AccFuncSetType &AccFuncs = AccSetIt->second; - - for (access_iterator AI = AccFuncs.begin(), AE = AccFuncs.end(); AI != AE; - ++AI) - AI->printIR(OS.indent(ind + 2)); - } -} - int Scop::getRelativeLoopDepth(const Loop *L) const { Loop *OuterLoop = L ? R.outermostLoopInRegion(const_cast(L)) : nullptr; @@ -2742,10 +2703,9 @@ // we have to insert a scalar dependence from the definition of OpI to // OpBB if the definition is not in OpBB. if (OpIBB != OpBB) { - addMemoryAccess(OpBB, PHI, MemoryAccess::READ, OpI, ZeroOffset, 1, true, + addMemoryAccess(OpBB, PHI, MemoryAccess::READ, OpI, 1, true, OpI); + addMemoryAccess(OpIBB, OpI, MemoryAccess::MUST_WRITE, OpI, 1, true, OpI); - addMemoryAccess(OpIBB, OpI, MemoryAccess::MUST_WRITE, OpI, ZeroOffset, - 1, true, OpI); } } @@ -2753,13 +2713,13 @@ // instruction. OpI = OpBB->getTerminator(); - addMemoryAccess(OpBB, OpI, MemoryAccess::MUST_WRITE, PHI, ZeroOffset, 1, - true, Op, /* IsPHI */ !IsExitBlock); + addMemoryAccess(OpBB, OpI, MemoryAccess::MUST_WRITE, PHI, 1, true, Op, + /* IsPHI */ !IsExitBlock); } if (!OnlyNonAffineSubRegionOperands) { - addMemoryAccess(PHI->getParent(), PHI, MemoryAccess::READ, PHI, ZeroOffset, - 1, true, PHI, + addMemoryAccess(PHI->getParent(), PHI, MemoryAccess::READ, PHI, 1, true, + PHI, /* IsPHI */ !IsExitBlock); } } @@ -2816,8 +2776,7 @@ // Do not build a read access that is not in the current SCoP // Use the def instruction as base address of the MemoryAccess, so that it // will become the name of the scalar access in the polyhedral form. - addMemoryAccess(UseParent, UI, MemoryAccess::READ, Inst, ZeroOffset, 1, - true, Inst); + addMemoryAccess(UseParent, UI, MemoryAccess::READ, Inst, 1, true, Inst); } if (ModelReadOnlyScalars) { @@ -2832,8 +2791,8 @@ if (isa(Op)) continue; - addMemoryAccess(Inst->getParent(), Inst, MemoryAccess::READ, Op, - ZeroOffset, 1, true, Op); + addMemoryAccess(Inst->getParent(), Inst, MemoryAccess::READ, Op, 1, true, + Op); } } @@ -2905,7 +2864,7 @@ IntegerType::getInt64Ty(BasePtr->getContext()), Size))); addMemoryAccess(Inst->getParent(), Inst, Type, BasePointer->getValue(), - AccessFunction, Size, true, Subscripts, SizesSCEV, Val); + Size, true, Subscripts, SizesSCEV, Val); return; } } @@ -2914,8 +2873,7 @@ auto AccItr = InsnToMemAcc.find(Inst); if (PollyDelinearize && AccItr != InsnToMemAcc.end()) { addMemoryAccess(Inst->getParent(), Inst, Type, BasePointer->getValue(), - AccessFunction, Size, true, - AccItr->second.DelinearizedSubscripts, + Size, true, AccItr->second.DelinearizedSubscripts, AccItr->second.Shape->DelinearizedSizes, Val); return; } @@ -2940,8 +2898,8 @@ if (!IsAffine && Type == MemoryAccess::MUST_WRITE) Type = MemoryAccess::MAY_WRITE; - addMemoryAccess(Inst->getParent(), Inst, Type, BasePointer->getValue(), - AccessFunction, Size, IsAffine, Subscripts, Sizes, Val); + addMemoryAccess(Inst->getParent(), Inst, Type, BasePointer->getValue(), Size, + IsAffine, Subscripts, Sizes, Val); } void ScopInfo::buildAccessFunctions(Region &R, Region &SR) { @@ -2986,17 +2944,19 @@ if (buildScalarDependences(Inst, &R, NonAffineSubRegion)) { if (!isa(Inst)) - addMemoryAccess(&BB, Inst, MemoryAccess::MUST_WRITE, Inst, ZeroOffset, - 1, true, Inst); + addMemoryAccess(&BB, Inst, MemoryAccess::MUST_WRITE, Inst, 1, true, + Inst); } } } -void ScopInfo::addMemoryAccess( - BasicBlock *BB, Instruction *Inst, MemoryAccess::AccessType Type, - Value *BaseAddress, const SCEV *Offset, unsigned ElemBytes, bool Affine, - Value *AccessValue, ArrayRef Subscripts, - ArrayRef Sizes, bool IsPHI = false) { +void ScopInfo::addMemoryAccess(BasicBlock *BB, Instruction *Inst, + MemoryAccess::AccessType Type, + Value *BaseAddress, unsigned ElemBytes, + bool Affine, Value *AccessValue, + ArrayRef Subscripts, + ArrayRef Sizes, + bool IsPHI = false) { AccFuncSetType &AccList = AccFuncMap[BB]; size_t Identifier = AccList.size(); @@ -3006,7 +2966,7 @@ std::string IdName = "__polly_array_ref_" + std::to_string(Identifier); isl_id *Id = isl_id_alloc(ctx, IdName.c_str(), nullptr); - AccList.emplace_back(Inst, Id, Type, BaseAddress, Offset, ElemBytes, Affine, + AccList.emplace_back(Inst, Id, Type, BaseAddress, ElemBytes, Affine, Subscripts, Sizes, AccessValue, IsPHI, BaseName); } @@ -3036,7 +2996,6 @@ return; } - scop->printIRAccesses(OS, SE, LI); scop->print(OS); } Index: polly/trunk/test/ScopInfo/cond_in_loop.ll =================================================================== --- polly/trunk/test/ScopInfo/cond_in_loop.ll +++ polly/trunk/test/ScopInfo/cond_in_loop.ll @@ -45,4 +45,5 @@ } ; CHECK-LABEL: Printing analysis 'Polly - Create polyhedral description of Scops' for region: 'bb => return' in function 'f': -; CHECK-NEXT: Scop: bb => return +; CHECK-NEXT: Function: f +; CHECK-NEXT: Region: %bb---%return Index: polly/trunk/test/ScopInfo/inter_bb_scalar_dep.ll =================================================================== --- polly/trunk/test/ScopInfo/inter_bb_scalar_dep.ll +++ polly/trunk/test/ScopInfo/inter_bb_scalar_dep.ll @@ -0,0 +1,57 @@ +; RUN: opt %loadPolly -polly-detect-unprofitable -basicaa -polly-scops -analyze < %s | FileCheck %s + +; void f(long A[], int N, int *init_ptr) { +; long i, j; +; +; for (i = 0; i < N; ++i) { +; init = *init_ptr; +; for (i = 0; i < N; ++i) { +; A[i] = init + 2; +; } +; } +; } + +target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128" + +; Function Attrs: nounwind +define void @f(i64* noalias %A, i64 %N, i64* noalias %init_ptr) #0 { +entry: + br label %for.i + +for.i: ; preds = %for.i.end, %entry + %indvar.i = phi i64 [ 0, %entry ], [ %indvar.i.next, %for.i.end ] + %indvar.i.next = add nsw i64 %indvar.i, 1 + br label %entry.next + +entry.next: ; preds = %for.i + %init = load i64, i64* %init_ptr +; CHECK-LABEL: Stmt_entry_next +; CHECK: ReadAccess := [Reduction Type: NONE] [Scalar: 0] +; CHECK-NEXT: [N] -> { Stmt_entry_next[i0] -> MemRef_init_ptr[0] }; +; CHECK: MustWriteAccess := [Reduction Type: NONE] [Scalar: 1] +; CHECK-NEXT: [N] -> { Stmt_entry_next[i0] -> MemRef_init[] }; + br label %for.j + +for.j: ; preds = %for.j, %entry.next + %indvar.j = phi i64 [ 0, %entry.next ], [ %indvar.j.next, %for.j ] + %init_plus_two = add i64 %init, 2 +; CHECK-LABEL: Stmt_for_j +; CHECK: ReadAccess := [Reduction Type: NONE] [Scalar: 1] +; CHECK-NEXT: [N] -> { Stmt_for_j[i0, i1] -> MemRef_init[] }; +; CHECK: MustWriteAccess := [Reduction Type: NONE] [Scalar: 0] +; CHECK-NEXT: [N] -> { Stmt_for_j[i0, i1] -> MemRef_A[i1] }; + %scevgep = getelementptr i64, i64* %A, i64 %indvar.j + store i64 %init_plus_two, i64* %scevgep + %indvar.j.next = add nsw i64 %indvar.j, 1 + %exitcond.j = icmp eq i64 %indvar.j.next, %N + br i1 %exitcond.j, label %for.i.end, label %for.j + +for.i.end: ; preds = %for.j + %exitcond.i = icmp eq i64 %indvar.i.next, %N + br i1 %exitcond.i, label %return, label %for.i + +return: ; preds = %for.i.end + ret void +} + +attributes #0 = { nounwind } Index: polly/trunk/test/ScopInfo/intra_and_inter_bb_scalar_dep.ll =================================================================== --- polly/trunk/test/ScopInfo/intra_and_inter_bb_scalar_dep.ll +++ polly/trunk/test/ScopInfo/intra_and_inter_bb_scalar_dep.ll @@ -0,0 +1,61 @@ +; RUN: opt %loadPolly -polly-detect-unprofitable -basicaa -polly-scops -analyze < %s | FileCheck %s + +; void f(long A[], int N, int *init_ptr) { +; long i, j; +; +; for (i = 0; i < N; ++i) { +; init = *init_ptr; +; for (i = 0; i < N; ++i) { +; init2 = *init_ptr; +; A[i] = init + init2; +; } +; } +; } + +target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128" + +; Function Attrs: nounwind +define void @f(i64* noalias %A, i64 %N, i64* noalias %init_ptr) #0 { +entry: + br label %for.i + +for.i: ; preds = %for.i.end, %entry + %indvar.i = phi i64 [ 0, %entry ], [ %indvar.i.next, %for.i.end ] + %indvar.i.next = add nsw i64 %indvar.i, 1 + br label %entry.next + +entry.next: ; preds = %for.i + %init = load i64, i64* %init_ptr +; CHECK-LABEL: Stmt_entry_next +; CHECK: ReadAccess := [Reduction Type: NONE] [Scalar: 0] +; CHECK-NEXT: [N] -> { Stmt_entry_next[i0] -> MemRef_init_ptr[0] }; +; CHECK: MustWriteAccess := [Reduction Type: NONE] [Scalar: 1] +; CHECK-NEXT: [N] -> { Stmt_entry_next[i0] -> MemRef_init[] }; + br label %for.j + +for.j: ; preds = %for.j, %entry.next + %indvar.j = phi i64 [ 0, %entry.next ], [ %indvar.j.next, %for.j ] + %init_2 = load i64, i64* %init_ptr + %init_sum = add i64 %init, %init_2 +; CHECK-LABEL: Stmt_for_j +; CHECK: ReadAccess := [Reduction Type: NONE] [Scalar: 1] +; CHECK-NEXT: [N] -> { Stmt_for_j[i0, i1] -> MemRef_init[] }; +; CHECK: ReadAccess := [Reduction Type: NONE] [Scalar: 0] +; CHECK-NEXT: [N] -> { Stmt_for_j[i0, i1] -> MemRef_init_ptr[0] }; +; CHECK: MustWriteAccess := [Reduction Type: NONE] [Scalar: 0] +; CHECK-NEXT: [N] -> { Stmt_for_j[i0, i1] -> MemRef_A[i1] }; + %scevgep = getelementptr i64, i64* %A, i64 %indvar.j + store i64 %init_sum, i64* %scevgep + %indvar.j.next = add nsw i64 %indvar.j, 1 + %exitcond.j = icmp eq i64 %indvar.j.next, %N + br i1 %exitcond.j, label %for.i.end, label %for.j + +for.i.end: ; preds = %for.j + %exitcond.i = icmp eq i64 %indvar.i.next, %N + br i1 %exitcond.i, label %return, label %for.i + +return: ; preds = %for.i.end + ret void +} + +attributes #0 = { nounwind } Index: polly/trunk/test/ScopInfo/intra_bb_scalar_dep.ll =================================================================== --- polly/trunk/test/ScopInfo/intra_bb_scalar_dep.ll +++ polly/trunk/test/ScopInfo/intra_bb_scalar_dep.ll @@ -0,0 +1,52 @@ +; RUN: opt %loadPolly -polly-detect-unprofitable -basicaa -polly-scops -analyze < %s | FileCheck %s + +; void f(long A[], int N, int *init_ptr) { +; long i, j; +; +; for (i = 0; i < N; ++i) { +; for (i = 0; i < N; ++i) { +; init = *init_ptr; +; A[i] = init + 2; +; } +; } +; } + +target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128" + +; Function Attrs: nounwind +define void @f(i64* noalias %A, i64 %N, i64* noalias %init_ptr) #0 { +entry: + br label %for.i + +for.i: ; preds = %for.i.end, %entry + %indvar.i = phi i64 [ 0, %entry ], [ %indvar.i.next, %for.i.end ] + %indvar.i.next = add nsw i64 %indvar.i, 1 + br label %entry.next + +entry.next: ; preds = %for.i + br label %for.j + +for.j: ; preds = %for.j, %entry.next + %indvar.j = phi i64 [ 0, %entry.next ], [ %indvar.j.next, %for.j ] + %init = load i64, i64* %init_ptr + %init_plus_two = add i64 %init, 2 + %scevgep = getelementptr i64, i64* %A, i64 %indvar.j + store i64 %init_plus_two, i64* %scevgep +; CHECK-LABEL: Stmt_for_j +; CHECK: ReadAccess := [Reduction Type: NONE] [Scalar: 0] +; CHECK-NEXT: [N] -> { Stmt_for_j[i0, i1] -> MemRef_init_ptr[0] }; +; CHECK: MustWriteAccess := [Reduction Type: NONE] [Scalar: 0] +; CHECK-NEXT: [N] -> { Stmt_for_j[i0, i1] -> MemRef_A[i1] }; + %indvar.j.next = add nsw i64 %indvar.j, 1 + %exitcond.j = icmp eq i64 %indvar.j.next, %N + br i1 %exitcond.j, label %for.i.end, label %for.j + +for.i.end: ; preds = %for.j + %exitcond.i = icmp eq i64 %indvar.i.next, %N + br i1 %exitcond.i, label %return, label %for.i + +return: ; preds = %for.i.end + ret void +} + +attributes #0 = { nounwind } Index: polly/trunk/test/ScopInfo/nested-loops.ll =================================================================== --- polly/trunk/test/ScopInfo/nested-loops.ll +++ polly/trunk/test/ScopInfo/nested-loops.ll @@ -0,0 +1,40 @@ +; RUN: opt %loadPolly -polly-detect-unprofitable -polly-scops -analyze < %s | FileCheck %s + +target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128" + +define void @f(i64* nocapture %a) nounwind { +entry: + br label %for.i + +for.i: + %i = phi i64 [ 0, %entry ], [ %i.inc, %for.j ] + %i.inc = add nsw i64 %i, 1 + %exitcond.i = icmp sge i64 %i.inc, 2048 + br i1 %exitcond.i, label %return, label %for.j + +for.j: + %j = phi i64 [ 0, %for.i ], [ %j.inc, %body ] + %j.inc = add nsw i64 %j, 1 + %exitcond.j = icmp slt i64 %j.inc, 1024 + br i1 %exitcond.j, label %body, label %for.i + +body: + %scevgep = getelementptr i64, i64* %a, i64 %j + store i64 %j, i64* %scevgep + br label %for.j + +return: + ret void +} + +; CHECK: body +; CHECK: Domain := +; CHECK: { Stmt_body[i0, i1] : +; CHECK-DAG: i0 >= 0 +; CHECK-DAG: and +; CHECK-DAG: i0 <= 2046 +; CHECK-DAG: and +; CHECK-DAG: i1 >= 0 +; CHECK-DAG: and +; CHECK-DAG: i1 <= 1022 +; CHECK: } Index: polly/trunk/test/ScopInfo/not-a-reduction.ll =================================================================== --- polly/trunk/test/ScopInfo/not-a-reduction.ll +++ polly/trunk/test/ScopInfo/not-a-reduction.ll @@ -0,0 +1,51 @@ +; RUN: opt %loadPolly -polly-detect-unprofitable -polly-scops -analyze < %s 2>&1 | not FileCheck %s + +;#define TYPE float +;#define NUM 4 +; +;TYPE A[NUM]; +;TYPE B[NUM]; +;TYPE C[NUM]; +; +;void vector_multiply(void) { +; int i; +; for (i = 0; i < NUM; i++) { +; A[i] = B[i] * C[i]; +; } +;} + +target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64" + +@B = common global [4 x float] zeroinitializer, align 16 +@C = common global [4 x float] zeroinitializer, align 16 +@A = common global [4 x float] zeroinitializer, align 16 + +define void @vector_multiply() nounwind { +bb: + br label %bb3 + +bb3: ; preds = %bb7, %bb + %indvar = phi i64 [ %indvar.next, %bb7 ], [ 0, %bb ] + %scevgep = getelementptr [4 x float], [4 x float]* @A, i64 0, i64 %indvar + %scevgep1 = getelementptr [4 x float], [4 x float]* @C, i64 0, i64 %indvar + %scevgep2 = getelementptr [4 x float], [4 x float]* @B, i64 0, i64 %indvar + %exitcond = icmp ne i64 %indvar, 4 + br i1 %exitcond, label %bb4, label %bb8 + +bb4: ; preds = %bb3 + %tmp = load float, float* %scevgep2, align 4 + %tmp5 = load float, float* %scevgep1, align 4 + %tmp6 = fmul float %tmp, %tmp5 + store float %tmp6, float* %scevgep, align 4 + br label %bb7 + +bb7: ; preds = %bb4 + %indvar.next = add i64 %indvar, 1 + br label %bb3 + +bb8: ; preds = %bb3 + ret void +} + +; Match any reduction type except "[Reduction Type: NONE]" +; CHECK: [Reduction Type: {{[^N].*}}] Index: polly/trunk/test/ScopInfo/scalar_to_array.ll =================================================================== --- polly/trunk/test/ScopInfo/scalar_to_array.ll +++ polly/trunk/test/ScopInfo/scalar_to_array.ll @@ -0,0 +1,194 @@ +; RUN: opt %loadPolly -polly-detect-unprofitable -basicaa -polly-scops -analyze < %s | FileCheck %s + +; ModuleID = 'scalar_to_array.ll' +target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64" + +@A = common global [1024 x float] zeroinitializer, align 8 + +; Terminating loops without side-effects will be optimzied away, hence +; detecting a scop would be pointless. +; CHECK-NOT: Function: empty +; Function Attrs: nounwind +define i32 @empty() #0 { +entry: + fence seq_cst + br label %for.cond + +for.cond: ; preds = %for.inc, %entry + %indvar = phi i64 [ %indvar.next, %for.inc ], [ 0, %entry ] + %exitcond = icmp ne i64 %indvar, 1024 + br i1 %exitcond, label %for.body, label %return + +for.body: ; preds = %for.cond + br label %for.inc + +for.inc: ; preds = %for.body + %indvar.next = add i64 %indvar, 1 + br label %for.cond + +return: ; preds = %for.cond + fence seq_cst + ret i32 0 +} + +; CHECK-LABEL: Function: array_access +; Function Attrs: nounwind +define i32 @array_access() #0 { +entry: + fence seq_cst + br label %for.cond + +for.cond: ; preds = %for.inc, %entry + %indvar = phi i64 [ %indvar.next, %for.inc ], [ 0, %entry ] + %exitcond = icmp ne i64 %indvar, 1024 + br i1 %exitcond, label %for.body, label %return + +for.body: ; preds = %for.cond + %arrayidx = getelementptr [1024 x float], [1024 x float]* @A, i64 0, i64 %indvar + %float = uitofp i64 %indvar to float + store float %float, float* %arrayidx + br label %for.inc +; CHECK: Stmt_for_body +; CHECK-NOT: ReadAccess +; CHECK: MustWriteAccess := [Reduction Type: NONE] [Scalar: 0] +; CHECK-NEXT: { Stmt_for_body[i0] -> MemRef_A[i0] }; + +for.inc: ; preds = %for.body + %indvar.next = add i64 %indvar, 1 + br label %for.cond + +return: ; preds = %for.cond + fence seq_cst + ret i32 0 +} + +; Function Attrs: nounwind +; CHECK-LABEL: Function: intra_scop_dep +define i32 @intra_scop_dep() #0 { +entry: + fence seq_cst + br label %for.cond + +for.cond: ; preds = %for.inc, %entry + %indvar = phi i64 [ %indvar.next, %for.inc ], [ 0, %entry ] + %exitcond = icmp ne i64 %indvar, 1024 + br i1 %exitcond, label %for.body.a, label %return + +for.body.a: ; preds = %for.cond + %arrayidx = getelementptr [1024 x float], [1024 x float]* @A, i64 0, i64 %indvar + %scalar = load float, float* %arrayidx + br label %for.body.b +; CHECK: Stmt_for_body_a +; CHECK: ReadAccess := [Reduction Type: NONE] [Scalar: 0] +; CHECK-NEXT: { Stmt_for_body_a[i0] -> MemRef_A[i0] }; +; CHECK: MustWriteAccess := [Reduction Type: NONE] [Scalar: 1] +; CHECK-NEXT: { Stmt_for_body_a[i0] -> MemRef_scalar[] }; + +for.body.b: ; preds = %for.body.a + %arrayidx2 = getelementptr [1024 x float], [1024 x float]* @A, i64 0, i64 %indvar + %float = uitofp i64 %indvar to float + %sum = fadd float %scalar, %float + store float %sum, float* %arrayidx2 + br label %for.inc +; CHECK: Stmt_for_body_b +; CHECK: ReadAccess := [Reduction Type: NONE] [Scalar: 1] +; CHECK-NEXT: { Stmt_for_body_b[i0] -> MemRef_scalar[] }; +; CHECK: MustWriteAccess := [Reduction Type: NONE] [Scalar: 0] +; CHECK-NEXT: { Stmt_for_body_b[i0] -> MemRef_A[i0] }; + +for.inc: ; preds = %for.body.b + %indvar.next = add i64 %indvar, 1 + br label %for.cond + +return: ; preds = %for.cond + fence seq_cst + ret i32 0 +} + +; It is not possible to have a scop which accesses a scalar element that is +; a global variable. All global variables are pointers containing possibly +; a single element. Hence they do not need to be handled anyways. +; Please note that this is still required when scalar to array rewritting is +; disabled. + +; CHECK-LABEL: Function: use_after_scop +; Function Attrs: nounwind +define i32 @use_after_scop() #0 { +entry: + %scalar.s2a = alloca float + fence seq_cst + br label %for.head + +for.head: ; preds = %for.inc, %entry + %indvar = phi i64 [ %indvar.next, %for.inc ], [ 0, %entry ] + br label %for.body + +for.body: ; preds = %for.head + %arrayidx = getelementptr [1024 x float], [1024 x float]* @A, i64 0, i64 %indvar + %scalar = load float, float* %arrayidx + store float %scalar, float* %scalar.s2a +; Escaped uses are still required to be rewritten to stack variable. +; CHECK: Stmt_for_body +; CHECK: ReadAccess := [Reduction Type: NONE] [Scalar: 0] +; CHECK-NEXT: { Stmt_for_body[i0] -> MemRef_A[i0] }; +; CHECK: MustWriteAccess := [Reduction Type: NONE] [Scalar: 0] +; CHECK-NEXT: { Stmt_for_body[i0] -> MemRef_scalar_s2a[0] }; + br label %for.inc + +for.inc: ; preds = %for.body + %indvar.next = add i64 %indvar, 1 + %exitcond = icmp ne i64 %indvar.next, 1024 + br i1 %exitcond, label %for.head, label %for.after + +for.after: ; preds = %for.inc + %scalar.loadoutside = load float, float* %scalar.s2a + fence seq_cst + %return_value = fptosi float %scalar.loadoutside to i32 + br label %return + +return: ; preds = %for.after + ret i32 %return_value +} + +; We currently do not transform scalar references, that have only read accesses +; in the scop. There are two reasons for this: +; +; o We don't introduce additional memory references which may yield to compile +; time overhead. +; o For integer values, such a translation may block the use of scalar +; evolution on those values. +; +; CHECK-LABEL: Function: before_scop +; Function Attrs: nounwind +define i32 @before_scop() #0 { +entry: + br label %preheader + +preheader: ; preds = %entry + %scalar = fadd float 4.000000e+00, 5.000000e+00 + fence seq_cst + br label %for.cond + +for.cond: ; preds = %for.inc, %preheader + %indvar = phi i64 [ %indvar.next, %for.inc ], [ 0, %preheader ] + %exitcond = icmp ne i64 %indvar, 1024 + br i1 %exitcond, label %for.body, label %return + +for.body: ; preds = %for.cond + %arrayidx = getelementptr [1024 x float], [1024 x float]* @A, i64 0, i64 %indvar + store float %scalar, float* %arrayidx + br label %for.inc +; CHECK: Stmt_for_body +; CHECK: MustWriteAccess := [Reduction Type: NONE] [Scalar: 0] +; CHECK-NEXT: { Stmt_for_body[i0] -> MemRef_A[i0] }; + +for.inc: ; preds = %for.body + %indvar.next = add i64 %indvar, 1 + br label %for.cond + +return: ; preds = %for.cond + fence seq_cst + ret i32 0 +} + +attributes #0 = { nounwind } Index: polly/trunk/test/ScopInfo/tempscop-printing.ll =================================================================== --- polly/trunk/test/ScopInfo/tempscop-printing.ll +++ polly/trunk/test/ScopInfo/tempscop-printing.ll @@ -0,0 +1,95 @@ +; RUN: opt %loadPolly -polly-detect-unprofitable -basicaa -polly-scops -analyze < %s | FileCheck %s + +; void f(long A[], int N, int *init_ptr) { +; long i, j; +; +; for (i = 0; i < N; ++i) { +; init = *init_ptr; +; for (i = 0; i < N; ++i) { +; A[i] = init + 2; +; } +; } +; } + +target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128" + +; CHECK-LABEL: Function: f +define void @f(i64* noalias %A, i64 %N, i64* noalias %init_ptr) nounwind { +entry: + br label %for.i + +for.i: + %indvar.i = phi i64 [ 0, %entry ], [ %indvar.i.next, %for.i.end ] + %indvar.i.next = add nsw i64 %indvar.i, 1 + br label %entry.next + +entry.next: +; CHECK: Stmt_entry_next + %init = load i64, i64* %init_ptr +; CHECK: ReadAccess := [Reduction Type: NONE] [Scalar: 0] +; CHECK-NEXT: [N] -> { Stmt_entry_next[i0] -> MemRef_init_ptr[0] }; +; CHECK: MustWriteAccess := [Reduction Type: NONE] [Scalar: 1] +; CHECK-NEXT: [N] -> { Stmt_entry_next[i0] -> MemRef_init[] }; + br label %for.j + +for.j: + %indvar.j = phi i64 [ 0, %entry.next ], [ %indvar.j.next, %for.j ] +; CHECK: Stmt_for_j +; CHECK: ReadAccess := [Reduction Type: NONE] [Scalar: 1] +; CHECK-NEXT: [N] -> { Stmt_for_j[i0, i1] -> MemRef_init[] }; +; CHECK: MustWriteAccess := [Reduction Type: NONE] [Scalar: 0] +; CHECK-NEXT: [N] -> { Stmt_for_j[i0, i1] -> MemRef_A[i1] }; + %init_plus_two = add i64 %init, 2 + %scevgep = getelementptr i64, i64* %A, i64 %indvar.j + store i64 %init_plus_two, i64* %scevgep + %indvar.j.next = add nsw i64 %indvar.j, 1 + %exitcond.j = icmp eq i64 %indvar.j.next, %N + br i1 %exitcond.j, label %for.i.end, label %for.j + +for.i.end: + %exitcond.i = icmp eq i64 %indvar.i.next, %N + br i1 %exitcond.i, label %return, label %for.i + +return: + ret void +} + +; CHECK-LABEL: Function: g +define void @g(i64* noalias %A, i64 %N, i64* noalias %init_ptr) nounwind { +entry: + br label %for.i + +for.i: + %indvar.i = phi i64 [ 0, %entry ], [ %indvar.i.next, %for.i.end ] + %indvar.i.next = add nsw i64 %indvar.i, 1 + br label %entry.next + +entry.next: +; CHECK: Stmt_entry_next + %init = load i64, i64* %init_ptr +; CHECK: ReadAccess := [Reduction Type: NONE] [Scalar: 0] +; CHECK-NEXT: [N] -> { Stmt_entry_next[i0] -> MemRef_init_ptr[0] }; +; CHECK: MustWriteAccess := [Reduction Type: NONE] [Scalar: 1] +; CHECK-NEXT: [N] -> { Stmt_entry_next[i0] -> MemRef_init[] }; + br label %for.j + +for.j: +; CHECK: Stmt_for_j + %indvar.j = phi i64 [ 0, %entry.next ], [ %indvar.j.next, %for.j ] + %scevgep = getelementptr i64, i64* %A, i64 %indvar.j + store i64 %init, i64* %scevgep +; CHECK: ReadAccess := [Reduction Type: NONE] [Scalar: 1] +; CHECK-NEXT: [N] -> { Stmt_for_j[i0, i1] -> MemRef_init[] }; +; CHECK: MustWriteAccess := [Reduction Type: NONE] [Scalar: 0] +; CHECK-NEXT: [N] -> { Stmt_for_j[i0, i1] -> MemRef_A[i1] }; + %indvar.j.next = add nsw i64 %indvar.j, 1 + %exitcond.j = icmp eq i64 %indvar.j.next, %N + br i1 %exitcond.j, label %for.i.end, label %for.j + +for.i.end: + %exitcond.i = icmp eq i64 %indvar.i.next, %N + br i1 %exitcond.i, label %return, label %for.i + +return: + ret void +}