Coverage Report

Created: 2017-08-18 19:41

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