Coverage Report

Created: 2017-06-23 12:40

/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/tools/polly/lib/CodeGen/IslNodeBuilder.cpp
Line
Count
Source (jump to first uncovered line)
1
//===------ IslNodeBuilder.cpp - Translate an isl AST into a LLVM-IR AST---===//
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
// This file contains the IslNodeBuilder, a class to translate an isl AST into
11
// a LLVM-IR AST.
12
//
13
//===----------------------------------------------------------------------===//
14
15
#include "polly/CodeGen/IslNodeBuilder.h"
16
#include "polly/CodeGen/BlockGenerators.h"
17
#include "polly/CodeGen/CodeGeneration.h"
18
#include "polly/CodeGen/IslAst.h"
19
#include "polly/CodeGen/IslExprBuilder.h"
20
#include "polly/CodeGen/LoopGenerators.h"
21
#include "polly/CodeGen/RuntimeDebugBuilder.h"
22
#include "polly/CodeGen/Utils.h"
23
#include "polly/Config/config.h"
24
#include "polly/DependenceInfo.h"
25
#include "polly/LinkAllPasses.h"
26
#include "polly/Options.h"
27
#include "polly/ScopInfo.h"
28
#include "polly/Support/GICHelper.h"
29
#include "polly/Support/SCEVValidator.h"
30
#include "polly/Support/ScopHelper.h"
31
#include "llvm/ADT/PostOrderIterator.h"
32
#include "llvm/ADT/SmallPtrSet.h"
33
#include "llvm/Analysis/LoopInfo.h"
34
#include "llvm/IR/DataLayout.h"
35
#include "llvm/IR/Module.h"
36
#include "llvm/IR/Verifier.h"
37
#include "llvm/Support/CommandLine.h"
38
#include "llvm/Support/Debug.h"
39
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
40
#include "isl/aff.h"
41
#include "isl/ast.h"
42
#include "isl/ast_build.h"
43
#include "isl/list.h"
44
#include "isl/map.h"
45
#include "isl/set.h"
46
#include "isl/union_map.h"
47
#include "isl/union_set.h"
48
49
using namespace polly;
50
using namespace llvm;
51
52
#define DEBUG_TYPE "polly-codegen"
53
54
STATISTIC(VersionedScops, "Number of SCoPs that required versioning.");
55
56
// The maximal number of dimensions we allow during invariant load construction.
57
// More complex access ranges will result in very high compile time and are also
58
// unlikely to result in good code. This value is very high and should only
59
// trigger for corner cases (e.g., the "dct_luma" function in h264, SPEC2006).
60
static int const MaxDimensionsInAccessRange = 9;
61
62
static cl::opt<bool> PollyGenerateRTCPrint(
63
    "polly-codegen-emit-rtc-print",
64
    cl::desc("Emit code that prints the runtime check result dynamically."),
65
    cl::Hidden, cl::init(false), cl::ZeroOrMore, cl::cat(PollyCategory));
66
67
// If this option is set we always use the isl AST generator to regenerate
68
// memory accesses. Without this option set we regenerate expressions using the
69
// original SCEV expressions and only generate new expressions in case the
70
// access relation has been changed and consequently must be regenerated.
71
static cl::opt<bool> PollyGenerateExpressions(
72
    "polly-codegen-generate-expressions",
73
    cl::desc("Generate AST expressions for unmodified and modified accesses"),
74
    cl::Hidden, cl::init(false), cl::ZeroOrMore, cl::cat(PollyCategory));
75
76
static cl::opt<int> PollyTargetFirstLevelCacheLineSize(
77
    "polly-target-first-level-cache-line-size",
78
    cl::desc("The size of the first level cache line size specified in bytes."),
79
    cl::Hidden, cl::init(64), cl::ZeroOrMore, cl::cat(PollyCategory));
