Index: include/polly/PolyhedralInfo.h =================================================================== --- include/polly/PolyhedralInfo.h +++ include/polly/PolyhedralInfo.h @@ -45,6 +45,16 @@ /// @return Returns true, if loop is parallel false otherwise. bool isParallel(llvm::Loop *L) const; + /// @brief Check if a given loop is vectorizable and compute the minimum + /// dependence distance. + /// + /// @param L The loop. + /// @param VF The vectorization fector. Update if bigger VF possible. + /// + /// @return Returns true if loop is vectorizable for the given @p VF, false + /// otherwise. + bool isVectorizable(llvm::Loop *L, int *VF) const; + /// @brief Return the SCoP containing the @p L loop. /// /// @param L The loop. Index: lib/Analysis/PolyhedralInfo.cpp =================================================================== --- lib/Analysis/PolyhedralInfo.cpp +++ lib/Analysis/PolyhedralInfo.cpp @@ -59,6 +59,7 @@ void PolyhedralInfo::print(raw_ostream &OS, const Module *) const { auto &LI = getAnalysis().getLoopInfo(); + int VF = 2; for (auto *TopLevelLoop : LI) { for (auto *L : depth_first(TopLevelLoop)) { OS.indent(2) << L->getHeader()->getName() << ":\t"; @@ -66,6 +67,10 @@ OS << "Loop is parallel.\n"; else if (CheckParallel) OS << "Loop is not parallel.\n"; + if (CheckVectorizable && isVectorizable(L, &VF)) + OS << "Loop is vectorizable.\n"; + else if (CheckVectorizable) + OS << "Loop is not vectorizable.\n"; } } } @@ -96,6 +101,47 @@ bool PolyhedralInfo::isParallel(Loop *L) const { return checkParallel(L); } +/// @brief Get the minimum dependence distance from the quasi-affine expression +/// @p Dist and update it to @p User +static isl_stat getMinDependenceDistance(__isl_take isl_set *Set, + __isl_take isl_aff *Dist, void *User) { + int *MinDepDistance = (int *)User; + + isl_val *Distance = isl_aff_get_constant_val(Dist); + int Flag = isl_val_cmp_si(Distance, *MinDepDistance); + if (Flag != 1) + *MinDepDistance = (int)isl_val_get_num_si(Distance); + + isl_val_free(Distance); + isl_set_free(Set); + isl_aff_free(Dist); + return isl_stat_ok; +} + +bool PolyhedralInfo::isVectorizable(Loop *L, int *VF) const { + const Scop *S = getScopContainingLoop(L); + if (!S) + return false; + + isl_pw_aff *MinDistancePtr = nullptr; + bool IsVectorizable = checkParallel(L, &MinDistancePtr); + // Currently handle only constant distances + if (!isl_pw_aff_is_empty(MinDistancePtr) && + !isl_pw_aff_involves_nan(MinDistancePtr) && + isl_pw_aff_is_cst(MinDistancePtr)) { + int MinDepDistance = 999; + + isl_pw_aff_foreach_piece(MinDistancePtr, getMinDependenceDistance, + &MinDepDistance); + IsVectorizable = (*VF <= MinDepDistance) ? true : false; + *VF = IsVectorizable ? MinDepDistance : *VF; + DEBUG(dbgs() << "Min Dep Distance(constant):\t" << MinDepDistance << "\n"); + } + + isl_pw_aff_free(MinDistancePtr); + return IsVectorizable; +} + const Scop *PolyhedralInfo::getScopContainingLoop(Loop *L) const { assert((SI) && "ScopInfoWrapperPass is required by PolyhedralInfo pass!\n"); for (auto &It : *SI) { Index: test/Isl/Ast/OpenMP/multiple_loops_outer_parallel.ll =================================================================== --- test/Isl/Ast/OpenMP/multiple_loops_outer_parallel.ll +++ test/Isl/Ast/OpenMP/multiple_loops_outer_parallel.ll @@ -1,13 +1,16 @@ ; RUN: opt %loadPolly -polly-ast -polly-parallel -polly-parallel-force -analyze < %s | FileCheck %s ; RUN: opt %loadPolly -polyhedral-info -polly-check-parallel -analyze < %s | FileCheck %s -check-prefix=PINFO +; RUN: opt %loadPolly -polyhedral-info -polly-check-vectorizable -analyze < %s | FileCheck %s -check-prefix=PINFO-VEC ; ; void jd(int *A) { ; CHECK: #pragma omp parallel for ; PINFO: for.cond2: Loop is parallel. +; PINFO-VEC: for.cond2: Loop is vectorizable. ; for (int i = 0; i < 1024; i++) ; A[i] = 1; ; CHECK: #pragma omp parallel for ; PINFO: for.cond: Loop is parallel. +; PINFO-VEC: for.cond: Loop is vectorizable. ; for (int i = 0; i < 1024; i++) ; A[i] = A[i] * 2; ; } Index: test/Isl/Ast/dependence_distance_constant.ll =================================================================== --- test/Isl/Ast/dependence_distance_constant.ll +++ test/Isl/Ast/dependence_distance_constant.ll @@ -1,12 +1,15 @@ ; RUN: opt %loadPolly -polly-ast -polly-ast-detect-parallel -analyze < %s | FileCheck %s ; RUN: opt %loadPolly -polyhedral-info -polly-check-parallel -analyze < %s | FileCheck %s -check-prefix=PINFO +; RUN: opt %loadPolly -polyhedral-info -polly-check-vectorizable -analyze < %s | FileCheck %s -check-prefix=PINFO-VEC ; ; void f(int *A, int N) { ; CHECK: #pragma minimal dependence distance: 1 ; PINFO: for.cond: Loop is not parallel. +; PINFO-VEC: for.cond: Loop is not vectorizable. ; for (int j = 0; j < N; j++) ; CHECK: #pragma minimal dependence distance: 8 ; PINFO-NEXT: for.cond1: Loop is not parallel. +; PINFO-VEC: for.cond1: Loop is vectorizable. ; for (int i = 0; i < N; i++) ; A[i + 8] = A[i] + 1; ; } Index: test/Isl/Ast/dependence_distance_multiple_constant.ll =================================================================== --- test/Isl/Ast/dependence_distance_multiple_constant.ll +++ test/Isl/Ast/dependence_distance_multiple_constant.ll @@ -1,9 +1,11 @@ ; RUN: opt %loadPolly -basicaa -polly-ast -polly-ast-detect-parallel -analyze < %s | FileCheck %s ; RUN: opt %loadPolly -polyhedral-info -polly-check-parallel -analyze < %s | FileCheck %s -check-prefix=PINFO +; RUN: opt %loadPolly -polyhedral-info -polly-check-vectorizable -analyze < %s | FileCheck %s -check-prefix=PINFO-VEC ; ; void f(int *restrict A, int *restrict B, int N) { ; CHECK: #pragma minimal dependence distance: 5 ; PINFO: for.cond: Loop is not parallel. +; PINFO-VEC: for.cond: Loop is vectorizable. ; for (int i = 0; i < N; i++) { ; A[i + 7] = A[i] + 1; ; B[i + 5] = B[i] + 1; Index: test/Isl/Ast/dependence_distance_varying.ll =================================================================== --- test/Isl/Ast/dependence_distance_varying.ll +++ test/Isl/Ast/dependence_distance_varying.ll @@ -1,9 +1,11 @@ ; RUN: opt %loadPolly -polly-ast -polly-ast-detect-parallel -analyze < %s | FileCheck %s ; RUN: opt %loadPolly -polyhedral-info -polly-check-parallel -analyze < %s | FileCheck %s -check-prefix=PINFO +; RUN: opt %loadPolly -polyhedral-info -polly-check-vectorizable -analyze < %s | FileCheck %s -check-prefix=PINFO-VEC ; ; void f(int *A, int N) { ; CHECK: #pragma minimal dependence distance: ((N - 1) % 2) + 1 ; PINFO: for.cond: Loop is not parallel. +; PINFO-VEC: for.cond: Loop is not vectorizable. ; for (int i = 0; i < N; i++) ; A[i] = A[N - i] + 1; ; } Index: test/Isl/Ast/dependence_distance_varying_multiple.ll =================================================================== --- test/Isl/Ast/dependence_distance_varying_multiple.ll +++ test/Isl/Ast/dependence_distance_varying_multiple.ll @@ -1,10 +1,12 @@ ; RUN: opt %loadPolly -basicaa -polly-ast -polly-ast-detect-parallel -analyze < %s | FileCheck %s ; RUN: opt %loadPolly -polyhedral-info -polly-check-parallel -analyze < %s | FileCheck %s -check-prefix=PINFO +; RUN: opt %loadPolly -polyhedral-info -polly-check-vectorizable -analyze < %s | FileCheck %s -check-prefix=PINFO-VEC ; ; void f(int *restrict A, int *restrict B, int *restrict C, int *restrict D, ; int *restrict E, int N) { ; CHECK: #pragma minimal dependence distance: N >= 35 ? 1 : N >= 17 && N <= 34 ? 2 : 5 ; PINFO: for.cond: Loop is not parallel. +; PINFO-VEC: for.cond: Loop is not vectorizable. ; for (int i = 0; i < N; i++) { ; A[i] = A[100 - 2 * i] + 1; ; B[i] = B[100 - 3 * i] + 1;