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

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