Coverage Report

Created: 2017-04-28 04:32

/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/tools/polly/lib/CodeGen/IslAst.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- IslAst.cpp - isl code generator interface --------------------------===//
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
// The isl code generator interface takes a Scop and generates an isl_ast. This
11
// ist_ast can either be returned directly or it can be pretty printed to
12
// stdout.
13
//
14
// A typical isl_ast output looks like this:
15
//
16
// for (c2 = max(0, ceild(n + m, 2); c2 <= min(511, floord(5 * n, 3)); c2++) {
17
//   bb2(c2);
18
// }
19
//
20
// An in-depth discussion of our AST generation approach can be found in:
21
//
22
// Polyhedral AST generation is more than scanning polyhedra
23
// Tobias Grosser, Sven Verdoolaege, Albert Cohen
24
// ACM Transations on Programming Languages and Systems (TOPLAS),
25
// 37(4), July 2015
26
// http://www.grosser.es/#pub-polyhedral-AST-generation
27
//
28
//===----------------------------------------------------------------------===//
29
30
#include "polly/CodeGen/IslAst.h"
31
#include "polly/CodeGen/CodeGeneration.h"
32
#include "polly/DependenceInfo.h"
33
#include "polly/LinkAllPasses.h"
34
#include "polly/Options.h"
35
#include "polly/ScopInfo.h"
36
#include "polly/Support/GICHelper.h"
37
#include "llvm/Analysis/RegionInfo.h"
38
#include "llvm/Support/Debug.h"
39
#include "isl/aff.h"
40
#include "isl/ast_build.h"
41
#include "isl/list.h"
42
#include "isl/map.h"
43
#include "isl/set.h"
44
#include "isl/union_map.h"
45
46
#define DEBUG_TYPE "polly-ast"
47
48
using namespace llvm;
49
using namespace polly;
50
51
using IslAstUserPayload = IslAstInfo::IslAstUserPayload;
52
53
static cl::opt<bool>
54
    PollyParallel("polly-parallel",
55
                  cl::desc("Generate thread parallel code (isl codegen only)"),
56
                  cl::init(false), cl::ZeroOrMore, cl::cat(PollyCategory));
57
58
static cl::opt<bool> PollyParallelForce(
59
    "polly-parallel-force",
60
    cl::desc(
61
        "Force generation of thread parallel code ignoring any cost model"),
62
    cl::init(false), cl::ZeroOrMore, cl::cat(PollyCategory));
63
64
static cl::opt<bool> UseContext("polly-ast-use-context",
65
                                cl::desc("Use context"), cl::Hidden,
66
                                cl::init(true), cl::ZeroOrMore,
67
                                cl::cat(PollyCategory));
68
69
static cl::opt<bool> DetectParallel("polly-ast-detect-parallel",
70
                                    cl::desc("Detect parallelism"), cl::Hidden,
71
                                    cl::init(false), cl::ZeroOrMore,
72
                                    cl::cat(PollyCategory));
