Coverage Report

Created: 2018-04-24 22:41

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