1//===------ LoopGeneratorsGOMP.cpp - IR helper to create loops ------------===//
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 functions to create parallel loops as LLVM-IR.
10//
11//===----------------------------------------------------------------------===//
12
13#include "polly/CodeGen/LoopGeneratorsGOMP.h"
14#include "llvm/IR/Dominators.h"
15#include "llvm/IR/Module.h"
16
17using namespace llvm;
18using namespace polly;
19
20void ParallelLoopGeneratorGOMP::createCallSpawnThreads(Value *SubFn,
21 Value *SubFnParam,
22 Value *LB, Value *UB,
23 Value *Stride) {
24 const std::string Name = "GOMP_parallel_loop_runtime_start";
25
26 Function *F = M->getFunction(Name);
27
28 // If F is not available, declare it.
29 if (!F) {
30 GlobalValue::LinkageTypes Linkage = Function::ExternalLinkage;
31
32 Type *Params[] = {PointerType::getUnqual(ElementType: FunctionType::get(
33 Result: Builder.getVoidTy(), Params: Builder.getPtrTy(), isVarArg: false)),
34 Builder.getPtrTy(),
35 Builder.getInt32Ty(),
36 LongType,
37 LongType,
38 LongType};
39
40 FunctionType *Ty = FunctionType::get(Result: Builder.getVoidTy(), Params, isVarArg: false);
41 F = Function::Create(Ty, Linkage, N: Name, M);
42 }
43
44 Value *Args[] = {SubFn, SubFnParam, Builder.getInt32(C: PollyNumThreads),
45 LB, UB, Stride};
46
47 CallInst *Call = Builder.CreateCall(Callee: F, Args);
48 Call->setDebugLoc(DLGenerated);
49}
50
51void ParallelLoopGeneratorGOMP::deployParallelExecution(Function *SubFn,
52 Value *SubFnParam,
53 Value *LB, Value *UB,
54 Value *Stride) {
55 // Tell the runtime we start a parallel loop
56 createCallSpawnThreads(SubFn, SubFnParam, LB, UB, Stride);
57 CallInst *Call = Builder.CreateCall(Callee: SubFn, Args: SubFnParam);
58 Call->setDebugLoc(DLGenerated);
59 createCallJoinThreads();
60}
61
62Function *ParallelLoopGeneratorGOMP::prepareSubFnDefinition(Function *F) const {
63 FunctionType *FT =
64 FunctionType::get(Result: Builder.getVoidTy(), Params: {Builder.getPtrTy()}, isVarArg: false);
65 Function *SubFn = Function::Create(Ty: FT, Linkage: Function::InternalLinkage,
66 N: F->getName() + "_polly_subfn", M);
67 // Name the function's arguments
68 SubFn->arg_begin()->setName("polly.par.userContext");
69 return SubFn;
70}
71
72// Create a subfunction of the following (preliminary) structure:
73//
74// PrevBB
75// |
76// v
77// HeaderBB
78// | _____
79// v v |
80// CheckNextBB PreHeaderBB
81// |\ |
82// | \______/
83// |
84// v
85// ExitBB
86//
87// HeaderBB will hold allocations and loading of variables.
88// CheckNextBB will check for more work.
89// If there is more work to do: go to PreHeaderBB, otherwise go to ExitBB.
90// PreHeaderBB loads the new boundaries (& will lead to the loop body later on).
91// ExitBB marks the end of the parallel execution.
92std::tuple<Value *, Function *>
93ParallelLoopGeneratorGOMP::createSubFn(Value *Stride, AllocaInst *StructData,
94 SetVector<Value *> Data,
95 ValueMapT &Map) {
96 if (PollyScheduling != OMPGeneralSchedulingType::Runtime) {
97 // User tried to influence the scheduling type (currently not supported)
98 errs() << "warning: Polly's GNU OpenMP backend solely "
99 "supports the scheduling type 'runtime'.\n";
100 }
101
102 if (PollyChunkSize != 0) {
103 // User tried to influence the chunk size (currently not supported)
104 errs() << "warning: Polly's GNU OpenMP backend solely "
105 "supports the default chunk size.\n";
106 }
107
108 Function *SubFn = createSubFnDefinition();
109 LLVMContext &Context = SubFn->getContext();
110
111 // Store the previous basic block.
112 BasicBlock *PrevBB = Builder.GetInsertBlock();
113
114 // Create basic blocks.
115 BasicBlock *HeaderBB = BasicBlock::Create(Context, Name: "polly.par.setup", Parent: SubFn);
116 BasicBlock *ExitBB = BasicBlock::Create(Context, Name: "polly.par.exit", Parent: SubFn);
117 BasicBlock *CheckNextBB =
118 BasicBlock::Create(Context, Name: "polly.par.checkNext", Parent: SubFn);
119 BasicBlock *PreHeaderBB =
120 BasicBlock::Create(Context, Name: "polly.par.loadIVBounds", Parent: SubFn);
121
122 DT.addNewBlock(BB: HeaderBB, DomBB: PrevBB);
123 DT.addNewBlock(BB: ExitBB, DomBB: HeaderBB);
124 DT.addNewBlock(BB: CheckNextBB, DomBB: HeaderBB);
125 DT.addNewBlock(BB: PreHeaderBB, DomBB: HeaderBB);
126
127 // Fill up basic block HeaderBB.
128 Builder.SetInsertPoint(HeaderBB);
129 Value *LBPtr = Builder.CreateAlloca(Ty: LongType, ArraySize: nullptr, Name: "polly.par.LBPtr");
130 Value *UBPtr = Builder.CreateAlloca(Ty: LongType, ArraySize: nullptr, Name: "polly.par.UBPtr");
131 Value *UserContext = &*SubFn->arg_begin();
132
133 extractValuesFromStruct(Values: Data, Ty: StructData->getAllocatedType(), Struct: UserContext,
134 VMap&: Map);
135 Builder.CreateBr(Dest: CheckNextBB);
136
137 // Add code to check if another set of iterations will be executed.
138 Builder.SetInsertPoint(CheckNextBB);
139 Value *Next = createCallGetWorkItem(LBPtr, UBPtr);
140 Value *HasNextSchedule = Builder.CreateTrunc(
141 V: Next, DestTy: Builder.getInt1Ty(), Name: "polly.par.hasNextScheduleBlock");
142 Builder.CreateCondBr(Cond: HasNextSchedule, True: PreHeaderBB, False: ExitBB);
143
144 // Add code to load the iv bounds for this set of iterations.
145 Builder.SetInsertPoint(PreHeaderBB);
146 Value *LB = Builder.CreateLoad(Ty: LongType, Ptr: LBPtr, Name: "polly.par.LB");
147 Value *UB = Builder.CreateLoad(Ty: LongType, Ptr: UBPtr, Name: "polly.par.UB");
148
149 // Subtract one as the upper bound provided by OpenMP is a < comparison
150 // whereas the codegenForSequential function creates a <= comparison.
151 UB = Builder.CreateSub(LHS: UB, RHS: ConstantInt::get(Ty: LongType, V: 1),
152 Name: "polly.par.UBAdjusted");
153
154 Builder.CreateBr(Dest: CheckNextBB);
155 Builder.SetInsertPoint(&*--Builder.GetInsertPoint());
156 BasicBlock *AfterBB;
157 Value *IV =
158 createLoop(LowerBound: LB, UpperBound: UB, Stride, Builder, LI, DT, ExitBlock&: AfterBB, Predicate: ICmpInst::ICMP_SLE,
159 Annotator: nullptr, Parallel: true, /* UseGuard */ false);
160
161 BasicBlock::iterator LoopBody = Builder.GetInsertPoint();
162
163 // Add code to terminate this subfunction.
164 Builder.SetInsertPoint(ExitBB);
165 createCallCleanupThread();
166 Builder.CreateRetVoid();
167
168 Builder.SetInsertPoint(&*LoopBody);
169
170 return std::make_tuple(args&: IV, args&: SubFn);
171}
172
173Value *ParallelLoopGeneratorGOMP::createCallGetWorkItem(Value *LBPtr,
174 Value *UBPtr) {
175 const std::string Name = "GOMP_loop_runtime_next";
176
177 Function *F = M->getFunction(Name);
178
179 // If F is not available, declare it.
180 if (!F) {
181 GlobalValue::LinkageTypes Linkage = Function::ExternalLinkage;
182 Type *Params[] = {LongType->getPointerTo(), LongType->getPointerTo()};
183 FunctionType *Ty = FunctionType::get(Result: Builder.getInt8Ty(), Params, isVarArg: false);
184 F = Function::Create(Ty, Linkage, N: Name, M);
185 }
186
187 Value *Args[] = {LBPtr, UBPtr};
188 CallInst *Call = Builder.CreateCall(Callee: F, Args);
189 Call->setDebugLoc(DLGenerated);
190 Value *Return = Builder.CreateICmpNE(
191 LHS: Call, RHS: Builder.CreateZExt(V: Builder.getFalse(), DestTy: Call->getType()));
192 return Return;
193}
194
195void ParallelLoopGeneratorGOMP::createCallJoinThreads() {
196 const std::string Name = "GOMP_parallel_end";
197
198 Function *F = M->getFunction(Name);
199
200 // If F is not available, declare it.
201 if (!F) {
202 GlobalValue::LinkageTypes Linkage = Function::ExternalLinkage;
203
204 FunctionType *Ty = FunctionType::get(Result: Builder.getVoidTy(), isVarArg: false);
205 F = Function::Create(Ty, Linkage, N: Name, M);
206 }
207
208 CallInst *Call = Builder.CreateCall(Callee: F, Args: {});
209 Call->setDebugLoc(DLGenerated);
210}
211
212void ParallelLoopGeneratorGOMP::createCallCleanupThread() {
213 const std::string Name = "GOMP_loop_end_nowait";
214
215 Function *F = M->getFunction(Name);
216
217 // If F is not available, declare it.
218 if (!F) {
219 GlobalValue::LinkageTypes Linkage = Function::ExternalLinkage;
220
221 FunctionType *Ty = FunctionType::get(Result: Builder.getVoidTy(), isVarArg: false);
222 F = Function::Create(Ty, Linkage, N: Name, M);
223 }
224
225 CallInst *Call = Builder.CreateCall(Callee: F, Args: {});
226 Call->setDebugLoc(DLGenerated);
227}
228

source code of polly/lib/CodeGen/LoopGeneratorsGOMP.cpp