Coverage Report

Created: 2018-06-24 14:39

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/tools/polly/lib/Transform/ForwardOpTree.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- ForwardOpTree.h ------------------------------------------*- C++ -*-===//
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
// Move instructions between statements.
11
//
12
//===----------------------------------------------------------------------===//
13
14
#include "polly/ForwardOpTree.h"
15
#include "polly/Options.h"
16
#include "polly/ScopBuilder.h"
17
#include "polly/ScopInfo.h"
18
#include "polly/ScopPass.h"
19
#include "polly/Support/GICHelper.h"
20
#include "polly/Support/ISLOStream.h"
21
#include "polly/Support/ISLTools.h"
22
#include "polly/Support/VirtualInstruction.h"
23
#include "polly/ZoneAlgo.h"
24
#include "llvm/ADT/STLExtras.h"
25
#include "llvm/ADT/SmallVector.h"
26
#include "llvm/ADT/Statistic.h"
27
#include "llvm/Analysis/LoopInfo.h"
28
#include "llvm/Analysis/ValueTracking.h"
29
#include "llvm/IR/Instruction.h"
30
#include "llvm/IR/Instructions.h"
31
#include "llvm/IR/Value.h"
32
#include "llvm/Pass.h"
33
#include "llvm/Support/Casting.h"
34
#include "llvm/Support/CommandLine.h"
35
#include "llvm/Support/Compiler.h"
36
#include "llvm/Support/Debug.h"
37
#include "llvm/Support/ErrorHandling.h"
38
#include "llvm/Support/raw_ostream.h"
39
#include "isl/ctx.h"
40
#include "isl/isl-noexceptions.h"
41
#include <cassert>
42
#include <memory>
43
44
#define DEBUG_TYPE "polly-optree"
45
46
using namespace llvm;
47
using namespace polly;
48
49
static cl::opt<bool>
50
    AnalyzeKnown("polly-optree-analyze-known",
51
                 cl::desc("Analyze array contents for load forwarding"),
52
                 cl::cat(PollyCategory), cl::init(true), cl::Hidden);
53
54
static cl::opt<bool>
55
    NormalizePHIs("polly-optree-normalize-phi",
56
                  cl::desc("Replace PHIs by their incoming values"),
57
                  cl::cat(PollyCategory), cl::init(false), cl::Hidden);
58
59
static cl::opt<unsigned>
60
    MaxOps("polly-optree-max-ops",
61
           cl::desc("Maximum number of ISL operations to invest for known "
62
                    "analysis; 0=no limit"),
63
           cl::init(1000000), cl::cat(PollyCategory), cl::Hidden);
64
65
STATISTIC(KnownAnalyzed, "Number of successfully analyzed SCoPs");
66
STATISTIC(KnownOutOfQuota,
67
          "Analyses aborted because max_operations was reached");
68
69
STATISTIC(TotalInstructionsCopied, "Number of copied instructions");
70
STATISTIC(TotalKnownLoadsForwarded,
71
          "Number of forwarded loads because their value was known");
72
STATISTIC(TotalReloads, "Number of reloaded values");
73
STATISTIC(TotalReadOnlyCopied, "Number of copied read-only accesses");
74
STATISTIC(TotalForwardedTrees, "Number of forwarded operand trees");
75
STATISTIC(TotalModifiedStmts,
76
          "Number of statements with at least one forwarded tree");
77
78
STATISTIC(ScopsModified, "Number of SCoPs with at least one forwarded tree");
79
80
STATISTIC(NumValueWrites, "Number of scalar value writes after OpTree");
81
STATISTIC(NumValueWritesInLoops,
82
          "Number of scalar value writes nested in affine loops after OpTree");
83
STATISTIC(NumPHIWrites, "Number of scalar phi writes after OpTree");
84
STATISTIC(NumPHIWritesInLoops,
85
          "Number of scalar phi writes nested in affine loops after OpTree");
86
STATISTIC(NumSingletonWrites, "Number of singleton writes after OpTree");
87
STATISTIC(NumSingletonWritesInLoops,
88
          "Number of singleton writes nested in affine loops after OpTree");
