Coverage Report

Created: 2019-04-25 15:07

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