Coverage Report

Created: 2017-11-21 16:49

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