Coverage Report

Created: 2019-07-24 05:18

/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
}