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

source code of polly/lib/CodeGen/IslExprBuilder.cpp