Coverage Report

Created: 2017-06-23 12:40

/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/tools/polly/lib/Analysis/PolyhedralInfo.cpp
Line
Count
Source (jump to first uncovered line)
1
//===--------- PolyhedralInfo.cpp  - Create Scops from LLVM IR-------------===//
2
///
3
///                     The LLVM Compiler Infrastructure
4
///
5
/// This file is distributed under the University of Illinois Open Source
6
/// License. See LICENSE.TXT for details.
7
///
8
//===----------------------------------------------------------------------===//
9
///
10
/// An interface to the Polyhedral analysis engine(Polly) of LLVM.
11
///
12
/// This pass provides an interface to the polyhedral analysis performed by
13
/// Polly.
14
///
15
/// This interface provides basic interface like isParallel, isVectorizable
16
/// that can be used in LLVM transformation passes.
17
///
18
/// Work in progress, this file is subject to change.
19
//===----------------------------------------------------------------------===//
20
21
#include "polly/PolyhedralInfo.h"
22
#include "polly/DependenceInfo.h"
23
#include "polly/LinkAllPasses.h"
24
#include "polly/Options.h"
25
#include "polly/ScopInfo.h"
26
#include "polly/Support/GICHelper.h"
27
#include "llvm/Analysis/LoopInfo.h"
28
#include "llvm/Support/Debug.h"
29
#include <isl/map.h>
30
#include <isl/union_map.h>
31
32
using namespace llvm;
33
using namespace polly;
34
35
#define DEBUG_TYPE "polyhedral-info"
36
37
static cl::opt<bool> CheckParallel("polly-check-parallel",
38
                                   cl::desc("Check for parallel loops"),
39
                                   cl::Hidden, cl::init(false), cl::ZeroOrMore,
40
                                   cl::cat(PollyCategory));
41
42
static cl::opt<bool> CheckVectorizable("polly-check-vectorizable",
43
                                       cl::desc("Check for vectorizable loops"),
44
                                       cl::Hidden, cl::init(false),
45
                                       cl::ZeroOrMore, cl::cat(PollyCategory));