80
81
__isl_give isl_ast_expr *
82
IslNodeBuilder::getUpperBound(__isl_keep isl_ast_node *For,
83
274
                              ICmpInst::Predicate &Predicate) {
84
274
  isl_id *UBID, *IteratorID;
85
274
  isl_ast_expr *Cond, *Iterator, *UB, *Arg0;
86
274
  isl_ast_op_type Type;
87
274
88
274
  Cond = isl_ast_node_for_get_cond(For);
89
274
  Iterator = isl_ast_node_for_get_iterator(For);
90
274
  isl_ast_expr_get_type(Cond);
91
274
  assert(isl_ast_expr_get_type(Cond) == isl_ast_expr_op &&
92
274
         "conditional expression is not an atomic upper bound");
93
274
94
274
  Type = isl_ast_expr_get_op_type(Cond);
95
274
96
274
  switch (Type) {
97
200
  case isl_ast_op_le:
98
200
    Predicate = ICmpInst::ICMP_SLE;
99
200
    break;
100
74
  case isl_ast_op_lt:
101
74
    Predicate = ICmpInst::ICMP_SLT;
102
74
    break;
103
0
  default:
104
0
    llvm_unreachable("Unexpected comparison type in loop condition");
105
274
  }
106
274
107
274
  Arg0 = isl_ast_expr_get_op_arg(Cond, 0);
108
274
109
274
  assert(isl_ast_expr_get_type(Arg0) == isl_ast_expr_id &&
110
274
         "conditional expression is not an atomic upper bound");
111
274
112
274
  UBID = isl_ast_expr_get_id(Arg0);
113
274
114
274
  assert(isl_ast_expr_get_type(Iterator) == isl_ast_expr_id &&
115
274
         "Could not get the iterator");
116
274
117
274
  IteratorID = isl_ast_expr_get_id(Iterator);
118
274
119
274
  assert(UBID == IteratorID &&
120
274
         "conditional expression is not an atomic upper bound");
121
274
122
274
  UB = isl_ast_expr_get_op_arg(Cond, 1);
123
274
124
274
  isl_ast_expr_free(Cond);
125
274
  isl_ast_expr_free(Iterator);
126
274
  isl_ast_expr_free(Arg0);
127
274
  isl_id_free(IteratorID);
128
274
  isl_id_free(UBID);
129
274
130
274
  return UB;
131
274
}
132
133
/// Return true if a return value of Predicate is true for the value represented
134
/// by passed isl_ast_expr_int.
135
static bool checkIslAstExprInt(__isl_take isl_ast_expr *Expr,
136
42
                               isl_bool (*Predicate)(__isl_keep isl_val *)) {
137
42
  if (
isl_ast_expr_get_type(Expr) != isl_ast_expr_int42
)
{0
138
0
    isl_ast_expr_free(Expr);
139
0
    return false;
140
0
  }
141
42
  auto ExprVal = isl_ast_expr_get_val(Expr);
142
42
  isl_ast_expr_free(Expr);
143
42
  if (
Predicate(ExprVal) != true42
)
{0
144
0
    isl_val_free(ExprVal);
145
0
    return false;
146
0
  }
147
42
  isl_val_free(ExprVal);
148
42
  return true;
149
42
}
150
151
22
int IslNodeBuilder::getNumberOfIterations(__isl_keep isl_ast_node *For) {
152
22
  assert(isl_ast_node_get_type(For) == isl_ast_node_for);
153
22
  auto Body = isl_ast_node_for_get_body(For);
154
22
155
22
  // First, check if we can actually handle this code.
156
22
  switch (isl_ast_node_get_type(Body)) {
157
20
  case isl_ast_node_user:
158
20
    break;
159
2
  case isl_ast_node_block: {
160
2
    isl_ast_node_list *List = isl_ast_node_block_get_children(Body);
161
4
    for (int i = 0; 
i < isl_ast_node_list_n_ast_node(List)4
;
++i2
)
{3
162
3
      isl_ast_node *Node = isl_ast_node_list_get_ast_node(List, i);
163
3
      int Type = isl_ast_node_get_type(Node);
164
3
      isl_ast_node_free(Node);
165
3
      if (
Type != isl_ast_node_user3
)
{1
166
1
        isl_ast_node_list_free(List);
167
1
        isl_ast_node_free(Body);
168
1
        return -1;
169
1
      }
170
3
    }
171
1
    isl_ast_node_list_free(List);
172
1
    break;
173
2
  }
174
0
  default:
175
0
    isl_ast_node_free(Body);
176
0
    return -1;
177
22
  }
178
21
  isl_ast_node_free(Body);
179
21
180
21
  auto Init = isl_ast_node_for_get_init(For);
181
21
  if (!checkIslAstExprInt(Init, isl_val_is_zero))
182
0
    return -1;
183
21
  auto Inc = isl_ast_node_for_get_inc(For);
184
21
  if (!checkIslAstExprInt(Inc, isl_val_is_one))
185
0
    return -1;
186
21
  CmpInst::Predicate Predicate;
187
21
  auto UB = getUpperBound(For, Predicate);
188
21
  if (
isl_ast_expr_get_type(UB) != isl_ast_expr_int21
)
{2
189
2
    isl_ast_expr_free(UB);
190
2
    return -1;
191
2
  }
192
19
  auto UpVal = isl_ast_expr_get_val(UB);
193
19
  isl_ast_expr_free(UB);
194
19
  int NumberIterations = isl_val_get_num_si(UpVal);
195
19
  isl_val_free(UpVal);
196
19
  if (NumberIterations < 0)
197
0
    return -1;
198
19
  
if (19
Predicate == CmpInst::ICMP_SLT19
)
199
0
    return NumberIterations;
200
19
  else
201
19
    return NumberIterations + 1;
202
19
}
203
204
/// Extract the values and SCEVs needed to generate code for a block.
205
static int findReferencesInBlock(struct SubtreeReferences &References,
206
26
                                 const ScopStmt *Stmt, const BasicBlock *BB) {
207
26
  for (const Instruction &Inst : *BB)
208
328
    
for (Value *SrcVal : Inst.operands()) 173
{328
209
328
      auto *Scope = References.LI.getLoopFor(BB);
210
328
      if (
canSynthesize(SrcVal, References.S, &References.SE, Scope)328
)
{232
211
232
        References.SCEVs.insert(References.SE.getSCEVAtScope(SrcVal, Scope));
212
232
        continue;
213
96
      } else 
if (Value *96
NewVal96
= References.GlobalMap.lookup(SrcVal))
214
9
        References.Values.insert(NewVal);
215
328
    }
216
26
  return 0;
217
26
}
218
219
isl_stat addReferencesFromStmt(const ScopStmt *Stmt, void *UserPtr,
220
26
                               bool CreateScalarRefs) {
221
26
  auto &References = *static_cast<struct SubtreeReferences *>(UserPtr);
222
26
223
26
  if (Stmt->isBlockStmt())
224
26
    findReferencesInBlock(References, Stmt, Stmt->getBasicBlock());
225
0
  else {
226
0
    assert(Stmt->isRegionStmt() &&
227
0
           "Stmt was neither block nor region statement");
228
0
    for (const BasicBlock *BB : Stmt->getRegion()->blocks())
229
0
      findReferencesInBlock(References, Stmt, BB);
230
0
  }
231
26
232
40
  for (auto &Access : *Stmt) {
233
40
    if (
Access->isArrayKind()40
)
{38
234
38
      auto *BasePtr = Access->getScopArrayInfo()->getBasePtr();
235
38
      if (Instruction *OpInst = dyn_cast<Instruction>(BasePtr))
236
5
        
if (5
Stmt->getParent()->contains(OpInst)5
)
237
4
          continue;
238
38
239
34
      References.Values.insert(BasePtr);
240
34
      continue;
241
38
    }
242
40
243
2
    
if (2
CreateScalarRefs2
)
244
2
      References.Values.insert(References.BlockGen.getOrCreateAlloca(*Access));
245
2
  }
246
26
247
26
  return isl_stat_ok;
248
26
}
249
250
/// Extract the out-of-scop values and SCEVs referenced from a set describing
251
/// a ScopStmt.
252
///
253
/// This includes the SCEVUnknowns referenced by the SCEVs used in the
254
/// statement and the base pointers of the memory accesses. For scalar
255
/// statements we force the generation of alloca memory locations and list
256
/// these locations in the set of out-of-scop values as well.
257
///
258
/// @param Set     A set which references the ScopStmt we are interested in.
259
/// @param UserPtr A void pointer that can be casted to a SubtreeReferences
260
///                structure.
261
static isl_stat addReferencesFromStmtSet(__isl_take isl_set *Set,
262
26
                                         void *UserPtr) {
263
26
  isl_id *Id = isl_set_get_tuple_id(Set);
264
26
  auto *Stmt = static_cast<const ScopStmt *>(isl_id_get_user(Id));
265
26
  isl_id_free(Id);
266
26
  isl_set_free(Set);
267
26
  return addReferencesFromStmt(Stmt, UserPtr);
268
26
}
269
270
/// Extract the out-of-scop values and SCEVs referenced from a union set
271
/// referencing multiple ScopStmts.
272
///
273
/// This includes the SCEVUnknowns referenced by the SCEVs used in the
274
/// statement and the base pointers of the memory accesses. For scalar
275
/// statements we force the generation of alloca memory locations and list
276
/// these locations in the set of out-of-scop values as well.
277
///
278
/// @param USet       A union set referencing the ScopStmts we are interested
279
///                   in.
280
/// @param References The SubtreeReferences data structure through which
281
///                   results are returned and further information is
282
///                   provided.
283
static void
284
addReferencesFromStmtUnionSet(isl_union_set *USet,
285
26
                              struct SubtreeReferences &References) {
286
26
  isl_union_set_foreach_set(USet, addReferencesFromStmtSet, &References);
287
26
  isl_union_set_free(USet);
288
26
}
289
290
__isl_give isl_union_map *
291
45
IslNodeBuilder::getScheduleForAstNode(__isl_keep isl_ast_node *For) {
292
45
  return IslAstInfo::getSchedule(For);
293
45
}
294
295
void IslNodeBuilder::getReferencesInSubtree(__isl_keep isl_ast_node *For,
296
                                            SetVector<Value *> &Values,
297
26
                                            SetVector<const Loop *> &Loops) {
298
26
299
26
  SetVector<const SCEV *> SCEVs;
300
26
  struct SubtreeReferences References = {
301
26
      LI, SE, S, ValueMap, Values, SCEVs, getBlockGenerator()};
302
26
303
26
  for (const auto &I : IDToValue)
304
19
    Values.insert(I.second);
305
26
306
26
  for (const auto &I : OutsideLoopIterations)
307
2
    Values.insert(cast<SCEVUnknown>(I.second)->getValue());
308
26
309
26
  isl_union_set *Schedule = isl_union_map_domain(getScheduleForAstNode(For));
310
26
  addReferencesFromStmtUnionSet(Schedule, References);
311
26
312
172
  for (const SCEV *Expr : SCEVs) {
313
172
    findValues(Expr, SE, Values);
314
172
    findLoops(Expr, Loops);
315
172
  }
316
26
317
64
  Values.remove_if([](const Value *V) { return isa<GlobalValue>(V); });
318
26
319
26
  /// Remove loops that contain the scop or that are part of the scop, as they
320
26
  /// are considered local. This leaves only loops that are before the scop, but
321
26
  /// do not contain the scop itself.
322
38
  Loops.remove_if([this](const Loop *L) {
323
3
    return S.contains(L) || L->contains(S.getEntry());
324
38
  });
325
26
}
326
327
26
void IslNodeBuilder::updateValues(ValueMapT &NewValues) {
328
26
  SmallPtrSet<Value *, 5> Inserted;
329
26
330
19
  for (const auto &I : IDToValue) {
331
19
    IDToValue[I.first] = NewValues[I.second];
332
19
    Inserted.insert(I.second);
333
19
  }
334
26
335
58
  for (const auto &I : NewValues) {
336
58
    if (Inserted.count(I.first))
337
0
      continue;
338
58
339
58
    ValueMap[I.first] = I.second;
340
58
  }
341
26
}
342
343
void IslNodeBuilder::createUserVector(__isl_take isl_ast_node *User,
344
                                      std::vector<Value *> &IVS,
345
                                      __isl_take isl_id *IteratorID,
346
20
                                      __isl_take isl_union_map *Schedule) {
347
20
  isl_ast_expr *Expr = isl_ast_node_user_get_expr(User);
348
20
  isl_ast_expr *StmtExpr = isl_ast_expr_get_op_arg(Expr, 0);
349
20
  isl_id *Id = isl_ast_expr_get_id(StmtExpr);
350
20
  isl_ast_expr_free(StmtExpr);
351
20
  ScopStmt *Stmt = (ScopStmt *)isl_id_get_user(Id);
352
20
  std::vector<LoopToScevMapT> VLTS(IVS.size());
353
20
354
20
  isl_union_set *Domain = isl_union_set_from_set(Stmt->getDomain());
355
20
  Schedule = isl_union_map_intersect_domain(Schedule, Domain);
356
20
  isl_map *S = isl_map_from_union_map(Schedule);
357
20
358
20
  auto *NewAccesses = createNewAccesses(Stmt, User);
359
20
  createSubstitutionsVector(Expr, Stmt, VLTS, IVS, IteratorID);
360
20
  VectorBlockGenerator::generate(BlockGen, *Stmt, VLTS, S, NewAccesses);
361
20
  isl_id_to_ast_expr_free(NewAccesses);
362
20
  isl_map_free(S);
363
20
  isl_id_free(Id);
364
20
  isl_ast_node_free(User);
365
20
}
366
367
15
void IslNodeBuilder::createMark(__isl_take isl_ast_node *Node) {
368
15
  auto *Id = isl_ast_node_mark_get_id(Node);
369
15
  auto Child = isl_ast_node_mark_get_node(Node);
370
15
  isl_ast_node_free(Node);
371
15
  // If a child node of a 'SIMD mark' is a loop that has a single iteration,
372
15
  // it will be optimized away and we should skip it.
373
15
  if (!strcmp(isl_id_get_name(Id), "SIMD") &&
374
2
      
isl_ast_node_get_type(Child) == isl_ast_node_for2
)
{2
375
2
    bool Vector = PollyVectorizerChoice == VECTORIZER_POLLY;
376
2
    int VectorWidth = getNumberOfIterations(Child);
377
2
    if (
Vector && 2
1 < VectorWidth2
&&
VectorWidth <= 162
)
378
2
      createForVector(Child, VectorWidth);
379
2
    else
380
0
      createForSequential(Child, true);
381
2
    isl_id_free(Id);
382
2
    return;
383
2
  }
384
13
  
if (13
!strcmp(isl_id_get_name(Id), "Inter iteration alias-free")13
)
{1
385
1
    auto *BasePtr = static_cast<Value *>(isl_id_get_user(Id));
386
1
    Annotator.addInterIterationAliasFreeBasePtr(BasePtr);
387
1
  }
388
13
  create(Child);
389
13
  isl_id_free(Id);
390
13
}
391
392
void IslNodeBuilder::createForVector(__isl_take isl_ast_node *For,
393
19
                                     int VectorWidth) {
394
19
  isl_ast_node *Body = isl_ast_node_for_get_body(For);
395
19
  isl_ast_expr *Init = isl_ast_node_for_get_init(For);
396
19
  isl_ast_expr *Inc = isl_ast_node_for_get_inc(For);
397
19
  isl_ast_expr *Iterator = isl_ast_node_for_get_iterator(For);
398
19
  isl_id *IteratorID = isl_ast_expr_get_id(Iterator);
399
19
400
19
  Value *ValueLB = ExprBuilder.create(Init);
401
19
  Value *ValueInc = ExprBuilder.create(Inc);
402
19
403
19
  Type *MaxType = ExprBuilder.getType(Iterator);
404
19
  MaxType = ExprBuilder.getWidestType(MaxType, ValueLB->getType());
405
19
  MaxType = ExprBuilder.getWidestType(MaxType, ValueInc->getType());
406
19
407
19
  if (MaxType != ValueLB->getType())
408
0
    ValueLB = Builder.CreateSExt(ValueLB, MaxType);
409
19
  if (MaxType != ValueInc->getType())
410
0
    ValueInc = Builder.CreateSExt(ValueInc, MaxType);
411
19
412
19
  std::vector<Value *> IVS(VectorWidth);
413
19
  IVS[0] = ValueLB;
414
19
415
119
  for (int i = 1; 
i < VectorWidth119
;
i++100
)
416
100
    IVS[i] = Builder.CreateAdd(IVS[i - 1], ValueInc, "p_vector_iv");
417
19
418
19
  isl_union_map *Schedule = getScheduleForAstNode(For);
419
19
  assert(Schedule && "For statement annotation does not contain its schedule");
420
19
421
19
  IDToValue[IteratorID] = ValueLB;
422
19
423
19
  switch (isl_ast_node_get_type(Body)) {
424
18
  case isl_ast_node_user:
425
18
    createUserVector(Body, IVS, isl_id_copy(IteratorID),
426
18
                     isl_union_map_copy(Schedule));
427
18
    break;
428
1
  case isl_ast_node_block: {
429
1
    isl_ast_node_list *List = isl_ast_node_block_get_children(Body);
430
1
431
3
    for (int i = 0; 
i < isl_ast_node_list_n_ast_node(List)3
;
++i2
)
432
2
      createUserVector(isl_ast_node_list_get_ast_node(List, i), IVS,
433
2
                       isl_id_copy(IteratorID), isl_union_map_copy(Schedule));
434
1
435
1
    isl_ast_node_free(Body);
436
1
    isl_ast_node_list_free(List);
437
1
    break;
438
18
  }
439
0
  default:
440
0
    isl_ast_node_dump(Body);
441
0
    llvm_unreachable("Unhandled isl_ast_node in vectorizer");
442
19
  }
443
19
444
19
  IDToValue.erase(IDToValue.find(IteratorID));
445
19
  isl_id_free(IteratorID);
446
19
  isl_union_map_free(Schedule);
447
19
448
19
  isl_ast_node_free(For);
449
19
  isl_ast_expr_free(Iterator);
450
19
}
451
452
void IslNodeBuilder::createForSequential(__isl_take isl_ast_node *For,
453
227
                                         bool KnownParallel) {
454
227
  isl_ast_node *Body;
455
227
  isl_ast_expr *Init, *Inc, *Iterator, *UB;
456
227
  isl_id *IteratorID;
457
227
  Value *ValueLB, *ValueUB, *ValueInc;
458
227
  Type *MaxType;
459
227
  BasicBlock *ExitBlock;
460
227
  Value *IV;
461
227
  CmpInst::Predicate Predicate;
462
227
  bool Parallel;
463
227
464
227
  Parallel = KnownParallel || (IslAstInfo::isParallel(For) &&
465
16
                               !IslAstInfo::isReductionParallel(For));
466
227
467
227
  Body = isl_ast_node_for_get_body(For);
468
227
469
227
  // isl_ast_node_for_is_degenerate(For)
470
227
  //
471
227
  // TODO: For degenerated loops we could generate a plain assignment.
472
227
  //       However, for now we just reuse the logic for normal loops, which will
473
227
  //       create a loop with a single iteration.
474
227
475
227
  Init = isl_ast_node_for_get_init(For);
476
227
  Inc = isl_ast_node_for_get_inc(For);
477
227
  Iterator = isl_ast_node_for_get_iterator(For);
478
227
  IteratorID = isl_ast_expr_get_id(Iterator);
479
227
  UB = getUpperBound(For, Predicate);
480
227
481
227
  ValueLB = ExprBuilder.create(Init);
482
227
  ValueUB = ExprBuilder.create(UB);
483
227
  ValueInc = ExprBuilder.create(Inc);
484
227
485
227
  MaxType = ExprBuilder.getType(Iterator);
486
227
  MaxType = ExprBuilder.getWidestType(MaxType, ValueLB->getType());
487
227
  MaxType = ExprBuilder.getWidestType(MaxType, ValueUB->getType());
488
227
  MaxType = ExprBuilder.getWidestType(MaxType, ValueInc->getType());
489
227
490
227
  if (MaxType != ValueLB->getType())
491
0
    ValueLB = Builder.CreateSExt(ValueLB, MaxType);
492
227
  if (MaxType != ValueUB->getType())
493
29
    ValueUB = Builder.CreateSExt(ValueUB, MaxType);
494
227
  if (MaxType != ValueInc->getType())
495
0
    ValueInc = Builder.CreateSExt(ValueInc, MaxType);
496
227
497
227
  // If we can show that LB <Predicate> UB holds at least once, we can
498
227
  // omit the GuardBB in front of the loop.
499
227
  bool UseGuardBB =
500
227
      !SE.isKnownPredicate(Predicate, SE.getSCEV(ValueLB), SE.getSCEV(ValueUB));
501
227
  IV = createLoop(ValueLB, ValueUB, ValueInc, Builder, LI, DT, ExitBlock,
502
227
                  Predicate, &Annotator, Parallel, UseGuardBB);
503
227
  IDToValue[IteratorID] = IV;
504
227
505
227
  create(Body);
506
227
507
227
  Annotator.popLoop(Parallel);
508
227
509
227
  IDToValue.erase(IDToValue.find(IteratorID));
510
227
511
227
  Builder.SetInsertPoint(&ExitBlock->front());
512
227
513
227
  isl_ast_node_free(For);
514
227
  isl_ast_expr_free(Iterator);
515
227
  isl_id_free(IteratorID);
516
227
}
517
518
/// Remove the BBs contained in a (sub)function from the dominator tree.
519
///
520
/// This function removes the basic blocks that are part of a subfunction from
521
/// the dominator tree. Specifically, when generating code it may happen that at
522
/// some point the code generation continues in a new sub-function (e.g., when
523
/// generating OpenMP code). The basic blocks that are created in this
524
/// sub-function are then still part of the dominator tree of the original
525
/// function, such that the dominator tree reaches over function boundaries.
526
/// This is not only incorrect, but also causes crashes. This function now
527
/// removes from the dominator tree all basic blocks that are dominated (and
528
/// consequently reachable) from the entry block of this (sub)function.
529
///
530
/// FIXME: A LLVM (function or region) pass should not touch anything outside of
531
/// the function/region it runs on. Hence, the pure need for this function shows
532
/// that we do not comply to this rule. At the moment, this does not cause any
533
/// issues, but we should be aware that such issues may appear. Unfortunately
534
/// the current LLVM pass infrastructure does not allow to make Polly a module
535
/// or call-graph pass to solve this issue, as such a pass would not have access
536
/// to the per-function analyses passes needed by Polly. A future pass manager
537
/// infrastructure is supposed to enable such kind of access possibly allowing
538
/// us to create a cleaner solution here.
539
///
540
/// FIXME: Instead of adding the dominance information and then dropping it
541
/// later on, we should try to just not add it in the first place. This requires
542
/// some careful testing to make sure this does not break in interaction with
543
/// the SCEVBuilder and SplitBlock which may rely on the dominator tree or
544
/// which may try to update it.
545
///
546
/// @param F The function which contains the BBs to removed.
547
/// @param DT The dominator tree from which to remove the BBs.
548
26
static void removeSubFuncFromDomTree(Function *F, DominatorTree &DT) {
549
26
  DomTreeNode *N = DT.getNode(&F->getEntryBlock());
550
26
  std::vector<BasicBlock *> Nodes;
551
26
552
26
  // We can only remove an element from the dominator tree, if all its children
553
26
  // have been removed. To ensure this we obtain the list of nodes to remove
554
26
  // using a post-order tree traversal.
555
269
  for (po_iterator<DomTreeNode *> I = po_begin(N), E = po_end(N); 
I != E269
;
++I243
)
556
243
    Nodes.push_back(I->getBlock());
557
26
558
26
  for (BasicBlock *BB : Nodes)
559
243
    DT.eraseNode(BB);
560
26
}
561
562
26
void IslNodeBuilder::createForParallel(__isl_take isl_ast_node *For) {
563
26
  isl_ast_node *Body;
564
26
  isl_ast_expr *Init, *Inc, *Iterator, *UB;
565
26
  isl_id *IteratorID;
566
26
  Value *ValueLB, *ValueUB, *ValueInc;
567
26
  Type *MaxType;
568
26
  Value *IV;
569
26
  CmpInst::Predicate Predicate;
570
26
571
26
  // The preamble of parallel code interacts different than normal code with
572
26
  // e.g., scalar initialization. Therefore, we ensure the parallel code is
573
26
  // separated from the last basic block.
574
26
  BasicBlock *ParBB = SplitBlock(Builder.GetInsertBlock(),
575
26
                                 &*Builder.GetInsertPoint(), &DT, &LI);
576
26
  ParBB->setName("polly.parallel.for");
577
26
  Builder.SetInsertPoint(&ParBB->front());
578
26
579
26
  Body = isl_ast_node_for_get_body(For);
580
26
  Init = isl_ast_node_for_get_init(For);
581
26
  Inc = isl_ast_node_for_get_inc(For);
582
26
  Iterator = isl_ast_node_for_get_iterator(For);
583
26
  IteratorID = isl_ast_expr_get_id(Iterator);
584
26
  UB = getUpperBound(For, Predicate);
585
26
586
26
  ValueLB = ExprBuilder.create(Init);
587
26
  ValueUB = ExprBuilder.create(UB);
588
26
  ValueInc = ExprBuilder.create(Inc);
589
26
590
26
  // OpenMP always uses SLE. In case the isl generated AST uses a SLT
591
26
  // expression, we need to adjust the loop bound by one.
592
26
  if (Predicate == CmpInst::ICMP_SLT)
593
8
    ValueUB = Builder.CreateAdd(
594
8
        ValueUB, Builder.CreateSExt(Builder.getTrue(), ValueUB->getType()));
595
26
596
26
  MaxType = ExprBuilder.getType(Iterator);
597
26
  MaxType = ExprBuilder.getWidestType(MaxType, ValueLB->getType());
598
26
  MaxType = ExprBuilder.getWidestType(MaxType, ValueUB->getType());
599
26
  MaxType = ExprBuilder.getWidestType(MaxType, ValueInc->getType());
600
26
601
26
  if (MaxType != ValueLB->getType())
602
0
    ValueLB = Builder.CreateSExt(ValueLB, MaxType);
603
26
  if (MaxType != ValueUB->getType())
604
3
    ValueUB = Builder.CreateSExt(ValueUB, MaxType);
605
26
  if (MaxType != ValueInc->getType())
606
0
    ValueInc = Builder.CreateSExt(ValueInc, MaxType);
607
26
608
26
  BasicBlock::iterator LoopBody;
609
26
610
26
  SetVector<Value *> SubtreeValues;
611
26
  SetVector<const Loop *> Loops;
612
26
613
26
  getReferencesInSubtree(For, SubtreeValues, Loops);
614
26
615
26
  // Create for all loops we depend on values that contain the current loop
616
26
  // iteration. These values are necessary to generate code for SCEVs that
617
26
  // depend on such loops. As a result we need to pass them to the subfunction.
618
1
  for (const Loop *L : Loops) {
619
1
    const SCEV *OuterLIV = SE.getAddRecExpr(SE.getUnknown(Builder.getInt64(0)),
620
1
                                            SE.getUnknown(Builder.getInt64(1)),
621
1
                                            L, SCEV::FlagAnyWrap);
622
1
    Value *V = generateSCEV(OuterLIV);
623
1
    OutsideLoopIterations[L] = SE.getUnknown(V);
624
1
    SubtreeValues.insert(V);
625
1
  }
626
26
627
26
  ValueMapT NewValues;
628
26
  ParallelLoopGenerator ParallelLoopGen(Builder, LI, DT, DL);
629
26
630
26
  IV = ParallelLoopGen.createParallelLoop(ValueLB, ValueUB, ValueInc,
631
26
                                          SubtreeValues, NewValues, &LoopBody);
632
26
  BasicBlock::iterator AfterLoop = Builder.GetInsertPoint();
633
26
  Builder.SetInsertPoint(&*LoopBody);
634
26
635
26
  // Remember the parallel subfunction
636
26
  ParallelSubfunctions.push_back(LoopBody->getFunction());
637
26
638
26
  // Save the current values.
639
26
  auto ValueMapCopy = ValueMap;
640
26
  IslExprBuilder::IDToValueTy IDToValueCopy = IDToValue;
641
26
642
26
  updateValues(NewValues);
643
26
  IDToValue[IteratorID] = IV;
644
26
645
26
  ValueMapT NewValuesReverse;
646
26
647
26
  for (auto P : NewValues)
648
58
    NewValuesReverse[P.second] = P.first;
649
26
650
26
  Annotator.addAlternativeAliasBases(NewValuesReverse);
651
26
652
26
  create(Body);
653
26
654
26
  Annotator.resetAlternativeAliasBases();
655
26
  // Restore the original values.
656
26
  ValueMap = ValueMapCopy;
657
26
  IDToValue = IDToValueCopy;
658
26
659
26
  Builder.SetInsertPoint(&*AfterLoop);
660
26
  removeSubFuncFromDomTree((*LoopBody).getParent()->getParent(), DT);
661
26
662
26
  for (const Loop *L : Loops)
663
1
    OutsideLoopIterations.erase(L);
664
26
665
26
  isl_ast_node_free(For);
666
26
  isl_ast_expr_free(Iterator);
667
26
  isl_id_free(IteratorID);
668
26
}
669
670
/// Return whether any of @p Node's statements contain partial accesses.
671
///
672
/// Partial accesses are not supported by Polly's vector code generator.
673
17
static bool hasPartialAccesses(__isl_take isl_ast_node *Node) {
674
17
  return isl_ast_node_foreach_descendant_top_down(
675
17
             Node,
676
36
             [](isl_ast_node *Node, void *User) -> isl_bool {
677
36
               if (isl_ast_node_get_type(Node) != isl_ast_node_user)
678
18
                 return isl_bool_true;
679
36
680
18
               isl::ast_expr Expr = give(isl_ast_node_user_get_expr(Node));
681
18
               isl::ast_expr StmtExpr =
682
18
                   give(isl_ast_expr_get_op_arg(Expr.keep(), 0));
683
18
               isl::id Id = give(isl_ast_expr_get_id(StmtExpr.keep()));
684
18
685
18
               ScopStmt *Stmt =
686
18
                   static_cast<ScopStmt *>(isl_id_get_user(Id.keep()));
687
18
               isl::set StmtDom = give(Stmt->getDomain());
688
27
               for (auto *MA : *Stmt) {
689
27
                 if (MA->isLatestPartialAccess())
690
0
                   return isl_bool_error;
691
27
               }
692
18
               return isl_bool_true;
693
18
             },
694
17
             nullptr) == isl_stat_error;
695
17
}
696
697
270
void IslNodeBuilder::createFor(__isl_take isl_ast_node *For) {
698
270
  bool Vector = PollyVectorizerChoice == VECTORIZER_POLLY;
699
270
700
270
  if (
Vector && 270
IslAstInfo::isInnermostParallel(For)27
&&
701
20
      
!IslAstInfo::isReductionParallel(For)20
)
{20
702
20
    int VectorWidth = getNumberOfIterations(For);
703
20
    if (
1 < VectorWidth && 20
VectorWidth <= 1617
&&
!hasPartialAccesses(For)17
)
{17
704
17
      createForVector(For, VectorWidth);
705
17
      return;
706
17
    }
707
20
  }
708
270
709
253
  
if (253
IslAstInfo::isExecutedInParallel(For)253
)
{26
710
26
    createForParallel(For);
711
26
    return;
712
26
  }
713
227
  createForSequential(For, false);
714
227
}
715
716
59
void IslNodeBuilder::createIf(__isl_take isl_ast_node *If) {
717
59
  isl_ast_expr *Cond = isl_ast_node_if_get_cond(If);
718
59
719
59
  Function *F = Builder.GetInsertBlock()->getParent();
720
59
  LLVMContext &Context = F->getContext();
721
59
722
59
  BasicBlock *CondBB = SplitBlock(Builder.GetInsertBlock(),
723
59
                                  &*Builder.GetInsertPoint(), &DT, &LI);
724
59
  CondBB->setName("polly.cond");
725
59
  BasicBlock *MergeBB = SplitBlock(CondBB, &CondBB->front(), &DT, &LI);
726
59
  MergeBB->setName("polly.merge");
727
59
  BasicBlock *ThenBB = BasicBlock::Create(Context, "polly.then", F);
728
59
  BasicBlock *ElseBB = BasicBlock::Create(Context, "polly.else", F);
729
59
730
59
  DT.addNewBlock(ThenBB, CondBB);
731
59
  DT.addNewBlock(ElseBB, CondBB);
732
59
  DT.changeImmediateDominator(MergeBB, CondBB);
733
59
734
59
  Loop *L = LI.getLoopFor(CondBB);
735
59
  if (
L59
)
{30
736
30
    L->addBasicBlockToLoop(ThenBB, LI);
737
30
    L->addBasicBlockToLoop(ElseBB, LI);
738
30
  }
739
59
740
59
  CondBB->getTerminator()->eraseFromParent();
741
59
742
59
  Builder.SetInsertPoint(CondBB);
743
59
  Value *Predicate = ExprBuilder.create(Cond);
744
59
  Builder.CreateCondBr(Predicate, ThenBB, ElseBB);
745
59
  Builder.SetInsertPoint(ThenBB);
746
59
  Builder.CreateBr(MergeBB);
747
59
  Builder.SetInsertPoint(ElseBB);
748
59
  Builder.CreateBr(MergeBB);
749
59
  Builder.SetInsertPoint(&ThenBB->front());
750
59
751
59
  create(isl_ast_node_if_get_then(If));
752
59
753
59
  Builder.SetInsertPoint(&ElseBB->front());
754
59
755
59
  if (isl_ast_node_if_has_else(If))
756
10
    create(isl_ast_node_if_get_else(If));
757
59
758
59
  Builder.SetInsertPoint(&MergeBB->front());
759
59
760
59
  isl_ast_node_free(If);
761
59
}
762
763
__isl_give isl_id_to_ast_expr *
764
IslNodeBuilder::createNewAccesses(ScopStmt *Stmt,
765
396
                                  __isl_keep isl_ast_node *Node) {
766
396
  isl_id_to_ast_expr *NewAccesses =
767
396
      isl_id_to_ast_expr_alloc(Stmt->getParent()->getIslCtx(), 0);
768
396
769
396
  auto *Build = IslAstInfo::getBuild(Node);
770
396
  assert(Build && "Could not obtain isl_ast_build from user node");
771
396
  Stmt->setAstBuild(Build);
772
396
773
795
  for (auto *MA : *Stmt) {
774
795
    if (
!MA->hasNewAccessRelation()795
)
{728
775
728
      if (
PollyGenerateExpressions728
)
{2
776
2
        if (!MA->isAffine())
777
0
          continue;
778
2
        
if (2
MA->getLatestScopArrayInfo()->getBasePtrOriginSAI()2
)
779
0
          continue;
780
2
781
2
        auto *BasePtr =
782
2
            dyn_cast<Instruction>(MA->getLatestScopArrayInfo()->getBasePtr());
783
2
        if (
BasePtr && 2
Stmt->getParent()->getRegion().contains(BasePtr)0
)
784
0
          continue;
785
726
      } else {
786
726
        continue;
787
726
      }
788
728
    }
789
69
    assert(MA->isAffine() &&
790
69
           "Only affine memory accesses can be code generated");
791
69
792
69
    auto Schedule = isl_ast_build_get_schedule(Build);
793
69
794
69
#ifndef NDEBUG
795
    if (MA->isRead()) {
796
      auto Dom = Stmt->getDomain();
797
      auto SchedDom = isl_set_from_union_set(
798
          isl_union_map_domain(isl_union_map_copy(Schedule)));
799
      auto AccDom = isl_map_domain(MA->getAccessRelation());
800
      Dom = isl_set_intersect_params(Dom, Stmt->getParent()->getContext());
801
      SchedDom =
802
          isl_set_intersect_params(SchedDom, Stmt->getParent()->getContext());
803
      assert(isl_set_is_subset(SchedDom, AccDom) &&
804
             "Access relation not defined on full schedule domain");
805
      assert(isl_set_is_subset(Dom, AccDom) &&
806
             "Access relation not defined on full domain");
807
      isl_set_free(AccDom);
808
      isl_set_free(SchedDom);
809
      isl_set_free(Dom);
810
    }
811
#endif
812
69
813
69
    auto PWAccRel = MA->applyScheduleToAccessRelation(Schedule);
814
69
815
69
    // isl cannot generate an index expression for access-nothing accesses.
816
69
    isl::set AccDomain =
817
69
        give(isl_pw_multi_aff_domain(isl_pw_multi_aff_copy(PWAccRel)));
818
69
    if (
isl_set_is_empty(AccDomain.keep()) == isl_bool_true69
)
{1
819
1
      isl_pw_multi_aff_free(PWAccRel);
820
1
      continue;
821
1
    }
822
69
823
68
    auto AccessExpr = isl_ast_build_access_from_pw_multi_aff(Build, PWAccRel);
824
68
    NewAccesses = isl_id_to_ast_expr_set(NewAccesses, MA->getId(), AccessExpr);
825
68
  }
826
396
827
396
  return NewAccesses;
828
396
}
829
830
void IslNodeBuilder::createSubstitutions(__isl_take isl_ast_expr *Expr,
831
497
                                         ScopStmt *Stmt, LoopToScevMapT &LTS) {
832
497
  assert(isl_ast_expr_get_type(Expr) == isl_ast_expr_op &&
833
497
         "Expression of type 'op' expected");
834
497
  assert(isl_ast_expr_get_op_type(Expr) == isl_ast_op_call &&
835
497
         "Operation of type 'call' expected");
836
983
  for (int i = 0; 
i < isl_ast_expr_get_op_n_arg(Expr) - 1983
;
++i486
)
{486
837
486
    isl_ast_expr *SubExpr;
838
486
    Value *V;
839
486
840
486
    SubExpr = isl_ast_expr_get_op_arg(Expr, i + 1);
841
486
    V = ExprBuilder.create(SubExpr);
842
486
    ScalarEvolution *SE = Stmt->getParent()->getSE();
843
486
    LTS[Stmt->getLoopForDimension(i)] = SE->getUnknown(V);
844
486
  }
845
497
846
497
  isl_ast_expr_free(Expr);
847
497
}
848
849
void IslNodeBuilder::createSubstitutionsVector(
850
    __isl_take isl_ast_expr *Expr, ScopStmt *Stmt,
851
    std::vector<LoopToScevMapT> &VLTS, std::vector<Value *> &IVS,
852
20
    __isl_take isl_id *IteratorID) {
853
20
  int i = 0;
854
20
855
20
  Value *OldValue = IDToValue[IteratorID];
856
123
  for (Value *IV : IVS) {
857
123
    IDToValue[IteratorID] = IV;
858
123
    createSubstitutions(isl_ast_expr_copy(Expr), Stmt, VLTS[i]);
859
123
    i++;
860
123
  }
861
20
862
20
  IDToValue[IteratorID] = OldValue;
863
20
  isl_id_free(IteratorID);
864
20
  isl_ast_expr_free(Expr);
865
20
}
866
867
void IslNodeBuilder::generateCopyStmt(
868
2
    ScopStmt *Stmt, __isl_keep isl_id_to_ast_expr *NewAccesses) {
869
2
  assert(Stmt->size() == 2);
870
2
  auto ReadAccess = Stmt->begin();
871
2
  auto WriteAccess = ReadAccess++;
872
2
  assert((*ReadAccess)->isRead() && (*WriteAccess)->isMustWrite());
873
2
  assert((*ReadAccess)->getElementType() == (*WriteAccess)->getElementType() &&
874
2
         "Accesses use the same data type");
875
2
  assert((*ReadAccess)->isArrayKind() && (*WriteAccess)->isArrayKind());
876
2
  auto *AccessExpr =
877
2
      isl_id_to_ast_expr_get(NewAccesses, (*ReadAccess)->getId());
878
2
  auto *LoadValue = ExprBuilder.create(AccessExpr);
879
2
  AccessExpr = isl_id_to_ast_expr_get(NewAccesses, (*WriteAccess)->getId());
880
2
  auto *StoreAddr = ExprBuilder.createAccessAddress(AccessExpr);
881
2
  Builder.CreateStore(LoadValue, StoreAddr);
882
2
}
883
884
376
void IslNodeBuilder::createUser(__isl_take isl_ast_node *User) {
885
376
  LoopToScevMapT LTS;
886
376
  isl_id *Id;
887
376
  ScopStmt *Stmt;
888
376
889
376
  isl_ast_expr *Expr = isl_ast_node_user_get_expr(User);
890
376
  isl_ast_expr *StmtExpr = isl_ast_expr_get_op_arg(Expr, 0);
891
376
  Id = isl_ast_expr_get_id(StmtExpr);
892
376
  isl_ast_expr_free(StmtExpr);
893
376
894
376
  LTS.insert(OutsideLoopIterations.begin(), OutsideLoopIterations.end());
895
376
896
376
  Stmt = (ScopStmt *)isl_id_get_user(Id);
897
376
  auto *NewAccesses = createNewAccesses(Stmt, User);
898
376
  if (
Stmt->isCopyStmt()376
)
{2
899
2
    generateCopyStmt(Stmt, NewAccesses);
900
2
    isl_ast_expr_free(Expr);
901
374
  } else {
902
374
    createSubstitutions(Expr, Stmt, LTS);
903
374
904
374
    if (Stmt->isBlockStmt())
905
341
      BlockGen.copyStmt(*Stmt, LTS, NewAccesses);
906
374
    else
907
33
      RegionGen.copyStmt(*Stmt, LTS, NewAccesses);
908
374
  }
909
376
910
376
  isl_id_to_ast_expr_free(NewAccesses);
911
376
  isl_ast_node_free(User);
912
376
  isl_id_free(Id);
913
376
}
914
915
97
void IslNodeBuilder::createBlock(__isl_take isl_ast_node *Block) {
916
97
  isl_ast_node_list *List = isl_ast_node_block_get_children(Block);
917
97
918
304
  for (int i = 0; 
i < isl_ast_node_list_n_ast_node(List)304
;
++i207
)
919
207
    create(isl_ast_node_list_get_ast_node(List, i));
920
97
921
97
  isl_ast_node_free(Block);
922
97
  isl_ast_node_list_free(List);
923
97
}
924
925
817
void IslNodeBuilder::create(__isl_take isl_ast_node *Node) {
926
817
  switch (isl_ast_node_get_type(Node)) {
927
0
  case isl_ast_node_error:
928
0
    llvm_unreachable("code generation error");
929
15
  case isl_ast_node_mark:
930
15
    createMark(Node);
931
15
    return;
932
270
  case isl_ast_node_for:
933
270
    createFor(Node);
934
270
    return;
935
59
  case isl_ast_node_if:
936
59
    createIf(Node);
937
59
    return;
938
376
  case isl_ast_node_user:
939
376
    createUser(Node);
940
376
    return;
941
97
  case isl_ast_node_block:
942
97
    createBlock(Node);
943
97
    return;
944
817
  }
945
817
946
0
  
llvm_unreachable0
("Unknown isl_ast_node type");0
947
0
}
948
949
237
bool IslNodeBuilder::materializeValue(isl_id *Id) {
950
237
  // If the Id is already mapped, skip it.
951
237
  if (
!IDToValue.count(Id)237
)
{160
952
160
    auto *ParamSCEV = (const SCEV *)isl_id_get_user(Id);
953
160
    Value *V = nullptr;
954
160
955
160
    // Parameters could refer to invariant loads that need to be
956
160
    // preloaded before we can generate code for the parameter. Thus,
957
160
    // check if any value referred to in ParamSCEV is an invariant load
958
160
    // and if so make sure its equivalence class is preloaded.
959
160
    SetVector<Value *> Values;
960
160
    findValues(ParamSCEV, SE, Values);
961
166
    for (auto *Val : Values) {
962
166
963
166
      // Check if the value is an instruction in a dead block within the SCoP
964
166
      // and if so do not code generate it.
965
166
      if (auto *
Inst166
= dyn_cast<Instruction>(Val))
{28
966
28
        if (
S.contains(Inst)28
)
{14
967
14
          bool IsDead = true;
968
14
969
14
          // Check for "undef" loads first, then if there is a statement for
970
14
          // the parent of Inst and lastly if the parent of Inst has an empty
971
14
          // domain. In the first and last case the instruction is dead but if
972
14
          // there is a statement or the domain is not empty Inst is not dead.
973
14
          auto MemInst = MemAccInst::dyn_cast(Inst);
974
13
          auto Address = MemInst ? 
MemInst.getPointerOperand()13
:
nullptr1
;
975
14
          if (
Address && 14
SE.getUnknown(UndefValue::get(Address->getType())) ==12
976
0
                             SE.getPointerBase(SE.getSCEV(Address))) {
977
14
          } else 
if (14
S.getStmtFor(Inst)14
)
{8
978
8
            IsDead = false;
979
6
          } else {
980
6
            auto *Domain = S.getDomainConditions(Inst->getParent());
981
6
            IsDead = isl_set_is_empty(Domain);
982
6
            isl_set_free(Domain);
983
6
          }
984
14
985
14
          if (
IsDead14
)
{2
986
2
            V = UndefValue::get(ParamSCEV->getType());
987
2
            break;
988
2
          }
989
14
        }
990
28
      }
991
166
992
164
      
if (auto *164
IAClass164
= S.lookupInvariantEquivClass(Val))
{10
993
10
994
10
        // Check if this invariant access class is empty, hence if we never
995
10
        // actually added a loads instruction to it. In that case it has no
996
10
        // (meaningful) users and we should not try to code generate it.
997
10
        if (IAClass->InvariantAccesses.empty())
998
0
          V = UndefValue::get(ParamSCEV->getType());
999
10
1000
10
        if (
!preloadInvariantEquivClass(*IAClass)10
)
{3
1001
3
          isl_id_free(Id);
1002
3
          return false;
1003
3
        }
1004
10
      }
1005
164
    }
1006
160
1007
157
    
V = V ? 157
V2
:
generateSCEV(ParamSCEV)155
;
1008
157
    IDToValue[Id] = V;
1009
157
  }
1010
237
1011
234
  isl_id_free(Id);
1012
234
  return true;
1013
237
}
1014
1015
140
bool IslNodeBuilder::materializeParameters(isl_set *Set) {
1016
360
  for (unsigned i = 0, e = isl_set_dim(Set, isl_dim_param); 
i < e360
;
++i220
)
{223
1017
223
    if (!isl_set_involves_dims(Set, isl_dim_param, i, 1))
1018
159
      continue;
1019
64
    isl_id *Id = isl_set_get_dim_id(Set, isl_dim_param, i);
1020
64
    if (!materializeValue(Id))
1021
3
      return false;
1022
64
  }
1023
137
  return true;
1024
140
}
1025
1026
275
bool IslNodeBuilder::materializeParameters() {
1027
173
  for (const SCEV *Param : S.parameters()) {
1028
173
    isl_id *Id = S.getIdForParam(Param);
1029
173
    if (!materializeValue(Id))
1030
0
      return false;
1031
173
  }
1032
275
  return true;
1033
275
}
1034
1035
/// Generate the computation of the size of the outermost dimension from the
1036
/// Fortran array descriptor (in this case, `@g_arr`). The final `%size`
1037
/// contains the size of the array.
1038
///
1039
/// %arrty = type { i8*, i64, i64, [3 x %desc.dimensionty] }
1040
/// %desc.dimensionty = type { i64, i64, i64 }
1041
/// @g_arr = global %arrty zeroinitializer, align 32
1042
/// ...
1043
/// %0 = load i64, i64* getelementptr inbounds
1044
///                       (%arrty, %arrty* @g_arr, i64 0, i32 3, i64 0, i32 2)
1045
/// %1 = load i64, i64* getelementptr inbounds
1046
///                      (%arrty, %arrty* @g_arr, i64 0, i32 3, i64 0, i32 1)
1047
/// %2 = sub nsw i64 %0, %1
1048
/// %size = add nsw i64 %2, 1
1049
static Value *buildFADOutermostDimensionLoad(Value *GlobalDescriptor,
1050
                                             PollyIRBuilder &Builder,
1051
2
                                             std::string ArrayName) {
1052
2
  assert(GlobalDescriptor && "invalid global descriptor given");
1053
2
1054
2
  Value *endIdx[4] = {Builder.getInt64(0), Builder.getInt32(3),
1055
2
                      Builder.getInt64(0), Builder.getInt32(2)};
1056
2
  Value *endPtr = Builder.CreateInBoundsGEP(GlobalDescriptor, endIdx,
1057
2
                                            ArrayName + "_end_ptr");
1058
2
  Value *end = Builder.CreateLoad(endPtr, ArrayName + "_end");
1059
2
1060
2
  Value *beginIdx[4] = {Builder.getInt64(0), Builder.getInt32(3),
1061
2
                        Builder.getInt64(0), Builder.getInt32(1)};
1062
2
  Value *beginPtr = Builder.CreateInBoundsGEP(GlobalDescriptor, beginIdx,
1063
2
                                              ArrayName + "_begin_ptr");
1064
2
  Value *begin = Builder.CreateLoad(beginPtr, ArrayName + "_begin");
1065
2
1066
2
  Value *size =
1067
2
      Builder.CreateNSWSub(end, begin, ArrayName + "_end_begin_delta");
1068
2
  Type *endType = dyn_cast<IntegerType>(end->getType());
1069
2
  assert(endType && "expected type of end to be integral");
1070
2
1071
2
  size = Builder.CreateNSWAdd(end,
1072
2
                              ConstantInt::get(endType, 1, /* signed = */ true),
1073
2
                              ArrayName + "_size");
1074
2
1075
2
  return size;
1076
2
}
1077
1078
275
bool IslNodeBuilder::materializeFortranArrayOutermostDimension() {
1079
375
  for (const ScopStmt &Stmt : S) {
1080
744
    for (const MemoryAccess *Access : Stmt) {
1081
744
      if (!Access->isArrayKind())
1082
223
        continue;
1083
744
1084
521
      const ScopArrayInfo *Array = Access->getScopArrayInfo();
1085
521
      if (!Array)
1086
4
        continue;
1087
521
1088
517
      
if (517
Array->getNumberOfDimensions() == 0517
)
1089
0
        continue;
1090
517
1091
517
      Value *FAD = Access->getFortranArrayDescriptor();
1092
517
      if (!FAD)
1093
515
        continue;
1094
517
1095
2
      isl_pw_aff *ParametricPwAff = Array->getDimensionSizePw(0);
1096
2
      assert(ParametricPwAff && "parametric pw_aff corresponding "
1097
2
                                "to outermost dimension does not "
1098
2
                                "exist");
1099
2
1100
2
      isl_id *Id = isl_pw_aff_get_dim_id(ParametricPwAff, isl_dim_param, 0);
1101
2
      isl_pw_aff_free(ParametricPwAff);
1102
2
1103
2
      assert(Id && "pw_aff is not parametric");
1104
2
1105
2
      if (
IDToValue.count(Id)2
)
{0
1106
0
        isl_id_free(Id);
1107
0
        continue;
1108
0
      }
1109
2
1110
2
      Value *FinalValue =
1111
2
          buildFADOutermostDimensionLoad(FAD, Builder, Array->getName());
1112
2
      assert(FinalValue && "unable to build Fortran array "
1113
2
                           "descriptor load of outermost dimension");
1114
2
      IDToValue[Id] = FinalValue;
1115
2
      isl_id_free(Id);
1116
2
    }
1117
375
  }
1118
275
  return true;
1119
275
}
1120
1121
/// Add the number of dimensions in @p BS to @p U.
1122
145
static isl_stat countTotalDims(__isl_take isl_basic_set *BS, void *U) {
1123
145
  unsigned *NumTotalDim = static_cast<unsigned *>(U);
1124
145
  *NumTotalDim += isl_basic_set_total_dim(BS);
1125
145
  isl_basic_set_free(BS);
1126
145
  return isl_stat_ok;
1127
145
}
1128
1129
Value *IslNodeBuilder::preloadUnconditionally(isl_set *AccessRange,
1130
                                              isl_ast_build *Build,
1131
111
                                              Instruction *AccInst) {
1132
111
1133
111
  // TODO: This check could be performed in the ScopInfo already.
1134
111
  unsigned NumTotalDim = 0;
1135
111
  isl_set_foreach_basic_set(AccessRange, countTotalDims, &NumTotalDim);
1136
111
  if (
NumTotalDim > MaxDimensionsInAccessRange111
)
{1
1137
1
    isl_set_free(AccessRange);
1138
1
    return nullptr;
1139
1
  }
1140
111
1141
110
  isl_pw_multi_aff *PWAccRel = isl_pw_multi_aff_from_set(AccessRange);
1142
110
  isl_ast_expr *Access =
1143
110
      isl_ast_build_access_from_pw_multi_aff(Build, PWAccRel);
1144
110
  auto *Address = isl_ast_expr_address_of(Access);
1145
110
  auto *AddressValue = ExprBuilder.create(Address);
1146
110
  Value *PreloadVal;
1147
110
1148
110
  // Correct the type as the SAI might have a different type than the user
1149
110
  // expects, especially if the base pointer is a struct.
1150
110
  Type *Ty = AccInst->getType();
1151
110
1152
110
  auto *Ptr = AddressValue;
1153
110
  auto Name = Ptr->getName();
1154
110
  auto AS = Ptr->getType()->getPointerAddressSpace();
1155
110
  Ptr = Builder.CreatePointerCast(Ptr, Ty->getPointerTo(AS), Name + ".cast");
1156
110
  PreloadVal = Builder.CreateLoad(Ptr, Name + ".load");
1157
110
  if (LoadInst *PreloadInst = dyn_cast<LoadInst>(PreloadVal))
1158
110
    PreloadInst->setAlignment(dyn_cast<LoadInst>(AccInst)->getAlignment());
1159
110
1160
110
  // TODO: This is only a hot fix for SCoP sequences that use the same load
1161
110
  //       instruction contained and hoisted by one of the SCoPs.
1162
110
  if (SE.isSCEVable(Ty))
1163
95
    SE.forgetValue(AccInst);
1164
110
1165
110
  return PreloadVal;
1166
111
}
1167
1168
Value *IslNodeBuilder::preloadInvariantLoad(const MemoryAccess &MA,
1169
114
                                            isl_set *Domain) {
1170
114
1171
114
  isl_set *AccessRange = isl_map_range(MA.getAddressFunction());
1172
114
  AccessRange = isl_set_gist_params(AccessRange, S.getContext());
1173
114
1174
114
  if (
!materializeParameters(AccessRange)114
)
{0
1175
0
    isl_set_free(AccessRange);
1176
0
    isl_set_free(Domain);
1177
0
    return nullptr;
1178
0
  }
1179
114
1180
114
  auto *Build = isl_ast_build_from_context(isl_set_universe(S.getParamSpace()));
1181
114
  isl_set *Universe = isl_set_universe(isl_set_get_space(Domain));
1182
114
  bool AlwaysExecuted = isl_set_is_equal(Domain, Universe);
1183
114
  isl_set_free(Universe);
1184
114
1185
114
  Instruction *AccInst = MA.getAccessInstruction();
1186
114
  Type *AccInstTy = AccInst->getType();
1187
114
1188
114
  Value *PreloadVal = nullptr;
1189
114
  if (
AlwaysExecuted114
)
{88
1190
88
    PreloadVal = preloadUnconditionally(AccessRange, Build, AccInst);
1191
88
    isl_ast_build_free(Build);
1192
88
    isl_set_free(Domain);
1193
88
    return PreloadVal;
1194
88
  }
1195
114
1196
26
  
if (26
!materializeParameters(Domain)26
)
{3
1197
3
    isl_ast_build_free(Build);
1198
3
    isl_set_free(AccessRange);
1199
3
    isl_set_free(Domain);
1200
3
    return nullptr;
1201
3
  }
1202
26
1203
23
  isl_ast_expr *DomainCond = isl_ast_build_expr_from_set(Build, Domain);
1204
23
  Domain = nullptr;
1205
23
1206
23
  ExprBuilder.setTrackOverflow(true);
1207
23
  Value *Cond = ExprBuilder.create(DomainCond);
1208
23
  Value *OverflowHappened = Builder.CreateNot(ExprBuilder.getOverflowState(),
1209
23
                                              "polly.preload.cond.overflown");
1210
23
  Cond = Builder.CreateAnd(Cond, OverflowHappened, "polly.preload.cond.result");
1211
23
  ExprBuilder.setTrackOverflow(false);
1212
23
1213
23
  if (!Cond->getType()->isIntegerTy(1))
1214
0
    Cond = Builder.CreateIsNotNull(Cond);
1215
23
1216
23
  BasicBlock *CondBB = SplitBlock(Builder.GetInsertBlock(),
1217
23
                                  &*Builder.GetInsertPoint(), &DT, &LI);
1218
23
  CondBB->setName("polly.preload.cond");
1219
23
1220
23
  BasicBlock *MergeBB = SplitBlock(CondBB, &CondBB->front(), &DT, &LI);
1221
23
  MergeBB->setName("polly.preload.merge");
1222
23
1223
23
  Function *F = Builder.GetInsertBlock()->getParent();
1224
23
  LLVMContext &Context = F->getContext();
1225
23
  BasicBlock *ExecBB = BasicBlock::Create(Context, "polly.preload.exec", F);
1226
23
1227
23
  DT.addNewBlock(ExecBB, CondBB);
1228
23
  if (Loop *L = LI.getLoopFor(CondBB))
1229
9
    L->addBasicBlockToLoop(ExecBB, LI);
1230
23
1231
23
  auto *CondBBTerminator = CondBB->getTerminator();
1232
23
  Builder.SetInsertPoint(CondBBTerminator);
1233
23
  Builder.CreateCondBr(Cond, ExecBB, MergeBB);
1234
23
  CondBBTerminator->eraseFromParent();
1235
23
1236
23
  Builder.SetInsertPoint(ExecBB);
1237
23
  Builder.CreateBr(MergeBB);
1238
23
1239
23
  Builder.SetInsertPoint(ExecBB->getTerminator());
1240
23
  Value *PreAccInst = preloadUnconditionally(AccessRange, Build, AccInst);
1241
23
  Builder.SetInsertPoint(MergeBB->getTerminator());
1242
23
  auto *MergePHI = Builder.CreatePHI(
1243
23
      AccInstTy, 2, "polly.preload." + AccInst->getName() + ".merge");
1244
23
  PreloadVal = MergePHI;
1245
23
1246
23
  if (
!PreAccInst23
)
{0
1247
0
    PreloadVal = nullptr;
1248
0
    PreAccInst = UndefValue::get(AccInstTy);
1249
0
  }
1250
23
1251
23
  MergePHI->addIncoming(PreAccInst, ExecBB);
1252
23
  MergePHI->addIncoming(Constant::getNullValue(AccInstTy), CondBB);
1253
23
1254
23
  isl_ast_build_free(Build);
1255
23
  return PreloadVal;
1256
26
}
1257
1258
bool IslNodeBuilder::preloadInvariantEquivClass(
1259
158
    InvariantEquivClassTy &IAClass) {
1260
158
  // For an equivalence class of invariant loads we pre-load the representing
1261
158
  // element with the unified execution context. However, we have to map all
1262
158
  // elements of the class to the one preloaded load as they are referenced
1263
158
  // during the code generation and therefor need to be mapped.
1264
158
  const MemoryAccessList &MAs = IAClass.InvariantAccesses;
1265
158
  if (MAs.empty())
1266
2
    return true;
1267
158
1268
156
  MemoryAccess *MA = MAs.front();
1269
156
  assert(MA->isArrayKind() && MA->isRead());
1270
156
1271
156
  // If the access function was already mapped, the preload of this equivalence
1272
156
  // class was triggered earlier already and doesn't need to be done again.
1273
156
  if (ValueMap.count(MA->getAccessInstruction()))
1274
35
    return true;
1275
156
1276
156
  // Check for recursion which can be caused by additional constraints, e.g.,
1277
156
  // non-finite loop constraints. In such a case we have to bail out and insert
1278
156
  // a "false" runtime check that will cause the original code to be executed.
1279
121
  auto PtrId = std::make_pair(IAClass.IdentifyingPointer, IAClass.AccessType);
1280
121
  if (!PreloadedPtrs.insert(PtrId).second)
1281
4
    return false;
1282
121
1283
121
  // The execution context of the IAClass.
1284
117
  isl_set *&ExecutionCtx = IAClass.ExecutionContext;
1285
117
1286
117
  // If the base pointer of this class is dependent on another one we have to
1287
117
  // make sure it was preloaded already.
1288
117
  auto *SAI = MA->getScopArrayInfo();
1289
117
  if (auto *
BaseIAClass117
= S.lookupInvariantEquivClass(SAI->getBasePtr()))
{29
1290
29
    if (!preloadInvariantEquivClass(*BaseIAClass))
1291
1
      return false;
1292
29
1293
29
    // After we preloaded the BaseIAClass we adjusted the BaseExecutionCtx and
1294
29
    // we need to refine the ExecutionCtx.
1295
28
    isl_set *BaseExecutionCtx = isl_set_copy(BaseIAClass->ExecutionContext);
1296
28
    ExecutionCtx = isl_set_intersect(ExecutionCtx, BaseExecutionCtx);
1297
28
  }
1298
117
1299
117
  // If the size of a dimension is dependent on another class, make sure it is
1300
117
  // preloaded.
1301
116
  
for (unsigned i = 1, e = SAI->getNumberOfDimensions(); 116
i < e116
;
++i0
)
{2
1302
2
    const SCEV *Dim = SAI->getDimensionSize(i);
1303
2
    SetVector<Value *> Values;
1304
2
    findValues(Dim, SE, Values);
1305
2
    for (auto *Val : Values) {
1306
2
      if (auto *
BaseIAClass2
= S.lookupInvariantEquivClass(Val))
{2
1307
2
        if (!preloadInvariantEquivClass(*BaseIAClass))
1308
2
          return false;
1309
2
1310
2
        // After we preloaded the BaseIAClass we adjusted the BaseExecutionCtx
1311
2
        // and we need to refine the ExecutionCtx.
1312
0
        isl_set *BaseExecutionCtx = isl_set_copy(BaseIAClass->ExecutionContext);
1313
0
        ExecutionCtx = isl_set_intersect(ExecutionCtx, BaseExecutionCtx);
1314
0
      }
1315
2
    }
1316
2
  }
1317
116
1318
114
  Instruction *AccInst = MA->getAccessInstruction();
1319
114
  Type *AccInstTy = AccInst->getType();
1320
114
1321
114
  Value *PreloadVal = preloadInvariantLoad(*MA, isl_set_copy(ExecutionCtx));
1322
114
  if (!PreloadVal)
1323
4
    return false;
1324
114
1325
120
  
for (const MemoryAccess *MA : MAs) 110
{120
1326
120
    Instruction *MAAccInst = MA->getAccessInstruction();
1327
120
    assert(PreloadVal->getType() == MAAccInst->getType());
1328
120
    ValueMap[MAAccInst] = PreloadVal;
1329
120
  }
1330
110
1331
110
  if (
SE.isSCEVable(AccInstTy)110
)
{95
1332
95
    isl_id *ParamId = S.getIdForParam(SE.getSCEV(AccInst));
1333
95
    if (ParamId)
1334
20
      IDToValue[ParamId] = PreloadVal;
1335
95
    isl_id_free(ParamId);
1336
95
  }
1337
110
1338
110
  BasicBlock *EntryBB = &Builder.GetInsertBlock()->getParent()->getEntryBlock();
1339
110
  auto *Alloca = new AllocaInst(AccInstTy, DL.getAllocaAddrSpace(),
1340
110
                                AccInst->getName() + ".preload.s2a");
1341
110
  Alloca->insertBefore(&*EntryBB->getFirstInsertionPt());
1342
110
  Builder.CreateStore(PreloadVal, Alloca);
1343
110
  ValueMapT PreloadedPointer;
1344
110
  PreloadedPointer[PreloadVal] = AccInst;
1345
110
  Annotator.addAlternativeAliasBases(PreloadedPointer);
1346
110
1347
53
  for (auto *DerivedSAI : SAI->getDerivedSAIs()) {
1348
53
    Value *BasePtr = DerivedSAI->getBasePtr();
1349
53
1350
65
    for (const MemoryAccess *MA : MAs) {
1351
65
      // As the derived SAI information is quite coarse, any load from the
1352
65
      // current SAI could be the base pointer of the derived SAI, however we
1353
65
      // should only change the base pointer of the derived SAI if we actually
1354
65
      // preloaded it.
1355
65
      if (
BasePtr == MA->getOriginalBaseAddr()65
)
{0
1356
0
        assert(BasePtr->getType() == PreloadVal->getType());
1357
0
        DerivedSAI->setBasePtr(PreloadVal);
1358
0
      }
1359
65
1360
65
      // For scalar derived SAIs we remap the alloca used for the derived value.
1361
65
      if (BasePtr == MA->getAccessInstruction())
1362
41
        ScalarMap[DerivedSAI] = Alloca;
1363
65
    }
1364
53
  }
1365
110
1366
120
  for (const MemoryAccess *MA : MAs) {
1367
120
1368
120
    Instruction *MAAccInst = MA->getAccessInstruction();
1369
120
    // Use the escape system to get the correct value to users outside the SCoP.
1370
120
    BlockGenerator::EscapeUserVectorTy EscapeUsers;
1371
120
    for (auto *U : MAAccInst->users())
1372
126
      
if (Instruction *126
UI126
= dyn_cast<Instruction>(U))
1373
126
        
if (126
!S.contains(UI)126
)
1374
7
          EscapeUsers.push_back(UI);
1375
120
1376
120
    if (EscapeUsers.empty())
1377
114
      continue;
1378
120
1379
6
    EscapeMap[MA->getAccessInstruction()] =
1380
6
        std::make_pair(Alloca, std::move(EscapeUsers));
1381
6
  }
1382
110
1383
110
  return true;
1384
114
}
1385
1386
280
void IslNodeBuilder::allocateNewArrays() {
1387
599
  for (auto &SAI : S.arrays()) {
1388
599
    if (SAI->getBasePtr())
1389
594
      continue;
1390
599
1391
5
    assert(SAI->getNumberOfDimensions() > 0 && SAI->getDimensionSize(0) &&
1392
5
           "The size of the outermost dimension is used to declare newly "
1393
5
           "created arrays that require memory allocation.");
1394
5
1395
5
    Type *NewArrayType = nullptr;
1396
15
    for (int i = SAI->getNumberOfDimensions() - 1; 
i >= 015
;
i--10
)
{10
1397
10
      auto *DimSize = SAI->getDimensionSize(i);
1398
10
      unsigned UnsignedDimSize = static_cast<const SCEVConstant *>(DimSize)
1399
10
                                     ->getAPInt()
1400
10
                                     .getLimitedValue();
1401
10
1402
10
      if (!NewArrayType)
1403
5
        NewArrayType = SAI->getElementType();
1404
10
1405
10
      NewArrayType = ArrayType::get(NewArrayType, UnsignedDimSize);
1406
10
    }
1407
5
1408
5
    auto InstIt =
1409
5
        Builder.GetInsertBlock()->getParent()->getEntryBlock().getTerminator();
1410
5
    auto *CreatedArray = new AllocaInst(NewArrayType, DL.getAllocaAddrSpace(),
1411
5
                                        SAI->getName(), &*InstIt);
1412
5
    CreatedArray->setAlignment(PollyTargetFirstLevelCacheLineSize);
1413
5
    SAI->setBasePtr(CreatedArray);
1414
5
  }
1415
280
}
1416
1417
280
bool IslNodeBuilder::preloadInvariantLoads() {
1418
280
1419
280
  auto &InvariantEquivClasses = S.getInvariantAccesses();
1420
280
  if (InvariantEquivClasses.empty())
1421
216
    return true;
1422
280
1423
64
  BasicBlock *PreLoadBB = SplitBlock(Builder.GetInsertBlock(),
1424
64
                                     &*Builder.GetInsertPoint(), &DT, &LI);
1425
64
  PreLoadBB->setName("polly.preload.begin");
1426
64
  Builder.SetInsertPoint(&PreLoadBB->front());
1427
64
1428
64
  for (auto &IAClass : InvariantEquivClasses)
1429
117
    
if (117
!preloadInvariantEquivClass(IAClass)117
)
1430
5
      return false;
1431
64
1432
59
  return true;
1433
64
}
1434
1435
275
void IslNodeBuilder::addParameters(__isl_take isl_set *Context) {
1436
275
  // Materialize values for the parameters of the SCoP.
1437
275
  materializeParameters();
1438
275
1439
275
  // materialize the outermost dimension parameters for a Fortran array.
1440
275
  // NOTE: materializeParameters() does not work since it looks through
1441
275
  // the SCEVs. We don't have a corresponding SCEV for the array size
1442
275
  // parameter
1443
275
  materializeFortranArrayOutermostDimension();
1444
275
1445
275
  // Generate values for the current loop iteration for all surrounding loops.
1446
275
  //
1447
275
  // We may also reference loops outside of the scop which do not contain the
1448
275
  // scop itself, but as the number of such scops may be arbitrarily large we do
1449
275
  // not generate code for them here, but only at the point of code generation
1450
275
  // where these values are needed.
1451
275
  Loop *L = LI.getLoopFor(S.getEntry());
1452
275
1453
481
  while (
L != nullptr && 481
S.contains(L)230
)
1454
206
    L = L->getParentLoop();
1455
275
1456
300
  while (
L != nullptr300
)
{25
1457
25
    const SCEV *OuterLIV = SE.getAddRecExpr(SE.getUnknown(Builder.getInt64(0)),
1458
25
                                            SE.getUnknown(Builder.getInt64(1)),
1459
25
                                            L, SCEV::FlagAnyWrap);
1460
25
    Value *V = generateSCEV(OuterLIV);
1461
25
    OutsideLoopIterations[L] = SE.getUnknown(V);
1462
25
    L = L->getParentLoop();
1463
25
  }
1464
275
1465
275
  isl_set_free(Context);
1466
275
}
1467
1468
181
Value *IslNodeBuilder::generateSCEV(const SCEV *Expr) {
1469
181
  /// We pass the insert location of our Builder, as Polly ensures during IR
1470
181
  /// generation that there is always a valid CFG into which instructions are
1471
181
  /// inserted. As a result, the insertpoint is known to be always followed by a
1472
181
  /// terminator instruction. This means the insert point may be specified by a
1473
181
  /// terminator instruction, but it can never point to an ->end() iterator
1474
181
  /// which does not have a corresponding instruction. Hence, dereferencing
1475
181
  /// the insertpoint to obtain an instruction is known to be save.
1476
181
  ///
1477
181
  /// We also do not need to update the Builder here, as new instructions are
1478
181
  /// always inserted _before_ the given InsertLocation. As a result, the
1479
181
  /// insert location remains valid.
1480
181
  assert(Builder.GetInsertBlock()->end() != Builder.GetInsertPoint() &&
1481
181
         "Insert location points after last valid instruction");
1482
181
  Instruction *InsertLocation = &*Builder.GetInsertPoint();
1483
181
  return expandCodeFor(S, SE, DL, "polly", Expr, Expr->getType(),
1484
181
                       InsertLocation, &ValueMap,
1485
181
                       StartBlock->getSinglePredecessor());
1486
181
}
1487
1488
/// The AST expression we generate to perform the run-time check assumes
1489
/// computations on integer types of infinite size. As we only use 64-bit
1490
/// arithmetic we check for overflows, in case of which we set the result
1491
/// of this run-time check to false to be conservatively correct,
1492
275
Value *IslNodeBuilder::createRTC(isl_ast_expr *Condition) {
1493
275
  auto ExprBuilder = getExprBuilder();
1494
275
  ExprBuilder.setTrackOverflow(true);
1495
275
  Value *RTC = ExprBuilder.create(Condition);
1496
275
  if (!RTC->getType()->isIntegerTy(1))
1497
164
    RTC = Builder.CreateIsNotNull(RTC);
1498
275
  Value *OverflowHappened =
1499
275
      Builder.CreateNot(ExprBuilder.getOverflowState(), "polly.rtc.overflown");
1500
275
1501
275
  if (
PollyGenerateRTCPrint275
)
{0
1502
0
    auto *F = Builder.GetInsertBlock()->getParent();
1503
0
    RuntimeDebugBuilder::createCPUPrinter(
1504
0
        Builder,
1505
0
        "F: " + F->getName().str() + " R: " + S.getRegion().getNameStr() +
1506
0
            " __RTC: ",
1507
0
        RTC, " Overflow: ", OverflowHappened, "\n");
1508
0
  }
1509
275
1510
275
  RTC = Builder.CreateAnd(RTC, OverflowHappened, "polly.rtc.result");
1511
275
  ExprBuilder.setTrackOverflow(false);
1512
275
1513
275
  if (!isa<ConstantInt>(RTC))
1514
110
    VersionedScops++;
1515
275
1516
275
  return RTC;
1517
275
}