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