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/ScopDetection.h"
16 #include "polly/CodeGen/LoopGenerators.h"
17 #include "llvm/Analysis/LoopInfo.h"
18 #include "llvm/IR/DataLayout.h"
19 #include "llvm/IR/Dominators.h"
20 #include "llvm/IR/Module.h"
21 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
22 
23 using namespace llvm;
24 using namespace polly;
25 
26 // We generate a loop of either of the following structures:
27 //
28 //              BeforeBB                      BeforeBB
29 //                 |                             |
30 //                 v                             v
31 //              GuardBB                      PreHeaderBB
32 //              /      |                         |   _____
33 //     __  PreHeaderBB  |                        v  \/    |
34 //    /  \    /         |                     HeaderBB  latch
35 // latch  HeaderBB      |                        |\       |
36 //    \  /    \         /                        | \------/
37 //     <       \       /                         |
38 //              \     /                          v
39 //              ExitBB                         ExitBB
40 //
41 // depending on whether or not we know that it is executed at least once. If
42 // not, GuardBB checks if the loop is executed at least once. If this is the
43 // case we branch to PreHeaderBB and subsequently to the HeaderBB, which
44 // contains the loop iv 'polly.indvar', the incremented loop iv
45 // 'polly.indvar_next' as well as the condition to check if we execute another
46 // iteration of the loop. After the loop has finished, we branch to ExitBB.
47 Value *polly::createLoop(Value *LB, Value *UB, Value *Stride,
48                          PollyIRBuilder &Builder, Pass *P, LoopInfo &LI,
49                          DominatorTree &DT, BasicBlock *&ExitBB,
50                          ICmpInst::Predicate Predicate,
51                          LoopAnnotator *Annotator, bool Parallel,
52                          bool UseGuard) {
53   Function *F = Builder.GetInsertBlock()->getParent();
54   LLVMContext &Context = F->getContext();
55 
56   assert(LB->getType() == UB->getType() && "Types of loop bounds do not match");
57   IntegerType *LoopIVType = dyn_cast<IntegerType>(UB->getType());
58   assert(LoopIVType && "UB is not integer?");
59 
60   BasicBlock *BeforeBB = Builder.GetInsertBlock();
61   BasicBlock *GuardBB =
62       UseGuard ? BasicBlock::Create(Context, "polly.loop_if", F) : nullptr;
63   BasicBlock *HeaderBB = BasicBlock::Create(Context, "polly.loop_header", F);
64   BasicBlock *PreHeaderBB =
65       BasicBlock::Create(Context, "polly.loop_preheader", F);
66 
67   // Update LoopInfo
68   Loop *OuterLoop = LI.getLoopFor(BeforeBB);
69   Loop *NewLoop = new Loop();
70 
71   if (OuterLoop)
72     OuterLoop->addChildLoop(NewLoop);
73   else
74     LI.addTopLevelLoop(NewLoop);
75 
76   if (OuterLoop && GuardBB)
77     OuterLoop->addBasicBlockToLoop(GuardBB, LI.getBase());
78   else if (OuterLoop)
79     OuterLoop->addBasicBlockToLoop(PreHeaderBB, LI.getBase());
80 
81   NewLoop->addBasicBlockToLoop(HeaderBB, LI.getBase());
82 
83   // Notify the annotator (if present) that we have a new loop, but only
84   // after the header block is set.
85   if (Annotator)
86     Annotator->pushLoop(NewLoop, Parallel);
87 
88   // ExitBB
89   ExitBB = SplitBlock(BeforeBB, Builder.GetInsertPoint()++, P);
90   ExitBB->setName("polly.loop_exit");
91 
92   // BeforeBB
93   if (GuardBB) {
94     BeforeBB->getTerminator()->setSuccessor(0, GuardBB);
95     DT.addNewBlock(GuardBB, BeforeBB);
96 
97     // GuardBB
98     Builder.SetInsertPoint(GuardBB);
99     Value *LoopGuard;
100     LoopGuard = Builder.CreateICmp(Predicate, LB, UB);
101     LoopGuard->setName("polly.loop_guard");
102     Builder.CreateCondBr(LoopGuard, PreHeaderBB, ExitBB);
103     DT.addNewBlock(PreHeaderBB, GuardBB);
104   } else {
105     BeforeBB->getTerminator()->setSuccessor(0, PreHeaderBB);
106     DT.addNewBlock(PreHeaderBB, BeforeBB);
107   }
108 
109   // PreHeaderBB
110   Builder.SetInsertPoint(PreHeaderBB);
111   Builder.CreateBr(HeaderBB);
112 
113   // HeaderBB
114   DT.addNewBlock(HeaderBB, PreHeaderBB);
115   Builder.SetInsertPoint(HeaderBB);
116   PHINode *IV = Builder.CreatePHI(LoopIVType, 2, "polly.indvar");
117   IV->addIncoming(LB, PreHeaderBB);
118   Stride = Builder.CreateZExtOrBitCast(Stride, LoopIVType);
119   Value *IncrementedIV = Builder.CreateNSWAdd(IV, Stride, "polly.indvar_next");
120   Value *LoopCondition;
121   UB = Builder.CreateSub(UB, Stride, "polly.adjust_ub");
122   LoopCondition = Builder.CreateICmp(Predicate, IV, UB);
123   LoopCondition->setName("polly.loop_cond");
124 
125   // Create the loop latch and annotate it as such.
126   BranchInst *B = Builder.CreateCondBr(LoopCondition, HeaderBB, ExitBB);
127   if (Annotator)
128     Annotator->annotateLoopLatch(B, NewLoop, Parallel);
129 
130   IV->addIncoming(IncrementedIV, HeaderBB);
131   if (GuardBB)
132     DT.changeImmediateDominator(ExitBB, GuardBB);
133   else
134     DT.changeImmediateDominator(ExitBB, HeaderBB);
135 
136   // The loop body should be added here.
137   Builder.SetInsertPoint(HeaderBB->getFirstNonPHI());
138   return IV;
139 }
140 
141 void OMPGenerator::createCallParallelLoopStart(
142     Value *SubFunction, Value *SubfunctionParam, Value *NumberOfThreads,
143     Value *LowerBound, Value *UpperBound, Value *Stride) {
144   Module *M = getModule();
145   const char *Name = "GOMP_parallel_loop_runtime_start";
146   Function *F = M->getFunction(Name);
147 
148   // If F is not available, declare it.
149   if (!F) {
150     Type *LongTy = getIntPtrTy();
151     GlobalValue::LinkageTypes Linkage = Function::ExternalLinkage;
152 
153     Type *Params[] = {PointerType::getUnqual(FunctionType::get(
154                           Builder.getVoidTy(), Builder.getInt8PtrTy(), false)),
155                       Builder.getInt8PtrTy(), Builder.getInt32Ty(), LongTy,
156                       LongTy, LongTy};
157 
158     FunctionType *Ty = FunctionType::get(Builder.getVoidTy(), Params, false);
159     F = Function::Create(Ty, Linkage, Name, M);
160   }
161 
162   Value *Args[] = {SubFunction, SubfunctionParam, NumberOfThreads,
163                    LowerBound,  UpperBound,       Stride};
164 
165   Builder.CreateCall(F, Args);
166 }
167 
168 Value *OMPGenerator::createCallLoopNext(Value *LowerBoundPtr,
169                                         Value *UpperBoundPtr) {
170   Module *M = getModule();
171   const char *Name = "GOMP_loop_runtime_next";
172   Function *F = M->getFunction(Name);
173 
174   // If F is not available, declare it.
175   if (!F) {
176     Type *LongPtrTy = PointerType::getUnqual(getIntPtrTy());
177     GlobalValue::LinkageTypes Linkage = Function::ExternalLinkage;
178 
179     Type *Params[] = {LongPtrTy, LongPtrTy};
180 
181     FunctionType *Ty = FunctionType::get(Builder.getInt8Ty(), Params, false);
182     F = Function::Create(Ty, Linkage, Name, M);
183   }
184 
185   Value *Args[] = {LowerBoundPtr, UpperBoundPtr};
186 
187   Value *Return = Builder.CreateCall(F, Args);
188   Return = Builder.CreateICmpNE(
189       Return, Builder.CreateZExt(Builder.getFalse(), Return->getType()));
190   return Return;
191 }
192 
193 void OMPGenerator::createCallParallelEnd() {
194   const char *Name = "GOMP_parallel_end";
195   Module *M = getModule();
196   Function *F = M->getFunction(Name);
197 
198   // If F is not available, declare it.
199   if (!F) {
200     GlobalValue::LinkageTypes Linkage = Function::ExternalLinkage;
201 
202     FunctionType *Ty = FunctionType::get(Builder.getVoidTy(), false);
203     F = Function::Create(Ty, Linkage, Name, M);
204   }
205 
206   Builder.CreateCall(F);
207 }
208 
209 void OMPGenerator::createCallLoopEndNowait() {
210   const char *Name = "GOMP_loop_end_nowait";
211   Module *M = getModule();
212   Function *F = M->getFunction(Name);
213 
214   // If F is not available, declare it.
215   if (!F) {
216     GlobalValue::LinkageTypes Linkage = Function::ExternalLinkage;
217 
218     FunctionType *Ty = FunctionType::get(Builder.getVoidTy(), false);
219     F = Function::Create(Ty, Linkage, Name, M);
220   }
221 
222   Builder.CreateCall(F);
223 }
224 
225 IntegerType *OMPGenerator::getIntPtrTy() {
226   return P->getAnalysis<DataLayoutPass>().getDataLayout().getIntPtrType(
227       Builder.getContext());
228 }
229 
230 Module *OMPGenerator::getModule() {
231   return Builder.GetInsertBlock()->getParent()->getParent();
232 }
233 
234 Function *OMPGenerator::createSubfunctionDefinition() {
235   Module *M = getModule();
236   Function *F = Builder.GetInsertBlock()->getParent();
237   std::vector<Type *> Arguments(1, Builder.getInt8PtrTy());
238   FunctionType *FT = FunctionType::get(Builder.getVoidTy(), Arguments, false);
239   Function *FN = Function::Create(FT, Function::InternalLinkage,
240                                   F->getName() + ".omp_subfn", M);
241   // Do not run any polly pass on the new function.
242   FN->addFnAttr(PollySkipFnAttr);
243 
244   Function::arg_iterator AI = FN->arg_begin();
245   AI->setName("omp.userContext");
246 
247   return FN;
248 }
249 
250 Value *OMPGenerator::loadValuesIntoStruct(SetVector<Value *> &Values) {
251   std::vector<Type *> Members;
252 
253   for (Value *V : Values)
254     Members.push_back(V->getType());
255 
256   StructType *Ty = StructType::get(Builder.getContext(), Members);
257   Value *Struct = Builder.CreateAlloca(Ty, 0, "omp.userContext");
258 
259   for (unsigned i = 0; i < Values.size(); i++) {
260     Value *Address = Builder.CreateStructGEP(Struct, i);
261     Builder.CreateStore(Values[i], Address);
262   }
263 
264   return Struct;
265 }
266 
267 void OMPGenerator::extractValuesFromStruct(SetVector<Value *> OldValues,
268                                            Value *Struct,
269                                            ValueToValueMapTy &Map) {
270   for (unsigned i = 0; i < OldValues.size(); i++) {
271     Value *Address = Builder.CreateStructGEP(Struct, i);
272     Value *NewValue = Builder.CreateLoad(Address);
273     Map.insert(std::make_pair(OldValues[i], NewValue));
274   }
275 }
276 
277 Value *OMPGenerator::createSubfunction(Value *Stride, Value *StructData,
278                                        SetVector<Value *> Data,
279                                        ValueToValueMapTy &Map,
280                                        Function **SubFunction) {
281   Function *FN = createSubfunctionDefinition();
282 
283   BasicBlock *PrevBB, *HeaderBB, *ExitBB, *CheckNextBB, *LoadIVBoundsBB,
284       *AfterBB;
285   Value *LowerBoundPtr, *UpperBoundPtr, *UserContext, *Ret1, *HasNextSchedule,
286       *LowerBound, *UpperBound, *IV;
287   Type *IntPtrTy = getIntPtrTy();
288   LLVMContext &Context = FN->getContext();
289 
290   // Store the previous basic block.
291   PrevBB = Builder.GetInsertBlock();
292 
293   // Create basic blocks.
294   HeaderBB = BasicBlock::Create(Context, "omp.setup", FN);
295   ExitBB = BasicBlock::Create(Context, "omp.exit", FN);
296   CheckNextBB = BasicBlock::Create(Context, "omp.checkNext", FN);
297   LoadIVBoundsBB = BasicBlock::Create(Context, "omp.loadIVBounds", FN);
298 
299   DominatorTree &DT = P->getAnalysis<DominatorTreeWrapperPass>().getDomTree();
300   DT.addNewBlock(HeaderBB, PrevBB);
301   DT.addNewBlock(ExitBB, HeaderBB);
302   DT.addNewBlock(CheckNextBB, HeaderBB);
303   DT.addNewBlock(LoadIVBoundsBB, HeaderBB);
304 
305   // Fill up basic block HeaderBB.
306   Builder.SetInsertPoint(HeaderBB);
307   LowerBoundPtr = Builder.CreateAlloca(IntPtrTy, 0, "omp.lowerBoundPtr");
308   UpperBoundPtr = Builder.CreateAlloca(IntPtrTy, 0, "omp.upperBoundPtr");
309   UserContext = Builder.CreateBitCast(FN->arg_begin(), StructData->getType(),
310                                       "omp.userContext");
311 
312   extractValuesFromStruct(Data, UserContext, Map);
313   Builder.CreateBr(CheckNextBB);
314 
315   // Add code to check if another set of iterations will be executed.
316   Builder.SetInsertPoint(CheckNextBB);
317   Ret1 = createCallLoopNext(LowerBoundPtr, UpperBoundPtr);
318   HasNextSchedule = Builder.CreateTrunc(Ret1, Builder.getInt1Ty(),
319                                         "omp.hasNextScheduleBlock");
320   Builder.CreateCondBr(HasNextSchedule, LoadIVBoundsBB, ExitBB);
321 
322   // Add code to to load the iv bounds for this set of iterations.
323   Builder.SetInsertPoint(LoadIVBoundsBB);
324   LowerBound = Builder.CreateLoad(LowerBoundPtr, "omp.lowerBound");
325   UpperBound = Builder.CreateLoad(UpperBoundPtr, "omp.upperBound");
326 
327   // Subtract one as the upper bound provided by openmp is a < comparison
328   // whereas the codegenForSequential function creates a <= comparison.
329   UpperBound = Builder.CreateSub(UpperBound, ConstantInt::get(IntPtrTy, 1),
330                                  "omp.upperBoundAdjusted");
331 
332   Builder.CreateBr(CheckNextBB);
333   Builder.SetInsertPoint(--Builder.GetInsertPoint());
334   LoopInfo &LI = P->getAnalysis<LoopInfo>();
335   IV = createLoop(LowerBound, UpperBound, Stride, Builder, P, LI, DT, AfterBB,
336                   ICmpInst::ICMP_SLE, nullptr, true, /* UseGuard */ false);
337 
338   BasicBlock::iterator LoopBody = Builder.GetInsertPoint();
339   Builder.SetInsertPoint(AfterBB->begin());
340 
341   // Add code to terminate this openmp subfunction.
342   Builder.SetInsertPoint(ExitBB);
343   createCallLoopEndNowait();
344   Builder.CreateRetVoid();
345 
346   Builder.SetInsertPoint(LoopBody);
347   *SubFunction = FN;
348 
349   return IV;
350 }
351 
352 Value *OMPGenerator::createParallelLoop(Value *LowerBound, Value *UpperBound,
353                                         Value *Stride,
354                                         SetVector<Value *> &Values,
355                                         ValueToValueMapTy &Map,
356                                         BasicBlock::iterator *LoopBody) {
357   Value *Struct, *IV, *SubfunctionParam, *NumberOfThreads;
358   Function *SubFunction;
359 
360   Struct = loadValuesIntoStruct(Values);
361 
362   BasicBlock::iterator PrevInsertPoint = Builder.GetInsertPoint();
363   IV = createSubfunction(Stride, Struct, Values, Map, &SubFunction);
364   *LoopBody = Builder.GetInsertPoint();
365   Builder.SetInsertPoint(PrevInsertPoint);
366 
367   // Create call for GOMP_parallel_loop_runtime_start.
368   SubfunctionParam =
369       Builder.CreateBitCast(Struct, Builder.getInt8PtrTy(), "omp_data");
370 
371   NumberOfThreads = Builder.getInt32(0);
372 
373   // Add one as the upper bound provided by openmp is a < comparison
374   // whereas the codegenForSequential function creates a <= comparison.
375   UpperBound =
376       Builder.CreateAdd(UpperBound, ConstantInt::get(getIntPtrTy(), 1));
377 
378   createCallParallelLoopStart(SubFunction, SubfunctionParam, NumberOfThreads,
379                               LowerBound, UpperBound, Stride);
380   Builder.CreateCall(SubFunction, SubfunctionParam);
381   createCallParallelEnd();
382 
383   return IV;
384 }
385