Coverage Report

Created: 2019-04-21 19:17

/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
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4
// See https://llvm.org/LICENSE.txt for license information.
5
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6
//
7
//===----------------------------------------------------------------------===//
8
//
9
// An interface to the Polyhedral analysis engine(Polly) of LLVM.
10
//
11
// This pass provides an interface to the polyhedral analysis performed by
12
// Polly.
13
//
14
// This interface provides basic interface like isParallel, isVectorizable
15
// that can be used in LLVM transformation passes.
16
//
17
// Work in progress, this file is subject to change.
18
//
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/union_map.h"
30
31
using namespace llvm;
32
using namespace polly;
33
34
#define DEBUG_TYPE "polyhedral-info"
35
36
static cl::opt<bool> CheckParallel("polly-check-parallel",
37
                                   cl::desc("Check for parallel loops"),
38
                                   cl::Hidden, cl::init(false), cl::ZeroOrMore,
39
                                   cl::cat(PollyCategory));
40
41
static cl::opt<bool> CheckVectorizable("polly-check-vectorizable",
42
                                       cl::desc("Check for vectorizable loops"),
43
                                       cl::Hidden, cl::init(false),
44
                                       cl::ZeroOrMore, cl::cat(PollyCategory));
45
46
19
void PolyhedralInfo::getAnalysisUsage(AnalysisUsage &AU) const {
47
19
  AU.addRequiredTransitive<DependenceInfoWrapperPass>();
48
19
  AU.addRequired<LoopInfoWrapperPass>();
49
19
  AU.addRequiredTransitive<ScopInfoWrapperPass>();
50
19
  AU.setPreservesAll();
51
19
}
52
53
19
bool PolyhedralInfo::runOnFunction(Function &F) {
54
19
  DI = &getAnalysis<DependenceInfoWrapperPass>();
55
19
  SI = getAnalysis<ScopInfoWrapperPass>().getSI();
56
19
  return false;
57
19
}
58
59
19
void PolyhedralInfo::print(raw_ostream &OS, const Module *) const {
60
19
  auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
61
22
  for (auto *TopLevelLoop : LI) {
62
33
    for (auto *L : depth_first(TopLevelLoop)) {
63
33
      OS.indent(2) << L->getHeader()->getName() << ":\t";
64
33
      if (CheckParallel && isParallel(L))
65
15
        OS << "Loop is parallel.\n";
66
18
      else if (CheckParallel)
67
18
        OS << "Loop is not parallel.\n";
68
33
    }
69
22
  }
70
19
}
71
72
33
bool PolyhedralInfo::checkParallel(Loop *L, isl_pw_aff **MinDepDistPtr) const {
73
33
  bool IsParallel;
74
33
  const Scop *S = getScopContainingLoop(L);
75
33
  if (!S)
76
0
    return false;
77
33
  const Dependences &D =
78
33
      DI->getDependences(const_cast<Scop *>(S), Dependences::AL_Access);
79
33
  if (!D.hasValidDependences())
80
0
    return false;
81
33
  LLVM_DEBUG(dbgs() << "Loop :\t" << L->getHeader()->getName() << ":\n");
82
33
83
33
  isl_union_map *Deps =
84
33
      D.getDependences(Dependences::TYPE_RAW | Dependences::TYPE_WAW |
85
33
                       Dependences::TYPE_WAR | Dependences::TYPE_RED)
86
33
          .release();
87
33
88
33
  LLVM_DEBUG(dbgs() << "Dependences :\t" << stringFromIslObj(Deps) << "\n");
89
33
90
33
  isl_union_map *Schedule = getScheduleForLoop(S, L);
91
33
  LLVM_DEBUG(dbgs() << "Schedule: \t" << stringFromIslObj(Schedule) << "\n");
92
33
93
33
  IsParallel = D.isParallel(Schedule, Deps, MinDepDistPtr);
94
33
  isl_union_map_free(Schedule);
95
33
  return IsParallel;
96
33
}
97
98
33
bool PolyhedralInfo::isParallel(Loop *L) const { return checkParallel(L); }
99
100
33
const Scop *PolyhedralInfo::getScopContainingLoop(Loop *L) const {
101
33
  assert((SI) && "ScopInfoWrapperPass is required by PolyhedralInfo pass!\n");
102
33
  for (auto &It : *SI) {
103
33
    Region *R = It.first;
104
33
    if (R->contains(L))
105
33
      return It.second.get();
106
33
  }
107
33
  
return nullptr0
;
108
33
}
109
110
//  Given a Loop and the containing SCoP, we compute the partial schedule
111
//  by taking union of individual schedules of each ScopStmt within the loop
112
//  and projecting out the inner dimensions from the range of the schedule.
113
//   for (i = 0; i < n; i++)
114
//      for (j = 0; j < n; j++)
115
//        A[j] = 1;  //Stmt
116
//
117
//  The original schedule will be
118
//    Stmt[i0, i1] -> [i0, i1]
119
//  The schedule for the outer loop will be
120
//    Stmt[i0, i1] -> [i0]
121
//  The schedule for the inner loop will be
122
//    Stmt[i0, i1] -> [i0, i1]
123
__isl_give isl_union_map *PolyhedralInfo::getScheduleForLoop(const Scop *S,
124
33
                                                             Loop *L) const {
125
33
  isl_union_map *Schedule = isl_union_map_empty(S->getParamSpace().release());
126
33
  int CurrDim = S->getRelativeLoopDepth(L);
127
33
  LLVM_DEBUG(dbgs() << "Relative loop depth:\t" << CurrDim << "\n");
128
33
  assert(CurrDim >= 0 && "Loop in region should have at least depth one");
129
33
130
39
  for (auto &SS : *S) {
131
39
    if (L->contains(SS.getSurroundingLoop())) {
132
33
133
33
      unsigned int MaxDim = SS.getNumIterators();
134
33
      LLVM_DEBUG(dbgs() << "Maximum depth of Stmt:\t" << MaxDim << "\n");
135
33
      isl_map *ScheduleMap = SS.getSchedule().release();
136
33
      assert(
137
33
          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 = isl_map_set_tuple_id(ScheduleMap, isl_dim_in,
143
33
                                         SS.getDomainId().release());
144
33
      Schedule =
145
33
          isl_union_map_union(Schedule, isl_union_map_from_map(ScheduleMap));
146
33
    }
147
39
  }
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
47.0k
INITIALIZE_PASS_BEGIN(PolyhedralInfo, "polyhedral-info",
157
47.0k
                      "Polly - Interface to polyhedral analysis engine", false,
158
47.0k
                      false);
159
47.0k
INITIALIZE_PASS_DEPENDENCY(DependenceInfoWrapperPass);
160
47.0k
INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass);
161
47.0k
INITIALIZE_PASS_DEPENDENCY(ScopInfoWrapperPass);
162
47.0k
INITIALIZE_PASS_END(PolyhedralInfo, "polyhedral-info",
163
                    "Polly - Interface to polyhedral analysis engine", false,
164
                    false)