73
74
namespace polly {
75
/// Temporary information used when building the ast.
76
struct AstBuildUserInfo {
77
  /// Construct and initialize the helper struct for AST creation.
78
  AstBuildUserInfo()
79
410
      : Deps(nullptr), InParallelFor(false), LastForNodeId(nullptr) {}
80
81
  /// The dependence information used for the parallelism check.
82
  const Dependences *Deps;
83
84
  /// Flag to indicate that we are inside a parallel for node.
85
  bool InParallelFor;
86
87
  /// The last iterator id created for the current SCoP.
88
  isl_id *LastForNodeId;
89
};
90
} // namespace polly
91
92
/// Free an IslAstUserPayload object pointed to by @p Ptr.
93
1.47k
static void freeIslAstUserPayload(void *Ptr) {
94
1.47k
  delete ((IslAstInfo::IslAstUserPayload *)Ptr);
95
1.47k
}
96
97
1.47k
IslAstInfo::IslAstUserPayload::~IslAstUserPayload() {
98
1.47k
  isl_ast_build_free(Build);
99
1.47k
  isl_pw_aff_free(MinimalDependenceDistance);
100
1.47k
}
101
102
/// Print a string @p str in a single line using @p Printer.
103
static isl_printer *printLine(__isl_take isl_printer *Printer,
104
                              const std::string &str,
105
116
                              __isl_keep isl_pw_aff *PWA = nullptr) {
106
116
  Printer = isl_printer_start_line(Printer);
107
116
  Printer = isl_printer_print_str(Printer, str.c_str());
108
116
  if (PWA)
109
21
    Printer = isl_printer_print_pw_aff(Printer, PWA);
110
116
  return isl_printer_end_line(Printer);
111
116
}
112
113
/// Return all broken reductions as a string of clauses (OpenMP style).
114
368
static const std::string getBrokenReductionsStr(__isl_keep isl_ast_node *Node) {
115
368
  IslAstInfo::MemoryAccessSet *BrokenReductions;
116
368
  std::string str;
117
368
118
368
  BrokenReductions = IslAstInfo::getBrokenReductions(Node);
119
368
  if (
!BrokenReductions || 368
BrokenReductions->empty()152
)
120
346
    return "";
121
368
122
368
  // Map each type of reduction to a comma separated list of the base addresses.
123
22
  std::map<MemoryAccess::ReductionType, std::string> Clauses;
124
22
  for (MemoryAccess *MA : *BrokenReductions)
125
52
    
if (52
MA->isWrite()52
)
126
26
      Clauses[MA->getReductionType()] +=
127
26
          ", " + MA->getScopArrayInfo()->getName();
128
22
129
22
  // Now print the reductions sorted by type. Each type will cause a clause
130
22
  // like:  reduction (+ : sum0, sum1, sum2)
131
25
  for (const auto &ReductionClause : Clauses) {
132
25
    str += " reduction (";
133
25
    str += MemoryAccess::getReductionOperatorStr(ReductionClause.first);
134
25
    // Remove the first two symbols (", ") to make the output look pretty.
135
25
    str += " : " + ReductionClause.second.substr(2) + ")";
136
25
  }
137
22
138
22
  return str;
139
368
}
140
141
/// Callback executed for each for node in the ast in order to print it.
142
static isl_printer *cbPrintFor(__isl_take isl_printer *Printer,
143
                               __isl_take isl_ast_print_options *Options,
144
368
                               __isl_keep isl_ast_node *Node, void *) {
145
368
146
368
  isl_pw_aff *DD = IslAstInfo::getMinimalDependenceDistance(Node);
147
368
  const std::string BrokenReductionsStr = getBrokenReductionsStr(Node);
148
368
  const std::string KnownParallelStr = "#pragma known-parallel";
149
368
  const std::string DepDisPragmaStr = "#pragma minimal dependence distance: ";
150
368
  const std::string SimdPragmaStr = "#pragma simd";
151
368
  const std::string OmpPragmaStr = "#pragma omp parallel for";
152
368
153
368
  if (DD)
154
21
    Printer = printLine(Printer, DepDisPragmaStr, DD);
155
368
156
368
  if (IslAstInfo::isInnermostParallel(Node))
157
44
    Printer = printLine(Printer, SimdPragmaStr + BrokenReductionsStr);
158
368
159
368
  if (IslAstInfo::isExecutedInParallel(Node))
160
18
    Printer = printLine(Printer, OmpPragmaStr);
161
350
  else 
if (350
IslAstInfo::isOutermostParallel(Node)350
)
162
33
    Printer = printLine(Printer, KnownParallelStr + BrokenReductionsStr);
163
368
164
368
  isl_pw_aff_free(DD);
165
368
  return isl_ast_node_for_print(Node, Printer, Options);
166
368
}
167
168
/// Check if the current scheduling dimension is parallel.
169
///
170
/// In case the dimension is parallel we also check if any reduction
171
/// dependences is broken when we exploit this parallelism. If so,
172
/// @p IsReductionParallel will be set to true. The reduction dependences we use
173
/// to check are actually the union of the transitive closure of the initial
174
/// reduction dependences together with their reveresal. Even though these
175
/// dependences connect all iterations with each other (thus they are cyclic)
176
/// we can perform the parallelism check as we are only interested in a zero
177
/// (or non-zero) dependence distance on the dimension in question.
178
static bool astScheduleDimIsParallel(__isl_keep isl_ast_build *Build,
179
                                     const Dependences *D,
180
163
                                     IslAstUserPayload *NodeInfo) {
181
163
  if (!D->hasValidDependences())
182
1
    return false;
183
163
184
162
  isl_union_map *Schedule = isl_ast_build_get_schedule(Build);
185
162
  isl_union_map *Deps = D->getDependences(
186
162
      Dependences::TYPE_RAW | Dependences::TYPE_WAW | Dependences::TYPE_WAR);
187
162
188
162
  if (!D->isParallel(Schedule, Deps, &NodeInfo->MinimalDependenceDistance) &&
189
28
      !isl_union_map_free(Schedule))
190
28
    return false;
191
162
192
134
  isl_union_map *RedDeps = D->getDependences(Dependences::TYPE_TC_RED);
193
134
  if (!D->isParallel(Schedule, RedDeps))
194
22
    NodeInfo->IsReductionParallel = true;
195
134
196
134
  if (
!NodeInfo->IsReductionParallel && 134
!isl_union_map_free(Schedule)112
)
197
112
    return true;
198
134
199
134
  // Annotate reduction parallel nodes with the memory accesses which caused the
200
134
  // reduction dependences parallel execution of the node conflicts with.
201
52
  
for (const auto &MaRedPair : D->getReductionDependences()) 22
{52
202
52
    if (!MaRedPair.second)
203
0
      continue;
204
52
    RedDeps = isl_union_map_from_map(isl_map_copy(MaRedPair.second));
205
52
    if (!D->isParallel(Schedule, RedDeps))
206
52
      NodeInfo->BrokenReductions.insert(MaRedPair.first);
207
52
  }
208
22
209
22
  isl_union_map_free(Schedule);
210
22
  return true;
211
134
}
212
213
// This method is executed before the construction of a for node. It creates
214
// an isl_id that is used to annotate the subsequently generated ast for nodes.
215
//
216
// In this function we also run the following analyses:
217
//
218
// - Detection of openmp parallel loops
219
//
220
static __isl_give isl_id *astBuildBeforeFor(__isl_keep isl_ast_build *Build,
221
225
                                            void *User) {
222
225
  AstBuildUserInfo *BuildInfo = (AstBuildUserInfo *)User;
223
225
  IslAstUserPayload *Payload = new IslAstUserPayload();
224
225
  isl_id *Id = isl_id_alloc(isl_ast_build_get_ctx(Build), "", Payload);
225
225
  Id = isl_id_set_free_user(Id, freeIslAstUserPayload);
226
225
  BuildInfo->LastForNodeId = Id;
227
225
228
225
  // Test for parallelism only if we are not already inside a parallel loop
229
225
  if (!BuildInfo->InParallelFor)
230
128
    BuildInfo->InParallelFor = Payload->IsOutermostParallel =
231
128
        astScheduleDimIsParallel(Build, BuildInfo->Deps, Payload);
232
225
233
225
  return Id;
234
225
}
235
236
// This method is executed after the construction of a for node.
237
//
238
// It performs the following actions:
239
//
240
// - Reset the 'InParallelFor' flag, as soon as we leave a for node,
241
//   that is marked as openmp parallel.
242
//
243
static __isl_give isl_ast_node *
244
astBuildAfterFor(__isl_take isl_ast_node *Node, __isl_keep isl_ast_build *Build,
245
225
                 void *User) {
246
225
  isl_id *Id = isl_ast_node_get_annotation(Node);
247
225
  assert(Id && "Post order visit assumes annotated for nodes");
248
225
  IslAstUserPayload *Payload = (IslAstUserPayload *)isl_id_get_user(Id);
249
225
  assert(Payload && "Post order visit assumes annotated for nodes");
250
225
251
225
  AstBuildUserInfo *BuildInfo = (AstBuildUserInfo *)User;
252
225
  assert(!Payload->Build && "Build environment already set");
253
225
  Payload->Build = isl_ast_build_copy(Build);
254
225
  Payload->IsInnermost = (Id == BuildInfo->LastForNodeId);
255
225
256
225
  // Innermost loops that are surrounded by parallel loops have not yet been
257
225
  // tested for parallelism. Test them here to ensure we check all innermost
258
225
  // loops for parallelism.
259
225
  if (
Payload->IsInnermost && 225
BuildInfo->InParallelFor123
)
{111
260
111
    if (
Payload->IsOutermostParallel111
)
{62
261
62
      Payload->IsInnermostParallel = true;
262
49
    } else {
263
49
      if (PollyVectorizerChoice == VECTORIZER_NONE)
264
35
        Payload->IsInnermostParallel =
265
35
            astScheduleDimIsParallel(Build, BuildInfo->Deps, Payload);
266
49
    }
267
111
  }
268
225
  if (Payload->IsOutermostParallel)
269
104
    BuildInfo->InParallelFor = false;
270
225
271
225
  isl_id_free(Id);
272
225
  return Node;
273
225
}
274
275
static isl_stat astBuildBeforeMark(__isl_keep isl_id *MarkId,
276
                                   __isl_keep isl_ast_build *Build,
277
40
                                   void *User) {
278
40
  if (!MarkId)
279
0
    return isl_stat_error;
280
40
281
40
  AstBuildUserInfo *BuildInfo = (AstBuildUserInfo *)User;
282
40
  if (!strcmp(isl_id_get_name(MarkId), "SIMD"))
283
14
    BuildInfo->InParallelFor = true;
284
40
285
40
  return isl_stat_ok;
286
40
}
287
288
static __isl_give isl_ast_node *
289
astBuildAfterMark(__isl_take isl_ast_node *Node,
290
40
                  __isl_keep isl_ast_build *Build, void *User) {
291
40
  assert(isl_ast_node_get_type(Node) == isl_ast_node_mark);
292
40
  AstBuildUserInfo *BuildInfo = (AstBuildUserInfo *)User;
293
40
  auto *Id = isl_ast_node_mark_get_id(Node);
294
40
  if (!strcmp(isl_id_get_name(Id), "SIMD"))
295
14
    BuildInfo->InParallelFor = false;
296
40
  isl_id_free(Id);
297
40
  return Node;
298
40
}
299
300
static __isl_give isl_ast_node *AtEachDomain(__isl_take isl_ast_node *Node,
301
                                             __isl_keep isl_ast_build *Build,
302
1.25k
                                             void *User) {
303
1.25k
  assert(!isl_ast_node_get_annotation(Node) && "Node already annotated");
304
1.25k
305
1.25k
  IslAstUserPayload *Payload = new IslAstUserPayload();
306
1.25k
  isl_id *Id = isl_id_alloc(isl_ast_build_get_ctx(Build), "", Payload);
307
1.25k
  Id = isl_id_set_free_user(Id, freeIslAstUserPayload);
308
1.25k
309
1.25k
  Payload->Build = isl_ast_build_copy(Build);
310
1.25k
311
1.25k
  return isl_ast_node_set_annotation(Node, Id);
312
1.25k
}
313
314
// Build alias check condition given a pair of minimal/maximal access.
315
static __isl_give isl_ast_expr *
316
buildCondition(__isl_keep isl_ast_build *Build, const Scop::MinMaxAccessTy *It0,
317
146
               const Scop::MinMaxAccessTy *It1) {
318
146
  isl_ast_expr *NonAliasGroup, *MinExpr, *MaxExpr;
319
146
  MinExpr = isl_ast_expr_address_of(isl_ast_build_access_from_pw_multi_aff(
320
146
      Build, isl_pw_multi_aff_copy(It0->first)));
321
146
  MaxExpr = isl_ast_expr_address_of(isl_ast_build_access_from_pw_multi_aff(
322
146
      Build, isl_pw_multi_aff_copy(It1->second)));
323
146
  NonAliasGroup = isl_ast_expr_le(MaxExpr, MinExpr);
324
146
  MinExpr = isl_ast_expr_address_of(isl_ast_build_access_from_pw_multi_aff(
325
146
      Build, isl_pw_multi_aff_copy(It1->first)));
326
146
  MaxExpr = isl_ast_expr_address_of(isl_ast_build_access_from_pw_multi_aff(
327
146
      Build, isl_pw_multi_aff_copy(It0->second)));
328
146
  NonAliasGroup =
329
146
      isl_ast_expr_or(NonAliasGroup, isl_ast_expr_le(MaxExpr, MinExpr));
330
146
331
146
  return NonAliasGroup;
332
146
}
333
334
__isl_give isl_ast_expr *
335
410
IslAst::buildRunCondition(Scop *S, __isl_keep isl_ast_build *Build) {
336
410
  isl_ast_expr *RunCondition;
337
410
338
410
  // The conditions that need to be checked at run-time for this scop are
339
410
  // available as an isl_set in the runtime check context from which we can
340
410
  // directly derive a run-time condition.
341
410
  auto *PosCond = isl_ast_build_expr_from_set(Build, S->getAssumedContext());
342
410
  if (
S->hasTrivialInvalidContext()410
)
{299
343
299
    RunCondition = PosCond;
344
111
  } else {
345
111
    auto *ZeroV = isl_val_zero(isl_ast_build_get_ctx(Build));
346
111
    auto *NegCond = isl_ast_build_expr_from_set(Build, S->getInvalidContext());
347
111
    auto *NotNegCond = isl_ast_expr_eq(isl_ast_expr_from_val(ZeroV), NegCond);
348
111
    RunCondition = isl_ast_expr_and(PosCond, NotNegCond);
349
111
  }
350
410
351
410
  // Create the alias checks from the minimal/maximal accesses in each alias
352
410
  // group which consists of read only and non read only (read write) accesses.
353
410
  // This operation is by construction quadratic in the read-write pointers and
354
410
  // linear int the read only pointers in each alias group.
355
91
  for (const Scop::MinMaxVectorPairTy &MinMaxAccessPair : S->getAliasGroups()) {
356
91
    auto &MinMaxReadWrite = MinMaxAccessPair.first;
357
91
    auto &MinMaxReadOnly = MinMaxAccessPair.second;
358
91
    auto RWAccEnd = MinMaxReadWrite.end();
359
91
360
194
    for (auto RWAccIt0 = MinMaxReadWrite.begin(); RWAccIt0 != RWAccEnd;
361
103
         
++RWAccIt0103
)
{103
362
116
      for (auto RWAccIt1 = RWAccIt0 + 1; 
RWAccIt1 != RWAccEnd116
;
++RWAccIt113
)
363
13
        RunCondition = isl_ast_expr_and(
364
13
            RunCondition, buildCondition(Build, RWAccIt0, RWAccIt1));
365
103
      for (const Scop::MinMaxAccessTy &ROAccIt : MinMaxReadOnly)
366
133
        RunCondition = isl_ast_expr_and(
367
133
            RunCondition, buildCondition(Build, RWAccIt0, &ROAccIt));
368
103
    }
369
91
  }
370
410
371
410
  return RunCondition;
372
410
}
373
374
/// Simple cost analysis for a given SCoP.
375
///
376
/// TODO: Improve this analysis and extract it to make it usable in other
377
///       places too.
378
///       In order to improve the cost model we could either keep track of
379
///       performed optimizations (e.g., tiling) or compute properties on the
380
///       original as well as optimized SCoP (e.g., #stride-one-accesses).
381
410
static bool benefitsFromPolly(Scop *Scop, bool PerformParallelTest) {
382
410
383
410
  if (PollyProcessUnprofitable)
384
410
    return true;
385
410
386
410
  // Check if nothing interesting happened.
387
0
  
if (0
!PerformParallelTest && 0
!Scop->isOptimized()0
&&
388
0
      Scop->getAliasGroups().empty())
389
0
    return false;
390
0
391
0
  // The default assumption is that Polly improves the code.
392
0
  return true;
393
0
}
394
395
IslAst::IslAst(Scop *Scop)
396
    : S(Scop), Root(nullptr), RunCondition(nullptr),
