Coverage Report

Created: 2018-12-13 20:48

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