/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/tools/polly/lib/CodeGen/IslExprBuilder.cpp
Line | Count | Source (jump to first uncovered line) |
1 | | //===------ IslExprBuilder.cpp ----- Code generate isl AST expressions ----===// |
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 | | //===----------------------------------------------------------------------===// |
10 | | |
11 | | #include "polly/CodeGen/IslExprBuilder.h" |
12 | | #include "polly/CodeGen/RuntimeDebugBuilder.h" |
13 | | #include "polly/Options.h" |
14 | | #include "polly/ScopInfo.h" |
15 | | #include "polly/Support/GICHelper.h" |
16 | | #include "llvm/Transforms/Utils/BasicBlockUtils.h" |
17 | | |
18 | | using namespace llvm; |
19 | | using namespace polly; |
20 | | |
21 | | /// Different overflow tracking modes. |
22 | | enum OverflowTrackingChoice { |
23 | | OT_NEVER, ///< Never tack potential overflows. |
24 | | OT_REQUEST, ///< Track potential overflows if requested. |
25 | | OT_ALWAYS ///< Always track potential overflows. |
26 | | }; |
27 | | |
28 | | static cl::opt<OverflowTrackingChoice> OTMode( |
29 | | "polly-overflow-tracking", |
30 | | cl::desc("Define where potential integer overflows in generated " |
31 | | "expressions should be tracked."), |
32 | | cl::values(clEnumValN(OT_NEVER, "never", "Never track the overflow bit."), |
33 | | clEnumValN(OT_REQUEST, "request", |
34 | | "Track the overflow bit if requested."), |
35 | | clEnumValN(OT_ALWAYS, "always", |
36 | | "Always track the overflow bit.")), |
37 | | cl::Hidden, cl::init(OT_REQUEST), cl::ZeroOrMore, cl::cat(PollyCategory)); |
38 | | |
39 | | IslExprBuilder::IslExprBuilder(Scop &S, PollyIRBuilder &Builder, |
40 | | IDToValueTy &IDToValue, ValueMapT &GlobalMap, |
41 | | const DataLayout &DL, ScalarEvolution &SE, |
42 | | DominatorTree &DT, LoopInfo &LI, |
43 | | BasicBlock *StartBlock) |
44 | | : S(S), Builder(Builder), IDToValue(IDToValue), GlobalMap(GlobalMap), |
45 | 305 | DL(DL), SE(SE), DT(DT), LI(LI), StartBlock(StartBlock) { |
46 | 305 | OverflowState = (OTMode == OT_ALWAYS) ? Builder.getFalse()1 : nullptr304 ; |
47 | 305 | } |
48 | | |
49 | 630 | void IslExprBuilder::setTrackOverflow(bool Enable) { |
50 | 630 | // If potential overflows are tracked always or never we ignore requests |
51 | 630 | // to change the behavior. |
52 | 630 | if (OTMode != OT_REQUEST) |
53 | 12 | return; |
54 | 618 | |
55 | 618 | if (Enable) { |
56 | 309 | // If tracking should be enabled initialize the OverflowState. |
57 | 309 | OverflowState = Builder.getFalse(); |
58 | 309 | } else { |
59 | 309 | // If tracking should be disabled just unset the OverflowState. |
60 | 309 | OverflowState = nullptr; |
61 | 309 | } |
62 | 618 | } |
63 | | |
64 | 315 | Value *IslExprBuilder::getOverflowState() const { |
65 | 315 | // If the overflow tracking was requested but it is disabled we avoid the |
66 | 315 | // additional nullptr checks at the call sides but instead provide a |
67 | 315 | // meaningful result. |
68 | 315 | if (OTMode == OT_NEVER) |
69 | 3 | return Builder.getFalse(); |
70 | 312 | return OverflowState; |
71 | 312 | } |
72 | | |
73 | 3.19k | bool IslExprBuilder::hasLargeInts(isl::ast_expr Expr) { |
74 | 3.19k | enum isl_ast_expr_type Type = isl_ast_expr_get_type(Expr.get()); |
75 | 3.19k | |
76 | 3.19k | if (Type == isl_ast_expr_id) |
77 | 639 | return false; |
78 | 2.55k | |
79 | 2.55k | if (Type == isl_ast_expr_int) { |
80 | 926 | isl::val Val = Expr.get_val(); |
81 | 926 | APInt APValue = APIntFromVal(Val); |
82 | 926 | auto BitWidth = APValue.getBitWidth(); |
83 | 926 | return BitWidth >= 64; |
84 | 926 | } |
85 | 1.62k | |
86 | 1.62k | assert(Type == isl_ast_expr_op && "Expected isl_ast_expr of type operation"); |
87 | 1.62k | |
88 | 1.62k | int NumArgs = isl_ast_expr_get_op_n_arg(Expr.get()); |
89 | 1.62k | |
90 | 4.47k | for (int i = 0; i < NumArgs; i++2.84k ) { |
91 | 2.88k | isl::ast_expr Operand = Expr.get_op_arg(i); |
92 | 2.88k | if (hasLargeInts(Operand)) |
93 | 43 | return true; |
94 | 2.88k | } |
95 | 1.62k | |
96 | 1.62k | return false1.58k ; |
97 | 1.62k | } |
98 | | |
99 | | Value *IslExprBuilder::createBinOp(BinaryOperator::BinaryOps Opc, Value *LHS, |
100 | 1.42k | Value *RHS, const Twine &Name) { |
101 | 1.42k | // Handle the plain operation (without overflow tracking) first. |
102 | 1.42k | if (!OverflowState) { |
103 | 1.26k | switch (Opc) { |
104 | 1.26k | case Instruction::Add: |
105 | 589 | return Builder.CreateNSWAdd(LHS, RHS, Name); |
106 | 1.26k | case Instruction::Sub: |
107 | 105 | return Builder.CreateNSWSub(LHS, RHS, Name); |
108 | 1.26k | case Instruction::Mul: |
109 | 573 | return Builder.CreateNSWMul(LHS, RHS, Name); |
110 | 1.26k | default: |
111 | 0 | llvm_unreachable("Unknown binary operator!"); |
112 | 160 | } |
113 | 160 | } |
114 | 160 | |
115 | 160 | Function *F = nullptr; |
116 | 160 | Module *M = Builder.GetInsertBlock()->getModule(); |
117 | 160 | switch (Opc) { |
118 | 160 | case Instruction::Add: |
119 | 100 | F = Intrinsic::getDeclaration(M, Intrinsic::sadd_with_overflow, |
120 | 100 | {LHS->getType()}); |
121 | 100 | break; |
122 | 160 | case Instruction::Sub: |
123 | 3 | F = Intrinsic::getDeclaration(M, Intrinsic::ssub_with_overflow, |
124 | 3 | {LHS->getType()}); |
125 | 3 | break; |
126 | 160 | case Instruction::Mul: |
127 | 57 | F = Intrinsic::getDeclaration(M, Intrinsic::smul_with_overflow, |
128 | 57 | {LHS->getType()}); |
129 | 57 | break; |
130 | 160 | default: |
131 | 0 | llvm_unreachable("No overflow intrinsic for binary operator found!"); |
132 | 160 | } |
133 | 160 | |
134 | 160 | auto *ResultStruct = Builder.CreateCall(F, {LHS, RHS}, Name); |
135 | 160 | assert(ResultStruct->getType()->isStructTy()); |
136 | 160 | |
137 | 160 | auto *OverflowFlag = |
138 | 160 | Builder.CreateExtractValue(ResultStruct, 1, Name + ".obit"); |
139 | 160 | |
140 | 160 | // If all overflows are tracked we do not combine the results as this could |
141 | 160 | // cause dominance problems. Instead we will always keep the last overflow |
142 | 160 | // flag as current state. |
143 | 160 | if (OTMode == OT_ALWAYS) |
144 | 10 | OverflowState = OverflowFlag; |
145 | 150 | else |
146 | 150 | OverflowState = |
147 | 150 | Builder.CreateOr(OverflowState, OverflowFlag, "polly.overflow.state"); |
148 | 160 | |
149 | 160 | return Builder.CreateExtractValue(ResultStruct, 0, Name + ".res"); |
150 | 160 | } |
151 | | |
152 | 689 | Value *IslExprBuilder::createAdd(Value *LHS, Value *RHS, const Twine &Name) { |
153 | 689 | return createBinOp(Instruction::Add, LHS, RHS, Name); |
154 | 689 | } |
155 | | |
156 | 108 | Value *IslExprBuilder::createSub(Value *LHS, Value *RHS, const Twine &Name) { |
157 | 108 | return createBinOp(Instruction::Sub, LHS, RHS, Name); |
158 | 108 | } |
159 | | |
160 | 630 | Value *IslExprBuilder::createMul(Value *LHS, Value *RHS, const Twine &Name) { |
161 | 630 | return createBinOp(Instruction::Mul, LHS, RHS, Name); |
162 | 630 | } |
163 | | |
164 | 3.68k | Type *IslExprBuilder::getWidestType(Type *T1, Type *T2) { |
165 | 3.68k | assert(isa<IntegerType>(T1) && isa<IntegerType>(T2)); |
166 | 3.68k | |
167 | 3.68k | if (T1->getPrimitiveSizeInBits() < T2->getPrimitiveSizeInBits()) |
168 | 241 | return T2; |
169 | 3.44k | else |
170 | 3.44k | return T1; |
171 | 3.68k | } |
172 | | |
173 | 23 | Value *IslExprBuilder::createOpUnary(__isl_take isl_ast_expr *Expr) { |
174 | 23 | assert(isl_ast_expr_get_op_type(Expr) == isl_ast_op_minus && |
175 | 23 | "Unsupported unary operation"); |
176 | 23 | |
177 | 23 | Value *V; |
178 | 23 | Type *MaxType = getType(Expr); |
179 | 23 | assert(MaxType->isIntegerTy() && |
180 | 23 | "Unary expressions can only be created for integer types"); |
181 | 23 | |
182 | 23 | V = create(isl_ast_expr_get_op_arg(Expr, 0)); |
183 | 23 | MaxType = getWidestType(MaxType, V->getType()); |
184 | 23 | |
185 | 23 | if (MaxType != V->getType()) |
186 | 5 | V = Builder.CreateSExt(V, MaxType); |
187 | 23 | |
188 | 23 | isl_ast_expr_free(Expr); |
189 | 23 | return createSub(ConstantInt::getNullValue(MaxType), V); |
190 | 23 | } |
191 | | |
192 | 54 | Value *IslExprBuilder::createOpNAry(__isl_take isl_ast_expr *Expr) { |
193 | 54 | assert(isl_ast_expr_get_type(Expr) == isl_ast_expr_op && |
194 | 54 | "isl ast expression not of type isl_ast_op"); |
195 | 54 | assert(isl_ast_expr_get_op_n_arg(Expr) >= 2 && |
196 | 54 | "We need at least two operands in an n-ary operation"); |
197 | 54 | |
198 | 54 | CmpInst::Predicate Pred; |
199 | 54 | switch (isl_ast_expr_get_op_type(Expr)) { |
200 | 54 | default: |
201 | 0 | llvm_unreachable("This is not a an n-ary isl ast expression"); |
202 | 54 | case isl_ast_op_max: |
203 | 20 | Pred = CmpInst::ICMP_SGT; |
204 | 20 | break; |
205 | 54 | case isl_ast_op_min: |
206 | 34 | Pred = CmpInst::ICMP_SLT; |
207 | 34 | break; |
208 | 54 | } |
209 | 54 | |
210 | 54 | Value *V = create(isl_ast_expr_get_op_arg(Expr, 0)); |
211 | 54 | |
212 | 111 | for (int i = 1; i < isl_ast_expr_get_op_n_arg(Expr); ++i57 ) { |
213 | 57 | Value *OpV = create(isl_ast_expr_get_op_arg(Expr, i)); |
214 | 57 | Type *Ty = getWidestType(V->getType(), OpV->getType()); |
215 | 57 | |
216 | 57 | if (Ty != OpV->getType()) |
217 | 3 | OpV = Builder.CreateSExt(OpV, Ty); |
218 | 57 | |
219 | 57 | if (Ty != V->getType()) |
220 | 0 | V = Builder.CreateSExt(V, Ty); |
221 | 57 | |
222 | 57 | Value *Cmp = Builder.CreateICmp(Pred, V, OpV); |
223 | 57 | V = Builder.CreateSelect(Cmp, V, OpV); |
224 | 57 | } |
225 | 54 | |
226 | 54 | // TODO: We can truncate the result, if it fits into a smaller type. This can |
227 | 54 | // help in cases where we have larger operands (e.g. i67) but the result is |
228 | 54 | // known to fit into i64. Without the truncation, the larger i67 type may |
229 | 54 | // force all subsequent operations to be performed on a non-native type. |
230 | 54 | isl_ast_expr_free(Expr); |
231 | 54 | return V; |
232 | 54 | } |
233 | | |
234 | 756 | Value *IslExprBuilder::createAccessAddress(isl_ast_expr *Expr) { |
235 | 756 | assert(isl_ast_expr_get_type(Expr) == isl_ast_expr_op && |
236 | 756 | "isl ast expression not of type isl_ast_op"); |
237 | 756 | assert(isl_ast_expr_get_op_type(Expr) == isl_ast_op_access && |
238 | 756 | "not an access isl ast expression"); |
239 | 756 | assert(isl_ast_expr_get_op_n_arg(Expr) >= 1 && |
240 | 756 | "We need at least two operands to create a member access."); |
241 | 756 | |
242 | 756 | Value *Base, *IndexOp, *Access; |
243 | 756 | isl_ast_expr *BaseExpr; |
244 | 756 | isl_id *BaseId; |
245 | 756 | |
246 | 756 | BaseExpr = isl_ast_expr_get_op_arg(Expr, 0); |
247 | 756 | BaseId = isl_ast_expr_get_id(BaseExpr); |
248 | 756 | isl_ast_expr_free(BaseExpr); |
249 | 756 | |
250 | 756 | const ScopArrayInfo *SAI = nullptr; |
251 | 756 | |
252 | 756 | if (PollyDebugPrinting) |
253 | 0 | RuntimeDebugBuilder::createCPUPrinter(Builder, isl_id_get_name(BaseId)); |
254 | 756 | |
255 | 756 | if (IDToSAI) |
256 | 0 | SAI = (*IDToSAI)[BaseId]; |
257 | 756 | |
258 | 756 | if (!SAI) |
259 | 756 | SAI = ScopArrayInfo::getFromId(isl::manage(BaseId)); |
260 | 0 | else |
261 | 0 | isl_id_free(BaseId); |
262 | 756 | |
263 | 756 | assert(SAI && "No ScopArrayInfo found for this isl_id."); |
264 | 756 | |
265 | 756 | Base = SAI->getBasePtr(); |
266 | 756 | |
267 | 756 | if (auto NewBase = GlobalMap.lookup(Base)) |
268 | 81 | Base = NewBase; |
269 | 756 | |
270 | 756 | assert(Base->getType()->isPointerTy() && "Access base should be a pointer"); |
271 | 756 | StringRef BaseName = Base->getName(); |
272 | 756 | |
273 | 756 | auto PointerTy = PointerType::get(SAI->getElementType(), |
274 | 756 | Base->getType()->getPointerAddressSpace()); |
275 | 756 | if (Base->getType() != PointerTy) { |
276 | 284 | Base = |
277 | 284 | Builder.CreateBitCast(Base, PointerTy, "polly.access.cast." + BaseName); |
278 | 284 | } |
279 | 756 | |
280 | 756 | if (isl_ast_expr_get_op_n_arg(Expr) == 1) { |
281 | 0 | isl_ast_expr_free(Expr); |
282 | 0 | if (PollyDebugPrinting) |
283 | 0 | RuntimeDebugBuilder::createCPUPrinter(Builder, "\n"); |
284 | 0 | return Base; |
285 | 0 | } |
286 | 756 | |
287 | 756 | IndexOp = nullptr; |
288 | 1.00k | for (unsigned u = 1, e = isl_ast_expr_get_op_n_arg(Expr); u < e; u++245 ) { |
289 | 1.00k | Value *NextIndex = create(isl_ast_expr_get_op_arg(Expr, u)); |
290 | 1.00k | assert(NextIndex->getType()->isIntegerTy() && |
291 | 1.00k | "Access index should be an integer"); |
292 | 1.00k | |
293 | 1.00k | if (PollyDebugPrinting) |
294 | 0 | RuntimeDebugBuilder::createCPUPrinter(Builder, "[", NextIndex, "]"); |
295 | 1.00k | |
296 | 1.00k | if (!IndexOp) { |
297 | 756 | IndexOp = NextIndex; |
298 | 756 | } else { |
299 | 245 | Type *Ty = getWidestType(NextIndex->getType(), IndexOp->getType()); |
300 | 245 | |
301 | 245 | if (Ty != NextIndex->getType()) |
302 | 0 | NextIndex = Builder.CreateIntCast(NextIndex, Ty, true); |
303 | 245 | if (Ty != IndexOp->getType()) |
304 | 4 | IndexOp = Builder.CreateIntCast(IndexOp, Ty, true); |
305 | 245 | |
306 | 245 | IndexOp = createAdd(IndexOp, NextIndex, "polly.access.add." + BaseName); |
307 | 245 | } |
308 | 1.00k | |
309 | 1.00k | // For every but the last dimension multiply the size, for the last |
310 | 1.00k | // dimension we can exit the loop. |
311 | 1.00k | if (u + 1 >= e) |
312 | 756 | break; |
313 | 245 | |
314 | 245 | const SCEV *DimSCEV = SAI->getDimensionSize(u); |
315 | 245 | |
316 | 245 | llvm::ValueToValueMap Map(GlobalMap.begin(), GlobalMap.end()); |
317 | 245 | DimSCEV = SCEVParameterRewriter::rewrite(DimSCEV, SE, Map); |
318 | 245 | Value *DimSize = |
319 | 245 | expandCodeFor(S, SE, DL, "polly", DimSCEV, DimSCEV->getType(), |
320 | 245 | &*Builder.GetInsertPoint(), nullptr, |
321 | 245 | StartBlock->getSinglePredecessor()); |
322 | 245 | |
323 | 245 | Type *Ty = getWidestType(DimSize->getType(), IndexOp->getType()); |
324 | 245 | |
325 | 245 | if (Ty != IndexOp->getType()) |
326 | 3 | IndexOp = Builder.CreateSExtOrTrunc(IndexOp, Ty, |
327 | 3 | "polly.access.sext." + BaseName); |
328 | 245 | if (Ty != DimSize->getType()) |
329 | 2 | DimSize = Builder.CreateSExtOrTrunc(DimSize, Ty, |
330 | 2 | "polly.access.sext." + BaseName); |
331 | 245 | IndexOp = createMul(IndexOp, DimSize, "polly.access.mul." + BaseName); |
332 | 245 | } |
333 | 756 | |
334 | 756 | Access = Builder.CreateGEP(Base, IndexOp, "polly.access." + BaseName); |
335 | 756 | |
336 | 756 | if (PollyDebugPrinting) |
337 | 0 | RuntimeDebugBuilder::createCPUPrinter(Builder, "\n"); |
338 | 756 | isl_ast_expr_free(Expr); |
339 | 756 | return Access; |
340 | 756 | } |
341 | | |
342 | 4 | Value *IslExprBuilder::createOpAccess(isl_ast_expr *Expr) { |
343 | 4 | Value *Addr = createAccessAddress(Expr); |
344 | 4 | assert(Addr && "Could not create op access address"); |
345 | 4 | return Builder.CreateLoad(Addr, Addr->getName() + ".load"); |
346 | 4 | } |
347 | | |
348 | 969 | Value *IslExprBuilder::createOpBin(__isl_take isl_ast_expr *Expr) { |
349 | 969 | Value *LHS, *RHS, *Res; |
350 | 969 | Type *MaxType; |
351 | 969 | isl_ast_op_type OpType; |
352 | 969 | |
353 | 969 | assert(isl_ast_expr_get_type(Expr) == isl_ast_expr_op && |
354 | 969 | "isl ast expression not of type isl_ast_op"); |
355 | 969 | assert(isl_ast_expr_get_op_n_arg(Expr) == 2 && |
356 | 969 | "not a binary isl ast expression"); |
357 | 969 | |
358 | 969 | OpType = isl_ast_expr_get_op_type(Expr); |
359 | 969 | |
360 | 969 | LHS = create(isl_ast_expr_get_op_arg(Expr, 0)); |
361 | 969 | RHS = create(isl_ast_expr_get_op_arg(Expr, 1)); |
362 | 969 | |
363 | 969 | Type *LHSType = LHS->getType(); |
364 | 969 | Type *RHSType = RHS->getType(); |
365 | 969 | |
366 | 969 | MaxType = getWidestType(LHSType, RHSType); |
367 | 969 | |
368 | 969 | // Take the result into account when calculating the widest type. |
369 | 969 | // |
370 | 969 | // For operations such as '+' the result may require a type larger than |
371 | 969 | // the type of the individual operands. For other operations such as '/', the |
372 | 969 | // result type cannot be larger than the type of the individual operand. isl |
373 | 969 | // does not calculate correct types for these operations and we consequently |
374 | 969 | // exclude those operations here. |
375 | 969 | switch (OpType) { |
376 | 969 | case isl_ast_op_pdiv_q: |
377 | 55 | case isl_ast_op_pdiv_r: |
378 | 55 | case isl_ast_op_div: |
379 | 55 | case isl_ast_op_fdiv_q: |
380 | 55 | case isl_ast_op_zdiv_r: |
381 | 55 | // Do nothing |
382 | 55 | break; |
383 | 914 | case isl_ast_op_add: |
384 | 914 | case isl_ast_op_sub: |
385 | 914 | case isl_ast_op_mul: |
386 | 914 | MaxType = getWidestType(MaxType, getType(Expr)); |
387 | 914 | break; |
388 | 914 | default: |
389 | 0 | llvm_unreachable("This is no binary isl ast expression"); |
390 | 969 | } |
391 | 969 | |
392 | 969 | if (MaxType != RHS->getType()) |
393 | 47 | RHS = Builder.CreateSExt(RHS, MaxType); |
394 | 969 | |
395 | 969 | if (MaxType != LHS->getType()) |
396 | 96 | LHS = Builder.CreateSExt(LHS, MaxType); |
397 | 969 | |
398 | 969 | switch (OpType) { |
399 | 969 | default: |
400 | 0 | llvm_unreachable("This is no binary isl ast expression"); |
401 | 969 | case isl_ast_op_add: |
402 | 444 | Res = createAdd(LHS, RHS); |
403 | 444 | break; |
404 | 969 | case isl_ast_op_sub: |
405 | 85 | Res = createSub(LHS, RHS); |
406 | 85 | break; |
407 | 969 | case isl_ast_op_mul: |
408 | 385 | Res = createMul(LHS, RHS); |
409 | 385 | break; |
410 | 969 | case isl_ast_op_div: |
411 | 3 | Res = Builder.CreateSDiv(LHS, RHS, "pexp.div", true); |
412 | 3 | break; |
413 | 969 | case isl_ast_op_pdiv_q: // Dividend is non-negative |
414 | 13 | Res = Builder.CreateUDiv(LHS, RHS, "pexp.p_div_q"); |
415 | 13 | break; |
416 | 969 | case isl_ast_op_fdiv_q: { // Round towards -infty |
417 | 12 | if (auto *Const = dyn_cast<ConstantInt>(RHS)) { |
418 | 12 | auto &Val = Const->getValue(); |
419 | 12 | if (Val.isPowerOf2() && Val.isNonNegative()) { |
420 | 12 | Res = Builder.CreateAShr(LHS, Val.ceilLogBase2(), "polly.fdiv_q.shr"); |
421 | 12 | break; |
422 | 12 | } |
423 | 0 | } |
424 | 0 | // TODO: Review code and check that this calculation does not yield |
425 | 0 | // incorrect overflow in some edge cases. |
426 | 0 | // |
427 | 0 | // floord(n,d) ((n < 0) ? (n - d + 1) : n) / d |
428 | 0 | Value *One = ConstantInt::get(MaxType, 1); |
429 | 0 | Value *Zero = ConstantInt::get(MaxType, 0); |
430 | 0 | Value *Sum1 = createSub(LHS, RHS, "pexp.fdiv_q.0"); |
431 | 0 | Value *Sum2 = createAdd(Sum1, One, "pexp.fdiv_q.1"); |
432 | 0 | Value *isNegative = Builder.CreateICmpSLT(LHS, Zero, "pexp.fdiv_q.2"); |
433 | 0 | Value *Dividend = |
434 | 0 | Builder.CreateSelect(isNegative, Sum2, LHS, "pexp.fdiv_q.3"); |
435 | 0 | Res = Builder.CreateSDiv(Dividend, RHS, "pexp.fdiv_q.4"); |
436 | 0 | break; |
437 | 0 | } |
438 | 24 | case isl_ast_op_pdiv_r: // Dividend is non-negative |
439 | 24 | Res = Builder.CreateURem(LHS, RHS, "pexp.pdiv_r"); |
440 | 24 | break; |
441 | 0 |
|
442 | 3 | case isl_ast_op_zdiv_r: // Result only compared against zero |
443 | 3 | Res = Builder.CreateSRem(LHS, RHS, "pexp.zdiv_r"); |
444 | 3 | break; |
445 | 969 | } |
446 | 969 | |
447 | 969 | // TODO: We can truncate the result, if it fits into a smaller type. This can |
448 | 969 | // help in cases where we have larger operands (e.g. i67) but the result is |
449 | 969 | // known to fit into i64. Without the truncation, the larger i67 type may |
450 | 969 | // force all subsequent operations to be performed on a non-native type. |
451 | 969 | isl_ast_expr_free(Expr); |
452 | 969 | return Res; |
453 | 969 | } |
454 | | |
455 | 7 | Value *IslExprBuilder::createOpSelect(__isl_take isl_ast_expr *Expr) { |
456 | 7 | assert(isl_ast_expr_get_op_type(Expr) == isl_ast_op_select && |
457 | 7 | "Unsupported unary isl ast expression"); |
458 | 7 | Value *LHS, *RHS, *Cond; |
459 | 7 | Type *MaxType = getType(Expr); |
460 | 7 | |
461 | 7 | Cond = create(isl_ast_expr_get_op_arg(Expr, 0)); |
462 | 7 | if (!Cond->getType()->isIntegerTy(1)) |
463 | 0 | Cond = Builder.CreateIsNotNull(Cond); |
464 | 7 | |
465 | 7 | LHS = create(isl_ast_expr_get_op_arg(Expr, 1)); |
466 | 7 | RHS = create(isl_ast_expr_get_op_arg(Expr, 2)); |
467 | 7 | |
468 | 7 | MaxType = getWidestType(MaxType, LHS->getType()); |
469 | 7 | MaxType = getWidestType(MaxType, RHS->getType()); |
470 | 7 | |
471 | 7 | if (MaxType != RHS->getType()) |
472 | 0 | RHS = Builder.CreateSExt(RHS, MaxType); |
473 | 7 | |
474 | 7 | if (MaxType != LHS->getType()) |
475 | 0 | LHS = Builder.CreateSExt(LHS, MaxType); |
476 | 7 | |
477 | 7 | // TODO: Do we want to truncate the result? |
478 | 7 | isl_ast_expr_free(Expr); |
479 | 7 | return Builder.CreateSelect(Cond, LHS, RHS); |
480 | 7 | } |
481 | | |
482 | 546 | Value *IslExprBuilder::createOpICmp(__isl_take isl_ast_expr *Expr) { |
483 | 546 | assert(isl_ast_expr_get_type(Expr) == isl_ast_expr_op && |
484 | 546 | "Expected an isl_ast_expr_op expression"); |
485 | 546 | |
486 | 546 | Value *LHS, *RHS, *Res; |
487 | 546 | |
488 | 546 | auto *Op0 = isl_ast_expr_get_op_arg(Expr, 0); |
489 | 546 | auto *Op1 = isl_ast_expr_get_op_arg(Expr, 1); |
490 | 546 | bool HasNonAddressOfOperand = |
491 | 546 | isl_ast_expr_get_type(Op0) != isl_ast_expr_op || |
492 | 546 | isl_ast_expr_get_type(Op1) != isl_ast_expr_op248 || |
493 | 546 | isl_ast_expr_get_op_type(Op0) != isl_ast_op_address_of200 || |
494 | 546 | isl_ast_expr_get_op_type(Op1) != isl_ast_op_address_of200 ; |
495 | 546 | |
496 | 546 | LHS = create(Op0); |
497 | 546 | RHS = create(Op1); |
498 | 546 | |
499 | 546 | auto *LHSTy = LHS->getType(); |
500 | 546 | auto *RHSTy = RHS->getType(); |
501 | 546 | bool IsPtrType = LHSTy->isPointerTy() || RHSTy->isPointerTy()346 ; |
502 | 546 | bool UseUnsignedCmp = IsPtrType && !HasNonAddressOfOperand200 ; |
503 | 546 | |
504 | 546 | auto *PtrAsIntTy = Builder.getIntNTy(DL.getPointerSizeInBits()); |
505 | 546 | if (LHSTy->isPointerTy()) |
506 | 200 | LHS = Builder.CreatePtrToInt(LHS, PtrAsIntTy); |
507 | 546 | if (RHSTy->isPointerTy()) |
508 | 200 | RHS = Builder.CreatePtrToInt(RHS, PtrAsIntTy); |
509 | 546 | |
510 | 546 | if (LHS->getType() != RHS->getType()) { |
511 | 207 | Type *MaxType = LHS->getType(); |
512 | 207 | MaxType = getWidestType(MaxType, RHS->getType()); |
513 | 207 | |
514 | 207 | if (MaxType != RHS->getType()) |
515 | 64 | RHS = Builder.CreateSExt(RHS, MaxType); |
516 | 207 | |
517 | 207 | if (MaxType != LHS->getType()) |
518 | 143 | LHS = Builder.CreateSExt(LHS, MaxType); |
519 | 207 | } |
520 | 546 | |
521 | 546 | isl_ast_op_type OpType = isl_ast_expr_get_op_type(Expr); |
522 | 546 | assert(OpType >= isl_ast_op_eq && OpType <= isl_ast_op_gt && |
523 | 546 | "Unsupported ICmp isl ast expression"); |
524 | 546 | assert(isl_ast_op_eq + 4 == isl_ast_op_gt && |
525 | 546 | "Isl ast op type interface changed"); |
526 | 546 | |
527 | 546 | CmpInst::Predicate Predicates[5][2] = { |
528 | 546 | {CmpInst::ICMP_EQ, CmpInst::ICMP_EQ}, |
529 | 546 | {CmpInst::ICMP_SLE, CmpInst::ICMP_ULE}, |
530 | 546 | {CmpInst::ICMP_SLT, CmpInst::ICMP_ULT}, |
531 | 546 | {CmpInst::ICMP_SGE, CmpInst::ICMP_UGE}, |
532 | 546 | {CmpInst::ICMP_SGT, CmpInst::ICMP_UGT}, |
533 | 546 | }; |
534 | 546 | |
535 | 546 | Res = Builder.CreateICmp(Predicates[OpType - isl_ast_op_eq][UseUnsignedCmp], |
536 | 546 | LHS, RHS); |
537 | 546 | |
538 | 546 | isl_ast_expr_free(Expr); |
539 | 546 | return Res; |
540 | 546 | } |
541 | | |
542 | 363 | Value *IslExprBuilder::createOpBoolean(__isl_take isl_ast_expr *Expr) { |
543 | 363 | assert(isl_ast_expr_get_type(Expr) == isl_ast_expr_op && |
544 | 363 | "Expected an isl_ast_expr_op expression"); |
545 | 363 | |
546 | 363 | Value *LHS, *RHS, *Res; |
547 | 363 | isl_ast_op_type OpType; |
548 | 363 | |
549 | 363 | OpType = isl_ast_expr_get_op_type(Expr); |
550 | 363 | |
551 | 363 | assert((OpType == isl_ast_op_and || OpType == isl_ast_op_or) && |
552 | 363 | "Unsupported isl_ast_op_type"); |
553 | 363 | |
554 | 363 | LHS = create(isl_ast_expr_get_op_arg(Expr, 0)); |
555 | 363 | RHS = create(isl_ast_expr_get_op_arg(Expr, 1)); |
556 | 363 | |
557 | 363 | // Even though the isl pretty printer prints the expressions as 'exp && exp' |
558 | 363 | // or 'exp || exp', we actually code generate the bitwise expressions |
559 | 363 | // 'exp & exp' or 'exp | exp'. This forces the evaluation of both branches, |
560 | 363 | // but it is, due to the use of i1 types, otherwise equivalent. The reason |
561 | 363 | // to go for bitwise operations is, that we assume the reduced control flow |
562 | 363 | // will outweigh the overhead introduced by evaluating unneeded expressions. |
563 | 363 | // The isl code generation currently does not take advantage of the fact that |
564 | 363 | // the expression after an '||' or '&&' is in some cases not evaluated. |
565 | 363 | // Evaluating it anyways does not cause any undefined behaviour. |
566 | 363 | // |
567 | 363 | // TODO: Document in isl itself, that the unconditionally evaluating the |
568 | 363 | // second part of '||' or '&&' expressions is safe. |
569 | 363 | if (!LHS->getType()->isIntegerTy(1)) |
570 | 97 | LHS = Builder.CreateIsNotNull(LHS); |
571 | 363 | if (!RHS->getType()->isIntegerTy(1)) |
572 | 1 | RHS = Builder.CreateIsNotNull(RHS); |
573 | 363 | |
574 | 363 | switch (OpType) { |
575 | 363 | default: |
576 | 0 | llvm_unreachable("Unsupported boolean expression"); |
577 | 363 | case isl_ast_op_and: |
578 | 210 | Res = Builder.CreateAnd(LHS, RHS); |
579 | 210 | break; |
580 | 363 | case isl_ast_op_or: |
581 | 153 | Res = Builder.CreateOr(LHS, RHS); |
582 | 153 | break; |
583 | 363 | } |
584 | 363 | |
585 | 363 | isl_ast_expr_free(Expr); |
586 | 363 | return Res; |
587 | 363 | } |
588 | | |
589 | | Value * |
590 | 0 | IslExprBuilder::createOpBooleanConditional(__isl_take isl_ast_expr *Expr) { |
591 | 0 | assert(isl_ast_expr_get_type(Expr) == isl_ast_expr_op && |
592 | 0 | "Expected an isl_ast_expr_op expression"); |
593 | 0 |
|
594 | 0 | Value *LHS, *RHS; |
595 | 0 | isl_ast_op_type OpType; |
596 | 0 |
|
597 | 0 | Function *F = Builder.GetInsertBlock()->getParent(); |
598 | 0 | LLVMContext &Context = F->getContext(); |
599 | 0 |
|
600 | 0 | OpType = isl_ast_expr_get_op_type(Expr); |
601 | 0 |
|
602 | 0 | assert((OpType == isl_ast_op_and_then || OpType == isl_ast_op_or_else) && |
603 | 0 | "Unsupported isl_ast_op_type"); |
604 | 0 |
|
605 | 0 | auto InsertBB = Builder.GetInsertBlock(); |
606 | 0 | auto InsertPoint = Builder.GetInsertPoint(); |
607 | 0 | auto NextBB = SplitBlock(InsertBB, &*InsertPoint, &DT, &LI); |
608 | 0 | BasicBlock *CondBB = BasicBlock::Create(Context, "polly.cond", F); |
609 | 0 | LI.changeLoopFor(CondBB, LI.getLoopFor(InsertBB)); |
610 | 0 | DT.addNewBlock(CondBB, InsertBB); |
611 | 0 |
|
612 | 0 | InsertBB->getTerminator()->eraseFromParent(); |
613 | 0 | Builder.SetInsertPoint(InsertBB); |
614 | 0 | auto BR = Builder.CreateCondBr(Builder.getTrue(), NextBB, CondBB); |
615 | 0 |
|
616 | 0 | Builder.SetInsertPoint(CondBB); |
617 | 0 | Builder.CreateBr(NextBB); |
618 | 0 |
|
619 | 0 | Builder.SetInsertPoint(InsertBB->getTerminator()); |
620 | 0 |
|
621 | 0 | LHS = create(isl_ast_expr_get_op_arg(Expr, 0)); |
622 | 0 | if (!LHS->getType()->isIntegerTy(1)) |
623 | 0 | LHS = Builder.CreateIsNotNull(LHS); |
624 | 0 | auto LeftBB = Builder.GetInsertBlock(); |
625 | 0 |
|
626 | 0 | if (OpType == isl_ast_op_and || OpType == isl_ast_op_and_then) |
627 | 0 | BR->setCondition(Builder.CreateNeg(LHS)); |
628 | 0 | else |
629 | 0 | BR->setCondition(LHS); |
630 | 0 |
|
631 | 0 | Builder.SetInsertPoint(CondBB->getTerminator()); |
632 | 0 | RHS = create(isl_ast_expr_get_op_arg(Expr, 1)); |
633 | 0 | if (!RHS->getType()->isIntegerTy(1)) |
634 | 0 | RHS = Builder.CreateIsNotNull(RHS); |
635 | 0 | auto RightBB = Builder.GetInsertBlock(); |
636 | 0 |
|
637 | 0 | Builder.SetInsertPoint(NextBB->getTerminator()); |
638 | 0 | auto PHI = Builder.CreatePHI(Builder.getInt1Ty(), 2); |
639 | 0 | PHI->addIncoming(OpType == isl_ast_op_and_then ? Builder.getFalse() |
640 | 0 | : Builder.getTrue(), |
641 | 0 | LeftBB); |
642 | 0 | PHI->addIncoming(RHS, RightBB); |
643 | 0 |
|
644 | 0 | isl_ast_expr_free(Expr); |
645 | 0 | return PHI; |
646 | 0 | } |
647 | | |
648 | 2.71k | Value *IslExprBuilder::createOp(__isl_take isl_ast_expr *Expr) { |
649 | 2.71k | assert(isl_ast_expr_get_type(Expr) == isl_ast_expr_op && |
650 | 2.71k | "Expression not of type isl_ast_expr_op"); |
651 | 2.71k | switch (isl_ast_expr_get_op_type(Expr)) { |
652 | 2.71k | case isl_ast_op_error: |
653 | 0 | case isl_ast_op_cond: |
654 | 0 | case isl_ast_op_call: |
655 | 0 | case isl_ast_op_member: |
656 | 0 | llvm_unreachable("Unsupported isl ast expression"); |
657 | 4 | case isl_ast_op_access: |
658 | 4 | return createOpAccess(Expr); |
659 | 54 | case isl_ast_op_max: |
660 | 54 | case isl_ast_op_min: |
661 | 54 | return createOpNAry(Expr); |
662 | 969 | case isl_ast_op_add: |
663 | 969 | case isl_ast_op_sub: |
664 | 969 | case isl_ast_op_mul: |
665 | 969 | case isl_ast_op_div: |
666 | 969 | case isl_ast_op_fdiv_q: // Round towards -infty |
667 | 969 | case isl_ast_op_pdiv_q: // Dividend is non-negative |
668 | 969 | case isl_ast_op_pdiv_r: // Dividend is non-negative |
669 | 969 | case isl_ast_op_zdiv_r: // Result only compared against zero |
670 | 969 | return createOpBin(Expr); |
671 | 969 | case isl_ast_op_minus: |
672 | 23 | return createOpUnary(Expr); |
673 | 969 | case isl_ast_op_select: |
674 | 7 | return createOpSelect(Expr); |
675 | 969 | case isl_ast_op_and: |
676 | 363 | case isl_ast_op_or: |
677 | 363 | return createOpBoolean(Expr); |
678 | 363 | case isl_ast_op_and_then: |
679 | 0 | case isl_ast_op_or_else: |
680 | 0 | return createOpBooleanConditional(Expr); |
681 | 546 | case isl_ast_op_eq: |
682 | 546 | case isl_ast_op_le: |
683 | 546 | case isl_ast_op_lt: |
684 | 546 | case isl_ast_op_ge: |
685 | 546 | case isl_ast_op_gt: |
686 | 546 | return createOpICmp(Expr); |
687 | 748 | case isl_ast_op_address_of: |
688 | 748 | return createOpAddressOf(Expr); |
689 | 0 | } |
690 | 0 | |
691 | 0 | llvm_unreachable("Unsupported isl_ast_expr_op kind."); |
692 | 0 | } |
693 | | |
694 | 748 | Value *IslExprBuilder::createOpAddressOf(__isl_take isl_ast_expr *Expr) { |
695 | 748 | assert(isl_ast_expr_get_type(Expr) == isl_ast_expr_op && |
696 | 748 | "Expected an isl_ast_expr_op expression."); |
697 | 748 | assert(isl_ast_expr_get_op_n_arg(Expr) == 1 && "Address of should be unary."); |
698 | 748 | |
699 | 748 | isl_ast_expr *Op = isl_ast_expr_get_op_arg(Expr, 0); |
700 | 748 | assert(isl_ast_expr_get_type(Op) == isl_ast_expr_op && |
701 | 748 | "Expected address of operator to be an isl_ast_expr_op expression."); |
702 | 748 | assert(isl_ast_expr_get_op_type(Op) == isl_ast_op_access && |
703 | 748 | "Expected address of operator to be an access expression."); |
704 | 748 | |
705 | 748 | Value *V = createAccessAddress(Op); |
706 | 748 | |
707 | 748 | isl_ast_expr_free(Expr); |
708 | 748 | |
709 | 748 | return V; |
710 | 748 | } |
711 | | |
712 | 1.75k | Value *IslExprBuilder::createId(__isl_take isl_ast_expr *Expr) { |
713 | 1.75k | assert(isl_ast_expr_get_type(Expr) == isl_ast_expr_id && |
714 | 1.75k | "Expression not of type isl_ast_expr_ident"); |
715 | 1.75k | |
716 | 1.75k | isl_id *Id; |
717 | 1.75k | Value *V; |
718 | 1.75k | |
719 | 1.75k | Id = isl_ast_expr_get_id(Expr); |
720 | 1.75k | |
721 | 1.75k | assert(IDToValue.count(Id) && "Identifier not found"); |
722 | 1.75k | |
723 | 1.75k | V = IDToValue[Id]; |
724 | 1.75k | if (!V) |
725 | 0 | V = UndefValue::get(getType(Expr)); |
726 | 1.75k | |
727 | 1.75k | if (V->getType()->isPointerTy()) |
728 | 24 | V = Builder.CreatePtrToInt(V, Builder.getIntNTy(DL.getPointerSizeInBits())); |
729 | 1.75k | |
730 | 1.75k | assert(V && "Unknown parameter id found"); |
731 | 1.75k | |
732 | 1.75k | isl_id_free(Id); |
733 | 1.75k | isl_ast_expr_free(Expr); |
734 | 1.75k | |
735 | 1.75k | return V; |
736 | 1.75k | } |
737 | | |
738 | 4.23k | IntegerType *IslExprBuilder::getType(__isl_keep isl_ast_expr *Expr) { |
739 | 4.23k | // XXX: We assume i64 is large enough. This is often true, but in general |
740 | 4.23k | // incorrect. Also, on 32bit architectures, it would be beneficial to |
741 | 4.23k | // use a smaller type. We can and should directly derive this information |
742 | 4.23k | // during code generation. |
743 | 4.23k | return IntegerType::get(Builder.getContext(), 64); |
744 | 4.23k | } |
745 | | |
746 | 2.94k | Value *IslExprBuilder::createInt(__isl_take isl_ast_expr *Expr) { |
747 | 2.94k | assert(isl_ast_expr_get_type(Expr) == isl_ast_expr_int && |
748 | 2.94k | "Expression not of type isl_ast_expr_int"); |
749 | 2.94k | isl_val *Val; |
750 | 2.94k | Value *V; |
751 | 2.94k | APInt APValue; |
752 | 2.94k | IntegerType *T; |
753 | 2.94k | |
754 | 2.94k | Val = isl_ast_expr_get_val(Expr); |
755 | 2.94k | APValue = APIntFromVal(Val); |
756 | 2.94k | |
757 | 2.94k | auto BitWidth = APValue.getBitWidth(); |
758 | 2.94k | if (BitWidth <= 64) |
759 | 2.94k | T = getType(Expr); |
760 | 0 | else |
761 | 0 | T = Builder.getIntNTy(BitWidth); |
762 | 2.94k | |
763 | 2.94k | APValue = APValue.sextOrSelf(T->getBitWidth()); |
764 | 2.94k | V = ConstantInt::get(T, APValue); |
765 | 2.94k | |
766 | 2.94k | isl_ast_expr_free(Expr); |
767 | 2.94k | return V; |
768 | 2.94k | } |
769 | | |
770 | 7.41k | Value *IslExprBuilder::create(__isl_take isl_ast_expr *Expr) { |
771 | 7.41k | switch (isl_ast_expr_get_type(Expr)) { |
772 | 7.41k | case isl_ast_expr_error: |
773 | 0 | llvm_unreachable("Code generation error"); |
774 | 7.41k | case isl_ast_expr_op: |
775 | 2.71k | return createOp(Expr); |
776 | 7.41k | case isl_ast_expr_id: |
777 | 1.75k | return createId(Expr); |
778 | 7.41k | case isl_ast_expr_int: |
779 | 2.94k | return createInt(Expr); |
780 | 0 | } |
781 | 0 | |
782 | 0 | llvm_unreachable("Unexpected enum value"); |
783 | 0 | } |