397
410
      Ctx(Scop->getSharedIslCtx()) {}
398
399
410
void IslAst::init(const Dependences &D) {
400
364
  bool PerformParallelTest = PollyParallel || DetectParallel ||
401
332
                             PollyVectorizerChoice != VECTORIZER_NONE;
402
410
403
410
  // We can not perform the dependence analysis and, consequently,
404
410
  // the parallel code generation in case the schedule tree contains
405
410
  // extension nodes.
406
410
  auto *ScheduleTree = S->getScheduleTree();
407
410
  PerformParallelTest =
408
107
      PerformParallelTest && !S->containsExtensionNode(ScheduleTree);
409
410
  isl_schedule_free(ScheduleTree);
410
410
411
410
  // Skip AST and code generation if there was no benefit achieved.
412
410
  if (!benefitsFromPolly(S, PerformParallelTest))
413
0
    return;
414
410
415
410
  isl_ctx *Ctx = S->getIslCtx();
416
410
  isl_options_set_ast_build_atomic_upper_bound(Ctx, true);
417
410
  isl_options_set_ast_build_detect_min_max(Ctx, true);
418
410
  isl_ast_build *Build;
419
410
  AstBuildUserInfo BuildInfo;
420
410
421
410
  if (UseContext)
422
410
    Build = isl_ast_build_from_context(S->getContext());
423
410
  else
424
0
    Build = isl_ast_build_from_context(isl_set_universe(S->getParamSpace()));
425
410
426
410
  Build = isl_ast_build_set_at_each_domain(Build, AtEachDomain, nullptr);
427
410
428
410
  if (
PerformParallelTest410
)
{107
429
107
    BuildInfo.Deps = &D;
430
107
    BuildInfo.InParallelFor = 0;
431
107
432
107
    Build = isl_ast_build_set_before_each_for(Build, &astBuildBeforeFor,
433
107
                                              &BuildInfo);
434
107
    Build =
435
107
        isl_ast_build_set_after_each_for(Build, &astBuildAfterFor, &BuildInfo);
436
107
437
107
    Build = isl_ast_build_set_before_each_mark(Build, &astBuildBeforeMark,
438
107
                                               &BuildInfo);
439
107
440
107
    Build = isl_ast_build_set_after_each_mark(Build, &astBuildAfterMark,
441
107
                                              &BuildInfo);
442
107
  }
443
410
444
410
  RunCondition = buildRunCondition(S, Build);
445
410
446
410
  Root = isl_ast_build_node_from_schedule(Build, S->getScheduleTree());
447
410
448
410
  isl_ast_build_free(Build);
449
410
}
450
451
410
IslAst *IslAst::create(Scop *Scop, const Dependences &D) {
452
410
  auto Ast = new IslAst(Scop);
453
410
  Ast->init(D);
454
410
  return Ast;
455
410
}
456
457
410
IslAst::~IslAst() {
458
410
  isl_ast_node_free(Root);
459
410
  isl_ast_expr_free(RunCondition);
460
410
}
461
462
410
__isl_give isl_ast_node *IslAst::getAst() { return isl_ast_node_copy(Root); }
463
405
__isl_give isl_ast_expr *IslAst::getRunCondition() {
464
405
  return isl_ast_expr_copy(RunCondition);
465
405
}
466
467
1.58k
void IslAstInfo::releaseMemory() {
468
1.58k
  if (
Ast1.58k
)
{410
469
410
    delete Ast;
470
410
    Ast = nullptr;
471
410
  }
472
1.58k
}
473
474
410
bool IslAstInfo::runOnScop(Scop &Scop) {
475
410
  if (Ast)
476
0
    delete Ast;
477
410
478
410
  S = &Scop;
479
410
480
410
  const Dependences &D =
481
410
      getAnalysis<DependenceInfo>().getDependences(Dependences::AL_Statement);
482
410
483
410
  Ast = IslAst::create(&Scop, D);
484
410
485
410
  DEBUG(printScop(dbgs(), Scop));
486
410
  return false;
487
410
}
488
489
410
__isl_give isl_ast_node *IslAstInfo::getAst() const { return Ast->getAst(); }
490
405
__isl_give isl_ast_expr *IslAstInfo::getRunCondition() const {
491
405
  return Ast->getRunCondition();
492
405
}
493
494
2.47k
IslAstUserPayload *IslAstInfo::getNodePayload(__isl_keep isl_ast_node *Node) {
495
2.47k
  isl_id *Id = isl_ast_node_get_annotation(Node);
496
2.47k
  if (!Id)
497
1.23k
    return nullptr;
498
1.23k
  IslAstUserPayload *Payload = (IslAstUserPayload *)isl_id_get_user(Id);
499
1.23k
  isl_id_free(Id);
500
1.23k
  return Payload;
501
2.47k
}
502
503
30
bool IslAstInfo::isInnermost(__isl_keep isl_ast_node *Node) {
504
30
  IslAstUserPayload *Payload = getNodePayload(Node);
505
30
  return Payload && Payload->IsInnermost;
506
30
}
507
508
213
bool IslAstInfo::isParallel(__isl_keep isl_ast_node *Node) {
509
213
  return IslAstInfo::isInnermostParallel(Node) ||
510
200
         IslAstInfo::isOutermostParallel(Node);
511
213
}
512
513
607
bool IslAstInfo::isInnermostParallel(__isl_keep isl_ast_node *Node) {
514
607
  IslAstUserPayload *Payload = getNodePayload(Node);
515
206
  return Payload && Payload->IsInnermostParallel;
516
607
}
517
518
606
bool IslAstInfo::isOutermostParallel(__isl_keep isl_ast_node *Node) {
519
606
  IslAstUserPayload *Payload = getNodePayload(Node);
520
205
  return Payload && Payload->IsOutermostParallel;
521
606
}
522
523
80
bool IslAstInfo::isReductionParallel(__isl_keep isl_ast_node *Node) {
524
80
  IslAstUserPayload *Payload = getNodePayload(Node);
525
80
  return Payload && Payload->IsReductionParallel;
526
80
}
527
528
607
bool IslAstInfo::isExecutedInParallel(__isl_keep isl_ast_node *Node) {
529
607
530
607
  if (!PollyParallel)
531
537
    return false;
532
607
533
607
  // Do not parallelize innermost loops.
534
607
  //
535
607
  // Parallelizing innermost loops is often not profitable, especially if
536
607
  // they have a low number of iterations.
537
607
  //
538
607
  // TODO: Decide this based on the number of loop iterations that will be
539
607
  //       executed. This can possibly require run-time checks, which again
540
607
  //       raises the question of both run-time check overhead and code size
541
607
  //       costs.
542
70
  
if (70
!PollyParallelForce && 70
isInnermost(Node)30
)
543
14
    return false;
544
70
545
56
  
return isOutermostParallel(Node) && 56
!isReductionParallel(Node)44
;
546
70
}
547
548
__isl_give isl_union_map *
549
45
IslAstInfo::getSchedule(__isl_keep isl_ast_node *Node) {
550
45
  IslAstUserPayload *Payload = getNodePayload(Node);
551
45
  return Payload ? 
isl_ast_build_get_schedule(Payload->Build)45
:
nullptr0
;
552
45
}
553
554
__isl_give isl_pw_aff *
555
368
IslAstInfo::getMinimalDependenceDistance(__isl_keep isl_ast_node *Node) {
556
368
  IslAstUserPayload *Payload = getNodePayload(Node);
557
152
  return Payload ? isl_pw_aff_copy(Payload->MinimalDependenceDistance)
558
216
                 : nullptr;
559
368
}
560
561
IslAstInfo::MemoryAccessSet *
562
368
IslAstInfo::getBrokenReductions(__isl_keep isl_ast_node *Node) {
563
368
  IslAstUserPayload *Payload = getNodePayload(Node);
564
216
  return Payload ? 
&Payload->BrokenReductions152
:
nullptr216
;
565
368
}
566
567
369
isl_ast_build *IslAstInfo::getBuild(__isl_keep isl_ast_node *Node) {
568
369
  IslAstUserPayload *Payload = getNodePayload(Node);
569
369
  return Payload ? 
Payload->Build369
:
nullptr0
;
570
369
}
571
572
148
void IslAstInfo::printScop(raw_ostream &OS, Scop &S) const {
573
148
  isl_ast_print_options *Options;
574
148
  isl_ast_node *RootNode = getAst();
575
148
  Function &F = S.getFunction();
576
148
577
148
  OS << ":: isl ast :: " << F.getName() << " :: " << S.getNameStr() << "\n";
578
148
579
148
  if (
!RootNode148
)
{0
580
0
    OS << ":: isl ast generation and code generation was skipped!\n\n";
581
0
    OS << ":: This is either because no useful optimizations could be applied "
582
0
          "(use -polly-process-unprofitable to enforce code generation) or "
583
0
          "because earlier passes such as dependence analysis timed out (use "
584
0
          "-polly-dependences-computeout=0 to set dependence analysis timeout "
585
0
          "to infinity)\n\n";
586
0
    return;
587
0
  }
588
148
589
148
  isl_ast_expr *RunCondition = getRunCondition();
590
148
  char *RtCStr, *AstStr;
591
148
592
148
  Options = isl_ast_print_options_alloc(S.getIslCtx());
593
148
  Options = isl_ast_print_options_set_print_for(Options, cbPrintFor, nullptr);
594
148
595
148
  isl_printer *P = isl_printer_to_str(S.getIslCtx());
596
148
  P = isl_printer_set_output_format(P, ISL_FORMAT_C);
597
148
  P = isl_printer_print_ast_expr(P, RunCondition);
598
148
  RtCStr = isl_printer_get_str(P);
599
148
  P = isl_printer_flush(P);
600
148
  P = isl_printer_indent(P, 4);
601
148
  P = isl_ast_node_print(RootNode, P, Options);
602
148
  AstStr = isl_printer_get_str(P);
603
148
604
148
  auto *Schedule = S.getScheduleTree();
605
148
606
148
  DEBUG({
607
148
    dbgs() << S.getContextStr() << "\n";
608
148
    dbgs() << stringFromIslObj(Schedule);
609
148
  });
610
148
  OS << "\nif (" << RtCStr << ")\n\n";
611
148
  OS << AstStr << "\n";
612
148
  OS << "else\n";
613
148
  OS << "    {  /* original code */ }\n\n";
614
148
615
148
  free(RtCStr);
616
148
  free(AstStr);
617
148
618
148
  isl_ast_expr_free(RunCondition);
619
148
  isl_schedule_free(Schedule);
620
148
  isl_ast_node_free(RootNode);
621
148
  isl_printer_free(P);
622
148
}
623
624
435
void IslAstInfo::getAnalysisUsage(AnalysisUsage &AU) const {
625
435
  // Get the Common analysis usage of ScopPasses.
626
435
  ScopPass::getAnalysisUsage(AU);
627
435
  AU.addRequired<ScopInfoRegionPass>();
628
435
  AU.addRequired<DependenceInfo>();
629
435
}
630
631
char IslAstInfo::ID = 0;
632
633
0
Pass *polly::createIslAstInfoPass() { return new IslAstInfo(); }
634
635
39.7k
INITIALIZE_PASS_BEGIN39.7k
(IslAstInfo, "polly-ast",39.7k
636
39.7k
                      "Polly - Generate an AST of the SCoP (isl)", false,
637
39.7k
                      false);
638
39.7k
INITIALIZE_PASS_DEPENDENCY(ScopInfoRegionPass);
639
39.7k
INITIALIZE_PASS_DEPENDENCY(DependenceInfo);
640
39.7k
INITIALIZE_PASS_END(IslAstInfo, "polly-ast",
641
                    "Polly - Generate an AST from the SCoP (isl)", false, false)