Coverage Report

Created: 2018-08-14 02:14

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/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 && isParallel(L))
66
15
        OS << "Loop is parallel.\n";
67
18
      else if (CheckParallel)
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
  LLVM_DEBUG(dbgs() << "Loop :\t" << L->getHeader()->getName() << ":\n");
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
          .release();
88
33
89
33
  LLVM_DEBUG(dbgs() << "Dependences :\t" << stringFromIslObj(Deps) << "\n");
90
33
91
33
  isl_union_map *Schedule = getScheduleForLoop(S, L);
92
33
  LLVM_DEBUG(dbgs() << "Schedule: \t" << stringFromIslObj(Schedule) << "\n");
93
33
94
33
  IsParallel = D.isParallel(Schedule, Deps, MinDepDistPtr);
95
33
  isl_union_map_free(Schedule);
96
33
  return IsParallel;
97
33
}
98
99
33
bool PolyhedralInfo::isParallel(Loop *L) const { return checkParallel(L); }
100
101
33
const Scop *PolyhedralInfo::getScopContainingLoop(Loop *L) const {
102
33
  assert((SI) && "ScopInfoWrapperPass is required by PolyhedralInfo pass!\n");
103
33
  for (auto &It : *SI) {
104
33
    Region *R = It.first;
105
33
    if (R->contains(L))
106
33
      return It.second.get();
107
33
  }
108
33
  
return nullptr0
;
109
33
}
110
111
//  Given a Loop and the containing SCoP, we compute the partial schedule
112
//  by taking union of individual schedules of each ScopStmt within the loop
113
//  and projecting out the inner dimensions from the range of the schedule.
114
//   for (i = 0; i < n; i++)
115
//      for (j = 0; j < n; j++)
116
//        A[j] = 1;  //Stmt
117
//
118
//  The original schedule will be
119
//    Stmt[i0, i1] -> [i0, i1]
120
//  The schedule for the outer loop will be
121
//    Stmt[i0, i1] -> [i0]
122
//  The schedule for the inner loop will be
123
//    Stmt[i0, i1] -> [i0, i1]
124
__isl_give isl_union_map *PolyhedralInfo::getScheduleForLoop(const Scop *S,
125
33
                                                             Loop *L) const {
126
33
  isl_union_map *Schedule = isl_union_map_empty(S->getParamSpace().release());
127
33
  int CurrDim = S->getRelativeLoopDepth(L);
128
33
  LLVM_DEBUG(dbgs() << "Relative loop depth:\t" << CurrDim << "\n");
129
33
  assert(CurrDim >= 0 && "Loop in region should have at least depth one");
130
33
131
39
  for (auto &SS : *S) {
132
39
    if (L->contains(SS.getSurroundingLoop())) {
133
33
134
33
      unsigned int MaxDim = SS.getNumIterators();
135
33
      LLVM_DEBUG(dbgs() << "Maximum depth of Stmt:\t" << MaxDim << "\n");
136
33
      isl_map *ScheduleMap = SS.getSchedule().release();
137
33
      assert(
138
33
          ScheduleMap &&
139
33
          "Schedules that contain extension nodes require special handling.");
140
33
141
33
      ScheduleMap = isl_map_project_out(ScheduleMap, isl_dim_out, CurrDim + 1,
142
33
                                        MaxDim - CurrDim - 1);
143
33
      ScheduleMap = isl_map_set_tuple_id(ScheduleMap, isl_dim_in,
144
33
                                         SS.getDomainId().release());
145
33
      Schedule =
146
33
          isl_union_map_union(Schedule, isl_union_map_from_map(ScheduleMap));
147
33
    }
148
39
  }
149
33
  Schedule = isl_union_map_coalesce(Schedule);
150
33
  return Schedule;
151
33
}
152
153
char PolyhedralInfo::ID = 0;
154
155
0
Pass *polly::createPolyhedralInfoPass() { return new PolyhedralInfo(); }
156
157
44.2k
INITIALIZE_PASS_BEGIN(PolyhedralInfo, "polyhedral-info",
158
44.2k
                      "Polly - Interface to polyhedral analysis engine", false,
159
44.2k
                      false);
160
44.2k
INITIALIZE_PASS_DEPENDENCY(DependenceInfoWrapperPass);
161
44.2k
INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass);
162
44.2k
INITIALIZE_PASS_DEPENDENCY(ScopInfoWrapperPass);
163
44.2k
INITIALIZE_PASS_END(PolyhedralInfo, "polyhedral-info",
164
                    "Polly - Interface to polyhedral analysis engine", false,
165
                    false)