46
47
19
void PolyhedralInfo::getAnalysisUsage(AnalysisUsage &AU) const {
48
19
  AU.addRequiredTransitive<DependenceInfoWrapperPass>();
49
19
  AU.addRequired<LoopInfoWrapperPass>();
50
19
  AU.addRequiredTransitive<ScopInfoWrapperPass>();
51
19
  AU.setPreservesAll();
52
19
}
53
54
19
bool PolyhedralInfo::runOnFunction(Function &F) {
55
19
  DI = &getAnalysis<DependenceInfoWrapperPass>();
56
19
  SI = getAnalysis<ScopInfoWrapperPass>().getSI();
57
19
  return false;
58
19
}
59
60
19
void PolyhedralInfo::print(raw_ostream &OS, const Module *) const {
61
19
  auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
62
22
  for (auto *TopLevelLoop : LI) {
63
33
    for (auto *L : depth_first(TopLevelLoop)) {
64
33
      OS.indent(2) << L->getHeader()->getName() << ":\t";
65
33
      if (
CheckParallel && 33
isParallel(L)33
)
66
15
        OS << "Loop is parallel.\n";
67
18
      else 
if (18
CheckParallel18
)
68
18
        OS << "Loop is not parallel.\n";
69
33
    }
70
22
  }
71
19
}
72
73
33
bool PolyhedralInfo::checkParallel(Loop *L, isl_pw_aff **MinDepDistPtr) const {
74
33
  bool IsParallel;
75
33
  const Scop *S = getScopContainingLoop(L);
76
33
  if (!S)
77
0
    return false;
78
33
  const Dependences &D =
79
33
      DI->getDependences(const_cast<Scop *>(S), Dependences::AL_Access);
80
33
  if (!D.hasValidDependences())
81
0
    return false;
82
33
  
DEBUG33
(dbgs() << "Loop :\t" << L->getHeader()->getName() << ":\n");33
83
33
84
33
  isl_union_map *Deps =
85
33
      D.getDependences(Dependences::TYPE_RAW | Dependences::TYPE_WAW |
86
33
                       Dependences::TYPE_WAR | Dependences::TYPE_RED);
87
33
  DEBUG(dbgs() << "Dependences :\t" << stringFromIslObj(Deps) << "\n");
88
33
89
33
  isl_union_map *Schedule = getScheduleForLoop(S, L);
90
33
  DEBUG(dbgs() << "Schedule: \t" << stringFromIslObj(Schedule) << "\n");
91
33
92
33
  IsParallel = D.isParallel(Schedule, Deps, MinDepDistPtr);
93
33
  isl_union_map_free(Schedule);
94
33
  return IsParallel;
95
33
}
96
97
33
bool PolyhedralInfo::isParallel(Loop *L) const { return checkParallel(L); }
98
99
33
const Scop *PolyhedralInfo::getScopContainingLoop(Loop *L) const {
100
33
  assert((SI) && "ScopInfoWrapperPass is required by PolyhedralInfo pass!\n");
101
33
  for (auto &It : *SI) {
102
33
    Region *R = It.first;
103
33
    if (R->contains(L))
104
33
      return It.second.get();
105
33
  }
106
0
  return nullptr;
107
33
}
108
109
//  Given a Loop and the containing SCoP, we compute the partial schedule
110
//  by taking union of individual schedules of each ScopStmt within the loop
111
//  and projecting out the inner dimensions from the range of the schedule.
112
//   for (i = 0; i < n; i++)
113
//      for (j = 0; j < n; j++)
114
//        A[j] = 1;  //Stmt
115
//
116
//  The original schedule will be
117
//    Stmt[i0, i1] -> [i0, i1]
118
//  The schedule for the outer loop will be
119
//    Stmt[i0, i1] -> [i0]
120
//  The schedule for the inner loop will be
121
//    Stmt[i0, i1] -> [i0, i1]
122
__isl_give isl_union_map *PolyhedralInfo::getScheduleForLoop(const Scop *S,
123
33
                                                             Loop *L) const {
124
33
  isl_union_map *Schedule = isl_union_map_empty(S->getParamSpace());
125
33
  int CurrDim = S->getRelativeLoopDepth(L);
126
33
  DEBUG(dbgs() << "Relative loop depth:\t" << CurrDim << "\n");
127
33
  assert(CurrDim >= 0 && "Loop in region should have at least depth one");
128
33
129
143
  for (auto *BB : L->blocks()) {
130
143
    auto *SS = S->getStmtFor(BB);
131
143
    if (!SS)
132
110
      continue;
133
143
134
33
    unsigned int MaxDim = SS->getNumIterators();
135
33
    DEBUG(dbgs() << "Maximum depth of Stmt:\t" << MaxDim << "\n");
136
33
    auto *ScheduleMap = SS->getSchedule();
137
33
    assert(ScheduleMap &&
138
33
           "Schedules that contain extension nodes require special handling.");
139
33
140
33
    ScheduleMap = isl_map_project_out(ScheduleMap, isl_dim_out, CurrDim + 1,
141
33
                                      MaxDim - CurrDim - 1);
142
33
    ScheduleMap =
143
33
        isl_map_set_tuple_id(ScheduleMap, isl_dim_in, SS->getDomainId());
144
33
    Schedule =
145
33
        isl_union_map_union(Schedule, isl_union_map_from_map(ScheduleMap));
146
33
  }
147
33
148
33
  Schedule = isl_union_map_coalesce(Schedule);
149
33
  return Schedule;
150
33
}
151
152
char PolyhedralInfo::ID = 0;
153
154
0
Pass *polly::createPolyhedralInfoPass() { return new PolyhedralInfo(); }
155
156
41.0k
INITIALIZE_PASS_BEGIN41.0k
(PolyhedralInfo, "polyhedral-info",41.0k
157
41.0k
                      "Polly - Interface to polyhedral analysis engine", false,
158
41.0k
                      false);
159
41.0k
INITIALIZE_PASS_DEPENDENCY(DependenceInfoWrapperPass);
160
41.0k
INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass);
161
41.0k
INITIALIZE_PASS_DEPENDENCY(ScopInfoWrapperPass);
162
41.0k
INITIALIZE_PASS_END(PolyhedralInfo, "polyhedral-info",
163
                    "Polly - Interface to polyhedral analysis engine", false,
164
                    false)