Coverage Report

Created: 2017-08-21 19:50

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