Coverage Report

Created: 2018-08-20 19:24

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/tools/polly/lib/Transform/MaximalStaticExpansion.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- MaximalStaticExpansion.cpp -----------------------------------------===//
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
// This pass fully expand the memory accesses of a Scop to get rid of
11
// dependencies.
12
//
13
//===----------------------------------------------------------------------===//
14
15
#include "polly/DependenceInfo.h"
16
#include "polly/LinkAllPasses.h"
17
#include "polly/ScopInfo.h"
18
#include "polly/ScopPass.h"
19
#include "polly/Support/GICHelper.h"
20
#include "polly/Support/ISLTools.h"
21
#include "llvm/ADT/SmallPtrSet.h"
22
#include "llvm/ADT/StringRef.h"
23
#include "llvm/Analysis/OptimizationRemarkEmitter.h"
24
#include "llvm/Pass.h"
25
#include "isl/isl-noexceptions.h"
26
#include "isl/union_map.h"
27
#include <cassert>
28
#include <limits>
29
#include <string>
30
#include <vector>
31
32
using namespace llvm;
33
using namespace polly;
34
35
14
#define DEBUG_TYPE "polly-mse"
36
37
namespace {
38
39
class MaximalStaticExpander : public ScopPass {
40
public:
41
  static char ID;
42
43
17
  explicit MaximalStaticExpander() : ScopPass(ID) {}
44
45
17
  ~MaximalStaticExpander() override = default;
46
47
  /// Expand the accesses of the SCoP.
48
  ///
49
  /// @param S The SCoP that must be expanded.
50
  bool runOnScop(Scop &S) override;
51
52
  /// Print the SCoP.
53
  ///
54
  /// @param OS The stream where to print.
55
  /// @param S The SCop that must be printed.
56
  void printScop(raw_ostream &OS, Scop &S) const override;
57
58
  /// Register all analyses and transformations required.
59
  void getAnalysisUsage(AnalysisUsage &AU) const override;
60
61
private:
62
  /// OptimizationRemarkEmitter object for displaying diagnostic remarks.
63
  OptimizationRemarkEmitter *ORE;
64
65
  /// Emit remark
66
  void emitRemark(StringRef Msg, Instruction *Inst);
67
68
  /// Return true if the SAI in parameter is expandable.
69
  ///
70
  /// @param SAI the SAI that need to be checked.
71
  /// @param Writes A set that will contains all the write accesses.
72
  /// @param Reads A set that will contains all the read accesses.
73
  /// @param S The SCop in which the SAI is in.
74
  /// @param Dependences The RAW dependences of the SCop.
75
  bool isExpandable(const ScopArrayInfo *SAI,
76
                    SmallPtrSetImpl<MemoryAccess *> &Writes,
77
                    SmallPtrSetImpl<MemoryAccess *> &Reads, Scop &S,
78
                    const isl::union_map &Dependences);
79
80
  /// Expand the MemoryAccess according to its domain.
81
  ///
82
  /// @param S The SCop in which the memory access appears in.
83
  /// @param MA The memory access that need to be expanded.
84
  ScopArrayInfo *expandAccess(Scop &S, MemoryAccess *MA);
85
86
  /// Filter the dependences to have only one related to current memory access.
87
  ///
88
  /// @param S The SCop in which the memory access appears in.
89
  /// @param MapDependences The dependences to filter.
90
  /// @param MA The memory access that need to be expanded.
91
  isl::union_map filterDependences(Scop &S,
92
                                   const isl::union_map &MapDependences,
93
                                   MemoryAccess *MA);
94
95
  /// Expand the MemoryAccess according to Dependences and already expanded
96
  /// MemoryAccesses.
97
  ///
98
  /// @param The SCop in which the memory access appears in.
99
  /// @param The memory access that need to be expanded.
100
  /// @param Dependences The RAW dependences of the SCop.
101
  /// @param ExpandedSAI The expanded SAI created during write expansion.
102
  /// @param Reverse if true, the Dependences union_map is reversed before
103
  /// intersection.
104
  void mapAccess(Scop &S, SmallPtrSetImpl<MemoryAccess *> &Accesses,
105
                 const isl::union_map &Dependences, ScopArrayInfo *ExpandedSAI,
106
                 bool Reverse);
107
108
  /// Expand PHI memory accesses.
109
  ///
110
  /// @param The SCop in which the memory access appears in.
111
  /// @param The ScopArrayInfo representing the PHI accesses to expand.
112
  /// @param Dependences The RAW dependences of the SCop.
113
  void expandPhi(Scop &S, const ScopArrayInfo *SAI,
114
                 const isl::union_map &Dependences);
115
};
116
} // namespace
117
118
#ifndef NDEBUG
119
/// Whether a dimension of a set is bounded (lower and upper) by a constant,
120
/// i.e. there are two constants Min and Max, such that every value x of the
121
/// chosen dimensions is Min <= x <= Max.
122
static bool isDimBoundedByConstant(isl::set Set, unsigned dim) {
123
  auto ParamDims = Set.dim(isl::dim::param);
124
  Set = Set.project_out(isl::dim::param, 0, ParamDims);
125
  Set = Set.project_out(isl::dim::set, 0, dim);
126
  auto SetDims = Set.dim(isl::dim::set);
127
  Set = Set.project_out(isl::dim::set, 1, SetDims - 1);
128
  return bool(Set.is_bounded());
129
}
130
#endif
131
132
char MaximalStaticExpander::ID = 0;
133
134
isl::union_map MaximalStaticExpander::filterDependences(
135
90
    Scop &S, const isl::union_map &Dependences, MemoryAccess *MA) {
136
90
  auto SAI = MA->getLatestScopArrayInfo();
137
90
138
90
  auto AccessDomainSet = MA->getAccessRelation().domain();
139
90
  auto AccessDomainId = AccessDomainSet.get_tuple_id();
140
90
141
90
  isl::union_map MapDependences = isl::union_map::empty(S.getParamSpace());
142
90
143
1.07k
  for (isl::map Map : Dependences.get_map_list()) {
144
1.07k
    // Filter out Statement to Statement dependences.
145
1.07k
    if (!Map.can_curry())
146
478
      continue;
147
594
148
594
    // Intersect with the relevant SAI.
149
594
    auto TmpMapDomainId =
150
594
        Map.get_space().domain().unwrap().range().get_tuple_id(isl::dim::set);
151
594
152
594
    ScopArrayInfo *UserSAI =
153
594
        static_cast<ScopArrayInfo *>(TmpMapDomainId.get_user());
154
594
155
594
    if (SAI != UserSAI)
156
462
      continue;
157
132
158
132
    // Get the correct S1[] -> S2[] dependence.
159
132
    auto NewMap = Map.factor_domain();
160
132
    auto NewMapDomainId = NewMap.domain().get_tuple_id();
161
132
162
132
    if (AccessDomainId.get() != NewMapDomainId.get())
163
42
      continue;
164
90
165
90
    // Add the corresponding map to MapDependences.
166
90
    MapDependences = MapDependences.add_map(NewMap);
167
90
  }
168
90
169
90
  return MapDependences;
170
90
}
171
172
bool MaximalStaticExpander::isExpandable(
173
    const ScopArrayInfo *SAI, SmallPtrSetImpl<MemoryAccess *> &Writes,
174
    SmallPtrSetImpl<MemoryAccess *> &Reads, Scop &S,
175
63
    const isl::union_map &Dependences) {
176
63
  if (SAI->isValueKind()) {
177
3
    Writes.insert(S.getValueDef(SAI));
178
3
    for (auto MA : S.getValueUses(SAI))
179
4
      Reads.insert(MA);
180
3
    return true;
181
60
  } else if (SAI->isPHIKind()) {
182
28
    auto Read = S.getPHIRead(SAI);
183
28
184
28
    auto StmtDomain = isl::union_set(Read->getStatement()->getDomain());
185
28
186
28
    auto Writes = S.getPHIIncomings(SAI);
187
28
188
28
    // Get the domain where all the writes are writing to.
189
28
    auto WriteDomain = isl::union_set::empty(S.getParamSpace());
190
28
191
38
    for (auto Write : Writes) {
192
38
      auto MapDeps = filterDependences(S, Dependences, Write);
193
38
      for (isl::map Map : MapDeps.get_map_list())
194
38
        WriteDomain = WriteDomain.add_set(Map.range());
195
38
    }
196
28
197
28
    // For now, read from original scalar is not possible.
198
28
    if (!StmtDomain.is_equal(WriteDomain)) {
199
8
      emitRemark(SAI->getName() + " read from its original value.",
200
8
                 Read->getAccessInstruction());
201
8
      return false;
202
8
    }
203
20
204
20
    return true;
205
32
  } else if (SAI->isExitPHIKind()) {
206
0
    // For now, we are not able to expand ExitPhi.
207
0
    emitRemark(SAI->getName() + " is a ExitPhi node.",
208
0
               S.getEnteringBlock()->getFirstNonPHI());
209
0
    return false;
210
0
  }
211
32
212
32
  int NumberWrites = 0;
213
90
  for (ScopStmt &Stmt : S) {
214
90
    auto StmtReads = isl::union_map::empty(S.getParamSpace());
215
90
    auto StmtWrites = isl::union_map::empty(S.getParamSpace());
216
90
217
186
    for (MemoryAccess *MA : Stmt) {
218
186
      // Check if the current MemoryAccess involved the current SAI.
219
186
      if (SAI != MA->getLatestScopArrayInfo())
220
140
        continue;
221
46
222
46
      // For now, we are not able to expand array where read come after write
223
46
      // (to the same location) in a same statement.
224
46
      auto AccRel = isl::union_map(MA->getAccessRelation());
225
46
      if (MA->isRead()) {
226
12
        // Reject load after store to same location.
227
12
        if (!StmtWrites.is_disjoint(AccRel)) {
228
2
          emitRemark(SAI->getName() + " has read after write to the same "
229
2
                                      "element in same statement. The "
230
2
                                      "dependences found during analysis may "
231
2
                                      "be wrong because Polly is not able to "
232
2
                                      "handle such case for now.",
233
2
                     MA->getAccessInstruction());
234
2
          return false;
235
2
        }
236
10
237
10
        StmtReads = StmtReads.unite(AccRel);
238
34
      } else {
239
34
        StmtWrites = StmtWrites.unite(AccRel);
240
34
      }
241
46
242
46
      // For now, we are not able to expand MayWrite.
243
46
      
if (44
MA->isMayWrite()44
) {
244
0
        emitRemark(SAI->getName() + " has a maywrite access.",
245
0
                   MA->getAccessInstruction());
246
0
        return false;
247
0
      }
248
44
249
44
      // For now, we are not able to expand SAI with more than one write.
250
44
      if (MA->isMustWrite()) {
251
34
        Writes.insert(MA);
252
34
        NumberWrites++;
253
34
        if (NumberWrites > 1) {
254
2
          emitRemark(SAI->getName() + " has more than 1 write access.",
255
2
                     MA->getAccessInstruction());
256
2
          return false;
257
2
        }
258
42
      }
259
42
260
42
      // Check if it is possible to expand this read.
261
42
      if (MA->isRead()) {
262
10
        // Get the domain of the current ScopStmt.
263
10
        auto StmtDomain = Stmt.getDomain();
264
10
265
10
        // Get the domain of the future Read access.
266
10
        auto ReadDomainSet = MA->getAccessRelation().domain();
267
10
        auto ReadDomain = isl::union_set(ReadDomainSet);
268
10
269
10
        // Get the dependences relevant for this MA
270
10
        auto MapDependences = filterDependences(S, Dependences.reverse(), MA);
271
10
        unsigned NumberElementMap = isl_union_map_n_map(MapDependences.get());
272
10
273
10
        if (NumberElementMap == 0) {
274
0
          emitRemark("The expansion of " + SAI->getName() +
275
0
                         " would lead to a read from the original array.",
276
0
                     MA->getAccessInstruction());
277
0
          return false;
278
0
        }
279
10
280
10
        auto DepsDomain = MapDependences.domain();
281
10
282
10
        // If there are multiple maps in the Deps, we cannot handle this case
283
10
        // for now.
284
10
        if (NumberElementMap != 1) {
285
0
          emitRemark(SAI->getName() +
286
0
                         " has too many dependences to be handle for now.",
287
0
                     MA->getAccessInstruction());
288
0
          return false;
289
0
        }
290
10
291
10
        auto DepsDomainSet = isl::set(DepsDomain);
292
10
293
10
        // For now, read from the original array is not possible.
294
10
        if (!StmtDomain.is_subset(DepsDomainSet)) {
295
2
          emitRemark("The expansion of " + SAI->getName() +
296
2
                         " would lead to a read from the original array.",
297
2
                     MA->getAccessInstruction());
298
2
          return false;
299
2
        }
300
8
301
8
        Reads.insert(MA);
302
8
      }
303
42
    }
304
90
  }
305
32
306
32
  // No need to expand SAI with no write.
307
32
  
if (26
NumberWrites == 026
) {
308
0
    emitRemark(SAI->getName() + " has 0 write access.",
309
0
               S.getEnteringBlock()->getFirstNonPHI());
310
0
    return false;
311
0
  }
312
26
313
26
  return true;
314
26
}
315
316
void MaximalStaticExpander::mapAccess(Scop &S,
317
                                      SmallPtrSetImpl<MemoryAccess *> &Accesses,
318
                                      const isl::union_map &Dependences,
319
                                      ScopArrayInfo *ExpandedSAI,
320
49
                                      bool Reverse) {
321
49
  for (auto MA : Accesses) {
322
42
    // Get the current AM.
323
42
    auto CurrentAccessMap = MA->getAccessRelation();
324
42
325
42
    // Get RAW dependences for the current WA.
326
42
    auto DomainSet = MA->getAccessRelation().domain();
327
42
    auto Domain = isl::union_set(DomainSet);
328
42
329
42
    // Get the dependences relevant for this MA.
330
42
    isl::union_map MapDependences =
331
42
        filterDependences(S, Reverse ? 
Dependences.reverse()12
:
Dependences30
, MA);
332
42
333
42
    // If no dependences, no need to modify anything.
334
42
    if (MapDependences.is_empty())
335
0
      return;
336
42
337
42
    assert(isl_union_map_n_map(MapDependences.get()) == 1 &&
338
42
           "There are more than one RAW dependencies in the union map.");
339
42
    auto NewAccessMap = isl::map::from_union_map(MapDependences);
340
42
341
42
    auto Id = ExpandedSAI->getBasePtrId();
342
42
343
42
    // Replace the out tuple id with the one of the access array.
344
42
    NewAccessMap = NewAccessMap.set_tuple_id(isl::dim::out, Id);
345
42
346
42
    // Set the new access relation.
347
42
    MA->setNewAccessRelation(NewAccessMap);
348
42
  }
349
49
}
350
351
49
ScopArrayInfo *MaximalStaticExpander::expandAccess(Scop &S, MemoryAccess *MA) {
352
49
  // Get the current AM.
353
49
  auto CurrentAccessMap = MA->getAccessRelation();
354
49
355
49
  unsigned in_dimensions = CurrentAccessMap.dim(isl::dim::in);
356
49
357
49
  // Get domain from the current AM.
358
49
  auto Domain = CurrentAccessMap.domain();
359
49
360
49
  // Create a new AM from the domain.
361
49
  auto NewAccessMap = isl::map::from_domain(Domain);
362
49
363
49
  // Add dimensions to the new AM according to the current in_dim.
364
49
  NewAccessMap = NewAccessMap.add_dims(isl::dim::out, in_dimensions);
365
49
366
49
  // Create the string representing the name of the new SAI.
367
49
  // One new SAI for each statement so that each write go to a different memory
368
49
  // cell.
369
49
  auto CurrentStmtDomain = MA->getStatement()->getDomain();
370
49
  auto CurrentStmtName = CurrentStmtDomain.get_tuple_name();
371
49
  auto CurrentOutId = CurrentAccessMap.get_tuple_id(isl::dim::out);
372
49
  std::string CurrentOutIdString =
373
49
      MA->getScopArrayInfo()->getName() + "_" + CurrentStmtName + "_expanded";
374
49
375
49
  // Set the tuple id for the out dimension.
376
49
  NewAccessMap = NewAccessMap.set_tuple_id(isl::dim::out, CurrentOutId);
377
49
378
49
  // Create the size vector.
379
49
  std::vector<unsigned> Sizes;
380
129
  for (unsigned i = 0; i < in_dimensions; 
i++80
) {
381
80
    assert(isDimBoundedByConstant(CurrentStmtDomain, i) &&
382
80
           "Domain boundary are not constant.");
383
80
    auto UpperBound = getConstant(CurrentStmtDomain.dim_max(i), true, false);
384
80
    assert(!UpperBound.is_null() && UpperBound.is_pos() &&
385
80
           !UpperBound.is_nan() &&
386
80
           "The upper bound is not a positive integer.");
387
80
    assert(UpperBound.le(isl::val(CurrentAccessMap.get_ctx(),
388
80
                                  std::numeric_limits<int>::max() - 1)) &&
389
80
           "The upper bound overflow a int.");
390
80
    Sizes.push_back(UpperBound.get_num_si() + 1);
391
80
  }
392
49
393
49
  // Get the ElementType of the current SAI.
394
49
  auto ElementType = MA->getLatestScopArrayInfo()->getElementType();
395
49
396
49
  // Create (or get if already existing) the new expanded SAI.
397
49
  auto ExpandedSAI =
398
49
      S.createScopArrayInfo(ElementType, CurrentOutIdString, Sizes);
399
49
  ExpandedSAI->setIsOnHeap(true);
400
49
401
49
  // Get the out Id of the expanded Array.
402
49
  auto NewOutId = ExpandedSAI->getBasePtrId();
403
49
404
49
  // Set the out id of the new AM to the new SAI id.
405
49
  NewAccessMap = NewAccessMap.set_tuple_id(isl::dim::out, NewOutId);
406
49
407
49
  // Add constraints to linked output with input id.
408
49
  auto SpaceMap = NewAccessMap.get_space();
409
49
  auto ConstraintBasicMap =
410
49
      isl::basic_map::equal(SpaceMap, SpaceMap.dim(isl::dim::in));
411
49
  NewAccessMap = isl::map(ConstraintBasicMap);
412
49
413
49
  // Set the new access relation map.
414
49
  MA->setNewAccessRelation(NewAccessMap);
415
49
416
49
  return ExpandedSAI;
417
49
}
418
419
void MaximalStaticExpander::expandPhi(Scop &S, const ScopArrayInfo *SAI,
420
20
                                      const isl::union_map &Dependences) {
421
20
  SmallPtrSet<MemoryAccess *, 4> Writes;
422
20
  for (auto MA : S.getPHIIncomings(SAI))
423
30
    Writes.insert(MA);
424
20
  auto Read = S.getPHIRead(SAI);
425
20
  auto ExpandedSAI = expandAccess(S, Read);
426
20
427
20
  mapAccess(S, Writes, Dependences, ExpandedSAI, false);
428
20
}
429
430
14
void MaximalStaticExpander::emitRemark(StringRef Msg, Instruction *Inst) {
431
14
  ORE->emit(OptimizationRemarkAnalysis(DEBUG_TYPE, "ExpansionRejection", Inst)
432
14
            << Msg);
433
14
}
434
435
17
bool MaximalStaticExpander::runOnScop(Scop &S) {
436
17
  // Get the ORE from OptimizationRemarkEmitterWrapperPass.
437
17
  ORE = &(getAnalysis<OptimizationRemarkEmitterWrapperPass>().getORE());
438
17
439
17
  // Get the RAW Dependences.
440
17
  auto &DI = getAnalysis<DependenceInfo>();
441
17
  auto &D = DI.getDependences(Dependences::AL_Reference);
442
17
  isl::union_map Dependences = D.getDependences(Dependences::TYPE_RAW);
443
17
444
17
  SmallVector<ScopArrayInfo *, 4> CurrentSAI(S.arrays().begin(),
445
17
                                             S.arrays().end());
446
17
447
63
  for (auto SAI : CurrentSAI) {
448
63
    SmallPtrSet<MemoryAccess *, 4> AllWrites;
449
63
    SmallPtrSet<MemoryAccess *, 4> AllReads;
450
63
    if (!isExpandable(SAI, AllWrites, AllReads, S, Dependences))
451
14
      continue;
452
49
453
49
    if (SAI->isValueKind() || 
SAI->isArrayKind()46
) {
454
29
      assert(AllWrites.size() == 1 || SAI->isValueKind());
455
29
456
29
      auto TheWrite = *(AllWrites.begin());
457
29
      ScopArrayInfo *ExpandedArray = expandAccess(S, TheWrite);
458
29
459
29
      mapAccess(S, AllReads, Dependences, ExpandedArray, true);
460
29
    } else 
if (20
SAI->isPHIKind()20
) {
461
20
      expandPhi(S, SAI, Dependences);
462
20
    }
463
49
  }
464
17
465
17
  return false;
466
17
}
467
468
17
void MaximalStaticExpander::printScop(raw_ostream &OS, Scop &S) const {
469
17
  S.print(OS, false);
470
17
}
471
472
17
void MaximalStaticExpander::getAnalysisUsage(AnalysisUsage &AU) const {
473
17
  ScopPass::getAnalysisUsage(AU);
474
17
  AU.addRequired<DependenceInfo>();
475
17
  AU.addRequired<OptimizationRemarkEmitterWrapperPass>();
476
17
}
477
478
0
Pass *polly::createMaximalStaticExpansionPass() {
479
0
  return new MaximalStaticExpander();
480
0
}
481
482
44.3k
INITIALIZE_PASS_BEGIN(MaximalStaticExpander, "polly-mse",
483
44.3k
                      "Polly - Maximal static expansion of SCoP", false, false);
484
44.3k
INITIALIZE_PASS_DEPENDENCY(DependenceInfo);
485
44.3k
INITIALIZE_PASS_DEPENDENCY(OptimizationRemarkEmitterWrapperPass);
486
44.3k
INITIALIZE_PASS_END(MaximalStaticExpander, "polly-mse",
487
                    "Polly - Maximal static expansion of SCoP", false, false)