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