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