Coverage Report

Created: 2017-03-28 09:59

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