Coverage Report

Created: 2017-10-03 07:32

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