Coverage Report

Created: 2018-04-23 18:20

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