Coverage Report

Created: 2017-10-03 07:32

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