1 
2 #include "polly/Support/SCEVValidator.h"
3 
4 #include "llvm/Analysis/ScalarEvolution.h"
5 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
6 #include "llvm/Analysis/RegionInfo.h"
7 
8 #include <vector>
9 
10 using namespace llvm;
11 
12 namespace SCEVType {
13   /// @brief The type of a SCEV
14   ///
15   /// To check for the validity of a SCEV we assign to each SCEV a type. The
16   /// possible types are INT, PARAM, IV and INVALID. The order of the types is
17   /// important. The subexpressions of SCEV with a type X can only have a type
18   /// that is smaller or equal than X.
19   enum TYPE {
20              // An integer value.
21              INT,
22 
23              // An expression that is constant during the execution of the Scop,
24              // but that may depend on parameters unknown at compile time.
25              PARAM,
26 
27              // An expression that may change during the execution of the SCoP.
28              IV,
29 
30              // An invalid expression.
31              INVALID
32   };
33 }
34 
35 /// @brief The result the validator returns for a SCEV expression.
36 class ValidatorResult {
37   /// @brief The type of the expression
38   SCEVType::TYPE Type;
39 
40   /// @brief The set of Parameters in the expression.
41   std::vector<const SCEV*> Parameters;
42 
43 public:
44 
45   /// @brief Create an invalid result.
46   ValidatorResult() : Type(SCEVType::INVALID) {};
47 
48   /// @brief The copy constructor
49   ValidatorResult(const ValidatorResult &Source) {
50     Type = Source.Type;
51     Parameters = Source.Parameters;
52   };
53 
54   /// @brief Construct a result with a certain type and no parameters.
55   ValidatorResult(SCEVType::TYPE Type) : Type(Type) {};
56 
57   /// @brief Construct a result with a certain type and a single parameter.
58   ValidatorResult(SCEVType::TYPE Type, const SCEV *Expr) : Type(Type) {
59     Parameters.push_back(Expr);
60   };
61 
62   /// @brief Is the analyzed SCEV constant during the execution of the SCoP.
63   bool isConstant() {
64     return Type == SCEVType::INT || Type == SCEVType::PARAM;
65   }
66 
67   /// @brief Is the analyzed SCEV valid.
68   bool isValid() {
69     return Type != SCEVType::INVALID;
70   }
71 
72   /// @brief Is the analyzed SCEV of Type IV.
73   bool isIV() {
74     return Type == SCEVType::IV;
75   }
76 
77   /// @brief Is the analyzed SCEV of Type INT.
78   bool isINT() {
79     return Type == SCEVType::INT;
80   }
81 
82   /// @brief Get the parameters of this validator result.
83   std::vector<const SCEV*> getParameters() {
84     return Parameters;
85   }
86 
87   /// @brief Add the parameters of Source to this result.
88   void addParamsFrom(class ValidatorResult &Source) {
89     Parameters.insert(Parameters.end(),
90                       Source.Parameters.begin(),
91                       Source.Parameters.end());
92   }
93 
94   /// @brief Merge a result.
95   ///
96   /// This means to merge the parameters and to set the Type to the most
97   /// specific Type that matches both.
98   void merge(class ValidatorResult &ToMerge) {
99     Type = std::max(Type, ToMerge.Type);
100     addParamsFrom(ToMerge);
101   }
102 };
103 
104 /// Check if a SCEV is valid in a SCoP.
105 struct SCEVValidator
106   : public SCEVVisitor<SCEVValidator, class ValidatorResult> {
107 private:
108   const Region *R;
109   ScalarEvolution &SE;
110   const Value *BaseAddress;
111 
112 public:
113   SCEVValidator(const Region *R, ScalarEvolution &SE,
114                 const Value *BaseAddress) : R(R), SE(SE),
115     BaseAddress(BaseAddress) {};
116 
117   class ValidatorResult visitConstant(const SCEVConstant *Constant) {
118     return ValidatorResult(SCEVType::INT);
119   }
120 
121   class ValidatorResult visitTruncateExpr(const SCEVTruncateExpr *Expr) {
122     ValidatorResult Op = visit(Expr->getOperand());
123 
124     // We currently do not represent a truncate expression as an affine
125     // expression. If it is constant during Scop execution, we treat it as a
126     // parameter, otherwise we bail out.
127     if (Op.isConstant())
128       return ValidatorResult(SCEVType::PARAM, Expr);
129 
130     return ValidatorResult(SCEVType::INVALID);
131   }
132 
133   class ValidatorResult visitZeroExtendExpr(const SCEVZeroExtendExpr *Expr) {
134     ValidatorResult Op = visit(Expr->getOperand());
135 
136     // We currently do not represent a zero extend expression as an affine
137     // expression. If it is constant during Scop execution, we treat it as a
138     // parameter, otherwise we bail out.
139     if (Op.isConstant())
140       return ValidatorResult(SCEVType::PARAM, Expr);
141 
142     return ValidatorResult(SCEVType::INVALID);
143   }
144 
145   class ValidatorResult visitSignExtendExpr(const SCEVSignExtendExpr *Expr) {
146     // We currently allow only signed SCEV expressions. In the case of a
147     // signed value, a sign extend is a noop.
148     //
149     // TODO: Reconsider this when we add support for unsigned values.
150     return visit(Expr->getOperand());
151   }
152 
153   class ValidatorResult visitAddExpr(const SCEVAddExpr *Expr) {
154     ValidatorResult Return(SCEVType::INT);
155 
156     for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) {
157       ValidatorResult Op = visit(Expr->getOperand(i));
158 
159       if (!Op.isValid())
160         return ValidatorResult(SCEVType::INVALID);
161 
162       Return.merge(Op);
163     }
164 
165     // TODO: Check for NSW and NUW.
166     return Return;
167   }
168 
169   class ValidatorResult visitMulExpr(const SCEVMulExpr *Expr) {
170     ValidatorResult Return(SCEVType::INT);
171 
172     for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) {
173       ValidatorResult Op = visit(Expr->getOperand(i));
174 
175       if (Op.isINT())
176         continue;
177 
178       if (!Op.isValid() || !Return.isINT())
179         return ValidatorResult(SCEVType::INVALID);
180 
181       Return.merge(Op);
182     }
183 
184     // TODO: Check for NSW and NUW.
185     return Return;
186   }
187 
188   class ValidatorResult visitUDivExpr(const SCEVUDivExpr *Expr) {
189     ValidatorResult LHS = visit(Expr->getLHS());
190     ValidatorResult RHS = visit(Expr->getRHS());
191 
192     // We currently do not represent an unsigned devision as an affine
193     // expression. If the division is constant during Scop execution we treat it
194     // as a parameter, otherwise we bail out.
195     if (LHS.isConstant() && RHS.isConstant())
196       return ValidatorResult(SCEVType::PARAM, Expr);
197 
198     return ValidatorResult(SCEVType::INVALID);
199   }
200 
201   class ValidatorResult visitAddRecExpr(const SCEVAddRecExpr *Expr) {
202     if (!Expr->isAffine())
203       return ValidatorResult(SCEVType::INVALID);
204 
205     ValidatorResult Start = visit(Expr->getStart());
206     ValidatorResult Recurrence = visit(Expr->getStepRecurrence(SE));
207 
208     if (!Start.isValid() || !Recurrence.isConstant())
209       return ValidatorResult(SCEVType::INVALID);
210 
211     if (R->contains(Expr->getLoop())) {
212       if (Recurrence.isINT()) {
213         ValidatorResult Result(SCEVType::IV);
214         Result.addParamsFrom(Start);
215         return Result;
216       }
217 
218       return ValidatorResult(SCEVType::INVALID);
219     }
220 
221     if (Start.isConstant())
222       return ValidatorResult(SCEVType::PARAM, Expr);
223 
224     return ValidatorResult(SCEVType::INVALID);
225   }
226 
227   class ValidatorResult visitSMaxExpr(const SCEVSMaxExpr *Expr) {
228     ValidatorResult Return(SCEVType::INT);
229 
230     for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) {
231       ValidatorResult Op = visit(Expr->getOperand(i));
232 
233       if (!Op.isValid())
234         return ValidatorResult(SCEVType::INVALID);
235 
236       Return.merge(Op);
237     }
238 
239     return Return;
240   }
241 
242   class ValidatorResult visitUMaxExpr(const SCEVUMaxExpr *Expr) {
243     ValidatorResult Return(SCEVType::PARAM);
244 
245     // We do not support unsigned operations. If 'Expr' is constant during Scop
246     // execution we treat this as a parameter, otherwise we bail out.
247     for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) {
248       ValidatorResult Op = visit(Expr->getOperand(i));
249 
250       if (!Op.isConstant())
251         return ValidatorResult(SCEVType::INVALID);
252 
253       Return.merge(Op);
254     }
255 
256     return Return;
257   }
258 
259   ValidatorResult visitUnknown(const SCEVUnknown *Expr) {
260     Value *V = Expr->getValue();
261 
262     if (isa<UndefValue>(V))
263       return ValidatorResult(SCEVType::INVALID);
264 
265     if (Instruction *I = dyn_cast<Instruction>(Expr->getValue()))
266       if (R->contains(I))
267         return ValidatorResult(SCEVType::INVALID);
268 
269     if (BaseAddress == V)
270       return ValidatorResult(SCEVType::INVALID);
271 
272     return ValidatorResult(SCEVType::PARAM, Expr);
273   }
274 };
275 
276 namespace polly {
277   bool isAffineExpr(const Region *R, const SCEV *Expr, ScalarEvolution &SE,
278                     const Value *BaseAddress) {
279     if (isa<SCEVCouldNotCompute>(Expr))
280       return false;
281 
282     SCEVValidator Validator(R, SE, BaseAddress);
283     ValidatorResult Result = Validator.visit(Expr);
284 
285     return Result.isValid();
286   }
287 
288   std::vector<const SCEV*> getParamsInAffineExpr(const Region *R,
289                                                  const SCEV *Expr,
290                                                  ScalarEvolution &SE,
291                                                  const Value *BaseAddress) {
292     if (isa<SCEVCouldNotCompute>(Expr))
293       return std::vector<const SCEV*>();
294 
295     SCEVValidator Validator(R, SE, BaseAddress);
296     ValidatorResult Result = Validator.visit(Expr);
297 
298     return Result.getParameters();
299   }
300 }
301 
302 
303