Coverage Report

Created: 2017-08-21 19:50

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