1 //===--------- SCEVAffinator.cpp  - Create Scops from LLVM IR -------------===//
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 #include "polly/Support/SCEVAffinator.h"
15 #include "polly/ScopInfo.h"
16 #include "polly/Support/GICHelper.h"
17 #include "polly/Support/SCEVValidator.h"
18 #include "polly/Support/ScopHelper.h"
19 #include "isl/aff.h"
20 #include "isl/local_space.h"
21 #include "isl/set.h"
22 #include "isl/val.h"
23 
24 using namespace llvm;
25 using namespace polly;
26 
27 SCEVAffinator::SCEVAffinator(Scop *S)
28     : S(S), Ctx(S->getIslCtx()), R(S->getRegion()), SE(*S->getSE()),
29       TD(R.getEntry()->getParent()->getParent()->getDataLayout()) {}
30 
31 SCEVAffinator::~SCEVAffinator() {
32   for (const auto &CachedPair : CachedExpressions)
33     isl_pw_aff_free(CachedPair.second);
34 }
35 
36 __isl_give isl_pw_aff *SCEVAffinator::getPwAff(const SCEV *Expr,
37                                                BasicBlock *BB) {
38   this->BB = BB;
39 
40   if (BB) {
41     auto *DC = S->getDomainConditions(BB);
42     NumIterators = isl_set_n_dim(DC);
43     isl_set_free(DC);
44   } else
45     NumIterators = 0;
46 
47   S->addParams(getParamsInAffineExpr(&R, Expr, SE));
48 
49   return visit(Expr);
50 }
51 
52 __isl_give isl_set *
53 SCEVAffinator::getWrappingContext(SCEV::NoWrapFlags Flags, Type *ExprType,
54                                   __isl_keep isl_pw_aff *PWA,
55                                   __isl_take isl_set *ExprDomain) const {
56   // If the SCEV flags do contain NSW (no signed wrap) then PWA already
57   // represents Expr in modulo semantic (it is not allowed to overflow), thus we
58   // are done. Otherwise, we will compute:
59   //   PWA = ((PWA + 2^(n-1)) mod (2 ^ n)) - 2^(n-1)
60   // whereas n is the number of bits of the Expr, hence:
61   //   n = bitwidth(ExprType)
62 
63   if (Flags & SCEV::FlagNSW)
64     return nullptr;
65 
66   isl_pw_aff *PWAMod = addModuloSemantic(isl_pw_aff_copy(PWA), ExprType);
67   if (isl_pw_aff_is_equal(PWA, PWAMod)) {
68     isl_pw_aff_free(PWAMod);
69     return nullptr;
70   }
71 
72   PWA = isl_pw_aff_copy(PWA);
73 
74   auto *NotEqualSet = isl_pw_aff_ne_set(PWA, PWAMod);
75   NotEqualSet = isl_set_intersect(NotEqualSet, isl_set_copy(ExprDomain));
76   NotEqualSet = isl_set_gist_params(NotEqualSet, S->getContext());
77   NotEqualSet = isl_set_params(NotEqualSet);
78   return NotEqualSet;
79 }
80 
81 __isl_give isl_set *SCEVAffinator::getWrappingContext() const {
82 
83   isl_set *WrappingCtx = isl_set_empty(S->getParamSpace());
84 
85   for (const auto &CachedPair : CachedExpressions) {
86     const SCEV *Expr = CachedPair.first.first;
87     SCEV::NoWrapFlags Flags;
88 
89     switch (Expr->getSCEVType()) {
90     case scAddExpr:
91       Flags = cast<SCEVAddExpr>(Expr)->getNoWrapFlags();
92       break;
93     case scMulExpr:
94       Flags = cast<SCEVMulExpr>(Expr)->getNoWrapFlags();
95       break;
96     case scAddRecExpr:
97       Flags = cast<SCEVAddRecExpr>(Expr)->getNoWrapFlags();
98       break;
99     default:
100       continue;
101     }
102 
103     isl_pw_aff *PWA = CachedPair.second;
104     BasicBlock *BB = CachedPair.first.second;
105     isl_set *ExprDomain = BB ? S->getDomainConditions(BB) : nullptr;
106 
107     isl_set *WPWACtx =
108         getWrappingContext(Flags, Expr->getType(), PWA, ExprDomain);
109     isl_set_free(ExprDomain);
110 
111     WrappingCtx = WPWACtx ? isl_set_union(WrappingCtx, WPWACtx) : WrappingCtx;
112   }
113 
114   return WrappingCtx;
115 }
116 
117 __isl_give isl_pw_aff *
118 SCEVAffinator::addModuloSemantic(__isl_take isl_pw_aff *PWA,
119                                  Type *ExprType) const {
120   unsigned Width = TD.getTypeStoreSizeInBits(ExprType);
121   isl_ctx *Ctx = isl_pw_aff_get_ctx(PWA);
122 
123   isl_val *ModVal = isl_val_int_from_ui(Ctx, Width);
124   ModVal = isl_val_2exp(ModVal);
125 
126   isl_val *AddVal = isl_val_int_from_ui(Ctx, Width - 1);
127   AddVal = isl_val_2exp(AddVal);
128 
129   isl_set *Domain = isl_pw_aff_domain(isl_pw_aff_copy(PWA));
130 
131   isl_pw_aff *AddPW = isl_pw_aff_val_on_domain(Domain, AddVal);
132 
133   PWA = isl_pw_aff_add(PWA, isl_pw_aff_copy(AddPW));
134   PWA = isl_pw_aff_mod_val(PWA, ModVal);
135   PWA = isl_pw_aff_sub(PWA, AddPW);
136 
137   return PWA;
138 }
139 
140 bool SCEVAffinator::hasNSWAddRecForLoop(Loop *L) const {
141   for (const auto &CachedPair : CachedExpressions) {
142     auto *AddRec = dyn_cast<SCEVAddRecExpr>(CachedPair.first.first);
143     if (!AddRec)
144       continue;
145     if (AddRec->getLoop() != L)
146       continue;
147     if (AddRec->getNoWrapFlags() & SCEV::FlagNSW)
148       return true;
149   }
150 
151   return false;
152 }
153 
154 __isl_give isl_pw_aff *SCEVAffinator::visit(const SCEV *Expr) {
155 
156   auto Key = std::make_pair(Expr, BB);
157   isl_pw_aff *PWA = CachedExpressions[Key];
158   if (PWA)
159     return isl_pw_aff_copy(PWA);
160 
161   auto ConstantAndLeftOverPair = extractConstantFactor(Expr, *S->getSE());
162   auto *Factor = ConstantAndLeftOverPair.first;
163   Expr = ConstantAndLeftOverPair.second;
164 
165   // In case the scev is a valid parameter, we do not further analyze this
166   // expression, but create a new parameter in the isl_pw_aff. This allows us
167   // to treat subexpressions that we cannot translate into an piecewise affine
168   // expression, as constant parameters of the piecewise affine expression.
169   if (isl_id *Id = S->getIdForParam(Expr)) {
170     isl_space *Space = isl_space_set_alloc(Ctx, 1, NumIterators);
171     Space = isl_space_set_dim_id(Space, isl_dim_param, 0, Id);
172 
173     isl_set *Domain = isl_set_universe(isl_space_copy(Space));
174     isl_aff *Affine = isl_aff_zero_on_domain(isl_local_space_from_space(Space));
175     Affine = isl_aff_add_coefficient_si(Affine, isl_dim_param, 0, 1);
176 
177     PWA = isl_pw_aff_alloc(Domain, Affine);
178   } else {
179     PWA = SCEVVisitor<SCEVAffinator, isl_pw_aff *>::visit(Expr);
180   }
181 
182   PWA = isl_pw_aff_mul(visitConstant(Factor), PWA);
183 
184   // For compile time reasons we need to simplify the PWA before we cache and
185   // return it.
186   PWA = isl_pw_aff_coalesce(PWA);
187   CachedExpressions[Key] = isl_pw_aff_copy(PWA);
188   return PWA;
189 }
190 
191 __isl_give isl_pw_aff *SCEVAffinator::visitConstant(const SCEVConstant *Expr) {
192   ConstantInt *Value = Expr->getValue();
193   isl_val *v;
194 
195   // LLVM does not define if an integer value is interpreted as a signed or
196   // unsigned value. Hence, without further information, it is unknown how
197   // this value needs to be converted to GMP. At the moment, we only support
198   // signed operations. So we just interpret it as signed. Later, there are
199   // two options:
200   //
201   // 1. We always interpret any value as signed and convert the values on
202   //    demand.
203   // 2. We pass down the signedness of the calculation and use it to interpret
204   //    this constant correctly.
205   v = isl_valFromAPInt(Ctx, Value->getValue(), /* isSigned */ true);
206 
207   isl_space *Space = isl_space_set_alloc(Ctx, 0, NumIterators);
208   isl_local_space *ls = isl_local_space_from_space(Space);
209   return isl_pw_aff_from_aff(isl_aff_val_on_domain(ls, v));
210 }
211 
212 __isl_give isl_pw_aff *
213 SCEVAffinator::visitTruncateExpr(const SCEVTruncateExpr *Expr) {
214   llvm_unreachable("SCEVTruncateExpr not yet supported");
215 }
216 
217 __isl_give isl_pw_aff *
218 SCEVAffinator::visitZeroExtendExpr(const SCEVZeroExtendExpr *Expr) {
219   llvm_unreachable("SCEVZeroExtendExpr not yet supported");
220 }
221 
222 __isl_give isl_pw_aff *
223 SCEVAffinator::visitSignExtendExpr(const SCEVSignExtendExpr *Expr) {
224   // Assuming the value is signed, a sign extension is basically a noop.
225   // TODO: Reconsider this as soon as we support unsigned values.
226   return visit(Expr->getOperand());
227 }
228 
229 __isl_give isl_pw_aff *SCEVAffinator::visitAddExpr(const SCEVAddExpr *Expr) {
230   isl_pw_aff *Sum = visit(Expr->getOperand(0));
231 
232   for (int i = 1, e = Expr->getNumOperands(); i < e; ++i) {
233     isl_pw_aff *NextSummand = visit(Expr->getOperand(i));
234     Sum = isl_pw_aff_add(Sum, NextSummand);
235   }
236 
237   return Sum;
238 }
239 
240 __isl_give isl_pw_aff *SCEVAffinator::visitMulExpr(const SCEVMulExpr *Expr) {
241   llvm_unreachable("SCEVMulExpr should not be reached");
242 }
243 
244 __isl_give isl_pw_aff *SCEVAffinator::visitUDivExpr(const SCEVUDivExpr *Expr) {
245   llvm_unreachable("SCEVUDivExpr not yet supported");
246 }
247 
248 __isl_give isl_pw_aff *
249 SCEVAffinator::visitAddRecExpr(const SCEVAddRecExpr *Expr) {
250   assert(Expr->isAffine() && "Only affine AddRecurrences allowed");
251 
252   auto Flags = Expr->getNoWrapFlags();
253 
254   // Directly generate isl_pw_aff for Expr if 'start' is zero.
255   if (Expr->getStart()->isZero()) {
256     assert(S->getRegion().contains(Expr->getLoop()) &&
257            "Scop does not contain the loop referenced in this AddRec");
258 
259     isl_pw_aff *Step = visit(Expr->getOperand(1));
260     isl_space *Space = isl_space_set_alloc(Ctx, 0, NumIterators);
261     isl_local_space *LocalSpace = isl_local_space_from_space(Space);
262 
263     unsigned loopDimension = S->getRelativeLoopDepth(Expr->getLoop());
264 
265     isl_aff *LAff = isl_aff_set_coefficient_si(
266         isl_aff_zero_on_domain(LocalSpace), isl_dim_in, loopDimension, 1);
267     isl_pw_aff *LPwAff = isl_pw_aff_from_aff(LAff);
268 
269     return isl_pw_aff_mul(Step, LPwAff);
270   }
271 
272   // Translate AddRecExpr from '{start, +, inc}' into 'start + {0, +, inc}'
273   // if 'start' is not zero.
274   // TODO: Using the original SCEV no-wrap flags is not always safe, however
275   //       as our code generation is reordering the expression anyway it doesn't
276   //       really matter.
277   ScalarEvolution &SE = *S->getSE();
278   const SCEV *ZeroStartExpr =
279       SE.getAddRecExpr(SE.getConstant(Expr->getStart()->getType(), 0),
280                        Expr->getStepRecurrence(SE), Expr->getLoop(), Flags);
281 
282   isl_pw_aff *ZeroStartResult = visit(ZeroStartExpr);
283   isl_pw_aff *Start = visit(Expr->getStart());
284 
285   return isl_pw_aff_add(ZeroStartResult, Start);
286 }
287 
288 __isl_give isl_pw_aff *SCEVAffinator::visitSMaxExpr(const SCEVSMaxExpr *Expr) {
289   isl_pw_aff *Max = visit(Expr->getOperand(0));
290 
291   for (int i = 1, e = Expr->getNumOperands(); i < e; ++i) {
292     isl_pw_aff *NextOperand = visit(Expr->getOperand(i));
293     Max = isl_pw_aff_max(Max, NextOperand);
294   }
295 
296   return Max;
297 }
298 
299 __isl_give isl_pw_aff *SCEVAffinator::visitUMaxExpr(const SCEVUMaxExpr *Expr) {
300   llvm_unreachable("SCEVUMaxExpr not yet supported");
301 }
302 
303 __isl_give isl_pw_aff *SCEVAffinator::visitSDivInstruction(Instruction *SDiv) {
304   assert(SDiv->getOpcode() == Instruction::SDiv && "Assumed SDiv instruction!");
305   auto *SE = S->getSE();
306 
307   auto *Divisor = SDiv->getOperand(1);
308   auto *DivisorSCEV = SE->getSCEV(Divisor);
309   auto *DivisorPWA = visit(DivisorSCEV);
310   assert(isa<ConstantInt>(Divisor) &&
311          "SDiv is no parameter but has a non-constant RHS.");
312 
313   auto *Dividend = SDiv->getOperand(0);
314   auto *DividendSCEV = SE->getSCEV(Dividend);
315   auto *DividendPWA = visit(DividendSCEV);
316   return isl_pw_aff_tdiv_q(DividendPWA, DivisorPWA);
317 }
318 
319 __isl_give isl_pw_aff *SCEVAffinator::visitSRemInstruction(Instruction *SRem) {
320   assert(SRem->getOpcode() == Instruction::SRem && "Assumed SRem instruction!");
321   auto *SE = S->getSE();
322 
323   auto *Divisor = dyn_cast<ConstantInt>(SRem->getOperand(1));
324   assert(Divisor && "SRem is no parameter but has a non-constant RHS.");
325   auto *DivisorVal = isl_valFromAPInt(Ctx, Divisor->getValue(),
326                                       /* isSigned */ true);
327 
328   auto *Dividend = SRem->getOperand(0);
329   auto *DividendSCEV = SE->getSCEV(Dividend);
330   auto *DividendPWA = visit(DividendSCEV);
331 
332   return isl_pw_aff_mod_val(DividendPWA, isl_val_abs(DivisorVal));
333 }
334 
335 __isl_give isl_pw_aff *SCEVAffinator::visitUnknown(const SCEVUnknown *Expr) {
336   if (Instruction *I = dyn_cast<Instruction>(Expr->getValue())) {
337     switch (I->getOpcode()) {
338     case Instruction::SDiv:
339       return visitSDivInstruction(I);
340     case Instruction::SRem:
341       return visitSRemInstruction(I);
342     default:
343       break; // Fall through.
344     }
345   }
346 
347   llvm_unreachable(
348       "Unknowns SCEV was neither parameter nor a valid instruction.");
349 }
350