1 //===------ LoopGenerators.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 scalar loops and orchestrate the
10 // creation of parallel loops as LLVM-IR.
11 //
12 //===----------------------------------------------------------------------===//
13
14 #include "polly/CodeGen/LoopGenerators.h"
15 #include "polly/Options.h"
16 #include "polly/ScopDetection.h"
17 #include "llvm/Analysis/LoopInfo.h"
18 #include "llvm/IR/DataLayout.h"
19 #include "llvm/IR/DebugInfoMetadata.h"
20 #include "llvm/IR/Dominators.h"
21 #include "llvm/IR/Module.h"
22 #include "llvm/Support/CommandLine.h"
23 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
24
25 using namespace llvm;
26 using namespace polly;
27
28 int polly::PollyNumThreads;
29 OMPGeneralSchedulingType polly::PollyScheduling;
30 int polly::PollyChunkSize;
31
32 static cl::opt<int, true>
33 XPollyNumThreads("polly-num-threads",
34 cl::desc("Number of threads to use (0 = auto)"),
35 cl::Hidden, cl::location(polly::PollyNumThreads),
36 cl::init(0), cl::cat(PollyCategory));
37
38 static cl::opt<OMPGeneralSchedulingType, true> XPollyScheduling(
39 "polly-scheduling",
40 cl::desc("Scheduling type of parallel OpenMP for loops"),
41 cl::values(clEnumValN(OMPGeneralSchedulingType::StaticChunked, "static",
42 "Static scheduling"),
43 clEnumValN(OMPGeneralSchedulingType::Dynamic, "dynamic",
44 "Dynamic scheduling"),
45 clEnumValN(OMPGeneralSchedulingType::Guided, "guided",
46 "Guided scheduling"),
47 clEnumValN(OMPGeneralSchedulingType::Runtime, "runtime",
48 "Runtime determined (OMP_SCHEDULE)")),
49 cl::Hidden, cl::location(polly::PollyScheduling),
50 cl::init(OMPGeneralSchedulingType::Runtime), cl::Optional,
51 cl::cat(PollyCategory));
52
53 static cl::opt<int, true>
54 XPollyChunkSize("polly-scheduling-chunksize",
55 cl::desc("Chunksize to use by the OpenMP runtime calls"),
56 cl::Hidden, cl::location(polly::PollyChunkSize),
57 cl::init(0), cl::Optional, cl::cat(PollyCategory));
58
59 // We generate a loop of either of the following structures:
60 //
61 // BeforeBB BeforeBB
62 // | |
63 // v v
64 // GuardBB PreHeaderBB
65 // / | | _____
66 // __ PreHeaderBB | v \/ |
67 // / \ / | HeaderBB latch
68 // latch HeaderBB | |\ |
69 // \ / \ / | \------/
70 // < \ / |
71 // \ / v
72 // ExitBB ExitBB
73 //
74 // depending on whether or not we know that it is executed at least once. If
75 // not, GuardBB checks if the loop is executed at least once. If this is the
76 // case we branch to PreHeaderBB and subsequently to the HeaderBB, which
77 // contains the loop iv 'polly.indvar', the incremented loop iv
78 // 'polly.indvar_next' as well as the condition to check if we execute another
79 // iteration of the loop. After the loop has finished, we branch to ExitBB.
80 // We expect the type of UB, LB, UB+Stride to be large enough for values that
81 // UB may take throughout the execution of the loop, including the computation
82 // of indvar + Stride before the final abort.
createLoop(Value * LB,Value * UB,Value * Stride,PollyIRBuilder & Builder,LoopInfo & LI,DominatorTree & DT,BasicBlock * & ExitBB,ICmpInst::Predicate Predicate,ScopAnnotator * Annotator,bool Parallel,bool UseGuard,bool LoopVectDisabled)83 Value *polly::createLoop(Value *LB, Value *UB, Value *Stride,
84 PollyIRBuilder &Builder, LoopInfo &LI,
85 DominatorTree &DT, BasicBlock *&ExitBB,
86 ICmpInst::Predicate Predicate,
87 ScopAnnotator *Annotator, bool Parallel, bool UseGuard,
88 bool LoopVectDisabled) {
89 Function *F = Builder.GetInsertBlock()->getParent();
90 LLVMContext &Context = F->getContext();
91
92 assert(LB->getType() == UB->getType() && "Types of loop bounds do not match");
93 IntegerType *LoopIVType = dyn_cast<IntegerType>(UB->getType());
94 assert(LoopIVType && "UB is not integer?");
95
96 BasicBlock *BeforeBB = Builder.GetInsertBlock();
97 BasicBlock *GuardBB =
98 UseGuard ? BasicBlock::Create(Context, "polly.loop_if", F) : nullptr;
99 BasicBlock *HeaderBB = BasicBlock::Create(Context, "polly.loop_header", F);
100 BasicBlock *PreHeaderBB =
101 BasicBlock::Create(Context, "polly.loop_preheader", F);
102
103 // Update LoopInfo
104 Loop *OuterLoop = LI.getLoopFor(BeforeBB);
105 Loop *NewLoop = LI.AllocateLoop();
106
107 if (OuterLoop)
108 OuterLoop->addChildLoop(NewLoop);
109 else
110 LI.addTopLevelLoop(NewLoop);
111
112 if (OuterLoop) {
113 if (GuardBB)
114 OuterLoop->addBasicBlockToLoop(GuardBB, LI);
115 OuterLoop->addBasicBlockToLoop(PreHeaderBB, LI);
116 }
117
118 NewLoop->addBasicBlockToLoop(HeaderBB, LI);
119
120 // Notify the annotator (if present) that we have a new loop, but only
121 // after the header block is set.
122 if (Annotator)
123 Annotator->pushLoop(NewLoop, Parallel);
124
125 // ExitBB
126 ExitBB = SplitBlock(BeforeBB, &*Builder.GetInsertPoint(), &DT, &LI);
127 ExitBB->setName("polly.loop_exit");
128
129 // BeforeBB
130 if (GuardBB) {
131 BeforeBB->getTerminator()->setSuccessor(0, GuardBB);
132 DT.addNewBlock(GuardBB, BeforeBB);
133
134 // GuardBB
135 Builder.SetInsertPoint(GuardBB);
136 Value *LoopGuard;
137 LoopGuard = Builder.CreateICmp(Predicate, LB, UB);
138 LoopGuard->setName("polly.loop_guard");
139 Builder.CreateCondBr(LoopGuard, PreHeaderBB, ExitBB);
140 DT.addNewBlock(PreHeaderBB, GuardBB);
141 } else {
142 BeforeBB->getTerminator()->setSuccessor(0, PreHeaderBB);
143 DT.addNewBlock(PreHeaderBB, BeforeBB);
144 }
145
146 // PreHeaderBB
147 Builder.SetInsertPoint(PreHeaderBB);
148 Builder.CreateBr(HeaderBB);
149
150 // HeaderBB
151 DT.addNewBlock(HeaderBB, PreHeaderBB);
152 Builder.SetInsertPoint(HeaderBB);
153 PHINode *IV = Builder.CreatePHI(LoopIVType, 2, "polly.indvar");
154 IV->addIncoming(LB, PreHeaderBB);
155 Stride = Builder.CreateZExtOrBitCast(Stride, LoopIVType);
156 Value *IncrementedIV = Builder.CreateNSWAdd(IV, Stride, "polly.indvar_next");
157 Value *LoopCondition =
158 Builder.CreateICmp(Predicate, IncrementedIV, UB, "polly.loop_cond");
159
160 // Create the loop latch and annotate it as such.
161 BranchInst *B = Builder.CreateCondBr(LoopCondition, HeaderBB, ExitBB);
162 if (Annotator)
163 Annotator->annotateLoopLatch(B, NewLoop, Parallel, LoopVectDisabled);
164
165 IV->addIncoming(IncrementedIV, HeaderBB);
166 if (GuardBB)
167 DT.changeImmediateDominator(ExitBB, GuardBB);
168 else
169 DT.changeImmediateDominator(ExitBB, HeaderBB);
170
171 // The loop body should be added here.
172 Builder.SetInsertPoint(HeaderBB->getFirstNonPHI());
173 return IV;
174 }
175
createParallelLoop(Value * LB,Value * UB,Value * Stride,SetVector<Value * > & UsedValues,ValueMapT & Map,BasicBlock::iterator * LoopBody)176 Value *ParallelLoopGenerator::createParallelLoop(
177 Value *LB, Value *UB, Value *Stride, SetVector<Value *> &UsedValues,
178 ValueMapT &Map, BasicBlock::iterator *LoopBody) {
179
180 AllocaInst *Struct = storeValuesIntoStruct(UsedValues);
181 BasicBlock::iterator BeforeLoop = Builder.GetInsertPoint();
182
183 Value *IV;
184 Function *SubFn;
185 std::tie(IV, SubFn) = createSubFn(Stride, Struct, UsedValues, Map);
186 *LoopBody = Builder.GetInsertPoint();
187 Builder.SetInsertPoint(&*BeforeLoop);
188
189 Value *SubFnParam = Builder.CreateBitCast(Struct, Builder.getInt8PtrTy(),
190 "polly.par.userContext");
191
192 // Add one as the upper bound provided by OpenMP is a < comparison
193 // whereas the codegenForSequential function creates a <= comparison.
194 UB = Builder.CreateAdd(UB, ConstantInt::get(LongType, 1));
195
196 // Execute the prepared subfunction in parallel.
197 deployParallelExecution(SubFn, SubFnParam, LB, UB, Stride);
198
199 return IV;
200 }
201
createSubFnDefinition()202 Function *ParallelLoopGenerator::createSubFnDefinition() {
203 Function *F = Builder.GetInsertBlock()->getParent();
204 Function *SubFn = prepareSubFnDefinition(F);
205
206 // Certain backends (e.g., NVPTX) do not support '.'s in function names.
207 // Hence, we ensure that all '.'s are replaced by '_'s.
208 std::string FunctionName = SubFn->getName().str();
209 std::replace(FunctionName.begin(), FunctionName.end(), '.', '_');
210 SubFn->setName(FunctionName);
211
212 // Do not run any polly pass on the new function.
213 SubFn->addFnAttr(PollySkipFnAttr);
214
215 return SubFn;
216 }
217
218 AllocaInst *
storeValuesIntoStruct(SetVector<Value * > & Values)219 ParallelLoopGenerator::storeValuesIntoStruct(SetVector<Value *> &Values) {
220 SmallVector<Type *, 8> Members;
221
222 for (Value *V : Values)
223 Members.push_back(V->getType());
224
225 const DataLayout &DL = Builder.GetInsertBlock()->getModule()->getDataLayout();
226
227 // We do not want to allocate the alloca inside any loop, thus we allocate it
228 // in the entry block of the function and use annotations to denote the actual
229 // live span (similar to clang).
230 BasicBlock &EntryBB = Builder.GetInsertBlock()->getParent()->getEntryBlock();
231 Instruction *IP = &*EntryBB.getFirstInsertionPt();
232 StructType *Ty = StructType::get(Builder.getContext(), Members);
233 AllocaInst *Struct = new AllocaInst(Ty, DL.getAllocaAddrSpace(), nullptr,
234 "polly.par.userContext", IP);
235
236 for (unsigned i = 0; i < Values.size(); i++) {
237 Value *Address = Builder.CreateStructGEP(Ty, Struct, i);
238 Address->setName("polly.subfn.storeaddr." + Values[i]->getName());
239 Builder.CreateStore(Values[i], Address);
240 }
241
242 return Struct;
243 }
244
extractValuesFromStruct(SetVector<Value * > OldValues,Type * Ty,Value * Struct,ValueMapT & Map)245 void ParallelLoopGenerator::extractValuesFromStruct(
246 SetVector<Value *> OldValues, Type *Ty, Value *Struct, ValueMapT &Map) {
247 for (unsigned i = 0; i < OldValues.size(); i++) {
248 Value *Address = Builder.CreateStructGEP(Ty, Struct, i);
249 Type *ElemTy = cast<GetElementPtrInst>(Address)->getResultElementType();
250 Value *NewValue = Builder.CreateLoad(ElemTy, Address);
251 NewValue->setName("polly.subfunc.arg." + OldValues[i]->getName());
252 Map[OldValues[i]] = NewValue;
253 }
254 }
255
createDebugLocForGeneratedCode(Function * F)256 DebugLoc polly::createDebugLocForGeneratedCode(Function *F) {
257 if (!F)
258 return DebugLoc();
259
260 LLVMContext &Ctx = F->getContext();
261 DISubprogram *DILScope =
262 dyn_cast_or_null<DISubprogram>(F->getMetadata(LLVMContext::MD_dbg));
263 if (!DILScope)
264 return DebugLoc();
265 return DILocation::get(Ctx, 0, 0, DILScope);
266 }
267