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