Coverage Report

Created: 2018-06-19 22:08

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/tools/polly/include/polly/ScopDetection.h
Line
Count
Source (jump to first uncovered line)
1
//===- ScopDetection.h - Detect Scops ---------------------------*- 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
// Detect the maximal Scops of a function.
11
//
12
// A static control part (Scop) is a subgraph of the control flow graph (CFG)
13
// that only has statically known control flow and can therefore be described
14
// within the polyhedral model.
15
//
16
// Every Scop fulfills these restrictions:
17
//
18
// * It is a single entry single exit region
19
//
20
// * Only affine linear bounds in the loops
21
//
22
// Every natural loop in a Scop must have a number of loop iterations that can
23
// be described as an affine linear function in surrounding loop iterators or
24
// parameters. (A parameter is a scalar that does not change its value during
25
// execution of the Scop).
26
//
27
// * Only comparisons of affine linear expressions in conditions
28
//
29
// * All loops and conditions perfectly nested
30
//
31
// The control flow needs to be structured such that it could be written using
32
// just 'for' and 'if' statements, without the need for any 'goto', 'break' or
33
// 'continue'.
34
//
35
// * Side effect free functions call
36
//
37
// Only function calls and intrinsics that do not have side effects are allowed
38
// (readnone).
39
//
40
// The Scop detection finds the largest Scops by checking if the largest
41
// region is a Scop. If this is not the case, its canonical subregions are
42
// checked until a region is a Scop. It is now tried to extend this Scop by
43
// creating a larger non canonical region.
44
//
45
//===----------------------------------------------------------------------===//
46
47
#ifndef POLLY_SCOPDETECTION_H
48
#define POLLY_SCOPDETECTION_H
49
50
#include "polly/ScopDetectionDiagnostic.h"
51
#include "polly/Support/ScopHelper.h"
52
#include "llvm/ADT/DenseMap.h"
53
#include "llvm/ADT/SetVector.h"
54
#include "llvm/ADT/SmallVector.h"
55
#include "llvm/ADT/StringRef.h"
56
#include "llvm/Analysis/AliasAnalysis.h"
57
#include "llvm/Analysis/AliasSetTracker.h"
58
#include "llvm/Analysis/RegionInfo.h"
59
#include "llvm/Analysis/ScalarEvolutionExpressions.h"
60
#include "llvm/Pass.h"
61
#include <algorithm>
62
#include <map>
63
#include <memory>
64
#include <set>
65
#include <string>
66
#include <utility>
67
#include <vector>
68
69
using namespace llvm;
70
71
namespace llvm {
72
73
class BasicBlock;
74
class BranchInst;
75
class CallInst;
76
class DebugLoc;
77
class DominatorTree;
78
class Function;
79
class Instruction;
80
class IntrinsicInst;
81
class Loop;
82
class LoopInfo;
83
class OptimizationRemarkEmitter;
84
class PassRegistry;
85
class raw_ostream;
86
class ScalarEvolution;
87
class SCEV;
88
class SCEVUnknown;
89
class SwitchInst;
90
class Value;
91
92
void initializeScopDetectionWrapperPassPass(PassRegistry &);
93
} // namespace llvm
94
95
namespace polly {
96
97
using ParamSetType = std::set<const SCEV *>;
98
99
// Description of the shape of an array.
100
struct ArrayShape {
101
  // Base pointer identifying all accesses to this array.
102
  const SCEVUnknown *BasePointer;
103
104
  // Sizes of each delinearized dimension.
105
  SmallVector<const SCEV *, 4> DelinearizedSizes;
106
107
441
  ArrayShape(const SCEVUnknown *B) : BasePointer(B) {}
108
};
109
110
struct MemAcc {
111
  const Instruction *Insn;
112
113
  // A pointer to the shape description of the array.
114
  std::shared_ptr<ArrayShape> Shape;
115
116
  // Subscripts computed by delinearization.
117
  SmallVector<const SCEV *, 4> DelinearizedSubscripts;
118
119
  MemAcc(const Instruction *I, std::shared_ptr<ArrayShape> S)
120
703
      : Insn(I), Shape(S) {}
121
};
122
123
using MapInsnToMemAcc = std::map<const Instruction *, MemAcc>;
124
using PairInstSCEV = std::pair<const Instruction *, const SCEV *>;
125
using AFs = std::vector<PairInstSCEV>;
126
using BaseToAFs = std::map<const SCEVUnknown *, AFs>;
127
using BaseToElSize = std::map<const SCEVUnknown *, const SCEV *>;
128
129
extern bool PollyTrackFailures;
130
extern bool PollyDelinearize;
131
extern bool PollyUseRuntimeAliasChecks;
132
extern bool PollyProcessUnprofitable;
133
extern bool PollyInvariantLoadHoisting;
134
extern bool PollyAllowUnsignedOperations;
135
extern bool PollyAllowFullFunction;
136
137
/// A function attribute which will cause Polly to skip the function
138
extern StringRef PollySkipFnAttr;
139
140
//===----------------------------------------------------------------------===//
141
/// Pass to detect the maximal static control parts (Scops) of a
142
/// function.
143
class ScopDetection {
144
public:
145
  using RegionSet = SetVector<const Region *>;
146
147
  // Remember the valid regions
148
  RegionSet ValidRegions;
149
150
  /// Context variables for SCoP detection.
151
  struct DetectionContext {
152
    Region &CurRegion;   // The region to check.
153
    AliasSetTracker AST; // The AliasSetTracker to hold the alias information.
154
    bool Verifying;      // If we are in the verification phase?
155
156
    /// Container to remember rejection reasons for this region.
157
    RejectLog Log;
158
159
    /// Map a base pointer to all access functions accessing it.
160
    ///
161
    /// This map is indexed by the base pointer. Each element of the map
162
    /// is a list of memory accesses that reference this base pointer.
163
    BaseToAFs Accesses;
164
165
    /// The set of base pointers with non-affine accesses.
166
    ///
167
    /// This set contains all base pointers and the locations where they are
168
    /// used for memory accesses that can not be detected as affine accesses.
169
    SetVector<std::pair<const SCEVUnknown *, Loop *>> NonAffineAccesses;
170
    BaseToElSize ElementSize;
171
172
    /// The region has at least one load instruction.
173
    bool hasLoads = false;
174
175
    /// The region has at least one store instruction.
176
    bool hasStores = false;
177
178
    /// Flag to indicate the region has at least one unknown access.
179
    bool HasUnknownAccess = false;
180
181
    /// The set of non-affine subregions in the region we analyze.
182
    RegionSet NonAffineSubRegionSet;
183
184
    /// The set of loops contained in non-affine regions.
185
    BoxedLoopsSetTy BoxedLoopsSet;
186
187
    /// Loads that need to be invariant during execution.
188
    InvariantLoadsSetTy RequiredILS;
189
190
    /// Map to memory access description for the corresponding LLVM
191
    ///        instructions.
192
    MapInsnToMemAcc InsnToMemAcc;
193
194
    /// Initialize a DetectionContext from scratch.
195
    DetectionContext(Region &R, AliasAnalysis &AA, bool Verify)
196
5.14k
        : CurRegion(R), AST(AA), Verifying(Verify), Log(&R) {}
197
198
    /// Initialize a DetectionContext with the data from @p DC.
199
    DetectionContext(const DetectionContext &&DC)
200
        : CurRegion(DC.CurRegion), AST(DC.AST.getAliasAnalysis()),
201
          Verifying(DC.Verifying), Log(std::move(DC.Log)),
202
          Accesses(std::move(DC.Accesses)),
203
          NonAffineAccesses(std::move(DC.NonAffineAccesses)),
204
          ElementSize(std::move(DC.ElementSize)), hasLoads(DC.hasLoads),
205
          hasStores(DC.hasStores), HasUnknownAccess(DC.HasUnknownAccess),
206
          NonAffineSubRegionSet(std::move(DC.NonAffineSubRegionSet)),
207
          BoxedLoopsSet(std::move(DC.BoxedLoopsSet)),
208
10.2k
          RequiredILS(std::move(DC.RequiredILS)) {
209
10.2k
      AST.add(DC.AST);
210
10.2k
    }
211
  };
212
213
  /// Helper data structure to collect statistics about loop counts.
214
  struct LoopStats {
215
    int NumLoops;
216
    int MaxDepth;
217
  };
218
219
private:
220
  //===--------------------------------------------------------------------===//
221
222
  /// Analyses used
223
  //@{
224
  const DominatorTree &DT;
225
  ScalarEvolution &SE;
226
  LoopInfo &LI;
227
  RegionInfo &RI;
228
  AliasAnalysis &AA;
229
  //@}
230
231
  /// Map to remember detection contexts for all regions.
232
  using DetectionContextMapTy = DenseMap<BBPair, DetectionContext>;
233
  mutable DetectionContextMapTy DetectionContextMap;
234
235
  /// Remove cached results for @p R.
236
  void removeCachedResults(const Region &R);
237
238
  /// Remove cached results for the children of @p R recursively.
239
  void removeCachedResultsRecursively(const Region &R);
240
241
  /// Check if @p S0 and @p S1 do contain multiple possibly aliasing pointers.
242
  ///
243
  /// @param S0    A expression to check.
244
  /// @param S1    Another expression to check or nullptr.
245
  /// @param Scope The loop/scope the expressions are checked in.
246
  ///
247
  /// @returns True, if multiple possibly aliasing pointers are used in @p S0
248
  ///          (and @p S1 if given).
249
  bool involvesMultiplePtrs(const SCEV *S0, const SCEV *S1, Loop *Scope) const;
250
251
  /// Add the region @p AR as over approximated sub-region in @p Context.
252
  ///
253
  /// @param AR      The non-affine subregion.
254
  /// @param Context The current detection context.
255
  ///
256
  /// @returns True if the subregion can be over approximated, false otherwise.
257
  bool addOverApproximatedRegion(Region *AR, DetectionContext &Context) const;
258
259
  /// Find for a given base pointer terms that hint towards dimension
260
  ///        sizes of a multi-dimensional array.
261
  ///
262
  /// @param Context      The current detection context.
263
  /// @param BasePointer  A base pointer indicating the virtual array we are
264
  ///                     interested in.
265
  SmallVector<const SCEV *, 4>
266
  getDelinearizationTerms(DetectionContext &Context,
267
                          const SCEVUnknown *BasePointer) const;
268
269
  /// Check if the dimension size of a delinearized array is valid.
270
  ///
271
  /// @param Context     The current detection context.
272
  /// @param Sizes       The sizes of the different array dimensions.
273
  /// @param BasePointer The base pointer we are interested in.
274
  /// @param Scope       The location where @p BasePointer is being used.
275
  /// @returns True if one or more array sizes could be derived - meaning: we
276
  ///          see this array as multi-dimensional.
277
  bool hasValidArraySizes(DetectionContext &Context,
278
                          SmallVectorImpl<const SCEV *> &Sizes,
279
                          const SCEVUnknown *BasePointer, Loop *Scope) const;
280
281
  /// Derive access functions for a given base pointer.
282
  ///
283
  /// @param Context     The current detection context.
284
  /// @param Sizes       The sizes of the different array dimensions.
285
  /// @param BasePointer The base pointer of all the array for which to compute
286
  ///                    access functions.
287
  /// @param Shape       The shape that describes the derived array sizes and
288
  ///                    which should be filled with newly computed access
289
  ///                    functions.
290
  /// @returns True if a set of affine access functions could be derived.
291
  bool computeAccessFunctions(DetectionContext &Context,
292
                              const SCEVUnknown *BasePointer,
293
                              std::shared_ptr<ArrayShape> Shape) const;
294
295
  /// Check if all accesses to a given BasePointer are affine.
296
  ///
297
  /// @param Context     The current detection context.
298
  /// @param BasePointer the base pointer we are interested in.
299
  /// @param Scope       The location where @p BasePointer is being used.
300
  /// @param True if consistent (multi-dimensional) array accesses could be
301
  ///        derived for this array.
302
  bool hasBaseAffineAccesses(DetectionContext &Context,
303
                             const SCEVUnknown *BasePointer, Loop *Scope) const;
304
305
  // Delinearize all non affine memory accesses and return false when there
306
  // exists a non affine memory access that cannot be delinearized. Return true
307
  // when all array accesses are affine after delinearization.
308
  bool hasAffineMemoryAccesses(DetectionContext &Context) const;
309
310
  // Try to expand the region R. If R can be expanded return the expanded
311
  // region, NULL otherwise.
312
  Region *expandRegion(Region &R);
313
314
  /// Find the Scops in this region tree.
315
  ///
316
  /// @param The region tree to scan for scops.
317
  void findScops(Region &R);
318
319
  /// Check if all basic block in the region are valid.
320
  ///
321
  /// @param Context The context of scop detection.
322
  ///
323
  /// @return True if all blocks in R are valid, false otherwise.
324
  bool allBlocksValid(DetectionContext &Context) const;
325
326
  /// Check if a region has sufficient compute instructions.
327
  ///
328
  /// This function checks if a region has a non-trivial number of instructions
329
  /// in each loop. This can be used as an indicator whether a loop is worth
330
  /// optimizing.
331
  ///
332
  /// @param Context  The context of scop detection.
333
  /// @param NumLoops The number of loops in the region.
334
  ///
335
  /// @return True if region is has sufficient compute instructions,
336
  ///         false otherwise.
337
  bool hasSufficientCompute(DetectionContext &Context,
338
                            int NumAffineLoops) const;
339
340
  /// Check if the unique affine loop might be amendable to distribution.
341
  ///
342
  /// This function checks if the number of non-trivial blocks in the unique
343
  /// affine loop in Context.CurRegion is at least two, thus if the loop might
344
  /// be amendable to distribution.
345
  ///
346
  /// @param Context  The context of scop detection.
347
  ///
348
  /// @return True only if the affine loop might be amendable to distributable.
349
  bool hasPossiblyDistributableLoop(DetectionContext &Context) const;
350
351
  /// Check if a region is profitable to optimize.
352
  ///
353
  /// Regions that are unlikely to expose interesting optimization opportunities
354
  /// are called 'unprofitable' and may be skipped during scop detection.
355
  ///
356
  /// @param Context The context of scop detection.
357
  ///
358
  /// @return True if region is profitable to optimize, false otherwise.
359
  bool isProfitableRegion(DetectionContext &Context) const;
360
361
  /// Check if a region is a Scop.
362
  ///
363
  /// @param Context The context of scop detection.
364
  ///
365
  /// @return True if R is a Scop, false otherwise.
366
  bool isValidRegion(DetectionContext &Context) const;
367
368
  /// Check if an intrinsic call can be part of a Scop.
369
  ///
370
  /// @param II      The intrinsic call instruction to check.
371
  /// @param Context The current detection context.
372
  ///
373
  /// @return True if the call instruction is valid, false otherwise.
374
  bool isValidIntrinsicInst(IntrinsicInst &II, DetectionContext &Context) const;
375
376
  /// Check if a call instruction can be part of a Scop.
377
  ///
378
  /// @param CI      The call instruction to check.
379
  /// @param Context The current detection context.
380
  ///
381
  /// @return True if the call instruction is valid, false otherwise.
382
  bool isValidCallInst(CallInst &CI, DetectionContext &Context) const;
383
384
  /// Check if the given loads could be invariant and can be hoisted.
385
  ///
386
  /// If true is returned the loads are added to the required invariant loads
387
  /// contained in the @p Context.
388
  ///
389
  /// @param RequiredILS The loads to check.
390
  /// @param Context     The current detection context.
391
  ///
392
  /// @return True if all loads can be assumed invariant.
393
  bool onlyValidRequiredInvariantLoads(InvariantLoadsSetTy &RequiredILS,
394
                                       DetectionContext &Context) const;
395
396
  /// Check if a value is invariant in the region Reg.
397
  ///
398
  /// @param Val Value to check for invariance.
399
  /// @param Reg The region to consider for the invariance of Val.
400
  /// @param Ctx The current detection context.
401
  ///
402
  /// @return True if the value represented by Val is invariant in the region
403
  ///         identified by Reg.
404
  bool isInvariant(Value &Val, const Region &Reg, DetectionContext &Ctx) const;
405
406
  /// Check if the memory access caused by @p Inst is valid.
407
  ///
408
  /// @param Inst    The access instruction.
409
  /// @param AF      The access function.
410
  /// @param BP      The access base pointer.
411
  /// @param Context The current detection context.
412
  bool isValidAccess(Instruction *Inst, const SCEV *AF, const SCEVUnknown *BP,
413
                     DetectionContext &Context) const;
414
415
  /// Check if a memory access can be part of a Scop.
416
  ///
417
  /// @param Inst The instruction accessing the memory.
418
  /// @param Context The context of scop detection.
419
  ///
420
  /// @return True if the memory access is valid, false otherwise.
421
  bool isValidMemoryAccess(MemAccInst Inst, DetectionContext &Context) const;
422
423
  /// Check if an instruction has any non trivial scalar dependencies as part of
424
  /// a Scop.
425
  ///
426
  /// @param Inst The instruction to check.
427
  /// @param RefRegion The region in respect to which we check the access
428
  ///                  function.
429
  ///
430
  /// @return True if the instruction has scalar dependences, false otherwise.
431
  bool hasScalarDependency(Instruction &Inst, Region &RefRegion) const;
432
433
  /// Check if an instruction can be part of a Scop.
434
  ///
435
  /// @param Inst The instruction to check.
436
  /// @param Context The context of scop detection.
437
  ///
438
  /// @return True if the instruction is valid, false otherwise.
439
  bool isValidInstruction(Instruction &Inst, DetectionContext &Context) const;
440
441
  /// Check if the switch @p SI with condition @p Condition is valid.
442
  ///
443
  /// @param BB           The block to check.
444
  /// @param SI           The switch to check.
445
  /// @param Condition    The switch condition.
446
  /// @param IsLoopBranch Flag to indicate the branch is a loop exit/latch.
447
  /// @param Context      The context of scop detection.
448
  ///
449
  /// @return True if the branch @p BI is valid.
450
  bool isValidSwitch(BasicBlock &BB, SwitchInst *SI, Value *Condition,
451
                     bool IsLoopBranch, DetectionContext &Context) const;
452
453
  /// Check if the branch @p BI with condition @p Condition is valid.
454
  ///
455
  /// @param BB           The block to check.
456
  /// @param BI           The branch to check.
457
  /// @param Condition    The branch condition.
458
  /// @param IsLoopBranch Flag to indicate the branch is a loop exit/latch.
459
  /// @param Context      The context of scop detection.
460
  ///
461
  /// @return True if the branch @p BI is valid.
462
  bool isValidBranch(BasicBlock &BB, BranchInst *BI, Value *Condition,
463
                     bool IsLoopBranch, DetectionContext &Context) const;
464
465
  /// Check if the SCEV @p S is affine in the current @p Context.
466
  ///
467
  /// This will also use a heuristic to decide if we want to require loads to be
468
  /// invariant to make the expression affine or if we want to treat is as
469
  /// non-affine.
470
  ///
471
  /// @param S           The expression to be checked.
472
  /// @param Scope       The loop nest in which @p S is used.
473
  /// @param Context     The context of scop detection.
474
  bool isAffine(const SCEV *S, Loop *Scope, DetectionContext &Context) const;
475
476
  /// Check if the control flow in a basic block is valid.
477
  ///
478
  /// This function checks if a certain basic block is terminated by a
479
  /// Terminator instruction we can handle or, if this is not the case,
480
  /// registers this basic block as the start of a non-affine region.
481
  ///
482
  /// This function optionally allows unreachable statements.
483
  ///
484
  /// @param BB               The BB to check the control flow.
485
  /// @param IsLoopBranch     Flag to indicate the branch is a loop exit/latch.
486
  //  @param AllowUnreachable Allow unreachable statements.
487
  /// @param Context          The context of scop detection.
488
  ///
489
  /// @return True if the BB contains only valid control flow.
490
  bool isValidCFG(BasicBlock &BB, bool IsLoopBranch, bool AllowUnreachable,
491
                  DetectionContext &Context) const;
492
493
  /// Is a loop valid with respect to a given region.
494
  ///
495
  /// @param L The loop to check.
496
  /// @param Context The context of scop detection.
497
  ///
498
  /// @return True if the loop is valid in the region.
499
  bool isValidLoop(Loop *L, DetectionContext &Context) const;
500
501
  /// Count the number of loops and the maximal loop depth in @p L.
502
  ///
503
  /// @param L The loop to check.
504
  /// @param SE The scalar evolution analysis.
505
  /// @param MinProfitableTrips The minimum number of trip counts from which
506
  ///                           a loop is assumed to be profitable and
507
  ///                           consequently is counted.
508
  /// returns A tuple of number of loops and their maximal depth.
509
  static ScopDetection::LoopStats
510
  countBeneficialSubLoops(Loop *L, ScalarEvolution &SE,
511
                          unsigned MinProfitableTrips);
512
513
  /// Check if the function @p F is marked as invalid.
514
  ///
515
  /// @note An OpenMP subfunction will be marked as invalid.
516
  bool isValidFunction(Function &F);
517
518
  /// Can ISL compute the trip count of a loop.
519
  ///
520
  /// @param L The loop to check.
521
  /// @param Context The context of scop detection.
522
  ///
523
  /// @return True if ISL can compute the trip count of the loop.
524
  bool canUseISLTripCount(Loop *L, DetectionContext &Context) const;
525
526
  /// Print the locations of all detected scops.
527
  void printLocations(Function &F);
528
529
  /// Check if a region is reducible or not.
530
  ///
531
  /// @param Region The region to check.
532
  /// @param DbgLoc Parameter to save the location of instruction that
533
  ///               causes irregular control flow if the region is irreducible.
534
  ///
535
  /// @return True if R is reducible, false otherwise.
536
  bool isReducibleRegion(Region &R, DebugLoc &DbgLoc) const;
537
538
  /// Track diagnostics for invalid scops.
539
  ///
540
  /// @param Context The context of scop detection.
541
  /// @param Assert Throw an assert in verify mode or not.
542
  /// @param Args Argument list that gets passed to the constructor of RR.
543
  template <class RR, typename... Args>
544
  inline bool invalid(DetectionContext &Context, bool Assert,
545
                      Args &&... Arguments) const;
546
547
public:
548
  ScopDetection(Function &F, const DominatorTree &DT, ScalarEvolution &SE,
549
                LoopInfo &LI, RegionInfo &RI, AliasAnalysis &AA,
550
                OptimizationRemarkEmitter &ORE);
551
552
  /// Get the RegionInfo stored in this pass.
553
  ///
554
  /// This was added to give the DOT printer easy access to this information.
555
22
  RegionInfo *getRI() const { return &RI; }
556
557
  /// Get the LoopInfo stored in this pass.
558
0
  LoopInfo *getLI() const { return &LI; }
559
560
  /// Is the region is the maximum region of a Scop?
561
  ///
562
  /// @param R The Region to test if it is maximum.
563
  /// @param Verify Rerun the scop detection to verify SCoP was not invalidated
564
  ///               meanwhile.
565
  ///
566
  /// @return Return true if R is the maximum Region in a Scop, false otherwise.
567
  bool isMaxRegionInScop(const Region &R, bool Verify = true) const;
568
569
  /// Return the detection context for @p R, nullptr if @p R was invalid.
570
  DetectionContext *getDetectionContext(const Region *R) const;
571
572
  /// Return the set of rejection causes for @p R.
573
  const RejectLog *lookupRejectionLog(const Region *R) const;
574
575
  /// Return true if @p SubR is a non-affine subregion in @p ScopR.
576
  bool isNonAffineSubRegion(const Region *SubR, const Region *ScopR) const;
577
578
  /// Get a message why a region is invalid
579
  ///
580
  /// @param R The region for which we get the error message
581
  ///
582
  /// @return The error or "" if no error appeared.
583
  std::string regionIsInvalidBecause(const Region *R) const;
584
585
  /// @name Maximum Region In Scops Iterators
586
  ///
587
  /// These iterators iterator over all maximum region in Scops of this
588
  /// function.
589
  //@{
590
  using iterator = RegionSet::iterator;
591
  using const_iterator = RegionSet::const_iterator;
592
593
52
  iterator begin() { return ValidRegions.begin(); }
594
52
  iterator end() { return ValidRegions.end(); }
595
596
0
  const_iterator begin() const { return ValidRegions.begin(); }
597
0
  const_iterator end() const { return ValidRegions.end(); }
598
  //@}
599
600
  /// Emit rejection remarks for all rejected regions.
601
  ///
602
  /// @param F The function to emit remarks for.
603
  void emitMissedRemarks(const Function &F);
604
605
  /// Mark the function as invalid so we will not extract any scop from
606
  ///        the function.
607
  ///
608
  /// @param F The function to mark as invalid.
609
  static void markFunctionAsInvalid(Function *F);
610
611
  /// Verify if all valid Regions in this Function are still valid
612
  /// after some transformations.
613
  void verifyAnalysis() const;
614
615
  /// Verify if R is still a valid part of Scop after some transformations.
616
  ///
617
  /// @param R The Region to verify.
618
  void verifyRegion(const Region &R) const;
619
620
  /// Count the number of loops and the maximal loop depth in @p R.
621
  ///
622
  /// @param R The region to check
623
  /// @param SE The scalar evolution analysis.
624
  /// @param MinProfitableTrips The minimum number of trip counts from which
625
  ///                           a loop is assumed to be profitable and
626
  ///                           consequently is counted.
627
  /// returns A tuple of number of loops and their maximal depth.
628
  static ScopDetection::LoopStats
629
  countBeneficialLoops(Region *R, ScalarEvolution &SE, LoopInfo &LI,
630
                       unsigned MinProfitableTrips);
631
632
private:
633
  /// OptimizationRemarkEmitter object used to emit diagnostic remarks
634
  OptimizationRemarkEmitter &ORE;
635
};
636
637
struct ScopAnalysis : public AnalysisInfoMixin<ScopAnalysis> {
638
  static AnalysisKey Key;
639
640
  using Result = ScopDetection;
641
642
  ScopAnalysis();
643
644
  Result run(Function &F, FunctionAnalysisManager &FAM);
645
};
646
647
struct ScopAnalysisPrinterPass : public PassInfoMixin<ScopAnalysisPrinterPass> {
648
1
  ScopAnalysisPrinterPass(raw_ostream &OS) : OS(OS) {}
649
650
  PreservedAnalyses run(Function &F, FunctionAnalysisManager &FAM);
651
652
  raw_ostream &OS;
653
};
654
655
struct ScopDetectionWrapperPass : public FunctionPass {
656
  static char ID;
657
  std::unique_ptr<ScopDetection> Result;
658
659
  ScopDetectionWrapperPass();
660
661
  /// @name FunctionPass interface
662
  //@{
663
  void getAnalysisUsage(AnalysisUsage &AU) const override;
664
  void releaseMemory() override;
665
  bool runOnFunction(Function &F) override;
666
  void print(raw_ostream &OS, const Module *) const override;
667
  //@}
668
669
4.19k
  ScopDetection &getSD() { return *Result; }
670
2
  const ScopDetection &getSD() const { return *Result; }
671
};
672
} // namespace polly
673
674
#endif // POLLY_SCOPDETECTION_H