1 //===------ LoopGenerators.cpp -  IR helper to create loops ---------------===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file contains functions to create scalar and OpenMP parallel loops
11 // as LLVM-IR.
12 //
13 //===----------------------------------------------------------------------===//
14 
15 #include "polly/LoopGenerators.h"
16 #include "polly/ScopDetection.h"
17 
18 #include "llvm/Module.h"
19 #include "llvm/Analysis/Dominators.h"
20 #include "llvm/Target/TargetData.h"
21 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
22 
23 using namespace llvm;
24 
25 Value *createLoop(Value *LB, Value *UB, Value *Stride,
26                   IRBuilder<> *Builder, Pass *P, BasicBlock **AfterBlock) {
27   DominatorTree &DT = P->getAnalysis<DominatorTree>();
28   Function *F = Builder->GetInsertBlock()->getParent();
29   LLVMContext &Context = F->getContext();
30 
31   BasicBlock *PreheaderBB = Builder->GetInsertBlock();
32   BasicBlock *HeaderBB = BasicBlock::Create(Context, "polly.loop_header", F);
33   BasicBlock *BodyBB = BasicBlock::Create(Context, "polly.loop_body", F);
34   BasicBlock *AfterBB = SplitBlock(PreheaderBB, Builder->GetInsertPoint()++, P);
35   AfterBB->setName("polly.loop_after");
36 
37   PreheaderBB->getTerminator()->setSuccessor(0, HeaderBB);
38   DT.addNewBlock(HeaderBB, PreheaderBB);
39 
40   Builder->SetInsertPoint(HeaderBB);
41 
42   // Use the type of upper and lower bound.
43   assert(LB->getType() == UB->getType()
44          && "Different types for upper and lower bound.");
45 
46   IntegerType *LoopIVType = dyn_cast<IntegerType>(UB->getType());
47   assert(LoopIVType && "UB is not integer?");
48 
49   // IV
50   PHINode *IV = Builder->CreatePHI(LoopIVType, 2, "polly.loopiv");
51   IV->addIncoming(LB, PreheaderBB);
52 
53   Stride = Builder->CreateZExtOrBitCast(Stride, LoopIVType);
54   Value *IncrementedIV = Builder->CreateAdd(IV, Stride, "polly.next_loopiv");
55 
56   // Exit condition.
57   Value *CMP;
58   CMP = Builder->CreateICmpSLE(IV, UB);
59 
60   Builder->CreateCondBr(CMP, BodyBB, AfterBB);
61   DT.addNewBlock(BodyBB, HeaderBB);
62 
63   Builder->SetInsertPoint(BodyBB);
64   Builder->CreateBr(HeaderBB);
65   IV->addIncoming(IncrementedIV, BodyBB);
66   DT.changeImmediateDominator(AfterBB, HeaderBB);
67 
68   Builder->SetInsertPoint(BodyBB->begin());
69   *AfterBlock = AfterBB;
70 
71   return IV;
72 }
73 
74 void OMPGenerator::createCallParallelLoopStart(Value *SubFunction,
75                                                Value *SubfunctionParam,
76                                                Value *NumberOfThreads,
77                                                Value *LowerBound,
78                                                Value *UpperBound,
79                                                Value *Stride) {
80   Module *M = getModule();
81   const char *Name = "GOMP_parallel_loop_runtime_start";
82   Function *F = M->getFunction(Name);
83 
84   // If F is not available, declare it.
85   if (!F) {
86     Type *LongTy = getIntPtrTy();
87     GlobalValue::LinkageTypes Linkage = Function::ExternalLinkage;
88 
89     Type *Params[] = {
90       PointerType::getUnqual(FunctionType::get(Builder.getVoidTy(),
91                                                Builder.getInt8PtrTy(),
92                                                false)),
93       Builder.getInt8PtrTy(),
94       Builder.getInt32Ty(),
95       LongTy,
96       LongTy,
97       LongTy,
98     };
99 
100     FunctionType *Ty = FunctionType::get(Builder.getVoidTy(), Params, false);
101     F = Function::Create(Ty, Linkage, Name, M);
102   }
103 
104   Value *Args[] = {
105     SubFunction,
106     SubfunctionParam,
107     NumberOfThreads,
108     LowerBound,
109     UpperBound,
110     Stride,
111   };
112 
113   Builder.CreateCall(F, Args);
114 }
115 
116 Value *OMPGenerator::createCallLoopNext(Value *LowerBoundPtr,
117                                         Value *UpperBoundPtr) {
118   Module *M = getModule();
119   const char *Name = "GOMP_loop_runtime_next";
120   Function *F = M->getFunction(Name);
121 
122   // If F is not available, declare it.
123   if (!F) {
124     Type *LongPtrTy = PointerType::getUnqual(getIntPtrTy());
125     GlobalValue::LinkageTypes Linkage = Function::ExternalLinkage;
126 
127     Type *Params[] = {
128       LongPtrTy,
129       LongPtrTy,
130     };
131 
132     FunctionType *Ty = FunctionType::get(Builder.getInt8Ty(), Params, false);
133     F = Function::Create(Ty, Linkage, Name, M);
134   }
135 
136   Value *Args[] = {
137     LowerBoundPtr,
138     UpperBoundPtr,
139   };
140 
141   Value *Return = Builder.CreateCall(F, Args);
142   Return = Builder.CreateICmpNE(Return, Builder.CreateZExt(Builder.getFalse(),
143                                                            Return->getType()));
144   return Return;
145 }
146 
147 void OMPGenerator::createCallParallelEnd() {
148   const char *Name = "GOMP_parallel_end";
149   Module *M = getModule();
150   Function *F = M->getFunction(Name);
151 
152   // If F is not available, declare it.
153   if (!F) {
154     GlobalValue::LinkageTypes Linkage = Function::ExternalLinkage;
155 
156     FunctionType *Ty = FunctionType::get(Builder.getVoidTy(), false);
157     F = Function::Create(Ty, Linkage, Name, M);
158   }
159 
160   Builder.CreateCall(F);
161 }
162 
163 void OMPGenerator::createCallLoopEndNowait() {
164   const char *Name = "GOMP_loop_end_nowait";
165   Module *M = getModule();
166   Function *F = M->getFunction(Name);
167 
168   // If F is not available, declare it.
169   if (!F) {
170     GlobalValue::LinkageTypes Linkage = Function::ExternalLinkage;
171 
172     FunctionType *Ty = FunctionType::get(Builder.getVoidTy(), false);
173     F = Function::Create(Ty, Linkage, Name, M);
174   }
175 
176   Builder.CreateCall(F);
177 }
178 
179 IntegerType *OMPGenerator::getIntPtrTy() {
180   return P->getAnalysis<TargetData>().getIntPtrType(Builder.getContext());
181 }
182 
183 Module *OMPGenerator::getModule() {
184   return Builder.GetInsertBlock()->getParent()->getParent();
185 }
186 
187 Function *OMPGenerator::createSubfunctionDefinition() {
188   Module *M = getModule();
189   Function *F = Builder.GetInsertBlock()->getParent();
190   std::vector<Type*> Arguments(1, Builder.getInt8PtrTy());
191   FunctionType *FT = FunctionType::get(Builder.getVoidTy(), Arguments, false);
192   Function *FN = Function::Create(FT, Function::InternalLinkage,
193                                   F->getName() + ".omp_subfn", M);
194   // Do not run any polly pass on the new function.
195   P->getAnalysis<polly::ScopDetection>().markFunctionAsInvalid(FN);
196 
197   Function::arg_iterator AI = FN->arg_begin();
198   AI->setName("omp.userContext");
199 
200   return FN;
201 }
202 
203 Value *OMPGenerator::loadValuesIntoStruct(SetVector<Value*> &Values) {
204   std::vector<Type*> Members;
205 
206   for (unsigned i = 0; i < Values.size(); i++)
207     Members.push_back(Values[i]->getType());
208 
209   StructType *Ty = StructType::get(Builder.getContext(), Members);
210   Value *Struct = Builder.CreateAlloca(Ty, 0, "omp.userContext");
211 
212   for (unsigned i = 0; i < Values.size(); i++) {
213     Value *Address = Builder.CreateStructGEP(Struct, i);
214     Builder.CreateStore(Values[i], Address);
215   }
216 
217   return Struct;
218 }
219 
220 void OMPGenerator::extractValuesFromStruct(SetVector<Value*> OldValues,
221                                            Value *Struct,
222                                            ValueToValueMapTy &Map) {
223   for (unsigned i = 0; i < OldValues.size(); i++) {
224     Value *Address = Builder.CreateStructGEP(Struct, i);
225     Value *NewValue = Builder.CreateLoad(Address);
226     Map.insert(std::make_pair<Value*, Value*>(OldValues[i], NewValue));
227   }
228 }
229 
230 Value *OMPGenerator::createSubfunction(Value *Stride, Value *StructData,
231                                        SetVector<Value*> Data,
232                                        ValueToValueMapTy &Map,
233                                        Function **SubFunction) {
234   Function *FN = createSubfunctionDefinition();
235 
236   BasicBlock *PrevBB, *HeaderBB, *ExitBB, *CheckNextBB, *LoadIVBoundsBB,
237              *AfterBB;
238   Value *LowerBoundPtr, *UpperBoundPtr, *UserContext, *Ret1, *HasNextSchedule,
239         *LowerBound, *UpperBound, *IV;
240   Type *IntPtrTy = getIntPtrTy();
241   LLVMContext &Context = FN->getContext();
242 
243   // Store the previous basic block.
244   PrevBB = Builder.GetInsertBlock();
245 
246   // Create basic blocks.
247   HeaderBB = BasicBlock::Create(Context, "omp.setup", FN);
248   ExitBB = BasicBlock::Create(Context, "omp.exit", FN);
249   CheckNextBB = BasicBlock::Create(Context, "omp.checkNext", FN);
250   LoadIVBoundsBB = BasicBlock::Create(Context, "omp.loadIVBounds", FN);
251 
252   DominatorTree &DT = P->getAnalysis<DominatorTree>();
253   DT.addNewBlock(HeaderBB, PrevBB);
254   DT.addNewBlock(ExitBB, HeaderBB);
255   DT.addNewBlock(CheckNextBB, HeaderBB);
256   DT.addNewBlock(LoadIVBoundsBB, HeaderBB);
257 
258   // Fill up basic block HeaderBB.
259   Builder.SetInsertPoint(HeaderBB);
260   LowerBoundPtr = Builder.CreateAlloca(IntPtrTy, 0, "omp.lowerBoundPtr");
261   UpperBoundPtr = Builder.CreateAlloca(IntPtrTy, 0, "omp.upperBoundPtr");
262   UserContext = Builder.CreateBitCast(FN->arg_begin(), StructData->getType(),
263                                       "omp.userContext");
264 
265   extractValuesFromStruct(Data, UserContext, Map);
266   Builder.CreateBr(CheckNextBB);
267 
268   // Add code to check if another set of iterations will be executed.
269   Builder.SetInsertPoint(CheckNextBB);
270   Ret1 = createCallLoopNext(LowerBoundPtr, UpperBoundPtr);
271   HasNextSchedule = Builder.CreateTrunc(Ret1, Builder.getInt1Ty(),
272                                         "omp.hasNextScheduleBlock");
273   Builder.CreateCondBr(HasNextSchedule, LoadIVBoundsBB, ExitBB);
274 
275   // Add code to to load the iv bounds for this set of iterations.
276   Builder.SetInsertPoint(LoadIVBoundsBB);
277   LowerBound = Builder.CreateLoad(LowerBoundPtr, "omp.lowerBound");
278   UpperBound = Builder.CreateLoad(UpperBoundPtr, "omp.upperBound");
279 
280   // Subtract one as the upper bound provided by openmp is a < comparison
281   // whereas the codegenForSequential function creates a <= comparison.
282   UpperBound = Builder.CreateSub(UpperBound, ConstantInt::get(IntPtrTy, 1),
283                                  "omp.upperBoundAdjusted");
284 
285   Builder.CreateBr(CheckNextBB);
286   Builder.SetInsertPoint(--Builder.GetInsertPoint());
287   IV = createLoop(LowerBound, UpperBound, Stride, &Builder, P, &AfterBB);
288 
289   BasicBlock::iterator LoopBody = Builder.GetInsertPoint();
290   Builder.SetInsertPoint(AfterBB->begin());
291 
292   // Add code to terminate this openmp subfunction.
293   Builder.SetInsertPoint(ExitBB);
294   createCallLoopEndNowait();
295   Builder.CreateRetVoid();
296 
297   Builder.SetInsertPoint(LoopBody);
298   *SubFunction = FN;
299 
300   return IV;
301 }
302 
303 Value *OMPGenerator::createParallelLoop(Value *LowerBound, Value *UpperBound,
304                                         Value *Stride,
305                                         SetVector<Value*> &Values,
306                                         ValueToValueMapTy &Map,
307                                         BasicBlock::iterator *LoopBody) {
308   Value *Struct, *IV, *SubfunctionParam, *NumberOfThreads;
309   Function *SubFunction;
310 
311   Struct = loadValuesIntoStruct(Values);
312 
313   BasicBlock::iterator PrevInsertPoint = Builder.GetInsertPoint();
314   IV = createSubfunction(Stride, Struct, Values, Map, &SubFunction);
315   *LoopBody = Builder.GetInsertPoint();
316   Builder.SetInsertPoint(PrevInsertPoint);
317 
318   // Create call for GOMP_parallel_loop_runtime_start.
319   SubfunctionParam = Builder.CreateBitCast(Struct, Builder.getInt8PtrTy(),
320                                            "omp_data");
321 
322   NumberOfThreads = Builder.getInt32(0);
323 
324   // Add one as the upper bound provided by openmp is a < comparison
325   // whereas the codegenForSequential function creates a <= comparison.
326   UpperBound = Builder.CreateAdd(UpperBound,
327                                  ConstantInt::get(getIntPtrTy(), 1));
328 
329   createCallParallelLoopStart(SubFunction, SubfunctionParam, NumberOfThreads,
330                               LowerBound, UpperBound, Stride);
331   Builder.CreateCall(SubFunction, SubfunctionParam);
332   createCallParallelEnd();
333 
334   return IV;
335 }
336