Coverage Report

Created: 2017-06-27 13:53

/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/tools/polly/lib/Transform/DeadCodeElimination.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- DeadCodeElimination.cpp - Eliminate dead iteration  ----------------===//
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
// The polyhedral dead code elimination pass analyses a SCoP to eliminate
11
// statement instances that can be proven dead.
12
// As a consequence, the code generated for this SCoP may execute a statement
13
// less often. This means, a statement may be executed only in certain loop
14
// iterations or it may not even be part of the generated code at all.
15
//
16
// This code:
17
//
18
//    for (i = 0; i < N; i++)
19
//        arr[i] = 0;
20
//    for (i = 0; i < N; i++)
21
//        arr[i] = 10;
22
//    for (i = 0; i < N; i++)
23
//        arr[i] = i;
24
//
25
// is e.g. simplified to:
26
//
27
//    for (i = 0; i < N; i++)
28
//        arr[i] = i;
29
//
30
// The idea and the algorithm used was first implemented by Sven Verdoolaege in
31
// the 'ppcg' tool.
32
//
33
//===----------------------------------------------------------------------===//
34
35
#include "polly/DependenceInfo.h"
36
#include "polly/LinkAllPasses.h"
37
#include "polly/Options.h"
38
#include "polly/ScopInfo.h"
39
#include "llvm/Support/CommandLine.h"
40
#include "isl/flow.h"
41
#include "isl/map.h"
42
#include "isl/set.h"
43
#include "isl/union_map.h"
44
#include "isl/union_set.h"
45
46
#include "isl-noexceptions.h"
47
48
using namespace llvm;
49
using namespace polly;
50
51
namespace {
52
53
cl::opt<int> DCEPreciseSteps(
54
    "polly-dce-precise-steps",
55
    cl::desc("The number of precise steps between two approximating "
56
             "iterations. (A value of -1 schedules another approximation stage "
57
             "before the actual dead code elimination."),
58
    cl::ZeroOrMore, cl::init(-1), cl::cat(PollyCategory));
59
60
class DeadCodeElim : public ScopPass {
61
public:
62
  static char ID;
63
8
  explicit DeadCodeElim() : ScopPass(ID) {}
64
65
  /// Remove dead iterations from the schedule of @p S.
66
  bool runOnScop(Scop &S) override;
67
68
  /// Register all analyses and transformation required.
69
  void getAnalysisUsage(AnalysisUsage &AU) const override;
70
71
private:
72
  /// Return the set of live iterations.
73
  ///
74
  /// The set of live iterations are all iterations that write to memory and for
75
  /// which we can not prove that there will be a later write that _must_
76
  /// overwrite the same memory location and is consequently the only one that
77
  /// is visible after the execution of the SCoP.
78
  ///
79
  isl::union_set getLiveOut(Scop &S);
80
  bool eliminateDeadCode(Scop &S, int PreciseSteps);
81
};
82
} // namespace
83
84
char DeadCodeElim::ID = 0;
85
86
// To compute the live outs, we compute for the data-locations that are
87
// must-written to the last statement that touches these locations. On top of
88
// this we add all statements that perform may-write accesses.
89
//
90
// We could be more precise by removing may-write accesses for which we know
91
// that they are overwritten by a must-write after. However, at the moment the
92
// only may-writes we introduce access the full (unbounded) array, such that
93
// bounded write accesses can not overwrite all of the data-locations. As
94
// this means may-writes are in the current situation always live, there is
95
// no point in trying to remove them from the live-out set.
96
7
isl::union_set DeadCodeElim::getLiveOut(Scop &S) {
97
7
  isl::union_map Schedule = isl::manage(S.getSchedule());
98
7
  isl::union_map MustWrites = isl::manage(S.getMustWrites());
99
7
  isl::union_map WriteIterations = MustWrites.reverse();
100
7
  isl::union_map WriteTimes = WriteIterations.apply_range(Schedule);
101
7
102
7
  isl::union_map LastWriteTimes = WriteTimes.lexmax();
103
7
  isl::union_map LastWriteIterations =
104
7
      LastWriteTimes.apply_range(Schedule.reverse());
105
7
106
7
  isl::union_set Live = LastWriteIterations.range();
107
7
  isl::union_map MayWrites = isl::manage(S.getMayWrites());
108
7
  Live = Live.unite(MayWrites.domain());
109
7
  return Live.coalesce();
110
7
}
111
112
/// Performs polyhedral dead iteration elimination by:
113
/// o Assuming that the last write to each location is live.
114
/// o Following each RAW dependency from a live iteration backwards and adding
115
///   that iteration to the live set.
116
///
117
/// To ensure the set of live iterations does not get too complex we always
118
/// combine a certain number of precise steps with one approximating step that
119
/// simplifies the life set with an affine hull.
120
8
bool DeadCodeElim::eliminateDeadCode(Scop &S, int PreciseSteps) {
121
8
  DependenceInfo &DI = getAnalysis<DependenceInfo>();
122
8
  const Dependences &D = DI.getDependences(Dependences::AL_Statement);
123
8
124
8
  if (!D.hasValidDependences())
125
1
    return false;
126
8
127
7
  isl::union_set Live = getLiveOut(S);
128
7
  isl::union_map Dep = isl::manage(
129
7
      D.getDependences(Dependences::TYPE_RAW | Dependences::TYPE_RED));
130
7
  Dep = Dep.reverse();
131
7
132
7
  if (PreciseSteps == -1)
133
6
    Live = Live.affine_hull();
134
7
135
7
  isl::union_set OriginalDomain = isl::manage(S.getDomains());
136
7
  int Steps = 0;
137
8
  while (
true8
)
{8
138
8
    Steps++;
139
8
140
8
    isl::union_set Extra = Live.apply(Dep);
141
8
142
8
    if (Extra.is_subset(Live))
143
7
      break;
144
8
145
1
    Live = Live.unite(Extra);
146
1
147
1
    if (
Steps > PreciseSteps1
)
{0
148
0
      Steps = 0;
149
0
      Live = Live.affine_hull();
150
0
    }
151
1
152
1
    Live = Live.intersect(OriginalDomain);
153
1
  }
154
7
155
7
  Live = Live.coalesce();
156
7
157
7
  bool Changed = S.restrictDomains(Live.copy());
158
7
159
7
  // FIXME: We can probably avoid the recomputation of all dependences by
160
7
  // updating them explicitly.
161
7
  if (Changed)
162
5
    DI.recomputeDependences(Dependences::AL_Statement);
163
7
  return Changed;
164
8
}
165
166
8
bool DeadCodeElim::runOnScop(Scop &S) {
167
8
  return eliminateDeadCode(S, DCEPreciseSteps);
168
8
}
169
170
8
void DeadCodeElim::getAnalysisUsage(AnalysisUsage &AU) const {
171
8
  ScopPass::getAnalysisUsage(AU);
172
8
  AU.addRequired<DependenceInfo>();
173
8
}
174
175
0
Pass *polly::createDeadCodeElimPass() { return new DeadCodeElim(); }
176
177
41.0k
INITIALIZE_PASS_BEGIN41.0k
(DeadCodeElim, "polly-dce",41.0k
178
41.0k
                      "Polly - Remove dead iterations", false, false)
179
41.0k
INITIALIZE_PASS_DEPENDENCY(DependenceInfo)
180
41.0k
INITIALIZE_PASS_DEPENDENCY(ScopInfoRegionPass)
181
41.0k
INITIALIZE_PASS_END(DeadCodeElim, "polly-dce", "Polly - Remove dead iterations",
182
                    false, false)