[Polly][GSoC 2016]Add PolyhedralInfo pass- new interface to Polly Analysis

[cs14mtech11017]

Summary

Adding a new pass PolyhedralInfo. This pass will be the interface to Polly.
Initially, we will provide the following interfaces, which could be extended at a later phase:-
#IsParallel(Loop *L) - return a bool depending on whether the loop is parallel or not for the given program order.
#IsVectorizable(Loop *L) - return minimum dependence distance for the loop. This is work in progress.

Please provide your suggestions and directions so that I can take a better approach.

[jdoerfert]

Some comments are inlined. Also add test cases please.

include/polly/PolyhedralInfo.h

21 ↗

(On Diff #61146)

Please do not open the namespace but use llvm:: where needed.

38 ↗

(On Diff #61146)

Unused!

45 ↗

(On Diff #61146)

Documentation is missing for all these functions.

lib/Analysis/PolyhedralInfo.cpp

37 ↗

(On Diff #61146)

Do we really require all these passes transitive?

38 ↗

(On Diff #61146)

Not neeeded.

45 ↗

(On Diff #61146)

Not neeeded.

53 ↗

(On Diff #61146)

Maybe also print the "name" of the loop not only if it is parallel or not.

61 ↗

(On Diff #61146)

Move this down before the conditional where it is possibly changed.

66 ↗

(On Diff #61146)

Maybe change the "getDependences" interface to accept const Scops first.

71 ↗

(On Diff #61146)

If you do not include reduction dependences here you need to make that clear in the documentation.

73 ↗

(On Diff #61146)

Does this work? I would have expected you would get the initial schedule from the Scop.

77 ↗

(On Diff #61146)

Why do you check isParallel twice, you can simply add the TC_RED dependences above.

[jdoerfert]

More comments

lib/Analysis/PolyhedralInfo.cpp

99 ↗

(On Diff #62630)

I would not declare variables early if they have an actual limited scope. The two comments below show I would declare them.

102 ↗

(On Diff #62630)

for (auto *BB : LI->blocks())

104 ↗

(On Diff #62630)

auto *Stmt = S->getStmtFor(BB);
if (!Stmt)
  continue;

114 ↗

(On Diff #62630)

I just recalled that you can use the Scop::getRelativeLoopDepth(Loop *) function here too.

[cs14mtech11017]

Fixed corrupt memory issues due to isl objects. Added test cases.

[cs14mtech11017]

Updated the patch with necessary changes. Added unit test cases.

include/polly/PolyhedralInfo.h

38 ↗

(On Diff #61146)

Removed. Will add as per need.

lib/Analysis/PolyhedralInfo.cpp

37 ↗

(On Diff #61146)

DependenceInfoWrapperPass and ScopInfoWrapperPass are required transitive. LoopInfoWrapperPass is not. Updated accordingly.

66 ↗

(On Diff #61146)

Anyhow we will require a constant cast. Dependences::calculateDependences(Scop &S) is being called from DependenceInfoWrapperPass. It is better to do it in this interface itself.

100 ↗

(On Diff #63213)

It was WIP, now updated accordingly.

[jdoerfert]

Some minor remarks but after they are fixed it looks good to go in.

include/polly/PolyhedralInfo.h

23 ↗

(On Diff #63213)

Please do not open the namespace but use llvm:: where needed.

46 ↗

(On Diff #63213)

"in its outermost dimension" doesn't make sense. Just remove that part.

lib/Analysis/PolyhedralInfo.cpp

52 ↗

(On Diff #63213)

"Loop" is a bad variable name as it is a type, use L or something else.

116 ↗

(On Diff #63213)

if (!SS)
  continue;

lowers the indention

test/Isl/Ast/OpenMP/nested_loop_both_parallel.ll

55 ↗

(On Diff #63213)

Why is there a check not omp parallel for but you report a parallel loop?

[cs14mtech11017]

Updated according to review comments.

[cs14mtech11017]

test/Isl/Ast/OpenMP/nested_loop_both_parallel.ll

55 ↗

(On Diff #63523)

Its a restriction on nested openmp parallel pragma where the outer loop is also openmp parallel.

[jdoerfert]

Does this pass LNT when it is part of the Polly pipeline [profitable but also unprofitable] or are there any crashes? If not I would go ahead and commit it for you.

[cs14mtech11017]

I tested this with lnt and there are no crashes. However, there exists few failed cases with and without this patch.

[jdoerfert]

LGTM.

[mreisinger]

lib/Analysis/PolyhedralInfo.cpp

15 ↗

(On Diff #64124)

Maybe reformulate "This interface provides basic interface".

polly/trunk/include/polly/LinkAllPasses.h

 llvm::Pass *createDependenceInfoWrapperPassPass();
 llvm::Pass *createDOTOnlyPrinterPass();
 llvm::Pass *createDOTOnlyViewerPass();
 llvm::Pass *createDOTPrinterPass();
 llvm::Pass *createDOTViewerPass();
 llvm::Pass *createJSONExporterPass();
 llvm::Pass *createJSONImporterPass();
 llvm::Pass *createPollyCanonicalizePass();
+llvm::Pass *createPolyhedralInfoPass();
 llvm::Pass *createScopDetectionPass();
 llvm::Pass *createScopInfoRegionPassPass();
 llvm::Pass *createScopInfoWrapperPassPass();
 llvm::Pass *createIslAstInfoPass();
 llvm::Pass *createCodeGenerationPass();
 #ifdef GPU_CODEGEN
 llvm::Pass *createPPCGCodeGenerationPass();
 #endif
PollyForcePassLinking() {
     polly::createDOTOnlyViewerPass();
     polly::createDOTPrinterPass();
     polly::createDOTViewerPass();
     polly::createJSONExporterPass();
     polly::createJSONImporterPass();
     polly::createScopDetectionPass();
     polly::createScopInfoRegionPassPass();
     polly::createPollyCanonicalizePass();
+    polly::createPolyhedralInfoPass();
     polly::createIslAstInfoPass();
     polly::createCodeGenerationPass();
 #ifdef GPU_CODEGEN
     polly::createPPCGCodeGenerationPass();
 #endif
     polly::createIslScheduleOptimizerPass();
   }
 } PollyForcePassLinking; // Force link by creating a global definition.

polly/trunk/include/polly/PolyhedralInfo.h

+//===- polly/PolyhedralInfo.h - PolyhedralInfo class definition -*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+///
+/// This file contains the declaration of the PolyhedralInfo class, which will
+/// provide an interface to expose polyhedral analysis information of Polly.
+///
+/// This is work in progress. We will add more API's as an when deemed required.
+//===----------------------------------------------------------------------===///
+
+#ifndef POLLY_POLYHEDRAL_INFO_H
+#define POLLY_POLYHEDRAL_INFO_H
+
+#include "llvm/Pass.h"
+#include "isl/ctx.h"
+#include "isl/union_map.h"
+
+namespace llvm {
+class Loop;
+}
+
+namespace polly {
+
+class Scop;
+class ScopInfoWrapperPass;
+class DependenceInfoWrapperPass;
+
+class PolyhedralInfo : public llvm::FunctionPass {
+public:
+  static char ID; // Pass identification, replacement for typeid
+
+  /// @brief Construct a new PolyhedralInfo pass.
+  PolyhedralInfo() : FunctionPass(ID) {}
+  ~PolyhedralInfo() {}
+
+  /// @brief   Check if a given loop is parallel.
+  ///
+  /// @param L The loop.
+  ///
+  /// @return  Returns true, if loop is parallel false otherwise.
+  bool isParallel(llvm::Loop *L) const;
+
+  /// @brief   Return the SCoP containing the @p L loop.
+  ///
+  /// @param L The loop.
+  ///
+  /// @return  Returns the SCoP containing the given loop.
+  ///          Returns null if the loop is not contained in any SCoP.
+  const Scop *getScopContainingLoop(llvm::Loop *L) const;
+
+  /// @brief   Computes the partial schedule for the given @p L loop.
+  ///
+  /// @param S The SCoP containing the given loop
+  /// @param L The loop.
+  ///
+  /// @return  Returns the partial schedule for the given loop
+  __isl_give isl_union_map *getScheduleForLoop(const Scop *S,
+                                               llvm::Loop *L) const;
+
+  /// @brief Get the SCoP and dependence analysis information for @p F.
+  bool runOnFunction(llvm::Function &F) override;
+
+  /// @brief Release the internal memory.
+  void releaseMemory() override {}
+
+  /// @brief Print to @p OS if each dimension of a loop nest is parallel or not.
+  void print(llvm::raw_ostream &OS,
+             const llvm::Module *M = nullptr) const override;
+
+  /// @brief Register all analyses and transformation required.
+  void getAnalysisUsage(llvm::AnalysisUsage &AU) const override;
+
+private:
+  /// @brief   Check if a given loop is parallel or vectorizable.
+  ///
+  /// @param L             The loop.
+  /// @param MinDepDistPtr If not nullptr, the minimal dependence distance will
+  ///                      be returned at the address of that pointer
+  ///
+  /// @return  Returns true if loop is parallel or vectorizable, false
+  ///          otherwise.
+  bool checkParallel(llvm::Loop *L,
+                     __isl_give isl_pw_aff **MinDepDistPtr = nullptr) const;
+
+  ScopInfoWrapperPass *SI;
+  DependenceInfoWrapperPass *DI;
+};
+
+} // end namespace polly
+
+namespace llvm {
+class PassRegistry;
+void initializePolyhedralInfoPass(llvm::PassRegistry &);
+}
+
+#endif

polly/trunk/lib/Analysis/PolyhedralInfo.cpp

+//===--------- PolyhedralInfo.cpp  - Create Scops from LLVM IR-------------===//
+///
+///                     The LLVM Compiler Infrastructure
+///
+/// This file is distributed under the University of Illinois Open Source
+/// License. See LICENSE.TXT for details.
+///
+//===----------------------------------------------------------------------===//
+///
+/// An interface to the Polyhedral analysis engine(Polly) of LLVM.
+///
+/// This pass provides an interface to the polyhedral analysis performed by
+/// Polly.
+///
+/// This interface provides basic interface like isParallel, isVectorizable
+/// that can be used in LLVM transformation passes.
+///
+/// Work in progress, this file is subject to change.
+//===----------------------------------------------------------------------===//
+
+#include "polly/PolyhedralInfo.h"
+#include "polly/DependenceInfo.h"
+#include "polly/LinkAllPasses.h"
+#include "polly/Options.h"
+#include "polly/ScopInfo.h"
+#include "polly/Support/GICHelper.h"
+#include "llvm/Analysis/LoopInfo.h"
+#include "llvm/Support/Debug.h"
+#include <isl/map.h>
+#include <isl/union_map.h>
+
+using namespace llvm;
+using namespace polly;
+
+#define DEBUG_TYPE "polyhedral-info"
+
+static cl::opt<bool> CheckParallel("polly-check-parallel",
+                                   cl::desc("Check for parallel loops"),
+                                   cl::Hidden, cl::init(false), cl::ZeroOrMore,
+                                   cl::cat(PollyCategory));
+
+static cl::opt<bool> CheckVectorizable("polly-check-vectorizable",
+                                       cl::desc("Check for vectorizable loops"),
+                                       cl::Hidden, cl::init(false),
+                                       cl::ZeroOrMore, cl::cat(PollyCategory));
+
+void PolyhedralInfo::getAnalysisUsage(AnalysisUsage &AU) const {
+  AU.addRequiredTransitive<DependenceInfoWrapperPass>();
+  AU.addRequired<LoopInfoWrapperPass>();
+  AU.addRequiredTransitive<ScopInfoWrapperPass>();
+  AU.setPreservesAll();
+}
+
+bool PolyhedralInfo::runOnFunction(Function &F) {
+  DI = &getAnalysis<DependenceInfoWrapperPass>();
+  SI = &getAnalysis<ScopInfoWrapperPass>();
+  return false;
+}
+
+void PolyhedralInfo::print(raw_ostream &OS, const Module *) const {
+  auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
+  for (auto *TopLevelLoop : LI) {
+    for (auto *L : depth_first(TopLevelLoop)) {
+      OS.indent(2) << L->getHeader()->getName() << ":\t";
+      if (CheckParallel && isParallel(L))
+        OS << "Loop is parallel.\n";
+      else if (CheckParallel)
+        OS << "Loop is not parallel.\n";
+    }
+  }
+}
+
+bool PolyhedralInfo::checkParallel(Loop *L, isl_pw_aff **MinDepDistPtr) const {
+  bool IsParallel;
+  const Scop *S = getScopContainingLoop(L);
+  if (!S)
+    return false;
+  const Dependences &D =
+      DI->getDependences(const_cast<Scop *>(S), Dependences::AL_Access);
+  if (!D.hasValidDependences())
+    return false;
+  DEBUG(dbgs() << "Loop :\t" << L->getHeader()->getName() << ":\n");
+
+  isl_union_map *Deps =
+      D.getDependences(Dependences::TYPE_RAW | Dependences::TYPE_WAW |
+                       Dependences::TYPE_WAR | Dependences::TYPE_RED);
+  DEBUG(dbgs() << "Dependences :\t" << stringFromIslObj(Deps) << "\n");
+
+  isl_union_map *Schedule = getScheduleForLoop(S, L);
+  DEBUG(dbgs() << "Schedule: \t" << stringFromIslObj(Schedule) << "\n");
+
+  IsParallel = D.isParallel(Schedule, Deps, MinDepDistPtr);
+  isl_union_map_free(Schedule);
+  return IsParallel;
+}
+
+bool PolyhedralInfo::isParallel(Loop *L) const { return checkParallel(L); }
+
+const Scop *PolyhedralInfo::getScopContainingLoop(Loop *L) const {
+  assert((SI) && "ScopInfoWrapperPass is required by PolyhedralInfo pass!\n");
+  for (auto &It : *SI) {
+    Region *R = It.first;
+    if (R->contains(L))
+      return It.second.get();
+  }
+  return nullptr;
+}
+
+//  Given a Loop and the containing SCoP, we compute the partial schedule
+//  by taking union of individual schedules of each ScopStmt within the loop
+//  and projecting out the inner dimensions from the range of the schedule.
+//   for (i = 0; i < n; i++)
+//      for (j = 0; j < n; j++)
+//        A[j] = 1;  //Stmt
+//
+//  The original schedule will be
+//    Stmt[i0, i1] -> [i0, i1]
+//  The schedule for the outer loop will be
+//    Stmt[i0, i1] -> [i0]
+//  The schedule for the inner loop will be
+//    Stmt[i0, i1] -> [i0, i1]
+__isl_give isl_union_map *PolyhedralInfo::getScheduleForLoop(const Scop *S,
+                                                             Loop *L) const {
+  isl_union_map *Schedule = isl_union_map_empty(S->getParamSpace());
+  int CurrDim = S->getRelativeLoopDepth(L);
+  DEBUG(dbgs() << "Relative loop depth:\t" << CurrDim << "\n");
+  assert(CurrDim >= 0 && "Loop in region should have at least depth one");
+
+  for (auto *BB : L->blocks()) {
+    auto *SS = S->getStmtFor(BB);
+    if (!SS)
+      continue;
+
+    unsigned int MaxDim = SS->getNumIterators();
+    DEBUG(dbgs() << "Maximum depth of Stmt:\t" << MaxDim << "\n");
+    auto *ScheduleMap = SS->getSchedule();
+
+    ScheduleMap = isl_map_project_out(ScheduleMap, isl_dim_out, CurrDim + 1,
+                                      MaxDim - CurrDim - 1);
+    ScheduleMap =
+        isl_map_set_tuple_id(ScheduleMap, isl_dim_in, SS->getDomainId());
+    Schedule =
+        isl_union_map_union(Schedule, isl_union_map_from_map(ScheduleMap));
+  }
+
+  Schedule = isl_union_map_coalesce(Schedule);
+  return Schedule;
+}
+
+char PolyhedralInfo::ID = 0;
+
+Pass *polly::createPolyhedralInfoPass() { return new PolyhedralInfo(); }
+
+INITIALIZE_PASS_BEGIN(PolyhedralInfo, "polyhedral-info",
+                      "Polly - Interface to polyhedral analysis engine", false,
+                      false);
+INITIALIZE_PASS_DEPENDENCY(DependenceInfoWrapperPass);
+INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass);
+INITIALIZE_PASS_DEPENDENCY(ScopInfoWrapperPass);
+INITIALIZE_PASS_END(PolyhedralInfo, "polyhedral-info",
+                    "Polly - Interface to polyhedral analysis engine", false,
+                    false)

polly/trunk/lib/CMakeLists.txt

 
 set(POLLY_HEADER_FILES)
 if (MSVC_IDE OR XCODE)
   file(GLOB_RECURSE POLLY_HEADER_FILES "${POLLY_SOURCE_DIR}/include/polly/*.h")
 endif ()
 
 add_polly_library(Polly
   Analysis/DependenceInfo.cpp
+  Analysis/PolyhedralInfo.cpp
   Analysis/ScopDetection.cpp
   Analysis/ScopDetectionDiagnostic.cpp
   Analysis/ScopInfo.cpp
   Analysis/ScopBuilder.cpp
   Analysis/ScopGraphPrinter.cpp
   Analysis/ScopPass.cpp
   CodeGen/BlockGenerators.cpp
   ${ISL_CODEGEN_FILES}

polly/trunk/lib/Support/RegisterPasses.cpp

 
 #include "polly/RegisterPasses.h"
 #include "polly/Canonicalization.h"
 #include "polly/CodeGen/CodeGeneration.h"
 #include "polly/CodeGen/CodegenCleanup.h"
 #include "polly/DependenceInfo.h"
 #include "polly/LinkAllPasses.h"
 #include "polly/Options.h"
+#include "polly/PolyhedralInfo.h"
 #include "polly/ScopDetection.h"
 #include "polly/ScopInfo.h"
 #include "llvm/Analysis/CFGPrinter.h"
 #include "llvm/IR/LegacyPassManager.h"
 #include "llvm/Transforms/IPO.h"
 #include "llvm/Transforms/IPO/PassManagerBuilder.h"
 #include "llvm/Transforms/Scalar.h"
 #include "llvm/Transforms/Vectorize.h"
static cl::opt<bool> PollyOnlyPrinter(
     cl::value_desc("Run the Polly DOT printer at -O3 (no BB content"),
     cl::init(false), cl::cat(PollyCategory));
 
 static cl::opt<bool>
     CFGPrinter("polly-view-cfg",
                cl::desc("Show the Polly CFG right after code generation"),
                cl::Hidden, cl::init(false), cl::cat(PollyCategory));
 
+static cl::opt<bool>
+    EnablePolyhedralInfo("polly-enable-polyhedralinfo",
+                         cl::desc("Enable polyhedral interface of Polly"),
+                         cl::Hidden, cl::init(false), cl::cat(PollyCategory));
+
 namespace polly {
 void initializePollyPasses(PassRegistry &Registry) {
   initializeCodeGenerationPass(Registry);
 
 #ifdef GPU_CODEGEN
   initializePPCGCodeGenerationPass(Registry);
 #endif
   initializeCodePreparationPass(Registry);
   initializeDeadCodeElimPass(Registry);
   initializeDependenceInfoPass(Registry);
   initializeDependenceInfoWrapperPassPass(Registry);
   initializeJSONExporterPass(Registry);
   initializeJSONImporterPass(Registry);
   initializeIslAstInfoPass(Registry);
   initializeIslScheduleOptimizerPass(Registry);
   initializePollyCanonicalizePass(Registry);
+  initializePolyhedralInfoPass(Registry);
   initializeScopDetectionPass(Registry);
   initializeScopInfoRegionPassPass(Registry);
   initializeScopInfoWrapperPassPass(Registry);
   initializeCodegenCleanupPass(Registry);
 }
 
 /// @brief Register Polly passes such that they form a polyhedral optimizer.
 ///
void registerPollyPasses(llvm::legacy::PassManagerBase &PM) {
   if (PollyOnlyViewer)
     PM.add(polly::createDOTOnlyViewerPass());
   if (PollyPrinter)
     PM.add(polly::createDOTPrinterPass());
   if (PollyOnlyPrinter)
     PM.add(polly::createDOTOnlyPrinterPass());
 
   PM.add(polly::createScopInfoRegionPassPass());
+  if (EnablePolyhedralInfo)
+    PM.add(polly::createPolyhedralInfoPass());
 
   if (ImportJScop)
     PM.add(polly::createJSONImporterPass());
 
   if (DeadCodeElim)
     PM.add(polly::createDeadCodeElimPass());
 
   if (Target == TARGET_GPU) {

polly/trunk/test/Isl/Ast/OpenMP/multiple_loops_outer_parallel.ll

 ; 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
 ;
 ;       void jd(int *A) {
 ; CHECK:  #pragma omp parallel for
+; PINFO:  for.cond2: Loop is parallel.
 ;         for (int i = 0; i < 1024; i++)
 ;           A[i] = 1;
 ; CHECK:  #pragma omp parallel for
+; PINFO:  for.cond: Loop is parallel.
 ;         for (int i = 0; i < 1024; i++)
 ;           A[i] = A[i] * 2;
 ;       }
 ;
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 
 define void @jd(i32* %A) {
 entry:

polly/trunk/test/Isl/Ast/OpenMP/nested_loop_both_parallel.ll

 ; RUN: opt %loadPolly -polly-ast -polly-parallel -analyze < %s | FileCheck %s
+; RUN: opt %loadPolly -polyhedral-info -polly-check-parallel -analyze < %s | FileCheck %s -check-prefix=PINFO
 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"
 
 ; for (i = 0; i < 1024; i++)
 ;   for (j = 0; j < 1024; j++)
 ;     A[i][j] = 1;
 
 @A = common global [1024 x [1024 x i32]] zeroinitializer
 define void @bar() {

 
 ; CHECK:     #pragma omp parallel for
 ; CHECK:     for (int c0 = 0; c0 <= 1023; c0 += 1)
 ; CHECK-NOT:   #pragma omp parallel for
 ; CHECK:       #pragma simd
 ; CHECK-NOT:   #pragma omp parallel for
 ; CHECK:       for (int c1 = 0; c1 <= 1023; c1 += 1)
 ; CHECK:         Stmt_loop_body(c0, c1);
+;
+; PINFO:      loop.i: Loop is parallel.
+; PINFO-NEXT: loop.j: Loop is parallel.

polly/trunk/test/Isl/Ast/OpenMP/nested_loop_both_parallel_parametric.ll

 ; 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
 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"
 ; int A[1024][1024];
 ; void bar(int n) {
 ;   for (i = 0; i < n; i++)
 ;     for (j = 0; j < n; j++)
 ;       A[i][j] = 1;
 ; }
 @A = common global [1024 x [1024 x i32]] zeroinitializer

 }
 
 ; CHECK: if (n <= 1024)
 ; CHECK:   #pragma omp parallel for
 ; CHECK:   for (int c0 = 0; c0 < n; c0 += 1)
 ; CHECK:     #pragma simd
 ; CHECK:     for (int c1 = 0; c1 < n; c1 += 1)
 ; CHECK:       Stmt_loop_body(c0, c1);
+
+; PINFO:      loop.i: Loop is parallel.
+; PINFO-NEXT: loop.j: Loop is parallel.

polly/trunk/test/Isl/Ast/OpenMP/nested_loop_inner_parallel.ll

 ; 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
 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"
 
 ; for (i = 0; i < n; i++)
 ;   for (j = 0; j < n; j++)
 ;     A[j] = 1;
 
 @A = common global [1024 x i32] zeroinitializer
 define void @bar(i64 %n) {
ret:
   ret void
 }
 
 ; CHECK: for (int c0 = 0; c0 < n; c0 += 1)
 ; CHECK:   #pragma simd
 ; CHECK:   #pragma omp parallel for
 ; CHECK:   for (int c1 = 0; c1 < n; c1 += 1)
 ; CHECK:     Stmt_loop_body(c0, c1);
+
+; PINFO:      loop.i: Loop is not parallel.
+; PINFO-NEXT: loop.j: Loop is parallel.

polly/trunk/test/Isl/Ast/OpenMP/nested_loop_outer_parallel.ll

 ; RUN: opt %loadPolly -polly-ast -polly-parallel -analyze < %s | FileCheck %s
+; RUN: opt %loadPolly -polyhedral-info -polly-check-parallel -analyze < %s | FileCheck %s -check-prefix=PINFO
 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"
 
 ; for (i = 0; i < n; i++)
 ;   for (j = 0; j < n; j++)
 ;     A[i] = 1;
 
 @A = common global [1024 x i32] zeroinitializer
 define void @bar(i64 %n) {
ret:
   fence seq_cst
   ret void
 }
 
 ; CHECK: #pragma omp parallel for
 ; CHECK: for (int c0 = 0; c0 < n; c0 += 1)
 ; CHECK:   for (int c1 = 0; c1 < n; c1 += 1)
 ; CHECK:     Stmt_loop_body(c0, c1);
+
+; PINFO:      loop.i: Loop is parallel.
+; PINFO-NEXT: loop.j: Loop is not parallel.

polly/trunk/test/Isl/Ast/OpenMP/single_loop_param_non_parallel.ll

 ; RUN: opt %loadPolly -polly-ast -polly-parallel -analyze < %s | FileCheck %s
+; RUN: opt %loadPolly -polyhedral-info -polly-check-parallel -analyze < %s | FileCheck %s -check-prefix=PINFO
 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"
 
 ; for (i = 0; i < n; i++)
 ;   A[0] = i;
 
 @A = common global [1024 x i32] zeroinitializer
 define void @bar(i64 %n) {
 start:

 
 ret:
   fence seq_cst
   ret void
 }
 
 ; CHECK: for (int c0 = 0; c0 < n; c0 += 1)
 ; CHECK:   Stmt_loop_body(c0)
+; PINFO: loop.header: Loop is not parallel.

polly/trunk/test/Isl/Ast/OpenMP/single_loop_param_parallel.ll

 ; 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
 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"
 
 ; for (i = 0; i < n; i++)
 ;   A[i] = 1;
 
 @A = common global [1024 x i32] zeroinitializer
 define void @bar(i64 %n) {
 start:
ret:
   fence seq_cst
   ret void
 }
 
 ; CHECK: #pragma simd
 ; CHECK: #pragma omp parallel for
 ; CHECK: for (int c0 = 0; c0 < n; c0 += 1)
 ; CHECK:   Stmt_loop_body(c0)
+; PINFO: loop.header: Loop is parallel.

polly/trunk/test/Isl/Ast/OpenMP/single_loop_param_parallel_computeout.ll

 ; RUN: opt %loadPolly -polly-ast -polly-parallel -polly-dependences-computeout=1 -analyze < %s | FileCheck %s
+; RUN: opt %loadPolly -polyhedral-info -polly-check-parallel -analyze < %s | FileCheck %s -check-prefix=PINFO
 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"
 
 ; for (i = 0; i < n; i++)
 ;   A[i] = 1;
 
 @A = common global [1024 x i32] zeroinitializer
 define void @bar(i64 %n) {
 start:
ret:
   fence seq_cst
   ret void
 }
 
 ; CHECK-NOT: #pragma simd
 ; CHECK-NOT: #pragma omp parallel for
 ; CHECK: for (int c0 = 0; c0 < n; c0 += 1)
 ; CHECK:   Stmt_loop_body(c0)
+; PINFO: loop.header: Loop is parallel.

polly/trunk/test/Isl/Ast/dependence_distance_constant.ll

 ; 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
 ;
 ;        void f(int *A, int N) {
 ; CHECK:   #pragma minimal dependence distance: 1
+; PINFO:   for.cond: Loop is not parallel.
 ;          for (int j = 0; j < N; j++)
-; CHECK:     #pragma minimal dependence distance: 8
-;            for (int i = 0; i < N; i++)
-;              A[i + 8] = A[i] + 1;
+; CHECK:      #pragma minimal dependence distance: 8
+; PINFO-NEXT: for.cond1: Loop is not parallel.
+;             for (int i = 0; i < N; i++)
+;               A[i + 8] = A[i] + 1;
 ;        }
 ;
 target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-n32-S64"
 
 define void @f(i32* %A, i32 %N) {
 entry:
   br label %for.cond
 

polly/trunk/test/Isl/Ast/dependence_distance_multiple_constant.ll

 ; 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
 ;
 ;        void f(int *restrict A, int *restrict B, int N) {
 ; CHECK:   #pragma minimal dependence distance: 5
+; PINFO:   for.cond: Loop is not parallel.
 ;          for (int i = 0; i < N; i++) {
 ;            A[i + 7] = A[i] + 1;
 ;            B[i + 5] = B[i] + 1;
 ;          }
 ;        }
 ;
 target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-n32-S64"
 

polly/trunk/test/Isl/Ast/dependence_distance_parametric.ll

 ; 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
 ;
 ;        void f(int *A, int N, int c) {
 ; CHECK:   #pragma minimal dependence distance: 1
+; PINFO:   for.cond: Loop is not parallel.
 ;          for (int j = 0; j < N; j++)
-; CHECK:     #pragma minimal dependence distance: max(-c, c)
-;            for (int i = 0; i < N; i++)
-;              A[i + c] = A[i] + 1;
+; CHECK:      #pragma minimal dependence distance: max(-c, c)
+; PINFO-NEXT: for.cond1: Loop is not parallel.
+;             for (int i = 0; i < N; i++)
+;               A[i + c] = A[i] + 1;
 ;        }
 ;
 target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-n32-S64"
 
 define void @f(i32* %A, i32 %N, i32 %c) {
 entry:
   br label %for.cond
 

polly/trunk/test/Isl/Ast/dependence_distance_parametric_expr.ll

 ; 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
 ;
 ;        void f(int *A, int N, int c, int v) {
 ; CHECK:   #pragma minimal dependence distance: 1
+; PINFO:   for.cond: Loop is not parallel.
 ;          for (int j = 0; j < N; j++)
-; CHECK:     #pragma minimal dependence distance: max(-c - v, c + v)
-;            for (int i = 0; i < N; i++)
-;              A[i + c + v] = A[i] + 1;
+; CHECK:      #pragma minimal dependence distance: max(-c - v, c + v)
+; PINFO-NEXT: for.cond1: Loop is not parallel.
+;             for (int i = 0; i < N; i++)
+;               A[i + c + v] = A[i] + 1;
 ;        }
 ;
 target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-n32-S64"
 
 define void @f(i32* %A, i32 %N, i32 %c, i32 %v) {
 entry:
   br label %for.cond
 

polly/trunk/test/Isl/Ast/dependence_distance_varying.ll

 ; 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
 ;
 ;         void f(int *A, int N) {
 ; CHECK:    #pragma minimal dependence distance: ((N - 1) % 2) + 1
+; PINFO:    for.cond: Loop is not parallel.
 ;           for (int i = 0; i < N; i++)
 ;             A[i] = A[N - i] + 1;
 ;         }
 ;
 target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-n32-S64"
 
 define void @f(i32* %A, i32 %N) {
 entry:

polly/trunk/test/Isl/Ast/dependence_distance_varying_in_outer_loop.ll

 ; RUN: opt %loadPolly -polly-canonicalize -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
 ;
 ;        void f(int *restrict A, int *restrict sum) {
 ; CHECK:   #pragma minimal dependence distance: 1
+; PINFO:    for.cond: Loop is not parallel.
 ;          for (int j = 0; j < 1024; j++)
-; CHECK:     #pragma minimal dependence distance: 1
-;            for (int i = j; i < 1024; i++)
-;              A[i - 3] = A[j] * 2 + A[j] + 2;
+; CHECK:      #pragma minimal dependence distance: 1
+; PINFO-NEXT: for.cond1: Loop is not parallel.
+;             for (int i = j; i < 1024; i++)
+;               A[i - 3] = A[j] * 2 + A[j] + 2;
 ;        }
 ;
 target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-n32-S64"
 
 define void @f(i32* noalias %A, i32* noalias %sum) {
 entry:
   br label %for.cond
 

polly/trunk/test/Isl/Ast/dependence_distance_varying_multiple.ll

 ; 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
 ;
 ;        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.
 ;          for (int i = 0; i < N; i++) {
 ;            A[i] = A[100 - 2 * i] + 1;
 ;            B[i] = B[100 - 3 * i] + 1;
 ;            C[i] = C[100 - 4 * i] + 1;
 ;            D[i] = D[100 - 5 * i] + 1;
 ;            E[i] = E[100 - 6 * i] + 1;
 ;          }
 ;        }

polly/trunk/test/Isl/Ast/reduction_clauses_multidimensional_access.ll

 ; 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
 ;
 ; CHECK: #pragma known-parallel reduction (^ : sum)
 ;        void f(int N, int M, int P, int sum[P][M]) {
+; PINFO:   for.cond: Loop is not parallel.
 ;          for (int i = 0; i < N; i++)
-;            for (int j = 0; j < P; j++)
-; CHECK:       #pragma simd
-;              for (int k = 0; k < M; k++)
-;                sum[j][k] ^= j;
+; PINFO-NEXT: for.cond1: Loop is parallel.
+;             for (int j = 0; j < P; j++)
+; CHECK:        #pragma simd
+; PINFO-NEXT:   for.cond4: Loop is parallel.
+;               for (int k = 0; k < M; k++)
+;                 sum[j][k] ^= j;
 ;        }
 ;
 target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-n32-S64"
 
 define void @f(i32 %N, i32 %M, i32 %P, i32* %sum) {
 entry:
   br label %for.cond
 

polly/trunk/test/Isl/Ast/reduction_in_one_dimension.ll

 ; 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
 ;
 ; Verify that we won't privatize anything in the outer dimension
 ;
 ; CHECK:    #pragma known-parallel
+; PINFO:    for.cond: Loop is parallel.
 ; CHECK:    for (int c0 = 0; c0 < 2 * n; c0 += 1)
 ; CHECK:      #pragma simd reduction
+; PINFO-NEXT: for.cond1: Loop is not parallel.
 ; CHECK:      for (int c1 = 0; c1 <= 1023; c1 += 1)
 ; CHECK:        Stmt_for_body3(c0, c1);
 ;
 ;    void foo(int *A, long n) {
 ;      for (long i = 0; i < 2 * n; i++)
 ;        for (long j = 0; j < 1024; j++)
 ;          A[i] += i;
 ;    }

polly/trunk/test/Isl/Ast/reduction_loop_reversal.ll

 ; RUN: opt %loadPolly -polly-import-jscop-dir=%S -polly-import-jscop -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
 ;
 ; CHECK-NOT: #pragma simd{{\s*$}}
 ; CHECK: #pragma simd reduction
 ; CHECK: Stmt_S0(n - c1)
 ; CHECK: #pragma simd{{\s*$}}
 ; CHECK: Stmt_S1(n - c1)
 ;
+; PINFO:       for.cond2: Loop is parallel.
+; PINFO-NEXT:  for.cond: Loop is not parallel.
+;
 ;    void rlr(int *A, long n) {
 ;      for (long i = 0; i < 2 * n; i++)
 ; S0:    A[0] += i;
 ;      for (long i = 0; i < 2 * n; i++)
 ; S1:    A[i + 1] = 1;
 ;    }
 ;
 target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-n32-S64"

polly/trunk/test/Isl/Ast/reduction_modulo_schedule.ll

 ; RUN: opt %loadPolly -polly-import-jscop-dir=%S -polly-import-jscop -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
 ;
 ; CHECK:          #pragma known-parallel reduction (+ : A)
 ; CHECK-NEXT:     for (int c0 = 0; c0 <= 2; c0 += 1) {
 ; CHECK-NEXT:       if (c0 == 1) {
 ; CHECK-NEXT:         #pragma simd
 ; CHECK-NEXT:         for (int c1 = 0; c1 < 2 * n; c1 += 1)
 ; CHECK-NEXT:           Stmt_S1(c1);
 ; CHECK-NEXT:       } else
 ; CHECK-NEXT:         #pragma simd reduction (+ : A)
 ; CHECK-NEXT:         for (int c1 = c0 / 2; c1 < 2 * n; c1 += 2)
 ; CHECK-NEXT:           Stmt_S0(c1);
 ; CHECK-NEXT:     }
 ;
+; PINFO:      for.cond2: Loop is parallel.
+; PINFO-NEXT: for.cond: Loop is not parallel.
+;
 ;    void rms(int *A, long n) {
 ;      for (long i = 0; i < 2 * n; i++)
 ; S0:    A[0] += i;
 ;      for (long i = 0; i < 2 * n; i++)
 ; S1:    A[i + 1] = 1;
 ;    }
 ;
 target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-n32-S64"