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