Coverage Report

Created: 2019-02-15 18:59

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