Coverage Report

Created: 2019-02-20 07:29

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