89
90
namespace {
91
92
/// The state of whether an operand tree was/can be forwarded.
93
///
94
/// The items apply to an instructions and its operand tree with the instruction
95
/// as the root element. If the value in question is not an instruction in the
96
/// SCoP, it can be a leaf of an instruction's operand tree.
97
enum ForwardingDecision {
98
  /// The root instruction or value cannot be forwarded at all.
99
  FD_CannotForward,
100
101
  /// The root instruction or value can be forwarded as a leaf of a larger
102
  /// operand tree.
103
  /// It does not make sense to move the value itself, it would just replace it
104
  /// by a use of itself. For instance, a constant "5" used in a statement can
105
  /// be forwarded, but it would just replace it by the same constant "5".
106
  /// However, it makes sense to move as an operand of
107
  ///
108
  ///   %add = add 5, 5
109
  ///
110
  /// where "5" is moved as part of a larger operand tree. "5" would be placed
111
  /// (disregarding for a moment that literal constants don't have a location
112
  /// and can be used anywhere) into the same statement as %add would.
113
  FD_CanForwardLeaf,
114
115
  /// The root instruction can be forwarded and doing so avoids a scalar
116
  /// dependency.
117
  ///
118
  /// This can be either because the operand tree can be moved to the target
119
  /// statement, or a memory access is redirected to read from a different
120
  /// location.
121
  FD_CanForwardProfitably,
122
123
  /// Used to indicate that a forwarding has be carried out successfully, and
124
  /// the forwarded memory access can be deleted.
125
  FD_DidForwardTree,
126
127
  /// Used to indicate that a forwarding has be carried out successfully, and
128
  /// the forwarded memory access is being reused.
129
  FD_DidForwardLeaf,
130
131
  /// A forwarding method cannot be applied to the operand tree.
132
  /// The difference to FD_CannotForward is that there might be other methods
133
  /// that can handle it.
134
  /// The conditions that make an operand tree applicable must be checked even
135
  /// with DoIt==true because a method following the one that returned
136
  /// FD_NotApplicable might have returned FD_CanForwardTree.
137
  FD_NotApplicable
138
};
139
140
/// Implementation of operand tree forwarding for a specific SCoP.
141
///
142
/// For a statement that requires a scalar value (through a value read
143
/// MemoryAccess), see if its operand can be moved into the statement. If so,
144
/// the MemoryAccess is removed and the all the operand tree instructions are
145
/// moved into the statement. All original instructions are left in the source
146
/// statements. The simplification pass can clean these up.
147
class ForwardOpTreeImpl : ZoneAlgorithm {
148
private:
149
  /// Scope guard to limit the number of isl operations for this pass.
150
  IslMaxOperationsGuard &MaxOpGuard;
151
152
  /// How many instructions have been copied to other statements.
153
  int NumInstructionsCopied = 0;
154
155
  /// Number of loads forwarded because their value was known.
156
  int NumKnownLoadsForwarded = 0;
157
158
  /// Number of values reloaded from known array elements.
159
  int NumReloads = 0;
160
161
  /// How many read-only accesses have been copied.
162
  int NumReadOnlyCopied = 0;
163
164
  /// How many operand trees have been forwarded.
165
  int NumForwardedTrees = 0;
166
167
  /// Number of statements with at least one forwarded operand tree.
168
  int NumModifiedStmts = 0;
169
170
  /// Whether we carried out at least one change to the SCoP.
171
  bool Modified = false;
172
173
  /// Contains the zones where array elements are known to contain a specific
174
  /// value.
175
  /// { [Element[] -> Zone[]] -> ValInst[] }
176
  /// @see computeKnown()
177
  isl::union_map Known;
178
179
  /// Translator for newly introduced ValInsts to already existing ValInsts such
180
  /// that new introduced load instructions can reuse the Known analysis of its
181
  /// original load. { ValInst[] -> ValInst[] }
182
  isl::union_map Translator;
183
184
  /// A cache for getDefToTarget().
185
  DenseMap<std::pair<ScopStmt *, ScopStmt *>, isl::map> DefToTargetCache;
186
187
  /// Get list of array elements that do contain the same ValInst[] at Domain[].
188
  ///
189
  /// @param ValInst { Domain[] -> ValInst[] }
190
  ///                The values for which we search for alternative locations,
191
  ///                per statement instance.
192
  ///
193
  /// @return { Domain[] -> Element[] }
194
  ///         For each statement instance, the array elements that contain the
195
  ///         same ValInst.
196
65
  isl::union_map findSameContentElements(isl::union_map ValInst) {
197
65
    assert(!ValInst.is_single_valued().is_false());
198
65
199
65
    // { Domain[] }
200
65
    isl::union_set Domain = ValInst.domain();
201
65
202
65
    // { Domain[] -> Scatter[] }
203
65
    isl::union_map Schedule = getScatterFor(Domain);
204
65
205
65
    // { Element[] -> [Scatter[] -> ValInst[]] }
206
65
    isl::union_map MustKnownCurried =
207
65
        convertZoneToTimepoints(Known, isl::dim::in, false, true).curry();
208
65
209
65
    // { [Domain[] -> ValInst[]] -> Scatter[] }
210
65
    isl::union_map DomValSched = ValInst.domain_map().apply_range(Schedule);
211
65
212
65
    // { [Scatter[] -> ValInst[]] -> [Domain[] -> ValInst[]] }
213
65
    isl::union_map SchedValDomVal =
214
65
        DomValSched.range_product(ValInst.range_map()).reverse();
215
65
216
65
    // { Element[] -> [Domain[] -> ValInst[]] }
217
65
    isl::union_map MustKnownInst = MustKnownCurried.apply_range(SchedValDomVal);
218
65
219
65
    // { Domain[] -> Element[] }
220
65
    isl::union_map MustKnownMap =
221
65
        MustKnownInst.uncurry().domain().unwrap().reverse();
222
65
    simplify(MustKnownMap);
223
65
224
65
    return MustKnownMap;
225
65
  }
226
227
  /// Find a single array element for each statement instance, within a single
228
  /// array.
229
  ///
230
  /// @param MustKnown { Domain[] -> Element[] }
231
  ///                  Set of candidate array elements.
232
  /// @param Domain    { Domain[] }
233
  ///                  The statement instance for which we need elements for.
234
  ///
235
  /// @return { Domain[] -> Element[] }
236
  ///         For each statement instance, an array element out of @p MustKnown.
237
  ///         All array elements must be in the same array (Polly does not yet
238
  ///         support reading from different accesses using the same
239
  ///         MemoryAccess). If no mapping for all of @p Domain exists, returns
240
  ///         null.
241
65
  isl::map singleLocation(isl::union_map MustKnown, isl::set Domain) {
242
65
    // { Domain[] -> Element[] }
243
65
    isl::map Result;
244
65
245
65
    // MemoryAccesses can read only elements from a single array
246
65
    // (i.e. not: { Dom[0] -> A[0]; Dom[1] -> B[1] }).
247
65
    // Look through all spaces until we find one that contains at least the
248
65
    // wanted statement instance.s
249
65
    MustKnown.foreach_map([&](isl::map Map) -> isl::stat {
250
54
      // Get the array this is accessing.
251
54
      isl::id ArrayId = Map.get_tuple_id(isl::dim::out);
252
54
      ScopArrayInfo *SAI = static_cast<ScopArrayInfo *>(ArrayId.get_user());
253
54
254
54
      // No support for generation of indirect array accesses.
255
54
      if (SAI->getBasePtrOriginSAI())
256
0
        return isl::stat::ok; // continue
257
54
258
54
      // Determine whether this map contains all wanted values.
259
54
      isl::set MapDom = Map.domain();
260
54
      if (!Domain.is_subset(MapDom).is_true())
261
2
        return isl::stat::ok; // continue
262
52
263
52
      // There might be multiple array elements that contain the same value, but
264
52
      // choose only one of them. lexmin is used because it returns a one-value
265
52
      // mapping, we do not care about which one.
266
52
      // TODO: Get the simplest access function.
267
52
      Result = Map.lexmin();
268
52
      return isl::stat::error; // break
269
52
    });
270
65
271
65
    return Result;
272
65
  }
273
274
public:
275
  ForwardOpTreeImpl(Scop *S, LoopInfo *LI, IslMaxOperationsGuard &MaxOpGuard)
276
34
      : ZoneAlgorithm("polly-optree", S, LI), MaxOpGuard(MaxOpGuard) {}
277
278
  /// Compute the zones of known array element contents.
279
  ///
280
  /// @return True if the computed #Known is usable.
281
34
  bool computeKnownValues() {
282
34
    isl::union_map MustKnown, KnownFromLoad, KnownFromInit;
283
34
284
34
    // Check that nothing strange occurs.
285
34
    collectCompatibleElts();
286
34
287
34
    {
288
34
      IslQuotaScope QuotaScope = MaxOpGuard.enter();
289
34
290
34
      computeCommon();
291
34
      if (NormalizePHIs)
292
4
        computeNormalizedPHIs();
293
34
      Known = computeKnown(true, true);
294
34
295
34
      // Preexisting ValInsts use the known content analysis of themselves.
296
34
      Translator = makeIdentityMap(Known.range(), false);
297
34
    }
298
34
299
34
    if (!Known || !Translator || !NormalizeMap) {
300
0
      assert(isl_ctx_last_error(IslCtx.get()) == isl_error_quota);
301
0
      Known = nullptr;
302
0
      Translator = nullptr;
303
0
      NormalizeMap = nullptr;
304
0
      LLVM_DEBUG(dbgs() << "Known analysis exceeded max_operations\n");
305
0
      return false;
306
0
    }
307
34
308
34
    KnownAnalyzed++;
309
34
    LLVM_DEBUG(dbgs() << "All known: " << Known << "\n");
310
34
311
34
    return true;
312
34
  }
313
314
33
  void printStatistics(raw_ostream &OS, int Indent = 0) {
315
33
    OS.indent(Indent) << "Statistics {\n";
316
33
    OS.indent(Indent + 4) << "Instructions copied: " << NumInstructionsCopied
317
33
                          << '\n';
318
33
    OS.indent(Indent + 4) << "Known loads forwarded: " << NumKnownLoadsForwarded
319
33
                          << '\n';
320
33
    OS.indent(Indent + 4) << "Reloads: " << NumReloads << '\n';
321
33
    OS.indent(Indent + 4) << "Read-only accesses copied: " << NumReadOnlyCopied
322
33
                          << '\n';
323
33
    OS.indent(Indent + 4) << "Operand trees forwarded: " << NumForwardedTrees
324
33
                          << '\n';
325
33
    OS.indent(Indent + 4) << "Statements with forwarded operand trees: "
326
33
                          << NumModifiedStmts << '\n';
327
33
    OS.indent(Indent) << "}\n";
328
33
  }
329
330
25
  void printStatements(raw_ostream &OS, int Indent = 0) const {
331
25
    OS.indent(Indent) << "After statements {\n";
332
62
    for (auto &Stmt : *S) {
333
62
      OS.indent(Indent + 4) << Stmt.getBaseName() << "\n";
334
62
      for (auto *MA : Stmt)
335
120
        MA->print(OS);
336
62
337
62
      OS.indent(Indent + 12);
338
62
      Stmt.printInstructions(OS);
339
62
    }
340
25
    OS.indent(Indent) << "}\n";
341
25
  }
342
343
  /// Create a new MemoryAccess of type read and MemoryKind::Array.
344
  ///
345
  /// @param Stmt           The statement in which the access occurs.
346
  /// @param LI             The instruction that does the access.
347
  /// @param AccessRelation The array element that each statement instance
348
  ///                       accesses.
349
  ///
350
  /// @param The newly created access.
351
  MemoryAccess *makeReadArrayAccess(ScopStmt *Stmt, LoadInst *LI,
352
16
                                    isl::map AccessRelation) {
353
16
    isl::id ArrayId = AccessRelation.get_tuple_id(isl::dim::out);
354
16
    ScopArrayInfo *SAI = reinterpret_cast<ScopArrayInfo *>(ArrayId.get_user());
355
16
356
16
    // Create a dummy SCEV access, to be replaced anyway.
357
16
    SmallVector<const SCEV *, 4> Sizes;
358
16
    Sizes.reserve(SAI->getNumberOfDimensions());
359
16
    SmallVector<const SCEV *, 4> Subscripts;
360
16
    Subscripts.reserve(SAI->getNumberOfDimensions());
361
32
    for (unsigned i = 0; i < SAI->getNumberOfDimensions(); 
i += 116
) {
362
16
      Sizes.push_back(SAI->getDimensionSize(i));
363
16
      Subscripts.push_back(nullptr);
364
16
    }
365
16
366
16
    MemoryAccess *Access =
367
16
        new MemoryAccess(Stmt, LI, MemoryAccess::READ, SAI->getBasePtr(),
368
16
                         LI->getType(), true, {}, Sizes, LI, MemoryKind::Array);
369
16
    S->addAccessFunction(Access);
370
16
    Stmt->addAccess(Access, true);
371
16
372
16
    Access->setNewAccessRelation(AccessRelation);
373
16
374
16
    return Access;
375
16
  }
376
377
  /// For an llvm::Value defined in @p DefStmt, compute the RAW dependency for a
378
  /// use in every instance of @p UseStmt.
379
  ///
380
  /// @param UseStmt Statement a scalar is used in.
381
  /// @param DefStmt Statement a scalar is defined in.
382
  ///
383
  /// @return { DomainUse[] -> DomainDef[] }
384
2
  isl::map computeUseToDefFlowDependency(ScopStmt *UseStmt, ScopStmt *DefStmt) {
385
2
    // { DomainUse[] -> Scatter[] }
386
2
    isl::map UseScatter = getScatterFor(UseStmt);
387
2
388
2
    // { Zone[] -> DomainDef[] }
389
2
    isl::map ReachDefZone = getScalarReachingDefinition(DefStmt);
390
2
391
2
    // { Scatter[] -> DomainDef[] }
392
2
    isl::map ReachDefTimepoints =
393
2
        convertZoneToTimepoints(ReachDefZone, isl::dim::in, false, true);
394
2
395
2
    // { DomainUse[] -> DomainDef[] }
396
2
    return UseScatter.apply_range(ReachDefTimepoints);
397
2
  }
398
399
  /// Is @p InnerLoop nested inside @p OuterLoop?
400
28
  static bool isInsideLoop(Loop *OuterLoop, Loop *InnerLoop) {
401
28
    // If OuterLoop is nullptr, we cannot call its contains() method. In this
402
28
    // case OuterLoop represents the 'top level' and therefore contains all
403
28
    // loop.
404
28
    return !OuterLoop || 
OuterLoop->contains(InnerLoop)25
;
405
28
  }
406
407
  /// Get a domain translation map from a (scalar) definition to the statement
408
  /// where the definition is being moved to.
409
  ///
410
  /// @p TargetStmt can also be seen an llvm::Use of an llvm::Value in
411
  /// @p DefStmt. In addition, we allow transitive uses:
412
  ///
413
  /// DefStmt -> MiddleStmt -> TargetStmt
414
  ///
415
  /// where an operand tree of instructions in DefStmt and MiddleStmt are to be
416
  /// moved to TargetStmt. To be generally correct, we also need to know all the
417
  /// intermediate statements. However, we make use of the fact that we
418
  /// currently do not support a move from a loop body across its header such
419
  /// that only the first definition and the target statement are relevant.
420
  ///
421
  /// @param DefStmt    Statement from where a definition might be moved from.
422
  /// @param TargetStmt Statement where the definition is potentially being
423
  ///                   moved to (should contain a use of that definition).
424
  ///
425
  /// @return  { DomainDef[] -> DomainTarget[] }
426
81
  isl::map getDefToTarget(ScopStmt *DefStmt, ScopStmt *TargetStmt) {
427
81
    // No translation required if the definition is already at the target.
428
81
    if (TargetStmt == DefStmt)
429
53
      return isl::map::identity(
430
53
          getDomainFor(TargetStmt).get_space().map_from_set());
431
28
432
28
    isl::map &Result = DefToTargetCache[std::make_pair(TargetStmt, DefStmt)];
433
28
434
28
    // This is a shortcut in case the schedule is still the original and
435
28
    // TargetStmt is in the same or nested inside DefStmt's loop. With the
436
28
    // additional assumption that operand trees do not cross DefStmt's loop
437
28
    // header, then TargetStmt's instance shared coordinated are the same as
438
28
    // DefStmt's coordinated. All TargetStmt instances with this prefix share
439
28
    // the same DefStmt instance.
440
28
    // Model:
441
28
    //
442
28
    //   for (int i < 0; i < N; i+=1) {
443
28
    // DefStmt:
444
28
    //    D = ...;
445
28
    //    for (int j < 0; j < N; j+=1) {
446
28
    // TargetStmt:
447
28
    //      use(D);
448
28
    //    }
449
28
    //  }
450
28
    //
451
28
    // Here, the value used in TargetStmt is defined in the corresponding
452
28
    // DefStmt, i.e.
453
28
    //
454
28
    //   { DefStmt[i] -> TargetStmt[i,j] }
455
28
    //
456
28
    // In practice, this should cover the majority of cases.
457
28
    if (S->isOriginalSchedule() &&
458
28
        isInsideLoop(DefStmt->getSurroundingLoop(),
459
28
                     TargetStmt->getSurroundingLoop())) {
460
26
      isl::set DefDomain = getDomainFor(DefStmt);
461
26
      isl::set TargetDomain = getDomainFor(TargetStmt);
462
26
      assert(DefDomain.dim(isl::dim::set) <= TargetDomain.dim(isl::dim::set));
463
26
464
26
      Result = isl::map::from_domain_and_range(DefDomain, TargetDomain);
465
45
      for (unsigned i = 0, DefDims = DefDomain.dim(isl::dim::set); i < DefDims;
466
26
           
i += 119
)
467
19
        Result = Result.equate(isl::dim::in, i, isl::dim::out, i);
468
26
    }
469
28
470
28
    if (!Result) {
471
2
      // { DomainDef[] -> DomainTarget[] }
472
2
      Result = computeUseToDefFlowDependency(TargetStmt, DefStmt).reverse();
473
2
      simplify(Result);
474
2
    }
475
28
476
28
    return Result;
477
28
  }
478
479
  /// Forward a load by reading from an array element that contains the same
480
  /// value. Typically the location it was loaded from.
481
  ///
482
  /// @param TargetStmt  The statement the operand tree will be copied to.
483
  /// @param Inst        The (possibly speculatable) instruction to forward.
484
  /// @param UseStmt     The statement that uses @p Inst.
485
  /// @param UseLoop     The loop @p Inst is used in.
486
  /// @param DefStmt     The statement @p Inst is defined in.
487
  /// @param DefLoop     The loop which contains @p Inst.
488
  /// @param DoIt        If false, only determine whether an operand tree can be
489
  ///                    forwarded. If true, carry out the forwarding. Do not
490
  ///                    use DoIt==true if an operand tree is not known to be
491
  ///                    forwardable.
492
  ///
493
  /// @return FD_NotApplicable  if @p Inst cannot be forwarded by creating a new
494
  ///                           load.
495
  ///         FD_CannotForward  if the pointer operand cannot be forwarded.
496
  ///         FD_CanForwardProfitably if @p Inst is forwardable.
497
  ///         FD_DidForwardTree if @p DoIt was true.
498
  ForwardingDecision forwardKnownLoad(ScopStmt *TargetStmt, Instruction *Inst,
499
                                      ScopStmt *UseStmt, Loop *UseLoop,
500
                                      ScopStmt *DefStmt, Loop *DefLoop,
501
66
                                      bool DoIt) {
502
66
    // Cannot do anything without successful known analysis.
503
66
    if (Known.is_null() || Translator.is_null() ||
504
66
        MaxOpGuard.hasQuotaExceeded())
505
0
      return FD_NotApplicable;
506
66
507
66
    LoadInst *LI = dyn_cast<LoadInst>(Inst);
508
66
    if (!LI)
509
21
      return FD_NotApplicable;
510
45
511
45
    // If the load is already in the statement, no forwarding is necessary.
512
45
    // However, it might happen that the LoadInst is already present in the
513
45
    // statement's instruction list. In that case we do as follows:
514
45
    // - For the evaluation (DoIt==false), we can trivially forward it as it is
515
45
    //   benefit of forwarding an already present instruction.
516
45
    // - For the execution (DoIt==true), prepend the instruction (to make it
517
45
    //   available to all instructions following in the instruction list), but
518
45
    //   do not add another MemoryAccess.
519
45
    MemoryAccess *Access = TargetStmt->getArrayAccessOrNULLFor(LI);
520
45
    if (Access && 
!DoIt9
)
521
4
      return FD_CanForwardProfitably;
522
41
523
41
    ForwardingDecision OpDecision = forwardTree(
524
41
        TargetStmt, LI->getPointerOperand(), DefStmt, DefLoop, DoIt);
525
41
    switch (OpDecision) {
526
41
    case FD_CannotForward:
527
0
      assert(!DoIt);
528
0
      return OpDecision;
529
41
530
41
    case FD_CanForwardLeaf:
531
20
    case FD_CanForwardProfitably:
532
20
      assert(!DoIt);
533
20
      break;
534
20
535
21
    case FD_DidForwardLeaf:
536
21
    case FD_DidForwardTree:
537
21
      assert(DoIt);
538
21
      break;
539
21
540
21
    default:
541
0
      llvm_unreachable("Shouldn't return this");
542
41
    }
543
41
544
41
    IslQuotaScope QuotaScope = MaxOpGuard.enter(!DoIt);
545
41
546
41
    // { DomainDef[] -> ValInst[] }
547
41
    isl::map ExpectedVal = makeValInst(Inst, UseStmt, UseLoop);
548
41
    assert(!isNormalized(ExpectedVal).is_false() &&
549
41
           "LoadInsts are always normalized");
550
41
551
41
    // { DomainUse[] -> DomainTarget[] }
552
41
    isl::map UseToTarget = getDefToTarget(UseStmt, TargetStmt);
553
41
554
41
    // { DomainTarget[] -> ValInst[] }
555
41
    isl::map TargetExpectedVal = ExpectedVal.apply_domain(UseToTarget);
556
41
    isl::union_map TranslatedExpectedVal =
557
41
        isl::union_map(TargetExpectedVal).apply_range(Translator);
558
41
559
41
    // { DomainTarget[] -> Element[] }
560
41
    isl::union_map Candidates = findSameContentElements(TranslatedExpectedVal);
561
41
562
41
    isl::map SameVal = singleLocation(Candidates, getDomainFor(TargetStmt));
563
41
    if (!SameVal)
564
3
      return FD_NotApplicable;
565
38
566
38
    if (DoIt)
567
21
      TargetStmt->prependInstruction(LI);
568
38
569
38
    if (!DoIt)
570
17
      return FD_CanForwardProfitably;
571
21
572
21
    if (Access) {
573
5
      LLVM_DEBUG(
574
5
          dbgs() << "    forwarded known load with preexisting MemoryAccess"
575
5
                 << Access << "\n");
576
16
    } else {
577
16
      Access = makeReadArrayAccess(TargetStmt, LI, SameVal);
578
16
      LLVM_DEBUG(dbgs() << "    forwarded known load with new MemoryAccess"
579
16
                        << Access << "\n");
580
16
581
16
      // { ValInst[] }
582
16
      isl::space ValInstSpace = ExpectedVal.get_space().range();
583
16
584
16
      // After adding a new load to the SCoP, also update the Known content
585
16
      // about it. The new load will have a known ValInst of
586
16
      // { [DomainTarget[] -> Value[]] }
587
16
      // but which -- because it is a copy of it -- has same value as the
588
16
      // { [DomainDef[] -> Value[]] }
589
16
      // that it replicates. Instead of  cloning the known content of
590
16
      // [DomainDef[] -> Value[]]
591
16
      // for DomainTarget[], we add a 'translator' that maps
592
16
      // [DomainTarget[] -> Value[]] to [DomainDef[] -> Value[]]
593
16
      // before comparing to the known content.
594
16
      // TODO: 'Translator' could also be used to map PHINodes to their incoming
595
16
      // ValInsts.
596
16
      if (ValInstSpace.is_wrapping()) {
597
16
        // { DefDomain[] -> Value[] }
598
16
        isl::map ValInsts = ExpectedVal.range().unwrap();
599
16
600
16
        // { DefDomain[] }
601
16
        isl::set DefDomain = ValInsts.domain();
602
16
603
16
        // { Value[] }
604
16
        isl::space ValSpace = ValInstSpace.unwrap().range();
605
16
606
16
        // { Value[] -> Value[] }
607
16
        isl::map ValToVal =
608
16
            isl::map::identity(ValSpace.map_from_domain_and_range(ValSpace));
609
16
610
16
        // { DomainDef[] -> DomainTarget[] }
611
16
        isl::map DefToTarget = getDefToTarget(DefStmt, TargetStmt);
612
16
613
16
        // { [TargetDomain[] -> Value[]] -> [DefDomain[] -> Value] }
614
16
        isl::map LocalTranslator = DefToTarget.reverse().product(ValToVal);
615
16
616
16
        Translator = Translator.add_map(LocalTranslator);
617
16
        LLVM_DEBUG(dbgs() << "      local translator is " << LocalTranslator
618
16
                          << "\n");
619
16
      }
620
16
    }
621
21
    LLVM_DEBUG(dbgs() << "      expected values where " << TargetExpectedVal
622
21
                      << "\n");
623
21
    LLVM_DEBUG(dbgs() << "      candidate elements where " << Candidates
624
21
                      << "\n");
625
21
    assert(Access);
626
21
627
21
    NumKnownLoadsForwarded++;
628
21
    TotalKnownLoadsForwarded++;
629
21
    return FD_DidForwardTree;
630
21
  }
631
632
  /// Forward a scalar by redirecting the access to an array element that stores
633
  /// the same value.
634
  ///
635
  /// @param TargetStmt  The statement the operand tree will be copied to.
636
  /// @param Inst        The scalar to forward.
637
  /// @param UseStmt     The statement that uses @p Inst.
638
  /// @param UseLoop     The loop @p Inst is used in.
639
  /// @param DefStmt     The statement @p Inst is defined in.
640
  /// @param DefLoop     The loop which contains @p Inst.
641
  /// @param DoIt        If false, only determine whether an operand tree can be
642
  ///                    forwarded. If true, carry out the forwarding. Do not
643
  ///                    use DoIt==true if an operand tree is not known to be
644
  ///                    forwardable.
645
  ///
646
  /// @return FD_NotApplicable        if @p Inst cannot be reloaded.
647
  ///         FD_CanForwardLeaf       if @p Inst can be reloaded.
648
  ///         FD_CanForwardProfitably if @p Inst has been reloaded.
649
  ///         FD_DidForwardLeaf       if @p DoIt was true.
650
  ForwardingDecision reloadKnownContent(ScopStmt *TargetStmt, Instruction *Inst,
651
                                        ScopStmt *UseStmt, Loop *UseLoop,
652
                                        ScopStmt *DefStmt, Loop *DefLoop,
653
24
                                        bool DoIt) {
654
24
    // Cannot do anything without successful known analysis.
655
24
    if (Known.is_null() || Translator.is_null() ||
656
24
        MaxOpGuard.hasQuotaExceeded())
657
0
      return FD_NotApplicable;
658
24
659
24
    MemoryAccess *Access = TargetStmt->lookupInputAccessOf(Inst);
660
24
    if (Access && 
Access->isLatestArrayKind()22
) {
661
0
      if (DoIt)
662
0
        return FD_DidForwardLeaf;
663
0
      return FD_CanForwardLeaf;
664
0
    }
665
24
666
24
    // Don't spend too much time analyzing whether it can be reloaded. When
667
24
    // carrying-out the forwarding, we cannot bail-out in the middle of the
668
24
    // transformation. It also shouldn't take as long because some results are
669
24
    // cached.
670
24
    IslQuotaScope QuotaScope = MaxOpGuard.enter(!DoIt);
671
24
672
24
    // { DomainDef[] -> ValInst[] }
673
24
    isl::union_map ExpectedVal = makeNormalizedValInst(Inst, UseStmt, UseLoop);
674
24
675
24
    // { DomainUse[] -> DomainTarget[] }
676
24
    isl::map UseToTarget = getDefToTarget(UseStmt, TargetStmt);
677
24
678
24
    // { DomainTarget[] -> ValInst[] }
679
24
    isl::union_map TargetExpectedVal = ExpectedVal.apply_domain(UseToTarget);
680
24
    isl::union_map TranslatedExpectedVal =
681
24
        TargetExpectedVal.apply_range(Translator);
682
24
683
24
    // { DomainTarget[] -> Element[] }
684
24
    isl::union_map Candidates = findSameContentElements(TranslatedExpectedVal);
685
24
686
24
    isl::map SameVal = singleLocation(Candidates, getDomainFor(TargetStmt));
687
24
    if (!SameVal)
688
10
      return FD_NotApplicable;
689
14
690
14
    if (!DoIt)
691
7
      return FD_CanForwardProfitably;
692
7
693
7
    if (!Access)
694
0
      Access = TargetStmt->ensureValueRead(Inst);
695
7
696
7
    simplify(SameVal);
697
7
    Access->setNewAccessRelation(SameVal);
698
7
699
7
    TotalReloads++;
700
7
    NumReloads++;
701
7
    return FD_DidForwardLeaf;
702
7
  }
703
704
  /// Forwards a speculatively executable instruction.
705
  ///
706
  /// @param TargetStmt  The statement the operand tree will be copied to.
707
  /// @param UseInst     The (possibly speculatable) instruction to forward.
708
  /// @param DefStmt     The statement @p UseInst is defined in.
709
  /// @param DefLoop     The loop which contains @p UseInst.
710
  /// @param DoIt        If false, only determine whether an operand tree can be
711
  ///                    forwarded. If true, carry out the forwarding. Do not
712
  ///                    use DoIt==true if an operand tree is not known to be
713
  ///                    forwardable.
714
  ///
715
  /// @return FD_NotApplicable  if @p UseInst is not speculatable.
716
  ///         FD_CannotForward  if one of @p UseInst's operands is not
717
  ///                           forwardable.
718
  ///         FD_CanForwardTree if @p UseInst is forwardable.
719
  ///         FD_DidForward     if @p DoIt was true.
720
  ForwardingDecision forwardSpeculatable(ScopStmt *TargetStmt,
721
                                         Instruction *UseInst,
722
                                         ScopStmt *DefStmt, Loop *DefLoop,
723
100
                                         bool DoIt) {
724
100
    // PHIs, unless synthesizable, are not yet supported.
725
100
    if (isa<PHINode>(UseInst))
726
17
      return FD_NotApplicable;
727
83
728
83
    // Compatible instructions must satisfy the following conditions:
729
83
    // 1. Idempotent (instruction will be copied, not moved; although its
730
83
    //    original instance might be removed by simplification)
731
83
    // 2. Not access memory (There might be memory writes between)
732
83
    // 3. Not cause undefined behaviour (we might copy to a location when the
733
83
    //    original instruction was no executed; this is currently not possible
734
83
    //    because we do not forward PHINodes)
735
83
    // 4. Not leak memory if executed multiple times (i.e. malloc)
736
83
    //
737
83
    // Instruction::mayHaveSideEffects is not sufficient because it considers
738
83
    // malloc to not have side-effects. llvm::isSafeToSpeculativelyExecute is
739
83
    // not sufficient because it allows memory accesses.
740
83
    if (mayBeMemoryDependent(*UseInst))
741
49
      return FD_NotApplicable;
742
34
743
34
    if (DoIt) {
744
16
      // To ensure the right order, prepend this instruction before its
745
16
      // operands. This ensures that its operands are inserted before the
746
16
      // instruction using them.
747
16
      // TODO: The operand tree is not really a tree, but a DAG. We should be
748
16
      // able to handle DAGs without duplication.
749
16
      TargetStmt->prependInstruction(UseInst);
750
16
      NumInstructionsCopied++;
751
16
      TotalInstructionsCopied++;
752
16
    }
753
34
754
60
    for (Value *OpVal : UseInst->operand_values()) {
755
60
      ForwardingDecision OpDecision =
756
60
          forwardTree(TargetStmt, OpVal, DefStmt, DefLoop, DoIt);
757
60
      switch (OpDecision) {
758
60
      case FD_CannotForward:
759
2
        assert(!DoIt);
760
2
        return FD_CannotForward;
761
60
762
60
      case FD_CanForwardLeaf:
763
29
      case FD_CanForwardProfitably:
764
29
        assert(!DoIt);
765
29
        break;
766
29
767
29
      case FD_DidForwardLeaf:
768
29
      case FD_DidForwardTree:
769
29
        assert(DoIt);
770
29
        break;
771
29
772
29
      case FD_NotApplicable:
773
0
        llvm_unreachable("forwardTree should never return FD_NotApplicable");
774
60
      }
775
60
    }
776
34
777
34
    
if (32
DoIt32
)
778
16
      return FD_DidForwardTree;
779
16
    return FD_CanForwardProfitably;
780
16
  }
781
782
  /// Determines whether an operand tree can be forwarded or carries out a
783
  /// forwarding, depending on the @p DoIt flag.
784
  ///
785
  /// @param TargetStmt  The statement the operand tree will be copied to.
786
  /// @param UseVal      The value (usually an instruction) which is root of an
787
  ///                    operand tree.
788
  /// @param UseStmt     The statement that uses @p UseVal.
789
  /// @param UseLoop     The loop @p UseVal is used in.
790
  /// @param DoIt        If false, only determine whether an operand tree can be
791
  ///                    forwarded. If true, carry out the forwarding. Do not
792
  ///                    use DoIt==true if an operand tree is not known to be
793
  ///                    forwardable.
794
  ///
795
  /// @return If DoIt==false, return whether the operand tree can be forwarded.
796
  ///         If DoIt==true, return FD_DidForward.
797
  ForwardingDecision forwardTree(ScopStmt *TargetStmt, Value *UseVal,
798
186
                                 ScopStmt *UseStmt, Loop *UseLoop, bool DoIt) {
799
186
    ScopStmt *DefStmt = nullptr;
800
186
    Loop *DefLoop = nullptr;
801
186
802
186
    // { DefDomain[] -> TargetDomain[] }
803
186
    isl::map DefToTarget;
804
186
805
186
    VirtualUse VUse = VirtualUse::create(UseStmt, UseLoop, UseVal, true);
806
186
    switch (VUse.getKind()) {
807
186
    case VirtualUse::Constant:
808
42
    case VirtualUse::Block:
809
42
    case VirtualUse::Hoisted:
810
42
      // These can be used anywhere without special considerations.
811
42
      if (DoIt)
812
21
        return FD_DidForwardTree;
813
21
      return FD_CanForwardLeaf;
814
21
815
39
    case VirtualUse::Synthesizable: {
816
39
      // ScopExpander will take care for of generating the code at the new
817
39
      // location.
818
39
      if (DoIt)
819
20
        return FD_DidForwardTree;
820
19
821
19
      // Check if the value is synthesizable at the new location as well. This
822
19
      // might be possible when leaving a loop for which ScalarEvolution is
823
19
      // unable to derive the exit value for.
824
19
      // TODO: If there is a LCSSA PHI at the loop exit, use that one.
825
19
      // If the SCEV contains a SCEVAddRecExpr, we currently depend on that we
826
19
      // do not forward past its loop header. This would require us to use a
827
19
      // previous loop induction variable instead the current one. We currently
828
19
      // do not allow forwarding PHI nodes, thus this should never occur (the
829
19
      // only exception where no phi is necessary being an unreachable loop
830
19
      // without edge from the outside).
831
19
      VirtualUse TargetUse = VirtualUse::create(
832
19
          S, TargetStmt, TargetStmt->getSurroundingLoop(), UseVal, true);
833
19
      if (TargetUse.getKind() == VirtualUse::Synthesizable)
834
19
        return FD_CanForwardLeaf;
835
0
836
0
      LLVM_DEBUG(
837
0
          dbgs() << "    Synthesizable would not be synthesizable anymore: "
838
0
                 << *UseVal << "\n");
839
0
      return FD_CannotForward;
840
0
    }
841
0
842
5
    case VirtualUse::ReadOnly:
843
5
      // Note that we cannot return FD_CanForwardTree here. With a operand tree
844
5
      // depth of 0, UseVal is the use in TargetStmt that we try to replace.
845
5
      // With -polly-analyze-read-only-scalars=true we would ensure the
846
5
      // existence of a MemoryAccess (which already exists for a leaf) and be
847
5
      // removed again by tryForwardTree because it's goal is to remove this
848
5
      // scalar MemoryAccess. It interprets FD_CanForwardTree as the permission
849
5
      // to do so.
850
5
      if (!DoIt)
851
3
        return FD_CanForwardLeaf;
852
2
853
2
      // If we model read-only scalars, we need to create a MemoryAccess for it.
854
2
      if (ModelReadOnlyScalars)
855
1
        TargetStmt->ensureValueRead(UseVal);
856
2
857
2
      NumReadOnlyCopied++;
858
2
      TotalReadOnlyCopied++;
859
2
      return FD_DidForwardLeaf;
860
2
861
28
    case VirtualUse::Intra:
862
28
      // Knowing that UseStmt and DefStmt are the same statement instance, just
863
28
      // reuse the information about UseStmt for DefStmt
864
28
      DefStmt = UseStmt;
865
28
866
28
      LLVM_FALLTHROUGH;
867
100
    case VirtualUse::Inter:
868
100
      Instruction *Inst = cast<Instruction>(UseVal);
869
100
870
100
      if (!DefStmt) {
871
72
        DefStmt = S->getStmtFor(Inst);
872
72
        if (!DefStmt)
873
0
          return FD_CannotForward;
874
100
      }
875
100
876
100
      DefLoop = LI->getLoopFor(Inst->getParent());
877
100
878
100
      ForwardingDecision SpeculativeResult =
879
100
          forwardSpeculatable(TargetStmt, Inst, DefStmt, DefLoop, DoIt);
880
100
      if (SpeculativeResult != FD_NotApplicable)
881
34
        return SpeculativeResult;
882
66
883
66
      ForwardingDecision KnownResult = forwardKnownLoad(
884
66
          TargetStmt, Inst, UseStmt, UseLoop, DefStmt, DefLoop, DoIt);
885
66
      if (KnownResult != FD_NotApplicable)
886
42
        return KnownResult;
887
24
888
24
      ForwardingDecision ReloadResult = reloadKnownContent(
889
24
          TargetStmt, Inst, UseStmt, UseLoop, DefStmt, DefLoop, DoIt);
890
24
      if (ReloadResult != FD_NotApplicable)
891
14
        return ReloadResult;
892
10
893
10
      // When no method is found to forward the operand tree, we effectively
894
10
      // cannot handle it.
895
10
      LLVM_DEBUG(dbgs() << "    Cannot forward instruction: " << *Inst << "\n");
896
10
      return FD_CannotForward;
897
0
    }
898
0
899
0
    llvm_unreachable("Case unhandled");
900
0
  }
901
902
  /// Try to forward an operand tree rooted in @p RA.
903
48
  bool tryForwardTree(MemoryAccess *RA) {
904
48
    assert(RA->isLatestScalarKind());
905
48
    LLVM_DEBUG(dbgs() << "Trying to forward operand tree " << RA << "...\n");
906
48
907
48
    ScopStmt *Stmt = RA->getStatement();
908
48
    Loop *InLoop = Stmt->getSurroundingLoop();
909
48
910
48
    isl::map TargetToUse;
911
48
    if (!Known.is_null()) {
912
48
      isl::space DomSpace = Stmt->getDomainSpace();
913
48
      TargetToUse =
914
48
          isl::map::identity(DomSpace.map_from_domain_and_range(DomSpace));
915
48
    }
916
48
917
48
    ForwardingDecision Assessment =
918
48
        forwardTree(Stmt, RA->getAccessValue(), Stmt, InLoop, false);
919
48
    assert(Assessment != FD_DidForwardTree && Assessment != FD_DidForwardLeaf);
920
48
    if (Assessment != FD_CanForwardProfitably)
921
11
      return false;
922
37
923
37
    ForwardingDecision Execution =
924
37
        forwardTree(Stmt, RA->getAccessValue(), Stmt, InLoop, true);
925
37
    assert(((Execution == FD_DidForwardTree) ||
926
37
            (Execution == FD_DidForwardLeaf)) &&
927
37
           "A previous positive assessment must also be executable");
928
37
929
37
    if (Execution == FD_DidForwardTree)
930
30
      Stmt->removeSingleMemoryAccess(RA);
931
37
    return true;
932
37
  }
933
934
  /// Return which SCoP this instance is processing.
935
0
  Scop *getScop() const { return S; }
936
937
  /// Run the algorithm: Use value read accesses as operand tree roots and try
938
  /// to forward them into the statement.
939
34
  bool forwardOperandTrees() {
940
87
    for (ScopStmt &Stmt : *S) {
941
87
      bool StmtModified = false;
942
87
943
87
      // Because we are modifying the MemoryAccess list, collect them first to
944
87
      // avoid iterator invalidation.
945
87
      SmallVector<MemoryAccess *, 16> Accs;
946
177
      for (MemoryAccess *RA : Stmt) {
947
177
        if (!RA->isRead())
948
105
          continue;
949
72
        if (!RA->isLatestScalarKind())
950
24
          continue;
951
48
952
48
        Accs.push_back(RA);
953
48
      }
954
87
955
87
      for (MemoryAccess *RA : Accs) {
956
48
        if (tryForwardTree(RA)) {
957
37
          Modified = true;
958
37
          StmtModified = true;
959
37
          NumForwardedTrees++;
960
37
          TotalForwardedTrees++;
961
37
        }
962
48
      }
963
87
964
87
      if (StmtModified) {
965
33
        NumModifiedStmts++;
966
33
        TotalModifiedStmts++;
967
33
      }
968
87
    }
969
34
970
34
    if (Modified)
971
26
      ScopsModified++;
972
34
    return Modified;
973
34
  }
974
975
  /// Print the pass result, performed transformations and the SCoP after the
976
  /// transformation.
977
33
  void print(raw_ostream &OS, int Indent = 0) {
978
33
    printStatistics(OS, Indent);
979
33
980
33
    if (!Modified) {
981
8
      // This line can easily be checked in regression tests.
982
8
      OS << "ForwardOpTree executed, but did not modify anything\n";
983
8
      return;
984
8
    }
985
25
986
25
    printStatements(OS, Indent);
987
25
  }
988
};
989
990
/// Pass that redirects scalar reads to array elements that are known to contain
991
/// the same value.
992
///
993
/// This reduces the number of scalar accesses and therefore potentially
994
/// increases the freedom of the scheduler. In the ideal case, all reads of a
995
/// scalar definition are redirected (We currently do not care about removing
996
/// the write in this case).  This is also useful for the main DeLICM pass as
997
/// there are less scalars to be mapped.
998
class ForwardOpTree : public ScopPass {
999
private:
1000
  /// The pass implementation, also holding per-scop data.
1001
  std::unique_ptr<ForwardOpTreeImpl> Impl;
1002
1003
public:
1004
  static char ID;
1005
1006
33
  explicit ForwardOpTree() : ScopPass(ID) {}
1007
  ForwardOpTree(const ForwardOpTree &) = delete;
1008
  ForwardOpTree &operator=(const ForwardOpTree &) = delete;
1009
1010
33
  void getAnalysisUsage(AnalysisUsage &AU) const override {
1011
33
    AU.addRequiredTransitive<ScopInfoRegionPass>();
1012
33
    AU.addRequired<LoopInfoWrapperPass>();
1013
33
    AU.setPreservesAll();
1014
33
  }
1015
1016
34
  bool runOnScop(Scop &S) override {
1017
34
    // Free resources for previous SCoP's computation, if not yet done.
1018
34
    releaseMemory();
1019
34
1020
34
    LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
1021
34
1022
34
    {
1023
34
      IslMaxOperationsGuard MaxOpGuard(S.getIslCtx().get(), MaxOps, false);
1024
34
      Impl = llvm::make_unique<ForwardOpTreeImpl>(&S, &LI, MaxOpGuard);
1025
34
1026
34
      if (AnalyzeKnown) {
1027
34
        LLVM_DEBUG(dbgs() << "Prepare forwarders...\n");
1028
34
        Impl->computeKnownValues();
1029
34
      }
1030
34
1031
34
      LLVM_DEBUG(dbgs() << "Forwarding operand trees...\n");
1032
34
      Impl->forwardOperandTrees();
1033
34
1034
34
      if (MaxOpGuard.hasQuotaExceeded()) {
1035
0
        LLVM_DEBUG(dbgs() << "Not all operations completed because of "
1036
0
                             "max_operations exceeded\n");
1037
0
        KnownOutOfQuota++;
1038
0
      }
1039
34
    }
1040
34
1041
34
    LLVM_DEBUG(dbgs() << "\nFinal Scop:\n");
1042
34
    LLVM_DEBUG(dbgs() << S);
1043
34
1044
34
    // Update statistics
1045
34
    auto ScopStats = S.getStatistics();
1046
34
    NumValueWrites += ScopStats.NumValueWrites;
1047
34
    NumValueWritesInLoops += ScopStats.NumValueWritesInLoops;
1048
34
    NumPHIWrites += ScopStats.NumPHIWrites;
1049
34
    NumPHIWritesInLoops += ScopStats.NumPHIWritesInLoops;
1050
34
    NumSingletonWrites += ScopStats.NumSingletonWrites;
1051
34
    NumSingletonWritesInLoops += ScopStats.NumSingletonWritesInLoops;
1052
34
1053
34
    return false;
1054
34
  }
1055
1056
33
  void printScop(raw_ostream &OS, Scop &S) const override {
1057
33
    if (!Impl)
1058
0
      return;
1059
33
1060
33
    assert(Impl->getScop() == &S);
1061
33
    Impl->print(OS);
1062
33
  }
1063
1064
151
  void releaseMemory() override { Impl.reset(); }
1065
}; // class ForwardOpTree
1066
1067
char ForwardOpTree::ID;
1068
} // namespace
1069
1070
0
ScopPass *polly::createForwardOpTreePass() { return new ForwardOpTree(); }
1071
1072
43.8k
INITIALIZE_PASS_BEGIN(ForwardOpTree, "polly-optree",
1073
43.8k
                      "Polly - Forward operand tree", false, false)
1074
43.8k
INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
1075
43.8k
INITIALIZE_PASS_END(ForwardOpTree, "polly-optree",
1076
                    "Polly - Forward operand tree", false, false)