Coverage Report

Created: 2018-10-23 03:11

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/tools/polly/include/polly/Support/SCEVAffinator.h
Line
Count
Source
1
//===------ polly/SCEVAffinator.h - Create isl expressions from SCEVs -----===//
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
// Create a polyhedral description for a SCEV value.
11
//
12
//===----------------------------------------------------------------------===//
13
14
#ifndef POLLY_SCEV_AFFINATOR_H
15
#define POLLY_SCEV_AFFINATOR_H
16
17
#include "llvm/ADT/DenseMap.h"
18
#include "llvm/Analysis/ScalarEvolutionExpressions.h"
19
20
#include "isl/isl-noexceptions.h"
21
22
namespace llvm {
23
class Region;
24
class BasicBlock;
25
class DataLayout;
26
class ScalarEvolution;
27
} // namespace llvm
28
29
namespace polly {
30
class Scop;
31
class ScopStmt;
32
33
/// The result type of the SCEVAffinator.
34
///
35
/// The first element of the pair is the isl representation of the SCEV, the
36
/// second is the domain under which it is __invalid__.
37
typedef std::pair<isl::pw_aff, isl::set> PWACtx;
38
39
/// Translate a SCEV to an isl::pw_aff and the domain on which it is invalid.
40
struct SCEVAffinator : public llvm::SCEVVisitor<SCEVAffinator, PWACtx> {
41
public:
42
  SCEVAffinator(Scop *S, llvm::LoopInfo &LI);
43
44
  /// Translate a SCEV to an isl::pw_aff.
45
  ///
46
  /// @param E  he expression that is translated.
47
  /// @param BB The block in which @p E is executed.
48
  ///
49
  /// @returns The isl representation of the SCEV @p E in @p Domain.
50
  PWACtx getPwAff(const llvm::SCEV *E, llvm::BasicBlock *BB = nullptr);
51
52
  /// Take the assumption that @p PWAC is non-negative.
53
  void takeNonNegativeAssumption(PWACtx &PWAC);
54
55
  /// Interpret the PWA in @p PWAC as an unsigned value.
56
  void interpretAsUnsigned(PWACtx &PWAC, unsigned Width);
57
58
  /// Check an <nsw> AddRec for the loop @p L is cached.
59
  bool hasNSWAddRecForLoop(llvm::Loop *L) const;
60
61
  /// Return the LoopInfo used by thi object.
62
2.70k
  llvm::LoopInfo *getLI() const { return &LI; }
63
64
private:
65
  /// Key to identify cached expressions.
66
  using CacheKey = std::pair<const llvm::SCEV *, llvm::BasicBlock *>;
67
68
  /// Map to remembered cached expressions.
69
  llvm::DenseMap<CacheKey, PWACtx> CachedExpressions;
70
71
  Scop *S;
72
  isl::ctx Ctx;
73
  unsigned NumIterators;
74
  llvm::ScalarEvolution &SE;
75
  llvm::LoopInfo &LI;
76
  llvm::BasicBlock *BB;
77
78
  /// Target data for element size computing.
79
  const llvm::DataLayout &TD;
80
81
  /// Return the loop for the current block if any.
82
  llvm::Loop *getScope();
83
84
  /// Return a PWACtx for @p PWA that is always valid.
85
  PWACtx getPWACtxFromPWA(isl::pw_aff PWA);
86
87
  /// Compute the non-wrapping version of @p PWA for type @p ExprType.
88
  ///
89
  /// @param PWA  The piece-wise affine function that might wrap.
90
  /// @param Type The type of the SCEV that was translated to @p PWA.
91
  ///
92
  /// @returns The expr @p PWA modulo the size constraints of @p ExprType.
93
  isl::pw_aff addModuloSemantic(isl::pw_aff PWA, llvm::Type *ExprType) const;
94
95
  /// If @p Expr might cause an integer wrap record an assumption.
96
  ///
97
  /// @param Expr The SCEV expression that might wrap.
98
  /// @param PWAC The isl representation of @p Expr with the invalid domain.
99
  ///
100
  /// @returns The isl representation @p PWAC with a possibly adjusted domain.
101
  PWACtx checkForWrapping(const llvm::SCEV *Expr, PWACtx PWAC) const;
102
103
  /// Whether to track the value of this expression precisely, rather than
104
  /// assuming it won't wrap.
105
  bool computeModuloForExpr(const llvm::SCEV *Expr);
106
107
  PWACtx visit(const llvm::SCEV *E);
108
  PWACtx visitConstant(const llvm::SCEVConstant *E);
109
  PWACtx visitTruncateExpr(const llvm::SCEVTruncateExpr *E);
110
  PWACtx visitZeroExtendExpr(const llvm::SCEVZeroExtendExpr *E);
111
  PWACtx visitSignExtendExpr(const llvm::SCEVSignExtendExpr *E);
112
  PWACtx visitAddExpr(const llvm::SCEVAddExpr *E);
113
  PWACtx visitMulExpr(const llvm::SCEVMulExpr *E);
114
  PWACtx visitUDivExpr(const llvm::SCEVUDivExpr *E);
115
  PWACtx visitAddRecExpr(const llvm::SCEVAddRecExpr *E);
116
  PWACtx visitSMaxExpr(const llvm::SCEVSMaxExpr *E);
117
  PWACtx visitUMaxExpr(const llvm::SCEVUMaxExpr *E);
118
  PWACtx visitUnknown(const llvm::SCEVUnknown *E);
119
  PWACtx visitSDivInstruction(llvm::Instruction *SDiv);
120
  PWACtx visitSRemInstruction(llvm::Instruction *SRem);
121
  PWACtx complexityBailout();
122
123
  friend struct llvm::SCEVVisitor<SCEVAffinator, PWACtx>;
124
};
125
} // namespace polly
126
127
#endif