Coverage Report

Created: 2017-08-18 19:41

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